1
3 package jminusminus;
4
5 import java.util.ArrayList;
6 import java.util.BitSet;
7 import java.util.HashMap;
8 import java.util.LinkedList;
9 import java.util.Stack;
10 import java.util.TreeMap;
11 import java.util.Queue;
12
13 import static jminusminus.CLConstants.*;
14
15
16
19 class NTuple {
20
23 public int pc;
24
25
28 public int opcode;
29
30
33 public ArrayList<Short> operands;
34
35
38 public String mnemonic;
39
40
43 public boolean isLeader;
44
45
52 public NTuple(int pc, int opcode, ArrayList<Short> operands) {
53 this.pc = pc;
54 this.opcode = opcode;
55 this.operands = operands;
56 this.mnemonic = CLInstruction.instructionInfo[opcode].mnemonic;
57 this.isLeader = false;
58 }
59
60
65 public void writeToStdOut(PrettyPrinter p) {
66 p.printf("%s: %s", pc, mnemonic);
67 for (short s : operands) {
68 p.printf(" %s", s);
69 }
70 p.println();
71 }
72 }
73
74
77 class NBasicBlock {
78
81 public NControlFlowGraph cfg;
82
83
86 public int id;
87
88
91 public ArrayList<NTuple> tuples;
92
93
96 public ArrayList<NBasicBlock> predecessors;
97
98
101 public ArrayList<NBasicBlock> successors;
102
103
106 public ArrayList<Integer> hir;
107
108
111 public ArrayList<NLIRInstruction> lir;
112
113
117 public int[] locals;
118
119
122 public boolean visited;
123
124
127 public boolean active;
128
129
132 public boolean isLoopHead;
133
134
137 public boolean isLoopTail;
138
139
142 public int loopIndex;
143
144
147 public int loopDepth;
148
149
152 public int fwdBranches;
153
154
157 public int bwdBranches;
158
159
162 public int ref;
163
164
167 public NBasicBlock dom;
168
169
172 public BitSet liveDef;
173
174
177 public BitSet liveUse;
178
179
182 public BitSet liveIn;
183
184
187 public BitSet liveOut;
188
189
195 public NBasicBlock(NControlFlowGraph cfg, int id) {
196 this.cfg = cfg;
197 this.id = id;
198 tuples = new ArrayList<NTuple>();
199 predecessors = new ArrayList<NBasicBlock>();
200 successors = new ArrayList<NBasicBlock>();
201 hir = new ArrayList<Integer>();
202 lir = new ArrayList<NLIRInstruction>();
203 isLoopHead = false;
204 }
205
206
211 public String id() {
212 return "B" + id;
213 }
214
215
221 public boolean equals(NBasicBlock other) {
222 return this.id == other.id;
223 }
224
225
230 public String toString() {
231 return "[B" + id + "]";
232 }
233
234
239 public void writeTuplesToStdOut(PrettyPrinter p) {
240 String s = id();
241 p.printf("%s\n", s);
242 for (NTuple tuple : tuples) {
243 tuple.writeToStdOut(p);
244 }
245 p.println();
246 }
247
248
253 public void writeHirToStdOut(PrettyPrinter p) {
254 String s = id() + (isLoopHead ? " [LH]" : "") + (isLoopTail ? " [LT]" : "");
255 if (tuples.size() > 0) {
256 s += " [" + tuples.get(0).pc + ", " + tuples.get(tuples.size() - 1).pc + "]";
257 }
258 if (dom != null) {
259 s += " dom: " + dom.id();
260 }
261 if (predecessors.size() > 0) {
262 s += " pred: ";
263 for (NBasicBlock block : predecessors) {
264 s += block.id() + " ";
265 }
266 }
267 if (successors.size() > 0) {
268 s += " succ: ";
269 for (NBasicBlock block : successors) {
270 s += block.id() + " ";
271 }
272 }
273 p.printf(s + "\n");
274 s = "Locals: ";
275 if (locals != null) {
276 for (int i = 0; i < locals.length; i++) {
277 if (!(cfg.hirMap.get(locals[i]) instanceof NHIRLocal)) {
278 s += cfg.hirMap.get(locals[i]).id() + " ";
279 }
280 }
281 }
282 p.printf("%s\n", s);
283 for (int ins : hir) {
284 if (cfg.hirMap.get(ins) instanceof NHIRPhiFunction) {
285 p.printf("%s: %s\n", ((NHIRPhiFunction) cfg.hirMap.get(ins)).id(),
286 ((NHIRPhiFunction) cfg.hirMap.get(ins)));
287 }
288 }
289 for (int ins : hir) {
290 if (!(cfg.hirMap.get(ins) instanceof NHIRPhiFunction)) {
291 p.printf("%s\n", cfg.hirMap.get(ins));
292 }
293 }
294 p.println();
295 }
296
297
302 public void writeLirToStdOut(PrettyPrinter p) {
303 p.printf("%s\n", id());
304 for (NLIRInstruction ins : lir) {
305 p.printf("%s\n", ins);
306 }
307 p.println();
308 }
309
310
315 public int getFirstLIRInstId() {
316 return lir.isEmpty() ? -1 : lir.get(0).id;
317 }
318
319
324 public int getLastLIRInstId() {
325 return lir.isEmpty() ? -1 : lir.get(lir.size() - 1).id;
326 }
327
328
334 public NLIRInstruction getInstruction(int id) {
335 for (NLIRInstruction inst : this.lir) {
336 if (inst.id == id) {
337 return inst;
338 }
339 }
340 return null;
341 }
342
343
349 public boolean idIsFree(int id) {
350 return getInstruction(id) == null;
351 }
352
353
359 public void insertLIRInst(NLIRInstruction inst) {
360 int idx = -1;
361 for (int i = 0; i < this.lir.size(); i++) {
362 if (this.lir.get(i).id < inst.id) {
363 idx = i;
364 }
365 }
366 if (++idx == this.lir.size()) {
367 this.lir.add(inst);
368 } else {
369 this.lir.add(idx, inst);
370 }
371 }
372 }
373
374
377 class NControlFlowGraph {
378 private CLConstantPool cp;
380
381 private CLMethodInfo m;
383
384 private HashMap<Integer, NBasicBlock> pcToBasicBlock;
386
387
390 public static int blockId;
391
392
395 public static int hirId;
396
397
400 public static int lirId;
401
402
405 public static int regId;
406
407
410 public int offset;
411
412
415 public static int loopIndex;
416
417
420 public String name;
421
422
425 public String desc;
426
427
430 public ArrayList<NBasicBlock> basicBlocks;
431
432
435 public TreeMap<Integer, NHIRInstruction> hirMap;
436
437
440 public ArrayList<NRegister> registers;
441
442
446 public int maxIntervals;
447
448
451 public ArrayList<NPhysicalRegister> pRegisters;
452
453
456 public ArrayList<NInterval> intervals;
457
458
461 public String labelPrefix;
462
463
466 public ArrayList<String> data;
467
468
474 public NControlFlowGraph(CLConstantPool cp, CLMethodInfo m) {
475 this.cp = cp;
476 this.m = m;
477 name = new String(((CLConstantUtf8Info) cp.cpItem(m.nameIndex)).b);
478 desc = new String(((CLConstantUtf8Info) cp.cpItem(m.descriptorIndex)).b);
479 basicBlocks = new ArrayList<NBasicBlock>();
480 pcToBasicBlock = new HashMap<Integer, NBasicBlock>();
481 ArrayList<Integer> code = getByteCode();
482 ArrayList<NTuple> tuples = bytecodeToTuples(code);
483 if (tuples.size() == 0) {
484 return;
485 }
486 NTuple[] tupleAt = new NTuple[code.size()];
487 for (NTuple tuple : tuples) {
488 tupleAt[tuple.pc] = tuple;
489 }
490
491 findLeaders(tuples, tupleAt);
493
494 buildBasicBlocks(tuples);
496
497 basicBlocks.get(0).successors.add(basicBlocks.get(1));
499 basicBlocks.get(1).predecessors.add(basicBlocks.get(0));
500 NBasicBlock[] blockAt = new NBasicBlock[code.size()];
501 for (NBasicBlock block : basicBlocks) {
502 if (block.tuples.size() == 0) {
503 continue;
504 }
505 blockAt[block.tuples.get(0).pc] = block;
506 }
507 for (int j = 0; j < basicBlocks.size(); j++) {
508 NBasicBlock block = basicBlocks.get(j);
509 if (block.tuples.size() == 0) {
510 continue;
511 }
512 NTuple tuple = block.tuples.get(block.tuples.size() - 1);
513 short operandByte1, operandByte2, operandByte3, operandByte4;
514 int offset;
515 NBasicBlock target;
516 switch (tuple.opcode) {
517 case IFEQ:
518 case IFNE:
519 case IFLT:
520 case IFGE:
521 case IFGT:
522 case IFLE:
523 case IF_ICMPEQ:
524 case IF_ICMPNE:
525 case IF_ICMPLT:
526 case IF_ICMPGE:
527 case IF_ICMPGT:
528 case IF_ICMPLE:
529 case IF_ACMPEQ:
530 case IF_ACMPNE:
531 case IFNULL:
532 case IFNONNULL:
533 operandByte1 = tuple.operands.get(0);
534 operandByte2 = tuple.operands.get(1);
535 offset = shortValue(operandByte1, operandByte2);
536 target = blockAt[tuple.pc + offset];
537 if (j < basicBlocks.size() - 1) {
538 block.successors.add(basicBlocks.get(j + 1));
539 basicBlocks.get(j + 1).predecessors.add(block);
540 }
541 block.successors.add(target);
542 target.predecessors.add(block);
543 break;
544 case GOTO:
545 case JSR:
546 operandByte1 = tuple.operands.get(0);
547 operandByte2 = tuple.operands.get(1);
548 offset = shortValue(operandByte1, operandByte2);
549 target = blockAt[tuple.pc + offset];
550 block.successors.add(target);
551 target.predecessors.add(block);
552 break;
553 case GOTO_W:
554 case JSR_W:
555 operandByte1 = tuple.operands.get(0);
556 operandByte2 = tuple.operands.get(1);
557 operandByte3 = tuple.operands.get(2);
558 operandByte4 = tuple.operands.get(3);
559 offset = intValue(operandByte1, operandByte2, operandByte3, operandByte4);
560 target = blockAt[tuple.pc + offset];
561 block.successors.add(target);
562 target.predecessors.add(block);
563 break;
564 case IRETURN:
565 case LRETURN:
566 case FRETURN:
567 case DRETURN:
568 case ARETURN:
569 case RETURN:
570 case RET:
571 case ATHROW:
572 break;
573 case TABLESWITCH: break;
575 case LOOKUPSWITCH: break;
577 default:
578 if (j < basicBlocks.size() - 1) {
579 block.successors.add(basicBlocks.get(j + 1));
580 basicBlocks.get(j + 1).predecessors.add(block);
581 }
582 }
583 }
584
585 for (NBasicBlock block : basicBlocks) {
587 block.ref = block.predecessors.size();
588 block.fwdBranches = block.predecessors.size() - block.bwdBranches;
589 }
590 }
591
592
599 public void detectLoops(NBasicBlock block, NBasicBlock pred) {
600 if (!block.visited) {
601 block.visited = true;
602 block.active = true;
603 for (NBasicBlock succ : block.successors) {
604 detectLoops(succ, block);
605 }
606 block.active = false;
607 } else if (block.active) {
608 block.isLoopHead = true;
609 pred.isLoopTail = true;
610 block.bwdBranches++;
611 block.loopIndex = NControlFlowGraph.loopIndex++;
612 }
613 }
614
615
619 public void removeUnreachableBlocks() {
620 ArrayList<NBasicBlock> toRemove = new ArrayList<NBasicBlock>();
622 for (NBasicBlock block : basicBlocks) {
623 if (!block.visited) {
624 toRemove.add(block);
625 }
626 }
627
628 for (NBasicBlock block : basicBlocks) {
630 for (NBasicBlock pred : toRemove) {
631 block.predecessors.remove(pred);
632 }
633 }
634
635 for (NBasicBlock block : toRemove) {
637 basicBlocks.remove(block);
638 }
639 }
640
641
648 public void computeDominators(NBasicBlock block, NBasicBlock pred) {
649 if (block.ref > 0) {
650 block.ref--;
651 }
652 if (block.dom == null) {
653 block.dom = pred;
654 } else {
655 block.dom = commonDom(block.dom, pred);
656 }
657 if (block.ref == block.bwdBranches) {
658 for (NBasicBlock s : block.successors) {
659 computeDominators(s, block);
660 }
661 }
662 }
663
664
667 public void tuplesToHir() {
668 clearBlockVisitations();
669 hirId = 0;
670 loopIndex = 0;
671 hirMap = new TreeMap<Integer, NHIRInstruction>();
672 int numLocals = numLocals();
673 int[] locals = new int[numLocals];
674 ArrayList<String> argTypes = argumentTypes(desc);
675 NBasicBlock beginBlock = basicBlocks.get(0);
676 for (int i = 0; i < locals.length; i++) {
677 NHIRInstruction ins = null;
678 if (i < argTypes.size()) {
679 String lType = argTypes.get(i);
680 ins = new NHIRLoadLocal(beginBlock, hirId++, i, shortType(lType), lType);
681 beginBlock.hir.add(ins.id);
682 } else {
683 ins = new NHIRLocal(beginBlock, hirId++, i, "", "");
684 }
685 beginBlock.cfg.hirMap.put(ins.id, ins);
686 locals[i] = ins.id;
687 }
688 beginBlock.locals = locals;
689 Stack<Integer> operandStack = new Stack<Integer>();
690 Queue<NBasicBlock> q = new LinkedList<NBasicBlock>();
691 beginBlock.visited = true;
692 q.add(beginBlock);
693 while (!q.isEmpty()) {
694 NBasicBlock block = q.remove();
695 for (NBasicBlock succ : block.successors) {
696 if (!succ.visited) {
697 succ.visited = true;
698 q.add(succ);
699 }
700 }
701
702 if (block.predecessors.size() == 1) {
704 block.locals = block.predecessors.get(0).locals.clone();
705 } else if (block.predecessors.size() > 1) {
706 if (block.isLoopHead) {
707 for (NBasicBlock pred : block.predecessors) {
708 if (pred.locals != null) {
709 block.locals = pred.locals.clone();
710 break;
711 }
712 }
713 for (int i = 0; i < block.locals.length; i++) {
714 ArrayList<Integer> args = new ArrayList<Integer>();
715 NHIRPhiFunction phi = new NHIRPhiFunction(block, hirId++, args, i);
716 block.hir.add(phi.id);
717 block.cfg.hirMap.put(phi.id, phi);
718 phi.getArguments().add(block.locals[i]);
719 for (int j = 1; j < block.predecessors.size(); j++) {
720 phi.getArguments().add(phi.id);
721 }
722 block.locals[i] = phi.id;
723 phi.inferType();
724 }
725 } else {
726 block.locals = block.predecessors.get(0).locals.clone();
727 for (int i = 1; i < block.predecessors.size(); i++) {
728 NBasicBlock pred = block.predecessors.get(i);
729 mergeLocals(block, pred);
730 }
731 }
732 }
733 for (NTuple tuple : block.tuples) {
734 CLInsInfo insInfo = CLInstruction.instructionInfo[tuple.opcode];
735 int localVariableIndex = insInfo.localVariableIndex;
736 NHIRInstruction ins = null;
737 short operandByte1 = 0, operandByte2 = 0, operandByte3 = 0, offset = 0;
738 int operand1 = 0, operand2 = 0, operand3 = 0;
739 switch (insInfo.opcode) {
740 case MULTIANEWARRAY: {
741 operandByte1 = tuple.operands.get(0);
742 operandByte2 = tuple.operands.get(1);
743 operandByte3 = tuple.operands.get(2);
744 int index = shortValue(operandByte1, operandByte2);
745 int classIndex = ((CLConstantClassInfo) cp.cpItem(index)).nameIndex;
746 String type = new String(((CLConstantUtf8Info) cp.cpItem(classIndex)).b);
747 ins = new NHIRNewArray(block, hirId++, insInfo.opcode,
748 (int) operandByte3, shortType(type), type);
749 block.cfg.hirMap.put(ins.id, ins);
750 block.hir.add(ins.id);
751 operandStack.push(ins.id);
752 break;
753 }
754 case AALOAD: {
755 operand2 = operandStack.pop();
756 operand1 = operandStack.pop();
757
758 NHIRInstruction ins1 = new NHIRIntConstant(block, hirId++, 12);
760 NHIRInstruction ins2 = new NHIRArithmetic(block, hirId++, IADD, operand1,
761 ins1.id);
762 block.cfg.hirMap.put(ins1.id, ins1);
763 block.hir.add(ins1.id);
764 block.cfg.hirMap.put(ins2.id, ins2);
765 block.hir.add(ins2.id);
766
767 NHIRInstruction ins3 = new NHIRIntConstant(block, hirId++, 4);
769 NHIRInstruction ins4 = new NHIRArithmetic(block, hirId++, IMUL, operand2,
770 ins3.id);
771 block.cfg.hirMap.put(ins3.id, ins3);
772 block.hir.add(ins3.id);
773 block.cfg.hirMap.put(ins4.id, ins4);
774 block.hir.add(ins4.id);
775
776 ins = new NHIRALoad(block, hirId++, insInfo.opcode, ins2.id, ins4.id,
777 "L", "L");
778 block.cfg.hirMap.put(ins.id, ins);
779 block.hir.add(ins.id);
780 operandStack.push(ins.id);
781 break;
782 }
783 case IALOAD: {
784 operand2 = operandStack.pop();
785 operand1 = operandStack.pop();
786
787 NHIRInstruction ins1 = new NHIRIntConstant(block, hirId++, 12);
789 NHIRInstruction ins2 = new NHIRArithmetic(block, hirId++, IADD, operand1,
790 ins1.id);
791 block.cfg.hirMap.put(ins1.id, ins1);
792 block.hir.add(ins1.id);
793 block.cfg.hirMap.put(ins2.id, ins2);
794 block.hir.add(ins2.id);
795
796 NHIRInstruction ins3 = new NHIRIntConstant(block, hirId++, 4);
798 NHIRInstruction ins4 = new NHIRArithmetic(block, hirId++, IMUL, operand2,
799 ins3.id);
800 block.cfg.hirMap.put(ins3.id, ins3);
801 block.hir.add(ins3.id);
802 block.cfg.hirMap.put(ins4.id, ins4);
803 block.hir.add(ins4.id);
804
805 ins = new NHIRALoad(block, hirId++, insInfo.opcode, ins2.id, ins4.id,
806 "I", "I");
807 block.cfg.hirMap.put(ins.id, ins);
808 block.hir.add(ins.id);
809 operandStack.push(ins.id);
810 break;
811 }
812 case IASTORE: {
813 operand3 = operandStack.pop();
814 operand2 = operandStack.pop();
815 operand1 = operandStack.pop();
816
817 NHIRInstruction ins1 = new NHIRIntConstant(block, hirId++, 12);
819 NHIRInstruction ins2 = new NHIRArithmetic(block, hirId++, IADD, operand1,
820 ins1.id);
821 block.cfg.hirMap.put(ins1.id, ins1);
822 block.hir.add(ins1.id);
823 block.cfg.hirMap.put(ins2.id, ins2);
824 block.hir.add(ins2.id);
825
826 NHIRInstruction ins3 = new NHIRIntConstant(block, hirId++, 4);
828 NHIRInstruction ins4 = new NHIRArithmetic(block, hirId++, IMUL, operand2,
829 ins3.id);
830 block.cfg.hirMap.put(ins3.id, ins3);
831 block.hir.add(ins3.id);
832 block.cfg.hirMap.put(ins4.id, ins4);
833 block.hir.add(ins4.id);
834
835 ins = new NHIRAStore(block, hirId++, insInfo.opcode, ins2.id, ins4.id,
836 operand3, "I", "I");
837 block.cfg.hirMap.put(ins.id, ins);
838 block.hir.add(ins.id);
839 break;
840 }
841 case ICONST_0:
842 case ICONST_1:
843 case ICONST_2:
844 case ICONST_3:
845 case ICONST_4:
846 case ICONST_5: {
847 ins = new NHIRIntConstant(block, hirId++, tuple.opcode - 3);
848 block.cfg.hirMap.put(ins.id, ins);
849 block.hir.add(ins.id);
850 operandStack.push(ins.id);
851 break;
852 }
853 case ILOAD: {
854 operandByte1 = tuple.operands.get(0);
855 localVariableIndex = operandByte1;
856 operandStack.push(block.locals[localVariableIndex]);
857 break;
858 }
859 case ILOAD_0:
860 case ILOAD_1:
861 case ILOAD_2:
862 case ILOAD_3:
863 case ALOAD_0:
864 case ALOAD_1:
865 case ALOAD_2:
866 case ALOAD_3: {
867 operandStack.push(block.locals[localVariableIndex]);
868 break;
869 }
870 case ISTORE: {
871 operandByte1 = tuple.operands.get(0);
872 localVariableIndex = operandByte1;
873 block.locals[localVariableIndex] = operandStack.pop();
874 break;
875 }
876 case ISTORE_0:
877 case ISTORE_1:
878 case ISTORE_2:
879 case ISTORE_3:
880 case ASTORE_0:
881 case ASTORE_1:
882 case ASTORE_2:
883 case ASTORE_3: {
884 block.locals[localVariableIndex] = operandStack.pop();
885 break;
886 }
887 case BIPUSH: {
888 operandByte1 = tuple.operands.get(0);
889 ins = new NHIRIntConstant(block, hirId++, operandByte1);
890 block.cfg.hirMap.put(ins.id, ins);
891 block.hir.add(ins.id);
892 operandStack.push(ins.id);
893 break;
894 }
895 case SIPUSH: {
896 operandByte1 = tuple.operands.get(0);
897 operandByte2 = tuple.operands.get(1);
898 ins = new NHIRIntConstant(block, hirId++, shortValue(
899 operandByte1, operandByte2));
900 block.cfg.hirMap.put(ins.id, ins);
901 block.hir.add(ins.id);
902 operandStack.push(ins.id);
903 break;
904 }
905 case LDC: {
906 operandByte1 = tuple.operands.get(0);
907
908 int stringIndex =
910 ((CLConstantStringInfo) cp.cpItem(operandByte1)).stringIndex;
911 String s = new String(((CLConstantUtf8Info) cp.cpItem(stringIndex)).b);
912 ins = new NHIRStringConstant(block, hirId++, s);
913 block.cfg.hirMap.put(ins.id, ins);
914 block.hir.add(ins.id);
915 operandStack.push(ins.id);
916 break;
917 }
918 case IADD:
919 case ISUB:
920 case IMUL: {
921 operand2 = operandStack.pop();
922 operand1 = operandStack.pop();
923 ins = new NHIRArithmetic(block, hirId++, insInfo.opcode, operand1,
924 operand2);
925 block.cfg.hirMap.put(ins.id, ins);
926 block.hir.add(ins.id);
927 operandStack.push(ins.id);
928 break;
929 }
930 case IINC: {
931 operandByte1 = tuple.operands.get(0);
932 operandByte2 = tuple.operands.get(1);
933 operand1 = block.locals[operandByte1];
934 NHIRInstruction ins1 = new NHIRIntConstant(block, hirId++,
935 (byte) operandByte2);
936 ins = new NHIRArithmetic(block, hirId++, IADD, operand1, ins1.id);
937 block.locals[operandByte1] = ins.id;
938 block.hir.add(ins1.id);
939 block.cfg.hirMap.put(ins1.id, ins1);
940 block.hir.add(ins.id);
941 block.cfg.hirMap.put(ins.id, ins);
942 break;
943 }
944 case IF_ICMPNE:
945 case IF_ICMPGT:
946 case IF_ICMPLE: {
947 operandByte1 = tuple.operands.get(0);
948 operandByte2 = tuple.operands.get(1);
949 offset = shortValue(operandByte1, operandByte2);
950 int rhs = operandStack.pop();
951 int lhs = operandStack.pop();
952 NBasicBlock trueDestination = pcToBasicBlock.get(tuple.pc + offset);
953 NBasicBlock falseDestination = pcToBasicBlock.get(tuple.pc + 3);
954 ins = new NHIRConditionalJump(block, hirId++, lhs, rhs, insInfo.opcode,
955 trueDestination, falseDestination);
956 block.cfg.hirMap.put(ins.id, ins);
957 block.hir.add(ins.id);
958 break;
959 }
960 case GOTO: {
961 operandByte1 = tuple.operands.get(0);
962 operandByte2 = tuple.operands.get(1);
963 offset = shortValue(operandByte1, operandByte2);
964 NBasicBlock destination = pcToBasicBlock.get(tuple.pc + offset);
965 ins = new NHIRGoto(block, hirId++, destination);
966 block.cfg.hirMap.put(ins.id, ins);
967 block.hir.add(ins.id);
968 break;
969 }
970 case GETSTATIC:
971 case PUTSTATIC: {
972 operandByte1 = tuple.operands.get(0);
973 operandByte2 = tuple.operands.get(1);
974 int index = shortValue(operandByte1, operandByte2);
975 int classIndex = ((CLConstantFieldRefInfo) cp.cpItem(index)).classIndex;
976 int nameAndTypeIndex =
977 ((CLConstantFieldRefInfo) cp.cpItem(index)).nameAndTypeIndex;
978 int nameIndex = ((CLConstantClassInfo) cp.cpItem(classIndex)).nameIndex;
979 String target = new String(((CLConstantUtf8Info) cp.cpItem(nameIndex)).b);
980 int fieldNameIndex =
981 ((CLConstantNameAndTypeInfo) cp.cpItem(nameAndTypeIndex)).nameIndex;
982 int fieldDescIndex =
983 ((CLConstantNameAndTypeInfo) cp.cpItem(nameAndTypeIndex)).descriptorIndex;
984 String name =
985 new String(((CLConstantUtf8Info) cp.cpItem(fieldNameIndex)).b);
986 String desc =
987 new String(((CLConstantUtf8Info) cp.cpItem(fieldDescIndex)).b);
988 if (insInfo.opcode == PUTSTATIC) {
989 ins = new NHIRPutField(block, hirId++, insInfo.opcode, target, name,
990 shortType(desc), desc, operandStack.pop());
991 } else {
992 ins = new NHIRGetField(block, hirId++, insInfo.opcode, target, name,
993 shortType(desc), desc);
994 operandStack.push(ins.id);
995 }
996 block.cfg.hirMap.put(ins.id, ins);
997 block.hir.add(ins.id);
998 break;
999 }
1000 case INVOKESPECIAL:
1001 case INVOKESTATIC: {
1002 operandByte1 = tuple.operands.get(0);
1003 operandByte2 = tuple.operands.get(1);
1004 int index = shortValue(operandByte1, operandByte2);
1005 int classIndex = ((CLConstantMethodRefInfo) cp.cpItem(index)).classIndex;
1006 int nameAndTypeIndex =
1007 ((CLConstantMethodRefInfo) cp.cpItem(index)).nameAndTypeIndex;
1008 int nameIndex =
1009 ((CLConstantClassInfo) cp.cpItem(classIndex)).nameIndex;
1010 String target = new String(((CLConstantUtf8Info) cp.cpItem(nameIndex)).b);
1011 int methodNameIndex =
1012 ((CLConstantNameAndTypeInfo) cp.cpItem(nameAndTypeIndex)).nameIndex;
1013 int methodDescIndex = ((CLConstantNameAndTypeInfo)
1014 cp.cpItem(nameAndTypeIndex)).descriptorIndex;
1015 String name =
1016 new String(((CLConstantUtf8Info) cp.cpItem(methodNameIndex)).b);
1017 String desc =
1018 new String(((CLConstantUtf8Info) cp.cpItem(methodDescIndex)).b);
1019 ArrayList<Integer> args = new ArrayList<Integer>();
1020 int numArgs = argumentCount(desc);
1021 for (int i = 0; i < numArgs; i++) {
1022 int arg = operandStack.pop();
1023 args.add(0, arg);
1024 }
1025 String returnType = returnType(desc);
1026 ins = new NHIRInvoke(block, hirId++, insInfo.opcode, target, name, args,
1027 shortType(returnType), returnType);
1028 if (!returnType.equals("V")) {
1029 operandStack.push(ins.id);
1030 }
1031 block.cfg.hirMap.put(ins.id, ins);
1032 block.hir.add(ins.id);
1033 break;
1034 }
1035 case IRETURN:
1036 case ARETURN: {
1037 ins = new NHIRReturn(block, hirId++, insInfo.opcode, operandStack.pop());
1038 block.cfg.hirMap.put(ins.id, ins);
1039 block.hir.add(ins.id);
1040 break;
1041 }
1042 case RETURN: {
1043 ins = new NHIRReturn(block, hirId++, insInfo.opcode, -1);
1044 block.cfg.hirMap.put(ins.id, ins);
1045 block.hir.add(ins.id);
1046 break;
1047 }
1048 }
1049 }
1050 }
1051 }
1052
1053
1056 public void optimize() {
1057 }
1059
1060
1063 public void eliminateRedundantPhiFunctions() {
1064 for (int ins : hirMap.keySet()) {
1065 NHIRInstruction hir = hirMap.get(ins);
1066 if (hir instanceof NHIRPhiFunction) {
1067 NHIRPhiFunction phi = (NHIRPhiFunction) hir;
1068 int firstArg = phi.getArguments().get(0);
1069 boolean match = true;
1070 NBasicBlock block = phi.block;
1071 if (!block.isLoopHead) {
1072 continue;
1073 }
1074 for (int i = 1; i < phi.getArguments().size(); i++) {
1075 if (phi.getArguments().get(i) != block.predecessors.get(i).locals[phi.getLocal()]) {
1076 match = false;
1077 phi.getArguments().set(i, block.predecessors.get(i).locals[phi.getLocal()]);
1078 }
1079 }
1080 if (match && firstArg != phi.id) {
1081 hirMap.put(phi.id, hirMap.get(firstArg));
1082 phi.block.hir.remove((Integer) phi.id);
1083 }
1084 }
1085 }
1086 }
1087
1088
1091 public void hirToLir() {
1092 lirId = 0;
1093 regId = 32;
1094 offset = 0;
1095 registers = new ArrayList<NRegister>();
1096 data = new ArrayList<String>();
1097 for (int i = 0; i < 32; i++) {
1098 registers.add(null);
1099 }
1100 pRegisters = new ArrayList<NPhysicalRegister>();
1101 for (int ins : hirMap.keySet()) {
1102 hirMap.get(ins).toLir();
1103 }
1104
1105 int size = registers.size();
1108 for (NBasicBlock block : basicBlocks) {
1109 block.liveDef = new BitSet(size);
1110 block.liveUse = new BitSet(size);
1111 block.liveIn = new BitSet(size);
1112 block.liveOut = new BitSet(size);
1113 }
1114 }
1115
1116
1121 public void resolvePhiFunctions() {
1122 for (int ins1 : hirMap.keySet()) {
1123 NHIRInstruction hir = hirMap.get(ins1);
1124 if (hir instanceof NHIRPhiFunction) {
1125 NHIRPhiFunction phi = (NHIRPhiFunction) hir;
1126 NBasicBlock block = phi.block;
1127 for (int i = 0; i < phi.getArguments().size(); i++) {
1128 NHIRInstruction arg = hirMap.get(phi.getArguments().get(i));
1129 if (arg.sType.equals("")) {
1130 continue;
1131 }
1132 NBasicBlock targetBlock = block.predecessors.get(i);
1133 NLIRMove move = new NLIRMove(arg.block, lirId++, arg.lir, phi.lir);
1134 int len = targetBlock.hir.size();
1135 if (isHIRJmp(hirMap.get(targetBlock.hir.get(len - 1)))) {
1136 targetBlock.lir.add(len - 1, move);
1137 } else {
1138 targetBlock.lir.add(move);
1139 }
1140 }
1141 }
1142 }
1143 }
1144
1145
1148 public void orderBlocks() {
1149 }
1151
1152
1158 public NBasicBlock blockAt(int id) {
1159 for (NBasicBlock b : this.basicBlocks) {
1160 if (b.getFirstLIRInstId() <= id && b.getLastLIRInstId() >= id) {
1161 return b;
1162 }
1163 }
1164 return null;
1165 }
1166
1167
1170 public void renumberLirInstructions() {
1171 int nextId = 0;
1172 for (NBasicBlock block : basicBlocks) {
1173 ArrayList<NLIRInstruction> newLir = new ArrayList<NLIRInstruction>();
1174 for (NLIRInstruction lir : block.lir) {
1175 if (lir instanceof NLIRLoadLocal && ((NLIRLoadLocal) lir).getLocal() < 4) {
1176 continue;
1178 }
1179 lir.id = nextId;
1180 nextId += 5; newLir.add(lir);
1182 }
1183 block.lir = newLir;
1184 }
1185 }
1186
1187
1191 public void allocatePhysicalRegisters() {
1192 for (NBasicBlock block : basicBlocks) {
1193 for (NLIRInstruction lir : block.lir) {
1194 lir.allocatePhysicalRegisters();
1195 }
1196 }
1197 }
1198
1199
1204 public void writeTuplesToStdOut(PrettyPrinter p) {
1205 p.indentRight();
1206 p.printf("[[ TUPLES ]]\n\n");
1207 for (NBasicBlock block : basicBlocks) {
1208 block.writeTuplesToStdOut(p);
1209 }
1210 p.indentLeft();
1211 }
1212
1213
1218 public void writeHirToStdOut(PrettyPrinter p) {
1219 p.indentRight();
1220 p.printf("[[ HIR ]]\n\n");
1221 for (NBasicBlock block : basicBlocks) {
1222 block.writeHirToStdOut(p);
1223 }
1224 p.indentLeft();
1225 }
1226
1227
1232 public void writeLirToStdOut(PrettyPrinter p) {
1233 p.indentRight();
1234 p.printf("[[ LIR ]]\n\n");
1235 for (NBasicBlock block : basicBlocks) {
1236 block.writeLirToStdOut(p);
1237 }
1238 p.indentLeft();
1239 }
1240
1241
1246 public void writeIntervalsToStdOut(PrettyPrinter p) {
1247 p.indentRight();
1248 p.printf("[[ INTERVALS ]]\n\n");
1249 for (NInterval interval : intervals) {
1250 interval.writeToStdOut(p);
1251 }
1252 p.indentLeft();
1253 p.println();
1254 }
1255
1256 private void findLeaders(ArrayList<NTuple> tuples, NTuple[] tupleAt) {
1258 tuples.get(0).isLeader = true;
1259 for (int j = 1; j < tuples.size(); j++) {
1260 NTuple tuple = tuples.get(j);
1261 boolean jumpInstruction = true;
1262 short operandByte1, operandByte2, operandByte3, operandByte4;
1263 int offset;
1264 switch (tuple.opcode) {
1265 case IFEQ:
1266 case IFNE:
1267 case IFLT:
1268 case IFGE:
1269 case IFGT:
1270 case IFLE:
1271 case IF_ICMPEQ:
1272 case IF_ICMPNE:
1273 case IF_ICMPLT:
1274 case IF_ICMPGE:
1275 case IF_ICMPGT:
1276 case IF_ICMPLE:
1277 case IF_ACMPEQ:
1278 case IF_ACMPNE:
1279 case GOTO:
1280 case JSR:
1281 case IFNULL:
1282 case IFNONNULL:
1283 operandByte1 = tuple.operands.get(0);
1284 operandByte2 = tuple.operands.get(1);
1285 offset = shortValue(operandByte1, operandByte2);
1286 tupleAt[tuple.pc + offset].isLeader = true;
1287 break;
1288 case GOTO_W:
1289 case JSR_W:
1290 operandByte1 = tuple.operands.get(0);
1291 operandByte2 = tuple.operands.get(1);
1292 operandByte3 = tuple.operands.get(2);
1293 operandByte4 = tuple.operands.get(3);
1294 offset = intValue(operandByte1, operandByte2, operandByte3, operandByte4);
1295 tupleAt[tuple.pc + offset].isLeader = true;
1296 break;
1297 case IRETURN:
1298 case LRETURN:
1299 case FRETURN:
1300 case DRETURN:
1301 case ARETURN:
1302 case RETURN:
1303 case RET:
1304 case ATHROW:
1305 break;
1306 case TABLESWITCH: break;
1308 case LOOKUPSWITCH: break;
1310 default:
1311 jumpInstruction = false;
1312 }
1313 if (jumpInstruction) {
1314 if (j < tuples.size() - 1) {
1315 tuples.get(j + 1).isLeader = true;
1316 }
1317 }
1318 }
1319
1320 }
1321
1322 private void buildBasicBlocks(ArrayList<NTuple> tuples) {
1324 blockId = 0;
1325 NBasicBlock block = new NBasicBlock(this, blockId++);
1326 for (NTuple tuple : tuples) {
1327 if (tuple.isLeader) {
1328 basicBlocks.add(block);
1329 block = new NBasicBlock(this, blockId++);
1330 if (!pcToBasicBlock.containsKey(tuple.pc)) {
1331 pcToBasicBlock.put(tuple.pc, block);
1332 }
1333 }
1334 block.tuples.add(tuple);
1335 }
1336 basicBlocks.add(block);
1337 }
1338
1339 private boolean isHIRJmp(NHIRInstruction instr) {
1341 return (instr instanceof NHIRGoto || instr instanceof NHIRConditionalJump);
1342 }
1343
1344 private void clearBlockVisitations() {
1346 for (NBasicBlock block : basicBlocks) {
1347 block.visited = false;
1348 }
1349 }
1350
1351 private NBasicBlock commonDom(NBasicBlock b, NBasicBlock pred) {
1353 NBasicBlock dom = b;
1354 clearBlockVisitations();
1355 while (dom != null) {
1356 dom.visited = true;
1357 dom = dom.dom;
1358 }
1359 dom = pred;
1360 while (!dom.visited) {
1361 dom = dom.dom;
1362 }
1363 return dom;
1364 }
1365
1366 private void mergeLocals(NBasicBlock block) {
1369 for (NBasicBlock other : block.predecessors) {
1370 mergeLocals(block, other);
1371 }
1372 }
1373
1374 private void mergeLocals(NBasicBlock a, NBasicBlock b) {
1376 for (int i = 0; i < a.locals.length; i++) {
1377 if (a.cfg.hirMap.get(a.locals[i]).equals(b.cfg.hirMap.get(b.locals[i]))) {
1378 continue;
1379 } else {
1380 ArrayList<Integer> args = new ArrayList<Integer>();
1381 args.add(a.locals[i]);
1382 args.add(b.locals[i]);
1383 NHIRInstruction ins = new NHIRPhiFunction(a, NControlFlowGraph.hirId++, args, i);
1384 a.locals[i] = ins.id;
1385 a.hir.add(ins.id);
1386 a.cfg.hirMap.put(ins.id, ins);
1387 ((NHIRPhiFunction) ins).inferType();
1388 }
1389 }
1390 }
1391
1392 private ArrayList<NTuple> bytecodeToTuples(ArrayList<Integer> code) {
1394 ArrayList<NTuple> tuples = new ArrayList<NTuple>();
1395 for (int i = 0; i < code.size(); i++) {
1396 int pc = i;
1397 int opcode = code.get(i);
1398 int operandBytes = CLInstruction.instructionInfo[opcode].operandCount;
1399 short operandByte1, operandByte2, operandByte3, operandByte4;
1400 ArrayList<Short> operands = new ArrayList<Short>();
1401 switch (operandBytes) {
1402 case 0:
1403 break;
1404 case 1:
1405 operandByte1 = code.get(++i).shortValue();
1406 operands.add(operandByte1);
1407 break;
1408 case 2:
1409 operandByte1 = code.get(++i).shortValue();
1410 operandByte2 = code.get(++i).shortValue();
1411 operands.add(operandByte1);
1412 operands.add(operandByte2);
1413 break;
1414 case 3:
1415 operandByte1 = code.get(++i).shortValue();
1416 operandByte2 = code.get(++i).shortValue();
1417 operandByte3 = code.get(++i).shortValue();
1418 operands.add(operandByte1);
1419 operands.add(operandByte2);
1420 operands.add(operandByte3);
1421 break;
1422 case 4:
1423 operandByte1 = code.get(++i).shortValue();
1424 operandByte2 = code.get(++i).shortValue();
1425 operandByte3 = code.get(++i).shortValue();
1426 operandByte4 = code.get(++i).shortValue();
1427 operands.add(operandByte1);
1428 operands.add(operandByte2);
1429 operands.add(operandByte3);
1430 operands.add(operandByte4);
1431 break;
1432 case DYNAMIC: break;
1434 }
1435 tuples.add(new NTuple(pc, opcode, operands));
1436 }
1437 return tuples;
1438 }
1439
1440 private short shortValue(short a, short b) {
1442 return (short) ((a << 8) | b);
1443 }
1444
1445 private int intValue(short a, short b, short c, short d) {
1447 return (a << 24) | (b << 16) | (c << 8) | d;
1448 }
1449
1450 private ArrayList<Integer> getByteCode() {
1452 ArrayList<Integer> code = null;
1453 for (CLAttributeInfo info : m.attributes) {
1454 if (info instanceof CLCodeAttribute) {
1455 code = ((CLCodeAttribute) info).code;
1456 break;
1457 }
1458 }
1459 return code;
1460 }
1461
1462 private String shortType(String descriptor) {
1464 String sType = "V";
1465 char c = descriptor.charAt(0);
1466 switch (c) {
1467 case 'B':
1468 case 'C':
1469 case 'I':
1470 case 'F':
1471 case 'S':
1472 case 'Z':
1473 case 'J':
1474 case 'D':
1475 sType = c + "";
1476 break;
1477 case '[':
1478 case 'L':
1479 sType = "L";
1480 break;
1481 }
1482 return sType;
1483 }
1484
1485 private int numLocals() {
1487 ArrayList<Integer> code = null;
1488 int numLocals = 0;
1489 for (CLAttributeInfo info : m.attributes) {
1490 if (info instanceof CLCodeAttribute) {
1491 code = ((CLCodeAttribute) info).code;
1492 numLocals = ((CLCodeAttribute) info).maxLocals;
1493 break;
1494 }
1495 }
1496 return numLocals;
1497 }
1498
1499 private int argumentCount(String descriptor) {
1502 int i = 0;
1503 String argTypes = descriptor.substring(1, descriptor.lastIndexOf(")"));
1504 for (int j = 0; j < argTypes.length(); j++) {
1505 char c = argTypes.charAt(j);
1506 switch (c) {
1507 case 'B':
1508 case 'C':
1509 case 'I':
1510 case 'F':
1511 case 'S':
1512 case 'Z':
1513 i += 1;
1514 break;
1515 case '[':
1516 break;
1517 case 'J':
1518 case 'D':
1519 i += 2;
1520 break;
1521 case 'L':
1522 int k = argTypes.indexOf(";", j);
1523 j = k;
1524 i += 1;
1525 break;
1526 }
1527 }
1528 return i;
1529 }
1530
1531 private ArrayList<String> argumentTypes(String descriptor) {
1533 ArrayList<String> args = new ArrayList<String>();
1534 int i = 0;
1535 String argTypes = descriptor.substring(1, descriptor.lastIndexOf(")"));
1536 String type = "";
1537 for (int j = 0; j < argTypes.length(); j++) {
1538 char c = argTypes.charAt(j);
1539 switch (c) {
1540 case 'B':
1541 case 'C':
1542 case 'I':
1543 case 'F':
1544 case 'S':
1545 case 'Z':
1546 case 'J':
1547 case 'D':
1548 args.add(type + String.valueOf(c));
1549 type = "";
1550 break;
1551 case '[':
1552 type += c;
1553 break;
1554 case 'L':
1555 int k = argTypes.indexOf(";", j);
1556 args.add(type + argTypes.substring(j, k));
1557 type = "";
1558 j = k;
1559 break;
1560 }
1561 }
1562 return args;
1563 }
1564
1565 private String returnType(String descriptor) {
1567 return descriptor.substring(descriptor.lastIndexOf(")") + 1);
1568 }
1569}
1570