1 /* 2 * Copyright (c) 2011, 2019, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 25 package org.graalvm.compiler.virtual.phases.ea; 26 27 import java.util.ArrayList; 28 import java.util.List; 29 30 import jdk.internal.vm.compiler.collections.EconomicMap; 31 import jdk.internal.vm.compiler.collections.EconomicSet; 32 import jdk.internal.vm.compiler.collections.Equivalence; 33 import org.graalvm.compiler.core.common.cfg.BlockMap; 34 import org.graalvm.compiler.core.common.cfg.Loop; 35 import org.graalvm.compiler.core.common.type.Stamp; 36 import org.graalvm.compiler.debug.DebugContext; 37 import org.graalvm.compiler.debug.GraalError; 38 import org.graalvm.compiler.debug.Indent; 39 import org.graalvm.compiler.graph.Node; 40 import org.graalvm.compiler.graph.NodeBitMap; 41 import org.graalvm.compiler.graph.NodeMap; 42 import org.graalvm.compiler.graph.iterators.NodeIterable; 43 import org.graalvm.compiler.nodes.AbstractMergeNode; 44 import org.graalvm.compiler.nodes.FixedWithNextNode; 45 import org.graalvm.compiler.nodes.IfNode; 46 import org.graalvm.compiler.nodes.LogicConstantNode; 47 import org.graalvm.compiler.nodes.LogicNode; 48 import org.graalvm.compiler.nodes.LoopBeginNode; 49 import org.graalvm.compiler.nodes.LoopExitNode; 50 import org.graalvm.compiler.nodes.PhiNode; 51 import org.graalvm.compiler.nodes.ProxyNode; 52 import org.graalvm.compiler.nodes.StructuredGraph; 53 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult; 54 import org.graalvm.compiler.nodes.ValueNode; 55 import org.graalvm.compiler.nodes.ValuePhiNode; 56 import org.graalvm.compiler.nodes.cfg.Block; 57 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph; 58 import org.graalvm.compiler.nodes.extended.BoxNode; 59 import org.graalvm.compiler.nodes.util.GraphUtil; 60 import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode; 61 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode; 62 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode; 63 import org.graalvm.compiler.options.OptionValues; 64 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator; 65 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.BlockIteratorClosure; 66 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.LoopInfo; 67 import jdk.internal.vm.compiler.word.LocationIdentity; 68 69 public abstract class EffectsClosure<BlockT extends EffectsBlockState<BlockT>> extends EffectsPhase.Closure<BlockT> { 70 71 protected final ControlFlowGraph cfg; 72 protected final ScheduleResult schedule; 73 74 /** 75 * If a node has an alias, this means that it was replaced with another node during analysis. 76 * Nodes can be replaced by normal ("scalar") nodes, e.g., a LoadIndexedNode with a 77 * ConstantNode, or by virtual nodes, e.g., a NewInstanceNode with a VirtualInstanceNode. A node 78 * was replaced with a virtual value iff the alias is a subclass of VirtualObjectNode. 79 * 80 * This alias map exists only once and is not part of the block state, so that during iterative 81 * loop processing the alias of a node may be changed to another value. 82 */ 83 protected final NodeMap<ValueNode> aliases; 84 85 /** 86 * This set allows for a quick check whether a node has inputs that were replaced with "scalar" 87 * values. 88 */ 89 private final NodeBitMap hasScalarReplacedInputs; 90 91 /* 92 * TODO: if it was possible to introduce your own subclasses of Block and Loop, these maps would 93 * not be necessary. We could merge the GraphEffectsList logic into them. 94 */ 95 96 /** 97 * The effects accumulated during analysis of nodes. They may be cleared and re-filled during 98 * iterative loop processing. 99 */ 100 protected final BlockMap<GraphEffectList> blockEffects; 101 102 /** 103 * Effects that can only be applied after the effects from within the loop have been applied and 104 * that must be applied before any effect from after the loop is applied. E.g., updating phis. 105 */ 106 protected final EconomicMap<Loop<Block>, GraphEffectList> loopMergeEffects = EconomicMap.create(Equivalence.IDENTITY); 107 108 /** 109 * The entry state of loops is needed when loop proxies are processed. 110 */ 111 private final EconomicMap<LoopBeginNode, BlockT> loopEntryStates = EconomicMap.create(Equivalence.IDENTITY); 112 113 // Intended to be used by read-eliminating phases based on the effects phase. 114 protected final EconomicMap<Loop<Block>, LoopKillCache> loopLocationKillCache = EconomicMap.create(Equivalence.IDENTITY); 115 116 protected boolean changed; 117 protected final DebugContext debug; 118 119 public EffectsClosure(ScheduleResult schedule, ControlFlowGraph cfg) { 120 this.schedule = schedule; 121 this.cfg = cfg; 122 this.aliases = cfg.graph.createNodeMap(); 123 this.hasScalarReplacedInputs = cfg.graph.createNodeBitMap(); 124 this.blockEffects = new BlockMap<>(cfg); 125 this.debug = cfg.graph.getDebug(); 126 for (Block block : cfg.getBlocks()) { 127 blockEffects.put(block, new GraphEffectList(debug)); 128 } 129 } 130 131 @Override 132 public boolean hasChanged() { 133 return changed; 134 } 135 136 @Override 137 public boolean needsApplyEffects() { 138 return true; 139 } 140 141 @Override 142 public void applyEffects() { 143 final StructuredGraph graph = cfg.graph; 144 final ArrayList<Node> obsoleteNodes = new ArrayList<>(0); 145 final ArrayList<GraphEffectList> effectList = new ArrayList<>(); 146 /* 147 * Effects are applied during a ordered iteration over the blocks to apply them in the 148 * correct order, e.g., apply the effect that adds a node to the graph before the node is 149 * used. 150 */ 151 BlockIteratorClosure<Void> closure = new BlockIteratorClosure<Void>() { 152 153 @Override 154 protected Void getInitialState() { 155 return null; 156 } 157 158 private void apply(GraphEffectList effects) { 159 if (effects != null && !effects.isEmpty()) { 160 effectList.add(effects); 161 } 162 } 163 164 @Override 165 protected Void processBlock(Block block, Void currentState) { 166 apply(blockEffects.get(block)); 167 return currentState; 168 } 169 170 @Override 171 protected Void merge(Block merge, List<Void> states) { 172 return null; 173 } 174 175 @Override 176 protected Void cloneState(Void oldState) { 177 return oldState; 178 } 179 180 @Override 181 protected List<Void> processLoop(Loop<Block> loop, Void initialState) { 182 LoopInfo<Void> info = ReentrantBlockIterator.processLoop(this, loop, initialState); 183 apply(loopMergeEffects.get(loop)); 184 return info.exitStates; 185 } 186 }; 187 ReentrantBlockIterator.apply(closure, cfg.getStartBlock()); 188 for (GraphEffectList effects : effectList) { 189 effects.apply(graph, obsoleteNodes, false); 190 } 191 /* 192 * Effects that modify the cfg (e.g., removing a branch for an if that got a constant 193 * condition) need to be performed after all other effects, because they change phi value 194 * indexes. 195 */ 196 for (GraphEffectList effects : effectList) { 197 effects.apply(graph, obsoleteNodes, true); 198 } 199 debug.dump(DebugContext.DETAILED_LEVEL, graph, "After applying effects"); 200 assert VirtualUtil.assertNonReachable(graph, obsoleteNodes); 201 for (Node node : obsoleteNodes) { 202 if (node.isAlive() && node.hasNoUsages()) { 203 if (node instanceof FixedWithNextNode) { 204 assert ((FixedWithNextNode) node).next() == null; 205 } 206 node.replaceAtUsages(null); 207 GraphUtil.killWithUnusedFloatingInputs(node); 208 } 209 } 210 } 211 212 @Override 213 protected BlockT processBlock(Block block, BlockT state) { 214 if (!state.isDead()) { 215 GraphEffectList effects = blockEffects.get(block); 216 217 /* 218 * If we enter an if branch that is known to be unreachable, we mark it as dead and 219 * cease to do any more analysis on it. At merges, these dead branches will be ignored. 220 */ 221 if (block.getBeginNode().predecessor() instanceof IfNode) { 222 IfNode ifNode = (IfNode) block.getBeginNode().predecessor(); 223 LogicNode condition = ifNode.condition(); 224 Node alias = getScalarAlias(condition); 225 if (alias instanceof LogicConstantNode) { 226 LogicConstantNode constant = (LogicConstantNode) alias; 227 boolean isTrueSuccessor = block.getBeginNode() == ifNode.trueSuccessor(); 228 229 if (constant.getValue() != isTrueSuccessor) { 230 state.markAsDead(); 231 effects.killIfBranch(ifNode, constant.getValue()); 232 return state; 233 } 234 } 235 } 236 237 OptionValues options = block.getBeginNode().getOptions(); 238 VirtualUtil.trace(options, debug, "\nBlock: %s, preds: %s, succ: %s (", block, block.getPredecessors(), block.getSuccessors()); 239 240 // a lastFixedNode is needed in case we want to insert fixed nodes 241 FixedWithNextNode lastFixedNode = null; 242 Iterable<? extends Node> nodes = schedule != null ? schedule.getBlockToNodesMap().get(block) : block.getNodes(); 243 for (Node node : nodes) { 244 // reset the aliases (may be non-null due to iterative loop processing) 245 aliases.set(node, null); 246 if (node instanceof LoopExitNode) { 247 LoopExitNode loopExit = (LoopExitNode) node; 248 for (ProxyNode proxy : loopExit.proxies()) { 249 aliases.set(proxy, null); 250 changed |= processNode(proxy, state, effects, lastFixedNode) && isSignificantNode(node); 251 } 252 processLoopExit(loopExit, loopEntryStates.get(loopExit.loopBegin()), state, blockEffects.get(block)); 253 } 254 changed |= processNode(node, state, effects, lastFixedNode) && isSignificantNode(node); 255 if (node instanceof FixedWithNextNode) { 256 lastFixedNode = (FixedWithNextNode) node; 257 } 258 if (state.isDead()) { 259 break; 260 } 261 } 262 VirtualUtil.trace(options, debug, ")\n end state: %s\n", state); 263 } 264 return state; 265 } 266 267 /** 268 * Changes to {@link CommitAllocationNode}s, {@link AllocatedObjectNode}s and {@link BoxNode}s 269 * are not considered to be "important". If only changes to those nodes are discovered during 270 * analysis, the effects need not be applied. 271 */ 272 private static boolean isSignificantNode(Node node) { 273 return !(node instanceof CommitAllocationNode || node instanceof AllocatedObjectNode || node instanceof BoxNode); 274 } 275 276 /** 277 * Collects the effects of virtualizing the given node. 278 * 279 * @return {@code true} if the effects include removing the node, {@code false} otherwise. 280 */ 281 protected abstract boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode); 282 283 @Override 284 protected BlockT merge(Block merge, List<BlockT> states) { 285 assert blockEffects.get(merge).isEmpty(); 286 MergeProcessor processor = createMergeProcessor(merge); 287 doMergeWithoutDead(processor, states); 288 blockEffects.get(merge).addAll(processor.mergeEffects); 289 blockEffects.get(merge).addAll(processor.afterMergeEffects); 290 return processor.newState; 291 } 292 293 @Override 294 @SuppressWarnings("try") 295 protected final List<BlockT> processLoop(Loop<Block> loop, BlockT initialState) { 296 if (initialState.isDead()) { 297 ArrayList<BlockT> states = new ArrayList<>(); 298 for (int i = 0; i < loop.getLoopExits().size(); i++) { 299 states.add(initialState); 300 } 301 return states; 302 } 303 /* 304 * Special case nested loops: To avoid an exponential runtime for nested loops we try to 305 * only process them as little times as possible. 306 * 307 * In the first iteration of an outer most loop we go into the inner most loop(s). We run 308 * the first iteration of the inner most loop and then, if necessary, a second iteration. 309 * 310 * We return from the recursion and finish the first iteration of the outermost loop. If we 311 * have to do a second iteration in the outer most loop we go again into the inner most 312 * loop(s) but this time we already know all states that are killed by the loop so inside 313 * the loop we will only have those changes that propagate from the first iteration of the 314 * outer most loop into the current loop. We strip the initial loop state for the inner most 315 * loops and do the first iteration with the (possible) changes from outer loops. If there 316 * are no changes we only have to do 1 iteration and are done. 317 * 318 */ 319 BlockT initialStateRemovedKilledLocations = stripKilledLoopLocations(loop, cloneState(initialState)); 320 BlockT loopEntryState = initialStateRemovedKilledLocations; 321 BlockT lastMergedState = cloneState(initialStateRemovedKilledLocations); 322 processInitialLoopState(loop, lastMergedState); 323 MergeProcessor mergeProcessor = createMergeProcessor(loop.getHeader()); 324 /* 325 * Iterative loop processing: we take the predecessor state as the loop's starting state, 326 * processing the loop contents, merge the states of all loop ends, and check whether the 327 * resulting state is equal to the starting state. If it is, the loop processing has 328 * finished, if not, another iteration is needed. 329 * 330 * This processing converges because the merge processing always makes the starting state 331 * more generic, e.g., adding phis instead of non-phi values. 332 */ 333 for (int iteration = 0; iteration < 10; iteration++) { 334 try (Indent i = debug.logAndIndent("================== Process Loop Effects Closure: block:%s begin node:%s", loop.getHeader(), loop.getHeader().getBeginNode())) { 335 LoopInfo<BlockT> info = ReentrantBlockIterator.processLoop(this, loop, cloneState(lastMergedState)); 336 337 List<BlockT> states = new ArrayList<>(); 338 states.add(initialStateRemovedKilledLocations); 339 states.addAll(info.endStates); 340 doMergeWithoutDead(mergeProcessor, states); 341 342 debug.log("MergeProcessor New State: %s", mergeProcessor.newState); 343 debug.log("===== vs."); 344 debug.log("Last Merged State: %s", lastMergedState); 345 346 if (mergeProcessor.newState.equivalentTo(lastMergedState)) { 347 blockEffects.get(loop.getHeader()).insertAll(mergeProcessor.mergeEffects, 0); 348 loopMergeEffects.put(loop, mergeProcessor.afterMergeEffects); 349 350 assert info.exitStates.size() == loop.getLoopExits().size(); 351 loopEntryStates.put((LoopBeginNode) loop.getHeader().getBeginNode(), loopEntryState); 352 assert assertExitStatesNonEmpty(loop, info); 353 354 processKilledLoopLocations(loop, initialStateRemovedKilledLocations, mergeProcessor.newState); 355 return info.exitStates; 356 } else { 357 lastMergedState = mergeProcessor.newState; 358 for (Block block : loop.getBlocks()) { 359 blockEffects.get(block).clear(); 360 if (block.isLoopHeader()) { 361 final GraphEffectList loopEffects = loopMergeEffects.get(block.getLoop()); 362 if (loopEffects != null) { 363 loopEffects.clear(); 364 } 365 } 366 } 367 } 368 } 369 } 370 throw new GraalError("too many iterations at %s", loop); 371 } 372 373 @SuppressWarnings("unused") 374 protected BlockT stripKilledLoopLocations(Loop<Block> loop, BlockT initialState) { 375 return initialState; 376 } 377 378 @SuppressWarnings("unused") 379 protected void processKilledLoopLocations(Loop<Block> loop, BlockT initialState, BlockT mergedStates) { 380 // nothing to do 381 } 382 383 @SuppressWarnings("unused") 384 protected void processInitialLoopState(Loop<Block> loop, BlockT initialState) { 385 // nothing to do 386 } 387 388 private void doMergeWithoutDead(MergeProcessor mergeProcessor, List<BlockT> states) { 389 int alive = 0; 390 for (BlockT state : states) { 391 if (!state.isDead()) { 392 alive++; 393 } 394 } 395 if (alive == 0) { 396 mergeProcessor.setNewState(states.get(0)); 397 } else if (alive == states.size()) { 398 int[] stateIndexes = new int[states.size()]; 399 for (int i = 0; i < stateIndexes.length; i++) { 400 stateIndexes[i] = i; 401 } 402 mergeProcessor.setStateIndexes(stateIndexes); 403 mergeProcessor.setNewState(getInitialState()); 404 mergeProcessor.merge(states); 405 } else { 406 ArrayList<BlockT> aliveStates = new ArrayList<>(alive); 407 int[] stateIndexes = new int[alive]; 408 for (int i = 0; i < states.size(); i++) { 409 if (!states.get(i).isDead()) { 410 stateIndexes[aliveStates.size()] = i; 411 aliveStates.add(states.get(i)); 412 } 413 } 414 mergeProcessor.setStateIndexes(stateIndexes); 415 mergeProcessor.setNewState(getInitialState()); 416 mergeProcessor.merge(aliveStates); 417 } 418 } 419 420 private boolean assertExitStatesNonEmpty(Loop<Block> loop, LoopInfo<BlockT> info) { 421 for (int i = 0; i < loop.getLoopExits().size(); i++) { 422 assert info.exitStates.get(i) != null : "no loop exit state at " + loop.getLoopExits().get(i) + " / " + loop.getHeader(); 423 } 424 return true; 425 } 426 427 protected abstract void processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects); 428 429 protected abstract MergeProcessor createMergeProcessor(Block merge); 430 431 /** 432 * The main workhorse for merging states, both for loops and for normal merges. 433 */ 434 protected abstract class MergeProcessor { 435 436 private final Block mergeBlock; 437 protected final AbstractMergeNode merge; 438 439 protected final GraphEffectList mergeEffects; 440 protected final GraphEffectList afterMergeEffects; 441 442 /** 443 * The indexes are used to map from an index in the list of active (non-dead) predecessors 444 * to an index in the list of all predecessors (the latter may be larger). 445 */ 446 private int[] stateIndexes; 447 protected BlockT newState; 448 449 public MergeProcessor(Block mergeBlock) { 450 this.mergeBlock = mergeBlock; 451 this.merge = (AbstractMergeNode) mergeBlock.getBeginNode(); 452 this.mergeEffects = new GraphEffectList(debug); 453 this.afterMergeEffects = new GraphEffectList(debug); 454 } 455 456 /** 457 * @param states the states that should be merged. 458 */ 459 protected abstract void merge(List<BlockT> states); 460 461 private void setNewState(BlockT state) { 462 newState = state; 463 mergeEffects.clear(); 464 afterMergeEffects.clear(); 465 } 466 467 private void setStateIndexes(int[] stateIndexes) { 468 this.stateIndexes = stateIndexes; 469 } 470 471 protected final Block getPredecessor(int index) { 472 return mergeBlock.getPredecessors()[stateIndexes[index]]; 473 } 474 475 protected final NodeIterable<PhiNode> getPhis() { 476 return merge.phis(); 477 } 478 479 protected final ValueNode getPhiValueAt(PhiNode phi, int index) { 480 return phi.valueAt(stateIndexes[index]); 481 } 482 483 protected final ValuePhiNode createValuePhi(Stamp stamp) { 484 return new ValuePhiNode(stamp, merge, new ValueNode[mergeBlock.getPredecessorCount()]); 485 } 486 487 protected final void setPhiInput(PhiNode phi, int index, ValueNode value) { 488 afterMergeEffects.initializePhiInput(phi, stateIndexes[index], value); 489 } 490 491 protected final StructuredGraph graph() { 492 return merge.graph(); 493 } 494 495 @Override 496 public String toString() { 497 return "MergeProcessor@" + merge; 498 } 499 } 500 501 public void addScalarAlias(ValueNode node, ValueNode alias) { 502 assert !(alias instanceof VirtualObjectNode); 503 aliases.set(node, alias); 504 for (Node usage : node.usages()) { 505 if (!hasScalarReplacedInputs.isNew(usage)) { 506 hasScalarReplacedInputs.mark(usage); 507 } 508 } 509 } 510 511 protected final boolean hasScalarReplacedInputs(Node node) { 512 return hasScalarReplacedInputs.isMarked(node); 513 } 514 515 public ValueNode getScalarAlias(ValueNode node) { 516 assert !(node instanceof VirtualObjectNode); 517 if (node == null || !node.isAlive() || aliases.isNew(node)) { 518 return node; 519 } 520 ValueNode result = aliases.get(node); 521 return (result == null || result instanceof VirtualObjectNode) ? node : result; 522 } 523 524 protected static final class LoopKillCache { 525 private int visits; 526 private LocationIdentity firstLocation; 527 private EconomicSet<LocationIdentity> killedLocations; 528 private boolean killsAll; 529 530 protected LoopKillCache(int visits) { 531 this.visits = visits; 532 } 533 534 protected void visited() { 535 visits++; 536 } 537 538 protected int visits() { 539 return visits; 540 } 541 542 protected void setKillsAll() { 543 killsAll = true; 544 firstLocation = null; 545 killedLocations = null; 546 } 547 548 protected boolean containsLocation(LocationIdentity locationIdentity) { 549 if (killsAll) { 550 return true; 551 } 552 if (firstLocation == null) { 553 return false; 554 } 555 if (!firstLocation.equals(locationIdentity)) { 556 return killedLocations != null ? killedLocations.contains(locationIdentity) : false; 557 } 558 return true; 559 } 560 561 protected void rememberLoopKilledLocation(LocationIdentity locationIdentity) { 562 if (killsAll) { 563 return; 564 } 565 if (firstLocation == null || firstLocation.equals(locationIdentity)) { 566 firstLocation = locationIdentity; 567 } else { 568 if (killedLocations == null) { 569 killedLocations = EconomicSet.create(Equivalence.IDENTITY); 570 } 571 killedLocations.add(locationIdentity); 572 } 573 } 574 575 protected boolean loopKillsLocations() { 576 if (killsAll) { 577 return true; 578 } 579 return firstLocation != null; 580 } 581 } 582 583 }