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