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.nodes.test;
26 
27 import static org.graalvm.compiler.core.test.GraalCompilerTest.getInitialOptions;
28 import static org.junit.Assert.assertEquals;
29 import static org.junit.Assert.assertFalse;
30 
31 import java.math.BigInteger;
32 import java.util.Arrays;
33 import java.util.List;
34 import java.util.stream.Stream;
35 
36 import org.graalvm.compiler.core.common.type.ArithmeticOpTable;
37 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp;
38 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.IntegerConvertOp;
39 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.ShiftOp;
40 import org.graalvm.compiler.core.common.type.IntegerStamp;
41 import org.graalvm.compiler.core.common.type.Stamp;
42 import org.graalvm.compiler.core.common.type.StampFactory;
43 import org.graalvm.compiler.debug.DebugContext;
44 import org.graalvm.compiler.graph.test.GraphTest;
45 import org.graalvm.compiler.nodes.ConstantNode;
46 import org.graalvm.compiler.nodes.NodeView;
47 import org.graalvm.compiler.nodes.StructuredGraph;
48 import org.graalvm.compiler.nodes.StructuredGraph.AllowAssumptions;
49 import org.graalvm.compiler.options.OptionValues;
50 import org.junit.Assert;
51 import org.junit.Before;
52 import org.junit.Test;
53 
54 import jdk.vm.ci.meta.JavaConstant;
55 import jdk.vm.ci.meta.JavaKind;
56 
57 /**
58  * This class tests that integer stamps are created correctly for constants.
59  */
60 public class IntegerStampTest extends GraphTest {
61 
62     private StructuredGraph graph;
63 
addIntStamp(Stamp a, Stamp b)64     private static Stamp addIntStamp(Stamp a, Stamp b) {
65         return IntegerStamp.OPS.getAdd().foldStamp(a, b);
66     }
67 
68     @Before
before()69     public void before() {
70         OptionValues options = getInitialOptions();
71         DebugContext debug = getDebug(options);
72         graph = new StructuredGraph.Builder(options, debug, AllowAssumptions.YES).build();
73     }
74 
75     @Test
testBooleanConstant()76     public void testBooleanConstant() {
77         assertEquals(IntegerStamp.create(32, 1, 1, 0x1, 0x1), ConstantNode.forBoolean(true, graph).stamp(NodeView.DEFAULT));
78         assertEquals(IntegerStamp.create(32, 0, 0, 0x0, 0x0), ConstantNode.forBoolean(false, graph).stamp(NodeView.DEFAULT));
79     }
80 
81     @Test
testByteConstant()82     public void testByteConstant() {
83         assertEquals(IntegerStamp.create(32, 0, 0, 0x0, 0x0), ConstantNode.forByte((byte) 0, graph).stamp(NodeView.DEFAULT));
84         assertEquals(IntegerStamp.create(32, 16, 16, 0x10, 0x10), ConstantNode.forByte((byte) 16, graph).stamp(NodeView.DEFAULT));
85         assertEquals(IntegerStamp.create(32, -16, -16, 0xfffffff0L, 0xfffffff0L), ConstantNode.forByte((byte) -16, graph).stamp(NodeView.DEFAULT));
86         assertEquals(IntegerStamp.create(32, 127, 127, 0x7f, 0x7f), ConstantNode.forByte((byte) 127, graph).stamp(NodeView.DEFAULT));
87         assertEquals(IntegerStamp.create(32, -128, -128, 0xffffff80L, 0xffffff80L), ConstantNode.forByte((byte) -128, graph).stamp(NodeView.DEFAULT));
88     }
89 
90     @Test
testShortConstant()91     public void testShortConstant() {
92         assertEquals(IntegerStamp.create(32, 0, 0, 0x0, 0x0), ConstantNode.forShort((short) 0, graph).stamp(NodeView.DEFAULT));
93         assertEquals(IntegerStamp.create(32, 128, 128, 0x80, 0x80), ConstantNode.forShort((short) 128, graph).stamp(NodeView.DEFAULT));
94         assertEquals(IntegerStamp.create(32, -128, -128, 0xffffff80L, 0xffffff80L), ConstantNode.forShort((short) -128, graph).stamp(NodeView.DEFAULT));
95         assertEquals(IntegerStamp.create(32, 32767, 32767, 0x7fff, 0x7fff), ConstantNode.forShort((short) 32767, graph).stamp(NodeView.DEFAULT));
96         assertEquals(IntegerStamp.create(32, -32768, -32768, 0xffff8000L, 0xffff8000L), ConstantNode.forShort((short) -32768, graph).stamp(NodeView.DEFAULT));
97     }
98 
99     @Test
testCharConstant()100     public void testCharConstant() {
101         assertEquals(IntegerStamp.create(32, 0, 0, 0x0, 0x0), ConstantNode.forChar((char) 0, graph).stamp(NodeView.DEFAULT));
102         assertEquals(IntegerStamp.create(32, 'A', 'A', 'A', 'A'), ConstantNode.forChar('A', graph).stamp(NodeView.DEFAULT));
103         assertEquals(IntegerStamp.create(32, 128, 128, 0x80, 0x80), ConstantNode.forChar((char) 128, graph).stamp(NodeView.DEFAULT));
104         assertEquals(IntegerStamp.create(32, 65535, 65535, 0xffff, 0xffff), ConstantNode.forChar((char) 65535, graph).stamp(NodeView.DEFAULT));
105     }
106 
107     @Test
testIntConstant()108     public void testIntConstant() {
109         assertEquals(IntegerStamp.create(32, 0, 0, 0x0, 0x0), ConstantNode.forInt(0, graph).stamp(NodeView.DEFAULT));
110         assertEquals(IntegerStamp.create(32, 128, 128, 0x80, 0x80), ConstantNode.forInt(128, graph).stamp(NodeView.DEFAULT));
111         assertEquals(IntegerStamp.create(32, -128, -128, 0xffffff80L, 0xffffff80L), ConstantNode.forInt(-128, graph).stamp(NodeView.DEFAULT));
112         assertEquals(IntegerStamp.create(32, Integer.MAX_VALUE, Integer.MAX_VALUE, 0x7fffffff, 0x7fffffff), ConstantNode.forInt(Integer.MAX_VALUE, graph).stamp(NodeView.DEFAULT));
113         assertEquals(IntegerStamp.create(32, Integer.MIN_VALUE, Integer.MIN_VALUE, 0x80000000L, 0x80000000L), ConstantNode.forInt(Integer.MIN_VALUE, graph).stamp(NodeView.DEFAULT));
114     }
115 
116     @Test
testLongConstant()117     public void testLongConstant() {
118         assertEquals(IntegerStamp.create(64, 0, 0, 0x0, 0x0), ConstantNode.forLong(0, graph).stamp(NodeView.DEFAULT));
119         assertEquals(IntegerStamp.create(64, 128, 128, 0x80, 0x80), ConstantNode.forLong(128, graph).stamp(NodeView.DEFAULT));
120         assertEquals(IntegerStamp.create(64, -128, -128, 0xffffffffffffff80L, 0xffffffffffffff80L), ConstantNode.forLong(-128, graph).stamp(NodeView.DEFAULT));
121         assertEquals(IntegerStamp.create(64, Long.MAX_VALUE, Long.MAX_VALUE, 0x7fffffffffffffffL, 0x7fffffffffffffffL), ConstantNode.forLong(Long.MAX_VALUE, graph).stamp(NodeView.DEFAULT));
122         assertEquals(IntegerStamp.create(64, Long.MIN_VALUE, Long.MIN_VALUE, 0x8000000000000000L, 0x8000000000000000L), ConstantNode.forLong(Long.MIN_VALUE, graph).stamp(NodeView.DEFAULT));
123     }
124 
125     @Test
testPositiveRanges()126     public void testPositiveRanges() {
127         assertEquals(IntegerStamp.create(32, 0, 0, 0, 0), StampFactory.forInteger(JavaKind.Int, 0, 0));
128         assertEquals(IntegerStamp.create(32, 0, 1, 0, 1), StampFactory.forInteger(JavaKind.Int, 0, 1));
129         assertEquals(IntegerStamp.create(32, 0, 0x123, 0, 0x1ff), StampFactory.forInteger(JavaKind.Int, 0, 0x123));
130         assertEquals(IntegerStamp.create(32, 0x120, 0x123, 0x120, 0x123), StampFactory.forInteger(JavaKind.Int, 0x120, 0x123));
131         assertEquals(IntegerStamp.create(32, 10000, 15000, 0x2000, 0x3fff), StampFactory.forInteger(JavaKind.Int, 10000, 15000));
132         assertEquals(IntegerStamp.create(64, 0, 1, 0, 1), StampFactory.forInteger(JavaKind.Long, 0, 1));
133         assertEquals(IntegerStamp.create(64, 10000, 15000, 0x2000, 0x3fff), StampFactory.forInteger(JavaKind.Long, 10000, 15000));
134         assertEquals(IntegerStamp.create(64, 140000000000L, 150000000000L, 0x2000000000L, 0x23ffffffffL), StampFactory.forInteger(JavaKind.Long, 140000000000L, 150000000000L));
135     }
136 
137     @Test
testNegativeRanges()138     public void testNegativeRanges() {
139         assertEquals(IntegerStamp.create(32, -2, -1, 0xfffffffeL, 0xffffffffL), StampFactory.forInteger(JavaKind.Int, -2, -1));
140         assertEquals(IntegerStamp.create(32, -20, -10, 0xffffffe0L, 0xffffffffL), StampFactory.forInteger(JavaKind.Int, -20, -10));
141         assertEquals(IntegerStamp.create(32, -10000, 0, 0, 0xffffffffL), StampFactory.forInteger(JavaKind.Int, -10000, 0));
142         assertEquals(IntegerStamp.create(32, -10000, -1, 0xffffc000L, 0xffffffffL), StampFactory.forInteger(JavaKind.Int, -10000, -1));
143         assertEquals(IntegerStamp.create(32, -10010, -10000, 0xffffd8e0L, 0xffffd8ffL), StampFactory.forInteger(JavaKind.Int, -10010, -10000));
144         assertEquals(IntegerStamp.create(64, -2, -1, 0xfffffffffffffffeL, 0xffffffffffffffffL), StampFactory.forInteger(JavaKind.Long, -2, -1));
145         assertEquals(IntegerStamp.create(64, -10010, -10000, 0xffffffffffffd8e0L, 0xffffffffffffd8ffL), StampFactory.forInteger(JavaKind.Long, -10010, -10000));
146         assertEquals(IntegerStamp.create(64, -150000000000L, -140000000000L, 0xffffffdc00000000L, 0xffffffdfffffffffL), StampFactory.forInteger(JavaKind.Long, -150000000000L, -140000000000L));
147     }
148 
149     @Test
testMixedRanges()150     public void testMixedRanges() {
151         assertEquals(IntegerStamp.create(32, -1, 0, 0, 0xffffffffL), StampFactory.forInteger(JavaKind.Int, -1, 0));
152         assertEquals(IntegerStamp.create(32, -10000, 1000, 0, 0xffffffffL), StampFactory.forInteger(JavaKind.Int, -10000, 1000));
153         assertEquals(IntegerStamp.create(64, -10000, 1000, 0, 0xffffffffffffffffL), StampFactory.forInteger(JavaKind.Long, -10000, 1000));
154     }
155 
narrowingKindConversion(IntegerStamp stamp, JavaKind kind)156     private static Stamp narrowingKindConversion(IntegerStamp stamp, JavaKind kind) {
157         Stamp narrow = IntegerStamp.OPS.getNarrow().foldStamp(stamp.getBits(), kind.getBitCount(), stamp);
158         IntegerConvertOp<?> implicitExtend = kind.isUnsigned() ? IntegerStamp.OPS.getZeroExtend() : IntegerStamp.OPS.getSignExtend();
159         return implicitExtend.foldStamp(kind.getBitCount(), 32, narrow);
160     }
161 
162     @Test
testNarrowingConversions()163     public void testNarrowingConversions() {
164         // byte cases
165         assertEquals(StampFactory.forInteger(JavaKind.Int, 0, 0), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, 0, 0), JavaKind.Byte));
166         assertEquals(StampFactory.forInteger(JavaKind.Int, 0, 10), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, 0, 10), JavaKind.Byte));
167         assertEquals(StampFactory.forInteger(JavaKind.Int, 10, 20), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, 10, 20), JavaKind.Byte));
168         assertEquals(StampFactory.forInteger(JavaKind.Int, -10, 0), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, -10, 0), JavaKind.Byte));
169         assertEquals(StampFactory.forInteger(JavaKind.Int, -20, -10), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, -20, -10), JavaKind.Byte));
170         assertEquals(StampFactory.forInteger(JavaKind.Int, Byte.MIN_VALUE, Byte.MAX_VALUE), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, 100, 200), JavaKind.Byte));
171         assertEquals(StampFactory.forInteger(JavaKind.Int, Byte.MIN_VALUE, Byte.MAX_VALUE), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, -100, 200), JavaKind.Byte));
172         assertEquals(StampFactory.forInteger(JavaKind.Int, Byte.MIN_VALUE, Byte.MAX_VALUE), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, -200, -100), JavaKind.Byte));
173         // char cases
174         assertEquals(StampFactory.forInteger(JavaKind.Int, 0, 10), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, 0, 10), JavaKind.Char));
175         assertEquals(StampFactory.forInteger(JavaKind.Int, 10, 20), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, 10, 20), JavaKind.Char));
176         assertEquals(StampFactory.forInteger(JavaKind.Int, Character.MIN_VALUE, Character.MAX_VALUE), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, 20000, 80000), JavaKind.Char));
177         assertEquals(StampFactory.forInteger(JavaKind.Int, Character.MIN_VALUE, Character.MAX_VALUE), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, -10000, 40000), JavaKind.Char));
178         assertEquals(StampFactory.forInteger(JavaKind.Int, Character.MIN_VALUE, Character.MAX_VALUE), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, -40000, -10000), JavaKind.Char));
179         // short cases
180         assertEquals(StampFactory.forInteger(JavaKind.Int, 0, 10), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, 0, 10), JavaKind.Short));
181         assertEquals(StampFactory.forInteger(JavaKind.Int, 10, 20), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, 10, 20), JavaKind.Short));
182         assertEquals(StampFactory.forInteger(JavaKind.Int, Short.MIN_VALUE, Short.MAX_VALUE), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, 20000, 40000), JavaKind.Short));
183         assertEquals(StampFactory.forInteger(JavaKind.Int, Short.MIN_VALUE, Short.MAX_VALUE), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, -10000, 40000), JavaKind.Short));
184         assertEquals(StampFactory.forInteger(JavaKind.Int, Short.MIN_VALUE, Short.MAX_VALUE), narrowingKindConversion(StampFactory.forInteger(JavaKind.Int, -40000, -10000), JavaKind.Short));
185         // int cases
186         assertEquals(StampFactory.forInteger(JavaKind.Int, 0, 10), narrowingKindConversion(StampFactory.forInteger(JavaKind.Long, 0, 10), JavaKind.Int));
187         assertEquals(StampFactory.forInteger(JavaKind.Int, 10, 20), narrowingKindConversion(StampFactory.forInteger(JavaKind.Long, 10, 20), JavaKind.Int));
188         assertEquals(StampFactory.forInteger(JavaKind.Int, Integer.MIN_VALUE, Integer.MAX_VALUE),
189                         narrowingKindConversion(StampFactory.forInteger(JavaKind.Long, 20000000000L, 40000000000L), JavaKind.Int));
190         assertEquals(StampFactory.forInteger(JavaKind.Int, Integer.MIN_VALUE, Integer.MAX_VALUE),
191                         narrowingKindConversion(StampFactory.forInteger(JavaKind.Long, -10000000000L, 40000000000L), JavaKind.Int));
192         assertEquals(StampFactory.forInteger(JavaKind.Int, Integer.MIN_VALUE, Integer.MAX_VALUE),
193                         narrowingKindConversion(StampFactory.forInteger(JavaKind.Long, -40000000000L, -10000000000L), JavaKind.Int));
194     }
195 
196     @Test
testMaskBasedNarrowing()197     public void testMaskBasedNarrowing() {
198         IntegerStamp stamp = IntegerStamp.create(32, 1, 2, 0x2, 0x3);
199         IntegerStamp resultStamp = IntegerStamp.create(32, 2, 2);
200         assertEquals(resultStamp, stamp);
201     }
202 
203     @Test
testJoinWeirdMasks()204     public void testJoinWeirdMasks() {
205         IntegerStamp minusOneOrThree = IntegerStamp.create(32, -1, 3, 0x3, 0xFFFFFFFFL);
206         IntegerStamp twoOrThree = IntegerStamp.create(32, 2, 3, 0x2, 0x3);
207         IntegerStamp three = IntegerStamp.create(32, 3, 3, 0x3, 0x3);
208         assertEquals(three, minusOneOrThree.join(twoOrThree));
209 
210         IntegerStamp minusOneOrThreeOrOne = IntegerStamp.create(32, -1, 3, 0x1, 0xFFFFFFFFL);
211         assertEquals(three, minusOneOrThreeOrOne.join(twoOrThree));
212 
213         IntegerStamp a = IntegerStamp.create(32, 0b101, 0b110, 0b100, 0b111);
214         IntegerStamp b = IntegerStamp.create(32, 0b011, 0b110, 0b010, 0b111);
215 
216         // This exercises a special case:
217         // The new lowest bound is max(0b101, 0b011) = 0b101
218         // The new down mask is (0b100 | 0b010) = 0b110
219         // Now based on lowest bound and down mask, we know that the new lowest bound is 0b110
220         // Just making an or with the new down mask would give however (0b110 | 0b101) = 0b111 and
221         // would therefore be wrong.
222         // New upper bound is 0b110.
223 
224         IntegerStamp result = IntegerStamp.create(32, 0b110, 0b110, 0b110, 0b110);
225         assertEquals(result, a.join(b));
226     }
227 
228     @Test
testXor()229     public void testXor() {
230         assertEquals(IntegerStamp.create(32, 0, 0xff, 0, 0xff), IntegerStamp.OPS.getXor().foldStamp(IntegerStamp.create(32, 0, 0, 0, 0), IntegerStamp.create(32, 0, 0xff, 0, 0xff)));
231         assertEquals(IntegerStamp.create(32, 0x10, 0x1f, 0x10, 0x1f), IntegerStamp.OPS.getXor().foldStamp(IntegerStamp.create(32, 0, 0, 0, 0), IntegerStamp.create(32, 0x10, 0x1f, 0x10, 0x1f)));
232         assertEquals(IntegerStamp.create(32, 0x0, 0xf, 0x0, 0xf),
233                         IntegerStamp.OPS.getXor().foldStamp(IntegerStamp.create(32, 0x10, 0x10, 0x10, 0x10), IntegerStamp.create(32, 0x10, 0x1f, 0x10, 0x1f)));
234         assertEquals(IntegerStamp.create(32, 0x10, 0x1f, 0x10, 0x1f),
235                         IntegerStamp.OPS.getXor().foldStamp(IntegerStamp.create(32, 0x10, 0x10, 0x10, 0x10), IntegerStamp.create(32, 0x0, 0xf, 0x0, 0xf)));
236     }
237 
238     @Test
testNot()239     public void testNot() {
240         assertEquals(IntegerStamp.create(32, -11, -1, 0xffff_fff0L, 0xffff_ffffL), IntegerStamp.OPS.getNot().foldStamp(IntegerStamp.create(32, 0, 10, 0, 0xf)));
241     }
242 
243     @Test
testAddIntSimple()244     public void testAddIntSimple() {
245         assertEquals(StampFactory.forInteger(JavaKind.Int, 0, 30, 0, 31), addIntStamp(StampFactory.forInteger(JavaKind.Int, 0, 10), StampFactory.forInteger(JavaKind.Int, 0, 20)));
246     }
247 
248     @Test
testAddNegativeOverFlowInt1()249     public void testAddNegativeOverFlowInt1() {
250         assertEquals(StampFactory.forInteger(JavaKind.Int, Integer.MIN_VALUE, Integer.MAX_VALUE, 0, 0xffff_ffffL),
251                         addIntStamp(StampFactory.forInteger(JavaKind.Int, Integer.MIN_VALUE, 0), StampFactory.forInteger(JavaKind.Int, -1, 0)));
252     }
253 
254     @Test
testAddNegativeOverFlowInt2()255     public void testAddNegativeOverFlowInt2() {
256         assertEquals(StampFactory.forInteger(JavaKind.Int, Integer.MAX_VALUE - 2, Integer.MAX_VALUE, 0x7fff_fffcL, 0x7fff_ffffL),
257                         addIntStamp(StampFactory.forInteger(JavaKind.Int, Integer.MIN_VALUE, Integer.MIN_VALUE + 1), StampFactory.forInteger(JavaKind.Int, -3, -2)));
258     }
259 
260     @Test
testAddPositiveOverFlowInt1()261     public void testAddPositiveOverFlowInt1() {
262         assertEquals(StampFactory.forKind(JavaKind.Int), addIntStamp(StampFactory.forInteger(JavaKind.Int, 0, 1), StampFactory.forInteger(JavaKind.Int, 0, Integer.MAX_VALUE)));
263     }
264 
265     @Test
testAddPositiveOverFlowInt2()266     public void testAddPositiveOverFlowInt2() {
267         assertEquals(StampFactory.forInteger(JavaKind.Int, Integer.MIN_VALUE, Integer.MIN_VALUE + 2),
268                         addIntStamp(StampFactory.forInteger(JavaKind.Int, Integer.MAX_VALUE - 1, Integer.MAX_VALUE), StampFactory.forInteger(JavaKind.Int, 2, 3)));
269     }
270 
271     @Test
testAddOverFlowsInt()272     public void testAddOverFlowsInt() {
273         assertEquals(StampFactory.forKind(JavaKind.Int), addIntStamp(StampFactory.forInteger(JavaKind.Int, -1, 1), StampFactory.forInteger(JavaKind.Int, Integer.MIN_VALUE, Integer.MAX_VALUE)));
274     }
275 
276     @Test
testAddLongSimple()277     public void testAddLongSimple() {
278         assertEquals(StampFactory.forInteger(JavaKind.Long, 0, 30, 0, 31), addIntStamp(StampFactory.forInteger(JavaKind.Long, 0, 10), StampFactory.forInteger(JavaKind.Long, 0, 20)));
279     }
280 
281     @Test
testAddNegativOverFlowLong1()282     public void testAddNegativOverFlowLong1() {
283         assertEquals(StampFactory.forInteger(JavaKind.Long, Long.MIN_VALUE, Long.MAX_VALUE, 0, 0xffff_ffff_ffff_ffffL),
284                         addIntStamp(StampFactory.forInteger(JavaKind.Long, Long.MIN_VALUE, Long.MIN_VALUE + 1), StampFactory.forInteger(JavaKind.Long, Integer.MIN_VALUE, Integer.MAX_VALUE)));
285     }
286 
287     @Test
testAddNegativeOverFlowLong2()288     public void testAddNegativeOverFlowLong2() {
289         assertEquals(StampFactory.forInteger(JavaKind.Long, Long.MAX_VALUE - 2, Long.MAX_VALUE),
290                         addIntStamp(StampFactory.forInteger(JavaKind.Long, Long.MIN_VALUE, Long.MIN_VALUE + 1), StampFactory.forInteger(JavaKind.Long, -3, -2)));
291     }
292 
293     @Test
testAddPositiveOverFlowLong1()294     public void testAddPositiveOverFlowLong1() {
295         assertEquals(StampFactory.forKind(JavaKind.Long), addIntStamp(StampFactory.forInteger(JavaKind.Long, 0, 1), StampFactory.forInteger(JavaKind.Long, 0, Long.MAX_VALUE)));
296     }
297 
298     @Test
testAddPositiveOverFlowLong2()299     public void testAddPositiveOverFlowLong2() {
300         assertEquals(StampFactory.forInteger(JavaKind.Long, Long.MIN_VALUE, Long.MIN_VALUE + 2),
301                         addIntStamp(StampFactory.forInteger(JavaKind.Long, Long.MAX_VALUE - 1, Long.MAX_VALUE), StampFactory.forInteger(JavaKind.Long, 2, 3)));
302     }
303 
304     @Test
testAddOverFlowsLong()305     public void testAddOverFlowsLong() {
306         assertEquals(StampFactory.forKind(JavaKind.Long), addIntStamp(StampFactory.forInteger(JavaKind.Long, -1, 1), StampFactory.forInteger(JavaKind.Long, Long.MIN_VALUE, Long.MAX_VALUE)));
307     }
308 
309     @Test
testAdd1()310     public void testAdd1() {
311         assertEquals(StampFactory.forInteger(JavaKind.Int, Integer.MIN_VALUE + 1, 31 + (Integer.MIN_VALUE + 1)),
312                         addIntStamp(StampFactory.forInteger(JavaKind.Int, 0, 31), StampFactory.forInteger(JavaKind.Int, Integer.MIN_VALUE + 1, Integer.MIN_VALUE + 1)));
313     }
314 
315     @Test
testAdd2()316     public void testAdd2() {
317         assertEquals(StampFactory.forInteger(JavaKind.Int, 0x8000_007e, 0x8000_007f, 0x8000_007eL, 0x8000_007fL),
318                         addIntStamp(StampFactory.forInteger(JavaKind.Int, 0x7fff_fffe, 0x7fff_ffff, 0x7fff_fffeL, 0x7ffff_fffL), StampFactory.forInteger(JavaKind.Int, 128, 128)));
319     }
320 
321     @Test
testAdd3()322     public void testAdd3() {
323         assertEquals(StampFactory.forInteger(JavaKind.Long, Long.MIN_VALUE, Long.MAX_VALUE - 1, 0, 0xffff_ffff_ffff_fffeL),
324                         addIntStamp(StampFactory.forInteger(JavaKind.Long, Long.MIN_VALUE, Long.MAX_VALUE - 1, 0, 0xffff_ffff_ffff_fffeL),
325                                         StampFactory.forInteger(JavaKind.Long, Long.MIN_VALUE, Long.MAX_VALUE - 1, 0, 0xffff_ffff_ffff_fffeL)));
326 
327     }
328 
329     @Test
testAnd()330     public void testAnd() {
331         assertEquals(IntegerStamp.create(32, Integer.MIN_VALUE, 0x40000000L, 0, 0xc0000000L),
332                         IntegerStamp.OPS.getAnd().foldStamp(StampFactory.forKind(JavaKind.Int), StampFactory.forConstant(JavaConstant.forInt(0xc0000000))));
333     }
334 
testSignExtendShort(long lower, long upper)335     private static void testSignExtendShort(long lower, long upper) {
336         Stamp shortStamp = StampFactory.forInteger(16, lower, upper);
337         Stamp intStamp = IntegerStamp.OPS.getSignExtend().foldStamp(16, 32, shortStamp);
338         assertEquals(StampFactory.forInteger(32, lower, upper), intStamp);
339     }
340 
341     @Test
testSignExtend()342     public void testSignExtend() {
343         testSignExtendShort(5, 7);
344         testSignExtendShort(0, 42);
345         testSignExtendShort(-42, -1);
346         testSignExtendShort(-42, 0);
347         testSignExtendShort(-1, 1);
348         testSignExtendShort(Short.MIN_VALUE, Short.MAX_VALUE);
349     }
350 
testZeroExtendShort(long lower, long upper, long newLower, long newUpper)351     private static void testZeroExtendShort(long lower, long upper, long newLower, long newUpper) {
352         Stamp shortStamp = StampFactory.forInteger(16, lower, upper);
353         Stamp intStamp = IntegerStamp.OPS.getZeroExtend().foldStamp(16, 32, shortStamp);
354         assertEquals(StampFactory.forInteger(32, newLower, newUpper), intStamp);
355     }
356 
357     @Test
testZeroExtend()358     public void testZeroExtend() {
359         testZeroExtendShort(5, 7, 5, 7);
360         testZeroExtendShort(0, 42, 0, 42);
361         testZeroExtendShort(-42, -1, 0xFFFF - 41, 0xFFFF);
362         testZeroExtendShort(-42, 0, 0, 0xFFFF);
363         testZeroExtendShort(-1, 1, 0, 0xFFFF);
364         testZeroExtendShort(Short.MIN_VALUE, Short.MAX_VALUE, 0, 0xFFFF);
365     }
366 
367     @Test
testIllegalJoin()368     public void testIllegalJoin() {
369         assertFalse(IntegerStamp.create(32, 0, 0xff00, 0, 0xff00).join(IntegerStamp.create(32, 1, 0xff, 0x00, 0xff)).hasValues());
370         assertFalse(IntegerStamp.create(32, 0x100, 0xff00, 0, 0xff00).join(IntegerStamp.create(32, 0, 0xff, 0x00, 0xff)).hasValues());
371     }
372 
373     @Test
testShiftLeft()374     public void testShiftLeft() {
375         ShiftOp<?> shl = IntegerStamp.OPS.getShl();
376         assertEquals(IntegerStamp.create(32, 0, 0x1ff, 0, 0x1ff), shl.foldStamp(IntegerStamp.create(32, 0, 0xff, 0, 0xff), IntegerStamp.create(32, 0, 1, 0, 1)));
377         assertEquals(IntegerStamp.create(32, 0, 0x1fe0, 0, 0x1fe0), shl.foldStamp(IntegerStamp.create(32, 0, 0xff, 0, 0xff), IntegerStamp.create(32, 5, 5, 5, 5)));
378         assertEquals(IntegerStamp.create(32, 0x1e0, 0x1fe0, 0, 0x1fe0), shl.foldStamp(IntegerStamp.create(32, 0xf, 0xff, 0, 0xff), IntegerStamp.create(32, 5, 5, 5, 5)));
379         assertEquals(IntegerStamp.create(32, -4096, -4096, -4096, -4096), shl.foldStamp(IntegerStamp.create(32, -16, -16, -16, -16), IntegerStamp.create(32, 8, 8, 8, 8)));
380         assertEquals(StampFactory.empty(JavaKind.Int), shl.foldStamp(StampFactory.empty(JavaKind.Int), IntegerStamp.create(32, 5, 5, 5, 5)));
381         assertEquals(StampFactory.empty(JavaKind.Int), shl.foldStamp(IntegerStamp.create(32, 0xf, 0xff, 0, 0xff), (IntegerStamp) StampFactory.empty(JavaKind.Int)));
382 
383         assertEquals(IntegerStamp.create(64, 0, 0x1ff, 0, 0x1ff), shl.foldStamp(IntegerStamp.create(64, 0, 0xff, 0, 0xff), IntegerStamp.create(32, 0, 1, 0, 1)));
384         assertEquals(IntegerStamp.create(64, 0, 0x1fe0, 0, 0x1fe0), shl.foldStamp(IntegerStamp.create(64, 0, 0xff, 0, 0xff), IntegerStamp.create(32, 5, 5, 5, 5)));
385         assertEquals(IntegerStamp.create(64, 0x1e0, 0x1fe0, 0, 0x1fe0), shl.foldStamp(IntegerStamp.create(64, 0xf, 0xff, 0, 0xff), IntegerStamp.create(32, 5, 5, 5, 5)));
386         assertEquals(IntegerStamp.create(64, -4096, -4096, -4096, -4096), shl.foldStamp(IntegerStamp.create(64, -16, -16, -16, -16), IntegerStamp.create(32, 8, 8, 8, 8)));
387         assertEquals(StampFactory.empty(JavaKind.Long), shl.foldStamp(StampFactory.empty(JavaKind.Long), IntegerStamp.create(32, 5, 5, 5, 5)));
388         assertEquals(StampFactory.empty(JavaKind.Long), shl.foldStamp(IntegerStamp.create(64, 0xf, 0xff, 0, 0xff), (IntegerStamp) StampFactory.empty(JavaKind.Int)));
389     }
390 
391     @Test
testUnsignedShiftRight()392     public void testUnsignedShiftRight() {
393         ShiftOp<?> ushr = IntegerStamp.OPS.getUShr();
394         assertEquals(IntegerStamp.create(32, 0, 0xff, 0, 0xff), ushr.foldStamp(IntegerStamp.create(32, 0, 0xff, 0, 0xff), IntegerStamp.create(32, 0, 1, 0, 1)));
395         assertEquals(IntegerStamp.create(32, 0, 0x07, 0, 0x07), ushr.foldStamp(IntegerStamp.create(32, 0, 0xff, 0, 0xff), IntegerStamp.create(32, 5, 5, 5, 5)));
396         assertEquals(IntegerStamp.create(32, 0x0, 0x07, 0, 0x07), ushr.foldStamp(IntegerStamp.create(32, 0xf, 0xff, 0, 0xff), IntegerStamp.create(32, 5, 5, 5, 5)));
397         assertEquals(IntegerStamp.create(32, 0xffffff, 0xffffff, 0xffffff, 0xffffff), ushr.foldStamp(IntegerStamp.create(32, -16, -16, -16, -16), IntegerStamp.create(32, 8, 8, 8, 8)));
398         assertEquals(StampFactory.empty(JavaKind.Int), ushr.foldStamp(StampFactory.empty(JavaKind.Int), IntegerStamp.create(32, 5, 5, 5, 5)));
399         assertEquals(StampFactory.empty(JavaKind.Int), ushr.foldStamp(IntegerStamp.create(32, 0xf, 0xff, 0, 0xff), (IntegerStamp) StampFactory.empty(JavaKind.Int)));
400 
401         assertEquals(IntegerStamp.create(64, 0, 0xff, 0, 0xff), ushr.foldStamp(IntegerStamp.create(64, 0, 0xff, 0, 0xff), IntegerStamp.create(32, 0, 1, 0, 1)));
402         assertEquals(IntegerStamp.create(64, 0, 0x07, 0, 0x07), ushr.foldStamp(IntegerStamp.create(64, 0, 0xff, 0, 0xff), IntegerStamp.create(32, 5, 5, 5, 5)));
403         assertEquals(IntegerStamp.create(64, 0x0, 0x07, 0, 0x07), ushr.foldStamp(IntegerStamp.create(64, 0xf, 0xff, 0, 0xff), IntegerStamp.create(32, 5, 5, 5, 5)));
404         assertEquals(IntegerStamp.create(64, 0xffffffffffffffL, 0xffffffffffffffL, 0xffffffffffffffL, 0xffffffffffffffL),
405                         ushr.foldStamp(IntegerStamp.create(64, -16, -16, -16, -16), IntegerStamp.create(32, 8, 8, 8, 8)));
406         assertEquals(StampFactory.empty(JavaKind.Long), ushr.foldStamp(StampFactory.empty(JavaKind.Long), IntegerStamp.create(32, 5, 5, 5, 5)));
407         assertEquals(StampFactory.empty(JavaKind.Long), ushr.foldStamp(IntegerStamp.create(64, 0xf, 0xff, 0, 0xff), (IntegerStamp) StampFactory.empty(JavaKind.Int)));
408     }
409 
410     @Test
testShiftRight()411     public void testShiftRight() {
412         ShiftOp<?> shr = IntegerStamp.OPS.getShr();
413         assertEquals(IntegerStamp.create(32, 0, 0xff, 0, 0xff), shr.foldStamp(IntegerStamp.create(32, 0, 0xff, 0, 0xff), IntegerStamp.create(32, 0, 1, 0, 1)));
414         assertEquals(IntegerStamp.create(32, 0, 0x07, 0, 0x07), shr.foldStamp(IntegerStamp.create(32, 0, 0xff, 0, 0xff), IntegerStamp.create(32, 5, 5, 5, 5)));
415         assertEquals(IntegerStamp.create(32, 0x0, 0x07, 0, 0x07), shr.foldStamp(IntegerStamp.create(32, 0xf, 0xff, 0, 0xff), IntegerStamp.create(32, 5, 5, 5, 5)));
416         assertEquals(IntegerStamp.create(32, -1, -1, -1, -1), shr.foldStamp(IntegerStamp.create(32, -16, -16, -16, -16), IntegerStamp.create(32, 8, 8, 8, 8)));
417         assertEquals(StampFactory.empty(JavaKind.Int), shr.foldStamp(StampFactory.empty(JavaKind.Int), IntegerStamp.create(32, 5, 5, 5, 5)));
418         assertEquals(StampFactory.empty(JavaKind.Int), shr.foldStamp(IntegerStamp.create(32, 0xf, 0xff, 0, 0xff), (IntegerStamp) StampFactory.empty(JavaKind.Int)));
419 
420         assertEquals(IntegerStamp.create(64, 0, 0xff, 0, 0xff), shr.foldStamp(IntegerStamp.create(64, 0, 0xff, 0, 0xff), IntegerStamp.create(32, 0, 1, 0, 1)));
421         assertEquals(IntegerStamp.create(64, 0, 0x07, 0, 0x07), shr.foldStamp(IntegerStamp.create(64, 0, 0xff, 0, 0xff), IntegerStamp.create(32, 5, 5, 5, 5)));
422         assertEquals(IntegerStamp.create(64, 0x0, 0x07, 0, 0x07), shr.foldStamp(IntegerStamp.create(64, 0xf, 0xff, 0, 0xff), IntegerStamp.create(32, 5, 5, 5, 5)));
423         assertEquals(IntegerStamp.create(64, -1, -1, -1, -1), shr.foldStamp(IntegerStamp.create(64, -16, -16, -16, -16), IntegerStamp.create(32, 8, 8, 8, 8)));
424         assertEquals(StampFactory.empty(JavaKind.Long), shr.foldStamp(StampFactory.empty(JavaKind.Long), IntegerStamp.create(32, 5, 5, 5, 5)));
425         assertEquals(StampFactory.empty(JavaKind.Long), shr.foldStamp(IntegerStamp.create(64, 0xf, 0xff, 0, 0xff), (IntegerStamp) StampFactory.empty(JavaKind.Int)));
426     }
427 
428     @Test
testMulHigh()429     public void testMulHigh() {
430         testSomeMulHigh(IntegerStamp.OPS.getMulHigh());
431     }
432 
433     @Test
testUMulHigh()434     public void testUMulHigh() {
435         testSomeMulHigh(IntegerStamp.OPS.getUMulHigh());
436     }
437 
testSomeMulHigh(BinaryOp<?> someMulHigh)438     private static void testSomeMulHigh(BinaryOp<?> someMulHigh) {
439         // 32 bits
440         testMulHigh(someMulHigh, 0, 0, 32);
441 
442         testMulHigh(someMulHigh, 1, 1, 32);
443         testMulHigh(someMulHigh, 1, 5, 32);
444         testMulHigh(someMulHigh, 256, 256, 32);
445         testMulHigh(someMulHigh, 0xFFFFFFF, 0xFFFFFFA, 32);
446         testMulHigh(someMulHigh, Integer.MAX_VALUE, 2, 32);
447 
448         testMulHigh(someMulHigh, -1, -1, 32);
449         testMulHigh(someMulHigh, -1, -5, 32);
450         testMulHigh(someMulHigh, -256, -256, 32);
451         testMulHigh(someMulHigh, -0xFFFFFFF, -0xFFFFFFA, 32);
452         testMulHigh(someMulHigh, Integer.MIN_VALUE, -2, 32);
453 
454         testMulHigh(someMulHigh, -1, 1, 32);
455         testMulHigh(someMulHigh, -1, 5, 32);
456         testMulHigh(someMulHigh, -256, 256, 32);
457         testMulHigh(someMulHigh, -0xFFFFFFF, 0xFFFFFFA, 32);
458         testMulHigh(someMulHigh, Integer.MIN_VALUE, 2, 32);
459 
460         testMulHigh(someMulHigh, Integer.MIN_VALUE, Integer.MIN_VALUE, 32);
461         testMulHigh(someMulHigh, Integer.MAX_VALUE, Integer.MAX_VALUE, 32);
462 
463         assertEquals(StampFactory.forKind(JavaKind.Int).empty(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Int).empty(), StampFactory.forKind(JavaKind.Int).empty()));
464         assertEquals(StampFactory.forKind(JavaKind.Int).empty(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Int).empty(), StampFactory.forKind(JavaKind.Int).unrestricted()));
465         assertEquals(StampFactory.forKind(JavaKind.Int).empty(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Int).empty(), IntegerStamp.create(32, 0, 0)));
466         assertEquals(StampFactory.forKind(JavaKind.Int).empty(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Int).empty(), IntegerStamp.create(32, 1, 1)));
467         assertEquals(StampFactory.forKind(JavaKind.Int).empty(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Int).empty(), IntegerStamp.create(32, -1, -1)));
468 
469         assertEquals(StampFactory.forKind(JavaKind.Int).unrestricted(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Int).unrestricted(), StampFactory.forKind(JavaKind.Int).unrestricted()));
470         assertEquals(StampFactory.forKind(JavaKind.Int).unrestricted(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Int).unrestricted(), IntegerStamp.create(32, 0, 0)));
471         assertEquals(StampFactory.forKind(JavaKind.Int).unrestricted(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Int).unrestricted(), IntegerStamp.create(32, 1, 1)));
472         assertEquals(StampFactory.forKind(JavaKind.Int).unrestricted(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Int).unrestricted(), IntegerStamp.create(32, -1, -1)));
473 
474         // 64 bits
475         testMulHigh(someMulHigh, 0, 0, 64);
476 
477         testMulHigh(someMulHigh, 1, 1, 64);
478         testMulHigh(someMulHigh, 1, 5, 64);
479         testMulHigh(someMulHigh, 256, 256, 64);
480         testMulHigh(someMulHigh, 0xFFFFFFF, 0xFFFFFFA, 64);
481         testMulHigh(someMulHigh, 0xFFFFFFFFFFFFFFL, 0xFFFFFFFFFFFFFAL, 64);
482         testMulHigh(someMulHigh, Integer.MAX_VALUE, 2, 64);
483         testMulHigh(someMulHigh, Long.MAX_VALUE, 2, 64);
484 
485         testMulHigh(someMulHigh, -1, -1, 64);
486         testMulHigh(someMulHigh, -1, -5, 64);
487         testMulHigh(someMulHigh, -256, -256, 64);
488         testMulHigh(someMulHigh, -0xFFFFFFF, -0xFFFFFFA, 64);
489         testMulHigh(someMulHigh, -0xFFFFFFFFFFFFFFL, -0xFFFFFFFFFFFFFAL, 64);
490         testMulHigh(someMulHigh, Integer.MIN_VALUE, -2, 64);
491         testMulHigh(someMulHigh, Long.MIN_VALUE, -2, 64);
492 
493         testMulHigh(someMulHigh, -1, 1, 64);
494         testMulHigh(someMulHigh, -1, 5, 64);
495         testMulHigh(someMulHigh, -256, 256, 64);
496         testMulHigh(someMulHigh, -0xFFFFFFF, 0xFFFFFFA, 64);
497         testMulHigh(someMulHigh, -0xFFFFFFFFFFFFFFL, 0xFFFFFFFFFFFFFAL, 64);
498         testMulHigh(someMulHigh, Integer.MIN_VALUE, 2, 64);
499         testMulHigh(someMulHigh, Long.MIN_VALUE, 2, 64);
500 
501         testMulHigh(someMulHigh, Integer.MIN_VALUE, Integer.MIN_VALUE, 64);
502         testMulHigh(someMulHigh, Long.MIN_VALUE, Long.MIN_VALUE, 64);
503         testMulHigh(someMulHigh, Integer.MAX_VALUE, Integer.MAX_VALUE, 64);
504         testMulHigh(someMulHigh, Long.MAX_VALUE, Long.MAX_VALUE, 64);
505 
506         assertEquals(StampFactory.forKind(JavaKind.Long).empty(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Long).empty(), StampFactory.forKind(JavaKind.Long).empty()));
507         assertEquals(StampFactory.forKind(JavaKind.Long).empty(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Long).empty(), StampFactory.forKind(JavaKind.Long).unrestricted()));
508         assertEquals(StampFactory.forKind(JavaKind.Long).empty(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Long).empty(), IntegerStamp.create(64, 0, 0)));
509         assertEquals(StampFactory.forKind(JavaKind.Long).empty(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Long).empty(), IntegerStamp.create(64, 1, 1)));
510         assertEquals(StampFactory.forKind(JavaKind.Long).empty(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Long).empty(), IntegerStamp.create(64, -1, -1)));
511 
512         assertEquals(StampFactory.forKind(JavaKind.Long).unrestricted(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Long).unrestricted(), StampFactory.forKind(JavaKind.Long).unrestricted()));
513         assertEquals(StampFactory.forKind(JavaKind.Long).unrestricted(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Long).unrestricted(), IntegerStamp.create(64, 0, 0)));
514         assertEquals(StampFactory.forKind(JavaKind.Long).unrestricted(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Long).unrestricted(), IntegerStamp.create(64, 1, 1)));
515         assertEquals(StampFactory.forKind(JavaKind.Long).unrestricted(), someMulHigh.foldStamp(StampFactory.forKind(JavaKind.Long).unrestricted(), IntegerStamp.create(64, -1, -1)));
516     }
517 
testMulHigh(BinaryOp<?> someMulHigh, long a, long b, int bits)518     private static void testMulHigh(BinaryOp<?> someMulHigh, long a, long b, int bits) {
519         long expectedResult = getExpectedValue(someMulHigh, a, b, bits);
520         assertEquals(IntegerStamp.create(bits, expectedResult, expectedResult), someMulHigh.foldStamp(IntegerStamp.create(bits, a, a), IntegerStamp.create(bits, b, b)));
521     }
522 
getExpectedValue(BinaryOp<?> someMulHigh, long a, long b, int bits)523     private static long getExpectedValue(BinaryOp<?> someMulHigh, long a, long b, int bits) {
524         if (someMulHigh == IntegerStamp.OPS.getMulHigh()) {
525             return mulHigh(a, b, bits);
526         } else {
527             assertEquals(IntegerStamp.OPS.getUMulHigh(), someMulHigh);
528             return umulHigh(a, b, bits);
529         }
530     }
531 
mulHigh(long a, long b, int bits)532     private static long mulHigh(long a, long b, int bits) {
533         BigInteger valA = BigInteger.valueOf(a);
534         BigInteger valB = BigInteger.valueOf(b);
535         BigInteger result = valA.multiply(valB).shiftRight(bits);
536         if (bits == 32) {
537             return result.intValue();
538         } else {
539             assertEquals(64, bits);
540             return result.longValue();
541         }
542     }
543 
umulHigh(long a, long b, int bits)544     private static long umulHigh(long a, long b, int bits) {
545         Assert.assertTrue(bits == 32 || bits == 64);
546         BigInteger valA = BigInteger.valueOf(a);
547         if (valA.compareTo(BigInteger.valueOf(0)) < 0) {
548             valA = valA.add(BigInteger.ONE.shiftLeft(bits));
549         }
550         BigInteger valB = BigInteger.valueOf(b);
551         if (valB.compareTo(BigInteger.valueOf(0)) < 0) {
552             valB = valB.add(BigInteger.ONE.shiftLeft(bits));
553         }
554 
555         BigInteger result = valA.multiply(valB).shiftRight(bits);
556         if (bits == 32) {
557             return result.intValue();
558         } else {
559             return result.longValue();
560         }
561     }
562 
563     @Test
testDiv()564     public void testDiv() {
565         testDiv(32, Integer.MIN_VALUE, Integer.MAX_VALUE);
566         testDiv(64, Long.MIN_VALUE, Long.MAX_VALUE);
567     }
568 
testDiv(int bits, long min, long max)569     private static void testDiv(int bits, long min, long max) {
570         BinaryOp<?> div = IntegerStamp.OPS.getDiv();
571         assertEquals(IntegerStamp.create(bits, -50, 50), div.foldStamp(IntegerStamp.create(bits, -100, 100), IntegerStamp.create(bits, 2, 5)));
572         assertEquals(IntegerStamp.create(bits, 20, 500), div.foldStamp(IntegerStamp.create(bits, 100, 1000), IntegerStamp.create(bits, 2, 5)));
573         assertEquals(IntegerStamp.create(bits, -500, -20), div.foldStamp(IntegerStamp.create(bits, -1000, -100), IntegerStamp.create(bits, 2, 5)));
574         assertEquals(IntegerStamp.create(bits, min, max), div.foldStamp(IntegerStamp.create(bits, min, max), IntegerStamp.create(bits, 1, max)));
575         assertEquals(IntegerStamp.create(bits, -100, 100), div.foldStamp(IntegerStamp.create(bits, -100, 100), IntegerStamp.create(bits, 1, max)));
576         assertEquals(IntegerStamp.create(bits, 0, 1000), div.foldStamp(IntegerStamp.create(bits, 100, 1000), IntegerStamp.create(bits, 1, max)));
577         assertEquals(IntegerStamp.create(bits, -1000, 0), div.foldStamp(IntegerStamp.create(bits, -1000, -100), IntegerStamp.create(bits, 1, max)));
578     }
579 
580     @Test
testEmpty()581     public void testEmpty() {
582         IntegerStamp intStamp = StampFactory.forInteger(32);
583         IntegerStamp longStamp = StampFactory.forInteger(64);
584         Stamp intEmpty = StampFactory.empty(JavaKind.Int);
585         Stamp longEmpty = StampFactory.empty(JavaKind.Long);
586         assertEquals(intStamp.join(intEmpty), intEmpty);
587         assertEquals(intStamp.meet(intEmpty), intStamp);
588         assertEquals(longStamp.join(longEmpty), longEmpty);
589         assertEquals(longStamp.meet(longEmpty), longStamp);
590     }
591 
592     @Test
testUnaryOpFoldEmpty()593     public void testUnaryOpFoldEmpty() {
594         // boolean?, byte, short, int, long
595         Stream.of(1, 8, 16, 32, 64).map(bits -> StampFactory.forInteger(bits).empty()).forEach(empty -> {
596             for (ArithmeticOpTable.UnaryOp<?> op : IntegerStamp.OPS.getUnaryOps()) {
597                 if (op != null) {
598                     Assert.assertTrue(op.foldStamp(empty).isEmpty());
599                 }
600             }
601         });
602     }
603 
604     @Test
testIntegerConvertOpWithEmpty()605     public void testIntegerConvertOpWithEmpty() {
606         int[] bits = new int[]{1, 8, 16, 32, 64};
607 
608         List<IntegerConvertOp<?>> extendOps = Arrays.asList(
609                         IntegerStamp.OPS.getSignExtend(),
610                         IntegerStamp.OPS.getZeroExtend());
611 
612         for (int inputBits : bits) {
613             IntegerStamp emptyIn = StampFactory.forInteger(inputBits).empty();
614             for (int outputBits : bits) {
615                 IntegerStamp emptyOut = StampFactory.forInteger(outputBits).empty();
616                 if (inputBits <= outputBits) {
617                     for (IntegerConvertOp<?> stamp : extendOps) {
618                         IntegerStamp folded = (IntegerStamp) stamp.foldStamp(inputBits, outputBits, emptyIn);
619                         Assert.assertTrue(folded.isEmpty());
620                         Assert.assertEquals(outputBits, folded.getBits());
621 
622                         // Widening is lossless, inversion is well-defined.
623                         IntegerStamp inverted = (IntegerStamp) stamp.invertStamp(inputBits, outputBits, emptyOut);
624                         Assert.assertTrue(inverted.isEmpty());
625                         Assert.assertEquals(inputBits, inverted.getBits());
626                     }
627                 }
628 
629                 if (inputBits >= outputBits) {
630                     IntegerConvertOp<?> narrow = IntegerStamp.OPS.getNarrow();
631                     IntegerStamp folded = (IntegerStamp) narrow.foldStamp(inputBits, outputBits, emptyIn);
632                     Assert.assertTrue(folded.isEmpty());
633                     Assert.assertEquals(outputBits, folded.getBits());
634 
635                     // Narrowing is lossy, inversion can potentially yield empty or unknown (null).
636                     IntegerStamp inverted = (IntegerStamp) narrow.invertStamp(inputBits, outputBits, emptyOut);
637                     Assert.assertTrue(inverted == null || inverted.isEmpty());
638                     if (inverted != null) {
639                         Assert.assertEquals(inputBits, inverted.getBits());
640                     }
641                 }
642             }
643         }
644     }
645 }
646