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