View Javadoc

1   // Solver.java, created Jun 14, 2003 10:20:27 PM by joewhaley
2   // Copyright (C) 2003 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.Compiler.Quad.IPA;
5   
6   import java.util.Collection;
7   import java.util.Iterator;
8   import java.util.Map;
9   import java.util.Set;
10  import joeq.Class.jq_Method;
11  import joeq.Compiler.Quad.CallGraph;
12  import jwutil.graphs.Navigator;
13  import jwutil.graphs.SCCTopSortedGraph;
14  import jwutil.graphs.SCComponent;
15  import jwutil.graphs.Traversals;
16  import jwutil.util.Assert;
17  
18  /***
19   * Solver
20   * 
21   * @author John Whaley
22   * @version $Id: Solver.java 2459 2006-05-16 00:47:32Z cunkel $
23   */
24  public abstract class Solver {
25      
26      protected CallGraph cg;
27      protected Map dependents;
28      protected Collection roots;
29      
30      public static final boolean TIMINGS = false;
31      public static final boolean TRACE = false;
32      public static final boolean TRACE_WORKLIST = false;
33      
34      protected boolean bottomUp = true;
35      
36      public abstract boolean visit(jq_Method m, boolean loop);
37      
38      public abstract void dispose(jq_Method m);
39      
40      protected void go() {
41          
42          long time = System.currentTimeMillis();
43          
44          /* Get the predecessor map and build SCCs. */
45          if (TRACE) System.out.print("Building and sorting SCCs...");
46          Navigator navigator = cg.getNavigator();
47          
48          if (bottomUp) {
49              dependents = Traversals.buildPredecessorMap(navigator, roots);
50          }
51          else {
52              dependents = Traversals.buildSuccessorMap(navigator, roots);
53          }
54          
55          Set sccs = SCComponent.buildSCC(roots, navigator);
56          SCCTopSortedGraph graph = SCCTopSortedGraph.topSort(sccs);
57          
58          if (TRACE) System.out.print("done.");
59          
60          if (TIMINGS) System.out.println("Initial setup:\t\t"+(System.currentTimeMillis()-time)/1000.+" seconds.");
61          
62          /* Walk through SCCs in reverse order. */
63          SCComponent scc;
64          if (bottomUp) {
65              scc = graph.getLast();
66          }
67          else {
68              scc = graph.getFirst();
69          }
70          
71          while (scc != null) {
72              /* Visit each method in the SCC. */
73              if (TRACE_WORKLIST) System.out.println("Visiting SCC"+scc.getId()+(scc.isLoop()?" (loop)":" (non-loop)"));
74              Object[] nodes = scc.nodes();
75              boolean change = false;
76              for (int i=0; i<nodes.length; ++i) {
77                  jq_Method m = (jq_Method) nodes[i];
78                  if (visit(m, scc.isLoop())) {
79                      if (TRACE_WORKLIST && scc.isLoop()) System.out.println(m+" changed.");
80                      change = true;
81                  }
82              }
83              if (scc.isLoop() && change) {
84                  if (TRACE_WORKLIST) System.out.println("Loop changed, redoing SCC.");
85                  continue;
86              }
87              /* Finished SCC, remove edges from nodes in this SCC. */
88              if (TRACE_WORKLIST) System.out.println("Finished SCC"+scc.getId());
89              for (int i=0; i<nodes.length; ++i) {
90                  jq_Method m1 = (jq_Method) nodes[i];
91                  for (Iterator j = bottomUp ? navigator.next(m1).iterator()
92                                             : navigator.prev(m1).iterator();
93                       j.hasNext(); ) {
94                      jq_Method m2 = (jq_Method) j.next();
95                      Set ps = (Set) dependents.get(m2);
96                      boolean b = ps.remove(m1);
97                      Assert._assert(b);
98                      if (ps.isEmpty()) {
99                          if (TRACE_WORKLIST) System.out.println(m2+" has no more predecessors, disposing.");
100                         dispose(m2);
101                     } else {
102                         if (TRACE_WORKLIST) System.out.println(m2+" still has "+ps.size()+" predecessors.");
103                     }
104                 }
105             }
106             
107             if (bottomUp) {
108                 scc = scc.prevTopSort();
109             }
110             else {
111                 scc = scc.nextTopSort();
112             }
113         }
114     }
115 }