1
2
3
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
52
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
74
75
76 public Iterator allLocations() { return traversalOrder.iterator(); }
77
78
79
80
81 public Iterator boundaryLocations() { return boundaries.iterator(); }
82
83
84
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();
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 }