1
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
19 public class NEmitter {
20 private String sourceFile;
22
23 private HashMap<CLFile, HashMap<CLMethodInfo, NControlFlowGraph>> classes;
26
27 private String destDir;
29
30 private boolean errorHasOccurred;
32
33
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 NControlFlowGraph cfg = new NControlFlowGraph(cp, m);
55
56 PrettyPrinter p = new PrettyPrinter();
58 p.printf(">>> %s %s\n", cfg.name, cfg.desc);
59 cfg.writeTuplesToStdOut(p);
60
61 cfg.detectLoops(cfg.basicBlocks.get(0), null);
64
65 cfg.removeUnreachableBlocks();
67
68 cfg.computeDominators(cfg.basicBlocks.get(0), null);
70
71 cfg.tuplesToHir();
73
74 cfg.eliminateRedundantPhiFunctions();
77
78 cfg.optimize();
80
81 cfg.writeHirToStdOut(p);
83
84 cfg.hirToLir();
87
88 cfg.resolvePhiFunctions();
90
91 cfg.orderBlocks();
93
94 cfg.renumberLirInstructions();
96
97 cfg.writeLirToStdOut(p);
99
100 methods.put(m, cfg);
103
104 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 cfg.allocatePhysicalRegisters();
118
119 regAllocator.writeLivenessInfoToStdOut(p);
121
122 cfg.writeIntervalsToStdOut(p);
124 }
125
126 classes.put(clFile, methods);
128 }
129 }
130
131
136 public void destinationDir(String destDir) {
137 this.destDir = destDir;
138 }
139
140
145 public boolean errorHasOccurred() {
146 return errorHasOccurred;
147 }
148
149
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 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 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 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 popStackFrame(cfg, out);
199
200 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 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 private void reportEmitterError(String message, Object... args) {
232 System.err.printf("Error: " + message, args);
233 System.err.println();
234 errorHasOccurred = true;
235 }
236
237 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 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
281 class PrettyPrinter {
282 private int indentWidth;
284
285 private int indent;
287
288
291 public PrettyPrinter() {
292 this(2);
293 }
294
295
300 public PrettyPrinter(int indentWidth) {
301 this.indentWidth = indentWidth;
302 indent = 0;
303 }
304
305
308 public void indentRight() {
309 indent += indentWidth;
310 }
311
312
315 public void indentLeft() {
316 if (indent > 0) {
317 indent -= indentWidth;
318 }
319 }
320
321
324 public void println() {
325 doIndent();
326 System.out.println();
327 }
328
329
334
335 public void println(String s) {
336 doIndent();
337 System.out.println(s);
338 }
339
340
345 public void print(String s) {
346 doIndent();
347 System.out.print(s);
348 }
349
350
356 public void printf(String format, Object... args) {
357 doIndent();
358 System.out.printf(format, args);
359 }
360
361 private void doIndent() {
363 for (int i = 0; i < indent; i++) {
364 System.out.print(" ");
365 }
366 }
367 }
368