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.StructuredGraph;
36 import org.graalvm.compiler.nodes.ValueNode;
37 import org.graalvm.compiler.nodes.calc.CompareNode;
38 import org.graalvm.compiler.nodes.calc.ConditionalNode;
39 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
40 import org.graalvm.compiler.nodes.extended.GuardingNode;
41
42 import jdk.vm.ci.code.CodeUtil;
43 import jdk.vm.ci.meta.DeoptimizationAction;
44 import jdk.vm.ci.meta.DeoptimizationReason;
45 import jdk.vm.ci.meta.JavaConstant;
46
47 public class CountedLoopInfo {
48
49 private final LoopEx loop;
50 private InductionVariable iv;
51 private ValueNode end;
52 private boolean oneOff;
53 private AbstractBeginNode body;
54
55 CountedLoopInfo(LoopEx loop, InductionVariable iv, ValueNode end, boolean oneOff, AbstractBeginNode body) {
56 this.loop = loop;
57 this.iv = iv;
58 this.end = end;
59 this.oneOff = oneOff;
60 this.body = body;
61 }
62
63 public ValueNode maxTripCountNode() {
64 return maxTripCountNode(false);
65 }
66
67 public ValueNode maxTripCountNode(boolean assumePositive) {
68 StructuredGraph graph = iv.valueNode().graph();
69 Stamp stamp = iv.valueNode().stamp();
70 ValueNode range = sub(graph, end, iv.initNode());
71
72 ValueNode oneDirection;
73 if (iv.direction() == Direction.Up) {
74 oneDirection = ConstantNode.forIntegerStamp(stamp, 1, graph);
75 } else {
76 assert iv.direction() == Direction.Down;
77 oneDirection = ConstantNode.forIntegerStamp(stamp, -1, graph);
78 }
79 if (oneOff) {
80 range = add(graph, range, oneDirection);
81 }
82 // round-away-from-zero divison: (range + stride -/+ 1) / stride
83 ValueNode denominator = add(graph, sub(graph, range, oneDirection), iv.strideNode());
84 ValueNode div = divBefore(graph, loop.entryPoint(), denominator, iv.strideNode());
85
86 if (assumePositive) {
87 return div;
88 }
89 ConstantNode zero = ConstantNode.forIntegerStamp(stamp, 0, graph);
90 return graph.unique(new ConditionalNode(graph.unique(new IntegerLessThanNode(zero, div)), div, zero));
91 }
92
93 public boolean isConstantMaxTripCount() {
94 return end instanceof ConstantNode && iv.isConstantInit() && iv.isConstantStride();
95 }
96
97 public long constantMaxTripCount() {
98 assert iv.direction() != null;
99 long off = oneOff ? iv.direction() == Direction.Up ? 1 : -1 : 0;
100 long max = (((ConstantNode) end).asJavaConstant().asLong() + off - iv.constantInit()) / iv.constantStride();
101 return Math.max(0, max);
102 }
103
104 public boolean isExactTripCount() {
105 return loop.loopBegin().loopExits().count() == 1;
106 }
107
108 public ValueNode exactTripCountNode() {
109 assert isExactTripCount();
110 return maxTripCountNode();
111 }
112
113 public boolean isConstantExactTripCount() {
114 assert isExactTripCount();
115 return isConstantMaxTripCount();
116 }
117
118 public long constantExactTripCount() {
119 assert isExactTripCount();
120 return constantMaxTripCount();
121 }
122
123 @Override
124 public String toString() {
125 return "iv=" + iv + " until " + end + (oneOff ? iv.direction() == Direction.Up ? "+1" : "-1" : "");
126 }
127
128 public ValueNode getLimit() {
129 return end;
130 }
131
132 public ValueNode getStart() {
133 return iv.initNode();
134 }
135
136 public boolean isLimitIncluded() {
137 return oneOff;
138 }
139
140 public AbstractBeginNode getBody() {
141 return body;
142 }
143
144 public Direction getDirection() {
145 return iv.direction();
146 }
147
148 public InductionVariable getCounter() {
149 return iv;
150 }
151
152 public GuardingNode getOverFlowGuard() {
153 return loop.loopBegin().getOverflowGuard();
154 }
155
156 public GuardingNode createOverFlowGuard() {
157 GuardingNode overflowGuard = getOverFlowGuard();
158 if (overflowGuard != null) {
159 return overflowGuard;
160 }
161 IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp();
162 StructuredGraph graph = iv.valueNode().graph();
163 CompareNode cond; // we use a negated guard with a < condition to achieve a >=
164 ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph);
165 if (iv.direction() == Direction.Up) {
166 ValueNode v1 = sub(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.maxValue(stamp.getBits()), graph), sub(graph, iv.strideNode(), one));
167 if (oneOff) {
168 v1 = sub(graph, v1, one);
169 }
170 cond = graph.unique(new IntegerLessThanNode(v1, end));
171 } else {
172 assert iv.direction() == Direction.Down;
173 ValueNode v1 = add(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.minValue(stamp.getBits()), graph), sub(graph, one, iv.strideNode()));
174 if (oneOff) {
175 v1 = add(graph, v1, one);
176 }
177 cond = graph.unique(new IntegerLessThanNode(end, v1));
178 }
179 assert graph.getGuardsStage().allowsFloatingGuards();
180 overflowGuard = graph.unique(new GuardNode(cond, AbstractBeginNode.prevBegin(loop.entryPoint()), DeoptimizationReason.LoopLimitCheck, DeoptimizationAction.InvalidateRecompile, true,
181 JavaConstant.NULL_POINTER)); // TODO gd: use speculation
182 loop.loopBegin().setOverflowGuard(overflowGuard);
183 return overflowGuard;
184 }
185
186 public IntegerStamp getStamp() {
187 return (IntegerStamp) iv.valueNode().stamp();
188 }
189 }