Source code

001/*
002 * Copyright (c) 2011, 2012, 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.util;
024
025import java.util.*;
026
027import jdk.internal.jvmci.common.*;
028
029import com.oracle.graal.compiler.common.cfg.*;
030import com.oracle.graal.graph.*;
031import com.oracle.graal.nodes.*;
032import com.oracle.graal.nodes.VirtualState.NodeClosure;
033import com.oracle.graal.nodes.cfg.*;
034import com.oracle.graal.nodes.virtual.*;
035import com.oracle.graal.phases.graph.*;
036import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
037import com.oracle.graal.phases.schedule.*;
038import com.oracle.graal.phases.schedule.SchedulePhase.SchedulingStrategy;
039
040public final class GraphOrder {
041
042    private GraphOrder() {
043    }
044
045    /**
046     * Quick (and imprecise) assertion that there are no (invalid) cycles in the given graph. First,
047     * an ordered list of all nodes in the graph (a total ordering) is created. A second run over
048     * this list checks whether inputs are scheduled before their usages.
049     *
050     * @param graph the graph to be checked.
051     * @throws AssertionError if a cycle was detected.
052     */
053    public static boolean assertNonCyclicGraph(StructuredGraph graph) {
054        List<Node> order = createOrder(graph);
055        NodeBitMap visited = graph.createNodeBitMap();
056        visited.clearAll();
057        for (Node node : order) {
058            if (node instanceof PhiNode && ((PhiNode) node).merge() instanceof LoopBeginNode) {
059                assert visited.isMarked(((PhiNode) node).valueAt(0));
060                // nothing to do
061            } else {
062                for (Node input : node.inputs()) {
063                    if (!visited.isMarked(input)) {
064                        if (input instanceof FrameState) {
065                            // nothing to do - frame states are known, allowed cycles
066                        } else {
067                            assert false : "unexpected cycle detected at input " + node + " -> " + input;
068                        }
069                    }
070                }
071            }
072            visited.mark(node);
073        }
074        return true;
075    }
076
077    private static List<Node> createOrder(StructuredGraph graph) {
078        final ArrayList<Node> nodes = new ArrayList<>();
079        final NodeBitMap visited = graph.createNodeBitMap();
080
081        new StatelessPostOrderNodeIterator(graph.start()) {
082            @Override
083            protected void node(FixedNode node) {
084                visitForward(nodes, visited, node, false);
085            }
086        }.apply();
087        return nodes;
088    }
089
090    private static void visitForward(ArrayList<Node> nodes, NodeBitMap visited, Node node, boolean floatingOnly) {
091        try {
092            assert node == null || node.isAlive() : node + " not alive";
093            if (node != null && !visited.isMarked(node)) {
094                if (floatingOnly && node instanceof FixedNode) {
095                    throw new JVMCIError("unexpected reference to fixed node: %s (this indicates an unexpected cycle)", node);
096                }
097                visited.mark(node);
098                FrameState stateAfter = null;
099                if (node instanceof StateSplit) {
100                    stateAfter = ((StateSplit) node).stateAfter();
101                }
102                for (Node input : node.inputs()) {
103                    if (input != stateAfter) {
104                        visitForward(nodes, visited, input, true);
105                    }
106                }
107                if (node instanceof EndNode) {
108                    EndNode end = (EndNode) node;
109                    for (PhiNode phi : end.merge().phis()) {
110                        visitForward(nodes, visited, phi.valueAt(end), true);
111                    }
112                }
113                nodes.add(node);
114                if (node instanceof AbstractMergeNode) {
115                    for (PhiNode phi : ((AbstractMergeNode) node).phis()) {
116                        visited.mark(phi);
117                        nodes.add(phi);
118                    }
119                }
120                if (stateAfter != null) {
121                    visitForward(nodes, visited, stateAfter, true);
122                }
123            }
124        } catch (JVMCIError e) {
125            throw GraalGraphJVMCIError.transformAndAddContext(e, node);
126        }
127    }
128
129    /**
130     * This method schedules the graph and makes sure that, for every node, all inputs are available
131     * at the position where it is scheduled. This is a very expensive assertion.
132     *
133     * Also, this phase assumes ProxyNodes to exist at LoopExitNodes, so that it cannot be run after
134     * phases that remove loop proxies or move proxies to BeginNodes.
135     */
136    public static boolean assertSchedulableGraph(final StructuredGraph graph) {
137        try {
138            final SchedulePhase schedule = new SchedulePhase(SchedulingStrategy.LATEST_OUT_OF_LOOPS);
139            final Map<LoopBeginNode, NodeBitMap> loopEntryStates = Node.newIdentityMap();
140            schedule.apply(graph, false);
141
142            BlockIteratorClosure<NodeBitMap> closure = new BlockIteratorClosure<NodeBitMap>() {
143
144                @Override
145                protected List<NodeBitMap> processLoop(Loop<Block> loop, NodeBitMap initialState) {
146                    return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates;
147                }
148
149                @Override
150                protected NodeBitMap processBlock(final Block block, final NodeBitMap currentState) {
151                    final List<Node> list = schedule.getBlockToNodesMap().get(block);
152
153                    /*
154                     * A stateAfter is not valid directly after its associated state split, but
155                     * right before the next fixed node. Therefore a pending stateAfter is kept that
156                     * will be checked at the correct position.
157                     */
158                    FrameState pendingStateAfter = null;
159                    for (final Node node : list) {
160                        if (node instanceof ValueNode) {
161                            FrameState stateAfter = node instanceof StateSplit ? ((StateSplit) node).stateAfter() : null;
162                            if (node instanceof FullInfopointNode) {
163                                stateAfter = ((FullInfopointNode) node).getState();
164                            }
165
166                            if (pendingStateAfter != null && node instanceof FixedNode) {
167                                pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() {
168                                    @Override
169                                    public void apply(Node usage, Node nonVirtualNode) {
170                                        assert currentState.isMarked(nonVirtualNode) || nonVirtualNode instanceof VirtualObjectNode || nonVirtualNode instanceof ConstantNode : nonVirtualNode +
171                                                        " not available at virtualstate " + usage + " before " + node + " in block " + block + " \n" + list;
172                                    }
173                                });
174                                pendingStateAfter = null;
175                            }
176
177                            if (node instanceof AbstractMergeNode) {
178                                // phis aren't scheduled, so they need to be added explicitly
179                                currentState.markAll(((AbstractMergeNode) node).phis());
180                                if (node instanceof LoopBeginNode) {
181                                    // remember the state at the loop entry, it's restored at exits
182                                    loopEntryStates.put((LoopBeginNode) node, currentState.copy());
183                                }
184                            } else if (node instanceof ProxyNode) {
185                                assert false : "proxy nodes should not be in the schedule";
186                            } else if (node instanceof LoopExitNode) {
187                                if (graph.hasValueProxies()) {
188                                    for (ProxyNode proxy : ((LoopExitNode) node).proxies()) {
189                                        for (Node input : proxy.inputs()) {
190                                            if (input != proxy.proxyPoint()) {
191                                                assert currentState.isMarked(input) : input + " not available at " + proxy + " in block " + block + "\n" + list;
192                                            }
193                                        }
194                                    }
195
196                                    // loop contents are only accessible via proxies at the exit
197                                    currentState.clearAll();
198                                    currentState.markAll(loopEntryStates.get(((LoopExitNode) node).loopBegin()));
199                                }
200                                // Loop proxies aren't scheduled, so they need to be added
201                                // explicitly
202                                currentState.markAll(((LoopExitNode) node).proxies());
203                            } else {
204                                for (Node input : node.inputs()) {
205                                    if (input != stateAfter) {
206                                        if (input instanceof FrameState) {
207                                            ((FrameState) input).applyToNonVirtual(new VirtualState.NodeClosure<Node>() {
208                                                @Override
209                                                public void apply(Node usage, Node nonVirtual) {
210                                                    assert currentState.isMarked(nonVirtual) : nonVirtual + " not available at " + node + " in block " + block + "\n" + list;
211                                                }
212                                            });
213                                        } else {
214                                            assert currentState.isMarked(input) || input instanceof VirtualObjectNode || input instanceof ConstantNode : input + " not available at " + node +
215                                                            " in block " + block + "\n" + list;
216                                        }
217                                    }
218                                }
219                            }
220                            if (node instanceof AbstractEndNode) {
221                                AbstractMergeNode merge = ((AbstractEndNode) node).merge();
222                                for (PhiNode phi : merge.phis()) {
223                                    ValueNode phiValue = phi.valueAt((AbstractEndNode) node);
224                                    assert phiValue == null || currentState.isMarked(phiValue) || phiValue instanceof ConstantNode : phiValue + " not available at phi " + phi + " / end " + node +
225                                                    " in block " + block;
226                                }
227                            }
228                            if (stateAfter != null) {
229                                assert pendingStateAfter == null;
230                                pendingStateAfter = stateAfter;
231                            }
232                            currentState.mark(node);
233                        }
234                    }
235                    if (pendingStateAfter != null) {
236                        pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() {
237                            @Override
238                            public void apply(Node usage, Node nonVirtualNode) {
239                                assert currentState.isMarked(nonVirtualNode) || nonVirtualNode instanceof VirtualObjectNode || nonVirtualNode instanceof ConstantNode : nonVirtualNode +
240                                                " not available at virtualstate " + usage + " at end of block " + block + " \n" + list;
241                            }
242                        });
243                    }
244                    return currentState;
245                }
246
247                @Override
248                protected NodeBitMap merge(Block merge, List<NodeBitMap> states) {
249                    NodeBitMap result = states.get(0);
250                    for (int i = 1; i < states.size(); i++) {
251                        result.intersect(states.get(i));
252                    }
253                    return result;
254                }
255
256                @Override
257                protected NodeBitMap getInitialState() {
258                    NodeBitMap ret = graph.createNodeBitMap();
259                    ret.markAll(graph.getNodes().filter(ConstantNode.class));
260                    return ret;
261                }
262
263                @Override
264                protected NodeBitMap cloneState(NodeBitMap oldState) {
265                    return oldState.copy();
266                }
267            };
268
269            ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock());
270
271        } catch (Throwable t) {
272            throw new AssertionError("unschedulable graph", t);
273        }
274        return true;
275    }
276}