1 /* 2 * Copyright (c) 2015, 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.phases.common; 26 27 import static org.graalvm.compiler.nodes.StaticDeoptimizingNode.mergeActions; 28 29 import java.util.ArrayDeque; 30 import java.util.Deque; 31 import java.util.List; 32 33 import jdk.internal.vm.compiler.collections.EconomicMap; 34 import jdk.internal.vm.compiler.collections.Equivalence; 35 import jdk.internal.vm.compiler.collections.MapCursor; 36 import jdk.internal.vm.compiler.collections.Pair; 37 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph; 38 import org.graalvm.compiler.core.common.cfg.BlockMap; 39 import org.graalvm.compiler.core.common.type.ArithmeticOpTable; 40 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp; 41 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.And; 42 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Or; 43 import org.graalvm.compiler.core.common.type.IntegerStamp; 44 import org.graalvm.compiler.core.common.type.ObjectStamp; 45 import org.graalvm.compiler.core.common.type.Stamp; 46 import org.graalvm.compiler.core.common.type.StampFactory; 47 import org.graalvm.compiler.debug.CounterKey; 48 import org.graalvm.compiler.debug.DebugCloseable; 49 import org.graalvm.compiler.debug.DebugContext; 50 import org.graalvm.compiler.graph.Node; 51 import org.graalvm.compiler.graph.NodeMap; 52 import org.graalvm.compiler.graph.NodeStack; 53 import org.graalvm.compiler.graph.spi.CanonicalizerTool; 54 import org.graalvm.compiler.nodeinfo.InputType; 55 import org.graalvm.compiler.nodes.AbstractBeginNode; 56 import org.graalvm.compiler.nodes.AbstractMergeNode; 57 import org.graalvm.compiler.nodes.BinaryOpLogicNode; 58 import org.graalvm.compiler.nodes.ConditionAnchorNode; 59 import org.graalvm.compiler.nodes.DeoptimizeNode; 60 import org.graalvm.compiler.nodes.DeoptimizingGuard; 61 import org.graalvm.compiler.nodes.EndNode; 62 import org.graalvm.compiler.nodes.FixedGuardNode; 63 import org.graalvm.compiler.nodes.FixedNode; 64 import org.graalvm.compiler.nodes.FixedWithNextNode; 65 import org.graalvm.compiler.nodes.GuardNode; 66 import org.graalvm.compiler.nodes.IfNode; 67 import org.graalvm.compiler.nodes.LogicConstantNode; 68 import org.graalvm.compiler.nodes.LogicNode; 69 import org.graalvm.compiler.nodes.LoopExitNode; 70 import org.graalvm.compiler.nodes.MergeNode; 71 import org.graalvm.compiler.nodes.NodeView; 72 import org.graalvm.compiler.nodes.ParameterNode; 73 import org.graalvm.compiler.nodes.PiNode; 74 import org.graalvm.compiler.nodes.ProxyNode; 75 import org.graalvm.compiler.nodes.ShortCircuitOrNode; 76 import org.graalvm.compiler.nodes.StructuredGraph; 77 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult; 78 import org.graalvm.compiler.nodes.UnaryOpLogicNode; 79 import org.graalvm.compiler.nodes.ValueNode; 80 import org.graalvm.compiler.nodes.ValuePhiNode; 81 import org.graalvm.compiler.nodes.calc.AndNode; 82 import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode; 83 import org.graalvm.compiler.nodes.calc.BinaryNode; 84 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode; 85 import org.graalvm.compiler.nodes.calc.UnaryNode; 86 import org.graalvm.compiler.nodes.cfg.Block; 87 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph; 88 import org.graalvm.compiler.nodes.extended.GuardingNode; 89 import org.graalvm.compiler.nodes.extended.IntegerSwitchNode; 90 import org.graalvm.compiler.nodes.extended.LoadHubNode; 91 import org.graalvm.compiler.nodes.extended.ValueAnchorNode; 92 import org.graalvm.compiler.nodes.java.InstanceOfNode; 93 import org.graalvm.compiler.nodes.java.TypeSwitchNode; 94 import org.graalvm.compiler.nodes.spi.CoreProviders; 95 import org.graalvm.compiler.nodes.spi.NodeWithState; 96 import org.graalvm.compiler.nodes.spi.StampInverter; 97 import org.graalvm.compiler.nodes.util.GraphUtil; 98 import org.graalvm.compiler.phases.BasePhase; 99 import org.graalvm.compiler.phases.schedule.SchedulePhase; 100 import org.graalvm.compiler.phases.schedule.SchedulePhase.SchedulingStrategy; 101 102 import jdk.vm.ci.meta.DeoptimizationAction; 103 import jdk.vm.ci.meta.JavaConstant; 104 import jdk.vm.ci.meta.SpeculationLog.Speculation; 105 import jdk.vm.ci.meta.TriState; 106 107 public class ConditionalEliminationPhase extends BasePhase<CoreProviders> { 108 109 private static final CounterKey counterStampsRegistered = DebugContext.counter("StampsRegistered"); 110 private static final CounterKey counterStampsFound = DebugContext.counter("StampsFound"); 111 private static final CounterKey counterIfsKilled = DebugContext.counter("CE_KilledIfs"); 112 private static final CounterKey counterPhiStampsImproved = DebugContext.counter("CE_ImprovedPhis"); 113 private final boolean fullSchedule; 114 private final boolean moveGuards; 115 116 public ConditionalEliminationPhase(boolean fullSchedule) { 117 this(fullSchedule, true); 118 } 119 120 public ConditionalEliminationPhase(boolean fullSchedule, boolean moveGuards) { 121 this.fullSchedule = fullSchedule; 122 this.moveGuards = moveGuards; 123 } 124 125 @Override 126 @SuppressWarnings("try") 127 protected void run(StructuredGraph graph, CoreProviders context) { 128 try (DebugContext.Scope s = graph.getDebug().scope("DominatorConditionalElimination")) { 129 BlockMap<List<Node>> blockToNodes = null; 130 NodeMap<Block> nodeToBlock = null; 131 ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true); 132 if (fullSchedule) { 133 if (moveGuards) { 134 cfg.visitDominatorTree(new MoveGuardsUpwards(), graph.hasValueProxies()); 135 } 136 try (DebugContext.Scope scheduleScope = graph.getDebug().scope(SchedulePhase.class)) { 137 SchedulePhase.run(graph, SchedulingStrategy.EARLIEST_WITH_GUARD_ORDER, cfg); 138 } catch (Throwable t) { 139 throw graph.getDebug().handle(t); 140 } 141 ScheduleResult r = graph.getLastSchedule(); 142 blockToNodes = r.getBlockToNodesMap(); 143 nodeToBlock = r.getNodeToBlockMap(); 144 } else { 145 nodeToBlock = cfg.getNodeToBlock(); 146 blockToNodes = getBlockToNodes(cfg); 147 } 148 ControlFlowGraph.RecursiveVisitor<?> visitor = createVisitor(graph, cfg, blockToNodes, nodeToBlock, context); 149 cfg.visitDominatorTree(visitor, graph.hasValueProxies()); 150 } 151 } 152 153 protected BlockMap<List<Node>> getBlockToNodes(@SuppressWarnings("unused") ControlFlowGraph cfg) { 154 return null; 155 } 156 157 protected ControlFlowGraph.RecursiveVisitor<?> createVisitor(StructuredGraph graph, @SuppressWarnings("unused") ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodes, 158 NodeMap<Block> nodeToBlock, CoreProviders context) { 159 return new Instance(graph, blockToNodes, nodeToBlock, context); 160 } 161 162 public static class MoveGuardsUpwards implements ControlFlowGraph.RecursiveVisitor<Block> { 163 164 Block anchorBlock; 165 166 @Override 167 @SuppressWarnings("try") 168 public Block enter(Block b) { 169 Block oldAnchorBlock = anchorBlock; 170 if (b.getDominator() == null || b.getDominator().getPostdominator() != b) { 171 // New anchor. 172 anchorBlock = b; 173 } 174 175 AbstractBeginNode beginNode = b.getBeginNode(); 176 if (beginNode instanceof AbstractMergeNode && anchorBlock != b) { 177 AbstractMergeNode mergeNode = (AbstractMergeNode) beginNode; 178 mergeNode.replaceAtUsages(InputType.Anchor, anchorBlock.getBeginNode()); 179 mergeNode.replaceAtUsages(InputType.Guard, anchorBlock.getBeginNode()); 180 assert mergeNode.anchored().isEmpty(); 181 } 182 183 FixedNode endNode = b.getEndNode(); 184 if (endNode instanceof IfNode) { 185 IfNode node = (IfNode) endNode; 186 187 // Check if we can move guards upwards. 188 AbstractBeginNode trueSuccessor = node.trueSuccessor(); 189 EconomicMap<LogicNode, GuardNode> trueGuards = EconomicMap.create(Equivalence.IDENTITY); 190 for (GuardNode guard : trueSuccessor.guards()) { 191 LogicNode condition = guard.getCondition(); 192 if (condition.hasMoreThanOneUsage()) { 193 trueGuards.put(condition, guard); 194 } 195 } 196 197 if (!trueGuards.isEmpty()) { 198 for (GuardNode guard : node.falseSuccessor().guards().snapshot()) { 199 GuardNode otherGuard = trueGuards.get(guard.getCondition()); 200 if (otherGuard != null && guard.isNegated() == otherGuard.isNegated()) { 201 Speculation speculation = otherGuard.getSpeculation(); 202 if (speculation == null) { 203 speculation = guard.getSpeculation(); 204 } else if (guard.getSpeculation() != null && guard.getSpeculation() != speculation) { 205 // Cannot optimize due to different speculations. 206 continue; 207 } 208 try (DebugCloseable closeable = guard.withNodeSourcePosition()) { 209 GuardNode newlyCreatedGuard = new GuardNode(guard.getCondition(), anchorBlock.getBeginNode(), guard.getReason(), guard.getAction(), guard.isNegated(), speculation, 210 guard.getNoDeoptSuccessorPosition()); 211 GuardNode newGuard = node.graph().unique(newlyCreatedGuard); 212 if (otherGuard.isAlive()) { 213 otherGuard.replaceAndDelete(newGuard); 214 } 215 guard.replaceAndDelete(newGuard); 216 } 217 } 218 } 219 } 220 } 221 return oldAnchorBlock; 222 } 223 224 @Override 225 public void exit(Block b, Block value) { 226 anchorBlock = value; 227 } 228 229 } 230 231 private static final class PhiInfoElement { 232 233 private EconomicMap<EndNode, InfoElement> infoElements; 234 235 public void set(EndNode end, InfoElement infoElement) { 236 if (infoElements == null) { 237 infoElements = EconomicMap.create(Equivalence.IDENTITY); 238 } 239 infoElements.put(end, infoElement); 240 } 241 242 public InfoElement get(EndNode end) { 243 if (infoElements == null) { 244 return null; 245 } 246 return infoElements.get(end); 247 } 248 } 249 250 public static final class Marks { 251 final int infoElementOperations; 252 final int conditions; 253 254 public Marks(int infoElementOperations, int conditions) { 255 this.infoElementOperations = infoElementOperations; 256 this.conditions = conditions; 257 } 258 } 259 260 protected static final class GuardedCondition { 261 private final GuardingNode guard; 262 private final LogicNode condition; 263 private final boolean negated; 264 265 public GuardedCondition(GuardingNode guard, LogicNode condition, boolean negated) { 266 this.guard = guard; 267 this.condition = condition; 268 this.negated = negated; 269 } 270 271 public GuardingNode getGuard() { 272 return guard; 273 } 274 275 public LogicNode getCondition() { 276 return condition; 277 } 278 279 public boolean isNegated() { 280 return negated; 281 } 282 } 283 284 public static class Instance implements ControlFlowGraph.RecursiveVisitor<Marks> { 285 protected final NodeMap<InfoElement> map; 286 protected final BlockMap<List<Node>> blockToNodes; 287 protected final NodeMap<Block> nodeToBlock; 288 protected final CanonicalizerTool tool; 289 protected final NodeStack undoOperations; 290 protected final StructuredGraph graph; 291 protected final DebugContext debug; 292 protected final EconomicMap<MergeNode, EconomicMap<ValuePhiNode, PhiInfoElement>> mergeMaps; 293 294 protected final ArrayDeque<GuardedCondition> conditions; 295 296 /** 297 * Tests which may be eliminated because post dominating tests to prove a broader condition. 298 */ 299 private Deque<DeoptimizingGuard> pendingTests; 300 301 public Instance(StructuredGraph graph, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, CoreProviders context) { 302 this.graph = graph; 303 this.debug = graph.getDebug(); 304 this.blockToNodes = blockToNodes; 305 this.nodeToBlock = nodeToBlock; 306 this.undoOperations = new NodeStack(); 307 this.map = graph.createNodeMap(); 308 this.pendingTests = new ArrayDeque<>(); 309 this.conditions = new ArrayDeque<>(); 310 tool = GraphUtil.getDefaultSimplifier(context.getMetaAccess(), context.getConstantReflection(), context.getConstantFieldProvider(), false, graph.getAssumptions(), graph.getOptions(), 311 context.getLowerer()); 312 mergeMaps = EconomicMap.create(Equivalence.IDENTITY); 313 } 314 315 protected void processConditionAnchor(ConditionAnchorNode node) { 316 tryProveCondition(node.condition(), (guard, result, guardedValueStamp, newInput) -> { 317 if (result != node.isNegated()) { 318 node.replaceAtUsages(guard.asNode()); 319 GraphUtil.unlinkFixedNode(node); 320 GraphUtil.killWithUnusedFloatingInputs(node); 321 } else { 322 ValueAnchorNode valueAnchor = node.graph().add(new ValueAnchorNode(null)); 323 node.replaceAtUsages(valueAnchor); 324 node.graph().replaceFixedWithFixed(node, valueAnchor); 325 } 326 return true; 327 }); 328 } 329 330 protected void processGuard(GuardNode node) { 331 if (!tryProveGuardCondition(node, node.getCondition(), (guard, result, guardedValueStamp, newInput) -> { 332 if (result != node.isNegated()) { 333 node.replaceAndDelete(guard.asNode()); 334 if (guard instanceof DeoptimizingGuard && !((DeoptimizingGuard) guard).isNegated()) { 335 rebuildPiNodes((DeoptimizingGuard) guard); 336 } 337 } else { 338 AbstractBeginNode beginNode = (AbstractBeginNode) node.getAnchor(); 339 340 if (beginNode.next() instanceof DeoptimizeNode) { 341 // This branch is already dead. 342 } else { 343 /* 344 * Don't kill this branch immediately because `killCFG` can have complex 345 * implications in the presence of loops: it might replace or delete nodes 346 * in other branches or even above the kill point. Instead of killing 347 * immediately, just leave the graph in a state that is easy to simplify by 348 * a subsequent canonicalizer phase. 349 */ 350 FixedGuardNode deopt = new FixedGuardNode(LogicConstantNode.forBoolean(result, node.graph()), node.getReason(), node.getAction(), node.getSpeculation(), node.isNegated(), 351 node.getNodeSourcePosition()); 352 graph.addAfterFixed(beginNode, node.graph().add(deopt)); 353 } 354 } 355 return true; 356 })) { 357 registerNewCondition(node.getCondition(), node.isNegated(), node); 358 } 359 } 360 361 protected void processFixedGuard(FixedGuardNode node) { 362 if (!tryProveGuardCondition(node, node.condition(), (guard, result, guardedValueStamp, newInput) -> { 363 if (result != node.isNegated()) { 364 node.replaceAtUsages(guard.asNode()); 365 GraphUtil.unlinkFixedNode(node); 366 GraphUtil.killWithUnusedFloatingInputs(node); 367 if (guard instanceof DeoptimizingGuard && !((DeoptimizingGuard) guard).isNegated()) { 368 rebuildPiNodes((DeoptimizingGuard) guard); 369 } 370 } else { 371 node.setCondition(LogicConstantNode.forBoolean(result, node.graph()), node.isNegated()); 372 // Don't kill this branch immediately, see `processGuard`. 373 } 374 375 debug.log("Kill fixed guard %s", node); 376 return true; 377 })) { 378 registerNewCondition(node.condition(), node.isNegated(), node); 379 } 380 } 381 382 private void rebuildPiNodes(DeoptimizingGuard guard) { 383 LogicNode newCondition = guard.getCondition(); 384 if (newCondition instanceof InstanceOfNode) { 385 InstanceOfNode inst = (InstanceOfNode) newCondition; 386 ValueNode originalValue = GraphUtil.skipPi(inst.getValue()); 387 PiNode pi = null; 388 // Ensure that any Pi that's weaker than what the instanceof proves is 389 // replaced by one derived from the instanceof itself. 390 for (PiNode existing : guard.asNode().usages().filter(PiNode.class).snapshot()) { 391 if (!existing.isAlive()) { 392 continue; 393 } 394 if (originalValue != GraphUtil.skipPi(existing.object())) { 395 // Somehow these are unrelated values so leave it alone 396 continue; 397 } 398 // If the pi has a weaker stamp or the same stamp but a different input 399 // then replace it. 400 boolean strongerStamp = !existing.piStamp().join(inst.getCheckedStamp()).equals(inst.getCheckedStamp()); 401 boolean differentCheckedStamp = !existing.piStamp().equals(inst.getCheckedStamp()); 402 boolean differentObject = existing.object() != inst.getValue(); 403 if (!strongerStamp && (differentCheckedStamp || differentObject)) { 404 if (pi == null) { 405 pi = graph.unique(new PiNode(inst.getValue(), inst.getCheckedStamp(), (ValueNode) guard)); 406 } 407 if (!pi.stamp(NodeView.DEFAULT).join(existing.stamp(NodeView.DEFAULT)).equals(pi.stamp(NodeView.DEFAULT))) { 408 /* 409 * With a code sequence like null check, type check, null check of type 410 * checked value, CE will use the first null check to prove the second 411 * null check so the graph ends up a Pi guarded by the first null check 412 * but consuming the output Pi from the type check check. In this case 413 * we should still canonicalize the checked stamp for consistency. 414 */ 415 if (differentCheckedStamp) { 416 PiNode alternatePi = graph.unique(new PiNode(existing.object(), inst.getCheckedStamp(), (ValueNode) guard)); 417 /* 418 * If the resulting stamp is as good or better then do the 419 * replacement. However when interface types are involved it's 420 * possible that improving the checked stamp merges types which 421 * appear unrelated so there's we must skip the replacement. 422 */ 423 if (alternatePi.stamp(NodeView.DEFAULT).join(existing.stamp(NodeView.DEFAULT)).equals(alternatePi.stamp(NodeView.DEFAULT))) { 424 existing.replaceAndDelete(alternatePi); 425 } 426 } 427 continue; 428 } 429 existing.replaceAndDelete(pi); 430 } 431 } 432 } 433 } 434 435 protected void processIf(IfNode node) { 436 tryProveCondition(node.condition(), (guard, result, guardedValueStamp, newInput) -> { 437 node.setCondition(LogicConstantNode.forBoolean(result, node.graph())); 438 AbstractBeginNode survivingSuccessor = node.getSuccessor(result); 439 survivingSuccessor.replaceAtUsages(InputType.Guard, guard.asNode()); 440 // Don't kill the other branch immediately, see `processGuard`. 441 counterIfsKilled.increment(debug); 442 return true; 443 }); 444 } 445 446 @Override 447 public Marks enter(Block block) { 448 int infoElementsMark = undoOperations.size(); 449 int conditionsMark = conditions.size(); 450 debug.log("[Pre Processing block %s]", block); 451 // For now conservatively collect guards only within the same block. 452 pendingTests.clear(); 453 processNodes(block); 454 return new Marks(infoElementsMark, conditionsMark); 455 } 456 457 protected void processNodes(Block block) { 458 if (blockToNodes != null) { 459 for (Node n : blockToNodes.get(block)) { 460 if (n.isAlive()) { 461 processNode(n); 462 } 463 } 464 } else { 465 processBlock(block); 466 } 467 } 468 469 private void processBlock(Block block) { 470 FixedNode n = block.getBeginNode(); 471 FixedNode endNode = block.getEndNode(); 472 debug.log("[Processing block %s]", block); 473 while (n != endNode) { 474 if (n.isDeleted() || endNode.isDeleted()) { 475 // This branch was deleted! 476 return; 477 } 478 FixedNode next = ((FixedWithNextNode) n).next(); 479 processNode(n); 480 n = next; 481 } 482 if (endNode.isAlive()) { 483 processNode(endNode); 484 } 485 } 486 487 @SuppressWarnings("try") 488 protected void processNode(Node node) { 489 try (DebugCloseable closeable = node.withNodeSourcePosition()) { 490 if (node instanceof NodeWithState && !(node instanceof GuardingNode)) { 491 pendingTests.clear(); 492 } 493 494 if (node instanceof MergeNode) { 495 introducePisForPhis((MergeNode) node); 496 } 497 498 if (node instanceof AbstractBeginNode) { 499 if (node instanceof LoopExitNode && graph.hasValueProxies()) { 500 // Condition must not be used down this path. 501 return; 502 } 503 processAbstractBegin((AbstractBeginNode) node); 504 } else if (node instanceof FixedGuardNode) { 505 processFixedGuard((FixedGuardNode) node); 506 } else if (node instanceof GuardNode) { 507 processGuard((GuardNode) node); 508 } else if (node instanceof ConditionAnchorNode) { 509 processConditionAnchor((ConditionAnchorNode) node); 510 } else if (node instanceof IfNode) { 511 processIf((IfNode) node); 512 } else if (node instanceof EndNode) { 513 processEnd((EndNode) node); 514 } 515 } 516 } 517 518 protected void introducePisForPhis(MergeNode merge) { 519 EconomicMap<ValuePhiNode, PhiInfoElement> mergeMap = this.mergeMaps.get(merge); 520 if (mergeMap != null) { 521 MapCursor<ValuePhiNode, PhiInfoElement> entries = mergeMap.getEntries(); 522 while (entries.advance()) { 523 ValuePhiNode phi = entries.getKey(); 524 assert phi.isAlive() || phi.isDeleted(); 525 /* 526 * Phi might have been killed already via a conditional elimination in another 527 * branch. 528 */ 529 if (phi.isDeleted()) { 530 continue; 531 } 532 PhiInfoElement phiInfoElements = entries.getValue(); 533 Stamp bestPossibleStamp = null; 534 for (int i = 0; i < phi.valueCount(); ++i) { 535 ValueNode valueAt = phi.valueAt(i); 536 Stamp curBestStamp = valueAt.stamp(NodeView.DEFAULT); 537 InfoElement infoElement = phiInfoElements.get(merge.forwardEndAt(i)); 538 if (infoElement != null) { 539 curBestStamp = curBestStamp.join(infoElement.getStamp()); 540 } 541 542 if (bestPossibleStamp == null) { 543 bestPossibleStamp = curBestStamp; 544 } else { 545 bestPossibleStamp = bestPossibleStamp.meet(curBestStamp); 546 } 547 } 548 549 Stamp oldStamp = phi.stamp(NodeView.DEFAULT); 550 if (oldStamp.tryImproveWith(bestPossibleStamp) != null) { 551 552 // Need to be careful to not run into stamp update cycles with the iterative 553 // canonicalization. 554 boolean allow = false; 555 if (bestPossibleStamp instanceof ObjectStamp) { 556 // Always allow object stamps. 557 allow = true; 558 } else if (bestPossibleStamp instanceof IntegerStamp) { 559 IntegerStamp integerStamp = (IntegerStamp) bestPossibleStamp; 560 IntegerStamp oldIntegerStamp = (IntegerStamp) oldStamp; 561 if (integerStamp.isPositive() != oldIntegerStamp.isPositive()) { 562 allow = true; 563 } else if (integerStamp.isNegative() != oldIntegerStamp.isNegative()) { 564 allow = true; 565 } else if (integerStamp.isStrictlyPositive() != oldIntegerStamp.isStrictlyPositive()) { 566 allow = true; 567 } else if (integerStamp.isStrictlyNegative() != oldIntegerStamp.isStrictlyNegative()) { 568 allow = true; 569 } else if (integerStamp.asConstant() != null) { 570 allow = true; 571 } else if (oldStamp.isUnrestricted()) { 572 allow = true; 573 } 574 } else { 575 // Fortify: Suppress Null Dereference false positive 576 assert bestPossibleStamp != null; 577 allow = (bestPossibleStamp.asConstant() != null); 578 } 579 580 if (allow) { 581 ValuePhiNode newPhi = graph.addWithoutUnique(new ValuePhiNode(bestPossibleStamp, merge)); 582 for (int i = 0; i < phi.valueCount(); ++i) { 583 ValueNode valueAt = phi.valueAt(i); 584 if (bestPossibleStamp.meet(valueAt.stamp(NodeView.DEFAULT)).equals(bestPossibleStamp)) { 585 // Pi not required here. 586 } else { 587 InfoElement infoElement = phiInfoElements.get(merge.forwardEndAt(i)); 588 assert infoElement != null; 589 Stamp curBestStamp = infoElement.getStamp(); 590 ValueNode input = infoElement.getProxifiedInput(); 591 if (input == null) { 592 input = valueAt; 593 } 594 valueAt = graph.maybeAddOrUnique(PiNode.create(input, curBestStamp, (ValueNode) infoElement.guard)); 595 } 596 newPhi.addInput(valueAt); 597 } 598 counterPhiStampsImproved.increment(debug); 599 phi.replaceAtUsagesAndDelete(newPhi); 600 } 601 } 602 } 603 } 604 } 605 606 protected void processEnd(EndNode end) { 607 AbstractMergeNode abstractMerge = end.merge(); 608 if (abstractMerge instanceof MergeNode) { 609 MergeNode merge = (MergeNode) abstractMerge; 610 611 EconomicMap<ValuePhiNode, PhiInfoElement> mergeMap = this.mergeMaps.get(merge); 612 for (ValuePhiNode phi : merge.valuePhis()) { 613 ValueNode valueAt = phi.valueAt(end); 614 InfoElement infoElement = this.getInfoElements(valueAt); 615 while (infoElement != null) { 616 Stamp newStamp = infoElement.getStamp(); 617 if (phi.stamp(NodeView.DEFAULT).tryImproveWith(newStamp) != null) { 618 if (mergeMap == null) { 619 mergeMap = EconomicMap.create(Equivalence.IDENTITY); 620 mergeMaps.put(merge, mergeMap); 621 } 622 623 PhiInfoElement phiInfoElement = mergeMap.get(phi); 624 if (phiInfoElement == null) { 625 phiInfoElement = new PhiInfoElement(); 626 mergeMap.put(phi, phiInfoElement); 627 } 628 629 phiInfoElement.set(end, infoElement); 630 break; 631 } 632 infoElement = nextElement(infoElement); 633 } 634 } 635 } 636 } 637 638 protected void registerNewCondition(LogicNode condition, boolean negated, GuardingNode guard) { 639 if (condition instanceof UnaryOpLogicNode) { 640 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) condition; 641 ValueNode value = unaryLogicNode.getValue(); 642 if (maybeMultipleUsages(value)) { 643 // getSucceedingStampForValue doesn't take the (potentially a Pi Node) input 644 // stamp into account, so it can be safely propagated. 645 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(negated); 646 registerNewStamp(value, newStamp, guard, true); 647 } 648 } else if (condition instanceof BinaryOpLogicNode) { 649 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) condition; 650 ValueNode x = binaryOpLogicNode.getX(); 651 ValueNode y = binaryOpLogicNode.getY(); 652 if (!x.isConstant() && maybeMultipleUsages(x)) { 653 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(negated, getSafeStamp(x), getOtherSafeStamp(y)); 654 registerNewStamp(x, newStampX, guard); 655 } 656 657 if (!y.isConstant() && maybeMultipleUsages(y)) { 658 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(negated, getOtherSafeStamp(x), getSafeStamp(y)); 659 registerNewStamp(y, newStampY, guard); 660 } 661 662 if (condition instanceof IntegerEqualsNode && guard instanceof DeoptimizingGuard && !negated) { 663 if (y.isConstant() && x instanceof AndNode) { 664 AndNode and = (AndNode) x; 665 ValueNode andX = and.getX(); 666 if (and.getY() == y && maybeMultipleUsages(andX)) { 667 /* 668 * This 'and' proves something about some of the bits in and.getX(). 669 * It's equivalent to or'ing in the mask value since those values are 670 * known to be set. 671 */ 672 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp(NodeView.DEFAULT)).getOr(); 673 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(andX), getOtherSafeStamp(y)); 674 registerNewStamp(andX, newStampX, guard); 675 } 676 } 677 } 678 } 679 if (guard instanceof DeoptimizingGuard) { 680 assert ((DeoptimizingGuard) guard).getCondition() == condition; 681 pendingTests.push((DeoptimizingGuard) guard); 682 } 683 registerCondition(condition, negated, guard); 684 } 685 686 Pair<InfoElement, Stamp> recursiveFoldStamp(Node node) { 687 if (node instanceof UnaryNode) { 688 UnaryNode unary = (UnaryNode) node; 689 ValueNode value = unary.getValue(); 690 InfoElement infoElement = getInfoElements(value); 691 while (infoElement != null) { 692 Stamp result = unary.foldStamp(infoElement.getStamp()); 693 if (result != null) { 694 return Pair.create(infoElement, result); 695 } 696 infoElement = nextElement(infoElement); 697 } 698 } else if (node instanceof BinaryNode) { 699 BinaryNode binary = (BinaryNode) node; 700 ValueNode y = binary.getY(); 701 ValueNode x = binary.getX(); 702 if (y.isConstant()) { 703 InfoElement infoElement = getInfoElements(x); 704 while (infoElement != null) { 705 Stamp result = binary.foldStamp(infoElement.stamp, y.stamp(NodeView.DEFAULT)); 706 if (result != null) { 707 return Pair.create(infoElement, result); 708 } 709 infoElement = nextElement(infoElement); 710 } 711 } 712 } 713 return null; 714 } 715 716 /** 717 * Get the stamp that may be used for the value for which we are registering the condition. 718 * We may directly use the stamp here without restriction, because any later lookup of the 719 * registered info elements is in the same chain of pi nodes. 720 */ 721 private static Stamp getSafeStamp(ValueNode x) { 722 return x.stamp(NodeView.DEFAULT); 723 } 724 725 /** 726 * We can only use the stamp of a second value involved in the condition if we are sure that 727 * we are not implicitly creating a dependency on a pi node that is responsible for that 728 * stamp. For now, we are conservatively only using the stamps of constants. Under certain 729 * circumstances, we may also be able to use the stamp of the value after skipping pi nodes 730 * (e.g., the stamp of a parameter after inlining, or the stamp of a fixed node that can 731 * never be replaced with a pi node via canonicalization). 732 */ 733 private static Stamp getOtherSafeStamp(ValueNode x) { 734 if (x.isConstant() || x.graph().isAfterFixedReadPhase()) { 735 return x.stamp(NodeView.DEFAULT); 736 } 737 return x.stamp(NodeView.DEFAULT).unrestricted(); 738 } 739 740 /** 741 * Recursively try to fold stamps within this expression using information from 742 * {@link #getInfoElements(ValueNode)}. It's only safe to use constants and one 743 * {@link InfoElement} otherwise more than one guard would be required. 744 * 745 * @param node 746 * @return the pair of the @{link InfoElement} used and the stamp produced for the whole 747 * expression 748 */ 749 Pair<InfoElement, Stamp> recursiveFoldStampFromInfo(Node node) { 750 return recursiveFoldStamp(node); 751 } 752 753 /** 754 * Look for a preceding guard whose condition is implied by {@code thisGuard}. If we find 755 * one, try to move this guard just above that preceding guard so that we can fold it: 756 * 757 * <pre> 758 * guard(C1); // preceding guard 759 * ... 760 * guard(C2); // thisGuard 761 * </pre> 762 * 763 * If C2 => C1, transform to: 764 * 765 * <pre> 766 * guard(C2); 767 * ... 768 * </pre> 769 */ 770 protected boolean foldPendingTest(DeoptimizingGuard thisGuard, ValueNode original, Stamp newStamp, GuardRewirer rewireGuardFunction) { 771 for (DeoptimizingGuard pendingGuard : pendingTests) { 772 LogicNode pendingCondition = pendingGuard.getCondition(); 773 TriState result = TriState.UNKNOWN; 774 if (pendingCondition instanceof UnaryOpLogicNode) { 775 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) pendingCondition; 776 if (unaryLogicNode.getValue() == original) { 777 result = unaryLogicNode.tryFold(newStamp); 778 } 779 } else if (pendingCondition instanceof BinaryOpLogicNode) { 780 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) pendingCondition; 781 ValueNode x = binaryOpLogicNode.getX(); 782 ValueNode y = binaryOpLogicNode.getY(); 783 if (x == original) { 784 result = binaryOpLogicNode.tryFold(newStamp, getOtherSafeStamp(y)); 785 } else if (y == original) { 786 result = binaryOpLogicNode.tryFold(getOtherSafeStamp(x), newStamp); 787 } else if (binaryOpLogicNode instanceof IntegerEqualsNode && y.isConstant() && x instanceof AndNode) { 788 AndNode and = (AndNode) x; 789 if (and.getY() == y && and.getX() == original) { 790 BinaryOp<And> andOp = ArithmeticOpTable.forStamp(newStamp).getAnd(); 791 result = binaryOpLogicNode.tryFold(andOp.foldStamp(newStamp, getOtherSafeStamp(y)), getOtherSafeStamp(y)); 792 } 793 } 794 } 795 if (result.isKnown()) { 796 /* 797 * The test case be folded using the information available but the test can only 798 * be moved up if we're sure there's no schedule dependence. 799 */ 800 if (canScheduleAbove(thisGuard.getCondition(), pendingGuard.asNode(), original) && foldGuard(thisGuard, pendingGuard, result.toBoolean(), newStamp, rewireGuardFunction)) { 801 return true; 802 } 803 } 804 } 805 return false; 806 } 807 808 private boolean canScheduleAbove(Node n, Node target, ValueNode knownToBeAbove) { 809 Block targetBlock = nodeToBlock.get(target); 810 Block testBlock = nodeToBlock.get(n); 811 if (targetBlock != null && testBlock != null) { 812 if (targetBlock == testBlock) { 813 for (Node fixed : blockToNodes.get(targetBlock)) { 814 if (fixed == n) { 815 return true; 816 } else if (fixed == target) { 817 break; 818 } 819 } 820 } else if (AbstractControlFlowGraph.dominates(testBlock, targetBlock)) { 821 return true; 822 } 823 } 824 InputFilter v = new InputFilter(knownToBeAbove); 825 n.applyInputs(v); 826 return v.ok; 827 } 828 829 protected boolean foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, boolean outcome, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) { 830 DeoptimizationAction action = mergeActions(otherGuard.getAction(), thisGuard.getAction()); 831 if (action != null && otherGuard.getSpeculation() == thisGuard.getSpeculation()) { 832 LogicNode condition = (LogicNode) thisGuard.getCondition().copyWithInputs(); 833 /* 834 * We have ...; guard(C1); guard(C2);... 835 * 836 * Where the first guard is `otherGuard` and the second one `thisGuard`. 837 * 838 * Depending on `outcome`, we have C2 => C1 or C2 => !C1. 839 * 840 * - If C2 => C1, `mustDeopt` below is false and we transform to ...; guard(C2); ... 841 * 842 * - If C2 => !C1, `mustDeopt` is true and we transform to ..; guard(C1); deopt; 843 */ 844 // for the second case, the action of the deopt is copied from there: 845 thisGuard.setAction(action); 846 GuardRewirer rewirer = (guard, result, innerGuardedValueStamp, newInput) -> { 847 // `result` is `outcome`, `guard` is `otherGuard` 848 boolean mustDeopt = result == otherGuard.isNegated(); 849 if (rewireGuardFunction.rewire(guard, mustDeopt == thisGuard.isNegated(), innerGuardedValueStamp, newInput)) { 850 if (!mustDeopt) { 851 otherGuard.setCondition(condition, thisGuard.isNegated()); 852 otherGuard.setAction(action); 853 otherGuard.setReason(thisGuard.getReason()); 854 } 855 return true; 856 } 857 condition.safeDelete(); 858 return false; 859 }; 860 // Move the later test up 861 return rewireGuards(otherGuard, outcome, null, guardedValueStamp, rewirer); 862 } 863 return false; 864 } 865 866 protected void registerCondition(LogicNode condition, boolean negated, GuardingNode guard) { 867 if (condition.hasMoreThanOneUsage()) { 868 registerNewStamp(condition, negated ? StampFactory.contradiction() : StampFactory.tautology(), guard); 869 } 870 conditions.push(new GuardedCondition(guard, condition, negated)); 871 } 872 873 protected InfoElement getInfoElements(ValueNode proxiedValue) { 874 if (proxiedValue == null) { 875 return null; 876 } 877 InfoElement infoElement = map.getAndGrow(proxiedValue); 878 if (infoElement == null) { 879 infoElement = map.getAndGrow(GraphUtil.skipPi(proxiedValue)); 880 } 881 return infoElement; 882 } 883 884 protected boolean rewireGuards(GuardingNode guard, boolean result, ValueNode proxifiedInput, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) { 885 counterStampsFound.increment(debug); 886 return rewireGuardFunction.rewire(guard, result, guardedValueStamp, proxifiedInput); 887 } 888 889 protected boolean tryProveCondition(LogicNode node, GuardRewirer rewireGuardFunction) { 890 return tryProveGuardCondition(null, node, rewireGuardFunction); 891 } 892 893 private InfoElement nextElement(InfoElement current) { 894 InfoElement parent = current.getParent(); 895 if (parent != null) { 896 return parent; 897 } else { 898 ValueNode proxifiedInput = current.getProxifiedInput(); 899 if (proxifiedInput instanceof PiNode) { 900 PiNode piNode = (PiNode) proxifiedInput; 901 return getInfoElements(piNode.getOriginalNode()); 902 } 903 } 904 return null; 905 } 906 907 protected boolean tryProveGuardCondition(DeoptimizingGuard thisGuard, LogicNode node, GuardRewirer rewireGuardFunction) { 908 InfoElement infoElement = getInfoElements(node); 909 while (infoElement != null) { 910 Stamp stamp = infoElement.getStamp(); 911 JavaConstant constant = (JavaConstant) stamp.asConstant(); 912 if (constant != null) { 913 // No proxified input and stamp required. 914 return rewireGuards(infoElement.getGuard(), constant.asBoolean(), null, null, rewireGuardFunction); 915 } 916 infoElement = nextElement(infoElement); 917 } 918 919 for (GuardedCondition guardedCondition : this.conditions) { 920 TriState result = guardedCondition.getCondition().implies(guardedCondition.isNegated(), node); 921 if (result.isKnown()) { 922 return rewireGuards(guardedCondition.guard, result.toBoolean(), null, null, rewireGuardFunction); 923 } 924 } 925 926 if (node instanceof UnaryOpLogicNode) { 927 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) node; 928 ValueNode value = unaryLogicNode.getValue(); 929 infoElement = getInfoElements(value); 930 while (infoElement != null) { 931 Stamp stamp = infoElement.getStamp(); 932 TriState result = unaryLogicNode.tryFold(stamp); 933 if (result.isKnown()) { 934 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction); 935 } 936 infoElement = nextElement(infoElement); 937 } 938 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(value); 939 if (foldResult != null) { 940 TriState result = unaryLogicNode.tryFold(foldResult.getRight()); 941 if (result.isKnown()) { 942 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction); 943 } 944 } 945 if (thisGuard != null) { 946 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(thisGuard.isNegated()); 947 if (newStamp != null && foldPendingTest(thisGuard, value, newStamp, rewireGuardFunction)) { 948 return true; 949 } 950 951 } 952 } else if (node instanceof BinaryOpLogicNode) { 953 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) node; 954 ValueNode x = binaryOpLogicNode.getX(); 955 ValueNode y = binaryOpLogicNode.getY(); 956 infoElement = getInfoElements(x); 957 while (infoElement != null) { 958 TriState result = binaryOpLogicNode.tryFold(infoElement.getStamp(), y.stamp(NodeView.DEFAULT)); 959 if (result.isKnown()) { 960 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction); 961 } 962 infoElement = nextElement(infoElement); 963 } 964 965 if (y.isConstant()) { 966 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(x); 967 if (foldResult != null) { 968 TriState result = binaryOpLogicNode.tryFold(foldResult.getRight(), y.stamp(NodeView.DEFAULT)); 969 if (result.isKnown()) { 970 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction); 971 } 972 } 973 } else { 974 infoElement = getInfoElements(y); 975 while (infoElement != null) { 976 TriState result = binaryOpLogicNode.tryFold(x.stamp(NodeView.DEFAULT), infoElement.getStamp()); 977 if (result.isKnown()) { 978 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction); 979 } 980 infoElement = nextElement(infoElement); 981 } 982 } 983 984 /* 985 * For complex expressions involving constants, see if it's possible to fold the 986 * tests by using stamps one level up in the expression. For instance, (x + n < y) 987 * might fold if something is known about x and all other values are constants. The 988 * reason for the constant restriction is that if more than 1 real value is involved 989 * the code might need to adopt multiple guards to have proper dependences. 990 */ 991 if (x instanceof BinaryArithmeticNode<?> && y.isConstant()) { 992 BinaryArithmeticNode<?> binary = (BinaryArithmeticNode<?>) x; 993 if (binary.getY().isConstant()) { 994 infoElement = getInfoElements(binary.getX()); 995 while (infoElement != null) { 996 Stamp newStampX = binary.foldStamp(infoElement.getStamp(), binary.getY().stamp(NodeView.DEFAULT)); 997 TriState result = binaryOpLogicNode.tryFold(newStampX, y.stamp(NodeView.DEFAULT)); 998 if (result.isKnown()) { 999 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), newStampX, rewireGuardFunction); 1000 } 1001 infoElement = nextElement(infoElement); 1002 } 1003 } 1004 } 1005 1006 if (thisGuard != null && binaryOpLogicNode instanceof IntegerEqualsNode && !thisGuard.isNegated()) { 1007 if (y.isConstant() && x instanceof AndNode) { 1008 AndNode and = (AndNode) x; 1009 if (and.getY() == y) { 1010 /* 1011 * This 'and' proves something about some of the bits in and.getX(). 1012 * It's equivalent to or'ing in the mask value since those values are 1013 * known to be set. 1014 */ 1015 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp(NodeView.DEFAULT)).getOr(); 1016 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(and.getX()), getOtherSafeStamp(y)); 1017 if (foldPendingTest(thisGuard, and.getX(), newStampX, rewireGuardFunction)) { 1018 return true; 1019 } 1020 } 1021 } 1022 } 1023 1024 if (thisGuard != null) { 1025 if (!x.isConstant()) { 1026 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(thisGuard.isNegated(), getSafeStamp(x), getOtherSafeStamp(y)); 1027 if (newStampX != null && foldPendingTest(thisGuard, x, newStampX, rewireGuardFunction)) { 1028 return true; 1029 } 1030 } 1031 if (!y.isConstant()) { 1032 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(thisGuard.isNegated(), getOtherSafeStamp(x), getSafeStamp(y)); 1033 if (newStampY != null && foldPendingTest(thisGuard, y, newStampY, rewireGuardFunction)) { 1034 return true; 1035 } 1036 } 1037 } 1038 } else if (node instanceof ShortCircuitOrNode) { 1039 final ShortCircuitOrNode shortCircuitOrNode = (ShortCircuitOrNode) node; 1040 return tryProveCondition(shortCircuitOrNode.getX(), (guard, result, guardedValueStamp, newInput) -> { 1041 if (result == !shortCircuitOrNode.isXNegated()) { 1042 return rewireGuards(guard, true, newInput, guardedValueStamp, rewireGuardFunction); 1043 } else { 1044 return tryProveCondition(shortCircuitOrNode.getY(), (innerGuard, innerResult, innerGuardedValueStamp, innerNewInput) -> { 1045 ValueNode proxifiedInput = newInput; 1046 if (proxifiedInput == null) { 1047 proxifiedInput = innerNewInput; 1048 } else if (innerNewInput != null) { 1049 if (innerNewInput != newInput) { 1050 // Cannot canonicalize due to different proxied inputs. 1051 return false; 1052 } 1053 } 1054 // Can only canonicalize if the guards are equal. 1055 if (innerGuard == guard) { 1056 return rewireGuards(guard, innerResult ^ shortCircuitOrNode.isYNegated(), proxifiedInput, guardedValueStamp, rewireGuardFunction); 1057 } 1058 return false; 1059 }); 1060 } 1061 }); 1062 } 1063 1064 return false; 1065 } 1066 1067 protected void registerNewStamp(ValueNode maybeProxiedValue, Stamp newStamp, GuardingNode guard) { 1068 registerNewStamp(maybeProxiedValue, newStamp, guard, false); 1069 } 1070 1071 protected void registerNewStamp(ValueNode maybeProxiedValue, Stamp newStamp, GuardingNode guard, boolean propagateThroughPis) { 1072 assert maybeProxiedValue != null; 1073 assert guard != null; 1074 1075 if (newStamp == null || newStamp.isUnrestricted()) { 1076 return; 1077 } 1078 1079 ValueNode value = maybeProxiedValue; 1080 Stamp stamp = newStamp; 1081 1082 while (stamp != null && value != null) { 1083 ValueNode proxiedValue = null; 1084 if (value instanceof PiNode) { 1085 proxiedValue = value; 1086 } 1087 counterStampsRegistered.increment(debug); 1088 debug.log("\t Saving stamp for node %s stamp %s guarded by %s", value, stamp, guard); 1089 assert value instanceof LogicNode || stamp.isCompatible(value.stamp(NodeView.DEFAULT)) : stamp + " vs. " + value.stamp(NodeView.DEFAULT) + " (" + value + ")"; 1090 map.setAndGrow(value, new InfoElement(stamp, guard, proxiedValue, map.getAndGrow(value))); 1091 undoOperations.push(value); 1092 if (propagateThroughPis && value instanceof PiNode) { 1093 PiNode piNode = (PiNode) value; 1094 value = piNode.getOriginalNode(); 1095 } else if (value instanceof StampInverter) { 1096 StampInverter stampInverter = (StampInverter) value; 1097 value = stampInverter.getValue(); 1098 stamp = stampInverter.invertStamp(stamp); 1099 } else { 1100 break; 1101 } 1102 } 1103 } 1104 1105 protected void processAbstractBegin(AbstractBeginNode beginNode) { 1106 Node predecessor = beginNode.predecessor(); 1107 if (predecessor instanceof IfNode) { 1108 IfNode ifNode = (IfNode) predecessor; 1109 boolean negated = (ifNode.falseSuccessor() == beginNode); 1110 LogicNode condition = ifNode.condition(); 1111 registerNewCondition(condition, negated, beginNode); 1112 } else if (predecessor instanceof TypeSwitchNode) { 1113 TypeSwitchNode typeSwitch = (TypeSwitchNode) predecessor; 1114 processTypeSwitch(beginNode, typeSwitch); 1115 } else if (predecessor instanceof IntegerSwitchNode) { 1116 IntegerSwitchNode integerSwitchNode = (IntegerSwitchNode) predecessor; 1117 processIntegerSwitch(beginNode, integerSwitchNode); 1118 } 1119 } 1120 1121 private static boolean maybeMultipleUsages(ValueNode value) { 1122 if (value.hasMoreThanOneUsage()) { 1123 return true; 1124 } else { 1125 return value instanceof ProxyNode || 1126 value instanceof PiNode || 1127 value instanceof StampInverter; 1128 } 1129 } 1130 1131 protected void processIntegerSwitch(AbstractBeginNode beginNode, IntegerSwitchNode integerSwitchNode) { 1132 ValueNode value = integerSwitchNode.value(); 1133 if (maybeMultipleUsages(value)) { 1134 Stamp stamp = integerSwitchNode.getValueStampForSuccessor(beginNode); 1135 if (stamp != null) { 1136 registerNewStamp(value, stamp, beginNode); 1137 } 1138 } 1139 } 1140 1141 protected void processTypeSwitch(AbstractBeginNode beginNode, TypeSwitchNode typeSwitch) { 1142 ValueNode hub = typeSwitch.value(); 1143 if (hub instanceof LoadHubNode) { 1144 LoadHubNode loadHub = (LoadHubNode) hub; 1145 ValueNode value = loadHub.getValue(); 1146 if (maybeMultipleUsages(value)) { 1147 Stamp stamp = typeSwitch.getValueStampForSuccessor(beginNode); 1148 if (stamp != null) { 1149 registerNewStamp(value, stamp, beginNode); 1150 } 1151 } 1152 } 1153 } 1154 1155 @Override 1156 public void exit(Block b, Marks marks) { 1157 int infoElementsMark = marks.infoElementOperations; 1158 while (undoOperations.size() > infoElementsMark) { 1159 Node node = undoOperations.pop(); 1160 if (node.isAlive()) { 1161 map.set(node, map.get(node).getParent()); 1162 } 1163 } 1164 1165 int conditionsMark = marks.conditions; 1166 while (conditions.size() > conditionsMark) { 1167 conditions.pop(); 1168 } 1169 } 1170 } 1171 1172 @FunctionalInterface 1173 protected interface InfoElementProvider { 1174 Iterable<InfoElement> getInfoElements(ValueNode value); 1175 } 1176 1177 /** 1178 * Checks for safe nodes when moving pending tests up. 1179 */ 1180 static class InputFilter extends Node.EdgeVisitor { 1181 boolean ok; 1182 private ValueNode value; 1183 1184 InputFilter(ValueNode value) { 1185 this.value = value; 1186 this.ok = true; 1187 } 1188 1189 @Override 1190 public Node apply(Node node, Node curNode) { 1191 if (!ok) { 1192 // Abort the recursion 1193 return curNode; 1194 } 1195 if (!(curNode instanceof ValueNode)) { 1196 ok = false; 1197 return curNode; 1198 } 1199 ValueNode curValue = (ValueNode) curNode; 1200 if (curValue.isConstant() || curValue == value || curValue instanceof ParameterNode) { 1201 return curNode; 1202 } 1203 if (curValue instanceof BinaryNode || curValue instanceof UnaryNode) { 1204 curValue.applyInputs(this); 1205 } else { 1206 ok = false; 1207 } 1208 return curNode; 1209 } 1210 } 1211 1212 @FunctionalInterface 1213 protected interface GuardRewirer { 1214 /** 1215 * Called if the condition could be proven to have a constant value ({@code result}) under 1216 * {@code guard}. 1217 * 1218 * @param guard the guard whose result is proven 1219 * @param result the known result of the guard 1220 * @param newInput new input to pi nodes depending on the new guard 1221 * @return whether the transformation could be applied 1222 */ 1223 boolean rewire(GuardingNode guard, boolean result, Stamp guardedValueStamp, ValueNode newInput); 1224 } 1225 1226 protected static final class InfoElement { 1227 private final Stamp stamp; 1228 private final GuardingNode guard; 1229 private final ValueNode proxifiedInput; 1230 private final InfoElement parent; 1231 1232 public InfoElement(Stamp stamp, GuardingNode guard, ValueNode proxifiedInput, InfoElement parent) { 1233 this.stamp = stamp; 1234 this.guard = guard; 1235 this.proxifiedInput = proxifiedInput; 1236 this.parent = parent; 1237 } 1238 1239 public InfoElement getParent() { 1240 return parent; 1241 } 1242 1243 public Stamp getStamp() { 1244 return stamp; 1245 } 1246 1247 public GuardingNode getGuard() { 1248 return guard; 1249 } 1250 1251 public ValueNode getProxifiedInput() { 1252 return proxifiedInput; 1253 } 1254 1255 @Override 1256 public String toString() { 1257 return stamp + " -> " + guard; 1258 } 1259 } 1260 1261 @Override 1262 public float codeSizeIncrease() { 1263 return 1.5f; 1264 } 1265 }