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