1 pnkfelix 1.1.2.1 // InstrSolver.java, created Wed Apr 7 22:37:59 1999 by pnkfelix
2 cananian 1.1.2.8 // Copyright (C) 1999 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Analysis.DataFlow;
5 pnkfelix 1.1.2.1
6 pnkfelix 1.1.2.5 import harpoon.Analysis.BasicBlock;
7 cananian 1.1.2.9 import harpoon.Util.Collections.WorkSet;
8 salcianu 1.3 import harpoon.Util.Graphs.SCComponent;
9 salcianu 1.3 import harpoon.Analysis.BasicBlockInterf;
10 pnkfelix 1.1.2.1
11 pnkfelix 1.1.2.3 import java.util.Set;
12 pnkfelix 1.1.2.3 import java.util.Iterator;
13 pnkfelix 1.1.2.3 import java.util.Collections;
14 pnkfelix 1.1.2.1 /**
15 pnkfelix 1.1.2.1 * <code>InstrSolver</code>
16 pnkfelix 1.1.2.1 *
17 cananian 1.1.2.8 * @author Felix S. Klock II <pnkfelix@mit.edu>
18 salcianu 1.5 * @version $Id: InstrSolver.java,v 1.5 2004/03/06 21:51:53 salcianu Exp $
19 pnkfelix 1.1.2.1 */
20 pnkfelix 1.1.2.1 public final class InstrSolver {
21 pnkfelix 1.1.2.1
22 pnkfelix 1.1.2.3 private static final boolean DEBUG = false;
23 pnkfelix 1.1.2.3
24 pnkfelix 1.1.2.1 /** Overriding default constructor to prevent instantiation. */
25 pnkfelix 1.1.2.1 private InstrSolver() {
26 pnkfelix 1.1.2.1
27 pnkfelix 1.1.2.1 }
28 pnkfelix 1.1.2.1
29 pnkfelix 1.1.2.4 /** Performs dataflow analysis on a set of
30 pnkfelix 1.1.2.4 <code>BasicBlock</code>s. Finds a maximum fixed point for the
31 pnkfelix 1.1.2.4 data-flow equations defined by <code>v</code>.
32 pnkfelix 1.1.2.1
33 pnkfelix 1.1.2.3 <BR> <B>requires:</B>
34 pnkfelix 1.1.2.3 <OL>
35 pnkfelix 1.1.2.3 <LI>Every instruction in <code>root</code> and in the
36 pnkfelix 1.1.2.3 <code>BasicBlock</code>s linked to by
37 pnkfelix 1.1.2.3 <code>root</code> is an instance of an
38 pnkfelix 1.1.2.3 <code>Instr</code>.
39 pnkfelix 1.1.2.3 <LI><code>v</code> can visit instructions of type
40 pnkfelix 1.1.2.3 <code>Instr</code>.
41 pnkfelix 1.1.2.3 </OL>
42 pnkfelix 1.1.2.1 <BR> <B>modifies:</B> <code>v</code>
43 pnkfelix 1.1.2.3 <BR> <B>effects:</B>
44 pnkfelix 1.1.2.3 Sends <code>v</code> into <code>root</code> and the
45 pnkfelix 1.1.2.3 <code>BasicBlock</code>s linked to by <code>root</code>,
46 pnkfelix 1.1.2.3 performing <code>v</code>'s transfer function on each
47 pnkfelix 1.1.2.3 <code>BasicBlock</code> in turn, tracking for when no
48 pnkfelix 1.1.2.4 change occurs, at which point the analysis is complete.
49 pnkfelix 1.1.2.6 <BR> <B>NOTE:</B> While this method guarantees that
50 pnkfelix 1.1.2.4 <code>root</code> will be visited by <code>v</code>,
51 pnkfelix 1.1.2.4 there is no guarantee on the number of times, if at all,
52 pnkfelix 1.1.2.4 <code>v</code> will visit the siblings of
53 pnkfelix 1.1.2.4 <code>root</code>, and therefore the analysis may
54 pnkfelix 1.1.2.4 terminate prematurely.
55 pnkfelix 1.1.2.1 */
56 pnkfelix 1.1.2.1 public static void worklistSolver(BasicBlock root, DataFlowBasicBlockVisitor v) {
57 pnkfelix 1.1.2.1 WorkSet w = new WorkSet();
58 pnkfelix 1.1.2.1 w.push(root);
59 pnkfelix 1.1.2.1 while (!w.isEmpty()) {
60 pnkfelix 1.1.2.3 // v.changed = false;
61 salcianu 1.3 BasicBlockInterf b = (BasicBlockInterf) w.pull();
62 pnkfelix 1.1.2.3 if (DEBUG)
63 pnkfelix 1.1.2.3 System.out.println
64 pnkfelix 1.1.2.3 ("Visiting block " + b);
65 pnkfelix 1.1.2.7 b.accept(v);
66 pnkfelix 1.1.2.3 v.addSuccessors(w, b);
67 pnkfelix 1.1.2.3 }
68 pnkfelix 1.1.2.3 }
69 pnkfelix 1.1.2.3
70 pnkfelix 1.1.2.3
71 pnkfelix 1.1.2.4 /** Performs dataflow analysis on a set of
72 pnkfelix 1.1.2.4 <code>BasicBlock</code>s. Finds a maximum fixed point for the
73 pnkfelix 1.1.2.4 data-flow equations defined by <code>v</code>.
74 pnkfelix 1.1.2.3
75 pnkfelix 1.1.2.3 <BR> <B>requires:</B>
76 pnkfelix 1.1.2.4 <OL>
77 pnkfelix 1.1.2.3 <LI> The elements of <code>iter</code> are
78 pnkfelix 1.1.2.3 <code>BasicBlock</code>s.
79 pnkfelix 1.1.2.3 <LI> Every instruction in the elements of
80 pnkfelix 1.1.2.3 <code>iter</code> and in the
81 pnkfelix 1.1.2.3 <code>BasicBlock</code>s linked to by the elements
82 pnkfelix 1.1.2.3 of <code>iter</code> is an instance of an
83 pnkfelix 1.1.2.3 <code>Instr</code>.
84 pnkfelix 1.1.2.3 <LI> <code>v</code> can visit instructions of type
85 pnkfelix 1.1.2.3 <code>Instr</code>.
86 pnkfelix 1.1.2.4 </OL>
87 pnkfelix 1.1.2.3 <BR> <B>modifies:</B> <code>v</code>, <code>iter</code>
88 pnkfelix 1.1.2.3 <BR> <B>effects:</B>
89 pnkfelix 1.1.2.3 Sends <code>v</code> into the elements of
90 pnkfelix 1.1.2.3 <code>iter</code> and the <code>BasicBlock</code>s
91 pnkfelix 1.1.2.3 linked to by the elements of <code>iter</code>,
92 pnkfelix 1.1.2.3 performing <code>v</code>'s transfer function on each
93 pnkfelix 1.1.2.3 <code>BasicBlock</code> in turn, tracking for when no
94 pnkfelix 1.1.2.3 change occurs, at which point the analysis is complete.
95 pnkfelix 1.1.2.4 This method guarantees that all of the
96 pnkfelix 1.1.2.4 <code>BasicBlock</code>s in <code>iter</code> will be
97 pnkfelix 1.1.2.4 visited by <code>v</code> at least once. */
98 pnkfelix 1.1.2.3 public static void worklistSolver(Iterator iter, DataFlowBasicBlockVisitor v) {
99 pnkfelix 1.1.2.3 WorkSet w = new WorkSet();
100 pnkfelix 1.1.2.3 while (iter.hasNext()) w.push(iter.next());
101 pnkfelix 1.1.2.3 while (!w.isEmpty()) {
102 pnkfelix 1.1.2.3 // v.changed = false;
103 salcianu 1.3 BasicBlockInterf b = (BasicBlockInterf) w.pull();
104 pnkfelix 1.1.2.3 if (DEBUG)
105 pnkfelix 1.1.2.3 System.out.println
106 pnkfelix 1.1.2.3 ("Visiting block " + b);
107 pnkfelix 1.1.2.7 b.accept(v);
108 pnkfelix 1.1.2.1 v.addSuccessors(w, b);
109 pnkfelix 1.1.2.1 }
110 salcianu 1.5 }
111 salcianu 1.3
112 salcianu 1.3
113 salcianu 1.3 public static void sccSolver(Iterator it_scc,
114 salcianu 1.3 DataFlowBasicBlockVisitor v) {
115 cananian 1.4 WorkSet w = new WorkSet();
116 salcianu 1.3
117 salcianu 1.3 while(it_scc.hasNext()) {
118 salcianu 1.3 SCComponent scc = (SCComponent) it_scc.next();
119 salcianu 1.3
120 salcianu 1.3 // put all the basic blocks of the current scc in the worklist
121 salcianu 1.5 for(Object bbs : scc.nodes())
122 salcianu 1.5 w.push(bbs);
123 salcianu 1.3
124 salcianu 1.3 // iterate over the current scc to reach the least fixed point
125 salcianu 1.3 while(!w.isEmpty()) {
126 salcianu 1.3 BasicBlockInterf bb = (BasicBlockInterf) w.pull();
127 salcianu 1.3
128 salcianu 1.3 // don't iterate outside scc
129 salcianu 1.3 if(!scc.contains(bb)) continue;
130 salcianu 1.3
131 salcianu 1.3 bb.accept(v);
132 salcianu 1.3 v.addSuccessors(w, bb);
133 salcianu 1.3 }
134 salcianu 1.3
135 salcianu 1.3 }
136 salcianu 1.3
137 salcianu 1.3 }
138 salcianu 1.3
139 cananian 1.2 }