1 /* GraphTransformer.java */
2 package org.quilt.cl;
3
4 import java.util.List;
5 import org.apache.bcel.classfile.LineNumberTable;
6 import org.apache.bcel.classfile.Method;
7 import org.apache.bcel.generic.*;
8
9 import org.quilt.graph.*;
10
11 /***
12 * <p>Build the control flow graph for a method, apply an arbitrary
13 * number of GraphXformers to it, and then collapse the graph
14 * back to an instruction list. Exception handlers are collected
15 * from the control flow graph and made available to callers.</p>
16 *
17 * <p>XXX Debug statements should be removed when code is definitely
18 * stable. XXX</p>
19 *
20 * @author <a href="mailto:jddixon@users.sourceforge.net">Jim Dixon</a>
21 */
22 public class GraphTransformer {
23
24 /*** GraphXformer vector; ordered list of graph processors. */
25 private List gxf;
26
27 private TryStacks ts = null;
28
29 /*** Exception handlers found in the method. */
30 private CodeExceptionGen[] handlers;
31
32 /*** Exception handlers from the transformed graph. */
33 private CodeExceptionGen [] ceg = null;
34
35 /*** Instruction list generated from the graph. */
36 private InstructionList ilist = null;
37
38 /***
39 * Creates method control flow graphs, applies application-
40 * specific transforms, and then collapses the graph to produce
41 * a new instruction list.
42 *
43 * @param gxf List of application-specific graph transformers.
44 *
45 * @author <a href="jddixon@users.sourceforge.net">Jim Dixon</a>
46 */
47 public GraphTransformer ( List gxf ) {
48 this.gxf = gxf;
49 }
50
51 private void zapGraphXformer ( GraphXformer gxf, Exception e) {
52 System.err.println("WARNING: exception in "
53 // + gxf.getName()
54 + ": transformation will not be applied" );
55 e.printStackTrace();
56 gxf = null;
57 }
58 /***
59 * Build a control flow graph for a method's instruction list,
60 * apply any transformers to it, and collapse the graph into
61 * a new instruction list.
62 *
63 * @param clazz Class being transformed.
64 * @param method The method being transformed.
65 * @return The transformed instruction list.
66 */
67 public InstructionList xform (ClassGen clazz, MethodGen method ) {
68 if (method == null) {
69 throw new IllegalArgumentException("null method");
70 }
71 ControlFlowGraph graph = makeGraph(clazz, method);
72 GraphXformer [] xf = new GraphXformer[ gxf.size() ];
73
74 // apply each graph processor in turn
75 for (int i = 0; i < gxf.size(); i++) {
76 try {
77 xf[i] = (GraphXformer) (
78 (gxf.get(i)).getClass().newInstance() );
79 } catch (IllegalAccessException e ) {
80 zapGraphXformer (xf[i], e);
81 } catch (InstantiationException e ) {
82 zapGraphXformer (xf[i], e);
83 }
84 if (xf[i] != null && graph != null) {
85 xf[i].xform(clazz, method, graph);
86 }
87 }
88
89 if (graph == null) {
90 return null;
91 }
92 BytecodeCollector bc = collapseGraph(graph);
93 ilist = bc.getInstructionList();
94 if (ilist == null) {
95 return null;
96 }
97 if (ts == null) {
98 ceg = null;
99 } else {
100 // this is guaranteed not to be null, but it may be empty
101 ceg = bc.getCEGs(ts.getCatchData());
102 if (ceg.length != handlers.length) {
103 System.out.println(
104 "GraphTransformer.xform WARNING - PROBABLE INTERNAL ERROR:\n method had "
105 + handlers.length
106 + " exception handlers, but after graph transformation "
107 + ceg.length);
108 }
109 }
110 return ilist;
111 }
112 /***
113 * Returns array of exception handlers, empty if the instruction
114 * list was null or there were no exception handlers.
115 *
116 * @return Array of CodeExceptionGen.
117 */
118 public CodeExceptionGen[] getExceptionHandlers() {
119 if (ilist != null && ceg != null) {
120 return ceg;
121 } else {
122 return new CodeExceptionGen[0];
123 }
124 }
125 /***
126 * Build the graph for the method.
127 *
128 * @param clazz Class being transformed in bcel ClassGen.
129 * @param m BCEL representation of method we are working on.
130 */
131 final protected ControlFlowGraph makeGraph ( ClassGen clazz,
132 MethodGen method ) {
133
134 SortedBlocks blox = new SortedBlocks();
135 handlers = method.getExceptionHandlers();
136 ControlFlowGraph cfg = new ControlFlowGraph();
137 ControlFlowGraph currGraph = cfg;
138 Edge e = cfg.getEntry().getEdge();
139 ts = null;
140 boolean startBlock = false;
141 CodeVertex currV = null;
142 LineNumberTable lineTab = method.getLineNumberTable (
143 clazz.getConstantPool() );
144 if (handlers.length > 0) {
145 // NEED TO ADJUST EDGE HERE
146 ts = new TryStacks (handlers, blox, cfg);
147 }
148 if (blox.exists(0)) {
149 // we must have a try block starting at 0
150 currV = blox.get(0);
151 } else {
152 currV = blox.find (0, currGraph, e);
153 }
154 if (lineTab != null) {
155 currV.setStartLine( lineTab.getSourceLine(0) );
156 }
157 e = currV.getEdge();
158 currGraph = (ControlFlowGraph) currV.getGraph();
159
160 // Walk through the method's bytecode, appending it to the
161 // current vertex, creating new vertices where necessary.
162
163 InstructionList iList = method.getInstructionList();
164 InstructionHandle currHandle = iList.getStart();
165 Instruction inst = currHandle.getInstruction();
166 int pos = currHandle.getPosition();
167 // current vertex's InstructionList
168 InstructionList vIList = currV.getInstructionList();
169
170 while (currHandle != null) {
171 if (startBlock) {
172 startBlock = false;
173 if (e == null) {
174 if ( !blox.exists(pos) ) {
175 // XXX this was formerly regarded as an
176 // error; handling it like this makes it
177 // clearer what the problem is, but we now get
178 // Falling off the end of the code
179 currV = new CodeVertex (currGraph, pos);
180 } else {
181 currV = blox.get(pos);
182 }
183 } else {
184 currV = blox.find(pos, currGraph, e);
185 }
186 if (lineTab != null) {
187 currV.setStartLine( lineTab.getSourceLine(pos) );
188 }
189 e = currV.getEdge();
190 currGraph = (ControlFlowGraph) currV.getGraph();
191 // DEBUG
192 //System.out.println("makeGraph while; e = " + e);
193 // END
194 vIList = currV.getInstructionList();
195 }
196 if (inst instanceof GotoInstruction) {
197 // to make the layout code (BytecodeCollector) work,
198 // introduce the notion of a 'virtual' edge; there is
199 // no flow of control, but the code along the virtual
200 // edge will be laid out first
201 Edge otherEdge = currV.makeBinary();
202 currV.setConnInst(inst);
203 int tpos = ((GotoInstruction)inst).getTarget().getPosition();
204 int endTry;
205 if (ts == null) {
206 endTry = -1;
207 } else {
208 endTry= ts.getEndTry(currGraph);
209 }
210 if (endTry >= 0 && tpos > endTry) {
211 // tpos is beyond end of try block and should be the
212 // first code vertex following the subgraph Exit; in
213 // any case the edge target becomes the Exit
214 Exit currExit = currGraph.getExit();
215 otherEdge.setTarget(currExit);
216 if (!blox.exists(tpos)) {
217 Vertex vFinal;
218 for (vFinal = currExit;
219 vFinal.getTarget() instanceof Entry;
220 vFinal = vFinal.getTarget()) {
221 ;
222 }
223 blox.add (tpos, vFinal.getEdge());
224 }
225 } else {
226 // tpos is within try block; make v target of e
227 blox.find (tpos, currGraph, otherEdge);
228 }
229 // continue to use this 'virtual' edge
230 startBlock = true;
231 // // DEBUG
232 // System.out.println("GraphTransformer: goto at end of "
233 // + currV);
234 // // END
235
236 } else if (inst instanceof IfInstruction
237 || inst instanceof JSR ) {
238 Edge otherEdge = currV.makeBinary();
239 currV.setConnInst(inst);
240 // handle 'then' branch or target of JSR
241 int tpos = ((BranchInstruction)inst).getTarget().getPosition();
242 // edge for 'then' vertex
243 blox.find(tpos, currGraph, otherEdge);
244 // continue to use the current edge
245 startBlock = true; // ... but start a new block
246
247 } else if (inst instanceof ReturnInstruction
248 || inst instanceof RET) {
249 currV.setConnInst(inst);
250 e = null;
251 startBlock = true;
252
253 } else if (inst instanceof InvokeInstruction) {
254 currV.setConnInst(inst);
255 // continue to use the current edge
256 startBlock = true; // ... but start a new block
257
258 } else if (inst instanceof Select) {
259 InstructionHandle[] targets = ((Select)inst).getTargets();
260 //MultiConnector conn = currV.makeMulti(targets.length);
261 ComplexConnector conn = currV.makeComplex(targets.length);
262 currV.setConnInst(inst);
263 for (int i = 0; i < targets.length; i++) {
264 int tpos = targets[i].getPosition();
265 blox.find(tpos, currGraph, conn.getEdge(i));
266 }
267 // EXPERIMENT IN HANDLING THE DEFAULT - seems to work ...
268 InstructionHandle theDefault = ((Select)inst).getTarget();
269 if (theDefault != null) {
270 blox.find ( theDefault.getPosition(),
271 currGraph, conn.getEdge());
272 }
273 e = null; // it's an n-way goto
274 startBlock = true;
275
276 } else if (inst instanceof ExceptionThrower) {
277 // Instructions which might or do (ATHROW) cause
278 // an exception. XXX This needs to be looked at
279 // more carefully! There are 22 such instructions
280 // or groups; these include NEW, LDIV, and
281 // ReturnInstruction. Splitting blocks here causes
282 // a very large increase in the number of vertices;
283 // the benefit is unclear.
284
285 currV.setConnInst(inst);
286 // continue along same edge
287 startBlock = true;
288 } else {
289 vIList.append(inst); // add the instruction
290 }
291 InstructionHandle nextHandle = currHandle.getNext();
292 if (nextHandle != null) {
293 if (hasInbound(nextHandle)) {
294 // This instruction is the target of a jump; start
295 // a new block. Connector is set to flow by default.
296 startBlock = true;
297 }
298 }
299 if (startBlock == true) {
300 if (lineTab != null) {
301 currV.setEndLine( lineTab.getSourceLine(0) );
302 }
303 }
304 currHandle = nextHandle;
305 if (currHandle != null) {
306 pos = currHandle.getPosition();
307 inst = currHandle.getInstruction();
308 }
309 }
310 return cfg;
311 }
312 /***
313 * Whether this instruction is target of branch instruction or
314 * starts catch block.
315 *
316 * @param ih Handle on instruction.
317 * @return True if targeted by branch or CodeExceptionGen.
318 */
319 final public static boolean hasInbound (InstructionHandle ih ) {
320 if (ih.hasTargeters()) {
321 InstructionTargeter targeters[] = ih.getTargeters();
322 for (int j = 0; j < targeters.length; j++) {
323 if (targeters[j] instanceof BranchInstruction) {
324 return true;
325 }
326 if (targeters[j] instanceof CodeExceptionGen) {
327 return true;
328 }
329 }
330 }
331 return false;
332 }
333 /***
334 * Collapse a method control flow graph, writing bytecode back
335 * into the MethodGen data structures.
336 */
337 final protected BytecodeCollector collapseGraph(ControlFlowGraph graph) {
338 BytecodeCollector theMan = new BytecodeCollector();
339 new Walker().visit(graph, theMan);
340 return theMan;
341 }
342 }
This page was automatically generated by Maven