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 }