Mercurial > hg > CbC > CbC_gcc
comparison gcc/domwalk.c @ 0:a06113de4d67
first commit
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 17 Jul 2009 14:47:48 +0900 |
parents | |
children | 77e2b8dfacca |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:a06113de4d67 |
---|---|
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 } |