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