View Javadoc

1   package joeq.Compiler.Analysis.IPA;
2   
3   import java.util.Collection;
4   import java.util.HashSet;
5   import java.util.Iterator;
6   import java.util.LinkedList;
7   import java.util.Set;
8   import java.io.IOException;
9   import joeq.Class.jq_Class;
10  import joeq.Class.jq_Method;
11  import joeq.Compiler.Quad.BasicBlock;
12  import joeq.Compiler.Quad.CallGraph;
13  import joeq.Compiler.Quad.CodeCache;
14  import joeq.Compiler.Quad.ControlFlowGraph;
15  import joeq.Compiler.Quad.ControlFlowGraphVisitor;
16  import joeq.Compiler.Quad.LoadedCallGraph;
17  import joeq.Compiler.Quad.Quad;
18  import joeq.Compiler.Quad.QuadVisitor;
19  import joeq.Main.Helper;
20  import jwutil.graphs.SCCTopSortedGraph;
21  import jwutil.graphs.SCComponent;
22  import jwutil.graphs.Traversals;
23  import jwutil.util.Assert;
24  
25  /***
26   * @author jwhaley
27   * @version $Id: LoopAnalysis.java 1931 2004-09-22 22:17:47Z joewhaley $
28   */
29  public class LoopAnalysis implements ControlFlowGraphVisitor {
30  
31      public static void main(String[] args) throws IOException {
32          jq_Class c = (jq_Class) Helper.load(args[0]);
33          CodeCache.AlwaysMap = true;
34          CallGraph cg = new LoadedCallGraph("callgraph");
35          LoopAnalysis a = new LoopAnalysis(cg);
36          Helper.runPass(c, a);
37          System.out.println("Visited methods: "+a.visitedMethods);
38          System.out.println("Loop methods: "+a.loopMethods);
39          System.out.println("Loop BB: "+a.loopBB);
40      }
41  
42      CallGraph cg;
43      jq_Method caller;
44      Set visitedMethods = new HashSet();
45      Set loopMethods = new HashSet();
46      Set loopBB = new HashSet();
47  
48      public LoopAnalysis() {
49      }
50      
51      public LoopAnalysis(CallGraph cg) {
52          this.cg = cg;
53      }
54      
55      /* (non-Javadoc)
56       * @see joeq.Compiler.Quad.ControlFlowGraphVisitor#visitCFG(joeq.Compiler.Quad.ControlFlowGraph)
57       */
58      public void visitCFG(ControlFlowGraph cfg) {
59          caller = cfg.getMethod();
60          if (visitedMethods.contains(caller))
61              return;
62          visitedMethods.add(caller);
63          
64          // Find SCCs.
65          Set roots = SCComponent.buildSCC(cfg);
66          SCCTopSortedGraph g = SCCTopSortedGraph.topSort(roots);
67          
68          // Find loops.
69          for (Iterator i = Traversals.reversePostOrder(g.getNavigator(), roots).iterator();
70               i.hasNext(); ) {
71              SCComponent scc = (SCComponent) i.next();
72              if (scc.isLoop()) {
73                  for (Iterator j = scc.nodeSet().iterator(); j.hasNext(); ) {
74                      BasicBlock bb = (BasicBlock) j.next();
75                      loopBB.add(bb);
76                      if (cg != null)
77                          bb.visitQuads(invoke_visitor);
78                  }
79              }
80          }
81      }
82      
83      public boolean isInLoop(jq_Method m, BasicBlock bb) {
84          if (loopMethods.contains(m)) return true;
85          if (!visitedMethods.contains(m)) {
86              visitCFG(CodeCache.getCode(m));
87              if (loopMethods.contains(m)) return true;
88          }
89          if (loopBB.contains(bb)) return true;
90          return false;
91      }
92      
93      InvokeVisitor invoke_visitor = new InvokeVisitor();
94      public class InvokeVisitor extends QuadVisitor.EmptyVisitor {
95          public void visitInvoke(Quad q) {
96              super.visitInvoke(q);
97              Assert._assert(caller != null);
98              Assert._assert(q != null);
99              ProgramLocation mc = new ProgramLocation.QuadProgramLocation(caller, q);
100             LinkedList w = new LinkedList();
101             w.add(mc);
102             while (!w.isEmpty()) {
103                 mc = (ProgramLocation) w.removeFirst();
104                 Collection targets = cg.getTargetMethods(mc);
105                 for (Iterator i = targets.iterator(); i.hasNext(); ) {
106                     jq_Method callee = (jq_Method) i.next();
107                     boolean change = loopMethods.add(callee);
108                     if (change) {
109                         w.addAll(cg.getCallSites(callee));
110                     }
111                 }
112             }
113         }
114     }
115 }