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 ConditionalEliminationPhase(boolean fullSchedule)114 public ConditionalEliminationPhase(boolean fullSchedule) { 115 this(fullSchedule, true); 116 } 117 ConditionalEliminationPhase(boolean fullSchedule, boolean moveGuards)118 public ConditionalEliminationPhase(boolean fullSchedule, boolean moveGuards) { 119 this.fullSchedule = fullSchedule; 120 this.moveGuards = moveGuards; 121 } 122 123 @Override 124 @SuppressWarnings("try") run(StructuredGraph graph, PhaseContext context)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 getBlockToNodes(@uppressWarningsR) ControlFlowGraph cfg)151 protected BlockMap<List<Node>> getBlockToNodes(@SuppressWarnings("unused") ControlFlowGraph cfg) { 152 return null; 153 } 154 createVisitor(StructuredGraph graph, @SuppressWarnings(R) ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, PhaseContext context)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") enter(Block b)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 exit(Block b, Block value)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 set(EndNode end, InfoElement infoElement)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 get(EndNode end)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 Marks(int infoElementOperations, int conditions)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 GuardedCondition(GuardingNode guard, LogicNode condition, boolean negated)268 public GuardedCondition(GuardingNode guard, LogicNode condition, boolean negated) { 269 this.guard = guard; 270 this.condition = condition; 271 this.negated = negated; 272 } 273 getGuard()274 public GuardingNode getGuard() { 275 return guard; 276 } 277 getCondition()278 public LogicNode getCondition() { 279 return condition; 280 } 281 isNegated()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 Instance(StructuredGraph graph, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, PhaseContext context)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 processConditionAnchor(ConditionAnchorNode node)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 processGuard(GuardNode node)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 processFixedGuard(FixedGuardNode node)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 processIf(IfNode node)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 enter(Block block)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 processNodes(Block block)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 processBlock(Block block)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") processNode(Node node)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 introducePisForPhis(MergeNode merge)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 allow = (bestPossibleStamp.asConstant() != null); 515 } 516 517 if (allow) { 518 ValuePhiNode newPhi = graph.addWithoutUnique(new ValuePhiNode(bestPossibleStamp, merge)); 519 for (int i = 0; i < phi.valueCount(); ++i) { 520 ValueNode valueAt = phi.valueAt(i); 521 if (bestPossibleStamp.meet(valueAt.stamp(NodeView.DEFAULT)).equals(bestPossibleStamp)) { 522 // Pi not required here. 523 } else { 524 InfoElement infoElement = phiInfoElements.get(merge.forwardEndAt(i)); 525 assert infoElement != null; 526 Stamp curBestStamp = infoElement.getStamp(); 527 ValueNode input = infoElement.getProxifiedInput(); 528 if (input == null) { 529 input = valueAt; 530 } 531 valueAt = graph.maybeAddOrUnique(PiNode.create(input, curBestStamp, (ValueNode) infoElement.guard)); 532 } 533 newPhi.addInput(valueAt); 534 } 535 counterPhiStampsImproved.increment(debug); 536 phi.replaceAtUsagesAndDelete(newPhi); 537 } 538 } 539 } 540 } 541 } 542 processEnd(EndNode end)543 protected void processEnd(EndNode end) { 544 AbstractMergeNode abstractMerge = end.merge(); 545 if (abstractMerge instanceof MergeNode) { 546 MergeNode merge = (MergeNode) abstractMerge; 547 548 EconomicMap<ValuePhiNode, PhiInfoElement> mergeMap = this.mergeMaps.get(merge); 549 for (ValuePhiNode phi : merge.valuePhis()) { 550 ValueNode valueAt = phi.valueAt(end); 551 InfoElement infoElement = this.getInfoElements(valueAt); 552 while (infoElement != null) { 553 Stamp newStamp = infoElement.getStamp(); 554 if (phi.stamp(NodeView.DEFAULT).tryImproveWith(newStamp) != null) { 555 if (mergeMap == null) { 556 mergeMap = EconomicMap.create(); 557 mergeMaps.put(merge, mergeMap); 558 } 559 560 PhiInfoElement phiInfoElement = mergeMap.get(phi); 561 if (phiInfoElement == null) { 562 phiInfoElement = new PhiInfoElement(); 563 mergeMap.put(phi, phiInfoElement); 564 } 565 566 phiInfoElement.set(end, infoElement); 567 break; 568 } 569 infoElement = nextElement(infoElement); 570 } 571 } 572 } 573 } 574 registerNewCondition(LogicNode condition, boolean negated, GuardingNode guard)575 protected void registerNewCondition(LogicNode condition, boolean negated, GuardingNode guard) { 576 if (condition instanceof UnaryOpLogicNode) { 577 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) condition; 578 ValueNode value = unaryLogicNode.getValue(); 579 if (maybeMultipleUsages(value)) { 580 // getSucceedingStampForValue doesn't take the (potentially a Pi Node) input 581 // stamp into account, so it can be safely propagated. 582 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(negated); 583 registerNewStamp(value, newStamp, guard, true); 584 } 585 } else if (condition instanceof BinaryOpLogicNode) { 586 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) condition; 587 ValueNode x = binaryOpLogicNode.getX(); 588 ValueNode y = binaryOpLogicNode.getY(); 589 if (!x.isConstant() && maybeMultipleUsages(x)) { 590 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(negated, getSafeStamp(x), getOtherSafeStamp(y)); 591 registerNewStamp(x, newStampX, guard); 592 } 593 594 if (!y.isConstant() && maybeMultipleUsages(y)) { 595 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(negated, getOtherSafeStamp(x), getSafeStamp(y)); 596 registerNewStamp(y, newStampY, guard); 597 } 598 599 if (condition instanceof IntegerEqualsNode && guard instanceof DeoptimizingGuard && !negated) { 600 if (y.isConstant() && x instanceof AndNode) { 601 AndNode and = (AndNode) x; 602 ValueNode andX = and.getX(); 603 if (and.getY() == y && maybeMultipleUsages(andX)) { 604 /* 605 * This 'and' proves something about some of the bits in and.getX(). 606 * It's equivalent to or'ing in the mask value since those values are 607 * known to be set. 608 */ 609 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp(NodeView.DEFAULT)).getOr(); 610 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(andX), getOtherSafeStamp(y)); 611 registerNewStamp(andX, newStampX, guard); 612 } 613 } 614 } 615 } 616 if (guard instanceof DeoptimizingGuard) { 617 assert ((DeoptimizingGuard) guard).getCondition() == condition; 618 pendingTests.push((DeoptimizingGuard) guard); 619 } 620 registerCondition(condition, negated, guard); 621 } 622 recursiveFoldStamp(Node node)623 Pair<InfoElement, Stamp> recursiveFoldStamp(Node node) { 624 if (node instanceof UnaryNode) { 625 UnaryNode unary = (UnaryNode) node; 626 ValueNode value = unary.getValue(); 627 InfoElement infoElement = getInfoElements(value); 628 while (infoElement != null) { 629 Stamp result = unary.foldStamp(infoElement.getStamp()); 630 if (result != null) { 631 return Pair.create(infoElement, result); 632 } 633 infoElement = nextElement(infoElement); 634 } 635 } else if (node instanceof BinaryNode) { 636 BinaryNode binary = (BinaryNode) node; 637 ValueNode y = binary.getY(); 638 ValueNode x = binary.getX(); 639 if (y.isConstant()) { 640 InfoElement infoElement = getInfoElements(x); 641 while (infoElement != null) { 642 Stamp result = binary.foldStamp(infoElement.stamp, y.stamp(NodeView.DEFAULT)); 643 if (result != null) { 644 return Pair.create(infoElement, result); 645 } 646 infoElement = nextElement(infoElement); 647 } 648 } 649 } 650 return null; 651 } 652 653 /** 654 * Get the stamp that may be used for the value for which we are registering the condition. 655 * We may directly use the stamp here without restriction, because any later lookup of the 656 * registered info elements is in the same chain of pi nodes. 657 */ getSafeStamp(ValueNode x)658 private static Stamp getSafeStamp(ValueNode x) { 659 return x.stamp(NodeView.DEFAULT); 660 } 661 662 /** 663 * We can only use the stamp of a second value involved in the condition if we are sure that 664 * we are not implicitly creating a dependency on a pi node that is responsible for that 665 * stamp. For now, we are conservatively only using the stamps of constants. Under certain 666 * circumstances, we may also be able to use the stamp of the value after skipping pi nodes 667 * (e.g., the stamp of a parameter after inlining, or the stamp of a fixed node that can 668 * never be replaced with a pi node via canonicalization). 669 */ getOtherSafeStamp(ValueNode x)670 private static Stamp getOtherSafeStamp(ValueNode x) { 671 if (x.isConstant() || x.graph().isAfterFixedReadPhase()) { 672 return x.stamp(NodeView.DEFAULT); 673 } 674 return x.stamp(NodeView.DEFAULT).unrestricted(); 675 } 676 677 /** 678 * Recursively try to fold stamps within this expression using information from 679 * {@link #getInfoElements(ValueNode)}. It's only safe to use constants and one 680 * {@link InfoElement} otherwise more than one guard would be required. 681 * 682 * @param node 683 * @return the pair of the @{link InfoElement} used and the stamp produced for the whole 684 * expression 685 */ recursiveFoldStampFromInfo(Node node)686 Pair<InfoElement, Stamp> recursiveFoldStampFromInfo(Node node) { 687 return recursiveFoldStamp(node); 688 } 689 690 /** 691 * Look for a preceding guard whose condition is implied by {@code thisGuard}. If we find 692 * one, try to move this guard just above that preceding guard so that we can fold it: 693 * 694 * <pre> 695 * guard(C1); // preceding guard 696 * ... 697 * guard(C2); // thisGuard 698 * </pre> 699 * 700 * If C2 => C1, transform to: 701 * 702 * <pre> 703 * guard(C2); 704 * ... 705 * </pre> 706 */ foldPendingTest(DeoptimizingGuard thisGuard, ValueNode original, Stamp newStamp, GuardRewirer rewireGuardFunction)707 protected boolean foldPendingTest(DeoptimizingGuard thisGuard, ValueNode original, Stamp newStamp, GuardRewirer rewireGuardFunction) { 708 for (DeoptimizingGuard pendingGuard : pendingTests) { 709 LogicNode pendingCondition = pendingGuard.getCondition(); 710 TriState result = TriState.UNKNOWN; 711 if (pendingCondition instanceof UnaryOpLogicNode) { 712 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) pendingCondition; 713 if (unaryLogicNode.getValue() == original) { 714 result = unaryLogicNode.tryFold(newStamp); 715 } 716 } else if (pendingCondition instanceof BinaryOpLogicNode) { 717 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) pendingCondition; 718 ValueNode x = binaryOpLogicNode.getX(); 719 ValueNode y = binaryOpLogicNode.getY(); 720 if (x == original) { 721 result = binaryOpLogicNode.tryFold(newStamp, getOtherSafeStamp(y)); 722 } else if (y == original) { 723 result = binaryOpLogicNode.tryFold(getOtherSafeStamp(x), newStamp); 724 } else if (binaryOpLogicNode instanceof IntegerEqualsNode && y.isConstant() && x instanceof AndNode) { 725 AndNode and = (AndNode) x; 726 if (and.getY() == y && and.getX() == original) { 727 BinaryOp<And> andOp = ArithmeticOpTable.forStamp(newStamp).getAnd(); 728 result = binaryOpLogicNode.tryFold(andOp.foldStamp(newStamp, getOtherSafeStamp(y)), getOtherSafeStamp(y)); 729 } 730 } 731 } 732 if (result.isKnown()) { 733 /* 734 * The test case be folded using the information available but the test can only 735 * be moved up if we're sure there's no schedule dependence. 736 */ 737 if (canScheduleAbove(thisGuard.getCondition(), pendingGuard.asNode(), original) && foldGuard(thisGuard, pendingGuard, result.toBoolean(), newStamp, rewireGuardFunction)) { 738 return true; 739 } 740 } 741 } 742 return false; 743 } 744 canScheduleAbove(Node n, Node target, ValueNode knownToBeAbove)745 private boolean canScheduleAbove(Node n, Node target, ValueNode knownToBeAbove) { 746 Block targetBlock = nodeToBlock.get(target); 747 Block testBlock = nodeToBlock.get(n); 748 if (targetBlock != null && testBlock != null) { 749 if (targetBlock == testBlock) { 750 for (Node fixed : blockToNodes.get(targetBlock)) { 751 if (fixed == n) { 752 return true; 753 } else if (fixed == target) { 754 break; 755 } 756 } 757 } else if (AbstractControlFlowGraph.dominates(testBlock, targetBlock)) { 758 return true; 759 } 760 } 761 InputFilter v = new InputFilter(knownToBeAbove); 762 n.applyInputs(v); 763 return v.ok; 764 } 765 foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, boolean outcome, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction)766 protected boolean foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, boolean outcome, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) { 767 DeoptimizationAction action = mergeActions(otherGuard.getAction(), thisGuard.getAction()); 768 if (action != null && otherGuard.getSpeculation() == thisGuard.getSpeculation()) { 769 LogicNode condition = (LogicNode) thisGuard.getCondition().copyWithInputs(); 770 /* 771 * We have ...; guard(C1); guard(C2);... 772 * 773 * Where the first guard is `otherGuard` and the second one `thisGuard`. 774 * 775 * Depending on `outcome`, we have C2 => C1 or C2 => !C1. 776 * 777 * - If C2 => C1, `mustDeopt` below is false and we transform to ...; guard(C2); ... 778 * 779 * - If C2 => !C1, `mustDeopt` is true and we transform to ..; guard(C1); deopt; 780 */ 781 // for the second case, the action of the deopt is copied from there: 782 thisGuard.setAction(action); 783 GuardRewirer rewirer = (guard, result, innerGuardedValueStamp, newInput) -> { 784 // `result` is `outcome`, `guard` is `otherGuard` 785 boolean mustDeopt = result == otherGuard.isNegated(); 786 if (rewireGuardFunction.rewire(guard, mustDeopt == thisGuard.isNegated(), innerGuardedValueStamp, newInput)) { 787 if (!mustDeopt) { 788 otherGuard.setCondition(condition, thisGuard.isNegated()); 789 otherGuard.setAction(action); 790 otherGuard.setReason(thisGuard.getReason()); 791 } 792 return true; 793 } 794 condition.safeDelete(); 795 return false; 796 }; 797 // Move the later test up 798 return rewireGuards(otherGuard, outcome, null, guardedValueStamp, rewirer); 799 } 800 return false; 801 } 802 registerCondition(LogicNode condition, boolean negated, GuardingNode guard)803 protected void registerCondition(LogicNode condition, boolean negated, GuardingNode guard) { 804 if (condition.hasMoreThanOneUsage()) { 805 registerNewStamp(condition, negated ? StampFactory.contradiction() : StampFactory.tautology(), guard); 806 } 807 conditions.push(new GuardedCondition(guard, condition, negated)); 808 } 809 getInfoElements(ValueNode proxiedValue)810 protected InfoElement getInfoElements(ValueNode proxiedValue) { 811 if (proxiedValue == null) { 812 return null; 813 } 814 InfoElement infoElement = map.getAndGrow(proxiedValue); 815 if (infoElement == null) { 816 infoElement = map.getAndGrow(GraphUtil.skipPi(proxiedValue)); 817 } 818 return infoElement; 819 } 820 rewireGuards(GuardingNode guard, boolean result, ValueNode proxifiedInput, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction)821 protected boolean rewireGuards(GuardingNode guard, boolean result, ValueNode proxifiedInput, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) { 822 counterStampsFound.increment(debug); 823 return rewireGuardFunction.rewire(guard, result, guardedValueStamp, proxifiedInput); 824 } 825 tryProveCondition(LogicNode node, GuardRewirer rewireGuardFunction)826 protected boolean tryProveCondition(LogicNode node, GuardRewirer rewireGuardFunction) { 827 return tryProveGuardCondition(null, node, rewireGuardFunction); 828 } 829 nextElement(InfoElement current)830 private InfoElement nextElement(InfoElement current) { 831 InfoElement parent = current.getParent(); 832 if (parent != null) { 833 return parent; 834 } else { 835 ValueNode proxifiedInput = current.getProxifiedInput(); 836 if (proxifiedInput instanceof PiNode) { 837 PiNode piNode = (PiNode) proxifiedInput; 838 return getInfoElements(piNode.getOriginalNode()); 839 } 840 } 841 return null; 842 } 843 tryProveGuardCondition(DeoptimizingGuard thisGuard, LogicNode node, GuardRewirer rewireGuardFunction)844 protected boolean tryProveGuardCondition(DeoptimizingGuard thisGuard, LogicNode node, GuardRewirer rewireGuardFunction) { 845 InfoElement infoElement = getInfoElements(node); 846 while (infoElement != null) { 847 Stamp stamp = infoElement.getStamp(); 848 JavaConstant constant = (JavaConstant) stamp.asConstant(); 849 if (constant != null) { 850 // No proxified input and stamp required. 851 return rewireGuards(infoElement.getGuard(), constant.asBoolean(), null, null, rewireGuardFunction); 852 } 853 infoElement = nextElement(infoElement); 854 } 855 856 for (GuardedCondition guardedCondition : this.conditions) { 857 TriState result = guardedCondition.getCondition().implies(guardedCondition.isNegated(), node); 858 if (result.isKnown()) { 859 return rewireGuards(guardedCondition.guard, result.toBoolean(), null, null, rewireGuardFunction); 860 } 861 } 862 863 if (node instanceof UnaryOpLogicNode) { 864 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) node; 865 ValueNode value = unaryLogicNode.getValue(); 866 infoElement = getInfoElements(value); 867 while (infoElement != null) { 868 Stamp stamp = infoElement.getStamp(); 869 TriState result = unaryLogicNode.tryFold(stamp); 870 if (result.isKnown()) { 871 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction); 872 } 873 infoElement = nextElement(infoElement); 874 } 875 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(value); 876 if (foldResult != null) { 877 TriState result = unaryLogicNode.tryFold(foldResult.getRight()); 878 if (result.isKnown()) { 879 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction); 880 } 881 } 882 if (thisGuard != null) { 883 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(thisGuard.isNegated()); 884 if (newStamp != null && foldPendingTest(thisGuard, value, newStamp, rewireGuardFunction)) { 885 return true; 886 } 887 888 } 889 } else if (node instanceof BinaryOpLogicNode) { 890 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) node; 891 ValueNode x = binaryOpLogicNode.getX(); 892 ValueNode y = binaryOpLogicNode.getY(); 893 infoElement = getInfoElements(x); 894 while (infoElement != null) { 895 TriState result = binaryOpLogicNode.tryFold(infoElement.getStamp(), y.stamp(NodeView.DEFAULT)); 896 if (result.isKnown()) { 897 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction); 898 } 899 infoElement = nextElement(infoElement); 900 } 901 902 if (y.isConstant()) { 903 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(x); 904 if (foldResult != null) { 905 TriState result = binaryOpLogicNode.tryFold(foldResult.getRight(), y.stamp(NodeView.DEFAULT)); 906 if (result.isKnown()) { 907 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction); 908 } 909 } 910 } else { 911 infoElement = getInfoElements(y); 912 while (infoElement != null) { 913 TriState result = binaryOpLogicNode.tryFold(x.stamp(NodeView.DEFAULT), infoElement.getStamp()); 914 if (result.isKnown()) { 915 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction); 916 } 917 infoElement = nextElement(infoElement); 918 } 919 } 920 921 /* 922 * For complex expressions involving constants, see if it's possible to fold the 923 * tests by using stamps one level up in the expression. For instance, (x + n < y) 924 * might fold if something is known about x and all other values are constants. The 925 * reason for the constant restriction is that if more than 1 real value is involved 926 * the code might need to adopt multiple guards to have proper dependences. 927 */ 928 if (x instanceof BinaryArithmeticNode<?> && y.isConstant()) { 929 BinaryArithmeticNode<?> binary = (BinaryArithmeticNode<?>) x; 930 if (binary.getY().isConstant()) { 931 infoElement = getInfoElements(binary.getX()); 932 while (infoElement != null) { 933 Stamp newStampX = binary.foldStamp(infoElement.getStamp(), binary.getY().stamp(NodeView.DEFAULT)); 934 TriState result = binaryOpLogicNode.tryFold(newStampX, y.stamp(NodeView.DEFAULT)); 935 if (result.isKnown()) { 936 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), newStampX, rewireGuardFunction); 937 } 938 infoElement = nextElement(infoElement); 939 } 940 } 941 } 942 943 if (thisGuard != null && binaryOpLogicNode instanceof IntegerEqualsNode && !thisGuard.isNegated()) { 944 if (y.isConstant() && x instanceof AndNode) { 945 AndNode and = (AndNode) x; 946 if (and.getY() == y) { 947 /* 948 * This 'and' proves something about some of the bits in and.getX(). 949 * It's equivalent to or'ing in the mask value since those values are 950 * known to be set. 951 */ 952 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp(NodeView.DEFAULT)).getOr(); 953 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(and.getX()), getOtherSafeStamp(y)); 954 if (foldPendingTest(thisGuard, and.getX(), newStampX, rewireGuardFunction)) { 955 return true; 956 } 957 } 958 } 959 } 960 961 if (thisGuard != null) { 962 if (!x.isConstant()) { 963 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(thisGuard.isNegated(), getSafeStamp(x), getOtherSafeStamp(y)); 964 if (newStampX != null && foldPendingTest(thisGuard, x, newStampX, rewireGuardFunction)) { 965 return true; 966 } 967 } 968 if (!y.isConstant()) { 969 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(thisGuard.isNegated(), getOtherSafeStamp(x), getSafeStamp(y)); 970 if (newStampY != null && foldPendingTest(thisGuard, y, newStampY, rewireGuardFunction)) { 971 return true; 972 } 973 } 974 } 975 } else if (node instanceof ShortCircuitOrNode) { 976 final ShortCircuitOrNode shortCircuitOrNode = (ShortCircuitOrNode) node; 977 return tryProveCondition(shortCircuitOrNode.getX(), (guard, result, guardedValueStamp, newInput) -> { 978 if (result == !shortCircuitOrNode.isXNegated()) { 979 return rewireGuards(guard, true, newInput, guardedValueStamp, rewireGuardFunction); 980 } else { 981 return tryProveCondition(shortCircuitOrNode.getY(), (innerGuard, innerResult, innerGuardedValueStamp, innerNewInput) -> { 982 ValueNode proxifiedInput = newInput; 983 if (proxifiedInput == null) { 984 proxifiedInput = innerNewInput; 985 } else if (innerNewInput != null) { 986 if (innerNewInput != newInput) { 987 // Cannot canonicalize due to different proxied inputs. 988 return false; 989 } 990 } 991 // Can only canonicalize if the guards are equal. 992 if (innerGuard == guard) { 993 return rewireGuards(guard, innerResult ^ shortCircuitOrNode.isYNegated(), proxifiedInput, guardedValueStamp, rewireGuardFunction); 994 } 995 return false; 996 }); 997 } 998 }); 999 } 1000 1001 return false; 1002 } 1003 1004 protected void registerNewStamp(ValueNode maybeProxiedValue, Stamp newStamp, GuardingNode guard) { 1005 registerNewStamp(maybeProxiedValue, newStamp, guard, false); 1006 } 1007 1008 protected void registerNewStamp(ValueNode maybeProxiedValue, Stamp newStamp, GuardingNode guard, boolean propagateThroughPis) { 1009 assert maybeProxiedValue != null; 1010 assert guard != null; 1011 1012 if (newStamp == null || newStamp.isUnrestricted()) { 1013 return; 1014 } 1015 1016 ValueNode value = maybeProxiedValue; 1017 Stamp stamp = newStamp; 1018 1019 while (stamp != null && value != null) { 1020 ValueNode proxiedValue = null; 1021 if (value instanceof PiNode) { 1022 proxiedValue = value; 1023 } 1024 counterStampsRegistered.increment(debug); 1025 debug.log("\t Saving stamp for node %s stamp %s guarded by %s", value, stamp, guard); 1026 assert value instanceof LogicNode || stamp.isCompatible(value.stamp(NodeView.DEFAULT)) : stamp + " vs. " + value.stamp(NodeView.DEFAULT) + " (" + value + ")"; 1027 map.setAndGrow(value, new InfoElement(stamp, guard, proxiedValue, map.getAndGrow(value))); 1028 undoOperations.push(value); 1029 if (propagateThroughPis && value instanceof PiNode) { 1030 PiNode piNode = (PiNode) value; 1031 value = piNode.getOriginalNode(); 1032 } else if (value instanceof StampInverter) { 1033 StampInverter stampInverter = (StampInverter) value; 1034 value = stampInverter.getValue(); 1035 stamp = stampInverter.invertStamp(stamp); 1036 } else { 1037 break; 1038 } 1039 } 1040 } 1041 1042 protected void processAbstractBegin(AbstractBeginNode beginNode) { 1043 Node predecessor = beginNode.predecessor(); 1044 if (predecessor instanceof IfNode) { 1045 IfNode ifNode = (IfNode) predecessor; 1046 boolean negated = (ifNode.falseSuccessor() == beginNode); 1047 LogicNode condition = ifNode.condition(); 1048 registerNewCondition(condition, negated, beginNode); 1049 } else if (predecessor instanceof TypeSwitchNode) { 1050 TypeSwitchNode typeSwitch = (TypeSwitchNode) predecessor; 1051 processTypeSwitch(beginNode, typeSwitch); 1052 } else if (predecessor instanceof IntegerSwitchNode) { 1053 IntegerSwitchNode integerSwitchNode = (IntegerSwitchNode) predecessor; 1054 processIntegerSwitch(beginNode, integerSwitchNode); 1055 } 1056 } 1057 1058 private static boolean maybeMultipleUsages(ValueNode value) { 1059 if (value.hasMoreThanOneUsage()) { 1060 return true; 1061 } else { 1062 return value instanceof ProxyNode || 1063 value instanceof PiNode || 1064 value instanceof StampInverter; 1065 } 1066 } 1067 1068 protected void processIntegerSwitch(AbstractBeginNode beginNode, IntegerSwitchNode integerSwitchNode) { 1069 ValueNode value = integerSwitchNode.value(); 1070 if (maybeMultipleUsages(value)) { 1071 Stamp stamp = integerSwitchNode.getValueStampForSuccessor(beginNode); 1072 if (stamp != null) { 1073 registerNewStamp(value, stamp, beginNode); 1074 } 1075 } 1076 } 1077 1078 protected void processTypeSwitch(AbstractBeginNode beginNode, TypeSwitchNode typeSwitch) { 1079 ValueNode hub = typeSwitch.value(); 1080 if (hub instanceof LoadHubNode) { 1081 LoadHubNode loadHub = (LoadHubNode) hub; 1082 ValueNode value = loadHub.getValue(); 1083 if (maybeMultipleUsages(value)) { 1084 Stamp stamp = typeSwitch.getValueStampForSuccessor(beginNode); 1085 if (stamp != null) { 1086 registerNewStamp(value, stamp, beginNode); 1087 } 1088 } 1089 } 1090 } 1091 1092 @Override 1093 public void exit(Block b, Marks marks) { 1094 int infoElementsMark = marks.infoElementOperations; 1095 while (undoOperations.size() > infoElementsMark) { 1096 Node node = undoOperations.pop(); 1097 if (node.isAlive()) { 1098 map.set(node, map.get(node).getParent()); 1099 } 1100 } 1101 1102 int conditionsMark = marks.conditions; 1103 while (conditions.size() > conditionsMark) { 1104 conditions.pop(); 1105 } 1106 } 1107 } 1108 1109 @FunctionalInterface 1110 protected interface InfoElementProvider { 1111 Iterable<InfoElement> getInfoElements(ValueNode value); 1112 } 1113 1114 /** 1115 * Checks for safe nodes when moving pending tests up. 1116 */ 1117 static class InputFilter extends Node.EdgeVisitor { 1118 boolean ok; 1119 private ValueNode value; 1120 1121 InputFilter(ValueNode value) { 1122 this.value = value; 1123 this.ok = true; 1124 } 1125 1126 @Override 1127 public Node apply(Node node, Node curNode) { 1128 if (!ok) { 1129 // Abort the recursion 1130 return curNode; 1131 } 1132 if (!(curNode instanceof ValueNode)) { 1133 ok = false; 1134 return curNode; 1135 } 1136 ValueNode curValue = (ValueNode) curNode; 1137 if (curValue.isConstant() || curValue == value || curValue instanceof ParameterNode) { 1138 return curNode; 1139 } 1140 if (curValue instanceof BinaryNode || curValue instanceof UnaryNode) { 1141 curValue.applyInputs(this); 1142 } else { 1143 ok = false; 1144 } 1145 return curNode; 1146 } 1147 } 1148 1149 @FunctionalInterface 1150 protected interface GuardRewirer { 1151 /** 1152 * Called if the condition could be proven to have a constant value ({@code result}) under 1153 * {@code guard}. 1154 * 1155 * @param guard the guard whose result is proven 1156 * @param result the known result of the guard 1157 * @param newInput new input to pi nodes depending on the new guard 1158 * @return whether the transformation could be applied 1159 */ 1160 boolean rewire(GuardingNode guard, boolean result, Stamp guardedValueStamp, ValueNode newInput); 1161 } 1162 1163 protected static final class InfoElement { 1164 private final Stamp stamp; 1165 private final GuardingNode guard; 1166 private final ValueNode proxifiedInput; 1167 private final InfoElement parent; 1168 1169 public InfoElement(Stamp stamp, GuardingNode guard, ValueNode proxifiedInput, InfoElement parent) { 1170 this.stamp = stamp; 1171 this.guard = guard; 1172 this.proxifiedInput = proxifiedInput; 1173 this.parent = parent; 1174 } 1175 1176 public InfoElement getParent() { 1177 return parent; 1178 } 1179 1180 public Stamp getStamp() { 1181 return stamp; 1182 } 1183 1184 public GuardingNode getGuard() { 1185 return guard; 1186 } 1187 1188 public ValueNode getProxifiedInput() { 1189 return proxifiedInput; 1190 } 1191 1192 @Override 1193 public String toString() { 1194 return stamp + " -> " + guard; 1195 } 1196 } 1197 1198 @Override 1199 public float codeSizeIncrease() { 1200 return 1.5f; 1201 } 1202 } 1203