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