View Javadoc

1   // ExceptionAnalysis.java, created May 5, 2004 2:10:39 AM by joewhaley
2   // Copyright (C) 2004 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.Compiler.Analysis.IPA;
5   
6   import java.util.Collection;
7   import java.util.Collections;
8   import java.util.HashMap;
9   import java.util.HashSet;
10  import java.util.Iterator;
11  import java.util.List;
12  import java.util.Map;
13  import java.util.Set;
14  import java.io.IOException;
15  import java.io.PrintStream;
16  import java.lang.ref.SoftReference;
17  import joeq.Class.PrimordialClassLoader;
18  import joeq.Class.jq_Class;
19  import joeq.Class.jq_Method;
20  import joeq.Compiler.Analysis.IPA.ProgramLocation.QuadProgramLocation;
21  import joeq.Compiler.Dataflow.ReachingDefs;
22  import joeq.Compiler.Quad.BasicBlock;
23  import joeq.Compiler.Quad.BasicBlockVisitor;
24  import joeq.Compiler.Quad.CallGraph;
25  import joeq.Compiler.Quad.CodeCache;
26  import joeq.Compiler.Quad.ControlFlowGraph;
27  import joeq.Compiler.Quad.ExceptionHandler;
28  import joeq.Compiler.Quad.ExceptionHandlerList;
29  import joeq.Compiler.Quad.LoadedCallGraph;
30  import joeq.Compiler.Quad.Operand;
31  import joeq.Compiler.Quad.Quad;
32  import joeq.Compiler.Quad.QuadVisitor;
33  import joeq.Compiler.Quad.Operand.AConstOperand;
34  import joeq.Compiler.Quad.Operand.RegisterOperand;
35  import joeq.Compiler.Quad.Operator.CheckCast;
36  import joeq.Compiler.Quad.Operator.Invoke;
37  import joeq.Compiler.Quad.Operator.Move;
38  import joeq.Compiler.Quad.Operator.New;
39  import joeq.Compiler.Quad.Operator.Return;
40  import joeq.Compiler.Quad.Operator.Special;
41  import joeq.Compiler.Quad.RegisterFactory.Register;
42  import joeq.Main.HostedVM;
43  import jwutil.graphs.SCComponent;
44  import jwutil.graphs.Traversals;
45  
46  /***
47   * Uses a call graph to figure out what exceptions can be thrown by a method invocation.
48   * 
49   * @author John Whaley
50   * @version $Id: ExceptionAnalysis.java 1931 2004-09-22 22:17:47Z joewhaley $
51   */
52  public class ExceptionAnalysis {
53      
54      /***
55       * Visit basic blocks to figure out what exceptions they can throw.
56       */
57      class BBVisit implements BasicBlockVisitor {
58          private final ControlFlowGraph cfg;
59          private final jq_Method method;
60          private final Set s;
61          boolean change;
62          ReachingDefs rd;
63  
64          private BBVisit(ControlFlowGraph cfg, jq_Method method, Set s) {
65              this.cfg = cfg;
66              this.method = method;
67              this.s = s;
68          }
69  
70          public void visitBasicBlock(final BasicBlock bb) {
71              bb.visitQuads(new QVisit(bb));
72          }
73          
74          /***
75           * Visit quads to figure out what exceptions they can throw.
76           * If toExHandler is set, we figure out the exceptions that can
77           * go to that handler.  If it is null, we figure out the exceptions
78           * that can go to method exit.
79           */
80          class QVisit extends QuadVisitor.EmptyVisitor {
81              private BasicBlock bb;
82              private ExceptionHandler toExHandler;
83  
84              QVisit(BasicBlock bb) {
85                  this.bb = bb;
86                  this.toExHandler = null;
87              }
88  
89              QVisit(BasicBlock bb, ExceptionHandler ex) {
90                  this.bb = bb;
91                  this.toExHandler = ex;
92              }
93              
94              /*** 
95               * Find the containing basic block for a quad.
96               */
97              BasicBlock findBasicBlock(Quad q) {
98                  if (bb.getQuadIndex(q) != -1) return bb;
99                  for (Iterator i = cfg.reversePostOrderIterator(); i.hasNext(); ) {
100                     BasicBlock bb2 = (BasicBlock) i.next();
101                     if (bb2.getQuadIndex(q) != -1) return bb2;
102                 }
103                 return null;
104             }
105             
106             void updateMySet(Collection exTypes) {
107                 if (toExHandler != null) {
108                     if (updateSet(exTypes, s, toExHandler))
109                         change = true;
110                 } else {
111                     if (updateSet(exTypes, s, bb.getExceptionHandlers()))
112                         change = true;
113                 }
114             }
115             
116             public void visitExceptionThrower(Quad obj) {
117                 if (obj.getOperator() instanceof Invoke) return; // handled elsewhere
118                 if (obj.getOperator() instanceof Return.THROW_A) return; // handled elsewhere
119                 updateMySet(obj.getThrownExceptions());
120             }
121 
122             public void visitReturn(Quad obj) {
123                 if (obj.getOperator() instanceof Return.THROW_A) {
124                     Operand op = Return.getSrc(obj);
125                     if (op instanceof RegisterOperand) {
126                         // TODO: common case is that the def is in the same basic block.
127                         // so just scan backwards in current basic block for definition.
128                         
129                         // use-def chain to figure out where this came from.
130                         if (rd == null) rd = ReachingDefs.solve(cfg);
131                         Register r = ((RegisterOperand) op).getRegister();
132                         Set d = rd.getReachingDefs(bb, obj, r);
133                         
134                         // Keep track of visited quads, so we don't get caught in a cycle.
135                         Set visited = new HashSet();
136                         for (Iterator i = d.iterator(); i.hasNext(); ) {
137                             Quad q = (Quad) i.next();
138                             BasicBlock bb2 = findBasicBlock(q);
139                             traceUseDef(visited, bb2, q);
140                         }
141                     } else if (op instanceof AConstOperand) {
142                         // evil: throw null constant.
143                         updateMySet(Collections.singleton(PrimordialClassLoader.getJavaLangNullPointerException()));
144                     }
145                 }
146             }
147 
148             public void visitInvoke(Quad obj) {
149                 ProgramLocation callSite = new QuadProgramLocation(method, obj);
150                 Collection targets = cg.getTargetMethods(callSite);
151                 for (Iterator i = targets.iterator(); i.hasNext(); ) {
152                     updateMySet(getThrownExceptions((jq_Method) i.next()));
153                 }
154             }
155             
156             void traceUseDef(Set visited, BasicBlock my_bb, Quad q) {
157                 if (!visited.add(q)) return;
158                 if (q.getOperator() instanceof New) {
159                     jq_Class type = (jq_Class) New.getType(q).getType();
160                     updateMySet(Collections.singleton(type));
161                 } else if (q.getOperator() instanceof Special.GET_EXCEPTION) {
162                     Iterator i = cfg.getExceptionHandlersMatchingEntry(my_bb);
163                     while (i.hasNext()) {
164                         ExceptionHandler eh = (ExceptionHandler) i.next();
165                         List bbs = eh.getHandledBasicBlocks();
166                         for (Iterator j = bbs.iterator(); j.hasNext(); ) {
167                             BasicBlock bb3 = (BasicBlock) j.next();
168                             // TODO: this will loop infinitely if there are mutually-dependent
169                             // exception handlers.
170                             bb3.visitQuads(new QVisit(bb3, eh));
171                         }
172                     }
173                 } else if (q.getOperator() instanceof Move ||
174                            q.getOperator() instanceof CheckCast) {
175                     Operand src = Move.getSrc(q);
176                     if (src instanceof RegisterOperand) {
177                         Register r = ((RegisterOperand) src).getRegister();
178                         if (rd == null) rd = ReachingDefs.solve(cfg);
179                         Set d = rd.getReachingDefs(my_bb, q, r);
180                         for (Iterator i = d.iterator(); i.hasNext(); ) {
181                             Quad q2 = (Quad) i.next();
182                             BasicBlock bb2 = findBasicBlock(q2);
183                             traceUseDef(visited, bb2, q2);
184                         }
185                     } else {
186                         // const null
187                         updateMySet(Collections.singleton(PrimordialClassLoader.getJavaLangNullPointerException()));
188                     }
189                 } else {
190                     // Comes from somewhere unknown.
191                     updateMySet(Collections.singleton(null));
192                 }
193             }
194 
195         }
196 
197     }
198 
199     static final boolean USE_SOFTREF = true;
200     static final boolean TRACE = false;
201     static final PrintStream out = System.out;
202     
203     CallGraph cg;
204     Map cache;
205     Map recursive;
206     
207     /***
208      * Construct exception analysis using the given call graph.
209      */
210     public ExceptionAnalysis(CallGraph cg) {
211         if (TRACE) out.println("Initializing exception analysis");
212         this.cg = cg;
213         this.cache = new HashMap();
214         this.recursive = new HashMap();
215     }
216     
217     private void findRecursiveMethods() {
218         Set/*SCComponent*/ roots = SCComponent.buildSCC(cg);
219         List list = Traversals.reversePostOrder(SCComponent.SCC_NAVIGATOR, roots);
220         for (Iterator i = list.iterator(); i.hasNext(); ) {
221             SCComponent scc = (SCComponent) i.next();
222             if (scc.isLoop()) {
223                 for (Iterator j = scc.nodeSet().iterator(); j.hasNext(); ) {
224                     this.recursive.put(j.next(), scc);
225                 }
226             }
227         }
228         if (TRACE) out.println("Recursive methods: "+recursive);
229     }
230     
231     static boolean updateSet(Collection exTypes, Set s, ExceptionHandler eh) {
232         boolean c = false;
233         for (Iterator i = exTypes.iterator(); i.hasNext(); ) {
234             jq_Class r = (jq_Class) i.next();
235             if (s.contains(r)) continue;
236             jq_Class r2 = r;
237             if (r2 == null) r2 = PrimordialClassLoader.JavaLangThrowable;
238             if (eh != null && !eh.mayCatch(r2)) continue;
239             if (s.add(r)) c = true;
240         }
241         return c;
242     }
243     
244     static boolean updateSet(Collection exTypes, Set s, ExceptionHandlerList ex) {
245         boolean c = false;
246         for (Iterator i = exTypes.iterator(); i.hasNext(); ) {
247             jq_Class r = (jq_Class) i.next();
248             if (s.contains(r)) continue;
249             jq_Class r2 = r;
250             if (r2 == null) r2 = PrimordialClassLoader.JavaLangThrowable;
251             if (ex != null && ex.mustCatch(r2) != null) continue;
252             if (s.add(r)) c = true;
253         }
254         return c;
255     }
256     
257     /***
258      * Return the set of exception types that can be thrown by this call.
259      * 
260      * @param callSite call site
261      * @return set of exception types
262      */
263     public Set getThrownExceptions(ProgramLocation callSite) {
264         Set s = new HashSet();
265         getThrownExceptions(callSite, s, null);
266         return s;
267     }
268     
269     /***
270      * Add the set of exception types that can be thrown by this call and
271      * that are not caught by the given exception handlers to the given set.
272      * Returns true iff the set changed.
273      * 
274      * @param callSite call site
275      * @param s set
276      * @param ex exception handler list
277      * @return whether set changed
278      */
279     public boolean getThrownExceptions(ProgramLocation callSite, Set s, ExceptionHandlerList ex) {
280         if (TRACE) out.println("Call site "+callSite);
281         Collection targets = cg.getTargetMethods(callSite);
282         if (TRACE) out.println("    Targets "+targets);
283         boolean change = false;
284         for (Iterator i = targets.iterator(); i.hasNext(); ) {
285             if (updateSet(getThrownExceptions((jq_Method) i.next()), s, ex))
286                 change = true;
287         }
288         if (TRACE) out.println("    Exceptions: "+s);
289         return change;
290     }
291     
292     private Set checkCache(jq_Method method) {
293         Object o = cache.get(method);
294         if (USE_SOFTREF && o instanceof SoftReference) {
295             return (Set) ((SoftReference) o).get();
296         } else {
297             return (Set) o;
298         }
299     }
300     
301     /***
302      * Return the set of exception types that can be thrown by this method.
303      * 
304      * @param method
305      * @return set of exception types
306      */
307     public Set getThrownExceptions(jq_Method method) {
308         Set s = checkCache(method);
309         if (s != null) {
310             if (TRACE) out.println("Cache hit: "+method);
311             return s;
312         }
313         
314         SCComponent scc = (SCComponent) recursive.get(method);
315         if (scc != null) {
316             if (TRACE) out.println(method+" is recursive, iterating around "+scc);
317             iterateScc(scc);
318             s = checkCache(method);
319         } else {
320             s = new HashSet();
321             cache.put(method, USE_SOFTREF ? (Object) new SoftReference(s) : (Object) s);
322             calcThrownExceptions(method, s);
323         }
324         return s;
325     }
326     
327     private boolean calcThrownExceptions(final jq_Method method, final Set s) {
328         if (TRACE) out.println("Calculating thrown exceptions of "+method);
329         if (method.getBytecode() == null) {
330             if (method.isAbstract()) {
331                 if (TRACE) out.println(method+" is abstract");
332                 return s.add(PrimordialClassLoader.loader.getOrCreateBSType("Ljava/lang/AbstractMethodError;"));
333             }
334             if (method.isNative()) {
335                 // Native methods can throw arbitrary exceptions.
336                 if (TRACE) out.println(method+" is native");
337                 boolean change = s.add(null);
338                 return s.add(PrimordialClassLoader.loader.getOrCreateBSType("Ljava/lang/LinkageError;")) || change;
339             }
340             // huh?
341             return s.add(null);
342         }
343         
344         ControlFlowGraph cfg = CodeCache.getCode(method);
345         BBVisit bbv = new BBVisit(cfg, method, s);
346         cfg.visitBasicBlocks(bbv);
347         
348         if (TRACE) out.println("Thrown exceptions of "+method+": "+s);
349         return bbv.change;
350     }
351 
352     private void iterateScc(SCComponent scc) {
353         // Pre-allocate all cache entries, so we don't reenter iterateScc on
354         // methods in the same SCC.
355         for (Iterator i = scc.nodeSet().iterator(); i.hasNext(); ) {
356             jq_Method method = (jq_Method) i.next();
357             Set s = checkCache(method);
358             if (s == null) {
359                 s = new HashSet();
360                 cache.put(method, USE_SOFTREF ? (Object) new SoftReference(s) : (Object) s);
361             }
362         }
363         // Iterate until no more changes.
364         boolean change;
365         do {
366             change = false;
367             if (TRACE) out.println("Iterating: "+scc);
368             for (Iterator i = scc.nodeSet().iterator(); i.hasNext(); ) {
369                 jq_Method method = (jq_Method) i.next();
370                 Set s = checkCache(method);
371                 if (USE_SOFTREF && s == null) {
372                     // Soft reference was cleared, make it a hard reference so that
373                     // we can finish the SCC iteration.
374                     if (TRACE) out.println("Soft ref for "+method+" was cleared, changing to hard ref");
375                     s = new HashSet();
376                     cache.put(method, s);
377                 }
378                 if (calcThrownExceptions(method, s)) {
379                     change = true;
380                 }
381             }
382             if (TRACE && change) out.println("Change occurred, iterating again.");
383         } while (change);
384     }
385     
386     public static void main(String[] args) throws IOException {
387         HostedVM.initialize();
388         CodeCache.AlwaysMap = true;
389         String cgFilename = System.getProperty("callgraph", "callgraph");
390         if (args.length > 1) cgFilename = args[0];
391         CallGraph cg = new LoadedCallGraph(cgFilename);
392         ExceptionAnalysis ea = new ExceptionAnalysis(cg);
393         long time = System.currentTimeMillis();
394         for (Iterator i = cg.getAllMethods().iterator(); i.hasNext(); ) {
395             jq_Method m = (jq_Method) i.next();
396             Set s = ea.getThrownExceptions(m);
397             //System.out.println("Method "+m+" can throw:");
398             //System.out.println("    "+s);
399         }
400         time = System.currentTimeMillis() - time;
401         System.out.println("Time spent: "+time+" ms");
402     }
403 }