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 static org.jikesrvm.compilers.opt.ir.Operators.READ_CEILING;
016 import static org.jikesrvm.compilers.opt.ir.Operators.WRITE_FLOOR;
017
018 import java.util.Enumeration;
019
020 import org.jikesrvm.classloader.TypeReference;
021 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
022 import org.jikesrvm.compilers.opt.dfsolver.DF_Equation;
023 import org.jikesrvm.compilers.opt.dfsolver.DF_LatticeCell;
024 import org.jikesrvm.compilers.opt.dfsolver.DF_Operator;
025 import org.jikesrvm.compilers.opt.dfsolver.DF_System;
026 import org.jikesrvm.compilers.opt.ir.ALoad;
027 import org.jikesrvm.compilers.opt.ir.AStore;
028 import org.jikesrvm.compilers.opt.ir.Attempt;
029 import org.jikesrvm.compilers.opt.ir.BasicBlock;
030 import org.jikesrvm.compilers.opt.ir.BasicBlockEnumeration;
031 import org.jikesrvm.compilers.opt.ir.CacheOp;
032 import org.jikesrvm.compilers.opt.ir.Call;
033 import org.jikesrvm.compilers.opt.ir.GetField;
034 import org.jikesrvm.compilers.opt.ir.GetStatic;
035 import org.jikesrvm.compilers.opt.ir.IR;
036 import org.jikesrvm.compilers.opt.ir.IRTools;
037 import org.jikesrvm.compilers.opt.ir.Instruction;
038 import org.jikesrvm.compilers.opt.ir.MonitorOp;
039 import org.jikesrvm.compilers.opt.ir.New;
040 import org.jikesrvm.compilers.opt.ir.NewArray;
041 import org.jikesrvm.compilers.opt.ir.Phi;
042 import org.jikesrvm.compilers.opt.ir.Prepare;
043 import org.jikesrvm.compilers.opt.ir.PutField;
044 import org.jikesrvm.compilers.opt.ir.PutStatic;
045 import org.jikesrvm.compilers.opt.ir.operand.HeapOperand;
046 import org.jikesrvm.compilers.opt.ir.operand.Operand;
047 import org.jikesrvm.compilers.opt.ssa.IndexPropagation.ArrayCell;
048 import org.jikesrvm.compilers.opt.ssa.IndexPropagation.ObjectCell;
049
050 /**
051 * Represents a set of dataflow equations used to solve the
052 * index propagation problem.
053 */
054 class IndexPropagationSystem extends DF_System {
055
056 /**
057 * The governing IR.
058 */
059 private final IR ir;
060 /**
061 * Heap Array SSA lookaside information for the IR.
062 */
063 private final SSADictionary ssa;
064 /**
065 * Results of global value numbering
066 */
067 private final GlobalValueNumberState valueNumbers;
068 /**
069 * object representing the MEET operator
070 */
071 private static final MeetOperator MEET = new MeetOperator();
072
073 /**
074 * Set up the system of dataflow equations.
075 * @param _ir the IR
076 */
077 public IndexPropagationSystem(IR _ir) {
078 ir = _ir;
079 ssa = ir.HIRInfo.dictionary;
080 valueNumbers = ir.HIRInfo.valueNumbers;
081 setupEquations();
082 }
083
084 /**
085 * Create an DF_LatticeCell corresponding to an HeapVariable
086 * @param o the heap variable
087 * @return a new lattice cell corresponding to this heap variable
088 */
089 protected DF_LatticeCell makeCell(Object o) {
090 if (!(o instanceof HeapVariable)) {
091 throw new OptimizingCompilerException("IndexPropagation:makeCell");
092 }
093 DF_LatticeCell result = null;
094 Object heapType = ((HeapVariable<?>) o).getHeapType();
095 if (heapType instanceof TypeReference) {
096 result = new ArrayCell((HeapVariable<?>) o);
097 } else {
098 result = new ObjectCell((HeapVariable<?>) o);
099 }
100 return result;
101 }
102
103 /**
104 * Initialize the lattice variables.
105 */
106 protected void initializeLatticeCells() {
107 // initially all lattice cells are set to TOP
108 // set the lattice cells that are exposed on entry to BOTTOM
109 for (DF_LatticeCell c : cells.values()) {
110 if (c instanceof ObjectCell) {
111 ObjectCell c1 = (ObjectCell) c;
112 HeapVariable<?> key = c1.getKey();
113 if (key.isExposedOnEntry()) {
114 c1.setBOTTOM();
115 }
116 } else {
117 ArrayCell c1 = (ArrayCell) c;
118 HeapVariable<?> key = c1.getKey();
119 if (key.isExposedOnEntry()) {
120 c1.setBOTTOM();
121 }
122 }
123 }
124 }
125
126 /**
127 * Initialize the work list for the dataflow equation system.
128 */
129 protected void initializeWorkList() {
130 // add all equations to the work list that contain a non-TOP
131 // variable
132 for (Enumeration<DF_Equation> e = getEquations(); e.hasMoreElements();) {
133 DF_Equation eq = e.nextElement();
134 for (DF_LatticeCell operand : eq.getOperands()) {
135 if (operand instanceof ObjectCell) {
136 if (!((ObjectCell) operand).isTOP()) {
137 addToWorkList(eq);
138 break;
139 }
140 } else {
141 if (!((ArrayCell) operand).isTOP()) {
142 addToWorkList(eq);
143 break;
144 }
145 }
146 }
147 }
148 }
149
150 /**
151 * Walk through the IR and add dataflow equations for each instruction
152 * that affects the values of Array SSA variables.
153 */
154 void setupEquations() {
155 for (BasicBlockEnumeration e = ir.getBasicBlocks(); e.hasMoreElements();) {
156 BasicBlock bb = e.nextElement();
157 for (SSADictionary.AllInstructionEnumeration e2 = ssa.getAllInstructions(bb); e2.hasMoreElements();) {
158 Instruction s = e2.nextElement();
159 // only consider instructions which use/def Array SSA variables
160 if (!ssa.usesHeapVariable(s) && !ssa.defsHeapVariable(s)) {
161 continue;
162 }
163 if (s.isDynamicLinkingPoint()) {
164 processCall(s);
165 } else if (GetStatic.conforms(s)) {
166 processLoad(s);
167 } else if (GetField.conforms(s)) {
168 processLoad(s);
169 } else if (PutStatic.conforms(s)) {
170 processStore(s);
171 } else if (PutField.conforms(s)) {
172 processStore(s);
173 } else if (New.conforms(s)) {
174 processNew(s);
175 } else if (NewArray.conforms(s)) {
176 processNew(s);
177 } else if (ALoad.conforms(s)) {
178 processALoad(s);
179 } else if (AStore.conforms(s)) {
180 processAStore(s);
181 } else if (Call.conforms(s)) {
182 processCall(s);
183 } else if (MonitorOp.conforms(s)) {
184 processCall(s);
185 } else if (Prepare.conforms(s)) {
186 processCall(s);
187 } else if (Attempt.conforms(s)) {
188 processCall(s);
189 } else if (CacheOp.conforms(s)) {
190 processCall(s);
191 } else if (Phi.conforms(s)) {
192 processPhi(s);
193 } else if (s.operator == READ_CEILING) {
194 processCall(s);
195 } else if (s.operator == WRITE_FLOOR) {
196 processCall(s);
197 }
198 }
199 }
200 }
201
202 /**
203 * Update the set of dataflow equations to account for the actions
204 * of a Load instruction
205 *
206 * <p> The load is of the form x = A[k]. let A_1 be the array SSA
207 * variable before the load, and A_2 the array SSA variable after
208 * the store. Then we add the dataflow equation
209 * L(A_2) = updateUse(L(A_1), VALNUM(k))
210 *
211 * <p> Intuitively, this equation represents the fact that A[k] is available
212 * after the store
213 *
214 * @param s the Load instruction
215 */
216 void processLoad(Instruction s) {
217 HeapOperand<?>[] A1 = ssa.getHeapUses(s);
218 HeapOperand<?>[] A2 = ssa.getHeapDefs(s);
219 if ((A1.length != 1) || (A2.length != 1)) {
220 throw new OptimizingCompilerException(
221 "IndexPropagation.processLoad: load instruction defs or uses multiple heap variables?");
222 }
223 int valueNumber = -1;
224 if (GetField.conforms(s)) {
225 Object address = GetField.getRef(s);
226 valueNumber = valueNumbers.getValueNumber(address);
227 } else { // GetStatic.conforms(s)
228 valueNumber = 0;
229 }
230 if (IRTools.mayBeVolatileFieldLoad(s) || ir.options.READS_KILL) {
231 // to obey JMM strictly, we must treat every load as a
232 // DEF
233 addUpdateObjectDefEquation(A2[0].getHeapVariable(), A1[0].getHeapVariable(), valueNumber);
234 } else {
235 // otherwise, don't have to treat every load as a DEF
236 addUpdateObjectUseEquation(A2[0].getHeapVariable(), A1[0].getHeapVariable(), valueNumber);
237 }
238 }
239
240 /**
241 * Update the set of dataflow equations to account for the actions
242 * of a Store instruction.
243 *
244 * <p> The store is of the form A[k] = val. let A_1 be the array SSA
245 * variable before the store, and A_2 the array SSA variable after
246 * the store. Then we add the dataflow equation
247 * L(A_2) = updateDef(L(A_1), VALNUM(k))
248 *
249 * <p> Intuitively, this equation represents the fact that A[k] is available
250 * after the store
251 *
252 * @param s the Store instruction
253 */
254 void processStore(Instruction s) {
255 HeapOperand<?>[] A1 = ssa.getHeapUses(s);
256 HeapOperand<?>[] A2 = ssa.getHeapDefs(s);
257 if ((A1.length != 1) || (A2.length != 1)) {
258 throw new OptimizingCompilerException(
259 "IndexPropagation.processStore: store instruction defs or uses multiple heap variables?");
260 }
261 int valueNumber = -1;
262 if (PutField.conforms(s)) {
263 Object address = PutField.getRef(s);
264 valueNumber = valueNumbers.getValueNumber(address);
265 } else { // PutStatic.conforms(s)
266 valueNumber = 0;
267 }
268 addUpdateObjectDefEquation(A2[0].getHeapVariable(), A1[0].getHeapVariable(), valueNumber);
269 }
270
271 /**
272 * Update the set of dataflow equations to account for the actions
273 * of ALoad instruction s
274 *
275 * <p> The load is of the form x = A[k]. let A_1 be the array SSA
276 * variable before the load, and A_2 the array SSA variable after
277 * the load. Then we add the dataflow equation
278 * L(A_2) = updateUse(L(A_1), VALNUM(k))
279 *
280 * <p> Intuitively, this equation represents the fact that A[k] is available
281 * after the store
282 *
283 * @param s the Aload instruction
284 */
285 void processALoad(Instruction s) {
286 HeapOperand<?>[] A1 = ssa.getHeapUses(s);
287 HeapOperand<?>[] A2 = ssa.getHeapDefs(s);
288 if ((A1.length != 1) || (A2.length != 1)) {
289 throw new OptimizingCompilerException(
290 "IndexPropagation.processALoad: aload instruction defs or uses multiple heap variables?");
291 }
292 Operand array = ALoad.getArray(s);
293 Operand index = ALoad.getIndex(s);
294 if (IRTools.mayBeVolatileFieldLoad(s) || ir.options.READS_KILL) {
295 // to obey JMM strictly, we must treat every load as a
296 // DEF
297 addUpdateArrayDefEquation(A2[0].getHeapVariable(), A1[0].getHeapVariable(), array, index);
298 } else {
299 // otherwise, don't have to treat every load as a DEF
300 addUpdateArrayUseEquation(A2[0].getHeapVariable(), A1[0].getHeapVariable(), array, index);
301 }
302 }
303
304 /**
305 * Update the set of dataflow equations to account for the actions
306 * of AStore instruction s
307 *
308 * <p> The store is of the form A[k] = val. let A_1 be the array SSA
309 * variable before the store, and A_2 the array SSA variable after
310 * the store. Then we add the dataflow equation
311 * L(A_2) = update(L(A_1), VALNUM(k))
312 *
313 * <p> Intuitively, this equation represents the fact that A[k] is available
314 * after the store
315 *
316 * @param s the Astore instruction
317 */
318 void processAStore(Instruction s) {
319 HeapOperand<?>[] A1 = ssa.getHeapUses(s);
320 HeapOperand<?>[] A2 = ssa.getHeapDefs(s);
321 if ((A1.length != 1) || (A2.length != 1)) {
322 throw new OptimizingCompilerException(
323 "IndexPropagation.processAStore: astore instruction defs or uses multiple heap variables?");
324 }
325 Operand array = AStore.getArray(s);
326 Operand index = AStore.getIndex(s);
327 addUpdateArrayDefEquation(A2[0].getHeapVariable(), A1[0].getHeapVariable(), array, index);
328 }
329
330 /**
331 * Update the set of dataflow equations to account for the actions
332 * of allocation instruction s
333 *
334 * @param s the New instruction
335 */
336 void processNew(Instruction s) {
337 /** Assume nothing is a available after a new. So, set
338 * each lattice cell defined by the NEW as BOTTOM.
339 * TODO: add logic that understands that after a
340 * NEW, all fields have their default values.
341 */
342 for (HeapOperand<?> def : ssa.getHeapDefs(s)) {
343 DF_LatticeCell c = findOrCreateCell(def.getHeapVariable());
344 if (c instanceof ObjectCell) {
345 ((ObjectCell) c).setBOTTOM();
346 } else {
347 ((ArrayCell) c).setBOTTOM();
348 }
349 }
350 }
351
352 /**
353 * Update the set of dataflow equations to account for the actions
354 * of CALL instruction.
355 *
356 * @param s the Call instruction
357 */
358 void processCall(Instruction s) {
359
360 /** set all lattice cells def'ed by the call to bottom */
361 for (HeapOperand<?> operand : ssa.getHeapDefs(s)) {
362 DF_LatticeCell c = findOrCreateCell(operand.getHeapVariable());
363 if (c instanceof ObjectCell) {
364 ((ObjectCell) c).setBOTTOM();
365 } else {
366 ((ArrayCell) c).setBOTTOM();
367 }
368 }
369 }
370
371 /**
372 * Update the set of dataflow equations to account for the actions
373 * of Phi instruction.
374 *
375 * <p> The instruction has the form A1 = PHI (A2, A3, A4);
376 * We add the dataflow equation
377 * L(A1) = MEET(L(A2), L(A3), L(A4))
378 *
379 * @param s the Phi instruction
380 */
381 void processPhi(Instruction s) {
382 Operand result = Phi.getResult(s);
383 if (!(result instanceof HeapOperand)) {
384 return;
385 }
386 HeapVariable<?> lhs = ((HeapOperand<?>) result).value;
387 DF_LatticeCell A1 = findOrCreateCell(lhs);
388 DF_LatticeCell[] rhs = new DF_LatticeCell[Phi.getNumberOfValues(s)];
389 for (int i = 0; i < rhs.length; i++) {
390 HeapOperand<?> op = (HeapOperand<?>) Phi.getValue(s, i);
391 rhs[i] = findOrCreateCell(op.value);
392 }
393 newEquation(A1, MEET, rhs);
394 }
395
396 /**
397 * Add an equation to the system of the form
398 * L(A1) = updateDef(L(A2), VALNUM(address))
399 *
400 * @param A1 variable in the equation
401 * @param A2 variable in the equation
402 * @param valueNumber value number of the address
403 */
404 void addUpdateObjectDefEquation(HeapVariable<?> A1, HeapVariable<?> A2, int valueNumber) {
405 DF_LatticeCell cell1 = findOrCreateCell(A1);
406 DF_LatticeCell cell2 = findOrCreateCell(A2);
407 UpdateDefObjectOperator op = new UpdateDefObjectOperator(valueNumber);
408 newEquation(cell1, op, cell2);
409 }
410
411 /**
412 * Add an equation to the system of the form
413 * <pre>
414 * L(A1) = updateUse(L(A2), VALNUM(address))
415 * </pre>
416 *
417 * @param A1 variable in the equation
418 * @param A2 variable in the equation
419 * @param valueNumber value number of address
420 */
421 void addUpdateObjectUseEquation(HeapVariable<?> A1, HeapVariable<?> A2, int valueNumber) {
422 DF_LatticeCell cell1 = findOrCreateCell(A1);
423 DF_LatticeCell cell2 = findOrCreateCell(A2);
424 UpdateUseObjectOperator op = new UpdateUseObjectOperator(valueNumber);
425 newEquation(cell1, op, cell2);
426 }
427
428 /**
429 * Add an equation to the system of the form
430 * <pre>
431 * L(A1) = updateDef(L(A2), <VALNUM(array),VALNUM(index)>)
432 * </pre>
433 *
434 * @param A1 variable in the equation
435 * @param A2 variable in the equation
436 * @param array variable in the equation
437 * @param index variable in the equation
438 */
439 void addUpdateArrayDefEquation(HeapVariable<?> A1, HeapVariable<?> A2, Object array, Object index) {
440 DF_LatticeCell cell1 = findOrCreateCell(A1);
441 DF_LatticeCell cell2 = findOrCreateCell(A2);
442 int arrayNumber = valueNumbers.getValueNumber(array);
443 int indexNumber = valueNumbers.getValueNumber(index);
444 UpdateDefArrayOperator op = new UpdateDefArrayOperator(arrayNumber, indexNumber);
445 newEquation(cell1, op, cell2);
446 }
447
448 /**
449 * Add an equation to the system of the form
450 * <pre>
451 * L(A1) = updateUse(L(A2), <VALNUM(array),VALNUM(index)>)
452 * </pre>
453 *
454 * @param A1 variable in the equation
455 * @param A2 variable in the equation
456 * @param array variable in the equation
457 * @param index variable in the equation
458 */
459 void addUpdateArrayUseEquation(HeapVariable<?> A1, HeapVariable<?> A2, Object array, Object index) {
460 DF_LatticeCell cell1 = findOrCreateCell(A1);
461 DF_LatticeCell cell2 = findOrCreateCell(A2);
462 int arrayNumber = valueNumbers.getValueNumber(array);
463 int indexNumber = valueNumbers.getValueNumber(index);
464 UpdateUseArrayOperator op = new UpdateUseArrayOperator(arrayNumber, indexNumber);
465 newEquation(cell1, op, cell2);
466 }
467
468 /**
469 * Represents a MEET function (intersection) over Cells.
470 */
471 static class MeetOperator extends DF_Operator {
472
473 /**
474 * @return "MEET"
475 */
476 public String toString() { return "MEET"; }
477
478 /**
479 * Evaluate a dataflow equation with the MEET operator
480 * @param operands the operands of the dataflow equation
481 * @return true iff the value of the lhs changes
482 */
483 public boolean evaluate(DF_LatticeCell[] operands) {
484 DF_LatticeCell lhs = operands[0];
485 if (lhs instanceof ObjectCell) {
486 return evaluateObjectMeet(operands);
487 } else {
488 return evaluateArrayMeet(operands);
489 }
490 }
491
492 /**
493 * Evaluate a dataflow equation with the MEET operator
494 * for lattice cells representing field heap variables.
495 * @param operands the operands of the dataflow equation
496 * @return true iff the value of the lhs changes
497 */
498 boolean evaluateObjectMeet(DF_LatticeCell[] operands) {
499 ObjectCell lhs = (ObjectCell) operands[0];
500
501 // short-circuit if lhs is already bottom
502 if (lhs.isBOTTOM()) {
503 return false;
504 }
505
506 // short-circuit if any rhs is bottom
507 for (int j = 1; j < operands.length; j++) {
508 ObjectCell r = (ObjectCell) operands[j];
509 if (r.isBOTTOM()) {
510 // from the previous short-circuit, we know lhs was not already bottom, so ...
511 lhs.setBOTTOM();
512 return true;
513 }
514 }
515
516 boolean lhsWasTOP = lhs.isTOP();
517 int[] oldNumbers = null;
518
519 if (!lhsWasTOP) oldNumbers = lhs.copyValueNumbers();
520
521 lhs.clear();
522 // perform the intersections
523 if (operands.length > 1) {
524 int firstNonTopRHS = -1;
525 // find the first RHS lattice cell that is not TOP
526 for (int j = 1; j < operands.length; j++) {
527 ObjectCell r = (ObjectCell) operands[j];
528 if (!r.isTOP()) {
529 firstNonTopRHS = j;
530 break;
531 }
532 }
533 // if we did not find ANY non-top cell, then simply set
534 // lhs to top and return
535 if (firstNonTopRHS == -1) {
536 lhs.setTOP(true);
537 return false;
538 }
539 // if we get here, we found a non-top cell. Start merging
540 // here
541 int[] rhsNumbers = ((ObjectCell) operands[firstNonTopRHS]).copyValueNumbers();
542
543 if (rhsNumbers != null) {
544 for (int v : rhsNumbers) {
545 lhs.add(v);
546 for (int j = firstNonTopRHS + 1; j < operands.length; j++) {
547 ObjectCell r = (ObjectCell) operands[j];
548 if (!r.contains(v)) {
549 lhs.remove(v);
550 break;
551 }
552 }
553 }
554 }
555 }
556 // check if anything has changed
557 if (lhsWasTOP) return true;
558 int[] newNumbers = lhs.copyValueNumbers();
559
560 return ObjectCell.setsDiffer(oldNumbers, newNumbers);
561 }
562
563 /**
564 * Evaluate a dataflow equation with the MEET operator
565 * for lattice cells representing array heap variables.
566 * @param operands the operands of the dataflow equation
567 * @return true iff the value of the lhs changes
568 */
569 boolean evaluateArrayMeet(DF_LatticeCell[] operands) {
570 ArrayCell lhs = (ArrayCell) operands[0];
571
572 // short-circuit if lhs is already bottom
573 if (lhs.isBOTTOM()) {
574 return false;
575 }
576
577 // short-circuit if any rhs is bottom
578 for (int j = 1; j < operands.length; j++) {
579 ArrayCell r = (ArrayCell) operands[j];
580 if (r.isBOTTOM()) {
581 // from the previous short-circuit, we know lhs was not already bottom, so ...
582 lhs.setBOTTOM();
583 return true;
584 }
585 }
586
587 boolean lhsWasTOP = lhs.isTOP();
588 ValueNumberPair[] oldNumbers = null;
589 if (!lhsWasTOP) oldNumbers = lhs.copyValueNumbers();
590
591 lhs.clear();
592 // perform the intersections
593 if (operands.length > 1) {
594 int firstNonTopRHS = -1;
595 // find the first RHS lattice cell that is not TOP
596 for (int j = 1; j < operands.length; j++) {
597 ArrayCell r = (ArrayCell) operands[j];
598 if (!r.isTOP()) {
599 firstNonTopRHS = j;
600 break;
601 }
602 }
603 // if we did not find ANY non-top cell, then simply set
604 // lhs to top and return
605 if (firstNonTopRHS == -1) {
606 lhs.setTOP(true);
607 return false;
608 }
609 // if we get here, we found a non-top cell. Start merging
610 // here
611 ValueNumberPair[] rhsNumbers = ((ArrayCell) operands[firstNonTopRHS]).copyValueNumbers();
612 if (rhsNumbers != null) {
613 for (ValueNumberPair pair : rhsNumbers) {
614 int v1 = pair.v1;
615 int v2 = pair.v2;
616 lhs.add(v1, v2);
617 for (int j = firstNonTopRHS + 1; j < operands.length; j++) {
618 ArrayCell r = (ArrayCell) operands[j];
619 if (!r.contains(v1, v2)) {
620 lhs.remove(v1, v2);
621 break;
622 }
623 }
624 }
625 }
626 }
627 // check if anything has changed
628 if (lhsWasTOP) return true;
629 ValueNumberPair[] newNumbers = lhs.copyValueNumbers();
630
631 return ArrayCell.setsDiffer(oldNumbers, newNumbers);
632 }
633 }
634
635 /**
636 * Represents an UPDATE_DEF function over two ObjectCells.
637 * <p> Given a value number v, this function updates a heap variable
638 * lattice cell to indicate that element at address v is
639 * available, but kills any available indices that are not DD from v
640 */
641 class UpdateDefObjectOperator extends DF_Operator {
642 /**
643 * The value number used in the dataflow equation.
644 */
645 private final int valueNumber;
646
647 /**
648 * @return a String representation
649 */
650 public String toString() { return "UPDATE-DEF<" + valueNumber + ">"; }
651
652 /**
653 * Create an operator with a given value number
654 * @param valueNumber
655 */
656 UpdateDefObjectOperator(int valueNumber) {
657 this.valueNumber = valueNumber;
658 }
659
660 /**
661 * Evaluate the dataflow equation with this operator.
662 * @param operands operands in the dataflow equation
663 * @return true iff the lhs changes from this evaluation
664 */
665 public boolean evaluate(DF_LatticeCell[] operands) {
666 ObjectCell lhs = (ObjectCell) operands[0];
667
668 if (lhs.isBOTTOM()) {
669 return false;
670 }
671
672 ObjectCell rhs = (ObjectCell) operands[1];
673 boolean lhsWasTOP = lhs.isTOP();
674 int[] oldNumbers = null;
675 if (!lhsWasTOP) oldNumbers = lhs.copyValueNumbers();
676 lhs.clear();
677 if (rhs.isTOP()) {
678 throw new OptimizingCompilerException("Unexpected lattice operation");
679 }
680 int[] numbers = rhs.copyValueNumbers();
681 // add all rhs numbers that are DD from valueNumber
682 if (numbers != null) {
683 for (int number : numbers) {
684 if (valueNumbers.DD(number, valueNumber)) {
685 lhs.add(number);
686 }
687 }
688 }
689 // add value number generated by this update
690 lhs.add(valueNumber);
691 // check if anything has changed
692 if (lhsWasTOP) return true;
693 int[] newNumbers = lhs.copyValueNumbers();
694
695 return ObjectCell.setsDiffer(oldNumbers, newNumbers);
696 }
697 }
698
699 /**
700 * Represents an UPDATE_USE function over two ObjectCells.
701 *
702 * <p> Given a value number v, this function updates a heap variable
703 * lattice cell to indicate that element at address v is
704 * available, and doesn't kill any available indices
705 */
706 static class UpdateUseObjectOperator extends DF_Operator {
707 /**
708 * The value number used in the dataflow equation.
709 */
710 private final int valueNumber;
711
712 /**
713 * @return "UPDATE-USE"
714 */
715 public String toString() { return "UPDATE-USE<" + valueNumber + ">"; }
716
717 /**
718 * Create an operator with a given value number
719 * @param valueNumber
720 */
721 UpdateUseObjectOperator(int valueNumber) {
722 this.valueNumber = valueNumber;
723 }
724
725 /**
726 * Evaluate the dataflow equation with this operator.
727 * @param operands operands in the dataflow equation
728 * @return true iff the lhs changes from this evaluation
729 */
730 public boolean evaluate(DF_LatticeCell[] operands) {
731 ObjectCell lhs = (ObjectCell) operands[0];
732
733 if (lhs.isBOTTOM()) {
734 return false;
735 }
736
737 ObjectCell rhs = (ObjectCell) operands[1];
738 int[] oldNumbers = null;
739 boolean lhsWasTOP = lhs.isTOP();
740 if (!lhsWasTOP) oldNumbers = lhs.copyValueNumbers();
741 lhs.clear();
742 if (rhs.isTOP()) {
743 throw new OptimizingCompilerException("Unexpected lattice operation");
744 }
745 int[] numbers = rhs.copyValueNumbers();
746 // add all rhs numbers
747 if (numbers != null) {
748 for (int number : numbers) {
749 lhs.add(number);
750 }
751 }
752 // add value number generated by this update
753 lhs.add(valueNumber);
754 // check if anything has changed
755 if (lhsWasTOP) return true;
756 int[] newNumbers = lhs.copyValueNumbers();
757
758 return ObjectCell.setsDiffer(oldNumbers, newNumbers);
759 }
760 }
761
762 /**
763 * Represents an UPDATE_DEF function over two ArrayCells.
764 * Given two value numbers v1, v2, this function updates a heap variable
765 * lattice cell to indicate that element for array v1 at address v2 is
766 * available, but kills any available indices that are not DD from <v1,v2>
767 */
768 class UpdateDefArrayOperator extends DF_Operator {
769 /**
770 * The value number pair used in the dataflow equation.
771 */
772 private final ValueNumberPair v;
773
774 /**
775 * @return "UPDATE-DEF"
776 */
777 public String toString() { return "UPDATE-DEF<" + v + ">"; }
778
779 /**
780 * Create an operator with a given value number pair
781 * @param v1 first value number in the pari
782 * @param v2 first value number in the pari
783 */
784 UpdateDefArrayOperator(int v1, int v2) {
785 v = new ValueNumberPair(v1, v2);
786 }
787
788 /**
789 * Evaluate the dataflow equation with this operator.
790 * @param operands operands in the dataflow equation
791 * @return true iff the lhs changes from this evaluation
792 */
793 public boolean evaluate(DF_LatticeCell[] operands) {
794 ArrayCell lhs = (ArrayCell) operands[0];
795
796 if (lhs.isBOTTOM()) {
797 return false;
798 }
799 ArrayCell rhs = (ArrayCell) operands[1];
800 ValueNumberPair[] oldNumbers = null;
801 boolean lhsWasTOP = lhs.isTOP();
802 if (!lhsWasTOP) oldNumbers = lhs.copyValueNumbers();
803 lhs.clear();
804 if (rhs.isTOP()) {
805 throw new OptimizingCompilerException("Unexpected lattice operation");
806 }
807 ValueNumberPair[] numbers = rhs.copyValueNumbers();
808 // add all rhs pairs that are DD from either v.v1 or v.v2
809 if (numbers != null) {
810 for (ValueNumberPair number : numbers) {
811 if (valueNumbers.DD(number.v1, v.v1)) {
812 lhs.add(number.v1, number.v2);
813 } else if (valueNumbers.DD(number.v2, v.v2)) {
814 lhs.add(number.v1, number.v2);
815 }
816 }
817 }
818 // add the value number pair generated by this update
819 lhs.add(v.v1, v.v2);
820 // check if anything has changed
821 if (lhsWasTOP) {
822 return true;
823 }
824 ValueNumberPair[] newNumbers = lhs.copyValueNumbers();
825
826 return ArrayCell.setsDiffer(oldNumbers, newNumbers);
827 }
828 }
829
830 /**
831 * Represents an UPDATE_USE function over two ArrayCells.
832 *
833 * <p> Given two value numbers v1, v2, this function updates a heap variable
834 * lattice cell to indicate that element at array v1 index v2 is
835 * available, and doesn't kill any available indices
836 */
837 static class UpdateUseArrayOperator extends DF_Operator {
838 /**
839 * The value number pair used in the dataflow equation.
840 */
841 private final ValueNumberPair v;
842
843 /**
844 * @return "UPDATE-USE"
845 */
846 public String toString() { return "UPDATE-USE<" + v + ">"; }
847
848 /**
849 * Create an operator with a given value number pair
850 * @param v1 first value number in the pair
851 * @param v2 second value number in the pair
852 */
853 UpdateUseArrayOperator(int v1, int v2) {
854 v = new ValueNumberPair(v1, v2);
855 }
856
857 /**
858 * Evaluate the dataflow equation with this operator.
859 * @param operands operands in the dataflow equation
860 * @return true iff the lhs changes from this evaluation
861 */
862 public boolean evaluate(DF_LatticeCell[] operands) {
863 ArrayCell lhs = (ArrayCell) operands[0];
864
865 if (lhs.isBOTTOM()) {
866 return false;
867 }
868
869 ArrayCell rhs = (ArrayCell) operands[1];
870 ValueNumberPair[] oldNumbers = null;
871 boolean lhsWasTOP = lhs.isTOP();
872 if (!lhsWasTOP) oldNumbers = lhs.copyValueNumbers();
873 lhs.clear();
874 if (rhs.isTOP()) {
875 throw new OptimizingCompilerException("Unexpected lattice operation");
876 }
877 ValueNumberPair[] numbers = rhs.copyValueNumbers();
878 // add all rhs numbers
879 if (numbers != null) {
880 for (ValueNumberPair number : numbers) {
881 lhs.add(number.v1, number.v2);
882 }
883 }
884 // add value number generated by this update
885 lhs.add(v.v1, v.v2);
886 // check if anything has changed
887 if (lhsWasTOP) {
888 return true;
889 }
890 ValueNumberPair[] newNumbers = lhs.copyValueNumbers();
891
892 return ArrayCell.setsDiffer(oldNumbers, newNumbers);
893 }
894 }
895 }