Source code

001/*
002 * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.phases.common;
024
025import com.oracle.graal.debug.*;
026import jdk.internal.jvmci.meta.*;
027
028import com.oracle.graal.graph.*;
029import com.oracle.graal.graph.Graph.Mark;
030import com.oracle.graal.graph.Graph.NodeEventListener;
031import com.oracle.graal.graph.Graph.NodeEventScope;
032import com.oracle.graal.graph.spi.*;
033import com.oracle.graal.graph.spi.Canonicalizable.BinaryCommutative;
034import com.oracle.graal.nodeinfo.*;
035import com.oracle.graal.nodes.*;
036import com.oracle.graal.nodes.calc.*;
037import com.oracle.graal.nodes.util.*;
038import com.oracle.graal.phases.*;
039import com.oracle.graal.phases.tiers.*;
040
041public class CanonicalizerPhase extends BasePhase<PhaseContext> {
042
043    private static final int MAX_ITERATION_PER_NODE = 10;
044    private static final DebugMetric METRIC_CANONICALIZED_NODES = Debug.metric("CanonicalizedNodes");
045    private static final DebugMetric METRIC_PROCESSED_NODES = Debug.metric("ProcessedNodes");
046    private static final DebugMetric METRIC_CANONICALIZATION_CONSIDERED_NODES = Debug.metric("CanonicalizationConsideredNodes");
047    private static final DebugMetric METRIC_INFER_STAMP_CALLED = Debug.metric("InferStampCalled");
048    private static final DebugMetric METRIC_STAMP_CHANGED = Debug.metric("StampChanged");
049    private static final DebugMetric METRIC_SIMPLIFICATION_CONSIDERED_NODES = Debug.metric("SimplificationConsideredNodes");
050    private static final DebugMetric METRIC_GLOBAL_VALUE_NUMBERING_HITS = Debug.metric("GlobalValueNumberingHits");
051
052    private boolean canonicalizeReads = true;
053    private boolean simplify = true;
054    private final CustomCanonicalizer customCanonicalizer;
055
056    public abstract static class CustomCanonicalizer {
057
058        public Node canonicalize(Node node) {
059            return node;
060        }
061
062        @SuppressWarnings("unused")
063        public void simplify(Node node, SimplifierTool tool) {
064        }
065    }
066
067    public CanonicalizerPhase() {
068        this(null);
069    }
070
071    public CanonicalizerPhase(CustomCanonicalizer customCanonicalizer) {
072        this.customCanonicalizer = customCanonicalizer;
073    }
074
075    public void disableReadCanonicalization() {
076        canonicalizeReads = false;
077    }
078
079    public void disableSimplification() {
080        simplify = false;
081    }
082
083    @Override
084    protected void run(StructuredGraph graph, PhaseContext context) {
085        new Instance(context).run(graph);
086    }
087
088    /**
089     * @param newNodesMark only the {@linkplain Graph#getNewNodes(Mark) new nodes} specified by this
090     *            mark are processed
091     */
092    public void applyIncremental(StructuredGraph graph, PhaseContext context, Mark newNodesMark) {
093        applyIncremental(graph, context, newNodesMark, true);
094    }
095
096    public void applyIncremental(StructuredGraph graph, PhaseContext context, Mark newNodesMark, boolean dumpGraph) {
097        new Instance(context, newNodesMark).apply(graph, dumpGraph);
098    }
099
100    /**
101     * @param workingSet the initial working set of nodes on which the canonicalizer works, should
102     *            be an auto-grow node bitmap
103     */
104    public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet) {
105        applyIncremental(graph, context, workingSet, true);
106    }
107
108    public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet, boolean dumpGraph) {
109        new Instance(context, workingSet).apply(graph, dumpGraph);
110    }
111
112    public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet, Mark newNodesMark) {
113        applyIncremental(graph, context, workingSet, newNodesMark, true);
114    }
115
116    public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet, Mark newNodesMark, boolean dumpGraph) {
117        new Instance(context, workingSet, newNodesMark).apply(graph, dumpGraph);
118    }
119
120    private final class Instance extends Phase {
121
122        private final Mark newNodesMark;
123        private final PhaseContext context;
124        private final Iterable<? extends Node> initWorkingSet;
125
126        private NodeWorkList workList;
127        private Tool tool;
128
129        private Instance(PhaseContext context) {
130            this(context, null, null);
131        }
132
133        private Instance(PhaseContext context, Iterable<? extends Node> workingSet) {
134            this(context, workingSet, null);
135        }
136
137        private Instance(PhaseContext context, Mark newNodesMark) {
138            this(context, null, newNodesMark);
139        }
140
141        private Instance(PhaseContext context, Iterable<? extends Node> workingSet, Mark newNodesMark) {
142            super("Canonicalizer");
143            this.newNodesMark = newNodesMark;
144            this.context = context;
145            this.initWorkingSet = workingSet;
146        }
147
148        @Override
149        protected void run(StructuredGraph graph) {
150            boolean wholeGraph = newNodesMark == null || newNodesMark.isStart();
151            if (initWorkingSet == null) {
152                workList = graph.createIterativeNodeWorkList(wholeGraph, MAX_ITERATION_PER_NODE);
153            } else {
154                workList = graph.createIterativeNodeWorkList(false, MAX_ITERATION_PER_NODE);
155                workList.addAll(initWorkingSet);
156            }
157            if (!wholeGraph) {
158                workList.addAll(graph.getNewNodes(newNodesMark));
159            }
160            tool = new Tool();
161            processWorkSet(graph);
162        }
163
164        private void processWorkSet(StructuredGraph graph) {
165            NodeEventListener listener = new NodeEventListener() {
166
167                public void nodeAdded(Node node) {
168                    workList.add(node);
169                }
170
171                public void inputChanged(Node node) {
172                    workList.add(node);
173                }
174
175                public void usagesDroppedToZero(Node node) {
176                    workList.add(node);
177                }
178
179            };
180            try (NodeEventScope nes = graph.trackNodeEvents(listener)) {
181                for (Node n : workList) {
182                    processNode(n);
183                }
184            }
185        }
186
187        private void processNode(Node node) {
188            if (node.isAlive()) {
189                METRIC_PROCESSED_NODES.increment();
190
191                NodeClass<?> nodeClass = node.getNodeClass();
192                if (tryGlobalValueNumbering(node, nodeClass)) {
193                    return;
194                }
195                StructuredGraph graph = (StructuredGraph) node.graph();
196                if (!GraphUtil.tryKillUnused(node)) {
197                    if (!tryCanonicalize(node, nodeClass)) {
198                        if (node instanceof ValueNode) {
199                            ValueNode valueNode = (ValueNode) node;
200                            boolean improvedStamp = tryInferStamp(valueNode);
201                            Constant constant = valueNode.stamp().asConstant();
202                            if (constant != null && !(node instanceof ConstantNode)) {
203                                valueNode.replaceAtUsages(InputType.Value, ConstantNode.forConstant(valueNode.stamp(), constant, context.getMetaAccess(), graph));
204                                GraphUtil.tryKillUnused(valueNode);
205                            } else if (improvedStamp) {
206                                // the improved stamp may enable additional canonicalization
207                                if (!tryCanonicalize(valueNode, nodeClass)) {
208                                    valueNode.usages().forEach(workList::add);
209                                }
210                            }
211                        }
212                    }
213                }
214            }
215        }
216
217        public boolean tryGlobalValueNumbering(Node node, NodeClass<?> nodeClass) {
218            if (nodeClass.valueNumberable() && !nodeClass.isLeafNode()) {
219                Node newNode = node.graph().findDuplicate(node);
220                if (newNode != null) {
221                    assert !(node instanceof FixedNode || newNode instanceof FixedNode);
222                    node.replaceAtUsages(newNode);
223                    node.safeDelete();
224                    METRIC_GLOBAL_VALUE_NUMBERING_HITS.increment();
225                    Debug.log("GVN applied and new node is %1s", newNode);
226                    return true;
227                }
228            }
229            return false;
230        }
231
232        private AutoCloseable getCanonicalizeableContractAssertion(Node node) {
233            boolean needsAssertion = false;
234            assert (needsAssertion = true) == true;
235            if (needsAssertion) {
236                Mark mark = node.graph().getMark();
237                return () -> {
238                    assert mark.equals(node.graph().getMark()) : "new node created while canonicalizing " + node.getClass().getSimpleName() + " " + node + ": " +
239                                    node.graph().getNewNodes(mark).snapshot();
240                };
241            } else {
242                return null;
243            }
244        }
245
246        public boolean tryCanonicalize(final Node node, NodeClass<?> nodeClass) {
247            if (customCanonicalizer != null) {
248                Node canonical = customCanonicalizer.canonicalize(node);
249                if (performReplacement(node, canonical)) {
250                    return true;
251                } else {
252                    customCanonicalizer.simplify(node, tool);
253                    if (node.isDeleted()) {
254                        return true;
255                    }
256                }
257            }
258            if (nodeClass.isCanonicalizable()) {
259                METRIC_CANONICALIZATION_CONSIDERED_NODES.increment();
260                Node canonical;
261                try (AutoCloseable verify = getCanonicalizeableContractAssertion(node)) {
262                    canonical = ((Canonicalizable) node).canonical(tool);
263                    if (canonical == node && nodeClass.isCommutative()) {
264                        canonical = ((BinaryCommutative<?>) node).maybeCommuteInputs();
265                    }
266                } catch (Throwable e) {
267                    throw new RuntimeException(e);
268                }
269                if (performReplacement(node, canonical)) {
270                    return true;
271                }
272            }
273
274            if (nodeClass.isSimplifiable() && simplify) {
275                Debug.log(3, "Canonicalizer: simplifying %s", node);
276                METRIC_SIMPLIFICATION_CONSIDERED_NODES.increment();
277                node.simplify(tool);
278                return node.isDeleted();
279            }
280            return false;
281        }
282
283// @formatter:off
284//     cases:                                           original node:
285//                                         |Floating|Fixed-unconnected|Fixed-connected|
286//                                         --------------------------------------------
287//                                     null|   1    |        X        |       3       |
288//                                         --------------------------------------------
289//                                 Floating|   2    |        X        |       4       |
290//       canonical node:                   --------------------------------------------
291//                        Fixed-unconnected|   X    |        X        |       5       |
292//                                         --------------------------------------------
293//                          Fixed-connected|   2    |        X        |       6       |
294//                                         --------------------------------------------
295//                              ControlSink|   X    |        X        |       7       |
296//                                         --------------------------------------------
297//       X: must not happen (checked with assertions)
298// @formatter:on
299        private boolean performReplacement(final Node node, Node newCanonical) {
300            if (newCanonical == node) {
301                Debug.log(3, "Canonicalizer: work on %1s", node);
302                return false;
303            } else {
304                Node canonical = newCanonical;
305                Debug.log("Canonicalizer: replacing %1s with %1s", node, canonical);
306                METRIC_CANONICALIZED_NODES.increment();
307                StructuredGraph graph = (StructuredGraph) node.graph();
308                if (canonical != null && !canonical.isAlive()) {
309                    assert !canonical.isDeleted();
310                    canonical = graph.addOrUniqueWithInputs(canonical);
311                }
312                if (node instanceof FloatingNode) {
313                    if (canonical == null) {
314                        // case 1
315                        node.replaceAtUsages(null);
316                        graph.removeFloating((FloatingNode) node);
317                    } else {
318                        // case 2
319                        assert !(canonical instanceof FixedNode) || (canonical.predecessor() != null || canonical instanceof StartNode || canonical instanceof AbstractMergeNode) : node + " -> " +
320                                        canonical + " : replacement should be floating or fixed and connected";
321                        graph.replaceFloating((FloatingNode) node, canonical);
322                    }
323                } else {
324                    assert node instanceof FixedNode && node.predecessor() != null : node + " -> " + canonical + " : node should be fixed & connected (" + node.predecessor() + ")";
325                    FixedNode fixed = (FixedNode) node;
326                    if (canonical instanceof ControlSinkNode) {
327                        // case 7
328                        fixed.replaceAtPredecessor(canonical);
329                        GraphUtil.killCFG(fixed);
330                        return true;
331                    } else {
332                        assert fixed instanceof FixedWithNextNode;
333                        FixedWithNextNode fixedWithNext = (FixedWithNextNode) fixed;
334                        // When removing a fixed node, new canonicalization
335                        // opportunities for its successor may arise
336                        assert fixedWithNext.next() != null;
337                        tool.addToWorkList(fixedWithNext.next());
338                        if (canonical == null) {
339                            // case 3
340                            node.replaceAtUsages(null);
341                            graph.removeFixed(fixedWithNext);
342                        } else if (canonical instanceof FloatingNode) {
343                            // case 4
344                            graph.replaceFixedWithFloating(fixedWithNext, (FloatingNode) canonical);
345                        } else {
346                            assert canonical instanceof FixedNode;
347                            if (canonical.predecessor() == null) {
348                                assert !canonical.cfgSuccessors().iterator().hasNext() : "replacement " + canonical + " shouldn't have successors";
349                                // case 5
350                                graph.replaceFixedWithFixed(fixedWithNext, (FixedWithNextNode) canonical);
351                            } else {
352                                assert canonical.cfgSuccessors().iterator().hasNext() : "replacement " + canonical + " should have successors";
353                                // case 6
354                                node.replaceAtUsages(canonical);
355                                graph.removeFixed(fixedWithNext);
356                            }
357                        }
358                    }
359                }
360                return true;
361            }
362        }
363
364        /**
365         * Calls {@link ValueNode#inferStamp()} on the node and, if it returns true (which means
366         * that the stamp has changed), re-queues the node's usages. If the stamp has changed then
367         * this method also checks if the stamp now describes a constant integer value, in which
368         * case the node is replaced with a constant.
369         */
370        private boolean tryInferStamp(ValueNode node) {
371            if (node.isAlive()) {
372                METRIC_INFER_STAMP_CALLED.increment();
373                if (node.inferStamp()) {
374                    METRIC_STAMP_CHANGED.increment();
375                    for (Node usage : node.usages()) {
376                        workList.add(usage);
377                    }
378                    return true;
379                }
380            }
381            return false;
382        }
383
384        private final class Tool implements SimplifierTool {
385
386            @Override
387            public void deleteBranch(Node branch) {
388                branch.predecessor().replaceFirstSuccessor(branch, null);
389                GraphUtil.killCFG(branch, this);
390            }
391
392            @Override
393            public MetaAccessProvider getMetaAccess() {
394                return context.getMetaAccess();
395            }
396
397            @Override
398            public ConstantReflectionProvider getConstantReflection() {
399                return context.getConstantReflection();
400            }
401
402            @Override
403            public void addToWorkList(Node node) {
404                workList.add(node);
405            }
406
407            public void addToWorkList(Iterable<? extends Node> nodes) {
408                workList.addAll(nodes);
409            }
410
411            @Override
412            public void removeIfUnused(Node node) {
413                GraphUtil.tryKillUnused(node);
414            }
415
416            @Override
417            public boolean canonicalizeReads() {
418                return canonicalizeReads;
419            }
420
421            @Override
422            public boolean allUsagesAvailable() {
423                return true;
424            }
425        }
426    }
427
428    public boolean getCanonicalizeReads() {
429        return canonicalizeReads;
430    }
431}