Mercurial > hg > truffle
changeset 15388:769fc3629f59
Add phase FlowSensitiveReductionPhase.
It is possible to remove GuardingPiNodes, CheckCastNodes, and FixedGuards during
HighTier under certain conditions (control-flow sensitive conditions).
The phase added in this commit (FlowSensitiveReductionPhase) does that,
and in addition replaces usages with "downcasting" PiNodes when possible
thus resulting in more precise object stamps (e.g., non-null).
Finally, usages of floating, side-effects free, expressions are also simplified
(as per control-flow sensitive conditions).
The newly added phase runs only during HighTier and can be deactivated
using Graal option FlowSensitiveReduction (it is active by default).
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/GraalOptions.java Fri Apr 25 16:45:05 2014 +0200 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/GraalOptions.java Fri Apr 25 16:50:52 2014 +0200 @@ -187,6 +187,8 @@ // Code generator settings @Option(help = "") + public static final OptionValue<Boolean> FlowSensitiveReduction = new OptionValue<>(true); + @Option(help = "") public static final OptionValue<Boolean> ConditionalElimination = new OptionValue<>(true); @Option(help = "") public static final OptionValue<Boolean> UseProfilingInformation = new OptionValue<>(true);
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTest.java Fri Apr 25 16:45:05 2014 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTest.java Fri Apr 25 16:50:52 2014 +0200 @@ -22,23 +22,16 @@ */ 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.*; -import com.oracle.graal.nodes.calc.*; -import com.oracle.graal.nodes.java.*; -import com.oracle.graal.nodes.java.MethodCallTargetNode.InvokeKind; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.phases.common.*; import com.oracle.graal.phases.tiers.*; /** - * Collection of tests for {@link ConditionalEliminationPhase} including those that triggered bugs - * in this phase. + * Collection of tests for {@link com.oracle.graal.phases.common.ConditionalEliminationPhase} + * including those that triggered bugs in this phase. */ public class ConditionalEliminationTest extends GraalCompilerTest { @@ -88,174 +81,6 @@ } 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 = parse("testNullnessSnippet"); - new ConditionalEliminationPhase(getMetaAccess()).apply(graph); - new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), null)); - for (ConstantNode constant : getConstantNodes(graph)) { - if (ConstantNodeRecordsUsages || !constant.gatherUsages(graph).isEmpty()) { - assertTrue("unexpected constant: " + constant, constant.asConstant().isNull() || constant.asConstant().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 = parse("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 ConditionalEliminationPhase(getMetaAccess()).apply(graph); - new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), null)); - for (ConstantNode constant : getConstantNodes(graph)) { - if (ConstantNodeRecordsUsages || !constant.gatherUsages(graph).isEmpty()) { - assertTrue("unexpected constant: " + constant, constant.asConstant().isNull() || constant.asConstant().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 = parse("testInvokeSnippet"); - new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), null)); - new ConditionalEliminationPhase(getMetaAccess()).apply(graph); - - InvokeNode invoke = graph.getNodes().filter(InvokeNode.class).first(); - assertEquals(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 = parse("testTypeMergingSnippet"); - new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), null)); - new ConditionalEliminationPhase(getMetaAccess()).apply(graph); - new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), null)); - - assertEquals(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 = parse("testInstanceOfCheckCastSnippet"); - new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), null)); - new ConditionalEliminationPhase(getMetaAccess()).apply(graph); - new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), null)); - - assertEquals(0, graph.getNodes().filter(CheckCastNode.class).count()); - } - public static int testRedundantComparesSnippet(int[] array) { if (array == null) { return 0; @@ -272,39 +97,17 @@ new LoweringPhase(canonicalizer, LoweringTool.StandardLoweringStage.HIGH_TIER).apply(graph, context); canonicalizer.apply(graph, context); new FloatingReadPhase().apply(graph); - new ConditionalEliminationPhase(getMetaAccess()).apply(graph); + new ConditionalEliminationPhase(getMetaAccess()).apply(graph, context); canonicalizer.apply(graph, context); assertEquals(1, graph.getNodes().filter(GuardNode.class).count()); } - public static int testDuplicateNullChecksSnippet(Object a) { - if (a == null) { - return 2; - } - try { - return ((Integer) a).intValue(); - } catch (ClassCastException e) { - return 0; + public static String testInstanceOfCheckCastSnippet(Object e) { + if (e instanceof Entry) { + return ((Entry) e).name; } - } - - @Test - @Ignore - public void testDuplicateNullChecks() { - // This tests whether explicit null checks properly eliminate later null guards. Currently - // it's failing. - StructuredGraph graph = parse("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 ConditionalEliminationPhase(getMetaAccess()).apply(graph); - canonicalizer.apply(graph, context); - - assertEquals(1, graph.getNodes().filter(GuardNode.class).count()); + return null; } @Test @@ -317,9 +120,10 @@ new LoweringPhase(canonicalizer, LoweringTool.StandardLoweringStage.HIGH_TIER).apply(graph, context); canonicalizer.apply(graph, context); - new ConditionalEliminationPhase(getMetaAccess()).apply(graph); + new ConditionalEliminationPhase(getMetaAccess()).apply(graph, context); canonicalizer.apply(graph, context); assertEquals(0, graph.getNodes().filter(GuardNode.class).count()); } + }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/FlowSenReduTest.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,395 @@ +/* + * Copyright (c) 2011, 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 com.oracle.graal.debug.Debug; +import com.oracle.graal.debug.DebugConfig; +import com.oracle.graal.debug.DebugConfigScope; +import com.oracle.graal.debug.internal.DebugScope; +import com.oracle.graal.graph.Node; +import com.oracle.graal.nodes.calc.ObjectEqualsNode; +import com.oracle.graal.nodes.util.GraphUtil; +import com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase; +import org.junit.*; + +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.java.*; +import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.tiers.*; + +import java.util.Iterator; +import java.util.List; + +/** + * 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() { + assertEquals(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"; + assertEquals(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"; + assertEquals(i7, redundantInstanceOfSnippet02(i7)); + int ioAfter = getNodes(afterFlowSensitiveReduce(snippet), InstanceOfNode.class).size(); + assertEquals(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"; + assertEquals(i7, devirtualizationSnippet(i7, i7)); + nodeCountEquals(afterFlowSensitiveReduce(snippet), CheckCastNode.class, 0); + + StructuredGraph graph = afterFlowSensitiveReduce(snippet); + assertEquals(0, graph.getNodes().filter(CheckCastNode.class).count()); + + List<InvokeNode> invokeNodes = getNodes(afterFlowSensitiveReduce(snippet), InvokeNode.class); + assertEquals(1, invokeNodes.size()); + + MethodCallTargetNode target = (MethodCallTargetNode) invokeNodes.get(0).callTarget(); + assertEquals(MethodCallTargetNode.InvokeKind.Special, target.invokeKind()); + assertEquals("HotSpotMethod<Integer.intValue()>", 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"; + assertEquals(false, t5Snippet(null, true)); + StructuredGraph resultGraph = canonicalize(afterFlowSensitiveReduce(snippet)); + nodeCountEquals(resultGraph, ReturnNode.class, 2); + + List<ReturnNode> returnNodes = getNodes(resultGraph, ReturnNode.class); + Iterator<ReturnNode> iter = returnNodes.iterator(); + + ConstantNode c1 = (ConstantNode) iter.next().result(); + ConstantNode c2 = (ConstantNode) iter.next().result(); + + assertEquals(c1, c2); + assertEquals(0, c1.getValue().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) + assertEquals(1, getNodes(graph, InstanceOfNode.class).size()); + + List<ReturnNode> returnNodes = getNodes(graph, ReturnNode.class); + assertEquals(2, returnNodes.size()); + Iterator<ReturnNode> iter = returnNodes.iterator(); + + ConstantNode c1 = (ConstantNode) iter.next().result(); + ConstantNode c2 = (ConstantNode) iter.next().result(); + + assertEquals(c1, c2); + Assert.assertTrue(c1.getValue().isNull()); + } + + /* + * 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); + + assertEquals(1, getNodes(graph, InvokeNode.class).size()); + + List<InvokeNode> invokeNodes = getNodes(graph, InvokeNode.class); + assertEquals(1, invokeNodes.size()); + + MethodCallTargetNode target = (MethodCallTargetNode) invokeNodes.get(0).callTarget(); + assertEquals(MethodCallTargetNode.InvokeKind.Special, target.invokeKind()); + assertEquals("HotSpotMethod<Integer.intValue()>", 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<ReturnNode> returnNodes = getNodes(graph, ReturnNode.class); + assertEquals(2, returnNodes.size()); + Iterator<ReturnNode> 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<InstanceOfNode> ioNodes = getNodes(graph, InstanceOfNode.class); + assertEquals(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 <N extends Node> List<N> getNodes(StructuredGraph graph, Class<N> nodeClass) { + return graph.getNodes().filter(nodeClass).snapshot(); + } + + public <N extends Node> void nodeCountEquals(StructuredGraph graph, Class<N> nodeClass, int expected) { + assertEquals(expected, getNodes(graph, nodeClass).size()); + } + + public StructuredGraph afterFlowSensitiveReduce(String snippet) { + StructuredGraph before = canonicalize(parse(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(false, true, false, false, debugConfig.dumpHandlers(), debugConfig.output()); + try (DebugConfigScope s = Debug.setConfig(fixedConfig)) { + Debug.dump(graph, title); + + return graph; + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/FlowSensitiveReductionTest.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,293 @@ +/* + * Copyright (c) 2011, 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 com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase; +import org.junit.*; + +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.java.*; +import com.oracle.graal.nodes.java.MethodCallTargetNode.InvokeKind; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.phases.common.*; +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 = parse("testNullnessSnippet"); + PhaseContext context = new PhaseContext(getProviders(), null); + new FlowSensitiveReductionPhase(getMetaAccess()).apply(graph, context); + new CanonicalizerPhase(true).apply(graph, context); + for (ConstantNode constant : getConstantNodes(graph)) { + if (ConstantNodeRecordsUsages || !constant.gatherUsages(graph).isEmpty()) { + assertTrue("unexpected constant: " + constant, constant.asConstant().isNull() || constant.asConstant().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 = parse("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)) { + if (ConstantNodeRecordsUsages || !constant.gatherUsages(graph).isEmpty()) { + assertTrue("unexpected constant: " + constant, constant.asConstant().isNull() || constant.asConstant().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 = parse("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(); + assertEquals(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 = parse("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)); + + assertEquals(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 = parse("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)); + + assertEquals(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 = parse("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); + + assertEquals(1, graph.getNodes().filter(GuardNode.class).count()); + } + +}
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ScalarTypeSystemTest.java Fri Apr 25 16:45:05 2014 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ScalarTypeSystemTest.java Fri Apr 25 16:50:52 2014 +0200 @@ -22,6 +22,7 @@ */ package com.oracle.graal.compiler.test; +import com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase; import org.junit.*; import com.oracle.graal.api.code.*; @@ -167,8 +168,9 @@ StructuredGraph graph = parse(snippet); Debug.dump(graph, "Graph"); Assumptions assumptions = new Assumptions(false); - new ConditionalEliminationPhase(getMetaAccess()).apply(graph); - new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), assumptions)); + PhaseContext context = new PhaseContext(getProviders(), assumptions); + new FlowSensitiveReductionPhase(getMetaAccess()).apply(graph, context); + new CanonicalizerPhase(true).apply(graph, context); StructuredGraph referenceGraph = parse(referenceSnippet); assertEquals(referenceGraph, graph); }
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/TypeSystemTest.java Fri Apr 25 16:45:05 2014 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/TypeSystemTest.java Fri Apr 25 16:50:52 2014 +0200 @@ -24,6 +24,7 @@ import java.io.*; +import com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase; import org.junit.*; import com.oracle.graal.api.code.*; @@ -184,7 +185,12 @@ StructuredGraph graph = parse(snippet); Debug.dump(graph, "Graph"); Assumptions assumptions = new Assumptions(false); - new ConditionalEliminationPhase(getMetaAccess()).apply(graph); + /* + * When using FlowSensitiveReductionPhase instead of ConditionalEliminationPhase, + * tail-duplication gets activated thus resulting in a graph with more nodes than the + * reference graph. + */ + new ConditionalEliminationPhase(getMetaAccess()).apply(graph, new PhaseContext(getProviders(), assumptions)); new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), assumptions)); // a second canonicalizer is needed to process nested MaterializeNodes new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), assumptions)); @@ -239,7 +245,7 @@ StructuredGraph graph = parse(snippet); Assumptions assumptions = new Assumptions(false); new CanonicalizerPhase(true).apply(graph, new PhaseContext(getProviders(), assumptions)); - new ConditionalEliminationPhase(getMetaAccess()).apply(graph); + 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());
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/HighTier.java Fri Apr 25 16:45:05 2014 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/HighTier.java Fri Apr 25 16:50:52 2014 +0200 @@ -30,6 +30,7 @@ import com.oracle.graal.options.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.common.cfs.IterativeFlowSensitiveReductionPhase; import com.oracle.graal.phases.tiers.*; import com.oracle.graal.virtual.phases.ea.*; @@ -57,9 +58,14 @@ appendPhase(new InliningPhase(canonicalizer)); appendPhase(new DeadCodeEliminationPhase()); - if (ConditionalElimination.getValue() && OptCanonicalizer.getValue()) { + boolean reduceOrEliminate = FlowSensitiveReduction.getValue() || ConditionalElimination.getValue(); + if (reduceOrEliminate && OptCanonicalizer.getValue()) { appendPhase(canonicalizer); - appendPhase(new IterativeConditionalEliminationPhase(canonicalizer)); + if (FlowSensitiveReduction.getValue()) { + appendPhase(new IterativeFlowSensitiveReductionPhase(canonicalizer)); + } else { + appendPhase(new IterativeConditionalEliminationPhase(canonicalizer)); + } } } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GuardingPiNode.java Fri Apr 25 16:45:05 2014 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GuardingPiNode.java Fri Apr 25 16:50:52 2014 +0200 @@ -51,6 +51,18 @@ return condition; } + public boolean isNegated() { + return negated; + } + + public DeoptimizationReason getReason() { + return reason; + } + + public DeoptimizationAction getAction() { + return action; + } + /** * Constructor for {@link #guardingNonNull(Object)} node intrinsic. */
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/IterativeConditionalEliminationPhase.java Fri Apr 25 16:45:05 2014 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/IterativeConditionalEliminationPhase.java Fri Apr 25 16:50:52 2014 +0200 @@ -62,7 +62,7 @@ canonicalizer.applyIncremental(graph, context, listener.getChangedNodes()); listener.getChangedNodes().clear(); if (++count > MAX_ITERATIONS) { - throw new BailoutException("Number of iterations in conditional elimination phase exceeds " + MAX_ITERATIONS); + throw new BailoutException("Number of iterations in ConditionalEliminationPhase phase exceeds " + MAX_ITERATIONS); } } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/BaseReduction.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,233 @@ +/* + * 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.code.Assumptions; +import com.oracle.graal.api.meta.*; +import com.oracle.graal.debug.Debug; +import com.oracle.graal.debug.DebugMetric; +import com.oracle.graal.graph.Node; +import com.oracle.graal.graph.spi.CanonicalizerTool; +import com.oracle.graal.nodes.*; +import com.oracle.graal.compiler.common.type.ObjectStamp; +import com.oracle.graal.phases.graph.PostOrderNodeIterator; +import com.oracle.graal.phases.tiers.PhaseContext; + +import java.util.ArrayList; + +/** + * <p> + * 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. + * </p> + * + * + * <p> + * 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. + * </p> + * */ +public abstract class BaseReduction extends PostOrderNodeIterator<State> { + + protected static final DebugMetric metricCheckCastRemoved = Debug.metric("CheckCastRemoved"); + protected static final DebugMetric metricGuardingPiNodeRemoved = Debug.metric("GuardingPiNodeRemoved"); + protected static final DebugMetric metricFixedGuardNodeRemoved = Debug.metric("FixedGuardNodeRemoved"); + protected static final DebugMetric metricMethodResolved = Debug.metric("MethodResolved"); + + /** + * <p> + * 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}. + * </p> + * + * @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; + } + + public void doRewrite(LogicNode falseConstant) { + 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<PostponedDeopt> { + + 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)); + } + + } + + /** + * <p> + * 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 com.oracle.graal.graph.Node#canonical(com.oracle.graal.graph.spi.CanonicalizerTool)}. + * Doing so, in turn, requires this subclass of + * {@link com.oracle.graal.graph.spi.CanonicalizerTool}. + * </p> + * */ + 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(); + } + + /** + * Postpone + * {@link com.oracle.graal.nodes.util.GraphUtil#tryKillUnused(com.oracle.graal.graph.Node)} + * until {@link FlowSensitiveReduction#finished()} for the reasons covered there. + * */ + @Override + public void removeIfUnused(Node node) { + // GraphUtil.tryKillUnused(node); + } + + @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(FixedNode 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); + } + + /** + * <p> + * 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. + * </p> + * + * <p> + * 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. + * </p> + * + * */ + protected 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; + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CastCheckExtractor.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,87 @@ +/* + * 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; + } + + static CastCheckExtractor extractCastCheckInfo(LogicNode x, LogicNode y) { + if (x instanceof IsNullNode) { + IsNullNode isNull = (IsNullNode) x; + ValueNode subject = isNull.object(); + 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. + * */ + public static boolean isInstanceOfCheckOn(LogicNode cond, ValueNode subject) { + if (!(cond instanceof InstanceOfNode)) { + return false; + } + InstanceOfNode io = (InstanceOfNode) cond; + return io.object() == subject; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CheckCastReduction.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,337 @@ +/* + * 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.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; + +/** + * <p> + * This class implements control-flow sensitive reductions for + * {@link com.oracle.graal.nodes.java.CheckCastNode}. + * </p> + * + * @see #visitCheckCastNode(com.oracle.graal.nodes.java.CheckCastNode) + * */ +public abstract class CheckCastReduction extends GuardingPiReduction { + + public CheckCastReduction(FixedNode start, State initialState, PhaseContext context) { + super(start, initialState, context); + } + + /** + * <p> + * This phase is able to refine the types of reference-values at use sites provided a + * {@link com.oracle.graal.nodes.extended.GuardingNode GuardingNode} is available witnessing + * that fact. + * </p> + * + * <p> + * This method turns non-redundant {@link com.oracle.graal.nodes.java.CheckCastNode}s into + * {@link com.oracle.graal.nodes.GuardingPiNode}s. Once such lowering has been performed (during + * run N of this phase) follow-up runs attempt to further simplify the resulting node, see + * {@link EquationalReasoner#downcastedGuardingPiNode(com.oracle.graal.nodes.GuardingPiNode, Witness)} + * and {@link #visitGuardingPiNode(com.oracle.graal.nodes.GuardingPiNode)} + * </p> + * + * <p> + * Precondition: the inputs (ie, object) hasn't been deverbosified yet. + * </p> + * */ + 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.isObjectAlwaysNull(subject) || (subjectType != null && toType.isAssignableFrom(subjectType)); + if (isRedundantPerStamp) { + metricCheckCastRemoved.increment(); + checkCast.replaceAtUsages(subject); + graph.removeFixed(checkCast); + return; + } + + assert !StampTool.isObjectAlwaysNull(subject) : "Null as per stamp subjects should have been handled above"; + + // --------- checkCast deemed unsatisfiable by subject-stamp alone --------- + if (state.knownNotToConform(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.untrivialNull(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 `downcasted(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.downcasted(subject) == subject; + lowerCheckCastAnchorFriendlyWay(checkCast, subject); + } + + /** + * Porcelain method. + * + * <p> + * Rather than tracking the CheckCastNode via {@link com.oracle.graal.phases.common.cfs.State + * State} (doing so woud add a special case because a + * {@link com.oracle.graal.nodes.java.CheckCastNode} isn't a + * {@link com.oracle.graal.nodes.extended.GuardingNode}) this method creates an anchor by + * lowering the CheckCastNode into a FixedGuardNode. Not the same way as done by + * {@link com.oracle.graal.nodes.java.CheckCastNode#lower(com.oracle.graal.nodes.spi.LoweringTool)} + * which lowers into a {@link com.oracle.graal.nodes.GuardingPiNode} (which is not a + * {@link com.oracle.graal.nodes.extended.GuardingNode}). + * </p> + * + * <p> + * With that, state tracking can proceed as usual. + * </p> + * + * @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.declared(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.downcasted(checkCast); + if (subject == checkCast) { + subject = reasoner.downcasted(checkCast.object()); + } + } else { + subject = reasoner.downcasted(checkCast.object()); + } + + ObjectStamp subjectStamp = (ObjectStamp) subject.stamp(); + ResolvedJavaType subjectType = subjectStamp.type(); + + // TODO move this check to downcasted() + assert !precisionLoss(checkCast.object(), subject); + + /* + * 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, `downcasted()` 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); + + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/EquationalReasoner.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,946 @@ +/* + * 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.debug.Debug; +import com.oracle.graal.debug.DebugMetric; +import com.oracle.graal.graph.Node; +import com.oracle.graal.graph.NodeBitMap; +import com.oracle.graal.graph.spi.CanonicalizerTool; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.FloatingNode; +import com.oracle.graal.nodes.calc.IsNullNode; +import com.oracle.graal.nodes.calc.ObjectEqualsNode; +import com.oracle.graal.nodes.extended.GuardedNode; +import com.oracle.graal.nodes.extended.GuardingNode; +import com.oracle.graal.nodes.java.CheckCastNode; +import com.oracle.graal.nodes.java.InstanceOfNode; +import com.oracle.graal.nodes.spi.ValueProxy; +import com.oracle.graal.compiler.common.type.IllegalStamp; +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.nodes.util.GraphUtil; + +import java.util.IdentityHashMap; +import java.util.Set; + +/** + * <p> + * 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 + * EquationalReasoner} can be used to reduce N's inputs (actually only those inputs of Value and + * Condition {@link com.oracle.graal.graph.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)} + * </p> + * + * <p> + * The name {@link EquationalReasoner EquationalReasoner} was chosen because it conveys what it + * does. + * </p> + */ +public final class EquationalReasoner { + + private static final DebugMetric metricInstanceOfRemoved = Debug.metric("InstanceOfRemoved"); + private static final DebugMetric metricNullCheckRemoved = Debug.metric("NullCheckRemoved"); + private static final DebugMetric metricObjectEqualsRemoved = Debug.metric("ObjectEqualsRemoved"); + private static final DebugMetric metricEquationalReasoning = Debug.metric("EquationalReasoning"); + private static final DebugMetric metricDowncasting = Debug.metric("Downcasting"); + + 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<ValueNode> added = java.util.Collections.newSetFromMap(new IdentityHashMap<ValueNode, Boolean>()); + + /** + * 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 IdentityHashMap<ValueNode, ValueNode> substs = new IdentityHashMap<>(); + + 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; + substs.clear(); + added.clear(); + visited = null; + versionNrAsofLastForce = s.versionNr; + } + + /** + * <p> + * 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). + * </p> + * + * <p> + * Between clearings of cached substitutions, it is expected they get applied a number of times + * to justify the bookkeeping cost. + * </p> + * + */ + 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: + * <ul> + * <li> + * 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)} + * </li> + * <li> + * 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)} + * </li> + * + * </ul> + * + * + * <p> + * 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). + * </p> + * + * <p> + * This method must behave as a function (idempotent query method), ie refrain from mutating the + * state other than updating caches: + * <ul> + * <li>{@link EquationalReasoner#added EquationalReasoner#added},</li> + * <li>{@link EquationalReasoner#visited EquationalReasoner#visited} and</li> + * <li>the cache updated via + * {@link EquationalReasoner#rememberSubstitution(com.oracle.graal.nodes.ValueNode, com.oracle.graal.nodes.ValueNode) + * EquationalReasoner#rememberSubstitution(ValueNode, FloatingNode)}.</li> + * </ul> + * </p> + * + * <p> + * 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). + * </p> + * + * <p> + * This method returns: + * <ul> + * <li> + * the original argument, in case no reduction possible.</li> + * <li> + * 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.</li> + * <li> + * the unmodified argument, in case no reduction was made. Otherwise, a maximally reduced + * {@link com.oracle.graal.nodes.ValueNode}.</li> + * </ul> + * </p> + * + * @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 yet ready 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 ((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)` + */ + if (v instanceof ValueProxy) { + return downcasted(v); + } + + if (n instanceof FloatingNode) { + /* + * `deverbosifyFloatingNode()` will drill down over floating inputs, when that not + * possible anymore it resorts to calling `downcasted()`. Thus it's ok to take the + * `deverbosifyFloatingNode()` route first, as no downcasting opportunity will be + * missed. + */ + return deverbosifyFloatingNode((FloatingNode) n); + } + + if (FlowUtil.hasLegalObjectStamp(v)) { + return downcasted(v); + } + + return n; + } + + /** + * This method: + * + * <ul> + * <li> + * Recurses only over floating inputs to attempt reductions, leave anything else as is.</li> + * <li> + * Performs copy-on-write aka lazy-DAG-copying as described in source comments, in-line.</li> + * <li> + * Usage: must be called only from {@link #deverbosify(com.oracle.graal.graph.Node) + * deverbosify(Node)}.</li> + * </ul> + * */ + 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); + if (FlowUtil.hasLegalObjectStamp(f)) { + /* + * No input has changed doesn't imply there's no witness to refine the + * floating-object value. + */ + ValueNode d = downcasted(f); + return d; + } else { + return f; + } + } + FlowUtil.inferStampAndCheck(changed); + added.add(changed); + ValueNode canon = (ValueNode) changed.canonical(tool); + // might be already in `added`, no problem adding it again. + added.add(canon); + rememberSubstitution(f, canon); + return canon; + } + + /** + * In case of doubt (on whether a reduction actually triggered) it's always ok to invoke " + * <code>rememberSubstitution(f, downcasted(f))</code>": 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 extends ValueNode> 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; + } + + /** + * <p> + * 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). + * </p> + * + * <p> + * 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. + * </p> + * <p> + * 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). + * </p> + * + * @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); + } + } + 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.object()); + if (!FlowUtil.hasLegalObjectStamp(scrutinee)) { + return instanceOf; + } + if (state.isNull(scrutinee)) { + 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 isNull) { + ValueNode object = isNull.object(); + if (!FlowUtil.hasLegalObjectStamp(object)) { + return isNull; + } + ValueNode scrutinee = GraphUtil.unproxify(isNull.object()); + GuardingNode evidence = untrivialNullAnchor(scrutinee); + if (evidence != null) { + metricNullCheckRemoved.increment(); + return trueConstant; + } else if (state.isNonNull(scrutinee)) { + metricNullCheckRemoved.increment(); + return falseConstant; + } + return isNull; + } + + /** + * @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.x()) || !FlowUtil.hasLegalObjectStamp(equals.y())) { + return equals; + } + ValueNode x = GraphUtil.unproxify(equals.x()); + ValueNode y = GraphUtil.unproxify(equals.y()); + 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; + } + + /** + * It's always ok to use "<code>downcasted(object)</code>" instead of " <code>object</code>" + * 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. + * + * <p> + * This method does not + * {@link #rememberSubstitution(com.oracle.graal.nodes.ValueNode, com.oracle.graal.nodes.ValueNode)} + * . + * </p> + * + * @return One of: + * <ul> + * <li>a {@link com.oracle.graal.nodes.PiNode} with more precise stamp than the input if + * the state warrants such downcasting</li> + * <li>a {@link com.oracle.graal.nodes.java.CheckCastNode CheckCastNode} for the same + * scrutinee in question</li> + * <li>the unmodified argument otherwise.</li> + * </ul> + */ + ValueNode downcasted(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.isObjectAlwaysNull(object.stamp())) { + return untrivialNull(object); + } + + // ------------------------------------------ + // actions based on the stamp and the witness + // ------------------------------------------ + + ValueNode scrutinee = GraphUtil.unproxify(object); + + PiNode untrivialNull = untrivialNull(scrutinee); + if (untrivialNull != null) { + 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 = downcastedValueProxy((ValueProxy) object, w); + } else { + result = downcastedUtil(object, w); + } + + return result; + } + + /** + * TODO TypeProfileProxyNode.inferStamp doesn't infer non-null from non-null payload + * + * <p> + * 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. + * </p> + * */ + private static void fixupTypeProfileStamp(ValueNode object) { + if (!(object instanceof TypeProfileProxyNode)) { + return; + } + TypeProfileProxyNode profile = (TypeProfileProxyNode) object; + ObjectStamp outgoinStamp = (ObjectStamp) profile.stamp(); + ObjectStamp payloadStamp = (ObjectStamp) profile.getObject().stamp(); + if (payloadStamp.nonNull() && !outgoinStamp.nonNull()) { + profile.setStamp(FlowUtil.asNonNullStamp(outgoinStamp)); + } + } + + /** + * <p> + * Porcelain method. + * </p> + * + * <p> + * 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. + * </p> + * + * <p> + * The resulting node might not have been in the graph already. + * </p> + * */ + 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); + } + } + + /** + * <p> + * 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. + * </p> + * + * <p> + * Otherwise, if an anchor is found it is returned, null otherwise. + * </p> + */ + public GuardingNode untrivialNullAnchor(ValueNode object) { + assert FlowUtil.hasLegalObjectStamp(object); + if (StampTool.isObjectAlwaysNull(object)) { + return null; + } + return state.knownNull.get(GraphUtil.unproxify(object)); + } + + /** + * + * This method returns: + * <ul> + * <li><b>null</b>, if the argument is known null due to its stamp. Otherwise,</li> + * <li><b>a PiNode</b> wrapping the null constant and an anchor offering evidence as to why the + * argument is known null, if such anchor is available. Otherwise,</li> + * <li><b>null</b></li> + * </ul> + * <p> + * This method does not + * {@link #rememberSubstitution(com.oracle.graal.nodes.ValueNode, com.oracle.graal.nodes.ValueNode)} + * . + * </p> + */ + public PiNode untrivialNull(ValueNode object) { + assert FlowUtil.hasLegalObjectStamp(object); + GuardingNode anchor = untrivialNullAnchor(object); + if (anchor == null) { + return null; + } + if (object instanceof GuardedNode && StampTool.isObjectAlwaysNull(object.stamp())) { + return (PiNode) object; + } + // notice nullConstant is wrapped, not object + PiNode result = wrapInPiNode(nullConstant, anchor, (ObjectStamp) StampFactory.alwaysNull(), false); + return result; + } + + // @formatter:off + /** + * <p>ValueProxys can be classified along two dimensions, + * in addition to the fixed-floating dichotomy.</p> + * + * <p> + * 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. + * </p> + * + * <p> + * 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 <code>downcasted(proxy) == proxy</code> in such cases. + * </p> + * + * <p> + * 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) + *</p> + */ + // @formatter:on + private ValueNode downcastedValueProxy(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 downcastedPiNodeOrPiArrayNode((PiNode) proxy, w); + } else if (proxy instanceof GuardingPiNode) { + return downcastedGuardingPiNode((GuardingPiNode) proxy, w); + } else if (proxy instanceof TypeProfileProxyNode) { + return downcastedTypeProfileProxyNode((TypeProfileProxyNode) proxy); + } else if (proxy instanceof CheckCastNode) { + return downcastedCheckCastNode((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); + } + + /** + * <p> + * 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()}). + * </p> + * + * <p> + * It's both possible and desirable. Example: <code> + * Number n = (Number) o; + * if (n instanceof Integer) { + * return n.intValue(); + * } + * </code> + * + * 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. + * </p> + * + * @see #downcastedValueProxy + * */ + public ValueNode downcastedGuardingPiNode(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); + } + + /** + * <p> + * This method accepts both {@link com.oracle.graal.nodes.PiNode} and + * {@link com.oracle.graal.nodes.PiArrayNode} argument. + * </p> + * + * <p> + * 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. + * </p> + * + * <p> + * 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. + * </p> + * + * <p> + * 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. + * </p> + * + * @see #downcastedValueProxy + * */ + private ValueNode downcastedPiNodeOrPiArrayNode(PiNode envelope, Witness w) { + return downcastedUtil(envelope, w); + } + + /** + * <p> + * 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. + * </p> + * + * <p> + * Otherwise returns the unmodified argument. + * </p> + * + * @see #downcastedValueProxy + * */ + private ValueNode downcastedTypeProfileProxyNode(TypeProfileProxyNode envelope) { + ValueNode payload = envelope.getOriginalNode(); + ValueNode d = downcasted(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; + } + + /** + * <p> + * 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. + * </p> + * */ + private ValueNode downcastedCheckCastNode(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 = downcasted(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 = downcasted(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); + } + + /** + * <p> + * Porcelain method. + * </p> + * + * <p> + * 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. + * </p> + * */ + 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; + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,218 @@ +/* + * 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.calc.IsNullNode; +import com.oracle.graal.nodes.extended.GuardingNode; +import com.oracle.graal.nodes.java.*; +import com.oracle.graal.phases.tiers.PhaseContext; + +/** + * <p> + * This class implements control-flow sensitive reductions for + * {@link com.oracle.graal.nodes.FixedGuardNode}. + * </p> + * + * @see #visitFixedGuardNode(com.oracle.graal.nodes.FixedGuardNode) + * */ +public abstract class FixedGuardReduction extends CheckCastReduction { + + public FixedGuardReduction(FixedNode start, State initialState, PhaseContext context) { + super(start, initialState, context); + } + + /** + * In case the condition is constant, + * {@link com.oracle.graal.nodes.FixedGuardNode#simplify(com.oracle.graal.graph.spi.SimplifierTool) + * FixedGuardNode#simplify(SimplifierTool)} will eventually remove the + * {@link com.oracle.graal.nodes.FixedGuardNode} ("always succeeds") or kill the code that + * should be killed ("always fails"). + * + * <p> + * The only thing we do here is tracking as true fact (from this program point onwards) the + * condition of the {@link com.oracle.graal.nodes.FixedGuardNode FixedGuardNode}. + * </p> + * + * <p> + * Precondition: the condition hasn't been deverbosified yet. + * </p> + */ + protected final void visitFixedGuardNode(FixedGuardNode f) { + + /* + * A FixedGuardNode with LogicConstantNode condition is left untouched. + */ + + 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; + } + + /* + * Attempt to eliminate the current FixedGuardNode by using another GuardingNode already in + * scope and with equivalent condition. + */ + + GuardingNode existingGuard = f.isNegated() ? state.falseFacts.get(f.condition()) : state.trueFacts.get(f.condition()); + if (existingGuard != null) { + // assert existingGuard instanceof FixedGuardNode; + metricFixedGuardNodeRemoved.increment(); + f.replaceAtUsages(existingGuard.asNode()); + graph.removeFixed(f); + return; + } + + final LogicNode cond = f.condition(); + final boolean isTrue = !f.isNegated(); + + /* + * FixedGuardNode requires handling similar to that of GuardingPiNode, (ie the condition + * can't simply be deverbosified in place). A replacement anchor is needed, ie an anchor + * that amounts to the same combination of (negated, condition) for the FixedGuardNode at + * hand. + */ + + // TODO what about isDependencyTainted + + if (cond instanceof IsNullNode) { + final IsNullNode isNullNode = (IsNullNode) cond; + if (isTrue) { + // grab an anchor attesting nullness + final GuardingNode replacement = reasoner.untrivialNullAnchor(isNullNode.object()); + if (replacement != null) { + removeFixedGuardNode(f, replacement); + return; + } + if (state.isNonNull(isNullNode.object())) { + markFixedGuardNodeAlwaysFails(f); + return; + } + // can't produce evidence, fall-through to addFact + } else { + // grab an anchor attesting non-nullness + final Witness w = state.typeInfo(isNullNode.object()); + if (w != null && w.isNonNull()) { + removeFixedGuardNode(f, w.guard()); + return; + } + if (state.isNull(isNullNode.object())) { + markFixedGuardNodeAlwaysFails(f); + return; + } + // can't produce evidence, fall-through to addFact + } + } else if (cond instanceof InstanceOfNode) { + final InstanceOfNode iOf = (InstanceOfNode) cond; + final Witness w = state.typeInfo(iOf.object()); + if (isTrue) { + // grab an anchor attesting instanceof + if (w != null) { + if (w.isNonNull() && w.type() != null) { + if (iOf.type().isAssignableFrom(w.type())) { + removeFixedGuardNode(f, w.guard()); + return; + } + if (State.knownNotToConform(w.type(), iOf.type())) { + markFixedGuardNodeAlwaysFails(f); + return; + } + } + } + if (state.isNull(iOf.object())) { + markFixedGuardNodeAlwaysFails(f); + return; + } + // can't produce evidence, fall-through to addFact + } else { + // grab an anchor attesting not-instanceof + // (1 of 2) attempt determining nullness + final GuardingNode nullGuard = reasoner.untrivialNullAnchor(iOf.object()); + if (nullGuard != null) { + removeFixedGuardNode(f, nullGuard); + return; + } + // (2 of 2) attempt determining known-not-to-conform + if (w != null && !w.cluelessAboutType()) { + if (State.knownNotToConform(w.type(), iOf.type())) { + removeFixedGuardNode(f, w.guard()); + return; + } + } + // can't produce evidence, fall-through to addFact + } + } else if (isTrue && cond instanceof ShortCircuitOrNode) { + CastCheckExtractor cce = CastCheckExtractor.extract(cond); + if (cce != null && !State.isDependencyTainted(cce.subject, f)) { + // grab an anchor attesting check-cast + Witness w = state.typeInfo(cce.subject); + if (w != null && w.type() != null) { + if (cce.type.isAssignableFrom(w.type())) { + removeFixedGuardNode(f, w.guard()); + return; + } + if (State.knownNotToConform(w.type(), cce.type)) { + markFixedGuardNodeAlwaysFails(f); + return; + } + } + } + // can't produce evidence, fall-through to addFact + } + + state.addFact(isTrue, cond, 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. + * + * <p> + * The `replacement` guard must be such that it implies the `old` guard. + * </p> + * */ + private void removeFixedGuardNode(FixedGuardNode old, GuardingNode replacement) { + if (replacement == null) { + return; + } + metricFixedGuardNodeRemoved.increment(); + old.replaceAtUsages(replacement.asNode()); + graph.removeFixed(old); + // `old.condition()` if unused will be removed in finished() + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowSensitiveReduction.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,545 @@ +/* + * 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.graph.Node; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.FloatingNode; +import com.oracle.graal.nodes.extended.LoadHubNode; +import com.oracle.graal.nodes.extended.NullCheckNode; +import com.oracle.graal.nodes.java.*; +import com.oracle.graal.compiler.common.type.IllegalStamp; +import com.oracle.graal.nodes.type.StampTool; +import com.oracle.graal.nodes.util.GraphUtil; +import com.oracle.graal.phases.common.DeadCodeEliminationPhase; +import com.oracle.graal.phases.tiers.PhaseContext; + +import java.lang.reflect.Modifier; + +import static com.oracle.graal.api.meta.DeoptimizationReason.*; + +/** + * <p> + * All control-flow-sensitive reductions follow the common pattern of + * <ul> + * <li>Recognizing properties of interest (ie, LogicNode-s) at control-flow splits, as well as upon + * check-casts and fixed-guards.</li> + * <li>Using the information thus tracked to simplify + * <ul> + * <li>side-effects free expressions, via + * {@link com.oracle.graal.phases.common.cfs.EquationalReasoner#deverbosify(com.oracle.graal.graph.Node)} + * </li> + * <li>control-flow, eg. by eliminating redundant fixed-guards and check-casts, ie which are known + * always to hold.</li> + * </ul> + * </li> + * </ul> + * </p> + * + * @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(FixedNode start, State initialState, PhaseContext context) { + super(start, initialState, context); + } + + /** + * <p> + * This method performs two kinds of cleanup: + * <ol> + * <li> + * marking as unreachable certain code-paths, as described in + * {@link com.oracle.graal.phases.common.cfs.BaseReduction.PostponedDeopt}</li> + * <li> + * Removing nodes not in use that were added during this phase, as described next.</li> + * </ol> + * </p> + * + * + * <p> + * 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. + * </p> + * + * <p> + * This method goes over all of the nodes that deverbosification might have added, which are + * either: + * <ul> + * <li> + * {@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</li> + * <li> + * {@link com.oracle.graal.nodes.java.MethodCallTargetNode}, added by + * {@link #deverbosifyInputsCopyOnWrite(com.oracle.graal.nodes.java.MethodCallTargetNode)}</li> + * </ul> + * + * Checking if they aren't in use, proceeding to remove them in that case. + * </p> + * + * */ + @Override + public void finished() { + if (!postponedDeopts.isEmpty()) { + for (PostponedDeopt postponed : postponedDeopts) { + postponed.doRewrite(falseConstant); + } + new DeadCodeEliminationPhase().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); + } + + private static boolean isAliveWithoutUsages(FloatingNode node) { + return node.isAlive() && node.usages().isEmpty(); + } + + private void registerControlSplit(Node pred, BeginNode begin) { + assert pred != null && begin != null; + assert !state.isUnreachable; + + if (begin instanceof LoopExitNode) { + state.clear(); + } + + 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; + } + // preferable would be trackExact, but not there yet + state.addNullness(false, loadHub.object(), begin); + if (state.knownNotToConform(loadHub.object(), type)) { + postponedDeopts.addDeoptAfter(begin, UnreachedCode); + state.impossiblePath(); + return; + } + if (type.isInterface()) { + state.trackNN(loadHub.object(), begin); + } else { + state.trackIO(loadHub.object(), type, begin); + } + } + } + + /** + * + * <p> + * 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). + * </p> + * + * <p> + * 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. + * </p> + * + * <p> + * <b> Please note the parent node is mutated upon any descendant changing. No copy-on-write is + * performed for the parent node itself. </b> + * </p> + * + * <p> + * In more detail, for each direct {@link com.oracle.graal.nodes.ValueNode} input of the node at + * hand, + * + * <ol> + * <li> + * 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.</li> + * + * <li> + * 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.</li> + * + * </ol> + * </p> + * + * @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) : "ConditionalElim shouldn't run in 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) { + MethodCallTargetNode changed = null; + for (ValueNode i : FlowUtil.distinctValueAndConditionInputs(parent)) { + Node j = reasoner.deverbosify(i); + 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: + * + * <ul> + * <li>the state has already stabilized (ie no more pending iterations in the "iterative" + * dataflow algorithm); or</li> + * <li>any rewritings made based on the state in its current form are conservative enough to be + * safe.</li> + * </ul> + * + * <p> + * 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. + * </p> + * + */ + @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 AbstractBeginNode 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 the remaining FixedWithNextNode subclasses, pick those with good changes 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 others are additionally guarded (eg JavaReadNode), thus *their* guards could be + // simplified. + + } + + /** + * In case the scrutinee: + * + * <ul> + * <li>is known to be null, an unconditional deopt is added.</li> + * <li>is known to be non-null, the NullCheckNode is removed.</li> + * </ul> + * + * <p> + * Precondition: the input (ie, object) hasn't been deverbosified yet. + * </p> + * */ + 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; + } + // TODO ANCHOR NEEDED: state.trackNN(object, ncn); + } + + /** + * 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. + * + * <p> + * Precondition: inputs haven't been deverbosified yet. + * </p> + * */ + 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() + } + } + } + } + + /** + * One or more arguments at `invoke` may have control-flow sensitive simplifications. In such + * case, a new {@link com.oracle.graal.nodes.java.MethodCallTargetNode MethodCallTargetNode} is + * prepared just for this callsite, consuming reduced arguments. This proves useful in + * connection with inlining, in order to specialize callees on the types of arguments other than + * the receiver (examples: multi-methods, the inlining problem, lambdas as arguments). + * + * <p> + * Precondition: inputs haven't been deverbosified yet. + * </p> + * */ + 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() != MethodCallTargetNode.InvokeKind.Interface && callTarget.invokeKind() != MethodCallTargetNode.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.resolveMethod(callTarget.targetMethod()); + if (method == null) { + return; + } + if (method.canBeStaticallyBound() || Modifier.isFinal(type.getModifiers())) { + metricMethodResolved.increment(); + callTarget.setInvokeKind(MethodCallTargetNode.InvokeKind.Special); + callTarget.setTargetMethod(method); + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowSensitiveReductionPhase.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,52 @@ +/* + * 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<PhaseContext> { + + 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")) { + new FlowSensitiveReduction(graph.start(), new State(), context).apply(); + } catch (Throwable e) { + throw Debug.handle(e); + } + } + +} \ No newline at end of file
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowUtil.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,317 @@ +/* + * 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.debug.Debug; +import com.oracle.graal.debug.DebugConfig; +import com.oracle.graal.debug.DebugConfigScope; +import com.oracle.graal.debug.internal.DebugScope; +import com.oracle.graal.graph.InputType; +import com.oracle.graal.graph.Node; +import com.oracle.graal.graph.NodeClass; +import com.oracle.graal.nodes.*; +import com.oracle.graal.compiler.common.type.ObjectStamp; +import com.oracle.graal.compiler.common.type.Stamp; +import com.oracle.graal.compiler.common.type.StampFactory; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +public class FlowUtil { + + private FlowUtil() { + // no instances of this class + } + + public static boolean lacksUsages(Node n) { + return n.recordsUsages() && n.usages().isEmpty(); + } + + 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<ValueNode> distinctValueAndConditionInputs(Node n) { + ArrayList<ValueNode> result = null; + NodeClass.NodeClassIterator iter = n.inputs().iterator(); + while (iter.hasNext()) { + NodeClass.Position pos = iter.nextPosition(); + InputType inputType = pos.getInputType(n); + 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 <code>oldInput</code> among its (direct) inputs. After + * this method has run, all such occurrences have been replaced with <code>newInput</code>. In + * case that makes <code>oldInput</code> 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() + } + + public static StructuredGraph visualize(StructuredGraph graph, String title) { + DebugConfig debugConfig = DebugScope.getConfig(); + DebugConfig fixedConfig = Debug.fixedConfig(false, true, false, false, debugConfig.dumpHandlers(), debugConfig.output()); + try (DebugConfigScope s = Debug.setConfig(fixedConfig)) { + Debug.dump(graph, title); + + return graph; + } + } + + public static final String ANSI_RESET = "\u001B[0m"; + public static final String ANSI_BLACK = "\u001B[30m"; + public static final String ANSI_RED = "\u001B[31m"; + public static final String ANSI_GREEN = "\u001B[32m"; + public static final String ANSI_YELLOW = "\u001B[33m"; + public static final String ANSI_BLUE = "\u001B[34m"; + public static final String ANSI_PURPLE = "\u001B[35m"; + public static final String ANSI_CYAN = "\u001B[36m"; + public static final String ANSI_WHITE = "\u001B[37m"; + + public static void highlightInRed(String msg) { + System.out.println(ANSI_RED + msg + ANSI_RESET); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/GuardingPiReduction.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,373 @@ +/* + * 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.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; + +/** + * <p> + * This class implements control-flow sensitive reductions for + * {@link com.oracle.graal.nodes.GuardingPiNode}. + * </p> + * + * @see #visitGuardingPiNode(com.oracle.graal.nodes.GuardingPiNode) + * */ +public abstract class GuardingPiReduction extends BaseReduction { + + public GuardingPiReduction(FixedNode start, State initialState, PhaseContext context) { + super(start, initialState, context); + } + + /** + * <p> + * 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}. + * </p> + * + * <ol> + * <li> + * 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).</li> + * <li> + * 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.</li> + * <li> + * 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)}.</li> + * </ol> + * + * <p> + * Precondition: the condition hasn't been deverbosified yet. + * </p> + * + * */ + 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); + + 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); + + } + + /** + * <p> + * Based on flow-sensitive knowledge, two pre-requisites have to be fulfilled in order to remove + * a {@link com.oracle.graal.nodes.GuardingPiNode}: + * + * <ul> + * <li>the condition must refer only to the payload of the + * {@link com.oracle.graal.nodes.GuardingPiNode}</li> + * <li>the condition must check properties about which the state tracks not only a true/false + * answer, but also an anchor witnessing that fact</li> + * <li>the condition may not check anything else beyond what's stated in the items above.</li> + * </ul> + * </p> + * + * <p> + * 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.graph.InputType#Value}) with a {@link com.oracle.graal.nodes.PiNode} + * that wraps the payload and the anchor in question. + * </p> + * + * <p> + * Precondition: the condition hasn't been deverbosified yet. + * </p> + * + * @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.isObjectAlwaysNull(payload) ? payload : reasoner.untrivialNull(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 <something> + */ + 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.downcasted(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.isObjectNonNull(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.downcasted(payload); + if (d == null) { + return false; + } + + if (StampTool.isObjectAlwaysNull(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.object() == 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); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Histogram.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,70 @@ +/* + * 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<Integer, Integer> { + + 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<Integer, Integer> 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) { + FlowUtil.highlightInRed(msg); + } else { + System.out.println(msg); + } + } + System.out.println(prefix + "--------------------------"); + } + + @Override + public Histogram clone() { + return (Histogram) super.clone(); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/IterativeFlowSensitiveReductionPhase.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,90 @@ +/* + * 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.code.*; +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.CanonicalizerPhase; +import com.oracle.graal.phases.common.util.*; +import com.oracle.graal.phases.tiers.*; + +public class IterativeFlowSensitiveReductionPhase extends BasePhase<PhaseContext> { + + private static final int MAX_ITERATIONS = 256; + + private final CanonicalizerPhase canonicalizer; + + public IterativeFlowSensitiveReductionPhase(CanonicalizerPhase canonicalizer) { + this.canonicalizer = canonicalizer; + } + + public static class CountingListener extends HashSetNodeChangeListener { + + public int count; + + @Override + public void nodeChanged(Node node) { + super.nodeChanged(node); + } + + } + + // private Histogram histogram = new Histogram("FSR-"); + + @Override + protected void run(StructuredGraph graph, PhaseContext context) { + FlowSensitiveReductionPhase eliminate = new FlowSensitiveReductionPhase(context.getMetaAccess()); + CountingListener listener = new CountingListener(); + int count = 1; + while (true) { + listener.count = count; + graph.trackInputChange(listener); + graph.trackUsagesDroppedZero(listener); + eliminate.apply(graph, context); + graph.stopTrackingInputChange(); + graph.stopTrackingUsagesDroppedZero(); + if (listener.getChangedNodes().isEmpty()) { + // histogram.tick(count); + break; + } + for (Node node : graph.getNodes()) { + if (node instanceof Simplifiable) { + listener.getChangedNodes().add(node); + } + } + canonicalizer.applyIncremental(graph, context, listener.getChangedNodes()); + listener.getChangedNodes().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 " + MAX_ITERATIONS); + } + } + // histogram.print(); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/State.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,813 @@ +/* + * 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.Kind; +import com.oracle.graal.api.meta.ResolvedJavaType; +import com.oracle.graal.debug.Debug; +import com.oracle.graal.debug.DebugMetric; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.IsNullNode; +import com.oracle.graal.nodes.calc.ObjectEqualsNode; +import com.oracle.graal.nodes.extended.GuardedNode; +import com.oracle.graal.nodes.extended.GuardingNode; +import com.oracle.graal.nodes.java.InstanceOfNode; +import com.oracle.graal.nodes.spi.ValueProxy; +import com.oracle.graal.compiler.common.type.ObjectStamp; +import com.oracle.graal.nodes.type.StampTool; +import com.oracle.graal.nodes.util.GraphUtil; +import com.oracle.graal.phases.graph.MergeableState; + +import java.lang.reflect.Modifier; +import java.util.*; + +/** + * 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<State> implements Cloneable { + + private static final DebugMetric metricTypeRegistered = Debug.metric("TypeRegistered"); + private static final DebugMetric metricNullnessRegistered = Debug.metric("NullnessRegistered"); + private static final DebugMetric metricObjectEqualsRegistered = Debug.metric("ObjectEqualsRegistered"); + private static final DebugMetric metricImpossiblePathDetected = Debug.metric("ImpossiblePathDetected"); + + /** + * <p> + * 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. + * </p> + * + * <p> + * Still, {@link State#versionNr versionNr} proves useful in two cases: + * + * <ul> + * <li>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.</li> + * <li>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).</li> + * </ul> + * </p> + * + * */ + 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(); + } + + /** + * <p> + * This map semantically tracks "facts" (ie, properties valid for the program-point the state + * refers to) as opposed to floating-guard-dependent properties. The + * {@link com.oracle.graal.nodes.extended.GuardingNode} being tracked comes handy at + * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction#visitFixedGuardNode(com.oracle.graal.nodes.FixedGuardNode)} + * . + * </p> + * + * <p> + * On a related note, {@link #typeRefinements} also captures information the way + * {@link #trueFacts} and {@link #falseFacts} do, including "witnessing" guards. Why not just + * standardize on one of them, and drop the other? Because the {@link #typeRefinements} eagerly + * aggregates information for easier querying afterwards, e.g. when producing a "downcasted" + * value (which involves building a {@link com.oracle.graal.nodes.PiNode}, see + * {@link EquationalReasoner#downcasted(com.oracle.graal.nodes.ValueNode) downcasted()} + * </p> + * + * */ + private IdentityHashMap<ValueNode, Witness> typeRefinements; + + IdentityHashMap<ValueNode, GuardingNode> knownNull; + IdentityHashMap<LogicNode, GuardingNode> trueFacts; + IdentityHashMap<LogicNode, GuardingNode> falseFacts; + + public State() { + this.typeRefinements = new IdentityHashMap<>(); + this.knownNull = new IdentityHashMap<>(); + this.trueFacts = new IdentityHashMap<>(); + this.falseFacts = new IdentityHashMap<>(); + } + + public State(State other) { + this.isUnreachable = other.isUnreachable; + this.versionNr = other.versionNr; + this.typeRefinements = new IdentityHashMap<>(); + for (Map.Entry<ValueNode, Witness> entry : other.typeRefinements.entrySet()) { + this.typeRefinements.put(entry.getKey(), new Witness(entry.getValue())); + } + this.knownNull = new IdentityHashMap<>(other.knownNull); + this.trueFacts = new IdentityHashMap<>(other.trueFacts); + this.falseFacts = new IdentityHashMap<>(other.falseFacts); + } + + /** + * @return A new list containing only those states that are reachable. + * */ + private static ArrayList<State> reachableStates(List<State> states) { + ArrayList<State> result = new ArrayList<>(states); + Iterator<State> iter = result.iterator(); + while (iter.hasNext()) { + if (iter.next().isUnreachable) { + iter.remove(); + } + } + return result; + } + + private IdentityHashMap<ValueNode, Witness> mergeKnownTypes(MergeNode merge, ArrayList<State> withReachableStates) { + IdentityHashMap<ValueNode, Witness> newKnownTypes = new IdentityHashMap<>(); + + for (Map.Entry<ValueNode, Witness> 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; + } + + private IdentityHashMap<ValueNode, GuardingNode> mergeKnownNull(MergeNode merge, ArrayList<State> withReachableStates) { + // newKnownNull starts empty + IdentityHashMap<ValueNode, GuardingNode> newKnownNull = new IdentityHashMap<>(); + for (Map.Entry<ValueNode, GuardingNode> entry : knownNull.entrySet()) { + ValueNode key = entry.getKey(); + GuardingNode newGN = entry.getValue(); + boolean missing = false; + + for (State other : withReachableStates) { + GuardingNode otherGuard = other.knownNull.get(key); + if (otherGuard == null) { + missing = true; + break; + } + if (otherGuard != newGN) { + newGN = merge; + } + } + if (!missing) { + newKnownNull.put(key, newGN); + } + } + return newKnownNull; + } + + /** + * <p> + * 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. + * </p> + * + * <p> + * In more detail, <code>FlowSensitiveReduction#visitAbstractEndNode()</code> 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#inferPhiStamp()} but we are careful to skip them + * when merging type-witnesses and known-null maps. + * </p> + */ + private void mergePhis(MergeNode merge, List<State> withStates, IdentityHashMap<ValueNode, Witness> newKnownPhiTypes, IdentityHashMap<ValueNode, GuardingNode> newKnownNullPhis) { + + if (merge instanceof LoopBeginNode) { + return; + } + + for (PhiNode phi : merge.phis()) { + assert phi == GraphUtil.unproxify(phi); + if (phi instanceof ValuePhiNode && phi.getKind() == Kind.Object) { + ArrayList<ValueNode> 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 (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()); + } else if (w.isNonNull() && !phiStamp.nonNull()) { + // precision gain regarding nullness + newKnownPhiTypes.put(phi, w); + // confirm no precision loss regarding type + assert !FlowUtil.isMorePrecise(phiStamp.type(), w.type()); + } + if (nonPollutedStamp.alwaysNull()) { + newKnownNullPhis.put(phi, merge); + } + } + } + + } + + private static boolean implies(boolean a, boolean b) { + return !a || b; + } + + @Override + public boolean merge(MergeNode merge, List<State> withStates) { + + ArrayList<State> withReachableStates = reachableStates(withStates); + if (withReachableStates.isEmpty()) { + return true; + } + + for (State state : withReachableStates) { + versionNr = Math.max(versionNr, state.versionNr) + 1; + isUnreachable &= state.isUnreachable; + } + + if (isUnreachable) { + typeRefinements.clear(); + knownNull.clear(); + return true; + } + + // may also get updated in a moment, during processing of phi nodes. + IdentityHashMap<ValueNode, Witness> newKnownTypes = mergeKnownTypes(merge, withReachableStates); + // may also get updated in a moment, during processing of phi nodes. + IdentityHashMap<ValueNode, GuardingNode> newKnownNull = mergeKnownNull(merge, withReachableStates); + mergePhis(merge, withStates, newKnownTypes, newKnownNull); + this.typeRefinements = newKnownTypes; + this.knownNull = newKnownNull; + + this.trueFacts = mergeTrueFacts(withReachableStates, merge); + this.falseFacts = mergeFalseFacts(withReachableStates, merge); + return true; + } + + private IdentityHashMap<LogicNode, GuardingNode> mergeTrueFacts(ArrayList<State> withReachableStates, GuardingNode merge) { + IdentityHashMap<LogicNode, GuardingNode> newTrueConditions = new IdentityHashMap<>(); + for (Map.Entry<LogicNode, GuardingNode> 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 IdentityHashMap<LogicNode, GuardingNode> mergeFalseFacts(ArrayList<State> withReachableStates, GuardingNode merge) { + IdentityHashMap<LogicNode, GuardingNode> newFalseConditions = new IdentityHashMap<>(); + for (Map.Entry<LogicNode, GuardingNode> 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; + } + + /** + * @retun 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)); + } + + /** + * @retun true iff the argument is known to stand for null. + */ + public boolean isNull(ValueNode object) { + assert FlowUtil.hasLegalObjectStamp(object); + return StampTool.isObjectAlwaysNull(object) || knownNull.containsKey(GraphUtil.unproxify(object)); + } + + /** + * <p> + * 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. + * </p> + * + * <p> + * 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. + * </p> + * + * @retun true iff the argument is known to stand for non-null. + */ + public boolean isNonNull(ValueNode object) { + assert FlowUtil.hasLegalObjectStamp(object); + if (StampTool.isObjectNonNull(object)) { + return true; + } + Witness w = typeInfo(object); + return w == null ? false : w.isNonNull(); + } + + /** + * @retun true iff the argument is known to stand for an object conforming 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; + } + + /** + * @retun true iff the argument is known to stand for an object that definitely does not conform + * to the given type. + */ + public boolean knownNotToConform(ValueNode object, ResolvedJavaType to) { + assert FlowUtil.hasLegalObjectStamp(object); + assert !to.isPrimitive(); + final ValueNode scrutinee = GraphUtil.unproxify(object); + if (isNull(scrutinee)) { + 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; + } + + // @formatter:off + /** + * \ | | | | + * \ 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 + * + * @retun 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; + } + + /** + * <p> + * 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) + * <code>trackIO(ResolvedJavaType, GuardingNode)</code>} should be invoked instead. + * </p> + * + * <p> + * 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. + * </p> + * + * @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; + } + ResolvedJavaType stampType = StampTool.typeOrNull(object); + if (stampType != null && !stampType.isInterface()) { + return trackIO(object, stampType, anchor); + } + Witness w = getOrElseAddTypeInfo(object); + if (w.trackNN(anchor)) { + versionNr++; + 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) + * <code>trackIO(ResolvedJavaType, GuardingNode)</code>} should be invoked instead. + * + * <p> + * 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. + * </p> + * + * @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; + } + Witness w = getOrElseAddTypeInfo(object); + if (w.trackCC(observed, anchor)) { + versionNr++; + metricTypeRegistered.increment(); + return true; + } + return false; + } + + /** + * Updates this {@link State State} to account for an observation about the non-null scrutinee + * conforming to a type. + * + * <p> + * 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. + * </p> + * + * @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; + } + Witness w = getOrElseAddTypeInfo(object); + if (w.trackIO(observed, anchor)) { + versionNr++; + metricTypeRegistered.increment(); + 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. + * + * <p> + * 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. + * </p> + * + * */ + private void addFactPrimordial(LogicNode condition, IdentityHashMap<LogicNode, GuardingNode> to, GuardingNode anchor) { + assert condition != null; + if (!to.containsKey(condition)) { + versionNr++; + to.put(condition, anchor); + } + } + + /** + * Ideas for the future: + * <ul> + * <li>track inferred less-than edges from (accumulated) CompareNode-s</li> + * <li>track set-representative for equality classes determined by (chained) IntegerTestNode</li> + * </ul> + * + * */ + public void addFact(boolean isTrue, LogicNode condition, GuardingNode anchor) { + assert anchor != null; + assert !isUnreachable; + + if (condition instanceof LogicConstantNode) { + if (((LogicConstantNode) condition).getValue() != isTrue) { + impossiblePath(); + } + return; + } + + if (condition instanceof LogicNegationNode) { + addFact(!isTrue, ((LogicNegationNode) condition).getInput(), 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.object(), anchor); + } else if (condition instanceof ObjectEqualsNode) { + addFactObjectEqualsNode(isTrue, (ObjectEqualsNode) condition, anchor); + } else { + addFactPrimordial(condition, isTrue ? trueFacts : falseFacts, anchor); + } + } + + /** + * 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.object(); + if (isTrue) { + if (knownNotToConform(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); + } + } else { + if (knownToConform(object, instanceOf.type())) { + impossiblePath(); // TODO this used to be a bug + return; + } + if (instanceOf.type().isInterface()) { + if (!knownNotToConform(object, instanceOf.type())) { + addFactPrimordial(instanceOf, falseFacts, anchor); + } + } + } + } + + private void addFactObjectEqualsNode(boolean isTrue, ObjectEqualsNode equals, GuardingNode anchor) { + if (isDependencyTainted(equals.x(), anchor)) { + return; + } + if (isDependencyTainted(equals.y(), anchor)) { + return; + } + ValueNode x = GraphUtil.unproxify(equals.x()); + ValueNode y = GraphUtil.unproxify(equals.y()); + 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.x(), anchor); + addNullness(true, equals.y(), anchor); + } else if (isNonNull(x) || isNonNull(y)) { + metricObjectEqualsRegistered.increment(); + addNullness(false, equals.x(), anchor); + addNullness(false, equals.y(), 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.x(), best, anchor); + trackCC(equals.y(), 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.y(), anchor); + } else if (!isNonNull(x) && isNull(y)) { + metricObjectEqualsRegistered.increment(); + addNullness(false, equals.x(), 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; + } + ValueNode original = GraphUtil.unproxify(value); + boolean wasNull = isNull(original); + boolean wasNonNull = isNonNull(original); + if (isNull) { + if (wasNonNull) { + impossiblePath(); + } else { + metricNullnessRegistered.increment(); + versionNr++; + knownNull.put(original, anchor); + } + } else { + if (wasNull) { + impossiblePath(); + } else { + metricNullnessRegistered.increment(); + trackNN(original, anchor); + } + } + } + + /** + * + * @return true iff `value` may lose dependency not covered by `anchor`. + * */ + public static boolean isDependencyTainted(ValueNode value, GuardingNode anchor) { + 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(); + knownNull.clear(); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Witness.java Fri Apr 25 16:50:52 2014 +0200 @@ -0,0 +1,440 @@ +/* + * 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; + +/** + * <p> + * A witness progressively tracks more detailed properties about an object value (the scrutinee); + * the properties in question comprise whether the scrutinee has been observed: + * + * <ul> + * <li>as non-null,</li> + * <li>in a successful checkcast, or</li> + * <li>in a successful instanceof.</li> + * </ul> + * </p> + * + * <p> + * 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. + * </p> + * + * <p> + * 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. + * </p> + * + * <p> + * 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}: + * <ul> + * <li>{@link #atNonNull()}</li> + * <li>{@link #atCheckCast()}</li> + * <li>{@link #atInstanceOf()}</li> + * </ul> + * </p> + * + * <p> + * 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. + * </p> + * + * <p> + * Some useful facts about the Statechart implemented by {@link Witness Witness}: + * + * <ul> + * <li>the start-state is "clueless"</li> + * <li> + * 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.</li> + * </ul> + * </p> + * + */ +public class Witness implements Cloneable { + + private static enum LEVEL { + CLUELESS, + NN, + CC, + IO + } + + private boolean atNonNull() { + return level == LEVEL.NN; + } + + private boolean atCheckCast() { + return level == LEVEL.CC; + } + + private boolean atInstanceOf() { + return level == LEVEL.IO; + } + + 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; + 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(); + } + + /** + * Type-witnesses aren't tracked for known-to-be-null. Therefore, although method + * {@link #isNonNull() isNonNull()} can be found in this class there's on purpose no companion + * <code>isNull()</code> . + */ + public boolean isNonNull() { + return atNonNull() || atInstanceOf(); + } + + /** + * 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(), false); + } + + 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: + * + * <ul> + * <li> + * {@link com.oracle.graal.nodes.BeginNode BeginNode},</li> + * <li> + * {@link com.oracle.graal.nodes.LoopExitNode LoopExitNode},</li> + * <li> + * {@link com.oracle.graal.nodes.FixedGuardNode FixedGuardNode}</li> + * <li>{@link com.oracle.graal.nodes.MergeNode MergeNode}, resulting from merging two witnesses + * with different values for this anchor</li> + * </ul> + * + * <p> + * 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}. + * </p> + * + */ + private GuardingNode gn = null; + + /** + * Invariants of this class: + * <ul> + * <li>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 <code>java.lang.Object</code> as the + * seen type and nothing more.</li> + * <li>{@link #seen seen} may be null as long as the only hint being recorded is non-nullness</li> + * <li>A non-null value for {@link #seen seen} can't be tracked with NN, that combination + * amounts to IO and is tracked as such</li> + * <li>At most one of NN, CC, IO may be tracked at any given time</li> + * <li>A non-null CC or a non-null IO force {@link #seen seen} to be non-null</li> + * <li>{@link #seen seen} must be null or denote a non-interface reference type (ie, either a + * class-type or an array-type)</li> + * </ul> + */ + private boolean repOK() { + if (clueless()) { + assert level == LEVEL.CLUELESS; + return true; + } + if (level == LEVEL.NN) { + assert seen == null; + } + if (seen != null) { + assert !seen.isInterface(); + assert !seen.isPrimitive(); + } + boolean gnOK = gn instanceof BeginNode || gn instanceof LoopExitNode || gn instanceof MergeNode || gn instanceof FixedGuardNode; + assert gnOK; + return true; + } + + /** + * Helper method for readability in complex conditions. + */ + public boolean clueless() { + return cluelessAboutType() && cluelessAboutNonNullness(); + } + + /** + * 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 cluelessAboutNonNullness() { + return !atNonNull() && !atInstanceOf(); + } + + /** + * 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 (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) + * <code>trackIO(ResolvedJavaType, GuardingNode)</code>} 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(); + 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 + * conforming to the provided type. In case instanceof was observed, + * {@link #trackIO(com.oracle.graal.api.meta.ResolvedJavaType, com.oracle.graal.nodes.extended.GuardingNode) + * <code>trackIO(ResolvedJavaType, GuardingNode)</code>} 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(); + 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; + } + + // umbrella type over the observations from both witnesses + ResolvedJavaType newSeen = (seen == null || that.seen == null) ? null : FlowUtil.widen(seen, that.seen); + + // preserve guarding node only if matches other, otherwise settle on `merge` + final GuardingNode resultGuard = guard() == that.guard() ? guard() : merge; + + /* + * 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(); + } + +}
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCacheImpl.java Fri Apr 25 16:45:05 2014 +0200 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/TruffleCacheImpl.java Fri Apr 25 16:50:52 2014 +0200 @@ -43,6 +43,7 @@ import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase; import com.oracle.graal.phases.tiers.*; import com.oracle.graal.phases.util.*; import com.oracle.graal.truffle.phases.*; @@ -163,8 +164,8 @@ partialEscapePhase.apply(graph, phaseContext); // Conditional elimination. - ConditionalEliminationPhase conditionalEliminationPhase = new ConditionalEliminationPhase(phaseContext.getMetaAccess()); - conditionalEliminationPhase.apply(graph); + FlowSensitiveReductionPhase flowSensitiveReductionPhase = new FlowSensitiveReductionPhase(phaseContext.getMetaAccess()); + flowSensitiveReductionPhase.apply(graph, phaseContext); // Canonicalize / constant propagate. canonicalizerPhase.apply(graph, phaseContext);
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/IterativeInliningPhase.java Fri Apr 25 16:45:05 2014 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/IterativeInliningPhase.java Fri Apr 25 16:50:52 2014 +0200 @@ -31,6 +31,7 @@ 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.IterativeFlowSensitiveReductionPhase; import com.oracle.graal.phases.tiers.*; public class IterativeInliningPhase extends AbstractInliningPhase { @@ -72,7 +73,7 @@ if (ConditionalElimination.getValue() && OptCanonicalizer.getValue()) { canonicalizer.apply(graph, context); - new IterativeConditionalEliminationPhase(canonicalizer).apply(graph, context); + new IterativeFlowSensitiveReductionPhase(canonicalizer).apply(graph, context); } if (!progress) { break;