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.java.MonitorEnterNode;
  60 import org.graalvm.compiler.nodes.spi.NodeWithState;
  61 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
  62 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
  63 
  64 import jdk.vm.ci.meta.TriState;
  65 
  66 public abstract class LoopFragment {
  67 
  68     private final LoopEx loop;
  69     private final LoopFragment original;
  70     protected NodeBitMap nodes;
  71     protected boolean nodesReady;
  72     private EconomicMap<Node, Node> duplicationMap;
  73 
  74     public LoopFragment(LoopEx loop) {
  75         this(loop, null);
  76         this.nodesReady = true;
  77     }
  78 
  79     public LoopFragment(LoopEx loop, LoopFragment original) {
  80         this.loop = loop;
  81         this.original = original;
  82         this.nodesReady = false;
  83     }
  84 
  85     /**
  86      * Return the original LoopEx for this fragment. For duplicated fragments this returns null.
  87      */
  88     protected LoopEx loop() {
  89         return loop;
  90     }
  91 
  92     public abstract LoopFragment duplicate();
  93 
  94     public abstract void insertBefore(LoopEx l);
  95 
  96     public void disconnect() {
  97         // TODO (gd) possibly abstract
  98     }
  99 
 100     public boolean contains(Node n) {
 101         return nodes().isMarkedAndGrow(n);
 102     }
 103 
 104     @SuppressWarnings("unchecked")
 105     public <New extends Node, Old extends New> New getDuplicatedNode(Old n) {
 106         assert isDuplicate();
 107         return (New) duplicationMap.get(n);
 108     }
 109 
 110     protected <New extends Node, Old extends New> void putDuplicatedNode(Old oldNode, New newNode) {
 111         duplicationMap.put(oldNode, newNode);
 112     }
 113 
 114     /**
 115      * Gets the corresponding value in this fragment. Should be called on duplicate fragments with a
 116      * node from the original fragment as argument.
 117      *
 118      * @param b original value
 119      * @return corresponding value in the peel
 120      */
 121     protected abstract ValueNode prim(ValueNode b);
 122 
 123     public boolean isDuplicate() {
 124         return original != null;
 125     }
 126 
 127     public LoopFragment original() {
 128         return original;
 129     }
 130 
 131     public abstract NodeBitMap nodes();
 132 
 133     public StructuredGraph graph() {
 134         LoopEx l;
 135         if (isDuplicate()) {
 136             l = original().loop();
 137         } else {
 138             l = loop();
 139         }
 140         return l.loopBegin().graph();
 141     }
 142 
 143     protected abstract DuplicationReplacement getDuplicationReplacement();
 144 
 145     protected abstract void beforeDuplication();
 146 
 147     protected abstract void finishDuplication();











 148 
 149     protected void patchNodes(final DuplicationReplacement dataFix) {
 150         if (isDuplicate() && !nodesReady) {
 151             assert !original.isDuplicate();
 152             final DuplicationReplacement cfgFix = original().getDuplicationReplacement();
 153             DuplicationReplacement dr;
 154             if (cfgFix == null && dataFix != null) {
 155                 dr = dataFix;
 156             } else if (cfgFix != null && dataFix == null) {
 157                 dr = cfgFix;
 158             } else if (cfgFix != null && dataFix != null) {
 159                 dr = new DuplicationReplacement() {
 160 
 161                     @Override
 162                     public Node replacement(Node o) {
 163                         Node r1 = dataFix.replacement(o);
 164                         if (r1 != o) {
 165                             assert cfgFix.replacement(o) == o;
 166                             return r1;
 167                         }
 168                         Node r2 = cfgFix.replacement(o);
 169                         if (r2 != o) {
 170                             return r2;
 171                         }
 172                         return o;
 173                     }
 174                 };
 175             } else {
 176                 dr = null;
 177             }
 178             beforeDuplication();
 179             NodeIterable<Node> nodesIterable = original().nodes();
 180             duplicationMap = graph().addDuplicates(nodesIterable, graph(), nodesIterable.count(), dr);
 181             finishDuplication();
 182             nodes = new NodeBitMap(graph());
 183             nodes.markAll(duplicationMap.getValues());
 184             nodesReady = true;
 185         } else {
 186             // TODO (gd) apply fix ?
 187         }
 188     }
 189 
 190     protected static NodeBitMap computeNodes(Graph graph, Iterable<AbstractBeginNode> blocks) {
 191         return computeNodes(graph, blocks, Collections.emptyList());
 192     }
 193 
 194     protected static NodeBitMap computeNodes(Graph graph, Iterable<AbstractBeginNode> blocks, Iterable<AbstractBeginNode> earlyExits) {
 195         final NodeBitMap nodes = graph.createNodeBitMap();
 196         computeNodes(nodes, graph, blocks, earlyExits);
 197         return nodes;
 198     }
 199 
 200     protected static void computeNodes(NodeBitMap nodes, Graph graph, Iterable<AbstractBeginNode> blocks, Iterable<AbstractBeginNode> earlyExits) {
 201         for (AbstractBeginNode b : blocks) {
 202             if (b.isDeleted()) {
 203                 continue;
 204             }
 205 
 206             for (Node n : b.getBlockNodes()) {
 207                 if (n instanceof Invoke) {
 208                     nodes.mark(((Invoke) n).callTarget());
 209                 }
 210                 if (n instanceof NodeWithState) {
 211                     NodeWithState withState = (NodeWithState) n;
 212                     withState.states().forEach(state -> state.applyToVirtual(node -> nodes.mark(node)));
 213                 }
 214                 if (n instanceof AbstractMergeNode) {
 215                     // if a merge is in the loop, all of its phis are also in the loop
 216                     for (PhiNode phi : ((AbstractMergeNode) n).phis()) {
 217                         nodes.mark(phi);
 218                     }
 219                 }
 220                 nodes.mark(n);
 221             }
 222         }
 223         for (AbstractBeginNode earlyExit : earlyExits) {
 224             if (earlyExit.isDeleted()) {
 225                 continue;
 226             }
 227 
 228             nodes.mark(earlyExit);
 229 
 230             if (earlyExit instanceof LoopExitNode) {
 231                 LoopExitNode loopExit = (LoopExitNode) earlyExit;
 232                 FrameState stateAfter = loopExit.stateAfter();
 233                 if (stateAfter != null) {
 234                     stateAfter.applyToVirtual(node -> nodes.mark(node));
 235                 }
 236                 for (ProxyNode proxy : loopExit.proxies()) {
 237                     nodes.mark(proxy);
 238                 }
 239             }
 240         }
 241 
 242         final NodeBitMap nonLoopNodes = graph.createNodeBitMap();
 243         Deque<WorkListEntry> worklist = new ArrayDeque<>();
 244         for (AbstractBeginNode b : blocks) {
 245             if (b.isDeleted()) {
 246                 continue;
 247             }
 248 
 249             for (Node n : b.getBlockNodes()) {
 250                 if (n instanceof CommitAllocationNode) {
 251                     for (VirtualObjectNode obj : ((CommitAllocationNode) n).getVirtualObjects()) {
 252                         markFloating(worklist, obj, nodes, nonLoopNodes);
 253                     }
 254                 }
 255                 if (n instanceof MonitorEnterNode) {
 256                     markFloating(worklist, ((MonitorEnterNode) n).getMonitorId(), nodes, nonLoopNodes);
 257                 }
 258                 if (n instanceof AbstractMergeNode) {
 259                     /*
 260                      * Since we already marked all phi nodes as being in the loop to break cycles,
 261                      * we also have to iterate over their usages here.
 262                      */
 263                     for (PhiNode phi : ((AbstractMergeNode) n).phis()) {
 264                         for (Node usage : phi.usages()) {
 265                             markFloating(worklist, usage, nodes, nonLoopNodes);
 266                         }
 267                     }
 268                 }
 269                 for (Node usage : n.usages()) {
 270                     markFloating(worklist, usage, nodes, nonLoopNodes);
 271                 }
 272             }
 273         }
 274     }
 275 
 276     static class WorkListEntry {
 277         final Iterator<Node> usages;
 278         final Node n;
 279         boolean isLoopNode;
 280 
 281         WorkListEntry(Node n, NodeBitMap loopNodes) {
 282             this.n = n;
 283             this.usages = n.usages().iterator();
 284             this.isLoopNode = loopNodes.isMarked(n);
 285         }
 286 
 287         @Override
 288         public boolean equals(Object obj) {
 289             if (!(obj instanceof WorkListEntry)) {
 290                 return false;
 291             }
 292             WorkListEntry other = (WorkListEntry) obj;
 293             return this.n == other.n;
 294         }
 295 
 296         @Override
 297         public int hashCode() {
 298             return n.hashCode();
 299         }
 300     }
 301 
 302     static TriState isLoopNode(Node n, NodeBitMap loopNodes, NodeBitMap nonLoopNodes) {
 303         if (loopNodes.isMarked(n)) {
 304             return TriState.TRUE;
 305         }
 306         if (nonLoopNodes.isMarked(n)) {
 307             return TriState.FALSE;
 308         }
 309         if (n instanceof FixedNode || n instanceof PhiNode) {
 310             // phi nodes are treated the same as fixed nodes in this algorithm to break cycles
 311             return TriState.FALSE;
 312         }
 313         return TriState.UNKNOWN;
 314     }
 315 
 316     private static void pushWorkList(Deque<WorkListEntry> workList, Node node, NodeBitMap loopNodes) {
 317         WorkListEntry entry = new WorkListEntry(node, loopNodes);
 318         assert !workList.contains(entry) : "node " + node + " added to worklist twice";
 319         workList.push(entry);
 320     }
 321 
 322     private static void markFloating(Deque<WorkListEntry> workList, Node start, NodeBitMap loopNodes, NodeBitMap nonLoopNodes) {
 323         if (isLoopNode(start, loopNodes, nonLoopNodes).isKnown()) {
 324             return;
 325         }
 326         pushWorkList(workList, start, loopNodes);
 327         while (!workList.isEmpty()) {
 328             WorkListEntry currentEntry = workList.peek();
 329             if (currentEntry.usages.hasNext()) {
 330                 Node current = currentEntry.usages.next();
 331                 TriState result = isLoopNode(current, loopNodes, nonLoopNodes);
 332                 if (result.isKnown()) {
 333                     if (result.toBoolean()) {
 334                         currentEntry.isLoopNode = true;
 335                     }
 336                 } else {
 337                     pushWorkList(workList, current, loopNodes);
 338                 }
 339             } else {
 340                 workList.pop();
 341                 boolean isLoopNode = currentEntry.isLoopNode;
 342                 Node current = currentEntry.n;
 343                 if (!isLoopNode && current instanceof GuardNode) {
 344                     /*
 345                      * (gd) this is only OK if we are not going to make loop transforms based on
 346                      * this
 347                      */
 348                     assert !((GuardNode) current).graph().hasValueProxies();
 349                     isLoopNode = true;
 350                 }
 351                 if (isLoopNode) {
 352                     loopNodes.mark(current);
 353                     for (WorkListEntry e : workList) {
 354                         e.isLoopNode = true;
 355                     }
 356                 } else {
 357                     nonLoopNodes.mark(current);
 358                 }
 359             }
 360         }
 361     }
 362 
 363     public static NodeIterable<AbstractBeginNode> toHirBlocks(final Iterable<Block> blocks) {
 364         return new NodeIterable<AbstractBeginNode>() {
 365 
 366             @Override
 367             public Iterator<AbstractBeginNode> iterator() {
 368                 final Iterator<Block> it = blocks.iterator();
 369                 return new Iterator<AbstractBeginNode>() {
 370 
 371                     @Override
 372                     public void remove() {
 373                         throw new UnsupportedOperationException();
 374                     }
 375 
 376                     @Override
 377                     public AbstractBeginNode next() {
 378                         return it.next().getBeginNode();
 379                     }
 380 
 381                     @Override
 382                     public boolean hasNext() {
 383                         return it.hasNext();
 384                     }
 385                 };
 386             }
 387 
 388         };
 389     }
 390 
 391     public static NodeIterable<AbstractBeginNode> toHirExits(final Iterable<Block> blocks) {
 392         return new NodeIterable<AbstractBeginNode>() {
 393 
 394             @Override
 395             public Iterator<AbstractBeginNode> iterator() {
 396                 final Iterator<Block> it = blocks.iterator();
 397                 return new Iterator<AbstractBeginNode>() {
 398 
 399                     @Override
 400                     public void remove() {
 401                         throw new UnsupportedOperationException();
 402                     }
 403 
 404                     /**
 405                      * Return the true LoopExitNode for this loop or the BeginNode for the block.
 406                      */
 407                     @Override
 408                     public AbstractBeginNode next() {
 409                         Block next = it.next();
 410                         LoopExitNode exit = next.getLoopExit();
 411                         if (exit != null) {
 412                             return exit;
 413                         }
 414                         return next.getBeginNode();
 415                     }
 416 
 417                     @Override
 418                     public boolean hasNext() {
 419                         return it.hasNext();
 420                     }
 421                 };
 422             }
 423 
 424         };
 425     }
 426 
 427     /**
 428      * Merges the early exits (i.e. loop exits) that were duplicated as part of this fragment, with
 429      * the original fragment's exits.
 430      */
 431     protected void mergeEarlyExits() {
 432         assert isDuplicate();
 433         StructuredGraph graph = graph();
 434         for (AbstractBeginNode earlyExit : LoopFragment.toHirBlocks(original().loop().loop().getExits())) {
 435             LoopExitNode loopEarlyExit = (LoopExitNode) earlyExit;
 436             FixedNode next = loopEarlyExit.next();
 437             if (loopEarlyExit.isDeleted() || !this.original().contains(loopEarlyExit)) {
 438                 continue;
 439             }
 440             AbstractBeginNode newEarlyExit = getDuplicatedNode(loopEarlyExit);
 441             if (newEarlyExit == null) {
 442                 continue;
 443             }
 444             MergeNode merge = graph.add(new MergeNode());
 445             EndNode originalEnd = graph.add(new EndNode());
 446             EndNode newEnd = graph.add(new EndNode());
 447             merge.addForwardEnd(originalEnd);
 448             merge.addForwardEnd(newEnd);
 449             loopEarlyExit.setNext(originalEnd);
 450             newEarlyExit.setNext(newEnd);
 451             merge.setNext(next);
 452 
 453             FrameState exitState = loopEarlyExit.stateAfter();
 454             if (exitState != null) {
 455                 FrameState originalExitState = exitState;
 456                 exitState = exitState.duplicateWithVirtualState();
 457                 loopEarlyExit.setStateAfter(exitState);
 458                 merge.setStateAfter(originalExitState);
 459                 /*
 460                  * Using the old exit's state as the merge's state is necessary because some of the
 461                  * VirtualState nodes contained in the old exit's state may be shared by other
 462                  * dominated VirtualStates. Those dominated virtual states need to see the
 463                  * proxy->phi update that are applied below.
 464                  *
 465                  * We now update the original fragment's nodes accordingly:
 466                  */
 467                 originalExitState.applyToVirtual(node -> original.nodes.clearAndGrow(node));
 468                 exitState.applyToVirtual(node -> original.nodes.markAndGrow(node));
 469             }
 470             FrameState finalExitState = exitState;
 471 
 472             for (Node anchored : loopEarlyExit.anchored().snapshot()) {
 473                 anchored.replaceFirstInput(loopEarlyExit, merge);
 474             }
 475 
 476             boolean newEarlyExitIsLoopExit = newEarlyExit instanceof LoopExitNode;
 477             for (ProxyNode vpn : loopEarlyExit.proxies().snapshot()) {
 478                 if (vpn.hasNoUsages()) {
 479                     continue;
 480                 }
 481                 if (vpn.value() == null) {
 482                     assert vpn instanceof GuardProxyNode;
 483                     vpn.replaceAtUsages(null);
 484                     continue;
 485                 }
 486                 final ValueNode replaceWith;
 487                 ValueNode newVpn = prim(newEarlyExitIsLoopExit ? vpn : vpn.value());
 488                 if (newVpn != null) {
 489                     PhiNode phi;
 490                     if (vpn instanceof ValueProxyNode) {
 491                         phi = graph.addWithoutUnique(new ValuePhiNode(vpn.stamp(NodeView.DEFAULT), merge));
 492                     } else if (vpn instanceof GuardProxyNode) {
 493                         phi = graph.addWithoutUnique(new GuardPhiNode(merge));












 494                     } else {
 495                         throw GraalError.shouldNotReachHere();
 496                     }
 497                     phi.addInput(vpn);
 498                     phi.addInput(newVpn);
 499                     replaceWith = phi;
 500                 } else {
 501                     replaceWith = vpn.value();
 502                 }
 503                 vpn.replaceAtMatchingUsages(replaceWith, usage -> {
 504                     if (merge.isPhiAtMerge(usage)) {
 505                         return false;
 506                     }
 507                     if (usage instanceof VirtualState) {
 508                         VirtualState stateUsage = (VirtualState) usage;
 509                         if (finalExitState != null && finalExitState.isPartOfThisState(stateUsage)) {
 510                             return false;
 511                         }
 512                     }
 513                     return true;
 514                 });






 515             }
 516         }
 517     }
 518 }
--- EOF ---