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.lang.reflect.Constructor;
016 import java.util.Arrays;
017
018 import org.jikesrvm.compilers.opt.OptOptions;
019 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
020 import org.jikesrvm.compilers.opt.dfsolver.DF_AbstractCell;
021 import org.jikesrvm.compilers.opt.dfsolver.DF_Solution;
022 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
023 import org.jikesrvm.compilers.opt.ir.IR;
024
025 /**
026 * Perform index propagation (see Fink, Knobe && Sarkar, SAS 2000)
027 *
028 * <p> This analysis computes for each Array SSA variable A,
029 * the set of value numbers V(k) such that location
030 * A[k] is "available" at def A, and thus at all uses of A
031 *
032 * <p> We formulate this as a data flow problem as described in the paper.
033 *
034 * <p> This class relies on Array SSA form, global value numbering, and
035 * the dataflow equation solver framework.
036 *
037 * <p> TODO: This implementation is not terribly efficient. Speed it up.
038 */
039 public final class IndexPropagation extends CompilerPhase {
040
041 /**
042 * Constructor for this compiler phase
043 */
044 private static final Constructor<CompilerPhase> constructor =
045 getCompilerPhaseConstructor(IndexPropagation.class);
046
047 /**
048 * Get a constructor object for this compiler phase
049 * @return compiler phase constructor
050 */
051 @Override
052 public Constructor<CompilerPhase> getClassConstructor() {
053 return constructor;
054 }
055
056 /**
057 * @return <code>true</code> iff SSA is constructed on the HIR
058 */
059 @Override
060 public boolean shouldPerform(OptOptions options) {
061 return options.SSA;
062 }
063
064 /**
065 * Return the name of this compiler phase.
066 * @return "Index Propagation"
067 */
068 @Override
069 public String getName() {
070 return "Index Propagation";
071 }
072
073 /**
074 * Print verbose debugging messages?
075 */
076 private static final boolean DEBUG = false;
077
078 /**
079 * Perform the analysis.
080 * <p> Pre-condition: The IR is in Array SSA form and global value numbers
081 * have been computed.
082 *
083 * @param ir the IR to optimize
084 */
085 @Override
086 public void perform(IR ir) {
087 if (ir.desiredSSAOptions.getAbort()) return;
088 IndexPropagationSystem system = new IndexPropagationSystem(ir);
089 if (DEBUG) {
090 System.out.print("Solving...");
091 }
092 system.solve();
093 if (DEBUG) {
094 System.out.println("done");
095 }
096 DF_Solution solution = system.getSolution();
097 if (DEBUG) {
098 System.out.println("Index Propagation Solution: " + solution);
099 }
100 ir.HIRInfo.indexPropagationSolution = solution;
101 }
102
103 /**
104 * An ObjectCell is a lattice cell for the index propagation
105 * problem, used in redundant load elimination for fields.
106 * <p> An ObjectCell represents a set of value numbers,
107 * indicating that
108 * the elements indexed by these value numbers are available for
109 * a certain field type.
110 *
111 * <p> Note: this implementation does not scale, and is not terribly
112 * efficient.
113 */
114 static final class ObjectCell extends DF_AbstractCell {
115 /**
116 * a bound on the size of a lattice cell.
117 */
118 private static final int CAPACITY = 10;
119 /**
120 * a set of value numbers comparising this lattice cell.
121 */
122 private int[] numbers = null;
123 /**
124 * The number of value numbers in this cell.
125 */
126 private int size = 0;
127 /**
128 * The heap variable this lattice cell tracks information for.
129 */
130 private final HeapVariable<?> key;
131 /**
132 * Does this lattice cell represent TOP?
133 */
134 private boolean TOP = true;
135
136 /**
137 * Create a lattice cell corresponding to a heap variable.
138 * @param key the heap variable associated with this cell.
139 */
140 ObjectCell(HeapVariable<?> key) {
141 this.key = key;
142 }
143
144 /**
145 * Return the key
146 */
147 HeapVariable<?> getKey() {
148 return key;
149 }
150
151 /**
152 * Does this cell represent the TOP element in the dataflow lattice?
153 * @return true or false.
154 */
155 boolean isTOP() {
156 return TOP;
157 }
158
159 /**
160 * Does this cell represent the BOTTOM element in the dataflow lattice?
161 * @return true or false.
162 */
163 boolean isBOTTOM() {
164 return !TOP && (size == 0);
165 }
166
167 /**
168 * Mark this cell as representing (or not) the TOP element in the
169 * dataflow lattice.
170 * @param b should this cell contain TOP?
171 */
172 void setTOP(boolean b) {
173 TOP = b;
174 numbers = null;
175 }
176
177 /**
178 * Set the value of this cell to BOTTOM.
179 */
180 void setBOTTOM() {
181 clear();
182 }
183
184 /**
185 * Does this cell contain the value number v?
186 *
187 * @param v value number in question
188 * @return true or false
189 */
190 boolean contains(int v) {
191
192 if (isTOP()) return true;
193 if (v == GlobalValueNumberState.UNKNOWN) return false;
194
195 for (int i = 0; i < size; i++) {
196 if (numbers[i] == v) {
197 return true;
198 }
199 }
200 return false;
201 }
202
203 /**
204 * Add a value number to this cell.
205 *
206 * @param v value number
207 */
208 void add(int v) {
209 if (isTOP()) return;
210
211 if ((size < CAPACITY) && !contains(v)) {
212 if (size == 0) {
213 numbers = new int[CAPACITY];
214 }
215 numbers[size] = v;
216 size++;
217 }
218 }
219
220 /**
221 * Remove a value number from this cell.
222 *
223 * @param v value number
224 */
225 void remove(int v) {
226 if (isTOP()) {
227 throw new OptimizingCompilerException("Unexpected lattice operation");
228 }
229 int[] old = numbers;
230 int[] numbers = new int[CAPACITY];
231 int index = 0;
232 for (int i = 0; i < size; i++) {
233 if (old[i] == v) {
234 size--;
235 } else {
236 numbers[index++] = old[i];
237 }
238 }
239 }
240
241 /**
242 * Clear all value numbers from this cell.
243 */
244 void clear() {
245 setTOP(false);
246 size = 0;
247 numbers = null;
248 }
249
250 /**
251 * Return a deep copy of the value numbers in this cell.
252 * @return a deep copy of the value numbers in this cell, null to
253 * represent empty set.
254 */
255 int[] copyValueNumbers() {
256 if (isTOP()) {
257 throw new OptimizingCompilerException("Unexpected lattice operation");
258 }
259 if (size == 0) return null;
260
261 int[] result = new int[size];
262 for (int i = 0; i < size; i++) {
263 result[i] = numbers[i];
264 }
265 return result;
266 }
267
268 /**
269 * Return a string representation of this cell
270 * @return a string representation of this cell
271 */
272 @Override
273 public String toString() {
274 StringBuilder s = new StringBuilder(key.toString());
275
276 if (isTOP()) return s.append("{TOP}").toString();
277 if (isBOTTOM()) return s.append("{BOTTOM}").toString();
278
279 s.append("{");
280 for (int i = 0; i < size; i++) {
281 s.append(" ").append(numbers[i]);
282 }
283 s.append("}");
284 return s.toString();
285 }
286
287 /**
288 * Do two sets of value numbers differ?
289 * <p> SIDE EFFECT: sorts the sets
290 *
291 * @param set1 first set to compare
292 * @param set2 second set to compare
293 * @return true iff the two sets are different
294 */
295 public static boolean setsDiffer(int[] set1, int[] set2) {
296 if ((set1 != null) && (set2 != null)) {
297 Arrays.sort(set1);
298 Arrays.sort(set2);
299 return !Arrays.equals(set1, set2);
300 } else {
301 return set1 == set2;
302 }
303 }
304 }
305
306 /**
307 * An ArrayCell is a lattice cell for the index propagation
308 * problem, used in redundant load elimination for one-dimensional arrays.
309 * <p> An ArrayCell represents a set of value number pairs,
310 * indicating that
311 * the elements indexed by these value numbers are available for
312 * a certain array type.
313 *
314 * <p> For example, suppose p is an int[], with value number v(p).
315 * Then the value number pair <p,5> for heap variable I[ means
316 * that p[5] is available.
317 *
318 * <p> Note: this implementation does not scale, and is not terribly
319 * efficient.
320 */
321 static final class ArrayCell extends DF_AbstractCell {
322 /**
323 * a bound on the size of a lattice cell.
324 */
325 private static final int CAPACITY = 10;
326 /**
327 * a set of value number pairs comparising this lattice cell.
328 */
329 private ValueNumberPair[] numbers = null;
330 /**
331 * The number of value number pairs in this cell.
332 */
333 private int size = 0;
334 /**
335 * The heap variable this lattice cell tracks information for.
336 */
337 private final HeapVariable<?> key;
338 /**
339 * Does this lattice cell represent TOP?
340 */
341 private boolean TOP = true;
342
343 /**
344 * Create a lattice cell corresponding to a heap variable.
345 * @param key the heap variable associated with this cell.
346 */
347 ArrayCell(HeapVariable<?> key) {
348 this.key = key;
349 }
350
351 /**
352 * Return the key
353 */
354 HeapVariable<?> getKey() {
355 return key;
356 }
357
358 /**
359 * Does this cell represent the TOP element in the dataflow lattice?
360 * @return true or false.
361 */
362 boolean isTOP() {
363 return TOP;
364 }
365
366 /**
367 * Does this cell represent the BOTTOM element in the dataflow lattice?
368 * @return true or false.
369 */
370 boolean isBOTTOM() {
371 return !TOP && (size == 0);
372 }
373
374 /**
375 * Mark this cell as representing (or not) the TOP element in the
376 * dataflow lattice.
377 * @param b should this cell contain TOP?
378 */
379 void setTOP(boolean b) {
380 TOP = b;
381 numbers = null;
382 }
383
384 /**
385 * Set the value of this cell to BOTTOM.
386 */
387 void setBOTTOM() {
388 clear();
389 }
390
391 /**
392 * Does this cell contain the value number pair v1, v2?
393 *
394 * @param v1 first value number
395 * @param v2 second value number
396 * @return true or false
397 */
398 boolean contains(int v1, int v2) {
399 if (isTOP()) return true;
400 if (v1 == GlobalValueNumberState.UNKNOWN) return false;
401 if (v2 == GlobalValueNumberState.UNKNOWN) return false;
402 if (size == 0) return false;
403
404 ValueNumberPair p = new ValueNumberPair(v1, v2);
405 for (int i = 0; i < size; i++) {
406 if (numbers[i].equals(p)) {
407 return true;
408 }
409 }
410 return false;
411 }
412
413 /**
414 * Add a value number pair to this cell.
415 *
416 * @param v1 first value number
417 * @param v2 second value number
418 */
419 void add(int v1, int v2) {
420 if (isTOP()) return;
421
422 if ((size < CAPACITY) && !contains(v1, v2)) {
423 if (size == 0) {
424 numbers = new ValueNumberPair[CAPACITY];
425 }
426 ValueNumberPair p = new ValueNumberPair(v1, v2);
427 numbers[size] = p;
428 size++;
429 }
430 }
431
432 /**
433 * Remove a value number pair from this cell.
434 *
435 * @param v1 first value number
436 * @param v2 second value number
437 */
438 void remove(int v1, int v2) {
439 if (isTOP()) {
440 throw new OptimizingCompilerException("Unexpected lattice operation");
441 }
442 ValueNumberPair[] old = numbers;
443 ValueNumberPair[] numbers = new ValueNumberPair[CAPACITY];
444 int index = 0;
445 ValueNumberPair p = new ValueNumberPair(v1, v2);
446 for (int i = 0; i < size; i++) {
447 if (old[i].equals(p)) {
448 size--;
449 } else {
450 numbers[index++] = old[i];
451 }
452 }
453 }
454
455 /**
456 * Clear all value numbers from this cell.
457 */
458 void clear() {
459 setTOP(false);
460 size = 0;
461 numbers = null;
462 }
463
464 /**
465 * Return a deep copy of the value numbers in this cell
466 * @return a deep copy of the value numbers in this cell
467 */
468 ValueNumberPair[] copyValueNumbers() {
469 if (isTOP()) {
470 throw new OptimizingCompilerException("Unexpected lattice operation");
471 }
472
473 if (size == 0) return null;
474
475 ValueNumberPair[] result = new ValueNumberPair[size];
476 for (int i = 0; i < size; i++) {
477 result[i] = new ValueNumberPair(numbers[i]);
478 }
479 return result;
480 }
481
482 /**
483 * Return a string representation of this cell
484 * @return a string representation of this cell
485 */
486 @Override
487 public String toString() {
488 StringBuilder s = new StringBuilder(key.toString());
489
490 if (isTOP()) return s.append("{TOP}").toString();
491 if (isBOTTOM()) return s.append("{BOTTOM}").toString();
492
493 s.append("{");
494 for (int i = 0; i < size; i++) {
495 s.append(" ").append(numbers[i]);
496 }
497 s.append("}");
498 return s.toString();
499 }
500
501 /**
502 * Do two sets of value number pairs differ?
503 * <p> SIDE EFFECT: sorts the sets
504 *
505 * @param set1 first set to compare
506 * @param set2 second set to compare
507 * @return true iff the two sets are different
508 */
509 public static boolean setsDiffer(ValueNumberPair[] set1, ValueNumberPair[] set2) {
510 if ((set1 != null) && (set2 != null)) {
511 Arrays.sort(set1);
512 Arrays.sort(set2);
513 return !Arrays.equals(set1, set2);
514 } else {
515 return set1 == set2;
516 }
517 }
518 }
519 }