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