Mercurial > hg > truffle

annotate graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java @ 14534:ccf090d3be47

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
new graph ordering assertion mechanism
author Lukas Stadler <lukas.stadler@oracle.com>
date Fri, 14 Mar 2014 10:22:04 +0100
parents 73f0f4755aa3
children 0d5923064a88
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
1 /*
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
2 * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved.
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
4 *
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
7 * published by the Free Software Foundation.
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
8 *
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
13 * accompanied this code).
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
14 *
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
18 *
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
21 * questions.
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
22 */
6525
2c913b643422 rename packages in graal.phases to match project name
Doug Simon <doug.simon@oracle.com>
parents: 6522
diff changeset
23 package com.oracle.graal.phases.util;
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
24
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
25 import java.util.*;
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
26
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
27 import com.oracle.graal.graph.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
28 import com.oracle.graal.nodes.*;
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
29 import com.oracle.graal.nodes.VirtualState.NodeClosure;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
30 import com.oracle.graal.nodes.cfg.*;
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
31 import com.oracle.graal.phases.graph.*;
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
32 import com.oracle.graal.phases.graph.ReentrantBlockIterator.*;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
33 import com.oracle.graal.phases.schedule.*;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
34 import com.oracle.graal.phases.schedule.SchedulePhase.*;
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
35
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
36 public final class GraphOrder {
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
37
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
38 private GraphOrder() {
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
39 }
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
40
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
41 /**
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
42 * Quick (and imprecise) assertion that there are no (invalid) cycles in the given graph. First,
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
43 * an ordered list of all nodes in the graph (a total ordering) is created. A second run over
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
44 * this list checks whether inputs are scheduled before their usages.
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
45 *
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
46 * @param graph the graph to be checked.
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
47 * @throws AssertionError if a cycle was detected.
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
48 */
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
49 public static boolean assertNonCyclicGraph(StructuredGraph graph) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
50 List<Node> order = createOrder(graph);
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
51 NodeBitMap visited = graph.createNodeBitMap();
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
52 visited.clearAll();
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
53 for (Node node : order) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
54 if (node instanceof PhiNode && ((PhiNode) node).merge() instanceof LoopBeginNode) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
55 assert visited.isMarked(((PhiNode) node).valueAt(0));
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
56 // nothing to do
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
57 } else {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
58 for (Node input : node.inputs()) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
59 if (!visited.isMarked(input)) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
60 if (input instanceof FrameState && node instanceof StateSplit && input == ((StateSplit) node).stateAfter()) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
61 // nothing to do - after frame states are known, allowed cycles
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
62 } else {
13783
73f0f4755aa3 better assertion message in GraphOrder
Lukas Stadler <lukas.stadler@jku.at>
parents: 13729
diff changeset
63 assert false : "unexpected cycle detected at input " + node + " -> " + input;
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
64 }
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
65 }
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
66 }
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
67 }
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
68 visited.mark(node);
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
69 }
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
70 return true;
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
71 }
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
72
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
73 private static List<Node> createOrder(StructuredGraph graph) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
74 final ArrayList<Node> nodes = new ArrayList<>();
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
75 final NodeBitMap visited = graph.createNodeBitMap();
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
76
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
77 new PostOrderNodeIterator<MergeableState.EmptyState>(graph.start(), new MergeableState.EmptyState()) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
78 @Override
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
79 protected void node(FixedNode node) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
80 visitForward(nodes, visited, node, false);
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
81 }
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
82 }.apply();
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
83 return nodes;
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
84 }
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
85
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
86 private static void visitForward(ArrayList<Node> nodes, NodeBitMap visited, Node node, boolean floatingOnly) {
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
87 try {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
88 assert node.isAlive() : node + " not alive";
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
89 if (node != null && !visited.isMarked(node)) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
90 if (floatingOnly && node instanceof FixedNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
91 throw new GraalInternalError("unexpected reference to fixed node: %s (this indicates an unexpected cycle)", node);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
92 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
93 visited.mark(node);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
94 FrameState stateAfter = null;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
95 if (node instanceof StateSplit) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
96 stateAfter = ((StateSplit) node).stateAfter();
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
97 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
98 for (Node input : node.inputs()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
99 if (input != stateAfter) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
100 visitForward(nodes, visited, input, true);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
101 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
102 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
103 if (node instanceof EndNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
104 EndNode end = (EndNode) node;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
105 for (PhiNode phi : end.merge().phis()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
106 visitForward(nodes, visited, phi.valueAt(end), true);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
107 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
108 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
109 nodes.add(node);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
110 if (node instanceof MergeNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
111 for (PhiNode phi : ((MergeNode) node).phis()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
112 visited.mark(phi);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
113 nodes.add(phi);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
114 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
115 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
116 if (stateAfter != null) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
117 visitForward(nodes, visited, stateAfter, true);
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
118 }
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
119 }
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
120 } catch (GraalInternalError e) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
121 e.addContext(node);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
122 throw e;
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
123 }
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
124 }
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
125
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
126 /**
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
127 * This method schedules the graph and makes sure that, for every node, all inputs are available
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
128 * at the position where it is scheduled. This is a very expensive assertion.
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
129 *
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
130 * Also, this phase assumes ProxyNodes to exist at LoopExitNodes, so that it cannot be run after
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
131 * phases that remove loop proxies or move proxies to BeginNodes.
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
132 */
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
133 public static boolean assertSchedulableGraph(final StructuredGraph graph) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
134 try {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
135 final SchedulePhase schedule = new SchedulePhase(SchedulingStrategy.LATEST_OUT_OF_LOOPS, MemoryScheduling.NONE);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
136 final IdentityHashMap<LoopBeginNode, NodeBitMap> loopEntryStates = new IdentityHashMap<>();
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
137 schedule.apply(graph, false);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
138
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
139 BlockIteratorClosure<NodeBitMap> closure = new BlockIteratorClosure<NodeBitMap>() {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
140
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
141 @Override
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
142 protected List<NodeBitMap> processLoop(Loop loop, NodeBitMap initialState) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
143 return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
144 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
145
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
146 @Override
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
147 protected NodeBitMap processBlock(final Block block, final NodeBitMap currentState) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
148 final List<ScheduledNode> list = schedule.getBlockToNodesMap().get(block);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
149
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
150 /*
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
151 * A stateAfter is not valid directly after its associated state split, but
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
152 * right before the next fixed node. Therefore a pending stateAfter is kept that
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
153 * will be checked at the correct position.
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
154 */
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
155 FrameState pendingStateAfter = null;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
156 for (final ScheduledNode node : list) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
157 FrameState stateAfter = node instanceof StateSplit ? ((StateSplit) node).stateAfter() : null;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
158
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
159 if (pendingStateAfter != null && node instanceof FixedNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
160 pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
161 public void apply(Node usage, Node nonVirtualNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
162 assert currentState.isMarked(nonVirtualNode) : nonVirtualNode + " not available at virtualstate " + usage + " before " + node + " in block " + block + " \n" + list;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
163 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
164 });
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
165 pendingStateAfter = null;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
166 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
167
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
168 if (node instanceof MergeNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
169 // phis aren't scheduled, so they need to be added explicitly
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
170 currentState.markAll(((MergeNode) node).phis());
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
171 if (node instanceof LoopBeginNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
172 // remember the state at the loop entry, it's restored at exits
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
173 loopEntryStates.put((LoopBeginNode) node, currentState.copy());
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
174 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
175 } else if (node instanceof ProxyNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
176 for (Node input : node.inputs()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
177 if (input != ((ProxyNode) node).proxyPoint()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
178 assert currentState.isMarked(input) : input + " not available at " + node + " in block " + block + "\n" + list;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
179 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
180 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
181 } else if (node instanceof LoopExitNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
182 // the contents of the loop are only accessible via proxies at the exit
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
183 currentState.clearAll();
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
184 currentState.markAll(loopEntryStates.get(((LoopExitNode) node).loopBegin()));
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
185 // Loop proxies aren't scheduled, so they need to be added explicitly
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
186 currentState.markAll(((LoopExitNode) node).proxies());
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
187 } else {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
188 for (Node input : node.inputs()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
189 if (input != stateAfter) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
190 assert currentState.isMarked(input) : input + " not available at " + node + " in block " + block + "\n" + list;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
191 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
192 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
193 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
194 if (node instanceof AbstractEndNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
195 MergeNode merge = ((AbstractEndNode) node).merge();
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
196 for (PhiNode phi : merge.phis()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
197 assert currentState.isMarked(phi.valueAt((AbstractEndNode) node)) : phi.valueAt((AbstractEndNode) node) + " not available at phi " + phi + " / end " + node +
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
198 " in block " + block;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
199 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
200 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
201 if (stateAfter != null) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
202 assert pendingStateAfter == null;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
203 pendingStateAfter = stateAfter;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
204 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
205 currentState.mark(node);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
206 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
207 if (pendingStateAfter != null) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
208 pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
209 public void apply(Node usage, Node nonVirtualNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
210 assert currentState.isMarked(nonVirtualNode) : nonVirtualNode + " not available at virtualstate " + usage + " at end of block " + block + " \n" + list;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
211 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
212 });
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
213 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
214 return currentState;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
215 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
216
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
217 @Override
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
218 protected NodeBitMap merge(Block merge, List<NodeBitMap> states) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
219 NodeBitMap result = states.get(0);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
220 for (int i = 1; i < states.size(); i++) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
221 result.intersect(states.get(i));
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
222 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
223 return result;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
224 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
225
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
226 @Override
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
227 protected NodeBitMap getInitialState() {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
228 return graph.createNodeBitMap();
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
229 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
230
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
231 @Override
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
232 protected NodeBitMap cloneState(NodeBitMap oldState) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
233 return oldState.copy();
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
234 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
235 };
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
236
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
237 ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock());
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
238
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
239 } catch (Throwable t) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
240 throw new AssertionError("unschedulable graph", t);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
241 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
242 return true;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
243 }
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
244 }