61 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
62 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
63 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
64 import org.graalvm.compiler.nodes.calc.IsNullNode;
65 import org.graalvm.compiler.nodes.calc.NormalizeCompareNode;
66 import org.graalvm.compiler.nodes.calc.ObjectEqualsNode;
67 import org.graalvm.compiler.nodes.extended.UnboxNode;
68 import org.graalvm.compiler.nodes.java.InstanceOfNode;
69 import org.graalvm.compiler.nodes.java.LoadFieldNode;
70 import org.graalvm.compiler.nodes.spi.LIRLowerable;
71 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
72 import org.graalvm.compiler.nodes.util.GraphUtil;
73
74 import jdk.vm.ci.meta.Constant;
75 import jdk.vm.ci.meta.JavaConstant;
76 import jdk.vm.ci.meta.JavaKind;
77 import jdk.vm.ci.meta.MetaAccessProvider;
78 import jdk.vm.ci.meta.PrimitiveConstant;
79 import jdk.vm.ci.meta.ResolvedJavaMethod;
80 import jdk.vm.ci.meta.ResolvedJavaType;
81
82 /**
83 * The {@code IfNode} represents a branch that can go one of two directions depending on the outcome
84 * of a comparison.
85 */
86 @NodeInfo(cycles = CYCLES_1, size = SIZE_2, sizeRationale = "2 jmps")
87 public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable {
88 public static final NodeClass<IfNode> TYPE = NodeClass.create(IfNode.class);
89
90 private static final CounterKey CORRECTED_PROBABILITIES = DebugContext.counter("CorrectedProbabilities");
91
92 @Successor AbstractBeginNode trueSuccessor;
93 @Successor AbstractBeginNode falseSuccessor;
94 @Input(InputType.Condition) LogicNode condition;
95 protected double trueSuccessorProbability;
96
97 public LogicNode condition() {
98 return condition;
99 }
100
851 AbstractBeginNode trueBegin = trueSuccessor();
852 LogicNode conditionNode = condition();
853 graph().removeSplitPropagate(this, trueBegin);
854 tool.addToWorkList(trueBegin);
855 if (conditionNode != null) {
856 GraphUtil.tryKillUnused(conditionNode);
857 }
858 if (merge.isAlive() && merge.forwardEndCount() > 1) {
859 for (FixedNode end : merge.forwardEnds()) {
860 Node cur = end;
861 while (cur != null && cur.predecessor() instanceof BeginNode) {
862 cur = cur.predecessor();
863 }
864 if (cur != null && cur.predecessor() instanceof IfNode) {
865 tool.addToWorkList(cur.predecessor());
866 }
867 }
868 }
869 }
870
871 private ValueNode canonicalizeConditionalCascade(SimplifierTool tool, ValueNode trueValue, ValueNode falseValue) {
872 if (trueValue.getStackKind() != falseValue.getStackKind()) {
873 return null;
874 }
875 if (trueValue.getStackKind() != JavaKind.Int && trueValue.getStackKind() != JavaKind.Long) {
876 return null;
877 }
878 if (trueValue.isConstant() && falseValue.isConstant()) {
879 return graph().unique(new ConditionalNode(condition(), trueValue, falseValue));
880 } else if (!graph().isAfterExpandLogic()) {
881 ConditionalNode conditional = null;
882 ValueNode constant = null;
883 boolean negateCondition;
884 if (trueValue instanceof ConditionalNode && falseValue.isConstant()) {
885 conditional = (ConditionalNode) trueValue;
886 constant = falseValue;
887 negateCondition = true;
888 } else if (falseValue instanceof ConditionalNode && trueValue.isConstant()) {
889 conditional = (ConditionalNode) falseValue;
890 constant = trueValue;
891 negateCondition = false;
892 } else {
893 return null;
894 }
895 boolean negateConditionalCondition = false;
896 ValueNode otherValue = null;
897 if (constant == conditional.trueValue()) {
898 otherValue = conditional.falseValue();
899 negateConditionalCondition = false;
900 } else if (constant == conditional.falseValue()) {
901 otherValue = conditional.trueValue();
902 negateConditionalCondition = true;
903 }
904 if (otherValue != null && otherValue.isConstant()) {
905 double shortCutProbability = probability(trueSuccessor());
906 LogicNode newCondition = LogicNode.or(condition(), negateCondition, conditional.condition(), negateConditionalCondition, shortCutProbability);
907 return graph().unique(new ConditionalNode(newCondition, constant, otherValue));
908 } else if (constant.isJavaConstant() && conditional.trueValue().isJavaConstant() && conditional.falseValue().isJavaConstant() && condition() instanceof CompareNode &&
909 conditional.condition() instanceof CompareNode) {
910 Condition cond1 = ((CompareNode) condition()).condition().asCondition();
911 if (negateCondition) {
912 cond1 = cond1.negate();
913 }
914 // cond1 is EQ, NE, LT, or GE
915 Condition cond2 = ((CompareNode) conditional.condition()).condition().asCondition();
916 ValueNode x = ((CompareNode) condition()).getX();
917 ValueNode y = ((CompareNode) condition()).getY();
918 ValueNode x2 = ((CompareNode) conditional.condition()).getX();
919 ValueNode y2 = ((CompareNode) conditional.condition()).getY();
920 // `x cond1 y ? c1 : (x2 cond2 y2 ? c2 : c3)`
921 boolean sameVars = x == x2 && y == y2;
922 if (!sameVars && x == y2 && y == x2) {
923 sameVars = true;
924 cond2 = cond2.mirror();
925 }
926 // cond2 is EQ, LT, or GT
927 if (sameVars) {
928 JavaKind stackKind = conditional.trueValue().stamp(NodeView.from(tool)).getStackKind();
929 assert !stackKind.isNumericFloat();
930 long c1 = constant.asJavaConstant().asLong();
931 long c2 = conditional.trueValue().asJavaConstant().asLong();
932 long c3 = conditional.falseValue().asJavaConstant().asLong();
933 // `x cond1 y ? c1 : (x cond2 y ? c2 : c3)`
934 if (cond1 == Condition.GE && cond2 == Condition.LT) {
935 // x >= y ? v1 : (x < y ? v2 : v3) => x >= y ? v1 : v2
936 return graph().unique(new ConditionalNode(condition(), conditional.trueValue(), constant));
937 } else if (cond1 == Condition.GE && cond2 == Condition.GT) {
938 // x >= y ? v1 : (x > y ? v2 : v3) => x >= y ? v1 : v3
939 return graph().unique(new ConditionalNode(condition(), conditional.falseValue(), constant));
940 } else if (cond1 == Condition.EQ && cond2 == Condition.EQ) {
941 // x == y ? v1 : (x == y ? v2 : v3) => x == y ? v1 : v3
942 return graph().unique(new ConditionalNode(condition(), conditional.falseValue(), constant));
943 } else if (cond1 == Condition.NE && cond2 == Condition.LT) {
944 // x != y ? v1 : (x < y ? v2 : v3) => x != y ? v1 : v3
945 return graph().unique(new ConditionalNode(condition(), conditional.falseValue(), constant));
946 } else if (cond1 == Condition.LT && cond2 == Condition.EQ && c1 == -1 && c2 == 0 && c3 == 1) {
947 // x < y ? -1 : (x == y ? 0 : 1) => x cmp y
948 return graph().unique(new NormalizeCompareNode(x, y, stackKind, false));
949 } else if (cond1 == Condition.LT && cond2 == Condition.EQ && c1 == 1 && c2 == 0 && c3 == -1) {
950 // x < y ? 1 : (x == y ? 0 : -1) => y cmp x
951 return graph().unique(new NormalizeCompareNode(y, x, stackKind, false));
952 } else if (cond1 == Condition.EQ && cond2 == Condition.LT && c1 == 0 && c2 == -1 && c3 == 1) {
953 // x == y ? 0 : (x < y ? -1 : 1) => x cmp y
954 return graph().unique(new NormalizeCompareNode(x, y, stackKind, false));
955 } else if (cond1 == Condition.EQ && cond2 == Condition.LT && c1 == 0 && c2 == 1 && c3 == -1) {
956 // x == y ? 0 : (x < y ? 1 : -1) => y cmp x
957 return graph().unique(new NormalizeCompareNode(y, x, stackKind, false));
958 } else if (cond1 == Condition.EQ && cond2 == Condition.GT && c1 == 0 && c2 == -1 && c3 == 1) {
959 // x == y ? 0 : (x > y ? -1 : 1) => y cmp x
960 return graph().unique(new NormalizeCompareNode(y, x, stackKind, false));
961 } else if (cond1 == Condition.EQ && cond2 == Condition.GT && c1 == 0 && c2 == 1 && c3 == -1) {
962 // x == y ? 0 : (x > y ? 1 : -1) => x cmp y
963 return graph().unique(new NormalizeCompareNode(x, y, stackKind, false));
964 } else if (cond1 == Condition.LT && cond2 == Condition.GT && c1 == 1 && c2 == -1 && c3 == 0) {
965 // x < y ? 1 : (x > y ? -1 : 0) => y cmp x
966 return graph().unique(new NormalizeCompareNode(y, x, stackKind, false));
|
61 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
62 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
63 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
64 import org.graalvm.compiler.nodes.calc.IsNullNode;
65 import org.graalvm.compiler.nodes.calc.NormalizeCompareNode;
66 import org.graalvm.compiler.nodes.calc.ObjectEqualsNode;
67 import org.graalvm.compiler.nodes.extended.UnboxNode;
68 import org.graalvm.compiler.nodes.java.InstanceOfNode;
69 import org.graalvm.compiler.nodes.java.LoadFieldNode;
70 import org.graalvm.compiler.nodes.spi.LIRLowerable;
71 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
72 import org.graalvm.compiler.nodes.util.GraphUtil;
73
74 import jdk.vm.ci.meta.Constant;
75 import jdk.vm.ci.meta.JavaConstant;
76 import jdk.vm.ci.meta.JavaKind;
77 import jdk.vm.ci.meta.MetaAccessProvider;
78 import jdk.vm.ci.meta.PrimitiveConstant;
79 import jdk.vm.ci.meta.ResolvedJavaMethod;
80 import jdk.vm.ci.meta.ResolvedJavaType;
81 import jdk.vm.ci.meta.TriState;
82
83 /**
84 * The {@code IfNode} represents a branch that can go one of two directions depending on the outcome
85 * of a comparison.
86 */
87 @NodeInfo(cycles = CYCLES_1, size = SIZE_2, sizeRationale = "2 jmps")
88 public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable {
89 public static final NodeClass<IfNode> TYPE = NodeClass.create(IfNode.class);
90
91 private static final CounterKey CORRECTED_PROBABILITIES = DebugContext.counter("CorrectedProbabilities");
92
93 @Successor AbstractBeginNode trueSuccessor;
94 @Successor AbstractBeginNode falseSuccessor;
95 @Input(InputType.Condition) LogicNode condition;
96 protected double trueSuccessorProbability;
97
98 public LogicNode condition() {
99 return condition;
100 }
101
852 AbstractBeginNode trueBegin = trueSuccessor();
853 LogicNode conditionNode = condition();
854 graph().removeSplitPropagate(this, trueBegin);
855 tool.addToWorkList(trueBegin);
856 if (conditionNode != null) {
857 GraphUtil.tryKillUnused(conditionNode);
858 }
859 if (merge.isAlive() && merge.forwardEndCount() > 1) {
860 for (FixedNode end : merge.forwardEnds()) {
861 Node cur = end;
862 while (cur != null && cur.predecessor() instanceof BeginNode) {
863 cur = cur.predecessor();
864 }
865 if (cur != null && cur.predecessor() instanceof IfNode) {
866 tool.addToWorkList(cur.predecessor());
867 }
868 }
869 }
870 }
871
872 private ValueNode canonicalizeConditionalViaImplies(ValueNode trueValue, ValueNode falseValue) {
873 ValueNode collapsedTrue = trueValue;
874 ValueNode collapsedFalse = falseValue;
875 boolean simplify = false;
876 if (trueValue instanceof ConditionalNode) {
877 TriState result = condition().implies(false, ((ConditionalNode) trueValue).condition());
878 if (result.isKnown()) {
879 simplify = true;
880 collapsedTrue = result.toBoolean() ? ((ConditionalNode) trueValue).trueValue() : ((ConditionalNode) trueValue).falseValue();
881 }
882 }
883 if (falseValue instanceof ConditionalNode) {
884 TriState result = condition().implies(true, ((ConditionalNode) falseValue).condition());
885 if (result.isKnown()) {
886 simplify = true;
887 collapsedFalse = result.toBoolean() ? ((ConditionalNode) falseValue).trueValue() : ((ConditionalNode) falseValue).falseValue();
888 }
889 }
890 if (simplify) {
891 return graph().unique(new ConditionalNode(condition(), collapsedTrue, collapsedFalse));
892 }
893 return null;
894 }
895
896 private ValueNode canonicalizeConditionalCascade(SimplifierTool tool, ValueNode trueValue, ValueNode falseValue) {
897 if (trueValue.getStackKind() != falseValue.getStackKind()) {
898 return null;
899 }
900 if (trueValue.getStackKind() != JavaKind.Int && trueValue.getStackKind() != JavaKind.Long) {
901 return null;
902 }
903 if (trueValue.isConstant() && falseValue.isConstant()) {
904 return graph().unique(new ConditionalNode(condition(), trueValue, falseValue));
905 }
906 ValueNode value = canonicalizeConditionalViaImplies(trueValue, falseValue);
907 if (value != null) {
908 return value;
909 }
910 if (!graph().isAfterExpandLogic()) {
911 /*
912 * !isAfterExpandLogic() => Cannot spawn NormalizeCompareNodes after lowering in the
913 * ExpandLogicPhase.
914 */
915 ConditionalNode conditional = null;
916 ValueNode constant = null;
917 boolean negateCondition;
918 if (trueValue instanceof ConditionalNode && falseValue.isConstant()) {
919 conditional = (ConditionalNode) trueValue;
920 constant = falseValue;
921 negateCondition = true;
922 } else if (falseValue instanceof ConditionalNode && trueValue.isConstant()) {
923 conditional = (ConditionalNode) falseValue;
924 constant = trueValue;
925 negateCondition = false;
926 } else {
927 return null;
928 }
929 boolean negateConditionalCondition = false;
930 ValueNode otherValue = null;
931 if (constant == conditional.trueValue()) {
932 otherValue = conditional.falseValue();
933 negateConditionalCondition = false;
934 } else if (constant == conditional.falseValue()) {
935 otherValue = conditional.trueValue();
936 negateConditionalCondition = true;
937 }
938 if (otherValue != null && otherValue.isConstant()) {
939 double shortCutProbability = probability(trueSuccessor());
940 LogicNode newCondition = LogicNode.or(condition(), negateCondition, conditional.condition(), negateConditionalCondition, shortCutProbability);
941 return graph().unique(new ConditionalNode(newCondition, constant, otherValue));
942 }
943
944 if (constant.isJavaConstant() && conditional.trueValue().isJavaConstant() && conditional.falseValue().isJavaConstant() && condition() instanceof CompareNode &&
945 conditional.condition() instanceof CompareNode) {
946
947 Condition cond1 = ((CompareNode) condition()).condition().asCondition();
948 if (negateCondition) {
949 cond1 = cond1.negate();
950 }
951 // cond1 is EQ, NE, LT, or GE
952 Condition cond2 = ((CompareNode) conditional.condition()).condition().asCondition();
953 ValueNode x = ((CompareNode) condition()).getX();
954 ValueNode y = ((CompareNode) condition()).getY();
955 ValueNode x2 = ((CompareNode) conditional.condition()).getX();
956 ValueNode y2 = ((CompareNode) conditional.condition()).getY();
957 // `x cond1 y ? c1 : (x2 cond2 y2 ? c2 : c3)`
958 boolean sameVars = x == x2 && y == y2;
959 if (!sameVars && x == y2 && y == x2) {
960 sameVars = true;
961 cond2 = cond2.mirror();
962 }
963 if (sameVars) {
964 JavaKind stackKind = conditional.trueValue().stamp(NodeView.from(tool)).getStackKind();
965 assert !stackKind.isNumericFloat();
966
967 ValueNode v1 = constant;
968 ValueNode v2 = conditional.trueValue();
969 ValueNode v3 = conditional.falseValue();
970
971 long c1 = v1.asJavaConstant().asLong();
972 long c2 = v2.asJavaConstant().asLong();
973 long c3 = v3.asJavaConstant().asLong();
974
975 if (cond1 == Condition.LT && cond2 == Condition.EQ && c1 == -1 && c2 == 0 && c3 == 1) {
976 // x < y ? -1 : (x == y ? 0 : 1) => x cmp y
977 return graph().unique(new NormalizeCompareNode(x, y, stackKind, false));
978 } else if (cond1 == Condition.LT && cond2 == Condition.EQ && c1 == 1 && c2 == 0 && c3 == -1) {
979 // x < y ? 1 : (x == y ? 0 : -1) => y cmp x
980 return graph().unique(new NormalizeCompareNode(y, x, stackKind, false));
981 } else if (cond1 == Condition.EQ && cond2 == Condition.LT && c1 == 0 && c2 == -1 && c3 == 1) {
982 // x == y ? 0 : (x < y ? -1 : 1) => x cmp y
983 return graph().unique(new NormalizeCompareNode(x, y, stackKind, false));
984 } else if (cond1 == Condition.EQ && cond2 == Condition.LT && c1 == 0 && c2 == 1 && c3 == -1) {
985 // x == y ? 0 : (x < y ? 1 : -1) => y cmp x
986 return graph().unique(new NormalizeCompareNode(y, x, stackKind, false));
987 } else if (cond1 == Condition.EQ && cond2 == Condition.GT && c1 == 0 && c2 == -1 && c3 == 1) {
988 // x == y ? 0 : (x > y ? -1 : 1) => y cmp x
989 return graph().unique(new NormalizeCompareNode(y, x, stackKind, false));
990 } else if (cond1 == Condition.EQ && cond2 == Condition.GT && c1 == 0 && c2 == 1 && c3 == -1) {
991 // x == y ? 0 : (x > y ? 1 : -1) => x cmp y
992 return graph().unique(new NormalizeCompareNode(x, y, stackKind, false));
993 } else if (cond1 == Condition.LT && cond2 == Condition.GT && c1 == 1 && c2 == -1 && c3 == 0) {
994 // x < y ? 1 : (x > y ? -1 : 0) => y cmp x
995 return graph().unique(new NormalizeCompareNode(y, x, stackKind, false));
|