1 /* 2 * Copyright (c) 2011, 2016, 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.GraalOptions.GeneratePIC; 26 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_1; 27 28 import org.graalvm.compiler.core.common.calc.Condition; 29 import org.graalvm.compiler.core.common.type.AbstractObjectStamp; 30 import org.graalvm.compiler.core.common.type.AbstractPointerStamp; 31 import org.graalvm.compiler.core.common.type.IntegerStamp; 32 import org.graalvm.compiler.debug.GraalError; 33 import org.graalvm.compiler.graph.NodeClass; 34 import org.graalvm.compiler.graph.spi.Canonicalizable; 35 import org.graalvm.compiler.graph.spi.CanonicalizerTool; 36 import org.graalvm.compiler.nodeinfo.NodeInfo; 37 import org.graalvm.compiler.nodes.BinaryOpLogicNode; 38 import org.graalvm.compiler.nodes.ConstantNode; 39 import org.graalvm.compiler.nodes.LogicConstantNode; 40 import org.graalvm.compiler.nodes.LogicNegationNode; 41 import org.graalvm.compiler.nodes.LogicNode; 42 import org.graalvm.compiler.nodes.StructuredGraph; 43 import org.graalvm.compiler.nodes.ValueNode; 44 45 import jdk.vm.ci.meta.Constant; 46 import jdk.vm.ci.meta.ConstantReflectionProvider; 47 48 @NodeInfo(cycles = CYCLES_1) 49 public abstract class CompareNode extends BinaryOpLogicNode implements Canonicalizable.Binary<ValueNode> { 50 51 public static final NodeClass<CompareNode> TYPE = NodeClass.create(CompareNode.class); 52 protected final Condition condition; 53 protected final boolean unorderedIsTrue; 54 55 /** 56 * Constructs a new Compare instruction. 57 * 58 * @param x the instruction producing the first input to the instruction 59 * @param y the instruction that produces the second input to this instruction 60 */ 61 protected CompareNode(NodeClass<? extends CompareNode> c, Condition condition, boolean unorderedIsTrue, ValueNode x, ValueNode y) { 62 super(c, x, y); 63 this.condition = condition; 64 this.unorderedIsTrue = unorderedIsTrue; 65 } 66 67 /** 68 * Gets the condition (comparison operation) for this instruction. 69 * 70 * @return the condition 71 */ 72 public final Condition condition() { 73 return condition; 74 } 75 76 /** 77 * Checks whether unordered inputs mean true or false (only applies to float operations). 78 * 79 * @return {@code true} if unordered inputs produce true 80 */ 81 public final boolean unorderedIsTrue() { 82 return this.unorderedIsTrue; 83 } 84 85 private ValueNode optimizeConditional(Constant constant, ConditionalNode conditionalNode, ConstantReflectionProvider constantReflection, Condition cond) { 86 Constant trueConstant = conditionalNode.trueValue().asConstant(); 87 Constant falseConstant = conditionalNode.falseValue().asConstant(); 88 89 if (falseConstant != null && trueConstant != null && constantReflection != null) { 90 boolean trueResult = cond.foldCondition(trueConstant, constant, constantReflection, unorderedIsTrue()); 91 boolean falseResult = cond.foldCondition(falseConstant, constant, constantReflection, unorderedIsTrue()); 92 93 if (trueResult == falseResult) { 94 return LogicConstantNode.forBoolean(trueResult); 95 } else { 96 if (trueResult) { 97 assert falseResult == false; 98 return conditionalNode.condition(); 99 } else { 100 assert falseResult == true; 101 return LogicNegationNode.create(conditionalNode.condition()); 102 103 } 104 } 105 } 106 return this; 107 } 108 109 protected ValueNode optimizeNormalizeCmp(Constant constant, NormalizeCompareNode normalizeNode, boolean mirrored) { 110 throw new GraalError("NormalizeCompareNode connected to %s (%s %s %s)", this, constant, normalizeNode, mirrored); 111 } 112 113 @Override 114 public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) { 115 ConstantReflectionProvider constantReflection = tool.getConstantReflection(); 116 LogicNode constantCondition = tryConstantFold(condition(), forX, forY, constantReflection, unorderedIsTrue()); 117 if (constantCondition != null) { 118 return constantCondition; 119 } 120 ValueNode result; 121 if (forX.isConstant()) { 122 if ((result = canonicalizeSymmetricConstant(tool, forX.asConstant(), forY, true)) != this) { 123 return result; 124 } 125 } else if (forY.isConstant()) { 126 if ((result = canonicalizeSymmetricConstant(tool, forY.asConstant(), forX, false)) != this) { 127 return result; 128 } 129 } else if (forX instanceof ConvertNode && forY instanceof ConvertNode) { 130 ConvertNode convertX = (ConvertNode) forX; 131 ConvertNode convertY = (ConvertNode) forY; 132 if (convertX.preservesOrder(condition()) && convertY.preservesOrder(condition()) && convertX.getValue().stamp().isCompatible(convertY.getValue().stamp())) { 133 boolean supported = true; 134 if (convertX.getValue().stamp() instanceof IntegerStamp) { 135 IntegerStamp intStamp = (IntegerStamp) convertX.getValue().stamp(); 136 supported = tool.supportSubwordCompare(intStamp.getBits()); 137 } 138 139 if (supported) { 140 boolean multiUsage = (convertX.asNode().hasMoreThanOneUsage() || convertY.asNode().hasMoreThanOneUsage()); 141 if ((forX instanceof ZeroExtendNode || forX instanceof SignExtendNode) && multiUsage) { 142 // Do not perform for zero or sign extend if there are multiple usages of 143 // the value. 144 return this; 145 } 146 return duplicateModified(convertX.getValue(), convertY.getValue()); 147 } 148 } 149 } 150 return this; 151 } 152 153 public static LogicNode tryConstantFold(Condition condition, ValueNode forX, ValueNode forY, ConstantReflectionProvider constantReflection, boolean unorderedIsTrue) { 154 if (forX.isConstant() && forY.isConstant() && constantReflection != null) { 155 return LogicConstantNode.forBoolean(condition.foldCondition(forX.asConstant(), forY.asConstant(), constantReflection, unorderedIsTrue)); 156 } 157 return null; 158 } 159 160 /** 161 * Does this operation represent an identity check such that for x == y, x is exactly the same 162 * thing as y. This is generally true except for some floating point comparisons. 163 * 164 * @return true for identity comparisons 165 */ 166 public boolean isIdentityComparison() { 167 return condition == Condition.EQ; 168 } 169 170 protected abstract LogicNode duplicateModified(ValueNode newX, ValueNode newY); 171 172 protected ValueNode canonicalizeSymmetricConstant(CanonicalizerTool tool, Constant constant, ValueNode nonConstant, boolean mirrored) { 173 if (nonConstant instanceof ConditionalNode) { 174 return optimizeConditional(constant, (ConditionalNode) nonConstant, tool.getConstantReflection(), mirrored ? condition().mirror() : condition()); 175 } else if (nonConstant instanceof NormalizeCompareNode) { 176 return optimizeNormalizeCmp(constant, (NormalizeCompareNode) nonConstant, mirrored); 177 } else if (nonConstant instanceof ConvertNode) { 178 ConvertNode convert = (ConvertNode) nonConstant; 179 boolean multiUsage = (convert.asNode().hasMoreThanOneUsage() && convert.getValue().hasExactlyOneUsage()); 180 if ((convert instanceof ZeroExtendNode || convert instanceof SignExtendNode) && multiUsage) { 181 // Do not perform for zero or sign extend if it could introduce 182 // new live values. 183 return this; 184 } 185 186 boolean supported = true; 187 if (convert.getValue().stamp() instanceof IntegerStamp) { 188 IntegerStamp intStamp = (IntegerStamp) convert.getValue().stamp(); 189 supported = tool.supportSubwordCompare(intStamp.getBits()); 190 } 191 192 if (supported) { 193 ConstantNode newConstant = canonicalConvertConstant(tool, convert, constant); 194 if (newConstant != null) { 195 if (mirrored) { 196 return duplicateModified(newConstant, convert.getValue()); 197 } else { 198 return duplicateModified(convert.getValue(), newConstant); 199 } 200 } 201 } 202 } 203 204 return this; 205 } 206 207 private ConstantNode canonicalConvertConstant(CanonicalizerTool tool, ConvertNode convert, Constant constant) { 208 ConstantReflectionProvider constantReflection = tool.getConstantReflection(); 209 if (convert.preservesOrder(condition(), constant, constantReflection)) { 210 Constant reverseConverted = convert.reverse(constant, constantReflection); 211 if (reverseConverted != null && convert.convert(reverseConverted, constantReflection).equals(constant)) { 212 if (GeneratePIC.getValue(tool.getOptions())) { 213 // We always want uncompressed constants 214 return null; 215 } 216 return ConstantNode.forConstant(convert.getValue().stamp(), reverseConverted, tool.getMetaAccess()); 217 } 218 } 219 return null; 220 } 221 222 public static LogicNode createCompareNode(StructuredGraph graph, Condition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection) { 223 LogicNode result = createCompareNode(condition, x, y, constantReflection); 224 return (result.graph() == null ? graph.unique(result) : result); 225 } 226 227 public static LogicNode createCompareNode(Condition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection) { 228 assert x.getStackKind() == y.getStackKind(); 229 assert condition.isCanonical(); 230 assert !x.getStackKind().isNumericFloat(); 231 232 LogicNode comparison; 233 if (condition == Condition.EQ) { 234 if (x.stamp() instanceof AbstractObjectStamp) { 235 comparison = ObjectEqualsNode.create(x, y, constantReflection); 236 } else if (x.stamp() instanceof AbstractPointerStamp) { 237 comparison = PointerEqualsNode.create(x, y); 238 } else { 239 assert x.getStackKind().isNumericInteger(); 240 comparison = IntegerEqualsNode.create(x, y, constantReflection); 241 } 242 } else if (condition == Condition.LT) { 243 assert x.getStackKind().isNumericInteger(); 244 comparison = IntegerLessThanNode.create(x, y, constantReflection); 245 } else { 246 assert condition == Condition.BT; 247 assert x.getStackKind().isNumericInteger(); 248 comparison = IntegerBelowNode.create(x, y, constantReflection); 249 } 250 251 return comparison; 252 } 253 }