001: /* GraphTransformer.java */
002: package org.quilt.cl;
003:
004: import java.util.List;
005: import org.apache.bcel.classfile.LineNumberTable;
006: import org.apache.bcel.classfile.Method;
007: import org.apache.bcel.generic.*;
008:
009: import org.quilt.graph.*;
010:
011: /**
012: * <p>Build the control flow graph for a method, apply an arbitrary
013: * number of GraphXformers to it, and then collapse the graph
014: * back to an instruction list. Exception handlers are collected
015: * from the control flow graph and made available to callers.</p>
016: *
017: * <p>XXX Debug statements should be removed when code is definitely
018: * stable. XXX</p>
019: *
020: * @author <a href="mailto:jddixon@users.sourceforge.net">Jim Dixon</a>
021: */
022: public class GraphTransformer {
023:
024: /** GraphXformer vector; ordered list of graph processors. */
025: private List gxf;
026:
027: private TryStacks ts = null;
028:
029: /** Exception handlers found in the method. */
030: private CodeExceptionGen[] handlers;
031:
032: /** Exception handlers from the transformed graph. */
033: private CodeExceptionGen[] ceg = null;
034:
035: /** Instruction list generated from the graph. */
036: private InstructionList ilist = null;
037:
038: /**
039: * Creates method control flow graphs, applies application-
040: * specific transforms, and then collapses the graph to produce
041: * a new instruction list.
042: *
043: * @param gxf List of application-specific graph transformers.
044: *
045: * @author <a href="jddixon@users.sourceforge.net">Jim Dixon</a>
046: */
047: public GraphTransformer(List gxf) {
048: this .gxf = gxf;
049: }
050:
051: private void zapGraphXformer(GraphXformer gxf, Exception e) {
052: System.err.println("WARNING: exception in "
053: // + gxf.getName()
054: + ": transformation will not be applied");
055: e.printStackTrace();
056: gxf = null;
057: }
058:
059: /**
060: * Build a control flow graph for a method's instruction list,
061: * apply any transformers to it, and collapse the graph into
062: * a new instruction list.
063: *
064: * @param clazz Class being transformed.
065: * @param method The method being transformed.
066: * @return The transformed instruction list.
067: */
068: public InstructionList xform(ClassGen clazz, MethodGen method) {
069: if (method == null) {
070: throw new IllegalArgumentException("null method");
071: }
072: ControlFlowGraph graph = makeGraph(clazz, method);
073: GraphXformer[] xf = new GraphXformer[gxf.size()];
074:
075: // apply each graph processor in turn
076: for (int i = 0; i < gxf.size(); i++) {
077: try {
078: xf[i] = (GraphXformer) ((gxf.get(i)).getClass()
079: .newInstance());
080: } catch (IllegalAccessException e) {
081: zapGraphXformer(xf[i], e);
082: } catch (InstantiationException e) {
083: zapGraphXformer(xf[i], e);
084: }
085: if (xf[i] != null && graph != null) {
086: xf[i].xform(clazz, method, graph);
087: }
088: }
089:
090: if (graph == null) {
091: return null;
092: }
093: BytecodeCollector bc = collapseGraph(graph);
094: ilist = bc.getInstructionList();
095: if (ilist == null) {
096: return null;
097: }
098: if (ts == null) {
099: ceg = null;
100: } else {
101: // this is guaranteed not to be null, but it may be empty
102: ceg = bc.getCEGs(ts.getCatchData());
103: if (ceg.length != handlers.length) {
104: System.out
105: .println("GraphTransformer.xform WARNING - PROBABLE INTERNAL ERROR:\n method had "
106: + handlers.length
107: + " exception handlers, but after graph transformation "
108: + ceg.length);
109: }
110: }
111: return ilist;
112: }
113:
114: /**
115: * Returns array of exception handlers, empty if the instruction
116: * list was null or there were no exception handlers.
117: *
118: * @return Array of CodeExceptionGen.
119: */
120: public CodeExceptionGen[] getExceptionHandlers() {
121: if (ilist != null && ceg != null) {
122: return ceg;
123: } else {
124: return new CodeExceptionGen[0];
125: }
126: }
127:
128: /**
129: * Build the graph for the method.
130: *
131: * @param clazz Class being transformed in bcel ClassGen.
132: * @param m BCEL representation of method we are working on.
133: */
134: final protected ControlFlowGraph makeGraph(ClassGen clazz,
135: MethodGen method) {
136:
137: SortedBlocks blox = new SortedBlocks();
138: handlers = method.getExceptionHandlers();
139: ControlFlowGraph cfg = new ControlFlowGraph();
140: ControlFlowGraph currGraph = cfg;
141: Edge e = cfg.getEntry().getEdge();
142: ts = null;
143: boolean startBlock = false;
144: CodeVertex currV = null;
145: LineNumberTable lineTab = method.getLineNumberTable(clazz
146: .getConstantPool());
147: if (handlers.length > 0) {
148: // NEED TO ADJUST EDGE HERE
149: ts = new TryStacks(handlers, blox, cfg);
150: }
151: if (blox.exists(0)) {
152: // we must have a try block starting at 0
153: currV = blox.get(0);
154: } else {
155: currV = blox.find(0, currGraph, e);
156: }
157: if (lineTab != null) {
158: currV.setStartLine(lineTab.getSourceLine(0));
159: }
160: e = currV.getEdge();
161: currGraph = (ControlFlowGraph) currV.getGraph();
162:
163: // Walk through the method's bytecode, appending it to the
164: // current vertex, creating new vertices where necessary.
165:
166: InstructionList iList = method.getInstructionList();
167: InstructionHandle currHandle = iList.getStart();
168: Instruction inst = currHandle.getInstruction();
169: int pos = currHandle.getPosition();
170: // current vertex's InstructionList
171: InstructionList vIList = currV.getInstructionList();
172:
173: while (currHandle != null) {
174: if (startBlock) {
175: startBlock = false;
176: if (e == null) {
177: if (!blox.exists(pos)) {
178: // XXX this was formerly regarded as an
179: // error; handling it like this makes it
180: // clearer what the problem is, but we now get
181: // Falling off the end of the code
182: currV = new CodeVertex(currGraph, pos);
183: } else {
184: currV = blox.get(pos);
185: }
186: } else {
187: currV = blox.find(pos, currGraph, e);
188: }
189: if (lineTab != null) {
190: currV.setStartLine(lineTab.getSourceLine(pos));
191: }
192: e = currV.getEdge();
193: currGraph = (ControlFlowGraph) currV.getGraph();
194: // DEBUG
195: //System.out.println("makeGraph while; e = " + e);
196: // END
197: vIList = currV.getInstructionList();
198: }
199: if (inst instanceof GotoInstruction) {
200: // to make the layout code (BytecodeCollector) work,
201: // introduce the notion of a 'virtual' edge; there is
202: // no flow of control, but the code along the virtual
203: // edge will be laid out first
204: Edge otherEdge = currV.makeBinary();
205: currV.setConnInst(inst);
206: int tpos = ((GotoInstruction) inst).getTarget()
207: .getPosition();
208: int endTry;
209: if (ts == null) {
210: endTry = -1;
211: } else {
212: endTry = ts.getEndTry(currGraph);
213: }
214: if (endTry >= 0 && tpos > endTry) {
215: // tpos is beyond end of try block and should be the
216: // first code vertex following the subgraph Exit; in
217: // any case the edge target becomes the Exit
218: Exit currExit = currGraph.getExit();
219: otherEdge.setTarget(currExit);
220: if (!blox.exists(tpos)) {
221: Vertex vFinal;
222: for (vFinal = currExit; vFinal.getTarget() instanceof Entry; vFinal = vFinal
223: .getTarget()) {
224: ;
225: }
226: blox.add(tpos, vFinal.getEdge());
227: }
228: } else {
229: // tpos is within try block; make v target of e
230: blox.find(tpos, currGraph, otherEdge);
231: }
232: // continue to use this 'virtual' edge
233: startBlock = true;
234: // // DEBUG
235: // System.out.println("GraphTransformer: goto at end of "
236: // + currV);
237: // // END
238:
239: } else if (inst instanceof IfInstruction
240: || inst instanceof JSR) {
241: Edge otherEdge = currV.makeBinary();
242: currV.setConnInst(inst);
243: // handle 'then' branch or target of JSR
244: int tpos = ((BranchInstruction) inst).getTarget()
245: .getPosition();
246: // edge for 'then' vertex
247: blox.find(tpos, currGraph, otherEdge);
248: // continue to use the current edge
249: startBlock = true; // ... but start a new block
250:
251: } else if (inst instanceof ReturnInstruction
252: || inst instanceof RET) {
253: currV.setConnInst(inst);
254: e = null;
255: startBlock = true;
256:
257: } else if (inst instanceof InvokeInstruction) {
258: currV.setConnInst(inst);
259: // continue to use the current edge
260: startBlock = true; // ... but start a new block
261:
262: } else if (inst instanceof Select) {
263: InstructionHandle[] targets = ((Select) inst)
264: .getTargets();
265: //MultiConnector conn = currV.makeMulti(targets.length);
266: ComplexConnector conn = currV
267: .makeComplex(targets.length);
268: currV.setConnInst(inst);
269: for (int i = 0; i < targets.length; i++) {
270: int tpos = targets[i].getPosition();
271: blox.find(tpos, currGraph, conn.getEdge(i));
272: }
273: // EXPERIMENT IN HANDLING THE DEFAULT - seems to work ...
274: InstructionHandle theDefault = ((Select) inst)
275: .getTarget();
276: if (theDefault != null) {
277: blox.find(theDefault.getPosition(), currGraph, conn
278: .getEdge());
279: }
280: e = null; // it's an n-way goto
281: startBlock = true;
282:
283: } else if (inst instanceof ExceptionThrower) {
284: // Instructions which might or do (ATHROW) cause
285: // an exception. XXX This needs to be looked at
286: // more carefully! There are 22 such instructions
287: // or groups; these include NEW, LDIV, and
288: // ReturnInstruction. Splitting blocks here causes
289: // a very large increase in the number of vertices;
290: // the benefit is unclear.
291:
292: currV.setConnInst(inst);
293: // continue along same edge
294: startBlock = true;
295: } else {
296: vIList.append(inst); // add the instruction
297: }
298: InstructionHandle nextHandle = currHandle.getNext();
299: if (nextHandle != null) {
300: if (hasInbound(nextHandle)) {
301: // This instruction is the target of a jump; start
302: // a new block. Connector is set to flow by default.
303: startBlock = true;
304: }
305: }
306: if (startBlock == true) {
307: if (lineTab != null) {
308: currV.setEndLine(lineTab.getSourceLine(0));
309: }
310: }
311: currHandle = nextHandle;
312: if (currHandle != null) {
313: pos = currHandle.getPosition();
314: inst = currHandle.getInstruction();
315: }
316: }
317: return cfg;
318: }
319:
320: /**
321: * Whether this instruction is target of branch instruction or
322: * starts catch block.
323: *
324: * @param ih Handle on instruction.
325: * @return True if targeted by branch or CodeExceptionGen.
326: */
327: final public static boolean hasInbound(InstructionHandle ih) {
328: if (ih.hasTargeters()) {
329: InstructionTargeter targeters[] = ih.getTargeters();
330: for (int j = 0; j < targeters.length; j++) {
331: if (targeters[j] instanceof BranchInstruction) {
332: return true;
333: }
334: if (targeters[j] instanceof CodeExceptionGen) {
335: return true;
336: }
337: }
338: }
339: return false;
340: }
341:
342: /**
343: * Collapse a method control flow graph, writing bytecode back
344: * into the MethodGen data structures.
345: */
346: final protected BytecodeCollector collapseGraph(
347: ControlFlowGraph graph) {
348: BytecodeCollector theMan = new BytecodeCollector();
349: new Walker().visit(graph, theMan);
350: return theMan;
351: }
352: }
|