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.phases.util;
26
27 import java.util.ArrayList;
28 import java.util.List;
29
30 import jdk.internal.vm.compiler.collections.EconomicMap;
31 import jdk.internal.vm.compiler.collections.Equivalence;
32 import org.graalvm.compiler.core.common.cfg.Loop;
33 import org.graalvm.compiler.debug.DebugContext;
34 import org.graalvm.compiler.debug.GraalError;
35 import org.graalvm.compiler.graph.GraalGraphError;
36 import org.graalvm.compiler.graph.Node;
37 import org.graalvm.compiler.graph.NodeBitMap;
38 import org.graalvm.compiler.nodes.AbstractEndNode;
39 import org.graalvm.compiler.nodes.AbstractMergeNode;
40 import org.graalvm.compiler.nodes.ConstantNode;
41 import org.graalvm.compiler.nodes.EndNode;
42 import org.graalvm.compiler.nodes.FixedNode;
43 import org.graalvm.compiler.nodes.FrameState;
44 import org.graalvm.compiler.nodes.FullInfopointNode;
45 import org.graalvm.compiler.nodes.LoopBeginNode;
46 import org.graalvm.compiler.nodes.LoopExitNode;
47 import org.graalvm.compiler.nodes.PhiNode;
48 import org.graalvm.compiler.nodes.ProxyNode;
49 import org.graalvm.compiler.nodes.StateSplit;
50 import org.graalvm.compiler.nodes.StructuredGraph;
51 import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
52 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
53 import org.graalvm.compiler.nodes.ValueNode;
54 import org.graalvm.compiler.nodes.VirtualState;
55 import org.graalvm.compiler.nodes.VirtualState.NodeClosure;
56 import org.graalvm.compiler.nodes.cfg.Block;
57 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
58 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator;
59 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
60 import org.graalvm.compiler.phases.graph.StatelessPostOrderNodeIterator;
61 import org.graalvm.compiler.phases.schedule.SchedulePhase;
62 import org.graalvm.compiler.phases.schedule.SchedulePhase.SchedulingStrategy;
63
64 public final class GraphOrder {
65
66 private GraphOrder() {
67 }
68
69 /**
70 * Quick (and imprecise) assertion that there are no (invalid) cycles in the given graph. First,
71 * an ordered list of all nodes in the graph (a total ordering) is created. A second run over
72 * this list checks whether inputs are scheduled before their usages.
73 *
74 * @param graph the graph to be checked.
75 * @throws AssertionError if a cycle was detected.
76 */
77 public static boolean assertNonCyclicGraph(StructuredGraph graph) {
78 List<Node> order = createOrder(graph);
79 NodeBitMap visited = graph.createNodeBitMap();
80 visited.clearAll();
81 for (Node node : order) {
82 if (node instanceof PhiNode && ((PhiNode) node).merge() instanceof LoopBeginNode) {
83 assert visited.isMarked(((PhiNode) node).valueAt(0));
84 // nothing to do
85 } else {
86 for (Node input : node.inputs()) {
87 if (!visited.isMarked(input)) {
88 if (input instanceof FrameState) {
89 // nothing to do - frame states are known, allowed cycles
90 } else {
91 assert false : "unexpected cycle detected at input " + node + " -> " + input;
92 }
93 }
94 }
95 }
96 visited.mark(node);
97 }
98 return true;
99 }
100
101 private static List<Node> createOrder(StructuredGraph graph) {
102 final ArrayList<Node> nodes = new ArrayList<>();
103 final NodeBitMap visited = graph.createNodeBitMap();
104
105 new StatelessPostOrderNodeIterator(graph.start()) {
106 @Override
107 protected void node(FixedNode node) {
108 visitForward(nodes, visited, node, false);
109 }
110 }.apply();
111 return nodes;
112 }
113
114 private static void visitForward(ArrayList<Node> nodes, NodeBitMap visited, Node node, boolean floatingOnly) {
115 try {
116 assert node == null || node.isAlive() : node + " not alive";
117 if (node != null && !visited.isMarked(node)) {
118 if (floatingOnly && node instanceof FixedNode) {
119 throw new GraalError("unexpected reference to fixed node: %s (this indicates an unexpected cycle)", node);
120 }
121 visited.mark(node);
122 FrameState stateAfter = null;
123 if (node instanceof StateSplit) {
124 stateAfter = ((StateSplit) node).stateAfter();
125 }
126 for (Node input : node.inputs()) {
127 if (input != stateAfter) {
128 visitForward(nodes, visited, input, true);
129 }
130 }
131 if (node instanceof EndNode) {
132 EndNode end = (EndNode) node;
133 for (PhiNode phi : end.merge().phis()) {
134 visitForward(nodes, visited, phi.valueAt(end), true);
135 }
136 }
137 nodes.add(node);
138 if (node instanceof AbstractMergeNode) {
139 for (PhiNode phi : ((AbstractMergeNode) node).phis()) {
140 visited.mark(phi);
141 nodes.add(phi);
142 }
143 }
144 if (stateAfter != null) {
145 visitForward(nodes, visited, stateAfter, true);
146 }
147 }
148 } catch (GraalError e) {
149 throw GraalGraphError.transformAndAddContext(e, node);
150 }
151 }
152
153 /**
154 * This method schedules the graph and makes sure that, for every node, all inputs are available
155 * at the position where it is scheduled. This is a very expensive assertion.
156 */
157 @SuppressWarnings("try")
158 public static boolean assertSchedulableGraph(final StructuredGraph graph) {
159 assert graph.getGuardsStage() != GuardsStage.AFTER_FSA : "Cannot use the BlockIteratorClosure after FrameState Assignment, HIR Loop Data Structures are no longer valid.";
160 try (DebugContext.Scope s = graph.getDebug().scope("AssertSchedulableGraph")) {
161 final SchedulePhase schedulePhase = new SchedulePhase(SchedulingStrategy.LATEST_OUT_OF_LOOPS, true);
162 final EconomicMap<LoopBeginNode, NodeBitMap> loopEntryStates = EconomicMap.create(Equivalence.IDENTITY);
163 schedulePhase.apply(graph, false);
164 final ScheduleResult schedule = graph.getLastSchedule();
165
166 BlockIteratorClosure<NodeBitMap> closure = new BlockIteratorClosure<NodeBitMap>() {
167
168 @Override
169 protected List<NodeBitMap> processLoop(Loop<Block> loop, NodeBitMap initialState) {
170 return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates;
171 }
172
173 @Override
174 protected NodeBitMap processBlock(final Block block, final NodeBitMap currentState) {
175 final List<Node> list = graph.getLastSchedule().getBlockToNodesMap().get(block);
176
177 /*
178 * A stateAfter is not valid directly after its associated state split, but
179 * right before the next fixed node. Therefore a pending stateAfter is kept that
180 * will be checked at the correct position.
181 */
182 FrameState pendingStateAfter = null;
183 for (final Node node : list) {
184 if (node instanceof ValueNode) {
185 FrameState stateAfter = node instanceof StateSplit ? ((StateSplit) node).stateAfter() : null;
186 if (node instanceof FullInfopointNode) {
187 stateAfter = ((FullInfopointNode) node).getState();
188 }
189
190 if (pendingStateAfter != null && node instanceof FixedNode) {
191 pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() {
192 @Override
193 public void apply(Node usage, Node nonVirtualNode) {
194 assert currentState.isMarked(nonVirtualNode) || nonVirtualNode instanceof VirtualObjectNode || nonVirtualNode instanceof ConstantNode : nonVirtualNode +
195 " not available at virtualstate " + usage + " before " + node + " in block " + block + " \n" + list;
196 }
197 });
198 pendingStateAfter = null;
199 }
200
201 if (node instanceof AbstractMergeNode) {
202 // phis aren't scheduled, so they need to be added explicitly
203 currentState.markAll(((AbstractMergeNode) node).phis());
204 if (node instanceof LoopBeginNode) {
205 // remember the state at the loop entry, it's restored at exits
206 loopEntryStates.put((LoopBeginNode) node, currentState.copy());
207 }
208 } else if (node instanceof ProxyNode) {
209 assert false : "proxy nodes should not be in the schedule";
210 } else if (node instanceof LoopExitNode) {
211 if (graph.hasValueProxies()) {
212 for (ProxyNode proxy : ((LoopExitNode) node).proxies()) {
213 for (Node input : proxy.inputs()) {
214 if (input != proxy.proxyPoint()) {
215 assert currentState.isMarked(input) : input + " not available at " + proxy + " in block " + block + "\n" + list;
216 }
217 }
218 }
219
220 // loop contents are only accessible via proxies at the exit
221 currentState.clearAll();
222 currentState.markAll(loopEntryStates.get(((LoopExitNode) node).loopBegin()));
223 }
224 // Loop proxies aren't scheduled, so they need to be added
225 // explicitly
226 currentState.markAll(((LoopExitNode) node).proxies());
227 } else {
228 for (Node input : node.inputs()) {
229 if (input != stateAfter) {
230 if (input instanceof FrameState) {
231 ((FrameState) input).applyToNonVirtual(new VirtualState.NodeClosure<Node>() {
232 @Override
233 public void apply(Node usage, Node nonVirtual) {
234 assert currentState.isMarked(nonVirtual) : nonVirtual + " not available at " + node + " in block " + block + "\n" + list;
235 }
236 });
237 } else {
238 assert currentState.isMarked(input) || input instanceof VirtualObjectNode || input instanceof ConstantNode : input + " not available at " + node +
239 " in block " + block + "\n" + list;
240 }
241 }
242 }
243 }
244 if (node instanceof AbstractEndNode) {
245 AbstractMergeNode merge = ((AbstractEndNode) node).merge();
246 for (PhiNode phi : merge.phis()) {
247 ValueNode phiValue = phi.valueAt((AbstractEndNode) node);
248 assert phiValue == null || currentState.isMarked(phiValue) || phiValue instanceof ConstantNode : phiValue + " not available at phi " + phi + " / end " + node +
249 " in block " + block;
250 }
251 }
252 if (stateAfter != null) {
253 assert pendingStateAfter == null;
254 pendingStateAfter = stateAfter;
255 }
256 currentState.mark(node);
257 }
258 }
259 if (pendingStateAfter != null) {
260 pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() {
261 @Override
262 public void apply(Node usage, Node nonVirtualNode) {
263 assert currentState.isMarked(nonVirtualNode) || nonVirtualNode instanceof VirtualObjectNode || nonVirtualNode instanceof ConstantNode : nonVirtualNode +
264 " not available at virtualstate " + usage + " at end of block " + block + " \n" + list;
265 }
266 });
267 }
268 return currentState;
269 }
270
271 @Override
272 protected NodeBitMap merge(Block merge, List<NodeBitMap> states) {
273 NodeBitMap result = states.get(0);
274 for (int i = 1; i < states.size(); i++) {
275 result.intersect(states.get(i));
276 }
277 return result;
278 }
279
280 @Override
281 protected NodeBitMap getInitialState() {
282 NodeBitMap ret = graph.createNodeBitMap();
283 ret.markAll(graph.getNodes().filter(ConstantNode.class));
284 return ret;
285 }
286
287 @Override
288 protected NodeBitMap cloneState(NodeBitMap oldState) {
289 return oldState.copy();
290 }
291 };
292
293 ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock());
294
295 } catch (Throwable t) {
296 graph.getDebug().handle(t);
297 }
298 return true;
299 }
300 }