1 /* 2 * Copyright (c) 2016, 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.core.test; 24 25 import java.util.ArrayList; 26 import java.util.Collection; 27 28 import org.junit.Assert; 29 import org.junit.Test; 30 import org.junit.runner.RunWith; 31 import org.junit.runners.Parameterized; 32 import org.junit.runners.Parameterized.Parameter; 33 import org.junit.runners.Parameterized.Parameters; 34 import org.junit.runners.Suite; 35 import org.junit.runners.Suite.SuiteClasses; 36 37 import org.graalvm.compiler.core.common.type.IntegerStamp; 38 import org.graalvm.compiler.core.common.type.StampFactory; 39 40 @RunWith(Suite.class) 41 @SuiteClasses({IntegerStampMulFoldTest.OverflowTest.class, IntegerStampMulFoldTest.FoldTest.class}) 42 public class IntegerStampMulFoldTest extends GraalCompilerTest { 43 44 public static class OverflowTest { 45 @Test 46 public void testOverflowCheck() { 47 // a.u * b.u overflows 48 long a = Integer.MIN_VALUE; 49 long b = -1; 50 Assert.assertTrue(IntegerStamp.multiplicationOverflows(a, b, 32)); 51 } 52 53 @Test 54 public void testOverflowCheck01() { 55 // a.u * b.u overflows 56 long a = Integer.MAX_VALUE; 57 long b = Integer.MAX_VALUE; 58 Assert.assertTrue(IntegerStamp.multiplicationOverflows(a, b, 32)); 59 } 60 61 @Test 62 public void testOverflowCheck02() { 63 // a.u * b.u overflows 64 long a = Integer.MIN_VALUE; 65 long b = Integer.MIN_VALUE; 66 Assert.assertTrue(IntegerStamp.multiplicationOverflows(a, b, 32)); 67 } 68 69 @Test 70 public void testOverflowCheck03() { 71 // a.u * b.u overflows 72 long a = Integer.MIN_VALUE; 73 long b = 1; 74 Assert.assertFalse(IntegerStamp.multiplicationOverflows(a, b, 32)); 75 } 76 77 @Test 78 public void testOverflowCheck04() { 79 // a.u * b.u overflows 80 long a = Integer.MAX_VALUE; 81 long b = 1; 82 Assert.assertFalse(IntegerStamp.multiplicationOverflows(a, b, 32)); 83 } 84 85 @Test 86 public void testOverflowCheck05() { 87 // a.u * b.u overflows 88 long a = Integer.MAX_VALUE; 89 long b = Integer.MIN_VALUE; 90 Assert.assertTrue(IntegerStamp.multiplicationOverflows(a, b, 32)); 91 } 92 93 @Test 94 public void testOverflowCheck06() { 95 // 31bits*31bits = 62bits + 1 carry is max 63 bits, we can never need 64 bits 96 long a = Integer.MAX_VALUE; 97 long b = Integer.MAX_VALUE; 98 Assert.assertTrue("31bit*31bit overflows 62", IntegerStamp.multiplicationOverflows(a, b, 62)); 99 Assert.assertFalse("31bit*31bit does not overflow 63", IntegerStamp.multiplicationOverflows(a, b, 63)); 100 Assert.assertFalse("31bit*31bit does not overflow 64", IntegerStamp.multiplicationOverflows(a, b, 64)); 101 } 102 103 @Test 104 public void testOverflowCheck07() { 105 long a = Long.MAX_VALUE; 106 long b = 2; 107 Assert.assertTrue(IntegerStamp.multiplicationOverflows(a, b, 64)); 108 } 109 110 @Test 111 public void testOverflowCheck08() { 112 long a = Long.MAX_VALUE; 113 long b = Long.MAX_VALUE; 114 Assert.assertTrue(IntegerStamp.multiplicationOverflows(a, b, 64)); 115 } 116 117 @Test 118 public void testOverflowCheck09() { 119 long a = -Long.MAX_VALUE; 120 long b = Long.MAX_VALUE; 121 Assert.assertTrue(IntegerStamp.multiplicationOverflows(a, b, 64)); 122 } 123 124 @Test 125 public void testOverflowCheck10() { 126 long a = -Long.MAX_VALUE; 127 long b = -Long.MAX_VALUE; 128 Assert.assertTrue(IntegerStamp.multiplicationOverflows(a, b, 64)); 129 } 130 131 @Test 132 public void testOverflowCheck11() { 133 long a = Long.MAX_VALUE; 134 long b = -Long.MAX_VALUE; 135 Assert.assertTrue(IntegerStamp.multiplicationOverflows(a, b, 64)); 136 } 137 } 138 139 @RunWith(Parameterized.class) 140 public static class FoldTest { 141 @Parameter(0) public long lowerBound1; 142 @Parameter(1) public long upperBound1; 143 @Parameter(2) public long lowerBound2; 144 @Parameter(3) public long upperBound2; 145 @Parameter(4) public int bits; 146 147 @Test 148 public void computeStamp() { 149 IntegerStamp a = StampFactory.forInteger(bits, lowerBound1, upperBound1); 150 IntegerStamp b = StampFactory.forInteger(bits, lowerBound2, upperBound2); 151 IntegerStamp result = foldMul(a, b); 152 for (long l1 = lowerBound1; l1 <= upperBound1; l1++) { 153 for (long l2 = lowerBound2; l2 <= upperBound2; l2++) { 154 long res = 0; 155 if (bits == 8) { 156 res = (byte) (l1 * l2); 157 } else if (bits == 16) { 158 res = (short) (l1 * l2); 159 } else if (bits == 32) { 160 res = (int) (l1 * l2); 161 } else if (bits == 64) { 162 res = l1 * l2; 163 } 164 Assert.assertTrue(result.contains(res)); 165 if (l2 == Long.MAX_VALUE) { 166 // do not want to overflow the check loop 167 break; 168 } 169 } 170 if (l1 == Long.MAX_VALUE) { 171 // do not want to overflow the check loop 172 break; 173 } 174 } 175 } 176 177 @Parameters(name = "a[{0} - {1}] b[{2} - {3}] bits=32") 178 public static Collection<Object[]> data() { 179 ArrayList<Object[]> tests = new ArrayList<>(); 180 181 // zero related 182 addTest(tests, -2, 2, 3, 3, 8); 183 addTest(tests, 0, 0, 1, 1, 8); 184 addTest(tests, 1, 1, 0, 0, 8); 185 addTest(tests, -1, 1, 0, 1, 8); 186 addTest(tests, -1, 1, 1, 1, 8); 187 addTest(tests, -1, 1, -1, 1, 8); 188 189 addTest(tests, -2, 2, 3, 3, 16); 190 addTest(tests, 0, 0, 1, 1, 16); 191 addTest(tests, 1, 1, 0, 0, 16); 192 addTest(tests, -1, 1, 0, 1, 16); 193 addTest(tests, -1, 1, 1, 1, 16); 194 addTest(tests, -1, 1, -1, 1, 16); 195 196 addTest(tests, -2, 2, 3, 3, 32); 197 addTest(tests, 0, 0, 1, 1, 32); 198 addTest(tests, 1, 1, 0, 0, 32); 199 addTest(tests, -1, 1, 0, 1, 32); 200 addTest(tests, -1, 1, 1, 1, 32); 201 addTest(tests, -1, 1, -1, 1, 32); 202 203 addTest(tests, 0, 0, 1, 1, 64); 204 addTest(tests, 1, 1, 0, 0, 64); 205 addTest(tests, -1, 1, 0, 1, 64); 206 addTest(tests, -1, 1, 1, 1, 64); 207 addTest(tests, -1, 1, -1, 1, 64); 208 209 // bounds 210 addTest(tests, Byte.MIN_VALUE, Byte.MIN_VALUE + 1, Byte.MAX_VALUE - 1, Byte.MAX_VALUE, 8); 211 addTest(tests, Byte.MIN_VALUE, Byte.MIN_VALUE + 1, -1, -1, 8); 212 addTest(tests, Integer.MIN_VALUE, Integer.MIN_VALUE + 0xFF, Integer.MAX_VALUE - 0xFF, 213 Integer.MAX_VALUE, 32); 214 addTest(tests, Integer.MIN_VALUE, Integer.MIN_VALUE + 0xFFF, -1, -1, 32); 215 addTest(tests, Integer.MIN_VALUE, Integer.MIN_VALUE + 0xFF, Integer.MAX_VALUE - 0xFF, 216 Integer.MAX_VALUE, 64); 217 addTest(tests, Integer.MIN_VALUE, Integer.MIN_VALUE + 0xFFF, -1, -1, 64); 218 addTest(tests, Long.MIN_VALUE, Long.MIN_VALUE + 0xFFF, -1, -1, 64); 219 220 // constants 221 addTest(tests, 2, 2, 2, 2, 32); 222 addTest(tests, 1, 1, 2, 2, 32); 223 addTest(tests, 2, 2, 4, 4, 32); 224 addTest(tests, 3, 3, 3, 3, 32); 225 addTest(tests, -4, -4, 3, 3, 32); 226 addTest(tests, -4, -4, -3, -3, 32); 227 addTest(tests, 4, 4, -3, -3, 32); 228 229 addTest(tests, 2, 2, 2, 2, 64); 230 addTest(tests, 1, 1, 2, 2, 64); 231 addTest(tests, 3, 3, 3, 3, 64); 232 233 addTest(tests, Long.MAX_VALUE, Long.MAX_VALUE, 1, 1, 64); 234 addTest(tests, Long.MAX_VALUE, Long.MAX_VALUE, -1, -1, 64); 235 addTest(tests, Long.MIN_VALUE, Long.MIN_VALUE, -1, -1, 64); 236 addTest(tests, Long.MIN_VALUE, Long.MIN_VALUE, 1, 1, 64); 237 238 return tests; 239 } 240 241 private static void addTest(ArrayList<Object[]> tests, long lowerBound1, long upperBound1, long lowerBound2, long upperBound2, int bits) { 242 tests.add(new Object[]{lowerBound1, upperBound1, lowerBound2, upperBound2, bits}); 243 } 244 245 } 246 247 private static IntegerStamp foldMul(IntegerStamp a, IntegerStamp b) { 248 return (IntegerStamp) IntegerStamp.OPS.getMul().foldStamp(a, b); 249 } 250 251 }