1   // Copyright 2012- Bill Campbell, Swami Iyer and Bahar Akbal-Delibas
2   
3   package jminusminus;
4   
5   import java.io.BufferedReader;
6   import java.io.FileReader;
7   import java.io.File;
8   import java.io.FileNotFoundException;
9   import java.io.IOException;
10  import java.io.PrintWriter;
11  
12  import java.util.ArrayList;
13  import java.util.Calendar;
14  import java.util.HashMap;
15  
16  /**
17   * A class for generating native SPIM code.
18   */
19  public class NEmitter {
20      // Source program file name.
21      private String sourceFile;
22  
23      // Map of maps, one per class in the compilation unit. Each one of them maps methods in a
24      // class to their control flow graph.
25      private HashMap<CLFile, HashMap<CLMethodInfo, NControlFlowGraph>> classes;
26  
27      // Destination directory for the native SPIM code.
28      private String destDir;
29  
30      // Whether an error occurred while creating/writing SPIM code.
31      private boolean errorHasOccurred;
32  
33      /**
34       * Constructs an NEmitter object.
35       *
36       * @param sourceFile the source j-- program file name.
37       * @param clFiles    list of CLFile objects.
38       * @param ra         register allocation scheme (naive, linear, or graph).
39       */
40      public NEmitter(String sourceFile, ArrayList<CLFile> clFiles, String ra) {
41          this.sourceFile = sourceFile.substring(sourceFile.lastIndexOf(File.separator) + 1);
42          classes = new HashMap<CLFile, HashMap<CLMethodInfo, NControlFlowGraph>>();
43          for (CLFile clFile : clFiles) {
44              CLConstantPool cp = clFile.constantPool;
45              HashMap<CLMethodInfo, NControlFlowGraph> methods =
46                      new HashMap<CLMethodInfo, NControlFlowGraph>();
47  
48              for (int i = 0; i < clFile.methodsCount; i++) {
49                  CLMethodInfo m = clFile.methods.get(i);
50  
51                  // Build a control flow graph (cfg) for this method. Each block in the cfg, at
52                  // the end of this step, has the JVM bytecode translated into tuple
53                  // representation.
54                  NControlFlowGraph cfg = new NControlFlowGraph(cp, m);
55  
56                  // Write the tuples in cfg to standard output.
57                  PrettyPrinter p = new PrettyPrinter();
58                  p.printf(">>> %s %s\n", cfg.name, cfg.desc);
59                  cfg.writeTuplesToStdOut(p);
60  
61                  // Identify blocks in cfg that are loop heads and loop tails. Also, compute
62                  // number of backward branches to blocks.
63                  cfg.detectLoops(cfg.basicBlocks.get(0), null);
64  
65                  // Remove unreachable blocks from cfg.
66                  cfg.removeUnreachableBlocks();
67  
68                  // Compute the dominator of each block in the cfg.
69                  cfg.computeDominators(cfg.basicBlocks.get(0), null);
70  
71                  // Convert the tuples in each block in the cfg to high-level (HIR) instructions.
72                  cfg.tuplesToHir();
73  
74                  // Eliminate redundant phi functions, i.e., replace phi functions of the form x =
75                  // (y, x, x, ..., x) with y.
76                  cfg.eliminateRedundantPhiFunctions();
77  
78                  // Perform optimizations on the high-level instructions.
79                  cfg.optimize();
80  
81                  // Write the HIR instructions in cfg to standard output.
82                  cfg.writeHirToStdOut(p);
83  
84                  // Convert the HIR instructions in each block in the cfg to low-level (LIR)
85                  // instructions.
86                  cfg.hirToLir();
87  
88                  // Resolve phi functions;
89                  cfg.resolvePhiFunctions();
90  
91                  // Compute block order.
92                  cfg.orderBlocks();
93  
94                  // Assign new ids to LIR instructions.
95                  cfg.renumberLirInstructions();
96  
97                  // Write the LIR instructions in cfg to standard output.
98                  cfg.writeLirToStdOut(p);
99  
100                 // Save the cfg for the method in a map keyed in by the CLMethodInfo object for
101                 // the method.
102                 methods.put(m, cfg);
103 
104                 // Perform register allocation.
105                 NRegisterAllocator regAllocator;
106                 if (ra.equals("naive")) {
107                     regAllocator = new NNaiveRegisterAllocator(cfg);
108                 } else if (ra.equals("linear")) {
109                     regAllocator = new NLinearRegisterAllocator(cfg);
110                 } else {
111                     regAllocator = new NGraphRegisterAllocator(cfg);
112                 }
113                 regAllocator.allocation();
114 
115                 // Replace references to virtual registers in LIR instructions with references to
116                 // physical registers.
117                 cfg.allocatePhysicalRegisters();
118 
119                 // Write the liveness information to standard output.
120                 regAllocator.writeLivenessInfoToStdOut(p);
121 
122                 // Write the liveness intervals in cfg to standard output.
123                 cfg.writeIntervalsToStdOut(p);
124             }
125 
126             // Store the cfgs for the methods in this class in a map.
127             classes.put(clFile, methods);
128         }
129     }
130 
131     /**
132      * Sets the destination directory for the SPIM files.
133      *
134      * @param destDir the destination directory.
135      */
136     public void destinationDir(String destDir) {
137         this.destDir = destDir;
138     }
139 
140     /**
141      * Returns true if an emitter error has occurred up to now, and false otherwise.
142      *
143      * @return true if an emitter error has occurred up to now, and false otherwise.
144      */
145     public boolean errorHasOccurred() {
146         return errorHasOccurred;
147     }
148 
149     /**
150      * Writes out SPIM file(s) to the file system. The destination directory for the files can be
151      * set using the destinationDir() method.
152      */
153     public void write() {
154         String file = "";
155         try {
156             file = destDir + File.separator + sourceFile.replace(".java", ".s");
157             PrintWriter out = new PrintWriter(file);
158 
159             // Header.
160             out.printf("# %s\n", file);
161             out.printf("# Source file: %s\n", sourceFile);
162             out.printf("# Compiled: %s\n\n", Calendar.getInstance().getTime().toString());
163 
164             // Translate classes and their methods to SPIM.
165             for (CLFile clFile : classes.keySet()) {
166                 HashMap<CLMethodInfo, NControlFlowGraph> aClass = classes.get(clFile);
167                 CLConstantPool cp = clFile.constantPool;
168                 int nameIndex = ((CLConstantClassInfo) cp.cpItem(clFile.thisClass)).nameIndex;
169                 String className = new String(((CLConstantUtf8Info) cp.cpItem(nameIndex)).b);
170                 for (CLMethodInfo m : aClass.keySet()) {
171                     NControlFlowGraph cfg = aClass.get(m);
172                     String methodName = cfg.name;
173                     String methodDesc = cfg.desc;
174                     if (methodName.equals("<init>")) {
175                         continue;
176                     }
177                     out.printf(".text\n\n");
178                     if (methodName.equals("main") && methodDesc.equals("([Ljava/lang/String;)V")) {
179                         out.printf("%s:\n", methodName);
180                         cfg.labelPrefix = methodName;
181                     } else {
182                         out.printf("%s.%s:\n", className, methodName);
183                         cfg.labelPrefix = className + "." + methodName;
184                     }
185 
186                     // Setup stack frame for this method.
187                     pushStackFrame(cfg, out);
188 
189                     for (NBasicBlock block : cfg.basicBlocks) {
190                         out.printf("%s.%d:\n", cfg.labelPrefix, block.id);
191                         for (NLIRInstruction lir : block.lir) {
192                             lir.toSpim(out);
193                         }
194                         out.printf("\n");
195                     }
196 
197                     // Pop the stack frame for this method.
198                     popStackFrame(cfg, out);
199 
200                     // Data segment for this cfg storing string literals.
201                     if (cfg.data.size() > 0) {
202                         out.printf(".data\n\n");
203                         for (String line : cfg.data) {
204                             out.printf(line);
205                         }
206                     }
207 
208                     out.printf("\n\n");
209                 }
210             }
211 
212             // Emit SPIM runtime code (just SPIM.s for now).
213             out.printf("# SPIM Runtime\n\n");
214             String runtimeFile = String.format("%s/j--/src/jminusminus/SPIM.s", System.getenv("j"));
215             BufferedReader in = new BufferedReader(new FileReader(runtimeFile));
216             String line;
217             while ((line = in.readLine()) != null) {
218                 out.printf("%s\n", line);
219             }
220             in.close();
221 
222             out.close();
223         } catch (FileNotFoundException e) {
224             reportEmitterError("File %s not found", file);
225         } catch (IOException e) {
226             reportEmitterError("Cannot write to file %s", file);
227         }
228     }
229 
230     // Reports any error that occurs while creating/writing the spim file, to standard error.
231     private void reportEmitterError(String message, Object... args) {
232         System.err.printf("Error: " + message, args);
233         System.err.println();
234         errorHasOccurred = true;
235     }
236 
237     // Emits SPIM code to setup a stack frame for the procedure denoted by cfg. This involves
238     // saving the return address (ra), saving the frame pointer (fp), saving any physical
239     // registers (t0, ..., t9, s0, ..., s7) used by the procedure, and setting up the new value
240     // for fp (i.e. pushing a stack frame).
241     private void pushStackFrame(NControlFlowGraph cfg, PrintWriter out) {
242         int frameSize = cfg.pRegisters.size() * 4 + cfg.offset * 4 + 8;
243         out.printf("    subu    $sp,$sp,%d \t # Stack frame is %d bytes long\n", frameSize,
244                 frameSize);
245         out.printf("    sw      $ra,%d($sp) \t # Save return address\n", frameSize - 4);
246         out.printf("    sw      $fp,%d($sp) \t # Save frame pointer\n", frameSize - 8);
247         int i = 12;
248         for (NPhysicalRegister pRegister : cfg.pRegisters) {
249             out.printf("    sw      %s,%d($sp) \t # Save register %s\n", pRegister, frameSize - i
250                     , pRegister);
251             i += 4;
252         }
253         out.printf("    addiu   $fp,$sp,%d \t # Save frame pointer\n", frameSize - 4);
254         out.println();
255     }
256 
257     // Emits SPIM code to pop the stack frame that was setup for the procedure denoted by cfg.
258     // This involves restoring the return address (ra), the frame pointer (fp), any physical
259     // registers (t0, ..., t9, s0, ..., s7) used by the procedure, setting fp to the restored
260     // value (i.e. popping the stack frame), and finally jumping to ra (the caller).
261     private void popStackFrame(NControlFlowGraph cfg, PrintWriter out) {
262         int frameSize = cfg.pRegisters.size() * 4 + cfg.offset * 4 + 8;
263         out.printf("%s.restore:\n", cfg.labelPrefix);
264         out.printf("    lw      $ra,%d($sp) \t # Restore return address\n", frameSize - 4);
265         out.printf("    lw      $fp,%d($sp) \t # Restore frame pointer\n", frameSize - 8);
266         int i = 12;
267         for (NPhysicalRegister pRegister : cfg.pRegisters) {
268             out.printf("    lw      %s,%d($sp) \t # Restore register %s\n", pRegister,
269                     frameSize - i, pRegister);
270             i += 4;
271         }
272         out.printf("    addiu   $sp,$sp,%d \t # Pop stack\n", frameSize);
273         out.printf("    jr      $ra \t # Return to caller\n", frameSize);
274         out.println();
275     }
276 }
277 
278 /**
279  * A utility class that allows pretty (indented) printing to standard output.
280  */
281 class PrettyPrinter {
282     // Width of an indentation.
283     private int indentWidth;
284 
285     // Current indentation (number of blank spaces).
286     private int indent;
287 
288     /**
289      * Constructs a pretty printer with an indentation width of 2.
290      */
291     public PrettyPrinter() {
292         this(2);
293     }
294 
295     /**
296      * Constructs a pretty printer.
297      *
298      * @param indentWidth number of blank spaces for an indent.
299      */
300     public PrettyPrinter(int indentWidth) {
301         this.indentWidth = indentWidth;
302         indent = 0;
303     }
304 
305     /**
306      * Indents right.
307      */
308     public void indentRight() {
309         indent += indentWidth;
310     }
311 
312     /**
313      * Indents left.
314      */
315     public void indentLeft() {
316         if (indent > 0) {
317             indent -= indentWidth;
318         }
319     }
320 
321     /**
322      * Prints an empty line to standard output.
323      */
324     public void println() {
325         doIndent();
326         System.out.println();
327     }
328 
329     /**
330      * Prints the specified string (followed by a newline) to standard output.
331      *
332      * @param s string to print.
333      */
334 
335     public void println(String s) {
336         doIndent();
337         System.out.println(s);
338     }
339 
340     /**
341      * Prints the specified string to standard output.
342      *
343      * @param s string to print.
344      */
345     public void print(String s) {
346         doIndent();
347         System.out.print(s);
348     }
349 
350     /**
351      * Prints args to standard output according to the specified format.
352      *
353      * @param format format specifier.
354      * @param args   values to print.
355      */
356     public void printf(String format, Object... args) {
357         doIndent();
358         System.out.printf(format, args);
359     }
360 
361     // Indents by printing spaces to standard output.
362     private void doIndent() {
363         for (int i = 0; i < indent; i++) {
364             System.out.print(" ");
365         }
366     }
367 }
368