27 import static java.lang.Math.abs; |
27 import static java.lang.Math.abs; |
28 import static org.graalvm.compiler.loop.MathUtil.unsignedDivBefore; |
28 import static org.graalvm.compiler.loop.MathUtil.unsignedDivBefore; |
29 import static org.graalvm.compiler.nodes.calc.BinaryArithmeticNode.add; |
29 import static org.graalvm.compiler.nodes.calc.BinaryArithmeticNode.add; |
30 import static org.graalvm.compiler.nodes.calc.BinaryArithmeticNode.sub; |
30 import static org.graalvm.compiler.nodes.calc.BinaryArithmeticNode.sub; |
31 |
31 |
32 import org.graalvm.compiler.core.common.NumUtil; |
|
33 import org.graalvm.compiler.core.common.type.IntegerStamp; |
32 import org.graalvm.compiler.core.common.type.IntegerStamp; |
34 import org.graalvm.compiler.core.common.type.Stamp; |
33 import org.graalvm.compiler.core.common.type.Stamp; |
35 import org.graalvm.compiler.core.common.util.UnsignedLong; |
34 import org.graalvm.compiler.core.common.util.UnsignedLong; |
36 import org.graalvm.compiler.debug.DebugCloseable; |
35 import org.graalvm.compiler.debug.DebugCloseable; |
37 import org.graalvm.compiler.loop.InductionVariable.Direction; |
36 import org.graalvm.compiler.loop.InductionVariable.Direction; |
42 import org.graalvm.compiler.nodes.LogicNode; |
41 import org.graalvm.compiler.nodes.LogicNode; |
43 import org.graalvm.compiler.nodes.NodeView; |
42 import org.graalvm.compiler.nodes.NodeView; |
44 import org.graalvm.compiler.nodes.StructuredGraph; |
43 import org.graalvm.compiler.nodes.StructuredGraph; |
45 import org.graalvm.compiler.nodes.ValueNode; |
44 import org.graalvm.compiler.nodes.ValueNode; |
46 import org.graalvm.compiler.nodes.calc.ConditionalNode; |
45 import org.graalvm.compiler.nodes.calc.ConditionalNode; |
47 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode; |
|
48 import org.graalvm.compiler.nodes.calc.NegateNode; |
46 import org.graalvm.compiler.nodes.calc.NegateNode; |
49 import org.graalvm.compiler.nodes.extended.GuardingNode; |
47 import org.graalvm.compiler.nodes.extended.GuardingNode; |
50 import org.graalvm.compiler.nodes.util.GraphUtil; |
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; |
51 |
52 |
52 import jdk.vm.ci.meta.DeoptimizationAction; |
53 import jdk.vm.ci.meta.DeoptimizationAction; |
53 import jdk.vm.ci.meta.DeoptimizationReason; |
54 import jdk.vm.ci.meta.DeoptimizationReason; |
54 import jdk.vm.ci.meta.SpeculationLog; |
55 import jdk.vm.ci.meta.SpeculationLog; |
55 |
56 |
59 private InductionVariable iv; |
60 private InductionVariable iv; |
60 private ValueNode end; |
61 private ValueNode end; |
61 private boolean oneOff; |
62 private boolean oneOff; |
62 private AbstractBeginNode body; |
63 private AbstractBeginNode body; |
63 private IfNode ifNode; |
64 private IfNode ifNode; |
64 |
65 private final boolean unsigned; |
65 CountedLoopInfo(LoopEx loop, InductionVariable iv, IfNode ifNode, ValueNode end, boolean oneOff, AbstractBeginNode body) { |
66 |
|
67 CountedLoopInfo(LoopEx loop, InductionVariable iv, IfNode ifNode, ValueNode end, boolean oneOff, AbstractBeginNode body, boolean unsigned) { |
66 assert iv.direction() != null; |
68 assert iv.direction() != null; |
67 this.loop = loop; |
69 this.loop = loop; |
68 this.iv = iv; |
70 this.iv = iv; |
69 this.end = end; |
71 this.end = end; |
70 this.oneOff = oneOff; |
72 this.oneOff = oneOff; |
71 this.body = body; |
73 this.body = body; |
72 this.ifNode = ifNode; |
74 this.ifNode = ifNode; |
|
75 this.unsigned = unsigned; |
73 } |
76 } |
74 |
77 |
75 /** |
78 /** |
76 * Returns a node that computes the maximum trip count of this loop. That is the trip count of |
79 * Returns a node that computes the maximum trip count of this loop. That is the trip count of |
77 * this loop assuming it is not exited by an other exit than the {@linkplain #getLimitTest() |
80 * this loop assuming it is not exited by an other exit than the {@linkplain #getLimitTest() |
81 * |
84 * |
82 * THIS VALUE SHOULD BE TREATED AS UNSIGNED. |
85 * THIS VALUE SHOULD BE TREATED AS UNSIGNED. |
83 */ |
86 */ |
84 public ValueNode maxTripCountNode() { |
87 public ValueNode maxTripCountNode() { |
85 return maxTripCountNode(false); |
88 return maxTripCountNode(false); |
|
89 } |
|
90 |
|
91 public boolean isUnsignedCheck() { |
|
92 return this.unsigned; |
86 } |
93 } |
87 |
94 |
88 /** |
95 /** |
89 * Returns a node that computes the maximum trip count of this loop. That is the trip count of |
96 * Returns a node that computes the maximum trip count of this loop. That is the trip count of |
90 * this loop assuming it is not exited by an other exit than the {@linkplain #getLimitTest() |
97 * this loop assuming it is not exited by an other exit than the {@linkplain #getLimitTest() |
125 |
132 |
126 if (assumeLoopEntered) { |
133 if (assumeLoopEntered) { |
127 return graph.addOrUniqueWithInputs(div); |
134 return graph.addOrUniqueWithInputs(div); |
128 } |
135 } |
129 ConstantNode zero = ConstantNode.forIntegerStamp(stamp, 0); |
136 ConstantNode zero = ConstantNode.forIntegerStamp(stamp, 0); |
130 LogicNode noEntryCheck = IntegerLessThanNode.create(max, min, NodeView.DEFAULT); |
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); |
131 return graph.addOrUniqueWithInputs(ConditionalNode.create(noEntryCheck, zero, div, NodeView.DEFAULT)); |
141 return graph.addOrUniqueWithInputs(ConditionalNode.create(noEntryCheck, zero, div, NodeView.DEFAULT)); |
132 } |
142 } |
133 |
143 |
134 /** |
144 /** |
135 * @return true if the loop has constant bounds. |
145 * @return true if the loop has constant bounds. |
150 assert iv.direction() != null; |
160 assert iv.direction() != null; |
151 long endValue = end.asJavaConstant().asLong(); |
161 long endValue = end.asJavaConstant().asLong(); |
152 long initValue = iv.constantInit(); |
162 long initValue = iv.constantInit(); |
153 long range; |
163 long range; |
154 long absStride; |
164 long absStride; |
|
165 IntegerHelper helper = getCounterIntegerHelper(64); |
155 if (iv.direction() == Direction.Up) { |
166 if (iv.direction() == Direction.Up) { |
156 if (endValue < initValue) { |
167 if (helper.compare(endValue, initValue) < 0) { |
157 return 0; |
168 return 0; |
158 } |
169 } |
159 range = endValue - iv.constantInit(); |
170 range = endValue - iv.constantInit(); |
160 absStride = iv.constantStride(); |
171 absStride = iv.constantStride(); |
161 } else { |
172 } else { |
162 assert iv.direction() == Direction.Down; |
173 assert iv.direction() == Direction.Down; |
163 if (initValue < endValue) { |
174 if (helper.compare(initValue, endValue) < 0) { |
164 return 0; |
175 return 0; |
165 } |
176 } |
166 range = iv.constantInit() - endValue; |
177 range = iv.constantInit() - endValue; |
167 absStride = -iv.constantStride(); |
178 absStride = -iv.constantStride(); |
168 } |
179 } |
169 if (oneOff) { |
180 if (oneOff) { |
170 range += 1; |
181 range += 1; |
171 } |
182 } |
172 long denominator = range + absStride - 1; |
183 long denominator = range + absStride - 1; |
173 return Long.divideUnsigned(denominator, absStride); |
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; |
174 } |
200 } |
175 |
201 |
176 public boolean isExactTripCount() { |
202 public boolean isExactTripCount() { |
177 return loop.loop().getNaturalExits().size() == 1; |
203 return loop.loop().getNaturalExits().size() == 1; |
178 } |
204 } |
244 } |
270 } |
245 IntegerStamp endStamp = (IntegerStamp) end.stamp(NodeView.DEFAULT); |
271 IntegerStamp endStamp = (IntegerStamp) end.stamp(NodeView.DEFAULT); |
246 ValueNode strideNode = iv.strideNode(); |
272 ValueNode strideNode = iv.strideNode(); |
247 IntegerStamp strideStamp = (IntegerStamp) strideNode.stamp(NodeView.DEFAULT); |
273 IntegerStamp strideStamp = (IntegerStamp) strideNode.stamp(NodeView.DEFAULT); |
248 GraphUtil.tryKillUnused(strideNode); |
274 GraphUtil.tryKillUnused(strideNode); |
|
275 IntegerHelper integerHelper = getCounterIntegerHelper(); |
249 if (getDirection() == Direction.Up) { |
276 if (getDirection() == Direction.Up) { |
250 long max = NumUtil.maxValue(endStamp.getBits()); |
277 long max = integerHelper.maxValue(); |
251 return endStamp.upperBound() <= max - (strideStamp.upperBound() - 1) - (oneOff ? 1 : 0); |
278 return integerHelper.compare(endStamp.upperBound(), max - (strideStamp.upperBound() - 1) - (oneOff ? 1 : 0)) <= 0; |
252 } else if (getDirection() == Direction.Down) { |
279 } else if (getDirection() == Direction.Down) { |
253 long min = NumUtil.minValue(endStamp.getBits()); |
280 long min = integerHelper.minValue(); |
254 return min + (1 - strideStamp.lowerBound()) + (oneOff ? 1 : 0) <= endStamp.lowerBound(); |
281 return integerHelper.compare(min + (1 - strideStamp.lowerBound()) + (oneOff ? 1 : 0), endStamp.lowerBound()) <= 0; |
255 } |
282 } |
256 return false; |
283 return false; |
257 } |
284 } |
258 |
285 |
259 @SuppressWarnings("try") |
286 @SuppressWarnings("try") |
262 if (overflowGuard != null || counterNeverOverflows()) { |
289 if (overflowGuard != null || counterNeverOverflows()) { |
263 return overflowGuard; |
290 return overflowGuard; |
264 } |
291 } |
265 try (DebugCloseable position = loop.loopBegin().withNodeSourcePosition()) { |
292 try (DebugCloseable position = loop.loopBegin().withNodeSourcePosition()) { |
266 IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT); |
293 IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT); |
|
294 IntegerHelper integerHelper = getCounterIntegerHelper(); |
267 StructuredGraph graph = iv.valueNode().graph(); |
295 StructuredGraph graph = iv.valueNode().graph(); |
268 LogicNode cond; // we use a negated guard with a < condition to achieve a >= |
296 LogicNode cond; // we use a negated guard with a < condition to achieve a >= |
269 ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph); |
297 ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph); |
270 if (iv.direction() == Direction.Up) { |
298 if (iv.direction() == Direction.Up) { |
271 ValueNode v1 = sub(ConstantNode.forIntegerStamp(stamp, NumUtil.maxValue(stamp.getBits())), sub(iv.strideNode(), one)); |
299 ValueNode v1 = sub(ConstantNode.forIntegerStamp(stamp, integerHelper.maxValue()), sub(iv.strideNode(), one)); |
272 if (oneOff) { |
300 if (oneOff) { |
273 v1 = sub(v1, one); |
301 v1 = sub(v1, one); |
274 } |
302 } |
275 cond = graph.addOrUniqueWithInputs(IntegerLessThanNode.create(v1, end, NodeView.DEFAULT)); |
303 cond = graph.addOrUniqueWithInputs(integerHelper.createCompareNode(v1, end, NodeView.DEFAULT)); |
276 } else { |
304 } else { |
277 assert iv.direction() == Direction.Down; |
305 assert iv.direction() == Direction.Down; |
278 ValueNode v1 = add(ConstantNode.forIntegerStamp(stamp, NumUtil.minValue(stamp.getBits())), sub(one, iv.strideNode())); |
306 ValueNode v1 = add(ConstantNode.forIntegerStamp(stamp, integerHelper.minValue()), sub(one, iv.strideNode())); |
279 if (oneOff) { |
307 if (oneOff) { |
280 v1 = add(v1, one); |
308 v1 = add(v1, one); |
281 } |
309 } |
282 cond = graph.addOrUniqueWithInputs(IntegerLessThanNode.create(end, v1, NodeView.DEFAULT)); |
310 cond = graph.addOrUniqueWithInputs(integerHelper.createCompareNode(end, v1, NodeView.DEFAULT)); |
283 } |
311 } |
284 assert graph.getGuardsStage().allowsFloatingGuards(); |
312 assert graph.getGuardsStage().allowsFloatingGuards(); |
285 overflowGuard = graph.unique(new GuardNode(cond, AbstractBeginNode.prevBegin(loop.entryPoint()), DeoptimizationReason.LoopLimitCheck, DeoptimizationAction.InvalidateRecompile, true, |
313 overflowGuard = graph.unique(new GuardNode(cond, AbstractBeginNode.prevBegin(loop.entryPoint()), DeoptimizationReason.LoopLimitCheck, DeoptimizationAction.InvalidateRecompile, true, |
286 SpeculationLog.NO_SPECULATION, null)); // TODO gd: use speculation |
314 SpeculationLog.NO_SPECULATION, null)); // TODO gd: use speculation |
287 loop.loopBegin().setOverflowGuard(overflowGuard); |
315 loop.loopBegin().setOverflowGuard(overflowGuard); |