1/*
2 * Copyright (c) 2011, 2015, 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 */
23package org.graalvm.compiler.nodes;
24
25import static org.graalvm.compiler.graph.iterators.NodePredicates.isNotA;
26
27import org.graalvm.compiler.core.common.type.IntegerStamp;
28import org.graalvm.compiler.graph.IterableNodeType;
29import org.graalvm.compiler.graph.Node;
30import org.graalvm.compiler.graph.NodeClass;
31import org.graalvm.compiler.graph.iterators.NodeIterable;
32import org.graalvm.compiler.graph.spi.SimplifierTool;
33import org.graalvm.compiler.nodeinfo.InputType;
34import org.graalvm.compiler.nodeinfo.NodeInfo;
35import org.graalvm.compiler.nodes.calc.AddNode;
36import org.graalvm.compiler.nodes.extended.GuardingNode;
37import org.graalvm.compiler.nodes.spi.LIRLowerable;
38import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
39import org.graalvm.compiler.nodes.util.GraphUtil;
40
41@NodeInfo
42public final class LoopBeginNode extends AbstractMergeNode implements IterableNodeType, LIRLowerable {
43
44    public static final NodeClass<LoopBeginNode> TYPE = NodeClass.create(LoopBeginNode.class);
45    protected double loopFrequency;
46    protected double loopOrigFrequency;
47    protected int nextEndIndex;
48    protected int unswitches;
49    protected int splits;
50    protected int inversionCount;
51    protected LoopType loopType;
52    protected int unrollFactor;
53
54    public enum LoopType {
55        SIMPLE_LOOP,
56        PRE_LOOP,
57        MAIN_LOOP,
58        POST_LOOP
59    }
60
61    /** See {@link LoopEndNode#canSafepoint} for more information. */
62    boolean canEndsSafepoint;
63
64    @OptionalInput(InputType.Guard) GuardingNode overflowGuard;
65
66    public LoopBeginNode() {
67        super(TYPE);
68        loopFrequency = 1;
69        loopOrigFrequency = 1;
70        unswitches = 0;
71        splits = 0;
72        this.canEndsSafepoint = true;
73        loopType = LoopType.SIMPLE_LOOP;
74        unrollFactor = 1;
75    }
76
77    public boolean isSimpleLoop() {
78        return (loopType == LoopType.SIMPLE_LOOP);
79    }
80
81    public void setPreLoop() {
82        assert isSimpleLoop();
83        loopType = LoopType.PRE_LOOP;
84    }
85
86    public boolean isPreLoop() {
87        return (loopType == LoopType.PRE_LOOP);
88    }
89
90    public void setMainLoop() {
91        assert isSimpleLoop();
92        loopType = LoopType.MAIN_LOOP;
93    }
94
95    public boolean isMainLoop() {
96        return (loopType == LoopType.MAIN_LOOP);
97    }
98
99    public void setPostLoop() {
100        assert isSimpleLoop();
101        loopType = LoopType.POST_LOOP;
102    }
103
104    public boolean isPostLoop() {
105        return (loopType == LoopType.POST_LOOP);
106    }
107
108    public int getUnrollFactor() {
109        return unrollFactor;
110    }
111
112    public void setUnrollFactor(int currentUnrollFactor) {
113        unrollFactor = currentUnrollFactor;
114    }
115
116    /** Disables safepoint for the whole loop, i.e., for all {@link LoopEndNode loop ends}. */
117    public void disableSafepoint() {
118        /* Store flag locally in case new loop ends are created later on. */
119        this.canEndsSafepoint = false;
120        /* Propagate flag to all existing loop ends. */
121        for (LoopEndNode loopEnd : loopEnds()) {
122            loopEnd.disableSafepoint();
123        }
124    }
125
126    public double loopOrigFrequency() {
127        return loopOrigFrequency;
128    }
129
130    public void setLoopOrigFrequency(double loopOrigFrequency) {
131        assert loopOrigFrequency >= 0;
132        this.loopOrigFrequency = loopOrigFrequency;
133    }
134
135    public double loopFrequency() {
136        return loopFrequency;
137    }
138
139    public void setLoopFrequency(double loopFrequency) {
140        assert loopFrequency >= 0;
141        this.loopFrequency = loopFrequency;
142    }
143
144    /**
145     * Returns the <b>unordered</b> set of {@link LoopEndNode} that correspond to back-edges for
146     * this loop. The order of the back-edges is unspecified, if you need to get an ordering
147     * compatible for {@link PhiNode} creation, use {@link #orderedLoopEnds()}.
148     *
149     * @return the set of {@code LoopEndNode} that correspond to back-edges for this loop
150     */
151    public NodeIterable<LoopEndNode> loopEnds() {
152        return usages().filter(LoopEndNode.class);
153    }
154
155    public NodeIterable<LoopExitNode> loopExits() {
156        return usages().filter(LoopExitNode.class);
157    }
158
159    @Override
160    public NodeIterable<Node> anchored() {
161        return super.anchored().filter(isNotA(LoopEndNode.class).nor(LoopExitNode.class));
162    }
163
164    /**
165     * Returns the set of {@link LoopEndNode} that correspond to back-edges for this loop, in
166     * increasing {@link #phiPredecessorIndex} order. This method is suited to create new loop
167     * {@link PhiNode}.<br>
168     *
169     * For example a new PhiNode may be added as follow:
170     *
171     * <pre>
172     * PhiNode phi = new ValuePhiNode(stamp, loop);
173     * phi.addInput(forwardEdgeValue);
174     * for (LoopEndNode loopEnd : loop.orderedLoopEnds()) {
175     *     phi.addInput(backEdgeValue(loopEnd));
176     * }
177     * </pre>
178     *
179     * @return the set of {@code LoopEndNode} that correspond to back-edges for this loop
180     */
181    public LoopEndNode[] orderedLoopEnds() {
182        LoopEndNode[] result = new LoopEndNode[this.getLoopEndCount()];
183        for (LoopEndNode end : loopEnds()) {
184            result[end.endIndex()] = end;
185        }
186        return result;
187    }
188
189    public boolean isSingleEntryLoop() {
190        return (forwardEndCount() == 1);
191    }
192
193    public AbstractEndNode forwardEnd() {
194        assert forwardEndCount() == 1;
195        return forwardEndAt(0);
196    }
197
198    public int splits() {
199        return splits;
200    }
201
202    public void incrementSplits() {
203        splits++;
204    }
205
206    @Override
207    public void generate(NodeLIRBuilderTool gen) {
208        // Nothing to emit, since this is node is used for structural purposes only.
209    }
210
211    @Override
212    protected void deleteEnd(AbstractEndNode end) {
213        if (end instanceof LoopEndNode) {
214            LoopEndNode loopEnd = (LoopEndNode) end;
215            loopEnd.setLoopBegin(null);
216            int idx = loopEnd.endIndex();
217            for (LoopEndNode le : loopEnds()) {
218                int leIdx = le.endIndex();
219                assert leIdx != idx;
220                if (leIdx > idx) {
221                    le.setEndIndex(leIdx - 1);
222                }
223            }
224            nextEndIndex--;
225        } else {
226            super.deleteEnd(end);
227        }
228    }
229
230    @Override
231    public int phiPredecessorCount() {
232        return forwardEndCount() + loopEnds().count();
233    }
234
235    @Override
236    public int phiPredecessorIndex(AbstractEndNode pred) {
237        if (pred instanceof LoopEndNode) {
238            LoopEndNode loopEnd = (LoopEndNode) pred;
239            if (loopEnd.loopBegin() == this) {
240                assert loopEnd.endIndex() < loopEnds().count() : "Invalid endIndex : " + loopEnd;
241                return loopEnd.endIndex() + forwardEndCount();
242            }
243        } else {
244            return super.forwardEndIndex((EndNode) pred);
245        }
246        throw ValueNodeUtil.shouldNotReachHere("unknown pred : " + pred);
247    }
248
249    @Override
250    public AbstractEndNode phiPredecessorAt(int index) {
251        if (index < forwardEndCount()) {
252            return forwardEndAt(index);
253        }
254        for (LoopEndNode end : loopEnds()) {
255            int idx = index - forwardEndCount();
256            assert idx >= 0;
257            if (end.endIndex() == idx) {
258                return end;
259            }
260        }
261        throw ValueNodeUtil.shouldNotReachHere();
262    }
263
264    @Override
265    public boolean verify() {
266        assertTrue(loopEnds().isNotEmpty(), "missing loopEnd");
267        return super.verify();
268    }
269
270    int nextEndIndex() {
271        return nextEndIndex++;
272    }
273
274    public int getLoopEndCount() {
275        return nextEndIndex;
276    }
277
278    public int unswitches() {
279        return unswitches;
280    }
281
282    public void incrementUnswitches() {
283        unswitches++;
284    }
285
286    public int getInversionCount() {
287        return inversionCount;
288    }
289
290    public void setInversionCount(int count) {
291        inversionCount = count;
292    }
293
294    @Override
295    public void simplify(SimplifierTool tool) {
296        canonicalizePhis(tool);
297    }
298
299    public boolean isLoopExit(AbstractBeginNode begin) {
300        return begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == this;
301    }
302
303    public LoopExitNode getSingleLoopExit() {
304        assert loopExits().count() == 1;
305        return loopExits().first();
306    }
307
308    public LoopEndNode getSingleLoopEnd() {
309        assert loopEnds().count() == 1;
310        return loopEnds().first();
311    }
312
313    public void removeExits() {
314        for (LoopExitNode loopexit : loopExits().snapshot()) {
315            loopexit.removeProxies();
316            FrameState loopStateAfter = loopexit.stateAfter();
317            graph().replaceFixedWithFixed(loopexit, graph().add(new BeginNode()));
318            if (loopStateAfter != null) {
319                GraphUtil.tryKillUnused(loopStateAfter);
320            }
321        }
322    }
323
324    public GuardingNode getOverflowGuard() {
325        return overflowGuard;
326    }
327
328    public void setOverflowGuard(GuardingNode overflowGuard) {
329        updateUsagesInterface(this.overflowGuard, overflowGuard);
330        this.overflowGuard = overflowGuard;
331    }
332
333    private static final int NO_INCREMENT = Integer.MIN_VALUE;
334
335    /**
336     * Returns an array with one entry for each input of the phi, which is either
337     * {@link #NO_INCREMENT} or the increment, i.e., the value by which the phi is incremented in
338     * the corresponding branch.
339     */
340    private static int[] getSelfIncrements(PhiNode phi) {
341        int[] selfIncrement = new int[phi.valueCount()];
342        for (int i = 0; i < phi.valueCount(); i++) {
343            ValueNode input = phi.valueAt(i);
344            long increment = NO_INCREMENT;
345            if (input != null && input instanceof AddNode && input.stamp() instanceof IntegerStamp) {
346                AddNode add = (AddNode) input;
347                if (add.getX() == phi && add.getY().isConstant()) {
348                    increment = add.getY().asJavaConstant().asLong();
349                } else if (add.getY() == phi && add.getX().isConstant()) {
350                    increment = add.getX().asJavaConstant().asLong();
351                }
352            } else if (input == phi) {
353                increment = 0;
354            }
355            if (increment < Integer.MIN_VALUE || increment > Integer.MAX_VALUE || increment == NO_INCREMENT) {
356                increment = NO_INCREMENT;
357            }
358            selfIncrement[i] = (int) increment;
359        }
360        return selfIncrement;
361    }
362
363    /**
364     * Coalesces loop phis that represent the same value (which is not handled by normal Global
365     * Value Numbering).
366     */
367    public void canonicalizePhis(SimplifierTool tool) {
368        int phiCount = phis().count();
369        if (phiCount > 1) {
370            int phiInputCount = phiPredecessorCount();
371            int phiIndex = 0;
372            int[][] selfIncrement = new int[phiCount][];
373            PhiNode[] phis = this.phis().snapshot().toArray(new PhiNode[phiCount]);
374
375            for (phiIndex = 0; phiIndex < phiCount; phiIndex++) {
376                PhiNode phi = phis[phiIndex];
377                if (phi != null) {
378                    nextPhi: for (int otherPhiIndex = phiIndex + 1; otherPhiIndex < phiCount; otherPhiIndex++) {
379                        PhiNode otherPhi = phis[otherPhiIndex];
380                        if (otherPhi == null || phi.getNodeClass() != otherPhi.getNodeClass() || !phi.valueEquals(otherPhi)) {
381                            continue nextPhi;
382                        }
383                        if (selfIncrement[phiIndex] == null) {
384                            selfIncrement[phiIndex] = getSelfIncrements(phi);
385                        }
386                        if (selfIncrement[otherPhiIndex] == null) {
387                            selfIncrement[otherPhiIndex] = getSelfIncrements(otherPhi);
388                        }
389                        int[] phiIncrement = selfIncrement[phiIndex];
390                        int[] otherPhiIncrement = selfIncrement[otherPhiIndex];
391                        for (int inputIndex = 0; inputIndex < phiInputCount; inputIndex++) {
392                            if (phiIncrement[inputIndex] == NO_INCREMENT) {
393                                if (phi.valueAt(inputIndex) != otherPhi.valueAt(inputIndex)) {
394                                    continue nextPhi;
395                                }
396                            }
397                            if (phiIncrement[inputIndex] != otherPhiIncrement[inputIndex]) {
398                                continue nextPhi;
399                            }
400                        }
401                        if (tool != null) {
402                            tool.addToWorkList(otherPhi.usages());
403                        }
404                        otherPhi.replaceAtUsages(phi);
405                        GraphUtil.killWithUnusedFloatingInputs(otherPhi);
406                        phis[otherPhiIndex] = null;
407                    }
408                }
409            }
410        }
411    }
412}
413