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.GraalOptions.GeneratePIC; 28 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_1; 29 30 import org.graalvm.compiler.core.common.PermanentBailoutException; 31 import org.graalvm.compiler.core.common.calc.CanonicalCondition; 32 import org.graalvm.compiler.core.common.calc.Condition; 33 import org.graalvm.compiler.core.common.type.AbstractObjectStamp; 34 import org.graalvm.compiler.core.common.type.AbstractPointerStamp; 35 import org.graalvm.compiler.core.common.type.IntegerStamp; 36 import org.graalvm.compiler.graph.NodeClass; 37 import org.graalvm.compiler.graph.spi.Canonicalizable; 38 import org.graalvm.compiler.nodeinfo.NodeInfo; 39 import org.graalvm.compiler.nodes.BinaryOpLogicNode; 40 import org.graalvm.compiler.nodes.ConstantNode; 41 import org.graalvm.compiler.nodes.LogicConstantNode; 42 import org.graalvm.compiler.nodes.LogicNegationNode; 43 import org.graalvm.compiler.nodes.LogicNode; 44 import org.graalvm.compiler.nodes.NodeView; 45 import org.graalvm.compiler.nodes.StructuredGraph; 46 import org.graalvm.compiler.nodes.ValueNode; 47 import org.graalvm.compiler.options.OptionValues; 48 49 import jdk.vm.ci.meta.Constant; 50 import jdk.vm.ci.meta.ConstantReflectionProvider; 51 import jdk.vm.ci.meta.MetaAccessProvider; 52 import jdk.vm.ci.meta.PrimitiveConstant; 53 54 @NodeInfo(cycles = CYCLES_1) 55 public abstract class CompareNode extends BinaryOpLogicNode implements Canonicalizable.Binary<ValueNode> { 56 57 public static final NodeClass<CompareNode> TYPE = NodeClass.create(CompareNode.class); 58 protected final CanonicalCondition condition; 59 protected final boolean unorderedIsTrue; 60 61 /** 62 * Constructs a new Compare instruction. 63 * 64 * @param x the instruction producing the first input to the instruction 65 * @param y the instruction that produces the second input to this instruction 66 */ 67 protected CompareNode(NodeClass<? extends CompareNode> c, CanonicalCondition condition, boolean unorderedIsTrue, ValueNode x, ValueNode y) { 68 super(c, x, y); 69 this.condition = condition; 70 this.unorderedIsTrue = unorderedIsTrue; 71 } 72 73 /** 74 * Gets the condition (comparison operation) for this instruction. 75 * 76 * @return the condition 77 */ 78 public final CanonicalCondition condition() { 79 return condition; 80 } 81 82 /** 83 * Checks whether unordered inputs mean true or false (only applies to float operations). 84 * 85 * @return {@code true} if unordered inputs produce true 86 */ 87 public final boolean unorderedIsTrue() { 88 return this.unorderedIsTrue; 89 } 90 91 public static LogicNode tryConstantFold(CanonicalCondition condition, ValueNode forX, ValueNode forY, ConstantReflectionProvider constantReflection, boolean unorderedIsTrue) { 92 if (forX.isConstant() && forY.isConstant() && (constantReflection != null || forX.asConstant() instanceof PrimitiveConstant)) { 93 return LogicConstantNode.forBoolean(condition.foldCondition(forX.asConstant(), forY.asConstant(), constantReflection, unorderedIsTrue)); 94 } 95 return null; 96 } 97 98 @SuppressWarnings("unused") 99 public static LogicNode tryConstantFoldPrimitive(CanonicalCondition condition, ValueNode forX, ValueNode forY, boolean unorderedIsTrue, NodeView view) { 100 if (forX.asConstant() instanceof PrimitiveConstant && forY.asConstant() instanceof PrimitiveConstant) { 101 return LogicConstantNode.forBoolean(condition.foldCondition((PrimitiveConstant) forX.asConstant(), (PrimitiveConstant) forY.asConstant(), unorderedIsTrue)); 102 } 103 return null; 104 } 105 106 /** 107 * Does this operation represent an identity check such that for x == y, x is exactly the same 108 * thing as y. This is generally true except for some floating point comparisons. 109 * 110 * @return true for identity comparisons 111 */ 112 public boolean isIdentityComparison() { 113 return condition == CanonicalCondition.EQ; 114 } 115 116 public abstract static class CompareOp { 117 public LogicNode canonical(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, CanonicalCondition condition, 118 boolean unorderedIsTrue, ValueNode forX, ValueNode forY, NodeView view) { 119 LogicNode constantCondition = tryConstantFold(condition, forX, forY, constantReflection, unorderedIsTrue); 120 if (constantCondition != null) { 121 return constantCondition; 122 } 123 LogicNode result; 124 if (forX.isConstant()) { 125 if ((result = canonicalizeSymmetricConstant(constantReflection, metaAccess, options, smallestCompareWidth, condition, forX.asConstant(), forY, true, unorderedIsTrue, view)) != null) { 126 return result; 127 } 128 } else if (forY.isConstant()) { 129 if ((result = canonicalizeSymmetricConstant(constantReflection, metaAccess, options, smallestCompareWidth, condition, forY.asConstant(), forX, false, unorderedIsTrue, view)) != null) { 130 return result; 131 } 132 } else if (forX instanceof ConvertNode && forY instanceof ConvertNode) { 133 ConvertNode convertX = (ConvertNode) forX; 134 ConvertNode convertY = (ConvertNode) forY; 135 if (convertX.preservesOrder(condition) && convertY.preservesOrder(condition) && convertX.getValue().stamp(view).isCompatible(convertY.getValue().stamp(view))) { 136 boolean supported = true; 137 if (convertX.getValue().stamp(view) instanceof IntegerStamp) { 138 IntegerStamp intStamp = (IntegerStamp) convertX.getValue().stamp(view); 139 boolean isConversionCompatible = convertX.getClass() == convertY.getClass(); 140 supported = smallestCompareWidth != null && intStamp.getBits() >= smallestCompareWidth && isConversionCompatible; 141 } 142 143 if (supported) { 144 145 ValueNode xValue = convertX.getValue(); 146 ValueNode yValue = convertY.getValue(); 147 148 if (forX instanceof ZeroExtendNode || forX instanceof SignExtendNode) { 149 150 int introducedUsages = 0; 151 int eliminatedNodes = 0; 152 153 if (convertX.asNode().hasExactlyOneUsage()) { 154 eliminatedNodes++; 155 } else if (xValue.hasExactlyOneUsage()) { 156 introducedUsages++; 157 } 158 159 if (convertY.asNode().hasExactlyOneUsage()) { 160 eliminatedNodes++; 161 } else if (yValue.hasExactlyOneUsage()) { 162 introducedUsages++; 163 } 164 165 if (introducedUsages > eliminatedNodes) { 166 // Only perform the optimization if there is 167 // a good trade-off between introduced new usages and 168 // eliminated nodes. 169 return null; 170 } 171 } 172 return duplicateModified(convertX.getValue(), convertY.getValue(), unorderedIsTrue, view); 173 } 174 } 175 } 176 return null; 177 } 178 179 protected LogicNode canonicalizeSymmetricConstant(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, 180 CanonicalCondition condition, Constant constant, ValueNode nonConstant, boolean mirrored, boolean unorderedIsTrue, NodeView view) { 181 if (nonConstant instanceof ConditionalNode) { 182 Condition realCondition = condition.asCondition(); 183 if (mirrored) { 184 realCondition = realCondition.mirror(); 185 } 186 return optimizeConditional(constant, (ConditionalNode) nonConstant, constantReflection, realCondition, unorderedIsTrue); 187 } else if (nonConstant instanceof NormalizeCompareNode) { 188 return optimizeNormalizeCompare(constantReflection, metaAccess, options, smallestCompareWidth, constant, (NormalizeCompareNode) nonConstant, mirrored, view); 189 } else if (nonConstant instanceof ConvertNode) { 190 ConvertNode convert = (ConvertNode) nonConstant; 191 boolean multiUsage = (convert.asNode().hasMoreThanOneUsage() && convert.getValue().hasExactlyOneUsage()); 192 if ((convert instanceof ZeroExtendNode || convert instanceof SignExtendNode) && multiUsage) { 193 // Do not perform for zero or sign extend if it could introduce 194 // new live values. 195 return null; 196 } 197 198 boolean supported = true; 199 if (convert.getValue().stamp(view) instanceof IntegerStamp) { 200 IntegerStamp intStamp = (IntegerStamp) convert.getValue().stamp(view); 201 supported = smallestCompareWidth != null && intStamp.getBits() >= smallestCompareWidth; 202 } 203 204 if (supported) { 205 ConstantNode newConstant = canonicalConvertConstant(constantReflection, metaAccess, options, condition, convert, constant, view); 206 if (newConstant != null) { 207 if (mirrored) { 208 return duplicateModified(newConstant, convert.getValue(), unorderedIsTrue, view); 209 } else { 210 return duplicateModified(convert.getValue(), newConstant, unorderedIsTrue, view); 211 } 212 } 213 } 214 } 215 216 return null; 217 } 218 219 private static ConstantNode canonicalConvertConstant(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, CanonicalCondition condition, 220 ConvertNode convert, Constant constant, NodeView view) { 221 if (convert.preservesOrder(condition, constant, constantReflection)) { 222 Constant reverseConverted = convert.reverse(constant, constantReflection); 223 if (reverseConverted != null && convert.convert(reverseConverted, constantReflection).equals(constant)) { 224 if (GeneratePIC.getValue(options)) { 225 // We always want uncompressed constants 226 return null; 227 } 228 return ConstantNode.forConstant(convert.getValue().stamp(view), reverseConverted, metaAccess); 229 } 230 } 231 return null; 232 } 233 234 @SuppressWarnings("unused") 235 protected LogicNode optimizeNormalizeCompare(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, 236 Constant constant, NormalizeCompareNode normalizeNode, boolean mirrored, NodeView view) { 237 throw new PermanentBailoutException("NormalizeCompareNode connected to %s (%s %s %s)", this, constant, normalizeNode, mirrored); 238 } 239 240 private static LogicNode optimizeConditional(Constant constant, ConditionalNode conditionalNode, ConstantReflectionProvider constantReflection, Condition cond, boolean unorderedIsTrue) { 241 Constant trueConstant = conditionalNode.trueValue().asConstant(); 242 Constant falseConstant = conditionalNode.falseValue().asConstant(); 243 244 if (falseConstant != null && trueConstant != null && constantReflection != null) { 245 boolean trueResult = cond.foldCondition(trueConstant, constant, constantReflection, unorderedIsTrue); 246 boolean falseResult = cond.foldCondition(falseConstant, constant, constantReflection, unorderedIsTrue); 247 248 if (trueResult == falseResult) { 249 return LogicConstantNode.forBoolean(trueResult); 250 } else { 251 if (trueResult) { 252 assert falseResult == false; 253 return conditionalNode.condition(); 254 } else { 255 assert falseResult == true; 256 return LogicNegationNode.create(conditionalNode.condition()); 257 258 } 259 } 260 } 261 262 return null; 263 } 264 265 protected abstract LogicNode duplicateModified(ValueNode newW, ValueNode newY, boolean unorderedIsTrue, NodeView view); 266 } 267 268 public static LogicNode createCompareNode(StructuredGraph graph, CanonicalCondition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection, NodeView view) { 269 LogicNode result = createCompareNode(condition, x, y, constantReflection, view); 270 return (result.graph() == null ? graph.addOrUniqueWithInputs(result) : result); 271 } 272 273 public static LogicNode createCompareNode(CanonicalCondition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection, NodeView view) { 274 assert x.getStackKind() == y.getStackKind(); 275 assert !x.getStackKind().isNumericFloat(); 276 277 LogicNode comparison; 278 if (condition == CanonicalCondition.EQ) { 279 if (x.stamp(view) instanceof AbstractObjectStamp) { 280 comparison = ObjectEqualsNode.create(x, y, constantReflection, view); 281 } else if (x.stamp(view) instanceof AbstractPointerStamp) { 282 comparison = PointerEqualsNode.create(x, y, view); 283 } else { 284 assert x.getStackKind().isNumericInteger(); 285 comparison = IntegerEqualsNode.create(x, y, view); 286 } 287 } else if (condition == CanonicalCondition.LT) { 288 assert x.getStackKind().isNumericInteger(); 289 comparison = IntegerLessThanNode.create(x, y, view); 290 } else { 291 assert condition == CanonicalCondition.BT; 292 assert x.getStackKind().isNumericInteger(); 293 comparison = IntegerBelowNode.create(x, y, view); 294 } 295 296 return comparison; 297 } 298 299 public static LogicNode createCompareNode(StructuredGraph graph, ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, 300 CanonicalCondition condition, ValueNode x, ValueNode y, NodeView view) { 301 LogicNode result = createCompareNode(constantReflection, metaAccess, options, smallestCompareWidth, condition, x, y, view); 302 return (result.graph() == null ? graph.addOrUniqueWithInputs(result) : result); 303 } 304 305 public static LogicNode createCompareNode(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, 306 CanonicalCondition condition, ValueNode x, ValueNode y, NodeView view) { 307 assert x.getStackKind() == y.getStackKind(); 308 assert !x.getStackKind().isNumericFloat(); 309 310 LogicNode comparison; 311 if (condition == CanonicalCondition.EQ) { 312 if (x.stamp(view) instanceof AbstractObjectStamp) { 313 assert smallestCompareWidth == null; 314 comparison = ObjectEqualsNode.create(constantReflection, metaAccess, options, x, y, view); 315 } else if (x.stamp(view) instanceof AbstractPointerStamp) { 316 comparison = PointerEqualsNode.create(x, y, view); 317 } else { 318 assert x.getStackKind().isNumericInteger(); 319 comparison = IntegerEqualsNode.create(constantReflection, metaAccess, options, smallestCompareWidth, x, y, view); 320 } 321 } else if (condition == CanonicalCondition.LT) { 322 assert x.getStackKind().isNumericInteger(); 323 comparison = IntegerLessThanNode.create(constantReflection, metaAccess, options, smallestCompareWidth, x, y, view); 324 } else { 325 assert condition == CanonicalCondition.BT; 326 assert x.getStackKind().isNumericInteger(); 327 comparison = IntegerBelowNode.create(constantReflection, metaAccess, options, smallestCompareWidth, x, y, view); 328 } 329 330 return comparison; 331 } 332 }