1 /*
2 * Copyright (c) 2011, 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.nodes.calc;
24
25 import org.graalvm.compiler.core.common.calc.Condition;
26 import org.graalvm.compiler.core.common.type.FloatStamp;
27 import org.graalvm.compiler.core.common.type.IntegerStamp;
28 import org.graalvm.compiler.core.common.type.Stamp;
29 import org.graalvm.compiler.core.common.type.StampFactory;
30 import org.graalvm.compiler.debug.GraalError;
31 import org.graalvm.compiler.graph.IterableNodeType;
32 import org.graalvm.compiler.graph.NodeClass;
33 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
34 import org.graalvm.compiler.nodeinfo.NodeInfo;
35 import org.graalvm.compiler.nodes.LogicConstantNode;
36 import org.graalvm.compiler.nodes.LogicNode;
37 import org.graalvm.compiler.nodes.ValueNode;
38 import org.graalvm.compiler.nodes.util.GraphUtil;
39
40 import jdk.vm.ci.code.CodeUtil;
41 import jdk.vm.ci.meta.Constant;
42 import jdk.vm.ci.meta.ConstantReflectionProvider;
43 import jdk.vm.ci.meta.JavaKind;
44 import jdk.vm.ci.meta.PrimitiveConstant;
45 import jdk.vm.ci.meta.TriState;
46
47 @NodeInfo(shortName = "<")
48 public final class IntegerLessThanNode extends CompareNode implements IterableNodeType {
49 public static final NodeClass<IntegerLessThanNode> TYPE = NodeClass.create(IntegerLessThanNode.class);
50
51 public IntegerLessThanNode(ValueNode x, ValueNode y) {
52 super(TYPE, Condition.LT, false, x, y);
53 assert !x.getStackKind().isNumericFloat() && x.getStackKind() != JavaKind.Object;
54 assert !y.getStackKind().isNumericFloat() && y.getStackKind() != JavaKind.Object;
55 }
56
57 public static LogicNode create(ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection) {
58 LogicNode result = CompareNode.tryConstantFold(Condition.LT, x, y, constantReflection, false);
59 if (result != null) {
60 return result;
61 } else {
62 result = findSynonym(x, y);
63 if (result != null) {
64 return result;
65 }
66 return new IntegerLessThanNode(x, y);
67 }
68 }
69
70 @Override
71 protected ValueNode optimizeNormalizeCmp(Constant constant, NormalizeCompareNode normalizeNode, boolean mirrored) {
72 PrimitiveConstant primitive = (PrimitiveConstant) constant;
73 assert condition() == Condition.LT;
74 if (primitive.getJavaKind() == JavaKind.Int && primitive.asInt() == 0) {
75 ValueNode a = mirrored ? normalizeNode.getY() : normalizeNode.getX();
76 ValueNode b = mirrored ? normalizeNode.getX() : normalizeNode.getY();
77
78 if (normalizeNode.getX().getStackKind() == JavaKind.Double || normalizeNode.getX().getStackKind() == JavaKind.Float) {
79 return new FloatLessThanNode(a, b, mirrored ^ normalizeNode.isUnorderedLess);
80 } else {
81 return new IntegerLessThanNode(a, b);
82 }
83 }
84 return this;
85 }
86
87 public static boolean subtractMayUnderflow(long x, long y, long minValue) {
88 long r = x - y;
89 // HD 2-12 Overflow iff the arguments have different signs and
90 // the sign of the result is different than the sign of x
91 return (((x ^ y) & (x ^ r)) < 0) || r <= minValue;
92 }
93
94 public static boolean subtractMayOverflow(long x, long y, long maxValue) {
95 long r = x - y;
96 // HD 2-12 Overflow iff the arguments have different signs and
97 // the sign of the result is different than the sign of x
98 return (((x ^ y) & (x ^ r)) < 0) || r > maxValue;
99 }
100
101 @Override
102 public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
103 ValueNode result = super.canonical(tool, forX, forY);
104 if (result != this) {
105 return result;
106 }
107 ValueNode synonym = findSynonym(forX, forY);
108 if (synonym != null) {
109 return synonym;
110 }
111 if (forX.stamp() instanceof IntegerStamp && forY.stamp() instanceof IntegerStamp) {
112 if (IntegerStamp.sameSign((IntegerStamp) forX.stamp(), (IntegerStamp) forY.stamp())) {
113 return new IntegerBelowNode(forX, forY);
114 }
115 }
116 if (forY.isConstant() && forY.asConstant().isDefaultForKind() && forX instanceof SubNode) {
117 // (x - y) < 0 when x - y is known not to underflow == x < y
118 SubNode sub = (SubNode) forX;
119 IntegerStamp xStamp = (IntegerStamp) sub.getX().stamp();
120 IntegerStamp yStamp = (IntegerStamp) sub.getY().stamp();
121 long minValue = CodeUtil.minValue(xStamp.getBits());
122 long maxValue = CodeUtil.maxValue(xStamp.getBits());
123
124 if (!subtractMayUnderflow(xStamp.lowerBound(), yStamp.upperBound(), minValue) && !subtractMayOverflow(xStamp.upperBound(), yStamp.lowerBound(), maxValue)) {
125 return new IntegerLessThanNode(sub.getX(), sub.getY());
126 }
127 }
128 return this;
129 }
130
131 private static LogicNode findSynonym(ValueNode forX, ValueNode forY) {
132 if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) {
133 return LogicConstantNode.contradiction();
134 } else if (forX.stamp() instanceof IntegerStamp && forY.stamp() instanceof IntegerStamp) {
135 IntegerStamp xStamp = (IntegerStamp) forX.stamp();
136 IntegerStamp yStamp = (IntegerStamp) forY.stamp();
137 if (xStamp.upperBound() < yStamp.lowerBound()) {
138 return LogicConstantNode.tautology();
139 } else if (xStamp.lowerBound() >= yStamp.upperBound()) {
140 return LogicConstantNode.contradiction();
141 }
142 }
143 return null;
144 }
145
146 @Override
147 protected CompareNode duplicateModified(ValueNode newX, ValueNode newY) {
148 if (newX.stamp() instanceof FloatStamp && newY.stamp() instanceof FloatStamp) {
149 return new FloatLessThanNode(newX, newY, true);
150 } else if (newX.stamp() instanceof IntegerStamp && newY.stamp() instanceof IntegerStamp) {
151 return new IntegerLessThanNode(newX, newY);
152 }
153 throw GraalError.shouldNotReachHere();
154 }
155
156 @Override
157 public Stamp getSucceedingStampForX(boolean negated) {
158 Stamp xStampGeneric = getX().stamp();
159 Stamp yStampGeneric = getY().stamp();
160 if (xStampGeneric instanceof IntegerStamp) {
161 IntegerStamp xStamp = (IntegerStamp) xStampGeneric;
162 int bits = xStamp.getBits();
163 if (yStampGeneric instanceof IntegerStamp) {
164 IntegerStamp yStamp = (IntegerStamp) yStampGeneric;
165 assert yStamp.getBits() == bits;
166 if (negated) {
167 // x >= y
168 long xLowerBound = xStamp.lowerBound();
169 long yLowerBound = yStamp.lowerBound();
170 if (yLowerBound > xLowerBound) {
171 return StampFactory.forIntegerWithMask(bits, yLowerBound, xStamp.upperBound(), xStamp);
172 }
173 } else {
174 // x < y
175 long xUpperBound = xStamp.upperBound();
176 long yUpperBound = yStamp.upperBound();
177 if (yUpperBound == CodeUtil.minValue(bits)) {
178 return null;
179 } else if (yUpperBound <= xUpperBound) {
180 assert yUpperBound != CodeUtil.minValue(bits);
181 return StampFactory.forIntegerWithMask(bits, xStamp.lowerBound(), yUpperBound - 1, xStamp);
182 }
183 }
184 }
185 }
186 return null;
187 }
188
189 @Override
190 public Stamp getSucceedingStampForY(boolean negated) {
191 Stamp xStampGeneric = getX().stamp();
192 Stamp yStampGeneric = getY().stamp();
193 if (xStampGeneric instanceof IntegerStamp) {
194 IntegerStamp xStamp = (IntegerStamp) xStampGeneric;
195 int bits = xStamp.getBits();
196 if (yStampGeneric instanceof IntegerStamp) {
197 IntegerStamp yStamp = (IntegerStamp) yStampGeneric;
198 assert yStamp.getBits() == bits;
199 if (negated) {
200 // y <= x
201 long xUpperBound = xStamp.upperBound();
202 long yUpperBound = yStamp.upperBound();
203 if (xUpperBound < yUpperBound) {
204 return StampFactory.forIntegerWithMask(bits, yStamp.lowerBound(), xUpperBound, yStamp);
205 }
206 } else {
207 // y > x
208 long xLowerBound = xStamp.lowerBound();
209 long yLowerBound = yStamp.lowerBound();
210 if (xLowerBound == CodeUtil.maxValue(bits)) {
211 return null;
212 } else if (xLowerBound >= yLowerBound) {
213 assert xLowerBound != CodeUtil.maxValue(bits);
214 return StampFactory.forIntegerWithMask(bits, xLowerBound + 1, yStamp.upperBound(), yStamp);
215 }
216 }
217 }
218 }
219 return null;
220 }
221
222 @Override
223 public TriState tryFold(Stamp xStampGeneric, Stamp yStampGeneric) {
224 if (xStampGeneric instanceof IntegerStamp && yStampGeneric instanceof IntegerStamp) {
225 IntegerStamp xStamp = (IntegerStamp) xStampGeneric;
226 IntegerStamp yStamp = (IntegerStamp) yStampGeneric;
227 if (xStamp.upperBound() < yStamp.lowerBound()) {
228 return TriState.TRUE;
229 }
230 if (xStamp.lowerBound() >= yStamp.upperBound()) {
231 return TriState.FALSE;
232 }
233 }
234 return TriState.UNKNOWN;
235 }
236 }