13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
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_1;
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 jdk.vm.ci.meta.MetaAccessProvider;
34 import jdk.vm.ci.meta.ResolvedJavaType;
35 import org.graalvm.compiler.core.common.calc.Condition;
36 import org.graalvm.compiler.core.common.type.IntegerStamp;
37 import org.graalvm.compiler.core.common.type.Stamp;
38 import org.graalvm.compiler.core.common.type.StampFactory;
39 import org.graalvm.compiler.debug.CounterKey;
40 import org.graalvm.compiler.debug.DebugContext;
41 import org.graalvm.compiler.debug.GraalError;
42 import org.graalvm.compiler.graph.Node;
43 import org.graalvm.compiler.graph.NodeClass;
44 import org.graalvm.compiler.graph.iterators.NodeIterable;
45 import org.graalvm.compiler.graph.spi.Canonicalizable;
46 import org.graalvm.compiler.graph.spi.Simplifiable;
47 import org.graalvm.compiler.graph.spi.SimplifierTool;
48 import org.graalvm.compiler.nodeinfo.InputType;
49 import org.graalvm.compiler.nodeinfo.NodeInfo;
50 import org.graalvm.compiler.nodes.calc.CompareNode;
51 import org.graalvm.compiler.nodes.calc.ConditionalNode;
52 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
53 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
54 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
55 import org.graalvm.compiler.nodes.calc.IsNullNode;
56 import org.graalvm.compiler.nodes.calc.NormalizeCompareNode;
57 import org.graalvm.compiler.nodes.calc.ObjectEqualsNode;
58 import org.graalvm.compiler.nodes.extended.UnboxNode;
59 import org.graalvm.compiler.nodes.java.InstanceOfNode;
60 import org.graalvm.compiler.nodes.java.LoadFieldNode;
61 import org.graalvm.compiler.nodes.spi.LIRLowerable;
62 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
63 import org.graalvm.compiler.nodes.util.GraphUtil;
64 import org.graalvm.util.EconomicMap;
65 import org.graalvm.util.Equivalence;
66
67 import jdk.vm.ci.meta.Constant;
68 import jdk.vm.ci.meta.JavaConstant;
69 import jdk.vm.ci.meta.JavaKind;
70 import jdk.vm.ci.meta.PrimitiveConstant;
71
72 /**
73 * The {@code IfNode} represents a branch that can go one of two directions depending on the outcome
74 * of a comparison.
75 */
76 @NodeInfo(cycles = CYCLES_1, size = SIZE_2, sizeRationale = "2 jmps")
77 public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable {
78 public static final NodeClass<IfNode> TYPE = NodeClass.create(IfNode.class);
79
80 private static final CounterKey CORRECTED_PROBABILITIES = DebugContext.counter("CorrectedProbabilities");
81
82 @Successor AbstractBeginNode trueSuccessor;
83 @Successor AbstractBeginNode falseSuccessor;
84 @Input(InputType.Condition) LogicNode condition;
85 protected double trueSuccessorProbability;
86
87 public LogicNode condition() {
88 return condition;
89 }
90
399 return false;
400 }
401
402 if (trueSuccessor().anchored().isNotEmpty() || falseSuccessor().anchored().isNotEmpty()) {
403 return false;
404 }
405
406 PhiNode phi = merge.phis().first();
407 ValueNode falseValue = phi.valueAt(falseEnd);
408 ValueNode trueValue = phi.valueAt(trueEnd);
409
410 NodeView view = NodeView.from(tool);
411 ValueNode result = ConditionalNode.canonicalizeConditional(condition, trueValue, falseValue, phi.stamp(view), view);
412 if (result != null) {
413 /*
414 * canonicalizeConditional returns possibly new nodes so add them to the graph.
415 */
416 if (result.graph() == null) {
417 result = graph().addOrUniqueWithInputs(result);
418 }
419 /*
420 * This optimization can be performed even if multiple values merge at this phi
421 * since the two inputs get simplified into one.
422 */
423 phi.setValueAt(trueEnd, result);
424 removeThroughFalseBranch(tool, merge);
425 return true;
426 }
427 }
428
429 return false;
430 }
431
432 private void pushNodesThroughIf(SimplifierTool tool) {
433 assert trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages();
434 // push similar nodes upwards through the if, thereby deduplicating them
435 do {
436 AbstractBeginNode trueSucc = trueSuccessor();
437 AbstractBeginNode falseSucc = falseSuccessor();
438 if (trueSucc instanceof BeginNode && falseSucc instanceof BeginNode && trueSucc.next() instanceof FixedWithNextNode && falseSucc.next() instanceof FixedWithNextNode) {
681 for (PhiNode phi : merge.phis()) {
682 ValueNode trueValue = phi.valueAt(trueEnd);
683 ValueNode falseValue = phi.valueAt(falseEnd);
684 if (trueValue != falseValue) {
685 distinct++;
686 singlePhi = phi;
687 }
688 }
689 if (distinct == 0) {
690 /*
691 * Multiple phis but merging same values for true and false, so simply delete
692 * the path
693 */
694 removeThroughFalseBranch(tool, merge);
695 return true;
696 } else if (distinct == 1) {
697 ValueNode trueValue = singlePhi.valueAt(trueEnd);
698 ValueNode falseValue = singlePhi.valueAt(falseEnd);
699 ValueNode conditional = canonicalizeConditionalCascade(tool, trueValue, falseValue);
700 if (conditional != null) {
701 singlePhi.setValueAt(trueEnd, conditional);
702 removeThroughFalseBranch(tool, merge);
703 return true;
704 }
705 }
706 }
707 }
708 if (trueSuccessor().next() instanceof ReturnNode && falseSuccessor().next() instanceof ReturnNode) {
709 ReturnNode trueEnd = (ReturnNode) trueSuccessor().next();
710 ReturnNode falseEnd = (ReturnNode) falseSuccessor().next();
711 ValueNode trueValue = trueEnd.result();
712 ValueNode falseValue = falseEnd.result();
713 ValueNode value = null;
714 if (trueValue != null) {
715 if (trueValue == falseValue) {
716 value = trueValue;
717 } else {
718 value = canonicalizeConditionalCascade(tool, trueValue, falseValue);
719 if (value == null) {
720 return false;
721 }
722 }
723 }
724 ReturnNode newReturn = graph().add(new ReturnNode(value));
725 replaceAtPredecessor(newReturn);
726 GraphUtil.killCFG(this);
727 return true;
728 }
729 return false;
730 }
731
732 protected void removeThroughFalseBranch(SimplifierTool tool, AbstractMergeNode merge) {
733 AbstractBeginNode trueBegin = trueSuccessor();
734 LogicNode conditionNode = condition();
735 graph().removeSplitPropagate(this, trueBegin);
736 tool.addToWorkList(trueBegin);
737 if (conditionNode != null) {
738 GraphUtil.tryKillUnused(conditionNode);
739 }
740 if (merge.isAlive() && merge.forwardEndCount() > 1) {
741 for (FixedNode end : merge.forwardEnds()) {
742 Node cur = end;
743 while (cur != null && cur.predecessor() instanceof BeginNode) {
744 cur = cur.predecessor();
745 }
746 if (cur != null && cur.predecessor() instanceof IfNode) {
747 tool.addToWorkList(cur.predecessor());
748 }
749 }
750 }
751 }
|
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
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_1;
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.calc.ObjectEqualsNode;
56 import org.graalvm.compiler.nodes.extended.UnboxNode;
57 import org.graalvm.compiler.nodes.java.InstanceOfNode;
58 import org.graalvm.compiler.nodes.java.LoadFieldNode;
59 import org.graalvm.compiler.nodes.spi.LIRLowerable;
60 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
61 import org.graalvm.compiler.nodes.util.GraphUtil;
62 import org.graalvm.util.EconomicMap;
63 import org.graalvm.util.Equivalence;
64
65 import jdk.vm.ci.meta.Constant;
66 import jdk.vm.ci.meta.JavaConstant;
67 import jdk.vm.ci.meta.JavaKind;
68 import jdk.vm.ci.meta.MetaAccessProvider;
69 import jdk.vm.ci.meta.PrimitiveConstant;
70 import jdk.vm.ci.meta.ResolvedJavaType;
71
72 /**
73 * The {@code IfNode} represents a branch that can go one of two directions depending on the outcome
74 * of a comparison.
75 */
76 @NodeInfo(cycles = CYCLES_1, size = SIZE_2, sizeRationale = "2 jmps")
77 public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable {
78 public static final NodeClass<IfNode> TYPE = NodeClass.create(IfNode.class);
79
80 private static final CounterKey CORRECTED_PROBABILITIES = DebugContext.counter("CorrectedProbabilities");
81
82 @Successor AbstractBeginNode trueSuccessor;
83 @Successor AbstractBeginNode falseSuccessor;
84 @Input(InputType.Condition) LogicNode condition;
85 protected double trueSuccessorProbability;
86
87 public LogicNode condition() {
88 return condition;
89 }
90
399 return false;
400 }
401
402 if (trueSuccessor().anchored().isNotEmpty() || falseSuccessor().anchored().isNotEmpty()) {
403 return false;
404 }
405
406 PhiNode phi = merge.phis().first();
407 ValueNode falseValue = phi.valueAt(falseEnd);
408 ValueNode trueValue = phi.valueAt(trueEnd);
409
410 NodeView view = NodeView.from(tool);
411 ValueNode result = ConditionalNode.canonicalizeConditional(condition, trueValue, falseValue, phi.stamp(view), view);
412 if (result != null) {
413 /*
414 * canonicalizeConditional returns possibly new nodes so add them to the graph.
415 */
416 if (result.graph() == null) {
417 result = graph().addOrUniqueWithInputs(result);
418 }
419 result = proxyReplacement(result);
420 /*
421 * This optimization can be performed even if multiple values merge at this phi
422 * since the two inputs get simplified into one.
423 */
424 phi.setValueAt(trueEnd, result);
425 removeThroughFalseBranch(tool, merge);
426 return true;
427 }
428 }
429
430 return false;
431 }
432
433 private void pushNodesThroughIf(SimplifierTool tool) {
434 assert trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages();
435 // push similar nodes upwards through the if, thereby deduplicating them
436 do {
437 AbstractBeginNode trueSucc = trueSuccessor();
438 AbstractBeginNode falseSucc = falseSuccessor();
439 if (trueSucc instanceof BeginNode && falseSucc instanceof BeginNode && trueSucc.next() instanceof FixedWithNextNode && falseSucc.next() instanceof FixedWithNextNode) {
682 for (PhiNode phi : merge.phis()) {
683 ValueNode trueValue = phi.valueAt(trueEnd);
684 ValueNode falseValue = phi.valueAt(falseEnd);
685 if (trueValue != falseValue) {
686 distinct++;
687 singlePhi = phi;
688 }
689 }
690 if (distinct == 0) {
691 /*
692 * Multiple phis but merging same values for true and false, so simply delete
693 * the path
694 */
695 removeThroughFalseBranch(tool, merge);
696 return true;
697 } else if (distinct == 1) {
698 ValueNode trueValue = singlePhi.valueAt(trueEnd);
699 ValueNode falseValue = singlePhi.valueAt(falseEnd);
700 ValueNode conditional = canonicalizeConditionalCascade(tool, trueValue, falseValue);
701 if (conditional != null) {
702 conditional = proxyReplacement(conditional);
703 singlePhi.setValueAt(trueEnd, conditional);
704 removeThroughFalseBranch(tool, merge);
705 return true;
706 }
707 }
708 }
709 }
710 if (trueSuccessor().next() instanceof ReturnNode && falseSuccessor().next() instanceof ReturnNode) {
711 ReturnNode trueEnd = (ReturnNode) trueSuccessor().next();
712 ReturnNode falseEnd = (ReturnNode) falseSuccessor().next();
713 ValueNode trueValue = trueEnd.result();
714 ValueNode falseValue = falseEnd.result();
715 ValueNode value = null;
716 if (trueValue != null) {
717 if (trueValue == falseValue) {
718 value = trueValue;
719 } else {
720 value = canonicalizeConditionalCascade(tool, trueValue, falseValue);
721 if (value == null) {
722 return false;
723 }
724 }
725 }
726 ReturnNode newReturn = graph().add(new ReturnNode(value));
727 replaceAtPredecessor(newReturn);
728 GraphUtil.killCFG(this);
729 return true;
730 }
731 return false;
732 }
733
734 private ValueNode proxyReplacement(ValueNode replacement) {
735 /*
736 * Special case: Every empty diamond we collapse to a conditional node can potentially
737 * contain loop exit nodes on both branches. See the graph below: The two loop exits
738 * (instanceof begin node) exit the same loop. The resulting phi is defined outside the
739 * loop, but the resulting conditional node will be inside the loop, so we need to proxy the
740 * resulting conditional node. Callers of this method ensure that true and false successor
741 * have no usages, therefore a and b in the graph below can never be proxies themselves.
742 */
743 // @formatter:off
744 // +--+
745 // |If|
746 // +--+ +-----+ +-----+
747 // +----+ +----+ | a | | b |
748 // |Lex | |Lex | +----^+ +^----+
749 // +----+ +----+ | |
750 // +-------+ +---+
751 // | Merge +---------+Phi|
752 // +-------+ +---+
753 // @formatter:on
754 if (this.graph().hasValueProxies()) {
755 if (trueSuccessor instanceof LoopExitNode && falseSuccessor instanceof LoopExitNode) {
756 assert ((LoopExitNode) trueSuccessor).loopBegin() == ((LoopExitNode) falseSuccessor).loopBegin();
757 assert trueSuccessor.usages().isEmpty() && falseSuccessor.usages().isEmpty();
758 return this.graph().addOrUnique(new ValueProxyNode(replacement, (LoopExitNode) trueSuccessor));
759 }
760 }
761 return replacement;
762 }
763
764 protected void removeThroughFalseBranch(SimplifierTool tool, AbstractMergeNode merge) {
765 AbstractBeginNode trueBegin = trueSuccessor();
766 LogicNode conditionNode = condition();
767 graph().removeSplitPropagate(this, trueBegin);
768 tool.addToWorkList(trueBegin);
769 if (conditionNode != null) {
770 GraphUtil.tryKillUnused(conditionNode);
771 }
772 if (merge.isAlive() && merge.forwardEndCount() > 1) {
773 for (FixedNode end : merge.forwardEnds()) {
774 Node cur = end;
775 while (cur != null && cur.predecessor() instanceof BeginNode) {
776 cur = cur.predecessor();
777 }
778 if (cur != null && cur.predecessor() instanceof IfNode) {
779 tool.addToWorkList(cur.predecessor());
780 }
781 }
782 }
783 }
|