Mercurial > hg > truffle
annotate graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java @ 14759:56721cd3f8ba
remove a GraphOrder assertion which does not hold in substrate VM
author | Erik Eckstein <erik.eckstein@oracle.com> |
---|---|
date | Wed, 26 Mar 2014 10:16:28 +0100 |
parents | 0d5923064a88 |
children | c59eaa8d6632 |
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 { |
14759
56721cd3f8ba
remove a GraphOrder assertion which does not hold in substrate VM
Erik Eckstein <erik.eckstein@oracle.com>
parents:
14547
diff
changeset
|
63 // TODO assertion does not hold for Substrate VM (in general for all |
56721cd3f8ba
remove a GraphOrder assertion which does not hold in substrate VM
Erik Eckstein <erik.eckstein@oracle.com>
parents:
14547
diff
changeset
|
64 // notDataflow inputs) |
56721cd3f8ba
remove a GraphOrder assertion which does not hold in substrate VM
Erik Eckstein <erik.eckstein@oracle.com>
parents:
14547
diff
changeset
|
65 // assert false : "unexpected cycle detected at input " + node + " -> " |
56721cd3f8ba
remove a GraphOrder assertion which does not hold in substrate VM
Erik Eckstein <erik.eckstein@oracle.com>
parents:
14547
diff
changeset
|
66 // + input; |
13729
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 } |
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 } |
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
71 visited.mark(node); |
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
72 } |
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
73 return true; |
4642
9f781aae2470
separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
74 } |
9f781aae2470
separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
75 |
13729
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
76 private static List<Node> createOrder(StructuredGraph graph) { |
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
77 final ArrayList<Node> nodes = new ArrayList<>(); |
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
78 final NodeBitMap visited = graph.createNodeBitMap(); |
4642
9f781aae2470
separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
79 |
13729
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
80 new PostOrderNodeIterator<MergeableState.EmptyState>(graph.start(), new MergeableState.EmptyState()) { |
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
81 @Override |
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
82 protected void node(FixedNode node) { |
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
83 visitForward(nodes, visited, node, false); |
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
84 } |
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
85 }.apply(); |
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
86 return nodes; |
4642
9f781aae2470
separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
87 } |
9f781aae2470
separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
88 |
13729
9a6faa08bffe
cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents:
11641
diff
changeset
|
89 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
|
90 try { |
14547
0d5923064a88
fixed some findbugs issues
Doug Simon <doug.simon@oracle.com>
parents:
14534
diff
changeset
|
91 assert node == null || node.isAlive() : node + " not alive"; |
14534
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
92 if (node != null && !visited.isMarked(node)) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
93 if (floatingOnly && node instanceof FixedNode) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
94 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
|
95 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
96 visited.mark(node); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
97 FrameState stateAfter = null; |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
98 if (node instanceof StateSplit) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
99 stateAfter = ((StateSplit) node).stateAfter(); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
100 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
101 for (Node input : node.inputs()) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
102 if (input != stateAfter) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
103 visitForward(nodes, visited, input, true); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
104 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
105 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
106 if (node instanceof EndNode) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
107 EndNode end = (EndNode) node; |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
108 for (PhiNode phi : end.merge().phis()) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
109 visitForward(nodes, visited, phi.valueAt(end), true); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
110 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
111 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
112 nodes.add(node); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
113 if (node instanceof MergeNode) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
114 for (PhiNode phi : ((MergeNode) node).phis()) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
115 visited.mark(phi); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
116 nodes.add(phi); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
117 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
118 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
119 if (stateAfter != null) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
120 visitForward(nodes, visited, stateAfter, true); |
4642
9f781aae2470
separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
121 } |
9f781aae2470
separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
122 } |
14534
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
123 } catch (GraalInternalError e) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
124 e.addContext(node); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
125 throw e; |
4642
9f781aae2470
separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
126 } |
9f781aae2470
separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
127 } |
14534
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
128 |
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 * 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
|
131 * 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
|
132 * |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
133 * 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
|
134 * 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
|
135 */ |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
136 public static boolean assertSchedulableGraph(final StructuredGraph graph) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
137 try { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
138 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
|
139 final IdentityHashMap<LoopBeginNode, NodeBitMap> loopEntryStates = new IdentityHashMap<>(); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
140 schedule.apply(graph, false); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
141 |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
142 BlockIteratorClosure<NodeBitMap> closure = new BlockIteratorClosure<NodeBitMap>() { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
143 |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
144 @Override |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
145 protected List<NodeBitMap> processLoop(Loop loop, NodeBitMap initialState) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
146 return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates; |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
147 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
148 |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
149 @Override |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
150 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
|
151 final List<ScheduledNode> list = schedule.getBlockToNodesMap().get(block); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
152 |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
153 /* |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
154 * 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
|
155 * 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
|
156 * will be checked at the correct position. |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
157 */ |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
158 FrameState pendingStateAfter = null; |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
159 for (final ScheduledNode node : list) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
160 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
|
161 |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
162 if (pendingStateAfter != null && node instanceof FixedNode) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
163 pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
164 public void apply(Node usage, Node nonVirtualNode) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
165 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
|
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 pendingStateAfter = null; |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
169 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
170 |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
171 if (node instanceof MergeNode) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
172 // 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
|
173 currentState.markAll(((MergeNode) node).phis()); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
174 if (node instanceof LoopBeginNode) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
175 // 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
|
176 loopEntryStates.put((LoopBeginNode) node, currentState.copy()); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
177 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
178 } else if (node instanceof ProxyNode) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
179 for (Node input : node.inputs()) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
180 if (input != ((ProxyNode) node).proxyPoint()) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
181 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
|
182 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
183 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
184 } else if (node instanceof LoopExitNode) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
185 // 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
|
186 currentState.clearAll(); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
187 currentState.markAll(loopEntryStates.get(((LoopExitNode) node).loopBegin())); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
188 // 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
|
189 currentState.markAll(((LoopExitNode) node).proxies()); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
190 } else { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
191 for (Node input : node.inputs()) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
192 if (input != stateAfter) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
193 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
|
194 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
195 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
196 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
197 if (node instanceof AbstractEndNode) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
198 MergeNode merge = ((AbstractEndNode) node).merge(); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
199 for (PhiNode phi : merge.phis()) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
200 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
|
201 " in block " + block; |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
202 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
203 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
204 if (stateAfter != null) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
205 assert pendingStateAfter == null; |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
206 pendingStateAfter = stateAfter; |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
207 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
208 currentState.mark(node); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
209 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
210 if (pendingStateAfter != null) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
211 pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
212 public void apply(Node usage, Node nonVirtualNode) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
213 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
|
214 } |
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 return currentState; |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
218 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
219 |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
220 @Override |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
221 protected NodeBitMap merge(Block merge, List<NodeBitMap> states) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
222 NodeBitMap result = states.get(0); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
223 for (int i = 1; i < states.size(); i++) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
224 result.intersect(states.get(i)); |
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 return result; |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
227 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
228 |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
229 @Override |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
230 protected NodeBitMap getInitialState() { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
231 return graph.createNodeBitMap(); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
232 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
233 |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
234 @Override |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
235 protected NodeBitMap cloneState(NodeBitMap oldState) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
236 return oldState.copy(); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
237 } |
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 |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
240 ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock()); |
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 } catch (Throwable t) { |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
243 throw new AssertionError("unschedulable graph", t); |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
244 } |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
245 return true; |
ccf090d3be47
new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents:
13783
diff
changeset
|
246 } |
4642
9f781aae2470
separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff
changeset
|
247 } |