Source code

001/*
002 * Copyright (c) 2012, 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.loop;
024
025import static com.oracle.graal.graph.Node.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.common.*;
030import com.oracle.graal.debug.*;
031
032import com.oracle.graal.compiler.common.calc.*;
033import com.oracle.graal.compiler.common.cfg.*;
034import com.oracle.graal.compiler.common.type.*;
035import com.oracle.graal.graph.*;
036import com.oracle.graal.graph.iterators.*;
037import com.oracle.graal.loop.InductionVariable.Direction;
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.util.*;
043
044public class LoopEx {
045
046    private final Loop<Block> loop;
047    private LoopFragmentInside inside;
048    private LoopFragmentWhole whole;
049    private CountedLoopInfo counted;
050    private LoopsData data;
051    private Map<Node, InductionVariable> ivs;
052
053    LoopEx(Loop<Block> loop, LoopsData data) {
054        this.loop = loop;
055        this.data = data;
056    }
057
058    public Loop<Block> loop() {
059        return loop;
060    }
061
062    public LoopFragmentInside inside() {
063        if (inside == null) {
064            inside = new LoopFragmentInside(this);
065        }
066        return inside;
067    }
068
069    public LoopFragmentWhole whole() {
070        if (whole == null) {
071            whole = new LoopFragmentWhole(this);
072        }
073        return whole;
074    }
075
076    public void invalidateFragments() {
077        inside = null;
078        whole = null;
079    }
080
081    @SuppressWarnings("unused")
082    public LoopFragmentInsideFrom insideFrom(FixedNode point) {
083        // TODO (gd)
084        return null;
085    }
086
087    @SuppressWarnings("unused")
088    public LoopFragmentInsideBefore insideBefore(FixedNode point) {
089        // TODO (gd)
090        return null;
091    }
092
093    public boolean isOutsideLoop(Node n) {
094        return !whole().contains(n);
095    }
096
097    public LoopBeginNode loopBegin() {
098        return (LoopBeginNode) loop().getHeader().getBeginNode();
099    }
100
101    public FixedNode predecessor() {
102        return (FixedNode) loopBegin().forwardEnd().predecessor();
103    }
104
105    public FixedNode entryPoint() {
106        return loopBegin().forwardEnd();
107    }
108
109    public boolean isCounted() {
110        return counted != null;
111    }
112
113    public CountedLoopInfo counted() {
114        return counted;
115    }
116
117    public LoopEx parent() {
118        if (loop.getParent() == null) {
119            return null;
120        }
121        return data.loop(loop.getParent());
122    }
123
124    public int size() {
125        return whole().nodes().count();
126    }
127
128    @Override
129    public String toString() {
130        return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + loop().getDepth() + ") " + loopBegin();
131    }
132
133    private class InvariantPredicate implements NodePredicate {
134
135        @Override
136        public boolean apply(Node n) {
137            return isOutsideLoop(n);
138        }
139    }
140
141    public void reassociateInvariants() {
142        InvariantPredicate invariant = new InvariantPredicate();
143        StructuredGraph graph = loopBegin().graph();
144        for (BinaryArithmeticNode<?> binary : whole().nodes().filter(BinaryArithmeticNode.class)) {
145            if (!binary.isAssociative()) {
146                continue;
147            }
148            BinaryArithmeticNode<?> result = BinaryArithmeticNode.reassociate(binary, invariant, binary.getX(), binary.getY());
149            if (result != binary) {
150                if (Debug.isLogEnabled()) {
151                    Debug.log("%s : Reassociated %s into %s", graph.method().format("%H::%n"), binary, result);
152                }
153                if (!result.isAlive()) {
154                    assert !result.isDeleted();
155                    result = graph.addOrUniqueWithInputs(result);
156                }
157                binary.replaceAtUsages(result);
158                GraphUtil.killWithUnusedFloatingInputs(binary);
159            }
160        }
161    }
162
163    public boolean detectCounted() {
164        LoopBeginNode loopBegin = loopBegin();
165        FixedNode next = loopBegin.next();
166        while (next instanceof FixedGuardNode || next instanceof ValueAnchorNode || next instanceof InfopointNode) {
167            next = ((FixedWithNextNode) next).next();
168        }
169        if (next instanceof IfNode) {
170            IfNode ifNode = (IfNode) next;
171            boolean negated = false;
172            if (!loopBegin.isLoopExit(ifNode.falseSuccessor())) {
173                if (!loopBegin.isLoopExit(ifNode.trueSuccessor())) {
174                    return false;
175                }
176                negated = true;
177            }
178            LogicNode ifTest = ifNode.condition();
179            if (!(ifTest instanceof IntegerLessThanNode) && !(ifTest instanceof IntegerEqualsNode)) {
180                if (ifTest instanceof IntegerBelowNode) {
181                    Debug.log("Ignored potential Counted loop at %s with |<|", loopBegin);
182                }
183                return false;
184            }
185            CompareNode lessThan = (CompareNode) ifTest;
186            Condition condition = null;
187            InductionVariable iv = null;
188            ValueNode limit = null;
189            if (isOutsideLoop(lessThan.getX())) {
190                iv = getInductionVariables().get(lessThan.getY());
191                if (iv != null) {
192                    condition = lessThan.condition().mirror();
193                    limit = lessThan.getX();
194                }
195            } else if (isOutsideLoop(lessThan.getY())) {
196                iv = getInductionVariables().get(lessThan.getX());
197                if (iv != null) {
198                    condition = lessThan.condition();
199                    limit = lessThan.getY();
200                }
201            }
202            if (condition == null) {
203                return false;
204            }
205            if (negated) {
206                condition = condition.negate();
207            }
208            boolean oneOff = false;
209            switch (condition) {
210                case EQ:
211                    return false;
212                case NE: {
213                    if (!iv.isConstantStride() || Math.abs(iv.constantStride()) != 1) {
214                        return false;
215                    }
216                    IntegerStamp initStamp = (IntegerStamp) iv.initNode().stamp();
217                    IntegerStamp limitStamp = (IntegerStamp) limit.stamp();
218                    if (iv.direction() == Direction.Up) {
219                        if (initStamp.upperBound() > limitStamp.lowerBound()) {
220                            return false;
221                        }
222                    } else if (iv.direction() == Direction.Down) {
223                        if (initStamp.lowerBound() < limitStamp.upperBound()) {
224                            return false;
225                        }
226                    } else {
227                        return false;
228                    }
229                    oneOff = true;
230                    break;
231                }
232                case LE:
233                    oneOff = true; // fall through
234                case LT:
235                    if (iv.direction() != Direction.Up) {
236                        return false;
237                    }
238                    break;
239                case GE:
240                    oneOff = true; // fall through
241                case GT:
242                    if (iv.direction() != Direction.Down) {
243                        return false;
244                    }
245                    break;
246                default:
247                    throw JVMCIError.shouldNotReachHere();
248            }
249            counted = new CountedLoopInfo(this, iv, limit, oneOff, negated ? ifNode.falseSuccessor() : ifNode.trueSuccessor());
250            return true;
251        }
252        return false;
253    }
254
255    public LoopsData loopsData() {
256        return data;
257    }
258
259    public NodeBitMap nodesInLoopBranch(AbstractBeginNode branch) {
260        Collection<AbstractBeginNode> blocks = new LinkedList<>();
261        Collection<LoopExitNode> exits = new LinkedList<>();
262        Queue<Block> work = new LinkedList<>();
263        ControlFlowGraph cfg = loopsData().getCFG();
264        work.add(cfg.blockFor(branch));
265        while (!work.isEmpty()) {
266            Block b = work.remove();
267            if (loop().getExits().contains(b)) {
268                exits.add((LoopExitNode) b.getBeginNode());
269            } else {
270                blocks.add(b.getBeginNode());
271                for (Block d : b.getDominated()) {
272                    if (loop.getBlocks().contains(d)) {
273                        work.add(d);
274                    }
275                }
276            }
277        }
278        return LoopFragment.computeNodes(branch.graph(), blocks, exits);
279    }
280
281    public Map<Node, InductionVariable> getInductionVariables() {
282        if (ivs == null) {
283            ivs = findInductionVariables(this);
284        }
285        return ivs;
286    }
287
288    /**
289     * Collect all the basic induction variables for the loop and the find any induction variables
290     * which are derived from the basic ones.
291     *
292     * @param loop
293     * @return a map from node to induction variable
294     */
295    private static Map<Node, InductionVariable> findInductionVariables(LoopEx loop) {
296        Map<Node, InductionVariable> ivs = newIdentityMap();
297
298        Queue<InductionVariable> scanQueue = new LinkedList<>();
299        LoopBeginNode loopBegin = loop.loopBegin();
300        AbstractEndNode forwardEnd = loopBegin.forwardEnd();
301        for (PhiNode phi : loopBegin.phis().filter(ValuePhiNode.class)) {
302            ValueNode backValue = phi.singleBackValue();
303            if (backValue == PhiNode.MULTIPLE_VALUES) {
304                continue;
305            }
306            ValueNode stride = addSub(loop, backValue, phi);
307            if (stride != null) {
308                BasicInductionVariable biv = new BasicInductionVariable(loop, (ValuePhiNode) phi, phi.valueAt(forwardEnd), stride, (BinaryArithmeticNode<?>) backValue);
309                ivs.put(phi, biv);
310                scanQueue.add(biv);
311            }
312        }
313
314        while (!scanQueue.isEmpty()) {
315            InductionVariable baseIv = scanQueue.remove();
316            ValueNode baseIvNode = baseIv.valueNode();
317            for (ValueNode op : baseIvNode.usages().filter(ValueNode.class)) {
318                if (loop.isOutsideLoop(op)) {
319                    continue;
320                }
321                if (op.usages().count() == 1 && op.usages().first() == baseIvNode) {
322                    /*
323                     * This is just the base induction variable increment with no other uses so
324                     * don't bother reporting it.
325                     */
326                    continue;
327                }
328                InductionVariable iv = null;
329                ValueNode offset = addSub(loop, op, baseIvNode);
330                ValueNode scale;
331                if (offset != null) {
332                    iv = new DerivedOffsetInductionVariable(loop, baseIv, offset, (BinaryArithmeticNode<?>) op);
333                } else if (op instanceof NegateNode) {
334                    iv = new DerivedScaledInductionVariable(loop, baseIv, (NegateNode) op);
335                } else if ((scale = mul(loop, op, baseIvNode)) != null) {
336                    iv = new DerivedScaledInductionVariable(loop, baseIv, scale, op);
337                } else {
338                    boolean isValidConvert = op instanceof PiNode || op instanceof SignExtendNode;
339                    if (!isValidConvert && op instanceof ZeroExtendNode) {
340                        IntegerStamp inputStamp = (IntegerStamp) ((ZeroExtendNode) op).getValue().stamp();
341                        isValidConvert = inputStamp.isPositive();
342                    }
343
344                    if (isValidConvert) {
345                        iv = new DerivedConvertedInductionVariable(loop, baseIv, op.stamp(), op);
346                    }
347                }
348
349                if (iv != null) {
350                    ivs.put(op, iv);
351                    scanQueue.offer(iv);
352                }
353            }
354        }
355        return Collections.unmodifiableMap(ivs);
356    }
357
358    private static ValueNode addSub(LoopEx loop, ValueNode op, ValueNode base) {
359        if (op.stamp() instanceof IntegerStamp && (op instanceof AddNode || op instanceof SubNode)) {
360            BinaryArithmeticNode<?> aritOp = (BinaryArithmeticNode<?>) op;
361            if (aritOp.getX() == base && loop.isOutsideLoop(aritOp.getY())) {
362                return aritOp.getY();
363            } else if (aritOp.getY() == base && loop.isOutsideLoop(aritOp.getX())) {
364                return aritOp.getX();
365            }
366        }
367        return null;
368    }
369
370    private static ValueNode mul(LoopEx loop, ValueNode op, ValueNode base) {
371        if (op instanceof MulNode) {
372            MulNode mul = (MulNode) op;
373            if (mul.getX() == base && loop.isOutsideLoop(mul.getY())) {
374                return mul.getY();
375            } else if (mul.getY() == base && loop.isOutsideLoop(mul.getX())) {
376                return mul.getX();
377            }
378        }
379        if (op instanceof LeftShiftNode) {
380            LeftShiftNode shift = (LeftShiftNode) op;
381            if (shift.getX() == base && shift.getY().isConstant()) {
382                return ConstantNode.forIntegerStamp(base.stamp(), 1 << shift.getY().asJavaConstant().asInt(), base.graph());
383            }
384        }
385        return null;
386    }
387
388    /**
389     * Deletes any nodes created within the scope of this object that have no usages.
390     */
391    public void deleteUnusedNodes() {
392        if (ivs != null) {
393            for (InductionVariable iv : ivs.values()) {
394                iv.deleteUnusedNodes();
395            }
396        }
397    }
398}