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;
26
27 import static org.graalvm.compiler.nodeinfo.InputType.Condition;
28 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_0;
29 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_0;
30
31 import org.graalvm.compiler.core.common.type.IntegerStamp;
32 import org.graalvm.compiler.graph.IterableNodeType;
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.NodeInfo;
37 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
38 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
39
40 import jdk.vm.ci.meta.TriState;
41
42 @NodeInfo(cycles = CYCLES_0, size = SIZE_0)
43 public final class ShortCircuitOrNode extends LogicNode implements IterableNodeType, Canonicalizable.Binary<LogicNode> {
44 public static final NodeClass<ShortCircuitOrNode> TYPE = NodeClass.create(ShortCircuitOrNode.class);
45 @Input(Condition) LogicNode x;
46 @Input(Condition) LogicNode y;
47 protected boolean xNegated;
48 protected boolean yNegated;
49 protected double shortCircuitProbability;
50
51 public ShortCircuitOrNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, double shortCircuitProbability) {
52 super(TYPE);
53 this.x = x;
54 this.xNegated = xNegated;
55 this.y = y;
56 this.yNegated = yNegated;
57 this.shortCircuitProbability = shortCircuitProbability;
58 }
59
60 @Override
61 public LogicNode getX() {
62 return x;
63 }
64
65 @Override
66 public LogicNode getY() {
67 return y;
68 }
69
70 public boolean isXNegated() {
71 return xNegated;
72 }
73
74 public boolean isYNegated() {
75 return yNegated;
76 }
77
78 /**
79 * Gets the probability that the {@link #getY() y} part of this binary node is <b>not</b>
94 LogicNode yCond = forY;
95 boolean yNeg = yNegated;
96 while (yCond instanceof LogicNegationNode) {
97 yCond = ((LogicNegationNode) yCond).getValue();
98 yNeg = !yNeg;
99 }
100
101 if (xCond != forX || yCond != forY) {
102 return new ShortCircuitOrNode(xCond, xNeg, yCond, yNeg, shortCircuitProbability);
103 } else {
104 return this;
105 }
106 }
107
108 @Override
109 public LogicNode canonical(CanonicalizerTool tool, LogicNode forX, LogicNode forY) {
110 ShortCircuitOrNode ret = canonicalizeNegation(forX, forY);
111 if (ret != this) {
112 return ret;
113 }
114
115 if (forX == forY) {
116 // @formatter:off
117 // a || a = a
118 // a || !a = true
119 // !a || a = true
120 // !a || !a = !a
121 // @formatter:on
122 if (isXNegated()) {
123 if (isYNegated()) {
124 // !a || !a = !a
125 return LogicNegationNode.create(forX);
126 } else {
127 // !a || a = true
128 return LogicConstantNode.tautology();
129 }
130 } else {
131 if (isYNegated()) {
132 // a || !a = true
133 return LogicConstantNode.tautology();
186 ? LogicNegationNode.create(forX)
187 : forX);
188 }
189
190 // if X >= 0:
191 // u < 0 || X < u ==>> X |<| u
192 if (!isXNegated() && !isYNegated()) {
193 LogicNode sym = simplifyComparison(forX, forY);
194 if (sym != null) {
195 return sym;
196 }
197 }
198
199 // if X >= 0:
200 // X |<| u || X < u ==>> X |<| u
201 if (forX instanceof IntegerBelowNode && forY instanceof IntegerLessThanNode && !isXNegated() && !isYNegated()) {
202 IntegerBelowNode xNode = (IntegerBelowNode) forX;
203 IntegerLessThanNode yNode = (IntegerLessThanNode) forY;
204 ValueNode xxNode = xNode.getX(); // X >= 0
205 ValueNode yxNode = yNode.getX(); // X >= 0
206 if (xxNode == yxNode && ((IntegerStamp) xxNode.stamp(NodeView.DEFAULT)).isPositive()) {
207 ValueNode xyNode = xNode.getY(); // u
208 ValueNode yyNode = yNode.getY(); // u
209 if (xyNode == yyNode) {
210 return forX;
211 }
212 }
213 }
214
215 // if X >= 0:
216 // u < 0 || (X < u || tail) ==>> X |<| u || tail
217 if (forY instanceof ShortCircuitOrNode && !isXNegated() && !isYNegated()) {
218 ShortCircuitOrNode yNode = (ShortCircuitOrNode) forY;
219 if (!yNode.isXNegated()) {
220 LogicNode sym = simplifyComparison(forX, yNode.getX());
221 if (sym != null) {
222 double p1 = getShortCircuitProbability();
223 double p2 = yNode.getShortCircuitProbability();
224 return new ShortCircuitOrNode(sym, isXNegated(), yNode.getY(), yNode.isYNegated(), p1 + (1 - p1) * p2);
225 }
226 }
227 }
228
229 return this;
230 }
231
232 private static LogicNode simplifyComparison(LogicNode forX, LogicNode forY) {
233 LogicNode sym = simplifyComparisonOrdered(forX, forY);
234 if (sym == null) {
235 return simplifyComparisonOrdered(forY, forX);
236 }
237 return sym;
238 }
239
240 private static LogicNode simplifyComparisonOrdered(LogicNode forX, LogicNode forY) {
241 // if X is >= 0:
242 // u < 0 || X < u ==>> X |<| u
243 if (forX instanceof IntegerLessThanNode && forY instanceof IntegerLessThanNode) {
244 IntegerLessThanNode xNode = (IntegerLessThanNode) forX;
245 IntegerLessThanNode yNode = (IntegerLessThanNode) forY;
246 ValueNode xyNode = xNode.getY(); // 0
247 if (xyNode.isConstant() && IntegerStamp.OPS.getAdd().isNeutral(xyNode.asConstant())) {
248 ValueNode yxNode = yNode.getX(); // X >= 0
249 IntegerStamp stamp = (IntegerStamp) yxNode.stamp(NodeView.DEFAULT);
|
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;
26
27 import static org.graalvm.compiler.nodeinfo.InputType.Condition;
28 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_0;
29 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_0;
30
31 import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
32 import org.graalvm.compiler.core.common.type.IntegerStamp;
33 import org.graalvm.compiler.core.common.type.Stamp;
34 import org.graalvm.compiler.graph.IterableNodeType;
35 import org.graalvm.compiler.graph.NodeClass;
36 import org.graalvm.compiler.graph.spi.Canonicalizable;
37 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
38 import org.graalvm.compiler.nodeinfo.NodeInfo;
39 import org.graalvm.compiler.nodes.calc.CompareNode;
40 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
41 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
42 import org.graalvm.compiler.options.OptionValues;
43
44 import jdk.vm.ci.meta.Assumptions;
45 import jdk.vm.ci.meta.ConstantReflectionProvider;
46 import jdk.vm.ci.meta.MetaAccessProvider;
47 import jdk.vm.ci.meta.TriState;
48
49 @NodeInfo(cycles = CYCLES_0, size = SIZE_0)
50 public final class ShortCircuitOrNode extends LogicNode implements IterableNodeType, Canonicalizable.Binary<LogicNode> {
51 public static final NodeClass<ShortCircuitOrNode> TYPE = NodeClass.create(ShortCircuitOrNode.class);
52 @Input(Condition) LogicNode x;
53 @Input(Condition) LogicNode y;
54 protected boolean xNegated;
55 protected boolean yNegated;
56 protected double shortCircuitProbability;
57
58 public ShortCircuitOrNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, double shortCircuitProbability) {
59 super(TYPE);
60 this.x = x;
61 this.xNegated = xNegated;
62 this.y = y;
63 this.yNegated = yNegated;
64 this.shortCircuitProbability = shortCircuitProbability;
65 }
66
67 public static LogicNode create(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, double shortCircuitProbability) {
68 return new ShortCircuitOrNode(x, xNegated, y, yNegated, shortCircuitProbability);
69 }
70
71 @Override
72 public LogicNode getX() {
73 return x;
74 }
75
76 @Override
77 public LogicNode getY() {
78 return y;
79 }
80
81 public boolean isXNegated() {
82 return xNegated;
83 }
84
85 public boolean isYNegated() {
86 return yNegated;
87 }
88
89 /**
90 * Gets the probability that the {@link #getY() y} part of this binary node is <b>not</b>
105 LogicNode yCond = forY;
106 boolean yNeg = yNegated;
107 while (yCond instanceof LogicNegationNode) {
108 yCond = ((LogicNegationNode) yCond).getValue();
109 yNeg = !yNeg;
110 }
111
112 if (xCond != forX || yCond != forY) {
113 return new ShortCircuitOrNode(xCond, xNeg, yCond, yNeg, shortCircuitProbability);
114 } else {
115 return this;
116 }
117 }
118
119 @Override
120 public LogicNode canonical(CanonicalizerTool tool, LogicNode forX, LogicNode forY) {
121 ShortCircuitOrNode ret = canonicalizeNegation(forX, forY);
122 if (ret != this) {
123 return ret;
124 }
125 NodeView view = NodeView.from(tool);
126
127 if (forX == forY) {
128 // @formatter:off
129 // a || a = a
130 // a || !a = true
131 // !a || a = true
132 // !a || !a = !a
133 // @formatter:on
134 if (isXNegated()) {
135 if (isYNegated()) {
136 // !a || !a = !a
137 return LogicNegationNode.create(forX);
138 } else {
139 // !a || a = true
140 return LogicConstantNode.tautology();
141 }
142 } else {
143 if (isYNegated()) {
144 // a || !a = true
145 return LogicConstantNode.tautology();
198 ? LogicNegationNode.create(forX)
199 : forX);
200 }
201
202 // if X >= 0:
203 // u < 0 || X < u ==>> X |<| u
204 if (!isXNegated() && !isYNegated()) {
205 LogicNode sym = simplifyComparison(forX, forY);
206 if (sym != null) {
207 return sym;
208 }
209 }
210
211 // if X >= 0:
212 // X |<| u || X < u ==>> X |<| u
213 if (forX instanceof IntegerBelowNode && forY instanceof IntegerLessThanNode && !isXNegated() && !isYNegated()) {
214 IntegerBelowNode xNode = (IntegerBelowNode) forX;
215 IntegerLessThanNode yNode = (IntegerLessThanNode) forY;
216 ValueNode xxNode = xNode.getX(); // X >= 0
217 ValueNode yxNode = yNode.getX(); // X >= 0
218 if (xxNode == yxNode && ((IntegerStamp) xxNode.stamp(view)).isPositive()) {
219 ValueNode xyNode = xNode.getY(); // u
220 ValueNode yyNode = yNode.getY(); // u
221 if (xyNode == yyNode) {
222 return forX;
223 }
224 }
225 }
226
227 // if X >= 0:
228 // u < 0 || (X < u || tail) ==>> X |<| u || tail
229 if (forY instanceof ShortCircuitOrNode && !isXNegated() && !isYNegated()) {
230 ShortCircuitOrNode yNode = (ShortCircuitOrNode) forY;
231 if (!yNode.isXNegated()) {
232 LogicNode sym = simplifyComparison(forX, yNode.getX());
233 if (sym != null) {
234 double p1 = getShortCircuitProbability();
235 double p2 = yNode.getShortCircuitProbability();
236 return new ShortCircuitOrNode(sym, isXNegated(), yNode.getY(), yNode.isYNegated(), p1 + (1 - p1) * p2);
237 }
238 }
239 }
240
241 if (forX instanceof CompareNode && forY instanceof CompareNode) {
242 CompareNode xCompare = (CompareNode) forX;
243 CompareNode yCompare = (CompareNode) forY;
244
245 if (xCompare.getX() == yCompare.getX() || xCompare.getX() == yCompare.getY()) {
246
247 Stamp succeedingStampX = xCompare.getSucceedingStampForX(!xNegated, xCompare.getX().stamp(view), xCompare.getY().stamp(view));
248 // Try to canonicalize the other comparison using the knowledge gained from assuming
249 // the first part of the short circuit or is false (which is the only relevant case
250 // for the second part of the short circuit or).
251 if (succeedingStampX != null && !succeedingStampX.isUnrestricted()) {
252 CanonicalizerTool proxyTool = new ProxyCanonicalizerTool(succeedingStampX, xCompare.getX(), tool, view);
253 ValueNode result = yCompare.canonical(proxyTool);
254 if (result != yCompare) {
255 return ShortCircuitOrNode.create(forX, xNegated, (LogicNode) result, yNegated, this.shortCircuitProbability);
256 }
257 }
258 }
259 }
260
261 return this;
262 }
263
264 private static class ProxyCanonicalizerTool implements CanonicalizerTool, NodeView {
265
266 private final Stamp stamp;
267 private final ValueNode node;
268 private final CanonicalizerTool tool;
269 private final NodeView view;
270
271 ProxyCanonicalizerTool(Stamp stamp, ValueNode node, CanonicalizerTool tool, NodeView view) {
272 this.stamp = stamp;
273 this.node = node;
274 this.tool = tool;
275 this.view = view;
276 }
277
278 @Override
279 public Stamp stamp(ValueNode n) {
280 if (n == node) {
281 return stamp;
282 }
283 return view.stamp(n);
284 }
285
286 @Override
287 public Assumptions getAssumptions() {
288 return tool.getAssumptions();
289 }
290
291 @Override
292 public MetaAccessProvider getMetaAccess() {
293 return tool.getMetaAccess();
294 }
295
296 @Override
297 public ConstantReflectionProvider getConstantReflection() {
298 return tool.getConstantReflection();
299 }
300
301 @Override
302 public ConstantFieldProvider getConstantFieldProvider() {
303 return tool.getConstantFieldProvider();
304 }
305
306 @Override
307 public boolean canonicalizeReads() {
308 return tool.canonicalizeReads();
309 }
310
311 @Override
312 public boolean allUsagesAvailable() {
313 return tool.allUsagesAvailable();
314 }
315
316 @Override
317 public Integer smallestCompareWidth() {
318 return tool.smallestCompareWidth();
319 }
320
321 @Override
322 public OptionValues getOptions() {
323 return tool.getOptions();
324 }
325 }
326
327 private static LogicNode simplifyComparison(LogicNode forX, LogicNode forY) {
328 LogicNode sym = simplifyComparisonOrdered(forX, forY);
329 if (sym == null) {
330 return simplifyComparisonOrdered(forY, forX);
331 }
332 return sym;
333 }
334
335 private static LogicNode simplifyComparisonOrdered(LogicNode forX, LogicNode forY) {
336 // if X is >= 0:
337 // u < 0 || X < u ==>> X |<| u
338 if (forX instanceof IntegerLessThanNode && forY instanceof IntegerLessThanNode) {
339 IntegerLessThanNode xNode = (IntegerLessThanNode) forX;
340 IntegerLessThanNode yNode = (IntegerLessThanNode) forY;
341 ValueNode xyNode = xNode.getY(); // 0
342 if (xyNode.isConstant() && IntegerStamp.OPS.getAdd().isNeutral(xyNode.asConstant())) {
343 ValueNode yxNode = yNode.getX(); // X >= 0
344 IntegerStamp stamp = (IntegerStamp) yxNode.stamp(NodeView.DEFAULT);
|