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