GraphTransformer


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 }
343
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags