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.GraalGraphError; 30 import org.graalvm.compiler.graph.Graph; 31 import org.graalvm.compiler.graph.Graph.Mark; 32 import org.graalvm.compiler.graph.Graph.NodeEventListener; 33 import org.graalvm.compiler.graph.Graph.NodeEventScope; 34 import org.graalvm.compiler.graph.Node; 35 import org.graalvm.compiler.graph.Node.IndirectCanonicalization; 36 import org.graalvm.compiler.graph.NodeClass; 37 import org.graalvm.compiler.graph.NodeWorkList; 38 import org.graalvm.compiler.graph.spi.Canonicalizable; 39 import org.graalvm.compiler.graph.spi.Canonicalizable.BinaryCommutative; 40 import org.graalvm.compiler.graph.spi.SimplifierTool; 41 import org.graalvm.compiler.nodeinfo.InputType; 42 import org.graalvm.compiler.nodes.AbstractMergeNode; 43 import org.graalvm.compiler.nodes.ConstantNode; 44 import org.graalvm.compiler.nodes.ControlSinkNode; 45 import org.graalvm.compiler.nodes.FixedNode; 46 import org.graalvm.compiler.nodes.FixedWithNextNode; 47 import org.graalvm.compiler.nodes.StartNode; 48 import org.graalvm.compiler.nodes.StructuredGraph; 49 import org.graalvm.compiler.nodes.ValueNode; 50 import org.graalvm.compiler.nodes.calc.FloatingNode; 51 import org.graalvm.compiler.nodes.util.GraphUtil; 52 import org.graalvm.compiler.options.OptionValues; 53 import org.graalvm.compiler.phases.BasePhase; 54 import org.graalvm.compiler.phases.Phase; 55 import org.graalvm.compiler.phases.tiers.PhaseContext; 56 57 import jdk.vm.ci.meta.Assumptions; 58 import jdk.vm.ci.meta.Constant; 59 import jdk.vm.ci.meta.ConstantReflectionProvider; 60 import jdk.vm.ci.meta.MetaAccessProvider; 61 62 public class CanonicalizerPhase extends BasePhase<PhaseContext> { 63 64 private static final int MAX_ITERATION_PER_NODE = 10; 65 private static final DebugCounter COUNTER_CANONICALIZED_NODES = Debug.counter("CanonicalizedNodes"); 66 private static final DebugCounter COUNTER_PROCESSED_NODES = Debug.counter("ProcessedNodes"); 67 private static final DebugCounter COUNTER_CANONICALIZATION_CONSIDERED_NODES = Debug.counter("CanonicalizationConsideredNodes"); 68 private static final DebugCounter COUNTER_INFER_STAMP_CALLED = Debug.counter("InferStampCalled"); 69 private static final DebugCounter COUNTER_STAMP_CHANGED = Debug.counter("StampChanged"); 70 private static final DebugCounter COUNTER_SIMPLIFICATION_CONSIDERED_NODES = Debug.counter("SimplificationConsideredNodes"); 71 private static final DebugCounter COUNTER_GLOBAL_VALUE_NUMBERING_HITS = Debug.counter("GlobalValueNumberingHits"); 72 73 private boolean globalValueNumber = true; 74 private boolean canonicalizeReads = true; 75 private boolean simplify = true; 76 private final CustomCanonicalizer customCanonicalizer; 77 78 public abstract static class CustomCanonicalizer { 79 80 public Node canonicalize(Node node) { 81 return node; 82 } 83 84 @SuppressWarnings("unused") 85 public void simplify(Node node, SimplifierTool tool) { 86 } 87 } 88 89 public CanonicalizerPhase() { 90 this(null); 91 } 144 public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet, boolean dumpGraph) { 145 new Instance(context, workingSet).apply(graph, dumpGraph); 146 } 147 148 public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet, Mark newNodesMark) { 149 applyIncremental(graph, context, workingSet, newNodesMark, true); 150 } 151 152 public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet, Mark newNodesMark, boolean dumpGraph) { 153 new Instance(context, workingSet, newNodesMark).apply(graph, dumpGraph); 154 } 155 156 private final class Instance extends Phase { 157 158 private final Mark newNodesMark; 159 private final PhaseContext context; 160 private final Iterable<? extends Node> initWorkingSet; 161 162 private NodeWorkList workList; 163 private Tool tool; 164 165 private Instance(PhaseContext context) { 166 this(context, null, null); 167 } 168 169 private Instance(PhaseContext context, Iterable<? extends Node> workingSet) { 170 this(context, workingSet, null); 171 } 172 173 private Instance(PhaseContext context, Mark newNodesMark) { 174 this(context, null, newNodesMark); 175 } 176 177 private Instance(PhaseContext context, Iterable<? extends Node> workingSet, Mark newNodesMark) { 178 this.newNodesMark = newNodesMark; 179 this.context = context; 180 this.initWorkingSet = workingSet; 181 } 182 183 @Override 184 public boolean checkContract() { 185 return false; 186 } 187 188 @Override 189 protected void run(StructuredGraph graph) { 190 boolean wholeGraph = newNodesMark == null || newNodesMark.isStart(); 191 if (initWorkingSet == null) { 192 workList = graph.createIterativeNodeWorkList(wholeGraph, MAX_ITERATION_PER_NODE); 193 } else { 194 workList = graph.createIterativeNodeWorkList(false, MAX_ITERATION_PER_NODE); 195 workList.addAll(initWorkingSet); 196 } 197 if (!wholeGraph) { 198 workList.addAll(graph.getNewNodes(newNodesMark)); 199 } 200 tool = new Tool(graph.getAssumptions(), graph.getOptions()); 201 processWorkSet(graph); 202 } 203 204 @SuppressWarnings("try") 205 private void processWorkSet(StructuredGraph graph) { 206 NodeEventListener listener = new NodeEventListener() { 207 208 @Override 209 public void nodeAdded(Node node) { 212 213 @Override 214 public void inputChanged(Node node) { 215 workList.add(node); 216 if (node instanceof IndirectCanonicalization) { 217 for (Node usage : node.usages()) { 218 workList.add(usage); 219 } 220 } 221 } 222 223 @Override 224 public void usagesDroppedToZero(Node node) { 225 workList.add(node); 226 } 227 }; 228 229 try (NodeEventScope nes = graph.trackNodeEvents(listener)) { 230 for (Node n : workList) { 231 boolean changed = processNode(n); 232 if (changed && Debug.isDumpEnabled(Debug.DETAILED_LEVEL)) { 233 Debug.dump(Debug.DETAILED_LEVEL, graph, "CanonicalizerPhase %s", n); 234 } 235 } 236 } 237 } 238 239 /** 240 * @return true if the graph was changed. 241 */ 242 private boolean processNode(Node node) { 243 if (!node.isAlive()) { 244 return false; 245 } 246 COUNTER_PROCESSED_NODES.increment(); 247 if (GraphUtil.tryKillUnused(node)) { 248 return true; 249 } 250 NodeClass<?> nodeClass = node.getNodeClass(); 251 StructuredGraph graph = (StructuredGraph) node.graph(); 252 if (tryCanonicalize(node, nodeClass)) { 253 return true; 254 } 255 if (globalValueNumber && tryGlobalValueNumbering(node, nodeClass)) { 256 return true; 257 } 258 if (node instanceof ValueNode) { 259 ValueNode valueNode = (ValueNode) node; 260 boolean improvedStamp = tryInferStamp(valueNode); 261 Constant constant = valueNode.stamp().asConstant(); 262 if (constant != null && !(node instanceof ConstantNode)) { 263 ConstantNode stampConstant = ConstantNode.forConstant(valueNode.stamp(), constant, context.getMetaAccess(), graph); 264 Debug.log("Canonicalizer: constant stamp replaces %1s with %1s", valueNode, stampConstant); 265 valueNode.replaceAtUsages(InputType.Value, stampConstant); 266 GraphUtil.tryKillUnused(valueNode); 267 return true; 268 } else if (improvedStamp) { 269 // the improved stamp may enable additional canonicalization 270 if (tryCanonicalize(valueNode, nodeClass)) { 271 return true; 272 } 273 valueNode.usages().forEach(workList::add); 274 } 275 } 276 return false; 277 } 278 279 public boolean tryGlobalValueNumbering(Node node, NodeClass<?> nodeClass) { 280 if (nodeClass.valueNumberable()) { 281 Node newNode = node.graph().findDuplicate(node); 282 if (newNode != null) { 283 assert !(node instanceof FixedNode || newNode instanceof FixedNode); 284 node.replaceAtUsagesAndDelete(newNode); 285 COUNTER_GLOBAL_VALUE_NUMBERING_HITS.increment(); 286 Debug.log("GVN applied and new node is %1s", newNode); 287 return true; 288 } 289 } 290 return false; 291 } 292 293 private AutoCloseable getCanonicalizeableContractAssertion(Node node) { 294 boolean needsAssertion = false; 295 assert (needsAssertion = true) == true; 296 if (needsAssertion) { 297 Mark mark = node.graph().getMark(); 298 return () -> { 299 assert mark.equals(node.graph().getMark()) : "new node created while canonicalizing " + node.getClass().getSimpleName() + " " + node + ": " + 300 node.graph().getNewNodes(mark).snapshot(); 301 }; 302 } else { 303 return null; 304 } 305 } 306 307 @SuppressWarnings("try") 308 public boolean tryCanonicalize(final Node node, NodeClass<?> nodeClass) { 309 try (DebugCloseable position = node.withNodeSourcePosition()) { 310 if (customCanonicalizer != null) { 311 Node canonical = customCanonicalizer.canonicalize(node); 312 if (performReplacement(node, canonical)) { 313 return true; 314 } else { 315 customCanonicalizer.simplify(node, tool); 316 if (node.isDeleted()) { 317 return true; 318 } 319 } 320 } 321 if (nodeClass.isCanonicalizable()) { 322 COUNTER_CANONICALIZATION_CONSIDERED_NODES.increment(); 323 Node canonical; 324 try (AutoCloseable verify = getCanonicalizeableContractAssertion(node)) { 325 canonical = ((Canonicalizable) node).canonical(tool); 326 if (canonical == node && nodeClass.isCommutative()) { 327 canonical = ((BinaryCommutative<?>) node).maybeCommuteInputs(); 328 } 329 } catch (Throwable e) { 330 throw new GraalGraphError(e).addContext(node); 331 } 332 if (performReplacement(node, canonical)) { 333 return true; 334 } 335 } 336 337 if (nodeClass.isSimplifiable() && simplify) { 338 Debug.log(Debug.VERBOSE_LEVEL, "Canonicalizer: simplifying %s", node); 339 COUNTER_SIMPLIFICATION_CONSIDERED_NODES.increment(); 340 node.simplify(tool); 341 return node.isDeleted(); 342 } 343 return false; 344 } 345 } 346 347 // @formatter:off 348 // cases: original node: 349 // |Floating|Fixed-unconnected|Fixed-connected| 350 // -------------------------------------------- 351 // null| 1 | X | 3 | 352 // -------------------------------------------- 353 // Floating| 2 | X | 4 | 354 // canonical node: -------------------------------------------- 355 // Fixed-unconnected| X | X | 5 | 356 // -------------------------------------------- 357 // Fixed-connected| 2 | X | 6 | 358 // -------------------------------------------- 359 // ControlSink| X | X | 7 | 360 // -------------------------------------------- 361 // X: must not happen (checked with assertions) 362 // @formatter:on 363 private boolean performReplacement(final Node node, Node newCanonical) { 364 if (newCanonical == node) { 365 Debug.log(Debug.VERBOSE_LEVEL, "Canonicalizer: work on %1s", node); 366 return false; 367 } else { 368 Node canonical = newCanonical; 369 Debug.log("Canonicalizer: replacing %1s with %1s", node, canonical); 370 COUNTER_CANONICALIZED_NODES.increment(); 371 StructuredGraph graph = (StructuredGraph) node.graph(); 372 if (canonical != null && !canonical.isAlive()) { 373 assert !canonical.isDeleted(); 374 canonical = graph.addOrUniqueWithInputs(canonical); 375 } 376 if (node instanceof FloatingNode) { 377 assert canonical == null || !(canonical instanceof FixedNode) || 378 (canonical.predecessor() != null || canonical instanceof StartNode || canonical instanceof AbstractMergeNode) : node + 379 " -> " + canonical + " : replacement should be floating or fixed and connected"; 380 node.replaceAtUsages(canonical); 381 GraphUtil.killWithUnusedFloatingInputs(node, true); 382 } else { 383 assert node instanceof FixedNode && node.predecessor() != null : node + " -> " + canonical + " : node should be fixed & connected (" + node.predecessor() + ")"; 384 FixedNode fixed = (FixedNode) node; 385 if (canonical instanceof ControlSinkNode) { 386 // case 7 387 fixed.replaceAtPredecessor(canonical); 388 GraphUtil.killCFG(fixed); 389 return true; 390 } else { 411 assert canonical.cfgSuccessors().iterator().hasNext() : "replacement " + canonical + " should have successors"; 412 // case 6 413 node.replaceAtUsages(canonical); 414 GraphUtil.removeFixedWithUnusedInputs(fixedWithNext); 415 } 416 } 417 } 418 } 419 return true; 420 } 421 } 422 423 /** 424 * Calls {@link ValueNode#inferStamp()} on the node and, if it returns true (which means 425 * that the stamp has changed), re-queues the node's usages. If the stamp has changed then 426 * this method also checks if the stamp now describes a constant integer value, in which 427 * case the node is replaced with a constant. 428 */ 429 private boolean tryInferStamp(ValueNode node) { 430 if (node.isAlive()) { 431 COUNTER_INFER_STAMP_CALLED.increment(); 432 if (node.inferStamp()) { 433 COUNTER_STAMP_CHANGED.increment(); 434 for (Node usage : node.usages()) { 435 workList.add(usage); 436 } 437 return true; 438 } 439 } 440 return false; 441 } 442 443 private final class Tool implements SimplifierTool { 444 445 private final Assumptions assumptions; 446 private final OptionValues options; 447 448 Tool(Assumptions assumptions, OptionValues options) { 449 this.assumptions = assumptions; 450 this.options = options; 451 } 452 453 @Override | 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.CounterKey; 27 import org.graalvm.compiler.debug.DebugCloseable; 28 import org.graalvm.compiler.debug.DebugContext; 29 import org.graalvm.compiler.graph.GraalGraphError; 30 import org.graalvm.compiler.graph.Graph; 31 import org.graalvm.compiler.graph.Graph.Mark; 32 import org.graalvm.compiler.graph.Graph.NodeEventListener; 33 import org.graalvm.compiler.graph.Graph.NodeEventScope; 34 import org.graalvm.compiler.graph.Node; 35 import org.graalvm.compiler.graph.Node.IndirectCanonicalization; 36 import org.graalvm.compiler.graph.NodeClass; 37 import org.graalvm.compiler.graph.NodeWorkList; 38 import org.graalvm.compiler.graph.spi.Canonicalizable; 39 import org.graalvm.compiler.graph.spi.Canonicalizable.BinaryCommutative; 40 import org.graalvm.compiler.graph.spi.SimplifierTool; 41 import org.graalvm.compiler.nodeinfo.InputType; 42 import org.graalvm.compiler.nodes.AbstractMergeNode; 43 import org.graalvm.compiler.nodes.ConstantNode; 44 import org.graalvm.compiler.nodes.ControlSinkNode; 45 import org.graalvm.compiler.nodes.FixedNode; 46 import org.graalvm.compiler.nodes.FixedWithNextNode; 47 import org.graalvm.compiler.nodes.StartNode; 48 import org.graalvm.compiler.nodes.StructuredGraph; 49 import org.graalvm.compiler.nodes.ValueNode; 50 import org.graalvm.compiler.nodes.calc.FloatingNode; 51 import org.graalvm.compiler.nodes.util.GraphUtil; 52 import org.graalvm.compiler.options.OptionValues; 53 import org.graalvm.compiler.phases.BasePhase; 54 import org.graalvm.compiler.phases.Phase; 55 import org.graalvm.compiler.phases.tiers.PhaseContext; 56 57 import jdk.vm.ci.meta.Assumptions; 58 import jdk.vm.ci.meta.Constant; 59 import jdk.vm.ci.meta.ConstantReflectionProvider; 60 import jdk.vm.ci.meta.MetaAccessProvider; 61 62 public class CanonicalizerPhase extends BasePhase<PhaseContext> { 63 64 private static final int MAX_ITERATION_PER_NODE = 10; 65 private static final CounterKey COUNTER_CANONICALIZED_NODES = DebugContext.counter("CanonicalizedNodes"); 66 private static final CounterKey COUNTER_PROCESSED_NODES = DebugContext.counter("ProcessedNodes"); 67 private static final CounterKey COUNTER_CANONICALIZATION_CONSIDERED_NODES = DebugContext.counter("CanonicalizationConsideredNodes"); 68 private static final CounterKey COUNTER_INFER_STAMP_CALLED = DebugContext.counter("InferStampCalled"); 69 private static final CounterKey COUNTER_STAMP_CHANGED = DebugContext.counter("StampChanged"); 70 private static final CounterKey COUNTER_SIMPLIFICATION_CONSIDERED_NODES = DebugContext.counter("SimplificationConsideredNodes"); 71 private static final CounterKey COUNTER_GLOBAL_VALUE_NUMBERING_HITS = DebugContext.counter("GlobalValueNumberingHits"); 72 73 private boolean globalValueNumber = true; 74 private boolean canonicalizeReads = true; 75 private boolean simplify = true; 76 private final CustomCanonicalizer customCanonicalizer; 77 78 public abstract static class CustomCanonicalizer { 79 80 public Node canonicalize(Node node) { 81 return node; 82 } 83 84 @SuppressWarnings("unused") 85 public void simplify(Node node, SimplifierTool tool) { 86 } 87 } 88 89 public CanonicalizerPhase() { 90 this(null); 91 } 144 public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet, boolean dumpGraph) { 145 new Instance(context, workingSet).apply(graph, dumpGraph); 146 } 147 148 public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet, Mark newNodesMark) { 149 applyIncremental(graph, context, workingSet, newNodesMark, true); 150 } 151 152 public void applyIncremental(StructuredGraph graph, PhaseContext context, Iterable<? extends Node> workingSet, Mark newNodesMark, boolean dumpGraph) { 153 new Instance(context, workingSet, newNodesMark).apply(graph, dumpGraph); 154 } 155 156 private final class Instance extends Phase { 157 158 private final Mark newNodesMark; 159 private final PhaseContext context; 160 private final Iterable<? extends Node> initWorkingSet; 161 162 private NodeWorkList workList; 163 private Tool tool; 164 private DebugContext debug; 165 166 private Instance(PhaseContext context) { 167 this(context, null, null); 168 } 169 170 private Instance(PhaseContext context, Iterable<? extends Node> workingSet) { 171 this(context, workingSet, null); 172 } 173 174 private Instance(PhaseContext context, Mark newNodesMark) { 175 this(context, null, newNodesMark); 176 } 177 178 private Instance(PhaseContext context, Iterable<? extends Node> workingSet, Mark newNodesMark) { 179 this.newNodesMark = newNodesMark; 180 this.context = context; 181 this.initWorkingSet = workingSet; 182 } 183 184 @Override 185 public boolean checkContract() { 186 return false; 187 } 188 189 @Override 190 protected void run(StructuredGraph graph) { 191 this.debug = graph.getDebug(); 192 boolean wholeGraph = newNodesMark == null || newNodesMark.isStart(); 193 if (initWorkingSet == null) { 194 workList = graph.createIterativeNodeWorkList(wholeGraph, MAX_ITERATION_PER_NODE); 195 } else { 196 workList = graph.createIterativeNodeWorkList(false, MAX_ITERATION_PER_NODE); 197 workList.addAll(initWorkingSet); 198 } 199 if (!wholeGraph) { 200 workList.addAll(graph.getNewNodes(newNodesMark)); 201 } 202 tool = new Tool(graph.getAssumptions(), graph.getOptions()); 203 processWorkSet(graph); 204 } 205 206 @SuppressWarnings("try") 207 private void processWorkSet(StructuredGraph graph) { 208 NodeEventListener listener = new NodeEventListener() { 209 210 @Override 211 public void nodeAdded(Node node) { 214 215 @Override 216 public void inputChanged(Node node) { 217 workList.add(node); 218 if (node instanceof IndirectCanonicalization) { 219 for (Node usage : node.usages()) { 220 workList.add(usage); 221 } 222 } 223 } 224 225 @Override 226 public void usagesDroppedToZero(Node node) { 227 workList.add(node); 228 } 229 }; 230 231 try (NodeEventScope nes = graph.trackNodeEvents(listener)) { 232 for (Node n : workList) { 233 boolean changed = processNode(n); 234 if (changed && debug.isDumpEnabled(DebugContext.DETAILED_LEVEL)) { 235 debug.dump(DebugContext.DETAILED_LEVEL, graph, "CanonicalizerPhase %s", n); 236 } 237 } 238 } 239 } 240 241 /** 242 * @return true if the graph was changed. 243 */ 244 private boolean processNode(Node node) { 245 if (!node.isAlive()) { 246 return false; 247 } 248 COUNTER_PROCESSED_NODES.increment(debug); 249 if (GraphUtil.tryKillUnused(node)) { 250 return true; 251 } 252 NodeClass<?> nodeClass = node.getNodeClass(); 253 StructuredGraph graph = (StructuredGraph) node.graph(); 254 if (tryCanonicalize(node, nodeClass)) { 255 return true; 256 } 257 if (globalValueNumber && tryGlobalValueNumbering(node, nodeClass)) { 258 return true; 259 } 260 if (node instanceof ValueNode) { 261 ValueNode valueNode = (ValueNode) node; 262 boolean improvedStamp = tryInferStamp(valueNode); 263 Constant constant = valueNode.stamp().asConstant(); 264 if (constant != null && !(node instanceof ConstantNode)) { 265 ConstantNode stampConstant = ConstantNode.forConstant(valueNode.stamp(), constant, context.getMetaAccess(), graph); 266 debug.log("Canonicalizer: constant stamp replaces %1s with %1s", valueNode, stampConstant); 267 valueNode.replaceAtUsages(InputType.Value, stampConstant); 268 GraphUtil.tryKillUnused(valueNode); 269 return true; 270 } else if (improvedStamp) { 271 // the improved stamp may enable additional canonicalization 272 if (tryCanonicalize(valueNode, nodeClass)) { 273 return true; 274 } 275 valueNode.usages().forEach(workList::add); 276 } 277 } 278 return false; 279 } 280 281 public boolean tryGlobalValueNumbering(Node node, NodeClass<?> nodeClass) { 282 if (nodeClass.valueNumberable()) { 283 Node newNode = node.graph().findDuplicate(node); 284 if (newNode != null) { 285 assert !(node instanceof FixedNode || newNode instanceof FixedNode); 286 node.replaceAtUsagesAndDelete(newNode); 287 COUNTER_GLOBAL_VALUE_NUMBERING_HITS.increment(debug); 288 debug.log("GVN applied and new node is %1s", newNode); 289 return true; 290 } 291 } 292 return false; 293 } 294 295 private AutoCloseable getCanonicalizeableContractAssertion(Node node) { 296 boolean needsAssertion = false; 297 assert (needsAssertion = true) == true; 298 if (needsAssertion) { 299 Mark mark = node.graph().getMark(); 300 return () -> { 301 assert mark.equals(node.graph().getMark()) : "new node created while canonicalizing " + node.getClass().getSimpleName() + " " + node + ": " + 302 node.graph().getNewNodes(mark).snapshot(); 303 }; 304 } else { 305 return null; 306 } 307 } 308 309 @SuppressWarnings("try") 310 public boolean tryCanonicalize(final Node node, NodeClass<?> nodeClass) { 311 try (DebugCloseable position = node.withNodeSourcePosition()) { 312 if (customCanonicalizer != null) { 313 Node canonical = customCanonicalizer.canonicalize(node); 314 if (performReplacement(node, canonical)) { 315 return true; 316 } else { 317 customCanonicalizer.simplify(node, tool); 318 if (node.isDeleted()) { 319 return true; 320 } 321 } 322 } 323 if (nodeClass.isCanonicalizable()) { 324 COUNTER_CANONICALIZATION_CONSIDERED_NODES.increment(debug); 325 Node canonical; 326 try (AutoCloseable verify = getCanonicalizeableContractAssertion(node)) { 327 canonical = ((Canonicalizable) node).canonical(tool); 328 if (canonical == node && nodeClass.isCommutative()) { 329 canonical = ((BinaryCommutative<?>) node).maybeCommuteInputs(); 330 } 331 } catch (Throwable e) { 332 throw new GraalGraphError(e).addContext(node); 333 } 334 if (performReplacement(node, canonical)) { 335 return true; 336 } 337 } 338 339 if (nodeClass.isSimplifiable() && simplify) { 340 debug.log(DebugContext.VERBOSE_LEVEL, "Canonicalizer: simplifying %s", node); 341 COUNTER_SIMPLIFICATION_CONSIDERED_NODES.increment(debug); 342 node.simplify(tool); 343 return node.isDeleted(); 344 } 345 return false; 346 } 347 } 348 349 // @formatter:off 350 // cases: original node: 351 // |Floating|Fixed-unconnected|Fixed-connected| 352 // -------------------------------------------- 353 // null| 1 | X | 3 | 354 // -------------------------------------------- 355 // Floating| 2 | X | 4 | 356 // canonical node: -------------------------------------------- 357 // Fixed-unconnected| X | X | 5 | 358 // -------------------------------------------- 359 // Fixed-connected| 2 | X | 6 | 360 // -------------------------------------------- 361 // ControlSink| X | X | 7 | 362 // -------------------------------------------- 363 // X: must not happen (checked with assertions) 364 // @formatter:on 365 private boolean performReplacement(final Node node, Node newCanonical) { 366 if (newCanonical == node) { 367 debug.log(DebugContext.VERBOSE_LEVEL, "Canonicalizer: work on %1s", node); 368 return false; 369 } else { 370 Node canonical = newCanonical; 371 debug.log("Canonicalizer: replacing %1s with %1s", node, canonical); 372 COUNTER_CANONICALIZED_NODES.increment(debug); 373 StructuredGraph graph = (StructuredGraph) node.graph(); 374 if (canonical != null && !canonical.isAlive()) { 375 assert !canonical.isDeleted(); 376 canonical = graph.addOrUniqueWithInputs(canonical); 377 } 378 if (node instanceof FloatingNode) { 379 assert canonical == null || !(canonical instanceof FixedNode) || 380 (canonical.predecessor() != null || canonical instanceof StartNode || canonical instanceof AbstractMergeNode) : node + 381 " -> " + canonical + " : replacement should be floating or fixed and connected"; 382 node.replaceAtUsages(canonical); 383 GraphUtil.killWithUnusedFloatingInputs(node, true); 384 } else { 385 assert node instanceof FixedNode && node.predecessor() != null : node + " -> " + canonical + " : node should be fixed & connected (" + node.predecessor() + ")"; 386 FixedNode fixed = (FixedNode) node; 387 if (canonical instanceof ControlSinkNode) { 388 // case 7 389 fixed.replaceAtPredecessor(canonical); 390 GraphUtil.killCFG(fixed); 391 return true; 392 } else { 413 assert canonical.cfgSuccessors().iterator().hasNext() : "replacement " + canonical + " should have successors"; 414 // case 6 415 node.replaceAtUsages(canonical); 416 GraphUtil.removeFixedWithUnusedInputs(fixedWithNext); 417 } 418 } 419 } 420 } 421 return true; 422 } 423 } 424 425 /** 426 * Calls {@link ValueNode#inferStamp()} on the node and, if it returns true (which means 427 * that the stamp has changed), re-queues the node's usages. If the stamp has changed then 428 * this method also checks if the stamp now describes a constant integer value, in which 429 * case the node is replaced with a constant. 430 */ 431 private boolean tryInferStamp(ValueNode node) { 432 if (node.isAlive()) { 433 COUNTER_INFER_STAMP_CALLED.increment(debug); 434 if (node.inferStamp()) { 435 COUNTER_STAMP_CHANGED.increment(debug); 436 for (Node usage : node.usages()) { 437 workList.add(usage); 438 } 439 return true; 440 } 441 } 442 return false; 443 } 444 445 private final class Tool implements SimplifierTool { 446 447 private final Assumptions assumptions; 448 private final OptionValues options; 449 450 Tool(Assumptions assumptions, OptionValues options) { 451 this.assumptions = assumptions; 452 this.options = options; 453 } 454 455 @Override |