17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.nodes;
24
25 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_2;
26 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_2;
27
28 import java.util.ArrayList;
29 import java.util.Arrays;
30 import java.util.Iterator;
31 import java.util.List;
32
33 import org.graalvm.compiler.core.common.calc.Condition;
34 import org.graalvm.compiler.core.common.type.IntegerStamp;
35 import org.graalvm.compiler.core.common.type.Stamp;
36 import org.graalvm.compiler.core.common.type.StampFactory;
37 import org.graalvm.compiler.debug.Debug;
38 import org.graalvm.compiler.debug.DebugCounter;
39 import org.graalvm.compiler.debug.GraalError;
40 import org.graalvm.compiler.graph.Node;
41 import org.graalvm.compiler.graph.NodeClass;
42 import org.graalvm.compiler.graph.iterators.NodeIterable;
43 import org.graalvm.compiler.graph.spi.Canonicalizable;
44 import org.graalvm.compiler.graph.spi.Simplifiable;
45 import org.graalvm.compiler.graph.spi.SimplifierTool;
46 import org.graalvm.compiler.nodeinfo.InputType;
47 import org.graalvm.compiler.nodeinfo.NodeInfo;
48 import org.graalvm.compiler.nodes.calc.CompareNode;
49 import org.graalvm.compiler.nodes.calc.ConditionalNode;
50 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
51 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
52 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
53 import org.graalvm.compiler.nodes.calc.IsNullNode;
54 import org.graalvm.compiler.nodes.calc.NormalizeCompareNode;
55 import org.graalvm.compiler.nodes.java.InstanceOfNode;
56 import org.graalvm.compiler.nodes.spi.LIRLowerable;
57 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
58 import org.graalvm.compiler.nodes.util.GraphUtil;
59 import org.graalvm.util.EconomicMap;
60 import org.graalvm.util.Equivalence;
61
62 import jdk.vm.ci.meta.Constant;
63 import jdk.vm.ci.meta.ConstantReflectionProvider;
64 import jdk.vm.ci.meta.JavaConstant;
65 import jdk.vm.ci.meta.JavaKind;
66 import jdk.vm.ci.meta.PrimitiveConstant;
67
68 /**
69 * The {@code IfNode} represents a branch that can go one of two directions depending on the outcome
70 * of a comparison.
71 */
72 @NodeInfo(cycles = CYCLES_2, size = SIZE_2, sizeRationale = "2 jmps")
73 public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable {
74 public static final NodeClass<IfNode> TYPE = NodeClass.create(IfNode.class);
75
76 private static final DebugCounter CORRECTED_PROBABILITIES = Debug.counter("CorrectedProbabilities");
77
78 @Successor AbstractBeginNode trueSuccessor;
79 @Successor AbstractBeginNode falseSuccessor;
80 @Input(InputType.Condition) LogicNode condition;
81 protected double trueSuccessorProbability;
82
83 public LogicNode condition() {
84 return condition;
85 }
86
87 public void setCondition(LogicNode x) {
88 updateUsages(condition, x);
89 condition = x;
90 }
91
92 public IfNode(LogicNode condition, FixedNode trueSuccessor, FixedNode falseSuccessor, double trueSuccessorProbability) {
93 this(condition, BeginNode.begin(trueSuccessor), BeginNode.begin(falseSuccessor), trueSuccessorProbability);
94 }
95
96 public IfNode(LogicNode condition, AbstractBeginNode trueSuccessor, AbstractBeginNode falseSuccessor, double trueSuccessorProbability) {
162 public boolean verify() {
163 assertTrue(condition() != null, "missing condition");
164 assertTrue(trueSuccessor() != null, "missing trueSuccessor");
165 assertTrue(falseSuccessor() != null, "missing falseSuccessor");
166 return super.verify();
167 }
168
169 public void eliminateNegation() {
170 AbstractBeginNode oldTrueSuccessor = trueSuccessor;
171 AbstractBeginNode oldFalseSuccessor = falseSuccessor;
172 trueSuccessor = oldFalseSuccessor;
173 falseSuccessor = oldTrueSuccessor;
174 trueSuccessorProbability = 1 - trueSuccessorProbability;
175 setCondition(((LogicNegationNode) condition).getValue());
176 }
177
178 @Override
179 public void simplify(SimplifierTool tool) {
180 if (trueSuccessor().next() instanceof DeoptimizeNode) {
181 if (trueSuccessorProbability != 0) {
182 CORRECTED_PROBABILITIES.increment();
183 trueSuccessorProbability = 0;
184 }
185 } else if (falseSuccessor().next() instanceof DeoptimizeNode) {
186 if (trueSuccessorProbability != 1) {
187 CORRECTED_PROBABILITIES.increment();
188 trueSuccessorProbability = 1;
189 }
190 }
191
192 if (condition() instanceof LogicNegationNode) {
193 eliminateNegation();
194 }
195 if (condition() instanceof LogicConstantNode) {
196 LogicConstantNode c = (LogicConstantNode) condition();
197 if (c.getValue()) {
198 tool.deleteBranch(falseSuccessor());
199 tool.addToWorkList(trueSuccessor());
200 graph().removeSplit(this, trueSuccessor());
201 } else {
202 tool.deleteBranch(trueSuccessor());
203 tool.addToWorkList(falseSuccessor());
204 graph().removeSplit(this, falseSuccessor());
205 }
206 return;
207 }
436 }
437 } else if (next1 instanceof LoopExitNode && next2 instanceof LoopExitNode) {
438 LoopExitNode exit1 = (LoopExitNode) next1;
439 LoopExitNode exit2 = (LoopExitNode) next2;
440 if (exit1.loopBegin() == exit2.loopBegin() && exit1.stateAfter() == exit2.stateAfter() && exit1.stateAfter() == null && sameDestination(exit1, exit2)) {
441 // Exit the same loop and end up at the same place.
442 return true;
443 }
444 } else if (next1 instanceof ReturnNode && next2 instanceof ReturnNode) {
445 ReturnNode exit1 = (ReturnNode) next1;
446 ReturnNode exit2 = (ReturnNode) next2;
447 if (exit1.result() == exit2.result()) {
448 // Exit the same loop and end up at the same place.
449 return true;
450 }
451 }
452 return false;
453 }
454
455 private static boolean prepareForSwap(ConstantReflectionProvider constantReflection, LogicNode a, LogicNode b) {
456 if (a instanceof InstanceOfNode) {
457 InstanceOfNode instanceOfA = (InstanceOfNode) a;
458 if (b instanceof IsNullNode) {
459 IsNullNode isNullNode = (IsNullNode) b;
460 if (isNullNode.getValue() == instanceOfA.getValue()) {
461 Debug.log("Can swap instanceof and isnull if");
462 return true;
463 }
464 } else if (b instanceof InstanceOfNode) {
465 InstanceOfNode instanceOfB = (InstanceOfNode) b;
466 if (instanceOfA.getValue() == instanceOfB.getValue() && !instanceOfA.type().getType().isInterface() && !instanceOfB.type().getType().isInterface() &&
467 !instanceOfA.type().getType().isAssignableFrom(instanceOfB.type().getType()) && !instanceOfB.type().getType().isAssignableFrom(instanceOfA.type().getType())) {
468 // Two instanceof on the same value with mutually exclusive types.
469 Debug.log("Can swap instanceof for types %s and %s", instanceOfA.type(), instanceOfB.type());
470 return true;
471 }
472 }
473 } else if (a instanceof CompareNode) {
474 CompareNode compareA = (CompareNode) a;
475 Condition conditionA = compareA.condition();
476 if (compareA.unorderedIsTrue()) {
477 return false;
478 }
479 if (b instanceof CompareNode) {
480 CompareNode compareB = (CompareNode) b;
481 if (compareA == compareB) {
482 Debug.log("Same conditions => do not swap and leave the work for global value numbering.");
483 return false;
484 }
485 if (compareB.unorderedIsTrue()) {
486 return false;
487 }
488 Condition comparableCondition = null;
489 Condition conditionB = compareB.condition();
490 if (compareB.getX() == compareA.getX() && compareB.getY() == compareA.getY()) {
491 comparableCondition = conditionB;
492 } else if (compareB.getX() == compareA.getY() && compareB.getY() == compareA.getX()) {
493 comparableCondition = conditionB.mirror();
494 }
495
496 if (comparableCondition != null) {
497 Condition combined = conditionA.join(comparableCondition);
498 if (combined == null) {
499 // The two conditions are disjoint => can reorder.
500 Debug.log("Can swap disjoint coditions on same values: %s and %s", conditionA, comparableCondition);
501 return true;
502 }
503 } else if (conditionA == Condition.EQ && conditionB == Condition.EQ) {
504 boolean canSwap = false;
505 if ((compareA.getX() == compareB.getX() && valuesDistinct(constantReflection, compareA.getY(), compareB.getY()))) {
506 canSwap = true;
507 } else if ((compareA.getX() == compareB.getY() && valuesDistinct(constantReflection, compareA.getY(), compareB.getX()))) {
508 canSwap = true;
509 } else if ((compareA.getY() == compareB.getX() && valuesDistinct(constantReflection, compareA.getX(), compareB.getY()))) {
510 canSwap = true;
511 } else if ((compareA.getY() == compareB.getY() && valuesDistinct(constantReflection, compareA.getX(), compareB.getX()))) {
512 canSwap = true;
513 }
514
515 if (canSwap) {
516 Debug.log("Can swap equality condition with one shared and one disjoint value.");
517 return true;
518 }
519 }
520 }
521 }
522
523 return false;
524 }
525
526 private static boolean valuesDistinct(ConstantReflectionProvider constantReflection, ValueNode a, ValueNode b) {
527 if (a.isConstant() && b.isConstant()) {
528 Boolean equal = constantReflection.constantEquals(a.asConstant(), b.asConstant());
529 if (equal != null) {
530 return !equal.booleanValue();
531 }
532 }
533
534 Stamp stampA = a.stamp();
535 Stamp stampB = b.stamp();
536 return stampA.alwaysDistinct(stampB);
|
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.nodes;
24
25 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_2;
26 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_2;
27
28 import java.util.ArrayList;
29 import java.util.Arrays;
30 import java.util.Iterator;
31 import java.util.List;
32
33 import org.graalvm.compiler.core.common.calc.Condition;
34 import org.graalvm.compiler.core.common.type.IntegerStamp;
35 import org.graalvm.compiler.core.common.type.Stamp;
36 import org.graalvm.compiler.core.common.type.StampFactory;
37 import org.graalvm.compiler.debug.CounterKey;
38 import org.graalvm.compiler.debug.DebugContext;
39 import org.graalvm.compiler.debug.GraalError;
40 import org.graalvm.compiler.graph.Node;
41 import org.graalvm.compiler.graph.NodeClass;
42 import org.graalvm.compiler.graph.iterators.NodeIterable;
43 import org.graalvm.compiler.graph.spi.Canonicalizable;
44 import org.graalvm.compiler.graph.spi.Simplifiable;
45 import org.graalvm.compiler.graph.spi.SimplifierTool;
46 import org.graalvm.compiler.nodeinfo.InputType;
47 import org.graalvm.compiler.nodeinfo.NodeInfo;
48 import org.graalvm.compiler.nodes.calc.CompareNode;
49 import org.graalvm.compiler.nodes.calc.ConditionalNode;
50 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
51 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
52 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
53 import org.graalvm.compiler.nodes.calc.IsNullNode;
54 import org.graalvm.compiler.nodes.calc.NormalizeCompareNode;
55 import org.graalvm.compiler.nodes.java.InstanceOfNode;
56 import org.graalvm.compiler.nodes.spi.LIRLowerable;
57 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
58 import org.graalvm.compiler.nodes.util.GraphUtil;
59 import org.graalvm.util.EconomicMap;
60 import org.graalvm.util.Equivalence;
61
62 import jdk.vm.ci.meta.Constant;
63 import jdk.vm.ci.meta.ConstantReflectionProvider;
64 import jdk.vm.ci.meta.JavaConstant;
65 import jdk.vm.ci.meta.JavaKind;
66 import jdk.vm.ci.meta.PrimitiveConstant;
67
68 /**
69 * The {@code IfNode} represents a branch that can go one of two directions depending on the outcome
70 * of a comparison.
71 */
72 @NodeInfo(cycles = CYCLES_2, size = SIZE_2, sizeRationale = "2 jmps")
73 public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable {
74 public static final NodeClass<IfNode> TYPE = NodeClass.create(IfNode.class);
75
76 private static final CounterKey CORRECTED_PROBABILITIES = DebugContext.counter("CorrectedProbabilities");
77
78 @Successor AbstractBeginNode trueSuccessor;
79 @Successor AbstractBeginNode falseSuccessor;
80 @Input(InputType.Condition) LogicNode condition;
81 protected double trueSuccessorProbability;
82
83 public LogicNode condition() {
84 return condition;
85 }
86
87 public void setCondition(LogicNode x) {
88 updateUsages(condition, x);
89 condition = x;
90 }
91
92 public IfNode(LogicNode condition, FixedNode trueSuccessor, FixedNode falseSuccessor, double trueSuccessorProbability) {
93 this(condition, BeginNode.begin(trueSuccessor), BeginNode.begin(falseSuccessor), trueSuccessorProbability);
94 }
95
96 public IfNode(LogicNode condition, AbstractBeginNode trueSuccessor, AbstractBeginNode falseSuccessor, double trueSuccessorProbability) {
162 public boolean verify() {
163 assertTrue(condition() != null, "missing condition");
164 assertTrue(trueSuccessor() != null, "missing trueSuccessor");
165 assertTrue(falseSuccessor() != null, "missing falseSuccessor");
166 return super.verify();
167 }
168
169 public void eliminateNegation() {
170 AbstractBeginNode oldTrueSuccessor = trueSuccessor;
171 AbstractBeginNode oldFalseSuccessor = falseSuccessor;
172 trueSuccessor = oldFalseSuccessor;
173 falseSuccessor = oldTrueSuccessor;
174 trueSuccessorProbability = 1 - trueSuccessorProbability;
175 setCondition(((LogicNegationNode) condition).getValue());
176 }
177
178 @Override
179 public void simplify(SimplifierTool tool) {
180 if (trueSuccessor().next() instanceof DeoptimizeNode) {
181 if (trueSuccessorProbability != 0) {
182 CORRECTED_PROBABILITIES.increment(getDebug());
183 trueSuccessorProbability = 0;
184 }
185 } else if (falseSuccessor().next() instanceof DeoptimizeNode) {
186 if (trueSuccessorProbability != 1) {
187 CORRECTED_PROBABILITIES.increment(getDebug());
188 trueSuccessorProbability = 1;
189 }
190 }
191
192 if (condition() instanceof LogicNegationNode) {
193 eliminateNegation();
194 }
195 if (condition() instanceof LogicConstantNode) {
196 LogicConstantNode c = (LogicConstantNode) condition();
197 if (c.getValue()) {
198 tool.deleteBranch(falseSuccessor());
199 tool.addToWorkList(trueSuccessor());
200 graph().removeSplit(this, trueSuccessor());
201 } else {
202 tool.deleteBranch(trueSuccessor());
203 tool.addToWorkList(falseSuccessor());
204 graph().removeSplit(this, falseSuccessor());
205 }
206 return;
207 }
436 }
437 } else if (next1 instanceof LoopExitNode && next2 instanceof LoopExitNode) {
438 LoopExitNode exit1 = (LoopExitNode) next1;
439 LoopExitNode exit2 = (LoopExitNode) next2;
440 if (exit1.loopBegin() == exit2.loopBegin() && exit1.stateAfter() == exit2.stateAfter() && exit1.stateAfter() == null && sameDestination(exit1, exit2)) {
441 // Exit the same loop and end up at the same place.
442 return true;
443 }
444 } else if (next1 instanceof ReturnNode && next2 instanceof ReturnNode) {
445 ReturnNode exit1 = (ReturnNode) next1;
446 ReturnNode exit2 = (ReturnNode) next2;
447 if (exit1.result() == exit2.result()) {
448 // Exit the same loop and end up at the same place.
449 return true;
450 }
451 }
452 return false;
453 }
454
455 private static boolean prepareForSwap(ConstantReflectionProvider constantReflection, LogicNode a, LogicNode b) {
456 DebugContext debug = a.getDebug();
457 if (a instanceof InstanceOfNode) {
458 InstanceOfNode instanceOfA = (InstanceOfNode) a;
459 if (b instanceof IsNullNode) {
460 IsNullNode isNullNode = (IsNullNode) b;
461 if (isNullNode.getValue() == instanceOfA.getValue()) {
462 debug.log("Can swap instanceof and isnull if");
463 return true;
464 }
465 } else if (b instanceof InstanceOfNode) {
466 InstanceOfNode instanceOfB = (InstanceOfNode) b;
467 if (instanceOfA.getValue() == instanceOfB.getValue() && !instanceOfA.type().getType().isInterface() && !instanceOfB.type().getType().isInterface() &&
468 !instanceOfA.type().getType().isAssignableFrom(instanceOfB.type().getType()) && !instanceOfB.type().getType().isAssignableFrom(instanceOfA.type().getType())) {
469 // Two instanceof on the same value with mutually exclusive types.
470 debug.log("Can swap instanceof for types %s and %s", instanceOfA.type(), instanceOfB.type());
471 return true;
472 }
473 }
474 } else if (a instanceof CompareNode) {
475 CompareNode compareA = (CompareNode) a;
476 Condition conditionA = compareA.condition();
477 if (compareA.unorderedIsTrue()) {
478 return false;
479 }
480 if (b instanceof CompareNode) {
481 CompareNode compareB = (CompareNode) b;
482 if (compareA == compareB) {
483 debug.log("Same conditions => do not swap and leave the work for global value numbering.");
484 return false;
485 }
486 if (compareB.unorderedIsTrue()) {
487 return false;
488 }
489 Condition comparableCondition = null;
490 Condition conditionB = compareB.condition();
491 if (compareB.getX() == compareA.getX() && compareB.getY() == compareA.getY()) {
492 comparableCondition = conditionB;
493 } else if (compareB.getX() == compareA.getY() && compareB.getY() == compareA.getX()) {
494 comparableCondition = conditionB.mirror();
495 }
496
497 if (comparableCondition != null) {
498 Condition combined = conditionA.join(comparableCondition);
499 if (combined == null) {
500 // The two conditions are disjoint => can reorder.
501 debug.log("Can swap disjoint coditions on same values: %s and %s", conditionA, comparableCondition);
502 return true;
503 }
504 } else if (conditionA == Condition.EQ && conditionB == Condition.EQ) {
505 boolean canSwap = false;
506 if ((compareA.getX() == compareB.getX() && valuesDistinct(constantReflection, compareA.getY(), compareB.getY()))) {
507 canSwap = true;
508 } else if ((compareA.getX() == compareB.getY() && valuesDistinct(constantReflection, compareA.getY(), compareB.getX()))) {
509 canSwap = true;
510 } else if ((compareA.getY() == compareB.getX() && valuesDistinct(constantReflection, compareA.getX(), compareB.getY()))) {
511 canSwap = true;
512 } else if ((compareA.getY() == compareB.getY() && valuesDistinct(constantReflection, compareA.getX(), compareB.getX()))) {
513 canSwap = true;
514 }
515
516 if (canSwap) {
517 debug.log("Can swap equality condition with one shared and one disjoint value.");
518 return true;
519 }
520 }
521 }
522 }
523
524 return false;
525 }
526
527 private static boolean valuesDistinct(ConstantReflectionProvider constantReflection, ValueNode a, ValueNode b) {
528 if (a.isConstant() && b.isConstant()) {
529 Boolean equal = constantReflection.constantEquals(a.asConstant(), b.asConstant());
530 if (equal != null) {
531 return !equal.booleanValue();
532 }
533 }
534
535 Stamp stampA = a.stamp();
536 Stamp stampB = b.stamp();
537 return stampA.alwaysDistinct(stampB);
|