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
100 protected DummyGuardHandle(GuardingNode guard) {
101 super(TYPE, StampFactory.forVoid());
102 this.guard = guard;
103 }
104
105 @Override
106 public GuardingNode getGuard() {
107 return guard;
108 }
109
110 @Override
111 public void setGuard(GuardingNode guard) {
112 updateUsagesInterface(this.guard, guard);
113 this.guard = guard;
114 }
115
116 @Override
117 public ValueNode asNode() {
118 return this;
119 }
120 }
121
122 @Override
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
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
142 public LoweringStage getLoweringStage() {
143 return loweringStage;
144 }
145
146 @Override
147 public ConstantReflectionProvider getConstantReflection() {
148 return context.getConstantReflection();
149 }
150
151 @Override
152 public ConstantFieldProvider getConstantFieldProvider() {
153 return context.getConstantFieldProvider();
154 }
155
156 @Override
157 public MetaAccessProvider getMetaAccess() {
158 return context.getMetaAccess();
159 }
160
161 @Override
162 public LoweringProvider getLowerer() {
163 return context.getLowerer();
164 }
165
166 @Override
167 public Replacements getReplacements() {
168 return context.getReplacements();
169 }
170
171 @Override
172 public AnchoringNode getCurrentGuardAnchor() {
173 return guardAnchor;
174 }
175
176 @Override
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
182 public StampProvider getStampProvider() {
183 return context.getStampProvider();
184 }
185
186 @Override
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
215 public FixedWithNextNode lastFixedNode() {
216 return lastFixedNode;
217 }
218
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
228 public LoweringPhase(CanonicalizerPhase canonicalizer, LoweringTool.LoweringStage loweringStage) {
229 this.canonicalizer = canonicalizer;
230 this.loweringStage = loweringStage;
231 }
232
233 @Override
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 */
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
253 protected void run(final StructuredGraph graph, PhaseContext context) {
254 lower(graph, context, LoweringMode.LOWERING);
255 assert checkPostLowering(graph, context);
256 }
257
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 */
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
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
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
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
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
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
404 public void preprocess() {
405 this.anchor = Round.this.process(block, activeGuards, anchor);
406 }
407
408 @Override
409 public ProcessFrame enter(Block b) {
410 return new ProcessFrame(b, activeGuards, b.getBeginNode(), this);
411 }
412
413 @Override
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
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")
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 */
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 */
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
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
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
682 public Frame<?> enterAlwaysReached(Block b) {
683 return enter(b);
684 }
685
686 public abstract Frame<?> enter(Block b);
687
688 public abstract void preprocess();
689
690 public abstract void postprocess();
691 }
692
693 }