1 /*
2 * Copyright (c) 2009, 2014, 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.nodeinfo.NodeCycles.CYCLES_0;
26 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_2;
27 import static org.graalvm.compiler.nodes.calc.CompareNode.createCompareNode;
28
29 import org.graalvm.compiler.core.common.calc.Condition;
30 import org.graalvm.compiler.core.common.type.IntegerStamp;
31 import org.graalvm.compiler.core.common.type.Stamp;
32 import org.graalvm.compiler.core.common.type.StampFactory;
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.InputType;
37 import org.graalvm.compiler.nodeinfo.NodeInfo;
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 import org.graalvm.compiler.nodes.spi.LIRLowerable;
45 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
46
47 import jdk.vm.ci.meta.JavaConstant;
48
49 /**
50 * The {@code ConditionalNode} class represents a comparison that yields one of two values. Note
51 * that these nodes are not built directly from the bytecode but are introduced by canonicalization.
52 */
53 @NodeInfo(cycles = CYCLES_0, size = SIZE_2)
54 public final class ConditionalNode extends FloatingNode implements Canonicalizable, LIRLowerable {
55
56 public static final NodeClass<ConditionalNode> TYPE = NodeClass.create(ConditionalNode.class);
57 @Input(InputType.Condition) LogicNode condition;
58 @Input ValueNode trueValue;
59 @Input ValueNode falseValue;
60
61 public LogicNode condition() {
62 return condition;
63 }
64
65 public ConditionalNode(LogicNode condition) {
66 this(condition, ConstantNode.forInt(1, condition.graph()), ConstantNode.forInt(0, condition.graph()));
67 }
68
69 public ConditionalNode(LogicNode condition, ValueNode trueValue, ValueNode falseValue) {
70 super(TYPE, trueValue.stamp().meet(falseValue.stamp()));
71 assert trueValue.stamp().isCompatible(falseValue.stamp());
72 this.condition = condition;
73 this.trueValue = trueValue;
74 this.falseValue = falseValue;
75 }
76
77 public static ValueNode create(LogicNode condition) {
78 return create(condition, ConstantNode.forInt(1, condition.graph()), ConstantNode.forInt(0, condition.graph()));
79 }
80
81 public static ValueNode create(LogicNode condition, ValueNode trueValue, ValueNode falseValue) {
82 ValueNode synonym = findSynonym(condition, trueValue, falseValue);
83 if (synonym != null) {
84 return synonym;
85 }
86 ValueNode result = canonicalizeConditional(condition, trueValue, falseValue, trueValue.stamp().meet(falseValue.stamp()));
87 if (result != null) {
88 return result;
89 }
90 return new ConditionalNode(condition, trueValue, falseValue);
91 }
92
93 @Override
94 public boolean inferStamp() {
95 Stamp valueStamp = trueValue.stamp().meet(falseValue.stamp());
96 if (condition instanceof IntegerLessThanNode) {
97 IntegerLessThanNode lessThan = (IntegerLessThanNode) condition;
98 if (lessThan.getX() == trueValue && lessThan.getY() == falseValue) {
99 // this encodes a min operation
100 JavaConstant constant = lessThan.getX().asJavaConstant();
101 if (constant == null) {
102 constant = lessThan.getY().asJavaConstant();
103 }
104 if (constant != null) {
105 IntegerStamp bounds = StampFactory.forInteger(constant.getJavaKind(), constant.getJavaKind().getMinValue(), constant.asLong());
106 valueStamp = valueStamp.join(bounds);
107 }
108 } else if (lessThan.getX() == falseValue && lessThan.getY() == trueValue) {
109 // this encodes a max operation
110 JavaConstant constant = lessThan.getX().asJavaConstant();
111 if (constant == null) {
112 constant = lessThan.getY().asJavaConstant();
113 }
114 if (constant != null) {
115 IntegerStamp bounds = StampFactory.forInteger(constant.getJavaKind(), constant.asLong(), constant.getJavaKind().getMaxValue());
116 valueStamp = valueStamp.join(bounds);
117 }
118 }
119
120 }
121 return updateStamp(valueStamp);
122 }
123
124 public ValueNode trueValue() {
125 return trueValue;
126 }
127
128 public ValueNode falseValue() {
129 return falseValue;
130 }
131
132 @Override
133 public ValueNode canonical(CanonicalizerTool tool) {
134 ValueNode synonym = findSynonym(condition, trueValue(), falseValue());
135 if (synonym != null) {
136 return synonym;
137 }
138
139 ValueNode result = canonicalizeConditional(condition, trueValue(), falseValue(), stamp);
140 if (result != null) {
141 return result;
142 }
143
144 return this;
145 }
146
147 public static ValueNode canonicalizeConditional(LogicNode condition, ValueNode trueValue, ValueNode falseValue, Stamp stamp) {
148 // this optimizes the case where a value from the range 0 - 1 is mapped to the range 0 - 1
149 if (trueValue.isConstant() && falseValue.isConstant() && trueValue.stamp() instanceof IntegerStamp && falseValue.stamp() instanceof IntegerStamp) {
150 long constTrueValue = trueValue.asJavaConstant().asLong();
151 long constFalseValue = falseValue.asJavaConstant().asLong();
152 if (condition instanceof IntegerEqualsNode) {
153 IntegerEqualsNode equals = (IntegerEqualsNode) condition;
154 if (equals.getY().isConstant() && equals.getX().stamp() instanceof IntegerStamp) {
155 IntegerStamp equalsXStamp = (IntegerStamp) equals.getX().stamp();
156 if (equalsXStamp.upMask() == 1) {
157 long equalsY = equals.getY().asJavaConstant().asLong();
158 if (equalsY == 0) {
159 if (constTrueValue == 0 && constFalseValue == 1) {
160 // return x when: x == 0 ? 0 : 1;
161 return IntegerConvertNode.convertUnsigned(equals.getX(), stamp);
162 } else if (constTrueValue == 1 && constFalseValue == 0) {
163 // negate a boolean value via xor
164 return IntegerConvertNode.convertUnsigned(XorNode.create(equals.getX(), ConstantNode.forIntegerStamp(equals.getX().stamp(), 1)), stamp);
165 }
166 } else if (equalsY == 1) {
167 if (constTrueValue == 1 && constFalseValue == 0) {
168 // return x when: x == 1 ? 1 : 0;
169 return IntegerConvertNode.convertUnsigned(equals.getX(), stamp);
170 } else if (constTrueValue == 0 && constFalseValue == 1) {
171 // negate a boolean value via xor
172 return IntegerConvertNode.convertUnsigned(XorNode.create(equals.getX(), ConstantNode.forIntegerStamp(equals.getX().stamp(), 1)), stamp);
173 }
174 }
175 }
176 }
177 } else if (condition instanceof IntegerTestNode) {
178 // replace IntegerTestNode with AndNode for the following patterns:
179 // (value & 1) == 0 ? 0 : 1
180 // (value & 1) == 1 ? 1 : 0
181 IntegerTestNode integerTestNode = (IntegerTestNode) condition;
182 if (integerTestNode.getY().isConstant()) {
183 assert integerTestNode.getX().stamp() instanceof IntegerStamp;
184 long testY = integerTestNode.getY().asJavaConstant().asLong();
185 if (testY == 1 && constTrueValue == 0 && constFalseValue == 1) {
186 return IntegerConvertNode.convertUnsigned(AndNode.create(integerTestNode.getX(), integerTestNode.getY()), stamp);
187 }
188 }
189 }
190 }
191 if (condition instanceof CompareNode && ((CompareNode) condition).isIdentityComparison()) {
192 // optimize the pattern (x == y) ? x : y
193 CompareNode compare = (CompareNode) condition;
194 if ((compare.getX() == trueValue && compare.getY() == falseValue) || (compare.getX() == falseValue && compare.getY() == trueValue)) {
195 return falseValue;
196 }
197 }
198 if (trueValue == falseValue) {
199 return trueValue;
200 }
201
202 if (condition instanceof IntegerLessThanNode && trueValue.stamp() instanceof IntegerStamp) {
203 /*
204 * Convert a conditional add ((x < 0) ? (x + y) : x) into (x + (y & (x >> (bits - 1))))
205 * to avoid the test.
206 */
207 IntegerLessThanNode lt = (IntegerLessThanNode) condition;
208 if (lt.getY().isConstant() && lt.getY().asConstant().isDefaultForKind()) {
209 if (falseValue == lt.getX()) {
210 if (trueValue instanceof AddNode) {
211 AddNode add = (AddNode) trueValue;
212 if (add.getX() == falseValue) {
213 int bits = ((IntegerStamp) trueValue.stamp()).getBits();
214 ValueNode shift = new RightShiftNode(lt.getX(), ConstantNode.forIntegerBits(32, bits - 1));
215 ValueNode and = new AndNode(shift, add.getY());
216 return new AddNode(add.getX(), and);
217 }
218 }
219 }
220 }
221 }
222
223 return null;
224 }
225
226 private static ValueNode findSynonym(ValueNode condition, ValueNode trueValue, ValueNode falseValue) {
227 if (condition instanceof LogicNegationNode) {
228 LogicNegationNode negated = (LogicNegationNode) condition;
229 return ConditionalNode.create(negated.getValue(), falseValue, trueValue);
230 }
231 if (condition instanceof LogicConstantNode) {
232 LogicConstantNode c = (LogicConstantNode) condition;
233 if (c.getValue()) {
234 return trueValue;
235 } else {
236 return falseValue;
237 }
238 }
239 return null;
240 }
241
242 @Override
243 public void generate(NodeLIRBuilderTool generator) {
244 generator.emitConditional(this);
245 }
246
247 public ConditionalNode(StructuredGraph graph, Condition condition, ValueNode x, ValueNode y) {
248 this(createCompareNode(graph, condition, x, y, null));
249 }
250 }