annotate gcc/domwalk.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 /* Generic dominator tree walker
16
kono
parents: 14
diff changeset
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 Contributed by Diego Novillo <dnovillo@redhat.com>
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 This file is part of GCC.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 GCC is free software; you can redistribute it and/or modify
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 it under the terms of the GNU General Public License as published by
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 the Free Software Foundation; either version 3, or (at your option)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 any later version.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 GCC is distributed in the hope that it will be useful,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 GNU General Public License for more details.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 You should have received a copy of the GNU General Public License
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 along with GCC; see the file COPYING3. If not see
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 <http://www.gnu.org/licenses/>. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 #include "config.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 #include "system.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 #include "coretypes.h"
16
kono
parents: 14
diff changeset
24 #include "backend.h"
kono
parents: 14
diff changeset
25 #include "cfganal.h"
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 #include "domwalk.h"
16
kono
parents: 14
diff changeset
27 #include "dumpfile.h"
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
29 /* This file implements a generic walker for dominator trees.
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 To understand the dominator walker one must first have a grasp of dominators,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 immediate dominators and the dominator tree.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
33
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 Dominators
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 A block B1 is said to dominate B2 if every path from the entry to B2 must
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 pass through B1. Given the dominance relationship, we can proceed to
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 compute immediate dominators. Note it is not important whether or not
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 our definition allows a block to dominate itself.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 Immediate Dominators:
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 Every block in the CFG has no more than one immediate dominator. The
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 immediate dominator of block BB must dominate BB and must not dominate
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 any other dominator of BB and must not be BB itself.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
44
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 Dominator tree:
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 If we then construct a tree where each node is a basic block and there
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 is an edge from each block's immediate dominator to the block itself, then
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 we have a dominator tree.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
49
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
50
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 [ Note this walker can also walk the post-dominator tree, which is
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 defined in a similar manner. i.e., block B1 is said to post-dominate
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 block B2 if all paths from B2 to the exit block must pass through
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 B1. ]
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
55
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 For example, given the CFG
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
57
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 1
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 |
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 2
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 / \
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 3 4
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 / \
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 +---------->5 6
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 | / \ /
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 | +--->8 7
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 | | / |
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 | +--9 11
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 | / |
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 +--- 10 ---> 12
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
71
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
72
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 We have a dominator tree which looks like
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 1
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 |
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 2
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 / \
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 / \
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 3 4
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 / / \ \
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
82 | | | |
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 5 6 7 12
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 | |
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 8 11
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 |
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 9
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 |
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 10
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
90
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
91
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
92
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 The dominator tree is the basis for a number of analysis, transformation
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 and optimization algorithms that operate on a semi-global basis.
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
95
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 The dominator walker is a generic routine which visits blocks in the CFG
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 via a depth first search of the dominator tree. In the example above
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 the dominator walker might visit blocks in the following order
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 1, 2, 3, 4, 5, 8, 9, 10, 6, 7, 11, 12.
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
100
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
101 The dominator walker has a number of callbacks to perform actions
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 during the walk of the dominator tree. There are two callbacks
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
103 which walk statements, one before visiting the dominator children,
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
104 one after visiting the dominator children. There is a callback
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
105 before and after each statement walk callback. In addition, the
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
106 dominator walker manages allocation/deallocation of data structures
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 which are local to each block visited.
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
108
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 The dominator walker is meant to provide a generic means to build a pass
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 which can analyze or transform/optimize a function based on walking
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
111 the dominator tree. One simply fills in the dominator walker data
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 structure with the appropriate callbacks and calls the walker.
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
113
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 We currently use the dominator walker to prune the set of variables
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 which might need PHI nodes (which can greatly improve compile-time
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
116 performance in some cases).
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
117
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
118 We also use the dominator walker to rewrite the function into SSA form
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 which reduces code duplication since the rewriting phase is inherently
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 a walk of the dominator tree.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
121
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 And (of course), we use the dominator walker to drive our dominator
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
123 optimizer, which is a semi-global optimizer.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
124
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
125 TODO:
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
126
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 Walking statements is based on the block statement iterator abstraction,
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 which is currently an abstraction over walking tree statements. Thus
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
129 the dominator walker is currently only useful for trees. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
130
16
kono
parents: 14
diff changeset
131 /* Reverse postorder index of each basic block. */
kono
parents: 14
diff changeset
132 static int *bb_postorder;
kono
parents: 14
diff changeset
133
kono
parents: 14
diff changeset
134 static int
kono
parents: 14
diff changeset
135 cmp_bb_postorder (const void *a, const void *b)
kono
parents: 14
diff changeset
136 {
kono
parents: 14
diff changeset
137 basic_block bb1 = *(const basic_block *)(a);
kono
parents: 14
diff changeset
138 basic_block bb2 = *(const basic_block *)(b);
kono
parents: 14
diff changeset
139 /* Place higher completion number first (pop off lower number first). */
kono
parents: 14
diff changeset
140 return bb_postorder[bb2->index] - bb_postorder[bb1->index];
kono
parents: 14
diff changeset
141 }
kono
parents: 14
diff changeset
142
kono
parents: 14
diff changeset
143 /* Permute array BBS of N basic blocks in postorder,
kono
parents: 14
diff changeset
144 i.e. by descending number in BB_POSTORDER array. */
kono
parents: 14
diff changeset
145
kono
parents: 14
diff changeset
146 static void
kono
parents: 14
diff changeset
147 sort_bbs_postorder (basic_block *bbs, int n)
kono
parents: 14
diff changeset
148 {
kono
parents: 14
diff changeset
149 if (__builtin_expect (n == 2, true))
kono
parents: 14
diff changeset
150 {
kono
parents: 14
diff changeset
151 basic_block bb0 = bbs[0], bb1 = bbs[1];
kono
parents: 14
diff changeset
152 if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
kono
parents: 14
diff changeset
153 bbs[0] = bb1, bbs[1] = bb0;
kono
parents: 14
diff changeset
154 }
kono
parents: 14
diff changeset
155 else if (__builtin_expect (n == 3, true))
kono
parents: 14
diff changeset
156 {
kono
parents: 14
diff changeset
157 basic_block bb0 = bbs[0], bb1 = bbs[1], bb2 = bbs[2];
kono
parents: 14
diff changeset
158 if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
kono
parents: 14
diff changeset
159 std::swap (bb0, bb1);
kono
parents: 14
diff changeset
160 if (bb_postorder[bb1->index] < bb_postorder[bb2->index])
kono
parents: 14
diff changeset
161 {
kono
parents: 14
diff changeset
162 std::swap (bb1, bb2);
kono
parents: 14
diff changeset
163 if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
kono
parents: 14
diff changeset
164 std::swap (bb0, bb1);
kono
parents: 14
diff changeset
165 }
kono
parents: 14
diff changeset
166 bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2;
kono
parents: 14
diff changeset
167 }
kono
parents: 14
diff changeset
168 else
kono
parents: 14
diff changeset
169 qsort (bbs, n, sizeof *bbs, cmp_bb_postorder);
kono
parents: 14
diff changeset
170 }
kono
parents: 14
diff changeset
171
kono
parents: 14
diff changeset
172 /* Constructor for a dom walker.
kono
parents: 14
diff changeset
173
kono
parents: 14
diff changeset
174 If SKIP_UNREACHBLE_BLOCKS is true, then we need to set
kono
parents: 14
diff changeset
175 EDGE_EXECUTABLE on every edge in the CFG. */
kono
parents: 14
diff changeset
176 dom_walker::dom_walker (cdi_direction direction,
kono
parents: 14
diff changeset
177 bool skip_unreachable_blocks,
kono
parents: 14
diff changeset
178 int *bb_index_to_rpo)
kono
parents: 14
diff changeset
179 : m_dom_direction (direction),
kono
parents: 14
diff changeset
180 m_skip_unreachable_blocks (skip_unreachable_blocks),
kono
parents: 14
diff changeset
181 m_user_bb_to_rpo (bb_index_to_rpo != NULL),
kono
parents: 14
diff changeset
182 m_unreachable_dom (NULL),
kono
parents: 14
diff changeset
183 m_bb_to_rpo (bb_index_to_rpo)
kono
parents: 14
diff changeset
184 {
kono
parents: 14
diff changeset
185 /* Compute the basic-block index to RPO mapping if not provided by
kono
parents: 14
diff changeset
186 the user. */
kono
parents: 14
diff changeset
187 if (! m_bb_to_rpo && direction == CDI_DOMINATORS)
kono
parents: 14
diff changeset
188 {
kono
parents: 14
diff changeset
189 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
kono
parents: 14
diff changeset
190 int postorder_num = pre_and_rev_post_order_compute (NULL, postorder,
kono
parents: 14
diff changeset
191 true);
kono
parents: 14
diff changeset
192 m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
kono
parents: 14
diff changeset
193 for (int i = 0; i < postorder_num; ++i)
kono
parents: 14
diff changeset
194 m_bb_to_rpo[postorder[i]] = i;
kono
parents: 14
diff changeset
195 free (postorder);
kono
parents: 14
diff changeset
196 }
kono
parents: 14
diff changeset
197
kono
parents: 14
diff changeset
198 /* If we are not skipping unreachable blocks, then there is nothing
kono
parents: 14
diff changeset
199 further to do. */
kono
parents: 14
diff changeset
200 if (!m_skip_unreachable_blocks)
kono
parents: 14
diff changeset
201 return;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
202
16
kono
parents: 14
diff changeset
203 basic_block bb;
kono
parents: 14
diff changeset
204 FOR_ALL_BB_FN (bb, cfun)
kono
parents: 14
diff changeset
205 {
kono
parents: 14
diff changeset
206 edge_iterator ei;
kono
parents: 14
diff changeset
207 edge e;
kono
parents: 14
diff changeset
208 FOR_EACH_EDGE (e, ei, bb->succs)
kono
parents: 14
diff changeset
209 e->flags |= EDGE_EXECUTABLE;
kono
parents: 14
diff changeset
210 }
kono
parents: 14
diff changeset
211 }
kono
parents: 14
diff changeset
212
kono
parents: 14
diff changeset
213 /* Destructor. */
kono
parents: 14
diff changeset
214
kono
parents: 14
diff changeset
215 dom_walker::~dom_walker ()
kono
parents: 14
diff changeset
216 {
kono
parents: 14
diff changeset
217 if (! m_user_bb_to_rpo)
kono
parents: 14
diff changeset
218 free (m_bb_to_rpo);
kono
parents: 14
diff changeset
219 }
kono
parents: 14
diff changeset
220
kono
parents: 14
diff changeset
221 /* Return TRUE if BB is reachable, false otherwise. */
kono
parents: 14
diff changeset
222
kono
parents: 14
diff changeset
223 bool
kono
parents: 14
diff changeset
224 dom_walker::bb_reachable (struct function *fun, basic_block bb)
kono
parents: 14
diff changeset
225 {
kono
parents: 14
diff changeset
226 /* If we're not skipping unreachable blocks, then assume everything
kono
parents: 14
diff changeset
227 is reachable. */
kono
parents: 14
diff changeset
228 if (!m_skip_unreachable_blocks)
kono
parents: 14
diff changeset
229 return true;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
230
16
kono
parents: 14
diff changeset
231 /* If any of the predecessor edges that do not come from blocks dominated
kono
parents: 14
diff changeset
232 by us are still marked as possibly executable consider this block
kono
parents: 14
diff changeset
233 reachable. */
kono
parents: 14
diff changeset
234 bool reachable = false;
kono
parents: 14
diff changeset
235 if (!m_unreachable_dom)
kono
parents: 14
diff changeset
236 {
kono
parents: 14
diff changeset
237 reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun);
kono
parents: 14
diff changeset
238 edge_iterator ei;
kono
parents: 14
diff changeset
239 edge e;
kono
parents: 14
diff changeset
240 FOR_EACH_EDGE (e, ei, bb->preds)
kono
parents: 14
diff changeset
241 if (!dominated_by_p (CDI_DOMINATORS, e->src, bb))
kono
parents: 14
diff changeset
242 reachable |= (e->flags & EDGE_EXECUTABLE);
kono
parents: 14
diff changeset
243 }
kono
parents: 14
diff changeset
244
kono
parents: 14
diff changeset
245 return reachable;
kono
parents: 14
diff changeset
246 }
kono
parents: 14
diff changeset
247
kono
parents: 14
diff changeset
248 /* BB has been determined to be unreachable. Propagate that property
kono
parents: 14
diff changeset
249 to incoming and outgoing edges of BB as appropriate. */
kono
parents: 14
diff changeset
250
kono
parents: 14
diff changeset
251 void
kono
parents: 14
diff changeset
252 dom_walker::propagate_unreachable_to_edges (basic_block bb,
kono
parents: 14
diff changeset
253 FILE *dump_file,
kono
parents: 14
diff changeset
254 dump_flags_t dump_flags)
kono
parents: 14
diff changeset
255 {
kono
parents: 14
diff changeset
256 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
257 fprintf (dump_file, "Marking all outgoing edges of unreachable "
kono
parents: 14
diff changeset
258 "BB %d as not executable\n", bb->index);
kono
parents: 14
diff changeset
259
kono
parents: 14
diff changeset
260 edge_iterator ei;
kono
parents: 14
diff changeset
261 edge e;
kono
parents: 14
diff changeset
262 FOR_EACH_EDGE (e, ei, bb->succs)
kono
parents: 14
diff changeset
263 e->flags &= ~EDGE_EXECUTABLE;
kono
parents: 14
diff changeset
264
kono
parents: 14
diff changeset
265 FOR_EACH_EDGE (e, ei, bb->preds)
kono
parents: 14
diff changeset
266 {
kono
parents: 14
diff changeset
267 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
kono
parents: 14
diff changeset
268 {
kono
parents: 14
diff changeset
269 if (dump_file && (dump_flags & TDF_DETAILS))
kono
parents: 14
diff changeset
270 fprintf (dump_file, "Marking backedge from BB %d into "
kono
parents: 14
diff changeset
271 "unreachable BB %d as not executable\n",
kono
parents: 14
diff changeset
272 e->src->index, bb->index);
kono
parents: 14
diff changeset
273 e->flags &= ~EDGE_EXECUTABLE;
kono
parents: 14
diff changeset
274 }
kono
parents: 14
diff changeset
275 }
kono
parents: 14
diff changeset
276
kono
parents: 14
diff changeset
277 if (!m_unreachable_dom)
kono
parents: 14
diff changeset
278 m_unreachable_dom = bb;
kono
parents: 14
diff changeset
279 }
kono
parents: 14
diff changeset
280
kono
parents: 14
diff changeset
281 const edge dom_walker::STOP = (edge)-1;
kono
parents: 14
diff changeset
282
kono
parents: 14
diff changeset
283 /* Recursively walk the dominator tree.
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
284 BB is the basic block we are currently visiting. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
285
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
286 void
16
kono
parents: 14
diff changeset
287 dom_walker::walk (basic_block bb)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
288 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
289 basic_block dest;
16
kono
parents: 14
diff changeset
290 basic_block *worklist = XNEWVEC (basic_block,
kono
parents: 14
diff changeset
291 n_basic_blocks_for_fn (cfun) * 2);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
292 int sp = 0;
16
kono
parents: 14
diff changeset
293 bb_postorder = m_bb_to_rpo;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
294
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
295 while (true)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
296 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
297 /* Don't worry about unreachable blocks. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
298 if (EDGE_COUNT (bb->preds) > 0
16
kono
parents: 14
diff changeset
299 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
kono
parents: 14
diff changeset
300 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
301 {
16
kono
parents: 14
diff changeset
302 edge taken_edge = NULL;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
303
16
kono
parents: 14
diff changeset
304 /* Callback for subclasses to do custom things before we have walked
kono
parents: 14
diff changeset
305 the dominator children, but before we walk statements. */
kono
parents: 14
diff changeset
306 if (this->bb_reachable (cfun, bb))
kono
parents: 14
diff changeset
307 {
kono
parents: 14
diff changeset
308 taken_edge = before_dom_children (bb);
kono
parents: 14
diff changeset
309 if (taken_edge && taken_edge != STOP)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
310 {
16
kono
parents: 14
diff changeset
311 edge_iterator ei;
kono
parents: 14
diff changeset
312 edge e;
kono
parents: 14
diff changeset
313 FOR_EACH_EDGE (e, ei, bb->succs)
kono
parents: 14
diff changeset
314 if (e != taken_edge)
kono
parents: 14
diff changeset
315 e->flags &= ~EDGE_EXECUTABLE;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
316 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
317 }
16
kono
parents: 14
diff changeset
318 else
kono
parents: 14
diff changeset
319 propagate_unreachable_to_edges (bb, dump_file, dump_flags);
11
b7f97abdc517 update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
320
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
321 /* Mark the current BB to be popped out of the recursion stack
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
322 once children are processed. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
323 worklist[sp++] = bb;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
324 worklist[sp++] = NULL;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
325
16
kono
parents: 14
diff changeset
326 /* If the callback returned NONE then we are supposed to
kono
parents: 14
diff changeset
327 stop and not even propagate EDGE_EXECUTABLE further. */
kono
parents: 14
diff changeset
328 if (taken_edge != STOP)
kono
parents: 14
diff changeset
329 {
kono
parents: 14
diff changeset
330 int saved_sp = sp;
kono
parents: 14
diff changeset
331 for (dest = first_dom_son (m_dom_direction, bb);
kono
parents: 14
diff changeset
332 dest; dest = next_dom_son (m_dom_direction, dest))
kono
parents: 14
diff changeset
333 worklist[sp++] = dest;
kono
parents: 14
diff changeset
334 if (sp - saved_sp > 1 && m_dom_direction == CDI_DOMINATORS)
kono
parents: 14
diff changeset
335 sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp);
kono
parents: 14
diff changeset
336 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
337 }
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
338 /* NULL is used to mark pop operations in the recursion stack. */
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
339 while (sp > 0 && !worklist[sp - 1])
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
340 {
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
341 --sp;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
342 bb = worklist[--sp];
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
343
16
kono
parents: 14
diff changeset
344 /* Callback allowing subclasses to do custom things after we have
kono
parents: 14
diff changeset
345 walked dominator children, but before we walk statements. */
kono
parents: 14
diff changeset
346 if (bb_reachable (cfun, bb))
kono
parents: 14
diff changeset
347 after_dom_children (bb);
kono
parents: 14
diff changeset
348 else if (m_unreachable_dom == bb)
kono
parents: 14
diff changeset
349 m_unreachable_dom = NULL;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
350 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
351 if (sp)
16
kono
parents: 14
diff changeset
352 bb = worklist[--sp];
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
353 else
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
354 break;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
355 }
16
kono
parents: 14
diff changeset
356 bb_postorder = NULL;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
357 free (worklist);
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
358 }