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 */ 23package org.graalvm.compiler.virtual.phases.ea; 24 25import java.util.ArrayList; 26import java.util.List; 27 28import org.graalvm.compiler.core.common.cfg.BlockMap; 29import org.graalvm.compiler.core.common.cfg.Loop; 30import org.graalvm.compiler.core.common.type.Stamp; 31import org.graalvm.compiler.debug.DebugContext; 32import org.graalvm.compiler.debug.GraalError; 33import org.graalvm.compiler.debug.Indent; 34import org.graalvm.compiler.graph.Node; 35import org.graalvm.compiler.graph.NodeBitMap; 36import org.graalvm.compiler.graph.NodeMap; 37import org.graalvm.compiler.graph.iterators.NodeIterable; 38import org.graalvm.compiler.nodes.AbstractMergeNode; 39import org.graalvm.compiler.nodes.FixedWithNextNode; 40import org.graalvm.compiler.nodes.IfNode; 41import org.graalvm.compiler.nodes.LogicConstantNode; 42import org.graalvm.compiler.nodes.LogicNode; 43import org.graalvm.compiler.nodes.LoopBeginNode; 44import org.graalvm.compiler.nodes.LoopExitNode; 45import org.graalvm.compiler.nodes.PhiNode; 46import org.graalvm.compiler.nodes.ProxyNode; 47import org.graalvm.compiler.nodes.StructuredGraph; 48import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult; 49import org.graalvm.compiler.nodes.ValueNode; 50import org.graalvm.compiler.nodes.ValuePhiNode; 51import org.graalvm.compiler.nodes.cfg.Block; 52import org.graalvm.compiler.nodes.cfg.ControlFlowGraph; 53import org.graalvm.compiler.nodes.extended.BoxNode; 54import org.graalvm.compiler.nodes.util.GraphUtil; 55import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode; 56import org.graalvm.compiler.nodes.virtual.CommitAllocationNode; 57import org.graalvm.compiler.nodes.virtual.VirtualObjectNode; 58import org.graalvm.compiler.options.OptionValues; 59import org.graalvm.compiler.phases.graph.ReentrantBlockIterator; 60import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.BlockIteratorClosure; 61import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.LoopInfo; 62import org.graalvm.util.EconomicMap; 63import org.graalvm.util.EconomicSet; 64import org.graalvm.util.Equivalence; 65import org.graalvm.word.LocationIdentity; 66 67public abstract class EffectsClosure<BlockT extends EffectsBlockState<BlockT>> extends EffectsPhase.Closure<BlockT> { 68 69 protected final ControlFlowGraph cfg; 70 protected final ScheduleResult schedule; 71 72 /** 73 * If a node has an alias, this means that it was replaced with another node during analysis. 74 * Nodes can be replaced by normal ("scalar") nodes, e.g., a LoadIndexedNode with a 75 * ConstantNode, or by virtual nodes, e.g., a NewInstanceNode with a VirtualInstanceNode. A node 76 * was replaced with a virtual value iff the alias is a subclass of VirtualObjectNode. 77 * 78 * This alias map exists only once and is not part of the block state, so that during iterative 79 * loop processing the alias of a node may be changed to another value. 80 */ 81 protected final NodeMap<ValueNode> aliases; 82 83 /** 84 * This set allows for a quick check whether a node has inputs that were replaced with "scalar" 85 * values. 86 */ 87 private final NodeBitMap hasScalarReplacedInputs; 88 89 /* 90 * TODO: if it was possible to introduce your own subclasses of Block and Loop, these maps would 91 * not be necessary. We could merge the GraphEffectsList logic into them. 92 */ 93 94 /** 95 * The effects accumulated during analysis of nodes. They may be cleared and re-filled during 96 * iterative loop processing. 97 */ 98 protected final BlockMap<GraphEffectList> blockEffects; 99 100 /** 101 * Effects that can only be applied after the effects from within the loop have been applied and 102 * that must be applied before any effect from after the loop is applied. E.g., updating phis. 103 */ 104 protected final EconomicMap<Loop<Block>, GraphEffectList> loopMergeEffects = EconomicMap.create(Equivalence.IDENTITY); 105 106 /** 107 * The entry state of loops is needed when loop proxies are processed. 108 */ 109 private final EconomicMap<LoopBeginNode, BlockT> loopEntryStates = EconomicMap.create(Equivalence.IDENTITY); 110 111 // Intended to be used by read-eliminating phases based on the effects phase. 112 protected final EconomicMap<Loop<Block>, LoopKillCache> loopLocationKillCache = EconomicMap.create(Equivalence.IDENTITY); 113 114 protected boolean changed; 115 protected final DebugContext debug; 116 117 public EffectsClosure(ScheduleResult schedule, ControlFlowGraph cfg) { 118 this.schedule = schedule; 119 this.cfg = cfg; 120 this.aliases = cfg.graph.createNodeMap(); 121 this.hasScalarReplacedInputs = cfg.graph.createNodeBitMap(); 122 this.blockEffects = new BlockMap<>(cfg); 123 this.debug = cfg.graph.getDebug(); 124 for (Block block : cfg.getBlocks()) { 125 blockEffects.put(block, new GraphEffectList(debug)); 126 } 127 } 128 129 @Override 130 public boolean hasChanged() { 131 return changed; 132 } 133 134 @Override 135 public boolean needsApplyEffects() { 136 return true; 137 } 138 139 @Override 140 public void applyEffects() { 141 final StructuredGraph graph = cfg.graph; 142 final ArrayList<Node> obsoleteNodes = new ArrayList<>(0); 143 final ArrayList<GraphEffectList> effectList = new ArrayList<>(); 144 /* 145 * Effects are applied during a ordered iteration over the blocks to apply them in the 146 * correct order, e.g., apply the effect that adds a node to the graph before the node is 147 * used. 148 */ 149 BlockIteratorClosure<Void> closure = new BlockIteratorClosure<Void>() { 150 151 @Override 152 protected Void getInitialState() { 153 return null; 154 } 155 156 private void apply(GraphEffectList effects) { 157 if (effects != null && !effects.isEmpty()) { 158 effectList.add(effects); 159 } 160 } 161 162 @Override 163 protected Void processBlock(Block block, Void currentState) { 164 apply(blockEffects.get(block)); 165 return currentState; 166 } 167 168 @Override 169 protected Void merge(Block merge, List<Void> states) { 170 return null; 171 } 172 173 @Override 174 protected Void cloneState(Void oldState) { 175 return oldState; 176 } 177 178 @Override 179 protected List<Void> processLoop(Loop<Block> loop, Void initialState) { 180 LoopInfo<Void> info = ReentrantBlockIterator.processLoop(this, loop, initialState); 181 apply(loopMergeEffects.get(loop)); 182 return info.exitStates; 183 } 184 }; 185 ReentrantBlockIterator.apply(closure, cfg.getStartBlock()); 186 for (GraphEffectList effects : effectList) { 187 debug.log(" ==== effects"); 188 effects.apply(graph, obsoleteNodes, false); 189 } 190 /* 191 * Effects that modify the cfg (e.g., removing a branch for an if that got a constant 192 * condition) need to be performed after all other effects, because they change phi value 193 * indexes. 194 */ 195 for (GraphEffectList effects : effectList) { 196 debug.log(" ==== cfg kill effects"); 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.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") 368 protected BlockT stripKilledLoopLocations(Loop<Block> loop, BlockT initialState) { 369 return initialState; 370 } 371 372 @SuppressWarnings("unused") 373 protected void processKilledLoopLocations(Loop<Block> loop, BlockT initialState, BlockT mergedStates) { 374 // nothing to do 375 } 376 377 @SuppressWarnings("unused") 378 protected void processInitialLoopState(Loop<Block> loop, BlockT initialState) { 379 // nothing to do 380 } 381 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 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 421 protected abstract void processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects); 422 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 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 */ 453 protected abstract void merge(List<BlockT> states); 454 455 private void setNewState(BlockT state) { 456 newState = state; 457 mergeEffects.clear(); 458 afterMergeEffects.clear(); 459 } 460 461 private void setStateIndexes(int[] stateIndexes) { 462 this.stateIndexes = stateIndexes; 463 } 464 465 protected final Block getPredecessor(int index) { 466 return mergeBlock.getPredecessors()[stateIndexes[index]]; 467 } 468 469 protected final NodeIterable<PhiNode> getPhis() { 470 return merge.phis(); 471 } 472 473 protected final ValueNode getPhiValueAt(PhiNode phi, int index) { 474 return phi.valueAt(stateIndexes[index]); 475 } 476 477 protected final ValuePhiNode createValuePhi(Stamp stamp) { 478 return new ValuePhiNode(stamp, merge, new ValueNode[mergeBlock.getPredecessorCount()]); 479 } 480 481 protected final void setPhiInput(PhiNode phi, int index, ValueNode value) { 482 afterMergeEffects.initializePhiInput(phi, stateIndexes[index], value); 483 } 484 485 protected final StructuredGraph graph() { 486 return merge.graph(); 487 } 488 489 @Override 490 public String toString() { 491 return "MergeProcessor@" + merge; 492 } 493 } 494 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 505 protected final boolean hasScalarReplacedInputs(Node node) { 506 return hasScalarReplacedInputs.isMarked(node); 507 } 508 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 524 protected LoopKillCache(int visits) { 525 this.visits = visits; 526 } 527 528 protected void visited() { 529 visits++; 530 } 531 532 protected int visits() { 533 return visits; 534 } 535 536 protected void setKillsAll() { 537 killsAll = true; 538 firstLocation = null; 539 killedLocations = null; 540 } 541 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 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 569 protected boolean loopKillsLocations() { 570 if (killsAll) { 571 return true; 572 } 573 return firstLocation != null; 574 } 575 } 576 577} 578