1 /*
   2  * Copyright (c) 2012, 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.loop;
  26 
  27 import java.util.ArrayDeque;
  28 import java.util.Collections;
  29 import java.util.Deque;
  30 import java.util.Iterator;
  31 
  32 import jdk.internal.vm.compiler.collections.EconomicMap;
  33 import org.graalvm.compiler.debug.GraalError;
  34 import org.graalvm.compiler.graph.Graph;
  35 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
  36 import org.graalvm.compiler.graph.Node;
  37 import org.graalvm.compiler.graph.NodeBitMap;
  38 import org.graalvm.compiler.graph.iterators.NodeIterable;
  39 import org.graalvm.compiler.nodes.AbstractBeginNode;
  40 import org.graalvm.compiler.nodes.AbstractMergeNode;
  41 import org.graalvm.compiler.nodes.EndNode;
  42 import org.graalvm.compiler.nodes.FixedNode;
  43 import org.graalvm.compiler.nodes.FrameState;
  44 import org.graalvm.compiler.nodes.GuardNode;
  45 import org.graalvm.compiler.nodes.GuardPhiNode;
  46 import org.graalvm.compiler.nodes.GuardProxyNode;
  47 import org.graalvm.compiler.nodes.Invoke;
  48 import org.graalvm.compiler.nodes.LoopExitNode;
  49 import org.graalvm.compiler.nodes.MergeNode;
  50 import org.graalvm.compiler.nodes.NodeView;
  51 import org.graalvm.compiler.nodes.PhiNode;
  52 import org.graalvm.compiler.nodes.ProxyNode;
  53 import org.graalvm.compiler.nodes.StructuredGraph;
  54 import org.graalvm.compiler.nodes.ValueNode;
  55 import org.graalvm.compiler.nodes.ValuePhiNode;
  56 import org.graalvm.compiler.nodes.ValueProxyNode;
  57 import org.graalvm.compiler.nodes.VirtualState;
  58 import org.graalvm.compiler.nodes.cfg.Block;
  59 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
  60 import org.graalvm.compiler.nodes.java.MonitorEnterNode;
  61 import org.graalvm.compiler.nodes.spi.NodeWithState;
  62 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
  63 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
  64 
  65 import jdk.vm.ci.meta.TriState;
  66 
  67 public abstract class LoopFragment {
  68 
  69     private final LoopEx loop;
  70     private final LoopFragment original;
  71     protected NodeBitMap nodes;
  72     protected boolean nodesReady;
  73     private EconomicMap<Node, Node> duplicationMap;
  74 
  75     public LoopFragment(LoopEx loop) {
  76         this(loop, null);
  77         this.nodesReady = true;
  78     }
  79 
  80     public LoopFragment(LoopEx loop, LoopFragment original) {
  81         this.loop = loop;
  82         this.original = original;
  83         this.nodesReady = false;
  84     }
  85 
  86     /**
  87      * Return the original LoopEx for this fragment. For duplicated fragments this returns null.
  88      */
  89     protected LoopEx loop() {
  90         return loop;
  91     }
  92 
  93     public abstract LoopFragment duplicate();
  94 
  95     public abstract void insertBefore(LoopEx l);
  96 
  97     public void disconnect() {
  98         // TODO (gd) possibly abstract
  99     }
 100 
 101     public boolean contains(Node n) {
 102         return nodes().isMarkedAndGrow(n);
 103     }
 104 
 105     @SuppressWarnings("unchecked")
 106     public <New extends Node, Old extends New> New getDuplicatedNode(Old n) {
 107         assert isDuplicate();
 108         return (New) duplicationMap.get(n);
 109     }
 110 
 111     protected <New extends Node, Old extends New> void putDuplicatedNode(Old oldNode, New newNode) {
 112         duplicationMap.put(oldNode, newNode);
 113     }
 114 
 115     /**
 116      * Gets the corresponding value in this fragment. Should be called on duplicate fragments with a
 117      * node from the original fragment as argument.
 118      *
 119      * @param b original value
 120      * @return corresponding value in the peel
 121      */
 122     protected abstract ValueNode prim(ValueNode b);
 123 
 124     public boolean isDuplicate() {
 125         return original != null;
 126     }
 127 
 128     public LoopFragment original() {
 129         return original;
 130     }
 131 
 132     public abstract NodeBitMap nodes();
 133 
 134     public StructuredGraph graph() {
 135         LoopEx l;
 136         if (isDuplicate()) {
 137             l = original().loop();
 138         } else {
 139             l = loop();
 140         }
 141         return l.loopBegin().graph();
 142     }
 143 
 144     protected abstract DuplicationReplacement getDuplicationReplacement();
 145 
 146     protected abstract void beforeDuplication();
 147 
 148     protected void finishDuplication() {
 149         LoopEx originalLoopEx = original().loop();
 150         ControlFlowGraph cfg = originalLoopEx.loopsData().getCFG();
 151         for (LoopExitNode exit : originalLoopEx.loopBegin().loopExits().snapshot()) {
 152             if (!originalLoopEx.loop().isLoopExit(cfg.blockFor(exit))) {
 153                 // this LoopExitNode is too low, we need to remove it otherwise it will be below
 154                 // merged exits
 155                 exit.removeExit();
 156             }
 157         }
 158 
 159     }
 160 
 161     protected void patchNodes(final DuplicationReplacement dataFix) {
 162         if (isDuplicate() && !nodesReady) {
 163             assert !original.isDuplicate();
 164             final DuplicationReplacement cfgFix = original().getDuplicationReplacement();
 165             DuplicationReplacement dr;
 166             if (cfgFix == null && dataFix != null) {
 167                 dr = dataFix;
 168             } else if (cfgFix != null && dataFix == null) {
 169                 dr = cfgFix;
 170             } else if (cfgFix != null && dataFix != null) {
 171                 dr = new DuplicationReplacement() {
 172 
 173                     @Override
 174                     public Node replacement(Node o) {
 175                         Node r1 = dataFix.replacement(o);
 176                         if (r1 != o) {
 177                             assert cfgFix.replacement(o) == o;
 178                             return r1;
 179                         }
 180                         Node r2 = cfgFix.replacement(o);
 181                         if (r2 != o) {
 182                             return r2;
 183                         }
 184                         return o;
 185                     }
 186                 };
 187             } else {
 188                 dr = null;
 189             }
 190             beforeDuplication();
 191             NodeIterable<Node> nodesIterable = original().nodes();
 192             duplicationMap = graph().addDuplicates(nodesIterable, graph(), nodesIterable.count(), dr);
 193             finishDuplication();
 194             nodes = new NodeBitMap(graph());
 195             nodes.markAll(duplicationMap.getValues());
 196             nodesReady = true;
 197         } else {
 198             // TODO (gd) apply fix ?
 199         }
 200     }
 201 
 202     protected static NodeBitMap computeNodes(Graph graph, Iterable<AbstractBeginNode> blocks) {
 203         return computeNodes(graph, blocks, Collections.emptyList());
 204     }
 205 
 206     protected static NodeBitMap computeNodes(Graph graph, Iterable<AbstractBeginNode> blocks, Iterable<AbstractBeginNode> earlyExits) {
 207         final NodeBitMap nodes = graph.createNodeBitMap();
 208         computeNodes(nodes, graph, blocks, earlyExits);
 209         return nodes;
 210     }
 211 
 212     protected static void computeNodes(NodeBitMap nodes, Graph graph, Iterable<AbstractBeginNode> blocks, Iterable<AbstractBeginNode> earlyExits) {
 213         for (AbstractBeginNode b : blocks) {
 214             if (b.isDeleted()) {
 215                 continue;
 216             }
 217 
 218             for (Node n : b.getBlockNodes()) {
 219                 if (n instanceof Invoke) {
 220                     nodes.mark(((Invoke) n).callTarget());
 221                 }
 222                 if (n instanceof NodeWithState) {
 223                     NodeWithState withState = (NodeWithState) n;
 224                     withState.states().forEach(state -> state.applyToVirtual(node -> nodes.mark(node)));
 225                 }
 226                 if (n instanceof AbstractMergeNode) {
 227                     // if a merge is in the loop, all of its phis are also in the loop
 228                     for (PhiNode phi : ((AbstractMergeNode) n).phis()) {
 229                         nodes.mark(phi);
 230                     }
 231                 }
 232                 nodes.mark(n);
 233             }
 234         }
 235         for (AbstractBeginNode earlyExit : earlyExits) {
 236             if (earlyExit.isDeleted()) {
 237                 continue;
 238             }
 239 
 240             nodes.mark(earlyExit);
 241 
 242             if (earlyExit instanceof LoopExitNode) {
 243                 LoopExitNode loopExit = (LoopExitNode) earlyExit;
 244                 FrameState stateAfter = loopExit.stateAfter();
 245                 if (stateAfter != null) {
 246                     stateAfter.applyToVirtual(node -> nodes.mark(node));
 247                 }
 248                 for (ProxyNode proxy : loopExit.proxies()) {
 249                     nodes.mark(proxy);
 250                 }
 251             }
 252         }
 253 
 254         final NodeBitMap nonLoopNodes = graph.createNodeBitMap();
 255         Deque<WorkListEntry> worklist = new ArrayDeque<>();
 256         for (AbstractBeginNode b : blocks) {
 257             if (b.isDeleted()) {
 258                 continue;
 259             }
 260 
 261             for (Node n : b.getBlockNodes()) {
 262                 if (n instanceof CommitAllocationNode) {
 263                     for (VirtualObjectNode obj : ((CommitAllocationNode) n).getVirtualObjects()) {
 264                         markFloating(worklist, obj, nodes, nonLoopNodes);
 265                     }
 266                 }
 267                 if (n instanceof MonitorEnterNode) {
 268                     markFloating(worklist, ((MonitorEnterNode) n).getMonitorId(), nodes, nonLoopNodes);
 269                 }
 270                 if (n instanceof AbstractMergeNode) {
 271                     /*
 272                      * Since we already marked all phi nodes as being in the loop to break cycles,
 273                      * we also have to iterate over their usages here.
 274                      */
 275                     for (PhiNode phi : ((AbstractMergeNode) n).phis()) {
 276                         for (Node usage : phi.usages()) {
 277                             markFloating(worklist, usage, nodes, nonLoopNodes);
 278                         }
 279                     }
 280                 }
 281                 for (Node usage : n.usages()) {
 282                     markFloating(worklist, usage, nodes, nonLoopNodes);
 283                 }
 284             }
 285         }
 286     }
 287 
 288     static class WorkListEntry {
 289         final Iterator<Node> usages;
 290         final Node n;
 291         boolean isLoopNode;
 292 
 293         WorkListEntry(Node n, NodeBitMap loopNodes) {
 294             this.n = n;
 295             this.usages = n.usages().iterator();
 296             this.isLoopNode = loopNodes.isMarked(n);
 297         }
 298 
 299         @Override
 300         public boolean equals(Object obj) {
 301             if (!(obj instanceof WorkListEntry)) {
 302                 return false;
 303             }
 304             WorkListEntry other = (WorkListEntry) obj;
 305             return this.n == other.n;
 306         }
 307 
 308         @Override
 309         public int hashCode() {
 310             return n.hashCode();
 311         }
 312     }
 313 
 314     static TriState isLoopNode(Node n, NodeBitMap loopNodes, NodeBitMap nonLoopNodes) {
 315         if (loopNodes.isMarked(n)) {
 316             return TriState.TRUE;
 317         }
 318         if (nonLoopNodes.isMarked(n)) {
 319             return TriState.FALSE;
 320         }
 321         if (n instanceof FixedNode || n instanceof PhiNode) {
 322             // phi nodes are treated the same as fixed nodes in this algorithm to break cycles
 323             return TriState.FALSE;
 324         }
 325         return TriState.UNKNOWN;
 326     }
 327 
 328     private static void pushWorkList(Deque<WorkListEntry> workList, Node node, NodeBitMap loopNodes) {
 329         WorkListEntry entry = new WorkListEntry(node, loopNodes);
 330         assert !workList.contains(entry) : "node " + node + " added to worklist twice";
 331         workList.push(entry);
 332     }
 333 
 334     private static void markFloating(Deque<WorkListEntry> workList, Node start, NodeBitMap loopNodes, NodeBitMap nonLoopNodes) {
 335         if (isLoopNode(start, loopNodes, nonLoopNodes).isKnown()) {
 336             return;
 337         }
 338         pushWorkList(workList, start, loopNodes);
 339         while (!workList.isEmpty()) {
 340             WorkListEntry currentEntry = workList.peek();
 341             if (currentEntry.usages.hasNext()) {
 342                 Node current = currentEntry.usages.next();
 343                 TriState result = isLoopNode(current, loopNodes, nonLoopNodes);
 344                 if (result.isKnown()) {
 345                     if (result.toBoolean()) {
 346                         currentEntry.isLoopNode = true;
 347                     }
 348                 } else {
 349                     pushWorkList(workList, current, loopNodes);
 350                 }
 351             } else {
 352                 workList.pop();
 353                 boolean isLoopNode = currentEntry.isLoopNode;
 354                 Node current = currentEntry.n;
 355                 if (!isLoopNode && current instanceof GuardNode) {
 356                     /*
 357                      * (gd) this is only OK if we are not going to make loop transforms based on
 358                      * this
 359                      */
 360                     assert !((GuardNode) current).graph().hasValueProxies();
 361                     isLoopNode = true;
 362                 }
 363                 if (isLoopNode) {
 364                     loopNodes.mark(current);
 365                     for (WorkListEntry e : workList) {
 366                         e.isLoopNode = true;
 367                     }
 368                 } else {
 369                     nonLoopNodes.mark(current);
 370                 }
 371             }
 372         }
 373     }
 374 
 375     public static NodeIterable<AbstractBeginNode> toHirBlocks(final Iterable<Block> blocks) {
 376         return new NodeIterable<AbstractBeginNode>() {
 377 
 378             @Override
 379             public Iterator<AbstractBeginNode> iterator() {
 380                 final Iterator<Block> it = blocks.iterator();
 381                 return new Iterator<AbstractBeginNode>() {
 382 
 383                     @Override
 384                     public void remove() {
 385                         throw new UnsupportedOperationException();
 386                     }
 387 
 388                     @Override
 389                     public AbstractBeginNode next() {
 390                         return it.next().getBeginNode();
 391                     }
 392 
 393                     @Override
 394                     public boolean hasNext() {
 395                         return it.hasNext();
 396                     }
 397                 };
 398             }
 399 
 400         };
 401     }
 402 




































 403     /**
 404      * Merges the early exits (i.e. loop exits) that were duplicated as part of this fragment, with
 405      * the original fragment's exits.
 406      */
 407     protected void mergeEarlyExits() {
 408         assert isDuplicate();
 409         StructuredGraph graph = graph();
 410         for (AbstractBeginNode earlyExit : LoopFragment.toHirBlocks(original().loop().loop().getLoopExits())) {
 411             FixedNode next = earlyExit.next();
 412             if (earlyExit.isDeleted() || !this.original().contains(earlyExit)) {

 413                 continue;
 414             }
 415             AbstractBeginNode newEarlyExit = getDuplicatedNode(earlyExit);
 416             if (newEarlyExit == null) {
 417                 continue;
 418             }
 419             MergeNode merge = graph.add(new MergeNode());
 420             EndNode originalEnd = graph.add(new EndNode());
 421             EndNode newEnd = graph.add(new EndNode());
 422             merge.addForwardEnd(originalEnd);
 423             merge.addForwardEnd(newEnd);
 424             earlyExit.setNext(originalEnd);
 425             newEarlyExit.setNext(newEnd);
 426             merge.setNext(next);
 427 
 428             FrameState exitState = null;
 429             if (earlyExit instanceof LoopExitNode) {
 430                 LoopExitNode earlyLoopExit = (LoopExitNode) earlyExit;
 431                 exitState = earlyLoopExit.stateAfter();
 432                 if (exitState != null) {
 433                     FrameState originalExitState = exitState;
 434                     exitState = exitState.duplicateWithVirtualState();
 435                     earlyLoopExit.setStateAfter(exitState);
 436                     merge.setStateAfter(originalExitState);
 437                     /*
 438                      * Using the old exit's state as the merge's state is necessary because some of
 439                      * the VirtualState nodes contained in the old exit's state may be shared by
 440                      * other dominated VirtualStates. Those dominated virtual states need to see the
 441                      * proxy->phi update that are applied below.
 442                      *
 443                      * We now update the original fragment's nodes accordingly:
 444                      */
 445                     originalExitState.applyToVirtual(node -> original.nodes.clearAndGrow(node));
 446                     exitState.applyToVirtual(node -> original.nodes.markAndGrow(node));
 447                 }
 448             }
 449 
 450             for (Node anchored : earlyExit.anchored().snapshot()) {
 451                 anchored.replaceFirstInput(earlyExit, merge);
 452             }
 453 
 454             if (earlyExit instanceof LoopExitNode) {
 455                 LoopExitNode earlyLoopExit = (LoopExitNode) earlyExit;
 456                 FrameState finalExitState = exitState;
 457                 boolean newEarlyExitIsLoopExit = newEarlyExit instanceof LoopExitNode;
 458                 for (ProxyNode vpn : earlyLoopExit.proxies().snapshot()) {
 459                     if (vpn.hasNoUsages()) {
 460                         continue;
 461                     }
 462                     if (vpn.value() == null) {
 463                         assert vpn instanceof GuardProxyNode;
 464                         vpn.replaceAtUsages(null);
 465                         continue;
 466                     }
 467                     final ValueNode replaceWith;
 468                     ValueNode newVpn = prim(newEarlyExitIsLoopExit ? vpn : vpn.value());
 469                     if (newVpn != null) {
 470                         PhiNode phi;
 471                         if (vpn instanceof ValueProxyNode) {
 472                             phi = graph.addWithoutUnique(new ValuePhiNode(vpn.stamp(NodeView.DEFAULT), merge));
 473                         } else if (vpn instanceof GuardProxyNode) {
 474                             phi = graph.addWithoutUnique(new GuardPhiNode(merge));
 475                         } else {
 476                             throw GraalError.shouldNotReachHere();
 477                         }
 478                         phi.addInput(vpn);
 479                         phi.addInput(newVpn);
 480                         replaceWith = phi;
 481                     } else {
 482                         replaceWith = vpn.value();
 483                     }
 484                     vpn.replaceAtMatchingUsages(replaceWith, usage -> {
 485                         if (merge.isPhiAtMerge(usage)) {











 486                             return false;
 487                         }
 488                         if (usage instanceof VirtualState) {
 489                             VirtualState stateUsage = (VirtualState) usage;
 490                             if (finalExitState != null && finalExitState.isPartOfThisState(stateUsage)) {
 491                                 return false;
 492                             }
 493                         }
 494                         return true;
 495                     });
 496                 }
 497             }
 498         }
 499     }
 500 }
--- EOF ---