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 &amp;&amp; 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 }