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