| NEmitter.java |
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