1 pnkfelix 1.1.2.4 // Solver.java, created Mon Nov 8 22:52:13 1999 by pnkfelix
2 pnkfelix 1.1.2.4 // Copyright (C) 1999 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.4 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 jwhaley 1.1.2.1 package harpoon.Analysis.DataFlow;
5 jwhaley 1.1.2.1
6 pnkfelix 1.1.2.4 import harpoon.Analysis.BasicBlock;
7 duncan 1.1.2.5 import harpoon.Analysis.DataFlow.ReversePostOrderEnumerator;
8 cananian 1.3 import net.cscott.jutil.WorkSet;
9 jwhaley 1.1.2.1
10 duncan 1.1.2.5
11 duncan 1.1.2.5 import java.util.Enumeration;
12 pnkfelix 1.1.2.4 import java.util.Iterator;
13 jwhaley 1.1.2.1
14 pnkfelix 1.1.2.4 /**
15 pnkfelix 1.1.2.4 * <code>Solver</code> contains static methods to find the fixed point
16 pnkfelix 1.1.2.4 * of a set of data-flow equations. It is a generalization of the
17 pnkfelix 1.1.2.4 * <code>QuadSolver</code> and <code>InstrSolver</code> that is
18 pnkfelix 1.1.2.4 * intended for general usage on any Intermediate Representation that
19 pnkfelix 1.1.2.4 * is amicable to data-flow analysis.
20 pnkfelix 1.1.2.4 *
21 pnkfelix 1.1.2.4 * @author Felix S. Klock II <pnkfelix@mit.edu>
22 cananian 1.3 * @version $Id: Solver.java,v 1.3 2004/02/08 01:51:05 cananian Exp $
23 pnkfelix 1.1.2.4 */
24 pnkfelix 1.1.2.4 public class Solver {
25 jwhaley 1.1.2.1
26 pnkfelix 1.1.2.4 private static boolean DEBUG = false;
27 pnkfelix 1.1.2.4 private static void db(String s) { if(DEBUG)System.out.println(s); }
28 pnkfelix 1.1.2.7 static final boolean TIME = false;
29 jwhaley 1.1.2.1
30 pnkfelix 1.1.2.4 /** Creates a <code>Solver</code>. Ctor is made private so that
31 pnkfelix 1.1.2.4 there won't be any instances of Solvers running around. */
32 pnkfelix 1.1.2.4 private Solver() {
33 pnkfelix 1.1.2.4
34 jwhaley 1.1.2.1 }
35 pnkfelix 1.1.2.4
36 pnkfelix 1.1.2.4 /** Performs dataflow analysis on a set of
37 pnkfelix 1.1.2.4 <code>BasicBlock</code>s. Finds the maximum fixed point for
38 pnkfelix 1.1.2.4 the data-flow equations defined by <code>v</code>.
39 pnkfelix 1.1.2.4
40 pnkfelix 1.1.2.7 FSK: it seems to me that the <code>blocks</code> are added to
41 pnkfelix 1.1.2.7 a stack and then popped off for visitation, which means
42 pnkfelix 1.1.2.7 that if you want to visit the blocks in say Reverse
43 pnkfelix 1.1.2.7 Postorder, then <code>blocks</code> must iterate over
44 pnkfelix 1.1.2.7 them in *Normal* Postorder. This seems viciously
45 pnkfelix 1.1.2.7 unintuitive... perhaps the Solver interface should be
46 pnkfelix 1.1.2.7 revised to offer more control over the traversal... (on
47 pnkfelix 1.1.2.7 the other hand, the current implementation doesn't seem
48 pnkfelix 1.1.2.7 to be performing that shabbily to me, so perhaps is
49 pnkfelix 1.1.2.7 better to leave well enough alone...)
50 pnkfelix 1.1.2.7
51 pnkfelix 1.1.2.4 <BR> <B>requires:</B> <OL>
52 pnkfelix 1.1.2.4 <LI> The elements of <code>blocks</code> are
53 pnkfelix 1.1.2.4 <code>BasicBlock</code>s.
54 pnkfelix 1.1.2.4 <LI> <code>v</code> can safely visit the elements of
55 pnkfelix 1.1.2.4 <code>blocks</code>.
56 pnkfelix 1.1.2.4 </OL>
57 pnkfelix 1.1.2.4 <BR> <B>modifies:</B> <code>v</code>, <code>blocks</code>
58 pnkfelix 1.1.2.4 <BR> <B>effects:</B>
59 pnkfelix 1.1.2.4 Sends <code>v</code> into the elements of
60 pnkfelix 1.1.2.4 <code>blocks</code> and the 'successors' of the elements
61 pnkfelix 1.1.2.4 of <code>blocks</code> (where 'successors' is defined by
62 pnkfelix 1.1.2.4 <code>v</code>'s addSuccessors() method).
63 pnkfelix 1.1.2.4 On each visitation, performs <code>v</code>'s transfer
64 pnkfelix 1.1.2.4 function on each <code>BasicBlock</code> in turn,
65 pnkfelix 1.1.2.4 tracking for when no change occurs to the 'successors',
66 pnkfelix 1.1.2.4 at which point analysis is complete.
67 pnkfelix 1.1.2.4 This method guarantees that all of the
68 pnkfelix 1.1.2.4 <code>BasicBlock</code>s. in <code>blocks</code> will be
69 pnkfelix 1.1.2.4 visited by <code>v</code> at least once.
70 pnkfelix 1.1.2.4 */
71 pnkfelix 1.1.2.4 public static void worklistSolve(Iterator blocks,
72 pnkfelix 1.1.2.4 DataFlowBasicBlockVisitor v) {
73 pnkfelix 1.1.2.4 WorkSet w = new WorkSet();
74 pnkfelix 1.1.2.7 int total = 0;
75 pnkfelix 1.1.2.7 int count = 0;
76 pnkfelix 1.1.2.7 while (blocks.hasNext()) {
77 pnkfelix 1.1.2.7 w.push(blocks.next());
78 pnkfelix 1.1.2.7 total++;
79 pnkfelix 1.1.2.7 }
80 pnkfelix 1.1.2.4 while (!w.isEmpty()) {
81 pnkfelix 1.1.2.4 // v.changed = false;
82 cananian 1.3 BasicBlock b = (BasicBlock) w.removeLast();
83 pnkfelix 1.1.2.7 if (TIME) count++;
84 pnkfelix 1.1.2.4 if (DEBUG)
85 pnkfelix 1.1.2.4 System.out.println
86 pnkfelix 1.1.2.4 ("Visiting block " + b);
87 pnkfelix 1.1.2.6 b.accept(v);
88 pnkfelix 1.1.2.4 v.addSuccessors(w, b);
89 jwhaley 1.1.2.1 }
90 pnkfelix 1.1.2.7 if (TIME) System.out.print("(s:"+count+"/"+total+")");
91 pnkfelix 1.1.2.7
92 duncan 1.1.2.5 }
93 duncan 1.1.2.5
94 duncan 1.1.2.5 public static void forwardRPOSolve(BasicBlock root,
95 duncan 1.1.2.5 DataFlowBasicBlockVisitor v) {
96 duncan 1.1.2.5 ReversePostOrderEnumerator rpo = new ReversePostOrderEnumerator(root);
97 duncan 1.1.2.5 boolean changed = false;
98 duncan 1.1.2.5 do {
99 duncan 1.1.2.5 changed = false;
100 duncan 1.1.2.5
101 duncan 1.1.2.5 ReversePostOrderEnumerator iter = rpo.copy();
102 duncan 1.1.2.5 while (iter.hasMoreElements()) {
103 duncan 1.1.2.5 BasicBlock q = (BasicBlock)iter.next();
104 duncan 1.1.2.5 if (DEBUG) db("visiting: "+q);
105 pnkfelix 1.1.2.6 q.accept(v);
106 duncan 1.1.2.5 for (Enumeration e=q.next(); e.hasMoreElements(); ) {
107 duncan 1.1.2.5 BasicBlock qn = (BasicBlock)e.nextElement();
108 duncan 1.1.2.5 if (DEBUG) db("doing edge "+q+" -> "+qn);
109 duncan 1.1.2.5 changed = v.merge(q, qn);
110 duncan 1.1.2.5 }
111 duncan 1.1.2.5 }
112 jwhaley 1.1.2.1
113 duncan 1.1.2.5 } while (changed);
114 jwhaley 1.1.2.1 }
115 pnkfelix 1.1.2.2
116 cananian 1.2 }