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.loop.MathUtil.*;
026import jdk.internal.jvmci.code.*;
027import jdk.internal.jvmci.meta.*;
028
029import com.oracle.graal.compiler.common.type.*;
030import com.oracle.graal.loop.InductionVariable.Direction;
031import com.oracle.graal.nodes.*;
032import com.oracle.graal.nodes.calc.*;
033import com.oracle.graal.nodes.extended.*;
034
035public class CountedLoopInfo {
036
037    private final LoopEx loop;
038    private InductionVariable iv;
039    private ValueNode end;
040    private boolean oneOff;
041    private AbstractBeginNode body;
042
043    CountedLoopInfo(LoopEx loop, InductionVariable iv, ValueNode end, boolean oneOff, AbstractBeginNode body) {
044        this.loop = loop;
045        this.iv = iv;
046        this.end = end;
047        this.oneOff = oneOff;
048        this.body = body;
049    }
050
051    public ValueNode maxTripCountNode() {
052        return maxTripCountNode(false);
053    }
054
055    public ValueNode maxTripCountNode(boolean assumePositive) {
056        StructuredGraph graph = iv.valueNode().graph();
057        Stamp stamp = iv.valueNode().stamp();
058        ValueNode range = sub(graph, end, iv.initNode());
059
060        ValueNode oneDirection;
061        if (iv.direction() == Direction.Up) {
062            oneDirection = ConstantNode.forIntegerStamp(stamp, 1, graph);
063        } else {
064            assert iv.direction() == Direction.Down;
065            oneDirection = ConstantNode.forIntegerStamp(stamp, -1, graph);
066        }
067        if (oneOff) {
068            range = add(graph, range, oneDirection);
069        }
070        // round-away-from-zero divison: (range + stride -/+ 1) / stride
071        ValueNode denominator = add(graph, sub(graph, range, oneDirection), iv.strideNode());
072        ValueNode div = divBefore(graph, loop.entryPoint(), denominator, iv.strideNode());
073
074        if (assumePositive) {
075            return div;
076        }
077        ConstantNode zero = ConstantNode.forIntegerStamp(stamp, 0, graph);
078        return graph.unique(new ConditionalNode(graph.unique(new IntegerLessThanNode(zero, div)), div, zero));
079    }
080
081    public boolean isConstantMaxTripCount() {
082        return end instanceof ConstantNode && iv.isConstantInit() && iv.isConstantStride();
083    }
084
085    public long constantMaxTripCount() {
086        assert iv.direction() != null;
087        long off = oneOff ? iv.direction() == Direction.Up ? 1 : -1 : 0;
088        long max = (((ConstantNode) end).asJavaConstant().asLong() + off - iv.constantInit()) / iv.constantStride();
089        return Math.max(0, max);
090    }
091
092    public boolean isExactTripCount() {
093        return loop.loopBegin().loopExits().count() == 1;
094    }
095
096    public ValueNode exactTripCountNode() {
097        assert isExactTripCount();
098        return maxTripCountNode();
099    }
100
101    public boolean isConstantExactTripCount() {
102        assert isExactTripCount();
103        return isConstantMaxTripCount();
104    }
105
106    public long constantExactTripCount() {
107        assert isExactTripCount();
108        return constantMaxTripCount();
109    }
110
111    @Override
112    public String toString() {
113        return "iv=" + iv + " until " + end + (oneOff ? iv.direction() == Direction.Up ? "+1" : "-1" : "");
114    }
115
116    public ValueNode getLimit() {
117        return end;
118    }
119
120    public ValueNode getStart() {
121        return iv.initNode();
122    }
123
124    public boolean isLimitIncluded() {
125        return oneOff;
126    }
127
128    public AbstractBeginNode getBody() {
129        return body;
130    }
131
132    public Direction getDirection() {
133        return iv.direction();
134    }
135
136    public InductionVariable getCounter() {
137        return iv;
138    }
139
140    public GuardingNode getOverFlowGuard() {
141        return loop.loopBegin().getOverflowGuard();
142    }
143
144    public GuardingNode createOverFlowGuard() {
145        GuardingNode overflowGuard = getOverFlowGuard();
146        if (overflowGuard != null) {
147            return overflowGuard;
148        }
149        IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp();
150        StructuredGraph graph = iv.valueNode().graph();
151        CompareNode cond; // we use a negated guard with a < condition to achieve a >=
152        ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph);
153        if (iv.direction() == Direction.Up) {
154            ValueNode v1 = sub(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.maxValue(stamp.getBits()), graph), sub(graph, iv.strideNode(), one));
155            if (oneOff) {
156                v1 = sub(graph, v1, one);
157            }
158            cond = graph.unique(new IntegerLessThanNode(v1, end));
159        } else {
160            assert iv.direction() == Direction.Down;
161            ValueNode v1 = add(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.minValue(stamp.getBits()), graph), sub(graph, one, iv.strideNode()));
162            if (oneOff) {
163                v1 = add(graph, v1, one);
164            }
165            cond = graph.unique(new IntegerLessThanNode(end, v1));
166        }
167        overflowGuard = graph.unique(new GuardNode(cond, AbstractBeginNode.prevBegin(loop.entryPoint()), DeoptimizationReason.LoopLimitCheck, DeoptimizationAction.InvalidateRecompile, true,
168                        JavaConstant.NULL_POINTER)); // TODO gd: use speculation
169        loop.loopBegin().setOverflowGuard(overflowGuard);
170        return overflowGuard;
171    }
172
173    public IntegerStamp getStamp() {
174        return (IntegerStamp) iv.valueNode().stamp();
175    }
176}