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 /* TODO (thomaswue/gdub) For high-level optimization purpose the compare node should be a boolean *value* (it is currently only a helper node) 49 * But in the back-end the comparison should not always be materialized (for example in x86 the comparison result will not be in a register but in a flag) 50 * 51 * Compare should probably be made a value (so that it can be canonicalized for example) and in later stages some Compare usage should be transformed 52 * into variants that do not materialize the value (CompareIf, CompareGuard...) 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 Condition 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, Condition 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 Condition 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 private ValueNode optimizeConditional(Constant constant, ConditionalNode conditionalNode, ConstantReflectionProvider constantReflection, Condition cond) { 92 Constant trueConstant = conditionalNode.trueValue().asConstant(); 93 Constant falseConstant = conditionalNode.falseValue().asConstant(); 94 95 if (falseConstant != null && trueConstant != null && constantReflection != null) { 96 boolean trueResult = cond.foldCondition(trueConstant, constant, constantReflection, unorderedIsTrue()); 97 boolean falseResult = cond.foldCondition(falseConstant, constant, constantReflection, unorderedIsTrue()); 98 99 if (trueResult == falseResult) { 100 return LogicConstantNode.forBoolean(trueResult); 101 } else { 102 if (trueResult) { 103 assert falseResult == false; 104 return conditionalNode.condition(); 105 } else { 106 assert falseResult == true; 107 return LogicNegationNode.create(conditionalNode.condition()); 108 109 } 110 } 111 } 112 return this; 113 } 114 115 protected ValueNode optimizeNormalizeCmp(Constant constant, NormalizeCompareNode normalizeNode, boolean mirrored) { 116 throw new GraalError("NormalizeCompareNode connected to %s (%s %s %s)", this, constant, normalizeNode, mirrored); 117 } 118 119 @Override 120 public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) { 121 ConstantReflectionProvider constantReflection = tool.getConstantReflection(); 122 LogicNode constantCondition = tryConstantFold(condition(), forX, forY, constantReflection, unorderedIsTrue()); 123 if (constantCondition != null) { 124 return constantCondition; 125 } 126 ValueNode result; 127 if (forX.isConstant()) { 128 if ((result = canonicalizeSymmetricConstant(tool, forX.asConstant(), forY, true)) != this) { 129 return result; 130 } 131 } else if (forY.isConstant()) { 132 if ((result = canonicalizeSymmetricConstant(tool, forY.asConstant(), forX, false)) != this) { 133 return result; 134 } 135 } else if (forX instanceof ConvertNode && forY instanceof ConvertNode) { 136 ConvertNode convertX = (ConvertNode) forX; 137 ConvertNode convertY = (ConvertNode) forY; 138 if (convertX.preservesOrder(condition()) && convertY.preservesOrder(condition()) && convertX.getValue().stamp().isCompatible(convertY.getValue().stamp())) { 139 boolean supported = true; 140 if (convertX.getValue().stamp() instanceof IntegerStamp) { 141 IntegerStamp intStamp = (IntegerStamp) convertX.getValue().stamp(); 142 supported = tool.supportSubwordCompare(intStamp.getBits()); 143 } 144 145 if (supported) { 146 boolean multiUsage = (convertX.asNode().getUsageCount() > 1 || convertY.asNode().getUsageCount() > 1); 147 if ((forX instanceof ZeroExtendNode || forX instanceof SignExtendNode) && multiUsage) { 148 // Do not perform for zero or sign extend if there are multiple usages of 149 // the value. 150 return this; 151 } 152 return duplicateModified(convertX.getValue(), convertY.getValue()); 153 } 154 } 155 } 156 return this; 157 } 158 159 public static LogicNode tryConstantFold(Condition condition, ValueNode forX, ValueNode forY, ConstantReflectionProvider constantReflection, boolean unorderedIsTrue) { 160 if (forX.isConstant() && forY.isConstant() && constantReflection != null) { 161 return LogicConstantNode.forBoolean(condition.foldCondition(forX.asConstant(), forY.asConstant(), constantReflection, unorderedIsTrue)); 162 } 163 return null; 164 } 165 166 /** 167 * Does this operation represent an identity check such that for x == y, x is exactly the same 168 * thing as y. This is generally true except for some floating point comparisons. 169 * 170 * @return true for identity comparisons 171 */ 172 public boolean isIdentityComparison() { 173 return condition == Condition.EQ; 174 } 175 176 protected abstract LogicNode duplicateModified(ValueNode newX, ValueNode newY); 177 178 protected ValueNode canonicalizeSymmetricConstant(CanonicalizerTool tool, Constant constant, ValueNode nonConstant, boolean mirrored) { 179 if (nonConstant instanceof ConditionalNode) { 180 return optimizeConditional(constant, (ConditionalNode) nonConstant, tool.getConstantReflection(), mirrored ? condition().mirror() : condition()); 181 } else if (nonConstant instanceof NormalizeCompareNode) { 182 return optimizeNormalizeCmp(constant, (NormalizeCompareNode) nonConstant, mirrored); 183 } else if (nonConstant instanceof ConvertNode) { 184 ConvertNode convert = (ConvertNode) nonConstant; 185 boolean multiUsage = (convert.asNode().getUsageCount() > 1 && convert.getValue().getUsageCount() == 1); 186 if ((convert instanceof ZeroExtendNode || convert instanceof SignExtendNode) && multiUsage) { 187 // Do not perform for zero or sign extend if it could introduce 188 // new live values. 189 return this; 190 } 191 192 boolean supported = true; 193 if (convert.getValue().stamp() instanceof IntegerStamp) { 194 IntegerStamp intStamp = (IntegerStamp) convert.getValue().stamp(); 195 supported = tool.supportSubwordCompare(intStamp.getBits()); 196 } 197 198 if (supported) { 199 ConstantNode newConstant = canonicalConvertConstant(tool, convert, constant); 200 if (newConstant != null) { 201 if (mirrored) { 202 return duplicateModified(newConstant, convert.getValue()); 203 } else { 204 return duplicateModified(convert.getValue(), newConstant); 205 } 206 } 207 } 208 } 209 return this; 210 } 211 212 private ConstantNode canonicalConvertConstant(CanonicalizerTool tool, ConvertNode convert, Constant constant) { 213 ConstantReflectionProvider constantReflection = tool.getConstantReflection(); 214 if (convert.preservesOrder(condition(), constant, constantReflection)) { 215 Constant reverseConverted = convert.reverse(constant, constantReflection); 216 if (reverseConverted != null && convert.convert(reverseConverted, constantReflection).equals(constant)) { 217 if (GeneratePIC.getValue()) { 218 // We always want uncompressed constants 219 return null; 220 } 221 return ConstantNode.forConstant(convert.getValue().stamp(), reverseConverted, tool.getMetaAccess()); 222 } 223 } 224 return null; 225 } 226 227 public static LogicNode createCompareNode(StructuredGraph graph, Condition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection) { 228 LogicNode result = createCompareNode(condition, x, y, constantReflection); 229 return (result.graph() == null ? graph.unique(result) : result); 230 } 231 232 public static LogicNode createCompareNode(Condition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection) { 233 assert x.getStackKind() == y.getStackKind(); 234 assert condition.isCanonical() : "condition is not canonical: " + condition; 235 assert !x.getStackKind().isNumericFloat(); 236 237 LogicNode comparison; 238 if (condition == Condition.EQ) { 239 if (x.stamp() instanceof AbstractObjectStamp) { 240 comparison = ObjectEqualsNode.create(x, y, constantReflection); 241 } else if (x.stamp() instanceof AbstractPointerStamp) { 242 comparison = PointerEqualsNode.create(x, y); 243 } else { 244 assert x.getStackKind().isNumericInteger(); 245 comparison = IntegerEqualsNode.create(x, y, constantReflection); 246 } 247 } else if (condition == Condition.LT) { 248 assert x.getStackKind().isNumericInteger(); 249 comparison = IntegerLessThanNode.create(x, y, constantReflection); 250 } else { 251 assert condition == Condition.BT; 252 assert x.getStackKind().isNumericInteger(); 253 comparison = IntegerBelowNode.create(x, y, constantReflection); 254 } 255 256 return comparison; 257 } 258 }