1 /*
2 * Copyright (c) 2009, 2019, 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.FloatStamp;
44 import org.graalvm.compiler.core.common.type.IntegerStamp;
45 import org.graalvm.compiler.core.common.type.PrimitiveStamp;
46 import org.graalvm.compiler.core.common.type.Stamp;
47 import org.graalvm.compiler.core.common.type.StampFactory;
48 import org.graalvm.compiler.debug.CounterKey;
49 import org.graalvm.compiler.debug.DebugCloseable;
50 import org.graalvm.compiler.debug.DebugContext;
51 import org.graalvm.compiler.debug.GraalError;
52 import org.graalvm.compiler.graph.IterableNodeType;
53 import org.graalvm.compiler.graph.Node;
54 import org.graalvm.compiler.graph.NodeClass;
55 import org.graalvm.compiler.graph.NodeSourcePosition;
56 import org.graalvm.compiler.graph.iterators.NodeIterable;
57 import org.graalvm.compiler.graph.spi.Canonicalizable;
58 import org.graalvm.compiler.graph.spi.Simplifiable;
59 import org.graalvm.compiler.graph.spi.SimplifierTool;
60 import org.graalvm.compiler.nodeinfo.InputType;
61 import org.graalvm.compiler.nodeinfo.NodeInfo;
62 import org.graalvm.compiler.nodes.calc.AddNode;
63 import org.graalvm.compiler.nodes.calc.CompareNode;
64 import org.graalvm.compiler.nodes.calc.ConditionalNode;
65 import org.graalvm.compiler.nodes.calc.FloatNormalizeCompareNode;
66 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
67 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
68 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
69 import org.graalvm.compiler.nodes.calc.IntegerNormalizeCompareNode;
70 import org.graalvm.compiler.nodes.calc.IsNullNode;
71 import org.graalvm.compiler.nodes.calc.ObjectEqualsNode;
72 import org.graalvm.compiler.nodes.extended.UnboxNode;
73 import org.graalvm.compiler.nodes.java.InstanceOfNode;
74 import org.graalvm.compiler.nodes.java.LoadFieldNode;
75 import org.graalvm.compiler.nodes.spi.LIRLowerable;
76 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
77 import org.graalvm.compiler.nodes.spi.SwitchFoldable;
78 import org.graalvm.compiler.nodes.util.GraphUtil;
79
80 import jdk.vm.ci.code.CodeUtil;
81 import jdk.vm.ci.meta.Constant;
82 import jdk.vm.ci.meta.JavaConstant;
83 import jdk.vm.ci.meta.JavaKind;
84 import jdk.vm.ci.meta.MetaAccessProvider;
85 import jdk.vm.ci.meta.PrimitiveConstant;
86 import jdk.vm.ci.meta.ResolvedJavaMethod;
87 import jdk.vm.ci.meta.ResolvedJavaType;
88 import jdk.vm.ci.meta.TriState;
89
90 /**
91 * The {@code IfNode} represents a branch that can go one of two directions depending on the outcome
92 * of a comparison.
93 */
94 @NodeInfo(cycles = CYCLES_1, size = SIZE_2, sizeRationale = "2 jmps")
95 public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable, IterableNodeType, SwitchFoldable {
96 public static final NodeClass<IfNode> TYPE = NodeClass.create(IfNode.class);
97
98 private static final int MAX_USAGE_COLOR_SET_SIZE = 64;
99 private static final int MAX_FRAMESTATE_SEARCH_DEPTH = 4;
100
101 private static final CounterKey CORRECTED_PROBABILITIES = DebugContext.counter("CorrectedProbabilities");
102
103 @Successor AbstractBeginNode trueSuccessor;
104 @Successor AbstractBeginNode falseSuccessor;
105 @Input(InputType.Condition) LogicNode condition;
106 protected double trueSuccessorProbability;
107
108 public LogicNode condition() {
109 return condition;
110 }
111
112 public void setCondition(LogicNode x) {
113 updateUsages(condition, x);
114 condition = x;
115 }
116
117 public IfNode(LogicNode condition, FixedNode trueSuccessor, FixedNode falseSuccessor, double trueSuccessorProbability) {
118 this(condition, BeginNode.begin(trueSuccessor), BeginNode.begin(falseSuccessor), trueSuccessorProbability);
119 }
120
121 public IfNode(LogicNode condition, AbstractBeginNode trueSuccessor, AbstractBeginNode falseSuccessor, double trueSuccessorProbability) {
122 super(TYPE, StampFactory.forVoid());
123 this.condition = condition;
124 this.falseSuccessor = falseSuccessor;
125 this.trueSuccessor = trueSuccessor;
126 setTrueSuccessorProbability(trueSuccessorProbability);
127 }
128
129 /**
130 * Gets the true successor.
131 *
132 * @return the true successor
133 */
134 public AbstractBeginNode trueSuccessor() {
135 return trueSuccessor;
136 }
137
138 /**
139 * Gets the false successor.
140 *
141 * @return the false successor
142 */
143 public AbstractBeginNode falseSuccessor() {
144 return falseSuccessor;
145 }
146
147 public double getTrueSuccessorProbability() {
148 return this.trueSuccessorProbability;
149 }
150
151 public void setTrueSuccessor(AbstractBeginNode node) {
152 updatePredecessor(trueSuccessor, node);
153 trueSuccessor = node;
154 }
155
156 public void setFalseSuccessor(AbstractBeginNode node) {
157 updatePredecessor(falseSuccessor, node);
158 falseSuccessor = node;
159 }
160
161 /**
162 * Gets the node corresponding to the specified outcome of the branch.
163 *
164 * @param istrue {@code true} if the true successor is requested, {@code false} otherwise
165 * @return the corresponding successor
166 */
167 public AbstractBeginNode successor(boolean istrue) {
168 return istrue ? trueSuccessor : falseSuccessor;
169 }
170
171 public void setTrueSuccessorProbability(double prob) {
172 assert prob >= -0.000000001 && prob <= 1.000000001 : "Probability out of bounds: " + prob;
173 trueSuccessorProbability = Math.min(1.0, Math.max(0.0, prob));
174 }
175
176 @Override
177 public double probability(AbstractBeginNode successor) {
178 return successor == trueSuccessor ? trueSuccessorProbability : 1 - trueSuccessorProbability;
179 }
180
181 @Override
182 public void generate(NodeLIRBuilderTool gen) {
183 gen.emitIf(this);
184 }
185
186 @Override
187 public boolean verify() {
188 assertTrue(condition() != null, "missing condition");
189 assertTrue(trueSuccessor() != null, "missing trueSuccessor");
190 assertTrue(falseSuccessor() != null, "missing falseSuccessor");
191 return super.verify();
192 }
193
194 private boolean compareCallContext(NodeSourcePosition successorPosition) {
195 NodeSourcePosition position = getNodeSourcePosition();
196 NodeSourcePosition successor = successorPosition;
197 while (position != null) {
198 assertTrue(Objects.equals(position.getMethod(), successor.getMethod()), "method mismatch");
199 position = position.getCaller();
200 successor = successor.getCaller();
201 }
202 assertTrue(successor == null, "successor position has more methods");
203 return true;
204 }
205
206 @Override
207 public boolean verifySourcePosition() {
208 NodeSourcePosition sourcePosition = getNodeSourcePosition();
209 assertTrue(sourcePosition != null, "missing IfNode source position");
210
211 NodeSourcePosition trueSuccessorPosition = trueSuccessor.getNodeSourcePosition();
212 assertTrue(trueSuccessorPosition != null, "missing IfNode true successor source position");
213
214 NodeSourcePosition falseSuccessorPosition = falseSuccessor.getNodeSourcePosition();
215 assertTrue(falseSuccessorPosition != null, "missing IfNode false successor source position");
216
217 int bci = sourcePosition.getBCI();
218 ResolvedJavaMethod method = sourcePosition.getMethod();
219 int bytecode = BytecodeDisassembler.getBytecodeAt(method, bci);
220
221 if (!Bytecodes.isIfBytecode(bytecode)) {
222 return true;
223 }
224
225 byte[] code = (new ResolvedJavaMethodBytecode(method)).getCode();
226 int targetBCI = bci + Bytes.beS2(code, bci + 1);
227 int nextBCI = bci + Bytecodes.lengthOf(bytecode);
228
229 // At least one successor should have the correct BCI to indicate any possible negation that
230 // occurred after bytecode parsing
231 boolean matchingSuccessorFound = false;
232 if (trueSuccessorPosition.getBCI() == nextBCI || trueSuccessorPosition.getBCI() == targetBCI) {
233 assertTrue(compareCallContext(trueSuccessorPosition), "call context different from IfNode in trueSuccessor");
234 matchingSuccessorFound = true;
235 }
236
237 if (falseSuccessorPosition.getBCI() == nextBCI || falseSuccessorPosition.getBCI() == targetBCI) {
238 assertTrue(compareCallContext(falseSuccessorPosition), "call context different from IfNode in falseSuccessor");
239 matchingSuccessorFound = true;
240 }
241
242 assertTrue(matchingSuccessorFound, "no matching successor position found in IfNode");
243 assertTrue(trueSuccessorPosition.getBCI() != falseSuccessorPosition.getBCI(), "successor positions same in IfNode");
244
245 return true;
246 }
247
248 public void eliminateNegation() {
249 AbstractBeginNode oldTrueSuccessor = trueSuccessor;
250 AbstractBeginNode oldFalseSuccessor = falseSuccessor;
251 trueSuccessor = oldFalseSuccessor;
252 falseSuccessor = oldTrueSuccessor;
253 trueSuccessorProbability = 1 - trueSuccessorProbability;
254 setCondition(((LogicNegationNode) condition).getValue());
255 }
256
257 @Override
258 public void simplify(SimplifierTool tool) {
259 if (trueSuccessor().next() instanceof DeoptimizeNode) {
260 if (trueSuccessorProbability != 0) {
261 CORRECTED_PROBABILITIES.increment(getDebug());
262 trueSuccessorProbability = 0;
263 }
264 } else if (falseSuccessor().next() instanceof DeoptimizeNode) {
265 if (trueSuccessorProbability != 1) {
266 CORRECTED_PROBABILITIES.increment(getDebug());
267 trueSuccessorProbability = 1;
268 }
269 }
270
271 if (condition() instanceof LogicNegationNode) {
272 eliminateNegation();
273 }
274 if (condition() instanceof LogicConstantNode) {
275 LogicConstantNode c = (LogicConstantNode) condition();
276 if (c.getValue()) {
277 tool.deleteBranch(falseSuccessor());
278 tool.addToWorkList(trueSuccessor());
279 graph().removeSplit(this, trueSuccessor());
280 } else {
281 tool.deleteBranch(trueSuccessor());
282 tool.addToWorkList(falseSuccessor());
283 graph().removeSplit(this, falseSuccessor());
284 }
285 return;
286 }
287 if (tool.allUsagesAvailable() && trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages()) {
288
289 pushNodesThroughIf(tool);
290
291 if (checkForUnsignedCompare(tool) || removeOrMaterializeIf(tool)) {
292 return;
293 }
294 }
295
296 if (removeIntermediateMaterialization(tool)) {
297 return;
298 }
299
300 if (splitIfAtPhi(tool)) {
301 return;
302 }
303
304 if (conditionalNodeOptimization(tool)) {
305 return;
306 }
307
308 if (switchTransformationOptimization(tool)) {
309 return;
310 }
311
312 if (falseSuccessor().hasNoUsages() && (!(falseSuccessor() instanceof LoopExitNode)) && falseSuccessor().next() instanceof IfNode &&
313 !(((IfNode) falseSuccessor().next()).falseSuccessor() instanceof LoopExitNode)) {
314 AbstractBeginNode intermediateBegin = falseSuccessor();
315 IfNode nextIf = (IfNode) intermediateBegin.next();
316 double probabilityB = (1.0 - this.trueSuccessorProbability) * nextIf.trueSuccessorProbability;
317 if (this.trueSuccessorProbability < probabilityB) {
318 // Reordering of those two if statements is beneficial from the point of view of
319 // their probabilities.
320 if (prepareForSwap(tool, condition(), nextIf.condition())) {
321 // Reordering is allowed from (if1 => begin => if2) to (if2 => begin => if1).
322 assert intermediateBegin.next() == nextIf;
323 AbstractBeginNode bothFalseBegin = nextIf.falseSuccessor();
324 nextIf.setFalseSuccessor(null);
325 intermediateBegin.setNext(null);
326 this.setFalseSuccessor(null);
327
328 this.replaceAtPredecessor(nextIf);
329 nextIf.setFalseSuccessor(intermediateBegin);
330 intermediateBegin.setNext(this);
331 this.setFalseSuccessor(bothFalseBegin);
332
333 NodeSourcePosition intermediateBeginPosition = intermediateBegin.getNodeSourcePosition();
334 intermediateBegin.setNodeSourcePosition(bothFalseBegin.getNodeSourcePosition());
335 bothFalseBegin.setNodeSourcePosition(intermediateBeginPosition);
336
337 nextIf.setTrueSuccessorProbability(probabilityB);
338 if (probabilityB == 1.0) {
339 this.setTrueSuccessorProbability(0.0);
340 } else {
341 double newProbability = this.trueSuccessorProbability / (1.0 - probabilityB);
342 this.setTrueSuccessorProbability(Math.min(1.0, newProbability));
343 }
344 return;
345 }
346 }
347 }
348
349 if (tryEliminateBoxedReferenceEquals(tool)) {
350 return;
351 }
352 }
353
354 private static boolean isUnboxedFrom(MetaAccessProvider meta, NodeView view, ValueNode x, ValueNode src) {
355 if (x == src) {
356 return true;
357 } else if (x instanceof UnboxNode) {
358 return isUnboxedFrom(meta, view, ((UnboxNode) x).getValue(), src);
359 } else if (x instanceof PiNode) {
360 PiNode pi = (PiNode) x;
361 return isUnboxedFrom(meta, view, pi.getOriginalNode(), src);
362 } else if (x instanceof LoadFieldNode) {
363 LoadFieldNode load = (LoadFieldNode) x;
364 ResolvedJavaType integerType = meta.lookupJavaType(Integer.class);
365 if (load.getValue().stamp(view).javaType(meta).equals(integerType)) {
366 return isUnboxedFrom(meta, view, load.getValue(), src);
367 } else {
368 return false;
369 }
370 } else {
371 return false;
372 }
373 }
374
375 /**
376 * Attempts to replace the following pattern:
377 *
378 * <pre>
379 * Integer x = ...;
380 * Integer y = ...;
381 * if ((x == y) || x.equals(y)) { ... }
382 * </pre>
383 *
384 * with:
385 *
386 * <pre>
387 * Integer x = ...;
388 * Integer y = ...;
389 * if (x.equals(y)) { ... }
390 * </pre>
391 *
392 * whenever the probability that the reference check will pass is relatively small.
393 *
394 * See GR-1315 for more information.
395 */
396 private boolean tryEliminateBoxedReferenceEquals(SimplifierTool tool) {
397 if (!(condition instanceof ObjectEqualsNode)) {
398 return false;
399 }
400
401 MetaAccessProvider meta = tool.getMetaAccess();
402 ObjectEqualsNode equalsCondition = (ObjectEqualsNode) condition;
403 ValueNode x = equalsCondition.getX();
404 ValueNode y = equalsCondition.getY();
405 ResolvedJavaType integerType = meta.lookupJavaType(Integer.class);
406
407 // At least one argument for reference equal must be a boxed primitive.
408 NodeView view = NodeView.from(tool);
409 if (!x.stamp(view).javaType(meta).equals(integerType) && !y.stamp(view).javaType(meta).equals(integerType)) {
410 return false;
411 }
412
413 // The reference equality check is usually more efficient compared to a boxing check.
414 // The success of the reference equals must therefore be relatively rare, otherwise it makes
415 // no sense to eliminate it.
416 if (getTrueSuccessorProbability() > 0.4) {
417 return false;
418 }
419
420 // True branch must be empty.
421 if (trueSuccessor instanceof BeginNode || trueSuccessor instanceof LoopExitNode) {
422 if (trueSuccessor.next() instanceof EndNode) {
423 // Empty true branch.
424 } else {
425 return false;
426 }
427 } else {
428 return false;
429 }
430
431 // False branch must only check the unboxed values.
432 UnboxNode unbox = null;
433 FixedGuardNode unboxCheck = null;
434 for (FixedNode node : falseSuccessor.getBlockNodes()) {
435 if (!(node instanceof BeginNode || node instanceof UnboxNode || node instanceof FixedGuardNode || node instanceof EndNode ||
436 node instanceof LoadFieldNode || node instanceof LoopExitNode)) {
437 return false;
438 }
439 if (node instanceof UnboxNode) {
440 if (unbox == null) {
441 unbox = (UnboxNode) node;
442 } else {
443 return false;
444 }
445 }
446 if (!(node instanceof FixedGuardNode)) {
447 continue;
448 }
449 FixedGuardNode fixed = (FixedGuardNode) node;
450 if (!(fixed.condition() instanceof IntegerEqualsNode)) {
451 continue;
452 }
453 IntegerEqualsNode equals = (IntegerEqualsNode) fixed.condition();
454 if ((isUnboxedFrom(meta, view, equals.getX(), x) && isUnboxedFrom(meta, view, equals.getY(), y)) ||
455 (isUnboxedFrom(meta, view, equals.getX(), y) && isUnboxedFrom(meta, view, equals.getY(), x))) {
456 unboxCheck = fixed;
457 }
458 }
459 if (unbox == null || unboxCheck == null) {
460 return false;
461 }
462
463 // Falsify the reference check.
464 setCondition(graph().addOrUniqueWithInputs(LogicConstantNode.contradiction()));
465
466 return true;
467 }
468
469 // SwitchFoldable implementation.
470
471 @Override
472 public Node getNextSwitchFoldableBranch() {
473 return falseSuccessor();
474 }
475
476 @Override
477 public boolean isInSwitch(ValueNode switchValue) {
478 return SwitchFoldable.maybeIsInSwitch(condition()) && SwitchFoldable.sameSwitchValue(condition(), switchValue);
479 }
480
481 @Override
482 public void cutOffCascadeNode() {
483 setTrueSuccessor(null);
484 }
485
486 @Override
487 public void cutOffLowestCascadeNode() {
488 setFalseSuccessor(null);
489 setTrueSuccessor(null);
490 }
491
492 @Override
493 public AbstractBeginNode getDefault() {
494 return falseSuccessor();
495 }
496
497 @Override
498 public ValueNode switchValue() {
499 if (SwitchFoldable.maybeIsInSwitch(condition())) {
500 return ((IntegerEqualsNode) condition()).getX();
501 }
502 return null;
503 }
504
505 @Override
506 public boolean isNonInitializedProfile() {
507 return getTrueSuccessorProbability() == 0.5d;
508 }
509
510 @Override
511 public int intKeyAt(int i) {
512 assert i == 0;
513 return ((IntegerEqualsNode) condition()).getY().asJavaConstant().asInt();
514 }
515
516 @Override
517 public double keyProbability(int i) {
518 assert i == 0;
519 return getTrueSuccessorProbability();
520 }
521
522 @Override
523 public AbstractBeginNode keySuccessor(int i) {
524 assert i == 0;
525 return trueSuccessor();
526 }
527
528 @Override
529 public double defaultProbability() {
530 return 1.0d - getTrueSuccessorProbability();
531 }
532
533 /**
534 * Try to optimize this as if it were a {@link ConditionalNode}.
535 */
536 private boolean conditionalNodeOptimization(SimplifierTool tool) {
537 if (trueSuccessor().next() instanceof AbstractEndNode && falseSuccessor().next() instanceof AbstractEndNode) {
538 AbstractEndNode trueEnd = (AbstractEndNode) trueSuccessor().next();
539 AbstractEndNode falseEnd = (AbstractEndNode) falseSuccessor().next();
540 if (trueEnd.merge() != falseEnd.merge()) {
541 return false;
542 }
543 if (!(trueEnd.merge() instanceof MergeNode)) {
544 return false;
545 }
546 MergeNode merge = (MergeNode) trueEnd.merge();
547 if (!merge.hasExactlyOneUsage() || merge.phis().count() != 1) {
548 return false;
549 }
550
551 if (trueSuccessor().anchored().isNotEmpty() || falseSuccessor().anchored().isNotEmpty()) {
552 return false;
553 }
554
555 PhiNode phi = merge.phis().first();
556 ValueNode falseValue = phi.valueAt(falseEnd);
557 ValueNode trueValue = phi.valueAt(trueEnd);
558
559 NodeView view = NodeView.from(tool);
560 ValueNode result = ConditionalNode.canonicalizeConditional(condition, trueValue, falseValue, phi.stamp(view), view);
561 if (result != null) {
562 /*
563 * canonicalizeConditional returns possibly new nodes so add them to the graph.
564 */
565 if (result.graph() == null) {
566 result = graph().addOrUniqueWithInputs(result);
567 }
568 result = proxyReplacement(result);
569 /*
570 * This optimization can be performed even if multiple values merge at this phi
571 * since the two inputs get simplified into one.
572 */
573 phi.setValueAt(trueEnd, result);
574 removeThroughFalseBranch(tool, merge);
575 return true;
576 }
577 }
578
579 return false;
580 }
581
582 private void pushNodesThroughIf(SimplifierTool tool) {
583 assert trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages();
584 // push similar nodes upwards through the if, thereby deduplicating them
585 do {
586 AbstractBeginNode trueSucc = trueSuccessor();
587 AbstractBeginNode falseSucc = falseSuccessor();
588 if (trueSucc instanceof BeginNode && falseSucc instanceof BeginNode && trueSucc.next() instanceof FixedWithNextNode && falseSucc.next() instanceof FixedWithNextNode) {
589 FixedWithNextNode trueNext = (FixedWithNextNode) trueSucc.next();
590 FixedWithNextNode falseNext = (FixedWithNextNode) falseSucc.next();
591 NodeClass<?> nodeClass = trueNext.getNodeClass();
592 if (trueNext.getClass() == falseNext.getClass()) {
593 if (trueNext instanceof AbstractBeginNode) {
594 // Cannot do this optimization for begin nodes, because it could
595 // move guards above the if that need to stay below a branch.
596 } else if (nodeClass.equalInputs(trueNext, falseNext) && trueNext.valueEquals(falseNext)) {
597 falseNext.replaceAtUsages(trueNext);
598 graph().removeFixed(falseNext);
599 GraphUtil.unlinkFixedNode(trueNext);
600 graph().addBeforeFixed(this, trueNext);
601 for (Node usage : trueNext.usages().snapshot()) {
602 if (usage.isAlive()) {
603 NodeClass<?> usageNodeClass = usage.getNodeClass();
604 if (usageNodeClass.valueNumberable() && !usageNodeClass.isLeafNode()) {
605 Node newNode = graph().findDuplicate(usage);
606 if (newNode != null) {
607 usage.replaceAtUsagesAndDelete(newNode);
608 }
609 }
610 if (usage.isAlive()) {
611 tool.addToWorkList(usage);
612 }
613 }
614 }
615 continue;
616 }
617 }
618 }
619 break;
620 } while (true);
621 }
622
623 /**
624 * Recognize a couple patterns that can be merged into an unsigned compare.
625 *
626 * @param tool
627 * @return true if a replacement was done.
628 */
629 @SuppressWarnings("try")
630 private boolean checkForUnsignedCompare(SimplifierTool tool) {
631 assert trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages();
632 if (condition() instanceof IntegerLessThanNode) {
633 NodeView view = NodeView.from(tool);
634 IntegerLessThanNode lessThan = (IntegerLessThanNode) condition();
635 Constant y = lessThan.getY().stamp(view).asConstant();
636 if (y instanceof PrimitiveConstant && ((PrimitiveConstant) y).asLong() == 0 && falseSuccessor().next() instanceof IfNode) {
637 IfNode ifNode2 = (IfNode) falseSuccessor().next();
638 if (ifNode2.condition() instanceof IntegerLessThanNode) {
639 IntegerLessThanNode lessThan2 = (IntegerLessThanNode) ifNode2.condition();
640 AbstractBeginNode falseSucc = ifNode2.falseSuccessor();
641 AbstractBeginNode trueSucc = ifNode2.trueSuccessor();
642 IntegerBelowNode below = null;
643 /*
644 * Convert x >= 0 && x < positive which is represented as !(x < 0) && x <
645 * <positive> into an unsigned compare.
646 */
647 if (lessThan2.getX() == lessThan.getX() && lessThan2.getY().stamp(view) instanceof IntegerStamp &&
648 ((IntegerStamp) lessThan2.getY().stamp(view)).isPositive() &&
649 sameDestination(trueSuccessor(), ifNode2.falseSuccessor)) {
650 below = graph().unique(new IntegerBelowNode(lessThan2.getX(), lessThan2.getY()));
651 // swap direction
652 AbstractBeginNode tmp = falseSucc;
653 falseSucc = trueSucc;
654 trueSucc = tmp;
655 } else if (lessThan2.getY() == lessThan.getX() && sameDestination(trueSuccessor(), ifNode2.trueSuccessor)) {
656 /*
657 * Convert x >= 0 && x <= positive which is represented as !(x < 0) &&
658 * !(<positive> > x), into x <| positive + 1. This can only be done for
659 * constants since there isn't a IntegerBelowEqualThanNode but that doesn't
660 * appear to be interesting.
661 */
662 JavaConstant positive = lessThan2.getX().asJavaConstant();
663 if (positive != null && positive.asLong() > 0 && positive.asLong() < positive.getJavaKind().getMaxValue()) {
664 ConstantNode newLimit = ConstantNode.forIntegerStamp(lessThan2.getX().stamp(view), positive.asLong() + 1, graph());
665 below = graph().unique(new IntegerBelowNode(lessThan.getX(), newLimit));
666 }
667 }
668 if (below != null) {
669 try (DebugCloseable position = ifNode2.withNodeSourcePosition()) {
670 ifNode2.setTrueSuccessor(null);
671 ifNode2.setFalseSuccessor(null);
672
673 IfNode newIfNode = graph().add(new IfNode(below, falseSucc, trueSucc, 1 - trueSuccessorProbability));
674 // Remove the < 0 test.
675 tool.deleteBranch(trueSuccessor);
676 graph().removeSplit(this, falseSuccessor);
677
678 // Replace the second test with the new one.
679 ifNode2.predecessor().replaceFirstSuccessor(ifNode2, newIfNode);
680 ifNode2.safeDelete();
681 return true;
682 }
683 }
684 }
685 } else if (y instanceof PrimitiveConstant && ((PrimitiveConstant) y).asLong() < 0 && falseSuccessor().next() instanceof IfNode) {
686 IfNode ifNode2 = (IfNode) falseSuccessor().next();
687 AbstractBeginNode falseSucc = ifNode2.falseSuccessor();
688 AbstractBeginNode trueSucc = ifNode2.trueSuccessor();
689 IntegerBelowNode below = null;
690 if (ifNode2.condition() instanceof IntegerLessThanNode) {
691 ValueNode x = lessThan.getX();
692 IntegerLessThanNode lessThan2 = (IntegerLessThanNode) ifNode2.condition();
693 /*
694 * Convert x >= -C1 && x < C2, represented as !(x < -C1) && x < C2, into an
695 * unsigned compare. This condition is equivalent to x + C1 |<| C1 + C2 if C1 +
696 * C2 does not overflow.
697 */
698 Constant c2 = lessThan2.getY().stamp(view).asConstant();
699 if (lessThan2.getX() == x && c2 instanceof PrimitiveConstant && ((PrimitiveConstant) c2).asLong() > 0 &&
700 x.stamp(view).isCompatible(lessThan.getY().stamp(view)) &&
701 x.stamp(view).isCompatible(lessThan2.getY().stamp(view)) &&
702 sameDestination(trueSuccessor(), ifNode2.falseSuccessor)) {
703 long newLimitValue = -((PrimitiveConstant) y).asLong() + ((PrimitiveConstant) c2).asLong();
704 // Make sure the limit fits into the target type without overflow.
705 if (newLimitValue > 0 && newLimitValue <= CodeUtil.maxValue(PrimitiveStamp.getBits(x.stamp(view)))) {
706 ConstantNode newLimit = ConstantNode.forIntegerStamp(x.stamp(view), newLimitValue, graph());
707 ConstantNode c1 = ConstantNode.forIntegerStamp(x.stamp(view), -((PrimitiveConstant) y).asLong(), graph());
708 ValueNode addNode = graph().addOrUniqueWithInputs(AddNode.create(x, c1, view));
709 below = graph().unique(new IntegerBelowNode(addNode, newLimit));
710 }
711 }
712 }
713 if (below != null) {
714 try (DebugCloseable position = ifNode2.withNodeSourcePosition()) {
715 ifNode2.setTrueSuccessor(null);
716 ifNode2.setFalseSuccessor(null);
717
718 IfNode newIfNode = graph().add(new IfNode(below, trueSucc, falseSucc, trueSuccessorProbability));
719 // Remove the < -C1 test.
720 tool.deleteBranch(trueSuccessor);
721 graph().removeSplit(this, falseSuccessor);
722
723 // Replace the second test with the new one.
724 ifNode2.predecessor().replaceFirstSuccessor(ifNode2, newIfNode);
725 ifNode2.safeDelete();
726 return true;
727 }
728 }
729 }
730 }
731 return false;
732 }
733
734 /**
735 * Check it these two blocks end up at the same place. Meeting at the same merge, or
736 * deoptimizing in the same way.
737 */
738 private static boolean sameDestination(AbstractBeginNode succ1, AbstractBeginNode succ2) {
739 Node next1 = succ1.next();
740 Node next2 = succ2.next();
741 if (next1 instanceof EndNode && next2 instanceof EndNode) {
742 EndNode end1 = (EndNode) next1;
743 EndNode end2 = (EndNode) next2;
744 if (end1.merge() == end2.merge()) {
745 for (PhiNode phi : end1.merge().phis()) {
746 if (phi.valueAt(end1) != phi.valueAt(end2)) {
747 return false;
748 }
749 }
750 // They go to the same MergeNode and merge the same values
751 return true;
752 }
753 } else if (next1 instanceof DeoptimizeNode && next2 instanceof DeoptimizeNode) {
754 DeoptimizeNode deopt1 = (DeoptimizeNode) next1;
755 DeoptimizeNode deopt2 = (DeoptimizeNode) next2;
756 if (deopt1.getReason() == deopt2.getReason() && deopt1.getAction() == deopt2.getAction()) {
757 // Same deoptimization reason and action.
758 return true;
759 }
760 } else if (next1 instanceof LoopExitNode && next2 instanceof LoopExitNode) {
761 LoopExitNode exit1 = (LoopExitNode) next1;
762 LoopExitNode exit2 = (LoopExitNode) next2;
763 if (exit1.loopBegin() == exit2.loopBegin() && exit1.stateAfter() == exit2.stateAfter() && exit1.stateAfter() == null && sameDestination(exit1, exit2)) {
764 // Exit the same loop and end up at the same place.
765 return true;
766 }
767 } else if (next1 instanceof ReturnNode && next2 instanceof ReturnNode) {
768 ReturnNode exit1 = (ReturnNode) next1;
769 ReturnNode exit2 = (ReturnNode) next2;
770 if (exit1.result() == exit2.result()) {
771 // Exit the same loop and end up at the same place.
772 return true;
773 }
774 }
775 return false;
776 }
777
778 private static boolean prepareForSwap(SimplifierTool tool, LogicNode a, LogicNode b) {
779 DebugContext debug = a.getDebug();
780 if (a instanceof InstanceOfNode) {
781 InstanceOfNode instanceOfA = (InstanceOfNode) a;
782 if (b instanceof IsNullNode) {
783 IsNullNode isNullNode = (IsNullNode) b;
784 if (isNullNode.getValue() == instanceOfA.getValue()) {
785 debug.log("Can swap instanceof and isnull if");
786 return true;
787 }
788 } else if (b instanceof InstanceOfNode) {
789 InstanceOfNode instanceOfB = (InstanceOfNode) b;
790 if (instanceOfA.getValue() == instanceOfB.getValue() && !instanceOfA.type().getType().isInterface() && !instanceOfB.type().getType().isInterface() &&
791 !instanceOfA.type().getType().isAssignableFrom(instanceOfB.type().getType()) && !instanceOfB.type().getType().isAssignableFrom(instanceOfA.type().getType())) {
792 // Two instanceof on the same value with mutually exclusive types.
793 debug.log("Can swap instanceof for types %s and %s", instanceOfA.type(), instanceOfB.type());
794 return true;
795 }
796 }
797 } else if (a instanceof CompareNode) {
798 CompareNode compareA = (CompareNode) a;
799 Condition conditionA = compareA.condition().asCondition();
800 if (compareA.unorderedIsTrue()) {
801 return false;
802 }
803 if (b instanceof CompareNode) {
804 CompareNode compareB = (CompareNode) b;
805 if (compareA == compareB) {
806 debug.log("Same conditions => do not swap and leave the work for global value numbering.");
807 return false;
808 }
809 if (compareB.unorderedIsTrue()) {
810 return false;
811 }
812 Condition comparableCondition = null;
813 Condition conditionB = compareB.condition().asCondition();
814 if (compareB.getX() == compareA.getX() && compareB.getY() == compareA.getY()) {
815 comparableCondition = conditionB;
816 } else if (compareB.getX() == compareA.getY() && compareB.getY() == compareA.getX()) {
817 comparableCondition = conditionB.mirror();
818 }
819
820 if (comparableCondition != null) {
821 Condition combined = conditionA.join(comparableCondition);
822 if (combined == null) {
823 // The two conditions are disjoint => can reorder.
824 debug.log("Can swap disjoint coditions on same values: %s and %s", conditionA, comparableCondition);
825 return true;
826 }
827 } else if (conditionA == Condition.EQ && conditionB == Condition.EQ) {
828 boolean canSwap = false;
829 if ((compareA.getX() == compareB.getX() && valuesDistinct(tool, compareA.getY(), compareB.getY()))) {
830 canSwap = true;
831 } else if ((compareA.getX() == compareB.getY() && valuesDistinct(tool, compareA.getY(), compareB.getX()))) {
832 canSwap = true;
833 } else if ((compareA.getY() == compareB.getX() && valuesDistinct(tool, compareA.getX(), compareB.getY()))) {
834 canSwap = true;
835 } else if ((compareA.getY() == compareB.getY() && valuesDistinct(tool, compareA.getX(), compareB.getX()))) {
836 canSwap = true;
837 }
838
839 if (canSwap) {
840 debug.log("Can swap equality condition with one shared and one disjoint value.");
841 return true;
842 }
843 }
844 }
845 }
846
847 return false;
848 }
849
850 private static boolean valuesDistinct(SimplifierTool tool, ValueNode a, ValueNode b) {
851 if (a.isConstant() && b.isConstant()) {
852 Boolean equal = tool.getConstantReflection().constantEquals(a.asConstant(), b.asConstant());
853 if (equal != null) {
854 return !equal.booleanValue();
855 }
856 }
857
858 NodeView view = NodeView.from(tool);
859 Stamp stampA = a.stamp(view);
860 Stamp stampB = b.stamp(view);
861 return stampA.alwaysDistinct(stampB);
862 }
863
864 /**
865 * Tries to remove an empty if construct or replace an if construct with a materialization.
866 *
867 * @return true if a transformation was made, false otherwise
868 */
869 private boolean removeOrMaterializeIf(SimplifierTool tool) {
870 assert trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages();
871 if (trueSuccessor().next() instanceof AbstractEndNode && falseSuccessor().next() instanceof AbstractEndNode) {
872 AbstractEndNode trueEnd = (AbstractEndNode) trueSuccessor().next();
873 AbstractEndNode falseEnd = (AbstractEndNode) falseSuccessor().next();
874 AbstractMergeNode merge = trueEnd.merge();
875 if (merge == falseEnd.merge() && trueSuccessor().anchored().isEmpty() && falseSuccessor().anchored().isEmpty()) {
876 PhiNode singlePhi = null;
877 int distinct = 0;
878 for (PhiNode phi : merge.phis()) {
879 ValueNode trueValue = phi.valueAt(trueEnd);
880 ValueNode falseValue = phi.valueAt(falseEnd);
881 if (trueValue != falseValue) {
882 distinct++;
883 singlePhi = phi;
884 }
885 }
886 if (distinct == 0) {
887 /*
888 * Multiple phis but merging same values for true and false, so simply delete
889 * the path
890 */
891 removeThroughFalseBranch(tool, merge);
892 return true;
893 } else if (distinct == 1) {
894 // Fortify: Suppress Null Dereference false positive
895 assert singlePhi != null;
896
897 ValueNode trueValue = singlePhi.valueAt(trueEnd);
898 ValueNode falseValue = singlePhi.valueAt(falseEnd);
899 ValueNode conditional = canonicalizeConditionalCascade(tool, trueValue, falseValue);
900 if (conditional != null) {
901 conditional = proxyReplacement(conditional);
902 singlePhi.setValueAt(trueEnd, conditional);
903 removeThroughFalseBranch(tool, merge);
904 return true;
905 }
906 }
907 }
908 }
909 if (trueSuccessor().next() instanceof ReturnNode && falseSuccessor().next() instanceof ReturnNode) {
910 ReturnNode trueEnd = (ReturnNode) trueSuccessor().next();
911 ReturnNode falseEnd = (ReturnNode) falseSuccessor().next();
912 ValueNode trueValue = trueEnd.result();
913 ValueNode falseValue = falseEnd.result();
914 ValueNode value = null;
915 boolean needsProxy = false;
916 if (trueValue != null) {
917 if (trueValue == falseValue) {
918 value = trueValue;
919 } else {
920 value = canonicalizeConditionalCascade(tool, trueValue, falseValue);
921 if (value == null) {
922 return false;
923 }
924 needsProxy = true;
925 }
926 }
927
928 if (trueSuccessor() instanceof LoopExitNode) {
929 LoopBeginNode loopBegin = ((LoopExitNode) trueSuccessor()).loopBegin();
930 assert loopBegin == ((LoopExitNode) falseSuccessor()).loopBegin();
931 LoopExitNode loopExitNode = graph().add(new LoopExitNode(loopBegin));
932 graph().addBeforeFixed(this, loopExitNode);
933 if (graph().hasValueProxies() && needsProxy) {
934 value = graph().addOrUnique(new ValueProxyNode(value, loopExitNode));
935 }
936 }
937
938 ReturnNode newReturn = graph().add(new ReturnNode(value));
939 replaceAtPredecessor(newReturn);
940 GraphUtil.killCFG(this);
941 return true;
942 }
943 return false;
944 }
945
946 private ValueNode proxyReplacement(ValueNode replacement) {
947 /*
948 * Special case: Every empty diamond we collapse to a conditional node can potentially
949 * contain loop exit nodes on both branches. See the graph below: The two loop exits
950 * (instanceof begin node) exit the same loop. The resulting phi is defined outside the
951 * loop, but the resulting conditional node will be inside the loop, so we need to proxy the
952 * resulting conditional node. Callers of this method ensure that true and false successor
953 * have no usages, therefore a and b in the graph below can never be proxies themselves.
954 */
955 // @formatter:off
956 // +--+
957 // |If|
958 // +--+ +-----+ +-----+
959 // +----+ +----+ | a | | b |
960 // |Lex | |Lex | +----^+ +^----+
961 // +----+ +----+ | |
962 // +-------+ +---+
963 // | Merge +---------+Phi|
964 // +-------+ +---+
965 // @formatter:on
966 if (this.graph().hasValueProxies()) {
967 if (trueSuccessor instanceof LoopExitNode && falseSuccessor instanceof LoopExitNode) {
968 assert ((LoopExitNode) trueSuccessor).loopBegin() == ((LoopExitNode) falseSuccessor).loopBegin();
969 /*
970 * we can collapse all proxy nodes on one loop exit, the surviving one, which will
971 * be the true successor
972 */
973 if (falseSuccessor.anchored().isEmpty() && falseSuccessor.hasUsages()) {
974 for (Node n : falseSuccessor.usages().snapshot()) {
975 assert n instanceof ProxyNode;
976 ((ProxyNode) n).setProxyPoint((LoopExitNode) trueSuccessor);
977 }
978 }
979 /*
980 * The true successor (surviving loop exit) can have usages, namely proxy nodes, the
981 * false successor however, must not have usages any more after the code above
982 */
983 assert trueSuccessor.anchored().isEmpty() && falseSuccessor.hasNoUsages();
984 return this.graph().addOrUnique(new ValueProxyNode(replacement, (LoopExitNode) trueSuccessor));
985 }
986 }
987 return replacement;
988 }
989
990 protected void removeThroughFalseBranch(SimplifierTool tool, AbstractMergeNode merge) {
991 AbstractBeginNode trueBegin = trueSuccessor();
992 LogicNode conditionNode = condition();
993 graph().removeSplitPropagate(this, trueBegin);
994 tool.addToWorkList(trueBegin);
995 if (conditionNode != null) {
996 GraphUtil.tryKillUnused(conditionNode);
997 }
998 if (merge.isAlive() && merge.forwardEndCount() > 1) {
999 for (FixedNode end : merge.forwardEnds()) {
1000 Node cur = end;
1001 while (cur != null && cur.predecessor() instanceof BeginNode) {
1002 cur = cur.predecessor();
1003 }
1004 if (cur != null && cur.predecessor() instanceof IfNode) {
1005 tool.addToWorkList(cur.predecessor());
1006 }
1007 }
1008 }
1009 }
1010
1011 private ValueNode canonicalizeConditionalViaImplies(ValueNode trueValue, ValueNode falseValue) {
1012 ValueNode collapsedTrue = trueValue;
1013 ValueNode collapsedFalse = falseValue;
1014 boolean simplify = false;
1015 if (trueValue instanceof ConditionalNode) {
1016 TriState result = condition().implies(false, ((ConditionalNode) trueValue).condition());
1017 if (result.isKnown()) {
1018 simplify = true;
1019 collapsedTrue = result.toBoolean() ? ((ConditionalNode) trueValue).trueValue() : ((ConditionalNode) trueValue).falseValue();
1020 }
1021 }
1022 if (falseValue instanceof ConditionalNode) {
1023 TriState result = condition().implies(true, ((ConditionalNode) falseValue).condition());
1024 if (result.isKnown()) {
1025 simplify = true;
1026 collapsedFalse = result.toBoolean() ? ((ConditionalNode) falseValue).trueValue() : ((ConditionalNode) falseValue).falseValue();
1027 }
1028 }
1029 if (simplify) {
1030 return graph().unique(new ConditionalNode(condition(), collapsedTrue, collapsedFalse));
1031 }
1032 return null;
1033 }
1034
1035 private ValueNode canonicalizeConditionalCascade(SimplifierTool tool, ValueNode trueValue, ValueNode falseValue) {
1036 if (trueValue.getStackKind() != falseValue.getStackKind()) {
1037 return null;
1038 }
1039 if (trueValue.getStackKind() != JavaKind.Int && trueValue.getStackKind() != JavaKind.Long) {
1040 return null;
1041 }
1042 if (trueValue.isConstant() && falseValue.isConstant()) {
1043 return graph().unique(new ConditionalNode(condition(), trueValue, falseValue));
1044 }
1045 ValueNode value = canonicalizeConditionalViaImplies(trueValue, falseValue);
1046 if (value != null) {
1047 return value;
1048 }
1049 if (!graph().isAfterExpandLogic()) {
1050 /*
1051 * !isAfterExpandLogic() => Cannot spawn NormalizeCompareNodes after lowering in the
1052 * ExpandLogicPhase.
1053 */
1054 ConditionalNode conditional = null;
1055 ValueNode constant = null;
1056 boolean negateCondition;
1057 if (trueValue instanceof ConditionalNode && falseValue.isConstant()) {
1058 conditional = (ConditionalNode) trueValue;
1059 constant = falseValue;
1060 negateCondition = true;
1061 } else if (falseValue instanceof ConditionalNode && trueValue.isConstant()) {
1062 conditional = (ConditionalNode) falseValue;
1063 constant = trueValue;
1064 negateCondition = false;
1065 } else {
1066 return null;
1067 }
1068 boolean negateConditionalCondition = false;
1069 ValueNode otherValue = null;
1070 if (constant == conditional.trueValue()) {
1071 otherValue = conditional.falseValue();
1072 negateConditionalCondition = false;
1073 } else if (constant == conditional.falseValue()) {
1074 otherValue = conditional.trueValue();
1075 negateConditionalCondition = true;
1076 }
1077 if (otherValue != null && otherValue.isConstant()) {
1078 double shortCutProbability = probability(trueSuccessor());
1079 LogicNode newCondition = LogicNode.or(condition(), negateCondition, conditional.condition(), negateConditionalCondition, shortCutProbability);
1080 return graph().unique(new ConditionalNode(newCondition, constant, otherValue));
1081 }
1082
1083 if (constant.isJavaConstant() && conditional.trueValue().isJavaConstant() && conditional.falseValue().isJavaConstant() && condition() instanceof CompareNode &&
1084 conditional.condition() instanceof CompareNode) {
1085
1086 CompareNode condition1 = (CompareNode) condition();
1087 Condition cond1 = condition1.condition().asCondition();
1088 if (negateCondition) {
1089 cond1 = cond1.negate();
1090 }
1091 // cond1 is EQ, NE, LT, or GE
1092 CompareNode condition2 = (CompareNode) conditional.condition();
1093 Condition cond2 = condition2.condition().asCondition();
1094 ValueNode x = condition1.getX();
1095 ValueNode y = condition1.getY();
1096 ValueNode x2 = condition2.getX();
1097 ValueNode y2 = condition2.getY();
1098 // `x cond1 y ? c1 : (x2 cond2 y2 ? c2 : c3)`
1099 boolean sameVars = x == x2 && y == y2;
1100 if (!sameVars && x == y2 && y == x2) {
1101 sameVars = true;
1102 cond2 = cond2.mirror();
1103 }
1104 if (sameVars) {
1105
1106 JavaKind stackKind = conditional.trueValue().stamp(NodeView.from(tool)).getStackKind();
1107 assert !stackKind.isNumericFloat();
1108
1109 long c1 = constant.asJavaConstant().asLong();
1110 long c2 = conditional.trueValue().asJavaConstant().asLong();
1111 long c3 = conditional.falseValue().asJavaConstant().asLong();
1112
1113 // canonicalize cond2
1114 cond2 = cond2.join(cond1.negate());
1115 if (cond2 == null) {
1116 // mixing signed and unsigned cases, or useless combination of conditions
1117 return null;
1118 }
1119 // derive cond3 from cond1 and cond2
1120 Condition cond3 = cond1.negate().join(cond2.negate());
1121 if (cond3 == null) {
1122 // mixing signed and unsigned cases, or useless combination of conditions
1123 return null;
1124 }
1125 boolean unsigned = cond1.isUnsigned() || cond2.isUnsigned();
1126 boolean floatingPoint = x.stamp(NodeView.from(tool)) instanceof FloatStamp;
1127 assert !floatingPoint || y.stamp(NodeView.from(tool)) instanceof FloatStamp;
1128 assert !(floatingPoint && unsigned);
1129
1130 long expected1 = expectedConstantForNormalize(cond1);
1131 long expected2 = expectedConstantForNormalize(cond2);
1132 long expected3 = expectedConstantForNormalize(cond3);
1133
1134 if (c1 == expected1 && c2 == expected2 && c3 == expected3) {
1135 // normal order
1136 } else if (c1 == 0 - expected1 && c2 == 0 - expected2 && c3 == 0 - expected3) {
1137 // reverse order
1138 ValueNode tmp = x;
1139 x = y;
1140 y = tmp;
1141 } else {
1142 // cannot be expressed by NormalizeCompareNode
1143 return null;
1144 }
1145 if (floatingPoint) {
1146 boolean unorderedLess = false;
1147 if (((FloatStamp) x.stamp).canBeNaN() || ((FloatStamp) y.stamp).canBeNaN()) {
1148 // we may encounter NaNs, check the unordered value
1149 // (following the original condition's "unorderedIsTrue" path)
1150 long unorderedValue = condition1.unorderedIsTrue() ? c1 : condition2.unorderedIsTrue() ? c2 : c3;
1151 if (unorderedValue == 0) {
1152 // returning "0" for unordered is not possible
1153 return null;
1154 }
1155 unorderedLess = unorderedValue == -1;
1156 }
1157 return graph().unique(new FloatNormalizeCompareNode(x, y, stackKind, unorderedLess));
1158 } else {
1159 return graph().unique(new IntegerNormalizeCompareNode(x, y, stackKind, unsigned));
1160 }
1161 }
1162 }
1163 }
1164 return null;
1165 }
1166
1167 private static long expectedConstantForNormalize(Condition condition) {
1168 if (condition == Condition.EQ) {
1169 return 0;
1170 } else if (condition == Condition.LT || condition == Condition.BT) {
1171 return -1;
1172 } else {
1173 assert condition == Condition.GT || condition == Condition.AT;
1174 return 1;
1175 }
1176 }
1177
1178 public enum NodeColor {
1179 NONE,
1180 CONDITION_USAGE,
1181 TRUE_BRANCH,
1182 FALSE_BRANCH,
1183 PHI_MIXED,
1184 MIXED
1185 }
1186
1187 /**
1188 * Take an if that is immediately dominated by a merge with a single phi and split off any paths
1189 * where the test would be statically decidable creating a new merge below the appropriate side
1190 * of the IfNode. Any undecidable tests will continue to use the original IfNode.
1191 *
1192 * @param tool
1193 */
1194 @SuppressWarnings("try")
1195 private boolean splitIfAtPhi(SimplifierTool tool) {
1196 if (!(predecessor() instanceof MergeNode)) {
1197 return false;
1198 }
1199 MergeNode merge = (MergeNode) predecessor();
1200 if (merge.forwardEndCount() == 1) {
1201 // Don't bother.
1202 return false;
1203 }
1204 if (merge.getUsageCount() != 1 || merge.phis().count() != 1) {
1205 // Don't trigger with multiple phis. Would require more rewiring.
1206 // Most of the time the additional phis are memory phis that are removed after
1207 // fixed read phase.
1208 return false;
1209 }
1210 if (graph().getGuardsStage().areFrameStatesAtSideEffects() && merge.stateAfter() == null) {
1211 return false;
1212 }
1213
1214 PhiNode generalPhi = merge.phis().first();
1215 if (!(generalPhi instanceof ValuePhiNode)) {
1216 return false;
1217 }
1218
1219 ValuePhiNode phi = (ValuePhiNode) generalPhi;
1220
1221 EconomicMap<Node, NodeColor> coloredNodes = EconomicMap.create(Equivalence.IDENTITY, 8);
1222
1223 /*
1224 * Check that the condition uses the phi and that there is only one user of the condition
1225 * expression.
1226 */
1227 if (!conditionUses(condition(), phi, coloredNodes)) {
1228 return false;
1229 }
1230
1231 if (!mayRemoveSplit(merge)) {
1232 return false;
1233 }
1234
1235 LogicNode[] results = new LogicNode[merge.forwardEndCount()];
1236 boolean success = false;
1237 for (int i = 0; i < results.length; ++i) {
1238 ValueNode value = phi.valueAt(i);
1239 LogicNode curResult = computeCondition(tool, condition, phi, value);
1240 if (curResult != condition) {
1241 for (Node n : curResult.inputs()) {
1242 if (n instanceof ConstantNode || n instanceof ParameterNode || n instanceof FixedNode) {
1243 // Constant inputs or parameters or fixed nodes are OK.
1244 } else if (n == value) {
1245 // References to the value itself are also OK.
1246 } else {
1247 // Input may cause scheduling issues.
1248 curResult = condition;
1249 break;
1250 }
1251 }
1252 success = true;
1253 }
1254 results[i] = curResult;
1255 }
1256
1257 if (!success) {
1258 return false;
1259 }
1260
1261 for (Node usage : phi.usages()) {
1262 if (usage == merge.stateAfter()) {
1263 // This usage can be ignored, because it is directly in the state after.
1264 } else {
1265 NodeColor color = colorUsage(coloredNodes, usage, merge, this.trueSuccessor(), this.falseSuccessor());
1266 if (color == NodeColor.MIXED) {
1267 return false;
1268 }
1269 }
1270 }
1271
1272 /*
1273 * We could additionally filter for the case that at least some of the Phi inputs or one of
1274 * the condition inputs are constants but there are cases where a non-constant is
1275 * simplifiable, usually where the stamp allows the question to be answered.
1276 */
1277
1278 /* Each successor of the if gets a new merge if needed. */
1279 MergeNode trueMerge = null;
1280 MergeNode falseMerge = null;
1281 int i = 0;
1282 for (EndNode end : merge.forwardEnds().snapshot()) {
1283 ValueNode value = phi.valueAt(end);
1284 LogicNode result = results[i++];
1285 if (result instanceof LogicConstantNode) {
1286 if (((LogicConstantNode) result).getValue()) {
1287 if (trueMerge == null) {
1288 trueMerge = insertMerge(trueSuccessor(), phi, merge.stateAfter(), tool);
1289 replaceNodesInBranch(coloredNodes, NodeColor.TRUE_BRANCH, phi, trueMerge.phis().first());
1290 }
1291 trueMerge.phis().first().addInput(value);
1292 trueMerge.addForwardEnd(end);
1293 } else {
1294 if (falseMerge == null) {
1295 falseMerge = insertMerge(falseSuccessor(), phi, merge.stateAfter(), tool);
1296 replaceNodesInBranch(coloredNodes, NodeColor.FALSE_BRANCH, phi, falseMerge.phis().first());
1297 }
1298 falseMerge.phis().first().addInput(value);
1299 falseMerge.addForwardEnd(end);
1300 }
1301 merge.removeEnd(end);
1302 } else if (result != condition) {
1303 // Build a new IfNode using the new condition
1304 BeginNode trueBegin = graph().add(new BeginNode());
1305 trueBegin.setNodeSourcePosition(trueSuccessor().getNodeSourcePosition());
1306 BeginNode falseBegin = graph().add(new BeginNode());
1307 falseBegin.setNodeSourcePosition(falseSuccessor().getNodeSourcePosition());
1308
1309 if (result.graph() == null) {
1310 result = graph().addOrUniqueWithInputs(result);
1311 result.setNodeSourcePosition(condition.getNodeSourcePosition());
1312 }
1313 IfNode newIfNode = graph().add(new IfNode(result, trueBegin, falseBegin, trueSuccessorProbability));
1314 newIfNode.setNodeSourcePosition(getNodeSourcePosition());
1315
1316 if (trueMerge == null) {
1317 trueMerge = insertMerge(trueSuccessor(), phi, merge.stateAfter(), tool);
1318 replaceNodesInBranch(coloredNodes, NodeColor.TRUE_BRANCH, phi, trueMerge.phis().first());
1319 }
1320 trueMerge.phis().first().addInput(value);
1321 trueBegin.setNext(graph().add(new EndNode()));
1322 trueMerge.addForwardEnd((EndNode) trueBegin.next());
1323
1324 if (falseMerge == null) {
1325 falseMerge = insertMerge(falseSuccessor(), phi, merge.stateAfter(), tool);
1326 replaceNodesInBranch(coloredNodes, NodeColor.FALSE_BRANCH, phi, falseMerge.phis().first());
1327 }
1328 falseMerge.phis().first().addInput(value);
1329 falseBegin.setNext(graph().add(new EndNode()));
1330 falseMerge.addForwardEnd((EndNode) falseBegin.next());
1331
1332 merge.removeEnd(end);
1333 ((FixedWithNextNode) end.predecessor()).setNext(newIfNode);
1334 end.safeDelete();
1335 }
1336 }
1337
1338 cleanupMerge(merge);
1339 cleanupMerge(trueMerge);
1340 cleanupMerge(falseMerge);
1341
1342 return true;
1343 }
1344
1345 private static void replaceNodesInBranch(EconomicMap<Node, NodeColor> coloredNodes, NodeColor branch, ValuePhiNode phi, ValueNode newValue) {
1346 for (Node n : phi.usages().snapshot()) {
1347 if (coloredNodes.get(n) == branch) {
1348 n.replaceAllInputs(phi, newValue);
1349 } else if (coloredNodes.get(n) == NodeColor.PHI_MIXED) {
1350 assert n instanceof PhiNode;
1351 PhiNode phiNode = (PhiNode) n;
1352 AbstractMergeNode merge = phiNode.merge();
1353 for (int i = 0; i < merge.forwardEndCount(); ++i) {
1354 if (phiNode.valueAt(i) == phi && coloredNodes.get(merge.forwardEndAt(i)) == branch) {
1355 phiNode.setValueAt(i, newValue);
1356 }
1357 }
1358 }
1359 }
1360 }
1361
1362 private NodeColor colorUsage(EconomicMap<Node, NodeColor> coloredNodes, Node node, MergeNode merge, AbstractBeginNode trueSucc, AbstractBeginNode falseSucc) {
1363 NodeColor color = coloredNodes.get(node);
1364 if (color == null) {
1365
1366 if (coloredNodes.size() >= MAX_USAGE_COLOR_SET_SIZE) {
1367 return NodeColor.MIXED;
1368 }
1369
1370 coloredNodes.put(node, NodeColor.MIXED);
1371
1372 if (node == merge) {
1373 color = NodeColor.MIXED;
1374 } else if (node == trueSucc) {
1375 color = NodeColor.TRUE_BRANCH;
1376 } else if (node == falseSucc) {
1377 color = NodeColor.FALSE_BRANCH;
1378 } else {
1379 if (node instanceof AbstractMergeNode) {
1380 AbstractMergeNode mergeNode = (AbstractMergeNode) node;
1381 NodeColor combinedColor = null;
1382 for (int i = 0; i < mergeNode.forwardEndCount(); ++i) {
1383 NodeColor curColor = colorUsage(coloredNodes, mergeNode.forwardEndAt(i), merge, trueSucc, falseSucc);
1384 if (combinedColor == null) {
1385 combinedColor = curColor;
1386 } else if (combinedColor != curColor) {
1387 combinedColor = NodeColor.MIXED;
1388 break;
1389 }
1390 }
1391 color = combinedColor;
1392 } else if (node instanceof StartNode) {
1393 color = NodeColor.MIXED;
1394 } else if (node instanceof FixedNode) {
1395 FixedNode fixedNode = (FixedNode) node;
1396 Node predecessor = fixedNode.predecessor();
1397 assert predecessor != null : fixedNode;
1398 color = colorUsage(coloredNodes, predecessor, merge, trueSucc, falseSucc);
1399 } else if (node instanceof PhiNode) {
1400 PhiNode phiNode = (PhiNode) node;
1401 AbstractMergeNode phiMerge = phiNode.merge();
1402
1403 if (phiMerge instanceof LoopBeginNode) {
1404 color = colorUsage(coloredNodes, phiMerge, merge, trueSucc, falseSucc);
1405 } else {
1406
1407 for (int i = 0; i < phiMerge.forwardEndCount(); ++i) {
1408 NodeColor curColor = colorUsage(coloredNodes, phiMerge.forwardEndAt(i), merge, trueSucc, falseSucc);
1409 if (curColor != NodeColor.TRUE_BRANCH && curColor != NodeColor.FALSE_BRANCH) {
1410 color = NodeColor.MIXED;
1411 break;
1412 }
1413 }
1414
1415 if (color == null) {
1416 // Each of the inputs to the phi are either coming unambigously from
1417 // true or false branch.
1418 color = NodeColor.PHI_MIXED;
1419 assert node instanceof PhiNode;
1420 }
1421 }
1422 } else {
1423 NodeColor combinedColor = null;
1424 for (Node n : node.usages()) {
1425 if (n != node) {
1426 NodeColor curColor = colorUsage(coloredNodes, n, merge, trueSucc, falseSucc);
1427 if (combinedColor == null) {
1428 combinedColor = curColor;
1429 } else if (combinedColor != curColor) {
1430 combinedColor = NodeColor.MIXED;
1431 break;
1432 }
1433 }
1434 }
1435 if (combinedColor == NodeColor.PHI_MIXED) {
1436 combinedColor = NodeColor.MIXED;
1437 }
1438 if (combinedColor == null) {
1439 // Floating node without usages => association unclear.
1440 combinedColor = NodeColor.MIXED;
1441 }
1442 color = combinedColor;
1443 }
1444 }
1445
1446 assert color != null : node;
1447 coloredNodes.put(node, color);
1448 }
1449 return color;
1450 }
1451
1452 /**
1453 * @param condition
1454 * @param phi
1455 * @param coloredNodes
1456 * @return true if the passed in {@code condition} uses {@code phi} and the condition is only
1457 * used once. Since the phi will go dead the condition using it will also have to be
1458 * dead after the optimization.
1459 */
1460 private static boolean conditionUses(LogicNode condition, PhiNode phi, EconomicMap<Node, NodeColor> coloredNodes) {
1461 if (!condition.hasExactlyOneUsage()) {
1462 return false;
1463 }
1464 if (condition instanceof ShortCircuitOrNode) {
1465 if (condition.graph().getGuardsStage().areDeoptsFixed()) {
1466 /*
1467 * It can be unsafe to simplify a ShortCircuitOr before deopts are fixed because
1468 * conversion to guards assumes that all the required conditions are being tested.
1469 * Simplfying the condition based on context before this happens may lose a
1470 * condition.
1471 */
1472 ShortCircuitOrNode orNode = (ShortCircuitOrNode) condition;
1473 return (conditionUses(orNode.x, phi, coloredNodes) || conditionUses(orNode.y, phi, coloredNodes));
1474 }
1475 } else if (condition instanceof Canonicalizable.Unary<?>) {
1476 Canonicalizable.Unary<?> unary = (Canonicalizable.Unary<?>) condition;
1477 if (unary.getValue() == phi) {
1478 coloredNodes.put(condition, NodeColor.CONDITION_USAGE);
1479 return true;
1480 }
1481 } else if (condition instanceof Canonicalizable.Binary<?>) {
1482 Canonicalizable.Binary<?> binary = (Canonicalizable.Binary<?>) condition;
1483 if (binary.getX() == phi || binary.getY() == phi) {
1484 coloredNodes.put(condition, NodeColor.CONDITION_USAGE);
1485 return true;
1486 }
1487 }
1488 return false;
1489 }
1490
1491 /**
1492 * Canonicalize {@code} condition using {@code value} in place of {@code phi}.
1493 *
1494 * @param tool
1495 * @param condition
1496 * @param phi
1497 * @param value
1498 * @return an improved LogicNode or the original condition
1499 */
1500 @SuppressWarnings("unchecked")
1501 private static LogicNode computeCondition(SimplifierTool tool, LogicNode condition, PhiNode phi, Node value) {
1502 if (condition instanceof ShortCircuitOrNode) {
1503 if (condition.graph().getGuardsStage().areDeoptsFixed() && !condition.graph().isAfterExpandLogic()) {
1504 ShortCircuitOrNode orNode = (ShortCircuitOrNode) condition;
1505 LogicNode resultX = computeCondition(tool, orNode.x, phi, value);
1506 LogicNode resultY = computeCondition(tool, orNode.y, phi, value);
1507 if (resultX != orNode.x || resultY != orNode.y) {
1508 LogicNode result = orNode.canonical(tool, resultX, resultY);
1509 if (result != orNode) {
1510 return result;
1511 }
1512 /*
1513 * Create a new node to carry the optimized inputs.
1514 */
1515 ShortCircuitOrNode newOr = new ShortCircuitOrNode(resultX, orNode.xNegated, resultY,
1516 orNode.yNegated, orNode.getShortCircuitProbability());
1517 return newOr.canonical(tool);
1518 }
1519 return orNode;
1520 }
1521 } else if (condition instanceof Canonicalizable.Binary<?>) {
1522 Canonicalizable.Binary<Node> compare = (Canonicalizable.Binary<Node>) condition;
1523 if (compare.getX() == phi || compare.getY() == phi) {
1524 return (LogicNode) compare.canonical(tool, compare.getX() == phi ? value : compare.getX(), compare.getY() == phi ? value : compare.getY());
1525 }
1526 } else if (condition instanceof Canonicalizable.Unary<?>) {
1527 Canonicalizable.Unary<Node> compare = (Canonicalizable.Unary<Node>) condition;
1528 if (compare.getValue() == phi) {
1529 return (LogicNode) compare.canonical(tool, value);
1530 }
1531 }
1532 if (condition instanceof Canonicalizable) {
1533 return (LogicNode) ((Canonicalizable) condition).canonical(tool);
1534 }
1535 return condition;
1536 }
1537
1538 private void cleanupMerge(MergeNode merge) {
1539 if (merge != null && merge.isAlive()) {
1540 if (merge.forwardEndCount() == 0) {
1541 GraphUtil.killCFG(merge);
1542 } else if (merge.forwardEndCount() == 1) {
1543 graph().reduceTrivialMerge(merge);
1544 }
1545 }
1546 }
1547
1548 @SuppressWarnings("try")
1549 private MergeNode insertMerge(AbstractBeginNode begin, ValuePhiNode oldPhi, FrameState stateAfter, SimplifierTool tool) {
1550 MergeNode merge = graph().add(new MergeNode());
1551
1552 AbstractBeginNode newBegin;
1553 try (DebugCloseable position = begin.withNodeSourcePosition()) {
1554 newBegin = graph().add(new BeginNode());
1555 begin.replaceAtPredecessor(newBegin);
1556 newBegin.setNext(begin);
1557 }
1558
1559 FixedNode next = newBegin.next();
1560 next.replaceAtPredecessor(merge);
1561 newBegin.setNext(graph().add(new EndNode()));
1562 merge.addForwardEnd((EndNode) newBegin.next());
1563
1564 ValuePhiNode phi = begin.graph().addOrUnique(new ValuePhiNode(oldPhi.stamp(NodeView.DEFAULT), merge));
1565 phi.addInput(oldPhi);
1566
1567 if (stateAfter != null) {
1568 FrameState newState = stateAfter.duplicate();
1569 newState.replaceAllInputs(oldPhi, phi);
1570 merge.setStateAfter(newState);
1571 }
1572 merge.setNext(next);
1573 tool.addToWorkList(begin);
1574 return merge;
1575 }
1576
1577 /**
1578 * Tries to connect code that initializes a variable directly with the successors of an if
1579 * construct that switches on the variable. For example, the pseudo code below:
1580 *
1581 * <pre>
1582 * contains(list, e, yes, no) {
1583 * if (list == null || e == null) {
1584 * condition = false;
1585 * } else {
1586 * condition = false;
1587 * for (i in list) {
1588 * if (i.equals(e)) {
1589 * condition = true;
1590 * break;
1591 * }
1592 * }
1593 * }
1594 * if (condition) {
1595 * return yes;
1596 * } else {
1597 * return no;
1598 * }
1599 * }
1600 * </pre>
1601 *
1602 * will be transformed into:
1603 *
1604 * <pre>
1605 * contains(list, e, yes, no) {
1606 * if (list == null || e == null) {
1607 * return no;
1608 * } else {
1609 * condition = false;
1610 * for (i in list) {
1611 * if (i.equals(e)) {
1612 * return yes;
1613 * }
1614 * }
1615 * return no;
1616 * }
1617 * }
1618 * </pre>
1619 *
1620 * @return true if a transformation was made, false otherwise
1621 */
1622 private boolean removeIntermediateMaterialization(SimplifierTool tool) {
1623 if (!(predecessor() instanceof AbstractMergeNode) || predecessor() instanceof LoopBeginNode) {
1624 return false;
1625 }
1626 AbstractMergeNode merge = (AbstractMergeNode) predecessor();
1627
1628 if (!(condition() instanceof CompareNode)) {
1629 return false;
1630 }
1631
1632 CompareNode compare = (CompareNode) condition();
1633 if (compare.getUsageCount() != 1) {
1634 return false;
1635 }
1636
1637 // Only consider merges with a single usage that is both a phi and an operand of the
1638 // comparison
1639 NodeIterable<Node> mergeUsages = merge.usages();
1640 if (mergeUsages.count() != 1) {
1641 return false;
1642 }
1643 Node singleUsage = mergeUsages.first();
1644 if (!(singleUsage instanceof ValuePhiNode) || (singleUsage != compare.getX() && singleUsage != compare.getY())) {
1645 return false;
1646 }
1647
1648 // Ensure phi is used by at most the comparison and the merge's frame state (if any)
1649 ValuePhiNode phi = (ValuePhiNode) singleUsage;
1650 NodeIterable<Node> phiUsages = phi.usages();
1651 for (Node usage : phiUsages) {
1652 if (usage == compare) {
1653 continue;
1654 }
1655 if (usage == merge.stateAfter()) {
1656 continue;
1657 }
1658 // Checkstyle: stop
1659 // @formatter:off
1660 //
1661 // We also want to allow the usage to be on the loop-proxy if one of the branches is a
1662 // loop exit.
1663 //
1664 // This pattern:
1665 //
1666 // if------->cond
1667 // / \
1668 // begin begin
1669 // | |
1670 // end end C1 V2
1671 // \ / \ /
1672 // merge---------->phi<------ C1
1673 // | ^ \ /
1674 // if-------------|-------->==
1675 // / \ |
1676 // A B<--------Proxy
1677 //
1678 // Must be simplified to:
1679 //
1680 // if---------------------->cond
1681 // / \
1682 // A B<--------Proxy------>V2
1683 //
1684 // @formatter:on
1685 // Checkstyle: resume
1686 if (usage instanceof ValueProxyNode) {
1687 ValueProxyNode proxy = (ValueProxyNode) usage;
1688 if (proxy.proxyPoint() == trueSuccessor || proxy.proxyPoint() == falseSuccessor) {
1689 continue;
1690 }
1691 }
1692 return false;
1693 }
1694
1695 List<EndNode> mergePredecessors = merge.cfgPredecessors().snapshot();
1696 assert phi.valueCount() == merge.forwardEndCount();
1697
1698 Constant[] xs = constantValues(compare.getX(), merge, false);
1699 Constant[] ys = constantValues(compare.getY(), merge, false);
1700 if (xs == null || ys == null) {
1701 return false;
1702 }
1703
1704 if (!mayRemoveSplit(merge)) {
1705 return false;
1706 }
1707
1708 List<EndNode> falseEnds = new ArrayList<>(mergePredecessors.size());
1709 List<EndNode> trueEnds = new ArrayList<>(mergePredecessors.size());
1710 EconomicMap<AbstractEndNode, ValueNode> phiValues = EconomicMap.create(Equivalence.IDENTITY, mergePredecessors.size());
1711
1712 AbstractBeginNode oldFalseSuccessor = falseSuccessor();
1713 AbstractBeginNode oldTrueSuccessor = trueSuccessor();
1714
1715 setFalseSuccessor(null);
1716 setTrueSuccessor(null);
1717
1718 Iterator<EndNode> ends = mergePredecessors.iterator();
1719 for (int i = 0; i < xs.length; i++) {
1720 EndNode end = ends.next();
1721 phiValues.put(end, phi.valueAt(end));
1722 if (compare.condition().foldCondition(xs[i], ys[i], tool.getConstantReflection(), compare.unorderedIsTrue())) {
1723 trueEnds.add(end);
1724 } else {
1725 falseEnds.add(end);
1726 }
1727 }
1728 assert !ends.hasNext();
1729 assert falseEnds.size() + trueEnds.size() == xs.length;
1730
1731 connectEnds(falseEnds, phi, phiValues, oldFalseSuccessor, merge, tool);
1732 connectEnds(trueEnds, phi, phiValues, oldTrueSuccessor, merge, tool);
1733
1734 if (this.trueSuccessorProbability == 0.0) {
1735 for (AbstractEndNode endNode : trueEnds) {
1736 propagateZeroProbability(endNode);
1737 }
1738 }
1739
1740 if (this.trueSuccessorProbability == 1.0) {
1741 for (AbstractEndNode endNode : falseEnds) {
1742 propagateZeroProbability(endNode);
1743 }
1744 }
1745
1746 /*
1747 * Remove obsolete ends only after processing all ends, otherwise oldTrueSuccessor or
1748 * oldFalseSuccessor might have been removed if it is a LoopExitNode.
1749 */
1750 if (falseEnds.isEmpty()) {
1751 GraphUtil.killCFG(oldFalseSuccessor);
1752 }
1753 if (trueEnds.isEmpty()) {
1754 GraphUtil.killCFG(oldTrueSuccessor);
1755 }
1756 GraphUtil.killCFG(merge);
1757
1758 assert !merge.isAlive() : merge;
1759 assert !phi.isAlive() : phi;
1760 assert !compare.isAlive() : compare;
1761 assert !this.isAlive() : this;
1762
1763 return true;
1764 }
1765
1766 private boolean mayRemoveSplit(AbstractMergeNode merge) {
1767
1768 if (merge.stateAfter() != null && (!checkFrameState(trueSuccessor, MAX_FRAMESTATE_SEARCH_DEPTH) || !checkFrameState(trueSuccessor, MAX_FRAMESTATE_SEARCH_DEPTH))) {
1769 return false;
1770 }
1771
1772 return true;
1773 }
1774
1775 private static void propagateZeroProbability(FixedNode startNode) {
1776 Node prev = null;
1777 for (FixedNode node : GraphUtil.predecessorIterable(startNode)) {
1778 if (node instanceof IfNode) {
1779 IfNode ifNode = (IfNode) node;
1780 if (ifNode.trueSuccessor() == prev) {
1781 if (ifNode.trueSuccessorProbability == 0.0) {
1782 return;
1783 } else if (ifNode.trueSuccessorProbability == 1.0) {
1784 continue;
1785 } else {
1786 ifNode.setTrueSuccessorProbability(0.0);
1787 return;
1788 }
1789 } else if (ifNode.falseSuccessor() == prev) {
1790 if (ifNode.trueSuccessorProbability == 1.0) {
1791 return;
1792 } else if (ifNode.trueSuccessorProbability == 0.0) {
1793 continue;
1794 } else {
1795 ifNode.setTrueSuccessorProbability(1.0);
1796 return;
1797 }
1798 } else {
1799 throw new GraalError("Illegal state");
1800 }
1801 } else if (node instanceof AbstractMergeNode && !(node instanceof LoopBeginNode)) {
1802 for (AbstractEndNode endNode : ((AbstractMergeNode) node).cfgPredecessors()) {
1803 propagateZeroProbability(endNode);
1804 }
1805 return;
1806 }
1807 prev = node;
1808 }
1809 }
1810
1811 /**
1812 * Snippet lowerings may produce patterns without a frame state on the merge. We need to take
1813 * extra care when optimizing these patterns.
1814 */
1815 private static boolean checkFrameState(FixedNode start, int maxDepth) {
1816 if (maxDepth == 0) {
1817 return false;
1818 }
1819 FixedNode node = start;
1820 while (true) {
1821 if (node instanceof AbstractMergeNode) {
1822 AbstractMergeNode mergeNode = (AbstractMergeNode) node;
1823 if (mergeNode.stateAfter() == null) {
1824 return false;
1825 } else {
1826 return true;
1827 }
1828 } else if (node instanceof StateSplit) {
1829 StateSplit stateSplitNode = (StateSplit) node;
1830 if (stateSplitNode.stateAfter() != null) {
1831 return true;
1832 }
1833 }
1834
1835 if (node instanceof ControlSplitNode) {
1836 ControlSplitNode controlSplitNode = (ControlSplitNode) node;
1837 for (Node succ : controlSplitNode.cfgSuccessors()) {
1838 if (checkFrameState((FixedNode) succ, maxDepth - 1)) {
1839 return true;
1840 }
1841 }
1842 return false;
1843 } else if (node instanceof FixedWithNextNode) {
1844 FixedWithNextNode fixedWithNextNode = (FixedWithNextNode) node;
1845 node = fixedWithNextNode.next();
1846 } else if (node instanceof AbstractEndNode) {
1847 AbstractEndNode endNode = (AbstractEndNode) node;
1848 node = endNode.merge();
1849 } else if (node instanceof ControlSinkNode) {
1850 return true;
1851 } else {
1852 assert false : "unexpected node";
1853 return false;
1854 }
1855 }
1856 }
1857
1858 /**
1859 * Connects a set of ends to a given successor, inserting a merge node if there is more than one
1860 * end. If {@code ends} is not empty, then {@code successor} is added to {@code tool}'s
1861 * {@linkplain SimplifierTool#addToWorkList(org.graalvm.compiler.graph.Node) work list}.
1862 *
1863 * @param phi the original single-usage phi of the preceding merge
1864 * @param phiValues the values of the phi at the merge, keyed by the merge ends
1865 * @param oldMerge the merge being removed
1866 */
1867 private void connectEnds(List<EndNode> ends, ValuePhiNode phi, EconomicMap<AbstractEndNode, ValueNode> phiValues, AbstractBeginNode successor, AbstractMergeNode oldMerge, SimplifierTool tool) {
1868 if (!ends.isEmpty()) {
1869 // If there was a value proxy usage, then the proxy needs a new value.
1870 ValueProxyNode valueProxy = null;
1871 if (successor instanceof LoopExitNode) {
1872 for (Node usage : phi.usages()) {
1873 if (usage instanceof ValueProxyNode && ((ValueProxyNode) usage).proxyPoint() == successor) {
1874 valueProxy = (ValueProxyNode) usage;
1875 }
1876 }
1877 }
1878 final ValueProxyNode proxy = valueProxy;
1879 if (ends.size() == 1) {
1880 AbstractEndNode end = ends.get(0);
1881 if (proxy != null) {
1882 phi.replaceAtUsages(phiValues.get(end), n -> n == proxy);
1883 }
1884 ((FixedWithNextNode) end.predecessor()).setNext(successor);
1885 oldMerge.removeEnd(end);
1886 GraphUtil.killCFG(end);
1887 } else {
1888 // Need a new phi in case the frame state is used by more than the merge being
1889 // removed.
1890 NodeView view = NodeView.from(tool);
1891 AbstractMergeNode newMerge = graph().add(new MergeNode());
1892 PhiNode oldPhi = (PhiNode) oldMerge.usages().first();
1893 PhiNode newPhi = graph().addWithoutUnique(new ValuePhiNode(oldPhi.stamp(view), newMerge));
1894
1895 if (proxy != null) {
1896 phi.replaceAtUsages(newPhi, n -> n == proxy);
1897 }
1898
1899 for (EndNode end : ends) {
1900 newPhi.addInput(phiValues.get(end));
1901 newMerge.addForwardEnd(end);
1902 }
1903
1904 FrameState stateAfter = oldMerge.stateAfter();
1905 if (stateAfter != null) {
1906 stateAfter = stateAfter.duplicate();
1907 stateAfter.replaceFirstInput(oldPhi, newPhi);
1908 newMerge.setStateAfter(stateAfter);
1909 }
1910
1911 newMerge.setNext(successor);
1912 }
1913 tool.addToWorkList(successor);
1914 }
1915 }
1916
1917 /**
1918 * Gets an array of constants derived from a node that is either a {@link ConstantNode} or a
1919 * {@link PhiNode} whose input values are all constants. The length of the returned array is
1920 * equal to the number of ends terminating in a given merge node.
1921 *
1922 * @return null if {@code node} is neither a {@link ConstantNode} nor a {@link PhiNode} whose
1923 * input values are all constants
1924 */
1925 public static Constant[] constantValues(ValueNode node, AbstractMergeNode merge, boolean allowNull) {
1926 if (node.isConstant()) {
1927 Constant[] result = new Constant[merge.forwardEndCount()];
1928 Arrays.fill(result, node.asConstant());
1929 return result;
1930 }
1931
1932 if (node instanceof PhiNode) {
1933 PhiNode phi = (PhiNode) node;
1934 if (phi.merge() == merge && phi instanceof ValuePhiNode && phi.valueCount() == merge.forwardEndCount()) {
1935 Constant[] result = new Constant[merge.forwardEndCount()];
1936 int i = 0;
1937 for (ValueNode n : phi.values()) {
1938 if (!allowNull && !n.isConstant()) {
1939 return null;
1940 }
1941 result[i++] = n.asConstant();
1942 }
1943 return result;
1944 }
1945 }
1946
1947 return null;
1948 }
1949
1950 @Override
1951 public AbstractBeginNode getPrimarySuccessor() {
1952 return null;
1953 }
1954
1955 public AbstractBeginNode getSuccessor(boolean result) {
1956 return result ? this.trueSuccessor() : this.falseSuccessor();
1957 }
1958
1959 @Override
1960 public boolean setProbability(AbstractBeginNode successor, double value) {
1961 if (successor == this.trueSuccessor()) {
1962 this.setTrueSuccessorProbability(value);
1963 return true;
1964 } else if (successor == this.falseSuccessor()) {
1965 this.setTrueSuccessorProbability(1.0 - value);
1966 return true;
1967 }
1968 return false;
1969 }
1970
1971 @Override
1972 public int getSuccessorCount() {
1973 return 2;
1974 }
1975 }