1   // Copyright 2012- Bill Campbell, Swami Iyer and Bahar Akbal-Delibas
2   
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  /**
17   * A tuple representation of a JVM instruction.
18   */
19  class NTuple {
20      /**
21       * Program counter of the instruction.
22       */
23      public int pc;
24  
25      /**
26       * Opcode of the instruction.
27       */
28      public int opcode;
29  
30      /**
31       * Operands of the instructions.
32       */
33      public ArrayList<Short> operands;
34  
35      /**
36       * String representation (mnemonic) of the instruction.
37       */
38      public String mnemonic;
39  
40      /**
41       * Is this tuple the leader of the block containing it.
42       */
43      public boolean isLeader;
44  
45      /**
46       * Construct a tuple representing the JVM instruction.
47       *
48       * @param pc       program counter.
49       * @param opcode   opcode of the instruction.
50       * @param operands list of operands of the instruction.
51       */
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      /**
61       * Write the information pertaining to this tuple to standard output.
62       *
63       * @param p for pretty printing with indentation.
64       */
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  /**
75   * Representation of a block within a control flow graph.
76   */
77  class NBasicBlock {
78      /**
79       * The control flow graph (cfg) that this block belongs to.
80       */
81      public NControlFlowGraph cfg;
82  
83      /**
84       * Unique identifier of ths block.
85       */
86      public int id;
87  
88      /**
89       * List of tuples in this block.
90       */
91      public ArrayList<NTuple> tuples;
92  
93      /**
94       * List of predecessor blocks.
95       */
96      public ArrayList<NBasicBlock> predecessors;
97  
98      /**
99       * List of successor blocks.
100      */
101     public ArrayList<NBasicBlock> successors;
102 
103     /**
104      * List of high-level (HIR) instructions in this block.
105      */
106     public ArrayList<Integer> hir;
107 
108     /**
109      * List of low-level (LIR) instructions in this block.
110      */
111     public ArrayList<NLIRInstruction> lir;
112 
113     /**
114      * The state array for this block that maps local variable index to the HIR instruction that
115      * last affected it.
116      */
117     public int[] locals;
118 
119     /**
120      * Has this block been visited?
121      */
122     public boolean visited;
123 
124     /**
125      * Is this block active?
126      */
127     public boolean active;
128 
129     /**
130      * Is this block a loop head?
131      */
132     public boolean isLoopHead;
133 
134     /**
135      * Is this block a loop tail?
136      */
137     public boolean isLoopTail;
138 
139     /**
140      * Index of a loop.
141      */
142     public int loopIndex;
143 
144     /**
145      * Depth of a loop.
146      */
147     public int loopDepth;
148 
149     /**
150      * Number of forward branches to this block.
151      */
152     public int fwdBranches;
153 
154     /**
155      * Number of backward branches to this block.
156      */
157     public int bwdBranches;
158 
159     /**
160      * Ref count of this block.
161      */
162     public int ref;
163 
164     /**
165      * The dominator of this block.
166      */
167     public NBasicBlock dom;
168 
169     /**
170      * All virtual registers locally defined within this block.
171      */
172     public BitSet liveDef;
173 
174     /**
175      * All virtual registers used before definition within this block.
176      */
177     public BitSet liveUse;
178 
179     /**
180      * All virtual registers live in the block.
181      */
182     public BitSet liveIn;
183 
184     /**
185      * All virtual registers live outside the block.
186      */
187     public BitSet liveOut;
188 
189     /**
190      * Constructs a basic block.
191      *
192      * @param cfg the cfg containing this block.
193      * @param id  id of the block.
194      */
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     /**
207      * Returns a string identifier of this block.
208      *
209      * @return a string identifier of this block.
210      */
211     public String id() {
212         return "B" + id;
213     }
214 
215     /**
216      * Returns true if this block and other have the same id, and false otherwise.
217      *
218      * @param other the other block.
219      * @return true if this block and other have the same id, and false otherwise.
220      */
221     public boolean equals(NBasicBlock other) {
222         return this.id == other.id;
223     }
224 
225     /**
226      * Returns a string representation of this block.
227      *
228      * @return a string representation of this block.
229      */
230     public String toString() {
231         return "[B" + id + "]";
232     }
233 
234     /**
235      * Writes the tuples in this block to standard output.
236      *
237      * @param p for pretty printing with indentation.
238      */
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     /**
249      * Writes the HIR instructions in this block to standard output.
250      *
251      * @param p for pretty printing with indentation.
252      */
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     /**
298      * Writes the LIR instructions in this block to standard output.
299      *
300      * @param p for pretty printing with indentation.
301      */
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     /**
311      * Returns the instruction identifier for the first LIR instruction, or -1.
312      *
313      * @return the instruction identifier for the first LIR instruction, or -1.
314      */
315     public int getFirstLIRInstId() {
316         return lir.isEmpty() ? -1 : lir.get(0).id;
317     }
318 
319     /**
320      * Returns the instruction identifier for the last LIR instruction, or -1.
321      *
322      * @return the instruction identifier for the last LIR instruction, or -1.
323      */
324     public int getLastLIRInstId() {
325         return lir.isEmpty() ? -1 : lir.get(lir.size() - 1).id;
326     }
327 
328     /**
329      * Returns the LIR instruction with the given id, or null.
330      *
331      * @param id the id to look for.
332      * @return the LIR instruction with the given id, or null.
333      */
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     /**
344      * Returns true if there is no LIR instruction with the given id, and false otherwise.
345      *
346      * @param id the id to check for.
347      * @return true if there is no LIR instruction with the given id, and false otherwise.
348      */
349     public boolean idIsFree(int id) {
350         return getInstruction(id) == null;
351     }
352 
353     /**
354      * Inserts the given LIR instruction at the appropriate place in this block's lir array based
355      * on its id -- preserving order by id.
356      *
357      * @param inst the LIR instruction to be inserted.
358      */
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 /**
375  * Representation of a control flow graph (cfg) for a method.
376  */
377 class NControlFlowGraph {
378     // Constant pool for the class containing the method.
379     private CLConstantPool cp;
380 
381     // Contains information about the method.
382     private CLMethodInfo m;
383 
384     // Maps the pc of a JVM instruction to the block it's in.
385     private HashMap<Integer, NBasicBlock> pcToBasicBlock;
386 
387     /**
388      * Block identifier.
389      */
390     public static int blockId;
391 
392     /**
393      * HIR instruction identifier.
394      */
395     public static int hirId;
396 
397     /**
398      * HIR instruction identifier.
399      */
400     public static int lirId;
401 
402     /**
403      * Virtual register identifier.
404      */
405     public static int regId;
406 
407     /**
408      * Stack offset counter..
409      */
410     public int offset;
411 
412     /**
413      * Loop identifier.
414      */
415     public static int loopIndex;
416 
417     /**
418      * Name of the method this cfg corresponds to.
419      */
420     public String name;
421 
422     /**
423      * Descriptor of the method this cfg corresponds to.
424      */
425     public String desc;
426 
427     /**
428      * List of blocks forming the cfg for the method.
429      */
430     public ArrayList<NBasicBlock> basicBlocks;
431 
432     /**
433      * Maps HIR instruction ids in this cfg to HIR instructions.
434      */
435     public TreeMap<Integer, NHIRInstruction> hirMap;
436 
437     /**
438      * Registers allocated for this cfg by the HIR to LIR conversion algorithm.
439      */
440     public ArrayList<NRegister> registers;
441 
442     /**
443      * The total number of intervals. This is used to name split children and grows as more
444      * intervals are created by spills.
445      */
446     public int maxIntervals;
447 
448     /**
449      * Physical registers allocated for this cfg by the HIR to LIR conversion algorithm.
450      */
451     public ArrayList<NPhysicalRegister> pRegisters;
452 
453     /**
454      * Intervals allocated by the register allocation algorithm.
455      */
456     public ArrayList<NInterval> intervals;
457 
458     /**
459      * Used to construct jump labels in spim output.
460      */
461     public String labelPrefix;
462 
463     /**
464      * SPIM code for string literals added to the data segment.
465      */
466     public ArrayList<String> data;
467 
468     /**
469      * Constructs a NControlFlowGraph object for a method..
470      *
471      * @param cp constant pool for the class containing the method.
472      * @param m  contains information about the method.
473      */
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         // Identify the leaders.
492         findLeaders(tuples, tupleAt);
493 
494         // Form blocks.
495         buildBasicBlocks(tuples);
496 
497         // Connect up the blocks for this method, ie, build its control flow graph.
498         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: // Unsupported
574                     break;
575                 case LOOKUPSWITCH: // Unsupported
576                     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         // Calculate the ref count and number of forward branches to each block in the this cfg.
586         for (NBasicBlock block : basicBlocks) {
587             block.ref = block.predecessors.size();
588             block.fwdBranches = block.predecessors.size() - block.bwdBranches;
589         }
590     }
591 
592     /**
593      * Implements loop detection algorithm to figure out if the specified block is a loop head or
594      * a loop tail. Also calculates the number of backward branches to the block.
595      *
596      * @param block a block.
597      * @param pred  block's predecessor or null.
598      */
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     /**
616      * Removes blocks that cannot be reached from the begin block (B0). Also removes these blocks
617      * from the predecessor lists.
618      */
619     public void removeUnreachableBlocks() {
620         // Create a list of blocks that cannot be reached.
621         ArrayList<NBasicBlock> toRemove = new ArrayList<NBasicBlock>();
622         for (NBasicBlock block : basicBlocks) {
623             if (!block.visited) {
624                 toRemove.add(block);
625             }
626         }
627 
628         // From the predecessor list for each blocks, remove the ones that are in toRemove list.
629         for (NBasicBlock block : basicBlocks) {
630             for (NBasicBlock pred : toRemove) {
631                 block.predecessors.remove(pred);
632             }
633         }
634 
635         // From the list of all blocks, remove the ones that are in toRemove list.
636         for (NBasicBlock block : toRemove) {
637             basicBlocks.remove(block);
638         }
639     }
640 
641     /**
642      * Computes the dominator of each block in this cfg recursively given the starting block and
643      * its predecessor.
644      *
645      * @param block starting block.
646      * @param pred  block's predecessor.
647      */
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     /**
665      * Converts tuples in each block to their high-level (HIR) representations.
666      */
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             // Convert tuples in block to HIR instructions.
703             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                         // Compute base address.
759                         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                         // Compute index.
768                         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                         // Compute base address.
788                         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                         // Compute index.
797                         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                         // Compute base address.
818                         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                         // Compute index.
827                         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                         // Only allowing ldc of string constants for now.
909                         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    /**
1054     * Carries out optimizations on the high-level instructions.
1055     */
1056    public void optimize() {
1057        // Unsupported.
1058    }
1059
1060    /**
1061     * Eliminates redundant phi functions of the form x = (y, x, x, ..., x) with y.
1062     */
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    /**
1089     * Converts the hir instructions in this cfg to lir instructions.
1090     */
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        // We now know how many virtual registers are needed, so we can initialize bitset fields
1106        // in each block that are needed for interval calculation.
1107        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    /**
1117     * Resolves the phi functions in this cfg, i.e., for each x = phi(x1, x2, ..., xn) generate
1118     * an (LIR) move xi, x instruction at the end of the predecessor i of thte block defining the
1119     * phi function; if the instruction there is a branch, add the instruction prior to the branch.
1120     */
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    /**
1146     * Computes optimal ordering of the basic blocks in this cfg.
1147     */
1148    public void orderBlocks() {
1149        // Unsupported.
1150    }
1151
1152    /**
1153     * Returns the basic block at a particular instruction id, or null.
1154     *
1155     * @param id the (LIR) instruction id.
1156     * @return the basic block at a particular instruction id, or null.
1157     */
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    /**
1168     * Assigns new ids to the LIR instructions in this cfg.
1169     */
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                    // Ignore first four formals.
1177                    continue;
1178                }
1179                lir.id = nextId;
1180                nextId += 5; // Increment by 5 to accommodate spill instructions
1181                newLir.add(lir);
1182            }
1183            block.lir = newLir;
1184        }
1185    }
1186
1187    /**
1188     * Replaces references to virtual registers in LIR instructions with references to physical
1189     * registers.
1190     */
1191    public void allocatePhysicalRegisters() {
1192        for (NBasicBlock block : basicBlocks) {
1193            for (NLIRInstruction lir : block.lir) {
1194                lir.allocatePhysicalRegisters();
1195            }
1196        }
1197    }
1198
1199    /**
1200     * Writes the tuples in this cfg to standard output.
1201     *
1202     * @param p for pretty printing with indentation.
1203     */
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    /**
1214     * Writes the hir instructions in this cfg to standard output.
1215     *
1216     * @param p for pretty printing with indentation.
1217     */
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    /**
1228     * Writes the lir instructions in this cfg to standard output.
1229     *
1230     * @param p for pretty printing with indentation.
1231     */
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    /**
1242     * Writes the intervals in this cfg to standard output.
1243     *
1244     * @param p for pretty printing with indentation.
1245     */
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    // Finds the leaders for this control flow graph.
1257    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: // Unsupported
1307                    break;
1308                case LOOKUPSWITCH: // Unsupported
1309                    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    // Builds the basic blocks for this control flow graph.
1323    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    // Returns true if instr is a (conditional or unconditional) jump, and false otherwise.
1340    private boolean isHIRJmp(NHIRInstruction instr) {
1341        return (instr instanceof NHIRGoto || instr instanceof NHIRConditionalJump);
1342    }
1343
1344    // Clears the visitation information in each block in this cfg.
1345    private void clearBlockVisitations() {
1346        for (NBasicBlock block : basicBlocks) {
1347            block.visited = false;
1348        }
1349    }
1350
1351    // Returns the common dominator of the given basic block and its predecessor.
1352    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    // Merges the locals from each of the predecessors of the specified block with the locals in
1367    // the block.
1368    private void mergeLocals(NBasicBlock block) {
1369        for (NBasicBlock other : block.predecessors) {
1370            mergeLocals(block, other);
1371        }
1372    }
1373
1374    // Merges the locals in block b with the locals in block a.
1375    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    // Converts the bytecode in the specified list to their tuple representations.
1393    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: // Unsupported
1433                    break;
1434            }
1435            tuples.add(new NTuple(pc, opcode, operands));
1436        }
1437        return tuples;
1438    }
1439
1440    // Constructs and returns a short integer from two unsigned bytes specified.
1441    private short shortValue(short a, short b) {
1442        return (short) ((a << 8) | b);
1443    }
1444
1445    // Constructs and returns an integer from the four unsigned bytes specified.
1446    private int intValue(short a, short b, short c, short d) {
1447        return (a << 24) | (b << 16) | (c << 8) | d;
1448    }
1449
1450    // Extracts and returns the JVM bytecode for the method denoted by this cfg.
1451    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    // Returns the short form of the specified type descriptor.
1463    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    // Returns the number of local variables in the method denoted by this cfg.
1486    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    // Returns the argument count (number of formal parameters) for the method with the given
1500    // descriptor.
1501    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    // Returns a list containing the argument types for the method with the given descriptor.
1532    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    // Returns the return type of a method with the given descriptor, or "V" (for void).
1566    private String returnType(String descriptor) {
1567        return descriptor.substring(descriptor.lastIndexOf(")") + 1);
1568    }
1569}
1570