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