View Javadoc

1   // WorklistSolver.java, created Thu Apr 25 16:32:26 2002 by joewhaley
2   // Copyright (C) 2001-3 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.Compiler.Dataflow;
5   
6   import java.util.Collection;
7   import java.util.Iterator;
8   import jwutil.collections.MapFactory;
9   import jwutil.graphs.Graph;
10  import jwutil.graphs.Navigator;
11  
12  /***
13   * WorklistSolver
14   * 
15   * @author John Whaley
16   * @version $Id: WorklistSolver.java 2298 2005-08-24 01:34:10Z cunkel $
17   */
18  public abstract class WorklistSolver extends Solver {
19  
20      /*** Navigator to navigate the graph of locations. */
21      protected Navigator graphNavigator;
22      /*** The boundary locations. */
23      protected Collection boundaries;
24  
25      protected WorklistSolver(MapFactory f) {
26          super(f);
27      }
28      protected WorklistSolver() {
29          super();
30      }
31  
32      /*** Get the predecessor locations of the given location. */
33      protected Collection getPredecessors(Object c) { return graphNavigator.prev(c); }
34      /*** Get the successor locations of the given location. */
35      protected Collection getSuccessors(Object c) { return graphNavigator.next(c); }
36      
37      /*** (Re-)initialize the worklist. */
38      protected abstract void initializeWorklist();
39      /*** Returns true if the worklist is not empty, false otherwise. */
40      protected abstract boolean hasNext();
41      /*** Pull the next location off of the worklist. */
42      protected abstract Object pull();
43      /*** Push all of the given locations onto the worklist. */
44      protected abstract void pushAll(Collection c);
45  
46      /* (non-Javadoc)
47       * @see joeq.Compiler.Dataflow.Solver#boundaryLocations()
48       */
49      public Iterator boundaryLocations() {
50          return boundaries.iterator();
51      }
52      
53      /* (non-Javadoc)
54       * @see joeq.Compiler.Dataflow.Solver#initialize(joeq.Compiler.Dataflow.Problem, Util.Graphs.Graph)
55       */
56      public void initialize(Problem p, Graph graph) {
57          super.initialize(p, graph);
58          graphNavigator = graph.getNavigator();
59          boundaries = graph.getRoots();
60      }
61  
62      /* (non-Javadoc)
63       * @see joeq.Compiler.Dataflow.Solver#solve()
64       */
65      public void solve() {
66          initializeDataflowValueMap();
67          initializeWorklist();
68          while (hasNext()) {
69              Object c = pull();
70              if (TRACE) System.out.println("Node "+c);
71              Iterator j = getPredecessors(c).iterator();
72              Object p = j.next();
73              if (TRACE) System.out.println("   Predecessor "+p);
74              Fact in = (Fact) dataflowValues.get(p);
75              while (j.hasNext()) {
76                  p = j.next();
77                  if (TRACE) System.out.println("   Predecessor "+p);
78                  Fact in2 = (Fact) dataflowValues.get(p);
79                  in = problem.merge(in, in2);
80              }
81              TransferFunction tf = problem.getTransferFunction(c);
82              Fact out = problem.apply(tf, in);
83              Fact old = (Fact) dataflowValues.put(c, out);
84              if (!problem.compare(old, out)) {
85                  if (TRACE) {
86                      System.out.println("Changed!");
87                      System.out.println("Old: "+old);
88                      System.out.println("Out: "+out);
89                  }
90                  
91                  Collection next = getSuccessors(c);
92                  pushAll(next);
93              }
94          }
95      }
96  
97  }