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_2;
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_2, 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().addOrUnique(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 graph().removeSplitPropagate(this, trueBegin);
730 tool.addToWorkList(trueBegin);
731 if (condition() != null) {
732 GraphUtil.tryKillUnused(condition());
733 }
734 if (merge.isAlive() && merge.forwardEndCount() > 1) {
735 for (FixedNode end : merge.forwardEnds()) {
736 Node cur = end;
737 while (cur != null && cur.predecessor() instanceof BeginNode) {
738 cur = cur.predecessor();
739 }
740 if (cur != null && cur.predecessor() instanceof IfNode) {
741 tool.addToWorkList(cur.predecessor());
742 }
743 }
744 }
745 }
746
747 private ValueNode canonicalizeConditionalCascade(ValueNode trueValue, ValueNode falseValue) {
748 if (trueValue.getStackKind() != falseValue.getStackKind()) {
749 return null;
750 }
751 if (trueValue.getStackKind() != JavaKind.Int && trueValue.getStackKind() != JavaKind.Long) {
752 return null;
753 }
754 if (trueValue.isConstant() && falseValue.isConstant()) {
755 return graph().unique(new ConditionalNode(condition(), trueValue, falseValue));
756 } else if (!graph().isAfterExpandLogic()) {
757 ConditionalNode conditional = null;
758 ValueNode constant = null;
759 boolean negateCondition;
760 if (trueValue instanceof ConditionalNode && falseValue.isConstant()) {
761 conditional = (ConditionalNode) trueValue;
762 constant = falseValue;
763 negateCondition = true;
764 } else if (falseValue instanceof ConditionalNode && trueValue.isConstant()) {
765 conditional = (ConditionalNode) falseValue;
766 constant = trueValue;
767 negateCondition = false;
768 } else {
769 return null;
770 }
771 boolean negateConditionalCondition = false;
772 ValueNode otherValue = null;
773 if (constant == conditional.trueValue()) {
774 otherValue = conditional.falseValue();
775 negateConditionalCondition = false;
776 } else if (constant == conditional.falseValue()) {
777 otherValue = conditional.trueValue();
778 negateConditionalCondition = true;
779 }
780 if (otherValue != null && otherValue.isConstant()) {
781 double shortCutProbability = probability(trueSuccessor());
782 LogicNode newCondition = LogicNode.or(condition(), negateCondition, conditional.condition(), negateConditionalCondition, shortCutProbability);
783 return graph().unique(new ConditionalNode(newCondition, constant, otherValue));
784 } else if (!negateCondition && constant.isJavaConstant() && conditional.trueValue().isJavaConstant() && conditional.falseValue().isJavaConstant()) {
785 IntegerLessThanNode lessThan = null;
786 IntegerEqualsNode equals = null;
787 if (condition() instanceof IntegerLessThanNode && conditional.condition() instanceof IntegerEqualsNode && constant.asJavaConstant().asLong() == -1 &&
788 conditional.trueValue().asJavaConstant().asLong() == 0 && conditional.falseValue().asJavaConstant().asLong() == 1) {
789 lessThan = (IntegerLessThanNode) condition();
790 equals = (IntegerEqualsNode) conditional.condition();
791 } else if (condition() instanceof IntegerEqualsNode && conditional.condition() instanceof IntegerLessThanNode && constant.asJavaConstant().asLong() == 0 &&
792 conditional.trueValue().asJavaConstant().asLong() == -1 && conditional.falseValue().asJavaConstant().asLong() == 1) {
793 lessThan = (IntegerLessThanNode) conditional.condition();
794 equals = (IntegerEqualsNode) condition();
795 }
796 if (lessThan != null) {
797 assert equals != null;
798 if ((lessThan.getX() == equals.getX() && lessThan.getY() == equals.getY()) || (lessThan.getX() == equals.getY() && lessThan.getY() == equals.getX())) {
799 return graph().unique(new NormalizeCompareNode(lessThan.getX(), lessThan.getY(), conditional.trueValue().stamp().getStackKind(), false));
800 }
801 }
802 }
803 }
804 return null;
805 }
806
807 /**
808 * Take an if that is immediately dominated by a merge with a single phi and split off any paths
809 * where the test would be statically decidable creating a new merge below the approriate side
810 * of the IfNode. Any undecidable tests will continue to use the original IfNode.
811 *
812 * @param tool
813 */
814 private boolean splitIfAtPhi(SimplifierTool tool) {
815 if (graph().getGuardsStage().areFrameStatesAtSideEffects()) {
816 // Disabled until we make sure we have no FrameState-less merges at this stage
817 return false;
818 }
819
820 if (!(predecessor() instanceof MergeNode)) {
821 return false;
822 }
823 MergeNode merge = (MergeNode) predecessor();
824 if (merge.forwardEndCount() == 1) {
825 // Don't bother.
826 return false;
827 }
828 if (merge.usages().count() != 1 || merge.phis().count() != 1) {
829 return false;
830 }
831 if (merge.stateAfter() != null) {
832 /* We'll get the chance to simplify this after frame state assignment. */
833 return false;
834 }
835 PhiNode phi = merge.phis().first();
836 if (phi.usages().count() != 1) {
837 /*
838 * For simplicity the below code assumes assumes the phi goes dead at the end so skip
839 * this case.
840 */
841 return false;
842 }
843
844 /*
845 * Check that the condition uses the phi and that there is only one user of the condition
846 * expression.
847 */
848 if (!conditionUses(condition(), phi)) {
849 return false;
850 }
851
852 /*
853 * We could additionally filter for the case that at least some of the Phi inputs or one of
854 * the condition inputs are constants but there are cases where a non-constant is
855 * simplifiable, usually where the stamp allows the question to be answered.
856 */
857
858 /* Each successor of the if gets a new merge if needed. */
859 MergeNode trueMerge = null;
860 MergeNode falseMerge = null;
861 assert merge.stateAfter() == null;
862
863 for (EndNode end : merge.forwardEnds().snapshot()) {
864 Node value = phi.valueAt(end);
865 LogicNode result = computeCondition(tool, condition, phi, value);
866 if (result instanceof LogicConstantNode) {
867 merge.removeEnd(end);
868 if (((LogicConstantNode) result).getValue()) {
869 if (trueMerge == null) {
870 trueMerge = insertMerge(trueSuccessor());
871 }
872 trueMerge.addForwardEnd(end);
873 } else {
874 if (falseMerge == null) {
875 falseMerge = insertMerge(falseSuccessor());
876 }
877 falseMerge.addForwardEnd(end);
878 }
879 } else if (result != condition) {
880 // Build a new IfNode using the new condition
881 BeginNode trueBegin = graph().add(new BeginNode());
882 BeginNode falseBegin = graph().add(new BeginNode());
883
884 if (result.graph() == null) {
885 result = graph().addOrUniqueWithInputs(result);
886 }
887 IfNode newIfNode = graph().add(new IfNode(result, trueBegin, falseBegin, trueSuccessorProbability));
888 merge.removeEnd(end);
889 ((FixedWithNextNode) end.predecessor()).setNext(newIfNode);
890
891 if (trueMerge == null) {
892 trueMerge = insertMerge(trueSuccessor());
893 }
894 trueBegin.setNext(graph().add(new EndNode()));
895 trueMerge.addForwardEnd((EndNode) trueBegin.next());
896
897 if (falseMerge == null) {
898 falseMerge = insertMerge(falseSuccessor());
899 }
900 falseBegin.setNext(graph().add(new EndNode()));
901 falseMerge.addForwardEnd((EndNode) falseBegin.next());
902
903 end.safeDelete();
904 }
905 }
906
907 transferProxies(trueSuccessor(), trueMerge);
908 transferProxies(falseSuccessor(), falseMerge);
909
910 cleanupMerge(merge);
911 cleanupMerge(trueMerge);
912 cleanupMerge(falseMerge);
913
914 return true;
915 }
916
917 /**
918 * @param condition
919 * @param phi
920 * @return true if the passed in {@code condition} uses {@code phi} and the condition is only
921 * used once. Since the phi will go dead the condition using it will also have to be
922 * dead after the optimization.
923 */
924 private static boolean conditionUses(LogicNode condition, PhiNode phi) {
925 if (condition.usages().count() != 1) {
926 return false;
927 }
928 if (condition instanceof ShortCircuitOrNode) {
929 if (condition.graph().getGuardsStage().areDeoptsFixed()) {
930 /*
931 * It can be unsafe to simplify a ShortCircuitOr before deopts are fixed because
932 * conversion to guards assumes that all the required conditions are being tested.
933 * Simplfying the condition based on context before this happens may lose a
934 * condition.
935 */
936 ShortCircuitOrNode orNode = (ShortCircuitOrNode) condition;
937 return (conditionUses(orNode.x, phi) || conditionUses(orNode.y, phi));
938 }
939 } else if (condition instanceof Canonicalizable.Unary<?>) {
940 Canonicalizable.Unary<?> unary = (Canonicalizable.Unary<?>) condition;
941 return unary.getValue() == phi;
942 } else if (condition instanceof Canonicalizable.Binary<?>) {
943 Canonicalizable.Binary<?> binary = (Canonicalizable.Binary<?>) condition;
944 return binary.getX() == phi || binary.getY() == phi;
945 }
946 return false;
947 }
948
949 /**
950 * Canonicalize {@code} condition using {@code value} in place of {@code phi}.
951 *
952 * @param tool
953 * @param condition
954 * @param phi
955 * @param value
956 * @return an improved LogicNode or the original condition
957 */
958 @SuppressWarnings("unchecked")
959 private static LogicNode computeCondition(SimplifierTool tool, LogicNode condition, PhiNode phi, Node value) {
960 if (condition instanceof ShortCircuitOrNode) {
961 if (condition.graph().getGuardsStage().areDeoptsFixed() && !condition.graph().isAfterExpandLogic()) {
962 ShortCircuitOrNode orNode = (ShortCircuitOrNode) condition;
963 LogicNode resultX = computeCondition(tool, orNode.x, phi, value);
964 LogicNode resultY = computeCondition(tool, orNode.y, phi, value);
965 if (resultX != orNode.x || resultY != orNode.y) {
966 LogicNode result = orNode.canonical(tool, resultX, resultY);
967 if (result != orNode) {
968 return result;
969 }
970 /*
971 * Create a new node to carry the optimized inputs.
972 */
973 ShortCircuitOrNode newOr = new ShortCircuitOrNode(resultX, orNode.xNegated, resultY,
974 orNode.yNegated, orNode.getShortCircuitProbability());
975 return newOr.canonical(tool);
976 }
977 return orNode;
978 }
979 } else if (condition instanceof Canonicalizable.Binary<?>) {
980 Canonicalizable.Binary<Node> compare = (Canonicalizable.Binary<Node>) condition;
981 if (compare.getX() == phi) {
982 return (LogicNode) compare.canonical(tool, value, compare.getY());
983 } else if (compare.getY() == phi) {
984 return (LogicNode) compare.canonical(tool, compare.getX(), value);
985 }
986 } else if (condition instanceof Canonicalizable.Unary<?>) {
987 Canonicalizable.Unary<Node> compare = (Canonicalizable.Unary<Node>) condition;
988 if (compare.getValue() == phi) {
989 return (LogicNode) compare.canonical(tool, value);
990 }
991 }
992 if (condition instanceof Canonicalizable) {
993 return (LogicNode) ((Canonicalizable) condition).canonical(tool);
994 }
995 return condition;
996 }
997
998 private static void transferProxies(AbstractBeginNode successor, MergeNode falseMerge) {
999 if (successor instanceof LoopExitNode && falseMerge != null) {
1000 LoopExitNode loopExitNode = (LoopExitNode) successor;
1001 for (ProxyNode proxy : loopExitNode.proxies().snapshot()) {
1002 proxy.replaceFirstInput(successor, falseMerge);
1003 }
1004 }
1005 }
1006
1007 private void cleanupMerge(MergeNode merge) {
1008 if (merge != null && merge.isAlive()) {
1009 if (merge.forwardEndCount() == 0) {
1010 GraphUtil.killCFG(merge);
1011 } else if (merge.forwardEndCount() == 1) {
1012 graph().reduceTrivialMerge(merge);
1013 }
1014 }
1015 }
1016
1017 private MergeNode insertMerge(AbstractBeginNode begin) {
1018 MergeNode merge = graph().add(new MergeNode());
1019 if (!begin.anchored().isEmpty()) {
1020 Object before = null;
1021 before = begin.anchored().snapshot();
1022 begin.replaceAtUsages(InputType.Guard, merge);
1023 begin.replaceAtUsages(InputType.Anchor, merge);
1024 assert begin.anchored().isEmpty() : before + " " + begin.anchored().snapshot();
1025 }
1026
1027 AbstractBeginNode theBegin = begin;
1028 if (begin instanceof LoopExitNode) {
1029 // Insert an extra begin to make it easier.
1030 theBegin = graph().add(new BeginNode());
1031 begin.replaceAtPredecessor(theBegin);
1032 theBegin.setNext(begin);
1033 }
1034 FixedNode next = theBegin.next();
1035 next.replaceAtPredecessor(merge);
1036 theBegin.setNext(graph().add(new EndNode()));
1037 merge.addForwardEnd((EndNode) theBegin.next());
1038 merge.setNext(next);
1039 return merge;
1040 }
1041
1042 /**
1043 * Tries to connect code that initializes a variable directly with the successors of an if
1044 * construct that switches on the variable. For example, the pseudo code below:
1045 *
1046 * <pre>
1047 * contains(list, e, yes, no) {
1048 * if (list == null || e == null) {
1049 * condition = false;
1050 * } else {
1051 * condition = false;
1052 * for (i in list) {
1053 * if (i.equals(e)) {
1054 * condition = true;
1055 * break;
1056 * }
1057 * }
1058 * }
1059 * if (condition) {
1060 * return yes;
1061 * } else {
1062 * return no;
1063 * }
1064 * }
1065 * </pre>
1066 *
1067 * will be transformed into:
1068 *
1069 * <pre>
1070 * contains(list, e, yes, no) {
1071 * if (list == null || e == null) {
1072 * return no;
1073 * } else {
1074 * condition = false;
1075 * for (i in list) {
1076 * if (i.equals(e)) {
1077 * return yes;
1078 * }
1079 * }
1080 * return no;
1081 * }
1082 * }
1083 * </pre>
1084 *
1085 * @return true if a transformation was made, false otherwise
1086 */
1087 private boolean removeIntermediateMaterialization(SimplifierTool tool) {
1088 if (!(predecessor() instanceof AbstractMergeNode) || predecessor() instanceof LoopBeginNode) {
1089 return false;
1090 }
1091 AbstractMergeNode merge = (AbstractMergeNode) predecessor();
1092
1093 if (!(condition() instanceof CompareNode)) {
1094 return false;
1095 }
1096
1097 CompareNode compare = (CompareNode) condition();
1098 if (compare.getUsageCount() != 1) {
1099 return false;
1100 }
1101
1102 // Only consider merges with a single usage that is both a phi and an operand of the
1103 // comparison
1104 NodeIterable<Node> mergeUsages = merge.usages();
1105 if (mergeUsages.count() != 1) {
1106 return false;
1107 }
1108 Node singleUsage = mergeUsages.first();
1109 if (!(singleUsage instanceof ValuePhiNode) || (singleUsage != compare.getX() && singleUsage != compare.getY())) {
1110 return false;
1111 }
1112
1113 // Ensure phi is used by at most the comparison and the merge's frame state (if any)
1114 ValuePhiNode phi = (ValuePhiNode) singleUsage;
1115 NodeIterable<Node> phiUsages = phi.usages();
1116 if (phiUsages.count() > 2) {
1117 return false;
1118 }
1119 for (Node usage : phiUsages) {
1120 if (usage != compare && usage != merge.stateAfter()) {
1121 return false;
1122 }
1123 }
1124
1125 List<EndNode> mergePredecessors = merge.cfgPredecessors().snapshot();
1126 assert phi.valueCount() == merge.forwardEndCount();
1127
1128 Constant[] xs = constantValues(compare.getX(), merge, false);
1129 Constant[] ys = constantValues(compare.getY(), merge, false);
1130 if (xs == null || ys == null) {
1131 return false;
1132 }
1133
1134 // Sanity check that both ends are not followed by a merge without frame state.
1135 if (!checkFrameState(trueSuccessor()) && !checkFrameState(falseSuccessor())) {
1136 return false;
1137 }
1138
1139 List<EndNode> falseEnds = new ArrayList<>(mergePredecessors.size());
1140 List<EndNode> trueEnds = new ArrayList<>(mergePredecessors.size());
1141 EconomicMap<AbstractEndNode, ValueNode> phiValues = EconomicMap.create(Equivalence.IDENTITY, mergePredecessors.size());
1142
1143 AbstractBeginNode oldFalseSuccessor = falseSuccessor();
1144 AbstractBeginNode oldTrueSuccessor = trueSuccessor();
1145
1146 setFalseSuccessor(null);
1147 setTrueSuccessor(null);
1148
1149 Iterator<EndNode> ends = mergePredecessors.iterator();
1150 for (int i = 0; i < xs.length; i++) {
1151 EndNode end = ends.next();
1152 phiValues.put(end, phi.valueAt(end));
1153 if (compare.condition().foldCondition(xs[i], ys[i], tool.getConstantReflection(), compare.unorderedIsTrue())) {
1154 trueEnds.add(end);
1155 } else {
1156 falseEnds.add(end);
1157 }
1158 }
1159 assert !ends.hasNext();
1160 assert falseEnds.size() + trueEnds.size() == xs.length;
1161
1162 connectEnds(falseEnds, phiValues, oldFalseSuccessor, merge, tool);
1163 connectEnds(trueEnds, phiValues, oldTrueSuccessor, merge, tool);
1164
1165 if (this.trueSuccessorProbability == 0.0) {
1166 for (AbstractEndNode endNode : trueEnds) {
1167 propagateZeroProbability(endNode);
1168 }
1169 }
1170
1171 if (this.trueSuccessorProbability == 1.0) {
1172 for (AbstractEndNode endNode : falseEnds) {
1173 propagateZeroProbability(endNode);
1174 }
1175 }
1176
1177 /*
1178 * Remove obsolete ends only after processing all ends, otherwise oldTrueSuccessor or
1179 * oldFalseSuccessor might have been removed if it is a LoopExitNode.
1180 */
1181 if (falseEnds.isEmpty()) {
1182 GraphUtil.killCFG(oldFalseSuccessor);
1183 }
1184 if (trueEnds.isEmpty()) {
1185 GraphUtil.killCFG(oldTrueSuccessor);
1186 }
1187 GraphUtil.killCFG(merge);
1188
1189 assert !merge.isAlive() : merge;
1190 assert !phi.isAlive() : phi;
1191 assert !compare.isAlive() : compare;
1192 assert !this.isAlive() : this;
1193
1194 return true;
1195 }
1196
1197 private void propagateZeroProbability(FixedNode startNode) {
1198 Node prev = null;
1199 for (FixedNode node : GraphUtil.predecessorIterable(startNode)) {
1200 if (node instanceof IfNode) {
1201 IfNode ifNode = (IfNode) node;
1202 if (ifNode.trueSuccessor() == prev) {
1203 if (ifNode.trueSuccessorProbability == 0.0) {
1204 return;
1205 } else if (ifNode.trueSuccessorProbability == 1.0) {
1206 continue;
1207 } else {
1208 ifNode.setTrueSuccessorProbability(0.0);
1209 return;
1210 }
1211 } else if (ifNode.falseSuccessor() == prev) {
1212 if (ifNode.trueSuccessorProbability == 1.0) {
1213 return;
1214 } else if (ifNode.trueSuccessorProbability == 0.0) {
1215 continue;
1216 } else {
1217 ifNode.setTrueSuccessorProbability(1.0);
1218 return;
1219 }
1220 } else {
1221 throw new GraalError("Illegal state");
1222 }
1223 } else if (node instanceof AbstractMergeNode && !(node instanceof LoopBeginNode)) {
1224 for (AbstractEndNode endNode : ((AbstractMergeNode) node).cfgPredecessors()) {
1225 propagateZeroProbability(endNode);
1226 }
1227 return;
1228 }
1229 prev = node;
1230 }
1231 }
1232
1233 private static boolean checkFrameState(FixedNode start) {
1234 FixedNode node = start;
1235 while (true) {
1236 if (node instanceof AbstractMergeNode) {
1237 AbstractMergeNode mergeNode = (AbstractMergeNode) node;
1238 if (mergeNode.stateAfter() == null) {
1239 return false;
1240 } else {
1241 return true;
1242 }
1243 } else if (node instanceof StateSplit) {
1244 StateSplit stateSplitNode = (StateSplit) node;
1245 if (stateSplitNode.stateAfter() != null) {
1246 return true;
1247 }
1248 }
1249
1250 if (node instanceof ControlSplitNode) {
1251 ControlSplitNode controlSplitNode = (ControlSplitNode) node;
1252 for (Node succ : controlSplitNode.cfgSuccessors()) {
1253 if (checkFrameState((FixedNode) succ)) {
1254 return true;
1255 }
1256 }
1257 return false;
1258 } else if (node instanceof FixedWithNextNode) {
1259 FixedWithNextNode fixedWithNextNode = (FixedWithNextNode) node;
1260 node = fixedWithNextNode.next();
1261 } else if (node instanceof AbstractEndNode) {
1262 AbstractEndNode endNode = (AbstractEndNode) node;
1263 node = endNode.merge();
1264 } else if (node instanceof ControlSinkNode) {
1265 return true;
1266 } else {
1267 return false;
1268 }
1269 }
1270 }
1271
1272 /**
1273 * Connects a set of ends to a given successor, inserting a merge node if there is more than one
1274 * end. If {@code ends} is not empty, then {@code successor} is added to {@code tool}'s
1275 * {@linkplain SimplifierTool#addToWorkList(org.graalvm.compiler.graph.Node) work list}.
1276 *
1277 * @param oldMerge the merge being removed
1278 * @param phiValues the values of the phi at the merge, keyed by the merge ends
1279 */
1280 private void connectEnds(List<EndNode> ends, EconomicMap<AbstractEndNode, ValueNode> phiValues, AbstractBeginNode successor, AbstractMergeNode oldMerge, SimplifierTool tool) {
1281 if (!ends.isEmpty()) {
1282 if (ends.size() == 1) {
1283 AbstractEndNode end = ends.get(0);
1284 ((FixedWithNextNode) end.predecessor()).setNext(successor);
1285 oldMerge.removeEnd(end);
1286 GraphUtil.killCFG(end);
1287 } else {
1288 // Need a new phi in case the frame state is used by more than the merge being
1289 // removed
1290 AbstractMergeNode newMerge = graph().add(new MergeNode());
1291 PhiNode oldPhi = (PhiNode) oldMerge.usages().first();
1292 PhiNode newPhi = graph().addWithoutUnique(new ValuePhiNode(oldPhi.stamp(), newMerge));
1293
1294 for (EndNode end : ends) {
1295 newPhi.addInput(phiValues.get(end));
1296 newMerge.addForwardEnd(end);
1297 }
1298
1299 FrameState stateAfter = oldMerge.stateAfter();
1300 if (stateAfter != null) {
1301 stateAfter = stateAfter.duplicate();
1302 stateAfter.replaceFirstInput(oldPhi, newPhi);
1303 newMerge.setStateAfter(stateAfter);
1304 }
1305
1306 newMerge.setNext(successor);
1307 }
1308 tool.addToWorkList(successor);
1309 }
1310 }
1311
1312 /**
1313 * Gets an array of constants derived from a node that is either a {@link ConstantNode} or a
1314 * {@link PhiNode} whose input values are all constants. The length of the returned array is
1315 * equal to the number of ends terminating in a given merge node.
1316 *
1317 * @return null if {@code node} is neither a {@link ConstantNode} nor a {@link PhiNode} whose
1318 * input values are all constants
1319 */
1320 public static Constant[] constantValues(ValueNode node, AbstractMergeNode merge, boolean allowNull) {
1321 if (node.isConstant()) {
1322 Constant[] result = new Constant[merge.forwardEndCount()];
1323 Arrays.fill(result, node.asConstant());
1324 return result;
1325 }
1326
1327 if (node instanceof PhiNode) {
1328 PhiNode phi = (PhiNode) node;
1329 if (phi.merge() == merge && phi instanceof ValuePhiNode && phi.valueCount() == merge.forwardEndCount()) {
1330 Constant[] result = new Constant[merge.forwardEndCount()];
1331 int i = 0;
1332 for (ValueNode n : phi.values()) {
1333 if (!allowNull && !n.isConstant()) {
1334 return null;
1335 }
1336 result[i++] = n.asConstant();
1337 }
1338 return result;
1339 }
1340 }
1341
1342 return null;
1343 }
1344
1345 @Override
1346 public AbstractBeginNode getPrimarySuccessor() {
1347 return this.trueSuccessor();
1348 }
1349
1350 public AbstractBeginNode getSuccessor(boolean result) {
1351 return result ? this.trueSuccessor() : this.falseSuccessor();
1352 }
1353
1354 @Override
1355 public boolean setProbability(AbstractBeginNode successor, double value) {
1356 if (successor == this.trueSuccessor()) {
1357 this.setTrueSuccessorProbability(value);
1358 return true;
1359 } else if (successor == this.falseSuccessor()) {
1360 this.setTrueSuccessorProbability(1.0 - value);
1361 return true;
1362 }
1363 return false;
1364 }
1365
1366 @Override
1367 public int getSuccessorCount() {
1368 return 2;
1369 }
1370 }