ControlFlowGraph


1   /*
2    * Copyright  2000-2004 The Apache Software Foundation
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.apache.bcel.verifier.structurals;
18  
19  
20  import java.util.ArrayList  ;
21  import java.util.Hashtable  ;
22  import java.util.Map  ;
23  import org.apache.bcel.generic.ATHROW;
24  import org.apache.bcel.generic.BranchInstruction;
25  import org.apache.bcel.generic.GotoInstruction;
26  import org.apache.bcel.generic.Instruction;
27  import org.apache.bcel.generic.InstructionHandle;
28  import org.apache.bcel.generic.JsrInstruction;
29  import org.apache.bcel.generic.MethodGen;
30  import org.apache.bcel.generic.RET;
31  import org.apache.bcel.generic.ReturnInstruction;
32  import org.apache.bcel.generic.Select;
33  import org.apache.bcel.verifier.exc.AssertionViolatedException;
34  import org.apache.bcel.verifier.exc.StructuralCodeConstraintException;
35  
36  /**
37   * This class represents a control flow graph of a method.
38   *
39   * @version $Id: ControlFlowGraph.java 386056 2006-03-15 11:31:56Z tcurdt $
40   * @author Enver Haase
41   */
42  public class ControlFlowGraph{
43  
44      /**
45       * Objects of this class represent a node in a ControlFlowGraph.
46       * These nodes are instructions, not basic blocks.
47       */
48      private class InstructionContextImpl implements InstructionContext{
49  
50          /**
51           * The TAG field is here for external temporary flagging, such
52           * as graph colouring.
53           *
54           * @see #getTag()
55           * @see #setTag(int)
56           */
57          private int TAG;
58  
59          /**
60           * The InstructionHandle this InstructionContext is wrapped around.
61           */
62          private InstructionHandle instruction;
63  
64          /**
65           * The 'incoming' execution Frames.
66           */
67          private Map   inFrames;   // key: the last-executed JSR
68  
69          /**
70           * The 'outgoing' execution Frames.
71           */
72          private Map   outFrames; // key: the last-executed JSR 
73  
74          /**
75           * The 'execution predecessors' - a list of type InstructionContext 
76           * of those instances that have been execute()d before in that order.
77           */
78          private ArrayList   executionPredecessors = null; // Type: InstructionContext
79      
80          /**
81           * Creates an InstructionHandleImpl object from an InstructionHandle.
82           * Creation of one per InstructionHandle suffices. Don't create more.
83           */
84          public InstructionContextImpl(InstructionHandle inst){
85              if (inst == null) {
86                  throw new AssertionViolatedException("Cannot instantiate InstructionContextImpl from NULL.");
87              }
88          
89              instruction = inst;
90              inFrames = new java.util.HashMap  ();
91              outFrames = new java.util.HashMap  ();
92          }
93  
94          /* Satisfies InstructionContext.getTag(). */
95          public int getTag(){
96              return TAG;
97          }
98  
99          /* Satisfies InstructionContext.setTag(int). */
100         public void setTag(int tag){
101             TAG = tag;
102         }
103 
104         /**
105          * Returns the exception handlers of this instruction.
106          */
107         public ExceptionHandler[] getExceptionHandlers(){
108             return exceptionhandlers.getExceptionHandlers(getInstruction());
109         }
110 
111         /**
112          * Returns a clone of the "outgoing" frame situation with respect to the given ExecutionChain.
113          */ 
114         public Frame getOutFrame(ArrayList   execChain){
115             executionPredecessors = execChain;
116 
117             Frame org;
118 
119             InstructionContext jsr = lastExecutionJSR();
120 
121             org = (Frame) outFrames.get(jsr);
122 
123             if (org == null){
124                 throw new AssertionViolatedException("outFrame not set! This:\n"+this+"\nExecutionChain: "+getExecutionChain()+"\nOutFrames: '"+outFrames+"'.");
125             }
126             return org.getClone();
127         }
128 
129     public Frame getInFrame() {
130           Frame org;
131             
132             InstructionContext jsr = lastExecutionJSR();
133             
134             org = (Frame) inFrames.get(jsr);
135 
136             if (org == null){
137                 throw new AssertionViolatedException("inFrame not set! This:\n"+this+"\nInFrames: '"+inFrames+"'.");
138       }
139       return org.getClone();
140     }
141 
142         /**
143          * "Merges in" (vmspec2, page 146) the "incoming" frame situation;
144          * executes the instructions symbolically
145          * and therefore calculates the "outgoing" frame situation.
146          * Returns: True iff the "incoming" frame situation changed after
147          * merging with "inFrame".
148          * The execPreds ArrayList must contain the InstructionContext
149          * objects executed so far in the correct order. This is just
150          * one execution path [out of many]. This is needed to correctly
151          * "merge" in the special case of a RET's successor.
152          * <B>The InstConstraintVisitor and ExecutionVisitor instances
153          * must be set up correctly.</B>
154          * @return true - if and only if the "outgoing" frame situation
155          * changed from the one before execute()ing.
156          */
157         public boolean execute(Frame inFrame, ArrayList   execPreds, InstConstraintVisitor icv, ExecutionVisitor ev){
158 
159             executionPredecessors = (ArrayList  ) execPreds.clone();
160 
161             //sanity check
162             if ( (lastExecutionJSR() == null) && (subroutines.subroutineOf(getInstruction()) != subroutines.getTopLevel() ) ){
163                 throw new AssertionViolatedException("Huh?! Am I '"+this+"' part of a subroutine or not?");
164             }
165             if ( (lastExecutionJSR() != null) && (subroutines.subroutineOf(getInstruction()) == subroutines.getTopLevel() ) ){
166                 throw new AssertionViolatedException("Huh?! Am I '"+this+"' part of a subroutine or not?");
167             }
168 
169             Frame inF = (Frame) inFrames.get(lastExecutionJSR());
170             if (inF == null){// no incoming frame was set, so set it.
171                 inFrames.put(lastExecutionJSR(), inFrame);
172                 inF = inFrame;
173             }
174             else{// if there was an "old" inFrame
175                 if (inF.equals(inFrame)){ //shortcut: no need to merge equal frames.
176                     return false;
177                 }
178                 if (! mergeInFrames(inFrame)){
179                     return false;
180                 }
181             }
182             
183             // Now we're sure the inFrame has changed!
184             
185             // new inFrame is already merged in, see above.     
186             Frame workingFrame = inF.getClone();
187 
188             try{
189                 // This verifies the InstructionConstraint for the current
190                 // instruction, but does not modify the workingFrame object.
191 //InstConstraintVisitor icv = InstConstraintVisitor.getInstance(VerifierFactory.getVerifier(method_gen.getClassName()));
192                 icv.setFrame(workingFrame);
193                 getInstruction().accept(icv);
194             }
195             catch(StructuralCodeConstraintException ce){
196                 ce.extendMessage("","\nInstructionHandle: "+getInstruction()+"\n");
197                 ce.extendMessage("","\nExecution Frame:\n"+workingFrame);
198                 extendMessageWithFlow(ce);
199                 throw ce;
200             }
201 
202             // This executes the Instruction.
203             // Therefore the workingFrame object is modified.
204 //ExecutionVisitor ev = ExecutionVisitor.getInstance(VerifierFactory.getVerifier(method_gen.getClassName()));
205             ev.setFrame(workingFrame);
206             getInstruction().accept(ev);
207             //getInstruction().accept(ExecutionVisitor.withFrame(workingFrame));
208             outFrames.put(lastExecutionJSR(), workingFrame);
209 
210             return true;    // new inFrame was different from old inFrame so merging them
211                                         // yielded a different this.inFrame.
212         }
213 
214         /**
215          * Returns a simple String representation of this InstructionContext.
216          */
217         public String   toString(){
218         //TODO: Put information in the brackets, e.g.
219         //      Is this an ExceptionHandler? Is this a RET? Is this the start of
220         //      a subroutine?
221             String   ret = getInstruction().toString(false)+"\t[InstructionContext]";
222             return ret;
223         }
224 
225         /**
226          * Does the actual merging (vmspec2, page 146).
227          * Returns true IFF this.inFrame was changed in course of merging with inFrame.
228          */
229         private boolean mergeInFrames(Frame inFrame){
230             // TODO: Can be performance-improved.
231             Frame inF = (Frame) inFrames.get(lastExecutionJSR());
232             OperandStack oldstack = inF.getStack().getClone();
233             LocalVariables oldlocals = inF.getLocals().getClone();
234             try{
235                 inF.getStack().merge(inFrame.getStack());
236                 inF.getLocals().merge(inFrame.getLocals());
237             }
238             catch (StructuralCodeConstraintException sce){
239                 extendMessageWithFlow(sce);
240                 throw sce;
241             }
242             if (    oldstack.equals(inF.getStack()) &&
243                         oldlocals.equals(inF.getLocals()) ){
244                 return false;
245             }
246             else{
247                 return true;
248             }
249         }
250 
251         /**
252          * Returns the control flow execution chain. This is built
253          * while execute(Frame, ArrayList)-ing the code represented
254          * by the surrounding ControlFlowGraph.
255          */
256         private String   getExecutionChain(){
257             String   s = this.toString();
258             for (int i=executionPredecessors.size()-1; i>=0; i--){
259                 s = executionPredecessors.get(i)+"\n" + s;
260             }
261             return s;
262         }
263 
264 
265         /**
266          * Extends the StructuralCodeConstraintException ("e") object with an at-the-end-extended message.
267          * This extended message will then reflect the execution flow needed to get to the constraint
268          * violation that triggered the throwing of the "e" object.
269          */
270         private void extendMessageWithFlow(StructuralCodeConstraintException e){
271             String   s = "Execution flow:\n";
272             e.extendMessage("", s+getExecutionChain());
273         }
274 
275         /*
276          * Fulfils the contract of InstructionContext.getInstruction().
277          */
278         public InstructionHandle getInstruction(){
279             return instruction;
280         }
281 
282         /**
283          * Returns the InstructionContextImpl with an JSR/JSR_W
284          * that was last in the ExecutionChain, without
285          * a corresponding RET, i.e.
286          * we were called by this one.
287          * Returns null if we were called from the top level.
288          */
289         private InstructionContextImpl lastExecutionJSR(){
290             
291             int size = executionPredecessors.size();
292             int retcount = 0;
293             
294             for (int i=size-1; i>=0; i--){
295                 InstructionContextImpl current = (InstructionContextImpl) (executionPredecessors.get(i));
296                 Instruction currentlast = current.getInstruction().getInstruction();
297                 if (currentlast instanceof RET) {
298                     retcount++;
299                 }
300                 if (currentlast instanceof JsrInstruction){
301                     retcount--;
302                     if (retcount == -1) {
303                         return current;
304                     }
305                 }
306             }
307             return null;
308         }
309 
310         /* Satisfies InstructionContext.getSuccessors(). */
311         public InstructionContext[] getSuccessors(){
312             return contextsOf(_getSuccessors());
313         }
314 
315         /**
316          * A utility method that calculates the successors of a given InstructionHandle
317          * That means, a RET does have successors as defined here.
318          * A JsrInstruction has its target as its successor
319          * (opposed to its physical successor) as defined here.
320          */
321 // TODO: implement caching!
322         private InstructionHandle[] _getSuccessors(){
323             final InstructionHandle[] empty = new InstructionHandle[0];
324             final InstructionHandle[] single = new InstructionHandle[1];
325             final InstructionHandle[] pair = new InstructionHandle[2];
326         
327             Instruction inst = getInstruction().getInstruction();
328         
329             if (inst instanceof RET){
330                 Subroutine s = subroutines.subroutineOf(getInstruction());
331                 if (s==null){ //return empty; // RET in dead code. "empty" would be the correct answer, but we know something about the surrounding project...
332                     throw new AssertionViolatedException("Asking for successors of a RET in dead code?!");
333                 }
334 
335 //TODO: remove. Only JustIce must not use it, but foreign users of the ControlFlowGraph
336 //      will want it. Thanks Johannes Wust.
337 //throw new AssertionViolatedException("DID YOU REALLY WANT TO ASK FOR RET'S SUCCS?");
338 
339                 InstructionHandle[] jsrs = s.getEnteringJsrInstructions();
340                 InstructionHandle[] ret = new InstructionHandle[jsrs.length];
341                 for (int i=0; i<jsrs.length; i++){
342                     ret[i] = jsrs[i].getNext();
343                 }
344                 return ret;
345             }
346         
347             // Terminates method normally.
348             if (inst instanceof ReturnInstruction){
349                 return empty;
350             }
351         
352             // Terminates method abnormally, because JustIce mandates
353             // subroutines not to be protected by exception handlers.
354             if (inst instanceof ATHROW){
355                 return empty;
356             }
357         
358             // See method comment.
359             if (inst instanceof JsrInstruction){
360                 single[0] = ((JsrInstruction) inst).getTarget();
361                 return single;
362             }
363 
364             if (inst instanceof GotoInstruction){
365                 single[0] = ((GotoInstruction) inst).getTarget();
366                 return single;
367             }
368 
369             if (inst instanceof BranchInstruction){
370                 if (inst instanceof Select){
371                     // BCEL's getTargets() returns only the non-default targets,
372                     // thanks to Eli Tilevich for reporting.
373                     InstructionHandle[] matchTargets = ((Select) inst).getTargets();
374                     InstructionHandle[] ret = new InstructionHandle[matchTargets.length+1];
375                     ret[0] = ((Select) inst).getTarget();
376                     System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length);
377                     return ret;
378                 }
379                 else{
380                     pair[0] = getInstruction().getNext();
381                     pair[1] = ((BranchInstruction) inst).getTarget();
382                     return pair;
383                 }
384             }
385 
386             // default case: Fall through.      
387             single[0] = getInstruction().getNext();
388             return single;
389         }
390 
391     } // End Inner InstructionContextImpl Class.
392 
393     /** The MethodGen object we're working on. */
394     private final MethodGen method_gen;
395 
396     /** The Subroutines object for the method whose control flow is represented by this ControlFlowGraph. */
397     private final Subroutines subroutines;
398 
399     /** The ExceptionHandlers object for the method whose control flow is represented by this ControlFlowGraph. */
400     private final ExceptionHandlers exceptionhandlers;
401 
402     /** All InstructionContext instances of this ControlFlowGraph. */
403     private Hashtable   instructionContexts = new Hashtable  (); //keys: InstructionHandle, values: InstructionContextImpl
404 
405     /** 
406      * A Control Flow Graph.
407      */
408     public ControlFlowGraph(MethodGen method_gen){
409         subroutines = new Subroutines(method_gen);
410         exceptionhandlers = new ExceptionHandlers(method_gen);
411 
412         InstructionHandle[] instructionhandles = method_gen.getInstructionList().getInstructionHandles();
413         for (int i=0; i<instructionhandles.length; i++){
414             instructionContexts.put(instructionhandles[i], new InstructionContextImpl(instructionhandles[i]));
415         }
416         
417         this.method_gen = method_gen;
418     }
419 
420     /**
421      * Returns the InstructionContext of a given instruction.
422      */
423     public InstructionContext contextOf(InstructionHandle inst){
424         InstructionContext ic = (InstructionContext) instructionContexts.get(inst);
425         if (ic == null){
426             throw new AssertionViolatedException("InstructionContext requested for an InstructionHandle that's not known!");
427         }
428         return ic;
429     }
430 
431     /**
432      * Returns the InstructionContext[] of a given InstructionHandle[],
433      * in a naturally ordered manner.
434      */
435     public InstructionContext[] contextsOf(InstructionHandle[] insts){
436         InstructionContext[] ret = new InstructionContext[insts.length];
437         for (int i=0; i<insts.length; i++){
438             ret[i] = contextOf(insts[i]);
439         }
440         return ret;
441     }
442 
443     /**
444      * Returns an InstructionContext[] with all the InstructionContext instances
445      * for the method whose control flow is represented by this ControlFlowGraph
446      * <B>(NOT ORDERED!)</B>.
447      */
448     public InstructionContext[] getInstructionContexts(){
449         InstructionContext[] ret = new InstructionContext[instructionContexts.values().size()];
450         return (InstructionContext[]) instructionContexts.values().toArray(ret);
451     }
452 
453     /**
454      * Returns true, if and only if the said instruction is not reachable; that means,
455      * if it is not part of this ControlFlowGraph.
456      */
457     public boolean isDead(InstructionHandle i){
458         return subroutines.subroutineOf(i) == null;
459     }    
460 }
461
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags