1 /*
2 * Copyright (c) 2017, 2017, 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.nodes.calc;
26
27 import static jdk.vm.ci.code.CodeUtil.mask;
28
29 import org.graalvm.compiler.core.common.calc.CanonicalCondition;
30 import org.graalvm.compiler.core.common.type.IntegerStamp;
31 import org.graalvm.compiler.core.common.type.Stamp;
32 import org.graalvm.compiler.graph.NodeClass;
33 import org.graalvm.compiler.nodeinfo.NodeInfo;
34 import org.graalvm.compiler.nodes.ConstantNode;
35 import org.graalvm.compiler.nodes.LogicConstantNode;
36 import org.graalvm.compiler.nodes.LogicNegationNode;
37 import org.graalvm.compiler.nodes.LogicNode;
38 import org.graalvm.compiler.nodes.NodeView;
39 import org.graalvm.compiler.nodes.ValueNode;
40 import org.graalvm.compiler.nodes.util.GraphUtil;
41 import org.graalvm.compiler.options.OptionValues;
42
43 import jdk.vm.ci.meta.ConstantReflectionProvider;
44 import jdk.vm.ci.meta.MetaAccessProvider;
45 import jdk.vm.ci.meta.TriState;
46
47 /**
48 * Common super-class for "a < b" comparisons both {@linkplain IntegerLowerThanNode signed} and
49 * {@linkplain IntegerBelowNode unsigned}.
50 */
51 @NodeInfo()
52 public abstract class IntegerLowerThanNode extends CompareNode {
53 public static final NodeClass<IntegerLowerThanNode> TYPE = NodeClass.create(IntegerLowerThanNode.class);
54 private final LowerOp op;
55
56 protected IntegerLowerThanNode(NodeClass<? extends CompareNode> c, ValueNode x, ValueNode y, LowerOp op) {
57 super(c, op.getCondition(), false, x, y);
58 this.op = op;
59 }
60
61 protected LowerOp getOp() {
62 return op;
63 }
72 return getSucceedingStampForX(!negated, !negated, yStampGeneric, xStampGeneric, getY(), getX());
73 }
74
75 private Stamp getSucceedingStampForX(boolean mirror, boolean strict, Stamp xStampGeneric, Stamp yStampGeneric, ValueNode forX, ValueNode forY) {
76 Stamp s = getSucceedingStampForX(mirror, strict, xStampGeneric, yStampGeneric);
77 if (s != null && s.isUnrestricted()) {
78 s = null;
79 }
80 if (forY instanceof AddNode && xStampGeneric instanceof IntegerStamp) {
81 IntegerStamp xStamp = (IntegerStamp) xStampGeneric;
82 AddNode addNode = (AddNode) forY;
83 IntegerStamp aStamp = null;
84 if (addNode.getX() == forX && addNode.getY().stamp(NodeView.DEFAULT) instanceof IntegerStamp) {
85 // x < x + a
86 aStamp = (IntegerStamp) addNode.getY().stamp(NodeView.DEFAULT);
87 } else if (addNode.getY() == forX && addNode.getX().stamp(NodeView.DEFAULT) instanceof IntegerStamp) {
88 // x < a + x
89 aStamp = (IntegerStamp) addNode.getX().stamp(NodeView.DEFAULT);
90 }
91 if (aStamp != null) {
92 IntegerStamp result = getOp().getSucceedingStampForXLowerXPlusA(mirror, strict, aStamp);
93 result = (IntegerStamp) xStamp.tryImproveWith(result);
94 if (result != null) {
95 if (s != null) {
96 s = s.improveWith(result);
97 } else {
98 s = result;
99 }
100 }
101 }
102 }
103 return s;
104 }
105
106 private Stamp getSucceedingStampForX(boolean mirror, boolean strict, Stamp xStampGeneric, Stamp yStampGeneric) {
107 if (xStampGeneric instanceof IntegerStamp) {
108 IntegerStamp xStamp = (IntegerStamp) xStampGeneric;
109 if (yStampGeneric instanceof IntegerStamp) {
110 IntegerStamp yStamp = (IntegerStamp) yStampGeneric;
111 assert yStamp.getBits() == xStamp.getBits();
112 Stamp s = getOp().getSucceedingStampForX(xStamp, yStamp, mirror, strict);
168
169 protected abstract IntegerLowerThanNode createNode(ValueNode x, ValueNode y);
170
171 public LogicNode create(ValueNode x, ValueNode y, NodeView view) {
172 LogicNode result = CompareNode.tryConstantFoldPrimitive(getCondition(), x, y, false, view);
173 if (result != null) {
174 return result;
175 } else {
176 result = findSynonym(x, y, view);
177 if (result != null) {
178 return result;
179 }
180 return createNode(x, y);
181 }
182 }
183
184 protected LogicNode findSynonym(ValueNode forX, ValueNode forY, NodeView view) {
185 if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) {
186 return LogicConstantNode.contradiction();
187 }
188 TriState fold = tryFold(forX.stamp(view), forY.stamp(view));
189 if (fold.isTrue()) {
190 return LogicConstantNode.tautology();
191 } else if (fold.isFalse()) {
192 return LogicConstantNode.contradiction();
193 }
194 if (forY.stamp(view) instanceof IntegerStamp) {
195 IntegerStamp yStamp = (IntegerStamp) forY.stamp(view);
196 int bits = yStamp.getBits();
197 if (forX.isJavaConstant() && !forY.isConstant()) {
198 // bring the constant on the right
199 long xValue = forX.asJavaConstant().asLong();
200 if (xValue != maxValue(bits)) {
201 // c < x <=> !(c >= x) <=> !(x <= c) <=> !(x < c + 1)
202 return LogicNegationNode.create(create(forY, ConstantNode.forIntegerStamp(yStamp, xValue + 1), view));
203 }
204 }
205 if (forY.isJavaConstant()) {
206 long yValue = forY.asJavaConstant().asLong();
207 if (yValue == maxValue(bits)) {
208 // x < MAX <=> x != MAX
209 return LogicNegationNode.create(IntegerEqualsNode.create(forX, forY, view));
210 }
211 if (yValue == minValue(bits) + 1) {
212 // x < MIN + 1 <=> x <= MIN <=> x == MIN
213 return IntegerEqualsNode.create(forX, ConstantNode.forIntegerStamp(yStamp, minValue(bits)), view);
214 }
215 } else if (forY instanceof AddNode) {
216 AddNode addNode = (AddNode) forY;
217 LogicNode canonical = canonicalizeXLowerXPlusA(forX, addNode, false, true, view);
218 if (canonical != null) {
219 return canonical;
220 }
221 }
222 if (forX instanceof AddNode) {
223 AddNode addNode = (AddNode) forX;
224 LogicNode canonical = canonicalizeXLowerXPlusA(forY, addNode, true, false, view);
225 if (canonical != null) {
226 return canonical;
227 }
228 }
229 }
230 return null;
231 }
232
233 private LogicNode canonicalizeXLowerXPlusA(ValueNode forX, AddNode addNode, boolean mirrored, boolean strict, NodeView view) {
234 // x < x + a
235 IntegerStamp succeedingXStamp;
236 boolean exact;
237 if (addNode.getX() == forX && addNode.getY().stamp(view) instanceof IntegerStamp) {
238 IntegerStamp aStamp = (IntegerStamp) addNode.getY().stamp(view);
239 succeedingXStamp = getSucceedingStampForXLowerXPlusA(mirrored, strict, aStamp);
240 exact = aStamp.lowerBound() == aStamp.upperBound();
241 } else if (addNode.getY() == forX && addNode.getX().stamp(view) instanceof IntegerStamp) {
242 IntegerStamp aStamp = (IntegerStamp) addNode.getX().stamp(view);
243 succeedingXStamp = getSucceedingStampForXLowerXPlusA(mirrored, strict, aStamp);
244 exact = aStamp.lowerBound() == aStamp.upperBound();
245 } else {
246 return null;
247 }
248 if (succeedingXStamp.join(forX.stamp(view)).isEmpty()) {
249 return LogicConstantNode.contradiction();
250 } else if (exact && !succeedingXStamp.isEmpty()) {
251 int bits = succeedingXStamp.getBits();
252 if (compare(lowerBound(succeedingXStamp), minValue(bits)) > 0) {
253 assert upperBound(succeedingXStamp) == maxValue(bits);
254 // x must be in [L..MAX] <=> x >= L <=> !(x < L)
255 return LogicNegationNode.create(create(forX, ConstantNode.forIntegerStamp(succeedingXStamp, lowerBound(succeedingXStamp)), view));
256 } else if (compare(upperBound(succeedingXStamp), maxValue(bits)) < 0) {
257 // x must be in [MIN..H] <=> x <= H <=> !(H < x)
258 return LogicNegationNode.create(create(ConstantNode.forIntegerStamp(succeedingXStamp, upperBound(succeedingXStamp)), forX, view));
259 }
260 }
261 return null;
262 }
263
264 protected TriState tryFold(Stamp xStampGeneric, Stamp yStampGeneric) {
265 if (xStampGeneric instanceof IntegerStamp && yStampGeneric instanceof IntegerStamp) {
266 IntegerStamp xStamp = (IntegerStamp) xStampGeneric;
267 IntegerStamp yStamp = (IntegerStamp) yStampGeneric;
268 if (compare(upperBound(xStamp), lowerBound(yStamp)) < 0) {
269 return TriState.TRUE;
270 }
271 if (compare(lowerBound(xStamp), upperBound(yStamp)) >= 0) {
272 return TriState.FALSE;
273 }
288 }
289 if (compare(low, lowerBound(xStamp)) > 0 || upperBound(xStamp) != (xStamp.upperBound() & mask(xStamp.getBits()))) {
290 return forInteger(bits, low, upperBound(xStamp));
291 }
292 } else {
293 // x < y, i.e., x < y <= Y_UPPER_BOUND so x <= Y_UPPER_BOUND - 1
294 long low = upperBound(yStamp);
295 if (strict) {
296 if (low == minValue(bits)) {
297 return null;
298 }
299 low -= 1;
300 }
301 if (compare(low, upperBound(xStamp)) < 0 || lowerBound(xStamp) != (xStamp.lowerBound() & mask(xStamp.getBits()))) {
302 return forInteger(bits, lowerBound(xStamp), low);
303 }
304 }
305 return null;
306 }
307
308 protected IntegerStamp getSucceedingStampForXLowerXPlusA(boolean mirrored, boolean strict, IntegerStamp a) {
309 int bits = a.getBits();
310 long min = minValue(bits);
311 long max = maxValue(bits);
312 /*
313 * if x < x + a <=> x + a didn't overflow:
314 *
315 * x is outside ]MAX - a, MAX], i.e., inside [MIN, MAX - a]
316 *
317 * if a is negative those bounds wrap around correctly.
318 *
319 * If a is exactly zero this gives an unbounded stamp (any integer) in the positive case
320 * and an empty stamp in the negative case: if x |<| x is true, then either x has no
321 * value or any value...
322 *
323 * This does not use upper/lowerBound from LowerOp because it's about the (signed)
324 * addition not the comparison.
325 */
326 if (mirrored) {
327 if (a.contains(0)) {
328 // a may be zero
329 return a.unrestricted();
330 }
331 return forInteger(bits, min(max - a.lowerBound() + 1, max - a.upperBound() + 1, bits), max);
332 } else {
333 long aLower = a.lowerBound();
334 long aUpper = a.upperBound();
335 if (strict) {
336 if (aLower == 0) {
337 aLower = 1;
338 }
339 if (aUpper == 0) {
340 aUpper = -1;
341 }
342 if (aLower > aUpper) {
343 // impossible
344 return a.empty();
345 }
346 }
347 if (aLower < 0 && aUpper > 0) {
348 // a may be zero
349 return a.unrestricted();
350 }
351 return forInteger(bits, min, max(max - aLower, max - aUpper, bits));
352 }
353 }
354 }
355 }
|
1 /*
2 * Copyright (c) 2017, 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.nodes.calc;
26
27 import static jdk.vm.ci.code.CodeUtil.mask;
28
29 import org.graalvm.compiler.core.common.calc.CanonicalCondition;
30 import org.graalvm.compiler.core.common.type.IntegerStamp;
31 import org.graalvm.compiler.core.common.type.Stamp;
32 import org.graalvm.compiler.graph.NodeClass;
33 import org.graalvm.compiler.nodeinfo.NodeInfo;
34 import org.graalvm.compiler.nodes.ConstantNode;
35 import org.graalvm.compiler.nodes.LogicConstantNode;
36 import org.graalvm.compiler.nodes.LogicNegationNode;
37 import org.graalvm.compiler.nodes.LogicNode;
38 import org.graalvm.compiler.nodes.NodeView;
39 import org.graalvm.compiler.nodes.ValueNode;
40 import org.graalvm.compiler.nodes.util.GraphUtil;
41 import org.graalvm.compiler.options.OptionValues;
42
43 import jdk.vm.ci.code.CodeUtil;
44 import jdk.vm.ci.meta.ConstantReflectionProvider;
45 import jdk.vm.ci.meta.JavaConstant;
46 import jdk.vm.ci.meta.MetaAccessProvider;
47 import jdk.vm.ci.meta.TriState;
48
49 /**
50 * Common super-class for "a < b" comparisons both {@linkplain IntegerLowerThanNode signed} and
51 * {@linkplain IntegerBelowNode unsigned}.
52 */
53 @NodeInfo()
54 public abstract class IntegerLowerThanNode extends CompareNode {
55 public static final NodeClass<IntegerLowerThanNode> TYPE = NodeClass.create(IntegerLowerThanNode.class);
56 private final LowerOp op;
57
58 protected IntegerLowerThanNode(NodeClass<? extends CompareNode> c, ValueNode x, ValueNode y, LowerOp op) {
59 super(c, op.getCondition(), false, x, y);
60 this.op = op;
61 }
62
63 protected LowerOp getOp() {
64 return op;
65 }
74 return getSucceedingStampForX(!negated, !negated, yStampGeneric, xStampGeneric, getY(), getX());
75 }
76
77 private Stamp getSucceedingStampForX(boolean mirror, boolean strict, Stamp xStampGeneric, Stamp yStampGeneric, ValueNode forX, ValueNode forY) {
78 Stamp s = getSucceedingStampForX(mirror, strict, xStampGeneric, yStampGeneric);
79 if (s != null && s.isUnrestricted()) {
80 s = null;
81 }
82 if (forY instanceof AddNode && xStampGeneric instanceof IntegerStamp) {
83 IntegerStamp xStamp = (IntegerStamp) xStampGeneric;
84 AddNode addNode = (AddNode) forY;
85 IntegerStamp aStamp = null;
86 if (addNode.getX() == forX && addNode.getY().stamp(NodeView.DEFAULT) instanceof IntegerStamp) {
87 // x < x + a
88 aStamp = (IntegerStamp) addNode.getY().stamp(NodeView.DEFAULT);
89 } else if (addNode.getY() == forX && addNode.getX().stamp(NodeView.DEFAULT) instanceof IntegerStamp) {
90 // x < a + x
91 aStamp = (IntegerStamp) addNode.getX().stamp(NodeView.DEFAULT);
92 }
93 if (aStamp != null) {
94 IntegerStamp result = getOp().getSucceedingStampForXLowerXPlusA(mirror, strict, aStamp, xStamp);
95 result = (IntegerStamp) xStamp.tryImproveWith(result);
96 if (result != null) {
97 if (s != null) {
98 s = s.improveWith(result);
99 } else {
100 s = result;
101 }
102 }
103 }
104 }
105 return s;
106 }
107
108 private Stamp getSucceedingStampForX(boolean mirror, boolean strict, Stamp xStampGeneric, Stamp yStampGeneric) {
109 if (xStampGeneric instanceof IntegerStamp) {
110 IntegerStamp xStamp = (IntegerStamp) xStampGeneric;
111 if (yStampGeneric instanceof IntegerStamp) {
112 IntegerStamp yStamp = (IntegerStamp) yStampGeneric;
113 assert yStamp.getBits() == xStamp.getBits();
114 Stamp s = getOp().getSucceedingStampForX(xStamp, yStamp, mirror, strict);
170
171 protected abstract IntegerLowerThanNode createNode(ValueNode x, ValueNode y);
172
173 public LogicNode create(ValueNode x, ValueNode y, NodeView view) {
174 LogicNode result = CompareNode.tryConstantFoldPrimitive(getCondition(), x, y, false, view);
175 if (result != null) {
176 return result;
177 } else {
178 result = findSynonym(x, y, view);
179 if (result != null) {
180 return result;
181 }
182 return createNode(x, y);
183 }
184 }
185
186 protected LogicNode findSynonym(ValueNode forX, ValueNode forY, NodeView view) {
187 if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) {
188 return LogicConstantNode.contradiction();
189 }
190 Stamp xStampGeneric = forX.stamp(view);
191 TriState fold = tryFold(xStampGeneric, forY.stamp(view));
192 if (fold.isTrue()) {
193 return LogicConstantNode.tautology();
194 } else if (fold.isFalse()) {
195 return LogicConstantNode.contradiction();
196 }
197 if (forY.stamp(view) instanceof IntegerStamp) {
198 IntegerStamp yStamp = (IntegerStamp) forY.stamp(view);
199 IntegerStamp xStamp = (IntegerStamp) xStampGeneric;
200 int bits = yStamp.getBits();
201 if (forX.isJavaConstant() && !forY.isConstant()) {
202 // bring the constant on the right
203 long xValue = forX.asJavaConstant().asLong();
204 if (xValue != maxValue(bits)) {
205 // c < x <=> !(c >= x) <=> !(x <= c) <=> !(x < c + 1)
206 return LogicNegationNode.create(create(forY, ConstantNode.forIntegerStamp(yStamp, xValue + 1), view));
207 }
208 }
209 if (forY.isJavaConstant()) {
210 long yValue = forY.asJavaConstant().asLong();
211
212 // x < MAX <=> x != MAX
213 if (yValue == maxValue(bits)) {
214 return LogicNegationNode.create(IntegerEqualsNode.create(forX, forY, view));
215 }
216
217 // x < MIN + 1 <=> x <= MIN <=> x == MIN
218 if (yValue == minValue(bits) + 1) {
219 return IntegerEqualsNode.create(forX, ConstantNode.forIntegerStamp(yStamp, minValue(bits)), view);
220 }
221
222 // (x < c && x >= c - 1) => x == c - 1
223 // If the constant is negative, only signed comparison is allowed.
224 if (yValue != minValue(bits) && xStamp.lowerBound() == yValue - 1 && (yValue > 0 || getCondition() == CanonicalCondition.LT)) {
225 return IntegerEqualsNode.create(forX, ConstantNode.forIntegerStamp(yStamp, yValue - 1), view);
226 }
227
228 } else if (forY instanceof AddNode) {
229 AddNode addNode = (AddNode) forY;
230 LogicNode canonical = canonicalizeXLowerXPlusA(forX, addNode, false, true, view);
231 if (canonical != null) {
232 return canonical;
233 }
234 }
235 if (forX instanceof AddNode) {
236 AddNode addNode = (AddNode) forX;
237 LogicNode canonical = canonicalizeXLowerXPlusA(forY, addNode, true, false, view);
238 if (canonical != null) {
239 return canonical;
240 }
241 }
242 }
243 return null;
244 }
245
246 /**
247 * Exploit the fact that adding the (signed) MIN_VALUE on both side flips signed and
248 * unsigned comparison.
249 *
250 * In particular:
251 * <ul>
252 * <li>{@code x + MIN_VALUE < y + MIN_VALUE <=> x |<| y}</li>
253 * <li>{@code x + MIN_VALUE |<| y + MIN_VALUE <=> x < y}</li>
254 * </ul>
255 */
256 protected static LogicNode canonicalizeRangeFlip(ValueNode forX, ValueNode forY, int bits, boolean signed, NodeView view) {
257 long min = CodeUtil.minValue(bits);
258 long xResidue = 0;
259 ValueNode left = null;
260 JavaConstant leftCst = null;
261 if (forX instanceof AddNode) {
262 AddNode xAdd = (AddNode) forX;
263 if (xAdd.getY().isJavaConstant() && !xAdd.getY().asJavaConstant().isDefaultForKind()) {
264 long xCst = xAdd.getY().asJavaConstant().asLong();
265 xResidue = xCst - min;
266 left = xAdd.getX();
267 }
268 } else if (forX.isJavaConstant()) {
269 leftCst = forX.asJavaConstant();
270 }
271 if (left == null && leftCst == null) {
272 return null;
273 }
274 long yResidue = 0;
275 ValueNode right = null;
276 JavaConstant rightCst = null;
277 if (forY instanceof AddNode) {
278 AddNode yAdd = (AddNode) forY;
279 if (yAdd.getY().isJavaConstant() && !yAdd.getY().asJavaConstant().isDefaultForKind()) {
280 long yCst = yAdd.getY().asJavaConstant().asLong();
281 yResidue = yCst - min;
282 right = yAdd.getX();
283 }
284 } else if (forY.isJavaConstant()) {
285 rightCst = forY.asJavaConstant();
286 }
287 if (right == null && rightCst == null) {
288 return null;
289 }
290 if ((xResidue == 0 && left != null) || (yResidue == 0 && right != null)) {
291 if (left == null) {
292 left = ConstantNode.forIntegerBits(bits, leftCst.asLong() - min);
293 } else if (xResidue != 0) {
294 left = AddNode.create(left, ConstantNode.forIntegerBits(bits, xResidue), view);
295 }
296 if (right == null) {
297 right = ConstantNode.forIntegerBits(bits, rightCst.asLong() - min);
298 } else if (yResidue != 0) {
299 right = AddNode.create(right, ConstantNode.forIntegerBits(bits, yResidue), view);
300 }
301 if (signed) {
302 return new IntegerBelowNode(left, right);
303 } else {
304 return new IntegerLessThanNode(left, right);
305 }
306 }
307 return null;
308 }
309
310 private LogicNode canonicalizeXLowerXPlusA(ValueNode forX, AddNode addNode, boolean mirrored, boolean strict, NodeView view) {
311 // x < x + a
312 // x |<| x + a
313 IntegerStamp xStamp = (IntegerStamp) forX.stamp(view);
314 IntegerStamp succeedingXStamp;
315 boolean exact;
316 if (addNode.getX() == forX && addNode.getY().stamp(view) instanceof IntegerStamp) {
317 IntegerStamp aStamp = (IntegerStamp) addNode.getY().stamp(view);
318 succeedingXStamp = getSucceedingStampForXLowerXPlusA(mirrored, strict, aStamp, xStamp);
319 exact = aStamp.lowerBound() == aStamp.upperBound();
320 } else if (addNode.getY() == forX && addNode.getX().stamp(view) instanceof IntegerStamp) {
321 IntegerStamp aStamp = (IntegerStamp) addNode.getX().stamp(view);
322 succeedingXStamp = getSucceedingStampForXLowerXPlusA(mirrored, strict, aStamp, xStamp);
323 exact = aStamp.lowerBound() == aStamp.upperBound();
324 } else {
325 return null;
326 }
327 if (succeedingXStamp.join(forX.stamp(view)).isEmpty()) {
328 return LogicConstantNode.contradiction();
329 } else if (exact && !succeedingXStamp.isEmpty()) {
330 int bits = succeedingXStamp.getBits();
331 if (compare(lowerBound(succeedingXStamp), minValue(bits)) > 0) {
332 // x must be in [L..MAX] <=> x >= L <=> !(x < L)
333 return LogicNegationNode.create(create(forX, ConstantNode.forIntegerStamp(succeedingXStamp, lowerBound(succeedingXStamp)), view));
334 } else if (compare(upperBound(succeedingXStamp), maxValue(bits)) < 0) {
335 // x must be in [MIN..H] <=> x <= H <=> !(H < x)
336 return LogicNegationNode.create(create(ConstantNode.forIntegerStamp(succeedingXStamp, upperBound(succeedingXStamp)), forX, view));
337 }
338 }
339 return null;
340 }
341
342 protected TriState tryFold(Stamp xStampGeneric, Stamp yStampGeneric) {
343 if (xStampGeneric instanceof IntegerStamp && yStampGeneric instanceof IntegerStamp) {
344 IntegerStamp xStamp = (IntegerStamp) xStampGeneric;
345 IntegerStamp yStamp = (IntegerStamp) yStampGeneric;
346 if (compare(upperBound(xStamp), lowerBound(yStamp)) < 0) {
347 return TriState.TRUE;
348 }
349 if (compare(lowerBound(xStamp), upperBound(yStamp)) >= 0) {
350 return TriState.FALSE;
351 }
366 }
367 if (compare(low, lowerBound(xStamp)) > 0 || upperBound(xStamp) != (xStamp.upperBound() & mask(xStamp.getBits()))) {
368 return forInteger(bits, low, upperBound(xStamp));
369 }
370 } else {
371 // x < y, i.e., x < y <= Y_UPPER_BOUND so x <= Y_UPPER_BOUND - 1
372 long low = upperBound(yStamp);
373 if (strict) {
374 if (low == minValue(bits)) {
375 return null;
376 }
377 low -= 1;
378 }
379 if (compare(low, upperBound(xStamp)) < 0 || lowerBound(xStamp) != (xStamp.lowerBound() & mask(xStamp.getBits()))) {
380 return forInteger(bits, lowerBound(xStamp), low);
381 }
382 }
383 return null;
384 }
385
386 protected IntegerStamp getSucceedingStampForXLowerXPlusA(boolean mirrored, boolean strict, IntegerStamp aStamp, IntegerStamp xStamp) {
387 int bits = aStamp.getBits();
388 long min = minValue(bits);
389 long max = maxValue(bits);
390
391 /*
392 * if x < x + a <=> x + a didn't overflow:
393 *
394 * x is outside ]MAX - a, MAX], i.e., inside [MIN, MAX - a]
395 *
396 * if a is negative those bounds wrap around correctly.
397 *
398 * If a is exactly zero this gives an unbounded stamp (any integer) in the positive case
399 * and an empty stamp in the negative case: if x |<| x is true, then either x has no
400 * value or any value...
401 *
402 * This does not use upper/lowerBound from LowerOp because it's about the (signed)
403 * addition not the comparison.
404 */
405 if (mirrored) {
406 if (aStamp.contains(0)) {
407 // a may be zero
408 return aStamp.unrestricted();
409 }
410 return forInteger(bits, min(max - aStamp.lowerBound() + 1, max - aStamp.upperBound() + 1, bits), min(max, upperBound(xStamp)));
411 } else {
412 long aLower = aStamp.lowerBound();
413 long aUpper = aStamp.upperBound();
414 if (strict) {
415 if (aLower == 0) {
416 aLower = 1;
417 }
418 if (aUpper == 0) {
419 aUpper = -1;
420 }
421 if (aLower > aUpper) {
422 // impossible
423 return aStamp.empty();
424 }
425 }
426 if (aLower < 0 && aUpper > 0) {
427 // a may be zero
428 return aStamp.unrestricted();
429 }
430 return forInteger(bits, min, max(max - aLower, max - aUpper, bits));
431 }
432 }
433 }
434 }
|