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