1
2
3
4 package joeq.Compiler.Dataflow;
5
6 import java.util.Iterator;
7 import java.util.Map;
8 import jwutil.collections.MapFactory;
9 import jwutil.graphs.Graph;
10 import jwutil.graphs.Traversals;
11
12 /***
13 * Solver
14 *
15 * @author John Whaley
16 * @version $Id: Solver.java 1931 2004-09-22 22:17:47Z joewhaley $
17 */
18 public abstract class Solver {
19
20 static final boolean TRACE = false;
21
22 /*** The dataflow problem to solve. */
23 protected Problem problem;
24 /*** Map factory to create map from locations to dataflow values. */
25 protected final MapFactory factory;
26 /*** Map from locations to dataflow values. */
27 protected Map dataflowValues;
28
29 protected Solver(MapFactory factory) {
30 this.factory = factory;
31 }
32 protected Solver() {
33 this(MapFactory.hashMapFactory);
34 }
35
36 /*** Returns the direction of the dataflow problem that we are solving. */
37 public boolean direction() { return problem.direction(); }
38
39 /*** Returns an iteration of all graph locations. */
40 public abstract Iterator allLocations();
41 /*** Returns an iteration of all boundary locations. */
42 public abstract Iterator boundaryLocations();
43
44 /*** Initializes the solver to prepare to solve the dataflow
45 * problem on the given graph.
46 */
47 public void initialize(Problem p, Graph graph) {
48 this.problem = p;
49 p.initialize(graph);
50 }
51
52 /*** Solves this dataflow problem. */
53 public abstract void solve();
54
55 /*** Frees the memory associated with this solver. */
56 public void reset() {
57 this.dataflowValues = null;
58 }
59
60 /*** (Re-)initialize the map from locations to dataflow values. */
61 protected void initializeDataflowValueMap() {
62 dataflowValues = factory.makeMap();
63 for (Iterator i = allLocations(); i.hasNext(); ) {
64 Object c = i.next();
65 dataflowValues.put(c, problem.interior());
66 }
67 for (Iterator i = boundaryLocations(); i.hasNext(); ) {
68 Object c = i.next();
69 dataflowValues.put(c, problem.boundary());
70 }
71 }
72
73 /*** Get the dataflow value associated with the given location. */
74 public Fact getDataflowValue(Object c) {
75 return (Fact) dataflowValues.get(c);
76 }
77
78 public static void dumpResults(Graph g, Solver s) {
79 System.out.println("RESULTS");
80 for (Iterator i = Traversals.reversePostOrder(g.getNavigator(), g.getRoots()).iterator(); i.hasNext(); ) {
81 Object bb = i.next();
82 Fact r = s.getDataflowValue(bb);
83 System.out.println(bb+": "+r);
84 }
85 }
86
87 public static void compareResults(Graph g, Solver s1, Solver s2) {
88 for (Iterator i = Traversals.reversePostOrder(g.getNavigator(), g.getRoots()).iterator(); i.hasNext(); ) {
89 Object bb = i.next();
90 Fact r1 = s1.getDataflowValue(bb);
91 Fact r2 = s2.getDataflowValue(bb);
92 if (!r1.equals(r2)) {
93 System.out.println("MISMATCH");
94 System.out.println(s1.getClass()+" says "+r1);
95 System.out.println(s2.getClass()+" says "+r2);
96 }
97 }
98 }
99
100 }