1 /* 2 * Copyright (c) 2011, 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.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 EffectsClosure(ScheduleResult schedule, ControlFlowGraph cfg)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 hasChanged()132 public boolean hasChanged() { 133 return changed; 134 } 135 136 @Override needsApplyEffects()137 public boolean needsApplyEffects() { 138 return true; 139 } 140 141 @Override applyEffects()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 processBlock(Block block, BlockT state)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 */ isSignificantNode(Node node)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 */ processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode)281 protected abstract boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode); 282 283 @Override merge(Block merge, List<BlockT> states)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") processLoop(Loop<Block> loop, BlockT initialState)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.getExits().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.getExits().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 } 361 } 362 } 363 } 364 throw new GraalError("too many iterations at %s", loop); 365 } 366 367 @SuppressWarnings("unused") stripKilledLoopLocations(Loop<Block> loop, BlockT initialState)368 protected BlockT stripKilledLoopLocations(Loop<Block> loop, BlockT initialState) { 369 return initialState; 370 } 371 372 @SuppressWarnings("unused") processKilledLoopLocations(Loop<Block> loop, BlockT initialState, BlockT mergedStates)373 protected void processKilledLoopLocations(Loop<Block> loop, BlockT initialState, BlockT mergedStates) { 374 // nothing to do 375 } 376 377 @SuppressWarnings("unused") processInitialLoopState(Loop<Block> loop, BlockT initialState)378 protected void processInitialLoopState(Loop<Block> loop, BlockT initialState) { 379 // nothing to do 380 } 381 doMergeWithoutDead(MergeProcessor mergeProcessor, List<BlockT> states)382 private void doMergeWithoutDead(MergeProcessor mergeProcessor, List<BlockT> states) { 383 int alive = 0; 384 for (BlockT state : states) { 385 if (!state.isDead()) { 386 alive++; 387 } 388 } 389 if (alive == 0) { 390 mergeProcessor.setNewState(states.get(0)); 391 } else if (alive == states.size()) { 392 int[] stateIndexes = new int[states.size()]; 393 for (int i = 0; i < stateIndexes.length; i++) { 394 stateIndexes[i] = i; 395 } 396 mergeProcessor.setStateIndexes(stateIndexes); 397 mergeProcessor.setNewState(getInitialState()); 398 mergeProcessor.merge(states); 399 } else { 400 ArrayList<BlockT> aliveStates = new ArrayList<>(alive); 401 int[] stateIndexes = new int[alive]; 402 for (int i = 0; i < states.size(); i++) { 403 if (!states.get(i).isDead()) { 404 stateIndexes[aliveStates.size()] = i; 405 aliveStates.add(states.get(i)); 406 } 407 } 408 mergeProcessor.setStateIndexes(stateIndexes); 409 mergeProcessor.setNewState(getInitialState()); 410 mergeProcessor.merge(aliveStates); 411 } 412 } 413 assertExitStatesNonEmpty(Loop<Block> loop, LoopInfo<BlockT> info)414 private boolean assertExitStatesNonEmpty(Loop<Block> loop, LoopInfo<BlockT> info) { 415 for (int i = 0; i < loop.getExits().size(); i++) { 416 assert info.exitStates.get(i) != null : "no loop exit state at " + loop.getExits().get(i) + " / " + loop.getHeader(); 417 } 418 return true; 419 } 420 processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects)421 protected abstract void processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects); 422 createMergeProcessor(Block merge)423 protected abstract MergeProcessor createMergeProcessor(Block merge); 424 425 /** 426 * The main workhorse for merging states, both for loops and for normal merges. 427 */ 428 protected abstract class MergeProcessor { 429 430 private final Block mergeBlock; 431 private final AbstractMergeNode merge; 432 433 protected final GraphEffectList mergeEffects; 434 protected final GraphEffectList afterMergeEffects; 435 436 /** 437 * The indexes are used to map from an index in the list of active (non-dead) predecessors 438 * to an index in the list of all predecessors (the latter may be larger). 439 */ 440 private int[] stateIndexes; 441 protected BlockT newState; 442 MergeProcessor(Block mergeBlock)443 public MergeProcessor(Block mergeBlock) { 444 this.mergeBlock = mergeBlock; 445 this.merge = (AbstractMergeNode) mergeBlock.getBeginNode(); 446 this.mergeEffects = new GraphEffectList(debug); 447 this.afterMergeEffects = new GraphEffectList(debug); 448 } 449 450 /** 451 * @param states the states that should be merged. 452 */ merge(List<BlockT> states)453 protected abstract void merge(List<BlockT> states); 454 setNewState(BlockT state)455 private void setNewState(BlockT state) { 456 newState = state; 457 mergeEffects.clear(); 458 afterMergeEffects.clear(); 459 } 460 setStateIndexes(int[] stateIndexes)461 private void setStateIndexes(int[] stateIndexes) { 462 this.stateIndexes = stateIndexes; 463 } 464 getPredecessor(int index)465 protected final Block getPredecessor(int index) { 466 return mergeBlock.getPredecessors()[stateIndexes[index]]; 467 } 468 getPhis()469 protected final NodeIterable<PhiNode> getPhis() { 470 return merge.phis(); 471 } 472 getPhiValueAt(PhiNode phi, int index)473 protected final ValueNode getPhiValueAt(PhiNode phi, int index) { 474 return phi.valueAt(stateIndexes[index]); 475 } 476 createValuePhi(Stamp stamp)477 protected final ValuePhiNode createValuePhi(Stamp stamp) { 478 return new ValuePhiNode(stamp, merge, new ValueNode[mergeBlock.getPredecessorCount()]); 479 } 480 setPhiInput(PhiNode phi, int index, ValueNode value)481 protected final void setPhiInput(PhiNode phi, int index, ValueNode value) { 482 afterMergeEffects.initializePhiInput(phi, stateIndexes[index], value); 483 } 484 graph()485 protected final StructuredGraph graph() { 486 return merge.graph(); 487 } 488 489 @Override toString()490 public String toString() { 491 return "MergeProcessor@" + merge; 492 } 493 } 494 addScalarAlias(ValueNode node, ValueNode alias)495 public void addScalarAlias(ValueNode node, ValueNode alias) { 496 assert !(alias instanceof VirtualObjectNode); 497 aliases.set(node, alias); 498 for (Node usage : node.usages()) { 499 if (!hasScalarReplacedInputs.isNew(usage)) { 500 hasScalarReplacedInputs.mark(usage); 501 } 502 } 503 } 504 hasScalarReplacedInputs(Node node)505 protected final boolean hasScalarReplacedInputs(Node node) { 506 return hasScalarReplacedInputs.isMarked(node); 507 } 508 getScalarAlias(ValueNode node)509 public ValueNode getScalarAlias(ValueNode node) { 510 assert !(node instanceof VirtualObjectNode); 511 if (node == null || !node.isAlive() || aliases.isNew(node)) { 512 return node; 513 } 514 ValueNode result = aliases.get(node); 515 return (result == null || result instanceof VirtualObjectNode) ? node : result; 516 } 517 518 protected static final class LoopKillCache { 519 private int visits; 520 private LocationIdentity firstLocation; 521 private EconomicSet<LocationIdentity> killedLocations; 522 private boolean killsAll; 523 LoopKillCache(int visits)524 protected LoopKillCache(int visits) { 525 this.visits = visits; 526 } 527 visited()528 protected void visited() { 529 visits++; 530 } 531 visits()532 protected int visits() { 533 return visits; 534 } 535 setKillsAll()536 protected void setKillsAll() { 537 killsAll = true; 538 firstLocation = null; 539 killedLocations = null; 540 } 541 containsLocation(LocationIdentity locationIdentity)542 protected boolean containsLocation(LocationIdentity locationIdentity) { 543 if (killsAll) { 544 return true; 545 } 546 if (firstLocation == null) { 547 return false; 548 } 549 if (!firstLocation.equals(locationIdentity)) { 550 return killedLocations != null ? killedLocations.contains(locationIdentity) : false; 551 } 552 return true; 553 } 554 rememberLoopKilledLocation(LocationIdentity locationIdentity)555 protected void rememberLoopKilledLocation(LocationIdentity locationIdentity) { 556 if (killsAll) { 557 return; 558 } 559 if (firstLocation == null || firstLocation.equals(locationIdentity)) { 560 firstLocation = locationIdentity; 561 } else { 562 if (killedLocations == null) { 563 killedLocations = EconomicSet.create(Equivalence.IDENTITY); 564 } 565 killedLocations.add(locationIdentity); 566 } 567 } 568 loopKillsLocations()569 protected boolean loopKillsLocations() { 570 if (killsAll) { 571 return true; 572 } 573 return firstLocation != null; 574 } 575 } 576 577 } 578