Java > Open Source Codes > org > cojen > classfile > InstructionList


1 /*
2  * Copyright 2004 Brian S O'Neill
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 package org.cojen.classfile;
18
19 import java.util.AbstractCollection ;
20 import java.util.ArrayList ;
21 import java.util.Collection ;
22 import java.util.HashMap ;
23 import java.util.HashSet ;
24 import java.util.Iterator ;
25 import java.util.List ;
26 import java.util.Map ;
27 import java.util.NoSuchElementException ;
28 import java.util.Set ;
29
30 /**
31  * The InstructionList class is used by the CodeBuilder to perform lower-level
32  * bookkeeping operations and flow analysis.
33  *
34  * @author Brian S O'Neill
35  * @see CodeBuilder
36  */
37 class InstructionList implements CodeBuffer {
38     private static final boolean DEBUG = false;
39
40     Instruction mFirst;
41     Instruction mLast;
42
43     boolean mResolved = false;
44
45     private List mExceptionHandlers = new ArrayList (4);
46     private List mLocalVariables = new ArrayList ();
47     private int mNextFixedVariableNumber;
48
49     private int mMaxStack;
50     private int mMaxLocals;
51
52     private byte[] mByteCodes;
53     private int mBufferLength;
54
55     protected InstructionList() {
56         super();
57     }
58
59     /**
60      * Returns an immutable collection of all the instructions in this
61      * InstructionList.
62      */
63     public Collection getInstructions() {
64         return new AbstractCollection () {
65             public Iterator iterator() {
66                 return new Iterator () {
67                     private Instruction mNext = mFirst;
68
69                     public boolean hasNext() {
70                         return mNext != null;
71                     }
72
73                     public Object next() {
74                         if (mNext == null) {
75                             throw new NoSuchElementException ();
76                         }
77
78                         Instruction current = mNext;
79                         mNext = mNext.mNext;
80                         return current;
81                     }
82
83                     public void remove() {
84                         throw new UnsupportedOperationException ();
85                     }
86                 };
87             }
88
89             public int size() {
90                 int count = 0;
91                 for (Instruction i = mFirst; i != null; i = i.mNext) {
92                     count++;
93                 }
94                 return count;
95             }
96         };
97     }
98
99     public int getMaxStackDepth() {
100         resolve();
101         return mMaxStack;
102     }
103
104     public int getMaxLocals() {
105         resolve();
106         return mMaxLocals;
107     }
108
109     public byte[] getByteCodes() {
110         resolve();
111         return mByteCodes;
112     }
113
114     public ExceptionHandler[] getExceptionHandlers() {
115         resolve();
116
117         ExceptionHandler[] handlers = new ExceptionHandler[mExceptionHandlers.size()];
118         return (ExceptionHandler[])mExceptionHandlers.toArray(handlers);
119     }
120
121     public void addExceptionHandler(ExceptionHandler handler) {
122         mExceptionHandlers.add(handler);
123     }
124
125     public LocalVariable createLocalVariable(String name, TypeDesc type) {
126         LocalVariable var = new LocalVariableImpl(mLocalVariables.size(), name, type, -1);
127         mLocalVariables.add(var);
128         return var;
129     }
130
131     /**
132      * All parameters must be defined before adding instructions.
133      */
134     public LocalVariable createLocalParameter(String name, TypeDesc type) {
135         LocalVariable var = new LocalVariableImpl
136             (mLocalVariables.size(), name, type, mNextFixedVariableNumber);
137         mLocalVariables.add(var);
138         mNextFixedVariableNumber += type.isDoubleWord() ? 2 : 1;
139         return var;
140     }
141
142     private void resolve() {
143         if (mResolved) {
144             return;
145         }
146
147         if (!DEBUG) {
148             resolve0();
149         } else {
150             try {
151                 resolve0();
152             } finally {
153                 System.out.println("-- Instructions --");
154
155                 Iterator it = getInstructions().iterator();
156                 while (it.hasNext()) {
157                     System.out.println(it.next());
158                 }
159             }
160         }
161     }
162
163     private void resolve0() {
164         mMaxStack = 0;
165         mMaxLocals = 0;
166
167         Instruction instr;
168
169         // Sweep through the instructions, preparing for flow analysis.
170 int instrCount = 0;
171         for (instr = mFirst; instr != null; instr = instr.mNext) {
172             // Set address to instruction index.
173 instr.reset(instrCount++);
174         }
175
176         // Make sure exception handlers are registered with all guarded
177 // instructions.
178 Iterator it = mExceptionHandlers.iterator();
179         while (it.hasNext()) {
180             ExceptionHandler handler = (ExceptionHandler)it.next();
181             instr = (Instruction)handler.getStartLocation();
182             Instruction end = (Instruction)handler.getEndLocation();
183             for ( ; instr != null && instr != end; instr = instr.mNext) {
184                 instr.addExceptionHandler(handler);
185             }
186         }
187
188         // Perform variable liveness flow analysis for each local variable, in
189 // order to determine which register it should be assigned. Takes
190 // advantage of the fact that instruction addresses are not yet
191 // resolved to true addresses, but are instead indexes. This means the
192 // liveness analysis operates on smaller BitLists, which makes some
193 // operations (i.e. intersection) a bit faster.
194 {
195             int size = mLocalVariables.size();
196             BitList[] liveIn = new BitList[size];
197             BitList[] liveOut = new BitList[size];
198             for (int v=0; v<size; v++) {
199                 liveIn[v] = new BitList(instrCount);
200                 liveOut[v] = new BitList(instrCount);
201             }
202             
203             livenessAnalysis(liveIn, liveOut);
204             
205             // Register number -> list of variables that use that register.
206 List registerUsers = new ArrayList ();
207             
208             // First fill up list with variables that have a fixed number.
209 for (int v=0; v<size; v++) {
210                 LocalVariableImpl var = (LocalVariableImpl)mLocalVariables.get(v);
211                 if (var.isFixedNumber()) {
212                     addRegisterUser(registerUsers, var);
213                     // Ensure that max locals is large enough to hold parameters.
214 int num = var.getNumber();
215                     if (var.isDoubleWord()) {
216                         num++;
217                     }
218                     if (num >= mMaxLocals) {
219                         mMaxLocals = num + 1;
220                     }
221                 }
222             }
223             
224             // Merge bit lists together.
225 BitList[] live = liveIn;
226             for (int v=0; v<size; v++) {
227                 live[v].or(liveOut[v]);
228                 if (live[v].isAllClear()) {
229                     // Variable isn't needed.
230 live[v] = null;
231                 }
232             }
233             
234             for (int v=0; v<size; v++) {
235                 if (live[v] == null) {
236                     continue;
237                 }
238                 LocalVariableImpl var = (LocalVariableImpl)mLocalVariables.get(v);
239                 if (var.isFixedNumber()) {
240                     continue;
241                 }
242                 int r = 0;
243                 while (true) {
244                     r = findAvailableRegister(registerUsers, r, live, v);
245                     if (var.isDoubleWord()) {
246                         if (findAvailableRegister(registerUsers, ++r, live, v) == r) {
247                             // Found consecutive registers, required for double word.
248 r--;
249                             break;
250                         }
251                     } else {
252                         break;
253                     }
254                 }
255                 var.setNumber(r);
256                 addRegisterUser(registerUsers, var);
257             }
258             
259             mMaxLocals = Math.max(mMaxLocals, registerUsers.size());
260         } // end liveness analysis
261
262         // Perform stack flow analysis to determine the max stack size.
263 {
264             // Start the flow analysis at the first instruction.
265 Map subAdjustMap = new HashMap (11);
266             stackResolve(0, mFirst, subAdjustMap);
267             
268             // Continue flow analysis into exception handler entry points.
269 it = mExceptionHandlers.iterator();
270             while (it.hasNext()) {
271                 ExceptionHandler handler = (ExceptionHandler)it.next();
272                 Instruction enter = (Instruction)handler.getCatchLocation();
273                 stackResolve(1, enter, subAdjustMap);
274             }
275         }
276             
277         // Okay, build up the byte code and set real instruction locations.
278 // Multiple passes may be required because instructions may adjust
279 // their size as locations are set. Changing size affects the
280 // locations of other instructions, so that is why additional passes
281 // are required.
282
283         boolean passAgain;
284         do {
285             passAgain = false;
286             
287             mByteCodes = new byte[instrCount * 2]; // estimate
288 mBufferLength = 0;
289             
290             for (instr = mFirst; instr != null; instr = instr.mNext) {
291                 if (!instr.isResolved()) {
292                     passAgain = true;
293                 }
294                 
295                 if (instr instanceof Label) {
296                     if (instr.mLocation != mBufferLength) {
297                         if (instr.mLocation >= 0) {
298                             // If the location of this label is not where it
299 // should be, (most likely because an instruction
300 // needed to expand in size) then do another pass.
301 passAgain = true;
302                         }
303                         instr.mLocation = mBufferLength;
304                     }
305                 } else {
306                     instr.mLocation = mBufferLength;
307                     
308                     byte[] bytes = instr.getBytes();
309                     if (bytes != null) {
310                         if (passAgain) {
311                             // If there is going to be another pass, don't
312 // bother collecting bytes into the array. Just
313 // expand the the length variable.
314 mBufferLength += bytes.length;
315                         } else {
316                             addBytes(bytes);
317                         }
318                     }
319                 }
320             }
321         } while (passAgain); // do {} while ();
322
323         if (mBufferLength != mByteCodes.length) {
324             byte[] newBytes = new byte[mBufferLength];
325             System.arraycopy(mByteCodes, 0, newBytes, 0, mBufferLength);
326             mByteCodes = newBytes;
327         }
328
329         // Set resolved at end because during resolution, this field gets
330 // set false again while changes are being made to the list
331 // of instructions.
332 mResolved = true;
333     }
334
335     private void addBytes(byte[] code) {
336         growBuffer(code.length);
337         System.arraycopy(code, 0, mByteCodes, mBufferLength, code.length);
338         mBufferLength += code.length;
339     }
340
341     private void growBuffer(int amount) {
342         if ((mBufferLength + amount) > mByteCodes.length) {
343             int newCapacity = mByteCodes.length * 2;
344             if ((mBufferLength + amount) > newCapacity) {
345                 newCapacity = mBufferLength + amount;
346             }
347
348             byte[] newBuffer = new byte[newCapacity];
349             System.arraycopy(mByteCodes, 0, newBuffer, 0, mBufferLength);
350             mByteCodes = newBuffer;
351         }
352     }
353
354     private void livenessAnalysis(BitList[] liveIn, BitList[] liveOut) {
355         // Track stores to variables to see if the result is discarded.
356 List [] localStores = new List [liveIn.length];
357
358         int passCount = -1;
359         boolean passAgain;
360         do {
361             passCount++;
362             passAgain = false;
363
364             for (Instruction instr = mLast; instr != null; instr = instr.mPrev) {
365                 int n = instr.getLocation();
366
367                 int useIndex = -1;
368                 int defIndex = -1;
369
370                 if (instr instanceof LocalOperandInstruction) {
371                     LocalOperandInstruction loi = (LocalOperandInstruction)instr;
372                     LocalVariableImpl var = loi.getLocalVariable();
373                     int varIndex = var.getIndex();
374
375                     if (loi.isLoad()) {
376                         useIndex = varIndex;
377                     }
378
379                     if (loi.isStore()) {
380                         defIndex = varIndex;
381                         if (passCount == 0 && loi instanceof StoreLocalInstruction) {
382                             List stores = localStores[varIndex];
383                             if (stores == null) {
384                                 stores = new ArrayList ();
385                                 localStores[varIndex] = stores;
386                             }
387                             stores.add(instr);
388                         }
389                     }
390                 }
391
392                 for (int v=liveIn.length; --v>=0; ) {
393                     boolean setLiveIn, setLiveOut;
394
395                     if (useIndex == v || (v != defIndex && liveOut[v].get(n))) {
396                         passAgain |= liveIn[v].set(n);
397                         setLiveIn = true;
398                     } else {
399                         setLiveIn = false;
400                     }
401
402                     setLiveOut = false;
403
404                     if (instr.isFlowThrough() && instr.mNext != null) {
405                         if (liveIn[v].get(instr.mNext.getLocation())) {
406                             setLiveOut = true;
407                             passAgain |= liveOut[v].set(n);
408                         }
409                     }
410
411                     Location[] targets = instr.getBranchTargets();
412                     if (targets != null) {
413                         for (int i=0; i<targets.length; i++) {
414                             Instruction targetInstr = (Instruction)targets[i];
415                             if (liveIn[v].get(targetInstr.getLocation())) {
416                                 setLiveOut = true;
417                                 passAgain |= liveOut[v].set(n);
418                             }
419                         }
420                     }
421
422                     Iterator handlers = instr.getExceptionHandlers();
423                     if (handlers != null) {
424                         while (handlers.hasNext()) {
425                             ExceptionHandler handler = (ExceptionHandler)handlers.next();
426                             Instruction catchInstr = (Instruction)handler.getCatchLocation();
427                             if (liveIn[v].get(catchInstr.getLocation())) {
428                                 setLiveOut = true;
429                                 passAgain |= liveOut[v].set(n);
430                             }
431                         }
432                     }
433
434                     if (!setLiveIn && setLiveOut && v != defIndex) {
435                         // Set liveIn entry now that liveOut has been
436 // updated. This greatly reduces the number of full
437 // passes required.
438 passAgain |= liveIn[v].set(n);
439                     }
440                 }
441             }
442         } while (passAgain); // do {} while ();
443
444         // See which local store instructions should discard their results.
445 for (int v=localStores.length; --v>=0; ) {
446             List stores = localStores[v];
447             if (stores != null) {
448                 for (int i=stores.size(); --i>=0; ) {
449                     StoreLocalInstruction instr = (StoreLocalInstruction)stores.get(i);
450                     if (!liveOut[v].get(instr.getLocation())) {
451                         instr.discardResult();
452                     }
453                 }
454             }
455         }
456     }
457
458     private void addRegisterUser(List registerUsers, LocalVariable var) {
459         int num = var.getNumber();
460         if (num < 0) {
461             throw new IllegalStateException ("Local variable number not resolved");
462         }
463         getRegisterUsers(registerUsers, num).add(var);
464         if (var.isDoubleWord()) {
465             getRegisterUsers(registerUsers, num + 1).add(var);
466         }
467     }
468
469     private List getRegisterUsers(List registerUsers, int num) {
470         while (registerUsers.size() <= num) {
471             registerUsers.add(new ArrayList ());
472         }
473         return (List )registerUsers.get(num);
474     }
475
476     /**
477      * @param registerUsers
478      * @param r index into registerUsers
479      * @return index into registerUsers which is available, which may be equal
480      * to r or equal to the size of registerUsers
481      */
482     private int findAvailableRegister(List registerUsers, int r, BitList[] live, int v) {
483         registerScan:
484         for (; r<registerUsers.size(); r++) {
485             List users = getRegisterUsers(registerUsers, r);
486             for (int i=0; i<users.size(); i++) {
487                 int v2 = ((LocalVariableImpl)users.get(i)).getIndex();
488                 if (live[v].intersects(live[v2])) {
489                     continue registerScan;
490                 }
491             }
492             break;
493         }
494         return r;
495     }
496
497     private int stackResolve(int stackDepth,
498                              Instruction instr,
499                              Map subAdjustMap) {
500         while (instr != null) {
501             // Set the stack depth, marking this instruction as being visited.
502 // If already visited, break out of this flow.
503 if (instr.mStackDepth < 0) {
504                 instr.mStackDepth = stackDepth;
505             } else {
506                 if (instr.mStackDepth != stackDepth) {
507                     throw new IllegalStateException
508                         ("Stack depth different at previously visited " +
509                          "instruction: " + instr.mStackDepth +
510                          " != " + stackDepth);
511                 }
512
513                 break;
514             }
515
516             // Determine the next instruction to flow down to.
517 Instruction next = null;
518
519             if (instr.isFlowThrough()) {
520                 if ((next = instr.mNext) == null) {
521                     throw new IllegalStateException ("Execution flows through end of method");
522                 }
523             }
524
525             stackDepth += instr.getStackAdjustment();
526             if (stackDepth > mMaxStack) {
527                 mMaxStack = stackDepth;
528             } else if (stackDepth < 0) {
529                 throw new IllegalStateException ("Stack depth is negative: " + stackDepth);
530             }
531
532             Location[] targets = instr.getBranchTargets();
533
534             if (targets != null) {
535                 for (int i=0; i<targets.length; i++) {
536                     LabelInstruction targetInstr = (LabelInstruction)targets[i];
537
538                     if (i == 0 && next == null) {
539                         // Flow to the first target if instruction doesn't
540 // flow to its next instruction.
541 next = targetInstr;
542                         continue;
543                     }
544
545                     if (!instr.isSubroutineCall()) {
546                         stackResolve(stackDepth, targetInstr, subAdjustMap);
547                     } else {
548                         Integer subAdjust = (Integer )subAdjustMap.get(targetInstr);
549
550                         if (subAdjust == null) {
551                             int newDepth = stackResolve(stackDepth, targetInstr, subAdjustMap);
552                             subAdjust = new Integer (newDepth - stackDepth);
553                             subAdjustMap.put(targetInstr, subAdjust);
554                         }
555
556                         stackDepth += subAdjust.intValue();
557                     }
558                 }
559             }
560
561             instr = next;
562         }
563
564         return stackDepth;
565     }
566
567     private class LocalVariableImpl implements LocalVariable {
568         private final int mIndex;
569
570         private String mName;
571         private TypeDesc mType;
572
573         private int mNumber;
574         private boolean mFixed;
575
576         public LocalVariableImpl(int index, String name, TypeDesc type, int number) {
577             mIndex = index;
578             mName = name;
579             mType = type;
580             mNumber = number;
581             if (number >= 0) {
582                 mFixed = true;
583             }
584         }
585
586         int getIndex() {
587             return mIndex;
588         }
589
590         /**
591          * May return null if this LocalVariable is unnamed.
592          */
593         public String getName() {
594             return mName;
595         }
596
597         public void setName(String name) {
598             mName = name;
599         }
600
601         public TypeDesc getType() {
602             return mType;
603         }
604
605         public boolean isDoubleWord() {
606             return mType.isDoubleWord();
607         }
608
609         public int getNumber() {
610             return mNumber;
611         }
612
613         public Set getLocationRangeSet() {
614             // TODO
615 return null;
616         }
617
618         public void setNumber(int number) {
619             mNumber = number;
620         }
621
622         public void setFixedNumber(int number) {
623             mNumber = number;
624             mFixed = true;
625         }
626
627         public boolean isFixedNumber() {
628             return mFixed;
629         }
630
631         public String toString() {
632             if (getName() != null) {
633                 return String.valueOf(getType()) + ' ' + getName();
634             } else {
635                 return String.valueOf(getType());
636             }
637         }
638     }
639
640     /////////////////////////////////////////////////////////////////////////
641 //
642 // Begin inner class definitions for instructions of the InstructionList.
643 //
644 /////////////////////////////////////////////////////////////////////////
645
646     /**
647      * An Instruction is an element in an InstructionList, and represents a
648      * Java byte code instruction.
649      */
650     public abstract class Instruction implements Location {
651         private int mStackAdjust;
652
653         Instruction mPrev;
654         Instruction mNext;
655
656         // Indicates what the stack depth is when this instruction is reached.
657 // Is -1 if not reached. Flow analysis sets this value.
658 int mStackDepth = -1;
659
660         // Indicates the address of this instruction is, or -1 if not known.
661 int mLocation = -1;
662
663         private Set mExceptionHandlers;
664
665         /**
666          * Newly created instructions are automatically added to the
667          * InstructionList.
668          */
669         public Instruction(int stackAdjust) {
670             mStackAdjust = stackAdjust;
671             add();
672         }
673
674         /**
675          * This constructor allows sub-classes to disable auto-adding to the
676          * InstructionList.
677          */
678         protected Instruction(int stackAdjust, boolean addInstruction) {
679             mStackAdjust = stackAdjust;
680
681             if (addInstruction) {
682                 add();
683             }
684         }
685
686         /**
687          * Add this instruction to the end of the InstructionList. If the
688          * Instruction is already in the list, then it is moved to the end.
689          */
690         protected void add() {
691             InstructionList.this.mResolved = false;
692
693             if (mPrev != null) {
694                 mPrev.mNext = mNext;
695             }
696
697             if (mNext != null) {
698                 mNext.mPrev = mPrev;
699             }
700
701             mNext = null;
702
703             if (InstructionList.this.mFirst == null) {
704                 mPrev = null;
705                 InstructionList.this.mFirst = this;
706             } else {
707                 mPrev = InstructionList.this.mLast;
708                 InstructionList.this.mLast.mNext = this;
709             }
710
711             InstructionList.this.mLast = this;
712         }
713
714         /**
715          * Insert an Instruction immediately following this one.
716          */
717         public void insert(Instruction instr) {
718             InstructionList.this.mResolved = false;
719
720             instr.mPrev = this;
721             instr.mNext = mNext;
722
723             mNext = instr;
724
725             if (this == InstructionList.this.mLast) {
726                 InstructionList.this.mLast = instr;
727             }
728         }
729
730         /**
731          * Removes this Instruction from its parent InstructionList.
732          */
733         public void remove() {
734             InstructionList.this.mResolved = false;
735
736             if (mPrev != null) {
737                 mPrev.mNext = mNext;
738             }
739
740             if (mNext != null) {
741                 mNext.mPrev = mPrev;
742             }
743
744             if (this == InstructionList.this.mFirst) {
745                 InstructionList.this.mFirst = mNext;
746             }
747
748             if (this == InstructionList.this.mLast) {
749                 InstructionList.this.mLast = mPrev;
750             }
751
752             mPrev = null;
753             mNext = null;
754         }
755
756         /**
757          * Replace this Instruction with another one.
758          */
759         public void replace(Instruction replacement) {
760             if (replacement == null) {
761                 remove();
762                 return;
763             }
764
765             InstructionList.this.mResolved = false;
766
767             replacement.mPrev = mPrev;
768             replacement.mNext = mNext;
769
770             if (mPrev != null) {
771                 mPrev.mNext = replacement;
772             }
773
774             if (mNext != null) {
775                 mNext.mPrev = replacement;
776             }
777
778             if (this == InstructionList.this.mFirst) {
779                 InstructionList.this.mFirst = replacement;
780             }
781
782             if (this == InstructionList.this.mLast) {
783                 InstructionList.this.mLast = replacement;
784             }
785         }
786
787         /**
788          * Returns a positive, negative or zero value indicating what affect
789          * this generated instruction has on the runtime stack.
790          */
791         public int getStackAdjustment() {
792             return mStackAdjust;
793         }
794
795         /**
796          * Returns the stack depth for when this instruction is reached. If the
797          * value is negative, then this instruction is never reached.
798          */
799         public int getStackDepth() {
800             return mStackDepth;
801         }
802
803         /**
804          * Returns the address of this instruction or -1 if not known.
805          */
806         public int getLocation() {
807             return mLocation;
808         }
809
810         /**
811          * Returns all of the targets that this instruction may branch to. Not
812          * all instructions support branching, and null is returned by default.
813          */
814         public Location[] getBranchTargets() {
815             return null;
816         }
817
818         /**
819          * Returns an all the exception handlers that wraps this instruction,
820          * or null if none.
821          */
822         public Iterator getExceptionHandlers() {
823             if (mExceptionHandlers == null) {
824                 return null;
825             }
826             return mExceptionHandlers.iterator();
827         }
828
829         /**
830          * Adds an exception handler that wraps this instruction.
831          */
832         public void addExceptionHandler(ExceptionHandler handler) {
833             if (mExceptionHandlers == null) {
834                 mExceptionHandlers = new HashSet (4);
835             }
836             mExceptionHandlers.add(handler);
837         }
838
839         /**
840          * Returns true if execution flow may continue after this instruction.
841          * It may be a goto, a method return, an exception throw or a
842          * subroutine return. Default implementation returns true.
843          */
844         public boolean isFlowThrough() {
845             return true;
846         }
847
848         public boolean isSubroutineCall() {
849             return false;
850         }
851
852         /**
853          * Returns null if this is a pseudo instruction and no bytes are
854          * generated.
855          */
856         public abstract byte[] getBytes();
857
858         /**
859          * An instruction is resolved when it has all information needed to
860          * generate correct byte code.
861          */
862         public abstract boolean isResolved();
863
864         public int compareTo(Object obj) {
865             if (this == obj) {
866                 return 0;
867             }
868             Location other = (Location)obj;
869
870             int loca = getLocation();
871             int locb = other.getLocation();
872
873             if (loca < locb) {
874                 return -1;
875             } else if (loca > locb) {
876                 return 1;
877             } else {
878                 return 0;
879             }
880         }
881
882         /**
883          * Returns a string containing the type of this instruction, the stack
884          * adjustment and the list of byte codes. Unvisted instructions are
885          * marked with an asterisk.
886          */
887         public String toString() {
888             String name = getClass().getName();
889             int index = name.lastIndexOf('.');
890             if (index >= 0) {
891                 name = name.substring(index + 1);
892             }
893             index = name.lastIndexOf('$');
894             if (index >= 0) {
895                 name = name.substring(index + 1);
896             }
897
898             StringBuffer buf = new StringBuffer (name.length() + 20);
899
900             int adjust = getStackAdjustment();
901             int depth = getStackDepth();
902
903             if (depth >= 0) {
904                 buf.append(' ');
905             } else {
906                 buf.append('*');
907             }
908
909             buf.append('[');
910             buf.append(mLocation);
911             buf.append("] ");
912
913             buf.append(name);
914             buf.append(" (");
915
916             if (depth >= 0) {
917                 buf.append(depth);
918                 buf.append(" + ");
919                 buf.append(adjust);
920                 buf.append(" = ");
921                 buf.append(depth + adjust);
922             } else {
923                 buf.append(adjust);
924             }
925
926             buf.append(") ");
927
928             try {
929                 byte[] bytes = getBytes();
930                 boolean wide = false;
931                 if (bytes != null) {
932                     for (int i=0; i<bytes.length; i++) {
933                         if (i > 0) {
934                             buf.append(',');
935                         }
936
937                         byte code = bytes[i];
938
939                         if (i == 0 || wide) {
940                             buf.append(Opcode.getMnemonic(code));
941                             wide = code == Opcode.WIDE;
942                         } else {
943                             buf.append(code & 0xff);
944                         }
945                     }
946                 }
947             } catch (Exception e) {
948             }
949
950             return buf.toString();
951         }
952
953         /**
954          * Reset this instruction in preparation for flow analysis.
955          */
956         void reset(int instrCount) {
957             mStackDepth = -1;
958             // Start with a fake location.
959 mLocation = instrCount;
960         }
961     }
962
963     /**
964      * Defines a pseudo instruction for a label. No byte code is ever generated
965      * from a label. Labels are not automatically added to the list.
966      */
967     public class LabelInstruction extends Instruction implements Label {
968         public LabelInstruction() {
969             super(0, false);
970         }
971
972         /**
973          * Set this label's branch location to be the current address
974          * in this label's parent CodeBuilder or InstructionList.
975          *
976          * @return This Label.
977          */
978         public Label setLocation() {
979             add();
980             return this;
981         }
982
983         /**
984          * @return -1 when not resolved yet
985          */
986         public int getLocation() throws IllegalStateException {
987             int loc;
988             if ((loc = mLocation) < 0) {
989                 if (mPrev == null && mNext == null) {
990                     throw new IllegalStateException ("Label location is not set");
991                 }
992             }
993             return loc;
994         }
995
996         /**
997          * Always returns null.
998          */
999         public byte[] getBytes() {
1000            return null;
1001        }
1002
1003        public boolean isResolved() {
1004            return getLocation() >= 0;
1005        }
1006    }
1007
1008    /**
1009     * Defines a code instruction and has storage for byte codes.
1010     */
1011    public class CodeInstruction extends Instruction {
1012        protected byte[] mBytes;
1013
1014        private Set mExceptionHandlers;
1015
1016        public CodeInstruction(int stackAdjust) {
1017            super(stackAdjust);
1018        }
1019
1020        protected CodeInstruction(int stackAdjust, boolean addInstruction) {
1021            super(stackAdjust, addInstruction);
1022        }
1023
1024        public CodeInstruction(int stackAdjust, byte b) {
1025            super(stackAdjust);
1026            mBytes = new byte[] {b};
1027        }
1028
1029        public CodeInstruction(int stackAdjust, byte[] bytes) {
1030            super(stackAdjust);
1031            mBytes = bytes;
1032        }
1033
1034        public boolean isFlowThrough() {
1035            if (mBytes != null && mBytes.length > 0) {
1036                switch (mBytes[0]) {
1037                case Opcode.GOTO:
1038                case Opcode.GOTO_W:
1039                case Opcode.IRETURN:
1040                case Opcode.LRETURN:
1041                case Opcode.FRETURN:
1042                case Opcode.DRETURN:
1043                case Opcode.ARETURN:
1044                case Opcode.RETURN:
1045                case Opcode.ATHROW:
1046                    return false;
1047                }
1048            }
1049
1050            return true;
1051        }
1052
1053        public byte[] getBytes() {
1054            return mBytes;
1055        }
1056
1057        public boolean isResolved() {
1058            return true;
1059        }
1060    }
1061
1062    /**
1063     * Defines a branch instruction, like a goto, jsr or any conditional
1064     * branch.
1065     */
1066    public class BranchInstruction extends CodeInstruction {
1067        private Location mTarget;
1068        private boolean mHasShortHop = false;
1069        private boolean mIsSub = false;
1070
1071        public BranchInstruction(int stackAdjust,
1072                                 byte opcode, Location target) {
1073            this(stackAdjust, true, opcode, target);
1074        }
1075
1076        private BranchInstruction(int stackAdjust, boolean addInstruction,
1077                                  byte opcode, Location target) {
1078            super(stackAdjust, addInstruction);
1079
1080            mTarget = target;
1081
1082            switch (opcode) {
1083            case Opcode.JSR_W:
1084                mIsSub = true;
1085                // Flow through to next case.
1086 case Opcode.GOTO_W:
1087                mBytes = new byte[5];
1088                mBytes[0] = opcode;
1089                break;
1090            case Opcode.JSR:
1091                mIsSub = true;
1092                // Flow through to next case.
1093 case Opcode.GOTO:
1094            case Opcode.IF_ACMPEQ:
1095            case Opcode.IF_ACMPNE:
1096            case Opcode.IF_ICMPEQ:
1097            case Opcode.IF_ICMPNE:
1098            case Opcode.IF_ICMPLT:
1099            case Opcode.IF_ICMPGE:
1100            case Opcode.IF_ICMPGT:
1101            case Opcode.IF_ICMPLE:
1102            case Opcode.IFEQ:
1103            case Opcode.IFNE:
1104            case Opcode.IFLT:
1105            case Opcode.IFGE:
1106            case Opcode.IFGT:
1107            case Opcode.IFLE:
1108            case Opcode.IFNONNULL:
1109            case Opcode.IFNULL:
1110                mBytes = new byte[3];
1111                mBytes[0] = opcode;
1112                break;
1113            default:
1114                throw new IllegalArgumentException
1115                    ("Opcode not a branch instruction: " +
1116                     Opcode.getMnemonic(opcode));
1117            }
1118        }
1119
1120        public Location[] getBranchTargets() {
1121            return new Location[] {mTarget};
1122        }
1123
1124        public boolean isSubroutineCall() {
1125            return mIsSub;
1126        }
1127
1128        public byte[] getBytes() {
1129            if (!isResolved() || mHasShortHop) {
1130                return mBytes;
1131            }
1132
1133            int offset = mTarget.getLocation() - mLocation;
1134            byte opcode = mBytes[0];
1135
1136            if (opcode == Opcode.GOTO_W || opcode == Opcode.JSR_W) {
1137                mBytes[1] = (byte)(offset >> 24);
1138                mBytes[2] = (byte)(offset >> 16);
1139                mBytes[3] = (byte)(offset >> 8);
1140                mBytes[4] = (byte)(offset >> 0);
1141            } else if (-32768 <= offset && offset <= 32767) {
1142                mBytes[1] = (byte)(offset >> 8);
1143                mBytes[2] = (byte)(offset >> 0);
1144            } else if (opcode == Opcode.GOTO || opcode == Opcode.JSR) {
1145                mBytes = new byte[5];
1146                if (opcode == Opcode.GOTO) {
1147                    mBytes[0] = Opcode.GOTO_W;
1148                } else {
1149                    mBytes[0] = Opcode.JSR_W;
1150                }
1151                mBytes[1] = (byte)(offset >> 24);
1152                mBytes[2] = (byte)(offset >> 16);
1153                mBytes[3] = (byte)(offset >> 8);
1154                mBytes[4] = (byte)(offset >> 0);
1155            } else {
1156                // The if branch requires a 32 bit offset.
1157
1158                // Convert:
1159 //
1160 // if <cond> goto target
1161 // // reached if <cond> false
1162 // target: // reached if <cond> true
1163
1164                // to this:
1165 //
1166 // if not <cond> goto shortHop
1167 // goto_w target
1168 // shortHop: // reached if <cond> false
1169 // target: // reached if <cond> true
1170
1171                mHasShortHop = true;
1172
1173                opcode = Opcode.reverseIfOpcode(opcode);
1174
1175                mBytes[0] = opcode;
1176                mBytes[1] = (byte)0;
1177                mBytes[2] = (byte)8;
1178
1179                // insert goto_w instruction after this one.
1180 insert
1181                    (new BranchInstruction(0, false, Opcode.GOTO_W, mTarget));
1182            }
1183
1184            return mBytes;
1185        }
1186
1187        public boolean isResolved() {
1188            return mTarget.getLocation() >= 0;
1189        }
1190    }
1191
1192    /**
1193     * Defines an instruction that has a single operand which references a
1194     * constant in the constant pool.
1195     */
1196    public class ConstantOperandInstruction extends CodeInstruction {
1197        private ConstantInfo mInfo;
1198
1199        public ConstantOperandInstruction(int stackAdjust,
1200                                          byte[] bytes,
1201                                          ConstantInfo info) {
1202            super(stackAdjust, bytes);
1203            mInfo = info;
1204        }
1205
1206        public byte[] getBytes() {
1207            int index = mInfo.getIndex();
1208
1209            if (index < 0) {
1210                throw new IllegalStateException ("Constant pool index not resolved");
1211            }
1212
1213            mBytes[1] = (byte)(index >> 8);
1214            mBytes[2] = (byte)index;
1215
1216            return mBytes;
1217        }
1218
1219        public boolean isResolved() {
1220            return mInfo.getIndex() >= 0;
1221        }
1222    }
1223
1224    /**
1225     * Defines an instruction that loads a constant onto the stack from the
1226     * constant pool.
1227     */
1228    public class LoadConstantInstruction extends CodeInstruction {
1229        private ConstantInfo mInfo;
1230        private boolean mWideOnly;
1231
1232        public LoadConstantInstruction(int stackAdjust,
1233                                       ConstantInfo info) {
1234            this(stackAdjust, info, false);
1235        }
1236
1237        public LoadConstantInstruction(int stackAdjust,
1238                                       ConstantInfo info,
1239                                       boolean wideOnly) {
1240            super(stackAdjust);
1241            mInfo = info;
1242            mWideOnly = wideOnly;
1243        }
1244
1245        public boolean isFlowThrough() {
1246            return true;
1247        }
1248
1249        public byte[] getBytes() {
1250            int index = mInfo.getIndex();
1251
1252            if (index < 0) {
1253                throw new IllegalStateException ("Constant pool index not resolved");
1254            }
1255
1256            if (mWideOnly) {
1257                byte[] bytes = new byte[3];
1258                bytes[0] = Opcode.LDC2_W;
1259                bytes[1] = (byte)(index >> 8);
1260                bytes[2] = (byte)index;
1261                return bytes;
1262            } else if (index <= 255) {
1263                byte[] bytes = new byte[2];
1264                bytes[0] = Opcode.LDC;
1265                bytes[1] = (byte)index;
1266                return bytes;
1267            } else {
1268                byte[] bytes = new byte[3];
1269                bytes[0] = Opcode.LDC_W;
1270                bytes[1] = (byte)(index >> 8);
1271                bytes[2] = (byte)index;
1272                return bytes;
1273            }
1274        }
1275
1276        public boolean isResolved() {
1277            return mInfo.getIndex() >= 0;
1278        }
1279    }
1280
1281    /**
1282     * Defines an instruction that contains an operand for referencing a
1283     * LocalVariable.
1284     */
1285    public abstract class LocalOperandInstruction extends CodeInstruction {
1286        protected LocalVariableImpl mLocal;
1287
1288        public LocalOperandInstruction(int stackAdjust, LocalVariable local) {
1289            super(stackAdjust);
1290            mLocal = (LocalVariableImpl)local;
1291        }
1292
1293        public boolean isResolved() {
1294            return mLocal.getNumber() >= 0;
1295        }
1296
1297        public LocalVariableImpl getLocalVariable() {
1298            return mLocal;
1299        }
1300
1301        public int getVariableNumber() {
1302            int varNum = mLocal.getNumber();
1303
1304            if (varNum < 0) {
1305                throw new IllegalStateException ("Local variable number not resolved");
1306            }
1307
1308            return varNum;
1309        }
1310
1311        public abstract boolean isLoad();
1312
1313        public abstract boolean isStore();
1314    }
1315
1316    /**
1317     * Defines an instruction that loads a local variable onto the stack.
1318     */
1319    public class LoadLocalInstruction extends LocalOperandInstruction {
1320        public LoadLocalInstruction(int stackAdjust, LocalVariable local) {
1321            super(stackAdjust, local);
1322        }
1323
1324        public boolean isFlowThrough() {
1325            return true;
1326        }
1327
1328        public byte[] getBytes() {
1329            int varNum = getVariableNumber();
1330            byte opcode;
1331            boolean writeIndex = false;
1332
1333            int typeCode = mLocal.getType().getTypeCode();
1334
1335            switch(varNum) {
1336            case 0:
1337                switch (typeCode) {
1338                default:
1339                    opcode = Opcode.ALOAD_0;
1340                    break;
1341                case TypeDesc.LONG_CODE:
1342                    opcode = Opcode.LLOAD_0;
1343                    break;
1344                case TypeDesc.FLOAT_CODE:
1345                    opcode = Opcode.FLOAD_0;
1346                    break;
1347                case TypeDesc.DOUBLE_CODE:
1348                    opcode = Opcode.DLOAD_0;
1349                    break;
1350                case TypeDesc.INT_CODE:
1351                case TypeDesc.BOOLEAN_CODE:
1352                case TypeDesc.BYTE_CODE:
1353                case TypeDesc.CHAR_CODE:
1354                case TypeDesc.SHORT_CODE:
1355                    opcode = Opcode.ILOAD_0;
1356                    break;
1357                }
1358                break;
1359            case 1:
1360                switch (typeCode) {
1361                default:
1362                    opcode = Opcode.ALOAD_1;
1363                    break;
1364                case TypeDesc.LONG_CODE:
1365                    opcode = Opcode.LLOAD_1;
1366                    break;
1367                case TypeDesc.FLOAT_CODE:
1368                    opcode = Opcode.FLOAD_1;
1369                    break;
1370                case TypeDesc.DOUBLE_CODE:
1371                    opcode = Opcode.DLOAD_1;
1372                    break;
1373                case TypeDesc.INT_CODE:
1374                case TypeDesc.BOOLEAN_CODE:
1375                case TypeDesc.BYTE_CODE:
1376                case TypeDesc.CHAR_CODE:
1377                case TypeDesc.SHORT_CODE:
1378                    opcode = Opcode.ILOAD_1;
1379                    break;
1380                }
1381                break;
1382            case 2:
1383                switch (typeCode) {
1384                default:
1385                    opcode = Opcode.ALOAD_2;
1386                    break;
1387                case TypeDesc.LONG_CODE:
1388                    opcode = Opcode.LLOAD_2;
1389                    break;
1390                case TypeDesc.FLOAT_CODE:
1391                    opcode = Opcode.FLOAD_2;
1392                    break;
1393                case TypeDesc.DOUBLE_CODE:
1394                    opcode = Opcode.DLOAD_2;
1395                    break;
1396                case TypeDesc.INT_CODE:
1397                case TypeDesc.BOOLEAN_CODE:
1398                case TypeDesc.BYTE_CODE:
1399                case TypeDesc.CHAR_CODE:
1400                case TypeDesc.SHORT_CODE:
1401                    opcode = Opcode.ILOAD_2;
1402                    break;
1403                }
1404                break;
1405            case 3:
1406                switch (typeCode) {
1407                default:
1408                    opcode = Opcode.ALOAD_3;
1409                    break;
1410                case TypeDesc.LONG_CODE:
1411                    opcode = Opcode.LLOAD_3;
1412                    break;
1413                case TypeDesc.FLOAT_CODE:
1414                    opcode = Opcode.FLOAD_3;
1415                    break;
1416                case TypeDesc.DOUBLE_CODE:
1417                    opcode = Opcode.DLOAD_3;
1418                    break;
1419                case TypeDesc.INT_CODE:
1420                case TypeDesc.BOOLEAN_CODE:
1421                case TypeDesc.BYTE_CODE:
1422                case TypeDesc.CHAR_CODE:
1423                case TypeDesc.SHORT_CODE:
1424                    opcode = Opcode.ILOAD_3;
1425                    break;
1426                }
1427                break;
1428            default:
1429                writeIndex = true;
1430
1431                switch (typeCode) {
1432                default:
1433                    opcode = Opcode.ALOAD;
1434                    break;
1435                case TypeDesc.LONG_CODE:
1436                    opcode = Opcode.LLOAD;
1437                    break;
1438                case TypeDesc.FLOAT_CODE:
1439                    opcode = Opcode.FLOAD;
1440                    break;
1441                case TypeDesc.DOUBLE_CODE:
1442                    opcode = Opcode.DLOAD;
1443                    break;
1444                case TypeDesc.INT_CODE:
1445                case TypeDesc.BOOLEAN_CODE:
1446                case TypeDesc.BYTE_CODE:
1447                case TypeDesc.CHAR_CODE:
1448                case TypeDesc.SHORT_CODE:
1449                    opcode = Opcode.ILOAD;
1450                    break;
1451                }
1452                break;
1453            }
1454
1455            if (!writeIndex) {
1456                mBytes = new byte[] { opcode };
1457            } else {
1458                if (varNum <= 255) {
1459                    mBytes = new byte[] { opcode, (byte)varNum };
1460                } else {
1461                    mBytes = new byte[]
1462                    {
1463                        Opcode.WIDE,
1464                        opcode,
1465                        (byte)(varNum >> 8),
1466                        (byte)varNum
1467                    };
1468                }
1469            }
1470
1471            return mBytes;
1472        }
1473
1474        public boolean isLoad() {
1475            return true;
1476        }
1477
1478        public boolean isStore() {
1479            return false;
1480        }
1481    }
1482
1483    /**
1484     * Defines an instruction that stores a value from the stack into a local
1485     * variable.
1486     */
1487    public class StoreLocalInstruction extends LocalOperandInstruction {
1488        private boolean mDiscardResult;
1489
1490        public StoreLocalInstruction(int stackAdjust, LocalVariable local) {
1491            super(stackAdjust, local);
1492        }
1493
1494        public boolean isFlowThrough() {
1495            return true;
1496        }
1497
1498        public byte[] getBytes() {
1499            if (mDiscardResult) {
1500                // Liveness analysis discovered that the results of this store
1501 // are not needed so just pop if off the stack.
1502 return new byte[] { mLocal.isDoubleWord() ? Opcode.POP2 : Opcode.POP };
1503            }
1504
1505            int varNum = getVariableNumber();
1506
1507            byte opcode;
1508            boolean writeIndex = false;
1509
1510            int typeCode = mLocal.getType().getTypeCode();
1511
1512            switch(varNum) {
1513            case 0:
1514                switch (typeCode) {
1515                default:
1516                    opcode = Opcode.ASTORE_0;
1517                    break;
1518                case TypeDesc.LONG_CODE:
1519                    opcode = Opcode.LSTORE_0;
1520                    break;
1521                case TypeDesc.FLOAT_CODE:
1522                    opcode = Opcode.FSTORE_0;
1523                    break;
1524                case TypeDesc.DOUBLE_CODE:
1525                    opcode = Opcode.DSTORE_0;
1526                    break;
1527                case TypeDesc.INT_CODE:
1528                case TypeDesc.BOOLEAN_CODE:
1529                case TypeDesc.BYTE_CODE:
1530                case TypeDesc.CHAR_CODE:
1531                case TypeDesc.SHORT_CODE:
1532                    opcode = Opcode.ISTORE_0;
1533                    break;
1534                }
1535                break;
1536            case 1:
1537                switch (typeCode) {
1538                default:
1539                    opcode = Opcode.ASTORE_1;
1540                    break;
1541                case TypeDesc.LONG_CODE:
1542                    opcode = Opcode.LSTORE_1;
1543                    break;
1544                case TypeDesc.FLOAT_CODE:
1545                    opcode = Opcode.FSTORE_1;
1546                    break;
1547                case TypeDesc.DOUBLE_CODE:
1548                    opcode = Opcode.DSTORE_1;
1549                    break;
1550                case TypeDesc.INT_CODE:
1551                case TypeDesc.BOOLEAN_CODE:
1552                case TypeDesc.BYTE_CODE:
1553                case TypeDesc.CHAR_CODE:
1554                case TypeDesc.SHORT_CODE:
1555                    opcode = Opcode.ISTORE_1;
1556                    break;
1557                }
1558                break;
1559            case 2:
1560                switch (typeCode) {
1561                default:
1562                    opcode = Opcode.ASTORE_2;
1563                    break;
1564                case TypeDesc.LONG_CODE:
1565                    opcode = Opcode.LSTORE_2;
1566                    break;
1567                case TypeDesc.FLOAT_CODE:
1568                    opcode = Opcode.FSTORE_2;
1569                    break;
1570                case TypeDesc.DOUBLE_CODE:
1571                    opcode = Opcode.DSTORE_2;
1572                    break;
1573                case TypeDesc.INT_CODE:
1574                case TypeDesc.BOOLEAN_CODE:
1575                case TypeDesc.BYTE_CODE:
1576                case TypeDesc.CHAR_CODE:
1577                case TypeDesc.SHORT_CODE:
1578                    opcode = Opcode.ISTORE_2;
1579                    break;
1580                }
1581                break;
1582            case 3:
1583                switch (typeCode) {
1584                default:
1585                    opcode = Opcode.ASTORE_3;
1586                    break;
1587                case TypeDesc.LONG_CODE:
1588                    opcode = Opcode.LSTORE_3;
1589                    break;
1590                case TypeDesc.FLOAT_CODE:
1591                    opcode = Opcode.FSTORE_3;
1592                    break;
1593                case TypeDesc.DOUBLE_CODE:
1594                    opcode = Opcode.DSTORE_3;
1595                    break;
1596                case TypeDesc.INT_CODE:
1597                case TypeDesc.BOOLEAN_CODE:
1598                case TypeDesc.BYTE_CODE:
1599                case TypeDesc.CHAR_CODE:
1600                case TypeDesc.SHORT_CODE:
1601                    opcode = Opcode.ISTORE_3;
1602                    break;
1603                }
1604                break;
1605            default:
1606                writeIndex = true;
1607
1608                switch (typeCode) {
1609                default:
1610                    opcode = Opcode.ASTORE;
1611                    break;
1612                case TypeDesc.LONG_CODE:
1613                    opcode = Opcode.LSTORE;
1614                    break;
1615                case TypeDesc.FLOAT_CODE:
1616                    opcode = Opcode.FSTORE;
1617                    break;
1618                case TypeDesc.DOUBLE_CODE:
1619                    opcode = Opcode.DSTORE;
1620                    break;
1621                case TypeDesc.INT_CODE:
1622                case TypeDesc.BOOLEAN_CODE:
1623                case TypeDesc.BYTE_CODE:
1624                case TypeDesc.CHAR_CODE:
1625                case TypeDesc.SHORT_CODE:
1626                    opcode = Opcode.ISTORE;
1627                    break;
1628                }
1629                break;
1630            }
1631
1632            if (!writeIndex) {
1633                mBytes = new byte[] { opcode };
1634            } else {
1635                if (varNum <= 255) {
1636                    mBytes = new byte[] { opcode, (byte)varNum };
1637                } else {
1638                    mBytes = new byte[]
1639                    {
1640                        Opcode.WIDE,
1641                        opcode,
1642                        (byte)(varNum >> 8),
1643                        (byte)varNum
1644                    };
1645                }
1646            }
1647
1648            return mBytes;
1649        }
1650
1651        public boolean isResolved() {
1652            return true;
1653        }
1654
1655        public boolean isLoad() {
1656            return false;
1657        }
1658
1659        public boolean isStore() {
1660            return true;
1661        }
1662
1663        public void discardResult() {
1664            mDiscardResult = true;
1665        }
1666    }
1667
1668    /**
1669     * Defines a ret instruction for returning from a jsr call.
1670     */
1671    public class RetInstruction extends LocalOperandInstruction {
1672        // Note: This instruction does not provide any branch targets. The
1673 // analysis for determining all possible return locations is
1674 // complicated. Instead, the stack flow analysis assumes that all jsr
1675 // calls are "well formed", and so it doesn't need to follow the ret
1676 // back to a "comes from" label. Liveness analysis could take advantage
1677 // of the branch targets, and reduce the set of variables used to
1678 // manage jsr return addresses. Since jsr/ret is used infrequently,
1679 // local variables used by ret are fixed and are not optimized.
1680
1681        public RetInstruction(LocalVariable local) {
1682            super(0, local);
1683            ((LocalVariableImpl)local).setFixedNumber(mNextFixedVariableNumber++);
1684        }
1685
1686        public boolean isFlowThrough() {
1687            return false;
1688        }
1689
1690        public byte[] getBytes() {
1691            int varNum = getVariableNumber();
1692
1693            if (varNum <= 255) {
1694                mBytes = new byte[] { Opcode.RET, (byte)varNum };
1695            } else {
1696                mBytes = new byte[]
1697                {
1698                    Opcode.WIDE,
1699                    Opcode.RET,
1700                    (byte)(varNum >> 8),
1701                    (byte)varNum
1702                };
1703            }
1704
1705            return mBytes;
1706        }
1707
1708        public boolean isLoad() {
1709            return true;
1710        }
1711
1712        public boolean isStore() {
1713            return false;
1714        }
1715    }
1716
1717    /**
1718     * Defines a specialized instruction that increments a local variable by
1719     * a signed 16-bit amount.
1720     */
1721    public class ShortIncrementInstruction extends LocalOperandInstruction {
1722        private short mAmount;
1723
1724        public ShortIncrementInstruction(LocalVariable local, short amount) {
1725            super(0, local);
1726            mAmount = amount;
1727        }
1728
1729        public boolean isFlowThrough() {
1730            return true;
1731        }
1732
1733        public byte[] getBytes() {
1734            int varNum = getVariableNumber();
1735
1736            if ((-128 <= mAmount && mAmount <= 127) && varNum <= 255) {
1737                mBytes = new byte[]
1738                { Opcode.IINC,
1739                  (byte)varNum,
1740                  (byte)mAmount
1741                };
1742            } else {
1743                mBytes = new byte[]
1744                {
1745                    Opcode.WIDE,
1746                    Opcode.IINC,
1747                    (byte)(varNum >> 8),
1748                    (byte)varNum,
1749                    (byte)(mAmount >> 8),
1750                    (byte)mAmount
1751                };
1752            }
1753
1754            return mBytes;
1755        }
1756
1757        public boolean isLoad() {
1758            return true;
1759        }
1760
1761        public boolean isStore() {
1762            return true;
1763        }
1764    }
1765
1766    /**
1767     * Defines a switch instruction. The choice of which actual switch
1768     * implementation to use (table or lookup switch) is determined
1769     * automatically based on which generates to the smallest amount of bytes.
1770     */
1771    public class SwitchInstruction extends CodeInstruction {
1772        private int[] mCases;
1773        private Location[] mLocations;
1774        private Location mDefaultLocation;
1775
1776        private byte mOpcode;
1777
1778        private int mSmallest;
1779        private int mLargest;
1780
1781        public SwitchInstruction(int[] casesParam,
1782                                 Location[] locationsParam,
1783                                 Location defaultLocation) {
1784            // A SwitchInstruction always adjusts the stack by -1 because it
1785 // pops the switch key off the stack.
1786 super(-1);
1787
1788            if (casesParam.length != locationsParam.length) {
1789                throw new IllegalArgumentException
1790                    ("Switch cases and locations sizes differ: " +
1791                     casesParam.length + ", " + locationsParam.length);
1792            }
1793
1794            mCases = new int[casesParam.length];
1795            System.arraycopy(casesParam, 0, mCases, 0, casesParam.length);
1796
1797            mLocations = new Location[locationsParam.length];
1798            System.arraycopy(locationsParam, 0, mLocations,
1799                             0, locationsParam.length);
1800
1801            mDefaultLocation = defaultLocation;
1802
1803            // First sort the cases and locations.
1804 sort(0, mCases.length - 1);
1805
1806            // Check for duplicate cases.
1807 int lastCase = 0;
1808            for (int i=0; i<mCases.length; i++) {
1809                if (i > 0 && mCases[i] == lastCase) {
1810                    throw new IllegalArgumentException ("Duplicate switch cases: " + lastCase);
1811                }
1812                lastCase = mCases[i];
1813            }
1814
1815            // Now determine which kind of switch to use.
1816
1817            mSmallest = mCases[0];
1818            mLargest = mCases[mCases.length - 1];
1819            int tSize = 12 + 4 * (mLargest - mSmallest + 1);
1820
1821            int lSize = 8 + 8 * mCases.length;
1822
1823            if (tSize <= lSize) {
1824                mOpcode = Opcode.TABLESWITCH;
1825            } else {
1826                mOpcode = Opcode.LOOKUPSWITCH;
1827            }
1828        }
1829
1830        public Location[] getBranchTargets() {
1831            Location[] targets = new Location[mLocations.length + 1];
1832            System.arraycopy(mLocations, 0, targets, 0, mLocations.length);
1833            targets[targets.length - 1] = mDefaultLocation;
1834
1835            return targets;
1836        }
1837
1838        public boolean isFlowThrough() {
1839            return false;
1840        }
1841
1842        public byte[] getBytes() {
1843            int length = 1;
1844            int pad = 3 - (mLocation & 3);
1845            length += pad;
1846
1847            if (mOpcode == Opcode.TABLESWITCH) {
1848                length += 12 + 4 * (mLargest - mSmallest + 1);
1849            } else {
1850                length += 8 + 8 * mCases.length;
1851            }
1852
1853            mBytes = new byte[length];
1854
1855            if (!isResolved()) {
1856                return mBytes;
1857            }
1858
1859            mBytes[0] = mOpcode;
1860            int cursor = pad + 1;
1861
1862            int defaultOffset = mDefaultLocation.getLocation() - mLocation;
1863            mBytes[cursor++] = (byte)(defaultOffset >> 24);
1864            mBytes[cursor++] = (byte)(defaultOffset >> 16);
1865            mBytes[cursor++] = (byte)(defaultOffset >> 8);
1866            mBytes[cursor++] = (byte)(defaultOffset >> 0);
1867
1868            if (mOpcode == Opcode.TABLESWITCH) {
1869                mBytes[cursor++] = (byte)(mSmallest >> 24);
1870                mBytes[cursor++] = (byte)(mSmallest >> 16);
1871                mBytes[cursor++] = (byte)(mSmallest >> 8);
1872                mBytes[cursor++] = (byte)(mSmallest >> 0);
1873
1874                mBytes[cursor++] = (byte)(mLargest >> 24);
1875                mBytes[cursor++] = (byte)(mLargest >> 16);
1876                mBytes[cursor++] = (byte)(mLargest >> 8);
1877                mBytes[cursor++] = (byte)(mLargest >> 0);
1878
1879                int index = 0;
1880                for (int case_ = mSmallest; case_ <= mLargest; case_++) {
1881                    if (case_ == mCases[index]) {
1882                        int offset =
1883                            mLocations[index].getLocation() - mLocation;
1884                        mBytes[cursor++] = (byte)(offset >> 24);
1885                        mBytes[cursor++] = (byte)(offset >> 16);
1886                        mBytes[cursor++] = (byte)(offset >> 8);
1887                        mBytes[cursor++] = (byte)(offset >> 0);
1888
1889                        index++;
1890                    } else {
1891                        mBytes[cursor++] = (byte)(defaultOffset >> 24);
1892                        mBytes[cursor++] = (byte)(defaultOffset >> 16);
1893                        mBytes[cursor++] = (byte)(defaultOffset >> 8);
1894                        mBytes[cursor++] = (byte)(defaultOffset >> 0);
1895                    }
1896                }
1897            } else {
1898                mBytes[cursor++] = (byte)(mCases.length >> 24);
1899                mBytes[cursor++] = (byte)(mCases.length >> 16);
1900                mBytes[cursor++] = (byte)(mCases.length >> 8);
1901                mBytes[cursor++] = (byte)(mCases.length >> 0);
1902
1903                for (int index = 0; index < mCases.length; index++) {
1904                    int case_ = mCases[index];
1905
1906                    mBytes[cursor++] = (byte)(case_ >> 24);
1907                    mBytes[cursor++] = (byte)(case_ >> 16);
1908                    mBytes[cursor++] = (byte)(case_ >> 8);
1909                    mBytes[cursor++] = (byte)(case_ >> 0);
1910
1911                    int offset = mLocations[index].getLocation() - mLocation;
1912                    mBytes[cursor++] = (byte)(offset >> 24);
1913                    mBytes[cursor++] = (byte)(offset >> 16);
1914                    mBytes[cursor++] = (byte)(offset >> 8);
1915                    mBytes[cursor++] = (byte)(offset >> 0);
1916                }
1917            }
1918
1919            return mBytes;
1920        }
1921
1922        public boolean isResolved() {
1923            if (mDefaultLocation.getLocation() >= 0) {
1924                for (int i=0; i<mLocations.length; i++) {
1925                    if (mLocations[i].getLocation() < 0) {
1926                        break;
1927                    }
1928                }
1929
1930                return true;
1931            }
1932
1933            return false;
1934        }
1935
1936        private void sort(int left, int right) {
1937            if (left >= right) {
1938                return;
1939            }
1940
1941            swap(left, (left + right) / 2); // move middle element to 0
1942
1943            int last = left;
1944
1945            for (int i = left + 1; i <= right; i++) {
1946                if (mCases[i] < mCases[left]) {
1947                    swap(++last, i);
1948                }
1949            }
1950
1951            swap(left, last);
1952            sort(left, last-1);
1953            sort(last + 1, right);
1954        }
1955
1956        private void swap(int i, int j) {
1957            int tempInt = mCases[i];
1958            mCases[i] = mCases[j];
1959            mCases[j] = tempInt;
1960
1961            Location tempLocation = mLocations[i];
1962            mLocations[i] = mLocations[j];
1963            mLocations[j] = tempLocation;
1964        }
1965    }
1966}
1967

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags