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