1 /*
2 * Copyright (c) 2013, 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
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>
80 * evaluated. This is the probability that this operator will short-circuit its execution.
81 */
82 public double getShortCircuitProbability() {
83 return shortCircuitProbability;
84 }
85
86 protected ShortCircuitOrNode canonicalizeNegation(LogicNode forX, LogicNode forY) {
87 LogicNode xCond = forX;
88 boolean xNeg = xNegated;
89 while (xCond instanceof LogicNegationNode) {
90 xCond = ((LogicNegationNode) xCond).getValue();
91 xNeg = !xNeg;
92 }
93
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();
134 } else {
135 // a || a = a
136 return forX;
137 }
138 }
139 }
140 if (forX instanceof LogicConstantNode) {
141 if (((LogicConstantNode) forX).getValue() ^ isXNegated()) {
142 return LogicConstantNode.tautology();
143 } else {
144 if (isYNegated()) {
145 return new LogicNegationNode(forY);
146 } else {
147 return forY;
148 }
149 }
150 }
151 if (forY instanceof LogicConstantNode) {
152 if (((LogicConstantNode) forY).getValue() ^ isYNegated()) {
153 return LogicConstantNode.tautology();
154 } else {
155 if (isXNegated()) {
156 return new LogicNegationNode(forX);
157 } else {
158 return forX;
159 }
160 }
161 }
162
163 if (forX instanceof ShortCircuitOrNode) {
164 ShortCircuitOrNode inner = (ShortCircuitOrNode) forX;
165 if (forY == inner.getX()) {
166 return optimizeShortCircuit(inner, this.xNegated, this.yNegated, true);
167 } else if (forY == inner.getY()) {
168 return optimizeShortCircuit(inner, this.xNegated, this.yNegated, false);
169 }
170 } else if (forY instanceof ShortCircuitOrNode) {
171 ShortCircuitOrNode inner = (ShortCircuitOrNode) forY;
172 if (inner.getX() == forX) {
173 return optimizeShortCircuit(inner, this.yNegated, this.xNegated, true);
174 } else if (inner.getY() == forX) {
175 return optimizeShortCircuit(inner, this.yNegated, this.xNegated, false);
176 }
177 }
178
179 // !X => Y constant
180 TriState impliedForY = forX.implies(!isXNegated(), forY);
181 if (impliedForY.isKnown()) {
182 boolean yResult = impliedForY.toBoolean() ^ isYNegated();
183 return yResult
184 ? LogicConstantNode.tautology()
185 : (isXNegated()
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);
250 if (stamp.isPositive()) {
251 if (xNode.getX() == yNode.getY()) {
252 ValueNode u = xNode.getX();
253 return IntegerBelowNode.create(yxNode, u, NodeView.DEFAULT);
254 }
255 }
256 }
257 }
258
259 return null;
260 }
261
262 private static LogicNode optimizeShortCircuit(ShortCircuitOrNode inner, boolean innerNegated, boolean matchNegated, boolean matchIsInnerX) {
263 boolean innerMatchNegated;
264 if (matchIsInnerX) {
265 innerMatchNegated = inner.isXNegated();
266 } else {
267 innerMatchNegated = inner.isYNegated();
268 }
269 if (!innerNegated) {
270 // The four digit results of the expression used in the 16 subsequent formula comments
271 // correspond to results when using the following truth table for inputs a and b
272 // and testing all 4 possible input combinations:
273 // _ 1234
274 // a 1100
275 // b 1010
276 if (innerMatchNegated == matchNegated) {
277 // ( (!a ||!b) ||!a) => 0111 (!a ||!b)
278 // ( (!a || b) ||!a) => 1011 (!a || b)
279 // ( ( a ||!b) || a) => 1101 ( a ||!b)
280 // ( ( a || b) || a) => 1110 ( a || b)
281 // Only the inner or is relevant, the outer or never adds information.
282 return inner;
283 } else {
284 // ( ( a || b) ||!a) => 1111 (true)
285 // ( (!a ||!b) || a) => 1111 (true)
286 // ( (!a || b) || a) => 1111 (true)
287 // ( ( a ||!b) ||!a) => 1111 (true)
288 // The result of the expression is always true.
289 return LogicConstantNode.tautology();
290 }
291 } else {
292 if (innerMatchNegated == matchNegated) {
293 // (!(!a ||!b) ||!a) => 1011 (!a || b)
294 // (!(!a || b) ||!a) => 0111 (!a ||!b)
295 // (!( a ||!b) || a) => 1110 ( a || b)
296 // (!( a || b) || a) => 1101 ( a ||!b)
297 boolean newInnerXNegated = inner.isXNegated();
298 boolean newInnerYNegated = inner.isYNegated();
299 double newProbability = inner.getShortCircuitProbability();
300 if (matchIsInnerX) {
301 newInnerYNegated = !newInnerYNegated;
302 } else {
303 newInnerXNegated = !newInnerXNegated;
304 newProbability = 1.0 - newProbability;
305 }
306 // The expression can be transformed into a single or.
307 return new ShortCircuitOrNode(inner.getX(), newInnerXNegated, inner.getY(), newInnerYNegated, newProbability);
308 } else {
309 // (!(!a ||!b) || a) => 1100 (a)
310 // (!(!a || b) || a) => 1100 (a)
311 // (!( a ||!b) ||!a) => 0011 (!a)
312 // (!( a || b) ||!a) => 0011 (!a)
313 LogicNode result = inner.getY();
314 if (matchIsInnerX) {
315 result = inner.getX();
316 }
317 // Only the second part of the outer or is relevant.
318 if (matchNegated) {
319 return LogicNegationNode.create(result);
320 } else {
321 return result;
322 }
323 }
324 }
325 }
326 }