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
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 this.loop = loop;
65 this.iv = iv;
66 this.end = end;
67 this.oneOff = oneOff;
68 this.body = body;
69 this.ifNode = ifNode;
70 }
71
72 /**
73 * Returns a node that computes the maximum trip count of this loop. That is the trip count of
74 * this loop assuming it is not exited by an other exit than the {@linkplain #getLimitTest()
75 * count check}.
76 *
77 * This count is exact if {@link #isExactTripCount()} returns true.
78 *
79 * THIS VALUE SHOULD BE TREATED AS UNSIGNED.
80 */
81 public ValueNode maxTripCountNode() {
82 return maxTripCountNode(false);
83 }
84
85 /**
86 * Returns a node that computes the maximum trip count of this loop. That is the trip count of
87 * this loop assuming it is not exited by an other exit than the {@linkplain #getLimitTest()
88 * count check}.
89 *
90 * This count is exact if {@link #isExactTripCount()} returns true.
91 *
92 * THIS VALUE SHOULD BE TREATED AS UNSIGNED.
93 *
94 * @param assumePositive if true the check that the loop is entered at all will be omitted.
95 */
96 public ValueNode maxTripCountNode(boolean assumePositive) {
97 StructuredGraph graph = iv.valueNode().graph();
98 Stamp stamp = iv.valueNode().stamp(NodeView.DEFAULT);
99
100 ValueNode max;
101 ValueNode min;
102 ValueNode range;
103 ValueNode absStride;
104 if (iv.direction() == Direction.Up) {
105 absStride = iv.strideNode();
106 range = sub(graph, end, iv.initNode());
107 max = end;
108 min = iv.initNode();
109 } else {
110 assert iv.direction() == Direction.Down;
111 absStride = graph.maybeAddOrUnique(NegateNode.create(iv.strideNode(), NodeView.DEFAULT));
112 range = sub(graph, iv.initNode(), end);
113 max = iv.initNode();
114 min = end;
115 }
116
117 ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph);
118 if (oneOff) {
119 range = add(graph, range, one);
120 }
121 // round-away-from-zero divison: (range + stride -/+ 1) / stride
122 ValueNode denominator = add(graph, range, sub(graph, absStride, one));
123 ValueNode div = unsignedDivBefore(graph, loop.entryPoint(), denominator, absStride, null);
124
125 if (assumePositive) {
126 return div;
127 }
128 ConstantNode zero = ConstantNode.forIntegerStamp(stamp, 0, graph);
129 return graph.unique(new ConditionalNode(graph.unique(new IntegerLessThanNode(max, min)), zero, div));
130 }
131
132 /**
133 * @return true if the loop has constant bounds.
134 */
135 public boolean isConstantMaxTripCount() {
136 return end instanceof ConstantNode && iv.isConstantInit() && iv.isConstantStride();
137 }
138
139 public UnsignedLong constantMaxTripCount() {
140 assert isConstantMaxTripCount();
141 return new UnsignedLong(rawConstantMaxTripCount());
142 }
143
144 /**
145 * Compute the raw value of the trip count for this loop. THIS IS AN UNSIGNED VALUE;
146 */
147 private long rawConstantMaxTripCount() {
148 assert iv.direction() != null;
149 long endValue = end.asJavaConstant().asLong();
150 long initValue = iv.constantInit();
151 long range;
152 long absStride;
153 if (iv.direction() == Direction.Up) {
154 if (endValue < initValue) {
155 return 0;
156 }
157 range = endValue - iv.constantInit();
158 absStride = iv.constantStride();
159 } else {
160 if (initValue < endValue) {
161 return 0;
162 }
163 range = iv.constantInit() - endValue;
164 absStride = -iv.constantStride();
165 }
166 if (oneOff) {
167 range += 1;
168 }
169 long denominator = range + absStride - 1;
170 return Long.divideUnsigned(denominator, absStride);
171 }
172
173 public boolean isExactTripCount() {
174 return loop.loopBegin().loopExits().count() == 1;
175 }
176
177 public ValueNode exactTripCountNode() {
178 assert isExactTripCount();
179 return maxTripCountNode();
180 }
181
182 public boolean isConstantExactTripCount() {
183 assert isExactTripCount();
184 return isConstantMaxTripCount();
185 }
186
187 public UnsignedLong constantExactTripCount() {
188 assert isExactTripCount();
189 return constantMaxTripCount();
190 }
191
192 @Override
193 public String toString() {
194 return "iv=" + iv + " until " + end + (oneOff ? iv.direction() == Direction.Up ? "+1" : "-1" : "");
195 }
196
197 public ValueNode getLimit() {
198 return end;
199 }
200
201 public IfNode getLimitTest() {
202 return ifNode;
203 }
204
205 public ValueNode getStart() {
206 return iv.initNode();
207 }
208
209 public boolean isLimitIncluded() {
210 return oneOff;
211 }
212
213 public AbstractBeginNode getBody() {
214 return body;
215 }
216
217 public Direction getDirection() {
218 return iv.direction();
219 }
220
221 public InductionVariable getCounter() {
222 return iv;
223 }
224
225 public GuardingNode getOverFlowGuard() {
226 return loop.loopBegin().getOverflowGuard();
227 }
228
229 @SuppressWarnings("try")
230 public GuardingNode createOverFlowGuard() {
231 GuardingNode overflowGuard = getOverFlowGuard();
232 if (overflowGuard != null) {
233 return overflowGuard;
234 }
235 try (DebugCloseable position = loop.loopBegin().withNodeSourcePosition()) {
236 IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT);
237 StructuredGraph graph = iv.valueNode().graph();
238 CompareNode cond; // we use a negated guard with a < condition to achieve a >=
239 ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph);
240 if (iv.direction() == Direction.Up) {
241 ValueNode v1 = sub(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.maxValue(stamp.getBits()), graph), sub(graph, iv.strideNode(), one));
242 if (oneOff) {
243 v1 = sub(graph, v1, one);
244 }
245 cond = graph.unique(new IntegerLessThanNode(v1, end));
246 } else {
247 assert iv.direction() == Direction.Down;
248 ValueNode v1 = add(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.minValue(stamp.getBits()), graph), sub(graph, one, iv.strideNode()));
249 if (oneOff) {
250 v1 = add(graph, v1, one);
251 }
252 cond = graph.unique(new IntegerLessThanNode(end, v1));
253 }
254 assert graph.getGuardsStage().allowsFloatingGuards();
255 overflowGuard = graph.unique(new GuardNode(cond, AbstractBeginNode.prevBegin(loop.entryPoint()), DeoptimizationReason.LoopLimitCheck, DeoptimizationAction.InvalidateRecompile, true,
256 SpeculationLog.NO_SPECULATION, null)); // TODO gd: use speculation
257 loop.loopBegin().setOverflowGuard(overflowGuard);
258 return overflowGuard;
259 }
260 }
261
262 public IntegerStamp getStamp() {
263 return (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT);
264 }
265 }