Mercurial > hg > truffle

annotate graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java @ 19508:387f86ea4d10

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Speed up ControlFlowGraph#addBranchToLoop.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Thu, 19 Feb 2015 20:31:06 +0100
parents 61d3cb8e1280
children 2d045c20b1fd
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
1 /*
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
2 * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved.
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
4 *
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
7 * published by the Free Software Foundation.
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
8 *
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
13 * accompanied this code).
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
14 *
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
18 *
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
21 * questions.
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
22 */
6529
2e96dc4eb8e2 renamed package: com.oracle.graal.lir.cfg -> com.oracle.graal.nodes.cfg
Doug Simon <doug.simon@oracle.com>
parents: 6411
diff changeset
23 package com.oracle.graal.nodes.cfg;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
24
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
25 import java.util.*;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
26
15193
96bb07a5d667 Spit up and move GraalInternalError.
Josef Eisl <josef.eisl@jku.at>
parents: 15192
diff changeset
27 import com.oracle.graal.compiler.common.*;
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
28 import com.oracle.graal.compiler.common.cfg.*;
5210
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
29 import com.oracle.graal.debug.*;
5060
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.nodes.*;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
32
14791
be2be30c653d Introduce AbstractControlFlowGraph.
Josef Eisl <josef.eisl@jku.at>
parents: 13545
diff changeset
33 public class ControlFlowGraph implements AbstractControlFlowGraph<Block> {
16590
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 16508
diff changeset
34 /**
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 16508
diff changeset
35 * Don't allow probability values to be become too small as this makes frequency calculations
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 16508
diff changeset
36 * large enough that they can overflow the range of a double. This commonly happens with
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 16508
diff changeset
37 * infinite loops within infinite loops.
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 16508
diff changeset
38 */
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 16508
diff changeset
39 public static final double MIN_PROBABILITY = 0.000001;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
40
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
41 public final StructuredGraph graph;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
42
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
43 private final NodeMap<Block> nodeToBlock;
15537
8117e9cadb48 Use List instead of an array in AbstractControlFlowGraph.
Josef Eisl <josef.eisl@jku.at>
parents: 15534
diff changeset
44 private List<Block> reversePostOrder;
15107
1bf700e19e84 Make Loop generic.
Josef Eisl <josef.eisl@jku.at>
parents: 14791
diff changeset
45 private List<Loop<Block>> loops;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
46
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
47 public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
48 ControlFlowGraph cfg = new ControlFlowGraph(graph);
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
49 cfg.identifyBlocks();
9234
b9cf7d0b598e removal of FixedNode.probability (draft)
Christian Haeubl <haeubl@ssw.jku.at>
parents: 7871
diff changeset
50
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
51 if (connectBlocks || computeLoops || computeDominators || computePostdominators) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
52 cfg.connectBlocks();
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
53 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
54 if (computeLoops) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
55 cfg.computeLoopInformation();
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
56 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
57 if (computeDominators) {
16508
79bbd0e9f1c9 Move computeDominators to AbstractControlFlowGraph.
Josef Eisl <josef.eisl@jku.at>
parents: 16503
diff changeset
58 AbstractControlFlowGraph.computeDominators(cfg);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
59 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
60 if (computePostdominators) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
61 cfg.computePostdominators();
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
62 }
9496
13978836b7e2 don't verify ControlFlowGraph when connectBlocks == false
Lukas Stadler <lukas.stadler@jku.at>
parents: 9466
diff changeset
63 // there's not much to verify when connectBlocks == false
9609
c0d76a2ef720 small change to ControlFlowGraph assertion
Lukas Stadler <lukas.stadler@jku.at>
parents: 9496
diff changeset
64 assert !(connectBlocks || computeLoops || computeDominators || computePostdominators) || CFGVerifier.verify(cfg);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
65 return cfg;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
66 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
67
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
68 protected ControlFlowGraph(StructuredGraph graph) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
69 this.graph = graph;
15890
f4510fd9e8b3 Removed unused grow functionality on NodeMap.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 15537
diff changeset
70 this.nodeToBlock = graph.createNodeMap();
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
71 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
72
15537
8117e9cadb48 Use List instead of an array in AbstractControlFlowGraph.
Josef Eisl <josef.eisl@jku.at>
parents: 15534
diff changeset
73 public List<Block> getBlocks() {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
74 return reversePostOrder;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
75 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
76
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
77 public Block getStartBlock() {
15537
8117e9cadb48 Use List instead of an array in AbstractControlFlowGraph.
Josef Eisl <josef.eisl@jku.at>
parents: 15534
diff changeset
78 return reversePostOrder.get(0);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
79 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
80
5458
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
81 public Iterable<Block> postOrder() {
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
82 return new Iterable<Block>() {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
83
5458
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
84 @Override
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
85 public Iterator<Block> iterator() {
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
86 return new Iterator<Block>() {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
87
15537
8117e9cadb48 Use List instead of an array in AbstractControlFlowGraph.
Josef Eisl <josef.eisl@jku.at>
parents: 15534
diff changeset
88 private ListIterator<Block> it = reversePostOrder.listIterator(reversePostOrder.size());
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
89
5458
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
90 @Override
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
91 public boolean hasNext() {
15537
8117e9cadb48 Use List instead of an array in AbstractControlFlowGraph.
Josef Eisl <josef.eisl@jku.at>
parents: 15534
diff changeset
92 return it.hasPrevious();
5458
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
93 }
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
94
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
95 @Override
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
96 public Block next() {
15537
8117e9cadb48 Use List instead of an array in AbstractControlFlowGraph.
Josef Eisl <josef.eisl@jku.at>
parents: 15534
diff changeset
97 return it.previous();
5458
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
98 }
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
99
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
100 @Override
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
101 public void remove() {
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
102 throw new UnsupportedOperationException();
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
103 }
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
104 };
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
105 }
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
106 };
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
107 }
7accd1838b1b quick fix for postdominator calculation
Lukas Stadler <lukas.stadler@jku.at>
parents: 5210
diff changeset
108
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
109 public NodeMap<Block> getNodeToBlock() {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
110 return nodeToBlock;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
111 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
112
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
113 public Block blockFor(Node node) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
114 return nodeToBlock.get(node);
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
115 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
116
15107
1bf700e19e84 Make Loop generic.
Josef Eisl <josef.eisl@jku.at>
parents: 14791
diff changeset
117 public List<Loop<Block>> getLoops() {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
118 return loops;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
119 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
120
9234
b9cf7d0b598e removal of FixedNode.probability (draft)
Christian Haeubl <haeubl@ssw.jku.at>
parents: 7871
diff changeset
121 private void identifyBlock(Block block) {
19331
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
122 AbstractBeginNode start = block.getBeginNode();
10892
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 9609
diff changeset
123
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 9609
diff changeset
124 // assign proxies of a loop exit to this block
19331
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
125 if (start instanceof LoopExitNode) {
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
126 for (Node usage : start.usages()) {
10892
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 9609
diff changeset
127 if (usage instanceof ProxyNode) {
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 9609
diff changeset
128 nodeToBlock.set(usage, block);
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 9609
diff changeset
129 }
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 9609
diff changeset
130 }
19331
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
131 } else if (start instanceof AbstractMergeNode) {
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
132 for (PhiNode phi : ((AbstractMergeNode) start).phis()) {
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
133 nodeToBlock.set(phi, block);
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
134 }
10892
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 9609
diff changeset
135 }
caa8706c6202 CFG: attach proxies to loop exits
Bernhard Urban <bernhard.urban@jku.at>
parents: 9609
diff changeset
136
19331
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
137 FixedWithNextNode cur = start;
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
138 while (true) {
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
139 assert !cur.isDeleted();
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
140 assert nodeToBlock.get(cur) == null;
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
141 nodeToBlock.set(cur, block);
19331
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
142 FixedNode next = cur.next();
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
143 if (next instanceof AbstractBeginNode) {
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
144 block.endNode = cur;
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
145 return;
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
146 } else if (next instanceof FixedWithNextNode) {
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
147 cur = (FixedWithNextNode) next;
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
148 } else {
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
149 nodeToBlock.set(next, block);
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
150 block.endNode = next;
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
151 return;
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
152 }
19331
9a12234da10c Simplification to ControlFlowGraph#identifyBlock.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19259
diff changeset
153 }
7871
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
154 }
886990f21773 memory-aware scheduling phase
Lukas Stadler <lukas.stadler@jku.at>
parents: 7530
diff changeset
155
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
156 private void identifyBlocks() {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
157 // Find all block headers
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
158 int numBlocks = 0;
19403
61d3cb8e1280 Add generic parameter to NodeClass. Change Graph#getNodes(Class) to Graph#getNodes(NodeClass).
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19331
diff changeset
159 for (AbstractBeginNode begin : graph.getNodes(AbstractBeginNode.TYPE)) {
11805
73a886a9564a Make AbstractBeginNode a IterableNodeType and use this in ControlFlowGraph
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 10892
diff changeset
160 Block block = new Block(begin);
73a886a9564a Make AbstractBeginNode a IterableNodeType and use this in ControlFlowGraph
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 10892
diff changeset
161 numBlocks++;
73a886a9564a Make AbstractBeginNode a IterableNodeType and use this in ControlFlowGraph
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 10892
diff changeset
162 identifyBlock(block);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
163 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
164
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
165 // Compute postorder.
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
166 ArrayList<Block> postOrder = new ArrayList<>(numBlocks);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
167 ArrayList<Block> stack = new ArrayList<>();
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
168 stack.add(blockFor(graph.start()));
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
169
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
170 do {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
171 Block block = stack.get(stack.size() - 1);
15157
f4e31f06b019 Create com.oracle.graal.cfg project and move CFG related files.
Josef Eisl <josef.eisl@jku.at>
parents: 15145
diff changeset
172 if (block.getId() == BLOCK_ID_INITIAL) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
173 // First time we see this block: push all successors.
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
174 for (Node suxNode : block.getEndNode().cfgSuccessors()) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
175 Block suxBlock = blockFor(suxNode);
15157
f4e31f06b019 Create com.oracle.graal.cfg project and move CFG related files.
Josef Eisl <josef.eisl@jku.at>
parents: 15145
diff changeset
176 if (suxBlock.getId() == BLOCK_ID_INITIAL) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
177 stack.add(suxBlock);
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
178 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
179 }
15157
f4e31f06b019 Create com.oracle.graal.cfg project and move CFG related files.
Josef Eisl <josef.eisl@jku.at>
parents: 15145
diff changeset
180 block.setId(BLOCK_ID_VISITED);
f4e31f06b019 Create com.oracle.graal.cfg project and move CFG related files.
Josef Eisl <josef.eisl@jku.at>
parents: 15145
diff changeset
181 } else if (block.getId() == BLOCK_ID_VISITED) {
7530
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
182 // Second time we see this block: All successors have been processed, so add block
5e3d1a68664e applied mx eclipseformat to all Java files
Doug Simon <doug.simon@oracle.com>
parents: 7499
diff changeset
183 // to postorder list.
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
184 stack.remove(stack.size() - 1);
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
185 postOrder.add(block);
4522
cf13124efdd9 Restructure phi functions in LIR; Re-enabled C1Visualizer output
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4435
diff changeset
186 } else {
4524
dcc8f5c6f394 Refactorings to prepare for LIR project splitting
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4522
diff changeset
187 throw GraalInternalError.shouldNotReachHere();
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
188 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
189 } while (!stack.isEmpty());
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
190
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
191 // Compute reverse postorder and number blocks.
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
192 assert postOrder.size() <= numBlocks : "some blocks originally created can be unreachable, so actual block list can be shorter";
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
193 numBlocks = postOrder.size();
15537
8117e9cadb48 Use List instead of an array in AbstractControlFlowGraph.
Josef Eisl <josef.eisl@jku.at>
parents: 15534
diff changeset
194 reversePostOrder = new ArrayList<>(numBlocks);
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
195 for (int i = 0; i < numBlocks; i++) {
6411
c5afcc2ebd3d change of project structure: separate compiler and LIR, put EA into separate project
Lukas Stadler <lukas.stadler@jku.at>
parents: 5591
diff changeset
196 Block block = postOrder.get(numBlocks - i - 1);
15157
f4e31f06b019 Create com.oracle.graal.cfg project and move CFG related files.
Josef Eisl <josef.eisl@jku.at>
parents: 15145
diff changeset
197 block.setId(i);
15537
8117e9cadb48 Use List instead of an array in AbstractControlFlowGraph.
Josef Eisl <josef.eisl@jku.at>
parents: 15534
diff changeset
198 reversePostOrder.add(block);
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
199 }
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
200 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
201
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
202 // Connect blocks (including loop backward edges), but ignoring dead code (blocks with id < 0).
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
203 private void connectBlocks() {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
204 for (Block block : reversePostOrder) {
13544
c1b49fd59811 made initial size of block predecessor and successor lists 4 (testing shows this cover 99% of cases)
Doug Simon <doug.simon@oracle.com>
parents: 11805
diff changeset
205 List<Block> predecessors = new ArrayList<>(4);
15507
5fcbf87a58b7 fix block probabilities
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15470
diff changeset
206 double probability = block.getBeginNode() instanceof StartNode ? 1D : 0D;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
207 for (Node predNode : block.getBeginNode().cfgPredecessors()) {
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
208 Block predBlock = nodeToBlock.get(predNode);
15157
f4e31f06b019 Create com.oracle.graal.cfg project and move CFG related files.
Josef Eisl <josef.eisl@jku.at>
parents: 15145
diff changeset
209 if (predBlock.getId() >= 0) {
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
210 predecessors.add(predBlock);
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15199
diff changeset
211 probability += predBlock.probability;
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
212 }
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
213 }
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15199
diff changeset
214 if (predecessors.size() == 1 && predecessors.get(0).getEndNode() instanceof ControlSplitNode) {
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15199
diff changeset
215 probability *= ((ControlSplitNode) predecessors.get(0).getEndNode()).probability(block.getBeginNode());
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15199
diff changeset
216 }
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
217 if (block.getBeginNode() instanceof LoopBeginNode) {
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15199
diff changeset
218 LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode();
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15199
diff changeset
219 probability *= loopBegin.loopFrequency();
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15199
diff changeset
220 for (LoopEndNode predNode : loopBegin.orderedLoopEnds()) {
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
221 Block predBlock = nodeToBlock.get(predNode);
18946
4ac00633d83c Add some assertion messages
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 16590
diff changeset
222 assert predBlock != null : predNode;
15157
f4e31f06b019 Create com.oracle.graal.cfg project and move CFG related files.
Josef Eisl <josef.eisl@jku.at>
parents: 15145
diff changeset
223 if (predBlock.getId() >= 0) {
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
224 predecessors.add(predBlock);
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
225 }
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4525
diff changeset
226 }
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
227 }
16590
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 16508
diff changeset
228 if (probability > 1. / MIN_PROBABILITY) {
c62c1e0060cc Don't allow infinite loops to explode loop frequencies
Tom Rodriguez <tom.rodriguez@oracle.com>
parents: 16508
diff changeset
229 probability = 1. / MIN_PROBABILITY;
15948
6abfac153606 Ensure values stay finite in block probability computation.
Roland Schatz <roland.schatz@oracle.com>
parents: 15890
diff changeset
230 }
15157
f4e31f06b019 Create com.oracle.graal.cfg project and move CFG related files.
Josef Eisl <josef.eisl@jku.at>
parents: 15145
diff changeset
231 block.setPredecessors(predecessors);
15470
c55f44b3c5e5 remove NodesToDoubles, refactoring of node probability and inlining relevance computation
Lukas Stadler <lukas.stadler@oracle.com>
parents: 15199
diff changeset
232 block.setProbability(probability);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
233
13544
c1b49fd59811 made initial size of block predecessor and successor lists 4 (testing shows this cover 99% of cases)
Doug Simon <doug.simon@oracle.com>
parents: 11805
diff changeset
234 List<Block> successors = new ArrayList<>(4);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
235 for (Node suxNode : block.getEndNode().cfgSuccessors()) {
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
236 Block suxBlock = nodeToBlock.get(suxNode);
15157
f4e31f06b019 Create com.oracle.graal.cfg project and move CFG related files.
Josef Eisl <josef.eisl@jku.at>
parents: 15145
diff changeset
237 assert suxBlock.getId() >= 0;
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
238 successors.add(suxBlock);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
239 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
240 if (block.getEndNode() instanceof LoopEndNode) {
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
241 Block suxBlock = nodeToBlock.get(((LoopEndNode) block.getEndNode()).loopBegin());
15157
f4e31f06b019 Create com.oracle.graal.cfg project and move CFG related files.
Josef Eisl <josef.eisl@jku.at>
parents: 15145
diff changeset
242 assert suxBlock.getId() >= 0;
5010
f1cb5fa9a532 Make reverse postorder computation more robust so that it can handle dead code.
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents: 4614
diff changeset
243 successors.add(suxBlock);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
244 }
15157
f4e31f06b019 Create com.oracle.graal.cfg project and move CFG related files.
Josef Eisl <josef.eisl@jku.at>
parents: 15145
diff changeset
245 block.setSuccessors(successors);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
246 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
247 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
248
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
249 private void computeLoopInformation() {
15107
1bf700e19e84 Make Loop generic.
Josef Eisl <josef.eisl@jku.at>
parents: 14791
diff changeset
250 loops = new ArrayList<>();
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
251 for (Block block : reversePostOrder) {
18997
2ccaaf5a6be4 Fix class comparison statements for BeginNode and MergeNode to reflect new class hierarchy.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18995
diff changeset
252 AbstractBeginNode beginNode = block.getBeginNode();
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
253 if (beginNode instanceof LoopBeginNode) {
15109
e17fe8c1287d Introduce HIRLoop.
Josef Eisl <josef.eisl@jku.at>
parents: 15107
diff changeset
254 Loop<Block> loop = new HIRLoop(block.getLoop(), loops.size(), block);
15107
1bf700e19e84 Make Loop generic.
Josef Eisl <josef.eisl@jku.at>
parents: 14791
diff changeset
255 loops.add(loop);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
256
5210
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
257 LoopBeginNode loopBegin = (LoopBeginNode) beginNode;
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
258 for (LoopEndNode end : loopBegin.loopEnds()) {
4614
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4525
diff changeset
259 Block endBlock = nodeToBlock.get(end);
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4525
diff changeset
260 computeLoopBlocks(endBlock, loop);
a3882fd1ae61 Make it possible to have multiple LoopEnds per LoopBegin
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 4525
diff changeset
261 }
5210
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
262
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
263 for (LoopExitNode exit : loopBegin.loopExits()) {
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
264 Block exitBlock = nodeToBlock.get(exit);
7499
ca3e5df0e6cf Small clean up of access to predecessor/successor of blocks.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7498
diff changeset
265 assert exitBlock.getPredecessorCount() == 1;
ca3e5df0e6cf Small clean up of access to predecessor/successor of blocks.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 7498
diff changeset
266 computeLoopBlocks(exitBlock.getFirstPredecessor(), loop);
15534
4bd6ad45ee0a Encapsulate members of Loop.
Josef Eisl <josef.eisl@jku.at>
parents: 15507
diff changeset
267 loop.getExits().add(exitBlock);
5210
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
268 }
19508
387f86ea4d10 Speed up ControlFlowGraph#addBranchToLoop.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19403
diff changeset
269
387f86ea4d10 Speed up ControlFlowGraph#addBranchToLoop.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19403
diff changeset
270 // The following loop can add new blocks to the end of the loop's block list.
387f86ea4d10 Speed up ControlFlowGraph#addBranchToLoop.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19403
diff changeset
271 int size = loop.getBlocks().size();
387f86ea4d10 Speed up ControlFlowGraph#addBranchToLoop.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19403
diff changeset
272 for (int i = 0; i < size; ++i) {
387f86ea4d10 Speed up ControlFlowGraph#addBranchToLoop.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19403
diff changeset
273 Block b = loop.getBlocks().get(i);
5210
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
274 for (Block sux : b.getSuccessors()) {
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
275 if (sux.loop != loop) {
18993
480bd3b1adcd Rename BeginNode => AbstractBeginNode.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 18946
diff changeset
276 AbstractBeginNode begin = sux.getBeginNode();
5210
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
277 if (!(begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == loopBegin)) {
19259
ef87dd54821c Make CFG warnings about loop exists only appear at higher log level
Gilles Duboscq <gilles.m.duboscq@oracle.com>
parents: 18997
diff changeset
278 Debug.log(3, "Unexpected loop exit with %s, including whole branch in the loop", sux);
19508
387f86ea4d10 Speed up ControlFlowGraph#addBranchToLoop.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19403
diff changeset
279 addBranchToLoop(loop, sux);
5210
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
280 }
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
281 }
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
282 }
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
283 }
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
284 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
285 }
5210
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
286 }
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
287
15107
1bf700e19e84 Make Loop generic.
Josef Eisl <josef.eisl@jku.at>
parents: 14791
diff changeset
288 private static void addBranchToLoop(Loop<Block> l, Block b) {
19508
387f86ea4d10 Speed up ControlFlowGraph#addBranchToLoop.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19403
diff changeset
289 if (b.loop == l) {
5210
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
290 return;
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
291 }
19508
387f86ea4d10 Speed up ControlFlowGraph#addBranchToLoop.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 19403
diff changeset
292 assert !(l.getBlocks().contains(b));
15534
4bd6ad45ee0a Encapsulate members of Loop.
Josef Eisl <josef.eisl@jku.at>
parents: 15507
diff changeset
293 l.getBlocks().add(b);
5210
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
294 b.loop = l;
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
295 for (Block sux : b.getSuccessors()) {
e3e7542d78b7 Loop-closed form GraphBuidling
Gilles Duboscq <duboscq@ssw.jku.at>
parents: 5061
diff changeset
296 addBranchToLoop(l, sux);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
297 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
298 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
299
15107
1bf700e19e84 Make Loop generic.
Josef Eisl <josef.eisl@jku.at>
parents: 14791
diff changeset
300 private static void computeLoopBlocks(Block block, Loop<Block> loop) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
301 if (block.getLoop() == loop) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
302 return;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
303 }
15534
4bd6ad45ee0a Encapsulate members of Loop.
Josef Eisl <josef.eisl@jku.at>
parents: 15507
diff changeset
304 assert block.loop == loop.getParent();
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
305 block.loop = loop;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
306
15534
4bd6ad45ee0a Encapsulate members of Loop.
Josef Eisl <josef.eisl@jku.at>
parents: 15507
diff changeset
307 assert !loop.getBlocks().contains(block);
4bd6ad45ee0a Encapsulate members of Loop.
Josef Eisl <josef.eisl@jku.at>
parents: 15507
diff changeset
308 loop.getBlocks().add(block);
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
309
15534
4bd6ad45ee0a Encapsulate members of Loop.
Josef Eisl <josef.eisl@jku.at>
parents: 15507
diff changeset
310 if (block != loop.getHeader()) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
311 for (Block pred : block.getPredecessors()) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
312 computeLoopBlocks(pred, loop);
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
313 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
314 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
315 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
316
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
317 private void computePostdominators() {
9464
b5d83338286f Fix post dominator calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9445
diff changeset
318 outer: for (Block block : postOrder()) {
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
319 if (block.isLoopEnd()) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
320 // We do not want the loop header registered as the postdominator of the loop end.
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
321 continue;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
322 }
9464
b5d83338286f Fix post dominator calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9445
diff changeset
323 if (block.getSuccessorCount() == 0) {
b5d83338286f Fix post dominator calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9445
diff changeset
324 // No successors => no postdominator.
b5d83338286f Fix post dominator calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9445
diff changeset
325 continue;
b5d83338286f Fix post dominator calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9445
diff changeset
326 }
b5d83338286f Fix post dominator calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9445
diff changeset
327 Block firstSucc = block.getSuccessors().get(0);
b5d83338286f Fix post dominator calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9445
diff changeset
328 if (block.getSuccessorCount() == 1) {
9466
b8cae7920bca Fix postorder calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9465
diff changeset
329 block.postdominator = firstSucc;
9465
89c5c388d6d5 Fix for assertion.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9464
diff changeset
330 continue;
9464
b5d83338286f Fix post dominator calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9445
diff changeset
331 }
b5d83338286f Fix post dominator calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9445
diff changeset
332 Block postdominator = firstSucc;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
333 for (Block sux : block.getSuccessors()) {
9464
b5d83338286f Fix post dominator calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9445
diff changeset
334 postdominator = commonPostdominator(postdominator, sux);
b5d83338286f Fix post dominator calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9445
diff changeset
335 if (postdominator == null) {
b5d83338286f Fix post dominator calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9445
diff changeset
336 // There is a dead end => no postdominator available.
b5d83338286f Fix post dominator calculation.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9445
diff changeset
337 continue outer;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
338 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
339 }
9465
89c5c388d6d5 Fix for assertion.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents: 9464
diff changeset
340 assert !block.getSuccessors().contains(postdominator) : "Block " + block + " has a wrong post dominator: " + postdominator;
4435
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
341 block.postdominator = postdominator;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
342 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
343 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
344
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
345 private static Block commonPostdominator(Block a, Block b) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
346 Block iterA = a;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
347 Block iterB = b;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
348 while (iterA != iterB) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
349 if (iterA.getId() < iterB.getId()) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
350 iterA = iterA.getPostdominator();
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
351 if (iterA == null) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
352 return null;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
353 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
354 } else {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
355 assert iterB.getId() < iterA.getId();
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
356 iterB = iterB.getPostdominator();
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
357 if (iterB == null) {
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
358 return null;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
359 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
360 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
361 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
362 return iterA;
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
363 }
57cb8ec5f6bb Restructure block and control flow graph data structures
Christian Wimmer <Christian.Wimmer@Oracle.com>
parents:
diff changeset
364 }