1 /*
2 * Copyright (c) 2011, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.phases.common;
26
27 import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
28 import org.graalvm.compiler.core.common.type.Stamp;
29 import org.graalvm.compiler.debug.CounterKey;
30 import org.graalvm.compiler.debug.DebugCloseable;
31 import org.graalvm.compiler.debug.DebugContext;
32 import org.graalvm.compiler.graph.GraalGraphError;
33 import org.graalvm.compiler.graph.Graph;
34 import org.graalvm.compiler.graph.Graph.Mark;
35 import org.graalvm.compiler.graph.Graph.NodeEventListener;
36 import org.graalvm.compiler.graph.Graph.NodeEventScope;
37 import org.graalvm.compiler.graph.Node;
38 import org.graalvm.compiler.graph.Node.IndirectCanonicalization;
39 import org.graalvm.compiler.graph.NodeClass;
40 import org.graalvm.compiler.graph.NodeWorkList;
41 import org.graalvm.compiler.graph.spi.Canonicalizable;
42 import org.graalvm.compiler.graph.spi.Canonicalizable.BinaryCommutative;
43 import org.graalvm.compiler.graph.spi.SimplifierTool;
44 import org.graalvm.compiler.nodeinfo.InputType;
45 import org.graalvm.compiler.nodes.AbstractBeginNode;
46 import org.graalvm.compiler.nodes.AbstractMergeNode;
47 import org.graalvm.compiler.nodes.ConstantNode;
48 import org.graalvm.compiler.nodes.ControlSinkNode;
49 import org.graalvm.compiler.nodes.FixedNode;
50 import org.graalvm.compiler.nodes.FixedWithNextNode;
51 import org.graalvm.compiler.nodes.NodeView;
52 import org.graalvm.compiler.nodes.StartNode;
53 import org.graalvm.compiler.nodes.StructuredGraph;
54 import org.graalvm.compiler.nodes.ValueNode;
55 import org.graalvm.compiler.nodes.calc.FloatingNode;
56 import org.graalvm.compiler.nodes.spi.CoreProviders;
57 import org.graalvm.compiler.nodes.util.GraphUtil;
58 import org.graalvm.compiler.options.OptionValues;
59 import org.graalvm.compiler.phases.BasePhase;
60 import org.graalvm.compiler.phases.Phase;
61
62 import jdk.vm.ci.meta.Assumptions;
63 import jdk.vm.ci.meta.Constant;
64 import jdk.vm.ci.meta.ConstantReflectionProvider;
65 import jdk.vm.ci.meta.MetaAccessProvider;
66
67 public class CanonicalizerPhase extends BasePhase<CoreProviders> {
68
69 private static final int MAX_ITERATION_PER_NODE = 10;
70 private static final CounterKey COUNTER_CANONICALIZED_NODES = DebugContext.counter("CanonicalizedNodes");
71 private static final CounterKey COUNTER_PROCESSED_NODES = DebugContext.counter("ProcessedNodes");
72 private static final CounterKey COUNTER_CANONICALIZATION_CONSIDERED_NODES = DebugContext.counter("CanonicalizationConsideredNodes");
73 private static final CounterKey COUNTER_INFER_STAMP_CALLED = DebugContext.counter("InferStampCalled");
74 private static final CounterKey COUNTER_STAMP_CHANGED = DebugContext.counter("StampChanged");
75 private static final CounterKey COUNTER_SIMPLIFICATION_CONSIDERED_NODES = DebugContext.counter("SimplificationConsideredNodes");
76 private static final CounterKey COUNTER_GLOBAL_VALUE_NUMBERING_HITS = DebugContext.counter("GlobalValueNumberingHits");
77
78 private boolean globalValueNumber = true;
79 private boolean canonicalizeReads = true;
80 private boolean simplify = true;
81 private final CustomCanonicalizer customCanonicalizer;
82
83 public abstract static class CustomCanonicalizer {
84
85 public Node canonicalize(Node node) {
86 return node;
87 }
88
89 @SuppressWarnings("unused")
90 public void simplify(Node node, SimplifierTool tool) {
91 }
92 }
93
94 public CanonicalizerPhase() {
95 this(null);
96 }
97
98 public CanonicalizerPhase(CustomCanonicalizer customCanonicalizer) {
99 this.customCanonicalizer = customCanonicalizer;
100 }
101
102 public void disableGVN() {
103 globalValueNumber = false;
104 }
105
106 public void disableReadCanonicalization() {
107 canonicalizeReads = false;
108 }
109
110 public void disableSimplification() {
111 simplify = false;
112 }
113
114 @Override
115 public boolean checkContract() {
116 /*
117 * There are certain canonicalizations we make that heavily increase code size by e.g.
118 * replacing a merge followed by a return of the merge's phi with returns in each
119 * predecessor.
120 */
121 return false;
122 }
123
124 @Override
125 protected void run(StructuredGraph graph, CoreProviders context) {
126 new Instance(context).run(graph);
127 }
128
129 /**
130 * @param newNodesMark only the {@linkplain Graph#getNewNodes(Mark) new nodes} specified by this
131 * mark are processed
132 */
133 public void applyIncremental(StructuredGraph graph, CoreProviders context, Mark newNodesMark) {
134 applyIncremental(graph, context, newNodesMark, true);
135 }
136
137 public void applyIncremental(StructuredGraph graph, CoreProviders context, Mark newNodesMark, boolean dumpGraph) {
138 new Instance(context, newNodesMark).apply(graph, dumpGraph);
139 }
140
141 /**
142 * @param workingSet the initial working set of nodes on which the canonicalizer works, should
143 * be an auto-grow node bitmap
144 */
145 public void applyIncremental(StructuredGraph graph, CoreProviders context, Iterable<? extends Node> workingSet) {
146 applyIncremental(graph, context, workingSet, true);
147 }
148
149 public void applyIncremental(StructuredGraph graph, CoreProviders context, Iterable<? extends Node> workingSet, boolean dumpGraph) {
150 new Instance(context, workingSet).apply(graph, dumpGraph);
151 }
152
153 public void applyIncremental(StructuredGraph graph, CoreProviders context, Iterable<? extends Node> workingSet, Mark newNodesMark) {
154 applyIncremental(graph, context, workingSet, newNodesMark, true);
155 }
156
157 public void applyIncremental(StructuredGraph graph, CoreProviders context, Iterable<? extends Node> workingSet, Mark newNodesMark, boolean dumpGraph) {
158 new Instance(context, workingSet, newNodesMark).apply(graph, dumpGraph);
159 }
160
161 public NodeView getNodeView() {
162 return NodeView.DEFAULT;
163 }
164
165 private final class Instance extends Phase {
166
167 private final Mark newNodesMark;
168 private final CoreProviders context;
169 private final Iterable<? extends Node> initWorkingSet;
170
171 private NodeWorkList workList;
172 private Tool tool;
173 private DebugContext debug;
174
175 private Instance(CoreProviders context) {
176 this(context, null, null);
177 }
178
179 private Instance(CoreProviders context, Iterable<? extends Node> workingSet) {
180 this(context, workingSet, null);
181 }
182
183 private Instance(CoreProviders context, Mark newNodesMark) {
184 this(context, null, newNodesMark);
185 }
186
187 private Instance(CoreProviders context, Iterable<? extends Node> workingSet, Mark newNodesMark) {
188 this.newNodesMark = newNodesMark;
189 this.context = context;
190 this.initWorkingSet = workingSet;
191 }
192
193 @Override
194 public boolean checkContract() {
195 return false;
196 }
197
198 @Override
199 protected void run(StructuredGraph graph) {
200 this.debug = graph.getDebug();
201 boolean wholeGraph = newNodesMark == null || newNodesMark.isStart();
202 if (initWorkingSet == null) {
203 workList = graph.createIterativeNodeWorkList(wholeGraph, MAX_ITERATION_PER_NODE);
204 } else {
205 workList = graph.createIterativeNodeWorkList(false, MAX_ITERATION_PER_NODE);
206 workList.addAll(initWorkingSet);
207 }
208 if (!wholeGraph) {
209 workList.addAll(graph.getNewNodes(newNodesMark));
210 }
211
212 tool = new Tool(graph.getAssumptions(), graph.getOptions());
213 processWorkSet(graph);
214 }
215
216 @SuppressWarnings("try")
217 private int processWorkSet(StructuredGraph graph) {
218 int sum = 0;
219 NodeEventListener listener = new NodeEventListener() {
220
221 @Override
222 public void nodeAdded(Node node) {
223 workList.add(node);
224 }
225
226 @Override
227 public void inputChanged(Node node) {
228 workList.add(node);
229 if (node instanceof IndirectCanonicalization) {
230 for (Node usage : node.usages()) {
231 workList.add(usage);
232 }
233 }
234
235 if (node instanceof AbstractBeginNode) {
236 AbstractBeginNode abstractBeginNode = (AbstractBeginNode) node;
237 if (abstractBeginNode.predecessor() != null) {
238 workList.add(abstractBeginNode.predecessor());
239 }
240 }
241 }
242
243 @Override
244 public void usagesDroppedToZero(Node node) {
245 workList.add(node);
246 }
247 };
248
249 try (NodeEventScope nes = graph.trackNodeEvents(listener)) {
250 for (Node n : workList) {
251 boolean changed = processNode(n);
252 if (changed && debug.isDumpEnabled(DebugContext.DETAILED_LEVEL)) {
253 debug.dump(DebugContext.DETAILED_LEVEL, graph, "CanonicalizerPhase %s", n);
254 }
255 ++sum;
256 }
257 }
258 return sum;
259 }
260
261 /**
262 * @return true if the graph was changed.
263 */
264 private boolean processNode(Node node) {
265 if (!node.isAlive()) {
266 return false;
267 }
268 COUNTER_PROCESSED_NODES.increment(debug);
269 if (GraphUtil.tryKillUnused(node)) {
270 return true;
271 }
272 NodeClass<?> nodeClass = node.getNodeClass();
273 StructuredGraph graph = (StructuredGraph) node.graph();
274 if (tryCanonicalize(node, nodeClass)) {
275 return true;
276 }
277 if (globalValueNumber && tryGlobalValueNumbering(node, nodeClass)) {
278 return true;
279 }
280 if (node instanceof ValueNode) {
281 ValueNode valueNode = (ValueNode) node;
282 boolean improvedStamp = tryInferStamp(valueNode);
283 Constant constant = valueNode.stamp(NodeView.DEFAULT).asConstant();
284 if (constant != null && !(node instanceof ConstantNode)) {
285 ConstantNode stampConstant = ConstantNode.forConstant(valueNode.stamp(NodeView.DEFAULT), constant, context.getMetaAccess(), graph);
286 debug.log("Canonicalizer: constant stamp replaces %1s with %1s", valueNode, stampConstant);
287 valueNode.replaceAtUsages(InputType.Value, stampConstant);
288 GraphUtil.tryKillUnused(valueNode);
289 return true;
290 } else if (improvedStamp) {
291 // the improved stamp may enable additional canonicalization
292 if (tryCanonicalize(valueNode, nodeClass)) {
293 return true;
294 }
295 valueNode.usages().forEach(workList::add);
296 }
297 }
298 return false;
299 }
300
301 public boolean tryGlobalValueNumbering(Node node, NodeClass<?> nodeClass) {
302 if (nodeClass.valueNumberable()) {
303 Node newNode = node.graph().findDuplicate(node);
304 if (newNode != null) {
305 assert !(node instanceof FixedNode || newNode instanceof FixedNode);
306 node.replaceAtUsagesAndDelete(newNode);
307 COUNTER_GLOBAL_VALUE_NUMBERING_HITS.increment(debug);
308 debug.log("GVN applied and new node is %1s", newNode);
309 return true;
310 }
311 }
312 return false;
313 }
314
315 private AutoCloseable getCanonicalizeableContractAssertion(Node node) {
316 boolean needsAssertion = false;
317 assert (needsAssertion = true) == true;
318 if (needsAssertion) {
319 Mark mark = node.graph().getMark();
320 return () -> {
321 assert mark.equals(node.graph().getMark()) : "new node created while canonicalizing " + node.getClass().getSimpleName() + " " + node + ": " +
322 node.graph().getNewNodes(mark).snapshot();
323 };
324 } else {
325 return null;
326 }
327 }
328
329 @SuppressWarnings("try")
330 public boolean tryCanonicalize(final Node node, NodeClass<?> nodeClass) {
331 try (DebugCloseable position = node.withNodeSourcePosition(); DebugContext.Scope scope = debug.withContext(node)) {
332 if (customCanonicalizer != null) {
333 Node canonical = customCanonicalizer.canonicalize(node);
334 if (performReplacement(node, canonical)) {
335 return true;
336 } else {
337 customCanonicalizer.simplify(node, tool);
338 if (node.isDeleted()) {
339 return true;
340 }
341 }
342 }
343 if (nodeClass.isCanonicalizable()) {
344 COUNTER_CANONICALIZATION_CONSIDERED_NODES.increment(debug);
345 Node canonical;
346 try (AutoCloseable verify = getCanonicalizeableContractAssertion(node)) {
347 canonical = ((Canonicalizable) node).canonical(tool);
348 if (canonical == node && nodeClass.isCommutative()) {
349 canonical = ((BinaryCommutative<?>) node).maybeCommuteInputs();
350 }
351 } catch (Throwable e) {
352 throw new GraalGraphError(e).addContext(node);
353 }
354 if (performReplacement(node, canonical)) {
355 return true;
356 }
357 }
358
359 if (nodeClass.isSimplifiable() && simplify) {
360 debug.log(DebugContext.VERBOSE_LEVEL, "Canonicalizer: simplifying %s", node);
361 COUNTER_SIMPLIFICATION_CONSIDERED_NODES.increment(debug);
362 node.simplify(tool);
363 if (node.isDeleted()) {
364 debug.log("Canonicalizer: simplified %s", node);
365 }
366 return node.isDeleted();
367 }
368 return false;
369 } catch (Throwable throwable) {
370 throw debug.handle(throwable);
371 }
372 }
373
374 // @formatter:off
375 // cases: original node:
376 // |Floating|Fixed-unconnected|Fixed-connected|
377 // --------------------------------------------
378 // null| 1 | X | 3 |
379 // --------------------------------------------
380 // Floating| 2 | X | 4 |
381 // canonical node: --------------------------------------------
382 // Fixed-unconnected| X | X | 5 |
383 // --------------------------------------------
384 // Fixed-connected| 2 | X | 6 |
385 // --------------------------------------------
386 // ControlSink| X | X | 7 |
387 // --------------------------------------------
388 // X: must not happen (checked with assertions)
389 // @formatter:on
390 private boolean performReplacement(final Node node, Node newCanonical) {
391 if (newCanonical == node) {
392 debug.log(DebugContext.VERBOSE_LEVEL, "Canonicalizer: work on %1s", node);
393 return false;
394 } else {
395 Node canonical = newCanonical;
396 debug.log("Canonicalizer: replacing %1s with %1s", node, canonical);
397 COUNTER_CANONICALIZED_NODES.increment(debug);
398 StructuredGraph graph = (StructuredGraph) node.graph();
399 if (canonical != null && !canonical.isAlive()) {
400 assert !canonical.isDeleted();
401 canonical = graph.addOrUniqueWithInputs(canonical);
402 }
403 if (node instanceof FloatingNode) {
404 assert canonical == null || !(canonical instanceof FixedNode) ||
405 (canonical.predecessor() != null || canonical instanceof StartNode || canonical instanceof AbstractMergeNode) : node +
406 " -> " + canonical + " : replacement should be floating or fixed and connected";
407 node.replaceAtUsages(canonical);
408 GraphUtil.killWithUnusedFloatingInputs(node, true);
409 } else {
410 assert node instanceof FixedNode && node.predecessor() != null : node + " -> " + canonical + " : node should be fixed & connected (" + node.predecessor() + ")";
411 FixedNode fixed = (FixedNode) node;
412 if (canonical instanceof ControlSinkNode) {
413 // case 7
414 fixed.replaceAtPredecessor(canonical);
415 GraphUtil.killCFG(fixed);
416 return true;
417 } else {
418 assert fixed instanceof FixedWithNextNode;
419 FixedWithNextNode fixedWithNext = (FixedWithNextNode) fixed;
420 // When removing a fixed node, new canonicalization
421 // opportunities for its successor may arise
422 assert fixedWithNext.next() != null;
423 tool.addToWorkList(fixedWithNext.next());
424 if (canonical == null) {
425 // case 3
426 node.replaceAtUsages(null);
427 GraphUtil.removeFixedWithUnusedInputs(fixedWithNext);
428 } else if (canonical instanceof FloatingNode) {
429 // case 4
430 graph.replaceFixedWithFloating(fixedWithNext, (FloatingNode) canonical);
431 } else {
432 assert canonical instanceof FixedNode;
433 if (canonical.predecessor() == null) {
434 assert !canonical.cfgSuccessors().iterator().hasNext() : "replacement " + canonical + " shouldn't have successors";
435 // case 5
436 graph.replaceFixedWithFixed(fixedWithNext, (FixedWithNextNode) canonical);
437 } else {
438 assert canonical.cfgSuccessors().iterator().hasNext() : "replacement " + canonical + " should have successors";
439 // case 6
440 node.replaceAtUsages(canonical);
441 GraphUtil.removeFixedWithUnusedInputs(fixedWithNext);
442 }
443 }
444 }
445 }
446 return true;
447 }
448 }
449
450 /**
451 * Calls {@link ValueNode#inferStamp()} on the node and, if it returns true (which means
452 * that the stamp has changed), re-queues the node's usages. If the stamp has changed then
453 * this method also checks if the stamp now describes a constant integer value, in which
454 * case the node is replaced with a constant.
455 */
456 private boolean tryInferStamp(ValueNode node) {
457 if (node.isAlive()) {
458 COUNTER_INFER_STAMP_CALLED.increment(debug);
459 if (node.inferStamp()) {
460 COUNTER_STAMP_CHANGED.increment(debug);
461 for (Node usage : node.usages()) {
462 workList.add(usage);
463 }
464 return true;
465 }
466 }
467 return false;
468 }
469
470 private final class Tool implements SimplifierTool, NodeView {
471
472 private final Assumptions assumptions;
473 private final OptionValues options;
474 private NodeView nodeView;
475
476 Tool(Assumptions assumptions, OptionValues options) {
477 this.assumptions = assumptions;
478 this.options = options;
479 this.nodeView = getNodeView();
480 }
481
482 @Override
483 public void deleteBranch(Node branch) {
484 FixedNode fixedBranch = (FixedNode) branch;
485 fixedBranch.predecessor().replaceFirstSuccessor(fixedBranch, null);
486 GraphUtil.killCFG(fixedBranch);
487 }
488
489 @Override
490 public MetaAccessProvider getMetaAccess() {
491 return context.getMetaAccess();
492 }
493
494 @Override
495 public ConstantReflectionProvider getConstantReflection() {
496 return context.getConstantReflection();
497 }
498
499 @Override
500 public ConstantFieldProvider getConstantFieldProvider() {
501 return context.getConstantFieldProvider();
502 }
503
504 @Override
505 public void addToWorkList(Node node) {
506 workList.add(node);
507 }
508
509 @Override
510 public void addToWorkList(Iterable<? extends Node> nodes) {
511 workList.addAll(nodes);
512 }
513
514 @Override
515 public void removeIfUnused(Node node) {
516 GraphUtil.tryKillUnused(node);
517 }
518
519 @Override
520 public boolean canonicalizeReads() {
521 return canonicalizeReads;
522 }
523
524 @Override
525 public boolean allUsagesAvailable() {
526 return true;
527 }
528
529 @Override
530 public Assumptions getAssumptions() {
531 return assumptions;
532 }
533
534 @Override
535 public Integer smallestCompareWidth() {
536 return context.getLowerer().smallestCompareWidth();
537 }
538
539 @Override
540 public OptionValues getOptions() {
541 return options;
542 }
543
544 @Override
545 public Stamp stamp(ValueNode node) {
546 return nodeView.stamp(node);
547 }
548 }
549 }
550
551 public boolean getCanonicalizeReads() {
552 return canonicalizeReads;
553 }
554
555 }