LoopEx.java revision 12657:6ef01bd40ce2 
1/*
2 * Copyright (c) 2012, 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.loop;
24
25import static org.graalvm.compiler.graph.Node.newIdentityMap;
26
27import java.util.Collection;
28import java.util.Collections;
29import java.util.LinkedList;
30import java.util.Map;
31import java.util.Queue;
32
33import org.graalvm.compiler.core.common.calc.Condition;
34import org.graalvm.compiler.core.common.cfg.Loop;
35import org.graalvm.compiler.core.common.type.IntegerStamp;
36import org.graalvm.compiler.debug.Debug;
37import org.graalvm.compiler.debug.GraalError;
38import org.graalvm.compiler.graph.Node;
39import org.graalvm.compiler.graph.NodeBitMap;
40import org.graalvm.compiler.graph.iterators.NodePredicate;
41import org.graalvm.compiler.loop.InductionVariable.Direction;
42import org.graalvm.compiler.nodes.AbstractBeginNode;
43import org.graalvm.compiler.nodes.AbstractEndNode;
44import org.graalvm.compiler.nodes.ConstantNode;
45import org.graalvm.compiler.nodes.FixedGuardNode;
46import org.graalvm.compiler.nodes.FixedNode;
47import org.graalvm.compiler.nodes.FixedWithNextNode;
48import org.graalvm.compiler.nodes.FrameState;
49import org.graalvm.compiler.nodes.FullInfopointNode;
50import org.graalvm.compiler.nodes.IfNode;
51import org.graalvm.compiler.nodes.LogicNode;
52import org.graalvm.compiler.nodes.LoopBeginNode;
53import org.graalvm.compiler.nodes.LoopExitNode;
54import org.graalvm.compiler.nodes.PhiNode;
55import org.graalvm.compiler.nodes.PiNode;
56import org.graalvm.compiler.nodes.StructuredGraph;
57import org.graalvm.compiler.nodes.ValueNode;
58import org.graalvm.compiler.nodes.ValuePhiNode;
59import org.graalvm.compiler.nodes.calc.AddNode;
60import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode;
61import org.graalvm.compiler.nodes.calc.CompareNode;
62import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
63import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
64import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
65import org.graalvm.compiler.nodes.calc.LeftShiftNode;
66import org.graalvm.compiler.nodes.calc.MulNode;
67import org.graalvm.compiler.nodes.calc.NegateNode;
68import org.graalvm.compiler.nodes.calc.SignExtendNode;
69import org.graalvm.compiler.nodes.calc.SubNode;
70import org.graalvm.compiler.nodes.calc.ZeroExtendNode;
71import org.graalvm.compiler.nodes.cfg.Block;
72import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
73import org.graalvm.compiler.nodes.debug.ControlFlowAnchorNode;
74import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
75import org.graalvm.compiler.nodes.util.GraphUtil;
76
77import jdk.vm.ci.code.BytecodeFrame;
78
79public class LoopEx {
80
81    private final Loop<Block> loop;
82    private LoopFragmentInside inside;
83    private LoopFragmentWhole whole;
84    private CountedLoopInfo counted;
85    private LoopsData data;
86    private Map<Node, InductionVariable> ivs;
87
88    LoopEx(Loop<Block> loop, LoopsData data) {
89        this.loop = loop;
90        this.data = data;
91    }
92
93    public Loop<Block> loop() {
94        return loop;
95    }
96
97    public LoopFragmentInside inside() {
98        if (inside == null) {
99            inside = new LoopFragmentInside(this);
100        }
101        return inside;
102    }
103
104    public LoopFragmentWhole whole() {
105        if (whole == null) {
106            whole = new LoopFragmentWhole(this);
107        }
108        return whole;
109    }
110
111    public void invalidateFragments() {
112        inside = null;
113        whole = null;
114    }
115
116    @SuppressWarnings("unused")
117    public LoopFragmentInsideFrom insideFrom(FixedNode point) {
118        // TODO (gd)
119        return null;
120    }
121
122    @SuppressWarnings("unused")
123    public LoopFragmentInsideBefore insideBefore(FixedNode point) {
124        // TODO (gd)
125        return null;
126    }
127
128    public boolean isOutsideLoop(Node n) {
129        return !whole().contains(n);
130    }
131
132    public LoopBeginNode loopBegin() {
133        return (LoopBeginNode) loop().getHeader().getBeginNode();
134    }
135
136    public FixedNode predecessor() {
137        return (FixedNode) loopBegin().forwardEnd().predecessor();
138    }
139
140    public FixedNode entryPoint() {
141        return loopBegin().forwardEnd();
142    }
143
144    public boolean isCounted() {
145        return counted != null;
146    }
147
148    public CountedLoopInfo counted() {
149        return counted;
150    }
151
152    public LoopEx parent() {
153        if (loop.getParent() == null) {
154            return null;
155        }
156        return data.loop(loop.getParent());
157    }
158
159    public int size() {
160        return whole().nodes().count();
161    }
162
163    @Override
164    public String toString() {
165        return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + loop().getDepth() + ") " + loopBegin();
166    }
167
168    private class InvariantPredicate implements NodePredicate {
169
170        @Override
171        public boolean apply(Node n) {
172            return isOutsideLoop(n);
173        }
174    }
175
176    public void reassociateInvariants() {
177        InvariantPredicate invariant = new InvariantPredicate();
178        StructuredGraph graph = loopBegin().graph();
179        for (BinaryArithmeticNode<?> binary : whole().nodes().filter(BinaryArithmeticNode.class)) {
180            if (!binary.isAssociative()) {
181                continue;
182            }
183            BinaryArithmeticNode<?> result = BinaryArithmeticNode.reassociate(binary, invariant, binary.getX(), binary.getY());
184            if (result != binary) {
185                if (Debug.isLogEnabled()) {
186                    Debug.log("%s : Reassociated %s into %s", graph.method().format("%H::%n"), binary, result);
187                }
188                if (!result.isAlive()) {
189                    assert !result.isDeleted();
190                    result = graph.addOrUniqueWithInputs(result);
191                }
192                binary.replaceAtUsages(result);
193                GraphUtil.killWithUnusedFloatingInputs(binary);
194            }
195        }
196    }
197
198    public boolean detectCounted() {
199        LoopBeginNode loopBegin = loopBegin();
200        FixedNode next = loopBegin.next();
201        while (next instanceof FixedGuardNode || next instanceof ValueAnchorNode || next instanceof FullInfopointNode) {
202            next = ((FixedWithNextNode) next).next();
203        }
204        if (next instanceof IfNode) {
205            IfNode ifNode = (IfNode) next;
206            boolean negated = false;
207            if (!loopBegin.isLoopExit(ifNode.falseSuccessor())) {
208                if (!loopBegin.isLoopExit(ifNode.trueSuccessor())) {
209                    return false;
210                }
211                negated = true;
212            }
213            LogicNode ifTest = ifNode.condition();
214            if (!(ifTest instanceof IntegerLessThanNode) && !(ifTest instanceof IntegerEqualsNode)) {
215                if (ifTest instanceof IntegerBelowNode) {
216                    Debug.log("Ignored potential Counted loop at %s with |<|", loopBegin);
217                }
218                return false;
219            }
220            CompareNode lessThan = (CompareNode) ifTest;
221            Condition condition = null;
222            InductionVariable iv = null;
223            ValueNode limit = null;
224            if (isOutsideLoop(lessThan.getX())) {
225                iv = getInductionVariables().get(lessThan.getY());
226                if (iv != null) {
227                    condition = lessThan.condition().mirror();
228                    limit = lessThan.getX();
229                }
230            } else if (isOutsideLoop(lessThan.getY())) {
231                iv = getInductionVariables().get(lessThan.getX());
232                if (iv != null) {
233                    condition = lessThan.condition();
234                    limit = lessThan.getY();
235                }
236            }
237            if (condition == null) {
238                return false;
239            }
240            if (negated) {
241                condition = condition.negate();
242            }
243            boolean oneOff = false;
244            switch (condition) {
245                case EQ:
246                    return false;
247                case NE: {
248                    if (!iv.isConstantStride() || Math.abs(iv.constantStride()) != 1) {
249                        return false;
250                    }
251                    IntegerStamp initStamp = (IntegerStamp) iv.initNode().stamp();
252                    IntegerStamp limitStamp = (IntegerStamp) limit.stamp();
253                    if (iv.direction() == Direction.Up) {
254                        if (initStamp.upperBound() > limitStamp.lowerBound()) {
255                            return false;
256                        }
257                    } else if (iv.direction() == Direction.Down) {
258                        if (initStamp.lowerBound() < limitStamp.upperBound()) {
259                            return false;
260                        }
261                    } else {
262                        return false;
263                    }
264                    break;
265                }
266                case LE:
267                    oneOff = true;
268                    if (iv.direction() != Direction.Up) {
269                        return false;
270                    }
271                    break;
272                case LT:
273                    if (iv.direction() != Direction.Up) {
274                        return false;
275                    }
276                    break;
277                case GE:
278                    oneOff = true;
279                    if (iv.direction() != Direction.Down) {
280                        return false;
281                    }
282                    break;
283                case GT:
284                    if (iv.direction() != Direction.Down) {
285                        return false;
286                    }
287                    break;
288                default:
289                    throw GraalError.shouldNotReachHere();
290            }
291            counted = new CountedLoopInfo(this, iv, limit, oneOff, negated ? ifNode.falseSuccessor() : ifNode.trueSuccessor());
292            return true;
293        }
294        return false;
295    }
296
297    public LoopsData loopsData() {
298        return data;
299    }
300
301    public void nodesInLoopBranch(NodeBitMap branchNodes, AbstractBeginNode branch) {
302        Collection<AbstractBeginNode> blocks = new LinkedList<>();
303        Collection<LoopExitNode> exits = new LinkedList<>();
304        Queue<Block> work = new LinkedList<>();
305        ControlFlowGraph cfg = loopsData().getCFG();
306        work.add(cfg.blockFor(branch));
307        while (!work.isEmpty()) {
308            Block b = work.remove();
309            if (loop().getExits().contains(b)) {
310                exits.add((LoopExitNode) b.getBeginNode());
311            } else {
312                blocks.add(b.getBeginNode());
313                for (Block d : b.getDominated()) {
314                    if (loop.getBlocks().contains(d)) {
315                        work.add(d);
316                    }
317                }
318            }
319        }
320        LoopFragment.computeNodes(branchNodes, branch.graph(), blocks, exits);
321    }
322
323    public Map<Node, InductionVariable> getInductionVariables() {
324        if (ivs == null) {
325            ivs = findInductionVariables(this);
326        }
327        return ivs;
328    }
329
330    /**
331     * Collect all the basic induction variables for the loop and the find any induction variables
332     * which are derived from the basic ones.
333     *
334     * @param loop
335     * @return a map from node to induction variable
336     */
337    private static Map<Node, InductionVariable> findInductionVariables(LoopEx loop) {
338        Map<Node, InductionVariable> ivs = newIdentityMap();
339
340        Queue<InductionVariable> scanQueue = new LinkedList<>();
341        LoopBeginNode loopBegin = loop.loopBegin();
342        AbstractEndNode forwardEnd = loopBegin.forwardEnd();
343        for (PhiNode phi : loopBegin.phis().filter(ValuePhiNode.class)) {
344            ValueNode backValue = phi.singleBackValue();
345            if (backValue == PhiNode.MULTIPLE_VALUES) {
346                continue;
347            }
348            ValueNode stride = addSub(loop, backValue, phi);
349            if (stride != null) {
350                BasicInductionVariable biv = new BasicInductionVariable(loop, (ValuePhiNode) phi, phi.valueAt(forwardEnd), stride, (BinaryArithmeticNode<?>) backValue);
351                ivs.put(phi, biv);
352                scanQueue.add(biv);
353            }
354        }
355
356        while (!scanQueue.isEmpty()) {
357            InductionVariable baseIv = scanQueue.remove();
358            ValueNode baseIvNode = baseIv.valueNode();
359            for (ValueNode op : baseIvNode.usages().filter(ValueNode.class)) {
360                if (loop.isOutsideLoop(op)) {
361                    continue;
362                }
363                if (op.usages().count() == 1 && op.usages().first() == baseIvNode) {
364                    /*
365                     * This is just the base induction variable increment with no other uses so
366                     * don't bother reporting it.
367                     */
368                    continue;
369                }
370                InductionVariable iv = null;
371                ValueNode offset = addSub(loop, op, baseIvNode);
372                ValueNode scale;
373                if (offset != null) {
374                    iv = new DerivedOffsetInductionVariable(loop, baseIv, offset, (BinaryArithmeticNode<?>) op);
375                } else if (op instanceof NegateNode) {
376                    iv = new DerivedScaledInductionVariable(loop, baseIv, (NegateNode) op);
377                } else if ((scale = mul(loop, op, baseIvNode)) != null) {
378                    iv = new DerivedScaledInductionVariable(loop, baseIv, scale, op);
379                } else {
380                    boolean isValidConvert = op instanceof PiNode || op instanceof SignExtendNode;
381                    if (!isValidConvert && op instanceof ZeroExtendNode) {
382                        IntegerStamp inputStamp = (IntegerStamp) ((ZeroExtendNode) op).getValue().stamp();
383                        isValidConvert = inputStamp.isPositive();
384                    }
385
386                    if (isValidConvert) {
387                        iv = new DerivedConvertedInductionVariable(loop, baseIv, op.stamp(), op);
388                    }
389                }
390
391                if (iv != null) {
392                    ivs.put(op, iv);
393                    scanQueue.offer(iv);
394                }
395            }
396        }
397        return Collections.unmodifiableMap(ivs);
398    }
399
400    private static ValueNode addSub(LoopEx loop, ValueNode op, ValueNode base) {
401        if (op.stamp() instanceof IntegerStamp && (op instanceof AddNode || op instanceof SubNode)) {
402            BinaryArithmeticNode<?> aritOp = (BinaryArithmeticNode<?>) op;
403            if (aritOp.getX() == base && loop.isOutsideLoop(aritOp.getY())) {
404                return aritOp.getY();
405            } else if (aritOp.getY() == base && loop.isOutsideLoop(aritOp.getX())) {
406                return aritOp.getX();
407            }
408        }
409        return null;
410    }
411
412    private static ValueNode mul(LoopEx loop, ValueNode op, ValueNode base) {
413        if (op instanceof MulNode) {
414            MulNode mul = (MulNode) op;
415            if (mul.getX() == base && loop.isOutsideLoop(mul.getY())) {
416                return mul.getY();
417            } else if (mul.getY() == base && loop.isOutsideLoop(mul.getX())) {
418                return mul.getX();
419            }
420        }
421        if (op instanceof LeftShiftNode) {
422            LeftShiftNode shift = (LeftShiftNode) op;
423            if (shift.getX() == base && shift.getY().isConstant()) {
424                return ConstantNode.forIntegerStamp(base.stamp(), 1 << shift.getY().asJavaConstant().asInt(), base.graph());
425            }
426        }
427        return null;
428    }
429
430    /**
431     * Deletes any nodes created within the scope of this object that have no usages.
432     */
433    public void deleteUnusedNodes() {
434        if (ivs != null) {
435            for (InductionVariable iv : ivs.values()) {
436                iv.deleteUnusedNodes();
437            }
438        }
439    }
440
441    /**
442     * @return true if all nodes in the loop can be duplicated.
443     */
444    public boolean canDuplicateLoop() {
445        for (Node node : inside().nodes()) {
446            if (node instanceof ControlFlowAnchorNode) {
447                return false;
448            }
449            if (node instanceof FrameState) {
450                FrameState frameState = (FrameState) node;
451                if (frameState.bci == BytecodeFrame.AFTER_EXCEPTION_BCI || frameState.bci == BytecodeFrame.UNWIND_BCI) {
452                    return false;
453                }
454            }
455        }
456        return true;
457    }
458}
459