# HG changeset patch # User Tom Rodriguez # Date 1400037629 25200 # Node ID f02fb7c5a1cca6bcd25041ee563a32c4dcdc40fe # Parent dcaf3993ad175bc2e6b4440886099ddd9fe3c333 convert signed range tests into an unsigned compare diff -r dcaf3993ad17 -r f02fb7c5a1cc graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/IfCanonicalizerTest.java --- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/IfCanonicalizerTest.java Tue May 13 18:31:18 2014 -0700 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/IfCanonicalizerTest.java Tue May 13 20:20:29 2014 -0700 @@ -30,6 +30,8 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; import com.oracle.graal.phases.tiers.*; @@ -137,6 +139,44 @@ return 1; } + @Test + public void test6() { + testCombinedIf("test6Snippet", 3); + } + + public static int test6Snippet(int[] a) { + int i = a[0]; + if (i >= 0 && i < a.length) { + return a[i]; + } + return 0; + } + + @Test + public void test7() { + testCombinedIf("test7Snippet", 1); + } + + public static int test7Snippet(int v) { + if (v >= 0 && v < 1024) { + return v + 1; + } + return v - 1; + } + + private void testCombinedIf(String snippet, int count) { + StructuredGraph graph = parse(snippet); + PhaseContext context = new PhaseContext(getProviders(), new Assumptions(false)); + new LoweringPhase(new CanonicalizerPhase(true), LoweringTool.StandardLoweringStage.HIGH_TIER).apply(graph, context); + new FloatingReadPhase().apply(graph); + MidTierContext midContext = new MidTierContext(getProviders(), new Assumptions(false), getCodeCache().getTarget(), OptimisticOptimizations.ALL, graph.method().getProfilingInfo(), null); + new GuardLoweringPhase().apply(graph, midContext); + new LoweringPhase(new CanonicalizerPhase(true), LoweringTool.StandardLoweringStage.MID_TIER).apply(graph, midContext); + new ValueAnchorCleanupPhase().apply(graph); + new CanonicalizerPhase(true).apply(graph, context); + assertDeepEquals(count, graph.getNodes().filter(IfNode.class).count()); + } + private void test(String snippet) { StructuredGraph graph = parse(snippet); ParameterNode param = graph.getNodes(ParameterNode.class).iterator().next(); diff -r dcaf3993ad17 -r f02fb7c5a1cc graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Tue May 13 18:31:18 2014 -0700 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Tue May 13 20:20:29 2014 -0700 @@ -187,6 +187,10 @@ } while (false); } + if (checkForUnsignedCompare(tool)) { + return; + } + if (condition() instanceof LogicConstantNode) { LogicConstantNode c = (LogicConstantNode) condition(); if (c.getValue()) { @@ -219,7 +223,7 @@ // Reordering of those two if statements is beneficial from the point of view of // their probabilities. if (prepareForSwap(tool.getConstantReflection(), condition(), nextIf.condition(), this.trueSuccessorProbability, probabilityB)) { - // Reording is allowed from (if1 => begin => if2) to (if2 => begin => if1). + // Reordering is allowed from (if1 => begin => if2) to (if2 => begin => if1). assert intermediateBegin.next() == nextIf; BeginNode bothFalseBegin = nextIf.falseSuccessor(); nextIf.setFalseSuccessor(null); @@ -243,6 +247,104 @@ } } + /** + * Recognize a couple patterns that can be merged into an unsigned compare. + * + * @param tool + * @return true if a replacement was done. + */ + private boolean checkForUnsignedCompare(SimplifierTool tool) { + if (condition() instanceof IntegerLessThanNode && trueSuccessor().usages().isEmpty() && falseSuccessor().usages().isEmpty()) { + IntegerLessThanNode lessThan = (IntegerLessThanNode) condition(); + Constant y = lessThan.y().stamp().asConstant(); + if (y != null && y.asLong() == 0 && falseSuccessor().next() instanceof IfNode) { + IfNode ifNode2 = (IfNode) falseSuccessor().next(); + if (ifNode2.condition() instanceof IntegerLessThanNode) { + IntegerLessThanNode lessThan2 = (IntegerLessThanNode) ifNode2.condition(); + IntegerBelowThanNode below = null; + /* + * Convert x >= 0 && x < positive which is represented as !(x < 0) && x < + * into an unsigned compare. + */ + if (lessThan2.x() == lessThan.x() && lessThan2.y().stamp() instanceof IntegerStamp && ((IntegerStamp) lessThan2.y().stamp()).isPositive() && + sameDestination(trueSuccessor(), ifNode2.falseSuccessor)) { + + below = graph().unique(new IntegerBelowThanNode(lessThan2.x(), lessThan2.y())); + } else if (lessThan2.y() == lessThan.x() && sameDestination(trueSuccessor(), ifNode2.trueSuccessor)) { + /* + * Convert x >= 0 && x <= positive which is represented as !(x < 0) && + * !( > x), into x <| positive + 1. This can only be done for + * constants since there isn't a IntegerBelowEqualThanNode but that doesn't + * appear to be interesting. + */ + Constant positive = lessThan2.x().asConstant(); + if (positive != null && positive.asLong() > 0 && positive.asLong() < positive.getKind().getMaxValue()) { + ConstantNode newLimit = ConstantNode.forIntegerKind(positive.getKind(), positive.asLong() + 1, graph()); + below = graph().unique(new IntegerBelowThanNode(lessThan.x(), newLimit)); + } + } + if (below != null) { + BeginNode falseSucc = ifNode2.falseSuccessor(); + BeginNode trueSucc = ifNode2.trueSuccessor(); + + ifNode2.setTrueSuccessor(null); + ifNode2.setFalseSuccessor(null); + + IfNode newIfNode = graph().add(new IfNode(below, falseSucc, trueSucc, 1 - trueSuccessorProbability)); + // Remove the < 0 test. + tool.deleteBranch(trueSuccessor); + graph().removeSplit(this, falseSuccessor); + + // Replace the second test with the new one. + ifNode2.predecessor().replaceFirstSuccessor(ifNode2, newIfNode); + ifNode2.safeDelete(); + return true; + } + } + } + } + return false; + } + + /** + * Check it these two blocks end up at the same place. Meeting at the same merge, or + * deoptimizing in the same way. + */ + private static boolean sameDestination(BeginNode succ1, BeginNode succ2) { + Node next1 = succ1.next(); + Node next2 = succ2.next(); + if (next1 instanceof EndNode && next2 instanceof EndNode) { + EndNode end1 = (EndNode) next1; + EndNode end2 = (EndNode) next2; + if (end1.merge() == end2.merge()) { + // They go to the same MergeNode + return true; + } + } else if (next1 instanceof DeoptimizeNode && next2 instanceof DeoptimizeNode) { + DeoptimizeNode deopt1 = (DeoptimizeNode) next1; + DeoptimizeNode deopt2 = (DeoptimizeNode) next2; + if (deopt1.reason() == deopt2.reason() && deopt1.action() == deopt1.action()) { + // Same deoptimization reason and action. + return true; + } + } else if (next1 instanceof LoopExitNode && next2 instanceof LoopExitNode) { + LoopExitNode exit1 = (LoopExitNode) next1; + LoopExitNode exit2 = (LoopExitNode) next2; + if (exit1.loopBegin() == exit2.loopBegin() && exit1.stateAfter() == exit2.stateAfter() && exit1.stateAfter() == null && sameDestination(exit1, exit2)) { + // Exit the same loop and end up at the same place. + return true; + } + } else if (next1 instanceof ReturnNode && next2 instanceof ReturnNode) { + ReturnNode exit1 = (ReturnNode) next1; + ReturnNode exit2 = (ReturnNode) next2; + if (exit1.result() == exit2.result()) { + // Exit the same loop and end up at the same place. + return true; + } + } + return false; + } + private static boolean prepareForSwap(ConstantReflectionProvider constantReflection, LogicNode a, LogicNode b, double probabilityA, double probabilityB) { if (a instanceof InstanceOfNode) { InstanceOfNode instanceOfA = (InstanceOfNode) a;