Mercurial > hg > truffle

annotate graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/schedule/SchedulePhase.java @ 5583:8f529640e430

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix to SchedulePhase: correctly handle outer frame states that take a phi from the merge of the inner frame state as an input
author Lukas Stadler <lukas.stadler@jku.at>
date Wed, 13 Jun 2012 11:30:14 +0200
parents b4c406861c33
children d52edd1af4c4
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1 /*
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
2 * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
4 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
7 * published by the Free Software Foundation.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
8 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
13 * accompanied this code).
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
14 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
18 *
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
21 * questions.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
22 */
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
23 package com.oracle.graal.compiler.schedule;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
24
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
25 import java.util.*;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
26
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
27 import com.oracle.max.criutils.*;
5060
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
28 import com.oracle.graal.compiler.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
29 import com.oracle.graal.compiler.phases.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
30 import com.oracle.graal.graph.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
31 import com.oracle.graal.graph.Node.Verbosity;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
32 import com.oracle.graal.lir.cfg.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
33 import com.oracle.graal.nodes.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
34 import com.oracle.graal.nodes.extended.*;
4ed4295ce15f Update import statements.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5059
diff changeset
35 import com.oracle.graal.nodes.virtual.*;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
36
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
37 public class SchedulePhase extends Phase {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
38 private ControlFlowGraph cfg;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
39 private NodeMap<Block> earliestCache;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
40
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
41 /**
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
42 * Map from blocks to the nodes in each block.
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
43 */
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
44 private BlockMap<List<Node>> blockToNodesMap;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
45
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
46 public SchedulePhase() {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
47 super("Schedule");
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
48 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
49
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
50 @Override
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
51 protected void run(StructuredGraph graph) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
52 cfg = ControlFlowGraph.compute(graph, true, true, true, false);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
53 earliestCache = graph.createNodeMap();
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
54 blockToNodesMap = new BlockMap<>(cfg);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
55
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
56 assignBlockToNodes(graph);
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
57 sortNodesWithinBlocks(graph);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
58 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
59
4647
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
60 public void scheduleGraph() {
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
61 for (Block block : cfg.getBlocks()) {
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
62 List<Node> nodeList = blockToNodesMap.get(block);
4647
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
63 ScheduledNode last = null;
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
64 for (Node node : nodeList) {
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
65 if (!(node instanceof FrameState)) {
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
66 if (last != null) {
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
67 last.setScheduledNext((ScheduledNode) node);
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
68 }
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
69 last = (ScheduledNode) node;
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
70 }
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
71 }
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
72 }
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
73 }
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
74
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
75 public ControlFlowGraph getCFG() {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
76 return cfg;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
77 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
78
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
79 /**
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
80 * Gets the map from each block to the nodes in the block.
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
81 */
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
82 public BlockMap<List<Node>> getBlockToNodesMap() {
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
83 return blockToNodesMap;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
84 }
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
85
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
86 /**
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
87 * Gets the nodes in a given block.
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
88 */
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
89 public List<Node> nodesFor(Block block) {
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
90 return blockToNodesMap.get(block);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
91 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
92
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
93 private void assignBlockToNodes(StructuredGraph graph) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
94 for (Block block : cfg.getBlocks()) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
95 List<Node> nodes = new ArrayList<>();
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
96 assert blockToNodesMap.get(block) == null;
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
97 blockToNodesMap.put(block, nodes);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
98 for (Node node : block.getNodes()) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
99 nodes.add(node);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
100 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
101 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
102
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
103 for (Node n : graph.getNodes()) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
104 assignBlockToNode(n);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
105 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
106 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
107
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
108 private void assignBlockToNode(Node n) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
109 if (n == null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
110 return;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
111 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
112
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
113 assert !n.isDeleted();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
114
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
115 Block prevBlock = cfg.getNodeToBlock().get(n);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
116 if (prevBlock != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
117 return;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
118 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
119 assert !(n instanceof PhiNode) : n;
5210
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
120 assert !(n instanceof MergeNode);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
121 // if in CFG, schedule at the latest position possible in the outermost loop possible
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
122 Block latestBlock = latestBlock(n);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
123 Block block;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
124 if (latestBlock == null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
125 block = earliestBlock(n);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
126 } else if (GraalOptions.ScheduleOutOfLoops && !(n instanceof VirtualObjectFieldNode) && !(n instanceof VirtualObjectNode)) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
127 Block earliestBlock = earliestBlock(n);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
128 block = scheduleOutOfLoops(n, latestBlock, earliestBlock);
5583
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
129 assert earliestBlock.dominates(block) : "Graph can not be scheduled : inconsistent for " + n + " (" + earliestBlock + " needs to dominate " + block + ")";
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
130 } else {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
131 block = latestBlock;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
132 }
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
133 cfg.getNodeToBlock().set(n, block);
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
134 blockToNodesMap.get(block).add(n);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
135 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
136
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
137 private Block latestBlock(Node n) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
138 Block block = null;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
139 for (Node succ : n.successors()) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
140 if (succ == null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
141 continue;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
142 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
143 assignBlockToNode(succ);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
144 block = getCommonDominator(block, cfg.getNodeToBlock().get(succ));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
145 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
146 ensureScheduledUsages(n);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
147 CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(block);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
148 for (Node usage : n.usages()) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
149 blocksForUsage(n, usage, cdbc);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
150 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
151 return cdbc.block;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
152 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
153
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
154 private class CommonDominatorBlockClosure implements BlockClosure {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
155 public Block block;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
156 public CommonDominatorBlockClosure(Block block) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
157 this.block = block;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
158 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
159 @Override
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
160 public void apply(Block newBlock) {
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
161 this.block = getCommonDominator(this.block, newBlock);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
162 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
163 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
164
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
165 private Block earliestBlock(Node n) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
166 Block earliest = cfg.getNodeToBlock().get(n);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
167 if (earliest != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
168 return earliest;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
169 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
170 earliest = earliestCache.get(n);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
171 if (earliest != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
172 return earliest;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
173 }
5541
b4c406861c33 More renamings to drop Ri* prefix completely. Deleted graph.BitMap class and replaced with java.util.BitSet.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 5248
diff changeset
174 BitSet bits = new BitSet(cfg.getBlocks().length);
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
175 ArrayList<Node> before = new ArrayList<>();
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
176 if (n.predecessor() != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
177 before.add(n.predecessor());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
178 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
179 for (Node input : n.inputs()) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
180 before.add(input);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
181 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
182 for (Node pred : before) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
183 if (pred == null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
184 continue;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
185 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
186 Block b = earliestBlock(pred);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
187 if (!bits.get(b.getId())) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
188 earliest = b;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
189 do {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
190 bits.set(b.getId());
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
191 b = b.getDominator();
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
192 } while(b != null && !bits.get(b.getId()));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
193 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
194 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
195 if (earliest == null) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
196 Block start = cfg.getNodeToBlock().get(((StructuredGraph) n.graph()).start());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
197 assert start != null;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
198 return start;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
199 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
200 earliestCache.set(n, earliest);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
201 return earliest;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
202 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
203
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
204
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
205 private static Block scheduleOutOfLoops(Node n, Block latestBlock, Block earliest) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
206 assert latestBlock != null : "no latest : " + n;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
207 Block cur = latestBlock;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
208 Block result = latestBlock;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
209 while (cur.getLoop() != null && cur != earliest && cur.getDominator() != null) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
210 Block dom = cur.getDominator();
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
211 if (dom.getLoopDepth() < result.getLoopDepth()) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
212 result = dom;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
213 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
214 cur = dom;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
215 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
216 return result;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
217 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
218
5583
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
219 /**
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
220 * Passes all blocks that a specific usage of a node is in to a given closure.
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
221 * This is more complex than just taking the usage's block because of of PhiNodes and FrameStates.
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
222 *
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
223 * @param node the node that needs to be scheduled
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
224 * @param usage the usage whose blocks need to be considered
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
225 * @param closure the closure that will be called for each block
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
226 */
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
227 private void blocksForUsage(Node node, Node usage, BlockClosure closure) {
5583
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
228 assert !(node instanceof PhiNode);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
229 if (usage instanceof PhiNode) {
5583
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
230 // An input to a PhiNode is used at the end of the predecessor block that corresponds to the PhiNode input.
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
231 // One PhiNode can use an input multiple times, the closure will be called for each usage.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
232 PhiNode phi = (PhiNode) usage;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
233 MergeNode merge = phi.merge();
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
234 Block mergeBlock = cfg.getNodeToBlock().get(merge);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
235 assert mergeBlock != null : "no block for merge " + merge.toString(Verbosity.Id);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
236 for (int i = 0; i < phi.valueCount(); ++i) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
237 if (phi.valueAt(i) == node) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
238 if (mergeBlock.getPredecessors().size() <= i) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
239 TTY.println(merge.toString());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
240 TTY.println(phi.toString());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
241 TTY.println(merge.cfgPredecessors().toString());
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4525
diff changeset
242 TTY.println(mergeBlock.getPredecessors().toString());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
243 TTY.println(phi.inputs().toString());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
244 TTY.println("value count: " + phi.valueCount());
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
245 }
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4525
diff changeset
246 closure.apply(mergeBlock.getPredecessors().get(i));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
247 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
248 }
5583
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
249 } else if (usage instanceof FrameState && ((FrameState) usage).block() != null && !(node instanceof FrameState)) {
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
250 // If a FrameState belongs to a MergeNode then it's inputs will be placed at the common dominator of all EndNodes.
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
251 // BUT only if the input is neither a PhiNode (this method is never called for PhiNodes) nor a FrameState.
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
252 // A FrameState input is an outer FrameState. They should be placed into the same block as the usage, which is handled by the else.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
253 MergeNode merge = ((FrameState) usage).block();
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
254 Block block = null;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
255 for (Node pred : merge.cfgPredecessors()) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
256 block = getCommonDominator(block, cfg.getNodeToBlock().get(pred));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
257 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
258 closure.apply(block);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
259 } else {
5583
8f529640e430 fix to SchedulePhase: correctly handle outer frame states that take a phi from the
Lukas Stadler <lukas.stadler@jku.at>
parents: 5541
diff changeset
260 // All other types of usages: Just put the input into the same block as the usage.
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
261 assignBlockToNode(usage);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
262 closure.apply(cfg.getNodeToBlock().get(usage));
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
263 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
264 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
265
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
266 private void ensureScheduledUsages(Node node) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
267 for (Node usage : node.usages().snapshot()) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
268 assignBlockToNode(usage);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
269 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
270 // now true usages are ready
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
271 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
272
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
273 private static Block getCommonDominator(Block a, Block b) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
274 if (a == null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
275 return b;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
276 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
277 if (b == null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
278 return a;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
279 }
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
280 return ControlFlowGraph.commonDominator(a, b);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
281 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
282
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
283 private void sortNodesWithinBlocks(StructuredGraph graph) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
284 NodeBitMap map = graph.createNodeBitMap();
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
285 for (Block b : cfg.getBlocks()) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
286 sortNodesWithinBlocks(b, map);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
287 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
288 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
289
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
290 private void sortNodesWithinBlocks(Block b, NodeBitMap map) {
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
291 List<Node> instructions = blockToNodesMap.get(b);
4142
bc8527f3071c Adjust code base to new level of warnings.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 3733
diff changeset
292 List<Node> sortedInstructions = new ArrayList<>(instructions.size() + 2);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
293
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
294 assert !map.isMarked(b.getBeginNode()) && cfg.blockFor(b.getBeginNode()) == b;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
295 assert !map.isMarked(b.getEndNode()) && cfg.blockFor(b.getEndNode()) == b;
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
296
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
297 for (Node i : instructions) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
298 addToSorting(b, i, sortedInstructions, map);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
299 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
300
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
301 // Make sure that last node gets really last (i.e. when a frame state successor hangs off it).
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
302 Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
303 if (lastSorted != b.getEndNode()) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
304 int idx = sortedInstructions.indexOf(b.getEndNode());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
305 boolean canNotMove = false;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
306 for (int i = idx + 1; i < sortedInstructions.size(); i++) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
307 if (sortedInstructions.get(i).inputs().contains(b.getEndNode())) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
308 canNotMove = true;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
309 break;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
310 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
311 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
312 if (canNotMove) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
313 if (b.getEndNode() instanceof ControlSplitNode) {
4647
b32ccf2376d2 experimental: scheduling and unscheduling of the whole graph
Lukas Stadler <lukas.stadler@jku.at>
parents: 4629
diff changeset
314 throw new GraalInternalError("Schedule is not possible : needs to move a node after the last node of the block which can not be move").
4629
29da09bf4930 Fix a problem with having a MemoryCheckpoint that is also a ControlSplit (InvokeWithException), the ANY_LOCATION can not be this control split in both branches because it may lead to scheduling problems : make ExceptionObject a MemoryCheckpoint
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4619
diff changeset
315 addContext(lastSorted).
29da09bf4930 Fix a problem with having a MemoryCheckpoint that is also a ControlSplit (InvokeWithException), the ANY_LOCATION can not be this control split in both branches because it may lead to scheduling problems : make ExceptionObject a MemoryCheckpoint
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4619
diff changeset
316 addContext(b.getEndNode());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
317 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
318
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
319 //b.setLastNode(lastSorted);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
320 } else {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
321 sortedInstructions.remove(b.getEndNode());
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
322 sortedInstructions.add(b.getEndNode());
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
323 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
324 }
5248
066f1687ba24 rename: nodesFor -> blockToNodesMap
Doug Simon <doug.simon@oracle.com>
parents: 5210
diff changeset
325 blockToNodesMap.put(b, sortedInstructions);
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
326 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
327
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
328 private void addToSorting(Block b, Node i, List<Node> sortedInstructions, NodeBitMap map) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
329 if (i == null || map.isMarked(i) || cfg.getNodeToBlock().get(i) != b || i instanceof PhiNode || i instanceof LocalNode) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
330 return;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
331 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
332
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
333 FrameState state = null;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
334 WriteNode writeNode = null;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
335 for (Node input : i.inputs()) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4413
diff changeset
336 if (input instanceof WriteNode && !map.isMarked(input) && cfg.getNodeToBlock().get(input) == b) {
3733
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
337 writeNode = (WriteNode) input;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
338 } else if (input instanceof FrameState) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
339 state = (FrameState) input;
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
340 } else {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
341 addToSorting(b, input, sortedInstructions, map);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
342 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
343 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
344
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
345 if (i.predecessor() != null) {
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
346 addToSorting(b, i.predecessor(), sortedInstructions, map);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
347 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
348
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
349 map.mark(i);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
350
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
351 addToSorting(b, state, sortedInstructions, map);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
352 assert writeNode == null || !map.isMarked(writeNode);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
353 addToSorting(b, writeNode, sortedInstructions, map);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
354
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
355 // Now predecessors and inputs are scheduled => we can add this node.
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
356 sortedInstructions.add(i);
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
357 }
e233f5660da4 Added Java files from Maxine project.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
358 }