1 /*
   2  * Copyright (c) 2012, 2016, 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 package org.graalvm.compiler.loop;
  24 
  25 import java.util.LinkedList;
  26 import java.util.List;
  27 
  28 import org.graalvm.compiler.debug.GraalError;
  29 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
  30 import org.graalvm.compiler.graph.Node;
  31 import org.graalvm.compiler.graph.NodeBitMap;
  32 import org.graalvm.compiler.graph.iterators.NodeIterable;
  33 import org.graalvm.compiler.nodes.AbstractBeginNode;
  34 import org.graalvm.compiler.nodes.AbstractEndNode;
  35 import org.graalvm.compiler.nodes.AbstractMergeNode;
  36 import org.graalvm.compiler.nodes.BeginNode;
  37 import org.graalvm.compiler.nodes.EndNode;
  38 import org.graalvm.compiler.nodes.FrameState;
  39 import org.graalvm.compiler.nodes.GuardPhiNode;
  40 import org.graalvm.compiler.nodes.LoopBeginNode;
  41 import org.graalvm.compiler.nodes.LoopEndNode;
  42 import org.graalvm.compiler.nodes.LoopExitNode;
  43 import org.graalvm.compiler.nodes.MergeNode;
  44 import org.graalvm.compiler.nodes.PhiNode;
  45 import org.graalvm.compiler.nodes.ProxyNode;
  46 import org.graalvm.compiler.nodes.StateSplit;
  47 import org.graalvm.compiler.nodes.StructuredGraph;
  48 import org.graalvm.compiler.nodes.ValueNode;
  49 import org.graalvm.compiler.nodes.ValuePhiNode;
  50 import org.graalvm.compiler.nodes.VirtualState.NodeClosure;
  51 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
  52 import org.graalvm.compiler.nodes.util.GraphUtil;
  53 import org.graalvm.util.Equivalence;
  54 import org.graalvm.util.EconomicMap;
  55 
  56 public class LoopFragmentInside extends LoopFragment {
  57 
  58     /**
  59      * mergedInitializers. When an inside fragment's (loop)ends are merged to create a unique exit
  60      * point, some phis must be created : they phis together all the back-values of the loop-phis
  61      * These can then be used to update the loop-phis' forward edge value ('initializer') in the
  62      * peeling case. In the unrolling case they will be used as the value that replace the loop-phis
  63      * of the duplicated inside fragment
  64      */
  65     private EconomicMap<PhiNode, ValueNode> mergedInitializers;
  66     private final DuplicationReplacement dataFixBefore = new DuplicationReplacement() {
  67 
  68         @Override
  69         public Node replacement(Node oriInput) {
  70             if (!(oriInput instanceof ValueNode)) {
  71                 return oriInput;
  72             }
  73             return prim((ValueNode) oriInput);
  74         }
  75     };
  76 
  77     public LoopFragmentInside(LoopEx loop) {
  78         super(loop);
  79     }
  80 
  81     public LoopFragmentInside(LoopFragmentInside original) {
  82         super(null, original);
  83     }
  84 
  85     @Override
  86     public LoopFragmentInside duplicate() {
  87         assert !isDuplicate();
  88         return new LoopFragmentInside(this);
  89     }
  90 
  91     @Override
  92     public LoopFragmentInside original() {
  93         return (LoopFragmentInside) super.original();
  94     }
  95 
  96     @SuppressWarnings("unused")
  97     public void appendInside(LoopEx loop) {
  98         // TODO (gd)
  99     }
 100 
 101     @Override
 102     public LoopEx loop() {
 103         assert !this.isDuplicate();
 104         return super.loop();
 105     }
 106 
 107     @Override
 108     public void insertBefore(LoopEx loop) {
 109         assert this.isDuplicate() && this.original().loop() == loop;
 110 
 111         patchNodes(dataFixBefore);
 112 
 113         AbstractBeginNode end = mergeEnds();
 114 
 115         mergeEarlyExits();
 116 
 117         original().patchPeeling(this);
 118 
 119         AbstractBeginNode entry = getDuplicatedNode(loop.loopBegin());
 120         loop.entryPoint().replaceAtPredecessor(entry);
 121         end.setNext(loop.entryPoint());
 122     }
 123 
 124     @Override
 125     public NodeBitMap nodes() {
 126         if (nodes == null) {
 127             LoopFragmentWhole whole = loop().whole();
 128             whole.nodes(); // init nodes bitmap in whole
 129             nodes = whole.nodes.copy();
 130             // remove the phis
 131             LoopBeginNode loopBegin = loop().loopBegin();
 132             for (PhiNode phi : loopBegin.phis()) {
 133                 nodes.clear(phi);
 134             }
 135             clearStateNodes(loopBegin);
 136             for (LoopExitNode exit : exits()) {
 137                 clearStateNodes(exit);
 138                 for (ProxyNode proxy : exit.proxies()) {
 139                     nodes.clear(proxy);
 140                 }
 141             }
 142         }
 143         return nodes;
 144     }
 145 
 146     private void clearStateNodes(StateSplit stateSplit) {
 147         FrameState loopState = stateSplit.stateAfter();
 148         if (loopState != null) {
 149             loopState.applyToVirtual(v -> {
 150                 if (v.usages().filter(n -> nodes.isMarked(n) && n != stateSplit).isEmpty()) {
 151                     nodes.clear(v);
 152                 }
 153             });
 154         }
 155     }
 156 
 157     public NodeIterable<LoopExitNode> exits() {
 158         return loop().loopBegin().loopExits();
 159     }
 160 
 161     @Override
 162     protected DuplicationReplacement getDuplicationReplacement() {
 163         final LoopBeginNode loopBegin = loop().loopBegin();
 164         final StructuredGraph graph = graph();
 165         return new DuplicationReplacement() {
 166 
 167             private EconomicMap<Node, Node> seenNode = EconomicMap.create(Equivalence.IDENTITY);
 168 
 169             @Override
 170             public Node replacement(Node original) {
 171                 if (original == loopBegin) {
 172                     Node value = seenNode.get(original);
 173                     if (value != null) {
 174                         return value;
 175                     }
 176                     AbstractBeginNode newValue = graph.add(new BeginNode());
 177                     seenNode.put(original, newValue);
 178                     return newValue;
 179                 }
 180                 if (original instanceof LoopExitNode && ((LoopExitNode) original).loopBegin() == loopBegin) {
 181                     Node value = seenNode.get(original);
 182                     if (value != null) {
 183                         return value;
 184                     }
 185                     AbstractBeginNode newValue = graph.add(new BeginNode());
 186                     seenNode.put(original, newValue);
 187                     return newValue;
 188                 }
 189                 if (original instanceof LoopEndNode && ((LoopEndNode) original).loopBegin() == loopBegin) {
 190                     Node value = seenNode.get(original);
 191                     if (value != null) {
 192                         return value;
 193                     }
 194                     EndNode newValue = graph.add(new EndNode());
 195                     seenNode.put(original, newValue);
 196                     return newValue;
 197                 }
 198                 return original;
 199             }
 200         };
 201     }
 202 
 203     @Override
 204     protected void finishDuplication() {
 205         // TODO (gd) ?
 206     }
 207 
 208     private static PhiNode patchPhi(StructuredGraph graph, PhiNode phi, AbstractMergeNode merge) {
 209         PhiNode ret;
 210         if (phi instanceof ValuePhiNode) {
 211             ret = new ValuePhiNode(phi.stamp(), merge);
 212         } else if (phi instanceof GuardPhiNode) {
 213             ret = new GuardPhiNode(merge);
 214         } else if (phi instanceof MemoryPhiNode) {
 215             ret = new MemoryPhiNode(merge, ((MemoryPhiNode) phi).getLocationIdentity());
 216         } else {
 217             throw GraalError.shouldNotReachHere();
 218         }
 219         return graph.addWithoutUnique(ret);
 220     }
 221 
 222     private void patchPeeling(LoopFragmentInside peel) {
 223         LoopBeginNode loopBegin = loop().loopBegin();
 224         StructuredGraph graph = loopBegin.graph();
 225         List<PhiNode> newPhis = new LinkedList<>();
 226 
 227         NodeBitMap usagesToPatch = nodes.copy();
 228         for (LoopExitNode exit : exits()) {
 229             markStateNodes(exit, usagesToPatch);
 230             for (ProxyNode proxy : exit.proxies()) {
 231                 usagesToPatch.markAndGrow(proxy);
 232             }
 233         }
 234         markStateNodes(loopBegin, usagesToPatch);
 235 
 236         List<PhiNode> oldPhis = loopBegin.phis().snapshot();
 237         for (PhiNode phi : oldPhis) {
 238             if (phi.hasNoUsages()) {
 239                 continue;
 240             }
 241             ValueNode first;
 242             if (loopBegin.loopEnds().count() == 1) {
 243                 ValueNode b = phi.valueAt(loopBegin.loopEnds().first()); // back edge value
 244                 first = peel.prim(b); // corresponding value in the peel
 245             } else {
 246                 first = peel.mergedInitializers.get(phi);
 247             }
 248             // create a new phi (we don't patch the old one since some usages of the old one may
 249             // still be valid)
 250             PhiNode newPhi = patchPhi(graph, phi, loopBegin);
 251             newPhi.addInput(first);
 252             for (LoopEndNode end : loopBegin.orderedLoopEnds()) {
 253                 newPhi.addInput(phi.valueAt(end));
 254             }
 255             peel.putDuplicatedNode(phi, newPhi);
 256             newPhis.add(newPhi);
 257             for (Node usage : phi.usages().snapshot()) {
 258                 // patch only usages that should use the new phi ie usages that were peeled
 259                 if (usagesToPatch.isMarkedAndGrow(usage)) {
 260                     usage.replaceFirstInput(phi, newPhi);
 261                 }
 262             }
 263         }
 264         // check new phis to see if they have as input some old phis, replace those inputs with the
 265         // new corresponding phis
 266         for (PhiNode phi : newPhis) {
 267             for (int i = 0; i < phi.valueCount(); i++) {
 268                 ValueNode v = phi.valueAt(i);
 269                 if (loopBegin.isPhiAtMerge(v)) {
 270                     PhiNode newV = peel.getDuplicatedNode((ValuePhiNode) v);
 271                     if (newV != null) {
 272                         phi.setValueAt(i, newV);
 273                     }
 274                 }
 275             }
 276         }
 277 
 278         boolean progress = true;
 279         while (progress) {
 280             progress = false;
 281             int i = 0;
 282             outer: while (i < oldPhis.size()) {
 283                 PhiNode oldPhi = oldPhis.get(i);
 284                 for (Node usage : oldPhi.usages()) {
 285                     if (usage instanceof PhiNode && oldPhis.contains(usage)) {
 286                         // Do not mark.
 287                     } else {
 288                         // Mark alive by removing from delete set.
 289                         oldPhis.remove(i);
 290                         progress = true;
 291                         continue outer;
 292                     }
 293                 }
 294                 i++;
 295             }
 296         }
 297 
 298         for (PhiNode deadPhi : oldPhis) {
 299             deadPhi.clearInputs();
 300         }
 301 
 302         for (PhiNode deadPhi : oldPhis) {
 303             if (deadPhi.isAlive()) {
 304                 GraphUtil.killWithUnusedFloatingInputs(deadPhi);
 305             }
 306         }
 307     }
 308 
 309     private static void markStateNodes(StateSplit stateSplit, NodeBitMap marks) {
 310         FrameState exitState = stateSplit.stateAfter();
 311         if (exitState != null) {
 312             exitState.applyToVirtual(v -> marks.markAndGrow(v));
 313         }
 314     }
 315 
 316     /**
 317      * Gets the corresponding value in this fragment.
 318      *
 319      * @param b original value
 320      * @return corresponding value in the peel
 321      */
 322     @Override
 323     protected ValueNode prim(ValueNode b) {
 324         assert isDuplicate();
 325         LoopBeginNode loopBegin = original().loop().loopBegin();
 326         if (loopBegin.isPhiAtMerge(b)) {
 327             PhiNode phi = (PhiNode) b;
 328             return phi.valueAt(loopBegin.forwardEnd());
 329         } else if (nodesReady) {
 330             ValueNode v = getDuplicatedNode(b);
 331             if (v == null) {
 332                 return b;
 333             }
 334             return v;
 335         } else {
 336             return b;
 337         }
 338     }
 339 
 340     private AbstractBeginNode mergeEnds() {
 341         assert isDuplicate();
 342         List<EndNode> endsToMerge = new LinkedList<>();
 343         // map peel exits to the corresponding loop exits
 344         EconomicMap<AbstractEndNode, LoopEndNode> reverseEnds = EconomicMap.create(Equivalence.IDENTITY);
 345         LoopBeginNode loopBegin = original().loop().loopBegin();
 346         for (LoopEndNode le : loopBegin.loopEnds()) {
 347             AbstractEndNode duplicate = getDuplicatedNode(le);
 348             if (duplicate != null) {
 349                 endsToMerge.add((EndNode) duplicate);
 350                 reverseEnds.put(duplicate, le);
 351             }
 352         }
 353         mergedInitializers = EconomicMap.create(Equivalence.IDENTITY);
 354         AbstractBeginNode newExit;
 355         StructuredGraph graph = graph();
 356         if (endsToMerge.size() == 1) {
 357             AbstractEndNode end = endsToMerge.get(0);
 358             assert end.hasNoUsages();
 359             newExit = graph.add(new BeginNode());
 360             end.replaceAtPredecessor(newExit);
 361             end.safeDelete();
 362         } else {
 363             assert endsToMerge.size() > 1;
 364             AbstractMergeNode newExitMerge = graph.add(new MergeNode());
 365             newExit = newExitMerge;
 366             FrameState state = loopBegin.stateAfter();
 367             FrameState duplicateState = null;
 368             if (state != null) {
 369                 duplicateState = state.duplicateWithVirtualState();
 370                 newExitMerge.setStateAfter(duplicateState);
 371             }
 372             for (EndNode end : endsToMerge) {
 373                 newExitMerge.addForwardEnd(end);
 374             }
 375 
 376             for (final PhiNode phi : loopBegin.phis().snapshot()) {
 377                 if (phi.hasNoUsages()) {
 378                     continue;
 379                 }
 380                 final PhiNode firstPhi = patchPhi(graph, phi, newExitMerge);
 381                 for (AbstractEndNode end : newExitMerge.forwardEnds()) {
 382                     LoopEndNode loopEnd = reverseEnds.get(end);
 383                     ValueNode prim = prim(phi.valueAt(loopEnd));
 384                     assert prim != null;
 385                     firstPhi.addInput(prim);
 386                 }
 387                 ValueNode initializer = firstPhi;
 388                 if (duplicateState != null) {
 389                     // fix the merge's state after
 390                     duplicateState.applyToNonVirtual(new NodeClosure<ValueNode>() {
 391 
 392                         @Override
 393                         public void apply(Node from, ValueNode node) {
 394                             if (node == phi) {
 395                                 from.replaceFirstInput(phi, firstPhi);
 396                             }
 397                         }
 398                     });
 399                 }
 400                 mergedInitializers.put(phi, initializer);
 401             }
 402         }
 403         return newExit;
 404     }
 405 }