1 cananian 1.9.2.11 // Code.java, created Sun Sep 13 22:49:20 1998 by cananian
2 cananian 1.6 // Copyright (C) 1998 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.6 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1 package harpoon.IR.Bytecode;
5 cananian 1.1
6 cananian 1.9.2.6 import harpoon.ClassFile.HClass;
7 cananian 1.9.2.6 import harpoon.ClassFile.HCode;
8 cananian 1.9.2.14 import harpoon.ClassFile.HCodeAndMaps;
9 cananian 1.9.2.6 import harpoon.ClassFile.HCodeElement;
10 cananian 1.9.2.7 import harpoon.ClassFile.HCodeFactory;
11 cananian 1.9.2.6 import harpoon.ClassFile.HMethod;
12 cananian 1.9.2.12 import harpoon.ClassFile.Linker;
13 cananian 1.9.2.5 import harpoon.IR.RawClass.MethodInfo;
14 cananian 1.9.2.5 import harpoon.IR.RawClass.AttributeCode;
15 cananian 1.9.2.5 import harpoon.IR.RawClass.AttributeLineNumberTable;
16 cananian 1.9.2.5 import harpoon.IR.RawClass.LineNumberTable;
17 cananian 1.9.2.5 import harpoon.IR.RawClass.Constant;
18 cananian 1.9.2.14 import harpoon.Temp.TempMap;
19 cananian 1.14 import harpoon.Util.ArrayFactory;
20 cananian 1.14 import harpoon.Util.Collections.Graph;
21 cananian 1.1 import harpoon.Util.Util;
22 cananian 1.1
23 cananian 1.14 import java.util.AbstractSet;
24 cananian 1.9.2.9 import java.util.ArrayList;
25 cananian 1.9.2.9 import java.util.Collections;
26 cananian 1.5 import java.util.Enumeration;
27 cananian 1.9.2.9 import java.util.HashSet;
28 cananian 1.9.2.9 import java.util.List;
29 cananian 1.9.2.9 import java.util.Iterator;
30 cananian 1.9.2.14 import java.util.Map;
31 cananian 1.9.2.9 import java.util.Set;
32 cananian 1.1 /**
33 cananian 1.1 * <code>Bytecode.Code</code> is a code view that exposes the
34 cananian 1.1 * raw java classfile bytecodes.
35 cananian 1.1 *
36 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
37 cananian 1.14 * @version $Id: Code.java,v 1.14 2003/05/09 21:08:01 cananian Exp $
38 cananian 1.1 * @see harpoon.ClassFile.HCode
39 cananian 1.1 */
40 cananian 1.14 public class Code extends HCode implements Graph<Instr,InstrEdge> {
41 cananian 1.9.2.2 /** The name of this code view. */
42 cananian 1.9.2.2 public static final String codename = "bytecode";
43 cananian 1.1
44 cananian 1.9.2.12 final Linker linker;
45 cananian 1.9.2.12 final HMethod parent;
46 cananian 1.9.2.12 final MethodInfo methodinfo;
47 cananian 1.1
48 cananian 1.1 /** Constructor. */
49 cananian 1.1 public Code(HMethod parent, MethodInfo methodinfo) {
50 cananian 1.9.2.12 this.linker = parent.getDeclaringClass().getLinker();
51 cananian 1.1 this.parent = parent;
52 cananian 1.1 this.methodinfo = methodinfo;
53 cananian 1.8 }
54 cananian 1.8 /** Clone this code representation. The clone has its own copy of the
55 cananian 1.8 * bytecode graph. */
56 cananian 1.9.2.14 public HCodeAndMaps clone(HMethod newMethod) {
57 cananian 1.9.2.14 final HCode cloned = new Code(newMethod, methodinfo);
58 cananian 1.9.2.15 return new HCodeAndMaps(cloned, null, null, this, null, null);
59 cananian 1.1 }
60 cananian 1.1
61 cananian 1.1 /**
62 cananian 1.1 * Return the <code>HMethod</code> this codeview
63 cananian 1.1 * belongs to.
64 cananian 1.1 */
65 cananian 1.1 public HMethod getMethod() { return parent; }
66 cananian 1.1
67 cananian 1.1 /**
68 cananian 1.1 * Return the name of this code view, <code>"bytecode"</code>.
69 cananian 1.1 * @return the string <code>"bytecode"</code>.
70 cananian 1.1 */
71 cananian 1.9.2.2 public String getName() { return codename; }
72 cananian 1.1
73 cananian 1.1 /**
74 cananian 1.1 * Return an ordered list of the <code>Bytecode.Instr</code>s
75 cananian 1.1 * making up this code view. The first instruction to be
76 cananian 1.1 * executed is in element 0 of the array.
77 cananian 1.1 */
78 cananian 1.14 public List<Instr> getElementsL() {
79 cananian 1.1 if (elements==null) {
80 cananian 1.9.2.9 if (getCode()==null) return Collections.EMPTY_LIST; // no elements.
81 cananian 1.1 String sf = parent.getDeclaringClass().getSourceFile(); // source file.
82 cananian 1.1 byte[] code = getCode().code; // bytecode array.
83 cananian 1.1 // First locate merge nodes.
84 cananian 1.9.2.8 int[] merge = new int[code.length+1]; // init to 0.
85 cananian 1.7 merge[0]++; // the first instruction is reachable from outside.
86 cananian 1.1 for (int pc=0; pc<code.length; pc+=Op.instrSize(code, pc)) {
87 cananian 1.1 // if its a branch, mark the possible targets.
88 cananian 1.1 if (Op.isBranch(code[pc])) {
89 cananian 1.1 int[] targets = Op.branchTargets(code, pc);
90 cananian 1.1 for (int i=0; i<targets.length; i++)
91 cananian 1.1 merge[targets[i]]++; // mark a jump to this pc.
92 cananian 1.1 }
93 cananian 1.1 // unless its an unconditional branch, we can fall through to the
94 cananian 1.1 // next instr, too. Note that we shouldn't be able to fall off
95 cananian 1.1 // the end of the method.
96 cananian 1.1 if ((!Op.isUnconditionalBranch(code[pc])) ||
97 cananian 1.1 Op.isJSR(code[pc])) // jsrs eventually return to next instr, too.
98 cananian 1.1 merge[pc+Op.instrSize(code, pc)]++;
99 cananian 1.1 }
100 cananian 1.1 // try handlers count as targets, too
101 cananian 1.1 for (int i=0; i<getCode().exception_table.length; i++)
102 cananian 1.1 merge[getCode().exception_table[i].handler_pc]++;
103 cananian 1.1
104 cananian 1.9.2.8 // if merge[code.length]!=0, then execution may run off end of method.
105 cananian 1.9.2.8 if (merge[code.length]>0)
106 cananian 1.9.2.8 System.err.println("WARNING: execution may run off end of "+parent);
107 cananian 1.9.2.8
108 cananian 1.1 // now all pc's for which merge>1 are merge nodes.
109 cananian 1.1 Instr[] sparse = new Instr[code.length]; // index by pc still.
110 cananian 1.1 // crank through and add instrs without making links.
111 cananian 1.14 List<Instr> v = new ArrayList<Instr>(code.length);
112 cananian 1.1 for (int pc=0; pc<code.length; pc+=Op.instrSize(code, pc)) {
113 cananian 1.1 int line = getLine(pc);
114 cananian 1.1 // make merge node if appropriate.
115 cananian 1.1 InMerge m = null;
116 cananian 1.1 if (merge[pc] > 1)
117 cananian 1.9.2.9 v.add(m = new InMerge(sf, line, merge[pc] /*arity*/));
118 cananian 1.1 // make Instr object for this pc.
119 cananian 1.1 if (Op.isBranch(code[pc])) {
120 cananian 1.1 if (code[pc]==Op.TABLESWITCH || code[pc]==Op.LOOKUPSWITCH)
121 cananian 1.1 sparse[pc] = new InSwitch(sf, line, code, pc);
122 cananian 1.9.2.3 else if (code[pc]==Op.RET)
123 cananian 1.9.2.3 sparse[pc] = new InRet(sf, line, code, pc);
124 cananian 1.1 else
125 cananian 1.1 sparse[pc] = new InCti(sf, line, code, pc);
126 cananian 1.1 } else
127 cananian 1.1 sparse[pc] = new InGen(sf, line, code, pc, this);
128 cananian 1.9.2.9 v.add(sparse[pc]);
129 cananian 1.1 // Daisy-chain merge node if appropriate.
130 cananian 1.1 if (m != null) {
131 cananian 1.1 m.addNext(sparse[pc]);
132 cananian 1.1 sparse[pc].addPrev(m);
133 cananian 1.1 sparse[pc] = m;
134 cananian 1.1 }
135 cananian 1.1 }
136 cananian 1.1 // okay. The instructions are made (in pc order, no less...)
137 cananian 1.1 // link 'em.
138 cananian 1.1 for (int pc=0; pc<code.length; pc+=Op.instrSize(code, pc)) {
139 cananian 1.1 Instr curr = sparse[pc];
140 cananian 1.1 if (curr instanceof InMerge)
141 cananian 1.9.2.4 curr = ((InMerge)curr).next(0);
142 cananian 1.1 if ((!Op.isUnconditionalBranch(code[pc])) ||
143 cananian 1.1 Op.isJSR(code[pc])) { // jsrs return to next instruction eventually
144 cananian 1.9.2.8 // JVM spec is not clear whether 'code can run off end of array'
145 cananian 1.9.2.8 // or not.
146 cananian 1.9.2.8 if ((pc+Op.instrSize(code, pc)) < code.length) {
147 cananian 1.9.2.8 // link to next pc.
148 cananian 1.9.2.8 Instr next = sparse[pc+Op.instrSize(code, pc)];
149 cananian 1.9.2.8 curr.addNext(next);
150 cananian 1.9.2.8 next.addPrev(curr);
151 cananian 1.9.2.8 }
152 cananian 1.1 }
153 cananian 1.1 if (Op.isBranch(code[pc])) {
154 cananian 1.1 // link to branch targets.
155 cananian 1.1 int[] targets = Op.branchTargets(code, pc);
156 cananian 1.1 for (int i=0; i<targets.length; i++) {
157 cananian 1.1 Instr next = sparse[targets[i]];
158 cananian 1.1 curr.addNext(next);
159 cananian 1.1 next.addPrev(curr);
160 cananian 1.1 }
161 cananian 1.1 }
162 cananian 1.1 }
163 cananian 1.1 // Make tryBlocks table.
164 cananian 1.9.2.5 harpoon.IR.RawClass.ExceptionTable et[] =
165 cananian 1.1 getCode().exception_table;
166 cananian 1.1 tryBlocks = new ExceptionEntry[et.length];
167 cananian 1.1 for (int i=0; i<tryBlocks.length; i++) { // for each table entry...
168 cananian 1.1 // Add all the PC's in the try block to a list.
169 cananian 1.14 Set<Instr> uv = new HashSet<Instr>(et[i].end_pc-et[i].start_pc);
170 cananian 1.1 for (int pc=et[i].start_pc;
171 cananian 1.1 pc < et[i].end_pc;
172 cananian 1.9.2.4 pc+=Op.instrSize(code,pc)) {
173 cananian 1.9.2.9 uv.add(sparse[pc]);
174 cananian 1.9.2.4 if (sparse[pc] instanceof InMerge) // merges come in pairs.
175 cananian 1.9.2.9 uv.add(sparse[pc].next(0));
176 cananian 1.9.2.4 }
177 cananian 1.1 // Make an HClass for the exception caught...
178 cananian 1.1 HClass ex = null;
179 cananian 1.1 if (et[i].catch_type != 0)
180 cananian 1.9.2.12 ex = linker.forDescriptor("L"+et[i].catch_type().name()+";");
181 cananian 1.1 else
182 cananian 1.2 ex = null; // to indicate 'catch any'.
183 cananian 1.1 // and make the official exception entry.
184 cananian 1.9.2.10 tryBlocks[i] = new ExceptionEntry(i, uv, ex, sparse[et[i].handler_pc]);
185 cananian 1.1 }
186 cananian 1.9.2.9 // Okay. Just trim our list and we're ready to rumble.
187 cananian 1.9.2.9 ((ArrayList)v).trimToSize();
188 cananian 1.9.2.9 elements = Collections.unmodifiableList(v);
189 cananian 1.1 }
190 cananian 1.9.2.9 return elements;
191 cananian 1.1 }
192 cananian 1.1 /** Cached value of <code>getElements</code>. */
193 cananian 1.14 private List<Instr> elements = null;
194 cananian 1.1 /** Cached value of <code>getTryBlocks</code> blocks. */
195 cananian 1.1 private ExceptionEntry[] tryBlocks = null;
196 cananian 1.4
197 cananian 1.14 public List<Instr> getLeafElementsL() {
198 cananian 1.4 if (leaves == null) {
199 cananian 1.14 leaves = new ArrayList<Instr>();
200 cananian 1.14 for (Iterator<Instr> i = getElementsI(); i.hasNext(); ) {
201 cananian 1.14 Instr in = i.next();
202 cananian 1.9.2.9 if (in.next.size()==0)
203 cananian 1.9.2.9 leaves.add(in);
204 cananian 1.9.2.9 }
205 cananian 1.9.2.9 ((ArrayList)leaves).trimToSize();
206 cananian 1.9.2.9 leaves = Collections.unmodifiableList(leaves);
207 cananian 1.4 }
208 cananian 1.9.2.9 return leaves;
209 cananian 1.9.2.9 }
210 cananian 1.14 private List<Instr> leaves = null;
211 cananian 1.9.2.9
212 cananian 1.14 public Instr[] getLeafElements() {
213 cananian 1.14 List<Instr> l = getLeafElementsL();
214 cananian 1.14 return l.toArray(new Instr[l.size()]);
215 cananian 1.4 }
216 cananian 1.9.2.1
217 cananian 1.9.2.1 // implement elementArrayFactory which returns Instr[]s.
218 cananian 1.14 public ArrayFactory<Instr> elementArrayFactory() {
219 cananian 1.14 return Instr.arrayFactory;
220 cananian 1.14 }
221 cananian 1.14
222 cananian 1.14 // Graph interface
223 cananian 1.14 public Set<Instr> nodes() {
224 cananian 1.14 final List<Instr> l = getElementsL();
225 cananian 1.14 return new AbstractSet<Instr>() {
226 cananian 1.14 public Iterator<Instr> iterator() { return l.iterator(); }
227 cananian 1.14 public int size() { return l.size(); }
228 cananian 1.14 };
229 cananian 1.14 }
230 cananian 1.1
231 cananian 1.1 // special non-HCode-mandated access functions.
232 cananian 1.1 /** Get the number of local variables used in this method, including
233 cananian 1.1 * the parameters passed to the method on invocation. */
234 cananian 1.1 public int getMaxLocals() { return getCode().max_locals; }
235 cananian 1.1 /** Get the maximum number of words on the operand stack at any point
236 cananian 1.1 * during execution of this method. */
237 cananian 1.1 public int getMaxStack() { return getCode().max_stack; }
238 cananian 1.1 /** Get an array with the try-catch blocks/handlers for this bytecode. */
239 cananian 1.12 public ExceptionEntry[] getTryBlocks() { getElementsL(); return tryBlocks; }
240 cananian 1.1
241 cananian 1.1 /** Represents exception handlers in this code view. */
242 cananian 1.9.2.10 public static class ExceptionEntry implements Comparable {
243 cananian 1.9.2.10 int order; // smaller numbers have precedence over higher numbers.
244 cananian 1.14 Set<Instr> tryBlock;
245 cananian 1.1 HClass caughtException;
246 cananian 1.1 Instr handler;
247 cananian 1.9.2.10 ExceptionEntry(int order,
248 cananian 1.14 Set<Instr> tryBlock, HClass caughtException, Instr handler){
249 cananian 1.9.2.10 this.order = order;
250 cananian 1.1 this.tryBlock = tryBlock;
251 cananian 1.1 this.caughtException = caughtException;
252 cananian 1.1 this.handler = handler;
253 cananian 1.1 }
254 cananian 1.1 public boolean inTry(Instr i) { return tryBlock.contains(i); }
255 cananian 1.1 public HClass caughtException() { return caughtException; }
256 cananian 1.1 public Instr handler() { return handler; }
257 cananian 1.9.2.10
258 cananian 1.9.2.10 public int compareTo(Object o) {
259 cananian 1.9.2.10 int cmp = this.order - ((ExceptionEntry)o).order;
260 cananian 1.9.2.10 if (cmp==0 && !this.equals(o)) // check consistency.
261 cananian 1.9.2.10 throw new ClassCastException("Comparing uncomparable objects");
262 cananian 1.9.2.10 return cmp;
263 cananian 1.9.2.10 }
264 cananian 1.9.2.10 public String toString() {
265 cananian 1.9.2.10 return "Exception Entry #"+order+" for "+caughtException;
266 cananian 1.9.2.10 }
267 cananian 1.1 }
268 cananian 1.1
269 cananian 1.1 // Utility functions.
270 cananian 1.1 /** Return the Code attribute of this method. */
271 cananian 1.1 private AttributeCode getCode() {
272 cananian 1.1 if (attrcode==null) { // check cache.
273 cananian 1.1 for (int i=0; i<methodinfo.attributes.length; i++)
274 cananian 1.1 if (methodinfo.attributes[i] instanceof AttributeCode) {
275 cananian 1.1 attrcode = (AttributeCode) methodinfo.attributes[i];
276 cananian 1.1 break;
277 cananian 1.1 }
278 cananian 1.1 }
279 cananian 1.1 return attrcode; // null if no code attribute was found.
280 cananian 1.1 }
281 cananian 1.1 private AttributeCode attrcode = null;
282 cananian 1.1 /** Look up a constant in the appropriate constant_pool. */
283 cananian 1.1 public Constant getConstant(int index) { return getCode().constant(index); }
284 cananian 1.1
285 cananian 1.1
286 cananian 1.1 /** Get the line number corresponding to a given pc in the code
287 cananian 1.1 * array. Zero is returned if there is no line number information
288 cananian 1.1 * in the code attribute. */
289 cananian 1.1 private int getLine(int pc) {
290 cananian 1.1 int lineno = 0;
291 cananian 1.1 AttributeCode code = getCode();
292 cananian 1.1 for (int i=0; i<code.attributes.length; i++) {
293 cananian 1.1 if (code.attributes[i] instanceof AttributeLineNumberTable) {
294 cananian 1.1 LineNumberTable[] lnt =
295 cananian 1.1 ((AttributeLineNumberTable) code.attributes[i]).line_number_table;
296 cananian 1.1 for (int j=0; j<lnt.length; j++)
297 cananian 1.1 if (lnt[j].start_pc <= pc)
298 cananian 1.1 lineno = lnt[j].line_number;
299 cananian 1.1 else
300 cananian 1.1 break; // start_pc must be uniformly increasing within each table.
301 cananian 1.1 }
302 cananian 1.1 }
303 cananian 1.1 // hopefully this has done it.
304 cananian 1.1 return lineno;
305 cananian 1.9.2.7 }
306 cananian 1.9.2.7
307 cananian 1.9.2.7 /** Return an HCodeFactory for Bytecode form. */
308 cananian 1.9.2.7 public static HCodeFactory codeFactory() {
309 cananian 1.9.2.12 return harpoon.ClassFile.Loader.systemCodeFactory;
310 cananian 1.1 }
311 cananian 1.1 }
312 cananian 1.1
313 cananian 1.1 // set emacs indentation style.
314 cananian 1.1 // Local Variables:
315 cananian 1.1 // c-basic-offset:2
316 cananian 1.1 // End: