Mercurial > hg > truffle

annotate graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java @ 14889:5accc969c8c7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
use StatelessPostOrderNodeIterator in GraphOrder
author Lukas Stadler <lukas.stadler@oracle.com>
date Mon, 31 Mar 2014 13:45:40 +0200
parents c59eaa8d6632
children 64dcb92ee75a
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 {
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
14889
5accc969c8c7 use StatelessPostOrderNodeIterator in GraphOrder
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14760
diff changeset
83 new StatelessPostOrderNodeIterator(graph.start()) {
13729
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 }