1 /* 2 * Copyright (c) 2011, 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.nodes.util; 26 27 import java.util.ArrayList; 28 import java.util.Arrays; 29 import java.util.Collection; 30 import java.util.Collections; 31 import java.util.Iterator; 32 import java.util.List; 33 import java.util.Objects; 34 import java.util.function.BiFunction; 35 36 import jdk.internal.vm.compiler.collections.EconomicMap; 37 import jdk.internal.vm.compiler.collections.EconomicSet; 38 import jdk.internal.vm.compiler.collections.Equivalence; 39 import jdk.internal.vm.compiler.collections.MapCursor; 40 import org.graalvm.compiler.bytecode.Bytecode; 41 import org.graalvm.compiler.code.SourceStackTraceBailoutException; 42 import org.graalvm.compiler.core.common.spi.ConstantFieldProvider; 43 import org.graalvm.compiler.core.common.type.ObjectStamp; 44 import org.graalvm.compiler.debug.DebugContext; 45 import org.graalvm.compiler.graph.Graph; 46 import org.graalvm.compiler.graph.Node; 47 import org.graalvm.compiler.graph.NodeBitMap; 48 import org.graalvm.compiler.graph.NodeSourcePosition; 49 import org.graalvm.compiler.graph.NodeStack; 50 import org.graalvm.compiler.graph.Position; 51 import org.graalvm.compiler.graph.iterators.NodeIterable; 52 import org.graalvm.compiler.graph.spi.SimplifierTool; 53 import org.graalvm.compiler.nodes.AbstractBeginNode; 54 import org.graalvm.compiler.nodes.AbstractEndNode; 55 import org.graalvm.compiler.nodes.AbstractMergeNode; 56 import org.graalvm.compiler.nodes.ConstantNode; 57 import org.graalvm.compiler.nodes.ControlSplitNode; 58 import org.graalvm.compiler.nodes.FixedNode; 59 import org.graalvm.compiler.nodes.FixedWithNextNode; 60 import org.graalvm.compiler.nodes.FrameState; 61 import org.graalvm.compiler.nodes.GuardNode; 62 import org.graalvm.compiler.nodes.LoopBeginNode; 63 import org.graalvm.compiler.nodes.LoopEndNode; 64 import org.graalvm.compiler.nodes.LoopExitNode; 65 import org.graalvm.compiler.nodes.NodeView; 66 import org.graalvm.compiler.nodes.PhiNode; 67 import org.graalvm.compiler.nodes.PiNode; 68 import org.graalvm.compiler.nodes.ProxyNode; 69 import org.graalvm.compiler.nodes.StateSplit; 70 import org.graalvm.compiler.nodes.StructuredGraph; 71 import org.graalvm.compiler.nodes.ValueNode; 72 import org.graalvm.compiler.nodes.ValuePhiNode; 73 import org.graalvm.compiler.nodes.ValueProxyNode; 74 import org.graalvm.compiler.nodes.java.LoadIndexedNode; 75 import org.graalvm.compiler.nodes.java.MethodCallTargetNode; 76 import org.graalvm.compiler.nodes.java.MonitorIdNode; 77 import org.graalvm.compiler.nodes.spi.ArrayLengthProvider; 78 import org.graalvm.compiler.nodes.spi.ArrayLengthProvider.FindLengthMode; 79 import org.graalvm.compiler.nodes.spi.LimitedValueProxy; 80 import org.graalvm.compiler.nodes.spi.LoweringProvider; 81 import org.graalvm.compiler.nodes.spi.ValueProxy; 82 import org.graalvm.compiler.nodes.spi.VirtualizerTool; 83 import org.graalvm.compiler.nodes.type.StampTool; 84 import org.graalvm.compiler.nodes.virtual.VirtualArrayNode; 85 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode; 86 import org.graalvm.compiler.options.Option; 87 import org.graalvm.compiler.options.OptionKey; 88 import org.graalvm.compiler.options.OptionType; 89 import org.graalvm.compiler.options.OptionValues; 90 91 import jdk.vm.ci.code.BailoutException; 92 import jdk.vm.ci.code.BytecodePosition; 93 import jdk.vm.ci.meta.Assumptions; 94 import jdk.vm.ci.meta.Constant; 95 import jdk.vm.ci.meta.ConstantReflectionProvider; 96 import jdk.vm.ci.meta.JavaKind; 97 import jdk.vm.ci.meta.MetaAccessProvider; 98 import jdk.vm.ci.meta.ResolvedJavaMethod; 99 import jdk.vm.ci.meta.ResolvedJavaType; 100 101 public class GraphUtil { 102 103 public static class Options { 104 @Option(help = "Verify that there are no new unused nodes when performing killCFG", type = OptionType.Debug)// 105 public static final OptionKey<Boolean> VerifyKillCFGUnusedNodes = new OptionKey<>(false); 106 } 107 108 private static void killCFGInner(FixedNode node) { 109 EconomicSet<Node> markedNodes = EconomicSet.create(); 110 EconomicMap<AbstractMergeNode, List<AbstractEndNode>> unmarkedMerges = EconomicMap.create(); 111 112 // Detach this node from CFG 113 node.replaceAtPredecessor(null); 114 115 markFixedNodes(node, markedNodes, unmarkedMerges); 116 117 fixSurvivingAffectedMerges(markedNodes, unmarkedMerges); 118 119 DebugContext debug = node.getDebug(); 120 debug.dump(DebugContext.DETAILED_LEVEL, node.graph(), "After fixing merges (killCFG %s)", node); 121 122 // Mark non-fixed nodes 123 markUsages(markedNodes); 124 125 // Detach marked nodes from non-marked nodes 126 for (Node marked : markedNodes) { 127 for (Node input : marked.inputs()) { 128 if (!markedNodes.contains(input)) { 129 marked.replaceFirstInput(input, null); 130 tryKillUnused(input); 131 } 132 } 133 } 134 debug.dump(DebugContext.VERY_DETAILED_LEVEL, node.graph(), "After disconnecting non-marked inputs (killCFG %s)", node); 135 // Kill marked nodes 136 for (Node marked : markedNodes) { 137 if (marked.isAlive()) { 138 marked.markDeleted(); 139 } 140 } 141 } 142 143 private static void markFixedNodes(FixedNode node, EconomicSet<Node> markedNodes, EconomicMap<AbstractMergeNode, List<AbstractEndNode>> unmarkedMerges) { 144 NodeStack workStack = new NodeStack(); 145 workStack.push(node); 146 while (!workStack.isEmpty()) { 147 Node fixedNode = workStack.pop(); 148 markedNodes.add(fixedNode); 149 if (fixedNode instanceof AbstractMergeNode) { 150 unmarkedMerges.removeKey((AbstractMergeNode) fixedNode); 151 } 152 while (fixedNode instanceof FixedWithNextNode) { 153 fixedNode = ((FixedWithNextNode) fixedNode).next(); 154 if (fixedNode != null) { 155 markedNodes.add(fixedNode); 156 } 157 } 158 if (fixedNode instanceof ControlSplitNode) { 159 for (Node successor : fixedNode.successors()) { 160 workStack.push(successor); 161 } 162 } else if (fixedNode instanceof AbstractEndNode) { 163 AbstractEndNode end = (AbstractEndNode) fixedNode; 164 AbstractMergeNode merge = end.merge(); 165 if (merge != null) { 166 assert !markedNodes.contains(merge) || (merge instanceof LoopBeginNode && end instanceof LoopEndNode) : merge; 167 if (merge instanceof LoopBeginNode) { 168 if (end == ((LoopBeginNode) merge).forwardEnd()) { 169 workStack.push(merge); 170 continue; 171 } 172 if (markedNodes.contains(merge)) { 173 continue; 174 } 175 } 176 List<AbstractEndNode> endsSeen = unmarkedMerges.get(merge); 177 if (endsSeen == null) { 178 endsSeen = new ArrayList<>(merge.forwardEndCount()); 179 unmarkedMerges.put(merge, endsSeen); 180 } 181 endsSeen.add(end); 182 if (!(end instanceof LoopEndNode) && endsSeen.size() == merge.forwardEndCount()) { 183 assert merge.forwardEnds().filter(n -> !markedNodes.contains(n)).isEmpty(); 184 // all this merge's forward ends are marked: it needs to be killed 185 workStack.push(merge); 186 } 187 } 188 } 189 } 190 } 191 192 private static void fixSurvivingAffectedMerges(EconomicSet<Node> markedNodes, EconomicMap<AbstractMergeNode, List<AbstractEndNode>> unmarkedMerges) { 193 MapCursor<AbstractMergeNode, List<AbstractEndNode>> cursor = unmarkedMerges.getEntries(); 194 while (cursor.advance()) { 195 AbstractMergeNode merge = cursor.getKey(); 196 for (AbstractEndNode end : cursor.getValue()) { 197 merge.removeEnd(end); 198 } 199 if (merge.phiPredecessorCount() == 1) { 200 if (merge instanceof LoopBeginNode) { 201 LoopBeginNode loopBegin = (LoopBeginNode) merge; 202 assert merge.forwardEndCount() == 1; 203 for (LoopExitNode loopExit : loopBegin.loopExits().snapshot()) { 204 if (markedNodes.contains(loopExit)) { 205 /* 206 * disconnect from loop begin so that reduceDegenerateLoopBegin doesn't 207 * transform it into a new beginNode 208 */ 209 loopExit.replaceFirstInput(loopBegin, null); 210 } 211 } 212 merge.graph().reduceDegenerateLoopBegin(loopBegin); 213 } else { 214 merge.graph().reduceTrivialMerge(merge); 215 } 216 } else { 217 assert merge.phiPredecessorCount() > 1 : merge; 218 } 219 } 220 } 221 222 private static void markUsages(EconomicSet<Node> markedNodes) { 223 NodeStack workStack = new NodeStack(markedNodes.size() + 4); 224 for (Node marked : markedNodes) { 225 workStack.push(marked); 226 } 227 while (!workStack.isEmpty()) { 228 Node marked = workStack.pop(); 229 for (Node usage : marked.usages()) { 230 if (!markedNodes.contains(usage)) { 231 workStack.push(usage); 232 markedNodes.add(usage); 233 } 234 } 235 } 236 } 237 238 @SuppressWarnings("try") 239 public static void killCFG(FixedNode node) { 240 DebugContext debug = node.getDebug(); 241 try (DebugContext.Scope scope = debug.scope("KillCFG", node)) { 242 EconomicSet<Node> unusedNodes = null; 243 EconomicSet<Node> unsafeNodes = null; 244 Graph.NodeEventScope nodeEventScope = null; 245 OptionValues options = node.getOptions(); 246 boolean verifyGraalGraphEdges = Graph.Options.VerifyGraalGraphEdges.getValue(options); 247 boolean verifyKillCFGUnusedNodes = GraphUtil.Options.VerifyKillCFGUnusedNodes.getValue(options); 248 if (verifyGraalGraphEdges) { 249 unsafeNodes = collectUnsafeNodes(node.graph()); 250 } 251 if (verifyKillCFGUnusedNodes) { 252 EconomicSet<Node> collectedUnusedNodes = unusedNodes = EconomicSet.create(Equivalence.IDENTITY); 253 nodeEventScope = node.graph().trackNodeEvents(new Graph.NodeEventListener() { 254 @Override 255 public void changed(Graph.NodeEvent e, Node n) { 256 if (e == Graph.NodeEvent.ZERO_USAGES && isFloatingNode(n) && !(n instanceof GuardNode)) { 257 collectedUnusedNodes.add(n); 258 } 259 } 260 }); 261 } 262 debug.dump(DebugContext.VERY_DETAILED_LEVEL, node.graph(), "Before killCFG %s", node); 263 killCFGInner(node); 264 debug.dump(DebugContext.VERY_DETAILED_LEVEL, node.graph(), "After killCFG %s", node); 265 if (verifyGraalGraphEdges) { 266 EconomicSet<Node> newUnsafeNodes = collectUnsafeNodes(node.graph()); 267 newUnsafeNodes.removeAll(unsafeNodes); 268 assert newUnsafeNodes.isEmpty() : "New unsafe nodes: " + newUnsafeNodes; 269 } 270 if (verifyKillCFGUnusedNodes) { 271 nodeEventScope.close(); 272 Iterator<Node> iterator = unusedNodes.iterator(); 273 while (iterator.hasNext()) { 274 Node curNode = iterator.next(); 275 if (curNode.isDeleted()) { 276 iterator.remove(); 277 } 278 } 279 assert unusedNodes.isEmpty() : "New unused nodes: " + unusedNodes; 280 } 281 } catch (Throwable t) { 282 throw debug.handle(t); 283 } 284 } 285 286 /** 287 * Collects all node in the graph which have non-optional inputs that are null. 288 */ 289 private static EconomicSet<Node> collectUnsafeNodes(Graph graph) { 290 EconomicSet<Node> unsafeNodes = EconomicSet.create(Equivalence.IDENTITY); 291 for (Node n : graph.getNodes()) { 292 for (Position pos : n.inputPositions()) { 293 Node input = pos.get(n); 294 if (input == null) { 295 if (!pos.isInputOptional()) { 296 unsafeNodes.add(n); 297 } 298 } 299 } 300 } 301 return unsafeNodes; 302 } 303 304 public static boolean isFloatingNode(Node n) { 305 return !(n instanceof FixedNode); 306 } 307 308 private static boolean checkKill(Node node, boolean mayKillGuard) { 309 node.assertTrue(mayKillGuard || !(node instanceof GuardNode), "must not be a guard node %s", node); 310 node.assertTrue(node.isAlive(), "must be alive"); 311 node.assertTrue(node.hasNoUsages(), "cannot kill node %s because of usages: %s", node, node.usages()); 312 node.assertTrue(node.predecessor() == null, "cannot kill node %s because of predecessor: %s", node, node.predecessor()); 313 return true; 314 } 315 316 public static void killWithUnusedFloatingInputs(Node node) { 317 killWithUnusedFloatingInputs(node, false); 318 } 319 320 public static void killWithUnusedFloatingInputs(Node node, boolean mayKillGuard) { 321 assert checkKill(node, mayKillGuard); 322 node.markDeleted(); 323 outer: for (Node in : node.inputs()) { 324 if (in.isAlive()) { 325 in.removeUsage(node); 326 if (in.hasNoUsages()) { 327 node.maybeNotifyZeroUsages(in); 328 } 329 if (isFloatingNode(in)) { 330 if (in.hasNoUsages()) { 331 if (in instanceof GuardNode) { 332 // Guard nodes are only killed if their anchor dies. 333 } else { 334 killWithUnusedFloatingInputs(in); 335 } 336 } else if (in instanceof PhiNode) { 337 for (Node use : in.usages()) { 338 if (use != in) { 339 continue outer; 340 } 341 } 342 in.replaceAtUsages(null); 343 killWithUnusedFloatingInputs(in); 344 } 345 } 346 } 347 } 348 } 349 350 /** 351 * Removes all nodes created after the {@code mark}, assuming no "old" nodes point to "new" 352 * nodes. 353 */ 354 public static void removeNewNodes(Graph graph, Graph.Mark mark) { 355 assert checkNoOldToNewEdges(graph, mark); 356 for (Node n : graph.getNewNodes(mark)) { 357 n.markDeleted(); 358 for (Node in : n.inputs()) { 359 in.removeUsage(n); 360 } 361 } 362 } 363 364 private static boolean checkNoOldToNewEdges(Graph graph, Graph.Mark mark) { 365 for (Node old : graph.getNodes()) { 366 if (graph.isNew(mark, old)) { 367 break; 368 } 369 for (Node n : old.successors()) { 370 assert !graph.isNew(mark, n) : old + " -> " + n; 371 } 372 for (Node n : old.inputs()) { 373 assert !graph.isNew(mark, n) : old + " -> " + n; 374 } 375 } 376 return true; 377 } 378 379 public static void removeFixedWithUnusedInputs(FixedWithNextNode fixed) { 380 if (fixed instanceof StateSplit) { 381 FrameState stateAfter = ((StateSplit) fixed).stateAfter(); 382 if (stateAfter != null) { 383 ((StateSplit) fixed).setStateAfter(null); 384 if (stateAfter.hasNoUsages()) { 385 killWithUnusedFloatingInputs(stateAfter); 386 } 387 } 388 } 389 unlinkFixedNode(fixed); 390 killWithUnusedFloatingInputs(fixed); 391 } 392 393 public static void unlinkFixedNode(FixedWithNextNode fixed) { 394 assert fixed.next() != null && fixed.predecessor() != null && fixed.isAlive() : fixed; 395 FixedNode next = fixed.next(); 396 fixed.setNext(null); 397 fixed.replaceAtPredecessor(next); 398 } 399 400 public static void checkRedundantPhi(PhiNode phiNode) { 401 if (phiNode.isDeleted() || phiNode.valueCount() == 1) { 402 return; 403 } 404 405 ValueNode singleValue = phiNode.singleValueOrThis(); 406 if (singleValue != phiNode) { 407 Collection<PhiNode> phiUsages = phiNode.usages().filter(PhiNode.class).snapshot(); 408 Collection<ProxyNode> proxyUsages = phiNode.usages().filter(ProxyNode.class).snapshot(); 409 phiNode.replaceAtUsagesAndDelete(singleValue); 410 for (PhiNode phi : phiUsages) { 411 checkRedundantPhi(phi); 412 } 413 for (ProxyNode proxy : proxyUsages) { 414 checkRedundantProxy(proxy); 415 } 416 } 417 } 418 419 public static void checkRedundantProxy(ProxyNode vpn) { 420 if (vpn.isDeleted()) { 421 return; 422 } 423 AbstractBeginNode proxyPoint = vpn.proxyPoint(); 424 if (proxyPoint instanceof LoopExitNode) { 425 LoopExitNode exit = (LoopExitNode) proxyPoint; 426 LoopBeginNode loopBegin = exit.loopBegin(); 427 Node vpnValue = vpn.value(); 428 for (ValueNode v : loopBegin.stateAfter().values()) { 429 ValueNode v2 = v; 430 if (loopBegin.isPhiAtMerge(v2)) { 431 v2 = ((PhiNode) v2).valueAt(loopBegin.forwardEnd()); 432 } 433 if (vpnValue == v2) { 434 Collection<PhiNode> phiUsages = vpn.usages().filter(PhiNode.class).snapshot(); 435 Collection<ProxyNode> proxyUsages = vpn.usages().filter(ProxyNode.class).snapshot(); 436 vpn.replaceAtUsagesAndDelete(vpnValue); 437 for (PhiNode phi : phiUsages) { 438 checkRedundantPhi(phi); 439 } 440 for (ProxyNode proxy : proxyUsages) { 441 checkRedundantProxy(proxy); 442 } 443 return; 444 } 445 } 446 } 447 } 448 449 /** 450 * Remove loop header without loop ends. This can happen with degenerated loops like this one: 451 * 452 * <pre> 453 * for (;;) { 454 * try { 455 * break; 456 * } catch (UnresolvedException iioe) { 457 * } 458 * } 459 * </pre> 460 */ 461 public static void normalizeLoops(StructuredGraph graph) { 462 boolean loopRemoved = false; 463 for (LoopBeginNode begin : graph.getNodes(LoopBeginNode.TYPE)) { 464 if (begin.loopEnds().isEmpty()) { 465 assert begin.forwardEndCount() == 1; 466 graph.reduceDegenerateLoopBegin(begin); 467 loopRemoved = true; 468 } else { 469 normalizeLoopBegin(begin); 470 } 471 } 472 473 if (loopRemoved) { 474 /* 475 * Removing a degenerated loop can make non-loop phi functions unnecessary. Therefore, 476 * we re-check all phi functions and remove redundant ones. 477 */ 478 for (Node node : graph.getNodes()) { 479 if (node instanceof PhiNode) { 480 checkRedundantPhi((PhiNode) node); 481 } 482 } 483 } 484 } 485 486 private static void normalizeLoopBegin(LoopBeginNode begin) { 487 // Delete unnecessary loop phi functions, i.e., phi functions where all inputs are either 488 // the same or the phi itself. 489 for (PhiNode phi : begin.phis().snapshot()) { 490 GraphUtil.checkRedundantPhi(phi); 491 } 492 for (LoopExitNode exit : begin.loopExits()) { 493 for (ProxyNode vpn : exit.proxies().snapshot()) { 494 GraphUtil.checkRedundantProxy(vpn); 495 } 496 } 497 } 498 499 /** 500 * Gets an approximate source code location for a node if possible. 501 * 502 * @return the StackTraceElements if an approximate source location is found, null otherwise 503 */ 504 public static StackTraceElement[] approxSourceStackTraceElement(Node node) { 505 NodeSourcePosition position = node.getNodeSourcePosition(); 506 if (position != null) { 507 // use GraphBuilderConfiguration and enable trackNodeSourcePosition to get better source 508 // positions. 509 return approxSourceStackTraceElement(position); 510 } 511 ArrayList<StackTraceElement> elements = new ArrayList<>(); 512 Node n = node; 513 while (n != null) { 514 if (n instanceof MethodCallTargetNode) { 515 elements.add(((MethodCallTargetNode) n).targetMethod().asStackTraceElement(-1)); 516 n = ((MethodCallTargetNode) n).invoke().asNode(); 517 } 518 519 if (n instanceof StateSplit) { 520 FrameState state = ((StateSplit) n).stateAfter(); 521 elements.addAll(Arrays.asList(approxSourceStackTraceElement(state))); 522 break; 523 } 524 n = n.predecessor(); 525 } 526 return elements.toArray(new StackTraceElement[elements.size()]); 527 } 528 529 /** 530 * Gets an approximate source code location for frame state. 531 * 532 * @return the StackTraceElements if an approximate source location is found, null otherwise 533 */ 534 public static StackTraceElement[] approxSourceStackTraceElement(FrameState frameState) { 535 ArrayList<StackTraceElement> elements = new ArrayList<>(); 536 FrameState state = frameState; 537 while (state != null) { 538 Bytecode code = state.getCode(); 539 if (code != null) { 540 elements.add(code.asStackTraceElement(state.bci - 1)); 541 } 542 state = state.outerFrameState(); 543 } 544 return elements.toArray(new StackTraceElement[0]); 545 } 546 547 /** 548 * Gets approximate stack trace elements for a bytecode position. 549 */ 550 public static StackTraceElement[] approxSourceStackTraceElement(BytecodePosition bytecodePosition) { 551 ArrayList<StackTraceElement> elements = new ArrayList<>(); 552 BytecodePosition position = bytecodePosition; 553 while (position != null) { 554 ResolvedJavaMethod method = position.getMethod(); 555 if (method != null) { 556 elements.add(method.asStackTraceElement(position.getBCI())); 557 } 558 position = position.getCaller(); 559 } 560 return elements.toArray(new StackTraceElement[0]); 561 } 562 563 /** 564 * Gets an approximate source code location for a node, encoded as an exception, if possible. 565 * 566 * @return the exception with the location 567 */ 568 public static RuntimeException approxSourceException(Node node, Throwable cause) { 569 final StackTraceElement[] elements = approxSourceStackTraceElement(node); 570 return createBailoutException(cause == null ? "" : cause.getMessage(), cause, elements); 571 } 572 573 /** 574 * Creates a bailout exception with the given stack trace elements and message. 575 * 576 * @param message the message of the exception 577 * @param elements the stack trace elements 578 * @return the exception 579 */ 580 public static BailoutException createBailoutException(String message, Throwable cause, StackTraceElement[] elements) { 581 return SourceStackTraceBailoutException.create(cause, message, elements); 582 } 583 584 /** 585 * Gets an approximate source code location for a node if possible. 586 * 587 * @return a file name and source line number in stack trace format (e.g. "String.java:32") if 588 * an approximate source location is found, null otherwise 589 */ 590 public static String approxSourceLocation(Node node) { 591 StackTraceElement[] stackTraceElements = approxSourceStackTraceElement(node); 592 if (stackTraceElements != null && stackTraceElements.length > 0) { 593 StackTraceElement top = stackTraceElements[0]; 594 if (top.getFileName() != null && top.getLineNumber() >= 0) { 595 return top.getFileName() + ":" + top.getLineNumber(); 596 } 597 } 598 return null; 599 } 600 601 /** 602 * Returns a string representation of the given collection of objects. 603 * 604 * @param objects The {@link Iterable} that will be used to iterate over the objects. 605 * @return A string of the format "[a, b, ...]". 606 */ 607 public static String toString(Iterable<?> objects) { 608 StringBuilder str = new StringBuilder(); 609 str.append("["); 610 for (Object o : objects) { 611 str.append(o).append(", "); 612 } 613 if (str.length() > 1) { 614 str.setLength(str.length() - 2); 615 } 616 str.append("]"); 617 return str.toString(); 618 } 619 620 /** 621 * Gets the original value by iterating through all {@link ValueProxy ValueProxies}. 622 * 623 * @param value the start value. 624 * @return the first non-proxy value encountered 625 */ 626 public static ValueNode unproxify(ValueNode value) { 627 if (value instanceof ValueProxy) { 628 return unproxify((ValueProxy) value); 629 } else { 630 return value; 631 } 632 } 633 634 /** 635 * Gets the original value by iterating through all {@link ValueProxy ValueProxies}. 636 * 637 * @param value the start value proxy. 638 * @return the first non-proxy value encountered 639 */ 640 public static ValueNode unproxify(ValueProxy value) { 641 if (value != null) { 642 ValueNode result = value.getOriginalNode(); 643 while (result instanceof ValueProxy) { 644 result = ((ValueProxy) result).getOriginalNode(); 645 } 646 return result; 647 } else { 648 return null; 649 } 650 } 651 652 public static ValueNode skipPi(ValueNode node) { 653 ValueNode n = node; 654 while (n instanceof PiNode) { 655 PiNode piNode = (PiNode) n; 656 n = piNode.getOriginalNode(); 657 } 658 return n; 659 } 660 661 public static ValueNode skipPiWhileNonNull(ValueNode node) { 662 ValueNode n = node; 663 while (n instanceof PiNode) { 664 PiNode piNode = (PiNode) n; 665 ObjectStamp originalStamp = (ObjectStamp) piNode.getOriginalNode().stamp(NodeView.DEFAULT); 666 if (originalStamp.nonNull()) { 667 n = piNode.getOriginalNode(); 668 } else { 669 break; 670 } 671 } 672 return n; 673 } 674 675 /** 676 * Returns the length of the array described by the value parameter, or null if it is not 677 * available. Details of the different modes are documented in {@link FindLengthMode}. 678 * 679 * @param value The start value. 680 * @param mode The mode as documented in {@link FindLengthMode}. 681 * @return The array length if one was found, or null otherwise. 682 */ 683 public static ValueNode arrayLength(ValueNode value, FindLengthMode mode, ConstantReflectionProvider constantReflection) { 684 Objects.requireNonNull(mode); 685 686 ValueNode current = value; 687 do { 688 /* 689 * PiArrayNode implements ArrayLengthProvider and ValueProxy. We want to treat it as an 690 * ArrayLengthProvider, therefore we check this case first. 691 */ 692 if (current instanceof ArrayLengthProvider) { 693 return ((ArrayLengthProvider) current).findLength(mode, constantReflection); 694 695 } else if (current instanceof ValuePhiNode) { 696 return phiArrayLength((ValuePhiNode) current, mode, constantReflection); 697 698 } else if (current instanceof ValueProxyNode) { 699 ValueProxyNode proxy = (ValueProxyNode) current; 700 ValueNode length = arrayLength(proxy.getOriginalNode(), mode, constantReflection); 701 if (mode == ArrayLengthProvider.FindLengthMode.CANONICALIZE_READ && length != null && !length.isConstant()) { 702 length = new ValueProxyNode(length, proxy.proxyPoint()); 703 } 704 return length; 705 706 } else if (current instanceof ValueProxy) { 707 /* Written as a loop instead of a recursive call to reduce recursion depth. */ 708 current = ((ValueProxy) current).getOriginalNode(); 709 710 } else { 711 return null; 712 } 713 } while (true); 714 } 715 716 private static ValueNode phiArrayLength(ValuePhiNode phi, ArrayLengthProvider.FindLengthMode mode, ConstantReflectionProvider constantReflection) { 717 if (phi.merge() instanceof LoopBeginNode) { 718 /* Avoid cycle detection by not processing phi functions that could introduce cycles. */ 719 return null; 720 } 721 722 ValueNode singleLength = null; 723 for (int i = 0; i < phi.values().count(); i++) { 724 ValueNode input = phi.values().get(i); 725 ValueNode length = arrayLength(input, mode, constantReflection); 726 if (length == null) { 727 return null; 728 } 729 assert length.stamp(NodeView.DEFAULT).getStackKind() == JavaKind.Int; 730 731 if (i == 0) { 732 assert singleLength == null; 733 singleLength = length; 734 } else if (singleLength == length) { 735 /* Nothing to do, still having a single length. */ 736 } else { 737 return null; 738 } 739 } 740 return singleLength; 741 } 742 743 /** 744 * Tries to find an original value of the given node by traversing through proxies and 745 * unambiguous phis. Note that this method will perform an exhaustive search through phis. It is 746 * intended to be used during graph building, when phi nodes aren't yet canonicalized. 747 * 748 * @param value The node whose original value should be determined. 749 * @return The original value (which might be the input value itself). 750 */ 751 public static ValueNode originalValue(ValueNode value) { 752 ValueNode result = originalValueSimple(value); 753 assert result != null; 754 return result; 755 } 756 757 private static ValueNode originalValueSimple(ValueNode value) { 758 /* The very simple case: look through proxies. */ 759 ValueNode cur = originalValueForProxy(value); 760 761 while (cur instanceof PhiNode) { 762 /* 763 * We found a phi function. Check if we can analyze it without allocating temporary data 764 * structures. 765 */ 766 PhiNode phi = (PhiNode) cur; 767 768 ValueNode phiSingleValue = null; 769 int count = phi.valueCount(); 770 for (int i = 0; i < count; ++i) { 771 ValueNode phiCurValue = originalValueForProxy(phi.valueAt(i)); 772 if (phiCurValue == phi) { 773 /* Simple cycle, we can ignore the input value. */ 774 } else if (phiSingleValue == null) { 775 /* The first input. */ 776 phiSingleValue = phiCurValue; 777 } else if (phiSingleValue != phiCurValue) { 778 /* Another input that is different from the first input. */ 779 780 if (phiSingleValue instanceof PhiNode || phiCurValue instanceof PhiNode) { 781 /* 782 * We have two different input values for the phi function, and at least one 783 * of the inputs is another phi function. We need to do a complicated 784 * exhaustive check. 785 */ 786 return originalValueForComplicatedPhi(phi, new NodeBitMap(value.graph())); 787 } else { 788 /* 789 * We have two different input values for the phi function, but none of them 790 * is another phi function. This phi function cannot be reduce any further, 791 * so the phi function is the original value. 792 */ 793 return phi; 794 } 795 } 796 } 797 798 /* 799 * Successfully reduced the phi function to a single input value. The single input value 800 * can itself be a phi function again, so we might take another loop iteration. 801 */ 802 assert phiSingleValue != null; 803 cur = phiSingleValue; 804 } 805 806 /* We reached a "normal" node, which is the original value. */ 807 assert !(cur instanceof LimitedValueProxy) && !(cur instanceof PhiNode); 808 return cur; 809 } 810 811 private static ValueNode originalValueForProxy(ValueNode value) { 812 ValueNode cur = value; 813 while (cur instanceof LimitedValueProxy) { 814 cur = ((LimitedValueProxy) cur).getOriginalNode(); 815 } 816 return cur; 817 } 818 819 /** 820 * Handling for complicated nestings of phi functions. We need to reduce phi functions 821 * recursively, and need a temporary map of visited nodes to avoid endless recursion of cycles. 822 */ 823 private static ValueNode originalValueForComplicatedPhi(PhiNode phi, NodeBitMap visited) { 824 if (visited.isMarked(phi)) { 825 /* 826 * Found a phi function that was already seen. Either a cycle, or just a second phi 827 * input to a path we have already processed. 828 */ 829 return null; 830 } 831 visited.mark(phi); 832 833 ValueNode phiSingleValue = null; 834 int count = phi.valueCount(); 835 for (int i = 0; i < count; ++i) { 836 ValueNode phiCurValue = originalValueForProxy(phi.valueAt(i)); 837 if (phiCurValue instanceof PhiNode) { 838 /* Recursively process a phi function input. */ 839 phiCurValue = originalValueForComplicatedPhi((PhiNode) phiCurValue, visited); 840 } 841 842 if (phiCurValue == null) { 843 /* Cycle to a phi function that was already seen. We can ignore this input. */ 844 } else if (phiSingleValue == null) { 845 /* The first input. */ 846 phiSingleValue = phiCurValue; 847 } else if (phiCurValue != phiSingleValue) { 848 /* 849 * Another input that is different from the first input. Since we already 850 * recursively looked through other phi functions, we now know that this phi 851 * function cannot be reduce any further, so the phi function is the original value. 852 */ 853 return phi; 854 } 855 } 856 return phiSingleValue; 857 } 858 859 public static boolean tryKillUnused(Node node) { 860 if (node.isAlive() && isFloatingNode(node) && node.hasNoUsages() && !(node instanceof GuardNode)) { 861 killWithUnusedFloatingInputs(node); 862 return true; 863 } 864 return false; 865 } 866 867 /** 868 * Returns an iterator that will return the given node followed by all its predecessors, up 869 * until the point where {@link Node#predecessor()} returns null. 870 * 871 * @param start the node at which to start iterating 872 */ 873 public static NodeIterable<FixedNode> predecessorIterable(final FixedNode start) { 874 return new NodeIterable<FixedNode>() { 875 @Override 876 public Iterator<FixedNode> iterator() { 877 return new Iterator<FixedNode>() { 878 public FixedNode current = start; 879 880 @Override 881 public boolean hasNext() { 882 return current != null; 883 } 884 885 @Override 886 public FixedNode next() { 887 try { 888 return current; 889 } finally { 890 current = (FixedNode) current.predecessor(); 891 } 892 } 893 }; 894 } 895 }; 896 } 897 898 private static final class DefaultSimplifierTool implements SimplifierTool { 899 private final MetaAccessProvider metaAccess; 900 private final ConstantReflectionProvider constantReflection; 901 private final ConstantFieldProvider constantFieldProvider; 902 private final boolean canonicalizeReads; 903 private final Assumptions assumptions; 904 private final OptionValues options; 905 private final LoweringProvider loweringProvider; 906 907 DefaultSimplifierTool(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider, boolean canonicalizeReads, 908 Assumptions assumptions, OptionValues options, LoweringProvider loweringProvider) { 909 this.metaAccess = metaAccess; 910 this.constantReflection = constantReflection; 911 this.constantFieldProvider = constantFieldProvider; 912 this.canonicalizeReads = canonicalizeReads; 913 this.assumptions = assumptions; 914 this.options = options; 915 this.loweringProvider = loweringProvider; 916 } 917 918 @Override 919 public MetaAccessProvider getMetaAccess() { 920 return metaAccess; 921 } 922 923 @Override 924 public ConstantReflectionProvider getConstantReflection() { 925 return constantReflection; 926 } 927 928 @Override 929 public ConstantFieldProvider getConstantFieldProvider() { 930 return constantFieldProvider; 931 } 932 933 @Override 934 public boolean canonicalizeReads() { 935 return canonicalizeReads; 936 } 937 938 @Override 939 public boolean allUsagesAvailable() { 940 return true; 941 } 942 943 @Override 944 public void deleteBranch(Node branch) { 945 FixedNode fixedBranch = (FixedNode) branch; 946 fixedBranch.predecessor().replaceFirstSuccessor(fixedBranch, null); 947 GraphUtil.killCFG(fixedBranch); 948 } 949 950 @Override 951 public void removeIfUnused(Node node) { 952 GraphUtil.tryKillUnused(node); 953 } 954 955 @Override 956 public void addToWorkList(Node node) { 957 } 958 959 @Override 960 public void addToWorkList(Iterable<? extends Node> nodes) { 961 } 962 963 @Override 964 public Assumptions getAssumptions() { 965 return assumptions; 966 } 967 968 @Override 969 public OptionValues getOptions() { 970 return options; 971 } 972 973 @Override 974 public Integer smallestCompareWidth() { 975 if (loweringProvider != null) { 976 return loweringProvider.smallestCompareWidth(); 977 } else { 978 return null; 979 } 980 } 981 } 982 983 public static SimplifierTool getDefaultSimplifier(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider, 984 boolean canonicalizeReads, Assumptions assumptions, OptionValues options) { 985 return getDefaultSimplifier(metaAccess, constantReflection, constantFieldProvider, canonicalizeReads, assumptions, options, null); 986 } 987 988 public static SimplifierTool getDefaultSimplifier(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, ConstantFieldProvider constantFieldProvider, 989 boolean canonicalizeReads, Assumptions assumptions, OptionValues options, LoweringProvider loweringProvider) { 990 return new DefaultSimplifierTool(metaAccess, constantReflection, constantFieldProvider, canonicalizeReads, assumptions, options, loweringProvider); 991 } 992 993 public static Constant foldIfConstantAndRemove(ValueNode node, ValueNode constant) { 994 assert node.inputs().contains(constant); 995 if (constant.isConstant()) { 996 node.replaceFirstInput(constant, null); 997 Constant result = constant.asConstant(); 998 tryKillUnused(constant); 999 return result; 1000 } 1001 return null; 1002 } 1003 1004 /** 1005 * Virtualize an array copy. 1006 * 1007 * @param tool the virtualization tool 1008 * @param source the source array 1009 * @param sourceLength the length of the source array 1010 * @param newLength the length of the new array 1011 * @param from the start index in the source array 1012 * @param newComponentType the component type of the new array 1013 * @param elementKind the kind of the new array elements 1014 * @param graph the node graph 1015 * @param virtualArrayProvider a functional provider that returns a new virtual array given the 1016 * component type and length 1017 */ 1018 public static void virtualizeArrayCopy(VirtualizerTool tool, ValueNode source, ValueNode sourceLength, ValueNode newLength, ValueNode from, ResolvedJavaType newComponentType, JavaKind elementKind, 1019 StructuredGraph graph, BiFunction<ResolvedJavaType, Integer, VirtualArrayNode> virtualArrayProvider) { 1020 1021 ValueNode sourceAlias = tool.getAlias(source); 1022 ValueNode replacedSourceLength = tool.getAlias(sourceLength); 1023 ValueNode replacedNewLength = tool.getAlias(newLength); 1024 ValueNode replacedFrom = tool.getAlias(from); 1025 if (!replacedNewLength.isConstant() || !replacedFrom.isConstant() || !replacedSourceLength.isConstant()) { 1026 return; 1027 } 1028 1029 assert newComponentType != null : "An array copy can be virtualized only if the real type of the resulting array is known statically."; 1030 1031 int fromInt = replacedFrom.asJavaConstant().asInt(); 1032 int newLengthInt = replacedNewLength.asJavaConstant().asInt(); 1033 int sourceLengthInt = replacedSourceLength.asJavaConstant().asInt(); 1034 if (sourceAlias instanceof VirtualObjectNode) { 1035 VirtualObjectNode sourceVirtual = (VirtualObjectNode) sourceAlias; 1036 assert sourceLengthInt == sourceVirtual.entryCount(); 1037 } 1038 1039 if (fromInt < 0 || newLengthInt < 0 || fromInt > sourceLengthInt) { 1040 /* Illegal values for either from index, the new length or the source length. */ 1041 return; 1042 } 1043 1044 if (newLengthInt > tool.getMaximumEntryCount()) { 1045 /* The new array size is higher than maximum allowed size of virtualized objects. */ 1046 return; 1047 } 1048 1049 ValueNode[] newEntryState = new ValueNode[newLengthInt]; 1050 int readLength = Math.min(newLengthInt, sourceLengthInt - fromInt); 1051 1052 if (sourceAlias instanceof VirtualObjectNode) { 1053 /* The source array is virtualized, just copy over the values. */ 1054 VirtualObjectNode sourceVirtual = (VirtualObjectNode) sourceAlias; 1055 boolean alwaysAssignable = newComponentType.getJavaKind() == JavaKind.Object && newComponentType.isJavaLangObject(); 1056 for (int i = 0; i < readLength; i++) { 1057 ValueNode entry = tool.getEntry(sourceVirtual, fromInt + i); 1058 if (!alwaysAssignable) { 1059 ResolvedJavaType entryType = StampTool.typeOrNull(entry, tool.getMetaAccess()); 1060 if (entryType == null) { 1061 return; 1062 } 1063 if (!newComponentType.isAssignableFrom(entryType)) { 1064 return; 1065 } 1066 } 1067 newEntryState[i] = entry; 1068 } 1069 } else { 1070 /* The source array is not virtualized, emit index loads. */ 1071 ResolvedJavaType sourceType = StampTool.typeOrNull(sourceAlias, tool.getMetaAccess()); 1072 if (sourceType == null || !sourceType.isArray() || !newComponentType.isAssignableFrom(sourceType.getElementalType())) { 1073 return; 1074 } 1075 for (int i = 0; i < readLength; i++) { 1076 LoadIndexedNode load = new LoadIndexedNode(null, sourceAlias, ConstantNode.forInt(i + fromInt, graph), null, elementKind); 1077 tool.addNode(load); 1078 newEntryState[i] = load; 1079 } 1080 } 1081 if (readLength < newLengthInt) { 1082 /* Pad the copy with the default value of its elment kind. */ 1083 ValueNode defaultValue = ConstantNode.defaultForKind(elementKind, graph); 1084 for (int i = readLength; i < newLengthInt; i++) { 1085 newEntryState[i] = defaultValue; 1086 } 1087 } 1088 /* Perform the replacement. */ 1089 VirtualArrayNode newVirtualArray = virtualArrayProvider.apply(newComponentType, newLengthInt); 1090 tool.createVirtualObject(newVirtualArray, newEntryState, Collections.<MonitorIdNode> emptyList(), false); 1091 tool.replaceWithVirtual(newVirtualArray); 1092 } 1093 }