Line data Source code
1 : /* Generic dominator tree walker
2 : Copyright (C) 2003-2026 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 155522481 : cmp_bb_postorder (const void *a, const void *b, void *data)
133 : {
134 155522481 : basic_block bb1 = *(const basic_block *)(a);
135 155522481 : basic_block bb2 = *(const basic_block *)(b);
136 155522481 : int *bb_postorder = (int *)data;
137 : /* Place higher completion number first (pop off lower number first). */
138 155522481 : 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 98753184 : sort_bbs_postorder (basic_block *bbs, int n, int *bb_postorder)
146 : {
147 98753184 : if (LIKELY (n == 2))
148 : {
149 74951658 : basic_block bb0 = bbs[0], bb1 = bbs[1];
150 74951658 : if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
151 33109373 : bbs[0] = bb1, bbs[1] = bb0;
152 : }
153 23801526 : else if (LIKELY (n == 3))
154 : {
155 20202540 : basic_block bb0 = bbs[0], bb1 = bbs[1], bb2 = bbs[2];
156 20202540 : if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
157 3483855 : std::swap (bb0, bb1);
158 20202540 : if (bb_postorder[bb1->index] < bb_postorder[bb2->index])
159 : {
160 13988212 : std::swap (bb1, bb2);
161 13988212 : if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
162 1285762 : std::swap (bb0, bb1);
163 : }
164 20202540 : bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2;
165 : }
166 : else
167 3598986 : gcc_sort_r (bbs, n, sizeof *bbs, cmp_bb_postorder, bb_postorder);
168 98753184 : }
169 :
170 : /* Set EDGE_EXECUTABLE on every edge within FN's CFG. */
171 :
172 : void
173 6650026 : set_all_edges_as_executable (function *fn)
174 : {
175 6650026 : basic_block bb;
176 77458032 : FOR_ALL_BB_FN (bb, fn)
177 : {
178 70808006 : edge_iterator ei;
179 70808006 : edge e;
180 158068546 : FOR_EACH_EDGE (e, ei, bb->succs)
181 87260540 : e->flags |= EDGE_EXECUTABLE;
182 : }
183 6650026 : }
184 :
185 : /* Constructor for a dom walker. */
186 :
187 47640790 : dom_walker::dom_walker (cdi_direction direction,
188 : enum reachability reachability,
189 47640790 : int *bb_index_to_rpo)
190 47640790 : : m_dom_direction (direction),
191 47640790 : m_reachability (reachability),
192 47640790 : m_user_bb_to_rpo (bb_index_to_rpo != NULL),
193 47640790 : m_unreachable_dom (NULL),
194 47640790 : m_bb_to_rpo (bb_index_to_rpo == (int *)(uintptr_t)-1
195 47640790 : ? NULL : bb_index_to_rpo)
196 : {
197 47640790 : }
198 :
199 : /* Destructor. */
200 :
201 47640790 : dom_walker::~dom_walker ()
202 : {
203 47640790 : if (! m_user_bb_to_rpo)
204 37939456 : free (m_bb_to_rpo);
205 47640790 : }
206 :
207 : /* Return TRUE if BB is reachable, false otherwise. */
208 :
209 : bool
210 963326068 : 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 963326068 : 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 49150848 : bool reachable = false;
221 49150848 : if (!m_unreachable_dom)
222 : {
223 49078442 : reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun);
224 49078442 : edge_iterator ei;
225 49078442 : edge e;
226 112311989 : FOR_EACH_EDGE (e, ei, bb->preds)
227 63233547 : if (!dominated_by_p (CDI_DOMINATORS, e->src, bb))
228 60452743 : 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 58251 : dom_walker::propagate_unreachable_to_edges (basic_block bb,
239 : FILE *dump_file,
240 : dump_flags_t dump_flags)
241 : {
242 58251 : if (dump_file && (dump_flags & TDF_DETAILS))
243 13 : fprintf (dump_file, "Marking all outgoing edges of unreachable "
244 : "BB %d as not executable\n", bb->index);
245 :
246 58251 : edge_iterator ei;
247 58251 : edge e;
248 101156 : FOR_EACH_EDGE (e, ei, bb->succs)
249 42905 : e->flags &= ~EDGE_EXECUTABLE;
250 :
251 127029 : FOR_EACH_EDGE (e, ei, bb->preds)
252 : {
253 68778 : if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
254 : {
255 564 : if (dump_file && (dump_flags & TDF_DETAILS))
256 0 : fprintf (dump_file, "Marking backedge from BB %d into "
257 : "unreachable BB %d as not executable\n",
258 0 : e->src->index, bb->index);
259 564 : e->flags &= ~EDGE_EXECUTABLE;
260 : }
261 : }
262 :
263 58251 : if (!m_unreachable_dom)
264 44096 : m_unreachable_dom = bb;
265 58251 : }
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 41520409 : dom_walker::walk (basic_block bb)
274 : {
275 : /* Compute the basic-block index to RPO mapping lazily. */
276 41520409 : if (!m_user_bb_to_rpo
277 31819075 : && !m_bb_to_rpo
278 31819075 : && m_dom_direction == CDI_DOMINATORS)
279 : {
280 31819075 : int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
281 31819075 : int postorder_num = pre_and_rev_post_order_compute (NULL, postorder,
282 : true);
283 31819075 : m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
284 371279861 : for (int i = 0; i < postorder_num; ++i)
285 339460786 : m_bb_to_rpo[postorder[i]] = i;
286 31819075 : free (postorder);
287 : }
288 :
289 : /* Set up edge flags if need be. */
290 41520409 : if (m_reachability == REACHABLE_BLOCKS)
291 2192413 : set_all_edges_as_executable (cfun);
292 :
293 41520409 : basic_block dest;
294 41520409 : basic_block *worklist = XNEWVEC (basic_block,
295 : n_basic_blocks_for_fn (cfun) * 2);
296 41520409 : int sp = 0;
297 :
298 921805659 : while (true)
299 : {
300 : /* Don't worry about unreachable blocks. */
301 481663034 : if (EDGE_COUNT (bb->preds) > 0
302 40155936 : || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
303 441507098 : || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
304 : {
305 481663034 : 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 481663034 : if (this->bb_reachable (cfun, bb))
310 : {
311 481604783 : taken_edge = before_dom_children (bb);
312 481604783 : if (taken_edge && taken_edge != STOP)
313 : {
314 704598 : edge_iterator ei;
315 704598 : edge e;
316 1572951 : FOR_EACH_EDGE (e, ei, bb->succs)
317 868353 : if (e != taken_edge)
318 163755 : e->flags &= ~EDGE_EXECUTABLE;
319 : }
320 : }
321 : else
322 58251 : 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 481663034 : worklist[sp++] = bb;
327 481663034 : 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 481663034 : if (taken_edge != STOP)
332 : {
333 480498614 : int saved_sp = sp;
334 480498614 : for (dest = first_dom_son (m_dom_direction, bb);
335 920641239 : dest; dest = next_dom_son (m_dom_direction, dest))
336 440142625 : worklist[sp++] = dest;
337 : /* Sort worklist after RPO order if requested. */
338 480498614 : if (sp - saved_sp > 1
339 127064730 : && m_dom_direction == CDI_DOMINATORS
340 127064730 : && m_bb_to_rpo)
341 98753184 : sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp,
342 : m_bb_to_rpo);
343 : }
344 : }
345 : /* NULL is used to mark pop operations in the recursion stack. */
346 963326068 : while (sp > 0 && !worklist[sp - 1])
347 : {
348 481663034 : --sp;
349 481663034 : 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 481663034 : if (bb_reachable (cfun, bb))
354 481604783 : after_dom_children (bb);
355 58251 : else if (m_unreachable_dom == bb)
356 44096 : m_unreachable_dom = NULL;
357 : }
358 481663034 : if (sp)
359 440142625 : bb = worklist[--sp];
360 : else
361 : break;
362 440142625 : }
363 41520409 : free (worklist);
364 41520409 : }
|
