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