1 /*
2  * Copyright (c) 2013, 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.phases.graph;
26 
27 import java.util.ArrayDeque;
28 import java.util.Deque;
29 
30 import org.graalvm.compiler.graph.Node;
31 import org.graalvm.compiler.graph.NodeBitMap;
32 import org.graalvm.compiler.graph.iterators.NodeIterable;
33 import org.graalvm.compiler.nodes.AbstractEndNode;
34 import org.graalvm.compiler.nodes.AbstractMergeNode;
35 import org.graalvm.compiler.nodes.ControlSinkNode;
36 import org.graalvm.compiler.nodes.ControlSplitNode;
37 import org.graalvm.compiler.nodes.EndNode;
38 import org.graalvm.compiler.nodes.FixedNode;
39 import org.graalvm.compiler.nodes.FixedWithNextNode;
40 import org.graalvm.compiler.nodes.Invoke;
41 import org.graalvm.compiler.nodes.LoopBeginNode;
42 import org.graalvm.compiler.nodes.LoopEndNode;
43 import org.graalvm.compiler.nodes.LoopExitNode;
44 import org.graalvm.compiler.nodes.StructuredGraph;
45 
46 public abstract class ScopedPostOrderNodeIterator {
47 
48     private final Deque<FixedNode> nodeQueue;
49     private final NodeBitMap queuedNodes;
50     private final Deque<FixedNode> scopes;
51 
52     protected FixedNode currentScopeStart;
53 
ScopedPostOrderNodeIterator(StructuredGraph graph)54     public ScopedPostOrderNodeIterator(StructuredGraph graph) {
55         this.queuedNodes = graph.createNodeBitMap();
56         this.nodeQueue = new ArrayDeque<>();
57         this.scopes = getScopes(graph);
58     }
59 
apply()60     public void apply() {
61         while (!scopes.isEmpty()) {
62             queuedNodes.clearAll();
63             this.currentScopeStart = scopes.pop();
64             initializeScope();
65             processScope();
66         }
67     }
68 
processScope()69     public void processScope() {
70         FixedNode current;
71         queue(currentScopeStart);
72 
73         while ((current = nextQueuedNode()) != null) {
74             assert current.isAlive();
75 
76             if (current instanceof Invoke) {
77                 invoke((Invoke) current);
78                 queueSuccessors(current);
79             } else if (current instanceof LoopBeginNode) {
80                 queueLoopBeginSuccessors((LoopBeginNode) current);
81             } else if (current instanceof LoopExitNode) {
82                 queueLoopExitSuccessors((LoopExitNode) current);
83             } else if (current instanceof LoopEndNode) {
84                 // nothing todo
85             } else if (current instanceof AbstractMergeNode) {
86                 queueSuccessors(current);
87             } else if (current instanceof FixedWithNextNode) {
88                 queueSuccessors(current);
89             } else if (current instanceof EndNode) {
90                 queueMerge((EndNode) current);
91             } else if (current instanceof ControlSinkNode) {
92                 // nothing todo
93             } else if (current instanceof ControlSplitNode) {
94                 queueSuccessors(current);
95             } else {
96                 assert false : current;
97             }
98         }
99     }
100 
queueLoopBeginSuccessors(LoopBeginNode node)101     protected void queueLoopBeginSuccessors(LoopBeginNode node) {
102         if (currentScopeStart == node) {
103             queue(node.next());
104         } else if (currentScopeStart instanceof LoopBeginNode) {
105             // so we are currently processing loop A and found another loop B
106             // -> queue all loop exits of B except those that also exit loop A
107             for (LoopExitNode loopExit : node.loopExits()) {
108                 if (!((LoopBeginNode) currentScopeStart).loopExits().contains(loopExit)) {
109                     queue(loopExit);
110                 }
111             }
112         } else {
113             queue(node.loopExits());
114         }
115     }
116 
queueLoopExitSuccessors(LoopExitNode node)117     protected void queueLoopExitSuccessors(LoopExitNode node) {
118         if (!(currentScopeStart instanceof LoopBeginNode) || !((LoopBeginNode) currentScopeStart).loopExits().contains(node)) {
119             queueSuccessors(node);
120         }
121     }
122 
getScopes(StructuredGraph graph)123     protected Deque<FixedNode> getScopes(StructuredGraph graph) {
124         Deque<FixedNode> result = new ArrayDeque<>();
125         result.push(graph.start());
126         for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) {
127             result.push(loopBegin);
128         }
129         return result;
130     }
131 
queueSuccessors(FixedNode x)132     private void queueSuccessors(FixedNode x) {
133         queue(x.successors());
134     }
135 
queue(NodeIterable<? extends Node> iter)136     private void queue(NodeIterable<? extends Node> iter) {
137         for (Node node : iter) {
138             queue(node);
139         }
140     }
141 
queue(Node node)142     private void queue(Node node) {
143         if (node != null && !queuedNodes.isMarked(node)) {
144             queuedNodes.mark(node);
145             nodeQueue.addFirst((FixedNode) node);
146         }
147     }
148 
nextQueuedNode()149     private FixedNode nextQueuedNode() {
150         if (nodeQueue.isEmpty()) {
151             return null;
152         }
153 
154         FixedNode result = nodeQueue.removeFirst();
155         assert queuedNodes.isMarked(result);
156         return result;
157     }
158 
queueMerge(AbstractEndNode end)159     private void queueMerge(AbstractEndNode end) {
160         AbstractMergeNode merge = end.merge();
161         if (!queuedNodes.isMarked(merge) && visitedAllEnds(merge)) {
162             queue(merge);
163         }
164     }
165 
visitedAllEnds(AbstractMergeNode merge)166     private boolean visitedAllEnds(AbstractMergeNode merge) {
167         for (int i = 0; i < merge.forwardEndCount(); i++) {
168             if (!queuedNodes.isMarked(merge.forwardEndAt(i))) {
169                 return false;
170             }
171         }
172         return true;
173     }
174 
initializeScope()175     protected abstract void initializeScope();
176 
invoke(Invoke invoke)177     protected abstract void invoke(Invoke invoke);
178 }
179