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
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 supported = smallestCompareWidth != null && intStamp.getBits() >= smallestCompareWidth;
140 }
141
142 if (supported) {
143 boolean multiUsage = (convertX.asNode().hasMoreThanOneUsage() || convertY.asNode().hasMoreThanOneUsage());
144 if ((forX instanceof ZeroExtendNode || forX instanceof SignExtendNode) && multiUsage) {
145 // Do not perform for zero or sign extend if there are multiple usages
146 // of the value.
147 return null;
148 }
149 return duplicateModified(convertX.getValue(), convertY.getValue(), unorderedIsTrue, view);
150 }
151 }
152 }
153 return null;
154 }
155
156 protected LogicNode canonicalizeSymmetricConstant(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth,
157 CanonicalCondition condition, Constant constant, ValueNode nonConstant, boolean mirrored, boolean unorderedIsTrue, NodeView view) {
158 if (nonConstant instanceof ConditionalNode) {
159 Condition realCondition = condition.asCondition();
160 if (mirrored) {
161 realCondition = realCondition.mirror();
162 }
163 return optimizeConditional(constant, (ConditionalNode) nonConstant, constantReflection, realCondition, unorderedIsTrue);
164 } else if (nonConstant instanceof NormalizeCompareNode) {
165 return optimizeNormalizeCompare(constantReflection, metaAccess, options, smallestCompareWidth, constant, (NormalizeCompareNode) nonConstant, mirrored, view);
166 } else if (nonConstant instanceof ConvertNode) {
167 ConvertNode convert = (ConvertNode) nonConstant;
168 boolean multiUsage = (convert.asNode().hasMoreThanOneUsage() && convert.getValue().hasExactlyOneUsage());
169 if ((convert instanceof ZeroExtendNode || convert instanceof SignExtendNode) && multiUsage) {
170 // Do not perform for zero or sign extend if it could introduce
171 // new live values.
172 return null;
173 }
174
175 boolean supported = true;
176 if (convert.getValue().stamp(view) instanceof IntegerStamp) {
177 IntegerStamp intStamp = (IntegerStamp) convert.getValue().stamp(view);
178 supported = smallestCompareWidth != null && intStamp.getBits() > smallestCompareWidth;
179 }
180
181 if (supported) {
182 ConstantNode newConstant = canonicalConvertConstant(constantReflection, metaAccess, options, condition, convert, constant, view);
183 if (newConstant != null) {
184 if (mirrored) {
185 return duplicateModified(newConstant, convert.getValue(), unorderedIsTrue, view);
186 } else {
187 return duplicateModified(convert.getValue(), newConstant, unorderedIsTrue, view);
188 }
189 }
190 }
191 }
192
193 return null;
194 }
195
196 private static ConstantNode canonicalConvertConstant(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, CanonicalCondition condition,
197 ConvertNode convert, Constant constant, NodeView view) {
198 if (convert.preservesOrder(condition, constant, constantReflection)) {
199 Constant reverseConverted = convert.reverse(constant, constantReflection);
200 if (reverseConverted != null && convert.convert(reverseConverted, constantReflection).equals(constant)) {
201 if (GeneratePIC.getValue(options)) {
202 // We always want uncompressed constants
203 return null;
204 }
205 return ConstantNode.forConstant(convert.getValue().stamp(view), reverseConverted, metaAccess);
206 }
207 }
208 return null;
209 }
210
211 @SuppressWarnings("unused")
212 protected LogicNode optimizeNormalizeCompare(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth,
213 Constant constant, NormalizeCompareNode normalizeNode, boolean mirrored, NodeView view) {
214 throw new PermanentBailoutException("NormalizeCompareNode connected to %s (%s %s %s)", this, constant, normalizeNode, mirrored);
215 }
216
217 private static LogicNode optimizeConditional(Constant constant, ConditionalNode conditionalNode, ConstantReflectionProvider constantReflection, Condition cond, boolean unorderedIsTrue) {
218 Constant trueConstant = conditionalNode.trueValue().asConstant();
219 Constant falseConstant = conditionalNode.falseValue().asConstant();
220
221 if (falseConstant != null && trueConstant != null && constantReflection != null) {
222 boolean trueResult = cond.foldCondition(trueConstant, constant, constantReflection, unorderedIsTrue);
223 boolean falseResult = cond.foldCondition(falseConstant, constant, constantReflection, unorderedIsTrue);
224
225 if (trueResult == falseResult) {
226 return LogicConstantNode.forBoolean(trueResult);
227 } else {
228 if (trueResult) {
229 assert falseResult == false;
230 return conditionalNode.condition();
231 } else {
232 assert falseResult == true;
233 return LogicNegationNode.create(conditionalNode.condition());
234
235 }
236 }
237 }
238
239 return null;
240 }
241
242 protected abstract LogicNode duplicateModified(ValueNode newW, ValueNode newY, boolean unorderedIsTrue, NodeView view);
243 }
244
245 public static LogicNode createCompareNode(StructuredGraph graph, CanonicalCondition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection, NodeView view) {
246 LogicNode result = createCompareNode(condition, x, y, constantReflection, view);
247 return (result.graph() == null ? graph.addOrUniqueWithInputs(result) : result);
248 }
249
250 public static LogicNode createCompareNode(CanonicalCondition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection, NodeView view) {
251 assert x.getStackKind() == y.getStackKind();
252 assert !x.getStackKind().isNumericFloat();
253
254 LogicNode comparison;
255 if (condition == CanonicalCondition.EQ) {
256 if (x.stamp(view) instanceof AbstractObjectStamp) {
257 comparison = ObjectEqualsNode.create(x, y, constantReflection, view);
258 } else if (x.stamp(view) instanceof AbstractPointerStamp) {
259 comparison = PointerEqualsNode.create(x, y, view);
260 } else {
261 assert x.getStackKind().isNumericInteger();
262 comparison = IntegerEqualsNode.create(x, y, view);
263 }
264 } else if (condition == CanonicalCondition.LT) {
265 assert x.getStackKind().isNumericInteger();
266 comparison = IntegerLessThanNode.create(x, y, view);
267 } else {
268 assert condition == CanonicalCondition.BT;
269 assert x.getStackKind().isNumericInteger();
270 comparison = IntegerBelowNode.create(x, y, view);
271 }
272
273 return comparison;
274 }
275
276 public static LogicNode createCompareNode(StructuredGraph graph, ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth,
277 CanonicalCondition condition, ValueNode x, ValueNode y, NodeView view) {
278 LogicNode result = createCompareNode(constantReflection, metaAccess, options, smallestCompareWidth, condition, x, y, view);
279 return (result.graph() == null ? graph.addOrUniqueWithInputs(result) : result);
280 }
281
282 public static LogicNode createCompareNode(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth,
283 CanonicalCondition condition, ValueNode x, ValueNode y, NodeView view) {
284 assert x.getStackKind() == y.getStackKind();
285 assert !x.getStackKind().isNumericFloat();
286
287 LogicNode comparison;
288 if (condition == CanonicalCondition.EQ) {
289 if (x.stamp(view) instanceof AbstractObjectStamp) {
290 assert smallestCompareWidth == null;
291 comparison = ObjectEqualsNode.create(constantReflection, metaAccess, options, x, y, view);
292 } else if (x.stamp(view) instanceof AbstractPointerStamp) {
293 comparison = PointerEqualsNode.create(x, y, view);
294 } else {
295 assert x.getStackKind().isNumericInteger();
296 comparison = IntegerEqualsNode.create(constantReflection, metaAccess, options, smallestCompareWidth, x, y, view);
297 }
298 } else if (condition == CanonicalCondition.LT) {
299 assert x.getStackKind().isNumericInteger();
300 comparison = IntegerLessThanNode.create(constantReflection, metaAccess, options, smallestCompareWidth, x, y, view);
301 } else {
302 assert condition == CanonicalCondition.BT;
303 assert x.getStackKind().isNumericInteger();
304 comparison = IntegerBelowNode.create(constantReflection, metaAccess, options, smallestCompareWidth, x, y, view);
305 }
306
307 return comparison;
308 }
309 }