]>
Commit | Line | Data |
---|---|---|
4ee9c684 | 1 | /* Generic dominator tree walker |
71e45bc2 | 2 | Copyright (C) 2003, 2004, 2005, 2007, 2008, 2010, 2012 |
3 | Free Software Foundation, Inc. | |
4ee9c684 | 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 | |
8c4c00c1 | 10 | the Free Software Foundation; either version 3, or (at your option) |
4ee9c684 | 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 | |
8c4c00c1 | 19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ | |
4ee9c684 | 21 | |
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "tm.h" | |
4ee9c684 | 26 | #include "basic-block.h" |
4ee9c684 | 27 | #include "domwalk.h" |
0f71a633 | 28 | #include "sbitmap.h" |
4ee9c684 | 29 | |
48e1416a | 30 | /* This file implements a generic walker for dominator trees. |
4ee9c684 | 31 | |
32 | To understand the dominator walker one must first have a grasp of dominators, | |
33 | immediate dominators and the dominator tree. | |
34 | ||
35 | Dominators | |
36 | A block B1 is said to dominate B2 if every path from the entry to B2 must | |
37 | pass through B1. Given the dominance relationship, we can proceed to | |
38 | compute immediate dominators. Note it is not important whether or not | |
39 | our definition allows a block to dominate itself. | |
40 | ||
41 | Immediate Dominators: | |
42 | Every block in the CFG has no more than one immediate dominator. The | |
43 | immediate dominator of block BB must dominate BB and must not dominate | |
44 | any other dominator of BB and must not be BB itself. | |
45 | ||
46 | Dominator tree: | |
47 | If we then construct a tree where each node is a basic block and there | |
48 | is an edge from each block's immediate dominator to the block itself, then | |
49 | we have a dominator tree. | |
50 | ||
51 | ||
52 | [ Note this walker can also walk the post-dominator tree, which is | |
0c6d8c36 | 53 | defined in a similar manner. i.e., block B1 is said to post-dominate |
4ee9c684 | 54 | block B2 if all paths from B2 to the exit block must pass through |
55 | B1. ] | |
56 | ||
57 | For example, given the CFG | |
58 | ||
59 | 1 | |
60 | | | |
61 | 2 | |
62 | / \ | |
63 | 3 4 | |
64 | / \ | |
65 | +---------->5 6 | |
66 | | / \ / | |
67 | | +--->8 7 | |
68 | | | / | | |
69 | | +--9 11 | |
70 | | / | | |
71 | +--- 10 ---> 12 | |
48e1416a | 72 | |
73 | ||
4ee9c684 | 74 | We have a dominator tree which looks like |
75 | ||
76 | 1 | |
77 | | | |
78 | 2 | |
79 | / \ | |
80 | / \ | |
81 | 3 4 | |
82 | / / \ \ | |
83 | | | | | | |
84 | 5 6 7 12 | |
85 | | | | |
86 | 8 11 | |
87 | | | |
88 | 9 | |
89 | | | |
90 | 10 | |
48e1416a | 91 | |
92 | ||
93 | ||
4ee9c684 | 94 | The dominator tree is the basis for a number of analysis, transformation |
95 | and optimization algorithms that operate on a semi-global basis. | |
48e1416a | 96 | |
4ee9c684 | 97 | The dominator walker is a generic routine which visits blocks in the CFG |
98 | via a depth first search of the dominator tree. In the example above | |
99 | the dominator walker might visit blocks in the following order | |
100 | 1, 2, 3, 4, 5, 8, 9, 10, 6, 7, 11, 12. | |
48e1416a | 101 | |
4ee9c684 | 102 | The dominator walker has a number of callbacks to perform actions |
103 | during the walk of the dominator tree. There are two callbacks | |
104 | which walk statements, one before visiting the dominator children, | |
48e1416a | 105 | one after visiting the dominator children. There is a callback |
4ee9c684 | 106 | before and after each statement walk callback. In addition, the |
107 | dominator walker manages allocation/deallocation of data structures | |
108 | which are local to each block visited. | |
48e1416a | 109 | |
4ee9c684 | 110 | The dominator walker is meant to provide a generic means to build a pass |
111 | which can analyze or transform/optimize a function based on walking | |
112 | the dominator tree. One simply fills in the dominator walker data | |
113 | structure with the appropriate callbacks and calls the walker. | |
48e1416a | 114 | |
4ee9c684 | 115 | We currently use the dominator walker to prune the set of variables |
116 | which might need PHI nodes (which can greatly improve compile-time | |
117 | performance in some cases). | |
48e1416a | 118 | |
4ee9c684 | 119 | We also use the dominator walker to rewrite the function into SSA form |
120 | which reduces code duplication since the rewriting phase is inherently | |
121 | a walk of the dominator tree. | |
122 | ||
80777cd8 | 123 | And (of course), we use the dominator walker to drive our dominator |
4ee9c684 | 124 | optimizer, which is a semi-global optimizer. |
125 | ||
126 | TODO: | |
127 | ||
128 | Walking statements is based on the block statement iterator abstraction, | |
129 | which is currently an abstraction over walking tree statements. Thus | |
130 | the dominator walker is currently only useful for trees. */ | |
131 | ||
132 | /* Recursively walk the dominator tree. | |
133 | ||
134 | WALK_DATA contains a set of callbacks to perform pass-specific | |
135 | actions during the dominator walk as well as a stack of block local | |
136 | data maintained during the dominator walk. | |
137 | ||
138 | BB is the basic block we are currently visiting. */ | |
139 | ||
140 | void | |
141 | walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) | |
142 | { | |
143 | void *bd = NULL; | |
144 | basic_block dest; | |
3100c298 | 145 | basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2); |
146 | int sp = 0; | |
4bb63bc8 | 147 | sbitmap visited = sbitmap_alloc (last_basic_block + 1); |
53c5d9d4 | 148 | bitmap_clear (visited); |
08b7917c | 149 | bitmap_set_bit (visited, ENTRY_BLOCK_PTR->index); |
88dbf20f | 150 | |
3100c298 | 151 | while (true) |
4ee9c684 | 152 | { |
3100c298 | 153 | /* Don't worry about unreachable blocks. */ |
a490a493 | 154 | if (EDGE_COUNT (bb->preds) > 0 |
155 | || bb == ENTRY_BLOCK_PTR | |
156 | || bb == EXIT_BLOCK_PTR) | |
4ee9c684 | 157 | { |
3100c298 | 158 | /* Callback to initialize the local data structure. */ |
159 | if (walk_data->initialize_block_local_data) | |
160 | { | |
161 | bool recycled; | |
162 | ||
75a70cf9 | 163 | /* First get some local data, reusing any local data |
164 | pointer we may have saved. */ | |
f1f41a6c | 165 | if (walk_data->free_block_data.length () > 0) |
3100c298 | 166 | { |
f1f41a6c | 167 | bd = walk_data->free_block_data.pop (); |
3100c298 | 168 | recycled = 1; |
169 | } | |
170 | else | |
171 | { | |
172 | bd = xcalloc (1, walk_data->block_local_data_size); | |
173 | recycled = 0; | |
174 | } | |
175 | ||
176 | /* Push the local data into the local data stack. */ | |
f1f41a6c | 177 | walk_data->block_data_stack.safe_push (bd); |
3100c298 | 178 | |
179 | /* Call the initializer. */ | |
180 | walk_data->initialize_block_local_data (walk_data, bb, | |
181 | recycled); | |
182 | ||
183 | } | |
184 | ||
185 | /* Callback for operations to execute before we have walked the | |
186 | dominator children, but before we walk statements. */ | |
6bf320fb | 187 | if (walk_data->before_dom_children) |
188 | (*walk_data->before_dom_children) (walk_data, bb); | |
3100c298 | 189 | |
08b7917c | 190 | bitmap_set_bit (visited, bb->index); |
4bb63bc8 | 191 | |
3100c298 | 192 | /* Mark the current BB to be popped out of the recursion stack |
f0b5f617 | 193 | once children are processed. */ |
3100c298 | 194 | worklist[sp++] = bb; |
195 | worklist[sp++] = NULL; | |
196 | ||
197 | for (dest = first_dom_son (walk_data->dom_direction, bb); | |
198 | dest; dest = next_dom_son (walk_data->dom_direction, dest)) | |
199 | worklist[sp++] = dest; | |
4ee9c684 | 200 | } |
6bf320fb | 201 | /* NULL is used to mark pop operations in the recursion stack. */ |
3100c298 | 202 | while (sp > 0 && !worklist[sp - 1]) |
4ee9c684 | 203 | { |
3100c298 | 204 | --sp; |
205 | bb = worklist[--sp]; | |
3100c298 | 206 | |
207 | /* Callback for operations to execute after we have walked the | |
6bf320fb | 208 | dominator children, but before we walk statements. */ |
209 | if (walk_data->after_dom_children) | |
210 | (*walk_data->after_dom_children) (walk_data, bb); | |
3100c298 | 211 | |
212 | if (walk_data->initialize_block_local_data) | |
213 | { | |
214 | /* And finally pop the record off the block local data stack. */ | |
f1f41a6c | 215 | bd = walk_data->block_data_stack.pop (); |
3100c298 | 216 | /* And save the block data so that we can re-use it. */ |
f1f41a6c | 217 | walk_data->free_block_data.safe_push (bd); |
3100c298 | 218 | } |
4ee9c684 | 219 | } |
3100c298 | 220 | if (sp) |
4bb63bc8 | 221 | { |
222 | int spp; | |
223 | spp = sp - 1; | |
224 | if (walk_data->dom_direction == CDI_DOMINATORS) | |
225 | /* Find the dominator son that has all its predecessors | |
226 | visited and continue with that. */ | |
227 | while (1) | |
228 | { | |
229 | edge_iterator ei; | |
230 | edge e; | |
231 | bool found = true; | |
232 | bb = worklist[spp]; | |
233 | FOR_EACH_EDGE (e, ei, bb->preds) | |
234 | { | |
235 | if (!dominated_by_p (CDI_DOMINATORS, e->src, e->dest) | |
08b7917c | 236 | && !bitmap_bit_p (visited, e->src->index)) |
4bb63bc8 | 237 | { |
238 | found = false; | |
239 | break; | |
240 | } | |
241 | } | |
242 | if (found) | |
243 | break; | |
244 | /* If we didn't find a dom child with all visited | |
245 | predecessors just use the candidate we were checking. | |
246 | This happens for candidates in irreducible loops. */ | |
247 | if (!worklist[spp - 1]) | |
248 | break; | |
249 | --spp; | |
250 | } | |
251 | bb = worklist[spp]; | |
252 | worklist[spp] = worklist[--sp]; | |
253 | } | |
4ee9c684 | 254 | else |
3100c298 | 255 | break; |
4ee9c684 | 256 | } |
3100c298 | 257 | free (worklist); |
4bb63bc8 | 258 | sbitmap_free (visited); |
4ee9c684 | 259 | } |
260 | ||
261 | void | |
262 | init_walk_dominator_tree (struct dom_walk_data *walk_data) | |
263 | { | |
f1f41a6c | 264 | walk_data->free_block_data.create (0); |
265 | walk_data->block_data_stack.create (0); | |
4ee9c684 | 266 | } |
267 | ||
268 | void | |
269 | fini_walk_dominator_tree (struct dom_walk_data *walk_data) | |
270 | { | |
271 | if (walk_data->initialize_block_local_data) | |
272 | { | |
f1f41a6c | 273 | while (walk_data->free_block_data.length () > 0) |
274 | free (walk_data->free_block_data.pop ()); | |
4ee9c684 | 275 | } |
0c304c96 | 276 | |
f1f41a6c | 277 | walk_data->free_block_data.release (); |
278 | walk_data->block_data_stack.release (); | |
4ee9c684 | 279 | } |