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 }