View Javadoc

1   // IterativeSolver.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 java.util.List;
9   import jwutil.collections.MapFactory;
10  import jwutil.graphs.Graph;
11  import jwutil.graphs.Navigator;
12  import jwutil.graphs.Traversals;
13  import jwutil.strings.Strings;
14  import jwutil.util.Assert;
15  
16  /***
17   * Solves a dataflow problem using a iterative technique.  Successively
18   * iterates over the locations in the graph in a given order until there
19   * are no more changes.
20   * 
21   * @author John Whaley
22   * @version $Id: IterativeSolver.java 1931 2004-09-22 22:17:47Z joewhaley $
23   */
24  public class IterativeSolver
25      extends Solver
26  {
27      /*** The order in which the locations are to be traversed. */
28      protected List traversalOrder;
29      /*** The boundary locations. */
30      protected Collection boundaries;
31      /*** Navigator to navigate the graph of locations. */
32      protected Navigator graphNavigator;
33      /*** Change flag, set to true if we need to iterate more times. */
34      protected boolean change;
35  
36      public IterativeSolver(MapFactory f) {
37          super(f);
38      }
39      public IterativeSolver() {
40          super();
41      }
42  
43      /*** Returns an iteration of the order in which the locations are to be traversed. */
44      protected Iterator getTraversalOrder() { return traversalOrder.iterator(); }
45      
46      /*** Get the predecessor locations of the given location. */
47      protected Collection getPredecessors(Object c) { return graphNavigator.prev(c); }
48      /*** Get the successor locations of the given location. */
49      protected Collection getSuccessors(Object c) { return graphNavigator.next(c); }
50      
51      /* (non-Javadoc)
52       * @see joeq.Compiler.Dataflow.Solver#initialize(Compiler.Dataflow.Problem, Util.Graphs.Graph)
53       */
54      public void initialize(Problem p, Graph graph) {
55          List order = Traversals.reversePostOrder(graph.getNavigator(), graph.getRoots());
56          this.initialize(p, graph, order);
57      }
58      
59      /***
60       * Initializes this solver with the given dataflow problem, graph, and
61       * traversal order.
62       * 
63       * @see joeq.Compiler.Dataflow.Solver#initialize(joeq.Compiler.Dataflow.Problem, jwutil.graphs.Graph)
64       */
65      public void initialize(Problem p, Graph graph, List order) {
66          super.initialize(p, graph);
67          graphNavigator = graph.getNavigator();
68          boundaries = graph.getRoots();
69          traversalOrder = order;
70          if (TRACE) System.out.println("Traversal order: "+traversalOrder);
71      }
72      
73      /* (non-Javadoc)
74       * @see joeq.Compiler.Dataflow.Solver#allLocations()
75       */
76      public Iterator allLocations() { return traversalOrder.iterator(); }
77  
78      /* (non-Javadoc)
79       * @see joeq.Compiler.Dataflow.Solver#boundaryLocations()
80       */
81      public Iterator boundaryLocations() { return boundaries.iterator(); }
82  
83      /* (non-Javadoc)
84       * @see joeq.Compiler.Dataflow.Solver#solve()
85       */
86      public void solve() {
87          initializeDataflowValueMap();
88          int iterationCount = 0;
89          do {
90              change = false; if (TRACE) ++iterationCount;
91              Iterator i = getTraversalOrder();
92              Object o = i.next(); // skip boundary node.
93              Assert._assert(boundaries.contains(o));
94              while (i.hasNext()) {
95                  Object c = i.next();
96                  if (TRACE) System.out.println("Node "+c);
97                  Iterator j = getPredecessors(c).iterator();
98                  Object p = j.next();
99                  if (TRACE) System.out.println("  Predecessor "+p);
100                 Fact in = (Fact) dataflowValues.get(p);
101                 while (j.hasNext()) {
102                     p = j.next();
103                     if (TRACE) System.out.println("  Predecessor "+p);
104                     Fact in2 = (Fact) dataflowValues.get(p);
105                     in = problem.merge(in, in2);
106                 }
107                 if (TRACE) System.out.println(" In set: "+in);
108                 TransferFunction tf = problem.getTransferFunction(c);
109                 if (TRACE) System.out.println(" Transfer function:"+Strings.lineSep+tf);
110                 Fact out = problem.apply(tf, in);
111                 if (TRACE) System.out.println(" Out set: "+out);
112                 Fact old = (Fact) dataflowValues.put(c, out);
113                 if (!change && !problem.compare(old, out)) {
114                     change = true;
115                     if (TRACE) System.out.println("Changed occurred!");
116                 }
117             }
118         } while (change);
119         if (TRACE) System.out.println("Number of iterations: "+iterationCount);
120     }
121 
122 }