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