1 /* 2 * Copyright (c) 2015, 2017, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 25 package org.graalvm.compiler.phases.common; 26 27 import static org.graalvm.compiler.nodes.StaticDeoptimizingNode.mergeActions; 28 29 import java.util.ArrayDeque; 30 import java.util.Deque; 31 import java.util.List; 32 33 import jdk.internal.vm.compiler.collections.EconomicMap; 34 import jdk.internal.vm.compiler.collections.Equivalence; 35 import jdk.internal.vm.compiler.collections.MapCursor; 36 import jdk.internal.vm.compiler.collections.Pair; 37 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph; 38 import org.graalvm.compiler.core.common.cfg.BlockMap; 39 import org.graalvm.compiler.core.common.type.ArithmeticOpTable; 40 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp; 41 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.And; 42 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Or; 43 import org.graalvm.compiler.core.common.type.IntegerStamp; 44 import org.graalvm.compiler.core.common.type.ObjectStamp; 45 import org.graalvm.compiler.core.common.type.Stamp; 46 import org.graalvm.compiler.core.common.type.StampFactory; 47 import org.graalvm.compiler.debug.CounterKey; 48 import org.graalvm.compiler.debug.DebugCloseable; 49 import org.graalvm.compiler.debug.DebugContext; 50 import org.graalvm.compiler.graph.Node; 51 import org.graalvm.compiler.graph.NodeMap; 52 import org.graalvm.compiler.graph.NodeStack; 53 import org.graalvm.compiler.graph.spi.CanonicalizerTool; 54 import org.graalvm.compiler.nodeinfo.InputType; 55 import org.graalvm.compiler.nodes.AbstractBeginNode; 56 import org.graalvm.compiler.nodes.AbstractMergeNode; 57 import org.graalvm.compiler.nodes.BinaryOpLogicNode; 58 import org.graalvm.compiler.nodes.ConditionAnchorNode; 59 import org.graalvm.compiler.nodes.DeoptimizeNode; 60 import org.graalvm.compiler.nodes.DeoptimizingGuard; 61 import org.graalvm.compiler.nodes.EndNode; 62 import org.graalvm.compiler.nodes.FixedGuardNode; 63 import org.graalvm.compiler.nodes.FixedNode; 64 import org.graalvm.compiler.nodes.FixedWithNextNode; 65 import org.graalvm.compiler.nodes.GuardNode; 66 import org.graalvm.compiler.nodes.IfNode; 67 import org.graalvm.compiler.nodes.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 DeoptimizeNode deopt = node.graph().add(new DeoptimizeNode(node.getAction(), node.getReason(), node.getSpeculation())); 339 AbstractBeginNode beginNode = (AbstractBeginNode) node.getAnchor(); 340 FixedNode next = beginNode.next(); 341 beginNode.setNext(deopt); 342 GraphUtil.killCFG(next); 343 } 344 return true; 345 })) { 346 registerNewCondition(node.getCondition(), node.isNegated(), node); 347 } 348 } 349 processFixedGuard(FixedGuardNode node)350 protected void processFixedGuard(FixedGuardNode node) { 351 if (!tryProveGuardCondition(node, node.condition(), (guard, result, guardedValueStamp, newInput) -> { 352 if (result != node.isNegated()) { 353 node.replaceAtUsages(guard.asNode()); 354 GraphUtil.unlinkFixedNode(node); 355 GraphUtil.killWithUnusedFloatingInputs(node); 356 } else { 357 DeoptimizeNode deopt = node.graph().add(new DeoptimizeNode(node.getAction(), node.getReason(), node.getSpeculation())); 358 deopt.setStateBefore(node.stateBefore()); 359 node.replaceAtPredecessor(deopt); 360 GraphUtil.killCFG(node); 361 } 362 debug.log("Kill fixed guard guard"); 363 return true; 364 })) { 365 registerNewCondition(node.condition(), node.isNegated(), node); 366 } 367 } 368 processIf(IfNode node)369 protected void processIf(IfNode node) { 370 tryProveCondition(node.condition(), (guard, result, guardedValueStamp, newInput) -> { 371 AbstractBeginNode survivingSuccessor = node.getSuccessor(result); 372 survivingSuccessor.replaceAtUsages(InputType.Guard, guard.asNode()); 373 survivingSuccessor.replaceAtPredecessor(null); 374 node.replaceAtPredecessor(survivingSuccessor); 375 GraphUtil.killCFG(node); 376 counterIfsKilled.increment(debug); 377 return true; 378 }); 379 } 380 381 @Override enter(Block block)382 public Marks enter(Block block) { 383 int infoElementsMark = undoOperations.size(); 384 int conditionsMark = conditions.size(); 385 debug.log("[Pre Processing block %s]", block); 386 // For now conservatively collect guards only within the same block. 387 pendingTests.clear(); 388 processNodes(block); 389 return new Marks(infoElementsMark, conditionsMark); 390 } 391 processNodes(Block block)392 protected void processNodes(Block block) { 393 if (blockToNodes != null) { 394 for (Node n : blockToNodes.get(block)) { 395 if (n.isAlive()) { 396 processNode(n); 397 } 398 } 399 } else { 400 processBlock(block); 401 } 402 } 403 processBlock(Block block)404 private void processBlock(Block block) { 405 FixedNode n = block.getBeginNode(); 406 FixedNode endNode = block.getEndNode(); 407 debug.log("[Processing block %s]", block); 408 while (n != endNode) { 409 if (n.isDeleted() || endNode.isDeleted()) { 410 // This branch was deleted! 411 return; 412 } 413 FixedNode next = ((FixedWithNextNode) n).next(); 414 processNode(n); 415 n = next; 416 } 417 if (endNode.isAlive()) { 418 processNode(endNode); 419 } 420 } 421 422 @SuppressWarnings("try") processNode(Node node)423 protected void processNode(Node node) { 424 try (DebugCloseable closeable = node.withNodeSourcePosition()) { 425 if (node instanceof NodeWithState && !(node instanceof GuardingNode)) { 426 pendingTests.clear(); 427 } 428 429 if (node instanceof MergeNode) { 430 introducePisForPhis((MergeNode) node); 431 } 432 433 if (node instanceof AbstractBeginNode) { 434 if (node instanceof LoopExitNode && graph.hasValueProxies()) { 435 // Condition must not be used down this path. 436 return; 437 } 438 processAbstractBegin((AbstractBeginNode) node); 439 } else if (node instanceof FixedGuardNode) { 440 processFixedGuard((FixedGuardNode) node); 441 } else if (node instanceof GuardNode) { 442 processGuard((GuardNode) node); 443 } else if (node instanceof ConditionAnchorNode) { 444 processConditionAnchor((ConditionAnchorNode) node); 445 } else if (node instanceof IfNode) { 446 processIf((IfNode) node); 447 } else if (node instanceof EndNode) { 448 processEnd((EndNode) node); 449 } 450 } 451 } 452 introducePisForPhis(MergeNode merge)453 protected void introducePisForPhis(MergeNode merge) { 454 EconomicMap<ValuePhiNode, PhiInfoElement> mergeMap = this.mergeMaps.get(merge); 455 if (mergeMap != null) { 456 MapCursor<ValuePhiNode, PhiInfoElement> entries = mergeMap.getEntries(); 457 while (entries.advance()) { 458 ValuePhiNode phi = entries.getKey(); 459 assert phi.isAlive() || phi.isDeleted(); 460 /* 461 * Phi might have been killed already via a conditional elimination in another 462 * branch. 463 */ 464 if (phi.isDeleted()) { 465 continue; 466 } 467 PhiInfoElement phiInfoElements = entries.getValue(); 468 Stamp bestPossibleStamp = null; 469 for (int i = 0; i < phi.valueCount(); ++i) { 470 ValueNode valueAt = phi.valueAt(i); 471 Stamp curBestStamp = valueAt.stamp(NodeView.DEFAULT); 472 InfoElement infoElement = phiInfoElements.get(merge.forwardEndAt(i)); 473 if (infoElement != null) { 474 curBestStamp = curBestStamp.join(infoElement.getStamp()); 475 } 476 477 if (bestPossibleStamp == null) { 478 bestPossibleStamp = curBestStamp; 479 } else { 480 bestPossibleStamp = bestPossibleStamp.meet(curBestStamp); 481 } 482 } 483 484 Stamp oldStamp = phi.stamp(NodeView.DEFAULT); 485 if (oldStamp.tryImproveWith(bestPossibleStamp) != null) { 486 487 // Need to be careful to not run into stamp update cycles with the iterative 488 // canonicalization. 489 boolean allow = false; 490 if (bestPossibleStamp instanceof ObjectStamp) { 491 // Always allow object stamps. 492 allow = true; 493 } else if (bestPossibleStamp instanceof IntegerStamp) { 494 IntegerStamp integerStamp = (IntegerStamp) bestPossibleStamp; 495 IntegerStamp oldIntegerStamp = (IntegerStamp) oldStamp; 496 if (integerStamp.isPositive() != oldIntegerStamp.isPositive()) { 497 allow = true; 498 } else if (integerStamp.isNegative() != oldIntegerStamp.isNegative()) { 499 allow = true; 500 } else if (integerStamp.isStrictlyPositive() != oldIntegerStamp.isStrictlyPositive()) { 501 allow = true; 502 } else if (integerStamp.isStrictlyNegative() != oldIntegerStamp.isStrictlyNegative()) { 503 allow = true; 504 } else if (integerStamp.asConstant() != null) { 505 allow = true; 506 } else if (oldStamp.isUnrestricted()) { 507 allow = true; 508 } 509 } else { 510 allow = (bestPossibleStamp.asConstant() != null); 511 } 512 513 if (allow) { 514 ValuePhiNode newPhi = graph.addWithoutUnique(new ValuePhiNode(bestPossibleStamp, merge)); 515 for (int i = 0; i < phi.valueCount(); ++i) { 516 ValueNode valueAt = phi.valueAt(i); 517 if (bestPossibleStamp.meet(valueAt.stamp(NodeView.DEFAULT)).equals(bestPossibleStamp)) { 518 // Pi not required here. 519 } else { 520 InfoElement infoElement = phiInfoElements.get(merge.forwardEndAt(i)); 521 assert infoElement != null; 522 Stamp curBestStamp = infoElement.getStamp(); 523 ValueNode input = infoElement.getProxifiedInput(); 524 if (input == null) { 525 input = valueAt; 526 } 527 ValueNode valueNode = graph.maybeAddOrUnique(PiNode.create(input, curBestStamp, (ValueNode) infoElement.guard)); 528 valueAt = valueNode; 529 } 530 newPhi.addInput(valueAt); 531 } 532 counterPhiStampsImproved.increment(debug); 533 phi.replaceAtUsagesAndDelete(newPhi); 534 } 535 } 536 } 537 } 538 } 539 processEnd(EndNode end)540 protected void processEnd(EndNode end) { 541 AbstractMergeNode abstractMerge = end.merge(); 542 if (abstractMerge instanceof MergeNode) { 543 MergeNode merge = (MergeNode) abstractMerge; 544 545 EconomicMap<ValuePhiNode, PhiInfoElement> mergeMap = this.mergeMaps.get(merge); 546 for (ValuePhiNode phi : merge.valuePhis()) { 547 ValueNode valueAt = phi.valueAt(end); 548 InfoElement infoElement = this.getInfoElements(valueAt); 549 while (infoElement != null) { 550 Stamp newStamp = infoElement.getStamp(); 551 if (phi.stamp(NodeView.DEFAULT).tryImproveWith(newStamp) != null) { 552 if (mergeMap == null) { 553 mergeMap = EconomicMap.create(); 554 mergeMaps.put(merge, mergeMap); 555 } 556 557 PhiInfoElement phiInfoElement = mergeMap.get(phi); 558 if (phiInfoElement == null) { 559 phiInfoElement = new PhiInfoElement(); 560 mergeMap.put(phi, phiInfoElement); 561 } 562 563 phiInfoElement.set(end, infoElement); 564 break; 565 } 566 infoElement = nextElement(infoElement); 567 } 568 } 569 } 570 } 571 registerNewCondition(LogicNode condition, boolean negated, GuardingNode guard)572 protected void registerNewCondition(LogicNode condition, boolean negated, GuardingNode guard) { 573 if (condition instanceof UnaryOpLogicNode) { 574 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) condition; 575 ValueNode value = unaryLogicNode.getValue(); 576 if (maybeMultipleUsages(value)) { 577 // getSucceedingStampForValue doesn't take the (potentially a Pi Node) input 578 // stamp into account, so it can be safely propagated. 579 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(negated); 580 registerNewStamp(value, newStamp, guard, true); 581 } 582 } else if (condition instanceof BinaryOpLogicNode) { 583 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) condition; 584 ValueNode x = binaryOpLogicNode.getX(); 585 ValueNode y = binaryOpLogicNode.getY(); 586 if (!x.isConstant() && maybeMultipleUsages(x)) { 587 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(negated, getSafeStamp(x), getOtherSafeStamp(y)); 588 registerNewStamp(x, newStampX, guard); 589 } 590 591 if (!y.isConstant() && maybeMultipleUsages(y)) { 592 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(negated, getOtherSafeStamp(x), getSafeStamp(y)); 593 registerNewStamp(y, newStampY, guard); 594 } 595 596 if (condition instanceof IntegerEqualsNode && guard instanceof DeoptimizingGuard && !negated) { 597 if (y.isConstant() && x instanceof AndNode) { 598 AndNode and = (AndNode) x; 599 ValueNode andX = and.getX(); 600 if (and.getY() == y && maybeMultipleUsages(andX)) { 601 /* 602 * This 'and' proves something about some of the bits in and.getX(). 603 * It's equivalent to or'ing in the mask value since those values are 604 * known to be set. 605 */ 606 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp(NodeView.DEFAULT)).getOr(); 607 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(andX), getOtherSafeStamp(y)); 608 registerNewStamp(andX, newStampX, guard); 609 } 610 } 611 } 612 } 613 if (guard instanceof DeoptimizingGuard) { 614 assert ((DeoptimizingGuard) guard).getCondition() == condition; 615 pendingTests.push((DeoptimizingGuard) guard); 616 } 617 registerCondition(condition, negated, guard); 618 } 619 recursiveFoldStamp(Node node)620 Pair<InfoElement, Stamp> recursiveFoldStamp(Node node) { 621 if (node instanceof UnaryNode) { 622 UnaryNode unary = (UnaryNode) node; 623 ValueNode value = unary.getValue(); 624 InfoElement infoElement = getInfoElements(value); 625 while (infoElement != null) { 626 Stamp result = unary.foldStamp(infoElement.getStamp()); 627 if (result != null) { 628 return Pair.create(infoElement, result); 629 } 630 infoElement = nextElement(infoElement); 631 } 632 } else if (node instanceof BinaryNode) { 633 BinaryNode binary = (BinaryNode) node; 634 ValueNode y = binary.getY(); 635 ValueNode x = binary.getX(); 636 if (y.isConstant()) { 637 InfoElement infoElement = getInfoElements(x); 638 while (infoElement != null) { 639 Stamp result = binary.foldStamp(infoElement.stamp, y.stamp(NodeView.DEFAULT)); 640 if (result != null) { 641 return Pair.create(infoElement, result); 642 } 643 infoElement = nextElement(infoElement); 644 } 645 } 646 } 647 return null; 648 } 649 650 /** 651 * Get the stamp that may be used for the value for which we are registering the condition. 652 * We may directly use the stamp here without restriction, because any later lookup of the 653 * registered info elements is in the same chain of pi nodes. 654 */ getSafeStamp(ValueNode x)655 private static Stamp getSafeStamp(ValueNode x) { 656 return x.stamp(NodeView.DEFAULT); 657 } 658 659 /** 660 * We can only use the stamp of a second value involved in the condition if we are sure that 661 * we are not implicitly creating a dependency on a pi node that is responsible for that 662 * stamp. For now, we are conservatively only using the stamps of constants. Under certain 663 * circumstances, we may also be able to use the stamp of the value after skipping pi nodes 664 * (e.g., the stamp of a parameter after inlining, or the stamp of a fixed node that can 665 * never be replaced with a pi node via canonicalization). 666 */ getOtherSafeStamp(ValueNode x)667 private static Stamp getOtherSafeStamp(ValueNode x) { 668 if (x.isConstant() || x.graph().isAfterFixedReadPhase()) { 669 return x.stamp(NodeView.DEFAULT); 670 } 671 return x.stamp(NodeView.DEFAULT).unrestricted(); 672 } 673 674 /** 675 * Recursively try to fold stamps within this expression using information from 676 * {@link #getInfoElements(ValueNode)}. It's only safe to use constants and one 677 * {@link InfoElement} otherwise more than one guard would be required. 678 * 679 * @param node 680 * @return the pair of the @{link InfoElement} used and the stamp produced for the whole 681 * expression 682 */ recursiveFoldStampFromInfo(Node node)683 Pair<InfoElement, Stamp> recursiveFoldStampFromInfo(Node node) { 684 return recursiveFoldStamp(node); 685 } 686 687 /** 688 * Look for a preceding guard whose condition is implied by {@code thisGuard}. If we find 689 * one, try to move this guard just above that preceding guard so that we can fold it: 690 * 691 * <pre> 692 * guard(C1); // preceding guard 693 * ... 694 * guard(C2); // thisGuard 695 * </pre> 696 * 697 * If C2 => C1, transform to: 698 * 699 * <pre> 700 * guard(C2); 701 * ... 702 * </pre> 703 */ foldPendingTest(DeoptimizingGuard thisGuard, ValueNode original, Stamp newStamp, GuardRewirer rewireGuardFunction)704 protected boolean foldPendingTest(DeoptimizingGuard thisGuard, ValueNode original, Stamp newStamp, GuardRewirer rewireGuardFunction) { 705 for (DeoptimizingGuard pendingGuard : pendingTests) { 706 LogicNode pendingCondition = pendingGuard.getCondition(); 707 TriState result = TriState.UNKNOWN; 708 if (pendingCondition instanceof UnaryOpLogicNode) { 709 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) pendingCondition; 710 if (unaryLogicNode.getValue() == original) { 711 result = unaryLogicNode.tryFold(newStamp); 712 } 713 } else if (pendingCondition instanceof BinaryOpLogicNode) { 714 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) pendingCondition; 715 ValueNode x = binaryOpLogicNode.getX(); 716 ValueNode y = binaryOpLogicNode.getY(); 717 if (x == original) { 718 result = binaryOpLogicNode.tryFold(newStamp, getOtherSafeStamp(y)); 719 } else if (y == original) { 720 result = binaryOpLogicNode.tryFold(getOtherSafeStamp(x), newStamp); 721 } else if (binaryOpLogicNode instanceof IntegerEqualsNode && y.isConstant() && x instanceof AndNode) { 722 AndNode and = (AndNode) x; 723 if (and.getY() == y && and.getX() == original) { 724 BinaryOp<And> andOp = ArithmeticOpTable.forStamp(newStamp).getAnd(); 725 result = binaryOpLogicNode.tryFold(andOp.foldStamp(newStamp, getOtherSafeStamp(y)), getOtherSafeStamp(y)); 726 } 727 } 728 } 729 if (result.isKnown()) { 730 /* 731 * The test case be folded using the information available but the test can only 732 * be moved up if we're sure there's no schedule dependence. 733 */ 734 if (canScheduleAbove(thisGuard.getCondition(), pendingGuard.asNode(), original) && foldGuard(thisGuard, pendingGuard, result.toBoolean(), newStamp, rewireGuardFunction)) { 735 return true; 736 } 737 } 738 } 739 return false; 740 } 741 canScheduleAbove(Node n, Node target, ValueNode knownToBeAbove)742 private boolean canScheduleAbove(Node n, Node target, ValueNode knownToBeAbove) { 743 Block targetBlock = nodeToBlock.get(target); 744 Block testBlock = nodeToBlock.get(n); 745 if (targetBlock != null && testBlock != null) { 746 if (targetBlock == testBlock) { 747 for (Node fixed : blockToNodes.get(targetBlock)) { 748 if (fixed == n) { 749 return true; 750 } else if (fixed == target) { 751 break; 752 } 753 } 754 } else if (AbstractControlFlowGraph.dominates(testBlock, targetBlock)) { 755 return true; 756 } 757 } 758 InputFilter v = new InputFilter(knownToBeAbove); 759 n.applyInputs(v); 760 return v.ok; 761 } 762 foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, boolean outcome, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction)763 protected boolean foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, boolean outcome, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) { 764 DeoptimizationAction action = mergeActions(otherGuard.getAction(), thisGuard.getAction()); 765 if (action != null && otherGuard.getSpeculation() == thisGuard.getSpeculation()) { 766 LogicNode condition = (LogicNode) thisGuard.getCondition().copyWithInputs(); 767 /* 768 * We have ...; guard(C1); guard(C2);... 769 * 770 * Where the first guard is `otherGuard` and the second one `thisGuard`. 771 * 772 * Depending on `outcome`, we have C2 => C1 or C2 => !C1. 773 * 774 * - If C2 => C1, `mustDeopt` below is false and we transform to ...; guard(C2); ... 775 * 776 * - If C2 => !C1, `mustDeopt` is true and we transform to ..; guard(C1); deopt; 777 */ 778 // for the second case, the action of the deopt is copied from there: 779 thisGuard.setAction(action); 780 GuardRewirer rewirer = (guard, result, innerGuardedValueStamp, newInput) -> { 781 // `result` is `outcome`, `guard` is `otherGuard` 782 boolean mustDeopt = result == otherGuard.isNegated(); 783 if (rewireGuardFunction.rewire(guard, mustDeopt == thisGuard.isNegated(), innerGuardedValueStamp, newInput)) { 784 if (!mustDeopt) { 785 otherGuard.setCondition(condition, thisGuard.isNegated()); 786 otherGuard.setAction(action); 787 otherGuard.setReason(thisGuard.getReason()); 788 } 789 return true; 790 } 791 condition.safeDelete(); 792 return false; 793 }; 794 // Move the later test up 795 return rewireGuards(otherGuard, outcome, null, guardedValueStamp, rewirer); 796 } 797 return false; 798 } 799 registerCondition(LogicNode condition, boolean negated, GuardingNode guard)800 protected void registerCondition(LogicNode condition, boolean negated, GuardingNode guard) { 801 if (condition.hasMoreThanOneUsage()) { 802 registerNewStamp(condition, negated ? StampFactory.contradiction() : StampFactory.tautology(), guard); 803 } 804 conditions.push(new GuardedCondition(guard, condition, negated)); 805 } 806 getInfoElements(ValueNode proxiedValue)807 protected InfoElement getInfoElements(ValueNode proxiedValue) { 808 if (proxiedValue == null) { 809 return null; 810 } 811 InfoElement infoElement = map.getAndGrow(proxiedValue); 812 if (infoElement == null) { 813 infoElement = map.getAndGrow(GraphUtil.skipPi(proxiedValue)); 814 } 815 return infoElement; 816 } 817 rewireGuards(GuardingNode guard, boolean result, ValueNode proxifiedInput, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction)818 protected boolean rewireGuards(GuardingNode guard, boolean result, ValueNode proxifiedInput, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) { 819 counterStampsFound.increment(debug); 820 return rewireGuardFunction.rewire(guard, result, guardedValueStamp, proxifiedInput); 821 } 822 tryProveCondition(LogicNode node, GuardRewirer rewireGuardFunction)823 protected boolean tryProveCondition(LogicNode node, GuardRewirer rewireGuardFunction) { 824 return tryProveGuardCondition(null, node, rewireGuardFunction); 825 } 826 nextElement(InfoElement current)827 private InfoElement nextElement(InfoElement current) { 828 InfoElement parent = current.getParent(); 829 if (parent != null) { 830 return parent; 831 } else { 832 ValueNode proxifiedInput = current.getProxifiedInput(); 833 if (proxifiedInput instanceof PiNode) { 834 PiNode piNode = (PiNode) proxifiedInput; 835 return getInfoElements(piNode.getOriginalNode()); 836 } 837 } 838 return null; 839 } 840 tryProveGuardCondition(DeoptimizingGuard thisGuard, LogicNode node, GuardRewirer rewireGuardFunction)841 protected boolean tryProveGuardCondition(DeoptimizingGuard thisGuard, LogicNode node, GuardRewirer rewireGuardFunction) { 842 InfoElement infoElement = getInfoElements(node); 843 while (infoElement != null) { 844 Stamp stamp = infoElement.getStamp(); 845 JavaConstant constant = (JavaConstant) stamp.asConstant(); 846 if (constant != null) { 847 // No proxified input and stamp required. 848 return rewireGuards(infoElement.getGuard(), constant.asBoolean(), null, null, rewireGuardFunction); 849 } 850 infoElement = nextElement(infoElement); 851 } 852 853 for (GuardedCondition guardedCondition : this.conditions) { 854 TriState result = guardedCondition.getCondition().implies(guardedCondition.isNegated(), node); 855 if (result.isKnown()) { 856 return rewireGuards(guardedCondition.guard, result.toBoolean(), null, null, rewireGuardFunction); 857 } 858 } 859 860 if (node instanceof UnaryOpLogicNode) { 861 UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) node; 862 ValueNode value = unaryLogicNode.getValue(); 863 infoElement = getInfoElements(value); 864 while (infoElement != null) { 865 Stamp stamp = infoElement.getStamp(); 866 TriState result = unaryLogicNode.tryFold(stamp); 867 if (result.isKnown()) { 868 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction); 869 } 870 infoElement = nextElement(infoElement); 871 } 872 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(value); 873 if (foldResult != null) { 874 TriState result = unaryLogicNode.tryFold(foldResult.getRight()); 875 if (result.isKnown()) { 876 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction); 877 } 878 } 879 if (thisGuard != null) { 880 Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(thisGuard.isNegated()); 881 if (newStamp != null && foldPendingTest(thisGuard, value, newStamp, rewireGuardFunction)) { 882 return true; 883 } 884 885 } 886 } else if (node instanceof BinaryOpLogicNode) { 887 BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) node; 888 ValueNode x = binaryOpLogicNode.getX(); 889 ValueNode y = binaryOpLogicNode.getY(); 890 infoElement = getInfoElements(x); 891 while (infoElement != null) { 892 TriState result = binaryOpLogicNode.tryFold(infoElement.getStamp(), y.stamp(NodeView.DEFAULT)); 893 if (result.isKnown()) { 894 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction); 895 } 896 infoElement = nextElement(infoElement); 897 } 898 899 if (y.isConstant()) { 900 Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(x); 901 if (foldResult != null) { 902 TriState result = binaryOpLogicNode.tryFold(foldResult.getRight(), y.stamp(NodeView.DEFAULT)); 903 if (result.isKnown()) { 904 return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction); 905 } 906 } 907 } else { 908 infoElement = getInfoElements(y); 909 while (infoElement != null) { 910 TriState result = binaryOpLogicNode.tryFold(x.stamp(NodeView.DEFAULT), infoElement.getStamp()); 911 if (result.isKnown()) { 912 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction); 913 } 914 infoElement = nextElement(infoElement); 915 } 916 } 917 918 /* 919 * For complex expressions involving constants, see if it's possible to fold the 920 * tests by using stamps one level up in the expression. For instance, (x + n < y) 921 * might fold if something is known about x and all other values are constants. The 922 * reason for the constant restriction is that if more than 1 real value is involved 923 * the code might need to adopt multiple guards to have proper dependences. 924 */ 925 if (x instanceof BinaryArithmeticNode<?> && y.isConstant()) { 926 BinaryArithmeticNode<?> binary = (BinaryArithmeticNode<?>) x; 927 if (binary.getY().isConstant()) { 928 infoElement = getInfoElements(binary.getX()); 929 while (infoElement != null) { 930 Stamp newStampX = binary.foldStamp(infoElement.getStamp(), binary.getY().stamp(NodeView.DEFAULT)); 931 TriState result = binaryOpLogicNode.tryFold(newStampX, y.stamp(NodeView.DEFAULT)); 932 if (result.isKnown()) { 933 return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), newStampX, rewireGuardFunction); 934 } 935 infoElement = nextElement(infoElement); 936 } 937 } 938 } 939 940 if (thisGuard != null && binaryOpLogicNode instanceof IntegerEqualsNode && !thisGuard.isNegated()) { 941 if (y.isConstant() && x instanceof AndNode) { 942 AndNode and = (AndNode) x; 943 if (and.getY() == y) { 944 /* 945 * This 'and' proves something about some of the bits in and.getX(). 946 * It's equivalent to or'ing in the mask value since those values are 947 * known to be set. 948 */ 949 BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp(NodeView.DEFAULT)).getOr(); 950 IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(and.getX()), getOtherSafeStamp(y)); 951 if (foldPendingTest(thisGuard, and.getX(), newStampX, rewireGuardFunction)) { 952 return true; 953 } 954 } 955 } 956 } 957 958 if (thisGuard != null) { 959 if (!x.isConstant()) { 960 Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(thisGuard.isNegated(), getSafeStamp(x), getOtherSafeStamp(y)); 961 if (newStampX != null && foldPendingTest(thisGuard, x, newStampX, rewireGuardFunction)) { 962 return true; 963 } 964 } 965 if (!y.isConstant()) { 966 Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(thisGuard.isNegated(), getOtherSafeStamp(x), getSafeStamp(y)); 967 if (newStampY != null && foldPendingTest(thisGuard, y, newStampY, rewireGuardFunction)) { 968 return true; 969 } 970 } 971 } 972 } else if (node instanceof ShortCircuitOrNode) { 973 final ShortCircuitOrNode shortCircuitOrNode = (ShortCircuitOrNode) node; 974 return tryProveCondition(shortCircuitOrNode.getX(), (guard, result, guardedValueStamp, newInput) -> { 975 if (result == !shortCircuitOrNode.isXNegated()) { 976 return rewireGuards(guard, true, newInput, guardedValueStamp, rewireGuardFunction); 977 } else { 978 return tryProveCondition(shortCircuitOrNode.getY(), (innerGuard, innerResult, innerGuardedValueStamp, innerNewInput) -> { 979 ValueNode proxifiedInput = newInput; 980 if (proxifiedInput == null) { 981 proxifiedInput = innerNewInput; 982 } else if (innerNewInput != null) { 983 if (innerNewInput != newInput) { 984 // Cannot canonicalize due to different proxied inputs. 985 return false; 986 } 987 } 988 // Can only canonicalize if the guards are equal. 989 if (innerGuard == guard) { 990 return rewireGuards(guard, innerResult ^ shortCircuitOrNode.isYNegated(), proxifiedInput, guardedValueStamp, rewireGuardFunction); 991 } 992 return false; 993 }); 994 } 995 }); 996 } 997 998 return false; 999 } 1000 1001 protected void registerNewStamp(ValueNode maybeProxiedValue, Stamp newStamp, GuardingNode guard) { 1002 registerNewStamp(maybeProxiedValue, newStamp, guard, false); 1003 } 1004 1005 protected void registerNewStamp(ValueNode maybeProxiedValue, Stamp newStamp, GuardingNode guard, boolean propagateThroughPis) { 1006 assert maybeProxiedValue != null; 1007 assert guard != null; 1008 1009 if (newStamp == null || newStamp.isUnrestricted()) { 1010 return; 1011 } 1012 1013 ValueNode value = maybeProxiedValue; 1014 Stamp stamp = newStamp; 1015 1016 while (stamp != null && value != null) { 1017 ValueNode proxiedValue = null; 1018 if (value instanceof PiNode) { 1019 proxiedValue = value; 1020 } 1021 counterStampsRegistered.increment(debug); 1022 debug.log("\t Saving stamp for node %s stamp %s guarded by %s", value, stamp, guard); 1023 assert value instanceof LogicNode || stamp.isCompatible(value.stamp(NodeView.DEFAULT)) : stamp + " vs. " + value.stamp(NodeView.DEFAULT) + " (" + value + ")"; 1024 map.setAndGrow(value, new InfoElement(stamp, guard, proxiedValue, map.getAndGrow(value))); 1025 undoOperations.push(value); 1026 if (propagateThroughPis && value instanceof PiNode) { 1027 PiNode piNode = (PiNode) value; 1028 value = piNode.getOriginalNode(); 1029 } else if (value instanceof StampInverter) { 1030 StampInverter stampInverter = (StampInverter) value; 1031 value = stampInverter.getValue(); 1032 stamp = stampInverter.invertStamp(stamp); 1033 } else { 1034 break; 1035 } 1036 } 1037 } 1038 1039 protected void processAbstractBegin(AbstractBeginNode beginNode) { 1040 Node predecessor = beginNode.predecessor(); 1041 if (predecessor instanceof IfNode) { 1042 IfNode ifNode = (IfNode) predecessor; 1043 boolean negated = (ifNode.falseSuccessor() == beginNode); 1044 LogicNode condition = ifNode.condition(); 1045 registerNewCondition(condition, negated, beginNode); 1046 } else if (predecessor instanceof TypeSwitchNode) { 1047 TypeSwitchNode typeSwitch = (TypeSwitchNode) predecessor; 1048 processTypeSwitch(beginNode, typeSwitch); 1049 } else if (predecessor instanceof IntegerSwitchNode) { 1050 IntegerSwitchNode integerSwitchNode = (IntegerSwitchNode) predecessor; 1051 processIntegerSwitch(beginNode, integerSwitchNode); 1052 } 1053 } 1054 1055 private static boolean maybeMultipleUsages(ValueNode value) { 1056 if (value.hasMoreThanOneUsage()) { 1057 return true; 1058 } else { 1059 return value instanceof ProxyNode || 1060 value instanceof PiNode || 1061 value instanceof StampInverter; 1062 } 1063 } 1064 1065 protected void processIntegerSwitch(AbstractBeginNode beginNode, IntegerSwitchNode integerSwitchNode) { 1066 ValueNode value = integerSwitchNode.value(); 1067 if (maybeMultipleUsages(value)) { 1068 Stamp stamp = integerSwitchNode.getValueStampForSuccessor(beginNode); 1069 if (stamp != null) { 1070 registerNewStamp(value, stamp, beginNode); 1071 } 1072 } 1073 } 1074 1075 protected void processTypeSwitch(AbstractBeginNode beginNode, TypeSwitchNode typeSwitch) { 1076 ValueNode hub = typeSwitch.value(); 1077 if (hub instanceof LoadHubNode) { 1078 LoadHubNode loadHub = (LoadHubNode) hub; 1079 ValueNode value = loadHub.getValue(); 1080 if (maybeMultipleUsages(value)) { 1081 Stamp stamp = typeSwitch.getValueStampForSuccessor(beginNode); 1082 if (stamp != null) { 1083 registerNewStamp(value, stamp, beginNode); 1084 } 1085 } 1086 } 1087 } 1088 1089 @Override 1090 public void exit(Block b, Marks marks) { 1091 int infoElementsMark = marks.infoElementOperations; 1092 while (undoOperations.size() > infoElementsMark) { 1093 Node node = undoOperations.pop(); 1094 if (node.isAlive()) { 1095 map.set(node, map.get(node).getParent()); 1096 } 1097 } 1098 1099 int conditionsMark = marks.conditions; 1100 while (conditions.size() > conditionsMark) { 1101 conditions.pop(); 1102 } 1103 } 1104 } 1105 1106 @FunctionalInterface 1107 protected interface InfoElementProvider { 1108 Iterable<InfoElement> getInfoElements(ValueNode value); 1109 } 1110 1111 /** 1112 * Checks for safe nodes when moving pending tests up. 1113 */ 1114 static class InputFilter extends Node.EdgeVisitor { 1115 boolean ok; 1116 private ValueNode value; 1117 1118 InputFilter(ValueNode value) { 1119 this.value = value; 1120 this.ok = true; 1121 } 1122 1123 @Override 1124 public Node apply(Node node, Node curNode) { 1125 if (!ok) { 1126 // Abort the recursion 1127 return curNode; 1128 } 1129 if (!(curNode instanceof ValueNode)) { 1130 ok = false; 1131 return curNode; 1132 } 1133 ValueNode curValue = (ValueNode) curNode; 1134 if (curValue.isConstant() || curValue == value || curValue instanceof ParameterNode) { 1135 return curNode; 1136 } 1137 if (curValue instanceof BinaryNode || curValue instanceof UnaryNode) { 1138 curValue.applyInputs(this); 1139 } else { 1140 ok = false; 1141 } 1142 return curNode; 1143 } 1144 } 1145 1146 @FunctionalInterface 1147 protected interface GuardRewirer { 1148 /** 1149 * Called if the condition could be proven to have a constant value ({@code result}) under 1150 * {@code guard}. 1151 * 1152 * @param guard the guard whose result is proven 1153 * @param result the known result of the guard 1154 * @param newInput new input to pi nodes depending on the new guard 1155 * @return whether the transformation could be applied 1156 */ 1157 boolean rewire(GuardingNode guard, boolean result, Stamp guardedValueStamp, ValueNode newInput); 1158 } 1159 1160 protected static final class InfoElement { 1161 private final Stamp stamp; 1162 private final GuardingNode guard; 1163 private final ValueNode proxifiedInput; 1164 private final InfoElement parent; 1165 1166 public InfoElement(Stamp stamp, GuardingNode guard, ValueNode proxifiedInput, InfoElement parent) { 1167 this.stamp = stamp; 1168 this.guard = guard; 1169 this.proxifiedInput = proxifiedInput; 1170 this.parent = parent; 1171 } 1172 1173 public InfoElement getParent() { 1174 return parent; 1175 } 1176 1177 public Stamp getStamp() { 1178 return stamp; 1179 } 1180 1181 public GuardingNode getGuard() { 1182 return guard; 1183 } 1184 1185 public ValueNode getProxifiedInput() { 1186 return proxifiedInput; 1187 } 1188 1189 @Override 1190 public String toString() { 1191 return stamp + " -> " + guard; 1192 } 1193 } 1194 1195 @Override 1196 public float codeSizeIncrease() { 1197 return 1.5f; 1198 } 1199 } 1200