1
2
3
4 package net.sf.bddbddb.dataflow;
5
6 import java.util.HashMap;
7 import java.util.Iterator;
8 import java.util.ListIterator;
9 import java.util.Map;
10 import jwutil.util.Assert;
11 import net.sf.bddbddb.IterationFlowGraph;
12 import net.sf.bddbddb.IterationList;
13 import net.sf.bddbddb.dataflow.Problem.Fact;
14 import net.sf.bddbddb.dataflow.Problem.TransferFunction;
15 import net.sf.bddbddb.ir.Operation;
16 import net.sf.bddbddb.ir.dynamic.If;
17
18 /***
19 * DataflowSolver
20 *
21 * @author John Whaley
22 * @version $Id: DataflowSolver.java 328 2004-10-16 02:45:30Z joewhaley $
23 */
24 public class DataflowSolver {
25 boolean TRACE = false;
26 boolean WORKLIST = false;
27
28 /*** Matches blocks to their dataflow information. */
29 Map
30
31 public DataflowSolver() {
32 blockToFact = new HashMap();
33 }
34
35 /*** Resets dataflow information. */
36 public void reset() {
37 blockToFact.clear();
38 }
39
40 /*** Returns the dataflow information for a given block. */
41 public Fact getFact(IterationList block) {
42 return (Fact) blockToFact.get(block);
43 }
44
45 public DataflowIterator getIterator(Problem p, IterationFlowGraph g) {
46 IterationList block = g.getIterationList();
47 Fact f = getFact(block);
48 if (f == null) {
49 f = p.getBoundary();
50 f.setLocation(block);
51 }
52 return new DataflowIterator(p, f, block);
53 }
54 public class DataflowIterator implements ListIterator {
55 Problem p;
56 Fact fact;
57 IterationList block;
58 ListIterator ops;
59 DataflowIterator nested;
60
61
62
63
64
65 public DataflowIterator(Problem p, Fact startingFact, IterationList block) {
66 this.p = p;
67 this.fact = startingFact;
68 this.block = block;
69 this.ops = block.iterator();
70 }
71
72 public Fact getFact() {
73 if (nested != null) return nested.getFact();
74 return fact;
75 }
76
77
78
79
80
81
82 public boolean hasNext() {
83 if (nested != null && nested.hasNext()) return true;
84 return ops.hasNext();
85 }
86
87 public boolean hasPrevious() {
88 throw new UnsupportedOperationException();
89 }
90
91 public Object next() {
92 if (nested != null) {
93 if (!nested.hasNext()) {
94 if (TRACE) System.out.println("Exiting " + nested.block);
95 nested = null;
96 } else {
97 return nested.next();
98 }
99 }
100 Object o = ops.next();
101 if (o instanceof Operation) {
102 Operation op = (Operation) o;
103 TransferFunction tf = p.getTransferFunction(op);
104 fact = tf.apply(fact);
105 } else {
106 IterationList list = (IterationList) o;
107 Fact f = (Fact) blockToFact.get(list);
108 if (f != null) fact = f;
109 }
110 return o;
111 }
112
113 public Object previous() {
114 throw new UnsupportedOperationException();
115 }
116
117 public int nextIndex() {
118 throw new UnsupportedOperationException();
119 }
120
121 public int previousIndex() {
122 throw new UnsupportedOperationException();
123 }
124
125 public void enter(IterationList list) {
126 if (nested != null) nested.enter(list);
127 else {
128 if (TRACE) System.out.println("Entering " + list);
129 Fact f = (Fact) blockToFact.get(list);
130 if (f == null) {
131 f = fact.copy(list);
132 }
133 nested = new DataflowIterator(p, f, list);
134 }
135 }
136
137
138
139
140
141
142 public void remove() {
143 if (nested != null) nested.remove();
144 else ops.remove();
145 }
146
147 public void set(Object o) {
148 if (nested != null) nested.set(o);
149 else ops.set(o);
150 }
151
152 public void add(Object o) {
153 if (nested != null) nested.add(o);
154 else ops.add(o);
155 }
156 }
157
158 boolean again;
159
160 public void solve(Problem p, IterationList g) {
161 do {
162 Fact startFact;
163 startFact = (Fact) blockToFact.get(g);
164 if (startFact == null) {
165 startFact = p.getBoundary();
166 startFact.setLocation(g);
167
168 }
169 again = false;
170 if (TRACE) System.out.println("Main iteration! Start fact: "+System.identityHashCode(startFact));
171 solve2(startFact, p, g);
172 } while (again);
173 }
174
175 Fact solve2(Fact currentFact, Problem p, IterationList g) {
176 Assert._assert(currentFact.getLocation() == g);
177 if (g.isLoop()) {
178 Fact startFact = (Fact) blockToFact.get(g);
179 if (startFact == null) {
180 if (TRACE) System.out.println("Caching dataflow value at entry " + g);
181 blockToFact.put(g, startFact = currentFact.copy(g));
182 } else {
183 if (TRACE) System.out.println("Joining dataflow value at entry " + g);
184 Assert._assert(startFact.getLocation() == g);
185 Fact joinResult = startFact.join(currentFact);
186 Assert._assert(joinResult.getLocation() == g);
187 blockToFact.put(g, joinResult);
188 currentFact = joinResult.copy(g);
189 }
190 if (TRACE) System.out.println("At start of "+g+", we cached fact " + System.identityHashCode(blockToFact.get(g)));
191 } else {
192 if (TRACE) System.out.println(g+" is not a loop, incoming fact " + System.identityHashCode(currentFact));
193 currentFact = currentFact.copy(g);
194 }
195 if (TRACE) System.out.println("Using fact "+System.identityHashCode(currentFact)+" to iterate through "+g);
196 for (;;) {
197 for (Iterator i = p.direction() ? g.iterator() : g.reverseIterator(); i.hasNext();) {
198 Object o = i.next();
199 if (o instanceof IterationList || o instanceof If) {
200 IterationList list = null;
201 Fact preIfFact = null;
202 if (o instanceof If) {
203 if (p.direction()) {
204 TransferFunction tf = p.getTransferFunction((Operation) o);
205 currentFact = tf.apply(currentFact);
206 }
207 preIfFact = currentFact.copy(g);
208 list = ((If) o).getBlock();
209 } else {
210 list = (IterationList) o;
211 }
212 if (TRACE) System.out.println("Entering " + list + " with fact "+System.identityHashCode(currentFact));
213 currentFact.setLocation(list);
214 currentFact = solve2(currentFact, p, list);
215 currentFact.setLocation(g);
216 if (TRACE) System.out.println("Leaving " + list + ", current fact "+System.identityHashCode(currentFact));
217 if (o instanceof If) {
218 currentFact = preIfFact.join(currentFact);
219 if (!p.direction()) {
220 TransferFunction tf = p.getTransferFunction((Operation) o);
221 currentFact = tf.apply(currentFact);
222 }
223 }
224 } else {
225 Operation op = (Operation) o;
226 if (TRACE) System.out.println(" Operation: " + op);
227 TransferFunction tf = p.getTransferFunction(op);
228 currentFact = tf.apply(currentFact);
229 }
230 }
231 if (TRACE) System.out.println("Finished walking through "+g+", current fact is now "+System.identityHashCode(currentFact));
232 if (!g.isLoop()) break;
233 Fact blockFact = currentFact;
234 currentFact.setLocation(g.getLoopEdge());
235 Fact loopEdgeFact = solve2(currentFact, p, g.getLoopEdge());
236 loopEdgeFact.setLocation(g);
237 currentFact.setLocation(g);
238 if (TRACE) System.out.println("Loop edge fact: "+System.identityHashCode(loopEdgeFact));
239 Fact startFact = (Fact) blockToFact.get(g);
240 if (TRACE) System.out.println("Fact that was cached at start of "+g+": " + System.identityHashCode(startFact));
241 Assert._assert(startFact.getLocation() == g, startFact.getLocation()+" != "+g);
242 Fact joinResult = startFact.join(loopEdgeFact);
243 if (TRACE) System.out.println("Result: " + joinResult);
244 Assert._assert(joinResult.getLocation() == g);
245 if (joinResult.equals(startFact)) {
246 if (TRACE) System.out.println("No change after join, exiting.");
247 currentFact = blockFact;
248 break;
249 }
250 if (TRACE) System.out.println(g + " changed, iterating again...");
251 if (TRACE) System.out.println("Caching join result for "+g+": " + System.identityHashCode(joinResult));
252 blockToFact.put(g, joinResult);
253 currentFact = joinResult.copy(g);
254 if (TRACE) System.out.println("Current fact at end of "+g+": " + System.identityHashCode(currentFact));
255 if (!WORKLIST) {
256 again = true;
257 break;
258 }
259 }
260 if (TRACE) System.out.println("Returning current fact from "+g+": " + System.identityHashCode(currentFact));
261 return currentFact;
262 }
263 }