Mercurial > hg > truffle

annotate graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java @ 15192:644dfe49c0f4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Move packages com.oracle.graal.cfg to com.oracle.graal.compiler.common.cfg.
author Josef Eisl <josef.eisl@jku.at>
date Thu, 17 Apr 2014 13:18:18 +0200
parents f4e31f06b019
children 96bb07a5d667
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
15192
644dfe49c0f4 Move packages com.oracle.graal.cfg to com.oracle.graal.compiler.common.cfg.
Josef Eisl <josef.eisl@jku.at>
parents: 15157
diff changeset
27 import com.oracle.graal.compiler.common.cfg.*;
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
28 import com.oracle.graal.graph.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
29 import com.oracle.graal.nodes.*;
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
30 import com.oracle.graal.nodes.VirtualState.NodeClosure;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
31 import com.oracle.graal.nodes.cfg.*;
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
32 import com.oracle.graal.phases.graph.*;
14991
64dcb92ee75a Truffle: Change signature for Truffle calls from (PackedFrame, Arguments) to (Object[]).
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 14889
diff changeset
33 import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
34 import com.oracle.graal.phases.schedule.*;
14991
64dcb92ee75a Truffle: Change signature for Truffle calls from (PackedFrame, Arguments) to (Object[]).
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 14889
diff changeset
35 import com.oracle.graal.phases.schedule.SchedulePhase.MemoryScheduling;
64dcb92ee75a Truffle: Change signature for Truffle calls from (PackedFrame, Arguments) to (Object[]).
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 14889
diff changeset
36 import com.oracle.graal.phases.schedule.SchedulePhase.SchedulingStrategy;
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
37
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
38 public final class GraphOrder {
4642
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 private GraphOrder() {
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
41 }
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
42
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
43 /**
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
44 * 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
45 * 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
46 * this list checks whether inputs are scheduled before their usages.
15002
06e50d290784 isAllowedUsageType on Nodes
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
47 *
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
48 * @param graph the graph to be checked.
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
49 * @throws AssertionError if a cycle was detected.
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
50 */
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
51 public static boolean assertNonCyclicGraph(StructuredGraph graph) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
52 List<Node> order = createOrder(graph);
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
53 NodeBitMap visited = graph.createNodeBitMap();
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
54 visited.clearAll();
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
55 for (Node node : order) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
56 if (node instanceof PhiNode && ((PhiNode) node).merge() instanceof LoopBeginNode) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
57 assert visited.isMarked(((PhiNode) node).valueAt(0));
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
58 // nothing to do
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
59 } else {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
60 for (Node input : node.inputs()) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
61 if (!visited.isMarked(input)) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
62 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
63 // nothing to do - after frame states are known, allowed cycles
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
64 } else {
15035
bfad6492cce9 re-enable graph ordering assertion
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15002
diff changeset
65 assert false : "unexpected cycle detected at input " + node + " -> " + input;
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
66 }
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
67 }
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
68 }
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 visited.mark(node);
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 return true;
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
73 }
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
74
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
75 private static List<Node> createOrder(StructuredGraph graph) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
76 final ArrayList<Node> nodes = new ArrayList<>();
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
77 final NodeBitMap visited = graph.createNodeBitMap();
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
78
14889
5accc969c8c7 use StatelessPostOrderNodeIterator in GraphOrder
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14760
diff changeset
79 new StatelessPostOrderNodeIterator(graph.start()) {
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
80 @Override
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
81 protected void node(FixedNode node) {
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
82 visitForward(nodes, visited, node, false);
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
83 }
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
84 }.apply();
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
85 return nodes;
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
86 }
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
87
13729
9a6faa08bffe cyclic graph verification
Lukas Stadler <lukas.stadler@jku.at>
parents: 11641
diff changeset
88 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
89 try {
14547
0d5923064a88 fixed some findbugs issues
Doug Simon <doug.simon@oracle.com>
parents: 14534
diff changeset
90 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
91 if (node != null && !visited.isMarked(node)) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
92 if (floatingOnly && node instanceof FixedNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
93 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
94 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
95 visited.mark(node);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
96 FrameState stateAfter = null;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
97 if (node instanceof StateSplit) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
98 stateAfter = ((StateSplit) node).stateAfter();
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
99 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
100 for (Node input : node.inputs()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
101 if (input != stateAfter) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
102 visitForward(nodes, visited, input, true);
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 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
105 if (node instanceof EndNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
106 EndNode end = (EndNode) node;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
107 for (PhiNode phi : end.merge().phis()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
108 visitForward(nodes, visited, phi.valueAt(end), true);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
109 }
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 nodes.add(node);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
112 if (node instanceof MergeNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
113 for (PhiNode phi : ((MergeNode) node).phis()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
114 visited.mark(phi);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
115 nodes.add(phi);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
116 }
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 if (stateAfter != null) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
119 visitForward(nodes, visited, stateAfter, true);
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
120 }
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
121 }
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
122 } catch (GraalInternalError e) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
123 e.addContext(node);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
124 throw e;
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
125 }
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
126 }
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
127
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 * 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
130 * at the position where it is scheduled. This is a very expensive assertion.
15002
06e50d290784 isAllowedUsageType on Nodes
Lukas Stadler <lukas.stadler@oracle.com>
parents: 14991
diff changeset
131 *
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
132 * 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
133 * 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
134 */
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
135 public static boolean assertSchedulableGraph(final StructuredGraph graph) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
136 try {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
137 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
138 final IdentityHashMap<LoopBeginNode, NodeBitMap> loopEntryStates = new IdentityHashMap<>();
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
139 schedule.apply(graph, false);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
140
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
141 BlockIteratorClosure<NodeBitMap> closure = new BlockIteratorClosure<NodeBitMap>() {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
142
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
143 @Override
15107
1bf700e19e84 Make Loop generic.
Josef Eisl <josef.eisl@jku.at>
parents: 15035
diff changeset
144 protected List<NodeBitMap> processLoop(Loop<Block> loop, NodeBitMap initialState) {
14534
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
145 return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates;
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
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
148 @Override
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
149 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
150 final List<ScheduledNode> list = schedule.getBlockToNodesMap().get(block);
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 /*
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
153 * 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
154 * 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
155 * will be checked at the correct position.
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 FrameState pendingStateAfter = null;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
158 for (final ScheduledNode node : list) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
159 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
160
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
161 if (pendingStateAfter != null && node instanceof FixedNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
162 pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
163 public void apply(Node usage, Node nonVirtualNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
164 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
165 }
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 pendingStateAfter = null;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
168 }
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 if (node instanceof MergeNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
171 // 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
172 currentState.markAll(((MergeNode) node).phis());
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
173 if (node instanceof LoopBeginNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
174 // 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
175 loopEntryStates.put((LoopBeginNode) node, currentState.copy());
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
176 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
177 } else if (node instanceof ProxyNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
178 for (Node input : node.inputs()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
179 if (input != ((ProxyNode) node).proxyPoint()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
180 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
181 }
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 } else if (node instanceof LoopExitNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
184 // 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
185 currentState.clearAll();
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
186 currentState.markAll(loopEntryStates.get(((LoopExitNode) node).loopBegin()));
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
187 // 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
188 currentState.markAll(((LoopExitNode) node).proxies());
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
189 } else {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
190 for (Node input : node.inputs()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
191 if (input != stateAfter) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
192 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
193 }
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 if (node instanceof AbstractEndNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
197 MergeNode merge = ((AbstractEndNode) node).merge();
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
198 for (PhiNode phi : merge.phis()) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
199 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
200 " in block " + block;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
201 }
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 if (stateAfter != null) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
204 assert pendingStateAfter == null;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
205 pendingStateAfter = stateAfter;
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 currentState.mark(node);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
208 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
209 if (pendingStateAfter != null) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
210 pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
211 public void apply(Node usage, Node nonVirtualNode) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
212 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
213 }
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 return currentState;
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 @Override
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
220 protected NodeBitMap merge(Block merge, List<NodeBitMap> states) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
221 NodeBitMap result = states.get(0);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
222 for (int i = 1; i < states.size(); i++) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
223 result.intersect(states.get(i));
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
224 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
225 return result;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
226 }
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 @Override
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
229 protected NodeBitMap getInitialState() {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
230 return graph.createNodeBitMap();
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
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
233 @Override
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
234 protected NodeBitMap cloneState(NodeBitMap oldState) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
235 return oldState.copy();
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 };
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 ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock());
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 } catch (Throwable t) {
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
242 throw new AssertionError("unschedulable graph", t);
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
243 }
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
244 return true;
ccf090d3be47 new graph ordering assertion mechanism
Lukas Stadler <lukas.stadler@oracle.com>
parents: 13783
diff changeset
245 }
4642
9f781aae2470 separate GraphOrder from EscapeAnalysisPhase
Lukas Stadler <lukas.stadler@jku.at>
parents:
diff changeset
246 }