|
0
|
1 /* Generic dominator tree walker
|
|
|
2 Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation,
|
|
|
3 Inc.
|
|
|
4 Contributed by Diego Novillo <dnovillo@redhat.com>
|
|
|
5
|
|
|
6 This file is part of GCC.
|
|
|
7
|
|
|
8 GCC is free software; you can redistribute it and/or modify
|
|
|
9 it under the terms of the GNU General Public License as published by
|
|
|
10 the Free Software Foundation; either version 3, or (at your option)
|
|
|
11 any later version.
|
|
|
12
|
|
|
13 GCC is distributed in the hope that it will be useful,
|
|
|
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
16 GNU General Public License for more details.
|
|
|
17
|
|
|
18 You should have received a copy of the GNU General Public License
|
|
|
19 along with GCC; see the file COPYING3. If not see
|
|
|
20 <http://www.gnu.org/licenses/>. */
|
|
|
21
|
|
|
22 #include "config.h"
|
|
|
23 #include "system.h"
|
|
|
24 #include "coretypes.h"
|
|
|
25 #include "tm.h"
|
|
|
26 #include "tree.h"
|
|
|
27 #include "basic-block.h"
|
|
|
28 #include "tree-flow.h"
|
|
|
29 #include "domwalk.h"
|
|
|
30 #include "ggc.h"
|
|
|
31
|
|
|
32 /* This file implements a generic walker for dominator trees.
|
|
|
33
|
|
|
34 To understand the dominator walker one must first have a grasp of dominators,
|
|
|
35 immediate dominators and the dominator tree.
|
|
|
36
|
|
|
37 Dominators
|
|
|
38 A block B1 is said to dominate B2 if every path from the entry to B2 must
|
|
|
39 pass through B1. Given the dominance relationship, we can proceed to
|
|
|
40 compute immediate dominators. Note it is not important whether or not
|
|
|
41 our definition allows a block to dominate itself.
|
|
|
42
|
|
|
43 Immediate Dominators:
|
|
|
44 Every block in the CFG has no more than one immediate dominator. The
|
|
|
45 immediate dominator of block BB must dominate BB and must not dominate
|
|
|
46 any other dominator of BB and must not be BB itself.
|
|
|
47
|
|
|
48 Dominator tree:
|
|
|
49 If we then construct a tree where each node is a basic block and there
|
|
|
50 is an edge from each block's immediate dominator to the block itself, then
|
|
|
51 we have a dominator tree.
|
|
|
52
|
|
|
53
|
|
|
54 [ Note this walker can also walk the post-dominator tree, which is
|
|
|
55 defined in a similar manner. i.e., block B1 is said to post-dominate
|
|
|
56 block B2 if all paths from B2 to the exit block must pass through
|
|
|
57 B1. ]
|
|
|
58
|
|
|
59 For example, given the CFG
|
|
|
60
|
|
|
61 1
|
|
|
62 |
|
|
|
63 2
|
|
|
64 / \
|
|
|
65 3 4
|
|
|
66 / \
|
|
|
67 +---------->5 6
|
|
|
68 | / \ /
|
|
|
69 | +--->8 7
|
|
|
70 | | / |
|
|
|
71 | +--9 11
|
|
|
72 | / |
|
|
|
73 +--- 10 ---> 12
|
|
|
74
|
|
|
75
|
|
|
76 We have a dominator tree which looks like
|
|
|
77
|
|
|
78 1
|
|
|
79 |
|
|
|
80 2
|
|
|
81 / \
|
|
|
82 / \
|
|
|
83 3 4
|
|
|
84 / / \ \
|
|
|
85 | | | |
|
|
|
86 5 6 7 12
|
|
|
87 | |
|
|
|
88 8 11
|
|
|
89 |
|
|
|
90 9
|
|
|
91 |
|
|
|
92 10
|
|
|
93
|
|
|
94
|
|
|
95
|
|
|
96 The dominator tree is the basis for a number of analysis, transformation
|
|
|
97 and optimization algorithms that operate on a semi-global basis.
|
|
|
98
|
|
|
99 The dominator walker is a generic routine which visits blocks in the CFG
|
|
|
100 via a depth first search of the dominator tree. In the example above
|
|
|
101 the dominator walker might visit blocks in the following order
|
|
|
102 1, 2, 3, 4, 5, 8, 9, 10, 6, 7, 11, 12.
|
|
|
103
|
|
|
104 The dominator walker has a number of callbacks to perform actions
|
|
|
105 during the walk of the dominator tree. There are two callbacks
|
|
|
106 which walk statements, one before visiting the dominator children,
|
|
|
107 one after visiting the dominator children. There is a callback
|
|
|
108 before and after each statement walk callback. In addition, the
|
|
|
109 dominator walker manages allocation/deallocation of data structures
|
|
|
110 which are local to each block visited.
|
|
|
111
|
|
|
112 The dominator walker is meant to provide a generic means to build a pass
|
|
|
113 which can analyze or transform/optimize a function based on walking
|
|
|
114 the dominator tree. One simply fills in the dominator walker data
|
|
|
115 structure with the appropriate callbacks and calls the walker.
|
|
|
116
|
|
|
117 We currently use the dominator walker to prune the set of variables
|
|
|
118 which might need PHI nodes (which can greatly improve compile-time
|
|
|
119 performance in some cases).
|
|
|
120
|
|
|
121 We also use the dominator walker to rewrite the function into SSA form
|
|
|
122 which reduces code duplication since the rewriting phase is inherently
|
|
|
123 a walk of the dominator tree.
|
|
|
124
|
|
|
125 And (of course), we use the dominator walker to drive our dominator
|
|
|
126 optimizer, which is a semi-global optimizer.
|
|
|
127
|
|
|
128 TODO:
|
|
|
129
|
|
|
130 Walking statements is based on the block statement iterator abstraction,
|
|
|
131 which is currently an abstraction over walking tree statements. Thus
|
|
|
132 the dominator walker is currently only useful for trees. */
|
|
|
133
|
|
|
134 /* Recursively walk the dominator tree.
|
|
|
135
|
|
|
136 WALK_DATA contains a set of callbacks to perform pass-specific
|
|
|
137 actions during the dominator walk as well as a stack of block local
|
|
|
138 data maintained during the dominator walk.
|
|
|
139
|
|
|
140 BB is the basic block we are currently visiting. */
|
|
|
141
|
|
|
142 void
|
|
|
143 walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb)
|
|
|
144 {
|
|
|
145 void *bd = NULL;
|
|
|
146 basic_block dest;
|
|
|
147 gimple_stmt_iterator gsi;
|
|
|
148 bool is_interesting;
|
|
|
149 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2);
|
|
|
150 int sp = 0;
|
|
|
151
|
|
|
152 while (true)
|
|
|
153 {
|
|
|
154 /* Don't worry about unreachable blocks. */
|
|
|
155 if (EDGE_COUNT (bb->preds) > 0
|
|
|
156 || bb == ENTRY_BLOCK_PTR
|
|
|
157 || bb == EXIT_BLOCK_PTR)
|
|
|
158 {
|
|
|
159 /* If block BB is not interesting to the caller, then none of the
|
|
|
160 callbacks that walk the statements in BB are going to be
|
|
|
161 executed. */
|
|
|
162 is_interesting = walk_data->interesting_blocks == NULL
|
|
|
163 || TEST_BIT (walk_data->interesting_blocks,
|
|
|
164 bb->index);
|
|
|
165
|
|
|
166 /* Callback to initialize the local data structure. */
|
|
|
167 if (walk_data->initialize_block_local_data)
|
|
|
168 {
|
|
|
169 bool recycled;
|
|
|
170
|
|
|
171 /* First get some local data, reusing any local data
|
|
|
172 pointer we may have saved. */
|
|
|
173 if (VEC_length (void_p, walk_data->free_block_data) > 0)
|
|
|
174 {
|
|
|
175 bd = VEC_pop (void_p, walk_data->free_block_data);
|
|
|
176 recycled = 1;
|
|
|
177 }
|
|
|
178 else
|
|
|
179 {
|
|
|
180 bd = xcalloc (1, walk_data->block_local_data_size);
|
|
|
181 recycled = 0;
|
|
|
182 }
|
|
|
183
|
|
|
184 /* Push the local data into the local data stack. */
|
|
|
185 VEC_safe_push (void_p, heap, walk_data->block_data_stack, bd);
|
|
|
186
|
|
|
187 /* Call the initializer. */
|
|
|
188 walk_data->initialize_block_local_data (walk_data, bb,
|
|
|
189 recycled);
|
|
|
190
|
|
|
191 }
|
|
|
192
|
|
|
193 /* Callback for operations to execute before we have walked the
|
|
|
194 dominator children, but before we walk statements. */
|
|
|
195 if (walk_data->before_dom_children_before_stmts)
|
|
|
196 (*walk_data->before_dom_children_before_stmts) (walk_data, bb);
|
|
|
197
|
|
|
198 /* Statement walk before walking dominator children. */
|
|
|
199 if (is_interesting && walk_data->before_dom_children_walk_stmts)
|
|
|
200 {
|
|
|
201 if (walk_data->walk_stmts_backward)
|
|
|
202 for (gsi = gsi_last (bb_seq (bb)); !gsi_end_p (gsi);
|
|
|
203 gsi_prev (&gsi))
|
|
|
204 (*walk_data->before_dom_children_walk_stmts) (walk_data, bb,
|
|
|
205 gsi);
|
|
|
206 else
|
|
|
207 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
208 (*walk_data->before_dom_children_walk_stmts) (walk_data, bb,
|
|
|
209 gsi);
|
|
|
210 }
|
|
|
211
|
|
|
212 /* Callback for operations to execute before we have walked the
|
|
|
213 dominator children, and after we walk statements. */
|
|
|
214 if (walk_data->before_dom_children_after_stmts)
|
|
|
215 (*walk_data->before_dom_children_after_stmts) (walk_data, bb);
|
|
|
216
|
|
|
217 /* Mark the current BB to be popped out of the recursion stack
|
|
|
218 once children are processed. */
|
|
|
219 worklist[sp++] = bb;
|
|
|
220 worklist[sp++] = NULL;
|
|
|
221
|
|
|
222 for (dest = first_dom_son (walk_data->dom_direction, bb);
|
|
|
223 dest; dest = next_dom_son (walk_data->dom_direction, dest))
|
|
|
224 worklist[sp++] = dest;
|
|
|
225 }
|
|
|
226 /* NULL is used to signalize pop operation in recursion stack. */
|
|
|
227 while (sp > 0 && !worklist[sp - 1])
|
|
|
228 {
|
|
|
229 --sp;
|
|
|
230 bb = worklist[--sp];
|
|
|
231 is_interesting = walk_data->interesting_blocks == NULL
|
|
|
232 || TEST_BIT (walk_data->interesting_blocks,
|
|
|
233 bb->index);
|
|
|
234 /* Callback for operations to execute after we have walked the
|
|
|
235 dominator children, but before we walk statements. */
|
|
|
236 if (walk_data->after_dom_children_before_stmts)
|
|
|
237 (*walk_data->after_dom_children_before_stmts) (walk_data, bb);
|
|
|
238
|
|
|
239 /* Statement walk after walking dominator children. */
|
|
|
240 if (is_interesting && walk_data->after_dom_children_walk_stmts)
|
|
|
241 {
|
|
|
242 if (walk_data->walk_stmts_backward)
|
|
|
243 for (gsi = gsi_last (bb_seq (bb)); !gsi_end_p (gsi);
|
|
|
244 gsi_prev (&gsi))
|
|
|
245 (*walk_data->after_dom_children_walk_stmts) (walk_data, bb,
|
|
|
246 gsi);
|
|
|
247 else
|
|
|
248 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
249 (*walk_data->after_dom_children_walk_stmts) (walk_data, bb,
|
|
|
250 gsi);
|
|
|
251 }
|
|
|
252
|
|
|
253 /* Callback for operations to execute after we have walked the
|
|
|
254 dominator children and after we have walked statements. */
|
|
|
255 if (walk_data->after_dom_children_after_stmts)
|
|
|
256 (*walk_data->after_dom_children_after_stmts) (walk_data, bb);
|
|
|
257
|
|
|
258 if (walk_data->initialize_block_local_data)
|
|
|
259 {
|
|
|
260 /* And finally pop the record off the block local data stack. */
|
|
|
261 bd = VEC_pop (void_p, walk_data->block_data_stack);
|
|
|
262 /* And save the block data so that we can re-use it. */
|
|
|
263 VEC_safe_push (void_p, heap, walk_data->free_block_data, bd);
|
|
|
264 }
|
|
|
265 }
|
|
|
266 if (sp)
|
|
|
267 bb = worklist[--sp];
|
|
|
268 else
|
|
|
269 break;
|
|
|
270 }
|
|
|
271 free (worklist);
|
|
|
272 }
|
|
|
273
|
|
|
274 void
|
|
|
275 init_walk_dominator_tree (struct dom_walk_data *walk_data)
|
|
|
276 {
|
|
|
277 walk_data->free_block_data = NULL;
|
|
|
278 walk_data->block_data_stack = NULL;
|
|
|
279 }
|
|
|
280
|
|
|
281 void
|
|
|
282 fini_walk_dominator_tree (struct dom_walk_data *walk_data)
|
|
|
283 {
|
|
|
284 if (walk_data->initialize_block_local_data)
|
|
|
285 {
|
|
|
286 while (VEC_length (void_p, walk_data->free_block_data) > 0)
|
|
|
287 free (VEC_pop (void_p, walk_data->free_block_data));
|
|
|
288 }
|
|
|
289
|
|
|
290 VEC_free (void_p, heap, walk_data->free_block_data);
|
|
|
291 VEC_free (void_p, heap, walk_data->block_data_stack);
|
|
|
292 }
|
