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.phases.common.inlining.walker;
024
025import java.util.*;
026
027import com.oracle.graal.graph.*;
028import com.oracle.graal.nodes.*;
029import com.oracle.graal.nodes.java.*;
030
031/**
032 * Given a graph, visit all fixed nodes in dominator-based order, collecting in the process the
033 * {@link Invoke} nodes with {@link MethodCallTargetNode}. Such list of callsites is returned by
034 * {@link #apply()}
035 */
036public class InliningIterator {
037
038    private final StartNode start;
039    private final Deque<FixedNode> nodeQueue;
040    private final NodeBitMap queuedNodes;
041
042    public InliningIterator(StructuredGraph graph) {
043        this.start = graph.start();
044        this.nodeQueue = new ArrayDeque<>();
045        this.queuedNodes = graph.createNodeBitMap();
046        assert start.isAlive();
047    }
048
049    public LinkedList<Invoke> apply() {
050        LinkedList<Invoke> invokes = new LinkedList<>();
051        FixedNode current;
052        forcedQueue(start);
053
054        while ((current = nextQueuedNode()) != null) {
055            assert current.isAlive();
056
057            if (current instanceof Invoke && ((Invoke) current).callTarget() instanceof MethodCallTargetNode) {
058                if (current != start) {
059                    invokes.addLast((Invoke) current);
060                }
061                queueSuccessors(current);
062            } else if (current instanceof LoopBeginNode) {
063                queueSuccessors(current);
064            } else if (current instanceof LoopEndNode) {
065                // nothing to do
066            } else if (current instanceof AbstractMergeNode) {
067                queueSuccessors(current);
068            } else if (current instanceof FixedWithNextNode) {
069                queueSuccessors(current);
070            } else if (current instanceof EndNode) {
071                queueMerge((EndNode) current);
072            } else if (current instanceof ControlSinkNode) {
073                // nothing to do
074            } else if (current instanceof ControlSplitNode) {
075                queueSuccessors(current);
076            } else {
077                assert false : current;
078            }
079        }
080
081        assert invokes.size() == count(start.graph().getInvokes());
082        return invokes;
083    }
084
085    private void queueSuccessors(FixedNode x) {
086        for (Node node : x.successors()) {
087            queue(node);
088        }
089    }
090
091    private void queue(Node node) {
092        if (node != null && !queuedNodes.isMarked(node)) {
093            forcedQueue(node);
094        }
095    }
096
097    private void forcedQueue(Node node) {
098        queuedNodes.mark(node);
099        nodeQueue.addFirst((FixedNode) node);
100    }
101
102    private FixedNode nextQueuedNode() {
103        if (nodeQueue.isEmpty()) {
104            return null;
105        }
106
107        FixedNode result = nodeQueue.removeFirst();
108        assert queuedNodes.isMarked(result);
109        return result;
110    }
111
112    private void queueMerge(AbstractEndNode end) {
113        AbstractMergeNode merge = end.merge();
114        if (!queuedNodes.isMarked(merge) && visitedAllEnds(merge)) {
115            queuedNodes.mark(merge);
116            nodeQueue.add(merge);
117        }
118    }
119
120    private boolean visitedAllEnds(AbstractMergeNode merge) {
121        for (int i = 0; i < merge.forwardEndCount(); i++) {
122            if (!queuedNodes.isMarked(merge.forwardEndAt(i))) {
123                return false;
124            }
125        }
126        return true;
127    }
128
129    private static int count(Iterable<Invoke> invokes) {
130        int count = 0;
131        Iterator<Invoke> iterator = invokes.iterator();
132        while (iterator.hasNext()) {
133            iterator.next();
134            count++;
135        }
136        return count;
137    }
138}