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.ssa;
014
015 import java.util.ArrayList;
016 import java.util.Enumeration;
017 import java.util.HashMap;
018 import java.util.Iterator;
019 import java.util.Stack;
020 import org.jikesrvm.VM;
021 import org.jikesrvm.compilers.opt.ir.IR;
022 import org.jikesrvm.compilers.opt.ir.Instruction;
023 import org.jikesrvm.compilers.opt.ir.operand.ConstantOperand;
024 import org.jikesrvm.compilers.opt.util.GraphNode;
025
026 /**
027 * This class holds the results of global value numbering.
028 * ala Alpern, Wegman and Zadeck, PoPL 88.
029 * See Muchnick p.348 for a discussion (which is quite buggy, should
030 * have stuck to the dragon book, which gives a high-level description of
031 * the correct algorithm on page 143).
032 */
033 public final class GlobalValueNumberState {
034 /**
035 * Constant used to flag "unknown" value numbers
036 */
037 public static final int UNKNOWN = -1;
038 /**
039 * Print verbose debugging output?
040 */
041 private static final boolean DEBUG = false;
042 /**
043 * Assume parameters are not aliased?
044 */
045 private static final boolean NO_PARAM_ALIAS = false;
046
047 /**
048 * ArrayList of GVCongruenceClass, indexed by value number.
049 */
050 private final ArrayList<GVCongruenceClass> B;
051 /**
052 * The value graph.
053 */
054 final ValueGraph valueGraph;
055 /**
056 * Stack used for a work list.
057 */
058 private final Stack<GVCongruenceClass> workList;
059
060 /**
061 * Construct a structure to hold global value number results for an IR.
062 *
063 * @param ir governing IR
064 */
065 GlobalValueNumberState(IR ir) {
066 B = new ArrayList<GVCongruenceClass>();
067 workList = new Stack<GVCongruenceClass>();
068 valueGraph = new ValueGraph(ir);
069 globalValueNumber();
070 }
071
072 /**
073 * Compute node congruence over the value number graph.
074 *
075 * <p> Algorithm: Muchnick pp. 348-355
076 * <p> Note: the Muchnick algorithm is buggy. In particular, it
077 * does not put all needed congruence classes on the worklist.
078 *
079 * <p> Two nodes in the value graph are congruent if one of the
080 * following holds:
081 * <ul>
082 * <li> they are the same node
083 * <li> their labels are identical constants
084 * <li> they have the same operators and their operands are
085 * congruent
086 * </ul>
087 *
088 * <p> Optimistic algorithm:
089 * <ul>
090 * <li> Initially assume all nodes with the same label are congruent
091 * <li> start a work list with all congruence classes that
092 * have multiple operands
093 * <li> choose a congruence class from the worklist. partition its
094 * elements into new congruence classes if we can discover that
095 * they are not congruent.
096 * <li> Add any newly created congruence classes to the work list.
097 * <li> (Here's the step Muchnick omits:)
098 * For each class C which has a dependence on any of the newly
099 * created congruence classes, add C to the work list
100 * <li> repeat until work list is empty
101 * </ul>
102 *
103 * <p> The following method breaks Muchnick's algorithm, which will
104 * assign m and n the same value number. Muchnick's problem is that
105 * it does not put the congruence class for 'int_mul' back on the worklist
106 * when we discover, for example, that i is not congruent to k
107 * <pre>
108 * public int foo(int a, int b, int c, int d, int e, int f, int g, int h) {
109 * int i = a+b;
110 * int j = c+d;
111 * int k = e+f;
112 * int l = g+h;
113 * int m = i * j;
114 * int n = k * l;
115 * int o = m/n;
116 * return o;
117 * }
118 * </pre>
119 */
120 private void globalValueNumber() {
121 if (DEBUG) {
122 VM.sysWrite(valueGraph.toString());
123 }
124 // initialize the congurence classes
125 initialize();
126 // initialize the work list
127 initializeWorkList();
128 // drain the work list
129 while (!workList.empty()) {
130 GVCongruenceClass partition = workList.pop();
131 partitionClass(partition);
132 }
133 // all done
134 if (DEBUG) {
135 printValueNumbers();
136 }
137 }
138
139 /**
140 * Merge the congruence classes containing vertices v1 and v2.;
141 */
142 void mergeClasses(ValueGraphVertex v1, ValueGraphVertex v2) {
143 if (DEBUG) {
144 System.out.println("@@@@ mergeClasses called with v1 = " + v1 + " ; v2 = " + v2);
145 }
146
147 int val1 = v1.getValueNumber();
148 int val2 = v2.getValueNumber();
149 if (val1 == val2) return;
150
151 GVCongruenceClass class1 = B.get(val1);
152
153 while (true) {
154 GVCongruenceClass class2 = B.get(val2);
155 Iterator<ValueGraphVertex> i = class2.iterator();
156 if (!i.hasNext()) break;
157 ValueGraphVertex v = i.next();
158 if (DEBUG) {
159 System.out.println("@@@@ moving vertex " + v + " from class " + val2 + " to class " + val1);
160 }
161 class1.addVertex(v);
162 class2.removeVertex(v);
163 v.setValueNumber(val1);
164 }
165
166 // Null out entry for val2
167 B.set(val2, null);
168 }
169
170 /**
171 * Definitely-same relation.
172 * @param name1 first variable
173 * @param name2 second variable
174 * @return true iff the value numbers for two variables are equal
175 */
176 boolean DS(Object name1, Object name2) {
177 ValueGraphVertex v1 = valueGraph.getVertex(name1);
178 ValueGraphVertex v2 = valueGraph.getVertex(name2);
179 return v1.getValueNumber() == v2.getValueNumber();
180 }
181
182 /**
183 * Definitely-different relation for two value numbers.
184 * Returns true for the following cases:
185 * <ul>
186 * <li> v1 and v2 are both constants, but don't match
187 * <li> v1 and v2 both result from NEW statements, but don't match
188 * <li> one of v1 and v2 is a parameter, and the other results from a
189 * new statement
190 * </ul>
191 * <p> TODO: add more smarts
192 * @param v1 first value number
193 * @param v2 second value number
194 * @return true iff the value numbers for two variables are definitely
195 * different
196 */
197 boolean DD(int v1, int v2) {
198 if ((v1 == -1) || (v2 == -1)) {
199 return false;
200 }
201 GVCongruenceClass class1 = B.get(v1);
202 GVCongruenceClass class2 = B.get(v2);
203 Object label1 = class1.getLabel();
204 Object label2 = class2.getLabel();
205 // if one is a constant, they must both be ...
206 if (isConstant(label1) && !isConstant(label2)) {
207 return false;
208 }
209 if (!isConstant(label1) && isConstant(label2)) {
210 return false;
211 }
212 if (isConstant(label1)) {
213 return (v1 != v2);
214 }
215 // handle DD for allocations
216 if (isBornAtAllocation(label1)) {
217 if (isBornAtAllocation(label2)) {
218 // both are NEW. Are they dd?
219 return (v1 != v2);
220 } else if (class2.containsParameter()) {
221 // one is NEW, other is parameter. They are DD.
222 return true;
223 }
224 } else {
225 if (isBornAtAllocation(label2)) {
226 if (class1.containsParameter()) {
227 // one is NEW, other is parameter. They are DD.
228 return true;
229 }
230 }
231 }
232 // assume parameters are not aliased?
233 if (NO_PARAM_ALIAS) {
234 if (v1 != v2) {
235 if (class1.containsParameter()) {
236 if (class2.containsParameter()) {
237 return true;
238 }
239 }
240 }
241 }
242
243 // if we haven't figured out they're DD, return false;
244 return false;
245 }
246
247 /**
248 * Definitely-different relation.
249 * Returns true for the following cases:
250 * <ul>
251 * <li> name1 and name2 are both constants, but don't match
252 * <li> name1 and name2 both result from NEW statements, but don't match
253 * <li> one of name1 and name2 is a parameter, and the other results from a
254 * new statement
255 * </ul>
256 * <p> TODO: add more smarts
257 * @param name1 name of first object to compare
258 * @param name2 name of second object to compare
259 * @return true iff the value numbers for two variables are definitely
260 * different
261 */
262 boolean DD(Object name1, Object name2) {
263 ValueGraphVertex v1 = valueGraph.getVertex(name1);
264 ValueGraphVertex v2 = valueGraph.getVertex(name2);
265 return DD(v1.getValueNumber(), v2.getValueNumber());
266 }
267
268 GVCongruenceClass congruenceClass(Object name) {
269 ValueGraphVertex v = valueGraph.getVertex(name);
270 return B.get(v.getValueNumber());
271 }
272
273 /**
274 * Return the (integer) value number for a given variable
275 *
276 * @param name name of the variable to look up
277 * @return its value number
278 */
279 int getValueNumber(Object name) {
280 ValueGraphVertex v = valueGraph.getVertex(name);
281 if (v == null) {
282 return UNKNOWN;
283 }
284 return v.getValueNumber();
285 }
286
287 /**
288 * Print the value numbers for each node in the value graph.
289 */
290 void printValueNumbers() {
291 for (Enumeration<GraphNode> e = valueGraph.enumerateVertices(); e.hasMoreElements();) {
292 ValueGraphVertex v = (ValueGraphVertex) e.nextElement();
293 int valueNumber = v.getValueNumber();
294 GVCongruenceClass c = B.get(valueNumber);
295 System.out.println(v.getName() + " " + valueNumber + " " + c.getLabel());
296 }
297 }
298
299 /**
300 * Initialize the congruence classes, assuming that all nodes
301 * with the same label are congruent.
302 */
303 private void initialize() {
304 // store a map from label -> congruenceClass
305 HashMap<Object, GVCongruenceClass> labelMap = new HashMap<Object, GVCongruenceClass>(10);
306 for (Enumeration<GraphNode> e = valueGraph.enumerateVertices(); e.hasMoreElements();) {
307 ValueGraphVertex v = (ValueGraphVertex) e.nextElement();
308 Object label = v.getLabel();
309 GVCongruenceClass c = findOrCreateCongruenceClass(label, labelMap);
310 // add this node to the congruence class
311 c.addVertex(v);
312 // set the value number for the node
313 v.setValueNumber(c.getValueNumber());
314 }
315 }
316
317 /**
318 * Given a label, return the congruence class for that label.
319 * Create one if needed.
320 *
321 * @param label the label of a congruence class
322 * @param labelMap a mapping from labels to congruence class
323 * @return the congruence class for the label.
324 */
325 private GVCongruenceClass findOrCreateCongruenceClass(Object label,
326 HashMap<Object, GVCongruenceClass> labelMap) {
327 GVCongruenceClass result = labelMap.get(label);
328 if ((result == null) || (label == null)) {
329 result = createCongruenceClass(label);
330 labelMap.put(label, result);
331 }
332 return result;
333 }
334
335 /**
336 * Given a label, return a new congruence class for that label.
337 * @param label the label of a congruence class
338 * @return the congruence class for the label.
339 */
340 private GVCongruenceClass createCongruenceClass(Object label) {
341 // create a new congruence class, and update data structures
342 int index = B.size();
343 GVCongruenceClass result = new GVCongruenceClass(index, label);
344 B.add(result);
345 return result;
346 }
347
348 /**
349 * Initialize the work list.
350 * A congruence class gets put on the work list if any two nodes
351 * in the class point to corresponding targets in separate partitions.
352 */
353 private void initializeWorkList() {
354 for (GVCongruenceClass c : B) {
355 if (c.size() == 1) {
356 continue;
357 }
358 // store a reference to the first node in c
359 Iterator<ValueGraphVertex> i = c.iterator();
360 ValueGraphVertex first = i.next();
361 // now check that each other target matches the first element
362 // if not, add this class to the work list
363 //
364 while (i.hasNext()) {
365 ValueGraphVertex v = i.next();
366 if (!checkCongruence(first, v)) {
367 workList.push(c);
368 break;
369 }
370 }
371 }
372 }
373
374 /**
375 * Partition a congruence class.
376 * @param partition the class to partition
377 */
378 private void partitionClass(GVCongruenceClass partition) {
379 // store a reference to the first node in c, which will serve
380 // as a representative for this class
381 Iterator<ValueGraphVertex> i = partition.iterator();
382 ValueGraphVertex first = i.next();
383 ArrayList<GVCongruenceClass> newClasses = new ArrayList<GVCongruenceClass>();
384 // now check each other node in c, to see if it matches the
385 // representative
386 ArrayList<ValueGraphVertex> toRemove = new ArrayList<ValueGraphVertex>();
387 while (i.hasNext()) {
388 ValueGraphVertex v = i.next();
389 if (!checkCongruence(first, v)) {
390 // NOT CONGRUENT!! split the partition. first check if
391 // v fits in any other newly created congruence classes
392 int index = findCongruenceMatch(newClasses, v);
393 if (index > -1) {
394 // MATCH FOUND!! place v in newClasses[index]
395 GVCongruenceClass match = B.get(index);
396 match.addVertex(v);
397 v.setValueNumber(match.getValueNumber());
398 } else {
399 // NO MATCH FOUND!! create a new congruence class
400 // find the appropriate label for the new congruence class
401 // and create a new congruence class with this label
402 GVCongruenceClass c = createCongruenceClass(v);
403 newClasses.add(c);
404 c.addVertex(v);
405 v.setValueNumber(c.getValueNumber());
406 }
407 // mark v as to be removed from partition
408 // (Can't remove it yet while iterating over the set);
409 toRemove.add(v);
410 }
411 }
412 // remove necessary vertices
413 for (ValueGraphVertex v : toRemove) {
414 partition.removeVertex(v);
415 }
416 // if needed place the original partition back on the work list
417 if ((!newClasses.isEmpty()) && (partition.size() > 1)) {
418 workList.push(partition);
419 }
420 // place any new congruence classes with size > 1 on the worklist
421 // also place any classes which might indirectly be affected
422 for (GVCongruenceClass c : newClasses) {
423 if (c.size() > 1) {
424 workList.push(c);
425 }
426 addDependentClassesToWorklist(c);
427 }
428 }
429
430 /**
431 * Assuming congruence class c has changed: find all other classes
432 * that might be affected, and add them to the worklist
433 * @param c the congruence class that has changed
434 */
435 private void addDependentClassesToWorklist(GVCongruenceClass c) {
436 // for each element of this congruence class:
437 for (ValueGraphVertex v : c) {
438 // for each vertex which points to v in the value graph
439 for (Enumeration<GraphNode> e = v.inNodes(); e.hasMoreElements();) {
440 ValueGraphVertex in = (ValueGraphVertex) e.nextElement();
441 int vn = in.getValueNumber();
442 GVCongruenceClass x = B.get(vn);
443 workList.push(x);
444 }
445 }
446 }
447
448 /**
449 * Does vertex v belong to any congruence class in a vector?
450 * If so, returns the value number of the matching congruence class.
451 * If none found, returns -1.
452 * @param vector a vector of congruence classes
453 * @param v the vertex to search for
454 * @return the value number corresponding to the congruence class
455 * containing v. -1 iff no such class is found.
456 */
457 private int findCongruenceMatch(ArrayList<GVCongruenceClass> vector, ValueGraphVertex v) {
458 for (GVCongruenceClass klass : vector) {
459 if (checkCongruence(v, klass)) {
460 return klass.getValueNumber();
461 }
462 }
463 return -1;
464 }
465
466 /**
467 * Does the current state of the algorithm optimistically assume
468 * that a vertex v is congruent to the vertices in a congruence
469 * class? Note: this can return true even if
470 * if the value numbers don't currently match.
471 * @param v the vertex in question
472 * @param c the congurence class to check
473 * @return true or false
474 */
475 private boolean checkCongruence(ValueGraphVertex v, GVCongruenceClass c) {
476 ValueGraphVertex r = c.getRepresentative();
477 boolean result = checkCongruence(r, v);
478 return result;
479 }
480
481 /**
482 * Does the current state of the algorithm optimistically assume
483 * that two nodes are congruent? Note: this can return false
484 * even if the value numbers are currently the same.
485 * @param v1 first vertex
486 * @param v2 second vertex
487 */
488 private boolean checkCongruence(ValueGraphVertex v1, ValueGraphVertex v2) {
489 if (v1 == v2) {
490 return true;
491 }
492 // make sure the two nodes have the same label
493 if (v1.getLabel() != v2.getLabel()) {
494 return false;
495 }
496 // make sure that the operands match
497 int arity = v1.getArity();
498 for (int i = 0; i < arity; i++) {
499 ValueGraphVertex target1 = v1.getTarget(i);
500 ValueGraphVertex target2 = v2.getTarget(i);
501 // if either target is null, then that particular control
502 // flow path is never realized, so assume TOP
503 if ((target1 == null) || (target2 == null)) {
504 continue;
505 }
506 if (target1.getValueNumber() != target2.getValueNumber()) {
507 return false;
508 }
509 }
510 return true;
511 }
512
513 /**
514 * Does a given label indicate that the object has a constant value?
515 */
516 private static boolean isConstant(Object label) {
517 return (label instanceof ConstantOperand);
518 }
519
520 /**
521 * Does a given label indicate that the object is created at an
522 * allocation site?
523 */
524 private static boolean isBornAtAllocation(Object label) {
525 return (label instanceof Instruction);
526 }
527 }