# HG changeset patch # User Thomas Wuerthinger # Date 1422047635 -3600 # Node ID 2ad82c6147f14274076f78214ec99a51aa432d5a # Parent 732748092baee6736e798b9f4e8ef9d6b8a040f1 Temporarily remove FlowSensitiveReductionPhase. diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/GraalOptions.java --- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/GraalOptions.java Fri Jan 23 22:00:55 2015 +0100 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/GraalOptions.java Fri Jan 23 22:13:55 2015 +0100 @@ -232,10 +232,6 @@ @Option(help = "Comma separated list of register that the allocation is limited to.", type = OptionType.Debug) public static final OptionValue RegisterPressure = new OptionValue<>(null); - // Code generator settings - @Option(help = "", type = OptionType.Debug) - public static final OptionValue FlowSensitiveReduction = new OptionValue<>(false); - @Option(help = "", type = OptionType.Debug) public static final OptionValue ConditionalElimination = new OptionValue<>(true); diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/FlowSenReduTest.java --- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/FlowSenReduTest.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,392 +0,0 @@ -/* - * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.compiler.test; - -import java.util.*; - -import org.junit.*; - -import com.oracle.graal.debug.*; -import com.oracle.graal.debug.internal.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.calc.*; -import com.oracle.graal.nodes.java.*; -import com.oracle.graal.nodes.util.*; -import com.oracle.graal.phases.common.*; -import com.oracle.graal.phases.common.cfs.*; -import com.oracle.graal.phases.tiers.*; - -/** - * Tests whether {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase} actually - * performs some graph rewritings that it's supposed to perform. - */ -public class FlowSenReduTest extends GraalCompilerTest { - - /* - * A previous instanceof makes redundant a follow-up checkcast. - */ - public Object redundantCheckCastSnippet(Number o) { - Integer z = null; - if (o instanceof Integer) { - z = (Integer) o; // this CheckCastNode will be removed - } - return z; - } - - static final Integer i7 = new Integer(7); - - @Test - public void redundantCheckCastTest() { - assertDeepEquals(i7, redundantCheckCastSnippet(i7)); - StructuredGraph result = afterFlowSensitiveReduce("redundantCheckCastSnippet"); - nodeCountEquals(result, CheckCastNode.class, 0); - nodeCountEquals(result, InstanceOfNode.class, 1); - } - - @SuppressWarnings("unused") - public boolean redundantInstanceOfSnippet01(Object o) { - if (o != null) { - Integer x = (Integer) o; - return (o instanceof Number); // this InstanceOfNode will be removed - } - return false; - } - - @Test - public void redundantInstanceOfTest01() { - String snippet = "redundantInstanceOfSnippet01"; - assertDeepEquals(true, redundantInstanceOfSnippet01(i7)); - nodeCountEquals(afterFlowSensitiveReduce(snippet), InstanceOfNode.class, 1); - } - - /* - * The combination of (previous) non-null-check and checkcast make redundant an instanceof. - */ - @SuppressWarnings("unused") - public Object redundantInstanceOfSnippet02(Object o) { - Integer x = (Integer) o; - if (o != null) { - if (o instanceof Number) { // this InstanceOfNode will be removed - return o; - } - } - return null; - } - - @Test - public void redundantInstanceOfTest02() { - String snippet = "redundantInstanceOfSnippet02"; - assertDeepEquals(i7, redundantInstanceOfSnippet02(i7)); - int ioAfter = getNodes(afterFlowSensitiveReduce(snippet), InstanceOfNode.class).size(); - assertDeepEquals(ioAfter, 1); - } - - /* - * Once an exact-type has been inferred (due to instanceof final-class) a callsite is - * devirtualized. - */ - public int devirtualizationSnippet(Object x, Object y) { - boolean c = x instanceof Integer; - if (c && x == y) { - Number z = (Number) y; // this CheckCastNode will be removed - return z.intValue(); // devirtualized into InvokeSpecial on Integer.intValue() - } - return 0; - } - - @Test - public void devirtualizationTest() { - String snippet = "devirtualizationSnippet"; - assertDeepEquals(i7, devirtualizationSnippet(i7, i7)); - nodeCountEquals(afterFlowSensitiveReduce(snippet), CheckCastNode.class, 0); - - StructuredGraph graph = afterFlowSensitiveReduce(snippet); - assertDeepEquals(0, graph.getNodes().filter(CheckCastNode.class).count()); - - List invokeNodes = getNodes(afterFlowSensitiveReduce(snippet), InvokeNode.class); - assertDeepEquals(1, invokeNodes.size()); - - MethodCallTargetNode target = (MethodCallTargetNode) invokeNodes.get(0).callTarget(); - assertDeepEquals(MethodCallTargetNode.InvokeKind.Special, target.invokeKind()); - assertDeepEquals("HotSpotMethod", target.targetMethod().toString()); - } - - /* - * At the return statement, the returned value has been inferred to have type j.l.Number. The - * instanceof is deemed to always evaluate to false. The interplay with tail-duplication is also - * taken into account (resulting in two return statements, each with "false" as input). - */ - @SuppressWarnings("unused") - public boolean t5Snippet(Object o, boolean b) { - Number z; - if (b) { - z = (Number) o; // tail duplication of return stmt, which becomes "return false" - } else { - z = (Integer) o; // tail duplication of return stmt, which becomes "return false" - } - return o instanceof String; // unreachable - } - - @Test - public void t5a() { - String snippet = "t5Snippet"; - assertDeepEquals(false, t5Snippet(null, true)); - StructuredGraph resultGraph = canonicalize(afterFlowSensitiveReduce(snippet)); - nodeCountEquals(resultGraph, ReturnNode.class, 2); - - List returnNodes = getNodes(resultGraph, ReturnNode.class); - Iterator iter = returnNodes.iterator(); - - ConstantNode c1 = (ConstantNode) iter.next().result(); - ConstantNode c2 = (ConstantNode) iter.next().result(); - - assertDeepEquals(c1, c2); - assertDeepEquals(0, c1.asJavaConstant().asInt()); - } - - @Test - public void t5b() { - String snippet = "t5Snippet"; - StructuredGraph graph = afterFlowSensitiveReduce(snippet); - canonicalize(graph); - nodeCountEquals(graph, InstanceOfNode.class, 2); - } - - public boolean t6Snippet(Object x, Object y) { - if (!(x instanceof String)) { - return false; - } - if (!(y instanceof Number)) { - return false; - } - return x == y; // two known-not-to-conform reference values can't be == - } - - // TODO: two known-not-to-conform reference values can't be == - // but baseCaseObjectEqualsNode doesn't check that as of now. - public void t6() { - String snippet = "t6Snippet"; - // visualize(snippet); - StructuredGraph graph = afterFlowSensitiveReduce(snippet); - canonicalize(graph); - nodeCountEquals(graph, ObjectEqualsNode.class, 0); - } - - /* - * A previous instanceof check causes a follow-up instanceof to be deemed unsatisfiable, - * resulting in constant-substitution at that usage. - */ - public Object t7Snippet(Object o) { - if (o instanceof Number) { - if (o instanceof String) { // condition amounts to false - return o; // made unreachable - } - } - return null; - } - - @Test - public void t7() { - String snippet = "t7Snippet"; - StructuredGraph graph = afterFlowSensitiveReduce(snippet); - graph = dce(canonicalize(graph)); - // TODO how to simplify IfNode(false) - assertDeepEquals(1, getNodes(graph, InstanceOfNode.class).size()); - - List returnNodes = getNodes(graph, ReturnNode.class); - assertDeepEquals(2, returnNodes.size()); - Iterator iter = returnNodes.iterator(); - - ConstantNode c1 = (ConstantNode) iter.next().result(); - ConstantNode c2 = (ConstantNode) iter.next().result(); - - assertDeepEquals(c1, c2); - Assert.assertTrue(c1.isNullConstant()); - } - - /* - * During FlowSensitiveReduction, an unreachable branch doesn't contribute to the merged state. - * The resulting ("non-polluted") more precise inferred type after the merge allows - * devirtualizing a callsite. - */ - public int devirtualizationSnippet02(Number o) { - if (o instanceof Integer) { - Number z = o; - if (o instanceof Long) { - z = o; - } - /* - * devirtualized into InvokeSpecial on Integer.intValue() ie the inferred-type is not - * polluted with values from the unreachable branch. - */ - return z.intValue(); - } - return 0; - } - - @Test - public void devirtualizationTest02() { - String snippet = "devirtualizationSnippet02"; - StructuredGraph graph = afterFlowSensitiveReduce(snippet); - - assertDeepEquals(1, getNodes(graph, InvokeNode.class).size()); - - List invokeNodes = getNodes(graph, InvokeNode.class); - assertDeepEquals(1, invokeNodes.size()); - - MethodCallTargetNode target = (MethodCallTargetNode) invokeNodes.get(0).callTarget(); - assertDeepEquals(MethodCallTargetNode.InvokeKind.Special, target.invokeKind()); - assertDeepEquals("HotSpotMethod", target.targetMethod().toString()); - } - - /* - * TODO ClassCastException known to fail --- either Deopt or throw ObjectGetClassNode The latter - * might lead to direct jump to EH if present. - */ - @SuppressWarnings("unused") - public int t9Snippet(Object o) { - try { - if (o instanceof Number) { - String s = (String) o; - /* - * make a long story short: replace the above with throw new ClassCastException (ok, - * actual type of o unknown). - */ - return 1; - } - } catch (ClassCastException e) { - return 2; - } - return 3; - } - - /* - * "Partial evaluation" via canonicalization of an expression (in the last return statement) one - * of whose leaf sub-expressions was determined to be constant. - */ - @SuppressWarnings("unused") - public Object partialEvalSnippet01(Object o, boolean b) { - if (o == null) { - return o; // turned into "return null;" - } else { - Number z; - if (b) { - z = (Number) o; - } else { - z = (Integer) o; - } - return o instanceof String ? this : null; // turned into "return null;" - } - } - - @Test - public void partialEvalTest01() { - String snippet = "partialEvalSnippet01"; - - StructuredGraph graph = afterFlowSensitiveReduce(snippet); - canonicalize(graph); - dce(graph); - - List returnNodes = getNodes(graph, ReturnNode.class); - assertDeepEquals(2, returnNodes.size()); - Iterator iter = returnNodes.iterator(); - - ValueNode c1 = GraphUtil.unproxify(iter.next().result()); - ValueNode c2 = GraphUtil.unproxify(iter.next().result()); - assert !iter.hasNext(); - - Assert.assertTrue(c1.isNullConstant()); - Assert.assertTrue(c2.isNullConstant()); - } - - public static class C { - public int f; - } - - /* - * A previous (assumed successful) instanceof check is reused later on to remove a checkcast. - */ - public void deduplicateInstanceOfSnippet(Object o) { - ((C) o).f = ((C) o).f; // boils down to a single instanceof test - } - - @Test - public void deduplicateInstanceOfTest() { - String snippet = "deduplicateInstanceOfSnippet"; - StructuredGraph graph = afterFlowSensitiveReduce(snippet); - List ioNodes = getNodes(graph, InstanceOfNode.class); - assertDeepEquals(1, ioNodes.size()); - - } - - // --------------------------------------------- - // ----------------- UTILITIES ----------------- - // --------------------------------------------- - - private PhaseContext getPhaseContext() { - return new PhaseContext(getProviders(), null); - } - - private static StructuredGraph dce(StructuredGraph graph) { - new DeadCodeEliminationPhase().apply(graph); - return graph; - } - - private StructuredGraph canonicalize(StructuredGraph graph) { - new CanonicalizerPhase(true).apply(graph, getPhaseContext()); - return graph; - } - - private StructuredGraph flowSensitiveReduce(StructuredGraph graph) { - new FlowSensitiveReductionPhase(getMetaAccess()).apply(graph, getPhaseContext()); - return graph; - } - - public static List getNodes(StructuredGraph graph, Class nodeClass) { - return graph.getNodes().filter(nodeClass).snapshot(); - } - - public void nodeCountEquals(StructuredGraph graph, Class nodeClass, int expected) { - assertDeepEquals(expected, getNodes(graph, nodeClass).size()); - } - - public StructuredGraph afterFlowSensitiveReduce(String snippet) { - StructuredGraph before = canonicalize(parseEager(snippet)); - // visualize(before, snippet + "-before"); - StructuredGraph result = flowSensitiveReduce(before); - // visualize(result, snippet + "-after"); - return result; - } - - public StructuredGraph visualize(StructuredGraph graph, String title) { - DebugConfig debugConfig = DebugScope.getConfig(); - DebugConfig fixedConfig = Debug.fixedConfig(0, Debug.DEFAULT_LOG_LEVEL, false, false, false, false, debugConfig.dumpHandlers(), debugConfig.verifyHandlers(), debugConfig.output()); - try (DebugConfigScope s = Debug.setConfig(fixedConfig)) { - Debug.dump(graph, title); - - return graph; - } - } - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/FlowSensitiveReductionTest.java --- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/FlowSensitiveReductionTest.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,289 +0,0 @@ -/* - * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.compiler.test; - -import static com.oracle.graal.nodes.ConstantNode.*; -import static com.oracle.graal.nodes.extended.BranchProbabilityNode.*; -import static org.junit.Assert.*; - -import org.junit.*; - -import com.oracle.graal.nodes.CallTargetNode.InvokeKind; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.calc.*; -import com.oracle.graal.nodes.java.*; -import com.oracle.graal.nodes.spi.*; -import com.oracle.graal.phases.common.*; -import com.oracle.graal.phases.common.cfs.*; -import com.oracle.graal.phases.tiers.*; - -/** - * Collection of tests for {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase} - * including those that triggered bugs in this phase. - */ -public class FlowSensitiveReductionTest extends GraalCompilerTest { - - public static Object field; - - static class Entry { - - final String name; - - public Entry(String name) { - this.name = name; - } - } - - static class EntryWithNext extends Entry { - - public EntryWithNext(String name, Entry next) { - super(name); - this.next = next; - } - - final Entry next; - } - - public static Entry search(Entry start, String name, Entry alternative) { - Entry current = start; - do { - while (current instanceof EntryWithNext) { - if (name != null && current.name == name) { - current = null; - } else { - Entry next = ((EntryWithNext) current).next; - current = next; - } - } - - if (current != null) { - if (current.name.equals(name)) { - return current; - } - } - if (current == alternative) { - return null; - } - current = alternative; - - } while (true); - } - - /** - * This test presents a code pattern that triggered a bug where a (non-eliminated) checkcast - * caused an enclosing instanceof (for the same object and target type) to be incorrectly - * eliminated. - */ - @Test - public void testReanchoringIssue() { - Entry end = new Entry("end"); - EntryWithNext e1 = new EntryWithNext("e1", end); - EntryWithNext e2 = new EntryWithNext("e2", e1); - - test("search", e2, "e3", new Entry("e4")); - } - - @SuppressWarnings("unused") - public static int testNullnessSnippet(Object a, Object b) { - if (a == null) { - if (a == b) { - if (b == null) { - return 1; - } else { - return -2; - } - } else { - if (b == null) { - return -3; - } else { - return 4; - } - } - } else { - if (a == b) { - if (b == null) { - return -5; - } else { - return 6; - } - } else { - if (b == null) { - return 7; - } else { - return 8; - } - } - } - } - - @Test - public void testNullness() { - test("testNullnessSnippet", null, null); - test("testNullnessSnippet", null, new Object()); - test("testNullnessSnippet", new Object(), null); - test("testNullnessSnippet", new Object(), new Object()); - - StructuredGraph graph = parseEager("testNullnessSnippet"); - PhaseContext context = new PhaseContext(getProviders(), null); - new FlowSensitiveReductionPhase(getMetaAccess()).apply(graph, context); - new CanonicalizerPhase(true).apply(graph, context); - for (ConstantNode constant : getConstantNodes(graph)) { - assertTrue("unexpected constant: " + constant, constant.isNullConstant() || constant.asJavaConstant().asInt() > 0); - } - } - - @SuppressWarnings("unused") - public static int testDisjunctionSnippet(Object a) { - try { - if (a instanceof Integer) { - if (a == null) { - return -1; - } else { - return 2; - } - } else { - return 3; - } - } finally { - field = null; - } - } - - @Test - public void testDisjunction() { - StructuredGraph graph = parseEager("testDisjunctionSnippet"); - new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), null)); - IfNode ifNode = (IfNode) graph.start().next(); - InstanceOfNode instanceOf = (InstanceOfNode) ifNode.condition(); - IsNullNode x = graph.unique(new IsNullNode(graph.getParameter(0))); - InstanceOfNode y = instanceOf; - ShortCircuitOrNode disjunction = graph.unique(new ShortCircuitOrNode(x, false, y, false, NOT_FREQUENT_PROBABILITY)); - LogicNegationNode negation = graph.unique(new LogicNegationNode(disjunction)); - ifNode.setCondition(negation); - new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), null)); - new FlowSensitiveReductionPhase(getMetaAccess()).apply(graph, new PhaseContext(getProviders(), null)); - new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), null)); - for (ConstantNode constant : getConstantNodes(graph)) { - assertTrue("unexpected constant: " + constant, constant.isNullConstant() || constant.asJavaConstant().asInt() > 0); - } - } - - public static int testInvokeSnippet(Number n) { - if (n instanceof Integer) { - return n.intValue(); - } else { - return 1; - } - } - - @Test - public void testInvoke() { - test("testInvokeSnippet", new Integer(16)); - StructuredGraph graph = parseEager("testInvokeSnippet"); - PhaseContext context = new PhaseContext(getProviders(), null); - new CanonicalizerPhase(true).apply(graph, context); - new FlowSensitiveReductionPhase(getMetaAccess()).apply(graph, context); - - InvokeNode invoke = graph.getNodes().filter(InvokeNode.class).first(); - assertDeepEquals(InvokeKind.Special, ((MethodCallTargetNode) invoke.callTarget()).invokeKind()); - } - - public static void testTypeMergingSnippet(Object o, boolean b) { - if (b) { - if (!(o instanceof Double)) { - return; - } - } else { - if (!(o instanceof Integer)) { - return; - } - } - - /* - * For this test the conditional elimination has to correctly merge the type information it - * has about o, so that it can remove the check on Number. - */ - if (!(o instanceof Number)) { - field = o; - } - } - - @Test - public void testTypeMerging() { - StructuredGraph graph = parseEager("testTypeMergingSnippet"); - PhaseContext context = new PhaseContext(getProviders(), null); - new CanonicalizerPhase(true).apply(graph, context); - new FlowSensitiveReductionPhase(getMetaAccess()).apply(graph, context); - new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), null)); - - assertDeepEquals(0, graph.getNodes().filter(StoreFieldNode.class).count()); - } - - public static String testInstanceOfCheckCastSnippet(Object e) { - if (e instanceof Entry) { - return ((Entry) e).name; - } - return null; - } - - @Test - public void testInstanceOfCheckCast() { - StructuredGraph graph = parseEager("testInstanceOfCheckCastSnippet"); - PhaseContext context = new PhaseContext(getProviders(), null); - new CanonicalizerPhase(true).apply(graph, context); - new FlowSensitiveReductionPhase(getMetaAccess()).apply(graph, context); - new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), null)); - - assertDeepEquals(0, graph.getNodes().filter(CheckCastNode.class).count()); - } - - public static int testDuplicateNullChecksSnippet(Object a) { - if (a == null) { - return 2; - } - try { - return ((Integer) a).intValue(); - } catch (ClassCastException e) { - return 0; - } - } - - @Test - @Ignore - public void testDuplicateNullChecks() { - // This tests whether explicit null checks properly eliminate later null guards. Currently - // it's failing. - StructuredGraph graph = parseEager("testDuplicateNullChecksSnippet"); - CanonicalizerPhase canonicalizer = new CanonicalizerPhase(true); - PhaseContext context = new PhaseContext(getProviders(), null); - - new LoweringPhase(canonicalizer, LoweringTool.StandardLoweringStage.HIGH_TIER).apply(graph, context); - canonicalizer.apply(graph, context); - new FloatingReadPhase().apply(graph); - new FlowSensitiveReductionPhase(getMetaAccess()).apply(graph, context); - canonicalizer.apply(graph, context); - - assertDeepEquals(1, graph.getNodes().filter(GuardNode.class).count()); - } - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ScalarTypeSystemTest.java --- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ScalarTypeSystemTest.java Fri Jan 23 22:00:55 2015 +0100 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ScalarTypeSystemTest.java Fri Jan 23 22:13:55 2015 +0100 @@ -28,7 +28,6 @@ import com.oracle.graal.debug.*; import com.oracle.graal.nodes.*; import com.oracle.graal.phases.common.*; -import com.oracle.graal.phases.common.cfs.*; import com.oracle.graal.phases.tiers.*; /** @@ -104,28 +103,6 @@ } } - @Test - public void test4() { - test("test4Snippet", "referenceSnippet2"); - } - - public static int test4Snippet(int a, int b) { - if (a > b) { - if (a <= b) { - return 3; - } else { - return 1; - } - } else { - return 2; - } - } - - @Test - public void test5() { - test("test5Snippet", "referenceSnippet3"); - } - public static int referenceSnippet3(int a, int b) { if (a == b) { return 1; @@ -134,18 +111,6 @@ } } - public static int test5Snippet(int a, int b) { - if (a == b) { - if (a != b) { - return 3; - } else { - return 1; - } - } else { - return 2; - } - } - @Test(expected = AssertionError.class) public void test6() { test("test6Snippet", "referenceSnippet3"); @@ -169,7 +134,6 @@ Debug.dump(graph, "Graph"); Assumptions assumptions = new Assumptions(false); PhaseContext context = new PhaseContext(getProviders(), assumptions); - new FlowSensitiveReductionPhase(getMetaAccess()).apply(graph, context); new CanonicalizerPhase(true).apply(graph, context); StructuredGraph referenceGraph = parseEager(referenceSnippet); assertEquals(referenceGraph, graph); diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/TypeSystemTest.java --- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/TypeSystemTest.java Fri Jan 23 22:00:55 2015 +0100 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/TypeSystemTest.java Fri Jan 23 22:13:55 2015 +0100 @@ -34,7 +34,6 @@ import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.phases.common.*; -import com.oracle.graal.phases.common.cfs.*; import com.oracle.graal.phases.schedule.*; import com.oracle.graal.phases.tiers.*; @@ -45,30 +44,6 @@ public class TypeSystemTest extends GraalCompilerTest { @Test - public void test1() { - testHelper("test1Snippet", CheckCastNode.class); - } - - public static int test1Snippet(Object a) { - if (a instanceof Boolean) { - return ((Boolean) a).booleanValue() ? 0 : 1; - } - return 1; - } - - @Test - public void test2() { - testHelper("test2Snippet", CheckCastNode.class); - } - - public static int test2Snippet(Object a) { - if (a instanceof Integer) { - return ((Number) a).intValue(); - } - return 1; - } - - @Test public void test3() { test("test3Snippet", "referenceSnippet3"); } @@ -258,7 +233,6 @@ StructuredGraph graph = parseEager(snippet); Assumptions assumptions = new Assumptions(false); new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), assumptions)); - new FlowSensitiveReductionPhase(getMetaAccess()).apply(graph, new PhaseContext(getProviders(), assumptions)); new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), assumptions)); Debug.dump(graph, "Graph " + snippet); Assert.assertFalse("shouldn't have nodes of type " + clazz, graph.getNodes().filter(clazz).iterator().hasNext()); diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/HighTier.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/HighTier.java Fri Jan 23 22:00:55 2015 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/HighTier.java Fri Jan 23 22:13:55 2015 +0100 @@ -31,7 +31,6 @@ import com.oracle.graal.options.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; -import com.oracle.graal.phases.common.cfs.*; import com.oracle.graal.phases.common.inlining.*; import com.oracle.graal.phases.tiers.*; import com.oracle.graal.virtual.phases.ea.*; @@ -60,14 +59,9 @@ appendPhase(new InliningPhase(canonicalizer)); appendPhase(new DeadCodeEliminationPhase(Optional)); - boolean reduceOrEliminate = FlowSensitiveReduction.getValue() || ConditionalElimination.getValue(); - if (reduceOrEliminate && OptCanonicalizer.getValue()) { + if (ConditionalElimination.getValue() && OptCanonicalizer.getValue()) { appendPhase(canonicalizer); - if (FlowSensitiveReduction.getValue()) { - appendPhase(new IterativeFlowSensitiveReductionPhase(canonicalizer)); - } else { - appendPhase(new IterativeConditionalEliminationPhase(canonicalizer)); - } + appendPhase(new IterativeConditionalEliminationPhase(canonicalizer)); } } } diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/BaseReduction.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/BaseReduction.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,233 +0,0 @@ -/* - * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import java.util.*; - -import com.oracle.graal.api.code.*; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.compiler.common.type.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.spi.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.phases.graph.*; -import com.oracle.graal.phases.tiers.*; - -/** - *

