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