1
3 package jminusminus;
4
5 import static jminusminus.CLConstants.*;
6 import static jminusminus.NPhysicalRegister.*;
7 import java.io.PrintWriter;
8 import java.util.ArrayList;
9
10
13
14 abstract class NLIRInstruction {
15
16
20 protected static String[] lirMnemonic;
21 static {
22 lirMnemonic = new String[256];
23 lirMnemonic[IADD] = "ADD";
24 lirMnemonic[IMUL] = "MUL";
25 lirMnemonic[ISUB] = "SUB";
26 lirMnemonic[MULTIANEWARRAY] = "MULTIANEWARRAY";
27 lirMnemonic[AALOAD] = "AALOAD";
28 lirMnemonic[IALOAD] = "IALOAD";
29 lirMnemonic[IASTORE] = "IASTORE";
30 lirMnemonic[IF_ICMPNE] = "NE";
31 lirMnemonic[IF_ICMPGT] = "GT";
32 lirMnemonic[IF_ICMPLE] = "LE";
33 lirMnemonic[GETSTATIC] = "GETSTATIC";
34 lirMnemonic[PUTSTATIC] = "PUTSTATIC";
35 lirMnemonic[INVOKESPECIAL] = "INVOKESPECIAL";
36 lirMnemonic[INVOKESTATIC] = "INVOKESTATIC";
37 }
38
39
40 public NBasicBlock block;
41
42
43 public int id;
44
45
46 public ArrayList<NRegister> reads;
47
48
51 public NRegister write;
52
53
61
62 protected NLIRInstruction(NBasicBlock block, int id) {
63 this.block = block;
64 this.id = id;
65 reads = new ArrayList<NRegister>();
66 }
67
68
72
73 public void allocatePhysicalRegisters() {
74 }
76
77
84
85 public void toSpim(PrintWriter out) {
86 }
88
89
94
95 public String toString() {
96 return "" + id;
97 }
98
99 }
100
101
104
105 class NLIRArithmetic extends NLIRInstruction {
106
107
108 private int opcode;
109
110
124
125 public NLIRArithmetic(NBasicBlock block, int id, int opcode,
126 NLIRInstruction lhs, NLIRInstruction rhs) {
127 super(block, id);
128 this.opcode = opcode;
129 reads.add(lhs.write);
130 reads.add(rhs.write);
131 write = new NVirtualRegister(NControlFlowGraph.regId++, "I", "I");
132 block.cfg.registers.add((NVirtualRegister) write);
133 }
134
135
138
139 public void allocatePhysicalRegisters() {
140 NInterval input1 = block.cfg.intervals.get(reads.get(0).number())
141 .childAt(id);
142 NInterval input2 = block.cfg.intervals.get(reads.get(1).number())
143 .childAt(id);
144 NInterval output = block.cfg.intervals.get(write.number()).childAt(id);
145 reads.set(0, input1.pRegister);
146 reads.set(1, input2.pRegister);
147 write = output.pRegister;
148 }
149
150
153
154 public void toSpim(PrintWriter out) {
155 switch (opcode) {
156 case IADD:
157 out.printf(" add %s,%s,%s\n", write, reads.get(0), reads.get(1));
158 break;
159 case ISUB:
160 out.printf(" sub %s,%s,%s\n", write, reads.get(0), reads.get(1));
161 break;
162 case IMUL:
163 out.printf(" mul %s,%s,%s\n", write, reads.get(0), reads.get(1));
164 break;
165 }
166 }
167
168
171
172 public String toString() {
173 return id + ": " + lirMnemonic[opcode] + " " + reads.get(0) + " "
174 + reads.get(1) + " " + write;
175 }
176
177 }
178
179
183
184 class NLIRIntConstant extends NLIRInstruction {
185
186
187 public int value;
188
189
199
200 public NLIRIntConstant(NBasicBlock block, int id, int value) {
201 super(block, id);
202 this.value = value;
203 write = new NVirtualRegister(NControlFlowGraph.regId++, "I", "I");
204 block.cfg.registers.add((NVirtualRegister) write);
205 }
206
207
210
211 public void allocatePhysicalRegisters() {
212 NInterval output = block.cfg.intervals.get(write.number()).childAt(id);
213 write = output.pRegister;
214 }
215
216
219
220 public void toSpim(PrintWriter out) {
221 out.printf(" li %s,%d\n", write, value);
222 }
223
224
227
228 public String toString() {
229 return id + ": LDC [" + value + "] " + write;
230 }
231
232 }
233
234
238
239 class NLIRStringConstant extends NLIRInstruction {
240
241
242 public String value;
243
244
245 private static int labelSuffix;
246
247
257
258 public NLIRStringConstant(NBasicBlock block, int id, String value) {
259 super(block, id);
260 this.value = value;
261 write = new NVirtualRegister(NControlFlowGraph.regId++, "L",
262 "Ljava/lang/String;");
263 block.cfg.registers.add((NVirtualRegister) write);
264 labelSuffix = 0;
265 }
266
267
272
273 private String createLabel() {
274 return "Constant..String" + labelSuffix++;
275 }
276
277
280
281 public void allocatePhysicalRegisters() {
282 NInterval output = block.cfg.intervals.get(write.number()).childAt(id);
283 write = output.pRegister;
284 }
285
286
289
290 public void toSpim(PrintWriter out) {
291 String label = createLabel();
292 String s = label + ":\n";
293 int size = 12 + value.length() + 1;
294 int align = (size % 4 == 0) ? 0 : (size + 4) / 4 * 4 - size;
295 s += " .word 2 # Tag 2 indicates a string\n";
296 s += " .word " + (size + align) + " # Size of object in bytes\n";
297 s += " .word " + value.length()
298 + " # String length (not including null terminator)\n";
299 s += " .asciiz \"" + value
300 + "\" # String terminated by null character 0\n";
301 s += " .align " + align + " # Next object is on a word boundary\n";
302 block.cfg.data.add(s);
303 out.printf(" la %s,%s+12\n", write, label);
304 }
305
306
309
310 public String toString() {
311 return id + ": LDC [" + value + "] " + write;
312 }
313
314 }
315
316
319
320 class NLIRConditionalJump extends NLIRInstruction {
321
322
323 public int opcode;
324
325
326 public NBasicBlock onTrueDestination;
327
328
329 public NBasicBlock onFalseDestination;
330
331
349
350 public NLIRConditionalJump(NBasicBlock block, int id, NLIRInstruction lhs,
351 NLIRInstruction rhs, int opcode, NBasicBlock onTrueDestination,
352 NBasicBlock onFalseDestination) {
353 super(block, id);
354 this.opcode = opcode;
355 reads.add(lhs.write);
356 reads.add(rhs.write);
357 this.onTrueDestination = onTrueDestination;
358 this.onFalseDestination = onFalseDestination;
359 }
360
361
364
365 public void allocatePhysicalRegisters() {
366 NInterval input1 = block.cfg.intervals.get(reads.get(0).number())
367 .childAt(id);
368 NInterval input2 = block.cfg.intervals.get(reads.get(1).number())
369 .childAt(id);
370 reads.set(0, input1.pRegister);
371 reads.set(1, input2.pRegister);
372 }
373
374
377
378 public void toSpim(PrintWriter out) {
379 switch (opcode) {
380 case IF_ICMPNE:
381 out.printf(" bne %s,%s,%s\n", reads.get(0), reads.get(1),
382 block.cfg.labelPrefix + "." + onTrueDestination.id);
383 break;
384 case IF_ICMPGT:
385 out.printf(" bgt %s,%s,%s\n", reads.get(0), reads.get(1),
386 block.cfg.labelPrefix + "." + onTrueDestination.id);
387 break;
388 case IF_ICMPLE:
389 out.printf(" ble %s,%s,%s\n", reads.get(0), reads.get(1),
390 block.cfg.labelPrefix + "." + onTrueDestination.id);
391 break;
392 }
393 out.printf(" j %s\n", block.cfg.labelPrefix + "."
394 + onFalseDestination.id);
395 }
396
397
400
401 public String toString() {
402 return id + ": BRANCH [" + lirMnemonic[opcode] + "] " + reads.get(0)
403 + " " + reads.get(1) + " " + onTrueDestination.id();
404 }
405
406 }
407
408
411
412 class NLIRGoto extends NLIRInstruction {
413
414
415 private NBasicBlock destination;
416
417
427
428 public NLIRGoto(NBasicBlock block, int id, NBasicBlock destination) {
429 super(block, id);
430 this.destination = destination;
431 }
432
433
436
437 public void toSpim(PrintWriter out) {
438 String label = block.cfg.labelPrefix + "." + destination.id;
439 out.printf(" j %s\n", label);
440 }
441
442
445
446 public String toString() {
447 return id + ": BRANCH " + destination.id();
448 }
449
450 }
451
452
455
456 class NLIRInvoke extends NLIRInstruction {
457
458
459 public int opcode;
460
461
462 public String target;
463
464
465 public String name;
466
467
487
488 public NLIRInvoke(NBasicBlock block, int id, int opcode, String target,
489 String name, ArrayList<NRegister> arguments, String sType,
490 String lType) {
491 super(block, id);
492 this.opcode = opcode;
493 this.target = target;
494 this.name = name;
495 for (NRegister arg : arguments) {
496 reads.add(arg);
497 }
498 if (!sType.equals("V")) {
499 write = NPhysicalRegister.regInfo[V0];
500 block.cfg.registers.set(V0, write);
501 }
502 }
503
504
507
508 public void allocatePhysicalRegisters() {
509 for (int i = 0; i < reads.size(); i++) {
510 NInterval input = block.cfg.intervals.get(reads.get(i).number())
511 .childAt(id);
512 reads.set(i, input.pRegister);
513 }
514 }
515
516
519
520 public void toSpim(PrintWriter out) {
521 out.printf(" jal %s.%s\n", target.replace("/", "."), name
522 .equals("<init>") ? "__init__" : name);
523 }
524
525
528
529 public String toString() {
530 String s = id + ": " + lirMnemonic[opcode] + " "
531 + (write != null ? write + " = " : "") + target + "." + name
532 + "( ";
533 for (NRegister input : reads) {
534 s += input + " ";
535 }
536 s += ")";
537 return s;
538 }
539
540 }
541
542
545
546 class NLIRReturn extends NLIRInstruction {
547
548
549 public int opcode;
550
551
563
564 public NLIRReturn(NBasicBlock block, int id, int opcode,
565 NPhysicalRegister result) {
566 super(block, id);
567 this.opcode = opcode;
568 if (result != null) {
569 reads.add(result);
570 }
571 }
572
573
576
577 public void toSpim(PrintWriter out) {
578 out.printf(" j %s\n", block.cfg.labelPrefix + ".restore");
579 }
580
581
584
585 public String toString() {
586 if (reads.size() == 0) {
587 return id + ": RETURN";
588 }
589 return id + ": RETURN " + reads.get(0);
590 }
591
592 }
593
594
597
598 class NLIRPutField extends NLIRInstruction {
599
600
601 public int opcode;
602
603
604 public String target;
605
606
607 public String name;
608
609
629
630 public NLIRPutField(NBasicBlock block, int id, int opcode, String target,
631 String name, String sType, String lType, NLIRInstruction value) {
632 super(block, id);
633 this.opcode = opcode;
634 this.target = target;
635 this.name = name;
636 reads.add(value.write);
637 }
638
639
642
643 public void toSpim(PrintWriter out) {
644 out.printf(" NLIRPutField.toSpim() not yet implemented!\n");
645 }
646
647
650
651 public String toString() {
652 return id + ": " + lirMnemonic[opcode] + " " + target + "." + name
653 + " = " + reads.get(0);
654 }
655
656 }
657
658
661
662 class NLIRGetField extends NLIRInstruction {
663
664
665 public int opcode;
666
667
668 public String target;
669
670
671 public String name;
672
673
691
692 public NLIRGetField(NBasicBlock block, int id, int opcode, String target,
693 String name, String sType, String lType) {
694 super(block, id);
695 this.opcode = opcode;
696 this.target = target;
697 this.name = name;
698 write = new NVirtualRegister(NControlFlowGraph.regId++, sType, lType);
699 block.cfg.registers.add((NVirtualRegister) write);
700 }
701
702
705
706 public void toSpim(PrintWriter out) {
707 out.printf(" NLIRGetField.toSpim() not yet implemented!\n");
708 }
709
710
713
714 public String toString() {
715 return id + ": " + lirMnemonic[opcode] + " " + write + " = " + target
716 + "." + name;
717 }
718
719 }
720
721
724
725 class NLIRNewArray extends NLIRInstruction {
726
727
728 public int opcode;
729
730
731 public int dim;
732
733
749
750 public NLIRNewArray(NBasicBlock block, int id, int opcode, int dim,
751 String sType, String lType) {
752 super(block, id);
753 this.opcode = opcode;
754 this.dim = dim;
755 write = new NVirtualRegister(NControlFlowGraph.regId++, sType, lType);
756 block.cfg.registers.add((NVirtualRegister) write);
757 }
758
759
762
763 public void toSpim(PrintWriter out) {
764 out.printf(" NLIRNewArray.toSpim() not yet implemented!\n");
765 }
766
767
770
771 public String toString() {
772 return id + ": " + lirMnemonic[opcode] + " [" + dim + "]" + " " + write;
773 }
774
775 }
776
777
780
781 class NLIRALoad extends NLIRInstruction {
782
783
784 public int opcode;
785
786
804
805 public NLIRALoad(NBasicBlock block, int id, int opcode,
806 NLIRInstruction arrayRef, NLIRInstruction index, String sType,
807 String lType) {
808 super(block, id);
809 this.opcode = opcode;
810 reads.add(arrayRef.write);
811 reads.add(index.write);
812 write = new NVirtualRegister(NControlFlowGraph.regId++, sType, lType);
813 block.cfg.registers.add((NVirtualRegister) write);
814 }
815
816
819
820 public void toSpim(PrintWriter out) {
821 out.printf(" NLIRALoad.toSpim() not yet implemented!\n");
822 }
823
824
827
828 public String toString() {
829 return id + ": " + lirMnemonic[opcode] + " " + write + "= "
830 + reads.get(0) + "[" + reads.get(1) + "]";
831 }
832
833 }
834
835
838
839 class NLIRAStore extends NLIRInstruction {
840
841
842 public int opcode;
843
844
864
865 public NLIRAStore(NBasicBlock block, int id, int opcode,
866 NLIRInstruction arrayRef, NLIRInstruction index,
867 NLIRInstruction value, String sType, String lType) {
868 super(block, id);
869 this.opcode = opcode;
870 reads.add(arrayRef.write);
871 reads.add(index.write);
872 reads.add(value.write);
873 }
874
875
878
879 public void toSpim(PrintWriter out) {
880 out.printf(" NLIRAStore.toSpim() not yet implemented!\n");
881 }
882
883
886
887 public String toString() {
888 return id + ": " + lirMnemonic[opcode] + " " + reads.get(0) + "["
889 + reads.get(1) + "] = " + reads.get(2);
890 }
891
892 }
893
894
897
898 class NLIRPhiFunction extends NLIRInstruction {
899
900
912
913 public NLIRPhiFunction(NBasicBlock block, int id, String sType, String lType) {
914 super(block, id);
915 write = new NVirtualRegister(NControlFlowGraph.regId++, sType, lType);
916 block.cfg.registers.add((NVirtualRegister) write);
917 }
918
919
922
923 public String toString() {
924 return id + ": phi " + write;
925 }
926
927 }
928
929
932
933 class NLIRMove extends NLIRInstruction {
934
935
947
948 public NLIRMove(NBasicBlock block, int id, NLIRInstruction from,
949 NLIRInstruction to) {
950 super(block, id);
951 reads.add(from.write);
952 write = to.write;
953 }
954
955
967
968 public NLIRMove(NBasicBlock block, int id, NRegister from, NRegister to) {
969 super(block, id);
970 reads.add(from);
971 write = to;
972 }
973
974
977
978 public void allocatePhysicalRegisters() {
979 NInterval input = block.cfg.intervals.get(reads.get(0).number())
980 .childAt(id);
981 ;
982 NInterval output = block.cfg.intervals.get(write.number()).childAt(id);
983 reads.set(0, input.pRegister);
984 write = output.pRegister;
985 }
986
987
990
991 public void toSpim(PrintWriter out) {
992 out.printf(" move %s,%s\n", write, reads.get(0));
993 }
994
995
998
999 public String toString() {
1000 return id + ": MOVE " + reads.get(0) + " " + write;
1001 }
1002
1003}
1004
1005
1008
1009class NLIRLoadLocal extends NLIRInstruction {
1010
1011
1012 public int local;
1013
1014
1028
1029 public NLIRLoadLocal(NBasicBlock block, int id, int local, String sType,
1030 String lType) {
1031 super(block, id);
1032 this.local = local;
1033 if (local < 4) {
1034 write = NPhysicalRegister.regInfo[A0 + local];
1035 block.cfg.registers.set(A0 + local, NPhysicalRegister.regInfo[A0
1036 + local]);
1037 } else {
1038 write = new NVirtualRegister(NControlFlowGraph.regId++, sType,
1039 lType);
1040 block.cfg.registers.add((NVirtualRegister) write);
1041 }
1042 }
1043
1044
1047
1048 public String toString() {
1049 return id + ": LDLOC " + local + " " + write;
1050 }
1051
1052}
1053
1054
1057
1058class NLIRLoad extends NLIRInstruction {
1059
1060
1061 private int offset;
1062
1063
1066 private OffsetFrom offsetFrom;
1067
1068
1069 private NRegister register;
1070
1071
1086
1087 public NLIRLoad(NBasicBlock block, int id, int offset,
1088 OffsetFrom offsetFrom, NRegister register) {
1089 super(block, id);
1090 this.offset = offset;
1091 this.offsetFrom = offsetFrom;
1092 this.register = register;
1093 }
1094
1095
1098
1099 public void toSpim(PrintWriter out) {
1100 if (offsetFrom == OffsetFrom.FP) {
1101 out.printf(" lw %s,%d($fp)\n", register, offset * 4);
1102 } else {
1103 out.printf(" lw %s,%d($sp)\n", register, offset * 4);
1104 }
1105 }
1106
1107
1110
1111 public String toString() {
1112 return id + ": LOAD "
1113 + (offsetFrom == OffsetFrom.FP ? "[frame:" : "[stack:")
1114 + offset + "] " + register;
1115 }
1116
1117}
1118
1119
1122
1123class NLIRStore extends NLIRInstruction {
1124
1125
1126 private int offset;
1127
1128
1131 private OffsetFrom offsetFrom;
1132
1133
1134 private NRegister register;
1135
1136
1151
1152 public NLIRStore(NBasicBlock block, int id, int offset,
1153 OffsetFrom offsetFrom, NRegister register) {
1154 super(block, id);
1155 this.offset = offset;
1156 this.offsetFrom = offsetFrom;
1157 this.register = register;
1158 reads.add(register);
1159 }
1160
1161
1164
1165 public void allocatePhysicalRegisters() {
1166 NInterval input = block.cfg.intervals.get(reads.get(0).number())
1167 .childAt(id);
1168 if (input.vRegId >= 32) {
1169 reads.set(0, input.pRegister);
1170 }
1171 }
1172
1173
1176
1177 public void toSpim(PrintWriter out) {
1178 if (offsetFrom == OffsetFrom.FP) {
1179 out.printf(" sw %s,%d($fp)\n", reads.get(0), offset * 4);
1180 } else {
1181 out.printf(" sw %s,%d($sp)\n", reads.get(0), offset * 4);
1182 }
1183 }
1184
1185
1188
1189 public String toString() {
1190 return id + ": STORE " + reads.get(0) + " "
1191 + (offsetFrom == OffsetFrom.FP ? "[frame:" : "[stack:")
1192 + offset + "]";
1193 }
1194
1195}
1196