1 /*
   2  * Copyright (c) 2011, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 
  25 package org.graalvm.compiler.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.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 }