Source code

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.nodes;
024
025import static com.oracle.graal.graph.iterators.NodePredicates.*;
026
027import java.util.*;
028
029import com.oracle.graal.compiler.common.type.*;
030import com.oracle.graal.graph.*;
031import com.oracle.graal.graph.iterators.*;
032import com.oracle.graal.graph.spi.*;
033import com.oracle.graal.nodeinfo.*;
034import com.oracle.graal.nodes.calc.*;
035import com.oracle.graal.nodes.extended.*;
036import com.oracle.graal.nodes.spi.*;
037import com.oracle.graal.nodes.util.*;
038
039@NodeInfo
040public final class LoopBeginNode extends AbstractMergeNode implements IterableNodeType, LIRLowerable {
041
042    public static final NodeClass<LoopBeginNode> TYPE = NodeClass.create(LoopBeginNode.class);
043    protected double loopFrequency;
044    protected int nextEndIndex;
045    protected int unswitches;
046    protected int inversionCount;
047
048    @OptionalInput(InputType.Guard) GuardingNode overflowGuard;
049
050    public LoopBeginNode() {
051        super(TYPE);
052        loopFrequency = 1;
053    }
054
055    public double loopFrequency() {
056        return loopFrequency;
057    }
058
059    public void setLoopFrequency(double loopFrequency) {
060        assert loopFrequency >= 0;
061        this.loopFrequency = loopFrequency;
062    }
063
064    /**
065     * Returns the <b>unordered</b> set of {@link LoopEndNode} that correspond to back-edges for
066     * this loop. The order of the back-edges is unspecified, if you need to get an ordering
067     * compatible for {@link PhiNode} creation, use {@link #orderedLoopEnds()}.
068     *
069     * @return the set of {@code LoopEndNode} that correspond to back-edges for this loop
070     */
071    public NodeIterable<LoopEndNode> loopEnds() {
072        return usages().filter(LoopEndNode.class);
073    }
074
075    public NodeIterable<LoopExitNode> loopExits() {
076        return usages().filter(LoopExitNode.class);
077    }
078
079    @Override
080    public NodeIterable<Node> anchored() {
081        return super.anchored().filter(isNotA(LoopEndNode.class).nor(LoopExitNode.class));
082    }
083
084    /**
085     * Returns the set of {@link LoopEndNode} that correspond to back-edges for this loop, in
086     * increasing {@link #phiPredecessorIndex} order. This method is suited to create new loop
087     * {@link PhiNode}.<br>
088     *
089     * For example a new PhiNode may be added as follow:
090     *
091     * <pre>
092     * PhiNode phi = new ValuePhiNode(stamp, loop);
093     * phi.addInput(forwardEdgeValue);
094     * for (LoopEndNode loopEnd : loop.orderedLoopEnds()) {
095     *     phi.addInput(backEdgeValue(loopEnd));
096     * }
097     * </pre>
098     *
099     * @return the set of {@code LoopEndNode} that correspond to back-edges for this loop
100     */
101    public LoopEndNode[] orderedLoopEnds() {
102        LoopEndNode[] result = new LoopEndNode[this.getLoopEndCount()];
103        for (LoopEndNode end : loopEnds()) {
104            result[end.endIndex()] = end;
105        }
106        return result;
107    }
108
109    public AbstractEndNode forwardEnd() {
110        assert forwardEndCount() == 1;
111        return forwardEndAt(0);
112    }
113
114    @Override
115    public void generate(NodeLIRBuilderTool gen) {
116        // Nothing to emit, since this is node is used for structural purposes only.
117    }
118
119    @Override
120    protected void deleteEnd(AbstractEndNode end) {
121        if (end instanceof LoopEndNode) {
122            LoopEndNode loopEnd = (LoopEndNode) end;
123            loopEnd.setLoopBegin(null);
124            int idx = loopEnd.endIndex();
125            for (LoopEndNode le : loopEnds()) {
126                int leIdx = le.endIndex();
127                assert leIdx != idx;
128                if (leIdx > idx) {
129                    le.setEndIndex(leIdx - 1);
130                }
131            }
132            nextEndIndex--;
133        } else {
134            super.deleteEnd(end);
135        }
136    }
137
138    @Override
139    public int phiPredecessorCount() {
140        return forwardEndCount() + loopEnds().count();
141    }
142
143    @Override
144    public int phiPredecessorIndex(AbstractEndNode pred) {
145        if (pred instanceof LoopEndNode) {
146            LoopEndNode loopEnd = (LoopEndNode) pred;
147            if (loopEnd.loopBegin() == this) {
148                assert loopEnd.endIndex() < loopEnds().count() : "Invalid endIndex : " + loopEnd;
149                return loopEnd.endIndex() + forwardEndCount();
150            }
151        } else {
152            return super.forwardEndIndex((EndNode) pred);
153        }
154        throw ValueNodeUtil.shouldNotReachHere("unknown pred : " + pred);
155    }
156
157    @Override
158    public AbstractEndNode phiPredecessorAt(int index) {
159        if (index < forwardEndCount()) {
160            return forwardEndAt(index);
161        }
162        for (LoopEndNode end : loopEnds()) {
163            int idx = index - forwardEndCount();
164            assert idx >= 0;
165            if (end.endIndex() == idx) {
166                return end;
167            }
168        }
169        throw ValueNodeUtil.shouldNotReachHere();
170    }
171
172    @Override
173    public boolean verify() {
174        assertTrue(loopEnds().isNotEmpty(), "missing loopEnd");
175        return super.verify();
176    }
177
178    int nextEndIndex() {
179        return nextEndIndex++;
180    }
181
182    public int getLoopEndCount() {
183        return nextEndIndex;
184    }
185
186    public int unswitches() {
187        return unswitches;
188    }
189
190    public void incrementUnswitches() {
191        unswitches++;
192    }
193
194    public int getInversionCount() {
195        return inversionCount;
196    }
197
198    public void setInversionCount(int count) {
199        inversionCount = count;
200    }
201
202    @Override
203    public void simplify(SimplifierTool tool) {
204        removeDeadPhis();
205        canonicalizePhis(tool);
206    }
207
208    public boolean isLoopExit(AbstractBeginNode begin) {
209        return begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == this;
210    }
211
212    public void removeExits() {
213        for (LoopExitNode loopexit : loopExits().snapshot()) {
214            loopexit.removeProxies();
215            FrameState loopStateAfter = loopexit.stateAfter();
216            graph().replaceFixedWithFixed(loopexit, graph().add(new BeginNode()));
217            if (loopStateAfter != null && loopStateAfter.isAlive() && loopStateAfter.hasNoUsages()) {
218                GraphUtil.killWithUnusedFloatingInputs(loopStateAfter);
219            }
220        }
221    }
222
223    public GuardingNode getOverflowGuard() {
224        return overflowGuard;
225    }
226
227    public void setOverflowGuard(GuardingNode overflowGuard) {
228        updateUsagesInterface(this.overflowGuard, overflowGuard);
229        this.overflowGuard = overflowGuard;
230    }
231
232    /**
233     * Removes dead {@linkplain PhiNode phi nodes} hanging from this node.
234     *
235     * This method uses the heuristic that any node which not a phi node of this LoopBeginNode is
236     * alive. This allows the removal of dead phi loops.
237     */
238    public void removeDeadPhis() {
239        if (phis().isNotEmpty()) {
240            Set<PhiNode> alive = Node.newSet();
241            for (PhiNode phi : phis()) {
242                NodePredicate isAlive = u -> !isPhiAtMerge(u) || alive.contains(u);
243                if (phi.usages().filter(isAlive).isNotEmpty()) {
244                    alive.add(phi);
245                    for (PhiNode keptAlive : phi.values().filter(PhiNode.class).filter(isAlive.negate())) {
246                        alive.add(keptAlive);
247                    }
248                }
249            }
250            for (PhiNode phi : phis().filter(((NodePredicate) alive::contains).negate()).snapshot()) {
251                phi.replaceAtUsages(null);
252                phi.safeDelete();
253            }
254        }
255    }
256
257    private static final int NO_INCREMENT = Integer.MIN_VALUE;
258
259    /**
260     * Returns an array with one entry for each input of the phi, which is either
261     * {@link #NO_INCREMENT} or the increment, i.e., the value by which the phi is incremented in
262     * the corresponding branch.
263     */
264    private static int[] getSelfIncrements(PhiNode phi) {
265        int[] selfIncrement = new int[phi.valueCount()];
266        for (int i = 0; i < phi.valueCount(); i++) {
267            ValueNode input = phi.valueAt(i);
268            long increment = NO_INCREMENT;
269            if (input != null && input instanceof AddNode && input.stamp() instanceof IntegerStamp) {
270                AddNode add = (AddNode) input;
271                if (add.getX() == phi && add.getY().isConstant()) {
272                    increment = add.getY().asJavaConstant().asLong();
273                } else if (add.getY() == phi && add.getX().isConstant()) {
274                    increment = add.getX().asJavaConstant().asLong();
275                }
276            } else if (input == phi) {
277                increment = 0;
278            }
279            if (increment < Integer.MIN_VALUE || increment > Integer.MAX_VALUE || increment == NO_INCREMENT) {
280                increment = NO_INCREMENT;
281            }
282            selfIncrement[i] = (int) increment;
283        }
284        return selfIncrement;
285    }
286
287    /**
288     * Coalesces loop phis that represent the same value (which is not handled by normal Global
289     * Value Numbering).
290     */
291    public void canonicalizePhis(SimplifierTool tool) {
292        int phiCount = phis().count();
293        if (phiCount > 1) {
294            int phiInputCount = phiPredecessorCount();
295            int phiIndex = 0;
296            int[][] selfIncrement = new int[phiCount][];
297            PhiNode[] phis = this.phis().snapshot().toArray(new PhiNode[phiCount]);
298
299            for (phiIndex = 0; phiIndex < phiCount; phiIndex++) {
300                PhiNode phi = phis[phiIndex];
301                if (phi != null) {
302                    nextPhi: for (int otherPhiIndex = phiIndex + 1; otherPhiIndex < phiCount; otherPhiIndex++) {
303                        PhiNode otherPhi = phis[otherPhiIndex];
304                        if (otherPhi == null || phi.getNodeClass() != otherPhi.getNodeClass() || !phi.valueEquals(otherPhi)) {
305                            continue nextPhi;
306                        }
307                        if (selfIncrement[phiIndex] == null) {
308                            selfIncrement[phiIndex] = getSelfIncrements(phi);
309                        }
310                        if (selfIncrement[otherPhiIndex] == null) {
311                            selfIncrement[otherPhiIndex] = getSelfIncrements(otherPhi);
312                        }
313                        int[] phiIncrement = selfIncrement[phiIndex];
314                        int[] otherPhiIncrement = selfIncrement[otherPhiIndex];
315                        for (int inputIndex = 0; inputIndex < phiInputCount; inputIndex++) {
316                            if (phiIncrement[inputIndex] == NO_INCREMENT) {
317                                if (phi.valueAt(inputIndex) != otherPhi.valueAt(inputIndex)) {
318                                    continue nextPhi;
319                                }
320                            }
321                            if (phiIncrement[inputIndex] != otherPhiIncrement[inputIndex]) {
322                                continue nextPhi;
323                            }
324                        }
325                        if (tool != null) {
326                            tool.addToWorkList(otherPhi.usages());
327                        }
328                        otherPhi.replaceAtUsages(phi);
329                        GraphUtil.killWithUnusedFloatingInputs(otherPhi);
330                        phis[otherPhiIndex] = null;
331                    }
332                }
333            }
334        }
335    }
336}