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 AbstractNormalizeCompareNode) {
188 return optimizeNormalizeCompare(constantReflection, metaAccess, options, smallestCompareWidth, constant, (AbstractNormalizeCompareNode) 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 IntegerConvertNode && multiUsage) {
193 // Do not perform for integer convers if it could introduce
194 // new live values.
195 return null;
196 }
197
198 if (convert instanceof NarrowNode) {
199 NarrowNode narrowNode = (NarrowNode) convert;
200 if (narrowNode.getInputBits() > 32 && !constant.isDefaultForKind()) {
201 // Avoid large integer constants.
202 return null;
203 }
204 }
205
206 boolean supported = true;
207 if (convert.getValue().stamp(view) instanceof IntegerStamp) {
208 IntegerStamp intStamp = (IntegerStamp) convert.getValue().stamp(view);
209 supported = smallestCompareWidth != null && intStamp.getBits() >= smallestCompareWidth;
210 }
211
212 if (supported) {
213 ConstantNode newConstant = canonicalConvertConstant(constantReflection, metaAccess, options, condition, convert, constant, view);
214 if (newConstant != null) {
215 if (mirrored) {
216 return duplicateModified(newConstant, convert.getValue(), unorderedIsTrue, view);
217 } else {
218 return duplicateModified(convert.getValue(), newConstant, unorderedIsTrue, view);
219 }
220 }
221 }
222 }
223
224 return null;
225 }
226
227 private static ConstantNode canonicalConvertConstant(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, CanonicalCondition condition,
228 ConvertNode convert, Constant constant, NodeView view) {
229 if (convert.preservesOrder(condition, constant, constantReflection)) {
230 Constant reverseConverted = convert.reverse(constant, constantReflection);
231 if (reverseConverted != null && convert.convert(reverseConverted, constantReflection).equals(constant)) {
232 if (GeneratePIC.getValue(options)) {
233 // We always want uncompressed constants
234 return null;
235 }
236 return ConstantNode.forConstant(convert.getValue().stamp(view), reverseConverted, metaAccess);
237 }
238 }
239 return null;
240 }
241
242 @SuppressWarnings("unused")
243 protected LogicNode optimizeNormalizeCompare(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth,
244 Constant constant, AbstractNormalizeCompareNode normalizeNode, boolean mirrored, NodeView view) {
245 throw new PermanentBailoutException("NormalizeCompareNode connected to %s (%s %s %s)", this, constant, normalizeNode, mirrored);
246 }
247
248 private static LogicNode optimizeConditional(Constant constant, ConditionalNode conditionalNode, ConstantReflectionProvider constantReflection, Condition cond, boolean unorderedIsTrue) {
249 Constant trueConstant = conditionalNode.trueValue().asConstant();
250 Constant falseConstant = conditionalNode.falseValue().asConstant();
251
252 if (falseConstant != null && trueConstant != null && constantReflection != null) {
253 boolean trueResult = cond.foldCondition(trueConstant, constant, constantReflection, unorderedIsTrue);
254 boolean falseResult = cond.foldCondition(falseConstant, constant, constantReflection, unorderedIsTrue);
255
256 if (trueResult == falseResult) {
257 return LogicConstantNode.forBoolean(trueResult);
258 } else {
259 if (trueResult) {
260 assert falseResult == false;
261 return conditionalNode.condition();
262 } else {
263 assert falseResult == true;
264 return LogicNegationNode.create(conditionalNode.condition());
265
266 }
267 }
268 }
269
270 return null;
271 }
272
273 protected abstract LogicNode duplicateModified(ValueNode newW, ValueNode newY, boolean unorderedIsTrue, NodeView view);
274 }
275
276 public static LogicNode createCompareNode(StructuredGraph graph, CanonicalCondition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection, NodeView view) {
277 LogicNode result = createCompareNode(condition, x, y, constantReflection, view);
278 return (result.graph() == null ? graph.addOrUniqueWithInputs(result) : result);
279 }
280
281 public static LogicNode createCompareNode(CanonicalCondition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection, NodeView view) {
282 assert x.getStackKind() == y.getStackKind();
283 assert !x.getStackKind().isNumericFloat();
284
285 LogicNode comparison;
286 if (condition == CanonicalCondition.EQ) {
287 if (x.stamp(view) instanceof AbstractObjectStamp) {
288 comparison = ObjectEqualsNode.create(x, y, constantReflection, view);
289 } else if (x.stamp(view) instanceof AbstractPointerStamp) {
290 comparison = PointerEqualsNode.create(x, y, view);
291 } else {
292 assert x.getStackKind().isNumericInteger();
293 comparison = IntegerEqualsNode.create(x, y, view);
294 }
295 } else if (condition == CanonicalCondition.LT) {
296 assert x.getStackKind().isNumericInteger();
297 comparison = IntegerLessThanNode.create(x, y, view);
298 } else {
299 assert condition == CanonicalCondition.BT;
300 assert x.getStackKind().isNumericInteger();
301 comparison = IntegerBelowNode.create(x, y, view);
302 }
303
304 return comparison;
305 }
306
307 public static LogicNode createCompareNode(StructuredGraph graph, ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth,
308 CanonicalCondition condition, ValueNode x, ValueNode y, NodeView view) {
309 LogicNode result = createCompareNode(constantReflection, metaAccess, options, smallestCompareWidth, condition, x, y, view);
310 return (result.graph() == null ? graph.addOrUniqueWithInputs(result) : result);
311 }
312
313 public static LogicNode createCompareNode(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth,
314 CanonicalCondition condition, ValueNode x, ValueNode y, NodeView view) {
315 assert x.getStackKind() == y.getStackKind();
316 assert !x.getStackKind().isNumericFloat();
317
318 LogicNode comparison;
319 if (condition == CanonicalCondition.EQ) {
320 if (x.stamp(view) instanceof AbstractObjectStamp) {
321 assert smallestCompareWidth == null;
322 comparison = ObjectEqualsNode.create(constantReflection, metaAccess, options, x, y, view);
323 } else if (x.stamp(view) instanceof AbstractPointerStamp) {
324 comparison = PointerEqualsNode.create(x, y, view);
325 } else {
326 assert x.getStackKind().isNumericInteger();
327 comparison = IntegerEqualsNode.create(constantReflection, metaAccess, options, smallestCompareWidth, x, y, view);
328 }
329 } else if (condition == CanonicalCondition.LT) {
330 assert x.getStackKind().isNumericInteger();
331 comparison = IntegerLessThanNode.create(constantReflection, metaAccess, options, smallestCompareWidth, x, y, view);
332 } else {
333 assert condition == CanonicalCondition.BT;
334 assert x.getStackKind().isNumericInteger();
335 comparison = IntegerBelowNode.create(constantReflection, metaAccess, options, smallestCompareWidth, x, y, view);
336 }
337
338 return comparison;
339 }
340 }