1 /*
2 * Copyright (c) 2012, 2018, 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
24
25 package org.graalvm.compiler.loop;
26
27 import static java.lang.Math.abs;
28 import static org.graalvm.compiler.loop.MathUtil.unsignedDivBefore;
29 import static org.graalvm.compiler.nodes.calc.BinaryArithmeticNode.add;
30 import static org.graalvm.compiler.nodes.calc.BinaryArithmeticNode.sub;
31
32 import org.graalvm.compiler.core.common.type.IntegerStamp;
33 import org.graalvm.compiler.core.common.type.Stamp;
34 import org.graalvm.compiler.core.common.util.UnsignedLong;
35 import org.graalvm.compiler.debug.DebugCloseable;
36 import org.graalvm.compiler.loop.InductionVariable.Direction;
37 import org.graalvm.compiler.nodes.AbstractBeginNode;
38 import org.graalvm.compiler.nodes.ConstantNode;
39 import org.graalvm.compiler.nodes.GuardNode;
40 import org.graalvm.compiler.nodes.IfNode;
41 import org.graalvm.compiler.nodes.LogicNode;
42 import org.graalvm.compiler.nodes.NodeView;
43 import org.graalvm.compiler.nodes.StructuredGraph;
44 import org.graalvm.compiler.nodes.ValueNode;
45 import org.graalvm.compiler.nodes.calc.ConditionalNode;
46 import org.graalvm.compiler.nodes.calc.NegateNode;
47 import org.graalvm.compiler.nodes.extended.GuardingNode;
48 import org.graalvm.compiler.nodes.util.GraphUtil;
49 import org.graalvm.compiler.nodes.util.IntegerHelper;
50 import org.graalvm.compiler.nodes.util.SignedIntegerHelper;
51 import org.graalvm.compiler.nodes.util.UnsignedIntegerHelper;
52
53 import jdk.vm.ci.meta.DeoptimizationAction;
54 import jdk.vm.ci.meta.DeoptimizationReason;
55 import jdk.vm.ci.meta.SpeculationLog;
56
57 public class CountedLoopInfo {
58
59 private final LoopEx loop;
60 private InductionVariable iv;
61 private ValueNode end;
62 private boolean oneOff;
63 private AbstractBeginNode body;
64 private IfNode ifNode;
65 private final boolean unsigned;
66
67 CountedLoopInfo(LoopEx loop, InductionVariable iv, IfNode ifNode, ValueNode end, boolean oneOff, AbstractBeginNode body, boolean unsigned) {
68 assert iv.direction() != null;
69 this.loop = loop;
70 this.iv = iv;
71 this.end = end;
72 this.oneOff = oneOff;
73 this.body = body;
74 this.ifNode = ifNode;
75 this.unsigned = unsigned;
76 }
77
78 /**
79 * Returns a node that computes the maximum trip count of this loop. That is the trip count of
80 * this loop assuming it is not exited by an other exit than the {@linkplain #getLimitTest()
81 * count check}.
82 *
83 * This count is exact if {@link #isExactTripCount()} returns true.
84 *
85 * THIS VALUE SHOULD BE TREATED AS UNSIGNED.
86 */
87 public ValueNode maxTripCountNode() {
88 return maxTripCountNode(false);
89 }
90
91 public boolean isUnsignedCheck() {
92 return this.unsigned;
93 }
94
95 /**
96 * Returns a node that computes the maximum trip count of this loop. That is the trip count of
97 * this loop assuming it is not exited by an other exit than the {@linkplain #getLimitTest()
98 * count check}.
99 *
100 * This count is exact if {@link #isExactTripCount()} returns true.
101 *
102 * THIS VALUE SHOULD BE TREATED AS UNSIGNED.
103 *
104 * @param assumeLoopEntered if true the check that the loop is entered at all will be omitted.
105 */
106 public ValueNode maxTripCountNode(boolean assumeLoopEntered) {
107 StructuredGraph graph = iv.valueNode().graph();
108 Stamp stamp = iv.valueNode().stamp(NodeView.DEFAULT);
109
110 ValueNode max;
111 ValueNode min;
112 ValueNode absStride;
113 if (iv.direction() == Direction.Up) {
114 absStride = iv.strideNode();
115 max = end;
116 min = iv.initNode();
117 } else {
118 assert iv.direction() == Direction.Down;
119 absStride = NegateNode.create(iv.strideNode(), NodeView.DEFAULT);
120 max = iv.initNode();
121 min = end;
122 }
123 ValueNode range = sub(max, min);
124
125 ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1);
126 if (oneOff) {
127 range = add(range, one);
128 }
129 // round-away-from-zero divison: (range + stride -/+ 1) / stride
130 ValueNode denominator = add(range, sub(absStride, one));
131 ValueNode div = unsignedDivBefore(graph, loop.entryPoint(), denominator, absStride, null);
132
133 if (assumeLoopEntered) {
134 return graph.addOrUniqueWithInputs(div);
135 }
136 ConstantNode zero = ConstantNode.forIntegerStamp(stamp, 0);
137 // This check is "wide": it looks like min <= max
138 // That's OK even if the loop is strict (`!isLimitIncluded()`)
139 // because in this case, `div` will be zero when min == max
140 LogicNode noEntryCheck = getCounterIntegerHelper().createCompareNode(max, min, NodeView.DEFAULT);
141 return graph.addOrUniqueWithInputs(ConditionalNode.create(noEntryCheck, zero, div, NodeView.DEFAULT));
142 }
143
144 /**
145 * @return true if the loop has constant bounds.
146 */
147 public boolean isConstantMaxTripCount() {
148 return end instanceof ConstantNode && iv.isConstantInit() && iv.isConstantStride();
149 }
150
151 public UnsignedLong constantMaxTripCount() {
152 assert isConstantMaxTripCount();
153 return new UnsignedLong(rawConstantMaxTripCount());
154 }
155
156 /**
157 * Compute the raw value of the trip count for this loop. THIS IS AN UNSIGNED VALUE;
158 */
159 private long rawConstantMaxTripCount() {
160 assert iv.direction() != null;
161 long endValue = end.asJavaConstant().asLong();
162 long initValue = iv.constantInit();
163 long range;
164 long absStride;
165 IntegerHelper helper = getCounterIntegerHelper(64);
166 if (iv.direction() == Direction.Up) {
167 if (helper.compare(endValue, initValue) < 0) {
168 return 0;
169 }
170 range = endValue - iv.constantInit();
171 absStride = iv.constantStride();
172 } else {
173 assert iv.direction() == Direction.Down;
174 if (helper.compare(initValue, endValue) < 0) {
175 return 0;
176 }
177 range = iv.constantInit() - endValue;
178 absStride = -iv.constantStride();
179 }
180 if (oneOff) {
181 range += 1;
182 }
183 long denominator = range + absStride - 1;
184 return Long.divideUnsigned(denominator, absStride);
185 }
186
187 public IntegerHelper getCounterIntegerHelper() {
188 IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT);
189 return getCounterIntegerHelper(stamp.getBits());
190 }
191
192 public IntegerHelper getCounterIntegerHelper(int bits) {
193 IntegerHelper helper;
194 if (isUnsignedCheck()) {
195 helper = new UnsignedIntegerHelper(bits);
196 } else {
197 helper = new SignedIntegerHelper(bits);
198 }
199 return helper;
200 }
201
202 public boolean isExactTripCount() {
203 return loop.loop().getNaturalExits().size() == 1;
204 }
205
206 public ValueNode exactTripCountNode() {
207 assert isExactTripCount();
208 return maxTripCountNode();
209 }
210
211 public boolean isConstantExactTripCount() {
212 assert isExactTripCount();
213 return isConstantMaxTripCount();
214 }
215
216 public UnsignedLong constantExactTripCount() {
217 assert isExactTripCount();
218 return constantMaxTripCount();
219 }
220
221 @Override
222 public String toString() {
223 return "iv=" + iv + " until " + end + (oneOff ? iv.direction() == Direction.Up ? "+1" : "-1" : "");
224 }
225
226 public ValueNode getLimit() {
227 return end;
228 }
229
230 public IfNode getLimitTest() {
231 return ifNode;
232 }
233
234 public ValueNode getStart() {
235 return iv.initNode();
236 }
237
238 public boolean isLimitIncluded() {
239 return oneOff;
240 }
241
242 public AbstractBeginNode getBody() {
243 return body;
244 }
245
246 public AbstractBeginNode getCountedExit() {
247 if (getLimitTest().trueSuccessor() == getBody()) {
248 return getLimitTest().falseSuccessor();
249 } else {
250 assert getLimitTest().falseSuccessor() == getBody();
251 return getLimitTest().trueSuccessor();
252 }
253 }
254
255 public Direction getDirection() {
256 return iv.direction();
257 }
258
259 public InductionVariable getCounter() {
260 return iv;
261 }
262
263 public GuardingNode getOverFlowGuard() {
264 return loop.loopBegin().getOverflowGuard();
265 }
266
267 public boolean counterNeverOverflows() {
268 if (iv.isConstantStride() && abs(iv.constantStride()) == 1) {
269 return true;
270 }
271 IntegerStamp endStamp = (IntegerStamp) end.stamp(NodeView.DEFAULT);
272 ValueNode strideNode = iv.strideNode();
273 IntegerStamp strideStamp = (IntegerStamp) strideNode.stamp(NodeView.DEFAULT);
274 GraphUtil.tryKillUnused(strideNode);
275 IntegerHelper integerHelper = getCounterIntegerHelper();
276 if (getDirection() == Direction.Up) {
277 long max = integerHelper.maxValue();
278 return integerHelper.compare(endStamp.upperBound(), max - (strideStamp.upperBound() - 1) - (oneOff ? 1 : 0)) <= 0;
279 } else if (getDirection() == Direction.Down) {
280 long min = integerHelper.minValue();
281 return integerHelper.compare(min + (1 - strideStamp.lowerBound()) + (oneOff ? 1 : 0), endStamp.lowerBound()) <= 0;
282 }
283 return false;
284 }
285
286 @SuppressWarnings("try")
287 public GuardingNode createOverFlowGuard() {
288 GuardingNode overflowGuard = getOverFlowGuard();
289 if (overflowGuard != null || counterNeverOverflows()) {
290 return overflowGuard;
291 }
292 try (DebugCloseable position = loop.loopBegin().withNodeSourcePosition()) {
293 IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT);
294 IntegerHelper integerHelper = getCounterIntegerHelper();
295 StructuredGraph graph = iv.valueNode().graph();
296 LogicNode cond; // we use a negated guard with a < condition to achieve a >=
297 ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph);
298 if (iv.direction() == Direction.Up) {
299 ValueNode v1 = sub(ConstantNode.forIntegerStamp(stamp, integerHelper.maxValue()), sub(iv.strideNode(), one));
300 if (oneOff) {
301 v1 = sub(v1, one);
302 }
303 cond = graph.addOrUniqueWithInputs(integerHelper.createCompareNode(v1, end, NodeView.DEFAULT));
304 } else {
305 assert iv.direction() == Direction.Down;
306 ValueNode v1 = add(ConstantNode.forIntegerStamp(stamp, integerHelper.minValue()), sub(one, iv.strideNode()));
307 if (oneOff) {
308 v1 = add(v1, one);
309 }
310 cond = graph.addOrUniqueWithInputs(integerHelper.createCompareNode(end, v1, NodeView.DEFAULT));
311 }
312 assert graph.getGuardsStage().allowsFloatingGuards();
313 overflowGuard = graph.unique(new GuardNode(cond, AbstractBeginNode.prevBegin(loop.entryPoint()), DeoptimizationReason.LoopLimitCheck, DeoptimizationAction.InvalidateRecompile, true,
314 SpeculationLog.NO_SPECULATION, null)); // TODO gd: use speculation
315 loop.loopBegin().setOverflowGuard(overflowGuard);
316 return overflowGuard;
317 }
318 }
319
320 public IntegerStamp getStamp() {
321 return (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT);
322 }
323 }