001/*
002 * Copyright (c) 2011, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.phases.common;
024
025import static com.oracle.graal.compiler.common.GraalOptions.*;
026import static com.oracle.graal.phases.common.LoweringPhase.ProcessBlockState.*;
027
028import java.util.*;
029
030import jdk.internal.jvmci.common.*;
031import jdk.internal.jvmci.meta.*;
032
033import com.oracle.graal.compiler.common.type.*;
034import com.oracle.graal.graph.Graph.Mark;
035import com.oracle.graal.graph.*;
036import com.oracle.graal.graph.iterators.*;
037import com.oracle.graal.nodeinfo.*;
038import com.oracle.graal.nodes.*;
039import com.oracle.graal.nodes.calc.*;
040import com.oracle.graal.nodes.cfg.*;
041import com.oracle.graal.nodes.extended.*;
042import com.oracle.graal.nodes.spi.*;
043import com.oracle.graal.phases.*;
044import com.oracle.graal.phases.schedule.*;
045import com.oracle.graal.phases.tiers.*;
046
047/**
048 * Processes all {@link Lowerable} nodes to do their lowering.
049 */
050public class LoweringPhase extends BasePhase<PhaseContext> {
051
052    @NodeInfo
053    static final class DummyGuardHandle extends ValueNode implements GuardedNode {
054        public static final NodeClass<DummyGuardHandle> TYPE = NodeClass.create(DummyGuardHandle.class);
055        @Input(InputType.Guard) GuardingNode guard;
056
057        public DummyGuardHandle(GuardingNode guard) {
058            super(TYPE, StampFactory.forVoid());
059            this.guard = guard;
060        }
061
062        public GuardingNode getGuard() {
063            return guard;
064        }
065
066        public void setGuard(GuardingNode guard) {
067            updateUsagesInterface(this.guard, guard);
068            this.guard = guard;
069        }
070
071        @Override
072        public ValueNode asNode() {
073            return this;
074        }
075    }
076
077    final class LoweringToolImpl implements LoweringTool {
078
079        private final PhaseContext context;
080        private final NodeBitMap activeGuards;
081        private AnchoringNode guardAnchor;
082        private FixedWithNextNode lastFixedNode;
083
084        public LoweringToolImpl(PhaseContext context, AnchoringNode guardAnchor, NodeBitMap activeGuards, FixedWithNextNode lastFixedNode) {
085            this.context = context;
086            this.guardAnchor = guardAnchor;
087            this.activeGuards = activeGuards;
088            this.lastFixedNode = lastFixedNode;
089        }
090
091        @Override
092        public LoweringStage getLoweringStage() {
093            return loweringStage;
094        }
095
096        @Override
097        public ConstantReflectionProvider getConstantReflection() {
098            return context.getConstantReflection();
099        }
100
101        @Override
102        public MetaAccessProvider getMetaAccess() {
103            return context.getMetaAccess();
104        }
105
106        @Override
107        public LoweringProvider getLowerer() {
108            return context.getLowerer();
109        }
110
111        @Override
112        public Replacements getReplacements() {
113            return context.getReplacements();
114        }
115
116        @Override
117        public AnchoringNode getCurrentGuardAnchor() {
118            return guardAnchor;
119        }
120
121        @Override
122        public GuardingNode createGuard(FixedNode before, LogicNode condition, DeoptimizationReason deoptReason, DeoptimizationAction action) {
123            return createGuard(before, condition, deoptReason, action, JavaConstant.NULL_POINTER, false);
124        }
125
126        public StampProvider getStampProvider() {
127            return context.getStampProvider();
128        }
129
130        @Override
131        public GuardingNode createGuard(FixedNode before, LogicNode condition, DeoptimizationReason deoptReason, DeoptimizationAction action, JavaConstant speculation, boolean negated) {
132            if (OptEliminateGuards.getValue()) {
133                for (Node usage : condition.usages()) {
134                    if (!activeGuards.isNew(usage) && activeGuards.isMarked(usage) && ((GuardNode) usage).isNegated() == negated) {
135                        return (GuardNode) usage;
136                    }
137                }
138            }
139            StructuredGraph graph = before.graph();
140            if (!condition.graph().getGuardsStage().allowsFloatingGuards()) {
141                FixedGuardNode fixedGuard = graph.add(new FixedGuardNode(condition, deoptReason, action, speculation, negated));
142                graph.addBeforeFixed(before, fixedGuard);
143                DummyGuardHandle handle = graph.add(new DummyGuardHandle(fixedGuard));
144                fixedGuard.lower(this);
145                GuardingNode result = handle.getGuard();
146                handle.safeDelete();
147                return result;
148            } else {
149                GuardNode newGuard = graph.unique(new GuardNode(condition, guardAnchor, deoptReason, action, negated, speculation));
150                if (OptEliminateGuards.getValue()) {
151                    activeGuards.markAndGrow(newGuard);
152                }
153                return newGuard;
154            }
155        }
156
157        public FixedWithNextNode lastFixedNode() {
158            return lastFixedNode;
159        }
160
161        private void setLastFixedNode(FixedWithNextNode n) {
162            assert n.isAlive() : n;
163            lastFixedNode = n;
164        }
165    }
166
167    private final CanonicalizerPhase canonicalizer;
168    private final LoweringTool.LoweringStage loweringStage;
169
170    public LoweringPhase(CanonicalizerPhase canonicalizer, LoweringTool.LoweringStage loweringStage) {
171        this.canonicalizer = canonicalizer;
172        this.loweringStage = loweringStage;
173    }
174
175    /**
176     * Checks that second lowering of a given graph did not introduce any new nodes.
177     *
178     * @param graph a graph that was just {@linkplain #lower lowered}
179     * @throws AssertionError if the check fails
180     */
181    private boolean checkPostLowering(StructuredGraph graph, PhaseContext context) {
182        Mark expectedMark = graph.getMark();
183        lower(graph, context, 1);
184        Mark mark = graph.getMark();
185        assert mark.equals(expectedMark) : graph + ": a second round in the current lowering phase introduced these new nodes: " + graph.getNewNodes(expectedMark).snapshot();
186        return true;
187    }
188
189    @Override
190    protected void run(final StructuredGraph graph, PhaseContext context) {
191        lower(graph, context, 0);
192        assert checkPostLowering(graph, context);
193    }
194
195    private void lower(StructuredGraph graph, PhaseContext context, int i) {
196        IncrementalCanonicalizerPhase<PhaseContext> incrementalCanonicalizer = new IncrementalCanonicalizerPhase<>(canonicalizer);
197        incrementalCanonicalizer.appendPhase(new Round(i, context));
198        incrementalCanonicalizer.apply(graph, context);
199        assert graph.verify();
200    }
201
202    /**
203     * Checks that lowering of a given node did not introduce any new {@link Lowerable} nodes that
204     * could be lowered in the current {@link LoweringPhase}. Such nodes must be recursively lowered
205     * as part of lowering {@code node}.
206     *
207     * @param node a node that was just lowered
208     * @param preLoweringMark the graph mark before {@code node} was lowered
209     * @param unscheduledUsages set of {@code node}'s usages that were unscheduled before it was
210     *            lowered
211     * @throws AssertionError if the check fails
212     */
213    private static boolean checkPostNodeLowering(Node node, LoweringToolImpl loweringTool, Mark preLoweringMark, Collection<Node> unscheduledUsages) {
214        StructuredGraph graph = (StructuredGraph) node.graph();
215        Mark postLoweringMark = graph.getMark();
216        NodeIterable<Node> newNodesAfterLowering = graph.getNewNodes(preLoweringMark);
217        if (node instanceof FloatingNode) {
218            if (!unscheduledUsages.isEmpty()) {
219                for (Node n : newNodesAfterLowering) {
220                    assert !(n instanceof FixedNode) : node.graph() + ": cannot lower floatable node " + node + " as it introduces fixed node(s) but has the following unscheduled usages: " +
221                                    unscheduledUsages;
222                }
223            }
224        }
225        for (Node n : newNodesAfterLowering) {
226            if (n instanceof Lowerable) {
227                ((Lowerable) n).lower(loweringTool);
228                Mark mark = graph.getMark();
229                assert postLoweringMark.equals(mark) : graph + ": lowering of " + node + " produced lowerable " + n + " that should have been recursively lowered as it introduces these new nodes: " +
230                                graph.getNewNodes(postLoweringMark).snapshot();
231            }
232        }
233        return true;
234    }
235
236    private final class Round extends Phase {
237
238        private final PhaseContext context;
239        private final SchedulePhase schedule;
240        private final int iteration;
241
242        private Round(int iteration, PhaseContext context) {
243            this.iteration = iteration;
244            this.context = context;
245            this.schedule = new SchedulePhase();
246        }
247
248        @Override
249        protected CharSequence createName() {
250            return "LoweringIteration" + iteration;
251        }
252
253        @Override
254        public void run(StructuredGraph graph) {
255            schedule.apply(graph, false);
256            schedule.getCFG().computePostdominators();
257            Block startBlock = schedule.getCFG().getStartBlock();
258            ProcessFrame rootFrame = new ProcessFrame(startBlock, graph.createNodeBitMap(), startBlock.getBeginNode(), null);
259            LoweringPhase.processBlock(rootFrame);
260        }
261
262        private class ProcessFrame extends Frame<ProcessFrame> {
263            private final NodeBitMap activeGuards;
264            private AnchoringNode anchor;
265
266            public ProcessFrame(Block block, NodeBitMap activeGuards, AnchoringNode anchor, ProcessFrame parent) {
267                super(block, parent);
268                this.activeGuards = activeGuards;
269                this.anchor = anchor;
270            }
271
272            @Override
273            public void preprocess() {
274                this.anchor = Round.this.process(block, activeGuards, anchor);
275            }
276
277            @Override
278            public ProcessFrame enter(Block b) {
279                return new ProcessFrame(b, activeGuards, b.getBeginNode(), this);
280            }
281
282            @Override
283            public Frame<?> enterAlwaysReached(Block b) {
284                AnchoringNode newAnchor = anchor;
285                if (parent != null && b.getLoop() != parent.block.getLoop() && !b.isLoopHeader()) {
286                    // We are exiting a loop => cannot reuse the anchor without inserting loop
287                    // proxies.
288                    newAnchor = b.getBeginNode();
289                }
290                return new ProcessFrame(b, activeGuards, newAnchor, this);
291            }
292
293            @Override
294            public void postprocess() {
295                if (anchor != null && OptEliminateGuards.getValue()) {
296                    for (GuardNode guard : anchor.asNode().usages().filter(GuardNode.class)) {
297                        if (activeGuards.isMarkedAndGrow(guard)) {
298                            activeGuards.clear(guard);
299                        }
300                    }
301                }
302            }
303        }
304
305        private AnchoringNode process(final Block b, final NodeBitMap activeGuards, final AnchoringNode startAnchor) {
306
307            final LoweringToolImpl loweringTool = new LoweringToolImpl(context, startAnchor, activeGuards, b.getBeginNode());
308
309            // Lower the instructions of this block.
310            List<Node> nodes = schedule.nodesFor(b);
311            for (Node node : nodes) {
312
313                if (node.isDeleted()) {
314                    // This case can happen when previous lowerings deleted nodes.
315                    continue;
316                }
317
318                // Cache the next node to be able to reconstruct the previous of the next node
319                // after lowering.
320                FixedNode nextNode = null;
321                if (node instanceof FixedWithNextNode) {
322                    nextNode = ((FixedWithNextNode) node).next();
323                } else {
324                    nextNode = loweringTool.lastFixedNode().next();
325                }
326
327                if (node instanceof Lowerable) {
328                    Collection<Node> unscheduledUsages = null;
329                    assert (unscheduledUsages = getUnscheduledUsages(node)) != null;
330                    Mark preLoweringMark = node.graph().getMark();
331                    ((Lowerable) node).lower(loweringTool);
332                    if (loweringTool.guardAnchor.asNode().isDeleted()) {
333                        // TODO nextNode could be deleted but this is not currently supported
334                        assert nextNode.isAlive();
335                        loweringTool.guardAnchor = AbstractBeginNode.prevBegin(nextNode);
336                    }
337                    assert checkPostNodeLowering(node, loweringTool, preLoweringMark, unscheduledUsages);
338                }
339
340                if (!nextNode.isAlive()) {
341                    // can happen when the rest of the block is killed by lowering
342                    // (e.g. by an unconditional deopt)
343                    break;
344                } else {
345                    Node nextLastFixed = nextNode.predecessor();
346                    if (!(nextLastFixed instanceof FixedWithNextNode)) {
347                        // insert begin node, to have a valid last fixed for next lowerable node.
348                        // This is about lowering a FixedWithNextNode to a control split while this
349                        // FixedWithNextNode is followed by some kind of BeginNode.
350                        // For example the when a FixedGuard followed by a loop exit is lowered to a
351                        // control-split + deopt.
352                        AbstractBeginNode begin = node.graph().add(new BeginNode());
353                        nextLastFixed.replaceFirstSuccessor(nextNode, begin);
354                        begin.setNext(nextNode);
355                        nextLastFixed = begin;
356                    }
357                    loweringTool.setLastFixedNode((FixedWithNextNode) nextLastFixed);
358                }
359            }
360            return loweringTool.getCurrentGuardAnchor();
361        }
362
363        /**
364         * Gets all usages of a floating, lowerable node that are unscheduled.
365         * <p>
366         * Given that the lowering of such nodes may introduce fixed nodes, they must be lowered in
367         * the context of a usage that dominates all other usages. The fixed nodes resulting from
368         * lowering are attached to the fixed node context of the dominating usage. This ensures the
369         * post-lowering graph still has a valid schedule.
370         *
371         * @param node a {@link Lowerable} node
372         */
373        private Collection<Node> getUnscheduledUsages(Node node) {
374            List<Node> unscheduledUsages = new ArrayList<>();
375            if (node instanceof FloatingNode) {
376                for (Node usage : node.usages()) {
377                    if (usage instanceof ValueNode) {
378                        if (schedule.getCFG().getNodeToBlock().isNew(usage) || schedule.getCFG().blockFor(usage) == null) {
379                            unscheduledUsages.add(usage);
380                        }
381                    }
382                }
383            }
384            return unscheduledUsages;
385        }
386    }
387
388    enum ProcessBlockState {
389        ST_ENTER,
390        ST_PROCESS,
391        ST_ENTER_ALWAYS_REACHED,
392        ST_LEAVE,
393        ST_PROCESS_ALWAYS_REACHED;
394    }
395
396    /**
397     * This state-machine resembles the following recursion:
398     *
399     * <pre>
400     * void processBlock(Block block) {
401     *     preprocess();
402     *     // Process always reached block first.
403     *     Block alwaysReachedBlock = block.getPostdominator();
404     *     if (alwaysReachedBlock != null &amp;&amp; alwaysReachedBlock.getDominator() == block) {
405     *         processBlock(alwaysReachedBlock);
406     *     }
407     * 
408     *     // Now go for the other dominators.
409     *     for (Block dominated : block.getDominated()) {
410     *         if (dominated != alwaysReachedBlock) {
411     *             assert dominated.getDominator() == block;
412     *             processBlock(dominated);
413     *         }
414     *     }
415     *     postprocess();
416     * }
417     * </pre>
418     *
419     * This is necessary, as the recursive implementation quickly exceed the stack depth on SPARC.
420     *
421     * @param rootFrame contains the starting block.
422     */
423    public static void processBlock(final Frame<?> rootFrame) {
424        ProcessBlockState state = ST_PROCESS;
425        Frame<?> f = rootFrame;
426        while (f != null) {
427            ProcessBlockState nextState;
428            if (state == ST_PROCESS || state == ST_PROCESS_ALWAYS_REACHED) {
429                f.preprocess();
430                nextState = state == ST_PROCESS_ALWAYS_REACHED ? ST_ENTER : ST_ENTER_ALWAYS_REACHED;
431            } else if (state == ST_ENTER_ALWAYS_REACHED) {
432                if (f.alwaysReachedBlock != null && f.alwaysReachedBlock.getDominator() == f.block) {
433                    f = f.enterAlwaysReached(f.alwaysReachedBlock);
434                    nextState = ST_PROCESS;
435                } else {
436                    nextState = ST_ENTER;
437                }
438            } else if (state == ST_ENTER) {
439                if (f.dominated.hasNext()) {
440                    Block n = f.dominated.next();
441                    if (n == f.alwaysReachedBlock) {
442                        if (f.dominated.hasNext()) {
443                            n = f.dominated.next();
444                        } else {
445                            n = null;
446                        }
447                    }
448                    if (n == null) {
449                        nextState = ST_LEAVE;
450                    } else {
451                        f = f.enter(n);
452                        assert f.block.getDominator() == f.parent.block;
453                        nextState = ST_PROCESS;
454                    }
455                } else {
456                    nextState = ST_LEAVE;
457                }
458            } else if (state == ST_LEAVE) {
459                f.postprocess();
460                f = f.parent;
461                nextState = ST_ENTER;
462            } else {
463                throw JVMCIError.shouldNotReachHere();
464            }
465            state = nextState;
466        }
467    }
468
469    public abstract static class Frame<T extends Frame<?>> {
470        final Block block;
471        final T parent;
472        Iterator<Block> dominated;
473        final Block alwaysReachedBlock;
474
475        public Frame(Block block, T parent) {
476            super();
477            this.block = block;
478            this.alwaysReachedBlock = block.getPostdominator();
479            this.dominated = block.getDominated().iterator();
480            this.parent = parent;
481        }
482
483        public Frame<?> enterAlwaysReached(Block b) {
484            return enter(b);
485        }
486
487        public abstract Frame<?> enter(Block b);
488
489        public abstract void preprocess();
490
491        public abstract void postprocess();
492    }
493
494}