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 }