1 /* 2 * Copyright (c) 2011, 2017, 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.calc; 26 27 import static org.graalvm.compiler.core.common.calc.CanonicalCondition.LT; 28 29 import org.graalvm.compiler.core.common.NumUtil; 30 import org.graalvm.compiler.core.common.calc.CanonicalCondition; 31 import org.graalvm.compiler.core.common.type.FloatStamp; 32 import org.graalvm.compiler.core.common.type.IntegerStamp; 33 import org.graalvm.compiler.core.common.type.StampFactory; 34 import org.graalvm.compiler.debug.GraalError; 35 import org.graalvm.compiler.graph.Node; 36 import org.graalvm.compiler.graph.NodeClass; 37 import org.graalvm.compiler.graph.spi.CanonicalizerTool; 38 import org.graalvm.compiler.nodeinfo.NodeInfo; 39 import org.graalvm.compiler.nodes.ConstantNode; 40 import org.graalvm.compiler.nodes.LogicConstantNode; 41 import org.graalvm.compiler.nodes.LogicNegationNode; 42 import org.graalvm.compiler.nodes.LogicNode; 43 import org.graalvm.compiler.nodes.NodeView; 44 import org.graalvm.compiler.nodes.ValueNode; 45 import org.graalvm.compiler.options.OptionValues; 46 47 import jdk.vm.ci.code.CodeUtil; 48 import jdk.vm.ci.meta.Constant; 49 import jdk.vm.ci.meta.ConstantReflectionProvider; 50 import jdk.vm.ci.meta.JavaConstant; 51 import jdk.vm.ci.meta.JavaKind; 52 import jdk.vm.ci.meta.MetaAccessProvider; 53 import jdk.vm.ci.meta.PrimitiveConstant; 54 55 @NodeInfo(shortName = "<") 56 public final class IntegerLessThanNode extends IntegerLowerThanNode { 57 public static final NodeClass<IntegerLessThanNode> TYPE = NodeClass.create(IntegerLessThanNode.class); 58 private static final LessThanOp OP = new LessThanOp(); 59 IntegerLessThanNode(ValueNode x, ValueNode y)60 public IntegerLessThanNode(ValueNode x, ValueNode y) { 61 super(TYPE, x, y, OP); 62 assert !x.getStackKind().isNumericFloat() && x.getStackKind() != JavaKind.Object; 63 assert !y.getStackKind().isNumericFloat() && y.getStackKind() != JavaKind.Object; 64 } 65 create(ValueNode x, ValueNode y, NodeView view)66 public static LogicNode create(ValueNode x, ValueNode y, NodeView view) { 67 return OP.create(x, y, view); 68 } 69 create(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, ValueNode x, ValueNode y, NodeView view)70 public static LogicNode create(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, 71 ValueNode x, ValueNode y, NodeView view) { 72 LogicNode value = OP.canonical(constantReflection, metaAccess, options, smallestCompareWidth, OP.getCondition(), false, x, y, view); 73 if (value != null) { 74 return value; 75 } 76 return create(x, y, view); 77 } 78 79 @Override canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY)80 public Node canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) { 81 NodeView view = NodeView.from(tool); 82 ValueNode value = OP.canonical(tool.getConstantReflection(), tool.getMetaAccess(), tool.getOptions(), tool.smallestCompareWidth(), OP.getCondition(), false, forX, forY, view); 83 if (value != null) { 84 return value; 85 } 86 return this; 87 } 88 subtractMayUnderflow(long x, long y, long minValue)89 public static boolean subtractMayUnderflow(long x, long y, long minValue) { 90 long r = x - y; 91 // HD 2-12 Overflow iff the arguments have different signs and 92 // the sign of the result is different than the sign of x 93 return (((x ^ y) & (x ^ r)) < 0) || r <= minValue; 94 } 95 subtractMayOverflow(long x, long y, long maxValue)96 public static boolean subtractMayOverflow(long x, long y, long maxValue) { 97 long r = x - y; 98 // HD 2-12 Overflow iff the arguments have different signs and 99 // the sign of the result is different than the sign of x 100 return (((x ^ y) & (x ^ r)) < 0) || r > maxValue; 101 } 102 103 public static class LessThanOp extends LowerOp { 104 @Override duplicateModified(ValueNode newX, ValueNode newY, boolean unorderedIsTrue, NodeView view)105 protected CompareNode duplicateModified(ValueNode newX, ValueNode newY, boolean unorderedIsTrue, NodeView view) { 106 if (newX.stamp(view) instanceof FloatStamp && newY.stamp(view) instanceof FloatStamp) { 107 return new FloatLessThanNode(newX, newY, unorderedIsTrue); // TODO: Is the last arg 108 // supposed to be true? 109 } else if (newX.stamp(view) instanceof IntegerStamp && newY.stamp(view) instanceof IntegerStamp) { 110 return new IntegerLessThanNode(newX, newY); 111 } 112 throw GraalError.shouldNotReachHere(); 113 } 114 115 @Override optimizeNormalizeCompare(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, Constant constant, NormalizeCompareNode normalizeNode, boolean mirrored, NodeView view)116 protected LogicNode optimizeNormalizeCompare(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, 117 Constant constant, NormalizeCompareNode normalizeNode, boolean mirrored, NodeView view) { 118 PrimitiveConstant primitive = (PrimitiveConstant) constant; 119 /* @formatter:off 120 * a NC b < c (not mirrored) 121 * cases for c: 122 * 0 -> a < b 123 * [MIN, -1] -> false 124 * 1 -> a <= b 125 * [2, MAX] -> true 126 * unordered-is-less means unordered-is-true. 127 * 128 * c < a NC b (mirrored) 129 * cases for c: 130 * 0 -> a > b 131 * [1, MAX] -> false 132 * -1 -> a >= b 133 * [MIN, -2] -> true 134 * unordered-is-less means unordered-is-false. 135 * 136 * We can handle mirroring by swapping a & b and negating the constant. 137 * @formatter:on 138 */ 139 ValueNode a = mirrored ? normalizeNode.getY() : normalizeNode.getX(); 140 ValueNode b = mirrored ? normalizeNode.getX() : normalizeNode.getY(); 141 long cst = mirrored ? -primitive.asLong() : primitive.asLong(); 142 143 if (cst == 0) { 144 if (normalizeNode.getX().getStackKind() == JavaKind.Double || normalizeNode.getX().getStackKind() == JavaKind.Float) { 145 return FloatLessThanNode.create(constantReflection, metaAccess, options, smallestCompareWidth, a, b, mirrored ^ normalizeNode.isUnorderedLess, view); 146 } else { 147 return IntegerLessThanNode.create(constantReflection, metaAccess, options, smallestCompareWidth, a, b, view); 148 } 149 } else if (cst == 1) { 150 // a <= b <=> !(a > b) 151 LogicNode compare; 152 if (normalizeNode.getX().getStackKind() == JavaKind.Double || normalizeNode.getX().getStackKind() == JavaKind.Float) { 153 // since we negate, we have to reverse the unordered result 154 compare = FloatLessThanNode.create(constantReflection, metaAccess, options, smallestCompareWidth, b, a, mirrored == normalizeNode.isUnorderedLess, view); 155 } else { 156 compare = IntegerLessThanNode.create(constantReflection, metaAccess, options, smallestCompareWidth, b, a, view); 157 } 158 return LogicNegationNode.create(compare); 159 } else if (cst <= -1) { 160 return LogicConstantNode.contradiction(); 161 } else { 162 assert cst >= 2; 163 return LogicConstantNode.tautology(); 164 } 165 } 166 167 @Override findSynonym(ValueNode forX, ValueNode forY, NodeView view)168 protected LogicNode findSynonym(ValueNode forX, ValueNode forY, NodeView view) { 169 LogicNode result = super.findSynonym(forX, forY, view); 170 if (result != null) { 171 return result; 172 } 173 if (forX.stamp(view) instanceof IntegerStamp && forY.stamp(view) instanceof IntegerStamp) { 174 if (IntegerStamp.sameSign((IntegerStamp) forX.stamp(view), (IntegerStamp) forY.stamp(view))) { 175 return new IntegerBelowNode(forX, forY); 176 } 177 } 178 if (forY.isConstant() && forX instanceof SubNode) { 179 SubNode sub = (SubNode) forX; 180 ValueNode xx = null; 181 ValueNode yy = null; 182 boolean negate = false; 183 if (forY.asConstant().isDefaultForKind()) { 184 // (x - y) < 0 when x - y is known not to underflow <=> x < y 185 xx = sub.getX(); 186 yy = sub.getY(); 187 } else if (forY.isJavaConstant() && forY.asJavaConstant().asLong() == 1) { 188 // (x - y) < 1 when x - y is known not to underflow <=> !(y < x) 189 xx = sub.getY(); 190 yy = sub.getX(); 191 negate = true; 192 } 193 if (xx != null) { 194 assert yy != null; 195 IntegerStamp xStamp = (IntegerStamp) sub.getX().stamp(view); 196 IntegerStamp yStamp = (IntegerStamp) sub.getY().stamp(view); 197 long minValue = CodeUtil.minValue(xStamp.getBits()); 198 long maxValue = CodeUtil.maxValue(xStamp.getBits()); 199 200 if (!subtractMayUnderflow(xStamp.lowerBound(), yStamp.upperBound(), minValue) && !subtractMayOverflow(xStamp.upperBound(), yStamp.lowerBound(), maxValue)) { 201 LogicNode logic = new IntegerLessThanNode(xx, yy); 202 if (negate) { 203 logic = LogicNegationNode.create(logic); 204 } 205 return logic; 206 } 207 } 208 } 209 210 if (forX.stamp(view) instanceof IntegerStamp) { 211 assert forY.stamp(view) instanceof IntegerStamp; 212 int bits = ((IntegerStamp) forX.stamp(view)).getBits(); 213 assert ((IntegerStamp) forY.stamp(view)).getBits() == bits; 214 long min = OP.minValue(bits); 215 long xResidue = 0; 216 ValueNode left = null; 217 JavaConstant leftCst = null; 218 if (forX instanceof AddNode) { 219 AddNode xAdd = (AddNode) forX; 220 if (xAdd.getY().isJavaConstant()) { 221 long xCst = xAdd.getY().asJavaConstant().asLong(); 222 xResidue = xCst - min; 223 left = xAdd.getX(); 224 } 225 } else if (forX.isJavaConstant()) { 226 leftCst = forX.asJavaConstant(); 227 } 228 if (left != null || leftCst != null) { 229 long yResidue = 0; 230 ValueNode right = null; 231 JavaConstant rightCst = null; 232 if (forY instanceof AddNode) { 233 AddNode yAdd = (AddNode) forY; 234 if (yAdd.getY().isJavaConstant()) { 235 long yCst = yAdd.getY().asJavaConstant().asLong(); 236 yResidue = yCst - min; 237 right = yAdd.getX(); 238 } 239 } else if (forY.isJavaConstant()) { 240 rightCst = forY.asJavaConstant(); 241 } 242 if (right != null || rightCst != null) { 243 if ((xResidue == 0 && left != null) || (yResidue == 0 && right != null)) { 244 if (left == null) { 245 left = ConstantNode.forIntegerBits(bits, leftCst.asLong() - min); 246 } else if (xResidue != 0) { 247 left = AddNode.create(left, ConstantNode.forIntegerBits(bits, xResidue), view); 248 } 249 if (right == null) { 250 right = ConstantNode.forIntegerBits(bits, rightCst.asLong() - min); 251 } else if (yResidue != 0) { 252 right = AddNode.create(right, ConstantNode.forIntegerBits(bits, yResidue), view); 253 } 254 return new IntegerBelowNode(left, right); 255 } 256 } 257 } 258 } 259 return null; 260 } 261 262 @Override getCondition()263 protected CanonicalCondition getCondition() { 264 return LT; 265 } 266 267 @Override createNode(ValueNode x, ValueNode y)268 protected IntegerLowerThanNode createNode(ValueNode x, ValueNode y) { 269 return new IntegerLessThanNode(x, y); 270 } 271 272 @Override upperBound(IntegerStamp stamp)273 protected long upperBound(IntegerStamp stamp) { 274 return stamp.upperBound(); 275 } 276 277 @Override lowerBound(IntegerStamp stamp)278 protected long lowerBound(IntegerStamp stamp) { 279 return stamp.lowerBound(); 280 } 281 282 @Override compare(long a, long b)283 protected int compare(long a, long b) { 284 return Long.compare(a, b); 285 } 286 287 @Override min(long a, long b)288 protected long min(long a, long b) { 289 return Math.min(a, b); 290 } 291 292 @Override max(long a, long b)293 protected long max(long a, long b) { 294 return Math.max(a, b); 295 } 296 297 @Override cast(long a, int bits)298 protected long cast(long a, int bits) { 299 return CodeUtil.signExtend(a, bits); 300 } 301 302 @Override minValue(int bits)303 protected long minValue(int bits) { 304 return NumUtil.minValue(bits); 305 } 306 307 @Override maxValue(int bits)308 protected long maxValue(int bits) { 309 return NumUtil.maxValue(bits); 310 } 311 312 @Override forInteger(int bits, long min, long max)313 protected IntegerStamp forInteger(int bits, long min, long max) { 314 return StampFactory.forInteger(bits, cast(min, bits), cast(max, bits)); 315 } 316 } 317 } 318