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.Debug;
38 import org.graalvm.compiler.debug.DebugCounter;
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 DebugCounter CORRECTED_PROBABILITIES = Debug.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();
183 trueSuccessorProbability = 0;
184 }
185 } else if (falseSuccessor().next() instanceof DeoptimizeNode) {
186 if (trueSuccessorProbability != 1) {
187 CORRECTED_PROBABILITIES.increment();
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 if (a instanceof InstanceOfNode) {
457 InstanceOfNode instanceOfA = (InstanceOfNode) a;
458 if (b instanceof IsNullNode) {
459 IsNullNode isNullNode = (IsNullNode) b;
460 if (isNullNode.getValue() == instanceOfA.getValue()) {
461 Debug.log("Can swap instanceof and isnull if");
462 return true;
463 }
464 } else if (b instanceof InstanceOfNode) {
465 InstanceOfNode instanceOfB = (InstanceOfNode) b;
466 if (instanceOfA.getValue() == instanceOfB.getValue() && !instanceOfA.type().getType().isInterface() && !instanceOfB.type().getType().isInterface() &&
467 !instanceOfA.type().getType().isAssignableFrom(instanceOfB.type().getType()) && !instanceOfB.type().getType().isAssignableFrom(instanceOfA.type().getType())) {
468 // Two instanceof on the same value with mutually exclusive types.
469 Debug.log("Can swap instanceof for types %s and %s", instanceOfA.type(), instanceOfB.type());
470 return true;
471 }
472 }
473 } else if (a instanceof CompareNode) {
474 CompareNode compareA = (CompareNode) a;
475 Condition conditionA = compareA.condition();
476 if (compareA.unorderedIsTrue()) {
477 return false;
478 }
479 if (b instanceof CompareNode) {
480 CompareNode compareB = (CompareNode) b;
481 if (compareA == compareB) {
482 Debug.log("Same conditions => do not swap and leave the work for global value numbering.");
483 return false;
484 }
485 if (compareB.unorderedIsTrue()) {
486 return false;
487 }
488 Condition comparableCondition = null;
489 Condition conditionB = compareB.condition();
490 if (compareB.getX() == compareA.getX() && compareB.getY() == compareA.getY()) {
491 comparableCondition = conditionB;
492 } else if (compareB.getX() == compareA.getY() && compareB.getY() == compareA.getX()) {
493 comparableCondition = conditionB.mirror();
494 }
495
496 if (comparableCondition != null) {
497 Condition combined = conditionA.join(comparableCondition);
498 if (combined == null) {
499 // The two conditions are disjoint => can reorder.
500 Debug.log("Can swap disjoint coditions on same values: %s and %s", conditionA, comparableCondition);
501 return true;
502 }
503 } else if (conditionA == Condition.EQ && conditionB == Condition.EQ) {
504 boolean canSwap = false;
505 if ((compareA.getX() == compareB.getX() && valuesDistinct(constantReflection, compareA.getY(), compareB.getY()))) {
506 canSwap = true;
507 } else if ((compareA.getX() == compareB.getY() && valuesDistinct(constantReflection, compareA.getY(), compareB.getX()))) {
508 canSwap = true;
509 } else if ((compareA.getY() == compareB.getX() && valuesDistinct(constantReflection, compareA.getX(), compareB.getY()))) {
510 canSwap = true;
511 } else if ((compareA.getY() == compareB.getY() && valuesDistinct(constantReflection, compareA.getX(), compareB.getX()))) {
512 canSwap = true;
513 }
514
515 if (canSwap) {
516 Debug.log("Can swap equality condition with one shared and one disjoint value.");
517 return true;
518 }
519 }
520 }
521 }
522
523 return false;
524 }
525
526 private static boolean valuesDistinct(ConstantReflectionProvider constantReflection, ValueNode a, ValueNode b) {
527 if (a.isConstant() && b.isConstant()) {
528 Boolean equal = constantReflection.constantEquals(a.asConstant(), b.asConstant());
529 if (equal != null) {
530 return !equal.booleanValue();
531 }
532 }
533
534 Stamp stampA = a.stamp();
535 Stamp stampB = b.stamp();
536 return stampA.alwaysDistinct(stampB);
537 }
538
539 /**
540 * Tries to remove an empty if construct or replace an if construct with a materialization.
541 *
542 * @return true if a transformation was made, false otherwise
543 */
544 private boolean removeOrMaterializeIf(SimplifierTool tool) {
545 assert trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages();
546 if (trueSuccessor().next() instanceof AbstractEndNode && falseSuccessor().next() instanceof AbstractEndNode) {
547 AbstractEndNode trueEnd = (AbstractEndNode) trueSuccessor().next();
548 AbstractEndNode falseEnd = (AbstractEndNode) falseSuccessor().next();
549 AbstractMergeNode merge = trueEnd.merge();
550 if (merge == falseEnd.merge() && trueSuccessor().anchored().isEmpty() && falseSuccessor().anchored().isEmpty()) {
551 PhiNode singlePhi = null;
552 int distinct = 0;
553 for (PhiNode phi : merge.phis()) {
554 ValueNode trueValue = phi.valueAt(trueEnd);
555 ValueNode falseValue = phi.valueAt(falseEnd);
556 if (trueValue != falseValue) {
557 distinct++;
558 singlePhi = phi;
559 }
560 }
561 if (distinct == 0) {
562 /*
563 * Multiple phis but merging same values for true and false, so simply delete
564 * the path
565 */
566 removeThroughFalseBranch(tool, merge);
567 return true;
568 } else if (distinct == 1) {
569 ValueNode trueValue = singlePhi.valueAt(trueEnd);
570 ValueNode falseValue = singlePhi.valueAt(falseEnd);
571 ValueNode conditional = canonicalizeConditionalCascade(trueValue, falseValue);
572 if (conditional != null) {
573 singlePhi.setValueAt(trueEnd, conditional);
574 removeThroughFalseBranch(tool, merge);
575 return true;
576 }
577 }
578 }
579 }
580 if (trueSuccessor().next() instanceof ReturnNode && falseSuccessor().next() instanceof ReturnNode) {
581 ReturnNode trueEnd = (ReturnNode) trueSuccessor().next();
582 ReturnNode falseEnd = (ReturnNode) falseSuccessor().next();
583 ValueNode trueValue = trueEnd.result();
584 ValueNode falseValue = falseEnd.result();
585 ValueNode value = null;
586 if (trueValue != null) {
587 if (trueValue == falseValue) {
588 value = trueValue;
589 } else {
590 value = canonicalizeConditionalCascade(trueValue, falseValue);
591 if (value == null) {
592 return false;
593 }
594 }
595 }
596 ReturnNode newReturn = graph().add(new ReturnNode(value));
597 replaceAtPredecessor(newReturn);
598 GraphUtil.killCFG(this);
599 return true;
600 }
601 return false;
602 }
603
604 protected void removeThroughFalseBranch(SimplifierTool tool, AbstractMergeNode merge) {
605 AbstractBeginNode trueBegin = trueSuccessor();
606 graph().removeSplitPropagate(this, trueBegin);
607 tool.addToWorkList(trueBegin);
608 if (condition() != null) {
609 GraphUtil.tryKillUnused(condition());
610 }
611 if (merge.isAlive() && merge.forwardEndCount() > 1) {
612 for (FixedNode end : merge.forwardEnds()) {
613 Node cur = end;
614 while (cur != null && cur.predecessor() instanceof BeginNode) {
615 cur = cur.predecessor();
616 }
617 if (cur != null && cur.predecessor() instanceof IfNode) {
618 tool.addToWorkList(cur.predecessor());
619 }
620 }
621 }
622 }
623
624 private ValueNode canonicalizeConditionalCascade(ValueNode trueValue, ValueNode falseValue) {
625 if (trueValue.getStackKind() != falseValue.getStackKind()) {
626 return null;
627 }
628 if (trueValue.getStackKind() != JavaKind.Int && trueValue.getStackKind() != JavaKind.Long) {
629 return null;
630 }
631 if (trueValue.isConstant() && falseValue.isConstant()) {
632 return graph().unique(new ConditionalNode(condition(), trueValue, falseValue));
633 } else if (!graph().isAfterExpandLogic()) {
634 ConditionalNode conditional = null;
635 ValueNode constant = null;
636 boolean negateCondition;
637 if (trueValue instanceof ConditionalNode && falseValue.isConstant()) {
638 conditional = (ConditionalNode) trueValue;
639 constant = falseValue;
640 negateCondition = true;
641 } else if (falseValue instanceof ConditionalNode && trueValue.isConstant()) {
642 conditional = (ConditionalNode) falseValue;
643 constant = trueValue;
644 negateCondition = false;
645 } else {
646 return null;
647 }
648 boolean negateConditionalCondition = false;
649 ValueNode otherValue = null;
650 if (constant == conditional.trueValue()) {
651 otherValue = conditional.falseValue();
652 negateConditionalCondition = false;
653 } else if (constant == conditional.falseValue()) {
654 otherValue = conditional.trueValue();
655 negateConditionalCondition = true;
656 }
657 if (otherValue != null && otherValue.isConstant()) {
658 double shortCutProbability = probability(trueSuccessor());
659 LogicNode newCondition = LogicNode.or(condition(), negateCondition, conditional.condition(), negateConditionalCondition, shortCutProbability);
660 return graph().unique(new ConditionalNode(newCondition, constant, otherValue));
661 } else if (!negateCondition && constant.isJavaConstant() && conditional.trueValue().isJavaConstant() && conditional.falseValue().isJavaConstant()) {
662 IntegerLessThanNode lessThan = null;
663 IntegerEqualsNode equals = null;
664 if (condition() instanceof IntegerLessThanNode && conditional.condition() instanceof IntegerEqualsNode && constant.asJavaConstant().asLong() == -1 &&
665 conditional.trueValue().asJavaConstant().asLong() == 0 && conditional.falseValue().asJavaConstant().asLong() == 1) {
666 lessThan = (IntegerLessThanNode) condition();
667 equals = (IntegerEqualsNode) conditional.condition();
668 } else if (condition() instanceof IntegerEqualsNode && conditional.condition() instanceof IntegerLessThanNode && constant.asJavaConstant().asLong() == 0 &&
669 conditional.trueValue().asJavaConstant().asLong() == -1 && conditional.falseValue().asJavaConstant().asLong() == 1) {
670 lessThan = (IntegerLessThanNode) conditional.condition();
671 equals = (IntegerEqualsNode) condition();
672 }
673 if (lessThan != null) {
674 assert equals != null;
675 if ((lessThan.getX() == equals.getX() && lessThan.getY() == equals.getY()) || (lessThan.getX() == equals.getY() && lessThan.getY() == equals.getX())) {
676 return graph().unique(new NormalizeCompareNode(lessThan.getX(), lessThan.getY(), conditional.trueValue().stamp().getStackKind(), false));
677 }
678 }
679 }
680 }
681 return null;
682 }
683
684 /**
685 * Take an if that is immediately dominated by a merge with a single phi and split off any paths
686 * where the test would be statically decidable creating a new merge below the approriate side
687 * of the IfNode. Any undecidable tests will continue to use the original IfNode.
688 *
689 * @param tool
690 */
691 private boolean splitIfAtPhi(SimplifierTool tool) {
692 if (graph().getGuardsStage().areFrameStatesAtSideEffects()) {
693 // Disabled until we make sure we have no FrameState-less merges at this stage
694 return false;
695 }
696
697 if (!(predecessor() instanceof MergeNode)) {
698 return false;
699 }
700 MergeNode merge = (MergeNode) predecessor();
701 if (merge.forwardEndCount() == 1) {
702 // Don't bother.
703 return false;
704 }
705 if (merge.usages().count() != 1 || merge.phis().count() != 1) {
706 return false;
707 }
708 if (merge.stateAfter() != null) {
709 /* We'll get the chance to simplify this after frame state assignment. */
710 return false;
711 }
712 PhiNode phi = merge.phis().first();
713 if (phi.usages().count() != 1) {
714 /*
715 * For simplicity the below code assumes assumes the phi goes dead at the end so skip
716 * this case.
717 */
718 return false;
719 }
720
721 /*
722 * Check that the condition uses the phi and that there is only one user of the condition
723 * expression.
724 */
725 if (!conditionUses(condition(), phi)) {
726 return false;
727 }
728
729 /*
730 * We could additionally filter for the case that at least some of the Phi inputs or one of
731 * the condition inputs are constants but there are cases where a non-constant is
732 * simplifiable, usually where the stamp allows the question to be answered.
733 */
734
735 /* Each successor of the if gets a new merge if needed. */
736 MergeNode trueMerge = null;
737 MergeNode falseMerge = null;
738 assert merge.stateAfter() == null;
739
740 for (EndNode end : merge.forwardEnds().snapshot()) {
741 Node value = phi.valueAt(end);
742 LogicNode result = computeCondition(tool, condition, phi, value);
743 if (result instanceof LogicConstantNode) {
744 merge.removeEnd(end);
745 if (((LogicConstantNode) result).getValue()) {
746 if (trueMerge == null) {
747 trueMerge = insertMerge(trueSuccessor());
748 }
749 trueMerge.addForwardEnd(end);
750 } else {
751 if (falseMerge == null) {
752 falseMerge = insertMerge(falseSuccessor());
753 }
754 falseMerge.addForwardEnd(end);
755 }
756 } else if (result != condition) {
757 // Build a new IfNode using the new condition
758 BeginNode trueBegin = graph().add(new BeginNode());
759 BeginNode falseBegin = graph().add(new BeginNode());
760
761 if (result.graph() == null) {
762 result = graph().addOrUniqueWithInputs(result);
763 }
764 IfNode newIfNode = graph().add(new IfNode(result, trueBegin, falseBegin, trueSuccessorProbability));
765 merge.removeEnd(end);
766 ((FixedWithNextNode) end.predecessor()).setNext(newIfNode);
767
768 if (trueMerge == null) {
769 trueMerge = insertMerge(trueSuccessor());
770 }
771 trueBegin.setNext(graph().add(new EndNode()));
772 trueMerge.addForwardEnd((EndNode) trueBegin.next());
773
774 if (falseMerge == null) {
775 falseMerge = insertMerge(falseSuccessor());
776 }
777 falseBegin.setNext(graph().add(new EndNode()));
778 falseMerge.addForwardEnd((EndNode) falseBegin.next());
779
780 end.safeDelete();
781 }
782 }
783
784 transferProxies(trueSuccessor(), trueMerge);
785 transferProxies(falseSuccessor(), falseMerge);
786
787 cleanupMerge(merge);
788 cleanupMerge(trueMerge);
789 cleanupMerge(falseMerge);
790
791 return true;
792 }
793
794 /**
795 * @param condition
796 * @param phi
797 * @return true if the passed in {@code condition} uses {@code phi} and the condition is only
798 * used once. Since the phi will go dead the condition using it will also have to be
799 * dead after the optimization.
800 */
801 private static boolean conditionUses(LogicNode condition, PhiNode phi) {
802 if (condition.usages().count() != 1) {
803 return false;
804 }
805 if (condition instanceof ShortCircuitOrNode) {
806 if (condition.graph().getGuardsStage().areDeoptsFixed()) {
807 /*
808 * It can be unsafe to simplify a ShortCircuitOr before deopts are fixed because
809 * conversion to guards assumes that all the required conditions are being tested.
810 * Simplfying the condition based on context before this happens may lose a
811 * condition.
812 */
813 ShortCircuitOrNode orNode = (ShortCircuitOrNode) condition;
814 return (conditionUses(orNode.x, phi) || conditionUses(orNode.y, phi));
815 }
816 } else if (condition instanceof Canonicalizable.Unary<?>) {
817 Canonicalizable.Unary<?> unary = (Canonicalizable.Unary<?>) condition;
818 return unary.getValue() == phi;
819 } else if (condition instanceof Canonicalizable.Binary<?>) {
820 Canonicalizable.Binary<?> binary = (Canonicalizable.Binary<?>) condition;
821 return binary.getX() == phi || binary.getY() == phi;
822 }
823 return false;
824 }
825
826 /**
827 * Canonicalize {@code} condition using {@code value} in place of {@code phi}.
828 *
829 * @param tool
830 * @param condition
831 * @param phi
832 * @param value
833 * @return an improved LogicNode or the original condition
834 */
835 @SuppressWarnings("unchecked")
836 private static LogicNode computeCondition(SimplifierTool tool, LogicNode condition, PhiNode phi, Node value) {
837 if (condition instanceof ShortCircuitOrNode) {
838 if (condition.graph().getGuardsStage().areDeoptsFixed() && !condition.graph().isAfterExpandLogic()) {
839 ShortCircuitOrNode orNode = (ShortCircuitOrNode) condition;
840 LogicNode resultX = computeCondition(tool, orNode.x, phi, value);
841 LogicNode resultY = computeCondition(tool, orNode.y, phi, value);
842 if (resultX != orNode.x || resultY != orNode.y) {
843 LogicNode result = orNode.canonical(tool, resultX, resultY);
844 if (result != orNode) {
845 return result;
846 }
847 /*
848 * Create a new node to carry the optimized inputs.
849 */
850 ShortCircuitOrNode newOr = new ShortCircuitOrNode(resultX, orNode.xNegated, resultY,
851 orNode.yNegated, orNode.getShortCircuitProbability());
852 return newOr.canonical(tool);
853 }
854 return orNode;
855 }
856 } else if (condition instanceof Canonicalizable.Binary<?>) {
857 Canonicalizable.Binary<Node> compare = (Canonicalizable.Binary<Node>) condition;
858 if (compare.getX() == phi) {
859 return (LogicNode) compare.canonical(tool, value, compare.getY());
860 } else if (compare.getY() == phi) {
861 return (LogicNode) compare.canonical(tool, compare.getX(), value);
862 }
863 } else if (condition instanceof Canonicalizable.Unary<?>) {
864 Canonicalizable.Unary<Node> compare = (Canonicalizable.Unary<Node>) condition;
865 if (compare.getValue() == phi) {
866 return (LogicNode) compare.canonical(tool, value);
867 }
868 }
869 if (condition instanceof Canonicalizable) {
870 return (LogicNode) ((Canonicalizable) condition).canonical(tool);
871 }
872 return condition;
873 }
874
875 private static void transferProxies(AbstractBeginNode successor, MergeNode falseMerge) {
876 if (successor instanceof LoopExitNode && falseMerge != null) {
877 LoopExitNode loopExitNode = (LoopExitNode) successor;
878 for (ProxyNode proxy : loopExitNode.proxies().snapshot()) {
879 proxy.replaceFirstInput(successor, falseMerge);
880 }
881 }
882 }
883
884 private void cleanupMerge(MergeNode merge) {
885 if (merge != null && merge.isAlive()) {
886 if (merge.forwardEndCount() == 0) {
887 GraphUtil.killCFG(merge);
888 } else if (merge.forwardEndCount() == 1) {
889 graph().reduceTrivialMerge(merge);
890 }
891 }
892 }
893
894 private MergeNode insertMerge(AbstractBeginNode begin) {
895 MergeNode merge = graph().add(new MergeNode());
896 if (!begin.anchored().isEmpty()) {
897 Object before = null;
898 before = begin.anchored().snapshot();
899 begin.replaceAtUsages(InputType.Guard, merge);
900 begin.replaceAtUsages(InputType.Anchor, merge);
901 assert begin.anchored().isEmpty() : before + " " + begin.anchored().snapshot();
902 }
903
904 AbstractBeginNode theBegin = begin;
905 if (begin instanceof LoopExitNode) {
906 // Insert an extra begin to make it easier.
907 theBegin = graph().add(new BeginNode());
908 begin.replaceAtPredecessor(theBegin);
909 theBegin.setNext(begin);
910 }
911 FixedNode next = theBegin.next();
912 next.replaceAtPredecessor(merge);
913 theBegin.setNext(graph().add(new EndNode()));
914 merge.addForwardEnd((EndNode) theBegin.next());
915 merge.setNext(next);
916 return merge;
917 }
918
919 /**
920 * Tries to connect code that initializes a variable directly with the successors of an if
921 * construct that switches on the variable. For example, the pseudo code below:
922 *
923 * <pre>
924 * contains(list, e, yes, no) {
925 * if (list == null || e == null) {
926 * condition = false;
927 * } else {
928 * condition = false;
929 * for (i in list) {
930 * if (i.equals(e)) {
931 * condition = true;
932 * break;
933 * }
934 * }
935 * }
936 * if (condition) {
937 * return yes;
938 * } else {
939 * return no;
940 * }
941 * }
942 * </pre>
943 *
944 * will be transformed into:
945 *
946 * <pre>
947 * contains(list, e, yes, no) {
948 * if (list == null || e == null) {
949 * return no;
950 * } else {
951 * condition = false;
952 * for (i in list) {
953 * if (i.equals(e)) {
954 * return yes;
955 * }
956 * }
957 * return no;
958 * }
959 * }
960 * </pre>
961 *
962 * @return true if a transformation was made, false otherwise
963 */
964 private boolean removeIntermediateMaterialization(SimplifierTool tool) {
965 if (!(predecessor() instanceof AbstractMergeNode) || predecessor() instanceof LoopBeginNode) {
966 return false;
967 }
968 AbstractMergeNode merge = (AbstractMergeNode) predecessor();
969
970 if (!(condition() instanceof CompareNode)) {
971 return false;
972 }
973
974 CompareNode compare = (CompareNode) condition();
975 if (compare.getUsageCount() != 1) {
976 return false;
977 }
978
979 // Only consider merges with a single usage that is both a phi and an operand of the
980 // comparison
981 NodeIterable<Node> mergeUsages = merge.usages();
982 if (mergeUsages.count() != 1) {
983 return false;
984 }
985 Node singleUsage = mergeUsages.first();
986 if (!(singleUsage instanceof ValuePhiNode) || (singleUsage != compare.getX() && singleUsage != compare.getY())) {
987 return false;
988 }
989
990 // Ensure phi is used by at most the comparison and the merge's frame state (if any)
991 ValuePhiNode phi = (ValuePhiNode) singleUsage;
992 NodeIterable<Node> phiUsages = phi.usages();
993 if (phiUsages.count() > 2) {
994 return false;
995 }
996 for (Node usage : phiUsages) {
997 if (usage != compare && usage != merge.stateAfter()) {
998 return false;
999 }
1000 }
1001
1002 List<EndNode> mergePredecessors = merge.cfgPredecessors().snapshot();
1003 assert phi.valueCount() == merge.forwardEndCount();
1004
1005 Constant[] xs = constantValues(compare.getX(), merge, false);
1006 Constant[] ys = constantValues(compare.getY(), merge, false);
1007 if (xs == null || ys == null) {
1008 return false;
1009 }
1010
1011 // Sanity check that both ends are not followed by a merge without frame state.
1012 if (!checkFrameState(trueSuccessor()) && !checkFrameState(falseSuccessor())) {
1013 return false;
1014 }
1015
1016 List<EndNode> falseEnds = new ArrayList<>(mergePredecessors.size());
1017 List<EndNode> trueEnds = new ArrayList<>(mergePredecessors.size());
1018 EconomicMap<AbstractEndNode, ValueNode> phiValues = EconomicMap.create(Equivalence.IDENTITY, mergePredecessors.size());
1019
1020 AbstractBeginNode oldFalseSuccessor = falseSuccessor();
1021 AbstractBeginNode oldTrueSuccessor = trueSuccessor();
1022
1023 setFalseSuccessor(null);
1024 setTrueSuccessor(null);
1025
1026 Iterator<EndNode> ends = mergePredecessors.iterator();
1027 for (int i = 0; i < xs.length; i++) {
1028 EndNode end = ends.next();
1029 phiValues.put(end, phi.valueAt(end));
1030 if (compare.condition().foldCondition(xs[i], ys[i], tool.getConstantReflection(), compare.unorderedIsTrue())) {
1031 trueEnds.add(end);
1032 } else {
1033 falseEnds.add(end);
1034 }
1035 }
1036 assert !ends.hasNext();
1037 assert falseEnds.size() + trueEnds.size() == xs.length;
1038
1039 connectEnds(falseEnds, phiValues, oldFalseSuccessor, merge, tool);
1040 connectEnds(trueEnds, phiValues, oldTrueSuccessor, merge, tool);
1041
1042 if (this.trueSuccessorProbability == 0.0) {
1043 for (AbstractEndNode endNode : trueEnds) {
1044 propagateZeroProbability(endNode);
1045 }
1046 }
1047
1048 if (this.trueSuccessorProbability == 1.0) {
1049 for (AbstractEndNode endNode : falseEnds) {
1050 propagateZeroProbability(endNode);
1051 }
1052 }
1053
1054 /*
1055 * Remove obsolete ends only after processing all ends, otherwise oldTrueSuccessor or
1056 * oldFalseSuccessor might have been removed if it is a LoopExitNode.
1057 */
1058 if (falseEnds.isEmpty()) {
1059 GraphUtil.killCFG(oldFalseSuccessor);
1060 }
1061 if (trueEnds.isEmpty()) {
1062 GraphUtil.killCFG(oldTrueSuccessor);
1063 }
1064 GraphUtil.killCFG(merge);
1065
1066 assert !merge.isAlive() : merge;
1067 assert !phi.isAlive() : phi;
1068 assert !compare.isAlive() : compare;
1069 assert !this.isAlive() : this;
1070
1071 return true;
1072 }
1073
1074 private void propagateZeroProbability(FixedNode startNode) {
1075 Node prev = null;
1076 for (FixedNode node : GraphUtil.predecessorIterable(startNode)) {
1077 if (node instanceof IfNode) {
1078 IfNode ifNode = (IfNode) node;
1079 if (ifNode.trueSuccessor() == prev) {
1080 if (ifNode.trueSuccessorProbability == 0.0) {
1081 return;
1082 } else if (ifNode.trueSuccessorProbability == 1.0) {
1083 continue;
1084 } else {
1085 ifNode.setTrueSuccessorProbability(0.0);
1086 return;
1087 }
1088 } else if (ifNode.falseSuccessor() == prev) {
1089 if (ifNode.trueSuccessorProbability == 1.0) {
1090 return;
1091 } else if (ifNode.trueSuccessorProbability == 0.0) {
1092 continue;
1093 } else {
1094 ifNode.setTrueSuccessorProbability(1.0);
1095 return;
1096 }
1097 } else {
1098 throw new GraalError("Illegal state");
1099 }
1100 } else if (node instanceof AbstractMergeNode && !(node instanceof LoopBeginNode)) {
1101 for (AbstractEndNode endNode : ((AbstractMergeNode) node).cfgPredecessors()) {
1102 propagateZeroProbability(endNode);
1103 }
1104 return;
1105 }
1106 prev = node;
1107 }
1108 }
1109
1110 private static boolean checkFrameState(FixedNode start) {
1111 FixedNode node = start;
1112 while (true) {
1113 if (node instanceof AbstractMergeNode) {
1114 AbstractMergeNode mergeNode = (AbstractMergeNode) node;
1115 if (mergeNode.stateAfter() == null) {
1116 return false;
1117 } else {
1118 return true;
1119 }
1120 } else if (node instanceof StateSplit) {
1121 StateSplit stateSplitNode = (StateSplit) node;
1122 if (stateSplitNode.stateAfter() != null) {
1123 return true;
1124 }
1125 }
1126
1127 if (node instanceof ControlSplitNode) {
1128 ControlSplitNode controlSplitNode = (ControlSplitNode) node;
1129 for (Node succ : controlSplitNode.cfgSuccessors()) {
1130 if (checkFrameState((FixedNode) succ)) {
1131 return true;
1132 }
1133 }
1134 return false;
1135 } else if (node instanceof FixedWithNextNode) {
1136 FixedWithNextNode fixedWithNextNode = (FixedWithNextNode) node;
1137 node = fixedWithNextNode.next();
1138 } else if (node instanceof AbstractEndNode) {
1139 AbstractEndNode endNode = (AbstractEndNode) node;
1140 node = endNode.merge();
1141 } else if (node instanceof ControlSinkNode) {
1142 return true;
1143 } else {
1144 return false;
1145 }
1146 }
1147 }
1148
1149 /**
1150 * Connects a set of ends to a given successor, inserting a merge node if there is more than one
1151 * end. If {@code ends} is not empty, then {@code successor} is added to {@code tool}'s
1152 * {@linkplain SimplifierTool#addToWorkList(org.graalvm.compiler.graph.Node) work list}.
1153 *
1154 * @param oldMerge the merge being removed
1155 * @param phiValues the values of the phi at the merge, keyed by the merge ends
1156 */
1157 private void connectEnds(List<EndNode> ends, EconomicMap<AbstractEndNode, ValueNode> phiValues, AbstractBeginNode successor, AbstractMergeNode oldMerge, SimplifierTool tool) {
1158 if (!ends.isEmpty()) {
1159 if (ends.size() == 1) {
1160 AbstractEndNode end = ends.get(0);
1161 ((FixedWithNextNode) end.predecessor()).setNext(successor);
1162 oldMerge.removeEnd(end);
1163 GraphUtil.killCFG(end);
1164 } else {
1165 // Need a new phi in case the frame state is used by more than the merge being
1166 // removed
1167 AbstractMergeNode newMerge = graph().add(new MergeNode());
1168 PhiNode oldPhi = (PhiNode) oldMerge.usages().first();
1169 PhiNode newPhi = graph().addWithoutUnique(new ValuePhiNode(oldPhi.stamp(), newMerge));
1170
1171 for (EndNode end : ends) {
1172 newPhi.addInput(phiValues.get(end));
1173 newMerge.addForwardEnd(end);
1174 }
1175
1176 FrameState stateAfter = oldMerge.stateAfter();
1177 if (stateAfter != null) {
1178 stateAfter = stateAfter.duplicate();
1179 stateAfter.replaceFirstInput(oldPhi, newPhi);
1180 newMerge.setStateAfter(stateAfter);
1181 }
1182
1183 newMerge.setNext(successor);
1184 }
1185 tool.addToWorkList(successor);
1186 }
1187 }
1188
1189 /**
1190 * Gets an array of constants derived from a node that is either a {@link ConstantNode} or a
1191 * {@link PhiNode} whose input values are all constants. The length of the returned array is
1192 * equal to the number of ends terminating in a given merge node.
1193 *
1194 * @return null if {@code node} is neither a {@link ConstantNode} nor a {@link PhiNode} whose
1195 * input values are all constants
1196 */
1197 public static Constant[] constantValues(ValueNode node, AbstractMergeNode merge, boolean allowNull) {
1198 if (node.isConstant()) {
1199 Constant[] result = new Constant[merge.forwardEndCount()];
1200 Arrays.fill(result, node.asConstant());
1201 return result;
1202 }
1203
1204 if (node instanceof PhiNode) {
1205 PhiNode phi = (PhiNode) node;
1206 if (phi.merge() == merge && phi instanceof ValuePhiNode && phi.valueCount() == merge.forwardEndCount()) {
1207 Constant[] result = new Constant[merge.forwardEndCount()];
1208 int i = 0;
1209 for (ValueNode n : phi.values()) {
1210 if (!allowNull && !n.isConstant()) {
1211 return null;
1212 }
1213 result[i++] = n.asConstant();
1214 }
1215 return result;
1216 }
1217 }
1218
1219 return null;
1220 }
1221
1222 @Override
1223 public AbstractBeginNode getPrimarySuccessor() {
1224 return this.trueSuccessor();
1225 }
1226
1227 public AbstractBeginNode getSuccessor(boolean result) {
1228 return result ? this.trueSuccessor() : this.falseSuccessor();
1229 }
1230
1231 @Override
1232 public boolean setProbability(AbstractBeginNode successor, double value) {
1233 if (successor == this.trueSuccessor()) {
1234 this.setTrueSuccessorProbability(value);
1235 return true;
1236 } else if (successor == this.falseSuccessor()) {
1237 this.setTrueSuccessorProbability(1.0 - value);
1238 return true;
1239 }
1240 return false;
1241 }
1242
1243 @Override
1244 public int getSuccessorCount() {
1245 return 2;
1246 }
1247 }