1 /* 2 * Copyright (c) 2012, 2012, 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.Collections; 26 import java.util.Iterator; 27 28 import org.graalvm.compiler.debug.GraalError; 29 import org.graalvm.compiler.graph.Graph; 30 import org.graalvm.compiler.graph.Graph.DuplicationReplacement; 31 import org.graalvm.compiler.graph.Node; 32 import org.graalvm.compiler.graph.NodeBitMap; 33 import org.graalvm.compiler.graph.iterators.NodeIterable; 34 import org.graalvm.compiler.nodes.AbstractBeginNode; 35 import org.graalvm.compiler.nodes.EndNode; 36 import org.graalvm.compiler.nodes.FixedNode; 37 import org.graalvm.compiler.nodes.FrameState; 38 import org.graalvm.compiler.nodes.GuardNode; 39 import org.graalvm.compiler.nodes.GuardPhiNode; 40 import org.graalvm.compiler.nodes.GuardProxyNode; 41 import org.graalvm.compiler.nodes.Invoke; 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.StructuredGraph; 47 import org.graalvm.compiler.nodes.ValueNode; 48 import org.graalvm.compiler.nodes.ValuePhiNode; 49 import org.graalvm.compiler.nodes.ValueProxyNode; 50 import org.graalvm.compiler.nodes.VirtualState; 51 import org.graalvm.compiler.nodes.cfg.Block; 52 import org.graalvm.compiler.nodes.java.MonitorEnterNode; 53 import org.graalvm.compiler.nodes.spi.NodeWithState; 54 import org.graalvm.compiler.nodes.virtual.CommitAllocationNode; 55 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode; 56 import org.graalvm.util.EconomicMap; 57 58 public abstract class LoopFragment { 59 60 private final LoopEx loop; 61 private final LoopFragment original; 62 protected NodeBitMap nodes; 63 protected boolean nodesReady; 64 private EconomicMap<Node, Node> duplicationMap; 65 66 public LoopFragment(LoopEx loop) { 67 this(loop, null); 68 this.nodesReady = true; 69 } 70 71 public LoopFragment(LoopEx loop, LoopFragment original) { 72 this.loop = loop; 73 this.original = original; 74 this.nodesReady = false; 75 } 76 77 public LoopEx loop() { 78 return loop; 79 } 80 81 public abstract LoopFragment duplicate(); 82 83 public abstract void insertBefore(LoopEx l); 84 85 public void disconnect() { 86 // TODO (gd) possibly abstract 87 } 88 89 public boolean contains(Node n) { 90 return nodes().isMarkedAndGrow(n); 91 } 92 93 @SuppressWarnings("unchecked") 94 public <New extends Node, Old extends New> New getDuplicatedNode(Old n) { 95 assert isDuplicate(); 96 return (New) duplicationMap.get(n); 97 } 98 99 protected <New extends Node, Old extends New> void putDuplicatedNode(Old oldNode, New newNode) { 100 duplicationMap.put(oldNode, newNode); 101 } 102 103 /** 104 * Gets the corresponding value in this fragment. Should be called on duplicate fragments with a 105 * node from the original fragment as argument. 106 * 107 * @param b original value 108 * @return corresponding value in the peel 109 */ 110 protected abstract ValueNode prim(ValueNode b); 111 112 public boolean isDuplicate() { 113 return original != null; 114 } 115 116 public LoopFragment original() { 117 return original; 118 } 119 120 public abstract NodeBitMap nodes(); 121 122 public StructuredGraph graph() { 123 LoopEx l; 124 if (isDuplicate()) { 125 l = original().loop(); 126 } else { 127 l = loop(); 128 } 129 return l.loopBegin().graph(); 130 } 131 132 protected abstract DuplicationReplacement getDuplicationReplacement(); 133 134 protected abstract void finishDuplication(); 135 136 protected void patchNodes(final DuplicationReplacement dataFix) { 137 if (isDuplicate() && !nodesReady) { 138 assert !original.isDuplicate(); 139 final DuplicationReplacement cfgFix = original().getDuplicationReplacement(); 140 DuplicationReplacement dr; 141 if (cfgFix == null && dataFix != null) { 142 dr = dataFix; 143 } else if (cfgFix != null && dataFix == null) { 144 dr = cfgFix; 145 } else if (cfgFix != null && dataFix != null) { 146 dr = new DuplicationReplacement() { 147 148 @Override 149 public Node replacement(Node o) { 150 Node r1 = dataFix.replacement(o); 151 if (r1 != o) { 152 assert cfgFix.replacement(o) == o; 153 return r1; 154 } 155 Node r2 = cfgFix.replacement(o); 156 if (r2 != o) { 157 return r2; 158 } 159 return o; 160 } 161 }; 162 } else { 163 dr = null; 164 } 165 NodeIterable<Node> nodesIterable = original().nodes(); 166 duplicationMap = graph().addDuplicates(nodesIterable, graph(), nodesIterable.count(), dr); 167 finishDuplication(); 168 nodesReady = true; 169 } else { 170 // TODO (gd) apply fix ? 171 } 172 } 173 174 protected static NodeBitMap computeNodes(Graph graph, Iterable<AbstractBeginNode> blocks) { 175 return computeNodes(graph, blocks, Collections.emptyList()); 176 } 177 178 protected static NodeBitMap computeNodes(Graph graph, Iterable<AbstractBeginNode> blocks, Iterable<LoopExitNode> earlyExits) { 179 final NodeBitMap nodes = graph.createNodeBitMap(); 180 computeNodes(nodes, graph, blocks, earlyExits); 181 return nodes; 182 } 183 184 protected static void computeNodes(NodeBitMap nodes, Graph graph, Iterable<AbstractBeginNode> blocks, Iterable<LoopExitNode> earlyExits) { 185 for (AbstractBeginNode b : blocks) { 186 if (b.isDeleted()) { 187 continue; 188 } 189 190 for (Node n : b.getBlockNodes()) { 191 if (n instanceof Invoke) { 192 nodes.mark(((Invoke) n).callTarget()); 193 } 194 if (n instanceof NodeWithState) { 195 NodeWithState withState = (NodeWithState) n; 196 withState.states().forEach(state -> state.applyToVirtual(node -> nodes.mark(node))); 197 } 198 nodes.mark(n); 199 } 200 } 201 for (LoopExitNode earlyExit : earlyExits) { 202 if (earlyExit.isDeleted()) { 203 continue; 204 } 205 206 FrameState stateAfter = earlyExit.stateAfter(); 207 if (stateAfter != null) { 208 stateAfter.applyToVirtual(node -> nodes.mark(node)); 209 } 210 nodes.mark(earlyExit); 211 for (ProxyNode proxy : earlyExit.proxies()) { 212 nodes.mark(proxy); 213 } 214 } 215 216 final NodeBitMap nonLoopNodes = graph.createNodeBitMap(); 217 for (AbstractBeginNode b : blocks) { 218 if (b.isDeleted()) { 219 continue; 220 } 221 222 for (Node n : b.getBlockNodes()) { 223 if (n instanceof CommitAllocationNode) { 224 for (VirtualObjectNode obj : ((CommitAllocationNode) n).getVirtualObjects()) { 225 markFloating(obj, nodes, nonLoopNodes); 226 } 227 } 228 if (n instanceof MonitorEnterNode) { 229 markFloating(((MonitorEnterNode) n).getMonitorId(), nodes, nonLoopNodes); 230 } 231 for (Node usage : n.usages()) { 232 markFloating(usage, nodes, nonLoopNodes); 233 } 234 } 235 } 236 } 237 238 private static boolean markFloating(Node n, NodeBitMap loopNodes, NodeBitMap nonLoopNodes) { 239 if (loopNodes.isMarked(n)) { 240 return true; 241 } 242 if (nonLoopNodes.isMarked(n)) { 243 return false; 244 } 245 if (n instanceof FixedNode) { 246 return false; 247 } 248 boolean mark = false; 249 if (n instanceof PhiNode) { 250 PhiNode phi = (PhiNode) n; 251 mark = loopNodes.isMarked(phi.merge()); 252 if (mark) { 253 loopNodes.mark(n); 254 } else { 255 nonLoopNodes.mark(n); 256 return false; 257 } 258 } 259 for (Node usage : n.usages()) { 260 if (markFloating(usage, loopNodes, nonLoopNodes)) { 261 mark = true; 262 } 263 } 264 if (!mark && n instanceof GuardNode) { 265 // (gd) this is only OK if we are not going to make loop transforms based on this 266 assert !((GuardNode) n).graph().hasValueProxies(); 267 mark = true; 268 } 269 if (mark) { 270 loopNodes.mark(n); 271 return true; 272 } 273 nonLoopNodes.mark(n); 274 return false; 275 } 276 277 public static NodeIterable<AbstractBeginNode> toHirBlocks(final Iterable<Block> blocks) { 278 return new NodeIterable<AbstractBeginNode>() { 279 280 @Override 281 public Iterator<AbstractBeginNode> iterator() { 282 final Iterator<Block> it = blocks.iterator(); 283 return new Iterator<AbstractBeginNode>() { 284 285 @Override 286 public void remove() { 287 throw new UnsupportedOperationException(); 288 } 289 290 @Override 291 public AbstractBeginNode next() { 292 return it.next().getBeginNode(); 293 } 294 295 @Override 296 public boolean hasNext() { 297 return it.hasNext(); 298 } 299 }; 300 } 301 302 }; 303 } 304 305 public static NodeIterable<LoopExitNode> toHirExits(final Iterable<Block> blocks) { 306 return new NodeIterable<LoopExitNode>() { 307 308 @Override 309 public Iterator<LoopExitNode> iterator() { 310 final Iterator<Block> it = blocks.iterator(); 311 return new Iterator<LoopExitNode>() { 312 313 @Override 314 public void remove() { 315 throw new UnsupportedOperationException(); 316 } 317 318 @Override 319 public LoopExitNode next() { 320 return (LoopExitNode) it.next().getBeginNode(); 321 } 322 323 @Override 324 public boolean hasNext() { 325 return it.hasNext(); 326 } 327 }; 328 } 329 330 }; 331 } 332 333 /** 334 * Merges the early exits (i.e. loop exits) that were duplicated as part of this fragment, with 335 * the original fragment's exits. 336 */ 337 protected void mergeEarlyExits() { 338 assert isDuplicate(); 339 StructuredGraph graph = graph(); 340 for (AbstractBeginNode earlyExit : LoopFragment.toHirBlocks(original().loop().loop().getExits())) { 341 LoopExitNode loopEarlyExit = (LoopExitNode) earlyExit; 342 FixedNode next = loopEarlyExit.next(); 343 if (loopEarlyExit.isDeleted() || !this.original().contains(loopEarlyExit)) { 344 continue; 345 } 346 AbstractBeginNode newEarlyExit = getDuplicatedNode(loopEarlyExit); 347 if (newEarlyExit == null) { 348 continue; 349 } 350 MergeNode merge = graph.add(new MergeNode()); 351 EndNode originalEnd = graph.add(new EndNode()); 352 EndNode newEnd = graph.add(new EndNode()); 353 merge.addForwardEnd(originalEnd); 354 merge.addForwardEnd(newEnd); 355 loopEarlyExit.setNext(originalEnd); 356 newEarlyExit.setNext(newEnd); 357 merge.setNext(next); 358 359 FrameState exitState = loopEarlyExit.stateAfter(); 360 if (exitState != null) { 361 FrameState originalExitState = exitState; 362 exitState = exitState.duplicateWithVirtualState(); 363 loopEarlyExit.setStateAfter(exitState); 364 merge.setStateAfter(originalExitState); 365 /* 366 * Using the old exit's state as the merge's state is necessary because some of the 367 * VirtualState nodes contained in the old exit's state may be shared by other 368 * dominated VirtualStates. Those dominated virtual states need to see the 369 * proxy->phi update that are applied below. 370 * 371 * We now update the original fragment's nodes accordingly: 372 */ 373 originalExitState.applyToVirtual(node -> original.nodes.clearAndGrow(node)); 374 exitState.applyToVirtual(node -> original.nodes.markAndGrow(node)); 375 } 376 FrameState finalExitState = exitState; 377 378 for (Node anchored : loopEarlyExit.anchored().snapshot()) { 379 anchored.replaceFirstInput(loopEarlyExit, merge); 380 } 381 382 boolean newEarlyExitIsLoopExit = newEarlyExit instanceof LoopExitNode; 383 for (ProxyNode vpn : loopEarlyExit.proxies().snapshot()) { 384 if (vpn.hasNoUsages()) { 385 continue; 386 } 387 if (vpn.value() == null) { 388 assert vpn instanceof GuardProxyNode; 389 vpn.replaceAtUsages(null); 390 continue; 391 } 392 final ValueNode replaceWith; 393 ValueNode newVpn = prim(newEarlyExitIsLoopExit ? vpn : vpn.value()); 394 if (newVpn != null) { 395 PhiNode phi; 396 if (vpn instanceof ValueProxyNode) { 397 phi = graph.addWithoutUnique(new ValuePhiNode(vpn.stamp(), merge)); 398 } else if (vpn instanceof GuardProxyNode) { 399 phi = graph.addWithoutUnique(new GuardPhiNode(merge)); 400 } else { 401 throw GraalError.shouldNotReachHere(); 402 } 403 phi.addInput(vpn); 404 phi.addInput(newVpn); 405 replaceWith = phi; 406 } else { 407 replaceWith = vpn.value(); 408 } 409 vpn.replaceAtMatchingUsages(replaceWith, usage -> { 410 if (merge.isPhiAtMerge(usage)) { 411 return false; 412 } 413 if (usage instanceof VirtualState) { 414 VirtualState stateUsage = (VirtualState) usage; 415 if (finalExitState != null && finalExitState.isPartOfThisState(stateUsage)) { 416 return false; 417 } 418 } 419 return true; 420 }); 421 } 422 } 423 } 424 }