Mercurial > hg > graal-compiler
changeset 22919:6b81cca49187
Fix machinery for elimination of pending tests
| author | Tom Rodriguez <tom.rodriguez@oracle.com> |
|---|---|
| date | Thu, 29 Oct 2015 12:35:30 -0700 |
| parents | 6a508ee4c7ef |
| children | 85b76567ea2c |
| files | graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTest11.java graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTestBase.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/DeoptimizingGuard.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DominatorConditionalEliminationPhase.java |
| diffstat | 4 files changed, 211 insertions(+), 88 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTest11.java Fri Oct 30 10:46:56 2015 -0700 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTest11.java Thu Oct 29 12:35:30 2015 -0700 @@ -112,34 +112,19 @@ testConditionalElimination("test4Snippet", "referenceSnippet"); } - @SuppressWarnings("all") - public static int reference5Snippet(int a) { - if ((a & 15) == 15) { + public static int test5Snippet(int a) { + if ((a & 5) == 5) { GraalDirectives.deoptimize(); } - if (a > 0) { - a |= 32; + if ((a & 7) != 0) { + return 0; } - return a; + return 1; } - @SuppressWarnings("all") - public static int test5Snippet(int a) { - if ((a & 8) != 8) { - GraalDirectives.deoptimize(); - } - if (a > 0) { - a |= 32; - } - if ((a & 15) == 15) { - GraalDirectives.deoptimize(); - } - return a; - } - - @Ignore @Test public void test5() { + // Shouldn't be possible to optimize this testConditionalElimination("test5Snippet", "test5Snippet"); } @@ -163,7 +148,83 @@ @Test public void test6() { - // Shouldn't be able to optimize this testConditionalElimination("test6Snippet", "reference6Snippet"); } + + public static int test7Snippet(int a) { + if ((a & 15) == 15) { + GraalDirectives.deoptimize(); + } + if ((a & 8) == 8) { + GraalDirectives.deoptimize(); + } + return a; + } + + public static int reference7Snippet(int a) { + if ((a & 8) == 8) { + GraalDirectives.deoptimize(); + } + return a; + } + + @Test + public void test7() { + testConditionalElimination("test7Snippet", "reference7Snippet"); + } + + public static int test8Snippet(int a) { + if ((a & 16) == 16) { + GraalDirectives.deoptimize(); + } + if ((a & 8) != 8) { + GraalDirectives.deoptimize(); + } + if ((a & 44) != 44) { + GraalDirectives.deoptimize(); + } + return a; + } + + public static int reference8Snippet(int a) { + if ((a & 60) != 44) { + GraalDirectives.deoptimize(); + } + return a; + } + + @Ignore("requires merging of bit tests") + @Test + public void test8() { + testConditionalElimination("test8Snippet", "reference8Snippet"); + } + + public static int test9Snippet(int a) { + if ((a & 16) == 16) { + GraalDirectives.deoptimize(); + } + if ((a & 8) != 8) { + GraalDirectives.deoptimize(); + } + if ((a & 44) != 44) { + GraalDirectives.deoptimize(); + } + if (a != 44) { + GraalDirectives.deoptimize(); + } + return a; + } + + public static int reference9Snippet(int a) { + if (a != 44) { + GraalDirectives.deoptimize(); + } + return a; + } + + @Test + public void test9() { + testConditionalElimination("test9Snippet", "reference9Snippet"); + } + }
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTestBase.java Fri Oct 30 10:46:56 2015 -0700 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTestBase.java Thu Oct 29 12:35:30 2015 -0700 @@ -32,6 +32,7 @@ import com.oracle.graal.phases.common.CanonicalizerPhase; import com.oracle.graal.phases.common.ConvertDeoptimizeToGuardPhase; import com.oracle.graal.phases.common.DominatorConditionalEliminationPhase; +import com.oracle.graal.phases.common.IterativeConditionalEliminationPhase; import com.oracle.graal.phases.common.LoweringPhase; import com.oracle.graal.phases.schedule.SchedulePhase; import com.oracle.graal.phases.tiers.PhaseContext; @@ -73,7 +74,8 @@ try (Debug.Scope scope = Debug.scope("ConditionalEliminationTest", graph)) { canonicalizer1.apply(graph, context); new ConvertDeoptimizeToGuardPhase().apply(graph, context); - new DominatorConditionalEliminationPhase(true).apply(graph, context); + // new DominatorConditionalEliminationPhase(true).apply(graph, context); + new IterativeConditionalEliminationPhase(canonicalizer, true).apply(graph, context); canonicalizer.apply(graph, context); canonicalizer.apply(graph, context); new ConvertDeoptimizeToGuardPhase().apply(graph, context); @@ -81,7 +83,7 @@ Debug.handle(t); } StructuredGraph referenceGraph = parseEager(referenceSnippet, AllowAssumptions.YES); - try (Debug.Scope scope = Debug.scope("ConditionalEliminationTest.ReferenceGraph", graph)) { + try (Debug.Scope scope = Debug.scope("ConditionalEliminationTest.ReferenceGraph", referenceGraph)) { new ConvertDeoptimizeToGuardPhase().apply(referenceGraph, context); if (applyConditionalEliminationOnReference) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/DeoptimizingGuard.java Fri Oct 30 10:46:56 2015 -0700 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/DeoptimizingGuard.java Thu Oct 29 12:35:30 2015 -0700 @@ -45,4 +45,6 @@ JavaConstant getSpeculation(); boolean isNegated(); + + ValueNode asNode(); }
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DominatorConditionalEliminationPhase.java Fri Oct 30 10:46:56 2015 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DominatorConditionalEliminationPhase.java Thu Oct 29 12:35:30 2015 -0700 @@ -55,6 +55,7 @@ import com.oracle.graal.nodes.BinaryOpLogicNode; import com.oracle.graal.nodes.ConditionAnchorNode; import com.oracle.graal.nodes.DeoptimizeNode; +import com.oracle.graal.nodes.DeoptimizingGuard; import com.oracle.graal.nodes.FixedGuardNode; import com.oracle.graal.nodes.FixedNode; import com.oracle.graal.nodes.GuardNode; @@ -138,50 +139,51 @@ } @Override + @SuppressWarnings("try") protected void run(StructuredGraph graph) { - Function<Block, Iterable<? extends Node>> blockToNodes; - Function<Node, Block> nodeToBlock; - Block startBlock; + try (Debug.Scope s = Debug.scope("DominatorConditionalElimination")) { + Function<Block, Iterable<? extends Node>> blockToNodes; + Function<Node, Block> nodeToBlock; + Block startBlock; - if (fullSchedule) { - SchedulePhase schedule = new SchedulePhase(SchedulePhase.SchedulingStrategy.EARLIEST); - schedule.apply(graph); - ControlFlowGraph cfg = schedule.getCFG(); - cfg.computePostdominators(); - blockToNodes = b -> schedule.getBlockToNodesMap().get(b); - nodeToBlock = n -> schedule.getNodeToBlockMap().get(n); - startBlock = cfg.getStartBlock(); - } else { - ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true); - cfg.computePostdominators(); - BlockMap<List<FixedNode>> nodes = new BlockMap<>(cfg); - for (Block b : cfg.getBlocks()) { - ArrayList<FixedNode> curNodes = new ArrayList<>(); - for (FixedNode node : b.getNodes()) { - if (node instanceof AbstractBeginNode || node instanceof FixedGuardNode || node instanceof CheckCastNode || node instanceof ConditionAnchorNode || node instanceof IfNode) { - curNodes.add(node); + if (fullSchedule) { + SchedulePhase schedule = new SchedulePhase(SchedulePhase.SchedulingStrategy.EARLIEST); + schedule.apply(graph); + ControlFlowGraph cfg = schedule.getCFG(); + cfg.computePostdominators(); + blockToNodes = b -> schedule.getBlockToNodesMap().get(b); + nodeToBlock = n -> schedule.getNodeToBlockMap().get(n); + startBlock = cfg.getStartBlock(); + } else { + ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true); + cfg.computePostdominators(); + BlockMap<List<FixedNode>> nodes = new BlockMap<>(cfg); + for (Block b : cfg.getBlocks()) { + ArrayList<FixedNode> curNodes = new ArrayList<>(); + for (FixedNode node : b.getNodes()) { + if (node instanceof AbstractBeginNode || node instanceof FixedGuardNode || node instanceof CheckCastNode || node instanceof ConditionAnchorNode || node instanceof IfNode) { + curNodes.add(node); + } } + nodes.put(b, curNodes); } - nodes.put(b, curNodes); + blockToNodes = b -> nodes.get(b); + nodeToBlock = n -> cfg.blockFor(n); + startBlock = cfg.getStartBlock(); } - blockToNodes = b -> nodes.get(b); - nodeToBlock = n -> cfg.blockFor(n); - startBlock = cfg.getStartBlock(); + + Instance instance = new Instance(graph, blockToNodes, nodeToBlock); + instance.processBlock(startBlock); } - - Instance instance = new Instance(graph, blockToNodes, nodeToBlock); - instance.processBlock(startBlock); } static class PendingTest { private final LogicNode condition; - private final boolean negated; - private final ValueNode guard; + private final DeoptimizingGuard guard; - public PendingTest(LogicNode condition, boolean negated, ValueNode guard) { + public PendingTest(LogicNode condition, DeoptimizingGuard guard) { this.condition = condition; - this.negated = negated; this.guard = guard; } } @@ -348,7 +350,7 @@ Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(negated); registerNewStamp(y, newStampY, guard, undoOperations); } - if (condition instanceof IntegerEqualsNode && guard instanceof FixedGuardNode && !negated) { + if (condition instanceof IntegerEqualsNode && guard instanceof DeoptimizingGuard && !negated) { if (y.isConstant() && x instanceof AndNode) { AndNode and = (AndNode) x; if (and.getY() == y) { @@ -360,52 +362,66 @@ BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp()).getOr(); IntegerStamp newStampX = (IntegerStamp) op.foldStamp(and.getX().stamp(), y.stamp()); registerNewStamp(and.getX(), newStampX, guard, undoOperations); - foldPendingTest(negated, guard, and.getX(), newStampX); } } } } - pendingTests.push(new PendingTest(condition, negated, guard)); + if (guard instanceof DeoptimizingGuard) { + pendingTests.push(new PendingTest(condition, (DeoptimizingGuard) guard)); + } registerCondition(condition, negated, guard, undoOperations); } - private void foldPendingTest(boolean negated, ValueNode guard, ValueNode originalX, IntegerStamp newStampX) { + private boolean foldPendingTest(DeoptimizingGuard thisGuard, ValueNode original, Stamp newStamp, GuardRewirer rewireGuardFunction) { for (PendingTest pending : pendingTests) { - if (pending.condition instanceof BinaryOpLogicNode) { - TriState result = TriState.UNKNOWN; + TriState result = TriState.UNKNOWN; + if (pending.condition instanceof UnaryOpLogicNode) { + UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) pending.condition; + if (unaryLogicNode.getValue() == original) { + result = unaryLogicNode.tryFold(newStamp); + if (result.isKnown()) { + Debug.log("unary %s %s %1s", result, newStamp, unaryLogicNode); + } + } + } else if (pending.condition instanceof BinaryOpLogicNode) { BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) pending.condition; ValueNode x = binaryOpLogicNode.getX(); ValueNode y = binaryOpLogicNode.getY(); - if (binaryOpLogicNode.getX() == originalX) { - result = binaryOpLogicNode.tryFold(newStampX, binaryOpLogicNode.getY().stamp()); + if (binaryOpLogicNode.getX() == original) { + result = binaryOpLogicNode.tryFold(newStamp, binaryOpLogicNode.getY().stamp()); } else if (binaryOpLogicNode instanceof IntegerEqualsNode && y.isConstant() && x instanceof AndNode) { - AndNode and2 = (AndNode) x; - if (and2.getY() == y) { - BinaryOp<And> andOp = ArithmeticOpTable.forStamp(originalX.stamp()).getAnd(); - result = binaryOpLogicNode.tryFold(andOp.foldStamp(newStampX, y.stamp()), y.stamp()); - } - } - /* - * If the failure of the pending guard would also be triggered by the failure of - * this guard, then it's safe to replace the earlier guard with this guard. - */ - if (result.isKnown()) { - if (pending.guard instanceof FixedGuardNode && guard instanceof FixedGuardNode) { - FixedGuardNode fix = (FixedGuardNode) pending.guard; - FixedGuardNode thisGuard = (FixedGuardNode) guard; - if (fix.getAction() == thisGuard.getAction() && fix.getReason() == thisGuard.getReason() && fix.getSpeculation() == thisGuard.getSpeculation()) { - if (pending.negated == negated && result.isTrue() || pending.negated && result.isFalse()) { - assert !negated; - FixedGuardNode newFix = (FixedGuardNode) thisGuard.copyWithInputs(); - guard.graph().replaceFixedWithFixed(fix, newFix); - guard.replaceAtUsages(newFix); - guard.graph().removeFixed(thisGuard); - } - } + AndNode and = (AndNode) x; + if (and.getY() == y && and.getX() == original) { + BinaryOp<And> andOp = ArithmeticOpTable.forStamp(newStamp).getAnd(); + result = binaryOpLogicNode.tryFold(andOp.foldStamp(newStamp, y.stamp()), y.stamp()); } } } + if (result.isKnown()) { + if (foldGuard(thisGuard, pending.guard, result, rewireGuardFunction)) { + return true; + } + } } + return false; + } + + private boolean foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, TriState testResult, GuardRewirer rewireGuardFunction) { + if (otherGuard.getAction() == thisGuard.getAction() && otherGuard.getReason() == thisGuard.getReason() && otherGuard.getSpeculation() == thisGuard.getSpeculation()) { + LogicNode condition = (LogicNode) thisGuard.getCondition().copyWithInputs(); + GuardRewirer rewirer = (guard, result) -> { + if (rewireGuardFunction.rewire(guard, result)) { + otherGuard.setCondition(condition, thisGuard.isNegated()); + return true; + } + condition.safeDelete(); + return false; + }; + // Move the later test up + Debug.log("Folding guard %s %s %1s %s %1s %s\n", testResult, otherGuard, otherGuard.getCondition(), thisGuard, thisGuard.getCondition(), thisGuard.asNode().graph()); + return rewireGuards(otherGuard.asNode(), !thisGuard.isNegated(), rewirer); + } + return false; } private void registerCondition(LogicNode condition, boolean negated, ValueNode guard, List<Runnable> undoOperations) { @@ -463,6 +479,10 @@ } private boolean tryProofCondition(LogicNode node, GuardRewirer rewireGuardFunction) { + return tryProofGuardCondition(null, node, rewireGuardFunction); + } + + private boolean tryProofGuardCondition(DeoptimizingGuard thisGuard, LogicNode node, GuardRewirer rewireGuardFunction) { for (InfoElement infoElement : getInfoElements(node)) { Stamp stamp = infoElement.getStamp(); JavaConstant constant = (JavaConstant) stamp.asConstant(); @@ -480,6 +500,13 @@ return rewireGuards(infoElement.getGuard(), result.toBoolean(), rewireGuardFunction); } } + if (thisGuard != null && unaryLogicNode.stamp() instanceof IntegerStamp) { + Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(thisGuard.isNegated()); + if (newStamp != null && foldPendingTest(thisGuard, unaryLogicNode.getValue(), newStamp, rewireGuardFunction)) { + return true; + } + + } } else if (node instanceof BinaryOpLogicNode) { BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) node; for (InfoElement infoElement : getInfoElements(binaryOpLogicNode)) { @@ -524,6 +551,37 @@ } } } + if (thisGuard != null && binaryOpLogicNode instanceof IntegerEqualsNode && !thisGuard.isNegated()) { + if (y.isConstant() && x instanceof AndNode) { + AndNode and = (AndNode) x; + if (and.getY() == y) { + /* + * This 'and' proves something about some of the bits in and.getX(). + * It's equivalent to or'ing in the mask value since those values are + * known to be set. + */ + BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp()).getOr(); + IntegerStamp newStampX = (IntegerStamp) op.foldStamp(and.getX().stamp(), y.stamp()); + if (foldPendingTest(thisGuard, and.getX(), newStampX, rewireGuardFunction)) { + return true; + } + } + } + } + if (thisGuard != null) { + if (!x.isConstant()) { + Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(thisGuard.isNegated()); + if (newStampX != null && foldPendingTest(thisGuard, x, newStampX, rewireGuardFunction)) { + return true; + } + } + if (!y.isConstant()) { + Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(thisGuard.isNegated()); + if (newStampY != null && foldPendingTest(thisGuard, y, newStampY, rewireGuardFunction)) { + return true; + } + } + } } else if (node instanceof ShortCircuitOrNode) { final ShortCircuitOrNode shortCircuitOrNode = (ShortCircuitOrNode) node; if (this.loopExits.isEmpty()) { @@ -576,7 +634,7 @@ } private void processGuard(GuardNode node, List<Runnable> undoOperations) { - if (!tryProofCondition(node.getCondition(), (guard, result) -> { + if (!tryProofGuardCondition(node, node.getCondition(), (guard, result) -> { if (result != node.isNegated()) { node.replaceAndDelete(guard); } else { @@ -593,7 +651,7 @@ } private void processFixedGuard(FixedGuardNode node, List<Runnable> undoOperations) { - if (!tryProofCondition(node.condition(), (guard, result) -> { + if (!tryProofGuardCondition(node, node.condition(), (guard, result) -> { if (result != node.isNegated()) { node.replaceAtUsages(guard); GraphUtil.unlinkFixedNode(node);