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 * IndexPropagation.java
027 *
028 * <p> Perform index propagation (see Fink, Knobe && Sarkar, SAS 2000)
029 *
030 * <p> This analysis computes for each Array SSA variable A,
031 * the set of value numbers V(k) such that location
032 * A[k] is "available" at def A, and thus at all uses of A
033 *
034 * <p> We formulate this as a data flow problem as described in the paper.
035 *
036 * <p> This class relies on Array SSA form, global value numbering, and
037 * the dataflow equation solver framework.
038 *
039 * <p> TODO: This implementation is not terribly efficient. Speed it up.
040 */
041 public final class IndexPropagation extends CompilerPhase {
042
043 /**
044 * Constructor for this compiler phase
045 */
046 private static final Constructor<CompilerPhase> constructor =
047 getCompilerPhaseConstructor(IndexPropagation.class);
048
049 /**
050 * Get a constructor object for this compiler phase
051 * @return compiler phase constructor
052 */
053 public Constructor<CompilerPhase> getClassConstructor() {
054 return constructor;
055 }
056
057 /**
058 * Should this phase be performed?
059 * @param options controlling compiler options
060 * @return true or false
061 */
062 public boolean shouldPerform(OptOptions options) {
063 return options.SSA;
064 }
065
066 /**
067 * Return the name of this compiler phase.
068 * @return "Index Propagation"
069 */
070 public String getName() {
071 return "Index Propagation";
072 }
073
074 /**
075 * Print vervose debugging messages?
076 */
077 private static final boolean DEBUG = false;
078
079 /**
080 * Perform the analysis.
081 * <p> Pre-condition: The ir is in Array SSA form and global value numbers
082 * have been computed.
083 *
084 * @param ir the IR to optimize
085 */
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 latticle 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 public String toString() {
273 StringBuilder s = new StringBuilder(key.toString());
274
275 if (isTOP()) return s.append("{TOP}").toString();
276 if (isBOTTOM()) return s.append("{BOTTOM}").toString();
277
278 s.append("{");
279 for (int i = 0; i < size; i++) {
280 s.append(" ").append(numbers[i]);
281 }
282 s.append("}");
283 return s.toString();
284 }
285
286 /**
287 * Do two sets of value numbers differ?
288 * <p> SIDE EFFECT: sorts the sets
289 *
290 * @param set1 first set to compare
291 * @param set2 second set to compare
292 * @return true iff the two sets are different
293 */
294 public static boolean setsDiffer(int[] set1, int[] set2) {
295 if ((set1 != null) && (set2 != null)) {
296 Arrays.sort(set1);
297 Arrays.sort(set2);
298 return !Arrays.equals(set1, set2);
299 } else {
300 return set1 == set2;
301 }
302 }
303 }
304
305 /**
306 * An ArrayCell is a lattice cell for the index propagation
307 * problem, used in redundant load elimination for one-dimensional arrays.
308 * <p> An ArrayCell represents a set of value number pairs,
309 * indicating that
310 * the elements indexed by these value numbers are available for
311 * a certain array type.
312 *
313 * <p> For example, suppose p is an int[], with value number v(p).
314 * Then the value number pair <p,5> for heap variable I[ means
315 * that p[5] is available.
316 *
317 * <p> Note: this implementation does not scale, and is not terribly
318 * efficient.
319 */
320 static final class ArrayCell extends DF_AbstractCell {
321 /**
322 * a bound on the size of a lattice cell.
323 */
324 private static final int CAPACITY = 10;
325 /**
326 * a set of value number pairs comparising this lattice cell.
327 */
328 private ValueNumberPair[] numbers = null;
329 /**
330 * The number of value number pairs in this cell.
331 */
332 private int size = 0;
333 /**
334 * The heap variable this lattice cell tracks information for.
335 */
336 private final HeapVariable<?> key;
337 /**
338 * Does this lattice cell represent TOP?
339 */
340 private boolean TOP = true;
341
342 /**
343 * Create a latticle cell corresponding to a heap variable.
344 * @param key the heap variable associated with this cell.
345 */
346 ArrayCell(HeapVariable<?> key) {
347 this.key = key;
348 }
349
350 /**
351 * Return the key
352 */
353 HeapVariable<?> getKey() {
354 return key;
355 }
356
357 /**
358 * Does this cell represent the TOP element in the dataflow lattice?
359 * @return true or false.
360 */
361 boolean isTOP() {
362 return TOP;
363 }
364
365 /**
366 * Does this cell represent the BOTTOM element in the dataflow lattice?
367 * @return true or false.
368 */
369 boolean isBOTTOM() {
370 return !TOP && (size == 0);
371 }
372
373 /**
374 * Mark this cell as representing (or not) the TOP element in the
375 * dataflow lattice.
376 * @param b should this cell contain TOP?
377 */
378 void setTOP(boolean b) {
379 TOP = b;
380 numbers = null;
381 }
382
383 /**
384 * Set the value of this cell to BOTTOM.
385 */
386 void setBOTTOM() {
387 clear();
388 }
389
390 /**
391 * Does this cell contain the value number pair v1, v2?
392 *
393 * @param v1 first value number
394 * @param v2 second value number
395 * @return true or false
396 */
397 boolean contains(int v1, int v2) {
398 if (isTOP()) return true;
399 if (v1 == GlobalValueNumberState.UNKNOWN) return false;
400 if (v2 == GlobalValueNumberState.UNKNOWN) return false;
401 if (size == 0) return false;
402
403 ValueNumberPair p = new ValueNumberPair(v1, v2);
404 for (int i = 0; i < size; i++) {
405 if (numbers[i].equals(p)) {
406 return true;
407 }
408 }
409 return false;
410 }
411
412 /**
413 * Add a value number pair to this cell.
414 *
415 * @param v1 first value number
416 * @param v2 second value number
417 */
418 void add(int v1, int v2) {
419 if (isTOP()) return;
420
421 if ((size < CAPACITY) && !contains(v1, v2)) {
422 if (size == 0) {
423 numbers = new ValueNumberPair[CAPACITY];
424 }
425 ValueNumberPair p = new ValueNumberPair(v1, v2);
426 numbers[size] = p;
427 size++;
428 }
429 }
430
431 /**
432 * Remove a value number pair from this cell.
433 *
434 * @param v1 first value number
435 * @param v2 second value number
436 */
437 void remove(int v1, int v2) {
438 if (isTOP()) {
439 throw new OptimizingCompilerException("Unexpected lattice operation");
440 }
441 ValueNumberPair[] old = numbers;
442 ValueNumberPair[] numbers = new ValueNumberPair[CAPACITY];
443 int index = 0;
444 ValueNumberPair p = new ValueNumberPair(v1, v2);
445 for (int i = 0; i < size; i++) {
446 if (old[i].equals(p)) {
447 size--;
448 } else {
449 numbers[index++] = old[i];
450 }
451 }
452 }
453
454 /**
455 * Clear all value numbers from this cell.
456 */
457 void clear() {
458 setTOP(false);
459 size = 0;
460 numbers = null;
461 }
462
463 /**
464 * Return a deep copy of the value numbers in this cell
465 * @return a deep copy of the value numbers in this cell
466 */
467 ValueNumberPair[] copyValueNumbers() {
468 if (isTOP()) {
469 throw new OptimizingCompilerException("Unexpected lattice operation");
470 }
471
472 if (size == 0) return null;
473
474 ValueNumberPair[] result = new ValueNumberPair[size];
475 for (int i = 0; i < size; i++) {
476 result[i] = new ValueNumberPair(numbers[i]);
477 }
478 return result;
479 }
480
481 /**
482 * Return a string representation of this cell
483 * @return a string representation of this cell
484 */
485 public String toString() {
486 StringBuilder s = new StringBuilder(key.toString());
487
488 if (isTOP()) return s.append("{TOP}").toString();
489 if (isBOTTOM()) return s.append("{BOTTOM}").toString();
490
491 s.append("{");
492 for (int i = 0; i < size; i++) {
493 s.append(" ").append(numbers[i]);
494 }
495 s.append("}");
496 return s.toString();
497 }
498
499 /**
500 * Do two sets of value number pairs differ?
501 * <p> SIDE EFFECT: sorts the sets
502 *
503 * @param set1 first set to compare
504 * @param set2 second set to compare
505 * @return true iff the two sets are different
506 */
507 public static boolean setsDiffer(ValueNumberPair[] set1, ValueNumberPair[] set2) {
508 if ((set1 != null) && (set2 != null)) {
509 Arrays.sort(set1);
510 Arrays.sort(set2);
511 return !Arrays.equals(set1, set2);
512 } else {
513 return set1 == set2;
514 }
515 }
516 }
517 }