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