Branch data Line data Source code
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 : 123355767 : cmp_bb_postorder (const void *a, const void *b, void *data)
133 : : {
134 : 123355767 : basic_block bb1 = *(const basic_block *)(a);
135 : 123355767 : basic_block bb2 = *(const basic_block *)(b);
136 : 123355767 : int *bb_postorder = (int *)data;
137 : : /* Place higher completion number first (pop off lower number first). */
138 : 123355767 : 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 : 77952944 : sort_bbs_postorder (basic_block *bbs, int n, int *bb_postorder)
146 : : {
147 : 77952944 : if (LIKELY (n == 2))
148 : : {
149 : 58653888 : basic_block bb0 = bbs[0], bb1 = bbs[1];
150 : 58653888 : if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
151 : 27619099 : bbs[0] = bb1, bbs[1] = bb0;
152 : : }
153 : 19299056 : else if (LIKELY (n == 3))
154 : : {
155 : 16597167 : basic_block bb0 = bbs[0], bb1 = bbs[1], bb2 = bbs[2];
156 : 16597167 : if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
157 : 2857601 : std::swap (bb0, bb1);
158 : 16597167 : if (bb_postorder[bb1->index] < bb_postorder[bb2->index])
159 : : {
160 : 12638663 : std::swap (bb1, bb2);
161 : 12638663 : if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
162 : 1147549 : std::swap (bb0, bb1);
163 : : }
164 : 16597167 : bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2;
165 : : }
166 : : else
167 : 2701889 : gcc_sort_r (bbs, n, sizeof *bbs, cmp_bb_postorder, bb_postorder);
168 : 77952944 : }
169 : :
170 : : /* Set EDGE_EXECUTABLE on every edge within FN's CFG. */
171 : :
172 : : void
173 : 6019846 : set_all_edges_as_executable (function *fn)
174 : : {
175 : 6019846 : basic_block bb;
176 : 68582619 : FOR_ALL_BB_FN (bb, fn)
177 : : {
178 : 62562773 : edge_iterator ei;
179 : 62562773 : edge e;
180 : 139420005 : FOR_EACH_EDGE (e, ei, bb->succs)
181 : 76857232 : e->flags |= EDGE_EXECUTABLE;
182 : : }
183 : 6019846 : }
184 : :
185 : : /* Constructor for a dom walker. */
186 : :
187 : 40001777 : dom_walker::dom_walker (cdi_direction direction,
188 : : enum reachability reachability,
189 : 40001777 : int *bb_index_to_rpo)
190 : 40001777 : : m_dom_direction (direction),
191 : 40001777 : m_reachability (reachability),
192 : 40001777 : m_user_bb_to_rpo (bb_index_to_rpo != NULL),
193 : 40001777 : m_unreachable_dom (NULL),
194 : 40001777 : m_bb_to_rpo (bb_index_to_rpo == (int *)(uintptr_t)-1
195 : 40001777 : ? NULL : bb_index_to_rpo)
196 : : {
197 : 40001777 : }
198 : :
199 : : /* Destructor. */
200 : :
201 : 40001777 : dom_walker::~dom_walker ()
202 : : {
203 : 40001777 : if (! m_user_bb_to_rpo)
204 : 34773614 : free (m_bb_to_rpo);
205 : 40001777 : }
206 : :
207 : : /* Return TRUE if BB is reachable, false otherwise. */
208 : :
209 : : bool
210 : 766281896 : 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 : 766281896 : 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 : 44053042 : bool reachable = false;
221 : 44053042 : if (!m_unreachable_dom)
222 : : {
223 : 44002032 : reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun);
224 : 44002032 : edge_iterator ei;
225 : 44002032 : edge e;
226 : 100326700 : FOR_EACH_EDGE (e, ei, bb->preds)
227 : 56324668 : if (!dominated_by_p (CDI_DOMINATORS, e->src, bb))
228 : 53950556 : 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 : 40500 : dom_walker::propagate_unreachable_to_edges (basic_block bb,
239 : : FILE *dump_file,
240 : : dump_flags_t dump_flags)
241 : : {
242 : 40500 : 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 : 40500 : edge_iterator ei;
247 : 40500 : edge e;
248 : 75581 : FOR_EACH_EDGE (e, ei, bb->succs)
249 : 35081 : e->flags &= ~EDGE_EXECUTABLE;
250 : :
251 : 85208 : FOR_EACH_EDGE (e, ei, bb->preds)
252 : : {
253 : 44708 : if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
254 : : {
255 : 439 : 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 : 439 : e->flags &= ~EDGE_EXECUTABLE;
260 : : }
261 : : }
262 : :
263 : 40500 : if (!m_unreachable_dom)
264 : 29990 : m_unreachable_dom = bb;
265 : 40500 : }
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 : 34479800 : dom_walker::walk (basic_block bb)
274 : : {
275 : : /* Compute the basic-block index to RPO mapping lazily. */
276 : 34479800 : if (!m_user_bb_to_rpo
277 : 29251637 : && !m_bb_to_rpo
278 : 29251637 : && m_dom_direction == CDI_DOMINATORS)
279 : : {
280 : 29251637 : int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
281 : 29251637 : int postorder_num = pre_and_rev_post_order_compute (NULL, postorder,
282 : : true);
283 : 29251637 : m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
284 : 333714108 : for (int i = 0; i < postorder_num; ++i)
285 : 304462471 : m_bb_to_rpo[postorder[i]] = i;
286 : 29251637 : free (postorder);
287 : : }
288 : :
289 : : /* Set up edge flags if need be. */
290 : 34479800 : if (m_reachability == REACHABLE_BLOCKS)
291 : 1944572 : set_all_edges_as_executable (cfun);
292 : :
293 : 34479800 : basic_block dest;
294 : 34479800 : basic_block *worklist = XNEWVEC (basic_block,
295 : : n_basic_blocks_for_fn (cfun) * 2);
296 : 34479800 : int sp = 0;
297 : :
298 : 731802096 : while (true)
299 : : {
300 : : /* Don't worry about unreachable blocks. */
301 : 383140948 : if (EDGE_COUNT (bb->preds) > 0
302 : 33288258 : || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
303 : 349852690 : || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
304 : : {
305 : 383140948 : 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 : 383140948 : if (this->bb_reachable (cfun, bb))
310 : : {
311 : 383100448 : taken_edge = before_dom_children (bb);
312 : 383100448 : if (taken_edge && taken_edge != STOP)
313 : : {
314 : 644298 : edge_iterator ei;
315 : 644298 : edge e;
316 : 1374413 : FOR_EACH_EDGE (e, ei, bb->succs)
317 : 730115 : if (e != taken_edge)
318 : 85817 : e->flags &= ~EDGE_EXECUTABLE;
319 : : }
320 : : }
321 : : else
322 : 40500 : 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 : 383140948 : worklist[sp++] = bb;
327 : 383140948 : 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 : 383140948 : if (taken_edge != STOP)
332 : : {
333 : 382146838 : int saved_sp = sp;
334 : 382146838 : for (dest = first_dom_son (m_dom_direction, bb);
335 : 730807986 : dest; dest = next_dom_son (m_dom_direction, dest))
336 : 348661148 : worklist[sp++] = dest;
337 : : /* Sort worklist after RPO order if requested. */
338 : 382146838 : if (sp - saved_sp > 1
339 : 101230003 : && m_dom_direction == CDI_DOMINATORS
340 : 101230003 : && m_bb_to_rpo)
341 : 77952944 : 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 : 766281896 : while (sp > 0 && !worklist[sp - 1])
347 : : {
348 : 383140948 : --sp;
349 : 383140948 : 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 : 383140948 : if (bb_reachable (cfun, bb))
354 : 383100448 : after_dom_children (bb);
355 : 40500 : else if (m_unreachable_dom == bb)
356 : 29990 : m_unreachable_dom = NULL;
357 : : }
358 : 383140948 : if (sp)
359 : 348661148 : bb = worklist[--sp];
360 : : else
361 : : break;
362 : 348661148 : }
363 : 34479800 : free (worklist);
364 : 34479800 : }
|
