1 /* 2 * Copyright (c) 2012, 2015, 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 java.util.EnumSet; 28 import java.util.HashSet; 29 30 import org.graalvm.compiler.core.common.calc.FloatConvert; 31 import org.graalvm.compiler.core.common.calc.FloatConvertCategory; 32 import org.graalvm.compiler.core.common.type.ArithmeticOpTable; 33 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp; 34 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.IntegerConvertOp; 35 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.ShiftOp; 36 import org.graalvm.compiler.core.common.type.FloatStamp; 37 import org.graalvm.compiler.core.common.type.IntegerStamp; 38 import org.graalvm.compiler.core.common.type.PrimitiveStamp; 39 import org.graalvm.compiler.core.common.type.Stamp; 40 import org.graalvm.compiler.core.common.type.StampFactory; 41 import org.graalvm.compiler.test.GraalTest; 42 import org.junit.Test; 43 44 import jdk.vm.ci.meta.Constant; 45 import jdk.vm.ci.meta.JavaConstant; 46 import jdk.vm.ci.meta.JavaKind; 47 48 /** 49 * Exercise the various stamp folding operations by generating ranges from a set of boundary values 50 * and then ensuring that the values that produced those ranges are in the resulting stamp. 51 */ 52 public class PrimitiveStampBoundaryTest extends GraalTest { 53 54 static long[] longBoundaryValues = {Long.MIN_VALUE, Long.MIN_VALUE + 1, Integer.MIN_VALUE, Integer.MIN_VALUE + 1, -1, 0, 1, Integer.MAX_VALUE - 1, Integer.MAX_VALUE, Long.MAX_VALUE - 1, 55 Long.MAX_VALUE}; 56 57 static int[] shiftBoundaryValues = {-128, -1, 0, 1, 4, 8, 16, 31, 63, 128}; 58 59 static HashSet<IntegerStamp> shiftStamps; 60 static HashSet<PrimitiveStamp> integerTestStamps; 61 static HashSet<PrimitiveStamp> floatTestStamps; 62 63 static { 64 shiftStamps = new HashSet<>(); 65 for (long v1 : shiftBoundaryValues) { 66 for (long v2 : shiftBoundaryValues) { 67 shiftStamps.add(IntegerStamp.create(32, Math.min(v1, v2), Math.max(v1, v2))); 68 } 69 } shiftStamps.add(IntegerStamp) StampFactory.empty(JavaKind.Int)70 shiftStamps.add((IntegerStamp) StampFactory.empty(JavaKind.Int)); 71 72 integerTestStamps = new HashSet<>(); 73 for (long v1 : longBoundaryValues) { 74 for (long v2 : longBoundaryValues) { 75 if (v2 == (int) v2 && v1 == (int) v1) { 76 integerTestStamps.add(IntegerStamp.create(32, Math.min(v1, v2), Math.max(v1, v2))); 77 } 78 integerTestStamps.add(IntegerStamp.create(64, Math.min(v1, v2), Math.max(v1, v2))); 79 } 80 } integerTestStamps.add(PrimitiveStamp) StampFactory.empty(JavaKind.Int)81 integerTestStamps.add((PrimitiveStamp) StampFactory.empty(JavaKind.Int)); integerTestStamps.add(PrimitiveStamp) StampFactory.empty(JavaKind.Long)82 integerTestStamps.add((PrimitiveStamp) StampFactory.empty(JavaKind.Long)); 83 } 84 85 static double[] doubleBoundaryValues = {Double.NEGATIVE_INFINITY, Double.MIN_VALUE, Float.NEGATIVE_INFINITY, Float.MIN_VALUE, 86 Long.MIN_VALUE, Long.MIN_VALUE + 1, Integer.MIN_VALUE, Integer.MIN_VALUE + 1, -1, 0, 1, 87 Integer.MAX_VALUE - 1, Integer.MAX_VALUE, Long.MAX_VALUE - 1, Long.MAX_VALUE, 88 Float.MAX_VALUE, Float.POSITIVE_INFINITY, Double.MAX_VALUE, Double.POSITIVE_INFINITY}; 89 90 static double[] doubleSpecialValues = {Double.NaN, -0.0, -0.0F, Float.NaN}; 91 92 static { 93 floatTestStamps = new HashSet<>(); 94 95 for (double d1 : doubleBoundaryValues) { 96 for (double d2 : doubleBoundaryValues) { 97 float f1 = (float) d2; 98 float f2 = (float) d1; 99 if (d2 == f1 && d1 == f2) { generateFloatingStamps(new FloatStamp(32, Math.min(f2, f1), Math.max(f2, f1), true))100 generateFloatingStamps(new FloatStamp(32, Math.min(f2, f1), Math.max(f2, f1), true)); generateFloatingStamps(new FloatStamp(32, Math.min(f2, f1), Math.max(f2, f1), false))101 generateFloatingStamps(new FloatStamp(32, Math.min(f2, f1), Math.max(f2, f1), false)); 102 } generateFloatingStamps(new FloatStamp(64, Math.min(d1, d2), Math.max(d1, d2), true))103 generateFloatingStamps(new FloatStamp(64, Math.min(d1, d2), Math.max(d1, d2), true)); generateFloatingStamps(new FloatStamp(64, Math.min(d1, d2), Math.max(d1, d2), false))104 generateFloatingStamps(new FloatStamp(64, Math.min(d1, d2), Math.max(d1, d2), false)); 105 } 106 } floatTestStamps.add(PrimitiveStamp) StampFactory.empty(JavaKind.Float)107 floatTestStamps.add((PrimitiveStamp) StampFactory.empty(JavaKind.Float)); floatTestStamps.add(PrimitiveStamp) StampFactory.empty(JavaKind.Double)108 floatTestStamps.add((PrimitiveStamp) StampFactory.empty(JavaKind.Double)); 109 } 110 generateFloatingStamps(FloatStamp floatStamp)111 private static void generateFloatingStamps(FloatStamp floatStamp) { 112 floatTestStamps.add(floatStamp); 113 for (double d : doubleSpecialValues) { 114 FloatStamp newStamp = (FloatStamp) floatStamp.meet(floatStampForConstant(d, floatStamp.getBits())); 115 if (!newStamp.isUnrestricted()) { 116 floatTestStamps.add(newStamp); 117 } 118 } 119 } 120 121 @Test testConvertBoundaryValues()122 public void testConvertBoundaryValues() { 123 testConvertBoundaryValues(IntegerStamp.OPS.getSignExtend(), 32, 64, integerTestStamps); 124 testConvertBoundaryValues(IntegerStamp.OPS.getZeroExtend(), 32, 64, integerTestStamps); 125 testConvertBoundaryValues(IntegerStamp.OPS.getNarrow(), 64, 32, integerTestStamps); 126 } 127 testConvertBoundaryValues(IntegerConvertOp<?> op, int inputBits, int resultBits, HashSet<PrimitiveStamp> stamps)128 private static void testConvertBoundaryValues(IntegerConvertOp<?> op, int inputBits, int resultBits, HashSet<PrimitiveStamp> stamps) { 129 for (PrimitiveStamp stamp : stamps) { 130 if (inputBits == stamp.getBits()) { 131 Stamp lower = boundaryStamp(stamp, false); 132 Stamp upper = boundaryStamp(stamp, true); 133 checkConvertOperation(op, inputBits, resultBits, op.foldStamp(inputBits, resultBits, stamp), lower); 134 checkConvertOperation(op, inputBits, resultBits, op.foldStamp(inputBits, resultBits, stamp), upper); 135 } 136 } 137 } 138 checkConvertOperation(IntegerConvertOp<?> op, int inputBits, int resultBits, Stamp result, Stamp v1stamp)139 private static void checkConvertOperation(IntegerConvertOp<?> op, int inputBits, int resultBits, Stamp result, Stamp v1stamp) { 140 Stamp folded = op.foldStamp(inputBits, resultBits, v1stamp); 141 assertTrue(folded.isEmpty() || folded.asConstant() != null, "should constant fold %s %s %s", op, v1stamp, folded); 142 assertTrue(result.meet(folded).equals(result), "result out of range %s %s %s %s %s", op, v1stamp, folded, result, result.meet(folded)); 143 } 144 145 @Test testFloatConvertBoundaryValues()146 public void testFloatConvertBoundaryValues() { 147 for (FloatConvert op : EnumSet.allOf(FloatConvert.class)) { 148 ArithmeticOpTable.FloatConvertOp floatConvert = IntegerStamp.OPS.getFloatConvert(op); 149 if (floatConvert == null) { 150 continue; 151 } 152 assert op.getCategory() == FloatConvertCategory.IntegerToFloatingPoint : op; 153 testConvertBoundaryValues(floatConvert, op.getInputBits(), integerTestStamps); 154 } 155 for (FloatConvert op : EnumSet.allOf(FloatConvert.class)) { 156 ArithmeticOpTable.FloatConvertOp floatConvert = FloatStamp.OPS.getFloatConvert(op); 157 if (floatConvert == null) { 158 continue; 159 } 160 assert op.getCategory() == FloatConvertCategory.FloatingPointToInteger || op.getCategory() == FloatConvertCategory.FloatingPointToFloatingPoint : op; 161 testConvertBoundaryValues(floatConvert, op.getInputBits(), floatTestStamps); 162 } 163 } 164 testConvertBoundaryValues(ArithmeticOpTable.FloatConvertOp op, int bits, HashSet<PrimitiveStamp> stamps)165 private static void testConvertBoundaryValues(ArithmeticOpTable.FloatConvertOp op, int bits, HashSet<PrimitiveStamp> stamps) { 166 for (PrimitiveStamp stamp : stamps) { 167 if (bits == stamp.getBits()) { 168 Stamp lower = boundaryStamp(stamp, false); 169 Stamp upper = boundaryStamp(stamp, true); 170 checkConvertOperation(op, op.foldStamp(stamp), lower); 171 checkConvertOperation(op, op.foldStamp(stamp), upper); 172 } 173 } 174 } 175 checkConvertOperation(ArithmeticOpTable.FloatConvertOp op, Stamp result, Stamp v1stamp)176 private static void checkConvertOperation(ArithmeticOpTable.FloatConvertOp op, Stamp result, Stamp v1stamp) { 177 Stamp folded = op.foldStamp(v1stamp); 178 assertTrue(folded.isEmpty() || folded.asConstant() != null, "should constant fold %s %s %s", op, v1stamp, folded); 179 assertTrue(result.meet(folded).equals(result), "result out of range %s %s %s %s %s", op, v1stamp, folded, result, result.meet(folded)); 180 } 181 182 @Test testShiftBoundaryValues()183 public void testShiftBoundaryValues() { 184 for (ShiftOp<?> op : IntegerStamp.OPS.getShiftOps()) { 185 testShiftBoundaryValues(op, integerTestStamps, shiftStamps); 186 } 187 } 188 testShiftBoundaryValues(ShiftOp<?> shiftOp, HashSet<PrimitiveStamp> stamps, HashSet<IntegerStamp> shifts)189 private static void testShiftBoundaryValues(ShiftOp<?> shiftOp, HashSet<PrimitiveStamp> stamps, HashSet<IntegerStamp> shifts) { 190 for (PrimitiveStamp testStamp : stamps) { 191 if (testStamp instanceof IntegerStamp) { 192 IntegerStamp stamp = (IntegerStamp) testStamp; 193 for (IntegerStamp shiftStamp : shifts) { 194 IntegerStamp foldedStamp = (IntegerStamp) shiftOp.foldStamp(stamp, shiftStamp); 195 if (foldedStamp.isEmpty()) { 196 assertTrue(stamp.isEmpty() || shiftStamp.isEmpty()); 197 continue; 198 } 199 checkShiftOperation(stamp.getBits(), shiftOp, foldedStamp, stamp.lowerBound(), shiftStamp.lowerBound()); 200 checkShiftOperation(stamp.getBits(), shiftOp, foldedStamp, stamp.lowerBound(), shiftStamp.upperBound()); 201 checkShiftOperation(stamp.getBits(), shiftOp, foldedStamp, stamp.upperBound(), shiftStamp.lowerBound()); 202 checkShiftOperation(stamp.getBits(), shiftOp, foldedStamp, stamp.upperBound(), shiftStamp.upperBound()); 203 } 204 } 205 } 206 } 207 checkShiftOperation(int bits, ShiftOp<?> op, IntegerStamp result, long v1, long v2)208 private static void checkShiftOperation(int bits, ShiftOp<?> op, IntegerStamp result, long v1, long v2) { 209 IntegerStamp v1stamp = IntegerStamp.create(bits, v1, v1); 210 IntegerStamp v2stamp = IntegerStamp.create(32, v2, v2); 211 IntegerStamp folded = (IntegerStamp) op.foldStamp(v1stamp, v2stamp); 212 Constant constant = op.foldConstant(JavaConstant.forPrimitiveInt(bits, v1), (int) v2); 213 assertTrue(constant != null); 214 assertTrue(folded.asConstant() != null, "should constant fold %s %s %s %s", op, v1stamp, v2stamp, folded); 215 assertTrue(result.meet(folded).equals(result), "result out of range %s %s %s %s %s %s", op, v1stamp, v2stamp, folded, result, result.meet(folded)); 216 } 217 checkBinaryOperation(ArithmeticOpTable.BinaryOp<?> op, Stamp result, Stamp v1stamp, Stamp v2stamp)218 private static void checkBinaryOperation(ArithmeticOpTable.BinaryOp<?> op, Stamp result, Stamp v1stamp, Stamp v2stamp) { 219 Stamp folded = op.foldStamp(v1stamp, v2stamp); 220 if (v1stamp.isEmpty() || v2stamp.isEmpty()) { 221 assertTrue(folded.isEmpty()); 222 assertTrue(v1stamp.asConstant() != null || v1stamp.isEmpty()); 223 assertTrue(v2stamp.asConstant() != null || v2stamp.isEmpty()); 224 return; 225 } 226 Constant constant = op.foldConstant(v1stamp.asConstant(), v2stamp.asConstant()); 227 if (constant != null) { 228 assertFalse(folded.isEmpty()); 229 Constant constant2 = folded.asConstant(); 230 if (constant2 == null && v1stamp instanceof FloatStamp) { 231 JavaConstant c = (JavaConstant) constant; 232 assertTrue((c.getJavaKind() == JavaKind.Double && Double.isNaN(c.asDouble())) || 233 (c.getJavaKind() == JavaKind.Float && Float.isNaN(c.asFloat()))); 234 } else { 235 assertTrue(constant2 != null, "should constant fold %s %s %s %s", op, v1stamp, v2stamp, folded); 236 if (!constant.equals(constant2)) { 237 op.foldConstant(v1stamp.asConstant(), v2stamp.asConstant()); 238 op.foldStamp(v1stamp, v2stamp); 239 } 240 assertTrue(constant.equals(constant2), "should produce same constant %s %s %s %s %s", op, v1stamp, v2stamp, constant, constant2); 241 } 242 assertTrue(result.meet(folded).equals(result), "result out of range %s %s %s %s %s %s", op, v1stamp, v2stamp, folded, result, result.meet(folded)); 243 } 244 } 245 246 @Test testBinaryBoundaryValues()247 public void testBinaryBoundaryValues() { 248 for (BinaryOp<?> op : IntegerStamp.OPS.getBinaryOps()) { 249 if (op != null) { 250 testBinaryBoundaryValues(op, integerTestStamps); 251 } 252 } 253 for (BinaryOp<?> op : FloatStamp.OPS.getBinaryOps()) { 254 if (op != null) { 255 testBinaryBoundaryValues(op, floatTestStamps); 256 } 257 } 258 } 259 boundaryStamp(Stamp v1, boolean upper)260 private static Stamp boundaryStamp(Stamp v1, boolean upper) { 261 if (v1.isEmpty()) { 262 return v1; 263 } 264 if (v1 instanceof IntegerStamp) { 265 IntegerStamp istamp = (IntegerStamp) v1; 266 long bound = upper ? istamp.upperBound() : istamp.lowerBound(); 267 return IntegerStamp.create(istamp.getBits(), bound, bound); 268 } else if (v1 instanceof FloatStamp) { 269 FloatStamp floatStamp = (FloatStamp) v1; 270 double bound = upper ? floatStamp.upperBound() : floatStamp.lowerBound(); 271 int bits = floatStamp.getBits(); 272 return floatStampForConstant(bound, bits); 273 } else { 274 throw new InternalError("unexpected stamp type " + v1); 275 } 276 } 277 floatStampForConstant(double bound, int bits)278 private static FloatStamp floatStampForConstant(double bound, int bits) { 279 if (bits == 32) { 280 float fbound = (float) bound; 281 return new FloatStamp(bits, fbound, fbound, !Float.isNaN(fbound)); 282 } else { 283 return new FloatStamp(bits, bound, bound, !Double.isNaN(bound)); 284 } 285 } 286 testBinaryBoundaryValues(ArithmeticOpTable.BinaryOp<?> op, HashSet<PrimitiveStamp> stamps)287 private static void testBinaryBoundaryValues(ArithmeticOpTable.BinaryOp<?> op, HashSet<PrimitiveStamp> stamps) { 288 for (PrimitiveStamp v1 : stamps) { 289 for (PrimitiveStamp v2 : stamps) { 290 if (v1.getBits() == v2.getBits() && v1.getClass() == v2.getClass()) { 291 Stamp result = op.foldStamp(v1, v2); 292 Stamp v1lower = boundaryStamp(v1, false); 293 Stamp v1upper = boundaryStamp(v1, true); 294 Stamp v2lower = boundaryStamp(v2, false); 295 Stamp v2upper = boundaryStamp(v2, true); 296 checkBinaryOperation(op, result, v1lower, v2lower); 297 checkBinaryOperation(op, result, v1lower, v2upper); 298 checkBinaryOperation(op, result, v1upper, v2lower); 299 checkBinaryOperation(op, result, v1upper, v2upper); 300 } 301 } 302 } 303 } 304 305 @Test testUnaryBoundaryValues()306 public void testUnaryBoundaryValues() { 307 for (ArithmeticOpTable.UnaryOp<?> op : IntegerStamp.OPS.getUnaryOps()) { 308 if (op != null) { 309 testUnaryBoundaryValues(op, integerTestStamps); 310 } 311 } 312 for (ArithmeticOpTable.UnaryOp<?> op : FloatStamp.OPS.getUnaryOps()) { 313 if (op != null) { 314 testUnaryBoundaryValues(op, floatTestStamps); 315 } 316 } 317 } 318 testUnaryBoundaryValues(ArithmeticOpTable.UnaryOp<?> op, HashSet<PrimitiveStamp> stamps)319 private static void testUnaryBoundaryValues(ArithmeticOpTable.UnaryOp<?> op, HashSet<PrimitiveStamp> stamps) { 320 for (PrimitiveStamp v1 : stamps) { 321 Stamp result = op.foldStamp(v1); 322 checkUnaryOperation(op, result, boundaryStamp(v1, false)); 323 checkUnaryOperation(op, result, boundaryStamp(v1, true)); 324 } 325 } 326 checkUnaryOperation(ArithmeticOpTable.UnaryOp<?> op, Stamp result, Stamp v1stamp)327 private static void checkUnaryOperation(ArithmeticOpTable.UnaryOp<?> op, Stamp result, Stamp v1stamp) { 328 Stamp folded = op.foldStamp(v1stamp); 329 Constant v1constant = v1stamp.asConstant(); 330 if (v1constant != null) { 331 Constant constant = op.foldConstant(v1constant); 332 if (constant != null) { 333 Constant constant2 = folded.asConstant(); 334 if (constant2 == null && v1stamp instanceof FloatStamp) { 335 JavaConstant c = (JavaConstant) constant; 336 assertTrue((c.getJavaKind() == JavaKind.Double && Double.isNaN(c.asDouble())) || 337 (c.getJavaKind() == JavaKind.Float && Float.isNaN(c.asFloat()))); 338 } else { 339 assertTrue(constant2 != null, "should constant fold %s %s %s", op, v1stamp, folded); 340 assertTrue(constant.equals(constant2), "should produce same constant %s %s %s %s", op, v1stamp, constant, constant2); 341 } 342 } 343 } else { 344 assertTrue(v1stamp.isEmpty() || v1stamp instanceof FloatStamp); 345 } 346 assertTrue(result.meet(folded).equals(result), "result out of range %s %s %s %s %s", op, v1stamp, folded, result, result.meet(folded)); 347 } 348 } 349