hotspot/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.phases.common/src/org/graalvm/compiler/phases/common/CanonicalizerPhase.java
changeset 43972 1ade39b8381b
child 46344 694c102fd8ed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.phases.common/src/org/graalvm/compiler/phases/common/CanonicalizerPhase.java	Thu Feb 16 15:46:09 2017 -0800
@@ -0,0 +1,508 @@
+/*
+ * Copyright (c) 2011, 2016, 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 org.graalvm.compiler.phases.common;
+
+import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
+import org.graalvm.compiler.debug.Debug;
+import org.graalvm.compiler.debug.DebugCloseable;
+import org.graalvm.compiler.debug.DebugCounter;
+import org.graalvm.compiler.graph.Graph;
+import org.graalvm.compiler.graph.Graph.Mark;
+import org.graalvm.compiler.graph.Graph.NodeEventListener;
+import org.graalvm.compiler.graph.Graph.NodeEventScope;
+import org.graalvm.compiler.graph.Node;
+import org.graalvm.compiler.graph.Node.IndirectCanonicalization;
+import org.graalvm.compiler.graph.NodeClass;
+import org.graalvm.compiler.graph.NodeWorkList;
+import org.graalvm.compiler.graph.spi.Canonicalizable;
+import org.graalvm.compiler.graph.spi.Canonicalizable.BinaryCommutative;
+import org.graalvm.compiler.graph.spi.SimplifierTool;
+import org.graalvm.compiler.nodeinfo.InputType;
+import org.graalvm.compiler.nodes.AbstractMergeNode;
+import org.graalvm.compiler.nodes.ConstantNode;
+import org.graalvm.compiler.nodes.ControlSinkNode;
+import org.graalvm.compiler.nodes.FixedNode;
+import org.graalvm.compiler.nodes.FixedWithNextNode;
+import org.graalvm.compiler.nodes.StartNode;
+import org.graalvm.compiler.nodes.StructuredGraph;
+import org.graalvm.compiler.nodes.ValueNode;
+import org.graalvm.compiler.nodes.calc.FloatingNode;
+import org.graalvm.compiler.nodes.util.GraphUtil;
+import org.graalvm.compiler.phases.BasePhase;
+import org.graalvm.compiler.phases.Phase;
+import org.graalvm.compiler.phases.tiers.PhaseContext;
+
+import jdk.vm.ci.meta.Assumptions;
+import jdk.vm.ci.meta.Constant;
+import jdk.vm.ci.meta.ConstantReflectionProvider;
+import jdk.vm.ci.meta.MetaAccessProvider;
+
+public class CanonicalizerPhase extends BasePhase<PhaseContext> {
+
+    private static final int MAX_ITERATION_PER_NODE = 10;
+    private static final DebugCounter COUNTER_CANONICALIZED_NODES = Debug.counter("CanonicalizedNodes");
+    private static final DebugCounter COUNTER_PROCESSED_NODES = Debug.counter("ProcessedNodes");
+    private static final DebugCounter COUNTER_CANONICALIZATION_CONSIDERED_NODES = Debug.counter("CanonicalizationConsideredNodes");
+    private static final DebugCounter COUNTER_INFER_STAMP_CALLED = Debug.counter("InferStampCalled");
+    private static final DebugCounter COUNTER_STAMP_CHANGED = Debug.counter("StampChanged");
+    private static final DebugCounter COUNTER_SIMPLIFICATION_CONSIDERED_NODES = Debug.counter("SimplificationConsideredNodes");
+    private static final DebugCounter COUNTER_GLOBAL_VALUE_NUMBERING_HITS = Debug.counter("GlobalValueNumberingHits");
+
+    private boolean canonicalizeReads = true;
+    private boolean simplify = true;
+    private final CustomCanonicalizer customCanonicalizer;
+
+    public abstract static class CustomCanonicalizer {
+
+        public Node canonicalize(Node node) {
+            return node;
+        }
+
+        @SuppressWarnings("unused")
+        public void simplify(Node node, SimplifierTool tool) {
+        }
+    }
+
+    public CanonicalizerPhase() {
+        this(null);
+    }
+
+    public CanonicalizerPhase(CustomCanonicalizer customCanonicalizer) {
+        this.customCanonicalizer = customCanonicalizer;
+    }
+
+    public void disableReadCanonicalization() {
+        canonicalizeReads = false;
+    }
+
+    public void disableSimplification() {
+        simplify = false;
+    }
+
+    @Override
+    public boolean checkContract() {
+        /*
+         * There are certain canonicalizations we make that heavily increase code size by e.g.
+         * replacing a merge followed by a return of the merge's phi with returns in each
+         * predecessor.
+         */
+        return false;
+    }
+
+    @Override
+    protected void run(StructuredGraph graph, PhaseContext context) {
+        new Instance(context).run(graph);
+    }
+
+    /**
+     * @param newNodesMark only the {@linkplain Graph#getNewNodes(Mark) new nodes} specified by this
+     *            mark are processed
+     */
+    public void applyIncremental(StructuredGraph graph, PhaseContext context, Mark newNodesMark) {
+        applyIncremental(graph, context, newNodesMark, true);
+    }
+
+    public void applyIncremental(StructuredGraph graph, PhaseContext context, Mark newNodesMark, boolean dumpGraph) {
+        new Instance(context, newNodesMark).apply(graph, dumpGraph);
+    }
+
+    /**
+     * @param workingSet the initial working set of nodes on which the canonicalizer works, should
+     *            be an auto-grow node bitmap
+     */
+    public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet) {
+        applyIncremental(graph, context, workingSet, true);
+    }
+
+    public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet, boolean dumpGraph) {
+        new Instance(context, workingSet).apply(graph, dumpGraph);
+    }
+
+    public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet, Mark newNodesMark) {
+        applyIncremental(graph, context, workingSet, newNodesMark, true);
+    }
+
+    public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet, Mark newNodesMark, boolean dumpGraph) {
+        new Instance(context, workingSet, newNodesMark).apply(graph, dumpGraph);
+    }
+
+    private final class Instance extends Phase {
+
+        private final Mark newNodesMark;
+        private final PhaseContext context;
+        private final Iterable<? extends Node> initWorkingSet;
+
+        private NodeWorkList workList;
+        private Tool tool;
+
+        private Instance(PhaseContext context) {
+            this(context, null, null);
+        }
+
+        private Instance(PhaseContext context, Iterable<? extends Node> workingSet) {
+            this(context, workingSet, null);
+        }
+
+        private Instance(PhaseContext context, Mark newNodesMark) {
+            this(context, null, newNodesMark);
+        }
+
+        private Instance(PhaseContext context, Iterable<? extends Node> workingSet, Mark newNodesMark) {
+            this.newNodesMark = newNodesMark;
+            this.context = context;
+            this.initWorkingSet = workingSet;
+        }
+
+        @Override
+        protected void run(StructuredGraph graph) {
+            boolean wholeGraph = newNodesMark == null || newNodesMark.isStart();
+            if (initWorkingSet == null) {
+                workList = graph.createIterativeNodeWorkList(wholeGraph, MAX_ITERATION_PER_NODE);
+            } else {
+                workList = graph.createIterativeNodeWorkList(false, MAX_ITERATION_PER_NODE);
+                workList.addAll(initWorkingSet);
+            }
+            if (!wholeGraph) {
+                workList.addAll(graph.getNewNodes(newNodesMark));
+            }
+            tool = new Tool(graph.getAssumptions());
+            processWorkSet(graph);
+        }
+
+        @SuppressWarnings("try")
+        private void processWorkSet(StructuredGraph graph) {
+            NodeEventListener listener = new NodeEventListener() {
+
+                @Override
+                public void nodeAdded(Node node) {
+                    workList.add(node);
+                }
+
+                @Override
+                public void inputChanged(Node node) {
+                    workList.add(node);
+                    if (node instanceof IndirectCanonicalization) {
+                        for (Node usage : node.usages()) {
+                            workList.add(usage);
+                        }
+                    }
+                }
+
+                @Override
+                public void usagesDroppedToZero(Node node) {
+                    workList.add(node);
+                }
+
+            };
+            try (NodeEventScope nes = graph.trackNodeEvents(listener)) {
+                for (Node n : workList) {
+                    boolean changed = processNode(n);
+                    if (changed && Debug.isDumpEnabled(Debug.DETAILED_LOG_LEVEL)) {
+                        Debug.dump(Debug.DETAILED_LOG_LEVEL, graph, "CanonicalizerPhase %s", n);
+                    }
+                }
+            }
+        }
+
+        /**
+         * @return true if the graph was changed.
+         */
+        private boolean processNode(Node node) {
+            if (!node.isAlive()) {
+                return false;
+            }
+            if (node instanceof FloatingNode && node.hasNoUsages()) {
+                // Dead but on the worklist so simply kill it
+                GraphUtil.killWithUnusedFloatingInputs(node);
+                return false;
+            }
+            COUNTER_PROCESSED_NODES.increment();
+
+            NodeClass<?> nodeClass = node.getNodeClass();
+            if (tryGlobalValueNumbering(node, nodeClass)) {
+                return true;
+            }
+            StructuredGraph graph = (StructuredGraph) node.graph();
+            if (GraphUtil.tryKillUnused(node)) {
+                return true;
+            }
+            if (tryCanonicalize(node, nodeClass)) {
+                return true;
+            }
+            if (node instanceof ValueNode) {
+                ValueNode valueNode = (ValueNode) node;
+                boolean improvedStamp = tryInferStamp(valueNode);
+                Constant constant = valueNode.stamp().asConstant();
+                if (constant != null && !(node instanceof ConstantNode)) {
+                    ConstantNode stampConstant = ConstantNode.forConstant(valueNode.stamp(), constant, context.getMetaAccess(), graph);
+                    Debug.log("Canonicalizer: constant stamp replaces %1s with %1s", valueNode, stampConstant);
+                    valueNode.replaceAtUsages(InputType.Value, stampConstant);
+                    GraphUtil.tryKillUnused(valueNode);
+                    return true;
+                } else if (improvedStamp) {
+                    // the improved stamp may enable additional canonicalization
+                    if (tryCanonicalize(valueNode, nodeClass)) {
+                        return true;
+                    }
+                    valueNode.usages().forEach(workList::add);
+                }
+            }
+            return false;
+        }
+
+        public boolean tryGlobalValueNumbering(Node node, NodeClass<?> nodeClass) {
+            if (nodeClass.valueNumberable()) {
+                Node newNode = node.graph().findDuplicate(node);
+                if (newNode != null) {
+                    assert !(node instanceof FixedNode || newNode instanceof FixedNode);
+                    node.replaceAtUsagesAndDelete(newNode);
+                    COUNTER_GLOBAL_VALUE_NUMBERING_HITS.increment();
+                    Debug.log("GVN applied and new node is %1s", newNode);
+                    return true;
+                }
+            }
+            return false;
+        }
+
+        private AutoCloseable getCanonicalizeableContractAssertion(Node node) {
+            boolean needsAssertion = false;
+            assert (needsAssertion = true) == true;
+            if (needsAssertion) {
+                Mark mark = node.graph().getMark();
+                return () -> {
+                    assert mark.equals(node.graph().getMark()) : "new node created while canonicalizing " + node.getClass().getSimpleName() + " " + node + ": " +
+                                    node.graph().getNewNodes(mark).snapshot();
+                };
+            } else {
+                return null;
+            }
+        }
+
+        @SuppressWarnings("try")
+        public boolean tryCanonicalize(final Node node, NodeClass<?> nodeClass) {
+            try (DebugCloseable position = node.withNodeSourcePosition()) {
+                if (customCanonicalizer != null) {
+                    Node canonical = customCanonicalizer.canonicalize(node);
+                    if (performReplacement(node, canonical)) {
+                        return true;
+                    } else {
+                        customCanonicalizer.simplify(node, tool);
+                        if (node.isDeleted()) {
+                            return true;
+                        }
+                    }
+                }
+                if (nodeClass.isCanonicalizable()) {
+                    COUNTER_CANONICALIZATION_CONSIDERED_NODES.increment();
+                    Node canonical;
+                    try (AutoCloseable verify = getCanonicalizeableContractAssertion(node)) {
+                        canonical = ((Canonicalizable) node).canonical(tool);
+                        if (canonical == node && nodeClass.isCommutative()) {
+                            canonical = ((BinaryCommutative<?>) node).maybeCommuteInputs();
+                        }
+                    } catch (Throwable e) {
+                        throw new RuntimeException(e);
+                    }
+                    if (performReplacement(node, canonical)) {
+                        return true;
+                    }
+                }
+
+                if (nodeClass.isSimplifiable() && simplify) {
+                    Debug.log(Debug.VERBOSE_LOG_LEVEL, "Canonicalizer: simplifying %s", node);
+                    COUNTER_SIMPLIFICATION_CONSIDERED_NODES.increment();
+                    node.simplify(tool);
+                    return node.isDeleted();
+                }
+                return false;
+            }
+        }
+
+// @formatter:off
+//     cases:                                           original node:
+//                                         |Floating|Fixed-unconnected|Fixed-connected|
+//                                         --------------------------------------------
+//                                     null|   1    |        X        |       3       |
+//                                         --------------------------------------------
+//                                 Floating|   2    |        X        |       4       |
+//       canonical node:                   --------------------------------------------
+//                        Fixed-unconnected|   X    |        X        |       5       |
+//                                         --------------------------------------------
+//                          Fixed-connected|   2    |        X        |       6       |
+//                                         --------------------------------------------
+//                              ControlSink|   X    |        X        |       7       |
+//                                         --------------------------------------------
+//       X: must not happen (checked with assertions)
+// @formatter:on
+        private boolean performReplacement(final Node node, Node newCanonical) {
+            if (newCanonical == node) {
+                Debug.log(Debug.VERBOSE_LOG_LEVEL, "Canonicalizer: work on %1s", node);
+                return false;
+            } else {
+                Node canonical = newCanonical;
+                Debug.log("Canonicalizer: replacing %1s with %1s", node, canonical);
+                COUNTER_CANONICALIZED_NODES.increment();
+                StructuredGraph graph = (StructuredGraph) node.graph();
+                if (canonical != null && !canonical.isAlive()) {
+                    assert !canonical.isDeleted();
+                    canonical = graph.addOrUniqueWithInputs(canonical);
+                }
+                if (node instanceof FloatingNode) {
+                    assert canonical == null || !(canonical instanceof FixedNode) ||
+                                    (canonical.predecessor() != null || canonical instanceof StartNode || canonical instanceof AbstractMergeNode) : node +
+                                                    " -> " + canonical + " : replacement should be floating or fixed and connected";
+                    node.replaceAtUsages(canonical);
+                    GraphUtil.killWithUnusedFloatingInputs(node);
+                } else {
+                    assert node instanceof FixedNode && node.predecessor() != null : node + " -> " + canonical + " : node should be fixed & connected (" + node.predecessor() + ")";
+                    FixedNode fixed = (FixedNode) node;
+                    if (canonical instanceof ControlSinkNode) {
+                        // case 7
+                        fixed.replaceAtPredecessor(canonical);
+                        GraphUtil.killCFG(fixed);
+                        return true;
+                    } else {
+                        assert fixed instanceof FixedWithNextNode;
+                        FixedWithNextNode fixedWithNext = (FixedWithNextNode) fixed;
+                        // When removing a fixed node, new canonicalization
+                        // opportunities for its successor may arise
+                        assert fixedWithNext.next() != null;
+                        tool.addToWorkList(fixedWithNext.next());
+                        if (canonical == null) {
+                            // case 3
+                            node.replaceAtUsages(null);
+                            GraphUtil.removeFixedWithUnusedInputs(fixedWithNext);
+                        } else if (canonical instanceof FloatingNode) {
+                            // case 4
+                            graph.replaceFixedWithFloating(fixedWithNext, (FloatingNode) canonical);
+                        } else {
+                            assert canonical instanceof FixedNode;
+                            if (canonical.predecessor() == null) {
+                                assert !canonical.cfgSuccessors().iterator().hasNext() : "replacement " + canonical + " shouldn't have successors";
+                                // case 5
+                                graph.replaceFixedWithFixed(fixedWithNext, (FixedWithNextNode) canonical);
+                            } else {
+                                assert canonical.cfgSuccessors().iterator().hasNext() : "replacement " + canonical + " should have successors";
+                                // case 6
+                                node.replaceAtUsages(canonical);
+                                GraphUtil.removeFixedWithUnusedInputs(fixedWithNext);
+                            }
+                        }
+                    }
+                }
+                return true;
+            }
+        }
+
+        /**
+         * Calls {@link ValueNode#inferStamp()} on the node and, if it returns true (which means
+         * that the stamp has changed), re-queues the node's usages. If the stamp has changed then
+         * this method also checks if the stamp now describes a constant integer value, in which
+         * case the node is replaced with a constant.
+         */
+        private boolean tryInferStamp(ValueNode node) {
+            if (node.isAlive()) {
+                COUNTER_INFER_STAMP_CALLED.increment();
+                if (node.inferStamp()) {
+                    COUNTER_STAMP_CHANGED.increment();
+                    for (Node usage : node.usages()) {
+                        workList.add(usage);
+                    }
+                    return true;
+                }
+            }
+            return false;
+        }
+
+        private final class Tool implements SimplifierTool {
+
+            private final Assumptions assumptions;
+
+            Tool(Assumptions assumptions) {
+                this.assumptions = assumptions;
+            }
+
+            @Override
+            public void deleteBranch(Node branch) {
+                FixedNode fixedBranch = (FixedNode) branch;
+                fixedBranch.predecessor().replaceFirstSuccessor(fixedBranch, null);
+                GraphUtil.killCFG(fixedBranch, this);
+            }
+
+            @Override
+            public MetaAccessProvider getMetaAccess() {
+                return context.getMetaAccess();
+            }
+
+            @Override
+            public ConstantReflectionProvider getConstantReflection() {
+                return context.getConstantReflection();
+            }
+
+            @Override
+            public ConstantFieldProvider getConstantFieldProvider() {
+                return context.getConstantFieldProvider();
+            }
+
+            @Override
+            public void addToWorkList(Node node) {
+                workList.add(node);
+            }
+
+            @Override
+            public void addToWorkList(Iterable<? extends Node> nodes) {
+                workList.addAll(nodes);
+            }
+
+            @Override
+            public void removeIfUnused(Node node) {
+                GraphUtil.tryKillUnused(node);
+            }
+
+            @Override
+            public boolean canonicalizeReads() {
+                return canonicalizeReads;
+            }
+
+            @Override
+            public boolean allUsagesAvailable() {
+                return true;
+            }
+
+            @Override
+            public Assumptions getAssumptions() {
+                return assumptions;
+            }
+
+            @Override
+            public boolean supportSubwordCompare(int bits) {
+                return context.getLowerer().supportSubwordCompare(bits);
+            }
+        }
+    }
+
+    public boolean getCanonicalizeReads() {
+        return canonicalizeReads;
+    }
+
+}