1 /* 2 * Copyright (c) 2011, 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.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.JavaKind; 51 import jdk.vm.ci.meta.MetaAccessProvider; 52 import jdk.vm.ci.meta.PrimitiveConstant; 53 import jdk.vm.ci.meta.TriState; 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, AbstractNormalizeCompareNode normalizeNode, boolean mirrored, NodeView view)116 protected LogicNode optimizeNormalizeCompare(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, 117 Constant constant, AbstractNormalizeCompareNode 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 long cst = mirrored ? -primitive.asLong() : primitive.asLong(); 140 141 if (cst == 0) { 142 return normalizeNode.createLowerComparison(mirrored, constantReflection, metaAccess, options, smallestCompareWidth, view); 143 } else if (cst == 1) { 144 // a <= b <=> !(a > b) 145 // since we negate, we have to reverse the unordered result 146 LogicNode compare = normalizeNode.createLowerComparison(!mirrored, constantReflection, metaAccess, options, smallestCompareWidth, view); 147 return LogicNegationNode.create(compare); 148 } else if (cst <= -1) { 149 return LogicConstantNode.contradiction(); 150 } else { 151 assert cst >= 2; 152 return LogicConstantNode.tautology(); 153 } 154 } 155 156 @Override findSynonym(ValueNode forX, ValueNode forY, NodeView view)157 protected LogicNode findSynonym(ValueNode forX, ValueNode forY, NodeView view) { 158 LogicNode result = super.findSynonym(forX, forY, view); 159 if (result != null) { 160 return result; 161 } 162 if (forX.stamp(view) instanceof IntegerStamp && forY.stamp(view) instanceof IntegerStamp) { 163 if (IntegerStamp.sameSign((IntegerStamp) forX.stamp(view), (IntegerStamp) forY.stamp(view))) { 164 return new IntegerBelowNode(forX, forY); 165 } 166 } 167 168 // Attempt to optimize the case where we can fold a constant from the left side (either 169 // from an add or sub) into the constant on the right side. 170 if (forY.isConstant()) { 171 if (forX instanceof SubNode) { 172 SubNode sub = (SubNode) forX; 173 ValueNode xx = null; 174 ValueNode yy = null; 175 boolean negate = false; 176 if (forY.asConstant().isDefaultForKind()) { 177 // (x - y) < 0 when x - y is known not to underflow <=> x < y 178 xx = sub.getX(); 179 yy = sub.getY(); 180 } else if (forY.isJavaConstant() && forY.asJavaConstant().asLong() == 1) { 181 // (x - y) < 1 when x - y is known not to underflow <=> !(y < x) 182 xx = sub.getY(); 183 yy = sub.getX(); 184 negate = true; 185 } 186 if (xx != null) { 187 assert yy != null; 188 IntegerStamp xStamp = (IntegerStamp) sub.getX().stamp(view); 189 IntegerStamp yStamp = (IntegerStamp) sub.getY().stamp(view); 190 long minValue = CodeUtil.minValue(xStamp.getBits()); 191 long maxValue = CodeUtil.maxValue(xStamp.getBits()); 192 193 if (!subtractMayUnderflow(xStamp.lowerBound(), yStamp.upperBound(), minValue) && !subtractMayOverflow(xStamp.upperBound(), yStamp.lowerBound(), maxValue)) { 194 LogicNode logic = new IntegerLessThanNode(xx, yy); 195 if (negate) { 196 logic = LogicNegationNode.create(logic); 197 } 198 return logic; 199 } 200 } 201 } else if (forX instanceof AddNode) { 202 203 // (x + xConstant) < forY => x < (forY - xConstant) 204 AddNode addNode = (AddNode) forX; 205 if (addNode.getY().isJavaConstant()) { 206 IntegerStamp xStamp = (IntegerStamp) addNode.getX().stamp(view); 207 if (!IntegerStamp.addCanOverflow(xStamp, (IntegerStamp) addNode.getY().stamp(view))) { 208 long minValue = CodeUtil.minValue(xStamp.getBits()); 209 long maxValue = CodeUtil.maxValue(xStamp.getBits()); 210 long yConstant = forY.asJavaConstant().asLong(); 211 long xConstant = addNode.getY().asJavaConstant().asLong(); 212 if (!subtractMayUnderflow(yConstant, xConstant, minValue) && !subtractMayOverflow(yConstant, xConstant, maxValue)) { 213 long newConstant = yConstant - xConstant; 214 return IntegerLessThanNode.create(addNode.getX(), ConstantNode.forIntegerStamp(xStamp, newConstant), view); 215 } 216 } 217 } 218 } 219 } 220 221 if (forX.stamp(view) instanceof IntegerStamp) { 222 assert forY.stamp(view) instanceof IntegerStamp; 223 int bits = ((IntegerStamp) forX.stamp(view)).getBits(); 224 assert ((IntegerStamp) forY.stamp(view)).getBits() == bits; 225 LogicNode logic = canonicalizeRangeFlip(forX, forY, bits, true, view); 226 if (logic != null) { 227 return logic; 228 } 229 } 230 return null; 231 } 232 233 @Override getCondition()234 protected CanonicalCondition getCondition() { 235 return LT; 236 } 237 238 @Override createNode(ValueNode x, ValueNode y)239 protected IntegerLowerThanNode createNode(ValueNode x, ValueNode y) { 240 return new IntegerLessThanNode(x, y); 241 } 242 243 @Override upperBound(IntegerStamp stamp)244 protected long upperBound(IntegerStamp stamp) { 245 return stamp.upperBound(); 246 } 247 248 @Override lowerBound(IntegerStamp stamp)249 protected long lowerBound(IntegerStamp stamp) { 250 return stamp.lowerBound(); 251 } 252 253 @Override compare(long a, long b)254 protected int compare(long a, long b) { 255 return Long.compare(a, b); 256 } 257 258 @Override min(long a, long b)259 protected long min(long a, long b) { 260 return Math.min(a, b); 261 } 262 263 @Override max(long a, long b)264 protected long max(long a, long b) { 265 return Math.max(a, b); 266 } 267 268 @Override cast(long a, int bits)269 protected long cast(long a, int bits) { 270 return CodeUtil.signExtend(a, bits); 271 } 272 273 @Override minValue(int bits)274 protected long minValue(int bits) { 275 return NumUtil.minValue(bits); 276 } 277 278 @Override maxValue(int bits)279 protected long maxValue(int bits) { 280 return NumUtil.maxValue(bits); 281 } 282 283 @Override forInteger(int bits, long min, long max)284 protected IntegerStamp forInteger(int bits, long min, long max) { 285 return StampFactory.forInteger(bits, cast(min, bits), cast(max, bits)); 286 } 287 } 288 289 @Override implies(boolean thisNegated, LogicNode other)290 public TriState implies(boolean thisNegated, LogicNode other) { 291 if (!thisNegated) { 292 if (other instanceof IntegerLessThanNode) { 293 ValueNode otherX = ((IntegerLessThanNode) other).getX(); 294 ValueNode otherY = ((IntegerLessThanNode) other).getY(); 295 // x < y => !y < x 296 if (getX() == otherY && getY() == otherX) { 297 return TriState.FALSE; 298 } 299 } 300 301 // x < y => !x == y 302 // x < y => !y == x 303 if (other instanceof IntegerEqualsNode) { 304 ValueNode otherX = ((IntegerEqualsNode) other).getX(); 305 ValueNode otherY = ((IntegerEqualsNode) other).getY(); 306 if ((getX() == otherX && getY() == otherY) || (getX() == otherY && getY() == otherX)) { 307 return TriState.FALSE; 308 } 309 } 310 } 311 return super.implies(thisNegated, other); 312 } 313 } 314