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 return new ConditionalNode(condition, trueValue, falseValue);
87 }
88
89 @Override
90 public boolean inferStamp() {
91 Stamp valueStamp = trueValue.stamp().meet(falseValue.stamp());
92 if (condition instanceof IntegerLessThanNode) {
93 IntegerLessThanNode lessThan = (IntegerLessThanNode) condition;
94 if (lessThan.getX() == trueValue && lessThan.getY() == falseValue) {
95 // this encodes a min operation
96 JavaConstant constant = lessThan.getX().asJavaConstant();
97 if (constant == null) {
98 constant = lessThan.getY().asJavaConstant();
99 }
100 if (constant != null) {
101 IntegerStamp bounds = StampFactory.forInteger(constant.getJavaKind(), constant.getJavaKind().getMinValue(), constant.asLong());
102 valueStamp = valueStamp.join(bounds);
103 }
104 } else if (lessThan.getX() == falseValue && lessThan.getY() == trueValue) {
105 // this encodes a max operation
106 JavaConstant constant = lessThan.getX().asJavaConstant();
107 if (constant == null) {
108 constant = lessThan.getY().asJavaConstant();
109 }
110 if (constant != null) {
111 IntegerStamp bounds = StampFactory.forInteger(constant.getJavaKind(), constant.asLong(), constant.getJavaKind().getMaxValue());
112 valueStamp = valueStamp.join(bounds);
113 }
114 }
115
116 }
117 return updateStamp(valueStamp);
118 }
119
120 public ValueNode trueValue() {
121 return trueValue;
122 }
123
124 public ValueNode falseValue() {
125 return falseValue;
126 }
127
128 @Override
129 public ValueNode canonical(CanonicalizerTool tool) {
130 ValueNode synonym = findSynonym(condition, trueValue(), falseValue());
131 if (synonym != null) {
132 return synonym;
133 }
134
135 ValueNode result = canonicalizeConditional(condition, trueValue(), falseValue(), stamp);
136 if (result != null) {
137 return result;
138 }
139
140 return this;
141 }
142
143 public static ValueNode canonicalizeConditional(LogicNode condition, ValueNode trueValue, ValueNode falseValue, Stamp stamp) {
144 // this optimizes the case where a value that can only be 0 or 1 is materialized to 0 or 1
145 if (trueValue.isConstant() && falseValue.isConstant() && condition instanceof IntegerEqualsNode) {
146 IntegerEqualsNode equals = (IntegerEqualsNode) condition;
147 if (equals.getY().isConstant() && equals.getY().asConstant().equals(JavaConstant.INT_0) && equals.getX().stamp() instanceof IntegerStamp) {
148 IntegerStamp equalsXStamp = (IntegerStamp) equals.getX().stamp();
149 if (equalsXStamp.upMask() == 1) {
150 if (trueValue.asConstant().equals(JavaConstant.INT_0) && falseValue.asConstant().equals(JavaConstant.INT_1)) {
151 return IntegerConvertNode.convertUnsigned(equals.getX(), stamp);
152 }
153 }
154 }
155 }
156 if (condition instanceof CompareNode && ((CompareNode) condition).isIdentityComparison()) {
157 // optimize the pattern (x == y) ? x : y
158 CompareNode compare = (CompareNode) condition;
159 if ((compare.getX() == trueValue && compare.getY() == falseValue) || (compare.getX() == falseValue && compare.getY() == trueValue)) {
160 return falseValue;
161 }
162 }
163 if (trueValue == falseValue) {
164 return trueValue;
165 }
166
167 if (condition instanceof IntegerLessThanNode && trueValue.stamp() instanceof IntegerStamp) {
168 /*
169 * Convert a conditional add ((x < 0) ? (x + y) : x) into (x + (y & (x >> (bits - 1))))
170 * to avoid the test.
171 */
172 IntegerLessThanNode lt = (IntegerLessThanNode) condition;
173 if (lt.getY().isConstant() && lt.getY().asConstant().isDefaultForKind()) {
174 if (falseValue == lt.getX()) {
175 if (trueValue instanceof AddNode) {
176 AddNode add = (AddNode) trueValue;
177 if (add.getX() == falseValue) {
178 int bits = ((IntegerStamp) trueValue.stamp()).getBits();
179 ValueNode shift = new RightShiftNode(lt.getX(), ConstantNode.forIntegerBits(32, bits - 1));
180 ValueNode and = new AndNode(shift, add.getY());
181 return new AddNode(add.getX(), and);
182 }
183 }
184 }
185 }
186 }
187
188 return null;
189 }
190
191 private static ValueNode findSynonym(ValueNode condition, ValueNode trueValue, ValueNode falseValue) {
192 if (condition instanceof LogicNegationNode) {
193 LogicNegationNode negated = (LogicNegationNode) condition;
194 return ConditionalNode.create(negated.getValue(), falseValue, trueValue);
195 }
196 if (condition instanceof LogicConstantNode) {
197 LogicConstantNode c = (LogicConstantNode) condition;
198 if (c.getValue()) {
199 return trueValue;
200 } else {
201 return falseValue;
202 }
203 }
204 return null;
205 }
206
207 @Override
208 public void generate(NodeLIRBuilderTool generator) {
209 generator.emitConditional(this);
210 }
211
212 public ConditionalNode(StructuredGraph graph, Condition condition, ValueNode x, ValueNode y) {
213 this(createCompareNode(graph, condition, x, y, null));
214 }
215 }