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 */
23 package org.graalvm.compiler.loop;
24
25 import static org.graalvm.compiler.loop.MathUtil.add;
26 import static org.graalvm.compiler.loop.MathUtil.divBefore;
27 import static org.graalvm.compiler.loop.MathUtil.sub;
28
29 import org.graalvm.compiler.core.common.type.IntegerStamp;
30 import org.graalvm.compiler.core.common.type.Stamp;
31 import org.graalvm.compiler.loop.InductionVariable.Direction;
32 import org.graalvm.compiler.nodes.AbstractBeginNode;
33 import org.graalvm.compiler.nodes.ConstantNode;
34 import org.graalvm.compiler.nodes.GuardNode;
35 import org.graalvm.compiler.nodes.IfNode;
36 import org.graalvm.compiler.nodes.StructuredGraph;
37 import org.graalvm.compiler.nodes.ValueNode;
38 import org.graalvm.compiler.nodes.calc.CompareNode;
39 import org.graalvm.compiler.nodes.calc.ConditionalNode;
40 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
41 import org.graalvm.compiler.nodes.extended.GuardingNode;
42
43 import jdk.vm.ci.code.CodeUtil;
44 import jdk.vm.ci.meta.DeoptimizationAction;
45 import jdk.vm.ci.meta.DeoptimizationReason;
46 import jdk.vm.ci.meta.JavaConstant;
47
48 public class CountedLoopInfo {
49
50 private final LoopEx loop;
51 private InductionVariable iv;
52 private ValueNode end;
53 private boolean oneOff;
54 private AbstractBeginNode body;
55 private IfNode ifNode;
56
57 CountedLoopInfo(LoopEx loop, InductionVariable iv, IfNode ifNode, ValueNode end, boolean oneOff, AbstractBeginNode body) {
58 this.loop = loop;
59 this.iv = iv;
60 this.end = end;
61 this.oneOff = oneOff;
62 this.body = body;
63 this.ifNode = ifNode;
64 }
65
66 public ValueNode maxTripCountNode() {
67 return maxTripCountNode(false);
68 }
69
70 public ValueNode maxTripCountNode(boolean assumePositive) {
71 StructuredGraph graph = iv.valueNode().graph();
72 Stamp stamp = iv.valueNode().stamp();
73 ValueNode range = sub(graph, end, iv.initNode());
74
75 ValueNode oneDirection;
76 if (iv.direction() == Direction.Up) {
77 oneDirection = ConstantNode.forIntegerStamp(stamp, 1, graph);
78 } else {
79 assert iv.direction() == Direction.Down;
80 oneDirection = ConstantNode.forIntegerStamp(stamp, -1, graph);
81 }
82 if (oneOff) {
83 range = add(graph, range, oneDirection);
84 }
85 // round-away-from-zero divison: (range + stride -/+ 1) / stride
86 ValueNode denominator = range;
87 if (!oneDirection.stamp().equals(iv.strideNode().stamp())) {
88 ValueNode subedRanged = sub(graph, range, oneDirection);
89 denominator = add(graph, subedRanged, iv.strideNode());
90 }
91 ValueNode div = divBefore(graph, loop.entryPoint(), denominator, iv.strideNode());
92
93 if (assumePositive) {
94 return div;
95 }
96 ConstantNode zero = ConstantNode.forIntegerStamp(stamp, 0, graph);
97 return graph.unique(new ConditionalNode(graph.unique(new IntegerLessThanNode(zero, div)), div, zero));
98 }
99
100 /**
101 * @return true if the loop has constant bounds and the trip count is representable as a
102 * positive integer.
103 */
104 public boolean isConstantMaxTripCount() {
105 /*
106 * It's possible that the iteration range is too large to treat this as constant because it
107 * will overflow.
108 */
109 return (hasConstantBounds() && rawConstantMaxTripCount() >= 0);
110 }
111
112 /**
113 * @return true if the bounds on the iteration space are all constants.
114 */
115 public boolean hasConstantBounds() {
116 return end instanceof ConstantNode && iv.isConstantInit() && iv.isConstantStride();
117 }
118
119 public long constantMaxTripCount() {
120 assert isConstantMaxTripCount();
121 return rawConstantMaxTripCount();
122 }
123
124 /**
125 * Compute the raw value of the trip count for this loop. Since we don't have unsigned values
126 * this may be outside representable positive values.
127 */
128 protected long rawConstantMaxTripCount() {
129 assert iv.direction() != null;
130 long off = oneOff ? iv.direction() == Direction.Up ? 1 : -1 : 0;
131 long endValue = ((ConstantNode) end).asJavaConstant().asLong();
132 try {
133 // If no overflow occurs then negative values represent a trip count of 0
134 long max = Math.subtractExact(Math.addExact(endValue, off), iv.constantInit()) / iv.constantStride();
135 return Math.max(0, max);
136 } catch (ArithmeticException e) {
137 /*
138 * The computation overflowed to return a negative value. It's possible some
139 * optimization could handle this value as an unsigned and produce the right answer but
140 * we hide this value by default.
141 */
142 return -1;
143 }
144 }
145
146 public boolean isExactTripCount() {
147 return loop.loopBegin().loopExits().count() == 1;
148 }
149
150 public ValueNode exactTripCountNode() {
151 assert isExactTripCount();
152 return maxTripCountNode();
153 }
154
155 public boolean isConstantExactTripCount() {
156 assert isExactTripCount();
157 return isConstantMaxTripCount();
158 }
159
160 public long constantExactTripCount() {
161 assert isExactTripCount();
162 return constantMaxTripCount();
163 }
164
165 @Override
166 public String toString() {
167 return "iv=" + iv + " until " + end + (oneOff ? iv.direction() == Direction.Up ? "+1" : "-1" : "");
168 }
169
170 public ValueNode getLimit() {
171 return end;
172 }
173
174 public IfNode getLimitTest() {
175 return ifNode;
176 }
177
178 public ValueNode getStart() {
179 return iv.initNode();
180 }
181
182 public boolean isLimitIncluded() {
183 return oneOff;
184 }
185
186 public AbstractBeginNode getBody() {
187 return body;
188 }
189
190 public Direction getDirection() {
191 return iv.direction();
192 }
193
194 public InductionVariable getCounter() {
195 return iv;
196 }
197
198 public GuardingNode getOverFlowGuard() {
199 return loop.loopBegin().getOverflowGuard();
200 }
201
202 public GuardingNode createOverFlowGuard() {
203 GuardingNode overflowGuard = getOverFlowGuard();
204 if (overflowGuard != null) {
205 return overflowGuard;
206 }
207 IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp();
208 StructuredGraph graph = iv.valueNode().graph();
209 CompareNode cond; // we use a negated guard with a < condition to achieve a >=
210 ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph);
211 if (iv.direction() == Direction.Up) {
212 ValueNode v1 = sub(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.maxValue(stamp.getBits()), graph), sub(graph, iv.strideNode(), one));
213 if (oneOff) {
214 v1 = sub(graph, v1, one);
215 }
216 cond = graph.unique(new IntegerLessThanNode(v1, end));
217 } else {
218 assert iv.direction() == Direction.Down;
219 ValueNode v1 = add(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.minValue(stamp.getBits()), graph), sub(graph, one, iv.strideNode()));
220 if (oneOff) {
221 v1 = add(graph, v1, one);
222 }
223 cond = graph.unique(new IntegerLessThanNode(end, v1));
224 }
225 assert graph.getGuardsStage().allowsFloatingGuards();
226 overflowGuard = graph.unique(new GuardNode(cond, AbstractBeginNode.prevBegin(loop.entryPoint()), DeoptimizationReason.LoopLimitCheck, DeoptimizationAction.InvalidateRecompile, true,
227 JavaConstant.NULL_POINTER)); // TODO gd: use speculation
228 loop.loopBegin().setOverflowGuard(overflowGuard);
229 return overflowGuard;
230 }
231
232 public IntegerStamp getStamp() {
233 return (IntegerStamp) iv.valueNode().stamp();
234 }
235 }