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