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