- * For readability purposes the code realizing control-flow-sensitive reductions is chopped into - * several classes in an inheritance hierarchy, this class being their common ancestor. That way, - * many dependencies can be ruled out immediately (e.g., private members of a class aren't needed by - * other classes). The whole thing is reminiscent of trait-based patterns, minus their - * disadvantages. - *

- * - *

- * This class makes available little more than a few fields and a few utility methods used - * throughout the remaining components making up control-flow sensitive reductions. - *

- * - *

- * The laundry-list of all flow-sensitive reductions is summarized in - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction} - *

- * - */ -public abstract class BaseReduction extends SinglePassNodeIterator { - - protected static final DebugMetric metricCheckCastRemoved = Debug.metric("FSR-CheckCastRemoved"); - protected static final DebugMetric metricGuardingPiNodeRemoved = Debug.metric("FSR-GuardingPiNodeRemoved"); - protected static final DebugMetric metricFixedGuardNodeRemoved = Debug.metric("FSR-FixedGuardNodeRemoved"); - protected static final DebugMetric metricMethodResolved = Debug.metric("FSR-MethodResolved"); - protected static final DebugMetric metricUnconditionalDeoptInserted = Debug.metric("FSR-UnconditionalDeoptInserted"); - - /** - *

- * Upon visiting a {@link com.oracle.graal.nodes.FixedNode FixedNode} in - * {@link #node(com.oracle.graal.nodes.FixedNode)}, an impossible path may be detected. We'd - * like to insert an unconditional deoptimizing node as a hint for Dead Code Elimination to kill - * that branch. However that can't be made on the go (a - * {@link com.oracle.graal.nodes.ControlSinkNode} can't have successors). Thus their insertion - * is postponed till the end of a round of - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction}. - *

- * - * @see State#impossiblePath() - * @see com.oracle.graal.phases.common.cfs.FlowSensitiveReduction#finished() - */ - public static class PostponedDeopt { - - private final boolean goesBeforeFixed; - private final FixedWithNextNode fixed; - private final DeoptimizationReason deoptReason; - - public PostponedDeopt(boolean goesBeforeFixed, FixedWithNextNode fixed, DeoptimizationReason deoptReason) { - this.goesBeforeFixed = goesBeforeFixed; - this.fixed = fixed; - this.deoptReason = deoptReason; - } - - /* - * TODO Actually, we want to emit instructions to signal "should-not-reach-here". An - * imperfect substitute (as done here) is emitting FixedGuard(false). - * "should-not-reach-here" would be better for the runtime error it raises, thus pointing to - * a bug in FlowSensitiveReduction (the code was reachable, after all). - */ - public void doRewrite(LogicNode falseConstant) { - metricUnconditionalDeoptInserted.increment(); - StructuredGraph graph = fixed.graph(); - // have to insert a FixedNode other than a ControlSinkNode - FixedGuardNode buckStopsHere = graph.add(new FixedGuardNode(falseConstant, deoptReason, DeoptimizationAction.None)); - if (goesBeforeFixed) { - fixed.replaceAtPredecessor(buckStopsHere); - } else { - graph.addAfterFixed(fixed, buckStopsHere); - } - } - - } - - protected static class PostponedDeopts extends ArrayList { - - private static final long serialVersionUID = 7188324432387121238L; - - /** - * Enqueue adding a {@link com.oracle.graal.nodes.DeoptimizeNode} right before the fixed - * argument, will be done once we're done traversing the graph. - * - * @see #finished() - */ - void addDeoptBefore(FixedWithNextNode fixed, DeoptimizationReason deoptReason) { - add(new PostponedDeopt(true, fixed, deoptReason)); - } - - /** - * Enqueue adding a {@link com.oracle.graal.nodes.DeoptimizeNode} right after the fixed - * argument, will be done once we're done traversing the graph. - * - * @see #finished() - */ - void addDeoptAfter(FixedWithNextNode fixed, DeoptimizationReason deoptReason) { - add(new PostponedDeopt(false, fixed, deoptReason)); - } - - } - - /** - *

- * One of the promises of - * {@link com.oracle.graal.phases.common.cfs.EquationalReasoner#deverbosify(com.oracle.graal.graph.Node)} - * is that a "maximally reduced" node is returned. That is achieved in part by leveraging - * {@link Canonicalizable#canonical(com.oracle.graal.graph.spi.CanonicalizerTool)}. Doing so, in - * turn, requires this subclass of {@link com.oracle.graal.graph.spi.CanonicalizerTool}. - *

- */ - public final class Tool implements CanonicalizerTool { - - private final PhaseContext context; - - public Tool(PhaseContext context) { - this.context = context; - } - - @Override - public Assumptions assumptions() { - return context.getAssumptions(); - } - - @Override - public MetaAccessProvider getMetaAccess() { - return context.getMetaAccess(); - } - - @Override - public ConstantReflectionProvider getConstantReflection() { - return context.getConstantReflection(); - } - - @Override - public boolean canonicalizeReads() { - return false; - } - } // end of class FlowSensitiveReduction.Tool - - protected final LogicConstantNode trueConstant; - protected final LogicConstantNode falseConstant; - protected final ConstantNode nullConstant; - - protected final CanonicalizerTool tool; - protected final StructuredGraph graph; - - protected EquationalReasoner reasoner; - - protected final PostponedDeopts postponedDeopts = new PostponedDeopts(); - - protected BaseReduction(StartNode start, State initialState, PhaseContext context) { - super(start, initialState); - graph = start.graph(); - trueConstant = LogicConstantNode.tautology(graph); - falseConstant = LogicConstantNode.contradiction(graph); - nullConstant = ConstantNode.defaultForKind(Kind.Object, graph); // ConstantNode.forObject(null, - // metaAccess, graph); - tool = new Tool(context); - reasoner = new EquationalReasoner(graph, tool, trueConstant, falseConstant, nullConstant); - } - - /** - *

- * Test whether the output's stamp is an upcast of that of the input. For example, upon - * replacing a CheckCastNode in - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction#lowerCheckCastAnchorFriendlyWay(com.oracle.graal.nodes.java.CheckCastNode, com.oracle.graal.nodes.ValueNode)} - * we don't want to be left with an upcast, as it loses precision. - *

- * - *

- * As usual with object stamps, they can be compared along different dimensions (alwaysNull, - * etc.) It's enough for one such dimension to show precision loss for the end result to be - * reported as such. - *

- * - */ - public static boolean precisionLoss(ValueNode input, ValueNode output) { - ObjectStamp inputStamp = (ObjectStamp) input.stamp(); - ObjectStamp outputStamp = (ObjectStamp) output.stamp(); - if (FlowUtil.isMorePrecise(inputStamp.type(), outputStamp.type())) { - return true; - } - if (lessThan(outputStamp.alwaysNull(), inputStamp.alwaysNull())) { - return true; - } - if (lessThan(outputStamp.nonNull(), inputStamp.nonNull())) { - return true; - } - if (lessThan(outputStamp.isExactType(), inputStamp.isExactType())) { - return true; - } - return false; - } - - private static boolean lessThan(boolean a, boolean b) { - return a == false && b == true; - } - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CastCheckExtractor.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CastCheckExtractor.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,87 +0,0 @@ -/* - * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import com.oracle.graal.api.meta.ResolvedJavaType; -import com.oracle.graal.nodes.LogicNode; -import com.oracle.graal.nodes.ShortCircuitOrNode; -import com.oracle.graal.nodes.ValueNode; -import com.oracle.graal.nodes.calc.IsNullNode; -import com.oracle.graal.nodes.java.InstanceOfNode; - -/** - * @see #extract(com.oracle.graal.nodes.LogicNode) - */ -class CastCheckExtractor { - - public final ResolvedJavaType type; - public final ValueNode subject; - - CastCheckExtractor(ResolvedJavaType type, ValueNode subject) { - this.type = type; - this.subject = subject; - } - - private static CastCheckExtractor extractCastCheckInfo(LogicNode x, LogicNode y) { - if (x instanceof IsNullNode) { - IsNullNode isNull = (IsNullNode) x; - ValueNode subject = isNull.getValue(); - if (isInstanceOfCheckOn(y, subject)) { - InstanceOfNode iOf = (InstanceOfNode) y; - return new CastCheckExtractor(iOf.type(), subject); - } - } - return null; - } - - /** - * This method detects whether the argument realizes the CheckCast pattern. If so, distills and - * returns the essentials of such check, otherwise returns null. - */ - static CastCheckExtractor extract(LogicNode cond) { - if (!(cond instanceof ShortCircuitOrNode)) { - return null; - } - ShortCircuitOrNode orNode = (ShortCircuitOrNode) cond; - if (orNode.isXNegated() || orNode.isYNegated()) { - return null; - } - CastCheckExtractor result = extractCastCheckInfo(orNode.getX(), orNode.getY()); - if (result != null) { - return result; - } - result = extractCastCheckInfo(orNode.getY(), orNode.getX()); - return result; - } - - /** - * Porcelain method. - */ - static boolean isInstanceOfCheckOn(LogicNode cond, ValueNode subject) { - if (!(cond instanceof InstanceOfNode)) { - return false; - } - InstanceOfNode io = (InstanceOfNode) cond; - return io.getValue() == subject; - } -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CheckCastReduction.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CheckCastReduction.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,364 +0,0 @@ -/* - * Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import com.oracle.graal.api.meta.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.calc.IsNullNode; -import com.oracle.graal.nodes.java.*; -import com.oracle.graal.compiler.common.type.ObjectStamp; -import com.oracle.graal.compiler.common.type.StampFactory; -import com.oracle.graal.nodes.type.StampTool; -import com.oracle.graal.phases.tiers.PhaseContext; - -import static com.oracle.graal.api.meta.DeoptimizationAction.InvalidateReprofile; -import static com.oracle.graal.api.meta.DeoptimizationReason.*; -import static com.oracle.graal.nodes.extended.BranchProbabilityNode.NOT_FREQUENT_PROBABILITY; - -/** - *

- * This class implements control-flow sensitive reductions for - * {@link com.oracle.graal.nodes.java.CheckCastNode}. - *

- * - *

- * The laundry-list of all flow-sensitive reductions is summarized in - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction} - *

- * - * @see #visitCheckCastNode(com.oracle.graal.nodes.java.CheckCastNode) - */ -public abstract class CheckCastReduction extends GuardingPiReduction { - - public CheckCastReduction(StartNode start, State initialState, PhaseContext context) { - super(start, initialState, context); - } - - /** - *

- * Upon visiting a {@link com.oracle.graal.nodes.java.CheckCastNode}, based on flow-sensitive - * conditions, we need to determine whether: - *

    - *
  • it is redundant (in which case it should be simplified), or
    • - *
  • flow-sensitive information can be gained from it. "Gain information from it" requires - * lowering the {@link com.oracle.graal.nodes.java.CheckCastNode} such that a - * {@link com.oracle.graal.nodes.extended.GuardingNode GuardingNode} becomes available.
    • - *
- *

- * - *

- * This method realizes the above by testing first for situations that require less work: - *

    - *
  1. the stamp of the subject deems the check-cast redundant or unsatisfiable (ie, - * always-succeeds or always-fails). A previous round of canonicalization takes care of this - * situation, however it can also arise due to consecutive runs of - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase} without intervening - * {@link com.oracle.graal.phases.common.CanonicalizerPhase canonicalization}.
    2. - *
  2. - * flow-sensitive information reveals the subject to be null, trivially fulfilling the - * check-cast.
    3. - *
  3. - * flow-sensitive information reveals the subject to be narrower than it stamp says. If the - * narrower ("downcasted") value fulfills the check-cast, the check-cast is removed.
    4. - *
  4. - * otherwise the check-cast provides additional flow-sensitive information. For that, a - * {@link com.oracle.graal.nodes.FixedGuardNode} is needed, as described in - * {@link #lowerCheckCastAnchorFriendlyWay(com.oracle.graal.nodes.java.CheckCastNode, com.oracle.graal.nodes.ValueNode)} - * . Please notice this lowering is currently performed unconditionally: it might occur no - * flow-sensitive reduction is enabled down the road.
    5. - *
- *

- * - *

- * Precondition: the inputs (ie, object) hasn't been deverbosified yet. - *

- */ - protected final void visitCheckCastNode(CheckCastNode checkCast) { - - /* - * checkCast.object() hasn't been deverbosified yet. - */ - - if (!FlowUtil.hasLegalObjectStamp(checkCast)) { - // This situation is exercised by test Class_cast01 - return; - } - - final ValueNode subject = checkCast.object(); - final ResolvedJavaType toType = checkCast.type(); - ObjectStamp subjectStamp = (ObjectStamp) subject.stamp(); - ResolvedJavaType subjectType = subjectStamp.type(); - - // --------- checkCast deemed redundant by subject-stamp alone --------- - // --------- in particular due to stamp informing always null ---------- - boolean isRedundantPerStamp = StampTool.isPointerAlwaysNull(subject) || (subjectType != null && toType.isAssignableFrom(subjectType)); - if (isRedundantPerStamp) { - metricCheckCastRemoved.increment(); - checkCast.replaceAtUsages(subject); - graph.removeFixed(checkCast); - return; - } - - assert !StampTool.isPointerAlwaysNull(subject) : "Null as per stamp subjects should have been handled above"; - - // --------- checkCast deemed unsatisfiable by subject-stamp alone --------- - if (state.knownNotToPassCheckCast(subject, toType)) { - postponedDeopts.addDeoptBefore(checkCast, checkCast.isForStoreCheck() ? ArrayStoreException : ClassCastException); - state.impossiblePath(); - // let FixedGuardNode(false).simplify() prune the dead-code control-path - return; - } - - /* - * Remark: subject may be TypeProxyNode, GuardedValueNode, ProxyNode, GuardingPiNode, among - * others. - */ - - PiNode untrivialNull = reasoner.nonTrivialNull(subject); - if (untrivialNull != null) { - metricCheckCastRemoved.increment(); - checkCast.replaceAtUsages(untrivialNull); - graph.removeFixed(checkCast); - return; - } - - Witness w = state.typeInfo(subject); - - if (w == null) { - /* - * If there's no witness, attempting `downcast(subject)` is futile. - */ - visitCheckCastNodeLackingWitness(checkCast); - return; - } - - visitCheckCastNodeWithWitness(checkCast); - - } - - /** - * Given that no witness is available for the {@link com.oracle.graal.nodes.java.CheckCastNode} - * 's subject there's no point in downcasting such subject, ie no - * {@link com.oracle.graal.nodes.PiNode} can be fabricated for the subject. - * - * @see #lowerCheckCastAnchorFriendlyWay(com.oracle.graal.nodes.java.CheckCastNode, - * com.oracle.graal.nodes.ValueNode) - * - */ - private void visitCheckCastNodeLackingWitness(CheckCastNode checkCast) { - final ValueNode subject = checkCast.object(); - final ResolvedJavaType toType = checkCast.type(); - if (toType.isInterface()) { - return; - } - assert reasoner.downcast(subject) == subject; - lowerCheckCastAnchorFriendlyWay(checkCast, subject); - } - - /** - * Porcelain method. - * - *

- * Rather than tracking the CheckCastNode via {@link com.oracle.graal.phases.common.cfs.State - * State} (doing so would add a special case because a - * {@link com.oracle.graal.nodes.java.CheckCastNode} isn't a - * {@link com.oracle.graal.nodes.extended.GuardingNode guarding node}) this method creates an - * anchor by lowering the CheckCastNode into a FixedGuardNode. Not the same as the - * {@link com.oracle.graal.nodes.java.CheckCastNode#lower(com.oracle.graal.nodes.spi.LoweringTool) - * lowering of a CheckCastNode} which results in a {@link com.oracle.graal.nodes.GuardingPiNode} - * (which is not a {@link com.oracle.graal.nodes.extended.GuardingNode guarding node}). - *

- * - *

- * With that, state tracking can proceed as usual. - *

- * - *

- * TODO This lowering is currently performed unconditionally: it might occur no flow-sensitive - * reduction is enabled down the road - *

- * - * @see #visitCheckCastNode(com.oracle.graal.nodes.java.CheckCastNode) - * - */ - public void lowerCheckCastAnchorFriendlyWay(CheckCastNode checkCast, ValueNode subject) { - ValueNode originalCheckCastObject = checkCast.object(); - - ObjectStamp subjectStamp = (ObjectStamp) subject.stamp(); - final ResolvedJavaType toType = checkCast.type(); - ObjectStamp resultStamp = (ObjectStamp) StampFactory.declaredTrusted(toType); - JavaTypeProfile profile = checkCast.profile(); - - assert FlowUtil.isLegalObjectStamp(subjectStamp); - assert subjectStamp.type() == null || !toType.isAssignableFrom(subjectStamp.type()) : "No need to lower in an anchor-friendly way in the first place"; - - /* - * Depending on what is known about the subject: - * - * (a) definitely-non-null - * - * (b) null-not-seen-in-profiling - * - * (c) runtime-null-check-needed - * - * the condition (of the cast-guard to be emitted) and the stamp (of the PiNode to be - * emitted) are going to be different. Each of the three branches below deals with one of - * the cases above. - */ - LogicNode condition; - if (subjectStamp.nonNull()) { - /* - * (1 of 3) definitely-non-null - */ - // addWithoutUnique for the same reason as in CheckCastNode.lower() - condition = graph.addWithoutUnique(new InstanceOfNode(toType, subject, profile)); - reasoner.added.add(condition); - resultStamp = FlowUtil.asNonNullStamp(resultStamp); - // TODO fix in CheckCastNode.lower() - } else { - if (profile != null && profile.getNullSeen() == ProfilingInfo.TriState.FALSE) { - /* - * (2 of 3) null-not-seen-in-profiling - */ - IsNullNode isNN = graph.unique(new IsNullNode(subject)); - reasoner.added.add(isNN); - FixedGuardNode nullCheck = graph.add(new FixedGuardNode(isNN, UnreachedCode, InvalidateReprofile, true)); - graph.addBeforeFixed(checkCast, nullCheck); - // not calling wrapInPiNode() because we don't want to rememberSubstitution() - PiNode nonNullGuarded = graph.unique(new PiNode(subject, FlowUtil.asNonNullStamp(subjectStamp), nullCheck)); - reasoner.added.add(nonNullGuarded); - // addWithoutUnique for the same reason as in CheckCastNode.lower() - condition = graph.addWithoutUnique(new InstanceOfNode(toType, nonNullGuarded, profile)); - reasoner.added.add(condition); - resultStamp = FlowUtil.asNonNullStamp(resultStamp); - } else { - /* - * (3 of 3) runtime-null-check-needed - */ - // addWithoutUnique for the same reason as in CheckCastNode.lower() - InstanceOfNode typeTest = graph.addWithoutUnique(new InstanceOfNode(toType, subject, profile)); - reasoner.added.add(typeTest); - LogicNode nullTest = graph.unique(new IsNullNode(subject)); - reasoner.added.add(nullTest); - // TODO (ds) replace with probability of null-seen when available - final double shortCircuitProbability = NOT_FREQUENT_PROBABILITY; - condition = LogicNode.or(nullTest, typeTest, shortCircuitProbability); - reasoner.added.add(condition); - } - } - - /* - * Add a cast-guard (checking only what needs to be checked) and a PiNode (to be used in - * place of the CheckCastNode). - */ - FixedGuardNode castGuard = graph.add(new FixedGuardNode(condition, checkCast.isForStoreCheck() ? ArrayStoreException : ClassCastException, InvalidateReprofile)); - graph.addBeforeFixed(checkCast, castGuard); - - assert FlowUtil.isLegalObjectStamp(resultStamp); - Witness w = state.typeInfo(subject); - assert !isTypeOfWitnessBetter(w, resultStamp); - - if (!FlowUtil.lacksUsages(checkCast)) { - // not calling wrapInPiNode() because we don't want to rememberSubstitution() - PiNode checkedObject = graph.unique(new PiNode(subject, resultStamp, castGuard)); - reasoner.added.add(checkedObject); - assert !precisionLoss(originalCheckCastObject, checkedObject); - assert !precisionLoss(subject, checkedObject); - checkCast.replaceAtUsages(checkedObject); - } - - graph.removeFixed(checkCast); - - if (resultStamp.nonNull()) { - state.trackIO(subject, toType, castGuard); - } else { - state.trackCC(subject, toType, castGuard); - } - } - - /** - * Porcelain method. - */ - public static boolean isTypeOfWitnessBetter(Witness w, ObjectStamp stamp) { - if (w == null) { - return false; - } - return FlowUtil.isMorePrecise(w.type(), stamp.type()); - } - - /** - * - * Please note in this method "subject" refers to the downcasted input to the checkCast. - * - * @see #visitCheckCastNode(com.oracle.graal.nodes.java.CheckCastNode) - */ - private void visitCheckCastNodeWithWitness(CheckCastNode checkCast) { - - final ResolvedJavaType toType = checkCast.type(); - - ValueNode subject; - if (checkCast.object() instanceof CheckCastNode) { - subject = reasoner.downcast(checkCast); - if (subject == checkCast) { - subject = reasoner.downcast(checkCast.object()); - } - } else { - subject = reasoner.downcast(checkCast.object()); - } - - ObjectStamp subjectStamp = (ObjectStamp) subject.stamp(); - ResolvedJavaType subjectType = subjectStamp.type(); - - /* - * At this point, two sources of (partial) information: the witness and the stamp of - * subject. The latter might be more precise than the witness (eg, subject might be - * GuardedValueNode) - */ - - // --------- checkCast made redundant by downcasting its input --------- - if (subjectType != null && toType.isAssignableFrom(subjectType)) { - checkCast.replaceAtUsages(subject); - graph.removeFixed(checkCast); - return; - } - - /* - * At this point, `downcast()` might or might not have delivered a more precise value. If - * more precise, it wasn't precise enough to conform to `toType`. Even so, for the - * `toType.isInterface()` case (dealt with below) we'll replace the checkCast's input with - * that value (its class-stamp being more precise than the original). - */ - - if (toType.isInterface()) { - boolean wasDowncasted = (subject != checkCast.object()); - if (wasDowncasted) { - FlowUtil.replaceInPlace(checkCast, checkCast.object(), subject); - } - return; - } - - lowerCheckCastAnchorFriendlyWay(checkCast, subject); - - } - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/EquationalReasoner.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/EquationalReasoner.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,960 +0,0 @@ -/* - * Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import java.util.*; - -import com.oracle.graal.api.meta.*; -import com.oracle.graal.compiler.common.type.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.graph.spi.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.calc.*; -import com.oracle.graal.nodes.extended.*; -import com.oracle.graal.nodes.java.*; -import com.oracle.graal.nodes.spi.*; -import com.oracle.graal.nodes.type.*; -import com.oracle.graal.nodes.util.*; - -/** - *

- * This class implements a simple partial evaluator that recursively reduces a given - * {@link com.oracle.graal.nodes.calc.FloatingNode} into a simpler one based on the current state. - * Such evaluator comes handy when visiting a {@link com.oracle.graal.nodes.FixedNode} N, just - * before updating the state for N. At the pre-state, an {@link EquationalReasoner} can be used to - * reduce N's inputs (actually only those inputs of Value and Condition - * {@link com.oracle.graal.nodeinfo.InputType InputType}). For an explanation of where it's - * warranted to replace "old input" with "reduced input", see the inline comments in method - * {@link EquationalReasoner#deverbosify(com.oracle.graal.graph.Node n) deverbosify(Node n)} - *

- * - *

- * The name {@link EquationalReasoner EquationalReasoner} was chosen because it conveys what it - * does. - *

- */ -public final class EquationalReasoner { - - private static final DebugMetric metricInstanceOfRemoved = Debug.metric("FSR-InstanceOfRemoved"); - private static final DebugMetric metricNullCheckRemoved = Debug.metric("FSR-NullCheckRemoved"); - private static final DebugMetric metricObjectEqualsRemoved = Debug.metric("FSR-ObjectEqualsRemoved"); - private static final DebugMetric metricEquationalReasoning = Debug.metric("FSR-EquationalReasoning"); - private static final DebugMetric metricDowncasting = Debug.metric("FSR-Downcasting"); - private static final DebugMetric metricNullInserted = Debug.metric("FSR-NullInserted"); - - private final StructuredGraph graph; - private final CanonicalizerTool tool; - private final LogicConstantNode trueConstant; - private final LogicConstantNode falseConstant; - private final ConstantNode nullConstant; - - private State state; - private NodeBitMap visited; - - /** - * The reduction of a {@link com.oracle.graal.nodes.calc.FloatingNode} performed by - * {@link EquationalReasoner EquationalReasoner} may result in a FloatingNode being added to the - * graph. Those nodes aren't tracked in the {@link EquationalReasoner#visited visited} - * {@link com.oracle.graal.graph.NodeBitMap NodeBitMap} but in this set instead (those nodes are - * added after the {@link com.oracle.graal.graph.NodeBitMap} was obtained). - */ - final Set added = Node.newSet(); - - /** - * The reduction of a FloatingNode performed by {@link EquationalReasoner EquationalReasoner} - * may result in a FloatingNode being added to the graph. Those nodes are tracked in this map, - * to avoid recomputing them. - * - * The substitutions tracked in this field become invalid as described in - * {@link #updateState(com.oracle.graal.phases.common.cfs.State) updateState(State)} - */ - private final Map substs = Node.newIdentityMap(); - - public EquationalReasoner(StructuredGraph graph, CanonicalizerTool tool, LogicConstantNode trueConstant, LogicConstantNode falseConstant, ConstantNode nullConstant) { - this.graph = graph; - this.tool = tool; - this.trueConstant = trueConstant; - this.falseConstant = falseConstant; - this.nullConstant = nullConstant; - } - - /** - * {@link #added} grows during a run of - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase - * FlowSensitiveReductionPhase}, and doesn't survive across runs. - */ - public void forceState(State s) { - state = s; - assert state.repOK(); - substs.clear(); - added.clear(); - visited = null; - versionNrAsofLastForce = s.versionNr; - } - - /** - *

- * Gaining more precise type information about an SSA value doesn't "invalidate" as such any of - * the substitutions tracked in {@link EquationalReasoner#substs substs}, at least not in the - * sense of making the value tracked by one such entry "wrong". However, clearing the - * {@link EquationalReasoner#substs substs} is still justified because next time they are - * computed, the newly computed reduction could (in principle) be more effective (due to the - * more precise type information). - *

- * - *

- * Between clearings of cached substitutions, it is expected they get applied a number of times - * to justify the bookkeeping cost. - *

- * - */ - public void updateState(State s) { - assert s != null; - if (state == null || state != s || state.versionNr != versionNrAsofLastForce) { - forceState(s); - } - } - - private int versionNrAsofLastForce = 0; - - /** - * Reduce the argument based on the state at the program point where the argument is consumed. - * For most FixedNodes, that's how their inputs can be reduced. Two exceptions: - *
    - *
  • - * the condition of a {@link com.oracle.graal.nodes.GuardingPiNode}, see - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction#visitGuardingPiNode(com.oracle.graal.nodes.GuardingPiNode)} - *
    • - *
  • - * the condition of a {@link com.oracle.graal.nodes.FixedGuardNode}, see - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction#visitFixedGuardNode(com.oracle.graal.nodes.FixedGuardNode)} - *
    • - * - *
- * - * - *

- * Part of the reduction work is delegated to baseCase-style reducers, whose contract explicitly - * requires them not to deverbosify the argument's inputs --- the decision is made based on the - * argument only (thus "base case"). Returning the unmodified argument is how a baseCase-style - * tells this method to fall to the default case (for a floating node only: walk into the - * argument's inputs, canonicalize followed by - * {@link #rememberSubstitution(com.oracle.graal.nodes.ValueNode, com.oracle.graal.nodes.ValueNode) - * rememberSubstitution()} if any input changed). - *

- * - *

- * This method must behave as a function (idempotent query method), ie refrain from mutating the - * state other than updating caches: - *

    - *
  • {@link EquationalReasoner#added EquationalReasoner#added},
    • - *
  • {@link EquationalReasoner#visited EquationalReasoner#visited} and
    • - *
  • the cache updated via - * {@link EquationalReasoner#rememberSubstitution(com.oracle.graal.nodes.ValueNode, com.oracle.graal.nodes.ValueNode) - * EquationalReasoner#rememberSubstitution(ValueNode, FloatingNode)}.
    • - *
- *

- * - *

- * In turn, baseCase-style reducers are even more constrained: besides behaving as functions, - * their contract prevents them from updating any caches (basically because they already grab - * the answer from caches, if the answer isn't there they should just return their unmodified - * argument). - *

- * - *

- * This method returns: - *

    - *
  • - * the original argument, in case no reduction possible.
    • - *
  • - * a {@link com.oracle.graal.nodes.ValueNode ValueNode} different from the argument, in case the - * conditions for a reduction were met. The node being returned might be already in the graph. - * In any case it's canonicalized already, the caller need not perform that again.
    • - *
  • - * the unmodified argument, in case no reduction was made. Otherwise, a maximally reduced - * {@link com.oracle.graal.nodes.ValueNode}.
    • - *
- *

- * - * @see com.oracle.graal.phases.common.cfs.FlowSensitiveReduction#deverbosifyInputsInPlace(com.oracle.graal.nodes.ValueNode) - * - * @see com.oracle.graal.phases.common.cfs.BaseReduction.Tool - * - */ - public Node deverbosify(final Node n) { - - // -------------------------------------------------------------------- - // cases that don't initiate any call-chain that may enter this method - // -------------------------------------------------------------------- - - if (n == null) { - return null; - } - assert !(n instanceof GuardNode) : "This phase not intended to run during MidTier"; - if (!(n instanceof ValueNode)) { - return n; - } - ValueNode v = (ValueNode) n; - if (v.stamp() instanceof IllegalStamp) { - return v; - } - if (FlowUtil.isLiteralNode(v)) { - return v; - } - ValueNode result = substs.get(v); - if (result != null) { - // picked cached substitution - return result; - } - if (FlowUtil.hasLegalObjectStamp(v) && state.isNull(v)) { - // it's ok to return nullConstant in deverbosify unlike in downcast - metricNullInserted.increment(); - return nullConstant; - } - if (v instanceof ValueProxy) { - return v; - } - if (!(n instanceof FloatingNode)) { - return n; - } - if ((visited != null && visited.contains(n)) || added.contains(v)) { - return v; - } - - // -------------------------------------------------------------------- - // stack overflow prevention via added, visited - // -------------------------------------------------------------------- - - if (visited == null) { - visited = graph.createNodeBitMap(); - } - visited.mark(n); - - /* - * Past this point, if we ever want `n` to be deverbosified, it must be looked-up by one of - * the cases above. One sure way to achieve that is with `rememberSubstitution(old, new)` - */ - - /* - * `deverbosifyFloatingNode()` will drill down over floating inputs, when that not possible - * anymore it resorts to calling `downcast()`. Thus it's ok to take the - * `deverbosifyFloatingNode()` route first, as no downcasting opportunity will be missed. - */ - return deverbosifyFloatingNode((FloatingNode) n); - } - - /** - * This method: - * - *
    - *
  • - * Recurses only over floating inputs to attempt reductions, leave anything else as is.
    • - *
  • - * Performs copy-on-write aka lazy-DAG-copying as described in source comments, in-line.
    • - *
  • - * Usage: must be called only from {@link #deverbosify(com.oracle.graal.graph.Node) - * deverbosify(Node)}.
    • - *
- */ - public Node deverbosifyFloatingNode(final FloatingNode n) { - - assert n != null : "Should have been caught in deverbosify()"; - assert !(n instanceof ValueProxy) : "Should have been caught in deverbosify()"; - assert !FlowUtil.isLiteralNode(n) : "Should have been caught in deverbosify()"; - - if (n instanceof PhiNode) { - /* - * Each input to a PhiNode should be deverbosified with the state applicable to the path - * providing such input, as done in visitAbstractEndNode() - */ - return n; - } - - final FloatingNode f = baseCaseFloating(n); - if (f != n) { - return f; - } - - FloatingNode changed = null; - for (ValueNode i : FlowUtil.distinctValueAndConditionInputs(f)) { - /* - * Although deverbosify() is invoked below, it's only for floating inputs. That way, the - * state can't be used to make invalid conclusions. - */ - Node j = (i instanceof FloatingNode) ? deverbosify(i) : i; - if (i != j) { - assert j != f; - if (changed == null) { - changed = (FloatingNode) f.copyWithInputs(); - added.add(changed); - // copyWithInputs() implies graph.unique(changed) - assert changed.isAlive(); - assert FlowUtil.lacksUsages(changed); - } - /* - * Note: we don't trade i for j at each usage of i (doing so would change meaning) - * but only at those usages consumed by `changed`. In turn, `changed` won't replace - * `n` at arbitrary usages, but only where such substitution is valid as per the - * state holding there. In practice, this means the buck stops at the "root" - * FixedNode on whose inputs deverbosify() is invoked for the first time, via - * deverbosifyInputsInPlace(). - */ - FlowUtil.replaceInPlace(changed, i, j); - } - } - if (changed == null) { - assert visited.contains(f) || added.contains(f); - return f; - } - FlowUtil.inferStampAndCheck(changed); - added.add(changed); - - if (changed instanceof Canonicalizable) { - ValueNode canon = (ValueNode) ((Canonicalizable) changed).canonical(tool); - if (canon != null && !canon.isAlive()) { - assert !canon.isDeleted(); - canon = graph.addOrUniqueWithInputs(canon); - } - // might be already in `added`, no problem adding it again. - added.add(canon); - rememberSubstitution(f, canon); - return canon; - } else { - return changed; - } - } - - /** - * In case of doubt (on whether a reduction actually triggered) it's always ok to invoke " - * rememberSubstitution(f, downcast(f))": this method records a map entry only if - * pre-image and image differ. - * - * @return the image of the substitution (ie, the second argument) unmodified. - */ - private M rememberSubstitution(ValueNode from, M to) { - assert from != null && to != null; - if (from == to) { - return to; - } - // we don't track literals because they map to themselves - if (FlowUtil.isLiteralNode(from)) { - assert from == to; - return to; - } - /* - * It's ok for different keys (which were not unique in the graph after all) to map to the - * same value. However any given key can't map to different values. - */ - ValueNode image = substs.get(from); - if (image != null) { - assert image == to; - return to; - } - substs.put(from, to); - return to; - } - - /** - * The contract for this baseCase-style method is covered in - * {@link EquationalReasoner#deverbosify(com.oracle.graal.graph.Node) - * EquationalReasoner#deverbosify()}. - * - * @return a {@link com.oracle.graal.nodes.calc.FloatingNode} different from the argument, in - * case a reduction was made. The node being returned might be already in the graph. In - * any case it's canonicalized already, the caller need not perform that again. In case - * no reduction was made, this method returns the unmodified argument. - */ - private FloatingNode baseCaseFloating(final FloatingNode f) { - if (f instanceof LogicNode) { - FloatingNode result = baseCaseLogicNode((LogicNode) f); - return rememberSubstitution(f, result); - } - return f; - } - - /** - *

- * Reduce the argument based on the state at the program point for it (ie, based on - * "valid facts" only, without relying on any floating-guard-assumption). - *

- * - *

- * The inputs of the argument aren't traversed into, for that - * {@link EquationalReasoner#deverbosify(com.oracle.graal.graph.Node) - * EquationalReasoner#deverbosify()} should be used instead. - *

- *

- * This method must behave as a function (idempotent query method): it should refrain from - * changing the state, as well as from updating caches (other than DebugMetric-s). - *

- * - * @return a {@link com.oracle.graal.nodes.LogicNode} different from the argument, in case a - * reduction was made. The node being returned might be already in the graph. In any - * case it's canonicalized already, the caller need not perform that again. In case no - * reduction was made, this method returns the unmodified argument. - * - */ - public FloatingNode baseCaseLogicNode(LogicNode condition) { - assert condition != null; - if (condition instanceof LogicConstantNode) { - return condition; - } else if (state.trueFacts.containsKey(condition)) { - metricEquationalReasoning.increment(); - return trueConstant; - } else if (state.falseFacts.containsKey(condition)) { - metricEquationalReasoning.increment(); - return falseConstant; - } else { - if (condition instanceof InstanceOfNode) { - return baseCaseInstanceOfNode((InstanceOfNode) condition); - } else if (condition instanceof IsNullNode) { - return baseCaseIsNullNode((IsNullNode) condition); - } else if (condition instanceof ObjectEqualsNode) { - return baseCaseObjectEqualsNode((ObjectEqualsNode) condition); - } else if (condition instanceof ShortCircuitOrNode) { - return baseCaseShortCircuitOrNode((ShortCircuitOrNode) condition); - } - } - return condition; - } - - /** - * Actually the same result delivered by this method could be obtained by just letting - * {@link EquationalReasoner#deverbosify(com.oracle.graal.graph.Node) - * EquationalReasoner#deverbosify()} handle the argument in the default case for floating nodes - * (ie, deverbosify inputs followed by canonicalize). However it's done here for metrics - * purposes. - * - * @return a {@link com.oracle.graal.nodes.LogicConstantNode}, in case a reduction was made; - * otherwise the unmodified argument. - * - */ - private LogicNode baseCaseInstanceOfNode(InstanceOfNode instanceOf) { - ValueNode scrutinee = GraphUtil.unproxify(instanceOf.getValue()); - if (!FlowUtil.hasLegalObjectStamp(scrutinee)) { - return instanceOf; - } - if (state.isNull(scrutinee)) { - metricInstanceOfRemoved.increment(); - return falseConstant; - } else if (state.knownNotToPassInstanceOf(scrutinee, instanceOf.type())) { - // scrutinee turns out to be null -> falseConstant right answer - // scrutinee not null, but known-not-to-conform -> falseConstant - metricInstanceOfRemoved.increment(); - return falseConstant; - } else if (state.isNonNull(scrutinee) && state.knownToConform(scrutinee, instanceOf.type())) { - metricInstanceOfRemoved.increment(); - return trueConstant; - } - return instanceOf; - } - - /** - * @return a {@link com.oracle.graal.nodes.LogicConstantNode}, in case a reduction was - * performed; otherwise the unmodified argument. - * - */ - private FloatingNode baseCaseIsNullNode(IsNullNode isNu) { - ValueNode object = isNu.getValue(); - if (!FlowUtil.hasLegalObjectStamp(object)) { - return isNu; - } - if (state.isNull(object)) { - metricNullCheckRemoved.increment(); - return trueConstant; - } else if (state.isNonNull(object)) { - metricNullCheckRemoved.increment(); - return falseConstant; - } - return isNu; - } - - /** - * @return a {@link com.oracle.graal.nodes.LogicConstantNode}, in case a reduction was made; - * otherwise the unmodified argument. - */ - private LogicNode baseCaseObjectEqualsNode(ObjectEqualsNode equals) { - if (!FlowUtil.hasLegalObjectStamp(equals.getX()) || !FlowUtil.hasLegalObjectStamp(equals.getY())) { - return equals; - } - ValueNode x = GraphUtil.unproxify(equals.getX()); - ValueNode y = GraphUtil.unproxify(equals.getY()); - if (state.isNull(x) && state.isNonNull(y) || state.isNonNull(x) && state.isNull(y)) { - metricObjectEqualsRemoved.increment(); - return falseConstant; - } else if (state.isNull(x) && state.isNull(y)) { - metricObjectEqualsRemoved.increment(); - return trueConstant; - } - return equals; - } - - /** - * The following is tried: - * - *
    - *
  1. - * A {@link com.oracle.graal.phases.common.cfs.Witness} that is at check-cast level level - * doesn't entail {@link com.oracle.graal.nodes.calc.IsNullNode} (on its own) nor - * {@link com.oracle.graal.nodes.java.InstanceOfNode} (also on its own) but of course it entails - * (IsNull || IsInstanceOf). Good thing - * {@link com.oracle.graal.phases.common.cfs.CastCheckExtractor} detects that very pattern.
    2. - *
  2. - * Otherwise return the unmodified argument (later on, - * {@link #deverbosifyFloatingNode(com.oracle.graal.nodes.calc.FloatingNode)} will attempt to - * simplify the {@link com.oracle.graal.nodes.ShortCircuitOrNode}).
    3. - *
- * - * @return a {@link com.oracle.graal.nodes.LogicConstantNode}, in case a reduction was made; - * otherwise the unmodified argument. - */ - private LogicNode baseCaseShortCircuitOrNode(ShortCircuitOrNode orNode) { - CastCheckExtractor cast = CastCheckExtractor.extract(orNode); - if (cast != null) { - if (state.knownToConform(cast.subject, cast.type)) { - return trueConstant; - } else if (state.knownNotToPassCheckCast(cast.subject, cast.type)) { - return falseConstant; - } - return orNode; - } - return orNode; - } - - /** - * It's always ok to use "downcast(object)" instead of " object" - * because this method re-wraps the argument in a {@link com.oracle.graal.nodes.PiNode} only if - * the new stamp is strictly more refined than the original. - * - *

- * This method does not - * {@link #rememberSubstitution(com.oracle.graal.nodes.ValueNode, com.oracle.graal.nodes.ValueNode)} - * . - *

- * - * @return One of: - *
    - *
  • a {@link com.oracle.graal.nodes.PiNode} with more precise stamp than the input if - * the state warrants such downcasting
    • - *
  • a {@link com.oracle.graal.nodes.java.CheckCastNode CheckCastNode} for the same - * scrutinee in question
    • - *
  • the unmodified argument otherwise.
    • - *
- */ - ValueNode downcast(final ValueNode object) { - - // ------------------------------------------------- - // actions based only on the stamp of the input node - // ------------------------------------------------- - - if (!FlowUtil.hasLegalObjectStamp(object)) { - return object; - } - if (FlowUtil.isLiteralNode(object)) { - return object; - } - if (StampTool.isPointerAlwaysNull(object.stamp())) { - return object; - } - - // ------------------------------------------ - // actions based on the stamp and the witness - // ------------------------------------------ - - ValueNode scrutinee = GraphUtil.unproxify(object); - - PiNode untrivialNull = nonTrivialNull(scrutinee); - if (untrivialNull != null) { - metricNullInserted.increment(); - return untrivialNull; - } - - Witness w = state.typeInfo(scrutinee); - if (w == null) { - // no additional hints being tracked for the scrutinee - return object; - } - - assert !w.clueless(); - - ObjectStamp inputStamp = (ObjectStamp) object.stamp(); - ObjectStamp witnessStamp = w.asStamp(); - if (inputStamp.equals(witnessStamp) || !FlowUtil.isMorePrecise(witnessStamp, inputStamp)) { - // the witness offers no additional precision over current one - fixupTypeProfileStamp(object); - return object; - } - - assert !FlowUtil.isMorePrecise(inputStamp.type(), w.type()); - - ValueNode result; - if (object instanceof ValueProxy) { - result = downcastValueProxy((ValueProxy) object, w); - } else { - result = downcastedUtil(object, w); - } - - assert !BaseReduction.precisionLoss(object, result); - - return result; - } - - /** - * TODO TypeProfileProxyNode.inferStamp doesn't infer non-null from non-null payload - * - *

- * And there's a bunch of asserts in - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase} that assert no - * type-precision gets lost. Thus the need to fix-up on our own, as done here. - *

- */ - private static void fixupTypeProfileStamp(ValueNode object) { - if (!(object instanceof TypeProfileProxyNode)) { - return; - } - TypeProfileProxyNode profile = (TypeProfileProxyNode) object; - ObjectStamp outgoinStamp = (ObjectStamp) profile.stamp(); - ObjectStamp payloadStamp = (ObjectStamp) profile.getValue().stamp(); - if (payloadStamp.nonNull() && !outgoinStamp.nonNull()) { - profile.setStamp(FlowUtil.asNonNullStamp(outgoinStamp)); - } - } - - /** - *

- * Porcelain method. - *

- * - *

- * Utility to create, add to the graph, - * {@link EquationalReasoner#rememberSubstitution(com.oracle.graal.nodes.ValueNode, com.oracle.graal.nodes.ValueNode)} - * , and return a {@link com.oracle.graal.nodes.PiNode} that narrows into the given stamp, - * anchoring the payload. - *

- * - *

- * The resulting node might not have been in the graph already. - *

- */ - private PiNode wrapInPiNode(ValueNode payload, GuardingNode anchor, ObjectStamp newStamp, boolean remember) { - try (Debug.Scope s = Debug.scope("Downcast", payload)) { - assert payload != anchor : payload.graph().toString(); - metricDowncasting.increment(); - PiNode result = graph.unique(new PiNode(payload, newStamp, anchor.asNode())); - // we've possibly got a new node in the graph --- bookkeeping is in order. - added.add(result); - if (remember) { - rememberSubstitution(payload, result); - } - Debug.log("Downcasting from %s to %s", payload, result); - return result; - } catch (Throwable e) { - throw Debug.handle(e); - } - } - - /** - * - * This method returns: - *
    - *
  • null, if the argument is known null due to its stamp. Otherwise,
    • - *
  • a PiNode wrapping the null constant and an anchor offering evidence as to why the - * argument is known null, if such anchor is available. Otherwise,
    • - *
  • null
    • - *
- *

- * This method does not - * {@link #rememberSubstitution(com.oracle.graal.nodes.ValueNode, com.oracle.graal.nodes.ValueNode)} - * . - *

- */ - public PiNode nonTrivialNull(ValueNode object) { - assert FlowUtil.hasLegalObjectStamp(object); - GuardingNode anchor = state.nonTrivialNullAnchor(object); - if (anchor == null) { - return null; - } - if (object instanceof GuardedNode && StampTool.isPointerAlwaysNull(object.stamp())) { - return (PiNode) object; - } - // notice nullConstant is wrapped, not object - PiNode result = wrapInPiNode(nullConstant, anchor, (ObjectStamp) StampFactory.alwaysNull(), false); - return result; - } - - // @formatter:off - /** - *

ValueProxys can be classified along two dimensions, - * in addition to the fixed-floating dichotomy.

- * - *

- * First, we might be interested in separating those ValueProxys - * that are entitled to change (usually narrow) their stamp from those that aren't. - * In the first category are: - * PiNode, PiArrayNode, GuardingPiNode, - * CheckCastNode, UnsafeCastNode, and - * GuardedValueNode. - *

- * - *

- * A note on stamp-narrowing ValueProxys: - * our state abstraction tracks only the type refinements induced by CheckCastNode and GuardingPiNode - * (which are fixed nodes, unlike the other stamp-narrowing ValueProxys; - * the reason being that the state abstraction can be updated only at fixed nodes). - * As a result, the witness for a (PiNode, PiArrayNode, UnsafeCastNode, or GuardedValueNode) - * may be less precise than the proxy's stamp. We don't want to lose such precision, - * thus downcast(proxy) == proxy in such cases. - *

- * - *

- * The second classification focuses on - * the additional information that travels with the proxy - * (in addition to its "payload", ie getOriginalValue(), and any narrowing-stamp). - * Such additional information boils down to: - * - * (a) type profile (TypeProfileProxyNode) - * (b) type profile (CheckCastNode) - * (c) anchor (GuardedValueNode) - * (d) anchor (PiNode) - * (e) anchor and array length (PiArrayNode) - * (f) optional anchor (UnsafeCastNode) - * (g) deopt-condition (GuardingPiNode) - * (h) LocationIdentity (MemoryProxyNOde) - * (i) control-flow dependency (FixedValueAnchorNode) - * (j) proxyPoint (ProxyNode -- think loops) - *

- */ - // @formatter:on - private ValueNode downcastValueProxy(ValueProxy proxy, Witness w) { - assert FlowUtil.hasLegalObjectStamp((ValueNode) proxy); - assert FlowUtil.hasLegalObjectStamp((proxy).getOriginalNode()); - assert GraphUtil.unproxify((ValueNode) proxy) == GraphUtil.unproxify(proxy.getOriginalNode()); - - assert GraphUtil.unproxify((ValueNode) proxy) == GraphUtil.unproxify((proxy).getOriginalNode()); - - if (proxy instanceof PiNode) { - return downcastPiNodeOrPiArrayNode((PiNode) proxy, w); - } else if (proxy instanceof GuardingPiNode) { - return downcastGuardingPiNode((GuardingPiNode) proxy, w); - } else if (proxy instanceof TypeProfileProxyNode) { - return downcastTypeProfileProxyNode((TypeProfileProxyNode) proxy); - } else if (proxy instanceof CheckCastNode) { - return downcastCheckCastNode((CheckCastNode) proxy, w); - } else if (proxy instanceof ProxyNode || proxy instanceof GuardedValueNode) { - // TODO scaladacapo return downcastedUtil((ValueNode) proxy, w); - return (ValueNode) proxy; - } - - assert false : "TODO case not yet handled"; - - // TODO complete the missing implementation for the cases not yet handled - - return ((ValueNode) proxy); - } - - /** - *

- * Why would we want to downcast a GuardingPiNode? Is it even possible? Like, for example, a - * GuardingPiNode originating in the lowering of a CheckCastNode (carried out by - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction#visitCheckCastNode(com.oracle.graal.nodes.java.CheckCastNode) - * visitCheckCastNode()}). - *

- * - *

- * It's both possible and desirable. Example: - * Number n = (Number) o; - * if (n instanceof Integer) { - * return n.intValue(); - * } - * - * - * The receiver of intValue() is a usage of a previous checkCast, for which the current witness - * provides a more refined type (and an anchor). In this case, the advantage of downcasting a - * GuardingPiNode is clear: devirtualizing the `intValue()` callsite. - *

- * - * @see #downcastValueProxy - */ - public ValueNode downcastGuardingPiNode(GuardingPiNode envelope, Witness w) { - assert envelope != w.guard().asNode() : "The stamp of " + envelope + " would lead to downcasting with that very same GuardingPiNode as guard."; - return downcastedUtil(envelope, w); - } - - /** - *

- * This method accepts both {@link com.oracle.graal.nodes.PiNode} and - * {@link com.oracle.graal.nodes.PiArrayNode} argument. - *

- * - *

- * In case a witness reveals a strictly more precise type than the - * {@link com.oracle.graal.nodes.PiNode}'s stamp, this method wraps the argument in a new - * {@link com.oracle.graal.nodes.PiNode} with updated stamp, and returns it. - *

- * - *

- * A {@link com.oracle.graal.nodes.PiArrayNode} argument ends up wrapped in a - * {@link com.oracle.graal.nodes.PiNode}. Thus, the - * {@link com.oracle.graal.nodes.PiArrayNode#length} information doesn't get lost. - *

- * - *

- * Note: {@link com.oracle.graal.nodes.PiNode}'s semantics allow un-packing its payload as soon - * as it type conforms to that of the {@link com.oracle.graal.nodes.PiNode} (that's what - * {@link com.oracle.graal.nodes.PiNode#canonical(com.oracle.graal.graph.spi.CanonicalizerTool) - * PiNode.canonical()} does). Not clear the benefits of duplicating that logic here. - *

- * - * @see #downcastValueProxy - */ - private ValueNode downcastPiNodeOrPiArrayNode(PiNode envelope, Witness w) { - return downcastedUtil(envelope, w); - } - - /** - *

- * In a case the payload of the {@link com.oracle.graal.nodes.TypeProfileProxyNode} can be - * downcasted, this method returns a copy-on-write version with the downcasted payload. - *

- * - *

- * Otherwise returns the unmodified argument. - *

- * - * @see #downcastValueProxy - */ - private ValueNode downcastTypeProfileProxyNode(TypeProfileProxyNode envelope) { - ValueNode payload = envelope.getOriginalNode(); - ValueNode d = downcast(payload); - if (payload != d) { - TypeProfileProxyNode changed = (TypeProfileProxyNode) envelope.copyWithInputs(); - added.add(changed); - // copyWithInputs() implies graph.unique(changed) - FlowUtil.replaceInPlace(changed, payload, d); - FlowUtil.inferStampAndCheck(changed); - fixupTypeProfileStamp(changed); - /* - * It's not prudent to (1) obtain the canonical() of the (changed) TypeProfileProxyNode - * to (2) replace its usages; because we're potentially walking a DAG (after all, - * TypeProfileProxyNode is a floating-node). Those steps, which admittedly are needed, - * are better performed upon replacing in-place the inputs of a FixedNode, or during - * Canonicalize. - */ - return changed; - } - fixupTypeProfileStamp(envelope); - return envelope; - } - - /** - *

- * Re-wrap the checkCast in a type-refining {@link com.oracle.graal.nodes.PiNode PiNode} only if - * the downcasted scrutinee does not conform to the checkCast's target-type. - *

- */ - private ValueNode downcastCheckCastNode(CheckCastNode checkCast, Witness w) { - - final ResolvedJavaType toType = checkCast.type(); - - if (checkCast.object() instanceof CheckCastNode) { - ValueNode innerMost = checkCast; - while (innerMost instanceof CheckCastNode) { - innerMost = ((CheckCastNode) innerMost).object(); - } - ValueNode deepest = downcast(innerMost); - ResolvedJavaType deepestType = ((ObjectStamp) deepest.stamp()).type(); - if ((deepestType != null && deepestType.equals(toType)) || FlowUtil.isMorePrecise(deepestType, toType)) { - assert !w.knowsBetterThan(deepest); - return deepest; - } - } - - ValueNode subject = downcast(checkCast.object()); - ObjectStamp subjectStamp = (ObjectStamp) subject.stamp(); - ResolvedJavaType subjectType = subjectStamp.type(); - - if (subjectType != null && toType.isAssignableFrom(subjectType)) { - assert !w.knowsBetterThan(subject); - return subject; - } - - return downcastedUtil(checkCast, w); - } - - /** - *

- * Porcelain method. - *

- * - *

- * This method wraps the argument in a new {@link com.oracle.graal.nodes.PiNode PiNode} (created - * to hold an updated stamp) provided the argument's stamp can be strictly refined, and returns - * it. - *

- */ - private ValueNode downcastedUtil(ValueNode subject, Witness w) { - - ObjectStamp originalStamp = (ObjectStamp) subject.stamp(); - ObjectStamp outgoingStamp = originalStamp; - - if (w.isNonNull() && !outgoingStamp.nonNull()) { - outgoingStamp = FlowUtil.asNonNullStamp(outgoingStamp); - } - if (FlowUtil.isMorePrecise(w.type(), outgoingStamp.type())) { - outgoingStamp = FlowUtil.asRefinedStamp(outgoingStamp, w.type()); - } - - if (outgoingStamp != originalStamp) { - assert FlowUtil.isMorePrecise(outgoingStamp, originalStamp); - - boolean isWitnessGuardAnAliasForScrutinee = false; - if (w.guard() instanceof GuardingPiNode || w.guard() instanceof PiNode) { - /* - * The guard offered by the witness canonicalizes into its subject (a possibly - * type-refined scrutinee) provided its subject conforms as per stamp. - */ - if (w.guard().asNode().stamp().equals(outgoingStamp)) { - isWitnessGuardAnAliasForScrutinee = true; - } - } - - ValueNode result; - if (isWitnessGuardAnAliasForScrutinee) { - result = w.guard().asNode(); - assert !w.knowsBetterThan(result); - return result; // TODO this works. explain why. - } else { - result = wrapInPiNode(subject, w.guard(), outgoingStamp, true); - assert !w.knowsBetterThan(result); - return result; - } - - } else { - assert !w.knowsBetterThan(subject); - return subject; - } - } - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Evidence.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Evidence.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,61 +0,0 @@ -/* - * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import com.oracle.graal.nodes.extended.GuardingNode; - -public class Evidence { - - public final GuardingNode success; - public final boolean failure; - - public Evidence(GuardingNode success, boolean failure) { - this.success = success; - this.failure = failure; - assert repOK(); - } - - public Evidence(GuardingNode success) { - this(success, false); - } - - private Evidence(boolean failure) { - this(null, failure); - } - - public boolean isPositive() { - return success != null; - } - - public boolean isNegative() { - return failure; - } - - private boolean repOK() { - // either success or failure, ie boolean-XOR - return (success != null) != failure; - } - - public static Evidence COUNTEREXAMPLE = new Evidence(true); - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,154 +0,0 @@ -/* - * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.extended.GuardingNode; -import com.oracle.graal.phases.tiers.PhaseContext; - -/** - *

- * This class implements control-flow sensitive reductions for - * {@link com.oracle.graal.nodes.FixedGuardNode}. - *

- * - *

- * The laundry-list of all flow-sensitive reductions is summarized in - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction} - *

- * - * @see #visitFixedGuardNode(com.oracle.graal.nodes.FixedGuardNode) - */ -public abstract class FixedGuardReduction extends CheckCastReduction { - - public FixedGuardReduction(StartNode start, State initialState, PhaseContext context) { - super(start, initialState, context); - } - - /** - *

- * Upon visiting a {@link com.oracle.graal.nodes.FixedGuardNode}, based on flow-sensitive - * conditions, we need to determine whether: - *

    - *
  • it is redundant (in which case it should be simplified), or
    • - *
  • flow-sensitive information can be gained from it.
    • - *
- *

- * - *

- * This method realizes the above by inspecting the - * {@link com.oracle.graal.nodes.FixedGuardNode}'s condition: - *

    - *
  1. a constant condition signals the node won't be reduced here
    2. - *
  2. the outcome of the condition can be predicted:
    3. - *
      - *
    • - * "always succeeds", after finding an equivalent (or stronger) - * {@link com.oracle.graal.nodes.extended.GuardingNode} in scope. The - * {@link com.oracle.graal.nodes.FixedGuardNode} is removed after replacing its usages with the - * existing guarding node
      • - *
    • - * "always fails", which warrants making that explicit by making the condition constant, see - * {@link #markFixedGuardNodeAlwaysFails(com.oracle.graal.nodes.FixedGuardNode)}
      • - *
    - *
  3. otherwise the condition is tracked flow-sensitively
    4. - *
- *

- * - *

- * Precondition: the condition hasn't been deverbosified yet. - *

- */ - protected final void visitFixedGuardNode(FixedGuardNode f) { - - /* - * A FixedGuardNode with LogicConstantNode condition is left untouched. - * `FixedGuardNode.simplify()` will eventually remove the FixedGuardNode (in case it - * "always succeeds") or kill code ("always fails"). - */ - - if (f.condition() instanceof LogicConstantNode) { - if (FlowUtil.alwaysFails(f.isNegated(), f.condition())) { - state.impossiblePath(); - // let FixedGuardNode(false).simplify() prune the dead-code control-path - return; - } - assert FlowUtil.alwaysSucceeds(f.isNegated(), f.condition()); - return; - } - - final boolean isTrue = !f.isNegated(); - final Evidence evidence = state.outcome(isTrue, f.condition()); - - // can't produce evidence, must be information gain - if (evidence == null) { - state.addFact(isTrue, f.condition(), f); - return; - } - - if (evidence.isPositive()) { - /* - * A FixedGuardNode can only be removed provided a replacement anchor is found (so - * called "evidence"), ie an anchor that amounts to the same combination of (negated, - * condition) as for the FixedGuardNode at hand. Just deverbosifying the condition in - * place isn't semantics-preserving. - * - * Eliminate the current FixedGuardNode by using another GuardingNode already in scope, - * a GuardingNode that guards a condition that is at least as strong as that of the - * FixedGuardNode. - */ - removeFixedGuardNode(f, evidence.success); - return; - } - - assert evidence.isNegative(); - markFixedGuardNodeAlwaysFails(f); - - } - - /** - * Porcelain method. - */ - private void markFixedGuardNodeAlwaysFails(FixedGuardNode f) { - metricFixedGuardNodeRemoved.increment(); - state.impossiblePath(); - f.setCondition(f.isNegated() ? trueConstant : falseConstant); - // `f.condition()` if unused will be removed in finished() - } - - /** - * Porcelain method. - * - *

- * The `replacement` guard must be such that it implies the `old` guard. Moreover, rhe - * `replacement` guard must be in scope. - *

- */ - private void removeFixedGuardNode(FixedGuardNode old, GuardingNode replacement) { - assert replacement != null; - metricFixedGuardNodeRemoved.increment(); - old.replaceAtUsages(replacement.asNode()); - graph.removeFixed(old); - // `old.condition()` if unused will be removed in finished() - } -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowSensitiveReduction.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowSensitiveReduction.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,605 +0,0 @@ -/* - * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import static com.oracle.graal.api.meta.DeoptimizationAction.*; -import static com.oracle.graal.api.meta.DeoptimizationReason.*; -import static com.oracle.graal.phases.common.DeadCodeEliminationPhase.Optionality.*; - -import java.lang.reflect.*; - -import com.oracle.graal.api.meta.*; -import com.oracle.graal.compiler.common.type.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.calc.*; -import com.oracle.graal.nodes.extended.*; -import com.oracle.graal.nodes.java.*; -import com.oracle.graal.nodes.type.*; -import com.oracle.graal.nodes.util.*; -import com.oracle.graal.phases.common.*; -import com.oracle.graal.phases.tiers.*; - -/** - *

- * In a nutshell, {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase} makes a - * single pass in dominator-based order over the graph: - *

    - *
  1. collecting properties of interest at control-splits; as well as for check-casts, - * guarding-pis, null-checks, and fixed-guards. Such flow-sensitive information is tracked via a - * dedicated {@link com.oracle.graal.phases.common.cfs.State state instance} for each control-flow - * path.
    2. - *
  2. performing rewritings that are safe at specific program-points. This comprises: - *
      - *
    • simplification of side-effects free expressions, via - * {@link com.oracle.graal.phases.common.cfs.EquationalReasoner#deverbosify(com.oracle.graal.graph.Node)} - *
        - *
      • - * at certain {@link com.oracle.graal.nodes.FixedNode}, see - * {@link #deverbosifyInputsInPlace(com.oracle.graal.nodes.ValueNode)}
        • - *
      • - * including for devirtualization, see - * {@link #deverbosifyInputsCopyOnWrite(com.oracle.graal.nodes.java.MethodCallTargetNode)}
        • - *
      - *
      • - *
    • simplification of control-flow: - *
        - *
      • - * by simplifying the input-condition to an {@link com.oracle.graal.nodes.IfNode}
        • - *
      • - * by eliminating redundant check-casts, guarding-pis, null-checks, and fixed-guards; where - * "redundancy" is determined using flow-sensitive information. In these cases, redundancy can be - * due to: - *
          - *
        • an equivalent, existing, guarding node is already in scope (thus, use it as replacement and - * remove the redundant one)
          • - *
        • "always fails" (thus, replace the node in question with FixedGuardNode(false))
          • - *
        - *
        • - *
      - *
      • - *
    - *
    3. - *
- *

- * - *

- * Metrics for this phase are displayed starting with FSR-prefix, their counters are - * hosted in {@link com.oracle.graal.phases.common.cfs.BaseReduction}, - * {@link com.oracle.graal.phases.common.cfs.EquationalReasoner} and - * {@link com.oracle.graal.phases.common.cfs.State}. - *

- * - * @see com.oracle.graal.phases.common.cfs.CheckCastReduction - * @see com.oracle.graal.phases.common.cfs.GuardingPiReduction - * @see com.oracle.graal.phases.common.cfs.FixedGuardReduction - * - */ -public class FlowSensitiveReduction extends FixedGuardReduction { - - public FlowSensitiveReduction(StartNode start, State initialState, PhaseContext context) { - super(start, initialState, context); - } - - /** - *

- * This method performs two kinds of cleanup: - *

    - *
  1. - * marking as unreachable certain code-paths, as described in - * {@link com.oracle.graal.phases.common.cfs.BaseReduction.PostponedDeopt}
    2. - *
  2. - * Removing nodes not in use that were added during this phase, as described next.
    3. - *
- *

- * - * - *

- * Methods like - * {@link com.oracle.graal.phases.common.cfs.FlowUtil#replaceInPlace(com.oracle.graal.graph.Node, com.oracle.graal.graph.Node, com.oracle.graal.graph.Node)} - * may result in old inputs becoming disconnected from the graph. It's not advisable to - * {@link com.oracle.graal.nodes.util.GraphUtil#tryKillUnused(com.oracle.graal.graph.Node)} at - * that moment, because one of the inputs that might get killed is one of {@link #nullConstant}, - * {@link #falseConstant}, or {@link #trueConstant}; which thus could get killed too early, - * before another invocation of - * {@link com.oracle.graal.phases.common.cfs.EquationalReasoner#deverbosify(com.oracle.graal.graph.Node)} - * needs them. To recap, - * {@link com.oracle.graal.nodes.util.GraphUtil#tryKillUnused(com.oracle.graal.graph.Node)} also - * recursively visits the inputs of the its argument. - *

- * - *

- * This method goes over all of the nodes that deverbosification might have added, which are - * either: - *

    - *
  • - * {@link com.oracle.graal.nodes.calc.FloatingNode}, added by - * {@link com.oracle.graal.phases.common.cfs.EquationalReasoner#deverbosifyFloatingNode(com.oracle.graal.nodes.calc.FloatingNode)} - * ; or
    • - *
  • - * {@link com.oracle.graal.nodes.java.MethodCallTargetNode}, added by - * {@link #deverbosifyInputsCopyOnWrite(com.oracle.graal.nodes.java.MethodCallTargetNode)}
    • - *
- * - * Checking if they aren't in use, proceeding to remove them in that case. - *

- * - */ - @Override - public void finished() { - if (!postponedDeopts.isEmpty()) { - for (PostponedDeopt postponed : postponedDeopts) { - postponed.doRewrite(falseConstant); - } - new DeadCodeEliminationPhase(Optional).apply(graph); - } - for (MethodCallTargetNode mcn : graph.getNodes().filter(MethodCallTargetNode.class)) { - if (mcn.isAlive() && FlowUtil.lacksUsages(mcn)) { - mcn.safeDelete(); - } - } - for (Node n : graph.getNodes().filter(FloatingNode.class)) { - GraphUtil.tryKillUnused(n); - } - assert !isAliveWithoutUsages(trueConstant); - assert !isAliveWithoutUsages(falseConstant); - assert !isAliveWithoutUsages(nullConstant); - super.finished(); - } - - private static boolean isAliveWithoutUsages(FloatingNode node) { - return node.isAlive() && FlowUtil.lacksUsages(node); - } - - private void registerControlSplit(Node pred, BeginNode begin) { - assert pred != null && begin != null; - assert !state.isUnreachable; - - if (begin instanceof LoopExitNode) { - state.clear(); - /* - * TODO return or not? (by not returning we agree it's ok to update the state as below) - */ - } - - if (pred instanceof IfNode) { - registerIfNode((IfNode) pred, begin); - } else if (pred instanceof TypeSwitchNode) { - registerTypeSwitchNode((TypeSwitchNode) pred, begin); - } - } - - private void registerIfNode(IfNode ifNode, BeginNode begin) { - final boolean isThenBranch = (begin == ifNode.trueSuccessor()); - - if (ifNode.condition() instanceof LogicConstantNode) { - final LogicConstantNode constCond = (LogicConstantNode) ifNode.condition(); - if (isThenBranch != constCond.getValue()) { - state.impossiblePath(); - // let IfNode(constant) prune the dead-code control-path - } - } - - if (state.isUnreachable) { - if (!(ifNode.condition() instanceof LogicConstantNode)) { - // if condition constant, no need to add a Deopt node - postponedDeopts.addDeoptAfter(begin, UnreachedCode); - } - } else { - state.addFact(isThenBranch, ifNode.condition(), begin); - } - } - - /** - * TODO When tracking integer-stamps, the state at each successor of a TypeSwitchNode should - * track an integer-stamp for the LoadHubNode (meet over the constants leading to that - * successor). However, are LoadHubNode-s shared frequently enough? - */ - private void registerTypeSwitchNode(TypeSwitchNode typeSwitch, BeginNode begin) { - if (typeSwitch.value() instanceof LoadHubNode) { - LoadHubNode loadHub = (LoadHubNode) typeSwitch.value(); - ResolvedJavaType type = null; - for (int i = 0; i < typeSwitch.keyCount(); i++) { - if (typeSwitch.keySuccessor(i) == begin) { - if (type == null) { - type = typeSwitch.typeAt(i); - } else { - type = FlowUtil.widen(type, typeSwitch.typeAt(i)); - } - } - } - if (type == null) { - // `begin` denotes the default case of the TypeSwitchNode - return; - } - // it's unwarranted to assume loadHub.object() to be non-null - state.trackCC(loadHub.getValue(), type, begin); - } - } - - /** - * - *

- * Reduce input nodes based on the state at the program point for the argument (ie, based on - * "valid facts" only, without relying on any floating-guard-assumption). - *

- * - *

- * For each (direct or indirect) child, a copy-on-write version is made in case any of its - * children changed, with the copy accommodating the updated children. If the parent was shared, - * copy-on-write prevents the updates from becoming visible to anyone but the invoker of this - * method. - *

- * - *

- * Please note the parent node is mutated upon any descendant changing. No copy-on-write is - * performed for the parent node itself. - *

- * - *

- * In more detail, for each direct {@link com.oracle.graal.nodes.ValueNode} input of the node at - * hand, - * - *

    - *
  1. - * Obtain a lazy-copied version (via spanning tree) of the DAG rooted at the input-usage in - * question. Lazy-copying is done by walking a spanning tree of the original DAG, stopping at - * non-FloatingNodes but transitively walking FloatingNodes and their inputs. Upon arriving at a - * (floating) node N, the state's facts are checked to determine whether a constant C can be - * used instead in the resulting lazy-copied DAG. A NodeBitMap is used to realize the spanning - * tree.
    2. - * - *
  2. - * Provided one or more N-to-C node replacements took place, the resulting lazy-copied DAG has a - * parent different from the original (ie different object identity) which indicates the - * (copied, updated) DAG should replace the original via replaceFirstInput(), and inferStamp() - * should be invoked to reflect the updated inputs.
    3. - * - *
- *

- * - * @return whether any reduction was performed on the inputs of the arguments. - */ - public boolean deverbosifyInputsInPlace(ValueNode parent) { - boolean changed = false; - for (ValueNode i : FlowUtil.distinctValueAndConditionInputs(parent)) { - assert !(i instanceof GuardNode) : "This phase not intended to run during MidTier"; - ValueNode j = (ValueNode) reasoner.deverbosify(i); - if (i != j) { - changed = true; - FlowUtil.replaceInPlace(parent, i, j); - } - } - if (changed) { - FlowUtil.inferStampAndCheck(parent); - } - return changed; - } - - /** - * Similar to {@link #deverbosifyInputsInPlace(com.oracle.graal.nodes.ValueNode)}, except that - * not the parent but a fresh clone is updated upon any of its children changing. - * - * @return the original parent if no updated took place, a copy-on-write version of it - * otherwise. - * - */ - private MethodCallTargetNode deverbosifyInputsCopyOnWrite(MethodCallTargetNode parent) { - final CallTargetNode.InvokeKind ik = parent.invokeKind(); - boolean shouldDowncastReceiver = ik.isIndirect(); - MethodCallTargetNode changed = null; - for (ValueNode i : FlowUtil.distinctValueAndConditionInputs(parent)) { - ValueNode j = (ValueNode) reasoner.deverbosify(i); - if (shouldDowncastReceiver) { - shouldDowncastReceiver = false; - j = reasoner.downcast(j); - } - if (i != j) { - assert j != parent; - if (changed == null) { - changed = (MethodCallTargetNode) parent.copyWithInputs(); - reasoner.added.add(changed); - // copyWithInputs() implies graph.unique(changed) - assert changed.isAlive(); - assert FlowUtil.lacksUsages(changed); - } - FlowUtil.replaceInPlace(changed, i, j); - } - } - if (changed == null) { - return parent; - } - FlowUtil.inferStampAndCheck(changed); - /* - * No need to rememberSubstitution() because not called from deverbosify(). In detail, it's - * only deverbosify() that skips visited nodes (thus we'd better have recorded any - * substitutions we want for them). Not this case. - */ - return changed; - } - - /** - * Precondition: This method assumes that either: - * - *
    - *
  • the state has already stabilized (ie no more pending iterations in the "iterative" - * dataflow algorithm); or
    • - *
  • any rewritings made based on the state in its current form are conservative enough to be - * safe.
    • - *
- * - *

- * The overarching goal is to perform just enough rewriting to trigger other phases ( - * {@link com.oracle.graal.graph.spi.SimplifierTool SimplifierTool}, - * {@link com.oracle.graal.phases.common.DeadCodeEliminationPhase DeadCodeEliminationPhase}, - * etc) to perform the bulk of rewriting, thus lowering the maintenance burden. - *

- * - */ - @Override - protected void node(FixedNode node) { - - assert node.isAlive(); - - /*------------------------------------------------------------------------------------- - * Step 1: Unreachable paths are still visited (PostOrderNodeIterator requires all ends - * of a merge to have been visited), but time is saved by neither updating the state nor - * rewriting anything while on an an unreachable path. - *------------------------------------------------------------------------------------- - */ - if (state.isUnreachable) { - return; - } - - /*------------------------------------------------------------------------------------- - * Step 2: For an AbstractBeginNode, determine whether this path is reachable, register - * any associated guards. - *------------------------------------------------------------------------------------- - */ - if (node instanceof BeginNode) { - BeginNode begin = (BeginNode) node; - Node pred = node.predecessor(); - - if (pred != null) { - registerControlSplit(pred, begin); - } - return; - } - - /*------------------------------------------------------------------------------------- - * Step 3: Check whether EquationalReasoner caches should be cleared upon state updates. - *------------------------------------------------------------------------------------- - */ - reasoner.updateState(state); - - /*------------------------------------------------------------------------------------- - * Step 4: Whatever special-case handling makes sense for the FixedNode at hand before - * its inputs are reduced. - *------------------------------------------------------------------------------------- - */ - - if (node instanceof AbstractEndNode) { - visitAbstractEndNode((AbstractEndNode) node); - return; - } else if (node instanceof Invoke) { - visitInvoke((Invoke) node); - return; - } else if (node instanceof CheckCastNode) { - // it's important not to call deverbosification for visitCheckCastNode() - visitCheckCastNode((CheckCastNode) node); - return; - } else if (node instanceof GuardingPiNode) { - visitGuardingPiNode((GuardingPiNode) node); - return; - } else if (node instanceof NullCheckNode) { - visitNullCheckNode((NullCheckNode) node); - return; - } else if (node instanceof FixedGuardNode) { - visitFixedGuardNode((FixedGuardNode) node); - return; - } else if (node instanceof ConditionAnchorNode) { - // ConditionAnchorNode shouldn't occur during HighTier - return; - } - - /*------------------------------------------------------------------------------------- - * Step 5: After special-case handling, we do our best for those FixedNode-s - * where the effort to reduce their inputs might pay off. - * - * Why is this useful? For example, by the time the BeginNode for an If-branch - * is visited (in general a ControlSplitNode), the If-condition will have gone already - * through simplification (and thus potentially have been reduced to a - * LogicConstantNode). - *------------------------------------------------------------------------------------- - */ - boolean paysOffToReduce = false; - if (node instanceof ControlSplitNode) { - // desire to simplify control flow - paysOffToReduce = true; - } else if (node instanceof ReturnNode) { - paysOffToReduce = true; - } else if (node instanceof AccessFieldNode || node instanceof AccessArrayNode) { - // desire to remove null-checks - paysOffToReduce = true; - } - - // TODO comb remaining FixedWithNextNode subclasses, pick those with chances of paying-off - - // TODO UnsafeLoadNode takes a condition - - if (paysOffToReduce) { - deverbosifyInputsInPlace(node); - } - - /*--------------------------------------------------------------------------------------- - * Step 6: Any additional special-case handling, this time after having inputs reduced. - * For example, leverage anchors provided by the FixedNode, to add facts to the factbase. - *--------------------------------------------------------------------------------------- - */ - - // TODO some nodes are GuardingNodes (eg, FixedAccessNode) we could use them to track state - // TODO other nodes are guarded (eg JavaReadNode), thus *their* guards could be replaced. - - } - - /** - * In case the scrutinee: - * - *
    - *
  • is known to be null, an unconditional deopt is added.
    • - *
  • is known to be non-null, the NullCheckNode is removed.
    • - *
  • otherwise, the NullCheckNode is lowered to a FixedGuardNode which then allows using it as - * anchor for state-tracking.
    • - *
- * - *

- * Precondition: the input (ie, object) hasn't been deverbosified yet. - *

- */ - private void visitNullCheckNode(NullCheckNode ncn) { - ValueNode object = ncn.getObject(); - if (state.isNull(object)) { - postponedDeopts.addDeoptBefore(ncn, NullCheckException); - state.impossiblePath(); - return; - } - if (state.isNonNull(object)) { - /* - * Redundant NullCheckNode. Unlike GuardingPiNode or FixedGuardNode, NullCheckNode-s - * aren't used as GuardingNode-s, thus in this case can be removed without further ado. - */ - assert FlowUtil.lacksUsages(ncn); - graph.removeFixed(ncn); - return; - } - /* - * Lower the NullCheckNode to a FixedGuardNode which then allows using it as anchor for - * state-tracking. TODO the assumption here is that the code emitted for the resulting - * FixedGuardNode is as efficient as for NullCheckNode. - */ - IsNullNode isNN = graph.unique(new IsNullNode(object)); - reasoner.added.add(isNN); - FixedGuardNode nullCheck = graph.add(new FixedGuardNode(isNN, UnreachedCode, InvalidateReprofile, true)); - graph.replaceFixedWithFixed(ncn, nullCheck); - - state.trackNN(object, nullCheck); - } - - /** - * The {@link com.oracle.graal.nodes.AbstractEndNode} at the end of the current code path - * contributes values to {@link com.oracle.graal.nodes.PhiNode}s. Now is a good time to - * {@link EquationalReasoner#deverbosify(com.oracle.graal.graph.Node) - * EquationalReasoner#deverbosify} those values. - * - *

- * Precondition: inputs haven't been deverbosified yet. - *

- */ - private void visitAbstractEndNode(AbstractEndNode endNode) { - MergeNode merge = endNode.merge(); - for (PhiNode phi : merge.phis()) { - if (phi instanceof ValuePhiNode && phi.getKind() == Kind.Object) { - assert phi.verify(); - int index = merge.phiPredecessorIndex(endNode); - ValueNode original = phi.valueAt(index); - ValueNode reduced = (ValueNode) reasoner.deverbosify(original); - if (reduced != original) { - phi.setValueAt(index, reduced); - // `original` if unused will be removed in finished() - } - } - } - } - - /** - *

- * For one or more `invoke` arguments, flow-sensitive information may suggest their narrowing or - * simplification. In those cases, a new - * {@link com.oracle.graal.nodes.java.MethodCallTargetNode MethodCallTargetNode} is prepared - * just for this callsite, consuming reduced arguments. - *

- * - *

- * Specializing the {@link com.oracle.graal.nodes.java.MethodCallTargetNode - * MethodCallTargetNode} as described above may enable two optimizations: - *

    - *
  • - * devirtualization of an {@link com.oracle.graal.nodes.CallTargetNode.InvokeKind#Interface} or - * {@link com.oracle.graal.nodes.CallTargetNode.InvokeKind#Virtual} callsite (devirtualization - * made possible after narrowing the type of the receiver)
    • - *
  • - * (future work) actual-argument-aware inlining, ie, to specialize callees on the types of - * arguments other than the receiver (examples: multi-methods, the inlining problem, lambdas as - * arguments).
    • - * - *
- *

- * - *

- * Precondition: inputs haven't been deverbosified yet. - *

- */ - private void visitInvoke(Invoke invoke) { - if (invoke.asNode().stamp() instanceof IllegalStamp) { - return; // just to be safe - } - boolean isMethodCallTarget = invoke.callTarget() instanceof MethodCallTargetNode; - if (!isMethodCallTarget) { - return; - } - FlowUtil.replaceInPlace(invoke.asNode(), invoke.callTarget(), deverbosifyInputsCopyOnWrite((MethodCallTargetNode) invoke.callTarget())); - MethodCallTargetNode callTarget = (MethodCallTargetNode) invoke.callTarget(); - if (callTarget.invokeKind() != CallTargetNode.InvokeKind.Interface && callTarget.invokeKind() != CallTargetNode.InvokeKind.Virtual) { - return; - } - ValueNode receiver = callTarget.receiver(); - if (receiver == null) { - return; - } - if (!FlowUtil.hasLegalObjectStamp(receiver)) { - return; - } - Witness w = state.typeInfo(receiver); - ResolvedJavaType type; - ResolvedJavaType stampType = StampTool.typeOrNull(receiver); - if (w == null || w.cluelessAboutType()) { - // can't improve on stamp but wil try to devirtualize anyway - type = stampType; - } else { - type = FlowUtil.tighten(w.type(), stampType); - } - if (type == null) { - return; - } - ResolvedJavaMethod method = type.resolveConcreteMethod(callTarget.targetMethod(), invoke.getContextType()); - if (method == null) { - return; - } - if (method.canBeStaticallyBound() || Modifier.isFinal(type.getModifiers())) { - metricMethodResolved.increment(); - callTarget.setInvokeKind(CallTargetNode.InvokeKind.Special); - callTarget.setTargetMethod(method); - } - } - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowSensitiveReductionPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowSensitiveReductionPhase.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,58 +0,0 @@ -/* - * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import com.oracle.graal.api.meta.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.phases.*; -import com.oracle.graal.phases.tiers.PhaseContext; - -public class FlowSensitiveReductionPhase extends BasePhase { - - private final MetaAccessProvider metaAccess; - - public MetaAccessProvider getMetaAccess() { - return metaAccess; - } - - public FlowSensitiveReductionPhase(MetaAccessProvider metaAccess) { - this.metaAccess = metaAccess; - } - - @Override - protected final void run(StructuredGraph graph, PhaseContext context) { - try (Debug.Scope s = Debug.scope("FlowSensitiveReduction")) { - if (graph.isOSR()) { - Debug.log("Skipping OSR method %s", graph.method() == null ? "" : graph.method().format("%H.%n")); - return; - } - Debug.dump(graph, "FlowSensitiveReduction initial"); - new FlowSensitiveReduction(graph.start(), new State(), context).apply(); - Debug.dump(graph, "FlowSensitiveReduction done"); - } catch (Throwable e) { - throw Debug.handle(e); - } - } - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowUtil.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowUtil.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,284 +0,0 @@ -/* - * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import java.util.*; - -import com.oracle.graal.api.meta.*; -import com.oracle.graal.compiler.common.type.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.nodeinfo.*; -import com.oracle.graal.nodes.*; - -public final class FlowUtil { - - private FlowUtil() { - // no instances of this class - } - - public static boolean lacksUsages(Node n) { - return n.hasNoUsages(); - } - - public static ResolvedJavaType widen(ResolvedJavaType a, ResolvedJavaType b) { - if (a == null || b == null) { - return null; - } else if (a.equals(b)) { - return a; - } else { - return a.findLeastCommonAncestor(b); - } - } - - /** - * @return whether the first argument is strictly more precise than the second. - */ - public static boolean isMorePrecise(ResolvedJavaType a, ResolvedJavaType b) { - if (a == null) { - return false; - } - if (b == null) { - return true; - } - assert !a.isPrimitive(); - assert !b.isPrimitive(); - if (a.equals(b)) { - return false; - } - if (b.isInterface()) { - return b.isAssignableFrom(a); - } - if (a.isInterface()) { - return b.isInterface() && b.isAssignableFrom(a); - } - return b.isAssignableFrom(a); - } - - public static ResolvedJavaType tighten(ResolvedJavaType a, ResolvedJavaType b) { - if (a == null) { - assert b == null || !b.isPrimitive(); - return b; - } - if (b == null) { - assert !a.isPrimitive(); - return a; - } - assert !a.isPrimitive(); - assert !b.isPrimitive(); - if (a.equals(b)) { - return a; - } - if (isMorePrecise(a, b)) { - return a; - } else if (isMorePrecise(b, a)) { - return b; - } else { - /* - * Not comparable, two cases: - * - * Example 1: 'a' standing for j.l.Number and 'b' for j.l.String We return null for lack - * of a value representing NullType, the right answer. Same goes when both arguments are - * non-comparable interfaces. - * - * Example 2: 'a' standing for sun/nio/ch/DirectBuffer (an interface) and b for - * java/nio/Buffer (an abstract class). The class always takes precedence. - */ - if (a.isInterface()) { - return b.isInterface() ? null : b; - } - if (b.isInterface()) { - return a.isInterface() ? null : a; - } - return null; // a and b aren't comparable, can't tighten() them - } - } - - /** - * - * There are "illegal" stamps that are not of type IllegalStamp. - * - * For example, there may be an IntegerStamp with upperBound < lowerBound that returns - * !isLegal() but we still know it's an integer and thus not of type IllegalStamp. - * - * An IllegalStamp should never happen. In contrast, !isLegal() values could happen due to dead - * code not yet removed, or upon some non-sideeffecting instructions floating out of a dead - * branch. - */ - public static boolean isLegalObjectStamp(Stamp s) { - return isObjectStamp(s) && s.isLegal(); - } - - public static boolean hasLegalObjectStamp(ValueNode v) { - return isLegalObjectStamp(v.stamp()); - } - - public static boolean isObjectStamp(Stamp stamp) { - return stamp instanceof ObjectStamp; - } - - public static void inferStampAndCheck(ValueNode n) { - n.inferStamp(); - if (n.stamp() instanceof ObjectStamp) { - ObjectStamp objectStamp = (ObjectStamp) n.stamp(); - assert !objectStamp.isExactType() || objectStamp.type() != null; - } - } - - /** - * Compares the arguments along three dimensions (nullness, exactness, and type). For the first - * argument to be more precise than the second, it may not score lower in any dimension and must - * score higher in at least one dimension. - * - * When comparing types s and t, sameness counts as 0; while being more precise is awarded with - * a score of 1. In all other cases (non-comparable, or supertype) the score is -1. - * - * @return whether the first argument is strictly more precise than the second. - */ - public static boolean isMorePrecise(ObjectStamp a, ObjectStamp b) { - int d0 = minus(a.alwaysNull(), b.alwaysNull()); - if (d0 == -1) { - return false; - } - int d1 = minus(a.nonNull(), b.nonNull()); - if (d1 == -1) { - return false; - } - int d2 = minus(a.isExactType(), b.isExactType()); - if (d2 == -1) { - return false; - } - int d3; - ResolvedJavaType ta = a.type(); - ResolvedJavaType tb = b.type(); - if (ta == null) { - d3 = (tb == null) ? 0 : -1; - } else if (tb == null) { - d3 = 1; - } else if (isMorePrecise(ta, tb)) { - d3 = 1; - } else if (ta.equals(tb)) { - d3 = 0; - } else { - d3 = -1; - } - if (d3 == -1) { - return false; - } - int maxScore = Math.max(Math.max(d0, d1), Math.max(d2, d3)); - return maxScore > 0; - } - - private static int minus(boolean a, boolean b) { - int aa = a ? 1 : 0; - int bb = b ? 1 : 0; - return aa - bb; - } - - public static LogicConstantNode asLogicConstantNode(LogicNode cond) { - return (cond instanceof LogicConstantNode) ? (LogicConstantNode) cond : null; - } - - public static boolean isLiteralNode(ValueNode f) { - return f instanceof ConstantNode || f instanceof LogicConstantNode; - } - - public static boolean isConstantTrue(LogicNode cond) { - LogicConstantNode c = asLogicConstantNode(cond); - return (c != null) && c.getValue(); - } - - public static boolean isConstantFalse(LogicNode cond) { - LogicConstantNode c = asLogicConstantNode(cond); - return (c != null) && !c.getValue(); - } - - public static boolean alwaysFails(boolean isNegated, LogicNode cond) { - LogicConstantNode c = asLogicConstantNode(cond); - return (c != null) && (c.getValue() == isNegated); - } - - public static boolean alwaysSucceeds(boolean isNegated, LogicNode cond) { - LogicConstantNode c = asLogicConstantNode(cond); - return (c != null) && (c.getValue() != isNegated); - } - - /** - * Returns (preserving order) the ValueNodes without duplicates found among the argument's - * direct inputs. - */ - @SuppressWarnings("unchecked") - public static List distinctValueAndConditionInputs(Node n) { - ArrayList result = null; - NodePosIterator iter = n.inputs().iterator(); - while (iter.hasNext()) { - Position pos = iter.nextPosition(); - InputType inputType = pos.getInputType(); - boolean isReducibleInput = (inputType == InputType.Value || inputType == InputType.Condition); - if (isReducibleInput) { - ValueNode i = (ValueNode) pos.get(n); - if (!isLiteralNode(i)) { - if (result == null) { - result = new ArrayList<>(); - } - if (!result.contains(i)) { - result.add(i); - } - } - } - } - return result == null ? Collections.EMPTY_LIST : result; - } - - public static ObjectStamp asNonNullStamp(ObjectStamp stamp) { - ObjectStamp result = (ObjectStamp) stamp.join(StampFactory.objectNonNull()); - assert result.isLegal(); - return result; - } - - public static ObjectStamp asRefinedStamp(ObjectStamp stamp, ResolvedJavaType joinType) { - assert !joinType.isInterface(); - ObjectStamp result = (ObjectStamp) stamp.join(StampFactory.declared(joinType)); - assert result.isLegal(); - return result; - } - - /** - * Start situation: the parent node has oldInput among its (direct) inputs. After - * this method has run, all such occurrences have been replaced with newInput. In - * case that makes oldInput disconnected, it is removed from the graph. - */ - public static void replaceInPlace(Node parent, Node oldInput, Node newInput) { - assert parent != null; - assert parent.inputs().contains(oldInput); - if (oldInput == newInput) { - return; - } - assert oldInput != null && newInput != null; - assert !isLiteralNode((ValueNode) oldInput); - do { - parent.replaceFirstInput(oldInput, newInput); - } while (parent.inputs().contains(oldInput)); - // `oldInput` if unused wil be removed in finished() - } - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/GuardingPiReduction.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/GuardingPiReduction.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,384 +0,0 @@ -/* - * Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import com.oracle.graal.api.meta.*; -import com.oracle.graal.debug.Debug; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.calc.IsNullNode; -import com.oracle.graal.nodes.extended.GuardingNode; -import com.oracle.graal.nodes.java.*; -import com.oracle.graal.compiler.common.type.ObjectStamp; -import com.oracle.graal.nodes.type.StampTool; -import com.oracle.graal.phases.tiers.PhaseContext; - -/** - *

- * This class implements control-flow sensitive reductions for - * {@link com.oracle.graal.nodes.GuardingPiNode}. - *

- * - *

- * The laundry-list of all flow-sensitive reductions is summarized in - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction} - *

- * - * @see #visitGuardingPiNode(com.oracle.graal.nodes.GuardingPiNode) - */ -public abstract class GuardingPiReduction extends BaseReduction { - - public GuardingPiReduction(StartNode start, State initialState, PhaseContext context) { - super(start, initialState, context); - } - - /** - *

- * By the time a {@link com.oracle.graal.nodes.GuardingPiNode GuardingPiNode} is visited, the - * available type refinements may allow reductions similar to those performed for - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction#visitCheckCastNode(com.oracle.graal.nodes.java.CheckCastNode) - * CheckCastNode}. - *

- * - *
    - *
  1. - * If the condition needs no reduction (ie, it's already a - * {@link com.oracle.graal.nodes.LogicConstantNode LogicConstantNode}), this method basically - * gives up (thus letting other phases take care of it).
    2. - *
  2. - * Otherwise, an attempt is made to find a {@link com.oracle.graal.nodes.extended.GuardingNode} - * that implies the combination of (negated, condition) of the - * {@link com.oracle.graal.nodes.GuardingPiNode} being visited. Details in - * {@link #tryRemoveGuardingPiNode(com.oracle.graal.nodes.GuardingPiNode)}. If found, the node - * can be removed.
    3. - *
  3. - * Otherwise, the node is lowered to a {@link com.oracle.graal.nodes.FixedGuardNode} and its - * usages replaced with {@link com.oracle.graal.nodes.PiNode}. Details in - * {@link #visitGuardingPiNode(com.oracle.graal.nodes.GuardingPiNode)}.
    4. - *
- * - *

- * Precondition: the condition hasn't been deverbosified yet. - *

- * - */ - protected final void visitGuardingPiNode(GuardingPiNode envelope) { - - if (!FlowUtil.hasLegalObjectStamp(envelope)) { - // this situation exercised by com.oracle.graal.jtt.optimize.NCE_FlowSensitive02 - return; - } - if (!FlowUtil.hasLegalObjectStamp(envelope.object())) { - return; - } - - /* - * (1 of 3) Cover the case of GuardingPiNode(LogicConstantNode, ...) - */ - - if (envelope.condition() instanceof LogicConstantNode) { - if (FlowUtil.alwaysFails(envelope.isNegated(), envelope.condition())) { - state.impossiblePath(); - // let GuardingPiNode(false).canonical() prune the dead-code control-path - return; - } - // if not always-fails and condition-constant, then it always-succeeds! - assert FlowUtil.alwaysSucceeds(envelope.isNegated(), envelope.condition()); - // let GuardingPiNode(true).canonical() replaceAtUsages - return; - } - - /* - * The trick used in visitFixedGuardNode to look up an equivalent GuardingNode for the - * combination of (negated, condition) at hand doesn't work for GuardingPiNode, because the - * condition showing up here (a ShortCircuitOrNode that can be detected by - * CastCheckExtractor) doesn't appear as key in trueFacts, falseFacts. Good thing we have - * CastCheckExtractor! - */ - - /* - * (2 of 3) Cover the case of the condition known-to-be-false or known-to-be-true, but not - * LogicConstantNode. - * - * If deverbosify(condition) == falseConstant, it would be safe to set: - * `envelope.setCondition(falseConstant)` (only the API won't allow). - * - * On the other hand, it's totally unsafe to do something like that for trueConstant. What - * we can do about that case is the province of `tryRemoveGuardingPiNode(envelope)` - */ - - if (tryRemoveGuardingPiNode(envelope)) { - return; - } - - /* - * Experience has shown that an attempt to eliminate the current GuardingPiNode by using a - * GuardingNode already in scope and with equivalent condition (grabbed from `trueFacts` - * resp. `falseFacts`) proves futile. Therefore we're not even attempting that here. - */ - - /* - * (3 of 3) Neither always-succeeds nor always-fails, ie we don't known. Converting to - * FixedGuardNode allows tracking the condition via a GuardingNode, thus potentially - * triggering simplifications down the road. - */ - FixedGuardNode fixedGuard = graph.add(new FixedGuardNode(envelope.condition(), envelope.getReason(), envelope.getAction(), envelope.isNegated())); - graph.addBeforeFixed(envelope, fixedGuard); - - /* - * - * TODO This lowering is currently performed unconditionally: it might occur no - * flow-sensitive reduction is enabled down the road - */ - - if (!FlowUtil.lacksUsages(envelope)) { - // not calling wrapInPiNode() because we don't want to rememberSubstitution() - PiNode replacement = graph.unique(new PiNode(envelope.object(), envelope.stamp(), fixedGuard)); - reasoner.added.add(replacement); - // before removing the GuardingPiNode replace its usages - envelope.replaceAtUsages(replacement); - } - - graph.removeFixed(envelope); - - state.addFact(!fixedGuard.isNegated(), fixedGuard.condition(), fixedGuard); - - } - - /** - *

- * Based on flow-sensitive knowledge, two pre-requisites have to be fulfilled in order to remove - * a {@link com.oracle.graal.nodes.GuardingPiNode}: - * - *

    - *
  • the condition must refer only to the payload of the - * {@link com.oracle.graal.nodes.GuardingPiNode}
    • - *
  • the condition must check properties about which the state tracks not only a true/false - * answer, but also an anchor witnessing that fact
    • - *
  • the condition may not check anything else beyond what's stated in the items above.
    • - *
- *

- * - *

- * Provided a condition as above can be reduced to a constant (and an anchor obtained in the - * process), this method replaces all usages of the - * {@link com.oracle.graal.nodes.GuardingPiNode} (necessarily of - * {@link com.oracle.graal.nodeinfo.InputType#Value}) with a - * {@link com.oracle.graal.nodes.PiNode} that wraps the payload and the anchor in question. - *

- * - *

- * Precondition: the condition hasn't been deverbosified yet. - *

- * - * @see #visitGuardingPiNode(com.oracle.graal.nodes.GuardingPiNode) - * - */ - private boolean tryRemoveGuardingPiNode(GuardingPiNode envelope) { - - LogicNode cond = envelope.condition(); - ValueNode payload = envelope.object(); - - ObjectStamp outgoingStamp = (ObjectStamp) envelope.stamp(); - ObjectStamp payloadStamp = (ObjectStamp) payload.stamp(); - - if (isNullCheckOn(cond, payload)) { - if (envelope.isNegated()) { - /* - * GuardingPiNode succeeds if payload non-null - */ - if (!outgoingStamp.equals(FlowUtil.asNonNullStamp(payloadStamp))) { - warnAboutOutOfTheBlueGuardingPiNode(envelope); - } - return tryRemoveGuardingPiNodeNonNullCond(envelope); - } else { - /* - * GuardingPiNode succeeds if payload null - */ - ValueNode replacement = StampTool.isPointerAlwaysNull(payload) ? payload : reasoner.nonTrivialNull(payload); - if (replacement != null) { - // replacement == null means !isKnownNull(payload) - removeGuardingPiNode(envelope, replacement); - return true; - } - return false; - } - } else if (CastCheckExtractor.isInstanceOfCheckOn(cond, payload)) { - if (envelope.isNegated()) { - return false; - } - /* - * GuardingPiNode succeeds if payload instanceof - */ - InstanceOfNode io = (InstanceOfNode) cond; - assert io.type() != null; - Witness w = state.typeInfo(payload); - if (w != null && w.isNonNull() && isEqualOrMorePrecise(w.type(), io.type())) { - ValueNode d = reasoner.downcast(payload); - removeGuardingPiNode(envelope, d); - return true; - } - return false; - } else if (cond instanceof ShortCircuitOrNode) { - if (envelope.isNegated()) { - return false; - } - CastCheckExtractor cce = CastCheckExtractor.extract(cond); - if (cce == null || cce.subject != payload) { - return false; - } - /* - * GuardingPiNode succeeds if payload check-casts toType - */ - return tryRemoveGuardingPiNodeCheckCastCond(envelope, cce.type); - } - - return false; - } - - /** - * Porcelain method. - * - * This method handles the case where the GuardingPiNode succeeds if payload known to be - * non-null. - * - * @see #tryRemoveGuardingPiNode(com.oracle.graal.nodes.GuardingPiNode) - */ - private boolean tryRemoveGuardingPiNodeNonNullCond(GuardingPiNode envelope) { - - ValueNode payload = envelope.object(); - - if (state.isNull(payload)) { - // the GuardingPiNode fails always - postponedDeopts.addDeoptBefore(envelope, envelope.getReason()); - state.impossiblePath(); - return true; - } - - if (StampTool.isPointerNonNull(payload)) { - // payload needs no downcasting, it satisfies as-is the GuardingPiNode's condition. - if (precisionLoss(envelope, payload)) { - /* - * TODO The GuardingPiNode has an outgoing stamp whose narrowing goes beyond what - * the condition checks. That's suspicious. - */ - PiNode replacement = graph.unique(new PiNode(payload, envelope.stamp())); - reasoner.added.add(replacement); - removeGuardingPiNode(envelope, replacement); - return true; - } else { - removeGuardingPiNode(envelope, payload); - return true; - } - } - // if a non-null witness available, the GuardingPiNode can be removed - - Witness w = state.typeInfo(payload); - GuardingNode nonNullAnchor = (w != null && w.isNonNull()) ? w.guard() : null; - if (nonNullAnchor != null) { - PiNode replacement = graph.unique(new PiNode(payload, envelope.stamp(), nonNullAnchor.asNode())); - reasoner.added.add(replacement); - removeGuardingPiNode(envelope, replacement); - return true; - } - - /* - * TODO What about, nodes that always denote non-null values? (Even though their stamp - * forgot to make that clear) Candidates: ObjectGetClassNode, Parameter(0) on instance - */ - - return false; - } - - /** - * Porcelain method. - * - * This method handles the case where the GuardingPiNode succeeds if payload null or its actual - * type equal or subtype of `toType` - * - * @see #tryRemoveGuardingPiNode(com.oracle.graal.nodes.GuardingPiNode) - * - */ - private boolean tryRemoveGuardingPiNodeCheckCastCond(GuardingPiNode envelope, ResolvedJavaType toType) { - assert toType != null; - ValueNode payload = envelope.object(); - - ObjectStamp outgoingStamp = (ObjectStamp) envelope.stamp(); - ObjectStamp payloadStamp = (ObjectStamp) payload.stamp(); - - if (!outgoingStamp.equals(FlowUtil.asRefinedStamp(payloadStamp, toType))) { - warnAboutOutOfTheBlueGuardingPiNode(envelope); - } - - ValueNode d = reasoner.downcast(payload); - if (d == null) { - return false; - } - - if (StampTool.isPointerAlwaysNull(d)) { - removeGuardingPiNode(envelope, d); - return true; - } - ObjectStamp dStamp = (ObjectStamp) d.stamp(); - if (isEqualOrMorePrecise(dStamp.type(), toType)) { - removeGuardingPiNode(envelope, d); - return true; - } - return false; - } - - /* - * TODO There should be an assert in GuardingPiNode to detect that as soon as it happens - * (constructor, setStamp). - */ - private static void warnAboutOutOfTheBlueGuardingPiNode(GuardingPiNode envelope) { - Debug.log(String.format("GuardingPiNode has an outgoing stamp whose narrowing goes beyond what its condition checks: %s", envelope)); - } - - private static boolean isNullCheckOn(LogicNode cond, ValueNode subject) { - if (!(cond instanceof IsNullNode)) { - return false; - } - IsNullNode isNull = (IsNullNode) cond; - return isNull.getValue() == subject; - } - - /** - * Porcelain method. - */ - private void removeGuardingPiNode(GuardingPiNode envelope, ValueNode replacement) { - assert !precisionLoss(envelope, replacement); - metricGuardingPiNodeRemoved.increment(); - envelope.replaceAtUsages(replacement); - assert FlowUtil.lacksUsages(envelope); - graph.removeFixed(envelope); - } - - public static boolean isEqualOrMorePrecise(ResolvedJavaType a, ResolvedJavaType b) { - return a.equals(b) || FlowUtil.isMorePrecise(a, b); - } - - public static boolean isEqualOrMorePrecise(ObjectStamp a, ObjectStamp b) { - return a.equals(b) || FlowUtil.isMorePrecise(a, b); - } - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Histogram.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Histogram.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,77 +0,0 @@ -/* - * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import java.util.Map; -import java.util.TreeMap; - -public class Histogram extends TreeMap { - - private static final long serialVersionUID = 7188324319057387738L; - - private final String prefix; - - public Histogram(String prefix) { - this.prefix = prefix; - } - - public void tick(int bucket) { - Integer entry = get(bucket); - put(bucket, entry == null ? 1 : entry + 1); - } - - public void print() { - - // printing takes time, allow concurrent updates during printing - Histogram histogram = clone(); - - float casesTotal = 0; - for (int i : histogram.values()) { - casesTotal += i; - } - for (Map.Entry entry : histogram.entrySet()) { - int numCases = entry.getValue(); - int percentOut = (int) (numCases / casesTotal * 100); - String msg = prefix + String.format("%d iters in %4d cases (%2d %%)", entry.getKey(), numCases, percentOut); - if (entry.getKey() > 3) { - highlightInRed(msg); - } else { - System.out.println(msg); - } - } - System.out.println(prefix + "--------------------------"); - } - - @Override - public Histogram clone() { - return (Histogram) super.clone(); - } - - public static final String ANSI_RESET = "\u001B[0m"; - public static final String ANSI_RED = "\u001B[31m"; - - public static void highlightInRed(String msg) { - System.out.println(ANSI_RED + msg + ANSI_RESET); - } - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/IterativeFlowSensitiveReductionPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/IterativeFlowSensitiveReductionPhase.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,79 +0,0 @@ -/* - * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import static com.oracle.graal.graph.Graph.NodeEvent.*; - -import com.oracle.graal.api.code.*; -import com.oracle.graal.graph.Graph.NodeEventScope; -import com.oracle.graal.graph.*; -import com.oracle.graal.graph.spi.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.phases.*; -import com.oracle.graal.phases.common.*; -import com.oracle.graal.phases.common.util.*; -import com.oracle.graal.phases.tiers.*; - -public class IterativeFlowSensitiveReductionPhase extends BasePhase { - - private static final int MAX_ITERATIONS = 256; - - private final CanonicalizerPhase canonicalizer; - - public IterativeFlowSensitiveReductionPhase(CanonicalizerPhase canonicalizer) { - this.canonicalizer = canonicalizer; - } - - // private Histogram histogram = new Histogram("FSR-"); - - @Override - protected void run(StructuredGraph graph, PhaseContext context) { - FlowSensitiveReductionPhase eliminate = new FlowSensitiveReductionPhase(context.getMetaAccess()); - HashSetNodeEventListener listener = new HashSetNodeEventListener().exclude(NODE_ADDED); - int count = 1; - while (true) { - try (NodeEventScope nes = graph.trackNodeEvents(listener)) { - eliminate.apply(graph, context); - } - if (listener.getNodes().isEmpty()) { - // histogram.tick(count); - break; - } - for (Node node : graph.getNodes()) { - if (node instanceof Simplifiable) { - listener.getNodes().add(node); - } - } - canonicalizer.applyIncremental(graph, context, listener.getNodes()); - listener.getNodes().clear(); - if (++count > MAX_ITERATIONS) { - // System.out.println("Bailing out IterativeFlowSensitiveReductionPhase for graph: " - // + graph); - // FlowUtil.visualize(graph, "Bailout"); - throw new BailoutException("Number of iterations in FlowSensitiveReductionPhase exceeds %d", MAX_ITERATIONS); - } - } - // histogram.print(); - } - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/State.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/State.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1017 +0,0 @@ -/* - * Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import java.lang.reflect.*; -import java.util.*; - -import com.oracle.graal.api.meta.*; -import com.oracle.graal.compiler.common.type.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.calc.*; -import com.oracle.graal.nodes.extended.*; -import com.oracle.graal.nodes.java.*; -import com.oracle.graal.nodes.spi.*; -import com.oracle.graal.nodes.type.*; -import com.oracle.graal.nodes.util.*; -import com.oracle.graal.phases.graph.*; - -/** - * A State instance is mutated in place as each FixedNode is visited in a basic block of - * instructions. Basic block: starts with a {@link com.oracle.graal.nodes.BeginNode BeginNode}, ends - * at an {@link com.oracle.graal.nodes.EndNode EndNode} or - * {@link com.oracle.graal.nodes.ControlSinkNode ControlSinkNode} and lacks intervening control - * splits or merges. - */ -public final class State extends MergeableState implements Cloneable { - - private static final DebugMetric metricTypeRegistered = Debug.metric("FSR-TypeRegistered"); - private static final DebugMetric metricNullnessRegistered = Debug.metric("FSR-NullnessRegistered"); - private static final DebugMetric metricObjectEqualsRegistered = Debug.metric("FSR-ObjectEqualsRegistered"); - private static final DebugMetric metricImpossiblePathDetected = Debug.metric("FSR-ImpossiblePathDetected"); - - /** - *

- * Each state update results in a higher {@link State#versionNr versionNr}. The - * {@link State#versionNr versionNr} of different State instances can't be meaningfully compared - * (ie, same {@link State#versionNr versionNr} just indicates they've gone through the same - * number of updates). In particular, the {@link State#versionNr versionNr} of a merged state - * doesn't guarantee any more than being different from those of the states being merged. - *

- * - *

- * Still, {@link State#versionNr versionNr} proves useful in two cases: - * - *

    - *
  • recording the {@link State#versionNr versionNr} right after {@link State State} cloning, - * allows finding out afterwards whether (a) both states have diverged, (b) just one of them, or - * (c) none of them.
    • - *
  • a {@link State State} may become {@link State#isUnreachable isUnreachable}. In such case, - * it may make a difference whether any updates were performed on the state from the time it was - * cloned. Those updates indicate information not available in the state is was cloned from. For - * the purposes of {@link FlowSensitiveReduction FlowSensitiveReduction} an unreachable state - * need not be merged with any other (because control-flow won't reach the merge point over the - * path of the unreachable state).
    • - *
- *

- * - */ - int versionNr = 0; - - boolean isUnreachable = false; - - /** - * Getting here implies an opportunity was detected for dead-code-elimination. A counterpoint - * argument goes as follows: perhaps we don't get here that often, in which case the effort to - * detect an "impossible path" could be shaved off. - * - * @see com.oracle.graal.phases.common.cfs.BaseReduction.PostponedDeopt - */ - void impossiblePath() { - isUnreachable = true; - metricImpossiblePathDetected.increment(); - } - - /** - *

- * This map tracks properties about reference-values, ie combinations of: definitely-null, - * known-to-be-non-null, seen-type. - *

- * - *

- * In contrast to {@link #trueFacts} and {@link #falseFacts}, this map can answer queries even - * though the exact {@link LogicNode} standing for such query hasn't been tracked. For example, - * queries about subtyping. Additionally, a {@link Witness} can combine separate pieces of - * information more flexibly, eg, two separate observations about non-null and check-cast are - * promoted to an instance-of witness. - *

- * - */ - private Map typeRefinements; - - Map trueFacts; - Map falseFacts; - - public State() { - this.typeRefinements = Node.newIdentityMap(); - this.trueFacts = Node.newIdentityMap(); - this.falseFacts = Node.newIdentityMap(); - } - - public State(State other) { - this.isUnreachable = other.isUnreachable; - this.versionNr = other.versionNr; - this.typeRefinements = Node.newIdentityMap(); - for (Map.Entry entry : other.typeRefinements.entrySet()) { - this.typeRefinements.put(entry.getKey(), new Witness(entry.getValue())); - } - this.trueFacts = Node.newIdentityMap(other.trueFacts); - this.falseFacts = Node.newIdentityMap(other.falseFacts); - } - - public boolean repOK() { - // trueFacts and falseFacts disjoint - for (LogicNode trueFact : trueFacts.keySet()) { - assert !falseFacts.containsKey(trueFact) : trueFact + " tracked as both true and false fact."; - } - return true; - } - - /** - * @return A new list containing only those states that are reachable. - */ - private static ArrayList reachableStates(List states) { - ArrayList result = new ArrayList<>(states); - Iterator iter = result.iterator(); - while (iter.hasNext()) { - if (iter.next().isUnreachable) { - iter.remove(); - } - } - return result; - } - - private Map mergeKnownTypes(MergeNode merge, ArrayList withReachableStates) { - Map newKnownTypes = Node.newIdentityMap(); - - for (Map.Entry entry : typeRefinements.entrySet()) { - ValueNode node = entry.getKey(); - Witness type = new Witness(entry.getValue()); - - for (State other : withReachableStates) { - Witness otherType = other.typeInfo(node); - if (otherType == null) { - type = null; - break; - } - type.merge(otherType, merge); - } - if (type != null && type.knowsBetterThan(node)) { - assert node == GraphUtil.unproxify(node); - newKnownTypes.put(node, type); - } - } - - return newKnownTypes; - } - - /** - *

- * This method handles phis, by adding to the resulting state any information that can be gained - * (about type-refinement and nullness) based on the data available at each of the incoming - * branches. - *

- * - *

- * In more detail, FlowSensitiveReduction#visitAbstractEndNode() has already - * deverbosified the phi-values contributed by each reachable branch. The paths that - * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction} determined to be - * unreachable will be eliminated by canonicalization and dead code elimination. For now they - * still exist, thus polluting the result of - * {@link com.oracle.graal.nodes.ValuePhiNode#inferStamp()} but we are careful to skip them when - * merging type-witnesses and known-null maps. - *

- */ - private void mergePhis(MergeNode merge, List withStates, Map newKnownPhiTypes) { - - if (merge instanceof LoopBeginNode) { - return; - } - - for (PhiNode phi : merge.phis()) { - assert phi == GraphUtil.unproxify(phi); - if (phi instanceof ValuePhiNode && phi.getKind() == Kind.Object) { - ArrayList reachingValues = new ArrayList<>(); - if (!isUnreachable) { - reachingValues.add(phi.valueAt(0)); - } - for (int i = 0; i < withStates.size(); i++) { - State otherState = withStates.get(i); - if (!otherState.isUnreachable) { - reachingValues.add(phi.valueAt(i + 1)); - } - } - assert !reachingValues.isEmpty(); - ObjectStamp phiStamp = (ObjectStamp) phi.stamp(); - ObjectStamp nonPollutedStamp = (ObjectStamp) StampTool.meet(reachingValues); - Witness w = new Witness(nonPollutedStamp, merge); - if (w.isNull() && !phiStamp.alwaysNull()) { - // precision gain: null - newKnownPhiTypes.put(phi, w); - } else if (FlowUtil.isMorePrecise(w.type(), phiStamp.type())) { - // precision gain regarding type - newKnownPhiTypes.put(phi, w); - // confirm no precision loss regarding nullness - assert implies(phiStamp.nonNull(), w.isNonNull()); - assert implies(phiStamp.alwaysNull(), w.isNull()); - } else if (w.isNonNull() && !phiStamp.nonNull()) { - // precision gain: non-null - newKnownPhiTypes.put(phi, w); - // confirm no precision loss regarding type - assert !FlowUtil.isMorePrecise(phiStamp.type(), w.type()); - } - } - } - - } - - private static boolean implies(boolean a, boolean b) { - return !a || b; - } - - @Override - public boolean merge(MergeNode merge, List withStates) { - - ArrayList withReachableStates = reachableStates(withStates); - if (withReachableStates.isEmpty()) { - return true; - } - - for (State other : withReachableStates) { - versionNr = Math.max(versionNr, other.versionNr) + 1; - if (!other.isUnreachable) { - isUnreachable = false; - } - } - - if (isUnreachable) { - typeRefinements.clear(); - trueFacts.clear(); - falseFacts.clear(); - return true; - } - - // may also get updated in a moment, during processing of phi nodes. - Map newKnownTypes = mergeKnownTypes(merge, withReachableStates); - // may also get updated in a moment, during processing of phi nodes. - mergePhis(merge, withStates, newKnownTypes); - this.typeRefinements = newKnownTypes; - - this.trueFacts = mergeTrueFacts(withReachableStates, merge); - this.falseFacts = mergeFalseFacts(withReachableStates, merge); - - assert repOK(); - - return true; - } - - private Map mergeTrueFacts(ArrayList withReachableStates, GuardingNode merge) { - Map newTrueConditions = Node.newIdentityMap(); - for (Map.Entry entry : trueFacts.entrySet()) { - LogicNode check = entry.getKey(); - GuardingNode guard = entry.getValue(); - - for (State other : withReachableStates) { - GuardingNode otherGuard = other.trueFacts.get(check); - if (otherGuard == null) { - guard = null; - break; - } - if (otherGuard != guard) { - guard = merge; - } - } - if (guard != null) { - newTrueConditions.put(check, guard); - } - } - return newTrueConditions; - } - - private Map mergeFalseFacts(ArrayList withReachableStates, GuardingNode merge) { - Map newFalseConditions = Node.newIdentityMap(); - for (Map.Entry entry : falseFacts.entrySet()) { - LogicNode check = entry.getKey(); - GuardingNode guard = entry.getValue(); - - for (State other : withReachableStates) { - GuardingNode otherGuard = other.falseFacts.get(check); - if (otherGuard == null) { - guard = null; - break; - } - if (otherGuard != guard) { - guard = merge; - } - } - if (guard != null) { - newFalseConditions.put(check, guard); - } - } - return newFalseConditions; - } - - /** - * @return null if no type-witness available for the argument, the witness otherwise. - */ - public Witness typeInfo(ValueNode object) { - assert FlowUtil.hasLegalObjectStamp(object); - return typeRefinements.get(GraphUtil.unproxify(object)); - } - - /** - * @return true iff the argument is known to stand for null. - */ - public boolean isNull(ValueNode object) { - assert FlowUtil.hasLegalObjectStamp(object); - if (StampTool.isPointerAlwaysNull(object)) { - return true; - } - ValueNode scrutinee = GraphUtil.unproxify(object); - Witness w = typeRefinements.get(scrutinee); - return (w != null) && w.isNull(); - } - - /** - *

- * It makes a difference calling {@link Witness#isNonNull()} as opposed to - * {@link State#isNonNull(com.oracle.graal.nodes.ValueNode)}. The former guarantees the witness - * provides a guard certifying non-nullness. The latter just tells us there exists some guard - * that certifies the property we asked about. - *

- * - *

- * TODO improvement: isKnownNonNull could be made smarter by noticing some nodes always denote a - * non-null value (eg, ObjectGetClassNode). Similarly for isKnownNull. Code that looks at the - * stamp as well as code that looks for a non-null-witness would benefit from also checking such - * extended isKnownNonNull. Alternatively, the stamp of those nodes should always have - * is-non-null set. - *

- * - * @return true iff the argument is known to stand for non-null. - */ - public boolean isNonNull(ValueNode object) { - assert FlowUtil.hasLegalObjectStamp(object); - if (StampTool.isPointerNonNull(object)) { - return true; - } - Witness w = typeInfo(object); - return w == null ? false : w.isNonNull(); - } - - /** - * @return true iff the argument definitely stands for an object-value that conforms to the - * given type. - */ - public boolean knownToConform(ValueNode object, ResolvedJavaType to) { - assert FlowUtil.hasLegalObjectStamp(object); - assert !to.isPrimitive(); - ResolvedJavaType stampType = StampTool.typeOrNull(object); - if (stampType != null && to.isAssignableFrom(stampType)) { - return true; - } - final ValueNode scrutinee = GraphUtil.unproxify(object); - if (isNull(scrutinee)) { - return true; - } - Witness w = typeInfo(scrutinee); - boolean witnessAnswer = w != null && w.type() != null && to.isAssignableFrom(w.type()); - if (witnessAnswer) { - return true; - } - return false; - } - - /** - * @return true iff the argument is known to stand for an object that is definitely non-null and - * moreover does not conform to the given type. - */ - public boolean knownNotToPassCheckCast(ValueNode object, ResolvedJavaType to) { - assert FlowUtil.hasLegalObjectStamp(object); - assert !to.isPrimitive(); - final ValueNode scrutinee = GraphUtil.unproxify(object); - if (isNull(scrutinee)) { - // known-null means it conforms to whatever `to` - // and thus passes the check-cast - return false; - } - if (!isNonNull(scrutinee)) { - // unless `null` can be ruled out, a positive answer isn't safe - return false; - } - ResolvedJavaType stampType = StampTool.typeOrNull(object); - if (stampType != null && knownNotToConform(stampType, to)) { - return true; - } - Witness w = typeInfo(scrutinee); - boolean witnessAnswer = w != null && !w.cluelessAboutType() && knownNotToConform(w.type(), to); - if (witnessAnswer) { - return true; - } - return false; - } - - /** - * @return true iff the argument is known to stand for an object that definitely does not - * conform to the given type (no matter whether the object turns out to be null or - * non-null). - */ - public boolean knownNotToPassInstanceOf(ValueNode object, ResolvedJavaType to) { - assert FlowUtil.hasLegalObjectStamp(object); - assert !to.isPrimitive(); - final ValueNode scrutinee = GraphUtil.unproxify(object); - if (isNull(scrutinee)) { - return true; - } - ResolvedJavaType stampType = StampTool.typeOrNull(object); - if (stampType != null && knownNotToConform(stampType, to)) { - // object turns out to be null, positive answer is correct - // object turns out non-null, positive answer is also correct - return true; - } - Witness w = typeInfo(scrutinee); - boolean witnessAnswer = w != null && !w.cluelessAboutType() && knownNotToConform(w.type(), to); - if (witnessAnswer) { - // object turns out to be null, positive answer is correct - // object turns out non-null, positive answer is also correct - return true; - } - return false; - } - - // @formatter:off - /** - * Determines if the first argument is known not to conform to the second argument. - * - * 
-     *   \   |     |     |     |
-     *    \ b|     |     |     |
-     *   a \ |     |     |     |
-     *      \|iface|final|non-f|
-     *  -----+-----------------|
-     *  iface|  F  |  F  |  F  |
-     *  -----+-----------------|
-     *  final|  C  |  C  |  C  |
-     *  -----+-----------------|
-     *  non-f|  F  |  C  |  C  |
-     *  -----------------------+
-     *
-     *  where:
-     *    F:     false
-     *    C:     check
-     *    iface: interface
-     *    final: exact non-interface reference-type
-     *    non-f: non-exact non-interface reference-type
-     *
- * @return true iff the first argument is known not to conform to the second argument. - */ - // @formatter:on - public static boolean knownNotToConform(ResolvedJavaType a, ResolvedJavaType b) { - assert !a.isPrimitive(); - assert !b.isPrimitive(); - if (b.isAssignableFrom(a)) { - return false; - } - if (a.isInterface()) { - return false; - } - boolean aFinal = Modifier.isFinal(a.getModifiers()); - if (b.isInterface() && !aFinal) { - return false; - } - if (a.isAssignableFrom(b)) { - return false; - } else { - return true; - } - } - - @Override - public State clone() { - return new State(this); - } - - /** - * Porcelain method. - */ - private Witness getOrElseAddTypeInfo(ValueNode object) { - ValueNode scrutinee = GraphUtil.unproxify(object); - Witness w = typeRefinements.get(scrutinee); - if (w == null) { - w = new Witness(); - typeRefinements.put(scrutinee, w); - } - return w; - } - - /** - *

- * Updates this {@link State State} to account for an observation about the scrutinee being - * non-null. In case instanceof was observed, - * {@link #trackIO(com.oracle.graal.nodes.ValueNode, com.oracle.graal.api.meta.ResolvedJavaType, com.oracle.graal.nodes.extended.GuardingNode) - * trackIO(ResolvedJavaType, GuardingNode)} should be invoked instead. - *

- * - *

- * No check is made on whether a contradiction would be introduced into the factbase (in which - * case the state should be marked unreachable), the caller takes care of that. - *

- * - * @return whether state was updated (iff the observation added any new information) - */ - public boolean trackNN(ValueNode object, GuardingNode anchor) { - if (isDependencyTainted(object, anchor)) { - return false; - } - assert anchor instanceof FixedNode; - ResolvedJavaType stampType = StampTool.typeOrNull(object); - if (stampType != null && !stampType.isInterface()) { - return trackIO(object, stampType, anchor); - } - Witness w = getOrElseAddTypeInfo(object); - if (w.trackNN(anchor)) { - versionNr++; - assert repOK(); - return true; - } - return false; - } - - /** - * Updates this {@link State State} to account for an observation about the scrutinee conforming - * to a type. In case instanceof was observed, - * {@link #trackIO(com.oracle.graal.nodes.ValueNode, com.oracle.graal.api.meta.ResolvedJavaType, com.oracle.graal.nodes.extended.GuardingNode) - * trackIO(ResolvedJavaType, GuardingNode)} should be invoked instead. - * - *

- * No check is made on whether a contradiction would be introduced into the factbase (in which - * case the state should be marked unreachable), the caller must take care of that. - *

- * - * @return false iff the observed type is an interface, or doesn't provide any new information - * not already known. Ie, this method returns true iff the observation resulted in - * information gain. - */ - public boolean trackCC(ValueNode object, ResolvedJavaType observed, GuardingNode anchor) { - if (observed.isInterface()) { - return false; - } - if (isDependencyTainted(object, anchor)) { - return false; - } - assert anchor instanceof FixedNode; - Witness w = getOrElseAddTypeInfo(object); - if (w.trackCC(observed, anchor)) { - versionNr++; - metricTypeRegistered.increment(); - assert repOK(); - return true; - } - return false; - } - - /** - * Updates this {@link State State} to account for an observation about the non-null scrutinee - * conforming to a type. - * - *

- * No check is made on whether a contradiction would be introduced into the factbase (in which - * case the state should be marked unreachable), the caller must take care of that. - *

- * - * @return whether state was updated (iff the observation added any new information) - */ - public boolean trackIO(ValueNode object, ResolvedJavaType observed, GuardingNode anchor) { - assert !observed.isInterface() : "no infrastructure yet in State.Witness to support interfaces in general"; - if (isDependencyTainted(object, anchor)) { - return false; - } - assert anchor instanceof FixedNode; - Witness w = getOrElseAddTypeInfo(object); - if (w.trackIO(observed, anchor)) { - versionNr++; - metricTypeRegistered.increment(); - assert repOK(); - return true; - } - return false; - } - - /** - * This method increases {@link #versionNr} (thus potentially invalidating - * {@link EquationalReasoner EquationalReasoner}'s caches) only if the fact wasn't known - * already. - * - *

- * No check is made on whether a contradiction would be introduced into the factbase (in which - * case the state should be marked unreachable), the caller must take care of that. - *

- * - */ - private void addFactPrimordial(LogicNode condition, Map to, GuardingNode anchor) { - assert condition != null; - if (!to.containsKey(condition)) { - versionNr++; - to.put(condition, anchor); - } - } - - /** - * Ideas for the future. - *
    - *
  • track inferred less-than edges from (accumulated) CompareNode-s
    • - *
  • track set-representative for equality classes determined by (chained) IntegerTestNode
    • - *
- * - */ - public void addFact(boolean isTrue, LogicNode condition, GuardingNode anchor) { - assert anchor != null; - assert anchor instanceof FixedNode; - assert !isUnreachable; - - if (condition instanceof LogicConstantNode) { - if (((LogicConstantNode) condition).getValue() != isTrue) { - impossiblePath(); - } - return; - } - - if (condition instanceof LogicNegationNode) { - addFact(!isTrue, ((LogicNegationNode) condition).getValue(), anchor); - } else if (condition instanceof ShortCircuitOrNode) { - /* - * We can register the conditions being or-ed as long as the anchor is a fixed node, - * because floating guards will be registered at a BeginNode but might be "valid" only - * later due to data flow dependencies. Therefore, registering both conditions of a - * ShortCircuitOrNode for a floating guard could lead to cycles in data flow, because - * the guard will be used as anchor for both conditions, and one condition could be - * depending on the other. - */ - if (isTrue) { - CastCheckExtractor cce = CastCheckExtractor.extract(condition); - if (cce == null || isDependencyTainted(cce.subject, anchor)) { - addFactPrimordial(condition, isTrue ? trueFacts : falseFacts, anchor); - } else { - trackCC(cce.subject, cce.type, anchor); - } - } else { - ShortCircuitOrNode disjunction = (ShortCircuitOrNode) condition; - addFact(disjunction.isXNegated(), disjunction.getX(), anchor); - // previous addFact might have resulted in impossiblePath() - if (isUnreachable) { - return; - } - addFact(disjunction.isYNegated(), disjunction.getY(), anchor); - } - } else if (condition instanceof InstanceOfNode) { - addFactInstanceOf(isTrue, (InstanceOfNode) condition, anchor); - } else if (condition instanceof IsNullNode) { - IsNullNode nullCheck = (IsNullNode) condition; - addNullness(isTrue, nullCheck.getValue(), anchor); - } else if (condition instanceof ObjectEqualsNode) { - addFactObjectEqualsNode(isTrue, (ObjectEqualsNode) condition, anchor); - } else { - addFactPrimordial(condition, isTrue ? trueFacts : falseFacts, anchor); - } - assert repOK(); - } - - /** - * An instanceof hint is tracked differently depending on whether it's an interface-test or not - * (because type-refinements currently lacks the ability to track interface types). - * - */ - private void addFactInstanceOf(boolean isTrue, InstanceOfNode instanceOf, GuardingNode anchor) { - ValueNode object = instanceOf.getValue(); - if (isTrue) { - if (knownNotToPassInstanceOf(object, instanceOf.type())) { - impossiblePath(); - return; - } - addNullness(false, object, anchor); - if (instanceOf.type().isInterface()) { - if (!knownToConform(object, instanceOf.type())) { - addFactPrimordial(instanceOf, trueFacts, anchor); - } - } else { - trackIO(object, instanceOf.type(), anchor); - } - } - } - - private void addFactObjectEqualsNode(boolean isTrue, ObjectEqualsNode equals, GuardingNode anchor) { - if (isDependencyTainted(equals.getX(), anchor)) { - return; - } - if (isDependencyTainted(equals.getY(), anchor)) { - return; - } - assert anchor instanceof FixedNode; - ValueNode x = GraphUtil.unproxify(equals.getX()); - ValueNode y = GraphUtil.unproxify(equals.getY()); - if (isTrue) { - if (isNull(x) && isNonNull(y)) { - impossiblePath(); - return; - } - if (isNonNull(x) && isNull(y)) { - impossiblePath(); - return; - } - if (isNull(x) || isNull(y)) { - metricObjectEqualsRegistered.increment(); - addNullness(true, equals.getX(), anchor); - addNullness(true, equals.getY(), anchor); - } else if (isNonNull(x) || isNonNull(y)) { - metricObjectEqualsRegistered.increment(); - addNullness(false, equals.getX(), anchor); - addNullness(false, equals.getY(), anchor); - } - Witness wx = typeInfo(x); - Witness wy = typeInfo(y); - if (wx == null && wy == null) { - return; - } else if (wx != null && wy != null) { - // tighten their type-hints, provided at least one available - // both witnesses may have seen == null, ie they may be NN witnesses - ResolvedJavaType best = FlowUtil.tighten(wx.type(), wy.type()); - if (best != null) { - assert !best.isInterface(); - // type tightening is enough, nullness already taken care of - trackCC(equals.getX(), best, anchor); - trackCC(equals.getY(), best, anchor); - } - } else if (wx == null) { - typeRefinements.put(x, new Witness(wy)); - } else if (wy == null) { - typeRefinements.put(y, new Witness(wx)); - } - } else { - if (isNull(x) && !isNonNull(y)) { - metricObjectEqualsRegistered.increment(); - addNullness(false, equals.getY(), anchor); - } else if (!isNonNull(x) && isNull(y)) { - metricObjectEqualsRegistered.increment(); - addNullness(false, equals.getX(), anchor); - } - } - } - - /** - * Adds information about the nullness of a value. If isNull is true then the value is known to - * be null, otherwise the value is known to be non-null. - */ - public void addNullness(boolean isNull, ValueNode value, GuardingNode anchor) { - if (isDependencyTainted(value, anchor)) { - return; - } - assert anchor instanceof FixedNode; - ValueNode scrutinee = GraphUtil.unproxify(value); - boolean wasNull = isNull(scrutinee); - boolean wasNonNull = isNonNull(scrutinee); - if (isNull) { - if (wasNonNull) { - impossiblePath(); - } else { - metricNullnessRegistered.increment(); - versionNr++; - Witness w = getOrElseAddTypeInfo(scrutinee); - w.trackDN(anchor); - } - } else { - if (wasNull) { - impossiblePath(); - } else { - metricNullnessRegistered.increment(); - trackNN(scrutinee, anchor); - } - } - assert repOK(); - } - - /** - * - * @return true iff `value` may lose dependency not covered by `anchor`. - */ - public static boolean isDependencyTainted(ValueNode value, GuardingNode anchor) { - assert anchor instanceof FixedNode; - if (value instanceof ValueProxy) { - if (value instanceof GuardedNode) { - GuardedNode gn = (GuardedNode) value; - GuardingNode guardian = gn.getGuard(); - if (guardian != null) { - boolean isGuardedByFixed = guardian instanceof FixedNode; - if (!isGuardedByFixed) { - return true; - } - } - } - // if (value instanceof GuardingNode) { - // return true; - // } - ValueProxy proxy = (ValueProxy) value; - return isDependencyTainted(proxy.getOriginalNode(), anchor); - } - return false; - } - - public void clear() { - versionNr = 0; - isUnreachable = false; - typeRefinements.clear(); - trueFacts.clear(); - falseFacts.clear(); - } - - /** - *

- * If the argument is known null due to its stamp, there's no need to have an anchor for that - * fact and this method returns null. - *

- * - *

- * Otherwise, if an anchor is found it is returned, null otherwise. - *

- */ - public GuardingNode nonTrivialNullAnchor(ValueNode object) { - assert FlowUtil.hasLegalObjectStamp(object); - if (StampTool.isPointerAlwaysNull(object)) { - return null; - } - ValueNode scrutinee = GraphUtil.unproxify(object); - Witness w = typeRefinements.get(scrutinee); - if (w != null && w.isNull()) { - return w.guard(); - } - return null; - } - - /** - * This method: - *
    - *
  • - * attempts to find an existing {@link com.oracle.graal.nodes.extended.GuardingNode} that - * implies the property stated by the arguments. If found, returns it as positive evidence.
    • - *
  • - * otherwise, if the property of interest is known not to hold, negative evidence is returned.
    • - *
  • - * otherwise, null is returned.
    • - *
- */ - public Evidence outcome(boolean isTrue, LogicNode cond) { - - // attempt to find an anchor for the condition of interest, verbatim - if (isTrue) { - GuardingNode existingGuard = trueFacts.get(cond); - if (existingGuard != null) { - return new Evidence(existingGuard); - } - if (falseFacts.containsKey(cond)) { - return Evidence.COUNTEREXAMPLE; - } - } else { - GuardingNode existingGuard = falseFacts.get(cond); - if (existingGuard != null) { - return new Evidence(existingGuard); - } - if (trueFacts.containsKey(cond)) { - return Evidence.COUNTEREXAMPLE; - } - } - - if (cond instanceof IsNullNode) { - return outcomeIsNullNode(isTrue, (IsNullNode) cond); - } - - if (cond instanceof InstanceOfNode) { - return outcomeInstanceOfNode(isTrue, (InstanceOfNode) cond); - } - - if (cond instanceof ShortCircuitOrNode) { - return outcomeShortCircuitOrNode(isTrue, (ShortCircuitOrNode) cond); - } - - // can't produce evidence - return null; - } - - /** - * Utility method for {@link #outcome(boolean, com.oracle.graal.nodes.LogicNode)}. - */ - private Evidence outcomeIsNullNode(boolean isTrue, IsNullNode isNullNode) { - if (isTrue) { - // grab an anchor attesting nullness - final GuardingNode replacement = nonTrivialNullAnchor(isNullNode.getValue()); - if (replacement != null) { - return new Evidence(replacement); - } - if (isNonNull(isNullNode.getValue())) { - return Evidence.COUNTEREXAMPLE; - } - } else { - // grab an anchor attesting non-nullness - final Witness w = typeInfo(isNullNode.getValue()); - if (w != null && w.isNonNull()) { - return new Evidence(w.guard()); - } - if (isNull(isNullNode.getValue())) { - return Evidence.COUNTEREXAMPLE; - } - } - // can't produce evidence - return null; - } - - /** - * Utility method for {@link #outcome(boolean, com.oracle.graal.nodes.LogicNode)}. - */ - private Evidence outcomeInstanceOfNode(boolean isTrue, InstanceOfNode iOf) { - final Witness w = typeInfo(iOf.getValue()); - if (isTrue) { - if (isNull(iOf.getValue())) { - return Evidence.COUNTEREXAMPLE; - } - // grab an anchor attesting instanceof - if ((w != null) && (w.type() != null)) { - if (w.isNonNull()) { - if (iOf.type().isAssignableFrom(w.type())) { - return new Evidence(w.guard()); - } - } - if (State.knownNotToConform(w.type(), iOf.type())) { - // null -> fails instanceof - // non-null but non-conformant -> also fails instanceof - return Evidence.COUNTEREXAMPLE; - } - } - } else { - // grab an anchor attesting not-instanceof - // (1 of 2) attempt determining nullness - final GuardingNode nullGuard = nonTrivialNullAnchor(iOf.getValue()); - if (nullGuard != null) { - return new Evidence(nullGuard); - } - // (2 of 2) attempt determining known-not-to-conform - if (w != null && !w.cluelessAboutType()) { - if (State.knownNotToConform(w.type(), iOf.type())) { - return new Evidence(w.guard()); - } - } - } - // can't produce evidence - return null; - } - - /** - * Utility method for {@link #outcome(boolean, com.oracle.graal.nodes.LogicNode)}. - */ - private Evidence outcomeShortCircuitOrNode(boolean isTrue, ShortCircuitOrNode orNode) { - if (!isTrue) { - // too tricky to reason about - return null; - } - CastCheckExtractor cce = CastCheckExtractor.extract(orNode); - if (cce != null) { - // grab an anchor attesting check-cast - Witness w = typeInfo(cce.subject); - if (w != null && w.type() != null) { - if (cce.type.isAssignableFrom(w.type())) { - return new Evidence(w.guard()); - } - if (isNonNull(cce.subject) && State.knownNotToConform(w.type(), cce.type)) { - return Evidence.COUNTEREXAMPLE; - } - } - } - // search for positive-evidence for the first or-input - Evidence evidenceX = outcome(!orNode.isXNegated(), orNode.getX()); - if (evidenceX != null && evidenceX.isPositive()) { - return evidenceX; - } - // search for positive-evidence for the second or-input - Evidence evidenceY = outcome(!orNode.isYNegated(), orNode.getY()); - if (evidenceY != null && evidenceY.isPositive()) { - return evidenceY; - } - // check for contradictions on both or-inputs - if (evidenceX != null && evidenceY != null) { - assert evidenceX.isNegative() && evidenceY.isNegative(); - return Evidence.COUNTEREXAMPLE; - } - // can't produce evidence - return null; - } - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Witness.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Witness.java Fri Jan 23 22:00:55 2015 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,526 +0,0 @@ -/* - * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.phases.common.cfs; - -import com.oracle.graal.api.meta.ResolvedJavaType; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.extended.GuardingNode; -import com.oracle.graal.compiler.common.type.ObjectStamp; - -/** - *

- * A witness progressively tracks more detailed properties about an object value (the scrutinee); - * the properties in question comprise whether the scrutinee has been observed: - * - *

    - *
  • as non-null,
    • - *
  • in a successful checkcast, or
    • - *
  • in a successful instanceof.
    • - *
- *

- * - *

- * A witness is updated only when doing so increases the information content of the witness. For - * example, upon visiting a {@link com.oracle.graal.nodes.java.CheckCastNode CheckCastNode} the - * witness gets a chance to become updated. - *

- * - *

- * Therefore, at any given time, a witness represents the most detailed knowledge available so far - * about the scrutinee, which is the knowledge most relevant for upcoming program-points. - *

- * - *

- * The availability of witnesses about both non-nullness and checkcast (for a given scrutinee) - * promotes to an instanceof-style witness . The "levels" of knowledge a witness may exhibit are - * captured by {@link com.oracle.graal.phases.common.cfs.Witness.LEVEL}. For conciseness, the - * following query methods are available for a {@link com.oracle.graal.phases.common.cfs.Witness}: - *

    - *
  • {@link #atNonNull()}
    • - *
  • {@link #atCheckCast()}
    • - *
  • {@link #atInstanceOf()}
    • - *
- *

- * - *

- * Only non-interface object types (ie, class and array types) are tracked. Small extensions are - * required to track interfaces, extensions that might be added after the current scheme proves - * itself. - *

- * - *

- * Some useful facts about the Statechart implemented by {@link Witness Witness}: - * - *

    - *
  • the start-state is "clueless"
    • - *
  • - * A self-transition via trackCC from whichever the current state is to itself, without information - * gain, is always possible. Just give {@link Object java.lang.Object} as observed type.
    • - *
- *

- * - */ -public class Witness implements Cloneable { - - private static enum LEVEL { - CLUELESS, - NN, - CC, - IO, - DN - } - - private boolean atNonNull() { - return level == LEVEL.NN; - } - - private boolean atCheckCast() { - return level == LEVEL.CC; - } - - private boolean atInstanceOf() { - return level == LEVEL.IO; - } - - private boolean atDefinitelyNull() { - return level == LEVEL.DN; - } - - private void transition(LEVEL to, GuardingNode newAnchor) { - this.level = to; - this.gn = newAnchor; - assert repOK(); - } - - public Witness() { - } - - public Witness(Witness other) { - level = other.level; - seen = other.seen; - gn = other.gn; - } - - /** - * Counterpart to {@link #asStamp()}. - */ - public Witness(ObjectStamp stamp, GuardingNode anchor) { - assert stamp.isLegal(); - assert anchor != null; - if (stamp.alwaysNull()) { - // seen left null - transition(LEVEL.DN, anchor); - } else { - boolean isNonIface = (stamp.type() != null && !stamp.type().isInterface()); - if (stamp.nonNull()) { - if (isNonIface) { - seen = stamp.type(); - transition(LEVEL.IO, anchor); - } else { - seen = null; - transition(LEVEL.NN, anchor); - } - } else { - if (isNonIface) { - seen = stamp.type(); - transition(LEVEL.CC, anchor); - } else { - seen = null; - transition(LEVEL.CLUELESS, null); - assert clueless(); - } - } - } - assert repOK(); - } - - public boolean isNonNull() { - return atNonNull() || atInstanceOf(); - } - - public boolean isNull() { - return atDefinitelyNull(); - } - - /** - * The most precise type known so far about the scrutinee. (Please notice that nothing can be - * deduced about the non-nullness-status of the scrutinee from invoking this method alone). - */ - public ResolvedJavaType type() { - return seen; - } - - public ObjectStamp asStamp() { - boolean isKnownExact = (seen != null && seen.equals(seen.asExactType())); - return new ObjectStamp(seen, isKnownExact, isNonNull(), isNull()); - } - - private LEVEL level = LEVEL.CLUELESS; - private ResolvedJavaType seen = null; - - /** - * Evidence (ie, a {@link com.oracle.graal.nodes.extended.GuardingNode}) attesting to the status - * reported by this witness. - * - * May be one of: - * - *
    - *
  • - * {@link com.oracle.graal.nodes.BeginNode BeginNode},
    • - *
  • - * {@link com.oracle.graal.nodes.LoopExitNode LoopExitNode},
    • - *
  • - * {@link com.oracle.graal.nodes.FixedGuardNode FixedGuardNode}
    • - *
  • {@link com.oracle.graal.nodes.MergeNode MergeNode}, resulting from merging two witnesses - * with different values for this anchor
    • - *
- * - *

- * An {@link com.oracle.graal.nodes.calc.ObjectEqualsNode ObjectEqualsNode} test results in the - * more-clueless of both scrutinees having its witness upgraded to that of the other (both - * scrutinees share the same {@link Witness Witness} instance from then on). For this reason, - * this field may also hold the anchors associated to an - * {@link com.oracle.graal.nodes.calc.ObjectEqualsNode ObjectEqualsNode} occurrence, ie nodes - * that can serve as {@link com.oracle.graal.nodes.extended.GuardingNode GuardingNode} for the - * purposes of building a {@link com.oracle.graal.nodes.PiNode PiNode}. - *

- * - */ - private GuardingNode gn = null; - - /** - * Invariants of this class: - *
    - *
  • All fields holding null is ok, the hallmark of a {@link #clueless() clueless} witness. - * Another way for a witness to be clueless is by recording java.lang.Object as the - * seen type and nothing more.
    • - *
  • {@link #seen seen} may be null as long as the only hint being recorded is non-nullness
    • - *
  • A non-null value for {@link #seen seen} can't be tracked with NN, that combination - * amounts to IO and is tracked as such
    • - *
  • At most one of NN, CC, IO may be tracked at any given time
    • - *
  • A non-null CC or a non-null IO force {@link #seen seen} to be non-null
    • - *
  • {@link #seen seen} must be null or denote a non-interface reference type (ie, either a - * class-type or an array-type)
    • - *
- */ - private boolean repOK() { - if (clueless()) { - assert level == LEVEL.CLUELESS; - return true; - } - if (atNonNull() || atDefinitelyNull()) { - assert seen == null; - } - if (seen != null) { - assert !seen.isInterface(); - assert !seen.isPrimitive(); - } - assert gn instanceof BeginNode || gn instanceof LoopExitNode || gn instanceof MergeNode || gn instanceof FixedGuardNode; - return true; - } - - /** - * Helper method for readability in complex conditions. - */ - public boolean clueless() { - return cluelessAboutType() && cluelessAboutNullity(); - } - - /** - * Helper method for readability in complex conditions. - */ - public boolean cluelessAboutType() { - // TODO also clueless when `seen` is `java.lang.Object` - return seen == null; - } - - /** - * Helper method for readability in complex conditions. - */ - public boolean cluelessAboutNullity() { - return !atNonNull() && !atInstanceOf() && !atDefinitelyNull(); - } - - /** - * Whether this {@link Witness Witness} tracks information strictly more precise than that in - * the given {@link com.oracle.graal.compiler.common.type.ObjectStamp}. - */ - boolean knowsBetterThan(ObjectStamp other) { - return FlowUtil.isMorePrecise(asStamp(), other); - } - - /** - * Whether this {@link Witness Witness} tracks information strictly more precise than that in - * the {@link com.oracle.graal.compiler.common.type.ObjectStamp} of the given argument. - */ - boolean knowsBetterThan(ValueNode other) { - return knowsBetterThan((ObjectStamp) other.stamp()); - } - - /** - * Porcelain method for internal use only, invoked upon a Facade method being notified about - * checkcast or instanceof. - * - * @return whether the state was updated (iff the observation adds any new information) - */ - private boolean refinesSeenType(ResolvedJavaType observed) { - if (isNull()) { - return false; - } - if (cluelessAboutType() || FlowUtil.isMorePrecise(observed, seen)) { - seen = observed; - return true; - } - return false; - } - - /** - * Updates this {@link Witness Witness} to account for an observation about the scrutinee being - * non-null. In case instanceof was observed, - * {@link #trackIO(com.oracle.graal.api.meta.ResolvedJavaType, com.oracle.graal.nodes.extended.GuardingNode) - * trackIO(ResolvedJavaType, GuardingNode)} should be invoked instead - * - * @return whether this {@link Witness Witness} was updated (iff the observation adds any new - * information) - */ - public boolean trackNN(GuardingNode anchor) { - assert repOK(); - assert !isNull(); - try { - if (atInstanceOf()) { - return false; - } - if (atCheckCast()) { - transition(LEVEL.IO, anchor); - return true; - } - if (!atNonNull()) { - transition(LEVEL.NN, anchor); - return true; - } - return false; - } finally { - assert repOK(); - } - } - - /** - * Updates this {@link Witness Witness} to account for an observation about the scrutinee being - * null. - * - * @return whether this {@link Witness Witness} was updated (iff the observation adds any new - * information) - */ - public boolean trackDN(GuardingNode anchor) { - assert repOK(); - assert !isNonNull(); - try { - if (atDefinitelyNull()) { - return false; - } - assert level == LEVEL.CLUELESS || atCheckCast(); - seen = null; - transition(LEVEL.DN, anchor); - return true; - } finally { - assert repOK(); - } - } - - /** - * Updates this {@link Witness Witness} to account for an observation about the scrutinee - * conforming to the provided type. In case instanceof was observed, - * {@link #trackIO(com.oracle.graal.api.meta.ResolvedJavaType, com.oracle.graal.nodes.extended.GuardingNode) - * trackIO(ResolvedJavaType, GuardingNode)} should be invoked instead. - * - * @return true iff information was gained. - */ - public boolean trackCC(ResolvedJavaType observed, GuardingNode anchor) { - assert !observed.isInterface(); - assert anchor != null; - assert repOK(); - try { - boolean anchorObsolete = refinesSeenType(observed); - if (atInstanceOf()) { - /* - * Statechart: self-transition at IO, potential information gain. - */ - if (anchorObsolete) { - transition(LEVEL.IO, anchor); - return true; - } - return false; - } - if (anchorObsolete) { - if (!atNonNull()) { - /* Statechart: transition from clueless to CC. */ - transition(LEVEL.CC, anchor); - return true; - } else { - /* Statechart: transition from NN to IO. */ - transition(LEVEL.IO, anchor); - return true; - } - } - /* - * Statechart: self-transition from whichever the current state is to itself, without - * information gain. - */ - return false; - } finally { - assert repOK(); - } - } - - /** - * Updates this {@link Witness Witness} to account for an observation about the non-null - * scrutinee conforming to a type. - * - * @return whether this {@link Witness Witness} was updated (iff the observation adds any new - * information) - */ - public boolean trackIO(ResolvedJavaType observed, GuardingNode anchor) { - assert repOK(); - assert !isNull(); - try { - boolean gotMorePreciseType = refinesSeenType(observed); - if (!atInstanceOf() || gotMorePreciseType) { - transition(LEVEL.IO, anchor); - return true; - } - return gotMorePreciseType; - } finally { - assert repOK(); - } - } - - /** - * Shallow cloning is enough because what's reachable from {@link Witness} is primitive or used - * read-only when merging states. - */ - @Override - public Witness clone() { - return new Witness(this); - } - - /** - * @return null for a clueless method, non-null otherwise. - */ - GuardingNode guard() { - return gn; - } - - /** - * Merges another state into this one, by mutating this object, the other is left as is. - */ - public void merge(Witness that, MergeNode merge) { - assert this.repOK(); - assert that.repOK(); - - if (clueless()) { - return; - } - - // preserve guarding node only if matches other, otherwise settle on `merge` - final GuardingNode resultGuard = (guard() == that.guard()) ? guard() : merge; - - if (isNull()) { - switch (that.level) { - case CLUELESS: - case NN: - // lose is-null status, gain nothing - level = LEVEL.CLUELESS; - seen = null; - break; - case CC: - case IO: - // demote to check-cast - level = LEVEL.CC; - seen = that.seen; - break; - case DN: - // keep is-null status - } - gn = resultGuard; - return; - } - - if (that.isNull()) { - /* - * Same decisions as above (based on this-being-null and that-level) are now made based - * on (that-being-null and this-level). Because merge is commutative. - */ - switch (level) { - case CLUELESS: - case NN: - // lose is-null status, gain nothing - level = LEVEL.CLUELESS; - seen = null; - break; - case CC: - break; - case IO: - // demote to check-cast - level = LEVEL.CC; - // keep this.seen as-is - break; - case DN: - // keep is-null status - } - gn = resultGuard; - return; - } - - // by now we know neither this nor that are known-to-be-null - assert !isNull() && !that.isNull(); - - // umbrella type over the observations from both witnesses - ResolvedJavaType newSeen = (seen == null || that.seen == null) ? null : FlowUtil.widen(seen, that.seen); - - /* - * guarantee on (both conformance and non-nullness) required from each input in order for - * the result to be able to offer such guarantee - */ - final boolean resultIO = atInstanceOf() && that.atInstanceOf(); - /* failing that, attempt to rescue type-conformance */ - final boolean resultCC = !resultIO && (!cluelessAboutType() && !that.cluelessAboutType()); - /* if all else fails, attempt to rescue non-nullness */ - final boolean resultNN = !resultIO && !resultCC && (isNonNull() && that.isNonNull()); - - seen = newSeen; - level = resultIO ? LEVEL.IO : resultCC ? LEVEL.CC : resultNN ? LEVEL.NN : LEVEL.CLUELESS; - gn = resultGuard; - - assert repOK(); - } - - @Override - public String toString() { - StringBuilder sb = new StringBuilder(); - sb.append(cluelessAboutType() ? "seen=?" : "seen=" + seen); - sb.append(";"); - sb.append("gn=" + gn); - return sb.toString(); - } - -} diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/info/elem/InlineableGraph.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/info/elem/InlineableGraph.java Fri Jan 23 22:00:55 2015 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/info/elem/InlineableGraph.java Fri Jan 23 22:13:55 2015 +0100 @@ -33,7 +33,6 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.phases.common.*; -import com.oracle.graal.phases.common.cfs.*; import com.oracle.graal.phases.common.inlining.*; import com.oracle.graal.phases.graph.*; import com.oracle.graal.phases.tiers.*; @@ -90,7 +89,6 @@ try (Debug.Scope s = Debug.scope("InlineGraph", graph)) { ArrayList parameterUsages = replaceParamsWithMoreInformativeArguments(invoke, context); - parameterUsages = rewireParamsForDuplicateArguments(invoke, parameterUsages); if (parameterUsages != null && OptCanonicalizer.getValue()) { assert !parameterUsages.isEmpty() : "The caller didn't have more information about arguments after all"; canonicalizer.applyIncremental(graph, context, parameterUsages); @@ -107,48 +105,6 @@ } } - /** - * This method detects duplicate arguments (therefore corresponding to different - * {@link ParameterNode}s) and updates the graph to make all of their usages refer to the first - * one of them. - * - * @return a (possibly updated) list of nodes for incremental canonicalization. - */ - private ArrayList rewireParamsForDuplicateArguments(Invoke invoke, ArrayList parameterUsages0) { - ArrayList parameterUsages = parameterUsages0; - ArrayList params = new ArrayList<>(); - List originalArgs = invoke.callTarget().arguments(); - List argsInEffect = new ArrayList<>(); - // some param-nodes might have been deleted by replaceParamsWithMoreInformativeArguments() - // that's why we obtain an up-to-date list - for (ParameterNode p : graph.getNodes(ParameterNode.class)) { - if (!FlowUtil.lacksUsages(p)) { - params.add(p); - argsInEffect.add(originalArgs.get(p.index())); - } - } - // argsInEffect and params paired by position - assert params.size() == argsInEffect.size(); - int argIdx = 0; - for (ValueNode arg : argsInEffect) { - int firstOccurrrence = argsInEffect.indexOf(arg); - assert firstOccurrrence >= 0; - if (firstOccurrrence < argIdx) { - ParameterNode survivingParam = params.get(firstOccurrrence); - assert survivingParam.isAlive(); - ParameterNode duplicateParam = params.get(argIdx); - assert duplicateParam.isAlive(); - assert survivingParam != duplicateParam; - assert !isArgMoreInformativeThanParam(arg, survivingParam); - parameterUsages = trackParameterUsages(duplicateParam, parameterUsages); - // replaceFloating() deletes the duplicate param, unlike replaceAtUsages() - graph.replaceFloating(duplicateParam, survivingParam); - } - argIdx++; - } - return parameterUsages; - } - private static boolean isArgMoreInformativeThanParam(ValueNode arg, ParameterNode param) { return arg.isConstant() || canStampBeImproved(arg, param); } diff -r 732748092bae -r 2ad82c6147f1 graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/IterativeInliningPhase.java --- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/IterativeInliningPhase.java Fri Jan 23 22:00:55 2015 +0100 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/IterativeInliningPhase.java Fri Jan 23 22:13:55 2015 +0100 @@ -32,7 +32,6 @@ import com.oracle.graal.debug.Debug.Scope; import com.oracle.graal.nodes.*; import com.oracle.graal.phases.common.*; -import com.oracle.graal.phases.common.cfs.*; import com.oracle.graal.phases.common.inlining.*; import com.oracle.graal.phases.tiers.*; @@ -73,14 +72,9 @@ new DeadCodeEliminationPhase(Optional).apply(graph); - boolean reduceOrEliminate = FlowSensitiveReduction.getValue() || ConditionalElimination.getValue(); - if (reduceOrEliminate && OptCanonicalizer.getValue()) { + if (ConditionalElimination.getValue() && OptCanonicalizer.getValue()) { canonicalizer.apply(graph, context); - if (FlowSensitiveReduction.getValue()) { - new IterativeFlowSensitiveReductionPhase(canonicalizer).apply(graph, context); - } else { - new IterativeConditionalEliminationPhase(canonicalizer).apply(graph, context); - } + new IterativeConditionalEliminationPhase(canonicalizer).apply(graph, context); } if (!progress) { break;