1
3 package jminusminus;
4
5 import java.io.PrintWriter;
6 import java.util.ArrayList;
7
8 import static jminusminus.CLConstants.*;
9 import static jminusminus.NPhysicalRegister.*;
10
11
15 abstract class NLIRInstruction {
16
20 protected static String[] lirMnemonic;
21
22 static {
23 lirMnemonic = new String[256];
24 lirMnemonic[IADD] = "ADD";
25 lirMnemonic[IMUL] = "MUL";
26 lirMnemonic[ISUB] = "SUB";
27 lirMnemonic[MULTIANEWARRAY] = "MULTIANEWARRAY";
28 lirMnemonic[AALOAD] = "AALOAD";
29 lirMnemonic[IALOAD] = "IALOAD";
30 lirMnemonic[IASTORE] = "IASTORE";
31 lirMnemonic[IF_ICMPNE] = "NE";
32 lirMnemonic[IF_ICMPGT] = "GT";
33 lirMnemonic[IF_ICMPLE] = "LE";
34 lirMnemonic[GETSTATIC] = "GETSTATIC";
35 lirMnemonic[PUTSTATIC] = "PUTSTATIC";
36 lirMnemonic[INVOKESPECIAL] = "INVOKESPECIAL";
37 lirMnemonic[INVOKESTATIC] = "INVOKESTATIC";
38 }
39
40
43 public NBasicBlock block;
44
45
48 public int id;
49
50
53 public ArrayList<NRegister> reads;
54
55
58 public NRegister write;
59
60
66 protected NLIRInstruction(NBasicBlock block, int id) {
67 this.block = block;
68 this.id = id;
69 reads = new ArrayList<NRegister>();
70 }
71
72
76 public void allocatePhysicalRegisters() {
77 }
79
80
85 public void toSpim(PrintWriter out) {
86 }
88
89
94 public String toString() {
95 return "" + id;
96 }
97 }
98
99
102 class NLIRArithmetic extends NLIRInstruction {
103 private int opcode;
105
106
115 public NLIRArithmetic(NBasicBlock block, int id, int opcode, NLIRInstruction lhs,
116 NLIRInstruction rhs) {
117 super(block, id);
118 this.opcode = opcode;
119 reads.add(lhs.write);
120 reads.add(rhs.write);
121 write = new NVirtualRegister(NControlFlowGraph.regId++, "I", "I");
122 block.cfg.registers.add((NVirtualRegister) write);
123 }
124
125
128 public void allocatePhysicalRegisters() {
129 NInterval input1 = block.cfg.intervals.get(reads.get(0).number()).childAt(id);
130 NInterval input2 = block.cfg.intervals.get(reads.get(1).number()).childAt(id);
131 NInterval output = block.cfg.intervals.get(write.number()).childAt(id);
132 reads.set(0, input1.pRegister);
133 reads.set(1, input2.pRegister);
134 write = output.pRegister;
135 }
136
137
140 public void toSpim(PrintWriter out) {
141 switch (opcode) {
142 case IADD:
143 out.printf(" add %s,%s,%s\n", write, reads.get(0), reads.get(1));
144 break;
145 case ISUB:
146 out.printf(" sub %s,%s,%s\n", write, reads.get(0), reads.get(1));
147 break;
148 case IMUL:
149 out.printf(" mul %s,%s,%s\n", write, reads.get(0), reads.get(1));
150 break;
151 }
152 }
153
154
157 public String toString() {
158 return id + ": " + lirMnemonic[opcode] + " " + reads.get(0) + " " + reads.get(1) +
159 " " + write;
160 }
161 }
162
163
166 class NLIRIntConstant extends NLIRInstruction {
167 private int value;
169
170
177 public NLIRIntConstant(NBasicBlock block, int id, int value) {
178 super(block, id);
179 this.value = value;
180 write = new NVirtualRegister(NControlFlowGraph.regId++, "I", "I");
181 block.cfg.registers.add((NVirtualRegister) write);
182 }
183
184
187 public void allocatePhysicalRegisters() {
188 NInterval output = block.cfg.intervals.get(write.number()).childAt(id);
189 write = output.pRegister;
190 }
191
192
195 public void toSpim(PrintWriter out) {
196 out.printf(" li %s,%d\n", write, value);
197 }
198
199
202 public String toString() {
203 return id + ": LDC [" + value + "] " + write;
204 }
205 }
206
207
210 class NLIRStringConstant extends NLIRInstruction {
211 private String value;
213
214 private static int labelSuffix;
216
217
224 public NLIRStringConstant(NBasicBlock block, int id, String value) {
225 super(block, id);
226 this.value = value;
227 write = new NVirtualRegister(NControlFlowGraph.regId++, "L", "Ljava/lang/String;");
228 block.cfg.registers.add((NVirtualRegister) write);
229 labelSuffix = 0;
230 }
231
232
237 private String createLabel() {
238 return "Constant..String" + labelSuffix++;
239 }
240
241
244 public void allocatePhysicalRegisters() {
245 NInterval output = block.cfg.intervals.get(write.number()).childAt(id);
246 write = output.pRegister;
247 }
248
249
252 public void toSpim(PrintWriter out) {
253 String label = createLabel();
254 String s = label + ":\n";
255 int size = 12 + value.length() + 1;
256 int align = (size % 4 == 0) ? 0 : (size + 4) / 4 * 4 - size;
257 s += " .word 2 # Tag 2 indicates a string\n";
258 s += " .word " + (size + align) + " # Size of object in bytes\n";
259 s += " .word " + value.length() + " # String length (not including null terminator)\n";
260 s += " .asciiz \"" + value + "\" # String terminated by null character 0\n";
261 s += " .align " + align + " # Next object is on a word boundary\n";
262 block.cfg.data.add(s);
263 out.printf(" la %s,%s+12\n", write, label);
264 }
265
266
269 public String toString() {
270 return id + ": LDC [\"" + value + "\"] " + write;
271 }
272 }
273
274
277 class NLIRConditionalJump extends NLIRInstruction {
278 private int opcode;
280
281 private NBasicBlock onTrueDestination;
283
284 private NBasicBlock onFalseDestination;
286
287
298 public NLIRConditionalJump(NBasicBlock block, int id, NLIRInstruction lhs,
299 NLIRInstruction rhs, int opcode, NBasicBlock onTrueDestination,
300 NBasicBlock onFalseDestination) {
301 super(block, id);
302 this.opcode = opcode;
303 reads.add(lhs.write);
304 reads.add(rhs.write);
305 this.onTrueDestination = onTrueDestination;
306 this.onFalseDestination = onFalseDestination;
307 }
308
309
312 public void allocatePhysicalRegisters() {
313 NInterval input1 = block.cfg.intervals.get(reads.get(0).number()).childAt(id);
314 NInterval input2 = block.cfg.intervals.get(reads.get(1).number()).childAt(id);
315 reads.set(0, input1.pRegister);
316 reads.set(1, input2.pRegister);
317 }
318
319
322 public void toSpim(PrintWriter out) {
323 switch (opcode) {
324 case IF_ICMPNE:
325 out.printf(" bne %s,%s,%s\n", reads.get(0), reads.get(1),
326 block.cfg.labelPrefix + "." + onTrueDestination.id);
327 break;
328 case IF_ICMPGT:
329 out.printf(" bgt %s,%s,%s\n", reads.get(0), reads.get(1),
330 block.cfg.labelPrefix + "." + onTrueDestination.id);
331 break;
332 case IF_ICMPLE:
333 out.printf(" ble %s,%s,%s\n", reads.get(0), reads.get(1),
334 block.cfg.labelPrefix + "." + onTrueDestination.id);
335 break;
336 }
337 out.printf(" j %s\n", block.cfg.labelPrefix + "." + onFalseDestination.id);
338 }
339
340
343 public String toString() {
344 return id + ": BRANCH [" + lirMnemonic[opcode] + "] " + reads.get(0)
345 + " " + reads.get(1) + " " + onTrueDestination.id();
346 }
347 }
348
349
352 class NLIRGoto extends NLIRInstruction {
353 private NBasicBlock destination;
355
356
363 public NLIRGoto(NBasicBlock block, int id, NBasicBlock destination) {
364 super(block, id);
365 this.destination = destination;
366 }
367
368
371 public void toSpim(PrintWriter out) {
372 String label = block.cfg.labelPrefix + "." + destination.id;
373 out.printf(" j %s\n", label);
374 }
375
376
379 public String toString() {
380 return id + ": BRANCH " + destination.id();
381 }
382 }
383
384
387 class NLIRInvoke extends NLIRInstruction {
388 private int opcode;
390
391 private String target;
393
394 private String name;
396
397
409 public NLIRInvoke(NBasicBlock block, int id, int opcode, String target, String name,
410 ArrayList<NRegister> arguments, String sType, String lType) {
411 super(block, id);
412 this.opcode = opcode;
413 this.target = target;
414 this.name = name;
415 for (NRegister arg : arguments) {
416 reads.add(arg);
417 }
418 if (!sType.equals("V")) {
419 write = NPhysicalRegister.regInfo[V0];
420 block.cfg.registers.set(V0, write);
421 }
422 }
423
424
427 public void allocatePhysicalRegisters() {
428 for (int i = 0; i < reads.size(); i++) {
429 NInterval input = block.cfg.intervals.get(reads.get(i).number()).childAt(id);
430 reads.set(i, input.pRegister);
431 }
432 }
433
434
437 public void toSpim(PrintWriter out) {
438 out.printf(" jal %s.%s\n", target.replace("/", "."),
439 name.equals("<init>") ? "__init__" : name);
440 }
441
442
445 public String toString() {
446 String s = id + ": " + lirMnemonic[opcode] + " " +
447 (write != null ? write + " = " : "") + target + "." + name + "( ";
448 for (NRegister input : reads) {
449 s += input + " ";
450 }
451 s += ")";
452 return s;
453 }
454 }
455
456
459 class NLIRReturn extends NLIRInstruction {
460 private int opcode;
462
463
471 public NLIRReturn(NBasicBlock block, int id, int opcode, NPhysicalRegister result) {
472 super(block, id);
473 this.opcode = opcode;
474 if (result != null) {
475 reads.add(result);
476 }
477 }
478
479
482 public void toSpim(PrintWriter out) {
483 out.printf(" j %s\n", block.cfg.labelPrefix + ".restore");
484 }
485
486
489 public String toString() {
490 if (reads.size() == 0) {
491 return id + ": RETURN";
492 }
493 return id + ": RETURN " + reads.get(0);
494 }
495 }
496
497
500 class NLIRPutField extends NLIRInstruction {
501 private int opcode;
503
504 private String target;
506
507 private String name;
509
510
522 public NLIRPutField(NBasicBlock block, int id, int opcode, String target, String name,
523 String sType, String lType, NLIRInstruction value) {
524 super(block, id);
525 this.opcode = opcode;
526 this.target = target;
527 this.name = name;
528 reads.add(value.write);
529 }
530
531
534 public void toSpim(PrintWriter out) {
535 out.printf(" NLIRPutField.toSpim() not yet implemented!\n");
536 }
537
538
541 public String toString() {
542 return id + ": " + lirMnemonic[opcode] + " " + target + "." + name + " = " + reads.get(0);
543 }
544 }
545
546
549 class NLIRGetField extends NLIRInstruction {
550 private int opcode;
552
553 private String target;
555
556 private String name;
558
559
570 public NLIRGetField(NBasicBlock block, int id, int opcode, String target, String name,
571 String sType, String lType) {
572 super(block, id);
573 this.opcode = opcode;
574 this.target = target;
575 this.name = name;
576 write = new NVirtualRegister(NControlFlowGraph.regId++, sType, lType);
577 block.cfg.registers.add((NVirtualRegister) write);
578 }
579
580
583 public void toSpim(PrintWriter out) {
584 out.printf(" NLIRGetField.toSpim() not yet implemented!\n");
585 }
586
587
590 public String toString() {
591 return id + ": " + lirMnemonic[opcode] + " " + write + " = " + target + "." + name;
592 }
593 }
594
595
598 class NLIRNewArray extends NLIRInstruction {
599 private int opcode;
601
602 private int dim;
604
605
615 public NLIRNewArray(NBasicBlock block, int id, int opcode, int dim, String sType,
616 String lType) {
617 super(block, id);
618 this.opcode = opcode;
619 this.dim = dim;
620 write = new NVirtualRegister(NControlFlowGraph.regId++, sType, lType);
621 block.cfg.registers.add((NVirtualRegister) write);
622 }
623
624
627 public void toSpim(PrintWriter out) {
628 out.printf(" NLIRNewArray.toSpim() not yet implemented!\n");
629 }
630
631
634 public String toString() {
635 return id + ": " + lirMnemonic[opcode] + " [" + dim + "]" + " " + write;
636 }
637 }
638
639
642 class NLIRALoad extends NLIRInstruction {
643 private int opcode;
645
646
657 public NLIRALoad(NBasicBlock block, int id, int opcode,
658 NLIRInstruction arrayRef, NLIRInstruction index, String sType,
659 String lType) {
660 super(block, id);
661 this.opcode = opcode;
662 reads.add(arrayRef.write);
663 reads.add(index.write);
664 write = new NVirtualRegister(NControlFlowGraph.regId++, sType, lType);
665 block.cfg.registers.add((NVirtualRegister) write);
666 }
667
668
671
672 public void toSpim(PrintWriter out) {
673 out.printf(" NLIRALoad.toSpim() not yet implemented!\n");
674 }
675
676
679
680 public String toString() {
681 return id + ": " + lirMnemonic[opcode] + " " + write + "= " + reads.get(0) + "[" +
682 reads.get(1) + "]";
683 }
684 }
685
686
689 class NLIRAStore extends NLIRInstruction {
690 private int opcode;
692
693
705 public NLIRAStore(NBasicBlock block, int id, int opcode, NLIRInstruction arrayRef,
706 NLIRInstruction index, NLIRInstruction value, String sType, String lType) {
707 super(block, id);
708 this.opcode = opcode;
709 reads.add(arrayRef.write);
710 reads.add(index.write);
711 reads.add(value.write);
712 }
713
714
717 public void toSpim(PrintWriter out) {
718 out.printf(" NLIRAStore.toSpim() not yet implemented!\n");
719 }
720
721
724 public String toString() {
725 return id + ": " + lirMnemonic[opcode] + " " + reads.get(0) + "[" + reads.get(1) + "] = " +
726 reads.get(2);
727 }
728 }
729
730
733 class NLIRPhiFunction extends NLIRInstruction {
734
742 public NLIRPhiFunction(NBasicBlock block, int id, String sType, String lType) {
743 super(block, id);
744 write = new NVirtualRegister(NControlFlowGraph.regId++, sType, lType);
745 block.cfg.registers.add((NVirtualRegister) write);
746 }
747
748
751 public String toString() {
752 return id + ": phi " + write;
753 }
754 }
755
756
759 class NLIRMove extends NLIRInstruction {
760
768 public NLIRMove(NBasicBlock block, int id, NLIRInstruction from, NLIRInstruction to) {
769 super(block, id);
770 reads.add(from.write);
771 write = to.write;
772 }
773
774
782 public NLIRMove(NBasicBlock block, int id, NRegister from, NRegister to) {
783 super(block, id);
784 reads.add(from);
785 write = to;
786 }
787
788
791 public void allocatePhysicalRegisters() {
792 NInterval input = block.cfg.intervals.get(reads.get(0).number()).childAt(id);
793 NInterval output = block.cfg.intervals.get(write.number()).childAt(id);
794 reads.set(0, input.pRegister);
795 write = output.pRegister;
796 }
797
798
801 public void toSpim(PrintWriter out) {
802 out.printf(" move %s,%s\n", write, reads.get(0));
803 }
804
805
808 public String toString() {
809 return id + ": MOVE " + reads.get(0) + " " + write;
810 }
811 }
812
813
816 class NLIRLoadLocal extends NLIRInstruction {
817 private int local;
819
820
829 public NLIRLoadLocal(NBasicBlock block, int id, int local, String sType, String lType) {
830 super(block, id);
831 this.local = local;
832 if (local < 4) {
833 write = NPhysicalRegister.regInfo[A0 + local];
834 block.cfg.registers.set(A0 + local, NPhysicalRegister.regInfo[A0 + local]);
835 } else {
836 write = new NVirtualRegister(NControlFlowGraph.regId++, sType, lType);
837 block.cfg.registers.add((NVirtualRegister) write);
838 }
839 }
840
841
846 public int getLocal() {
847 return local;
848 }
849
850
853 public String toString() {
854 return id + ": LDLOC " + local + " " + write;
855 }
856 }
857
858
861 class NLIRLoad extends NLIRInstruction {
862 private int offset;
864
865 private OffsetFrom offsetFrom;
867
868 private NRegister register;
870
871
880 public NLIRLoad(NBasicBlock block, int id, int offset, OffsetFrom offsetFrom,
881 NRegister register) {
882 super(block, id);
883 this.offset = offset;
884 this.offsetFrom = offsetFrom;
885 this.register = register;
886 }
887
888
891 public void toSpim(PrintWriter out) {
892 if (offsetFrom == OffsetFrom.FP) {
893 out.printf(" lw %s,%d($fp)\n", register, offset * 4);
894 } else {
895 out.printf(" lw %s,%d($sp)\n", register, offset * 4);
896 }
897 }
898
899
902 public String toString() {
903 return id + ": LOAD " + (offsetFrom == OffsetFrom.FP ? "[frame:" : "[stack:") +
904 offset + "] " + register;
905 }
906 }
907
908
911 class NLIRStore extends NLIRInstruction {
912 private int offset;
914
915 private OffsetFrom offsetFrom;
917
918 private NRegister register;
920
921
930 public NLIRStore(NBasicBlock block, int id, int offset, OffsetFrom offsetFrom,
931 NRegister register) {
932 super(block, id);
933 this.offset = offset;
934 this.offsetFrom = offsetFrom;
935 this.register = register;
936 reads.add(register);
937 }
938
939
942 public void allocatePhysicalRegisters() {
943 NInterval input = block.cfg.intervals.get(reads.get(0).number()).childAt(id);
944 if (input.vRegId >= 32) {
945 reads.set(0, input.pRegister);
946 }
947 }
948
949
952 public void toSpim(PrintWriter out) {
953 if (offsetFrom == OffsetFrom.FP) {
954 out.printf(" sw %s,%d($fp)\n", reads.get(0), offset * 4);
955 } else {
956 out.printf(" sw %s,%d($sp)\n", reads.get(0), offset * 4);
957 }
958 }
959
960
963 public String toString() {
964 return id + ": STORE " + reads.get(0) + " " + (offsetFrom == OffsetFrom.FP ? "[frame:" :
965 "[stack:") + offset + "]";
966 }
967 }
968