1 /*
2 * Copyright (c) 2009, 2015, 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.NodeCycles.CYCLES_1;
28 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_2;
29
30 import java.util.ArrayList;
31 import java.util.Arrays;
32 import java.util.Iterator;
33 import java.util.List;
34 import java.util.Objects;
35
36 import jdk.internal.vm.compiler.collections.EconomicMap;
37 import jdk.internal.vm.compiler.collections.Equivalence;
38 import org.graalvm.compiler.bytecode.BytecodeDisassembler;
39 import org.graalvm.compiler.bytecode.Bytecodes;
40 import org.graalvm.compiler.bytecode.Bytes;
41 import org.graalvm.compiler.bytecode.ResolvedJavaMethodBytecode;
42 import org.graalvm.compiler.core.common.calc.Condition;
43 import org.graalvm.compiler.core.common.type.IntegerStamp;
44 import org.graalvm.compiler.core.common.type.Stamp;
45 import org.graalvm.compiler.core.common.type.StampFactory;
46 import org.graalvm.compiler.debug.CounterKey;
47 import org.graalvm.compiler.debug.DebugCloseable;
48 import org.graalvm.compiler.debug.DebugContext;
49 import org.graalvm.compiler.debug.GraalError;
50 import org.graalvm.compiler.graph.Node;
51 import org.graalvm.compiler.graph.NodeClass;
52 import org.graalvm.compiler.graph.NodeSourcePosition;
53 import org.graalvm.compiler.graph.iterators.NodeIterable;
54 import org.graalvm.compiler.graph.spi.Canonicalizable;
55 import org.graalvm.compiler.graph.spi.Simplifiable;
56 import org.graalvm.compiler.graph.spi.SimplifierTool;
57 import org.graalvm.compiler.nodeinfo.InputType;
58 import org.graalvm.compiler.nodeinfo.NodeInfo;
59 import org.graalvm.compiler.nodes.calc.CompareNode;
60 import org.graalvm.compiler.nodes.calc.ConditionalNode;
61 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
62 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
63 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
64 import org.graalvm.compiler.nodes.calc.IsNullNode;
65 import org.graalvm.compiler.nodes.calc.NormalizeCompareNode;
66 import org.graalvm.compiler.nodes.calc.ObjectEqualsNode;
67 import org.graalvm.compiler.nodes.extended.UnboxNode;
68 import org.graalvm.compiler.nodes.java.InstanceOfNode;
69 import org.graalvm.compiler.nodes.java.LoadFieldNode;
70 import org.graalvm.compiler.nodes.spi.LIRLowerable;
71 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
72 import org.graalvm.compiler.nodes.util.GraphUtil;
73
74 import jdk.vm.ci.meta.Constant;
75 import jdk.vm.ci.meta.JavaConstant;
76 import jdk.vm.ci.meta.JavaKind;
77 import jdk.vm.ci.meta.MetaAccessProvider;
78 import jdk.vm.ci.meta.PrimitiveConstant;
79 import jdk.vm.ci.meta.ResolvedJavaMethod;
80 import jdk.vm.ci.meta.ResolvedJavaType;
81
82 /**
83 * The {@code IfNode} represents a branch that can go one of two directions depending on the outcome
84 * of a comparison.
85 */
86 @NodeInfo(cycles = CYCLES_1, size = SIZE_2, sizeRationale = "2 jmps")
87 public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable {
88 public static final NodeClass<IfNode> TYPE = NodeClass.create(IfNode.class);
89
90 private static final CounterKey CORRECTED_PROBABILITIES = DebugContext.counter("CorrectedProbabilities");
91
92 @Successor AbstractBeginNode trueSuccessor;
93 @Successor AbstractBeginNode falseSuccessor;
94 @Input(InputType.Condition) LogicNode condition;
95 protected double trueSuccessorProbability;
96
97 public LogicNode condition() {
98 return condition;
99 }
100
101 public void setCondition(LogicNode x) {
102 updateUsages(condition, x);
103 condition = x;
104 }
105
106 public IfNode(LogicNode condition, FixedNode trueSuccessor, FixedNode falseSuccessor, double trueSuccessorProbability) {
107 this(condition, BeginNode.begin(trueSuccessor), BeginNode.begin(falseSuccessor), trueSuccessorProbability);
108 }
109
110 public IfNode(LogicNode condition, AbstractBeginNode trueSuccessor, AbstractBeginNode falseSuccessor, double trueSuccessorProbability) {
111 super(TYPE, StampFactory.forVoid());
112 this.condition = condition;
113 this.falseSuccessor = falseSuccessor;
114 this.trueSuccessor = trueSuccessor;
115 setTrueSuccessorProbability(trueSuccessorProbability);
116 }
117
118 /**
119 * Gets the true successor.
120 *
121 * @return the true successor
122 */
123 public AbstractBeginNode trueSuccessor() {
124 return trueSuccessor;
125 }
126
127 /**
128 * Gets the false successor.
129 *
130 * @return the false successor
131 */
132 public AbstractBeginNode falseSuccessor() {
133 return falseSuccessor;
134 }
135
136 public double getTrueSuccessorProbability() {
137 return this.trueSuccessorProbability;
138 }
139
140 public void setTrueSuccessor(AbstractBeginNode node) {
141 updatePredecessor(trueSuccessor, node);
142 trueSuccessor = node;
143 }
144
145 public void setFalseSuccessor(AbstractBeginNode node) {
146 updatePredecessor(falseSuccessor, node);
147 falseSuccessor = node;
148 }
149
150 /**
151 * Gets the node corresponding to the specified outcome of the branch.
152 *
153 * @param istrue {@code true} if the true successor is requested, {@code false} otherwise
154 * @return the corresponding successor
155 */
156 public AbstractBeginNode successor(boolean istrue) {
157 return istrue ? trueSuccessor : falseSuccessor;
158 }
159
160 public void setTrueSuccessorProbability(double prob) {
161 assert prob >= -0.000000001 && prob <= 1.000000001 : "Probability out of bounds: " + prob;
162 trueSuccessorProbability = Math.min(1.0, Math.max(0.0, prob));
163 }
164
165 @Override
166 public double probability(AbstractBeginNode successor) {
167 return successor == trueSuccessor ? trueSuccessorProbability : 1 - trueSuccessorProbability;
168 }
169
170 @Override
171 public void generate(NodeLIRBuilderTool gen) {
172 gen.emitIf(this);
173 }
174
175 @Override
176 public boolean verify() {
177 assertTrue(condition() != null, "missing condition");
178 assertTrue(trueSuccessor() != null, "missing trueSuccessor");
179 assertTrue(falseSuccessor() != null, "missing falseSuccessor");
180 return super.verify();
181 }
182
183 private boolean compareCallContext(NodeSourcePosition successorPosition) {
184 NodeSourcePosition position = getNodeSourcePosition();
185 NodeSourcePosition successor = successorPosition;
186 while (position != null) {
187 assertTrue(Objects.equals(position.getMethod(), successor.getMethod()), "method mismatch");
188 position = position.getCaller();
189 successor = successor.getCaller();
190 }
191 assertTrue(successor == null, "successor position has more methods");
192 return true;
193 }
194
195 @Override
196 public boolean verifySourcePosition() {
197 NodeSourcePosition sourcePosition = getNodeSourcePosition();
198 assertTrue(sourcePosition != null, "missing IfNode source position");
199
200 NodeSourcePosition trueSuccessorPosition = trueSuccessor.getNodeSourcePosition();
201 assertTrue(trueSuccessorPosition != null, "missing IfNode true successor source position");
202
203 NodeSourcePosition falseSuccessorPosition = falseSuccessor.getNodeSourcePosition();
204 assertTrue(falseSuccessorPosition != null, "missing IfNode false successor source position");
205
206 int bci = sourcePosition.getBCI();
207 ResolvedJavaMethod method = sourcePosition.getMethod();
208 int bytecode = BytecodeDisassembler.getBytecodeAt(method, bci);
209
210 if (!Bytecodes.isIfBytecode(bytecode)) {
211 return true;
212 }
213
214 byte[] code = (new ResolvedJavaMethodBytecode(method)).getCode();
215 int targetBCI = bci + Bytes.beS2(code, bci + 1);
216 int nextBCI = bci + Bytecodes.lengthOf(bytecode);
217
218 // At least one successor should have the correct BCI to indicate any possible negation that
219 // occurred after bytecode parsing
220 boolean matchingSuccessorFound = false;
221 if (trueSuccessorPosition.getBCI() == nextBCI || trueSuccessorPosition.getBCI() == targetBCI) {
222 assertTrue(compareCallContext(trueSuccessorPosition), "call context different from IfNode in trueSuccessor");
223 matchingSuccessorFound = true;
224 }
225
226 if (falseSuccessorPosition.getBCI() == nextBCI || falseSuccessorPosition.getBCI() == targetBCI) {
227 assertTrue(compareCallContext(falseSuccessorPosition), "call context different from IfNode in falseSuccessor");
228 matchingSuccessorFound = true;
229 }
230
231 assertTrue(matchingSuccessorFound, "no matching successor position found in IfNode");
232 assertTrue(trueSuccessorPosition.getBCI() != falseSuccessorPosition.getBCI(), "successor positions same in IfNode");
233
234 return true;
235 }
236
237 public void eliminateNegation() {
238 AbstractBeginNode oldTrueSuccessor = trueSuccessor;
239 AbstractBeginNode oldFalseSuccessor = falseSuccessor;
240 trueSuccessor = oldFalseSuccessor;
241 falseSuccessor = oldTrueSuccessor;
242 trueSuccessorProbability = 1 - trueSuccessorProbability;
243 setCondition(((LogicNegationNode) condition).getValue());
244 }
245
246 @Override
247 public void simplify(SimplifierTool tool) {
248 if (trueSuccessor().next() instanceof DeoptimizeNode) {
249 if (trueSuccessorProbability != 0) {
250 CORRECTED_PROBABILITIES.increment(getDebug());
251 trueSuccessorProbability = 0;
252 }
253 } else if (falseSuccessor().next() instanceof DeoptimizeNode) {
254 if (trueSuccessorProbability != 1) {
255 CORRECTED_PROBABILITIES.increment(getDebug());
256 trueSuccessorProbability = 1;
257 }
258 }
259
260 if (condition() instanceof LogicNegationNode) {
261 eliminateNegation();
262 }
263 if (condition() instanceof LogicConstantNode) {
264 LogicConstantNode c = (LogicConstantNode) condition();
265 if (c.getValue()) {
266 tool.deleteBranch(falseSuccessor());
267 tool.addToWorkList(trueSuccessor());
268 graph().removeSplit(this, trueSuccessor());
269 } else {
270 tool.deleteBranch(trueSuccessor());
271 tool.addToWorkList(falseSuccessor());
272 graph().removeSplit(this, falseSuccessor());
273 }
274 return;
275 }
276 if (tool.allUsagesAvailable() && trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages()) {
277
278 pushNodesThroughIf(tool);
279
280 if (checkForUnsignedCompare(tool) || removeOrMaterializeIf(tool)) {
281 return;
282 }
283 }
284
285 if (removeIntermediateMaterialization(tool)) {
286 return;
287 }
288
289 if (splitIfAtPhi(tool)) {
290 return;
291 }
292
293 if (conditionalNodeOptimization(tool)) {
294 return;
295 }
296
297 if (falseSuccessor().hasNoUsages() && (!(falseSuccessor() instanceof LoopExitNode)) && falseSuccessor().next() instanceof IfNode) {
298 AbstractBeginNode intermediateBegin = falseSuccessor();
299 IfNode nextIf = (IfNode) intermediateBegin.next();
300 double probabilityB = (1.0 - this.trueSuccessorProbability) * nextIf.trueSuccessorProbability;
301 if (this.trueSuccessorProbability < probabilityB) {
302 // Reordering of those two if statements is beneficial from the point of view of
303 // their probabilities.
304 if (prepareForSwap(tool, condition(), nextIf.condition())) {
305 // Reordering is allowed from (if1 => begin => if2) to (if2 => begin => if1).
306 assert intermediateBegin.next() == nextIf;
307 AbstractBeginNode bothFalseBegin = nextIf.falseSuccessor();
308 nextIf.setFalseSuccessor(null);
309 intermediateBegin.setNext(null);
310 this.setFalseSuccessor(null);
311
312 this.replaceAtPredecessor(nextIf);
313 nextIf.setFalseSuccessor(intermediateBegin);
314 intermediateBegin.setNext(this);
315 this.setFalseSuccessor(bothFalseBegin);
316
317 NodeSourcePosition intermediateBeginPosition = intermediateBegin.getNodeSourcePosition();
318 intermediateBegin.setNodeSourcePosition(bothFalseBegin.getNodeSourcePosition());
319 bothFalseBegin.setNodeSourcePosition(intermediateBeginPosition);
320
321 nextIf.setTrueSuccessorProbability(probabilityB);
322 if (probabilityB == 1.0) {
323 this.setTrueSuccessorProbability(0.0);
324 } else {
325 double newProbability = this.trueSuccessorProbability / (1.0 - probabilityB);
326 this.setTrueSuccessorProbability(Math.min(1.0, newProbability));
327 }
328 return;
329 }
330 }
331 }
332
333 if (tryEliminateBoxedReferenceEquals(tool)) {
334 return;
335 }
336 }
337
338 private boolean isUnboxedFrom(MetaAccessProvider meta, NodeView view, ValueNode x, ValueNode src) {
339 if (x == src) {
340 return true;
341 } else if (x instanceof UnboxNode) {
342 return isUnboxedFrom(meta, view, ((UnboxNode) x).getValue(), src);
343 } else if (x instanceof PiNode) {
344 PiNode pi = (PiNode) x;
345 return isUnboxedFrom(meta, view, pi.getOriginalNode(), src);
346 } else if (x instanceof LoadFieldNode) {
347 LoadFieldNode load = (LoadFieldNode) x;
348 ResolvedJavaType integerType = meta.lookupJavaType(Integer.class);
349 if (load.getValue().stamp(view).javaType(meta).equals(integerType)) {
350 return isUnboxedFrom(meta, view, load.getValue(), src);
351 } else {
352 return false;
353 }
354 } else {
355 return false;
356 }
357 }
358
359 /**
360 * Attempts to replace the following pattern:
361 *
362 * <pre>
363 * Integer x = ...;
364 * Integer y = ...;
365 * if ((x == y) || x.equals(y)) { ... }
366 * </pre>
367 *
368 * with:
369 *
370 * <pre>
371 * Integer x = ...;
372 * Integer y = ...;
373 * if (x.equals(y)) { ... }
374 * </pre>
375 *
376 * whenever the probability that the reference check will pass is relatively small.
377 *
378 * See GR-1315 for more information.
379 */
380 private boolean tryEliminateBoxedReferenceEquals(SimplifierTool tool) {
381 if (!(condition instanceof ObjectEqualsNode)) {
382 return false;
383 }
384
385 MetaAccessProvider meta = tool.getMetaAccess();
386 ObjectEqualsNode equalsCondition = (ObjectEqualsNode) condition;
387 ValueNode x = equalsCondition.getX();
388 ValueNode y = equalsCondition.getY();
389 ResolvedJavaType integerType = meta.lookupJavaType(Integer.class);
390
391 // At least one argument for reference equal must be a boxed primitive.
392 NodeView view = NodeView.from(tool);
393 if (!x.stamp(view).javaType(meta).equals(integerType) && !y.stamp(view).javaType(meta).equals(integerType)) {
394 return false;
395 }
396
397 // The reference equality check is usually more efficient compared to a boxing check.
398 // The success of the reference equals must therefore be relatively rare, otherwise it makes
399 // no sense to eliminate it.
400 if (getTrueSuccessorProbability() > 0.4) {
401 return false;
402 }
403
404 // True branch must be empty.
405 if (trueSuccessor instanceof BeginNode || trueSuccessor instanceof LoopExitNode) {
406 if (trueSuccessor.next() instanceof EndNode) {
407 // Empty true branch.
408 } else {
409 return false;
410 }
411 } else {
412 return false;
413 }
414
415 // False branch must only check the unboxed values.
416 UnboxNode unbox = null;
417 FixedGuardNode unboxCheck = null;
418 for (FixedNode node : falseSuccessor.getBlockNodes()) {
419 if (!(node instanceof BeginNode || node instanceof UnboxNode || node instanceof FixedGuardNode || node instanceof EndNode ||
420 node instanceof LoadFieldNode || node instanceof LoopExitNode)) {
421 return false;
422 }
423 if (node instanceof UnboxNode) {
424 if (unbox == null) {
425 unbox = (UnboxNode) node;
426 } else {
427 return false;
428 }
429 }
430 if (!(node instanceof FixedGuardNode)) {
431 continue;
432 }
433 FixedGuardNode fixed = (FixedGuardNode) node;
434 if (!(fixed.condition() instanceof IntegerEqualsNode)) {
435 continue;
436 }
437 IntegerEqualsNode equals = (IntegerEqualsNode) fixed.condition();
438 if ((isUnboxedFrom(meta, view, equals.getX(), x) && isUnboxedFrom(meta, view, equals.getY(), y)) ||
439 (isUnboxedFrom(meta, view, equals.getX(), y) && isUnboxedFrom(meta, view, equals.getY(), x))) {
440 unboxCheck = fixed;
441 }
442 }
443 if (unbox == null || unboxCheck == null) {
444 return false;
445 }
446
447 // Falsify the reference check.
448 setCondition(graph().addOrUniqueWithInputs(LogicConstantNode.contradiction()));
449
450 return true;
451 }
452
453 /**
454 * Try to optimize this as if it were a {@link ConditionalNode}.
455 */
456 private boolean conditionalNodeOptimization(SimplifierTool tool) {
457 if (trueSuccessor().next() instanceof AbstractEndNode && falseSuccessor().next() instanceof AbstractEndNode) {
458 AbstractEndNode trueEnd = (AbstractEndNode) trueSuccessor().next();
459 AbstractEndNode falseEnd = (AbstractEndNode) falseSuccessor().next();
460 if (trueEnd.merge() != falseEnd.merge()) {
461 return false;
462 }
463 if (!(trueEnd.merge() instanceof MergeNode)) {
464 return false;
465 }
466 MergeNode merge = (MergeNode) trueEnd.merge();
467 if (merge.usages().count() != 1 || merge.phis().count() != 1) {
468 return false;
469 }
470
471 if (trueSuccessor().anchored().isNotEmpty() || falseSuccessor().anchored().isNotEmpty()) {
472 return false;
473 }
474
475 PhiNode phi = merge.phis().first();
476 ValueNode falseValue = phi.valueAt(falseEnd);
477 ValueNode trueValue = phi.valueAt(trueEnd);
478
479 NodeView view = NodeView.from(tool);
480 ValueNode result = ConditionalNode.canonicalizeConditional(condition, trueValue, falseValue, phi.stamp(view), view);
481 if (result != null) {
482 /*
483 * canonicalizeConditional returns possibly new nodes so add them to the graph.
484 */
485 if (result.graph() == null) {
486 result = graph().addOrUniqueWithInputs(result);
487 }
488 result = proxyReplacement(result);
489 /*
490 * This optimization can be performed even if multiple values merge at this phi
491 * since the two inputs get simplified into one.
492 */
493 phi.setValueAt(trueEnd, result);
494 removeThroughFalseBranch(tool, merge);
495 return true;
496 }
497 }
498
499 return false;
500 }
501
502 private void pushNodesThroughIf(SimplifierTool tool) {
503 assert trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages();
504 // push similar nodes upwards through the if, thereby deduplicating them
505 do {
506 AbstractBeginNode trueSucc = trueSuccessor();
507 AbstractBeginNode falseSucc = falseSuccessor();
508 if (trueSucc instanceof BeginNode && falseSucc instanceof BeginNode && trueSucc.next() instanceof FixedWithNextNode && falseSucc.next() instanceof FixedWithNextNode) {
509 FixedWithNextNode trueNext = (FixedWithNextNode) trueSucc.next();
510 FixedWithNextNode falseNext = (FixedWithNextNode) falseSucc.next();
511 NodeClass<?> nodeClass = trueNext.getNodeClass();
512 if (trueNext.getClass() == falseNext.getClass()) {
513 if (trueNext instanceof AbstractBeginNode) {
514 // Cannot do this optimization for begin nodes, because it could
515 // move guards above the if that need to stay below a branch.
516 } else if (nodeClass.equalInputs(trueNext, falseNext) && trueNext.valueEquals(falseNext)) {
517 falseNext.replaceAtUsages(trueNext);
518 graph().removeFixed(falseNext);
519 GraphUtil.unlinkFixedNode(trueNext);
520 graph().addBeforeFixed(this, trueNext);
521 for (Node usage : trueNext.usages().snapshot()) {
522 if (usage.isAlive()) {
523 NodeClass<?> usageNodeClass = usage.getNodeClass();
524 if (usageNodeClass.valueNumberable() && !usageNodeClass.isLeafNode()) {
525 Node newNode = graph().findDuplicate(usage);
526 if (newNode != null) {
527 usage.replaceAtUsagesAndDelete(newNode);
528 }
529 }
530 if (usage.isAlive()) {
531 tool.addToWorkList(usage);
532 }
533 }
534 }
535 continue;
536 }
537 }
538 }
539 break;
540 } while (true);
541 }
542
543 /**
544 * Recognize a couple patterns that can be merged into an unsigned compare.
545 *
546 * @param tool
547 * @return true if a replacement was done.
548 */
549 @SuppressWarnings("try")
550 private boolean checkForUnsignedCompare(SimplifierTool tool) {
551 assert trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages();
552 if (condition() instanceof IntegerLessThanNode) {
553 NodeView view = NodeView.from(tool);
554 IntegerLessThanNode lessThan = (IntegerLessThanNode) condition();
555 Constant y = lessThan.getY().stamp(view).asConstant();
556 if (y instanceof PrimitiveConstant && ((PrimitiveConstant) y).asLong() == 0 && falseSuccessor().next() instanceof IfNode) {
557 IfNode ifNode2 = (IfNode) falseSuccessor().next();
558 if (ifNode2.condition() instanceof IntegerLessThanNode) {
559 IntegerLessThanNode lessThan2 = (IntegerLessThanNode) ifNode2.condition();
560 AbstractBeginNode falseSucc = ifNode2.falseSuccessor();
561 AbstractBeginNode trueSucc = ifNode2.trueSuccessor();
562 IntegerBelowNode below = null;
563 /*
564 * Convert x >= 0 && x < positive which is represented as !(x < 0) && x <
565 * <positive> into an unsigned compare.
566 */
567 if (lessThan2.getX() == lessThan.getX() && lessThan2.getY().stamp(view) instanceof IntegerStamp &&
568 ((IntegerStamp) lessThan2.getY().stamp(view)).isPositive() &&
569 sameDestination(trueSuccessor(), ifNode2.falseSuccessor)) {
570 below = graph().unique(new IntegerBelowNode(lessThan2.getX(), lessThan2.getY()));
571 // swap direction
572 AbstractBeginNode tmp = falseSucc;
573 falseSucc = trueSucc;
574 trueSucc = tmp;
575 } else if (lessThan2.getY() == lessThan.getX() && sameDestination(trueSuccessor(), ifNode2.trueSuccessor)) {
576 /*
577 * Convert x >= 0 && x <= positive which is represented as !(x < 0) &&
578 * !(<positive> > x), into x <| positive + 1. This can only be done for
579 * constants since there isn't a IntegerBelowEqualThanNode but that doesn't
580 * appear to be interesting.
581 */
582 JavaConstant positive = lessThan2.getX().asJavaConstant();
583 if (positive != null && positive.asLong() > 0 && positive.asLong() < positive.getJavaKind().getMaxValue()) {
584 ConstantNode newLimit = ConstantNode.forIntegerStamp(lessThan2.getX().stamp(view), positive.asLong() + 1, graph());
585 below = graph().unique(new IntegerBelowNode(lessThan.getX(), newLimit));
586 }
587 }
588 if (below != null) {
589 try (DebugCloseable position = ifNode2.withNodeSourcePosition()) {
590 ifNode2.setTrueSuccessor(null);
591 ifNode2.setFalseSuccessor(null);
592
593 IfNode newIfNode = graph().add(new IfNode(below, falseSucc, trueSucc, 1 - trueSuccessorProbability));
594 // Remove the < 0 test.
595 tool.deleteBranch(trueSuccessor);
596 graph().removeSplit(this, falseSuccessor);
597
598 // Replace the second test with the new one.
599 ifNode2.predecessor().replaceFirstSuccessor(ifNode2, newIfNode);
600 ifNode2.safeDelete();
601 return true;
602 }
603 }
604 }
605 }
606 }
607 return false;
608 }
609
610 /**
611 * Check it these two blocks end up at the same place. Meeting at the same merge, or
612 * deoptimizing in the same way.
613 */
614 private static boolean sameDestination(AbstractBeginNode succ1, AbstractBeginNode succ2) {
615 Node next1 = succ1.next();
616 Node next2 = succ2.next();
617 if (next1 instanceof EndNode && next2 instanceof EndNode) {
618 EndNode end1 = (EndNode) next1;
619 EndNode end2 = (EndNode) next2;
620 if (end1.merge() == end2.merge()) {
621 for (PhiNode phi : end1.merge().phis()) {
622 if (phi.valueAt(end1) != phi.valueAt(end2)) {
623 return false;
624 }
625 }
626 // They go to the same MergeNode and merge the same values
627 return true;
628 }
629 } else if (next1 instanceof DeoptimizeNode && next2 instanceof DeoptimizeNode) {
630 DeoptimizeNode deopt1 = (DeoptimizeNode) next1;
631 DeoptimizeNode deopt2 = (DeoptimizeNode) next2;
632 if (deopt1.getReason() == deopt2.getReason() && deopt1.getAction() == deopt2.getAction()) {
633 // Same deoptimization reason and action.
634 return true;
635 }
636 } else if (next1 instanceof LoopExitNode && next2 instanceof LoopExitNode) {
637 LoopExitNode exit1 = (LoopExitNode) next1;
638 LoopExitNode exit2 = (LoopExitNode) next2;
639 if (exit1.loopBegin() == exit2.loopBegin() && exit1.stateAfter() == exit2.stateAfter() && exit1.stateAfter() == null && sameDestination(exit1, exit2)) {
640 // Exit the same loop and end up at the same place.
641 return true;
642 }
643 } else if (next1 instanceof ReturnNode && next2 instanceof ReturnNode) {
644 ReturnNode exit1 = (ReturnNode) next1;
645 ReturnNode exit2 = (ReturnNode) next2;
646 if (exit1.result() == exit2.result()) {
647 // Exit the same loop and end up at the same place.
648 return true;
649 }
650 }
651 return false;
652 }
653
654 private static boolean prepareForSwap(SimplifierTool tool, LogicNode a, LogicNode b) {
655 DebugContext debug = a.getDebug();
656 if (a instanceof InstanceOfNode) {
657 InstanceOfNode instanceOfA = (InstanceOfNode) a;
658 if (b instanceof IsNullNode) {
659 IsNullNode isNullNode = (IsNullNode) b;
660 if (isNullNode.getValue() == instanceOfA.getValue()) {
661 debug.log("Can swap instanceof and isnull if");
662 return true;
663 }
664 } else if (b instanceof InstanceOfNode) {
665 InstanceOfNode instanceOfB = (InstanceOfNode) b;
666 if (instanceOfA.getValue() == instanceOfB.getValue() && !instanceOfA.type().getType().isInterface() && !instanceOfB.type().getType().isInterface() &&
667 !instanceOfA.type().getType().isAssignableFrom(instanceOfB.type().getType()) && !instanceOfB.type().getType().isAssignableFrom(instanceOfA.type().getType())) {
668 // Two instanceof on the same value with mutually exclusive types.
669 debug.log("Can swap instanceof for types %s and %s", instanceOfA.type(), instanceOfB.type());
670 return true;
671 }
672 }
673 } else if (a instanceof CompareNode) {
674 CompareNode compareA = (CompareNode) a;
675 Condition conditionA = compareA.condition().asCondition();
676 if (compareA.unorderedIsTrue()) {
677 return false;
678 }
679 if (b instanceof CompareNode) {
680 CompareNode compareB = (CompareNode) b;
681 if (compareA == compareB) {
682 debug.log("Same conditions => do not swap and leave the work for global value numbering.");
683 return false;
684 }
685 if (compareB.unorderedIsTrue()) {
686 return false;
687 }
688 Condition comparableCondition = null;
689 Condition conditionB = compareB.condition().asCondition();
690 if (compareB.getX() == compareA.getX() && compareB.getY() == compareA.getY()) {
691 comparableCondition = conditionB;
692 } else if (compareB.getX() == compareA.getY() && compareB.getY() == compareA.getX()) {
693 comparableCondition = conditionB.mirror();
694 }
695
696 if (comparableCondition != null) {
697 Condition combined = conditionA.join(comparableCondition);
698 if (combined == null) {
699 // The two conditions are disjoint => can reorder.
700 debug.log("Can swap disjoint coditions on same values: %s and %s", conditionA, comparableCondition);
701 return true;
702 }
703 } else if (conditionA == Condition.EQ && conditionB == Condition.EQ) {
704 boolean canSwap = false;
705 if ((compareA.getX() == compareB.getX() && valuesDistinct(tool, compareA.getY(), compareB.getY()))) {
706 canSwap = true;
707 } else if ((compareA.getX() == compareB.getY() && valuesDistinct(tool, compareA.getY(), compareB.getX()))) {
708 canSwap = true;
709 } else if ((compareA.getY() == compareB.getX() && valuesDistinct(tool, compareA.getX(), compareB.getY()))) {
710 canSwap = true;
711 } else if ((compareA.getY() == compareB.getY() && valuesDistinct(tool, compareA.getX(), compareB.getX()))) {
712 canSwap = true;
713 }
714
715 if (canSwap) {
716 debug.log("Can swap equality condition with one shared and one disjoint value.");
717 return true;
718 }
719 }
720 }
721 }
722
723 return false;
724 }
725
726 private static boolean valuesDistinct(SimplifierTool tool, ValueNode a, ValueNode b) {
727 if (a.isConstant() && b.isConstant()) {
728 Boolean equal = tool.getConstantReflection().constantEquals(a.asConstant(), b.asConstant());
729 if (equal != null) {
730 return !equal.booleanValue();
731 }
732 }
733
734 NodeView view = NodeView.from(tool);
735 Stamp stampA = a.stamp(view);
736 Stamp stampB = b.stamp(view);
737 return stampA.alwaysDistinct(stampB);
738 }
739
740 /**
741 * Tries to remove an empty if construct or replace an if construct with a materialization.
742 *
743 * @return true if a transformation was made, false otherwise
744 */
745 private boolean removeOrMaterializeIf(SimplifierTool tool) {
746 assert trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages();
747 if (trueSuccessor().next() instanceof AbstractEndNode && falseSuccessor().next() instanceof AbstractEndNode) {
748 AbstractEndNode trueEnd = (AbstractEndNode) trueSuccessor().next();
749 AbstractEndNode falseEnd = (AbstractEndNode) falseSuccessor().next();
750 AbstractMergeNode merge = trueEnd.merge();
751 if (merge == falseEnd.merge() && trueSuccessor().anchored().isEmpty() && falseSuccessor().anchored().isEmpty()) {
752 PhiNode singlePhi = null;
753 int distinct = 0;
754 for (PhiNode phi : merge.phis()) {
755 ValueNode trueValue = phi.valueAt(trueEnd);
756 ValueNode falseValue = phi.valueAt(falseEnd);
757 if (trueValue != falseValue) {
758 distinct++;
759 singlePhi = phi;
760 }
761 }
762 if (distinct == 0) {
763 /*
764 * Multiple phis but merging same values for true and false, so simply delete
765 * the path
766 */
767 removeThroughFalseBranch(tool, merge);
768 return true;
769 } else if (distinct == 1) {
770 ValueNode trueValue = singlePhi.valueAt(trueEnd);
771 ValueNode falseValue = singlePhi.valueAt(falseEnd);
772 ValueNode conditional = canonicalizeConditionalCascade(tool, trueValue, falseValue);
773 if (conditional != null) {
774 conditional = proxyReplacement(conditional);
775 singlePhi.setValueAt(trueEnd, conditional);
776 removeThroughFalseBranch(tool, merge);
777 return true;
778 }
779 }
780 }
781 }
782 if (trueSuccessor().next() instanceof ReturnNode && falseSuccessor().next() instanceof ReturnNode) {
783 ReturnNode trueEnd = (ReturnNode) trueSuccessor().next();
784 ReturnNode falseEnd = (ReturnNode) falseSuccessor().next();
785 ValueNode trueValue = trueEnd.result();
786 ValueNode falseValue = falseEnd.result();
787 ValueNode value = null;
788 if (trueValue != null) {
789 if (trueValue == falseValue) {
790 value = trueValue;
791 } else {
792 value = canonicalizeConditionalCascade(tool, trueValue, falseValue);
793 if (value == null) {
794 return false;
795 }
796 }
797 }
798 ReturnNode newReturn = graph().add(new ReturnNode(value));
799 replaceAtPredecessor(newReturn);
800 GraphUtil.killCFG(this);
801 return true;
802 }
803 return false;
804 }
805
806 private ValueNode proxyReplacement(ValueNode replacement) {
807 /*
808 * Special case: Every empty diamond we collapse to a conditional node can potentially
809 * contain loop exit nodes on both branches. See the graph below: The two loop exits
810 * (instanceof begin node) exit the same loop. The resulting phi is defined outside the
811 * loop, but the resulting conditional node will be inside the loop, so we need to proxy the
812 * resulting conditional node. Callers of this method ensure that true and false successor
813 * have no usages, therefore a and b in the graph below can never be proxies themselves.
814 */
815 // @formatter:off
816 // +--+
817 // |If|
818 // +--+ +-----+ +-----+
819 // +----+ +----+ | a | | b |
820 // |Lex | |Lex | +----^+ +^----+
821 // +----+ +----+ | |
822 // +-------+ +---+
823 // | Merge +---------+Phi|
824 // +-------+ +---+
825 // @formatter:on
826 if (this.graph().hasValueProxies()) {
827 if (trueSuccessor instanceof LoopExitNode && falseSuccessor instanceof LoopExitNode) {
828 assert ((LoopExitNode) trueSuccessor).loopBegin() == ((LoopExitNode) falseSuccessor).loopBegin();
829 /*
830 * we can collapse all proxy nodes on one loop exit, the surviving one, which will
831 * be the true successor
832 */
833 if (falseSuccessor.anchored().isEmpty() && falseSuccessor.usages().isNotEmpty()) {
834 for (Node n : falseSuccessor.usages().snapshot()) {
835 assert n instanceof ProxyNode;
836 ((ProxyNode) n).setProxyPoint((LoopExitNode) trueSuccessor);
837 }
838 }
839 /*
840 * The true successor (surviving loop exit) can have usages, namely proxy nodes, the
841 * false successor however, must not have usages any more after the code above
842 */
843 assert trueSuccessor.anchored().isEmpty() && falseSuccessor.usages().isEmpty();
844 return this.graph().addOrUnique(new ValueProxyNode(replacement, (LoopExitNode) trueSuccessor));
845 }
846 }
847 return replacement;
848 }
849
850 protected void removeThroughFalseBranch(SimplifierTool tool, AbstractMergeNode merge) {
851 AbstractBeginNode trueBegin = trueSuccessor();
852 LogicNode conditionNode = condition();
853 graph().removeSplitPropagate(this, trueBegin);
854 tool.addToWorkList(trueBegin);
855 if (conditionNode != null) {
856 GraphUtil.tryKillUnused(conditionNode);
857 }
858 if (merge.isAlive() && merge.forwardEndCount() > 1) {
859 for (FixedNode end : merge.forwardEnds()) {
860 Node cur = end;
861 while (cur != null && cur.predecessor() instanceof BeginNode) {
862 cur = cur.predecessor();
863 }
864 if (cur != null && cur.predecessor() instanceof IfNode) {
865 tool.addToWorkList(cur.predecessor());
866 }
867 }
868 }
869 }
870
871 private ValueNode canonicalizeConditionalCascade(SimplifierTool tool, ValueNode trueValue, ValueNode falseValue) {
872 if (trueValue.getStackKind() != falseValue.getStackKind()) {
873 return null;
874 }
875 if (trueValue.getStackKind() != JavaKind.Int && trueValue.getStackKind() != JavaKind.Long) {
876 return null;
877 }
878 if (trueValue.isConstant() && falseValue.isConstant()) {
879 return graph().unique(new ConditionalNode(condition(), trueValue, falseValue));
880 } else if (!graph().isAfterExpandLogic()) {
881 ConditionalNode conditional = null;
882 ValueNode constant = null;
883 boolean negateCondition;
884 if (trueValue instanceof ConditionalNode && falseValue.isConstant()) {
885 conditional = (ConditionalNode) trueValue;
886 constant = falseValue;
887 negateCondition = true;
888 } else if (falseValue instanceof ConditionalNode && trueValue.isConstant()) {
889 conditional = (ConditionalNode) falseValue;
890 constant = trueValue;
891 negateCondition = false;
892 } else {
893 return null;
894 }
895 boolean negateConditionalCondition = false;
896 ValueNode otherValue = null;
897 if (constant == conditional.trueValue()) {
898 otherValue = conditional.falseValue();
899 negateConditionalCondition = false;
900 } else if (constant == conditional.falseValue()) {
901 otherValue = conditional.trueValue();
902 negateConditionalCondition = true;
903 }
904 if (otherValue != null && otherValue.isConstant()) {
905 double shortCutProbability = probability(trueSuccessor());
906 LogicNode newCondition = LogicNode.or(condition(), negateCondition, conditional.condition(), negateConditionalCondition, shortCutProbability);
907 return graph().unique(new ConditionalNode(newCondition, constant, otherValue));
908 } else if (constant.isJavaConstant() && conditional.trueValue().isJavaConstant() && conditional.falseValue().isJavaConstant() && condition() instanceof CompareNode &&
909 conditional.condition() instanceof CompareNode) {
910 Condition cond1 = ((CompareNode) condition()).condition().asCondition();
911 if (negateCondition) {
912 cond1 = cond1.negate();
913 }
914 // cond1 is EQ, NE, LT, or GE
915 Condition cond2 = ((CompareNode) conditional.condition()).condition().asCondition();
916 ValueNode x = ((CompareNode) condition()).getX();
917 ValueNode y = ((CompareNode) condition()).getY();
918 ValueNode x2 = ((CompareNode) conditional.condition()).getX();
919 ValueNode y2 = ((CompareNode) conditional.condition()).getY();
920 // `x cond1 y ? c1 : (x2 cond2 y2 ? c2 : c3)`
921 boolean sameVars = x == x2 && y == y2;
922 if (!sameVars && x == y2 && y == x2) {
923 sameVars = true;
924 cond2 = cond2.mirror();
925 }
926 // cond2 is EQ, LT, or GT
927 if (sameVars) {
928 JavaKind stackKind = conditional.trueValue().stamp(NodeView.from(tool)).getStackKind();
929 assert !stackKind.isNumericFloat();
930 long c1 = constant.asJavaConstant().asLong();
931 long c2 = conditional.trueValue().asJavaConstant().asLong();
932 long c3 = conditional.falseValue().asJavaConstant().asLong();
933 // `x cond1 y ? c1 : (x cond2 y ? c2 : c3)`
934 if (cond1 == Condition.GE && cond2 == Condition.LT) {
935 // x >= y ? v1 : (x < y ? v2 : v3) => x >= y ? v1 : v2
936 return graph().unique(new ConditionalNode(condition(), conditional.trueValue(), constant));
937 } else if (cond1 == Condition.GE && cond2 == Condition.GT) {
938 // x >= y ? v1 : (x > y ? v2 : v3) => x >= y ? v1 : v3
939 return graph().unique(new ConditionalNode(condition(), conditional.falseValue(), constant));
940 } else if (cond1 == Condition.EQ && cond2 == Condition.EQ) {
941 // x == y ? v1 : (x == y ? v2 : v3) => x == y ? v1 : v3
942 return graph().unique(new ConditionalNode(condition(), conditional.falseValue(), constant));
943 } else if (cond1 == Condition.NE && cond2 == Condition.LT) {
944 // x != y ? v1 : (x < y ? v2 : v3) => x != y ? v1 : v3
945 return graph().unique(new ConditionalNode(condition(), conditional.falseValue(), constant));
946 } else if (cond1 == Condition.LT && cond2 == Condition.EQ && c1 == -1 && c2 == 0 && c3 == 1) {
947 // x < y ? -1 : (x == y ? 0 : 1) => x cmp y
948 return graph().unique(new NormalizeCompareNode(x, y, stackKind, false));
949 } else if (cond1 == Condition.LT && cond2 == Condition.EQ && c1 == 1 && c2 == 0 && c3 == -1) {
950 // x < y ? 1 : (x == y ? 0 : -1) => y cmp x
951 return graph().unique(new NormalizeCompareNode(y, x, stackKind, false));
952 } else if (cond1 == Condition.EQ && cond2 == Condition.LT && c1 == 0 && c2 == -1 && c3 == 1) {
953 // x == y ? 0 : (x < y ? -1 : 1) => x cmp y
954 return graph().unique(new NormalizeCompareNode(x, y, stackKind, false));
955 } else if (cond1 == Condition.EQ && cond2 == Condition.LT && c1 == 0 && c2 == 1 && c3 == -1) {
956 // x == y ? 0 : (x < y ? 1 : -1) => y cmp x
957 return graph().unique(new NormalizeCompareNode(y, x, stackKind, false));
958 } else if (cond1 == Condition.EQ && cond2 == Condition.GT && c1 == 0 && c2 == -1 && c3 == 1) {
959 // x == y ? 0 : (x > y ? -1 : 1) => y cmp x
960 return graph().unique(new NormalizeCompareNode(y, x, stackKind, false));
961 } else if (cond1 == Condition.EQ && cond2 == Condition.GT && c1 == 0 && c2 == 1 && c3 == -1) {
962 // x == y ? 0 : (x > y ? 1 : -1) => x cmp y
963 return graph().unique(new NormalizeCompareNode(x, y, stackKind, false));
964 } else if (cond1 == Condition.LT && cond2 == Condition.GT && c1 == 1 && c2 == -1 && c3 == 0) {
965 // x < y ? 1 : (x > y ? -1 : 0) => y cmp x
966 return graph().unique(new NormalizeCompareNode(y, x, stackKind, false));
967 } else if (cond1 == Condition.LT && cond2 == Condition.GT && c1 == -1 && c2 == 1 && c3 == 0) {
968 // x < y ? -1 : (x > y ? 1 : 0) => x cmp y
969 return graph().unique(new NormalizeCompareNode(x, y, stackKind, false));
970 }
971 }
972 }
973 }
974 return null;
975 }
976
977 /**
978 * Take an if that is immediately dominated by a merge with a single phi and split off any paths
979 * where the test would be statically decidable creating a new merge below the approriate side
980 * of the IfNode. Any undecidable tests will continue to use the original IfNode.
981 *
982 * @param tool
983 */
984 @SuppressWarnings("try")
985 private boolean splitIfAtPhi(SimplifierTool tool) {
986 if (graph().getGuardsStage().areFrameStatesAtSideEffects()) {
987 // Disabled until we make sure we have no FrameState-less merges at this stage
988 return false;
989 }
990
991 if (!(predecessor() instanceof MergeNode)) {
992 return false;
993 }
994 MergeNode merge = (MergeNode) predecessor();
995 if (merge.forwardEndCount() == 1) {
996 // Don't bother.
997 return false;
998 }
999 if (merge.usages().count() != 1 || merge.phis().count() != 1) {
1000 return false;
1001 }
1002 if (merge.stateAfter() != null) {
1003 /* We'll get the chance to simplify this after frame state assignment. */
1004 return false;
1005 }
1006 PhiNode phi = merge.phis().first();
1007 if (phi.usages().count() != 1) {
1008 /*
1009 * For simplicity the below code assumes assumes the phi goes dead at the end so skip
1010 * this case.
1011 */
1012 return false;
1013 }
1014
1015 /*
1016 * Check that the condition uses the phi and that there is only one user of the condition
1017 * expression.
1018 */
1019 if (!conditionUses(condition(), phi)) {
1020 return false;
1021 }
1022
1023 /*
1024 * We could additionally filter for the case that at least some of the Phi inputs or one of
1025 * the condition inputs are constants but there are cases where a non-constant is
1026 * simplifiable, usually where the stamp allows the question to be answered.
1027 */
1028
1029 /* Each successor of the if gets a new merge if needed. */
1030 MergeNode trueMerge = null;
1031 MergeNode falseMerge = null;
1032 assert merge.stateAfter() == null;
1033
1034 for (EndNode end : merge.forwardEnds().snapshot()) {
1035 Node value = phi.valueAt(end);
1036 LogicNode result = computeCondition(tool, condition, phi, value);
1037 if (result instanceof LogicConstantNode) {
1038 merge.removeEnd(end);
1039 if (((LogicConstantNode) result).getValue()) {
1040 if (trueMerge == null) {
1041 trueMerge = insertMerge(trueSuccessor());
1042 }
1043 trueMerge.addForwardEnd(end);
1044 } else {
1045 if (falseMerge == null) {
1046 falseMerge = insertMerge(falseSuccessor());
1047 }
1048 falseMerge.addForwardEnd(end);
1049 }
1050 } else if (result != condition) {
1051 // Build a new IfNode using the new condition
1052 BeginNode trueBegin = graph().add(new BeginNode());
1053 trueBegin.setNodeSourcePosition(trueSuccessor().getNodeSourcePosition());
1054 BeginNode falseBegin = graph().add(new BeginNode());
1055 falseBegin.setNodeSourcePosition(falseSuccessor().getNodeSourcePosition());
1056
1057 if (result.graph() == null) {
1058 result = graph().addOrUniqueWithInputs(result);
1059 result.setNodeSourcePosition(condition.getNodeSourcePosition());
1060 }
1061 IfNode newIfNode = graph().add(new IfNode(result, trueBegin, falseBegin, trueSuccessorProbability));
1062 newIfNode.setNodeSourcePosition(getNodeSourcePosition());
1063 merge.removeEnd(end);
1064 ((FixedWithNextNode) end.predecessor()).setNext(newIfNode);
1065
1066 if (trueMerge == null) {
1067 trueMerge = insertMerge(trueSuccessor());
1068 }
1069 trueBegin.setNext(graph().add(new EndNode()));
1070 trueMerge.addForwardEnd((EndNode) trueBegin.next());
1071
1072 if (falseMerge == null) {
1073 falseMerge = insertMerge(falseSuccessor());
1074 }
1075 falseBegin.setNext(graph().add(new EndNode()));
1076 falseMerge.addForwardEnd((EndNode) falseBegin.next());
1077
1078 end.safeDelete();
1079 }
1080 }
1081
1082 transferProxies(trueSuccessor(), trueMerge);
1083 transferProxies(falseSuccessor(), falseMerge);
1084
1085 cleanupMerge(merge);
1086 cleanupMerge(trueMerge);
1087 cleanupMerge(falseMerge);
1088
1089 return true;
1090 }
1091
1092 /**
1093 * @param condition
1094 * @param phi
1095 * @return true if the passed in {@code condition} uses {@code phi} and the condition is only
1096 * used once. Since the phi will go dead the condition using it will also have to be
1097 * dead after the optimization.
1098 */
1099 private static boolean conditionUses(LogicNode condition, PhiNode phi) {
1100 if (condition.usages().count() != 1) {
1101 return false;
1102 }
1103 if (condition instanceof ShortCircuitOrNode) {
1104 if (condition.graph().getGuardsStage().areDeoptsFixed()) {
1105 /*
1106 * It can be unsafe to simplify a ShortCircuitOr before deopts are fixed because
1107 * conversion to guards assumes that all the required conditions are being tested.
1108 * Simplfying the condition based on context before this happens may lose a
1109 * condition.
1110 */
1111 ShortCircuitOrNode orNode = (ShortCircuitOrNode) condition;
1112 return (conditionUses(orNode.x, phi) || conditionUses(orNode.y, phi));
1113 }
1114 } else if (condition instanceof Canonicalizable.Unary<?>) {
1115 Canonicalizable.Unary<?> unary = (Canonicalizable.Unary<?>) condition;
1116 return unary.getValue() == phi;
1117 } else if (condition instanceof Canonicalizable.Binary<?>) {
1118 Canonicalizable.Binary<?> binary = (Canonicalizable.Binary<?>) condition;
1119 return binary.getX() == phi || binary.getY() == phi;
1120 }
1121 return false;
1122 }
1123
1124 /**
1125 * Canonicalize {@code} condition using {@code value} in place of {@code phi}.
1126 *
1127 * @param tool
1128 * @param condition
1129 * @param phi
1130 * @param value
1131 * @return an improved LogicNode or the original condition
1132 */
1133 @SuppressWarnings("unchecked")
1134 private static LogicNode computeCondition(SimplifierTool tool, LogicNode condition, PhiNode phi, Node value) {
1135 if (condition instanceof ShortCircuitOrNode) {
1136 if (condition.graph().getGuardsStage().areDeoptsFixed() && !condition.graph().isAfterExpandLogic()) {
1137 ShortCircuitOrNode orNode = (ShortCircuitOrNode) condition;
1138 LogicNode resultX = computeCondition(tool, orNode.x, phi, value);
1139 LogicNode resultY = computeCondition(tool, orNode.y, phi, value);
1140 if (resultX != orNode.x || resultY != orNode.y) {
1141 LogicNode result = orNode.canonical(tool, resultX, resultY);
1142 if (result != orNode) {
1143 return result;
1144 }
1145 /*
1146 * Create a new node to carry the optimized inputs.
1147 */
1148 ShortCircuitOrNode newOr = new ShortCircuitOrNode(resultX, orNode.xNegated, resultY,
1149 orNode.yNegated, orNode.getShortCircuitProbability());
1150 return newOr.canonical(tool);
1151 }
1152 return orNode;
1153 }
1154 } else if (condition instanceof Canonicalizable.Binary<?>) {
1155 Canonicalizable.Binary<Node> compare = (Canonicalizable.Binary<Node>) condition;
1156 if (compare.getX() == phi) {
1157 return (LogicNode) compare.canonical(tool, value, compare.getY());
1158 } else if (compare.getY() == phi) {
1159 return (LogicNode) compare.canonical(tool, compare.getX(), value);
1160 }
1161 } else if (condition instanceof Canonicalizable.Unary<?>) {
1162 Canonicalizable.Unary<Node> compare = (Canonicalizable.Unary<Node>) condition;
1163 if (compare.getValue() == phi) {
1164 return (LogicNode) compare.canonical(tool, value);
1165 }
1166 }
1167 if (condition instanceof Canonicalizable) {
1168 return (LogicNode) ((Canonicalizable) condition).canonical(tool);
1169 }
1170 return condition;
1171 }
1172
1173 private static void transferProxies(AbstractBeginNode successor, MergeNode falseMerge) {
1174 if (successor instanceof LoopExitNode && falseMerge != null) {
1175 LoopExitNode loopExitNode = (LoopExitNode) successor;
1176 for (ProxyNode proxy : loopExitNode.proxies().snapshot()) {
1177 proxy.replaceFirstInput(successor, falseMerge);
1178 }
1179 }
1180 }
1181
1182 private void cleanupMerge(MergeNode merge) {
1183 if (merge != null && merge.isAlive()) {
1184 if (merge.forwardEndCount() == 0) {
1185 GraphUtil.killCFG(merge);
1186 } else if (merge.forwardEndCount() == 1) {
1187 graph().reduceTrivialMerge(merge);
1188 }
1189 }
1190 }
1191
1192 @SuppressWarnings("try")
1193 private MergeNode insertMerge(AbstractBeginNode begin) {
1194 MergeNode merge = graph().add(new MergeNode());
1195 if (!begin.anchored().isEmpty()) {
1196 Object before = null;
1197 before = begin.anchored().snapshot();
1198 begin.replaceAtUsages(InputType.Guard, merge);
1199 begin.replaceAtUsages(InputType.Anchor, merge);
1200 assert begin.anchored().isEmpty() : before + " " + begin.anchored().snapshot();
1201 }
1202
1203 AbstractBeginNode theBegin = begin;
1204 if (begin instanceof LoopExitNode) {
1205 // Insert an extra begin to make it easier.
1206 try (DebugCloseable position = begin.withNodeSourcePosition()) {
1207 theBegin = graph().add(new BeginNode());
1208 begin.replaceAtPredecessor(theBegin);
1209 theBegin.setNext(begin);
1210 }
1211 }
1212 FixedNode next = theBegin.next();
1213 next.replaceAtPredecessor(merge);
1214 theBegin.setNext(graph().add(new EndNode()));
1215 merge.addForwardEnd((EndNode) theBegin.next());
1216 merge.setNext(next);
1217 return merge;
1218 }
1219
1220 /**
1221 * Tries to connect code that initializes a variable directly with the successors of an if
1222 * construct that switches on the variable. For example, the pseudo code below:
1223 *
1224 * <pre>
1225 * contains(list, e, yes, no) {
1226 * if (list == null || e == null) {
1227 * condition = false;
1228 * } else {
1229 * condition = false;
1230 * for (i in list) {
1231 * if (i.equals(e)) {
1232 * condition = true;
1233 * break;
1234 * }
1235 * }
1236 * }
1237 * if (condition) {
1238 * return yes;
1239 * } else {
1240 * return no;
1241 * }
1242 * }
1243 * </pre>
1244 *
1245 * will be transformed into:
1246 *
1247 * <pre>
1248 * contains(list, e, yes, no) {
1249 * if (list == null || e == null) {
1250 * return no;
1251 * } else {
1252 * condition = false;
1253 * for (i in list) {
1254 * if (i.equals(e)) {
1255 * return yes;
1256 * }
1257 * }
1258 * return no;
1259 * }
1260 * }
1261 * </pre>
1262 *
1263 * @return true if a transformation was made, false otherwise
1264 */
1265 private boolean removeIntermediateMaterialization(SimplifierTool tool) {
1266 if (!(predecessor() instanceof AbstractMergeNode) || predecessor() instanceof LoopBeginNode) {
1267 return false;
1268 }
1269 AbstractMergeNode merge = (AbstractMergeNode) predecessor();
1270
1271 if (!(condition() instanceof CompareNode)) {
1272 return false;
1273 }
1274
1275 CompareNode compare = (CompareNode) condition();
1276 if (compare.getUsageCount() != 1) {
1277 return false;
1278 }
1279
1280 // Only consider merges with a single usage that is both a phi and an operand of the
1281 // comparison
1282 NodeIterable<Node> mergeUsages = merge.usages();
1283 if (mergeUsages.count() != 1) {
1284 return false;
1285 }
1286 Node singleUsage = mergeUsages.first();
1287 if (!(singleUsage instanceof ValuePhiNode) || (singleUsage != compare.getX() && singleUsage != compare.getY())) {
1288 return false;
1289 }
1290
1291 // Ensure phi is used by at most the comparison and the merge's frame state (if any)
1292 ValuePhiNode phi = (ValuePhiNode) singleUsage;
1293 NodeIterable<Node> phiUsages = phi.usages();
1294 if (phiUsages.count() > 2) {
1295 return false;
1296 }
1297 for (Node usage : phiUsages) {
1298 if (usage != compare && usage != merge.stateAfter()) {
1299 return false;
1300 }
1301 }
1302
1303 List<EndNode> mergePredecessors = merge.cfgPredecessors().snapshot();
1304 assert phi.valueCount() == merge.forwardEndCount();
1305
1306 Constant[] xs = constantValues(compare.getX(), merge, false);
1307 Constant[] ys = constantValues(compare.getY(), merge, false);
1308 if (xs == null || ys == null) {
1309 return false;
1310 }
1311
1312 // Sanity check that both ends are not followed by a merge without frame state.
1313 if (!checkFrameState(trueSuccessor()) && !checkFrameState(falseSuccessor())) {
1314 return false;
1315 }
1316
1317 List<EndNode> falseEnds = new ArrayList<>(mergePredecessors.size());
1318 List<EndNode> trueEnds = new ArrayList<>(mergePredecessors.size());
1319 EconomicMap<AbstractEndNode, ValueNode> phiValues = EconomicMap.create(Equivalence.IDENTITY, mergePredecessors.size());
1320
1321 AbstractBeginNode oldFalseSuccessor = falseSuccessor();
1322 AbstractBeginNode oldTrueSuccessor = trueSuccessor();
1323
1324 setFalseSuccessor(null);
1325 setTrueSuccessor(null);
1326
1327 Iterator<EndNode> ends = mergePredecessors.iterator();
1328 for (int i = 0; i < xs.length; i++) {
1329 EndNode end = ends.next();
1330 phiValues.put(end, phi.valueAt(end));
1331 if (compare.condition().foldCondition(xs[i], ys[i], tool.getConstantReflection(), compare.unorderedIsTrue())) {
1332 trueEnds.add(end);
1333 } else {
1334 falseEnds.add(end);
1335 }
1336 }
1337 assert !ends.hasNext();
1338 assert falseEnds.size() + trueEnds.size() == xs.length;
1339
1340 connectEnds(falseEnds, phiValues, oldFalseSuccessor, merge, tool);
1341 connectEnds(trueEnds, phiValues, oldTrueSuccessor, merge, tool);
1342
1343 if (this.trueSuccessorProbability == 0.0) {
1344 for (AbstractEndNode endNode : trueEnds) {
1345 propagateZeroProbability(endNode);
1346 }
1347 }
1348
1349 if (this.trueSuccessorProbability == 1.0) {
1350 for (AbstractEndNode endNode : falseEnds) {
1351 propagateZeroProbability(endNode);
1352 }
1353 }
1354
1355 /*
1356 * Remove obsolete ends only after processing all ends, otherwise oldTrueSuccessor or
1357 * oldFalseSuccessor might have been removed if it is a LoopExitNode.
1358 */
1359 if (falseEnds.isEmpty()) {
1360 GraphUtil.killCFG(oldFalseSuccessor);
1361 }
1362 if (trueEnds.isEmpty()) {
1363 GraphUtil.killCFG(oldTrueSuccessor);
1364 }
1365 GraphUtil.killCFG(merge);
1366
1367 assert !merge.isAlive() : merge;
1368 assert !phi.isAlive() : phi;
1369 assert !compare.isAlive() : compare;
1370 assert !this.isAlive() : this;
1371
1372 return true;
1373 }
1374
1375 private void propagateZeroProbability(FixedNode startNode) {
1376 Node prev = null;
1377 for (FixedNode node : GraphUtil.predecessorIterable(startNode)) {
1378 if (node instanceof IfNode) {
1379 IfNode ifNode = (IfNode) node;
1380 if (ifNode.trueSuccessor() == prev) {
1381 if (ifNode.trueSuccessorProbability == 0.0) {
1382 return;
1383 } else if (ifNode.trueSuccessorProbability == 1.0) {
1384 continue;
1385 } else {
1386 ifNode.setTrueSuccessorProbability(0.0);
1387 return;
1388 }
1389 } else if (ifNode.falseSuccessor() == prev) {
1390 if (ifNode.trueSuccessorProbability == 1.0) {
1391 return;
1392 } else if (ifNode.trueSuccessorProbability == 0.0) {
1393 continue;
1394 } else {
1395 ifNode.setTrueSuccessorProbability(1.0);
1396 return;
1397 }
1398 } else {
1399 throw new GraalError("Illegal state");
1400 }
1401 } else if (node instanceof AbstractMergeNode && !(node instanceof LoopBeginNode)) {
1402 for (AbstractEndNode endNode : ((AbstractMergeNode) node).cfgPredecessors()) {
1403 propagateZeroProbability(endNode);
1404 }
1405 return;
1406 }
1407 prev = node;
1408 }
1409 }
1410
1411 private static boolean checkFrameState(FixedNode start) {
1412 FixedNode node = start;
1413 while (true) {
1414 if (node instanceof AbstractMergeNode) {
1415 AbstractMergeNode mergeNode = (AbstractMergeNode) node;
1416 if (mergeNode.stateAfter() == null) {
1417 return false;
1418 } else {
1419 return true;
1420 }
1421 } else if (node instanceof StateSplit) {
1422 StateSplit stateSplitNode = (StateSplit) node;
1423 if (stateSplitNode.stateAfter() != null) {
1424 return true;
1425 }
1426 }
1427
1428 if (node instanceof ControlSplitNode) {
1429 ControlSplitNode controlSplitNode = (ControlSplitNode) node;
1430 for (Node succ : controlSplitNode.cfgSuccessors()) {
1431 if (checkFrameState((FixedNode) succ)) {
1432 return true;
1433 }
1434 }
1435 return false;
1436 } else if (node instanceof FixedWithNextNode) {
1437 FixedWithNextNode fixedWithNextNode = (FixedWithNextNode) node;
1438 node = fixedWithNextNode.next();
1439 } else if (node instanceof AbstractEndNode) {
1440 AbstractEndNode endNode = (AbstractEndNode) node;
1441 node = endNode.merge();
1442 } else if (node instanceof ControlSinkNode) {
1443 return true;
1444 } else {
1445 return false;
1446 }
1447 }
1448 }
1449
1450 /**
1451 * Connects a set of ends to a given successor, inserting a merge node if there is more than one
1452 * end. If {@code ends} is not empty, then {@code successor} is added to {@code tool}'s
1453 * {@linkplain SimplifierTool#addToWorkList(org.graalvm.compiler.graph.Node) work list}.
1454 *
1455 * @param oldMerge the merge being removed
1456 * @param phiValues the values of the phi at the merge, keyed by the merge ends
1457 */
1458 private void connectEnds(List<EndNode> ends, EconomicMap<AbstractEndNode, ValueNode> phiValues, AbstractBeginNode successor, AbstractMergeNode oldMerge, SimplifierTool tool) {
1459 if (!ends.isEmpty()) {
1460 if (ends.size() == 1) {
1461 AbstractEndNode end = ends.get(0);
1462 ((FixedWithNextNode) end.predecessor()).setNext(successor);
1463 oldMerge.removeEnd(end);
1464 GraphUtil.killCFG(end);
1465 } else {
1466 // Need a new phi in case the frame state is used by more than the merge being
1467 // removed.
1468 NodeView view = NodeView.from(tool);
1469 AbstractMergeNode newMerge = graph().add(new MergeNode());
1470 PhiNode oldPhi = (PhiNode) oldMerge.usages().first();
1471 PhiNode newPhi = graph().addWithoutUnique(new ValuePhiNode(oldPhi.stamp(view), newMerge));
1472
1473 for (EndNode end : ends) {
1474 newPhi.addInput(phiValues.get(end));
1475 newMerge.addForwardEnd(end);
1476 }
1477
1478 FrameState stateAfter = oldMerge.stateAfter();
1479 if (stateAfter != null) {
1480 stateAfter = stateAfter.duplicate();
1481 stateAfter.replaceFirstInput(oldPhi, newPhi);
1482 newMerge.setStateAfter(stateAfter);
1483 }
1484
1485 newMerge.setNext(successor);
1486 }
1487 tool.addToWorkList(successor);
1488 }
1489 }
1490
1491 /**
1492 * Gets an array of constants derived from a node that is either a {@link ConstantNode} or a
1493 * {@link PhiNode} whose input values are all constants. The length of the returned array is
1494 * equal to the number of ends terminating in a given merge node.
1495 *
1496 * @return null if {@code node} is neither a {@link ConstantNode} nor a {@link PhiNode} whose
1497 * input values are all constants
1498 */
1499 public static Constant[] constantValues(ValueNode node, AbstractMergeNode merge, boolean allowNull) {
1500 if (node.isConstant()) {
1501 Constant[] result = new Constant[merge.forwardEndCount()];
1502 Arrays.fill(result, node.asConstant());
1503 return result;
1504 }
1505
1506 if (node instanceof PhiNode) {
1507 PhiNode phi = (PhiNode) node;
1508 if (phi.merge() == merge && phi instanceof ValuePhiNode && phi.valueCount() == merge.forwardEndCount()) {
1509 Constant[] result = new Constant[merge.forwardEndCount()];
1510 int i = 0;
1511 for (ValueNode n : phi.values()) {
1512 if (!allowNull && !n.isConstant()) {
1513 return null;
1514 }
1515 result[i++] = n.asConstant();
1516 }
1517 return result;
1518 }
1519 }
1520
1521 return null;
1522 }
1523
1524 @Override
1525 public AbstractBeginNode getPrimarySuccessor() {
1526 return null;
1527 }
1528
1529 public AbstractBeginNode getSuccessor(boolean result) {
1530 return result ? this.trueSuccessor() : this.falseSuccessor();
1531 }
1532
1533 @Override
1534 public boolean setProbability(AbstractBeginNode successor, double value) {
1535 if (successor == this.trueSuccessor()) {
1536 this.setTrueSuccessorProbability(value);
1537 return true;
1538 } else if (successor == this.falseSuccessor()) {
1539 this.setTrueSuccessorProbability(1.0 - value);
1540 return true;
1541 }
1542 return false;
1543 }
1544
1545 @Override
1546 public int getSuccessorCount() {
1547 return 2;
1548 }
1549 }