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