1 | /* Generic dominator tree walker |
2 | Copyright (C) 2003-2024 Free Software Foundation, Inc. |
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 |
9 | the Free Software Foundation; either version 3, or (at your option) |
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 |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ |
20 | |
21 | #include "config.h" |
22 | #include "system.h" |
23 | #include "coretypes.h" |
24 | #include "backend.h" |
25 | #include "cfganal.h" |
26 | #include "domwalk.h" |
27 | #include "dumpfile.h" |
28 | |
29 | /* This file implements a generic walker for dominator trees. |
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 |
52 | defined in a similar manner. i.e., block B1 is said to post-dominate |
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 |
71 | |
72 | |
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 |
90 | |
91 | |
92 | |
93 | The dominator tree is the basis for a number of analysis, transformation |
94 | and optimization algorithms that operate on a semi-global basis. |
95 | |
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. |
100 | |
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, |
104 | one after visiting the dominator children. There is a callback |
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. |
108 | |
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. |
113 | |
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). |
117 | |
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 | |
122 | And (of course), we use the dominator walker to drive our dominator |
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 | |
131 | static int |
132 | cmp_bb_postorder (const void *a, const void *b, void *data) |
133 | { |
134 | basic_block bb1 = *(const basic_block *)(a); |
135 | basic_block bb2 = *(const basic_block *)(b); |
136 | int *bb_postorder = (int *)data; |
137 | /* Place higher completion number first (pop off lower number first). */ |
138 | return bb_postorder[bb2->index] - bb_postorder[bb1->index]; |
139 | } |
140 | |
141 | /* Permute array BBS of N basic blocks in postorder, |
142 | i.e. by descending number in BB_POSTORDER array. */ |
143 | |
144 | static void |
145 | sort_bbs_postorder (basic_block *bbs, int n, int *bb_postorder) |
146 | { |
147 | if (LIKELY (n == 2)) |
148 | { |
149 | basic_block bb0 = bbs[0], bb1 = bbs[1]; |
150 | if (bb_postorder[bb0->index] < bb_postorder[bb1->index]) |
151 | bbs[0] = bb1, bbs[1] = bb0; |
152 | } |
153 | else if (LIKELY (n == 3)) |
154 | { |
155 | basic_block bb0 = bbs[0], bb1 = bbs[1], bb2 = bbs[2]; |
156 | if (bb_postorder[bb0->index] < bb_postorder[bb1->index]) |
157 | std::swap (a&: bb0, b&: bb1); |
158 | if (bb_postorder[bb1->index] < bb_postorder[bb2->index]) |
159 | { |
160 | std::swap (a&: bb1, b&: bb2); |
161 | if (bb_postorder[bb0->index] < bb_postorder[bb1->index]) |
162 | std::swap (a&: bb0, b&: bb1); |
163 | } |
164 | bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2; |
165 | } |
166 | else |
167 | gcc_sort_r (bbs, n, sizeof *bbs, cmp_bb_postorder, bb_postorder); |
168 | } |
169 | |
170 | /* Set EDGE_EXECUTABLE on every edge within FN's CFG. */ |
171 | |
172 | void |
173 | set_all_edges_as_executable (function *fn) |
174 | { |
175 | basic_block bb; |
176 | FOR_ALL_BB_FN (bb, fn) |
177 | { |
178 | edge_iterator ei; |
179 | edge e; |
180 | FOR_EACH_EDGE (e, ei, bb->succs) |
181 | e->flags |= EDGE_EXECUTABLE; |
182 | } |
183 | } |
184 | |
185 | /* Constructor for a dom walker. */ |
186 | |
187 | dom_walker::dom_walker (cdi_direction direction, |
188 | enum reachability reachability, |
189 | int *bb_index_to_rpo) |
190 | : m_dom_direction (direction), |
191 | m_reachability (reachability), |
192 | m_user_bb_to_rpo (bb_index_to_rpo != NULL), |
193 | m_unreachable_dom (NULL), |
194 | m_bb_to_rpo (bb_index_to_rpo == (int *)(uintptr_t)-1 |
195 | ? NULL : bb_index_to_rpo) |
196 | { |
197 | } |
198 | |
199 | /* Destructor. */ |
200 | |
201 | dom_walker::~dom_walker () |
202 | { |
203 | if (! m_user_bb_to_rpo) |
204 | free (ptr: m_bb_to_rpo); |
205 | } |
206 | |
207 | /* Return TRUE if BB is reachable, false otherwise. */ |
208 | |
209 | bool |
210 | dom_walker::bb_reachable (struct function *fun, basic_block bb) |
211 | { |
212 | /* If we're not skipping unreachable blocks, then assume everything |
213 | is reachable. */ |
214 | if (m_reachability == ALL_BLOCKS) |
215 | return true; |
216 | |
217 | /* If any of the predecessor edges that do not come from blocks dominated |
218 | by us are still marked as possibly executable consider this block |
219 | reachable. */ |
220 | bool reachable = false; |
221 | if (!m_unreachable_dom) |
222 | { |
223 | reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun); |
224 | edge_iterator ei; |
225 | edge e; |
226 | FOR_EACH_EDGE (e, ei, bb->preds) |
227 | if (!dominated_by_p (CDI_DOMINATORS, e->src, bb)) |
228 | reachable |= (e->flags & EDGE_EXECUTABLE); |
229 | } |
230 | |
231 | return reachable; |
232 | } |
233 | |
234 | /* BB has been determined to be unreachable. Propagate that property |
235 | to incoming and outgoing edges of BB as appropriate. */ |
236 | |
237 | void |
238 | dom_walker::propagate_unreachable_to_edges (basic_block bb, |
239 | FILE *dump_file, |
240 | dump_flags_t dump_flags) |
241 | { |
242 | if (dump_file && (dump_flags & TDF_DETAILS)) |
243 | fprintf (stream: dump_file, format: "Marking all outgoing edges of unreachable " |
244 | "BB %d as not executable\n" , bb->index); |
245 | |
246 | edge_iterator ei; |
247 | edge e; |
248 | FOR_EACH_EDGE (e, ei, bb->succs) |
249 | e->flags &= ~EDGE_EXECUTABLE; |
250 | |
251 | FOR_EACH_EDGE (e, ei, bb->preds) |
252 | { |
253 | if (dominated_by_p (CDI_DOMINATORS, e->src, bb)) |
254 | { |
255 | if (dump_file && (dump_flags & TDF_DETAILS)) |
256 | fprintf (stream: dump_file, format: "Marking backedge from BB %d into " |
257 | "unreachable BB %d as not executable\n" , |
258 | e->src->index, bb->index); |
259 | e->flags &= ~EDGE_EXECUTABLE; |
260 | } |
261 | } |
262 | |
263 | if (!m_unreachable_dom) |
264 | m_unreachable_dom = bb; |
265 | } |
266 | |
267 | const edge dom_walker::STOP = (edge)-1; |
268 | |
269 | /* Recursively walk the dominator tree. |
270 | BB is the basic block we are currently visiting. */ |
271 | |
272 | void |
273 | dom_walker::walk (basic_block bb) |
274 | { |
275 | /* Compute the basic-block index to RPO mapping lazily. */ |
276 | if (!m_user_bb_to_rpo |
277 | && !m_bb_to_rpo |
278 | && m_dom_direction == CDI_DOMINATORS) |
279 | { |
280 | int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); |
281 | int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, |
282 | true); |
283 | m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun)); |
284 | for (int i = 0; i < postorder_num; ++i) |
285 | m_bb_to_rpo[postorder[i]] = i; |
286 | free (ptr: postorder); |
287 | } |
288 | |
289 | /* Set up edge flags if need be. */ |
290 | if (m_reachability == REACHABLE_BLOCKS) |
291 | set_all_edges_as_executable (cfun); |
292 | |
293 | basic_block dest; |
294 | basic_block *worklist = XNEWVEC (basic_block, |
295 | n_basic_blocks_for_fn (cfun) * 2); |
296 | int sp = 0; |
297 | |
298 | while (true) |
299 | { |
300 | /* Don't worry about unreachable blocks. */ |
301 | if (EDGE_COUNT (bb->preds) > 0 |
302 | || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) |
303 | || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
304 | { |
305 | edge taken_edge = NULL; |
306 | |
307 | /* Callback for subclasses to do custom things before we have walked |
308 | the dominator children, but before we walk statements. */ |
309 | if (this->bb_reachable (cfun, bb)) |
310 | { |
311 | taken_edge = before_dom_children (bb); |
312 | if (taken_edge && taken_edge != STOP) |
313 | { |
314 | edge_iterator ei; |
315 | edge e; |
316 | FOR_EACH_EDGE (e, ei, bb->succs) |
317 | if (e != taken_edge) |
318 | e->flags &= ~EDGE_EXECUTABLE; |
319 | } |
320 | } |
321 | else |
322 | propagate_unreachable_to_edges (bb, dump_file, dump_flags); |
323 | |
324 | /* Mark the current BB to be popped out of the recursion stack |
325 | once children are processed. */ |
326 | worklist[sp++] = bb; |
327 | worklist[sp++] = NULL; |
328 | |
329 | /* If the callback returned NONE then we are supposed to |
330 | stop and not even propagate EDGE_EXECUTABLE further. */ |
331 | if (taken_edge != STOP) |
332 | { |
333 | int saved_sp = sp; |
334 | for (dest = first_dom_son (m_dom_direction, bb); |
335 | dest; dest = next_dom_son (m_dom_direction, dest)) |
336 | worklist[sp++] = dest; |
337 | /* Sort worklist after RPO order if requested. */ |
338 | if (sp - saved_sp > 1 |
339 | && m_dom_direction == CDI_DOMINATORS |
340 | && m_bb_to_rpo) |
341 | sort_bbs_postorder (bbs: &worklist[saved_sp], n: sp - saved_sp, |
342 | bb_postorder: m_bb_to_rpo); |
343 | } |
344 | } |
345 | /* NULL is used to mark pop operations in the recursion stack. */ |
346 | while (sp > 0 && !worklist[sp - 1]) |
347 | { |
348 | --sp; |
349 | bb = worklist[--sp]; |
350 | |
351 | /* Callback allowing subclasses to do custom things after we have |
352 | walked dominator children, but before we walk statements. */ |
353 | if (bb_reachable (cfun, bb)) |
354 | after_dom_children (bb); |
355 | else if (m_unreachable_dom == bb) |
356 | m_unreachable_dom = NULL; |
357 | } |
358 | if (sp) |
359 | bb = worklist[--sp]; |
360 | else |
361 | break; |
362 | } |
363 | free (ptr: worklist); |
364 | } |
365 | |