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 org.graalvm.compiler.loop.MathUtil.add;
28 import static org.graalvm.compiler.loop.MathUtil.mul;
29 import static org.graalvm.compiler.loop.MathUtil.sub;
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.GraalError;
35 import org.graalvm.compiler.nodes.ConstantNode;
36 import org.graalvm.compiler.nodes.NodeView;
37 import org.graalvm.compiler.nodes.StructuredGraph;
38 import org.graalvm.compiler.nodes.ValueNode;
39 import org.graalvm.compiler.nodes.ValuePhiNode;
40 import org.graalvm.compiler.nodes.calc.AddNode;
41 import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode;
42 import org.graalvm.compiler.nodes.calc.IntegerConvertNode;
43 import org.graalvm.compiler.nodes.calc.NegateNode;
44 import org.graalvm.compiler.nodes.calc.SubNode;
45
46 public class BasicInductionVariable extends InductionVariable {
47
48 private final ValuePhiNode phi;
49 private final ValueNode init;
50 private ValueNode rawStride;
51 private BinaryArithmeticNode<?> op;
52
53 public BasicInductionVariable(LoopEx loop, ValuePhiNode phi, ValueNode init, ValueNode rawStride, BinaryArithmeticNode<?> op) {
54 super(loop);
55 this.phi = phi;
56 this.init = init;
57 this.rawStride = rawStride;
58 this.op = op;
59 }
60
61 @Override
62 public StructuredGraph graph() {
63 return phi.graph();
64 }
65
66 public BinaryArithmeticNode<?> getOp() {
67 return op;
68 }
69
70 public void setOP(BinaryArithmeticNode<?> newOp) {
71 rawStride = newOp.getY();
72 op = newOp;
73 }
74
75 @Override
76 public Direction direction() {
77 Stamp stamp = rawStride.stamp(NodeView.DEFAULT);
78 if (stamp instanceof IntegerStamp) {
79 IntegerStamp integerStamp = (IntegerStamp) stamp;
80 Direction dir = null;
81 if (integerStamp.isStrictlyPositive()) {
82 dir = Direction.Up;
83 } else if (integerStamp.isStrictlyNegative()) {
84 dir = Direction.Down;
85 }
86 if (dir != null) {
87 if (op instanceof AddNode) {
88 return dir;
89 } else {
90 assert op instanceof SubNode;
91 return dir.opposite();
92 }
93 }
94 }
95 return null;
96 }
97
98 @Override
99 public ValuePhiNode valueNode() {
100 return phi;
101 }
102
103 @Override
104 public ValueNode initNode() {
105 return init;
106 }
107
108 @Override
109 public ValueNode strideNode() {
110 if (op instanceof AddNode) {
111 return rawStride;
112 }
113 if (op instanceof SubNode) {
114 return graph().unique(new NegateNode(rawStride));
115 }
116 throw GraalError.shouldNotReachHere();
117 }
118
119 @Override
120 public boolean isConstantInit() {
121 return init.isConstant();
122 }
123
124 @Override
125 public boolean isConstantStride() {
126 return rawStride.isConstant();
127 }
128
129 @Override
130 public long constantInit() {
131 return init.asJavaConstant().asLong();
132 }
133
134 @Override
135 public long constantStride() {
136 if (op instanceof AddNode) {
137 return rawStride.asJavaConstant().asLong();
138 }
139 if (op instanceof SubNode) {
140 return -rawStride.asJavaConstant().asLong();
141 }
142 throw GraalError.shouldNotReachHere();
143 }
144
145 @Override
146 public ValueNode extremumNode(boolean assumeLoopEntered, Stamp stamp) {
147 Stamp fromStamp = phi.stamp(NodeView.DEFAULT);
148 StructuredGraph graph = graph();
149 ValueNode stride = strideNode();
150 ValueNode initNode = this.initNode();
151 if (!fromStamp.isCompatible(stamp)) {
152 stride = IntegerConvertNode.convert(stride, stamp, graph(), NodeView.DEFAULT);
153 initNode = IntegerConvertNode.convert(initNode, stamp, graph(), NodeView.DEFAULT);
154 }
155 ValueNode maxTripCount = loop.counted().maxTripCountNode(assumeLoopEntered);
156 if (!maxTripCount.stamp(NodeView.DEFAULT).isCompatible(stamp)) {
157 maxTripCount = IntegerConvertNode.convert(maxTripCount, stamp, graph(), NodeView.DEFAULT);
158 }
159 return add(graph, mul(graph, stride, sub(graph, maxTripCount, ConstantNode.forIntegerStamp(stamp, 1, graph))), initNode);
160 }
161
162 @Override
163 public ValueNode exitValueNode() {
164 Stamp stamp = phi.stamp(NodeView.DEFAULT);
165 ValueNode maxTripCount = loop.counted().maxTripCountNode();
166 if (!maxTripCount.stamp(NodeView.DEFAULT).isCompatible(stamp)) {
167 maxTripCount = IntegerConvertNode.convert(maxTripCount, stamp, graph(), NodeView.DEFAULT);
168 }
169 return add(graph(), mul(graph(), strideNode(), maxTripCount), initNode());
170 }
171
172 @Override
173 public boolean isConstantExtremum() {
174 return isConstantInit() && isConstantStride() && loop.counted().isConstantMaxTripCount();
175 }
176
177 @Override
178 public long constantExtremum() {
179 UnsignedLong tripCount = loop.counted().constantMaxTripCount();
180 if (tripCount.isLessThan(1)) {
181 return constantInit();
182 }
183 return tripCount.minus(1).wrappingTimes(constantStride()).wrappingPlus(constantInit()).asLong();
184 }
185
186 @Override
187 public void deleteUnusedNodes() {
188 }
189
190 @Override
191 public String toString() {
192 return String.format("BasicInductionVariable %s %s %s %s", initNode(), phi, op.getNodeClass().shortName(), strideNode());
193 }
194 }