1 /* 2 * Copyright (c) 2011, 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 package org.graalvm.compiler.nodes.calc; 24 25 import org.graalvm.compiler.core.common.calc.Condition; 26 import org.graalvm.compiler.core.common.type.FloatStamp; 27 import org.graalvm.compiler.core.common.type.IntegerStamp; 28 import org.graalvm.compiler.core.common.type.Stamp; 29 import org.graalvm.compiler.core.common.type.StampFactory; 30 import org.graalvm.compiler.debug.GraalError; 31 import org.graalvm.compiler.graph.IterableNodeType; 32 import org.graalvm.compiler.graph.NodeClass; 33 import org.graalvm.compiler.graph.spi.CanonicalizerTool; 34 import org.graalvm.compiler.nodeinfo.NodeInfo; 35 import org.graalvm.compiler.nodes.LogicConstantNode; 36 import org.graalvm.compiler.nodes.LogicNode; 37 import org.graalvm.compiler.nodes.ValueNode; 38 import org.graalvm.compiler.nodes.util.GraphUtil; 39 40 import jdk.vm.ci.code.CodeUtil; 41 import jdk.vm.ci.meta.Constant; 42 import jdk.vm.ci.meta.ConstantReflectionProvider; 43 import jdk.vm.ci.meta.JavaKind; 44 import jdk.vm.ci.meta.PrimitiveConstant; 45 import jdk.vm.ci.meta.TriState; 46 47 @NodeInfo(shortName = "<") 48 public final class IntegerLessThanNode extends CompareNode implements IterableNodeType { 49 public static final NodeClass<IntegerLessThanNode> TYPE = NodeClass.create(IntegerLessThanNode.class); 50 51 public IntegerLessThanNode(ValueNode x, ValueNode y) { 52 super(TYPE, Condition.LT, false, x, y); 53 assert !x.getStackKind().isNumericFloat() && x.getStackKind() != JavaKind.Object; 54 assert !y.getStackKind().isNumericFloat() && y.getStackKind() != JavaKind.Object; 55 } 56 57 public static LogicNode create(ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection) { 58 LogicNode result = CompareNode.tryConstantFold(Condition.LT, x, y, constantReflection, false); 59 if (result != null) { 60 return result; 61 } else { 62 result = findSynonym(x, y); 63 if (result != null) { 64 return result; 65 } 66 return new IntegerLessThanNode(x, y); 67 } 68 } 69 70 @Override 71 protected ValueNode optimizeNormalizeCmp(Constant constant, NormalizeCompareNode normalizeNode, boolean mirrored) { 72 PrimitiveConstant primitive = (PrimitiveConstant) constant; 73 assert condition() == Condition.LT; 74 if (primitive.getJavaKind() == JavaKind.Int && primitive.asInt() == 0) { 75 ValueNode a = mirrored ? normalizeNode.getY() : normalizeNode.getX(); 76 ValueNode b = mirrored ? normalizeNode.getX() : normalizeNode.getY(); 77 78 if (normalizeNode.getX().getStackKind() == JavaKind.Double || normalizeNode.getX().getStackKind() == JavaKind.Float) { 79 return new FloatLessThanNode(a, b, mirrored ^ normalizeNode.isUnorderedLess); 80 } else { 81 return new IntegerLessThanNode(a, b); 82 } 83 } 84 return this; 85 } 86 87 public static boolean subtractMayUnderflow(long x, long y, long minValue) { 88 long r = x - y; 89 // HD 2-12 Overflow iff the arguments have different signs and 90 // the sign of the result is different than the sign of x 91 return (((x ^ y) & (x ^ r)) < 0) || r <= minValue; 92 } 93 94 public static boolean subtractMayOverflow(long x, long y, long maxValue) { 95 long r = x - y; 96 // HD 2-12 Overflow iff the arguments have different signs and 97 // the sign of the result is different than the sign of x 98 return (((x ^ y) & (x ^ r)) < 0) || r > maxValue; 99 } 100 101 @Override 102 public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) { 103 ValueNode result = super.canonical(tool, forX, forY); 104 if (result != this) { 105 return result; 106 } 107 ValueNode synonym = findSynonym(forX, forY); 108 if (synonym != null) { 109 return synonym; 110 } 111 if (forX.stamp() instanceof IntegerStamp && forY.stamp() instanceof IntegerStamp) { 112 if (IntegerStamp.sameSign((IntegerStamp) forX.stamp(), (IntegerStamp) forY.stamp())) { 113 return new IntegerBelowNode(forX, forY); 114 } 115 } 116 if (forY.isConstant() && forY.asConstant().isDefaultForKind() && forX instanceof SubNode) { 117 // (x - y) < 0 when x - y is known not to underflow == x < y 118 SubNode sub = (SubNode) forX; 119 IntegerStamp xStamp = (IntegerStamp) sub.getX().stamp(); 120 IntegerStamp yStamp = (IntegerStamp) sub.getY().stamp(); 121 long minValue = CodeUtil.minValue(xStamp.getBits()); 122 long maxValue = CodeUtil.maxValue(xStamp.getBits()); 123 124 if (!subtractMayUnderflow(xStamp.lowerBound(), yStamp.upperBound(), minValue) && !subtractMayOverflow(xStamp.upperBound(), yStamp.lowerBound(), maxValue)) { 125 return new IntegerLessThanNode(sub.getX(), sub.getY()); 126 } 127 } 128 return this; 129 } 130 131 private static LogicNode findSynonym(ValueNode forX, ValueNode forY) { 132 if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) { 133 return LogicConstantNode.contradiction(); 134 } else if (forX.stamp() instanceof IntegerStamp && forY.stamp() instanceof IntegerStamp) { 135 IntegerStamp xStamp = (IntegerStamp) forX.stamp(); 136 IntegerStamp yStamp = (IntegerStamp) forY.stamp(); 137 if (xStamp.upperBound() < yStamp.lowerBound()) { 138 return LogicConstantNode.tautology(); 139 } else if (xStamp.lowerBound() >= yStamp.upperBound()) { 140 return LogicConstantNode.contradiction(); 141 } 142 } 143 return null; 144 } 145 146 @Override 147 protected CompareNode duplicateModified(ValueNode newX, ValueNode newY) { 148 if (newX.stamp() instanceof FloatStamp && newY.stamp() instanceof FloatStamp) { 149 return new FloatLessThanNode(newX, newY, true); 150 } else if (newX.stamp() instanceof IntegerStamp && newY.stamp() instanceof IntegerStamp) { 151 return new IntegerLessThanNode(newX, newY); 152 } 153 throw GraalError.shouldNotReachHere(); 154 } 155 156 @Override 157 public Stamp getSucceedingStampForX(boolean negated) { 158 Stamp xStampGeneric = getX().stamp(); 159 Stamp yStampGeneric = getY().stamp(); 160 if (xStampGeneric instanceof IntegerStamp) { 161 IntegerStamp xStamp = (IntegerStamp) xStampGeneric; 162 int bits = xStamp.getBits(); 163 if (yStampGeneric instanceof IntegerStamp) { 164 IntegerStamp yStamp = (IntegerStamp) yStampGeneric; 165 assert yStamp.getBits() == bits; 166 if (negated) { 167 // x >= y 168 long xLowerBound = xStamp.lowerBound(); 169 long yLowerBound = yStamp.lowerBound(); 170 if (yLowerBound > xLowerBound) { 171 return StampFactory.forIntegerWithMask(bits, yLowerBound, xStamp.upperBound(), xStamp); 172 } 173 } else { 174 // x < y 175 long xUpperBound = xStamp.upperBound(); 176 long yUpperBound = yStamp.upperBound(); 177 if (yUpperBound == CodeUtil.minValue(bits)) { 178 return null; 179 } else if (yUpperBound <= xUpperBound) { 180 assert yUpperBound != CodeUtil.minValue(bits); 181 return StampFactory.forIntegerWithMask(bits, xStamp.lowerBound(), yUpperBound - 1, xStamp); 182 } 183 } 184 } 185 } 186 return null; 187 } 188 189 @Override 190 public Stamp getSucceedingStampForY(boolean negated) { 191 Stamp xStampGeneric = getX().stamp(); 192 Stamp yStampGeneric = getY().stamp(); 193 if (xStampGeneric instanceof IntegerStamp) { 194 IntegerStamp xStamp = (IntegerStamp) xStampGeneric; 195 int bits = xStamp.getBits(); 196 if (yStampGeneric instanceof IntegerStamp) { 197 IntegerStamp yStamp = (IntegerStamp) yStampGeneric; 198 assert yStamp.getBits() == bits; 199 if (negated) { 200 // y <= x 201 long xUpperBound = xStamp.upperBound(); 202 long yUpperBound = yStamp.upperBound(); 203 if (xUpperBound < yUpperBound) { 204 return StampFactory.forIntegerWithMask(bits, yStamp.lowerBound(), xUpperBound, yStamp); 205 } 206 } else { 207 // y > x 208 long xLowerBound = xStamp.lowerBound(); 209 long yLowerBound = yStamp.lowerBound(); 210 if (xLowerBound == CodeUtil.maxValue(bits)) { 211 return null; 212 } else if (xLowerBound >= yLowerBound) { 213 assert xLowerBound != CodeUtil.maxValue(bits); 214 return StampFactory.forIntegerWithMask(bits, xLowerBound + 1, yStamp.upperBound(), yStamp); 215 } 216 } 217 } 218 } 219 return null; 220 } 221 222 @Override 223 public TriState tryFold(Stamp xStampGeneric, Stamp yStampGeneric) { 224 if (xStampGeneric instanceof IntegerStamp && yStampGeneric instanceof IntegerStamp) { 225 IntegerStamp xStamp = (IntegerStamp) xStampGeneric; 226 IntegerStamp yStamp = (IntegerStamp) yStampGeneric; 227 if (xStamp.upperBound() < yStamp.lowerBound()) { 228 return TriState.TRUE; 229 } 230 if (xStamp.lowerBound() >= yStamp.upperBound()) { 231 return TriState.FALSE; 232 } 233 } 234 return TriState.UNKNOWN; 235 } 236 }