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;
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);
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;
|
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_1;
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 (eagerly
51 * evaluated) values.
52 */
53 @NodeInfo(cycles = CYCLES_1, 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;
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 return updateStamp(valueStamp);
121 }
122
123 public ValueNode trueValue() {
124 return trueValue;
125 }
126
127 public ValueNode falseValue() {
128 return falseValue;
129 }
130
131 @Override
132 public ValueNode canonical(CanonicalizerTool tool) {
133 ValueNode synonym = findSynonym(condition, trueValue(), falseValue());
134 if (synonym != null) {
135 return synonym;
136 }
137
138 ValueNode result = canonicalizeConditional(condition, trueValue(), falseValue(), stamp);
139 if (result != null) {
140 return result;
141 }
142
143 return this;
144 }
145
146 public static ValueNode canonicalizeConditional(LogicNode condition, ValueNode trueValue, ValueNode falseValue, Stamp stamp) {
147 if (trueValue == falseValue) {
148 return trueValue;
149 }
150
151 if (condition instanceof CompareNode && ((CompareNode) condition).isIdentityComparison()) {
152 // optimize the pattern (x == y) ? x : y
153 CompareNode compare = (CompareNode) condition;
154 if ((compare.getX() == trueValue && compare.getY() == falseValue) || (compare.getX() == falseValue && compare.getY() == trueValue)) {
155 return falseValue;
156 }
157 }
158
159 if (trueValue.stamp() instanceof IntegerStamp) {
160 // check if the conditional is redundant
161 if (condition instanceof IntegerLessThanNode) {
162 IntegerLessThanNode lessThan = (IntegerLessThanNode) condition;
163 IntegerStamp falseValueStamp = (IntegerStamp) falseValue.stamp();
164 IntegerStamp trueValueStamp = (IntegerStamp) trueValue.stamp();
165 if (lessThan.getX() == trueValue && lessThan.getY() == falseValue) {
166 // return "x" for "x < y ? x : y" in case that we know "x <= y"
167 if (trueValueStamp.upperBound() <= falseValueStamp.lowerBound()) {
168 return trueValue;
169 }
170 } else if (lessThan.getX() == falseValue && lessThan.getY() == trueValue) {
171 // return "x" for "x < y ? y : x" in case that we know "x <= y"
172 if (falseValueStamp.upperBound() <= trueValueStamp.lowerBound()) {
173 return falseValue;
174 }
175 }
176 }
177
178 // this optimizes the case where a value from the range 0 - 1 is mapped to the
179 // range 0 - 1
180 if (trueValue.isConstant() && falseValue.isConstant()) {
181 long constTrueValue = trueValue.asJavaConstant().asLong();
182 long constFalseValue = falseValue.asJavaConstant().asLong();
183 if (condition instanceof IntegerEqualsNode) {
184 IntegerEqualsNode equals = (IntegerEqualsNode) condition;
185 if (equals.getY().isConstant() && equals.getX().stamp() instanceof IntegerStamp) {
186 IntegerStamp equalsXStamp = (IntegerStamp) equals.getX().stamp();
187 if (equalsXStamp.upMask() == 1) {
188 long equalsY = equals.getY().asJavaConstant().asLong();
189 if (equalsY == 0) {
190 if (constTrueValue == 0 && constFalseValue == 1) {
191 // return x when: x == 0 ? 0 : 1;
192 return IntegerConvertNode.convertUnsigned(equals.getX(), stamp);
193 } else if (constTrueValue == 1 && constFalseValue == 0) {
194 // negate a boolean value via xor
195 return IntegerConvertNode.convertUnsigned(XorNode.create(equals.getX(), ConstantNode.forIntegerStamp(equals.getX().stamp(), 1)), stamp);
196 }
197 } else if (equalsY == 1) {
198 if (constTrueValue == 1 && constFalseValue == 0) {
199 // return x when: x == 1 ? 1 : 0;
200 return IntegerConvertNode.convertUnsigned(equals.getX(), stamp);
202 // negate a boolean value via xor
203 return IntegerConvertNode.convertUnsigned(XorNode.create(equals.getX(), ConstantNode.forIntegerStamp(equals.getX().stamp(), 1)), stamp);
204 }
205 }
206 }
207 }
208 } else if (condition instanceof IntegerTestNode) {
209 // replace IntegerTestNode with AndNode for the following patterns:
210 // (value & 1) == 0 ? 0 : 1
211 // (value & 1) == 1 ? 1 : 0
212 IntegerTestNode integerTestNode = (IntegerTestNode) condition;
213 if (integerTestNode.getY().isConstant()) {
214 assert integerTestNode.getX().stamp() instanceof IntegerStamp;
215 long testY = integerTestNode.getY().asJavaConstant().asLong();
216 if (testY == 1 && constTrueValue == 0 && constFalseValue == 1) {
217 return IntegerConvertNode.convertUnsigned(AndNode.create(integerTestNode.getX(), integerTestNode.getY()), stamp);
218 }
219 }
220 }
221 }
222
223 if (condition instanceof IntegerLessThanNode) {
224 /*
225 * Convert a conditional add ((x < 0) ? (x + y) : x) into (x + (y & (x >> (bits -
226 * 1)))) to avoid the test.
227 */
228 IntegerLessThanNode lt = (IntegerLessThanNode) condition;
229 if (lt.getY().isConstant() && lt.getY().asConstant().isDefaultForKind()) {
230 if (falseValue == lt.getX()) {
231 if (trueValue instanceof AddNode) {
232 AddNode add = (AddNode) trueValue;
233 if (add.getX() == falseValue) {
234 int bits = ((IntegerStamp) trueValue.stamp()).getBits();
235 ValueNode shift = new RightShiftNode(lt.getX(), ConstantNode.forIntegerBits(32, bits - 1));
236 ValueNode and = new AndNode(shift, add.getY());
237 return new AddNode(add.getX(), and);
238 }
239 }
240 }
241 }
242 }
243 }
244
245 return null;
246 }
247
248 private static ValueNode findSynonym(ValueNode condition, ValueNode trueValue, ValueNode falseValue) {
249 if (condition instanceof LogicNegationNode) {
250 LogicNegationNode negated = (LogicNegationNode) condition;
251 return ConditionalNode.create(negated.getValue(), falseValue, trueValue);
252 }
253 if (condition instanceof LogicConstantNode) {
254 LogicConstantNode c = (LogicConstantNode) condition;
255 if (c.getValue()) {
256 return trueValue;
257 } else {
258 return falseValue;
|