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