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 /**
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 }
|
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 /**
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 }
|