BetterCFGBuilder2


1   /*
2    * Bytecode Analysis Framework
3    * Copyright (C) 2003,2004 University of Maryland
4    * 
5    * This library is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2.1 of the License, or (at your option) any later version.
9    * 
10   * This library is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   * 
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this library; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18   */
19  
20  package edu.umd.cs.findbugs.ba;
21  
22  import java.util.BitSet  ;
23  import java.util.IdentityHashMap  ;
24  import java.util.Iterator  ;
25  import java.util.LinkedList  ;
26  import java.util.List  ;
27  
28  import org.apache.bcel.Constants;
29  import org.apache.bcel.classfile.ClassParser;
30  import org.apache.bcel.classfile.JavaClass;
31  import org.apache.bcel.classfile.Method;
32  import org.apache.bcel.generic.BranchInstruction;
33  import org.apache.bcel.generic.ClassGen;
34  import org.apache.bcel.generic.CodeExceptionGen;
35  import org.apache.bcel.generic.ConstantPoolGen;
36  import org.apache.bcel.generic.ExceptionThrower;
37  import org.apache.bcel.generic.GETSTATIC;
38  import org.apache.bcel.generic.INSTANCEOF;
39  import org.apache.bcel.generic.Instruction;
40  import org.apache.bcel.generic.InstructionHandle;
41  import org.apache.bcel.generic.InstructionList;
42  import org.apache.bcel.generic.InstructionTargeter;
43  import org.apache.bcel.generic.JsrInstruction;
44  import org.apache.bcel.generic.MONITORENTER;
45  import org.apache.bcel.generic.MONITOREXIT;
46  import org.apache.bcel.generic.MethodGen;
47  import org.apache.bcel.generic.NEW;
48  import org.apache.bcel.generic.NOP;
49  import org.apache.bcel.generic.PUTSTATIC;
50  import org.apache.bcel.generic.ReturnInstruction;
51  
52  import edu.umd.cs.findbugs.SystemProperties;
53  import edu.umd.cs.findbugs.annotations.NonNull;
54  import edu.umd.cs.findbugs.annotations.Nullable;
55  
56  /**
57   * A CFGBuilder that really tries to construct accurate control flow graphs.
58   * The CFGs it creates have accurate exception edges, and have accurately
59   * inlined JSR subroutines.
60   *
61   * @author David Hovemeyer
62   * @see CFG
63   */
64  public class BetterCFGBuilder2 implements CFGBuilder, EdgeTypes, Debug {
65  
66      private static final boolean DEBUG = SystemProperties.getBoolean("cfgbuilder.debug");
67  
68      // TODO: don't forget to change BasicBlock so ATHROW is considered to have a null check
69  
70      /* ----------------------------------------------------------------------
71       * Helper classes
72       * ---------------------------------------------------------------------- */
73  
74      /**
75       * A work list item for creating the CFG for a subroutine.
76       */
77      private static class WorkListItem {
78          private final InstructionHandle start;
79          private final BasicBlock basicBlock;
80  
81          /**
82           * Constructor.
83           *
84           * @param start      first instruction in the basic block
85           * @param basicBlock the basic block to build
86           */
87          public WorkListItem(InstructionHandle start, BasicBlock basicBlock) {
88              this.start = start;
89              this.basicBlock = basicBlock;
90          }
91  
92          /**
93           * Get the start instruction.
94           */
95          public InstructionHandle getStartInstruction() {
96              return start;
97          }
98  
99          /**
100          * Get the basic block.
101          */
102         public BasicBlock getBasicBlock() {
103             return basicBlock;
104         }
105     }
106 
107     /**
108      * A placeholder for a control edge that escapes its subroutine to return
109      * control back to an outer (calling) subroutine.  It will turn into a
110      * real edge during inlining.
111      */
112     private static class EscapeTarget {
113         private final InstructionHandle target;
114         private final int edgeType;
115 
116         /**
117          * Constructor.
118          *
119          * @param target   the target instruction in a calling subroutine
120          * @param edgeType the type of edge that should be created when the
121          *                 subroutine is inlined into its calling context
122          */
123         public EscapeTarget(InstructionHandle target, int edgeType) {
124             this.target = target;
125             this.edgeType = edgeType;
126         }
127 
128         /**
129          * Get the target instruction.
130          */
131         public InstructionHandle getTarget() {
132             return target;
133         }
134 
135         /**
136          * Get the edge type.
137          */
138         public int getEdgeType() {
139             return edgeType;
140         }
141     }
142 
143     private static final LinkedList  <EscapeTarget> emptyEscapeTargetList = new LinkedList  <EscapeTarget>();
144 
145     /**
146      * JSR subroutine.  The top level subroutine is where execution starts.
147      * Each subroutine has its own CFG.  Eventually,
148      * all JSR subroutines will be inlined into the top level subroutine,
149      * resulting in an accurate CFG for the overall method.
150      */
151     private class Subroutine {
152         private final InstructionHandle start;
153         private final BitSet   instructionSet;
154         private final CFG cfg;
155         private IdentityHashMap  <InstructionHandle, BasicBlock> blockMap;
156         private IdentityHashMap  <BasicBlock, List  <EscapeTarget>> escapeTargetListMap;
157         private BitSet   returnBlockSet;
158         private BitSet   exitBlockSet;
159         private BitSet   unhandledExceptionBlockSet;
160         private LinkedList  <WorkListItem> workList;
161 
162         /**
163          * Constructor.
164          *
165          * @param start the start instruction for the subroutine
166          */
167         public Subroutine(InstructionHandle start) {
168             this.start = start;
169             this.instructionSet = new BitSet  ();
170             this.cfg = new CFG();
171             this.blockMap = new IdentityHashMap  <InstructionHandle, BasicBlock>();
172             this.escapeTargetListMap = new IdentityHashMap  <BasicBlock, List  <EscapeTarget>>();
173             this.returnBlockSet = new BitSet  ();
174             this.exitBlockSet = new BitSet  ();
175             this.unhandledExceptionBlockSet = new BitSet  ();
176             this.workList = new LinkedList  <WorkListItem>();
177         }
178 
179         /**
180          * Get the start instruction.
181          */
182         public InstructionHandle getStartInstruction() {
183             return start;
184         }
185 
186         /**
187          * Allocate a new basic block in the subroutine.
188          */
189         public BasicBlock allocateBasicBlock() {
190             return cfg.allocate();
191         }
192 
193         /**
194          * Add a work list item for a basic block to be constructed.
195          */
196         public void addItem(WorkListItem item) {
197             workList.add(item);
198         }
199 
200         /**
201          * Are there more work list items?
202          */
203         public boolean hasMoreWork() {
204             return !workList.isEmpty();
205         }
206 
207         /**
208          * Get the next work list item.
209          */
210         public WorkListItem nextItem() {
211             return workList.removeFirst();
212         }
213 
214         /**
215          * Get the entry block for the subroutine's CFG.
216          */
217         public BasicBlock getEntry() {
218             return cfg.getEntry();
219         }
220 
221         /**
222          * Get the exit block for the subroutine's CFG.
223          */
224         public BasicBlock getExit() {
225             return cfg.getExit();
226         }
227 
228         /**
229          * Get the start block for the subroutine's CFG.
230          * (I.e., the block containing the start instruction.)
231          */
232         public BasicBlock getStartBlock() {
233             return getBlock(start);
234         }
235 
236         /**
237          * Get the subroutine's CFG.
238          */
239         public CFG getCFG() {
240             return cfg;
241         }
242 
243         /**
244          * Add an instruction to the subroutine.
245          * We keep track of which instructions are part of which subroutines.
246          * No instruction may be part of more than one subroutine.
247          *
248          * @param handle the instruction to be added to the subroutine
249          */
250         public void addInstruction(InstructionHandle handle) throws CFGBuilderException {
251             int position = handle.getPosition();
252             if (usedInstructionSet.get(position))
253                 throw new CFGBuilderException("Instruction " + handle + " visited in multiple subroutines");
254             instructionSet.set(position);
255             usedInstructionSet.set(position);
256         }
257 
258         /**
259          * Is the given instruction part of this subroutine?
260          */
261         public boolean containsInstruction(InstructionHandle handle) {
262             return instructionSet.get(handle.getPosition());
263         }
264 
265         /**
266          * Get the basic block in the subroutine for the given instruction.
267          * If the block doesn't exist yet, it is created, and a work list
268          * item is added which will populate it.  Note that if start is
269          * an exception thrower, the block returned will be its ETB.
270          *
271          * @param start the start instruction for the block
272          * @return the basic block for the instruction
273          */
274         public BasicBlock getBlock(InstructionHandle start) {
275             BasicBlock block = blockMap.get(start);
276             if (block == null) {
277                 block = allocateBasicBlock();
278                 blockMap.put(start, block);
279 
280                 // Block is an exception handler?
281                 CodeExceptionGen exceptionGen = exceptionHandlerMap.getHandlerForStartInstruction(start);
282                 if (exceptionGen != null)
283                     block.setExceptionGen(exceptionGen);
284 
285                 addItem(new WorkListItem(start, block));
286             }
287             return block;
288         }
289 
290         /**
291          * Indicate that the method returns at the end of the given block.
292          *
293          * @param block the returning block
294          */
295         public void setReturnBlock(BasicBlock block) {
296             returnBlockSet.set(block.getId());
297         }
298 
299         /**
300          * Does the method return at the end of this block?
301          */
302         public boolean isReturnBlock(BasicBlock block) {
303             return returnBlockSet.get(block.getId());
304         }
305 
306         /**
307          * Indicate that System.exit() is called at the end of the given block.
308          *
309          * @param block the exiting block
310          */
311         public void setExitBlock(BasicBlock block) {
312             exitBlockSet.set(block.getId());
313         }
314 
315         /**
316          * Is System.exit() called at the end of this block?
317          */
318         public boolean isExitBlock(BasicBlock block) {
319             return exitBlockSet.get(block.getId());
320         }
321 
322         /**
323          * Indicate that an unhandled exception may be thrown by
324          * the given block.
325          *
326          * @param block the block throwing an unhandled exception
327          */
328         public void setUnhandledExceptionBlock(BasicBlock block) {
329             unhandledExceptionBlockSet.set(block.getId());
330         }
331 
332         /**
333          * Does this block throw an unhandled exception?
334          */
335         public boolean isUnhandledExceptionBlock(BasicBlock block) {
336             return unhandledExceptionBlockSet.get(block.getId());
337         }
338 
339         /**
340          * Add a control flow edge to the subroutine.
341          * If the control target has not yet been added to the subroutine,
342          * a new work list item is added.  If the control target is in
343          * another subroutine, an EscapeTarget is added.
344          *
345          * @param sourceBlock the source basic block
346          * @param target      the control target
347          * @param edgeType    the type of control edge
348          */
349         public void addEdgeAndExplore(BasicBlock sourceBlock, InstructionHandle target, int edgeType) {
350             if (usedInstructionSet.get(target.getPosition()) && !containsInstruction(target)) {
351                 // Control escapes this subroutine
352                 List  <EscapeTarget> escapeTargetList = escapeTargetListMap.get(sourceBlock);
353                 if (escapeTargetList == null) {
354                     escapeTargetList = new LinkedList  <EscapeTarget>();
355                     escapeTargetListMap.put(sourceBlock, escapeTargetList);
356                 }
357                 escapeTargetList.add(new EscapeTarget(target, edgeType));
358             } else {
359                 // Edge within the current subroutine
360                 BasicBlock targetBlock = getBlock(target);
361                 addEdge(sourceBlock, targetBlock, edgeType);
362             }
363         }
364 
365         /**
366          * Add an edge to the subroutine's CFG.
367          *
368          * @param sourceBlock the source basic block
369          * @param destBlock   the destination basic block
370          * @param edgeType    the type of edge
371          */
372         public void addEdge(BasicBlock sourceBlock, BasicBlock destBlock, int edgeType) {
373             if (VERIFY_INTEGRITY) {
374                 if (destBlock.isExceptionHandler() && edgeType != HANDLED_EXCEPTION_EDGE)
375                     throw new IllegalStateException  ("In method " + SignatureConverter.convertMethodSignature(methodGen) +
376                             ": exception handler " + destBlock.getFirstInstruction() + " reachable by non exception edge type " +
377                             edgeType);
378             }
379             cfg.createEdge(sourceBlock, destBlock, edgeType);
380         }
381 
382         /**
383          * Get an Iterator over the EscapeTargets of given basic block.
384          *
385          * @param sourceBlock the basic block
386          * @return an Iterator over the EscapeTargets
387          */
388         public Iterator  <EscapeTarget> escapeTargetIterator(BasicBlock sourceBlock) {
389             List  <EscapeTarget> escapeTargetList = escapeTargetListMap.get(sourceBlock);
390             if (escapeTargetList == null)
391                 escapeTargetList = emptyEscapeTargetList;
392             return escapeTargetList.iterator();
393         }
394     }
395 
396     /**
397      * Inlining context.
398      * This essentially consists of a inlining site and
399      * a subroutine to be inlined.  A stack of calling contexts
400      * is maintained in order to resolve EscapeTargets.
401      */
402     private static class Context {
403         private final Context caller;
404         private final Subroutine subroutine;
405         private final CFG result;
406         private final IdentityHashMap  <BasicBlock, BasicBlock> blockMap;
407         private final LinkedList  <BasicBlock> workList;
408 
409         /**
410          * Constructor.
411          *
412          * @param caller     the calling context
413          * @param subroutine the subroutine being inlined
414          * @param result     the result CFG
415          */
416         public Context(@Nullable Context caller, Subroutine subroutine, CFG result) {
417             this.caller = caller;
418             this.subroutine = subroutine;
419             this.result = result;
420             this.blockMap = new IdentityHashMap  <BasicBlock, BasicBlock>();
421             this.workList = new LinkedList  <BasicBlock>();
422         }
423 
424         /**
425          * Get the calling context.
426          */
427         public Context getCaller() {
428             return caller;
429         }
430 
431         /**
432          * Get the subroutine being inlined.
433          */
434         public Subroutine getSubroutine() {
435             return subroutine;
436         }
437 
438         /**
439          * Get the result CFG.
440          */
441         public CFG getResult() {
442             return result;
443         }
444 
445         /**
446          * Add a basic block to the inlining work list.
447          */
448         public void addItem(BasicBlock item) {
449             workList.add(item);
450         }
451 
452         /**
453          * Are there more work list items?
454          */
455         public boolean hasMoreWork() {
456             return !workList.isEmpty();
457         }
458 
459         /**
460          * Get the next work list item (basic block to be inlined).
461          */
462         public BasicBlock nextItem() {
463             return workList.removeFirst();
464         }
465 
466         /**
467          * Map a basic block in a subroutine to the corresponding block
468          * in the resulting CFG.
469          *
470          * @param subBlock    the subroutine block
471          * @param resultBlock the result CFG block
472          */
473         public void mapBlock(BasicBlock subBlock, BasicBlock resultBlock) {
474             blockMap.put(subBlock, resultBlock);
475         }
476 
477         /**
478          * Get the block in the result CFG corresponding to the given
479          * subroutine block.
480          *
481          * @param subBlock the subroutine block
482          * @return the result CFG block
483          */
484         public BasicBlock getBlock(BasicBlock subBlock) {
485             BasicBlock resultBlock = blockMap.get(subBlock);
486             if (resultBlock == null) {
487                 resultBlock = result.allocate();
488                 blockMap.put(subBlock, resultBlock);
489                 workList.add(subBlock);
490             }
491             return resultBlock;
492         }
493 
494         /**
495          * Check to ensure that this context is not the result of recursion.
496          */
497         public void checkForRecursion() throws CFGBuilderException {
498             Context callerContext = caller;
499 
500             while (callerContext != null) {
501                 if (callerContext.subroutine == this.subroutine)
502                     throw new CFGBuilderException("JSR recursion detected!");
503                 callerContext = callerContext.caller;
504             }
505         }
506     }
507 
508     /* ----------------------------------------------------------------------
509      * Instance data
510      * ---------------------------------------------------------------------- */
511 
512     private MethodGen methodGen;
513     private ConstantPoolGen cpg;
514     private ExceptionHandlerMap exceptionHandlerMap;
515     private BitSet   usedInstructionSet;
516     private LinkedList  <Subroutine> subroutineWorkList;
517     private IdentityHashMap  <InstructionHandle, Subroutine> jsrSubroutineMap;
518     private Subroutine topLevelSubroutine;
519     private CFG cfg;
520 
521     /* ----------------------------------------------------------------------
522      * Public methods
523      * ---------------------------------------------------------------------- */
524 
525     /**
526      * Constructor.
527      *
528      * @param methodGen the method to build a CFG for
529      */
530     public BetterCFGBuilder2(@NonNull MethodGen methodGen) {
531         this.methodGen = methodGen;
532         this.cpg = methodGen.getConstantPool();
533         this.exceptionHandlerMap = new ExceptionHandlerMap(methodGen);
534         this.usedInstructionSet = new BitSet  ();
535         this.jsrSubroutineMap = new IdentityHashMap  <InstructionHandle, Subroutine>();
536         this.subroutineWorkList = new LinkedList  <Subroutine>();
537     }
538 
539     public void build() throws CFGBuilderException {
540         topLevelSubroutine = new Subroutine(methodGen.getInstructionList().getStart());
541         subroutineWorkList.add(topLevelSubroutine);
542 
543         // Build top level subroutine and all JSR subroutines
544         while (!subroutineWorkList.isEmpty()) {
545             Subroutine subroutine = subroutineWorkList.removeFirst();
546             if (DEBUG) System.out.println("Starting subroutine " + subroutine.getStartInstruction());
547             build(subroutine);
548         }
549 
550         // Inline everything into the top level subroutine
551         cfg = inlineAll();
552 
553         // Add a NOP instruction to the entry block.
554         // This allows analyses to construct a Location
555         // representing the entry to the method.
556         BasicBlock entryBlock = cfg.getEntry();
557         InstructionList il = new InstructionList();
558         entryBlock.addInstruction(il.append(new NOP()));
559 
560         if (VERIFY_INTEGRITY)
561             cfg.checkIntegrity();
562     }
563 
564     public CFG getCFG() {
565         return cfg;
566     }
567 
568     /* ----------------------------------------------------------------------
569      * Implementation
570      * ---------------------------------------------------------------------- */
571 
572     /**
573      * Build a subroutine.
574      * We iteratively add basic blocks to the subroutine
575      * until there are no more blocks reachable from the calling context.
576      * As JSR instructions are encountered, new Subroutines are added
577      * to the subroutine work list.
578      *
579      * @param subroutine the subroutine
580      */
581     private void build(Subroutine subroutine) throws CFGBuilderException {
582         // Prime the work list
583         subroutine.addEdgeAndExplore(subroutine.getEntry(), subroutine.getStartInstruction(), START_EDGE);
584 
585         // Keep going until all basic blocks in the subroutine have been added
586         while (subroutine.hasMoreWork()) {
587             WorkListItem item = subroutine.nextItem();
588 
589             InstructionHandle handle = item.getStartInstruction();
590             BasicBlock basicBlock = item.getBasicBlock();
591 
592             // Add exception handler block (ETB) for exception-throwing instructions
593             if (isPEI(handle)) {
594                 if (DEBUG) System.out.println("ETB block " + basicBlock.getId() + " for " + handle);
595                 handleExceptions(subroutine, handle, basicBlock);
596                 BasicBlock body = subroutine.allocateBasicBlock();
597                 subroutine.addEdge(basicBlock, body, FALL_THROUGH_EDGE);
598                 basicBlock = body;
599             }
600 
601             if (DEBUG) System.out.println("BODY block " + basicBlock.getId() + " for " + handle);
602 
603             if (!basicBlock.isEmpty())
604                 throw new IllegalStateException  ("Block isn't empty!");
605 
606             // Add instructions until we get to the end of the block
607             boolean endOfBasicBlock = false;
608             do {
609                 Instruction ins = handle.getInstruction();
610 
611                 // Add the instruction to the block
612                 if (DEBUG) System.out.println("BB " + basicBlock.getId() + ": adding" + handle);
613                 basicBlock.addInstruction(handle);
614                 subroutine.addInstruction(handle);
615 
616                 short opcode = ins.getOpcode();
617 
618                 // TODO: should check instruction to ensure that in a JSR subroutine
619                 // no assignments are made to the local containing the return address.
620                 // if (ins instanceof ASTORE) ...
621 
622                 if (opcode == Constants.JSR || opcode == Constants.JSR_W) {
623                     // Find JSR subroutine, add it to subroutine work list if
624                     // we haven't built a CFG for it yet
625                     JsrInstruction jsr = (JsrInstruction) ins;
626                     InstructionHandle jsrTarget = jsr.getTarget();
627                     Subroutine jsrSubroutine = jsrSubroutineMap.get(jsrTarget);
628                     if (jsrSubroutine == null) {
629                         jsrSubroutine = new Subroutine(jsrTarget);
630                         jsrSubroutineMap.put(jsrTarget, jsrSubroutine);
631                         subroutineWorkList.add(jsrSubroutine);
632                     }
633 
634                     // This ends the basic block.
635                     // Add a JSR_EDGE to the successor.
636                     // It will be replaced later by the inlined JSR subroutine.
637                     subroutine.addEdgeAndExplore(basicBlock, handle.getNext(), JSR_EDGE);
638                     endOfBasicBlock = true;
639                 } else if (opcode == Constants.RET) {
640                     // End of JSR subroutine
641                     subroutine.addEdge(basicBlock, subroutine.getExit(), RET_EDGE);
642                     endOfBasicBlock = true;
643                 } else {
644                     TargetEnumeratingVisitor visitor = new TargetEnumeratingVisitor(handle, cpg);
645                     if (visitor.isEndOfBasicBlock()) {
646                         endOfBasicBlock = true;
647 
648                         // Add control edges as appropriate
649                         if (visitor.instructionIsThrow()) {
650                             handleExceptions(subroutine, handle, basicBlock);
651                         } else if (visitor.instructionIsExit()) {
652                             subroutine.setExitBlock(basicBlock);
653                         } else if (visitor.instructionIsReturn()) {
654                             subroutine.setReturnBlock(basicBlock);
655                         } else {
656                             Iterator  <Target> i = visitor.targetIterator();
657                             while (i.hasNext()) {
658                                 Target target = i.next();
659                                 subroutine.addEdgeAndExplore(basicBlock, target.getTargetInstruction(),
660                                         target.getEdgeType());
661                             }
662                         }
663                     }
664                 }
665 
666                 if (!endOfBasicBlock) {
667                     InstructionHandle next = handle.getNext();
668                     if (next == null)
669                         throw new CFGBuilderException("Control falls off end of method: " + handle);
670 
671                     // Is the next instruction a control merge or a PEI?
672                     if (isMerge(next) || isPEI(next)) {
673                         subroutine.addEdgeAndExplore(basicBlock, next, FALL_THROUGH_EDGE);
674                         endOfBasicBlock = true;
675                     } else {
676                         // Basic block continues
677                         handle = next;
678                     }
679                 }
680 
681             } while (!endOfBasicBlock);
682         }
683     }
684 
685     /**
686      * Add exception edges for given instruction.
687      *
688      * @param subroutine the subroutine containing the instruction
689      * @param pei        the instruction which throws an exception
690      * @param etb        the exception thrower block (ETB) for the instruction
691      */
692     private void handleExceptions(Subroutine subroutine, InstructionHandle pei, BasicBlock etb) {
693         etb.setExceptionThrower(pei);
694 
695         // Remember whether or not a universal exception handler
696         // is reachable.  If so, then we know that exceptions raised
697         // at this instruction cannot propagate out of the method.
698         boolean sawUniversalExceptionHandler = false;
699 
700         List  <CodeExceptionGen> exceptionHandlerList = exceptionHandlerMap.getHandlerList(pei);
701         if (exceptionHandlerList != null) {
702             for (CodeExceptionGen exceptionHandler : exceptionHandlerList) {
703                 InstructionHandle handlerStart = exceptionHandler.getHandlerPC();
704                 subroutine.addEdgeAndExplore(etb, handlerStart, HANDLED_EXCEPTION_EDGE);
705 
706                 if (Hierarchy.isUniversalExceptionHandler(exceptionHandler.getCatchType()))
707                     sawUniversalExceptionHandler = true;
708             }
709         }
710 
711         // If required, mark this block as throwing an unhandled exception.
712         // For now, we assume that if there is no reachable handler that handles
713         // ANY exception type, then the exception can be thrown out of the method.
714         if (!sawUniversalExceptionHandler) {
715             if (DEBUG) System.out.println("Adding unhandled exception edge from " + pei);
716             subroutine.setUnhandledExceptionBlock(etb);
717         }
718     }
719 
720     /**
721      * Return whether or not the given instruction can throw exceptions.
722      *
723      * @param handle the instruction
724      * @return true if the instruction can throw an exception, false otherwise
725      */
726     private boolean isPEI(InstructionHandle handle) {
727         Instruction ins = handle.getInstruction();
728 
729         if (!(ins instanceof ExceptionThrower))
730             return false;
731 
732         if (ins instanceof NEW) return false;
733         // if (ins instanceof ATHROW) return false;
734         if (ins instanceof GETSTATIC) return false;
735         if (ins instanceof PUTSTATIC) return false;
736         if (ins instanceof ReturnInstruction) return false;
737         if (ins instanceof INSTANCEOF) return false;
738         // if (ins instanceof INVOKESTATIC) return false;
739         if (ins instanceof MONITORENTER) return false;
740         if (ins instanceof MONITOREXIT) return false;
741         return true;
742     
743     }
744     /**
745      * Determine whether or not the given instruction is a control flow merge.
746      *
747      * @param handle the instruction
748      * @return true if the instruction is a control merge, false otherwise
749      */
750     private static boolean isMerge(InstructionHandle handle) {
751         if (handle.hasTargeters()) {
752             // Check all targeters of this handle to see if any
753             // of them are branches.  If so, the instruction is a merge.
754             InstructionTargeter[] targeterList = handle.getTargeters();
755             for (InstructionTargeter targeter : targeterList) {
756                 if (targeter instanceof BranchInstruction)
757                     return true;
758             }
759         }
760         return false;
761     }
762 
763     /**
764      * Inline all JSR subroutines into the top-level subroutine.
765      * This produces a complete CFG for the entire method, in which
766      * all JSR subroutines are inlined.
767      *
768      * @return the CFG for the method
769      */
770     private CFG inlineAll() throws CFGBuilderException {
771         CFG result = new CFG();
772 
773         Context rootContext = new Context(null, topLevelSubroutine, result);
774         rootContext.mapBlock(topLevelSubroutine.getEntry(), result.getEntry());
775         rootContext.mapBlock(topLevelSubroutine.getExit(), result.getExit());
776 
777         BasicBlock resultStartBlock = rootContext.getBlock(topLevelSubroutine.getStartBlock());
778         result.createEdge(result.getEntry(), resultStartBlock, START_EDGE);
779 
780         inline(rootContext);
781 
782         return result;
783     }
784 
785     /**
786      * Inline a subroutine into a calling context.
787      *
788      * @param context the Context
789      */
790     public void inline(Context context) throws CFGBuilderException {
791 
792         CFG result = context.getResult();
793 
794         // Check to ensure we're not trying to inline something that is recursive
795         context.checkForRecursion();
796 
797         Subroutine subroutine = context.getSubroutine();
798         CFG subCFG = subroutine.getCFG();
799 
800         while (context.hasMoreWork()) {
801             BasicBlock subBlock = context.nextItem();
802             BasicBlock resultBlock = context.getBlock(subBlock);
803             
804             // Mark blocks which are in JSR subroutines
805             resultBlock.setInJSRSubroutine(context.getCaller() != null);
806 
807             // Copy instructions into the result block
808             BasicBlock.InstructionIterator insIter = subBlock.instructionIterator();
809             while (insIter.hasNext()) {
810                 InstructionHandle handle = insIter.next();
811                 resultBlock.addInstruction(handle);
812             }
813 
814             // Set exception thrower status
815             if (subBlock.isExceptionThrower())
816                 resultBlock.setExceptionThrower(subBlock.getExceptionThrower());
817 
818             // Set exception handler status
819             if (subBlock.isExceptionHandler())
820                 resultBlock.setExceptionGen(subBlock.getExceptionGen());
821 
822             // Add control edges (including inlining JSR subroutines)
823             Iterator  <Edge> edgeIter = subCFG.outgoingEdgeIterator(subBlock);
824             while (edgeIter.hasNext()) {
825                 Edge edge = edgeIter.next();
826                 int edgeType = edge.getType();
827 
828                 if (edgeType == JSR_EDGE) {
829                     // Inline a JSR subroutine...
830 
831                     // Create a new Context
832                     InstructionHandle jsrHandle = subBlock.getLastInstruction();
833                     JsrInstruction jsr = (JsrInstruction) jsrHandle.getInstruction();
834                     Subroutine jsrSub = jsrSubroutineMap.get(jsr.getTarget());
835                     Context jsrContext = new Context(context, jsrSub, context.getResult());
836 
837                     // The start block in the JSR subroutine maps to the first
838                     // inlined block in the result CFG.
839                     BasicBlock resultJSRStartBlock = jsrContext.getBlock(jsrSub.getStartBlock());
840                     result.createEdge(resultBlock, resultJSRStartBlock, GOTO_EDGE);
841 
842                     // The exit block in the JSR subroutine maps to the result block
843                     // corresponding to the instruction following the JSR.
844                     // (I.e., that is where control returns after the execution of
845                     // the JSR subroutine.)
846                     BasicBlock subJSRSuccessorBlock = subroutine.getBlock(jsrHandle.getNext());
847                     BasicBlock resultJSRSuccessorBlock = context.getBlock(subJSRSuccessorBlock);
848                     jsrContext.mapBlock(jsrSub.getExit(), resultJSRSuccessorBlock);
849 
850                     // Inline the JSR subroutine
851                     inline(jsrContext);
852                 } else {
853                     // Ordinary control edge
854                     BasicBlock resultTarget = context.getBlock(edge.getTarget());
855                     result.createEdge(resultBlock, resultTarget, edge.getType());
856                 }
857             }
858 
859             // Add control edges for escape targets
860             Iterator  <EscapeTarget> escapeTargetIter = subroutine.escapeTargetIterator(subBlock);
861             while (escapeTargetIter.hasNext()) {
862                 EscapeTarget escapeTarget = escapeTargetIter.next();
863                 InstructionHandle targetInstruction = escapeTarget.getTarget();
864 
865                 // Look for the calling context which has the target instruction
866                 Context caller = context.getCaller();
867                 while (caller != null) {
868                     if (caller.getSubroutine().containsInstruction(targetInstruction))
869                         break;
870                     caller = caller.getCaller();
871                 }
872 
873                 if (caller == null)
874                     throw new CFGBuilderException("Unknown caller for escape target " + targetInstruction +
875                             " referenced by " + context.getSubroutine().getStartInstruction());
876 
877                 // Find result block in caller
878                 BasicBlock subCallerTargetBlock = caller.getSubroutine().getBlock(targetInstruction);
879                 BasicBlock resultCallerTargetBlock = caller.getBlock(subCallerTargetBlock);
880 
881                 // Add an edge to caller context
882                 result.createEdge(resultBlock, resultCallerTargetBlock, escapeTarget.getEdgeType());
883             }
884 
885             // If the block returns from the method, add a return edge
886             if (subroutine.isReturnBlock(subBlock)) {
887                 result.createEdge(resultBlock, result.getExit(), RETURN_EDGE);
888             }
889 
890             // If the block calls System.exit(), add an exit edge
891             if (subroutine.isExitBlock(subBlock)) {
892                 result.createEdge(resultBlock, result.getExit(), EXIT_EDGE);
893             }
894 
895             // If the block throws an unhandled exception, add an unhandled
896             // exception edge
897             if (subroutine.isUnhandledExceptionBlock(subBlock)) {
898                 result.createEdge(resultBlock, result.getExit(), UNHANDLED_EXCEPTION_EDGE);
899             }
900 
901         }
902 
903 /*
904         while (blocks are left) {
905 
906             get block from subroutine
907             get corresponding block from result
908             copy instructions into result block
909 
910             if (block terminated by JSR) {
911                 get JSR subroutine
912                 create new context
913                 create GOTO edge from current result block to start block of new inlined context
914                 map subroutine exit block to result JSR successor block
915                 inline (new context, result)
916             } else {
917                 for each outgoing edge {
918                     map each target to result blocks (add block to to work list if needed)
919                     add edges to result
920                 }
921 
922                 for each outgoing escape target {
923                     add edges into blocks in outer contexts (adding those blocks to outer work list if needed)
924                 }
925 
926                 if (block returns) {
927                     add return edge from result block to result CFG exit block
928                 }
929 
930                 if (block calls System.exit()) {
931                     add exit edge from result block to result CFG exit block
932                 }
933 
934                 if (block throws unhandled exception) {
935                     add unhandled exception edge from result block to result CFG exit block
936                 }
937             }
938 
939         }
940 */
941     }
942 
943     /**
944      * Test driver.
945      */
946     public static void main(String  [] argv) throws Exception   {
947         if (argv.length != 1) {
948             System.err.println("Usage: " + BetterCFGBuilder2.class.getName() + " <class file>");
949             System.exit(1);
950         }
951 
952         String   methodName = SystemProperties.getProperty("cfgbuilder.method");
953 
954         JavaClass jclass = new ClassParser(argv[0]).parse();
955         ClassGen classGen = new ClassGen(jclass);
956 
957         Method[] methodList = jclass.getMethods();
958         for (Method method : methodList) {
959             if (method.isAbstract() || method.isNative())
960                 continue;
961 
962             if (methodName != null && !method.getName().equals(methodName))
963                 continue;
964 
965             MethodGen methodGen = new MethodGen(method, jclass.getClassName(), classGen.getConstantPool());
966 
967             CFGBuilder cfgBuilder = new BetterCFGBuilder2(methodGen);
968             cfgBuilder.build();
969 
970             CFG cfg = cfgBuilder.getCFG();
971 
972             CFGPrinter cfgPrinter = new CFGPrinter(cfg);
973             System.out.println("---------------------------------------------------------------------");
974             System.out.println("Method: " + SignatureConverter.convertMethodSignature(methodGen));
975             System.out.println("---------------------------------------------------------------------");
976             cfgPrinter.print(System.out);
977         }
978     }
979 
980 }
981 
982 // vim:ts=4
983
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags