001/*
002 * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.nodes.util;
024
025import java.util.*;
026
027import jdk.internal.jvmci.code.*;
028import jdk.internal.jvmci.meta.*;
029
030import com.oracle.graal.graph.*;
031import com.oracle.graal.graph.iterators.*;
032import com.oracle.graal.graph.spi.*;
033import com.oracle.graal.nodes.*;
034import com.oracle.graal.nodes.java.*;
035import com.oracle.graal.nodes.spi.*;
036
037public class GraphUtil {
038
039    private static final NodePredicate FLOATING = new NodePredicate() {
040
041        @Override
042        public final boolean apply(Node n) {
043            return !(n instanceof FixedNode);
044        }
045    };
046
047    public static void killCFG(Node node, SimplifierTool tool) {
048        assert node.isAlive();
049        if (node instanceof AbstractEndNode) {
050            // We reached a control flow end.
051            AbstractEndNode end = (AbstractEndNode) node;
052            killEnd(end, tool);
053        } else if (node instanceof FixedNode) {
054            // Normal control flow node.
055            /*
056             * We do not take a successor snapshot because this iterator supports concurrent
057             * modifications as long as they do not change the size of the successor list. Not
058             * taking a snapshot allows us to see modifications to other branches that may happen
059             * while processing one branch.
060             */
061            for (Node successor : node.successors()) {
062                killCFG(successor, tool);
063            }
064        }
065        node.replaceAtPredecessor(null);
066        propagateKill(node);
067    }
068
069    public static void killCFG(Node node) {
070        killCFG(node, null);
071    }
072
073    private static void killEnd(AbstractEndNode end, SimplifierTool tool) {
074        AbstractMergeNode merge = end.merge();
075        if (merge != null) {
076            merge.removeEnd(end);
077            StructuredGraph graph = end.graph();
078            if (merge instanceof LoopBeginNode && merge.forwardEndCount() == 0) {
079                // dead loop
080                for (PhiNode phi : merge.phis().snapshot()) {
081                    propagateKill(phi);
082                }
083                LoopBeginNode begin = (LoopBeginNode) merge;
084                // disconnect and delete loop ends & loop exits
085                for (LoopEndNode loopend : begin.loopEnds().snapshot()) {
086                    loopend.predecessor().replaceFirstSuccessor(loopend, null);
087                    loopend.safeDelete();
088                }
089                begin.removeExits();
090                FixedNode loopBody = begin.next();
091                if (loopBody != null) { // for small infinite loops, the body may be killed while
092                                        // killing the loop ends
093                    killCFG(loopBody);
094                }
095                begin.safeDelete();
096            } else if (merge instanceof LoopBeginNode && ((LoopBeginNode) merge).loopEnds().isEmpty()) {
097                // not a loop anymore
098                if (tool != null) {
099                    merge.phis().forEach(phi -> tool.addToWorkList(phi.usages()));
100                }
101                graph.reduceDegenerateLoopBegin((LoopBeginNode) merge);
102            } else if (merge.phiPredecessorCount() == 1) {
103                // not a merge anymore
104                if (tool != null) {
105                    merge.phis().forEach(phi -> tool.addToWorkList(phi.usages()));
106                }
107                graph.reduceTrivialMerge(merge);
108            }
109        }
110    }
111
112    public static NodePredicate isFloatingNode() {
113        return FLOATING;
114    }
115
116    private static void propagateKill(Node node) {
117        if (node != null && node.isAlive()) {
118            node.markDeleted();
119
120            node.acceptInputs((n, in) -> {
121                if (in.isAlive()) {
122                    in.removeUsage(n);
123                    if (in.hasNoUsages() && !(in instanceof FixedNode)) {
124                        killWithUnusedFloatingInputs(in);
125                    }
126                }
127            });
128
129            ArrayList<Node> usageToKill = null;
130            for (Node usage : node.usages()) {
131                if (usage.isAlive() && !(usage instanceof FixedNode)) {
132                    if (usageToKill == null) {
133                        usageToKill = new ArrayList<>();
134                    }
135                    usageToKill.add(usage);
136                }
137            }
138            if (usageToKill != null) {
139                for (Node usage : usageToKill) {
140                    if (usage.isAlive()) {
141                        if (usage instanceof PhiNode) {
142                            usage.replaceFirstInput(node, null);
143                        } else {
144                            propagateKill(usage);
145                        }
146                    }
147                }
148            }
149        }
150    }
151
152    public static void killWithUnusedFloatingInputs(Node node) {
153        node.safeDelete();
154        node.acceptInputs((n, in) -> {
155            if (in.isAlive() && !(in instanceof FixedNode)) {
156                if (in.hasNoUsages()) {
157                    killWithUnusedFloatingInputs(in);
158                } else if (in instanceof PhiNode) {
159                    for (Node use : in.usages()) {
160                        if (use != in) {
161                            return;
162                        }
163                    }
164                    in.replaceAtUsages(null);
165                    killWithUnusedFloatingInputs(in);
166                }
167            }
168        });
169    }
170
171    public static void removeFixedWithUnusedInputs(FixedWithNextNode fixed) {
172        if (fixed instanceof StateSplit) {
173            FrameState stateAfter = ((StateSplit) fixed).stateAfter();
174            ((StateSplit) fixed).setStateAfter(null);
175            if (stateAfter.hasNoUsages()) {
176                killWithUnusedFloatingInputs(stateAfter);
177            }
178        }
179        unlinkFixedNode(fixed);
180        killWithUnusedFloatingInputs(fixed);
181    }
182
183    public static void unlinkFixedNode(FixedWithNextNode fixed) {
184        assert fixed.next() != null && fixed.predecessor() != null && fixed.isAlive() : fixed;
185        FixedNode next = fixed.next();
186        fixed.setNext(null);
187        fixed.replaceAtPredecessor(next);
188    }
189
190    public static void checkRedundantPhi(PhiNode phiNode) {
191        if (phiNode.isDeleted() || phiNode.valueCount() == 1) {
192            return;
193        }
194
195        ValueNode singleValue = phiNode.singleValue();
196        if (singleValue != PhiNode.MULTIPLE_VALUES) {
197            Collection<PhiNode> phiUsages = phiNode.usages().filter(PhiNode.class).snapshot();
198            Collection<ProxyNode> proxyUsages = phiNode.usages().filter(ProxyNode.class).snapshot();
199            phiNode.graph().replaceFloating(phiNode, singleValue);
200            for (PhiNode phi : phiUsages) {
201                checkRedundantPhi(phi);
202            }
203            for (ProxyNode proxy : proxyUsages) {
204                checkRedundantProxy(proxy);
205            }
206        }
207    }
208
209    public static void checkRedundantProxy(ProxyNode vpn) {
210        if (vpn.isDeleted()) {
211            return;
212        }
213        AbstractBeginNode proxyPoint = vpn.proxyPoint();
214        if (proxyPoint instanceof LoopExitNode) {
215            LoopExitNode exit = (LoopExitNode) proxyPoint;
216            LoopBeginNode loopBegin = exit.loopBegin();
217            Node vpnValue = vpn.value();
218            for (ValueNode v : loopBegin.stateAfter().values()) {
219                ValueNode v2 = v;
220                if (loopBegin.isPhiAtMerge(v2)) {
221                    v2 = ((PhiNode) v2).valueAt(loopBegin.forwardEnd());
222                }
223                if (vpnValue == v2) {
224                    Collection<PhiNode> phiUsages = vpn.usages().filter(PhiNode.class).snapshot();
225                    Collection<ProxyNode> proxyUsages = vpn.usages().filter(ProxyNode.class).snapshot();
226                    vpn.graph().replaceFloating(vpn, vpnValue);
227                    for (PhiNode phi : phiUsages) {
228                        checkRedundantPhi(phi);
229                    }
230                    for (ProxyNode proxy : proxyUsages) {
231                        checkRedundantProxy(proxy);
232                    }
233                    return;
234                }
235            }
236        }
237    }
238
239    /**
240     * Remove loop header without loop ends. This can happen with degenerated loops like this one:
241     *
242     * <pre>
243     * for (;;) {
244     *     try {
245     *         break;
246     *     } catch (UnresolvedException iioe) {
247     *     }
248     * }
249     * </pre>
250     */
251    public static void normalizeLoops(StructuredGraph graph) {
252        boolean loopRemoved = false;
253        for (LoopBeginNode begin : graph.getNodes(LoopBeginNode.TYPE)) {
254            if (begin.loopEnds().isEmpty()) {
255                assert begin.forwardEndCount() == 1;
256                graph.reduceDegenerateLoopBegin(begin);
257                loopRemoved = true;
258            } else {
259                normalizeLoopBegin(begin);
260            }
261        }
262
263        if (loopRemoved) {
264            /*
265             * Removing a degenerated loop can make non-loop phi functions unnecessary. Therefore,
266             * we re-check all phi functions and remove redundant ones.
267             */
268            for (Node node : graph.getNodes()) {
269                if (node instanceof PhiNode) {
270                    checkRedundantPhi((PhiNode) node);
271                }
272            }
273        }
274    }
275
276    private static void normalizeLoopBegin(LoopBeginNode begin) {
277        // Delete unnecessary loop phi functions, i.e., phi functions where all inputs are either
278        // the same or the phi itself.
279        for (PhiNode phi : begin.phis().snapshot()) {
280            GraphUtil.checkRedundantPhi(phi);
281        }
282        for (LoopExitNode exit : begin.loopExits()) {
283            for (ProxyNode vpn : exit.proxies().snapshot()) {
284                GraphUtil.checkRedundantProxy(vpn);
285            }
286        }
287    }
288
289    /**
290     * Gets an approximate source code location for a node if possible.
291     *
292     * @return the StackTraceElements if an approximate source location is found, null otherwise
293     */
294    public static StackTraceElement[] approxSourceStackTraceElement(Node node) {
295        ArrayList<StackTraceElement> elements = new ArrayList<>();
296        Node n = node;
297        while (n != null) {
298            if (n instanceof MethodCallTargetNode) {
299                elements.add(((MethodCallTargetNode) n).targetMethod().asStackTraceElement(-1));
300                n = ((MethodCallTargetNode) n).invoke().asNode();
301            }
302
303            if (n instanceof StateSplit) {
304                FrameState state = ((StateSplit) n).stateAfter();
305                elements.addAll(Arrays.asList(approxSourceStackTraceElement(state)));
306                break;
307            }
308            n = n.predecessor();
309        }
310        return elements.toArray(new StackTraceElement[elements.size()]);
311    }
312
313    /**
314     * Gets an approximate source code location for frame state.
315     *
316     * @return the StackTraceElements if an approximate source location is found, null otherwise
317     */
318    public static StackTraceElement[] approxSourceStackTraceElement(FrameState frameState) {
319        ArrayList<StackTraceElement> elements = new ArrayList<>();
320        FrameState state = frameState;
321        while (state != null) {
322            ResolvedJavaMethod method = state.method();
323            if (method != null) {
324                elements.add(method.asStackTraceElement(state.bci - 1));
325            }
326            state = state.outerFrameState();
327        }
328        return elements.toArray(new StackTraceElement[0]);
329    }
330
331    /**
332     * Gets an approximate source code location for a node, encoded as an exception, if possible.
333     *
334     * @return the exception with the location
335     */
336    public static RuntimeException approxSourceException(Node node, Throwable cause) {
337        final StackTraceElement[] elements = approxSourceStackTraceElement(node);
338        return createBailoutException(cause == null ? "" : cause.getMessage(), cause, elements);
339    }
340
341    /**
342     * Creates a bailout exception with the given stack trace elements and message.
343     *
344     * @param message the message of the exception
345     * @param elements the stack trace elements
346     * @return the exception
347     */
348    public static BailoutException createBailoutException(String message, Throwable cause, StackTraceElement[] elements) {
349        return SourceStackTrace.create(cause, message, elements);
350    }
351
352    /**
353     * Gets an approximate source code location for a node if possible.
354     *
355     * @return a file name and source line number in stack trace format (e.g. "String.java:32") if
356     *         an approximate source location is found, null otherwise
357     */
358    public static String approxSourceLocation(Node node) {
359        StackTraceElement[] stackTraceElements = approxSourceStackTraceElement(node);
360        if (stackTraceElements != null && stackTraceElements.length > 0) {
361            StackTraceElement top = stackTraceElements[0];
362            if (top.getFileName() != null && top.getLineNumber() >= 0) {
363                return top.getFileName() + ":" + top.getLineNumber();
364            }
365        }
366        return null;
367    }
368
369    /**
370     * Returns a string representation of the given collection of objects.
371     *
372     * @param objects The {@link Iterable} that will be used to iterate over the objects.
373     * @return A string of the format "[a, b, ...]".
374     */
375    public static String toString(Iterable<?> objects) {
376        StringBuilder str = new StringBuilder();
377        str.append("[");
378        for (Object o : objects) {
379            str.append(o).append(", ");
380        }
381        if (str.length() > 1) {
382            str.setLength(str.length() - 2);
383        }
384        str.append("]");
385        return str.toString();
386    }
387
388    /**
389     * Gets the original value by iterating through all {@link ValueProxy ValueProxies}.
390     *
391     * @param value The start value.
392     * @return The first non-proxy value encountered.
393     */
394    public static ValueNode unproxify(ValueNode value) {
395        ValueNode result = value;
396        while (result instanceof ValueProxy) {
397            result = ((ValueProxy) result).getOriginalNode();
398        }
399        return result;
400    }
401
402    /**
403     * Looks for an {@link ArrayLengthProvider} while iterating through all {@link ValueProxy
404     * ValueProxies}.
405     *
406     * @param value The start value.
407     * @return The array length if one was found, or null otherwise.
408     */
409    public static ValueNode arrayLength(ValueNode value) {
410        ValueNode current = value;
411        do {
412            if (current instanceof ArrayLengthProvider) {
413                ValueNode length = ((ArrayLengthProvider) current).length();
414                if (length != null) {
415                    return length;
416                }
417            }
418            if (current instanceof ValueProxy) {
419                current = ((ValueProxy) current).getOriginalNode();
420            } else {
421                break;
422            }
423        } while (true);
424        return null;
425    }
426
427    /**
428     * Tries to find an original value of the given node by traversing through proxies and
429     * unambiguous phis. Note that this method will perform an exhaustive search through phis. It is
430     * intended to be used during graph building, when phi nodes aren't yet canonicalized.
431     *
432     * @param proxy The node whose original value should be determined.
433     */
434    public static ValueNode originalValue(ValueNode proxy) {
435        ValueNode v = proxy;
436        do {
437            if (v instanceof LimitedValueProxy) {
438                v = ((LimitedValueProxy) v).getOriginalNode();
439            } else if (v instanceof PhiNode) {
440                v = ((PhiNode) v).singleValue();
441                if (v == PhiNode.MULTIPLE_VALUES) {
442                    v = null;
443                }
444            } else {
445                break;
446            }
447        } while (v != null);
448
449        if (v == null) {
450            v = new OriginalValueSearch(proxy).result;
451        }
452        return v;
453    }
454
455    public static boolean tryKillUnused(Node node) {
456        if (node.isAlive() && isFloatingNode().apply(node) && node.hasNoUsages()) {
457            killWithUnusedFloatingInputs(node);
458            return true;
459        }
460        return false;
461    }
462
463    /**
464     * Exhaustive search for {@link GraphUtil#originalValue(ValueNode)} when a simple search fails.
465     * This can happen in the presence of complicated phi/proxy/phi constructs.
466     */
467    static class OriginalValueSearch {
468        ValueNode result;
469
470        public OriginalValueSearch(ValueNode proxy) {
471            NodeWorkList worklist = proxy.graph().createNodeWorkList();
472            worklist.add(proxy);
473            for (Node node : worklist) {
474                if (node instanceof LimitedValueProxy) {
475                    ValueNode originalValue = ((LimitedValueProxy) node).getOriginalNode();
476                    if (!process(originalValue, worklist)) {
477                        return;
478                    }
479                } else if (node instanceof PhiNode) {
480                    for (Node value : ((PhiNode) node).values()) {
481                        if (!process((ValueNode) value, worklist)) {
482                            return;
483                        }
484                    }
485                } else {
486                    if (!process((ValueNode) node, null)) {
487                        return;
488                    }
489                }
490            }
491        }
492
493        /**
494         * Process a node as part of this search.
495         *
496         * @param node the next node encountered in the search
497         * @param worklist if non-null, {@code node} will be added to this list. Otherwise,
498         *            {@code node} is treated as a candidate result.
499         * @return true if the search should continue, false if a definitive {@link #result} has
500         *         been found
501         */
502        private boolean process(ValueNode node, NodeWorkList worklist) {
503            if (node.isAlive()) {
504                if (worklist == null) {
505                    if (result == null) {
506                        // Initial candidate result: continue search
507                        result = node;
508                    } else if (result != node) {
509                        // Conflicts with existing candidate: stop search with null result
510                        result = null;
511                        return false;
512                    }
513                } else {
514                    worklist.add(node);
515                }
516            }
517            return true;
518        }
519    }
520
521    /**
522     * Returns an iterator that will return the given node followed by all its predecessors, up
523     * until the point where {@link Node#predecessor()} returns null.
524     *
525     * @param start the node at which to start iterating
526     */
527    public static NodeIterable<FixedNode> predecessorIterable(final FixedNode start) {
528        return new NodeIterable<FixedNode>() {
529            public Iterator<FixedNode> iterator() {
530                return new Iterator<FixedNode>() {
531                    public FixedNode current = start;
532
533                    public boolean hasNext() {
534                        return current != null;
535                    }
536
537                    public FixedNode next() {
538                        try {
539                            return current;
540                        } finally {
541                            current = (FixedNode) current.predecessor();
542                        }
543                    }
544                };
545            }
546        };
547    }
548
549    private static final class DefaultSimplifierTool implements SimplifierTool {
550        private final MetaAccessProvider metaAccess;
551        private final ConstantReflectionProvider constantReflection;
552        private final boolean canonicalizeReads;
553
554        public DefaultSimplifierTool(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, boolean canonicalizeReads) {
555            this.metaAccess = metaAccess;
556            this.constantReflection = constantReflection;
557            this.canonicalizeReads = canonicalizeReads;
558        }
559
560        public MetaAccessProvider getMetaAccess() {
561            return metaAccess;
562        }
563
564        public ConstantReflectionProvider getConstantReflection() {
565            return constantReflection;
566        }
567
568        public boolean canonicalizeReads() {
569            return canonicalizeReads;
570        }
571
572        @Override
573        public boolean allUsagesAvailable() {
574            return true;
575        }
576
577        public void deleteBranch(Node branch) {
578            branch.predecessor().replaceFirstSuccessor(branch, null);
579            GraphUtil.killCFG(branch, this);
580        }
581
582        public void removeIfUnused(Node node) {
583            GraphUtil.tryKillUnused(node);
584        }
585
586        public void addToWorkList(Node node) {
587        }
588
589        public void addToWorkList(Iterable<? extends Node> nodes) {
590        }
591    }
592
593    public static SimplifierTool getDefaultSimplifier(MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection, boolean canonicalizeReads) {
594        return new DefaultSimplifierTool(metaAccess, constantReflection, canonicalizeReads);
595    }
596}