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 static org.graalvm.compiler.core.common.GraalOptions.OptEliminateGuards; 28 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED; 29 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED; 30 import static org.graalvm.compiler.phases.common.LoweringPhase.ProcessBlockState.ST_ENTER; 31 import static org.graalvm.compiler.phases.common.LoweringPhase.ProcessBlockState.ST_ENTER_ALWAYS_REACHED; 32 import static org.graalvm.compiler.phases.common.LoweringPhase.ProcessBlockState.ST_LEAVE; 33 import static org.graalvm.compiler.phases.common.LoweringPhase.ProcessBlockState.ST_PROCESS; 34 import static org.graalvm.compiler.phases.common.LoweringPhase.ProcessBlockState.ST_PROCESS_ALWAYS_REACHED; 35 36 import java.util.ArrayList; 37 import java.util.Collection; 38 import java.util.List; 39 40 import org.graalvm.compiler.core.common.spi.ConstantFieldProvider; 41 import org.graalvm.compiler.core.common.type.StampFactory; 42 import org.graalvm.compiler.debug.DebugCloseable; 43 import org.graalvm.compiler.debug.GraalError; 44 import org.graalvm.compiler.graph.Graph.Mark; 45 import org.graalvm.compiler.graph.Node; 46 import org.graalvm.compiler.graph.NodeBitMap; 47 import org.graalvm.compiler.graph.NodeClass; 48 import org.graalvm.compiler.graph.NodeSourcePosition; 49 import org.graalvm.compiler.graph.iterators.NodeIterable; 50 import org.graalvm.compiler.nodeinfo.InputType; 51 import org.graalvm.compiler.nodeinfo.NodeInfo; 52 import org.graalvm.compiler.nodes.AbstractBeginNode; 53 import org.graalvm.compiler.nodes.BeginNode; 54 import org.graalvm.compiler.nodes.ControlSinkNode; 55 import org.graalvm.compiler.nodes.FixedGuardNode; 56 import org.graalvm.compiler.nodes.FixedNode; 57 import org.graalvm.compiler.nodes.FixedWithNextNode; 58 import org.graalvm.compiler.nodes.GuardNode; 59 import org.graalvm.compiler.nodes.LogicNode; 60 import org.graalvm.compiler.nodes.PhiNode; 61 import org.graalvm.compiler.nodes.ProxyNode; 62 import org.graalvm.compiler.nodes.StructuredGraph; 63 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult; 64 import org.graalvm.compiler.nodes.ValueNode; 65 import org.graalvm.compiler.nodes.calc.FloatingNode; 66 import org.graalvm.compiler.nodes.cfg.Block; 67 import org.graalvm.compiler.nodes.extended.AnchoringNode; 68 import org.graalvm.compiler.nodes.extended.GuardedNode; 69 import org.graalvm.compiler.nodes.extended.GuardingNode; 70 import org.graalvm.compiler.nodes.memory.MemoryCheckpoint; 71 import org.graalvm.compiler.nodes.spi.Lowerable; 72 import org.graalvm.compiler.nodes.spi.LoweringProvider; 73 import org.graalvm.compiler.nodes.spi.LoweringTool; 74 import org.graalvm.compiler.nodes.spi.Replacements; 75 import org.graalvm.compiler.nodes.spi.StampProvider; 76 import org.graalvm.compiler.options.OptionValues; 77 import org.graalvm.compiler.phases.BasePhase; 78 import org.graalvm.compiler.phases.Phase; 79 import org.graalvm.compiler.phases.schedule.SchedulePhase; 80 import org.graalvm.compiler.phases.tiers.PhaseContext; 81 import jdk.internal.vm.compiler.word.LocationIdentity; 82 83 import jdk.vm.ci.meta.ConstantReflectionProvider; 84 import jdk.vm.ci.meta.DeoptimizationAction; 85 import jdk.vm.ci.meta.DeoptimizationReason; 86 import jdk.vm.ci.meta.MetaAccessProvider; 87 import jdk.vm.ci.meta.SpeculationLog; 88 import jdk.vm.ci.meta.SpeculationLog.Speculation; 89 90 /** 91 * Processes all {@link Lowerable} nodes to do their lowering. 92 */ 93 public class LoweringPhase extends BasePhase<PhaseContext> { 94 95 @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED) 96 static final class DummyGuardHandle extends ValueNode implements GuardedNode { 97 public static final NodeClass<DummyGuardHandle> TYPE = NodeClass.create(DummyGuardHandle.class); 98 @Input(InputType.Guard) GuardingNode guard; 99 DummyGuardHandle(GuardingNode guard)100 protected DummyGuardHandle(GuardingNode guard) { 101 super(TYPE, StampFactory.forVoid()); 102 this.guard = guard; 103 } 104 105 @Override getGuard()106 public GuardingNode getGuard() { 107 return guard; 108 } 109 110 @Override setGuard(GuardingNode guard)111 public void setGuard(GuardingNode guard) { 112 updateUsagesInterface(this.guard, guard); 113 this.guard = guard; 114 } 115 116 @Override asNode()117 public ValueNode asNode() { 118 return this; 119 } 120 } 121 122 @Override checkContract()123 public boolean checkContract() { 124 return false; 125 } 126 127 final class LoweringToolImpl implements LoweringTool { 128 129 private final PhaseContext context; 130 private final NodeBitMap activeGuards; 131 private AnchoringNode guardAnchor; 132 private FixedWithNextNode lastFixedNode; 133 LoweringToolImpl(PhaseContext context, AnchoringNode guardAnchor, NodeBitMap activeGuards, FixedWithNextNode lastFixedNode)134 LoweringToolImpl(PhaseContext context, AnchoringNode guardAnchor, NodeBitMap activeGuards, FixedWithNextNode lastFixedNode) { 135 this.context = context; 136 this.guardAnchor = guardAnchor; 137 this.activeGuards = activeGuards; 138 this.lastFixedNode = lastFixedNode; 139 } 140 141 @Override getLoweringStage()142 public LoweringStage getLoweringStage() { 143 return loweringStage; 144 } 145 146 @Override getConstantReflection()147 public ConstantReflectionProvider getConstantReflection() { 148 return context.getConstantReflection(); 149 } 150 151 @Override getConstantFieldProvider()152 public ConstantFieldProvider getConstantFieldProvider() { 153 return context.getConstantFieldProvider(); 154 } 155 156 @Override getMetaAccess()157 public MetaAccessProvider getMetaAccess() { 158 return context.getMetaAccess(); 159 } 160 161 @Override getLowerer()162 public LoweringProvider getLowerer() { 163 return context.getLowerer(); 164 } 165 166 @Override getReplacements()167 public Replacements getReplacements() { 168 return context.getReplacements(); 169 } 170 171 @Override getCurrentGuardAnchor()172 public AnchoringNode getCurrentGuardAnchor() { 173 return guardAnchor; 174 } 175 176 @Override createGuard(FixedNode before, LogicNode condition, DeoptimizationReason deoptReason, DeoptimizationAction action)177 public GuardingNode createGuard(FixedNode before, LogicNode condition, DeoptimizationReason deoptReason, DeoptimizationAction action) { 178 return createGuard(before, condition, deoptReason, action, SpeculationLog.NO_SPECULATION, false, null); 179 } 180 181 @Override getStampProvider()182 public StampProvider getStampProvider() { 183 return context.getStampProvider(); 184 } 185 186 @Override createGuard(FixedNode before, LogicNode condition, DeoptimizationReason deoptReason, DeoptimizationAction action, Speculation speculation, boolean negated, NodeSourcePosition noDeoptSucccessorPosition)187 public GuardingNode createGuard(FixedNode before, LogicNode condition, DeoptimizationReason deoptReason, DeoptimizationAction action, Speculation speculation, boolean negated, 188 NodeSourcePosition noDeoptSucccessorPosition) { 189 StructuredGraph graph = before.graph(); 190 if (OptEliminateGuards.getValue(graph.getOptions())) { 191 for (Node usage : condition.usages()) { 192 if (!activeGuards.isNew(usage) && activeGuards.isMarked(usage) && ((GuardNode) usage).isNegated() == negated) { 193 return (GuardNode) usage; 194 } 195 } 196 } 197 if (!condition.graph().getGuardsStage().allowsFloatingGuards()) { 198 FixedGuardNode fixedGuard = graph.add(new FixedGuardNode(condition, deoptReason, action, speculation, negated, noDeoptSucccessorPosition)); 199 graph.addBeforeFixed(before, fixedGuard); 200 DummyGuardHandle handle = graph.add(new DummyGuardHandle(fixedGuard)); 201 fixedGuard.lower(this); 202 GuardingNode result = handle.getGuard(); 203 handle.safeDelete(); 204 return result; 205 } else { 206 GuardNode newGuard = graph.unique(new GuardNode(condition, guardAnchor, deoptReason, action, negated, speculation, noDeoptSucccessorPosition)); 207 if (OptEliminateGuards.getValue(graph.getOptions())) { 208 activeGuards.markAndGrow(newGuard); 209 } 210 return newGuard; 211 } 212 } 213 214 @Override lastFixedNode()215 public FixedWithNextNode lastFixedNode() { 216 return lastFixedNode; 217 } 218 setLastFixedNode(FixedWithNextNode n)219 private void setLastFixedNode(FixedWithNextNode n) { 220 assert n.isAlive() : n; 221 lastFixedNode = n; 222 } 223 } 224 225 private final CanonicalizerPhase canonicalizer; 226 private final LoweringTool.LoweringStage loweringStage; 227 LoweringPhase(CanonicalizerPhase canonicalizer, LoweringTool.LoweringStage loweringStage)228 public LoweringPhase(CanonicalizerPhase canonicalizer, LoweringTool.LoweringStage loweringStage) { 229 this.canonicalizer = canonicalizer; 230 this.loweringStage = loweringStage; 231 } 232 233 @Override shouldDumpBeforeAtBasicLevel()234 protected boolean shouldDumpBeforeAtBasicLevel() { 235 return loweringStage == LoweringTool.StandardLoweringStage.HIGH_TIER; 236 } 237 238 /** 239 * Checks that second lowering of a given graph did not introduce any new nodes. 240 * 241 * @param graph a graph that was just {@linkplain #lower lowered} 242 * @throws AssertionError if the check fails 243 */ checkPostLowering(StructuredGraph graph, PhaseContext context)244 private boolean checkPostLowering(StructuredGraph graph, PhaseContext context) { 245 Mark expectedMark = graph.getMark(); 246 lower(graph, context, LoweringMode.VERIFY_LOWERING); 247 Mark mark = graph.getMark(); 248 assert mark.equals(expectedMark) : graph + ": a second round in the current lowering phase introduced these new nodes: " + graph.getNewNodes(expectedMark).snapshot(); 249 return true; 250 } 251 252 @Override run(final StructuredGraph graph, PhaseContext context)253 protected void run(final StructuredGraph graph, PhaseContext context) { 254 lower(graph, context, LoweringMode.LOWERING); 255 assert checkPostLowering(graph, context); 256 } 257 lower(StructuredGraph graph, PhaseContext context, LoweringMode mode)258 private void lower(StructuredGraph graph, PhaseContext context, LoweringMode mode) { 259 IncrementalCanonicalizerPhase<PhaseContext> incrementalCanonicalizer = new IncrementalCanonicalizerPhase<>(canonicalizer); 260 incrementalCanonicalizer.appendPhase(new Round(context, mode, graph.getOptions())); 261 incrementalCanonicalizer.apply(graph, context); 262 assert graph.verify(); 263 } 264 265 /** 266 * Checks that lowering of a given node did not introduce any new {@link Lowerable} nodes that 267 * could be lowered in the current {@link LoweringPhase}. Such nodes must be recursively lowered 268 * as part of lowering {@code node}. 269 * 270 * @param node a node that was just lowered 271 * @param preLoweringMark the graph mark before {@code node} was lowered 272 * @param unscheduledUsages set of {@code node}'s usages that were unscheduled before it was 273 * lowered 274 * @throws AssertionError if the check fails 275 */ checkPostNodeLowering(Node node, LoweringToolImpl loweringTool, Mark preLoweringMark, Collection<Node> unscheduledUsages)276 private static boolean checkPostNodeLowering(Node node, LoweringToolImpl loweringTool, Mark preLoweringMark, Collection<Node> unscheduledUsages) { 277 StructuredGraph graph = (StructuredGraph) node.graph(); 278 Mark postLoweringMark = graph.getMark(); 279 NodeIterable<Node> newNodesAfterLowering = graph.getNewNodes(preLoweringMark); 280 if (node instanceof FloatingNode) { 281 if (!unscheduledUsages.isEmpty()) { 282 for (Node n : newNodesAfterLowering) { 283 assert !(n instanceof FixedNode) : node.graph() + ": cannot lower floatable node " + node + " as it introduces fixed node(s) but has the following unscheduled usages: " + 284 unscheduledUsages; 285 } 286 } 287 } 288 for (Node n : newNodesAfterLowering) { 289 if (n instanceof Lowerable) { 290 ((Lowerable) n).lower(loweringTool); 291 Mark mark = graph.getMark(); 292 assert postLoweringMark.equals(mark) : graph + ": lowering of " + node + " produced lowerable " + n + " that should have been recursively lowered as it introduces these new nodes: " + 293 graph.getNewNodes(postLoweringMark).snapshot(); 294 } 295 if (graph.isAfterFloatingReadPhase() && n instanceof MemoryCheckpoint && !(node instanceof MemoryCheckpoint) && !(node instanceof ControlSinkNode)) { 296 /* 297 * The lowering introduced a MemoryCheckpoint but the current node isn't a 298 * checkpoint. This is only OK if the locations involved don't affect the memory 299 * graph or if the new kill location doesn't connect into the existing graph. 300 */ 301 boolean isAny = false; 302 if (n instanceof MemoryCheckpoint.Single) { 303 isAny = ((MemoryCheckpoint.Single) n).getLocationIdentity().isAny(); 304 } else { 305 for (LocationIdentity ident : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) { 306 if (ident.isAny()) { 307 isAny = true; 308 } 309 } 310 } 311 if (isAny && n instanceof FixedWithNextNode) { 312 /* 313 * Check if the next kill location leads directly to a ControlSinkNode in the 314 * new part of the graph. This is a fairly conservative test that could be made 315 * more general if required. 316 */ 317 FixedWithNextNode cur = (FixedWithNextNode) n; 318 while (cur != null && graph.isNew(preLoweringMark, cur)) { 319 if (cur.next() instanceof ControlSinkNode) { 320 isAny = false; 321 break; 322 } 323 if (cur.next() instanceof FixedWithNextNode) { 324 cur = (FixedWithNextNode) cur.next(); 325 } else { 326 break; 327 } 328 } 329 } 330 assert !isAny : node + " " + n; 331 } 332 } 333 return true; 334 } 335 336 private enum LoweringMode { 337 LOWERING, 338 VERIFY_LOWERING 339 } 340 341 private final class Round extends Phase { 342 343 private final PhaseContext context; 344 private final LoweringMode mode; 345 private ScheduleResult schedule; 346 private final SchedulePhase schedulePhase; 347 Round(PhaseContext context, LoweringMode mode, OptionValues options)348 private Round(PhaseContext context, LoweringMode mode, OptionValues options) { 349 this.context = context; 350 this.mode = mode; 351 352 /* 353 * In VERIFY_LOWERING, we want to verify whether the lowering itself changes the graph. 354 * Make sure we're not detecting spurious changes because the SchedulePhase modifies the 355 * graph. 356 */ 357 boolean immutableSchedule = mode == LoweringMode.VERIFY_LOWERING; 358 359 this.schedulePhase = new SchedulePhase(immutableSchedule, options); 360 } 361 362 @Override getName()363 protected CharSequence getName() { 364 switch (mode) { 365 case LOWERING: 366 return "LoweringRound"; 367 case VERIFY_LOWERING: 368 return "VerifyLoweringRound"; 369 default: 370 throw GraalError.shouldNotReachHere(); 371 } 372 } 373 374 @Override checkContract()375 public boolean checkContract() { 376 /* 377 * lowering with snippets cannot be fully built in the node costs of all high level 378 * nodes 379 */ 380 return false; 381 } 382 383 @Override run(StructuredGraph graph)384 public void run(StructuredGraph graph) { 385 schedulePhase.apply(graph, false); 386 schedule = graph.getLastSchedule(); 387 schedule.getCFG().computePostdominators(); 388 Block startBlock = schedule.getCFG().getStartBlock(); 389 ProcessFrame rootFrame = new ProcessFrame(startBlock, graph.createNodeBitMap(), startBlock.getBeginNode(), null); 390 LoweringPhase.processBlock(rootFrame); 391 } 392 393 private class ProcessFrame extends Frame<ProcessFrame> { 394 private final NodeBitMap activeGuards; 395 private AnchoringNode anchor; 396 ProcessFrame(Block block, NodeBitMap activeGuards, AnchoringNode anchor, ProcessFrame parent)397 ProcessFrame(Block block, NodeBitMap activeGuards, AnchoringNode anchor, ProcessFrame parent) { 398 super(block, parent); 399 this.activeGuards = activeGuards; 400 this.anchor = anchor; 401 } 402 403 @Override preprocess()404 public void preprocess() { 405 this.anchor = Round.this.process(block, activeGuards, anchor); 406 } 407 408 @Override enter(Block b)409 public ProcessFrame enter(Block b) { 410 return new ProcessFrame(b, activeGuards, b.getBeginNode(), this); 411 } 412 413 @Override enterAlwaysReached(Block b)414 public Frame<?> enterAlwaysReached(Block b) { 415 AnchoringNode newAnchor = anchor; 416 if (parent != null && b.getLoop() != parent.block.getLoop() && !b.isLoopHeader()) { 417 // We are exiting a loop => cannot reuse the anchor without inserting loop 418 // proxies. 419 newAnchor = b.getBeginNode(); 420 } 421 return new ProcessFrame(b, activeGuards, newAnchor, this); 422 } 423 424 @Override postprocess()425 public void postprocess() { 426 if (anchor == block.getBeginNode() && OptEliminateGuards.getValue(activeGuards.graph().getOptions())) { 427 for (GuardNode guard : anchor.asNode().usages().filter(GuardNode.class)) { 428 if (activeGuards.isMarkedAndGrow(guard)) { 429 activeGuards.clear(guard); 430 } 431 } 432 } 433 } 434 435 } 436 437 @SuppressWarnings("try") process(final Block b, final NodeBitMap activeGuards, final AnchoringNode startAnchor)438 private AnchoringNode process(final Block b, final NodeBitMap activeGuards, final AnchoringNode startAnchor) { 439 440 final LoweringToolImpl loweringTool = new LoweringToolImpl(context, startAnchor, activeGuards, b.getBeginNode()); 441 442 // Lower the instructions of this block. 443 List<Node> nodes = schedule.nodesFor(b); 444 for (Node node : nodes) { 445 446 if (node.isDeleted()) { 447 // This case can happen when previous lowerings deleted nodes. 448 continue; 449 } 450 451 // Cache the next node to be able to reconstruct the previous of the next node 452 // after lowering. 453 FixedNode nextNode = null; 454 if (node instanceof FixedWithNextNode) { 455 nextNode = ((FixedWithNextNode) node).next(); 456 } else { 457 nextNode = loweringTool.lastFixedNode().next(); 458 } 459 460 if (node instanceof Lowerable) { 461 Collection<Node> unscheduledUsages = null; 462 assert (unscheduledUsages = getUnscheduledUsages(node)) != null; 463 Mark preLoweringMark = node.graph().getMark(); 464 try (DebugCloseable s = node.graph().withNodeSourcePosition(node)) { 465 ((Lowerable) node).lower(loweringTool); 466 } 467 if (loweringTool.guardAnchor.asNode().isDeleted()) { 468 // TODO nextNode could be deleted but this is not currently supported 469 assert nextNode.isAlive(); 470 loweringTool.guardAnchor = AbstractBeginNode.prevBegin(nextNode); 471 } 472 assert checkPostNodeLowering(node, loweringTool, preLoweringMark, unscheduledUsages); 473 } 474 475 if (!nextNode.isAlive()) { 476 // can happen when the rest of the block is killed by lowering 477 // (e.g. by an unconditional deopt) 478 break; 479 } else { 480 Node nextLastFixed = nextNode.predecessor(); 481 if (!(nextLastFixed instanceof FixedWithNextNode)) { 482 // insert begin node, to have a valid last fixed for next lowerable node. 483 // This is about lowering a FixedWithNextNode to a control split while this 484 // FixedWithNextNode is followed by some kind of BeginNode. 485 // For example the when a FixedGuard followed by a loop exit is lowered to a 486 // control-split + deopt. 487 AbstractBeginNode begin = node.graph().add(new BeginNode()); 488 nextLastFixed.replaceFirstSuccessor(nextNode, begin); 489 begin.setNext(nextNode); 490 nextLastFixed = begin; 491 } 492 loweringTool.setLastFixedNode((FixedWithNextNode) nextLastFixed); 493 } 494 } 495 return loweringTool.getCurrentGuardAnchor(); 496 } 497 498 /** 499 * Gets all usages of a floating, lowerable node that are unscheduled. 500 * <p> 501 * Given that the lowering of such nodes may introduce fixed nodes, they must be lowered in 502 * the context of a usage that dominates all other usages. The fixed nodes resulting from 503 * lowering are attached to the fixed node context of the dominating usage. This ensures the 504 * post-lowering graph still has a valid schedule. 505 * 506 * @param node a {@link Lowerable} node 507 */ getUnscheduledUsages(Node node)508 private Collection<Node> getUnscheduledUsages(Node node) { 509 List<Node> unscheduledUsages = new ArrayList<>(); 510 if (node instanceof FloatingNode) { 511 for (Node usage : node.usages()) { 512 if (usage instanceof ValueNode && !(usage instanceof PhiNode) && !(usage instanceof ProxyNode)) { 513 if (schedule.getCFG().getNodeToBlock().isNew(usage) || schedule.getCFG().blockFor(usage) == null) { 514 unscheduledUsages.add(usage); 515 } 516 } 517 } 518 } 519 return unscheduledUsages; 520 } 521 } 522 523 enum ProcessBlockState { 524 ST_ENTER, 525 ST_PROCESS, 526 ST_ENTER_ALWAYS_REACHED, 527 ST_LEAVE, 528 ST_PROCESS_ALWAYS_REACHED; 529 } 530 531 /** 532 * This state-machine resembles the following recursion: 533 * 534 * <pre> 535 * void processBlock(Block block) { 536 * preprocess(); 537 * // Process always reached block first. 538 * Block alwaysReachedBlock = block.getPostdominator(); 539 * if (alwaysReachedBlock != null && alwaysReachedBlock.getDominator() == block) { 540 * processBlock(alwaysReachedBlock); 541 * } 542 * 543 * // Now go for the other dominators. 544 * for (Block dominated : block.getDominated()) { 545 * if (dominated != alwaysReachedBlock) { 546 * assert dominated.getDominator() == block; 547 * processBlock(dominated); 548 * } 549 * } 550 * postprocess(); 551 * } 552 * </pre> 553 * 554 * This is necessary, as the recursive implementation quickly exceed the stack depth on SPARC. 555 * 556 * @param rootFrame contains the starting block. 557 */ processBlock(final Frame<?> rootFrame)558 public static void processBlock(final Frame<?> rootFrame) { 559 ProcessBlockState state = ST_PROCESS; 560 Frame<?> f = rootFrame; 561 while (f != null) { 562 ProcessBlockState nextState; 563 if (state == ST_PROCESS || state == ST_PROCESS_ALWAYS_REACHED) { 564 f.preprocess(); 565 nextState = state == ST_PROCESS_ALWAYS_REACHED ? ST_ENTER : ST_ENTER_ALWAYS_REACHED; 566 } else if (state == ST_ENTER_ALWAYS_REACHED) { 567 if (f.alwaysReachedBlock != null && f.alwaysReachedBlock.getDominator() == f.block) { 568 f = f.enterAlwaysReached(f.alwaysReachedBlock); 569 nextState = ST_PROCESS; 570 } else { 571 nextState = ST_ENTER; 572 } 573 } else if (state == ST_ENTER) { 574 if (f.dominated != null) { 575 Block n = f.dominated; 576 f.dominated = n.getDominatedSibling(); 577 if (n == f.alwaysReachedBlock) { 578 if (f.dominated != null) { 579 n = f.dominated; 580 f.dominated = n.getDominatedSibling(); 581 } else { 582 n = null; 583 } 584 } 585 if (n == null) { 586 nextState = ST_LEAVE; 587 } else { 588 f = f.enter(n); 589 assert f.block.getDominator() == f.parent.block; 590 nextState = ST_PROCESS; 591 } 592 } else { 593 nextState = ST_LEAVE; 594 } 595 } else if (state == ST_LEAVE) { 596 f.postprocess(); 597 f = f.parent; 598 nextState = ST_ENTER; 599 } else { 600 throw GraalError.shouldNotReachHere(); 601 } 602 state = nextState; 603 } 604 } 605 processBlockBounded(final Frame<?> rootFrame)606 public static void processBlockBounded(final Frame<?> rootFrame) { 607 ProcessBlockState state = ST_PROCESS; 608 Frame<?> f = rootFrame; 609 while (f != null) { 610 ProcessBlockState nextState; 611 if (state == ST_PROCESS || state == ST_PROCESS_ALWAYS_REACHED) { 612 f.preprocess(); 613 nextState = state == ST_PROCESS_ALWAYS_REACHED ? ST_ENTER : ST_ENTER_ALWAYS_REACHED; 614 } else if (state == ST_ENTER_ALWAYS_REACHED) { 615 if (f.alwaysReachedBlock != null && f.alwaysReachedBlock.getDominator() == f.block) { 616 Frame<?> continueRecur = f.enterAlwaysReached(f.alwaysReachedBlock); 617 if (continueRecur == null) { 618 // stop recursion here 619 f.postprocess(); 620 f = f.parent; 621 state = ST_ENTER; 622 continue; 623 } 624 f = continueRecur; 625 nextState = ST_PROCESS; 626 } else { 627 nextState = ST_ENTER; 628 } 629 } else if (state == ST_ENTER) { 630 if (f.dominated != null) { 631 Block n = f.dominated; 632 f.dominated = n.getDominatedSibling(); 633 if (n == f.alwaysReachedBlock) { 634 if (f.dominated != null) { 635 n = f.dominated; 636 f.dominated = n.getDominatedSibling(); 637 } else { 638 n = null; 639 } 640 } 641 if (n == null) { 642 nextState = ST_LEAVE; 643 } else { 644 Frame<?> continueRecur = f.enter(n); 645 if (continueRecur == null) { 646 // stop recursion here 647 f.postprocess(); 648 f = f.parent; 649 state = ST_ENTER; 650 continue; 651 } 652 f = continueRecur; 653 nextState = ST_PROCESS; 654 } 655 } else { 656 nextState = ST_LEAVE; 657 } 658 } else if (state == ST_LEAVE) { 659 f.postprocess(); 660 f = f.parent; 661 nextState = ST_ENTER; 662 } else { 663 throw GraalError.shouldNotReachHere(); 664 } 665 state = nextState; 666 } 667 } 668 669 public abstract static class Frame<T extends Frame<?>> { 670 protected final Block block; 671 final T parent; 672 Block dominated; 673 final Block alwaysReachedBlock; 674 Frame(Block block, T parent)675 public Frame(Block block, T parent) { 676 this.block = block; 677 this.alwaysReachedBlock = block.getPostdominator(); 678 this.dominated = block.getFirstDominated(); 679 this.parent = parent; 680 } 681 enterAlwaysReached(Block b)682 public Frame<?> enterAlwaysReached(Block b) { 683 return enter(b); 684 } 685 enter(Block b)686 public abstract Frame<?> enter(Block b); 687 preprocess()688 public abstract void preprocess(); 689 postprocess()690 public abstract void postprocess(); 691 } 692 693 } 694