001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.opt.dfsolver;
014
015 import java.util.Comparator;
016 import java.util.Enumeration;
017 import java.util.HashSet;
018 import java.util.Iterator;
019 import java.util.TreeSet;
020
021 import org.jikesrvm.compilers.opt.util.FilterEnumerator;
022 import org.jikesrvm.compilers.opt.util.Graph;
023 import org.jikesrvm.compilers.opt.util.GraphNode;
024 import org.jikesrvm.compilers.opt.util.GraphNodeEnumeration;
025 import org.jikesrvm.compilers.opt.util.GraphUtilities;
026 import org.jikesrvm.compilers.opt.util.ReverseDFSenumerateByFinish;
027
028 /**
029 * Represents a system of Data Flow equations
030 *
031 * <p> Implementation Note:
032 * The set of equations is internally represented as a graph
033 * (actually a SpaceEffGraph). Each dataflow equation is a node in the
034 * graph. If a dataflow equation produces a lattice cell value
035 * that is used by another equation, the graph has a directed edge
036 * from the producer to the consumer. Fixed-point iteration proceeds
037 * in a topological order according to these edges.
038 */
039 public abstract class DF_System {
040 private static final boolean DEBUG = false;
041
042 private final boolean EAGER;
043
044 /**
045 * The equations that comprise this dataflow system.
046 */
047 private final Graph equations = new DF_Graph();
048
049 /**
050 * Set of equations pending evaluation
051 */
052 protected final TreeSet<DF_Equation> workList = new TreeSet<DF_Equation>(dfComparator);
053
054 /**
055 * Set of equations considered "new"
056 */
057 private final HashSet<DF_Equation> newEquations = new HashSet<DF_Equation>();
058
059 /**
060 * The lattice cells of the system: Mapping from Object to DF_LatticeCell
061 */
062 protected final DF_Solution cells = new DF_Solution();
063
064 public DF_System() {
065 EAGER = false;
066 }
067
068 public DF_System(boolean eager) {
069 EAGER = eager;
070 }
071
072 /**
073 * Solve the set of dataflow equations.
074 * <p> PRECONDITION: equations are set up
075 */
076 public void solve() {
077 // addGraphEdges();
078 numberEquationsTopological();
079 initializeLatticeCells();
080 initializeWorkList();
081 while (!workList.isEmpty()) {
082 DF_Equation eq = workList.first();
083 workList.remove(eq);
084 boolean change = eq.evaluate();
085 if (DEBUG) {
086 System.out.println("After evaluation " + eq);
087 }
088 if (change) {
089 updateWorkList(eq);
090 }
091 }
092 }
093
094 /**
095 * Return the solution of the dataflow equation system.
096 * This is only valid after calling solve()
097 *
098 * @return the solution
099 */
100 public DF_Solution getSolution() {
101 return cells;
102 }
103
104 /**
105 * Return a string representation of the system
106 * @return a string representation of the system
107 */
108 public String toString() {
109 String result = "EQUATIONS:\n";
110 Enumeration<GraphNode> v = equations.enumerateNodes();
111 for (int i = 0; i < equations.numberOfNodes(); i++) {
112 result = result + i + " : " + v.nextElement() + "\n";
113 }
114 return result;
115 }
116
117 /**
118 * Return an Enumeration over the equations in this system.
119 * @return an Enumeration over the equations in this system
120 */
121 public Enumeration<DF_Equation> getEquations() {
122 return new FilterEnumerator<GraphNode, DF_Equation>(equations.enumerateNodes(),
123 new FilterEnumerator.Filter<GraphNode, DF_Equation>() {
124 public boolean isElement(GraphNode x) {
125 return x instanceof DF_Equation;
126 }
127 });
128 }
129
130 /**
131 * Get the number of equations in this system
132 * @return the number of equations in this system
133 */
134 public int getNumberOfEquations() {
135 return equations.numberOfNodes();
136 }
137
138 /**
139 * Add an equation to the work list.
140 * @param eq the equation to add
141 */
142 public void addToWorkList(DF_Equation eq) {
143 workList.add(eq);
144 }
145
146 /**
147 * Add all new equations to the work list.
148 */
149 public void addNewEquationsToWorkList() {
150 if (DEBUG) {
151 System.out.println("new equations:");
152 }
153 for (DF_Equation eq : newEquations) {
154 if (DEBUG) {
155 System.out.println(eq.toString());
156 }
157 addToWorkList(eq);
158 }
159 newEquations.clear();
160 if (DEBUG) {
161 System.out.println("end of new equations");
162 }
163 }
164
165 /**
166 * Add all equations to the work list.
167 */
168 public void addAllEquationsToWorkList() {
169 for (Enumeration<DF_Equation> e = getEquations(); e.hasMoreElements();) {
170 DF_Equation eq = e.nextElement();
171 addToWorkList(eq);
172 }
173 }
174
175 /**
176 * Call this method when the contents of a lattice cell
177 * changes. This routine adds all equations using this cell
178 * to the set of new equations.
179 * @param cell the lattice cell that has changed
180 */
181 public void changedCell(DF_LatticeCell cell) {
182 Iterator<DF_Equation> e = cell.getUses();
183 while (e.hasNext()) {
184 newEquations.add(e.next());
185 }
186 }
187
188 /**
189 * Find the cell matching this key. If none found, create one.
190 *
191 * @param key the key for the lattice cell.
192 */
193 protected DF_LatticeCell findOrCreateCell(Object key) {
194 DF_LatticeCell result = cells.get(key);
195 if (result == null) {
196 result = makeCell(key);
197 cells.put(key, result);
198 }
199 return result;
200 }
201
202 /**
203 * Add an equation with one operand on the right-hand side.
204 *
205 * @param lhs the lattice cell set by this equation
206 * @param operator the equation operator
207 * @param op1 first operand on the rhs
208 */
209 protected void newEquation(DF_LatticeCell lhs, DF_Operator operator, DF_LatticeCell op1) {
210 // add to the list of equations
211 DF_Equation eq = new DF_Equation(lhs, operator, op1);
212 equations.addGraphNode(eq);
213 equations.addGraphNode(lhs);
214 equations.addGraphNode(op1);
215 newEquations.add(eq);
216 // add lattice cells for the operands to the working solution
217 // cells.put(lhs.getKey(),lhs);
218 // cells.put(op1.getKey(),op1);
219 op1.addUse(eq);
220 lhs.addDef(eq);
221 if (EAGER && eq.evaluate()) changedCell(lhs);
222 }
223
224 /**
225 * Add an equation with two operands on the right-hand side.
226 *
227 * @param lhs the lattice cell set by this equation
228 * @param operator the equation operator
229 * @param op1 first operand on the rhs
230 * @param op2 second operand on the rhs
231 */
232 void newEquation(DF_LatticeCell lhs, DF_Operator operator, DF_LatticeCell op1, DF_LatticeCell op2) {
233 // add to the list of equations
234 DF_Equation eq = new DF_Equation(lhs, operator, op1, op2);
235 equations.addGraphNode(eq);
236 equations.addGraphNode(lhs);
237 equations.addGraphNode(op1);
238 equations.addGraphNode(op2);
239 newEquations.add(eq);
240 // add lattice cells for the operands to the working solution
241 // cells.put(lhs.getKey(),lhs);
242 // cells.put(op1.getKey(),op1);
243 op1.addUse(eq);
244 // cells.put(op2.getKey(),op2);
245 op2.addUse(eq);
246 lhs.addDef(eq);
247 if (EAGER && eq.evaluate()) changedCell(lhs);
248 }
249
250 /**
251 * Add an equation with three operands on the right-hand side.
252 *
253 * @param lhs the lattice cell set by this equation
254 * @param operator the equation operator
255 * @param op1 first operand on the rhs
256 * @param op2 second operand on the rhs
257 * @param op3 third operand on the rhs
258 */
259 void newEquation(DF_LatticeCell lhs, DF_Operator operator, DF_LatticeCell op1, DF_LatticeCell op2,
260 DF_LatticeCell op3) {
261 // add to the list of equations
262 DF_Equation eq = new DF_Equation(lhs, operator, op1, op2, op3);
263 equations.addGraphNode(eq);
264 equations.addGraphNode(lhs);
265 equations.addGraphNode(op1);
266 equations.addGraphNode(op2);
267 equations.addGraphNode(op3);
268 newEquations.add(eq);
269 // add lattice cells for the operands to the working solution
270 // cells.put(lhs.getKey(),lhs);
271 // cells.put(op1.getKey(),op1);
272 op1.addUse(eq);
273 // cells.put(op2.getKey(),op2);
274 op2.addUse(eq);
275 // cells.put(op3.getKey(),op3);
276 op3.addUse(eq);
277 lhs.addDef(eq);
278 if (EAGER && eq.evaluate()) changedCell(lhs);
279 }
280
281 /**
282 * Add an equation to the system with an arbitrary number of operands on
283 * the right-hand side.
284 *
285 * @param lhs lattice cell set by this equation
286 * @param operator the equation operator
287 * @param rhs the operands on the rhs
288 */
289 protected void newEquation(DF_LatticeCell lhs, DF_Operator operator, DF_LatticeCell[] rhs) {
290 // add to the list of equations
291 DF_Equation eq = new DF_Equation(lhs, operator, rhs);
292 equations.addGraphNode(eq);
293 equations.addGraphNode(lhs);
294 newEquations.add(eq);
295 // add the operands to the working solution
296 // cells.put(lhs.getKey(),lhs);
297 for (DF_LatticeCell rh : rhs) {
298 // cells.put(rhs[i].getKey(),rhs[i]);
299 rh.addUse(eq);
300 equations.addGraphNode(rh);
301 }
302 lhs.addDef(eq);
303 if (EAGER && eq.evaluate()) changedCell(lhs);
304 }
305
306 /**
307 * Add an existing equation to the system
308 *
309 * @param eq the equation
310 */
311 void addEquation(DF_Equation eq) {
312 equations.addGraphNode(eq);
313 newEquations.add(eq);
314
315 DF_LatticeCell lhs = eq.getLHS();
316 if (!(lhs.getDefs().hasNext() || lhs.getUses().hasNext())) {
317 lhs.addDef(eq);
318 equations.addGraphNode(lhs);
319 } else {
320 lhs.addDef(eq);
321 }
322
323 DF_LatticeCell[] operands = eq.getOperands();
324 for (int i = 1; i < operands.length; i++) {
325 DF_LatticeCell op = operands[i];
326 if (!(op.getDefs().hasNext() || op.getUses().hasNext())) {
327 op.addUse(eq);
328 equations.addGraphNode(op);
329 } else {
330 op.addUse(eq);
331 }
332 }
333
334 if (EAGER && eq.evaluate()) changedCell(lhs);
335 }
336
337 /**
338 * Return the DF_LatticeCell corresponding to a key.
339 *
340 * @param key the key
341 * @return the LatticeCell if found. null otherwise
342 */
343 public DF_LatticeCell getCell(Object key) {
344 return cells.get(key);
345 }
346
347 /**
348 * Add all equations which contain a given cell to the work list.
349 * @param cell the cell in question
350 */
351 public void addCellAppearancesToWorkList(DF_LatticeCell cell) {
352 for (Enumeration<DF_Equation> e = getEquations(); e.hasMoreElements();) {
353 DF_Equation eq = e.nextElement();
354 if (eq.hasCell(cell)) {
355 addToWorkList(eq);
356 }
357 }
358 }
359
360 private static final Comparator<DF_Equation> dfComparator = new Comparator<DF_Equation>() {
361 public int compare(DF_Equation o1, DF_Equation o2) {
362 DF_Equation eq1 = o1;
363 DF_Equation eq2 = o2;
364 return (eq1.topologicalNumber - eq2.topologicalNumber);
365 }
366 };
367
368 /**
369 * Initialize all lattice cells in the system.
370 */
371 protected abstract void initializeLatticeCells();
372
373 /**
374 * Initialize the work list for iteration.j
375 */
376 protected abstract void initializeWorkList();
377
378 /**
379 * Create a new lattice cell, referenced by a given key
380 * @param key key to look up the new cell with
381 * @return the newly created lattice cell
382 */
383 protected abstract DF_LatticeCell makeCell(Object key);
384
385 /**
386 * Update the worklist, assuming that a particular equation
387 * has been re-evaluated
388 *
389 * @param eq the equation that has been re-evaluated.
390 */
391 protected void updateWorkList(DF_Equation eq) {
392 // find each equation which uses this lattice cell, and
393 // add it to the work list
394 Iterator<DF_Equation> e = eq.getLHS().getUses();
395 while (e.hasNext()) {
396 workList.add(e.next());
397 }
398 }
399
400 /**
401 * Number the equations in topological order.
402 *
403 * <p> PRECONDITION: Already called addGraphEdges()
404 *
405 * <p>Algorithm:
406 * <ul>
407 * <li> 1. create a DAG of SCCs
408 * <li> 2. number this DAG topologically
409 * <li> 3. walk through the DAG and number nodes as they are
410 * encountered
411 * </ul>
412 */
413 private void numberEquationsTopological() {
414 GraphNodeEnumeration topOrder = GraphUtilities.
415 enumerateTopSort(equations);
416 Enumeration<GraphNode> rev = new ReverseDFSenumerateByFinish(equations, topOrder);
417 int number = 0;
418 while (rev.hasMoreElements()) {
419 GraphNode elt = rev.nextElement();
420 if (elt instanceof DF_Equation) {
421 DF_Equation eq = (DF_Equation) elt;
422 eq.setTopologicalNumber(number++);
423 }
424 }
425 }
426
427 /**
428 * Debugging aid: print statistics about the dataflow system.
429 */
430 void showGraphStats() {
431 System.out.println("graph has " + equations.numberOfNodes() + " nodes");
432 int count = 0;
433 for (Enumeration<GraphNode> e = equations.enumerateNodes(); e.hasMoreElements();) {
434 GraphNode eq = e.nextElement();
435 GraphNodeEnumeration outs = eq.outNodes();
436 while (outs.hasMoreElements()) {
437 count++;
438 outs.next();
439 }
440 }
441 System.out.println("graph has " + count + " edges");
442 }
443 }