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