110d565efSmrg /* Generic dominator tree walker
2*ec02198aSmrg Copyright (C) 2003-2020 Free Software Foundation, Inc.
310d565efSmrg Contributed by Diego Novillo <dnovillo@redhat.com>
410d565efSmrg
510d565efSmrg This file is part of GCC.
610d565efSmrg
710d565efSmrg GCC is free software; you can redistribute it and/or modify
810d565efSmrg it under the terms of the GNU General Public License as published by
910d565efSmrg the Free Software Foundation; either version 3, or (at your option)
1010d565efSmrg any later version.
1110d565efSmrg
1210d565efSmrg GCC is distributed in the hope that it will be useful,
1310d565efSmrg but WITHOUT ANY WARRANTY; without even the implied warranty of
1410d565efSmrg MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1510d565efSmrg GNU General Public License for more details.
1610d565efSmrg
1710d565efSmrg You should have received a copy of the GNU General Public License
1810d565efSmrg along with GCC; see the file COPYING3. If not see
1910d565efSmrg <http://www.gnu.org/licenses/>. */
2010d565efSmrg
2110d565efSmrg #include "config.h"
2210d565efSmrg #include "system.h"
2310d565efSmrg #include "coretypes.h"
2410d565efSmrg #include "backend.h"
2510d565efSmrg #include "cfganal.h"
2610d565efSmrg #include "domwalk.h"
2710d565efSmrg #include "dumpfile.h"
2810d565efSmrg
2910d565efSmrg /* This file implements a generic walker for dominator trees.
3010d565efSmrg
3110d565efSmrg To understand the dominator walker one must first have a grasp of dominators,
3210d565efSmrg immediate dominators and the dominator tree.
3310d565efSmrg
3410d565efSmrg Dominators
3510d565efSmrg A block B1 is said to dominate B2 if every path from the entry to B2 must
3610d565efSmrg pass through B1. Given the dominance relationship, we can proceed to
3710d565efSmrg compute immediate dominators. Note it is not important whether or not
3810d565efSmrg our definition allows a block to dominate itself.
3910d565efSmrg
4010d565efSmrg Immediate Dominators:
4110d565efSmrg Every block in the CFG has no more than one immediate dominator. The
4210d565efSmrg immediate dominator of block BB must dominate BB and must not dominate
4310d565efSmrg any other dominator of BB and must not be BB itself.
4410d565efSmrg
4510d565efSmrg Dominator tree:
4610d565efSmrg If we then construct a tree where each node is a basic block and there
4710d565efSmrg is an edge from each block's immediate dominator to the block itself, then
4810d565efSmrg we have a dominator tree.
4910d565efSmrg
5010d565efSmrg
5110d565efSmrg [ Note this walker can also walk the post-dominator tree, which is
5210d565efSmrg defined in a similar manner. i.e., block B1 is said to post-dominate
5310d565efSmrg block B2 if all paths from B2 to the exit block must pass through
5410d565efSmrg B1. ]
5510d565efSmrg
5610d565efSmrg For example, given the CFG
5710d565efSmrg
5810d565efSmrg 1
5910d565efSmrg |
6010d565efSmrg 2
6110d565efSmrg / \
6210d565efSmrg 3 4
6310d565efSmrg / \
6410d565efSmrg +---------->5 6
6510d565efSmrg | / \ /
6610d565efSmrg | +--->8 7
6710d565efSmrg | | / |
6810d565efSmrg | +--9 11
6910d565efSmrg | / |
7010d565efSmrg +--- 10 ---> 12
7110d565efSmrg
7210d565efSmrg
7310d565efSmrg We have a dominator tree which looks like
7410d565efSmrg
7510d565efSmrg 1
7610d565efSmrg |
7710d565efSmrg 2
7810d565efSmrg / \
7910d565efSmrg / \
8010d565efSmrg 3 4
8110d565efSmrg / / \ \
8210d565efSmrg | | | |
8310d565efSmrg 5 6 7 12
8410d565efSmrg | |
8510d565efSmrg 8 11
8610d565efSmrg |
8710d565efSmrg 9
8810d565efSmrg |
8910d565efSmrg 10
9010d565efSmrg
9110d565efSmrg
9210d565efSmrg
9310d565efSmrg The dominator tree is the basis for a number of analysis, transformation
9410d565efSmrg and optimization algorithms that operate on a semi-global basis.
9510d565efSmrg
9610d565efSmrg The dominator walker is a generic routine which visits blocks in the CFG
9710d565efSmrg via a depth first search of the dominator tree. In the example above
9810d565efSmrg the dominator walker might visit blocks in the following order
9910d565efSmrg 1, 2, 3, 4, 5, 8, 9, 10, 6, 7, 11, 12.
10010d565efSmrg
10110d565efSmrg The dominator walker has a number of callbacks to perform actions
10210d565efSmrg during the walk of the dominator tree. There are two callbacks
10310d565efSmrg which walk statements, one before visiting the dominator children,
10410d565efSmrg one after visiting the dominator children. There is a callback
10510d565efSmrg before and after each statement walk callback. In addition, the
10610d565efSmrg dominator walker manages allocation/deallocation of data structures
10710d565efSmrg which are local to each block visited.
10810d565efSmrg
10910d565efSmrg The dominator walker is meant to provide a generic means to build a pass
11010d565efSmrg which can analyze or transform/optimize a function based on walking
11110d565efSmrg the dominator tree. One simply fills in the dominator walker data
11210d565efSmrg structure with the appropriate callbacks and calls the walker.
11310d565efSmrg
11410d565efSmrg We currently use the dominator walker to prune the set of variables
11510d565efSmrg which might need PHI nodes (which can greatly improve compile-time
11610d565efSmrg performance in some cases).
11710d565efSmrg
11810d565efSmrg We also use the dominator walker to rewrite the function into SSA form
11910d565efSmrg which reduces code duplication since the rewriting phase is inherently
12010d565efSmrg a walk of the dominator tree.
12110d565efSmrg
12210d565efSmrg And (of course), we use the dominator walker to drive our dominator
12310d565efSmrg optimizer, which is a semi-global optimizer.
12410d565efSmrg
12510d565efSmrg TODO:
12610d565efSmrg
12710d565efSmrg Walking statements is based on the block statement iterator abstraction,
12810d565efSmrg which is currently an abstraction over walking tree statements. Thus
12910d565efSmrg the dominator walker is currently only useful for trees. */
13010d565efSmrg
13110d565efSmrg static int
cmp_bb_postorder(const void * a,const void * b,void * data)132*ec02198aSmrg cmp_bb_postorder (const void *a, const void *b, void *data)
13310d565efSmrg {
134c7a68eb7Smrg basic_block bb1 = *(const basic_block *)(a);
135c7a68eb7Smrg basic_block bb2 = *(const basic_block *)(b);
136*ec02198aSmrg int *bb_postorder = (int *)data;
13710d565efSmrg /* Place higher completion number first (pop off lower number first). */
138c7a68eb7Smrg return bb_postorder[bb2->index] - bb_postorder[bb1->index];
13910d565efSmrg }
14010d565efSmrg
141c7a68eb7Smrg /* Permute array BBS of N basic blocks in postorder,
142c7a68eb7Smrg i.e. by descending number in BB_POSTORDER array. */
14310d565efSmrg
144c7a68eb7Smrg static void
sort_bbs_postorder(basic_block * bbs,int n,int * bb_postorder)145*ec02198aSmrg sort_bbs_postorder (basic_block *bbs, int n, int *bb_postorder)
14610d565efSmrg {
147c7a68eb7Smrg if (__builtin_expect (n == 2, true))
148c7a68eb7Smrg {
149c7a68eb7Smrg basic_block bb0 = bbs[0], bb1 = bbs[1];
150c7a68eb7Smrg if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
151c7a68eb7Smrg bbs[0] = bb1, bbs[1] = bb0;
152c7a68eb7Smrg }
153c7a68eb7Smrg else if (__builtin_expect (n == 3, true))
154c7a68eb7Smrg {
155c7a68eb7Smrg basic_block bb0 = bbs[0], bb1 = bbs[1], bb2 = bbs[2];
156c7a68eb7Smrg if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
157c7a68eb7Smrg std::swap (bb0, bb1);
158c7a68eb7Smrg if (bb_postorder[bb1->index] < bb_postorder[bb2->index])
159c7a68eb7Smrg {
160c7a68eb7Smrg std::swap (bb1, bb2);
161c7a68eb7Smrg if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
162c7a68eb7Smrg std::swap (bb0, bb1);
163c7a68eb7Smrg }
164c7a68eb7Smrg bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2;
165c7a68eb7Smrg }
166c7a68eb7Smrg else
167*ec02198aSmrg gcc_sort_r (bbs, n, sizeof *bbs, cmp_bb_postorder, bb_postorder);
168c7a68eb7Smrg }
16910d565efSmrg
170c7a68eb7Smrg /* Set EDGE_EXECUTABLE on every edge within FN's CFG. */
171c7a68eb7Smrg
172c7a68eb7Smrg void
set_all_edges_as_executable(function * fn)173c7a68eb7Smrg set_all_edges_as_executable (function *fn)
174c7a68eb7Smrg {
17510d565efSmrg basic_block bb;
176c7a68eb7Smrg FOR_ALL_BB_FN (bb, fn)
17710d565efSmrg {
17810d565efSmrg edge_iterator ei;
17910d565efSmrg edge e;
18010d565efSmrg FOR_EACH_EDGE (e, ei, bb->succs)
18110d565efSmrg e->flags |= EDGE_EXECUTABLE;
18210d565efSmrg }
18310d565efSmrg }
18410d565efSmrg
185c7a68eb7Smrg /* Constructor for a dom walker. */
186c7a68eb7Smrg
dom_walker(cdi_direction direction,enum reachability reachability,int * bb_index_to_rpo)187c7a68eb7Smrg dom_walker::dom_walker (cdi_direction direction,
188c7a68eb7Smrg enum reachability reachability,
189c7a68eb7Smrg int *bb_index_to_rpo)
190c7a68eb7Smrg : m_dom_direction (direction),
1910fc04c29Smrg m_reachability (reachability),
1920fc04c29Smrg m_user_bb_to_rpo (bb_index_to_rpo != NULL),
193c7a68eb7Smrg m_unreachable_dom (NULL),
194c7a68eb7Smrg m_bb_to_rpo (bb_index_to_rpo)
195c7a68eb7Smrg {
196c7a68eb7Smrg }
197c7a68eb7Smrg
198c7a68eb7Smrg /* Destructor. */
199c7a68eb7Smrg
~dom_walker()200c7a68eb7Smrg dom_walker::~dom_walker ()
201c7a68eb7Smrg {
202c7a68eb7Smrg if (! m_user_bb_to_rpo)
203c7a68eb7Smrg free (m_bb_to_rpo);
204c7a68eb7Smrg }
205c7a68eb7Smrg
20610d565efSmrg /* Return TRUE if BB is reachable, false otherwise. */
20710d565efSmrg
20810d565efSmrg bool
bb_reachable(struct function * fun,basic_block bb)20910d565efSmrg dom_walker::bb_reachable (struct function *fun, basic_block bb)
21010d565efSmrg {
21110d565efSmrg /* If we're not skipping unreachable blocks, then assume everything
21210d565efSmrg is reachable. */
2130fc04c29Smrg if (m_reachability == ALL_BLOCKS)
21410d565efSmrg return true;
21510d565efSmrg
21610d565efSmrg /* If any of the predecessor edges that do not come from blocks dominated
21710d565efSmrg by us are still marked as possibly executable consider this block
21810d565efSmrg reachable. */
21910d565efSmrg bool reachable = false;
22010d565efSmrg if (!m_unreachable_dom)
22110d565efSmrg {
22210d565efSmrg reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun);
22310d565efSmrg edge_iterator ei;
22410d565efSmrg edge e;
22510d565efSmrg FOR_EACH_EDGE (e, ei, bb->preds)
22610d565efSmrg if (!dominated_by_p (CDI_DOMINATORS, e->src, bb))
22710d565efSmrg reachable |= (e->flags & EDGE_EXECUTABLE);
22810d565efSmrg }
22910d565efSmrg
23010d565efSmrg return reachable;
23110d565efSmrg }
23210d565efSmrg
23310d565efSmrg /* BB has been determined to be unreachable. Propagate that property
23410d565efSmrg to incoming and outgoing edges of BB as appropriate. */
23510d565efSmrg
23610d565efSmrg void
propagate_unreachable_to_edges(basic_block bb,FILE * dump_file,dump_flags_t dump_flags)23710d565efSmrg dom_walker::propagate_unreachable_to_edges (basic_block bb,
23810d565efSmrg FILE *dump_file,
239c7a68eb7Smrg dump_flags_t dump_flags)
24010d565efSmrg {
24110d565efSmrg if (dump_file && (dump_flags & TDF_DETAILS))
24210d565efSmrg fprintf (dump_file, "Marking all outgoing edges of unreachable "
24310d565efSmrg "BB %d as not executable\n", bb->index);
24410d565efSmrg
24510d565efSmrg edge_iterator ei;
24610d565efSmrg edge e;
24710d565efSmrg FOR_EACH_EDGE (e, ei, bb->succs)
24810d565efSmrg e->flags &= ~EDGE_EXECUTABLE;
24910d565efSmrg
25010d565efSmrg FOR_EACH_EDGE (e, ei, bb->preds)
25110d565efSmrg {
25210d565efSmrg if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
25310d565efSmrg {
25410d565efSmrg if (dump_file && (dump_flags & TDF_DETAILS))
25510d565efSmrg fprintf (dump_file, "Marking backedge from BB %d into "
25610d565efSmrg "unreachable BB %d as not executable\n",
25710d565efSmrg e->src->index, bb->index);
25810d565efSmrg e->flags &= ~EDGE_EXECUTABLE;
25910d565efSmrg }
26010d565efSmrg }
26110d565efSmrg
26210d565efSmrg if (!m_unreachable_dom)
26310d565efSmrg m_unreachable_dom = bb;
26410d565efSmrg }
26510d565efSmrg
266c7a68eb7Smrg const edge dom_walker::STOP = (edge)-1;
267c7a68eb7Smrg
26810d565efSmrg /* Recursively walk the dominator tree.
26910d565efSmrg BB is the basic block we are currently visiting. */
27010d565efSmrg
27110d565efSmrg void
walk(basic_block bb)27210d565efSmrg dom_walker::walk (basic_block bb)
27310d565efSmrg {
2740fc04c29Smrg /* Compute the basic-block index to RPO mapping lazily. */
2750fc04c29Smrg if (!m_bb_to_rpo
2760fc04c29Smrg && m_dom_direction == CDI_DOMINATORS)
2770fc04c29Smrg {
2780fc04c29Smrg int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
2790fc04c29Smrg int postorder_num = pre_and_rev_post_order_compute (NULL, postorder,
2800fc04c29Smrg true);
2810fc04c29Smrg m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
2820fc04c29Smrg for (int i = 0; i < postorder_num; ++i)
2830fc04c29Smrg m_bb_to_rpo[postorder[i]] = i;
2840fc04c29Smrg free (postorder);
2850fc04c29Smrg }
2860fc04c29Smrg
2870fc04c29Smrg /* Set up edge flags if need be. */
2880fc04c29Smrg if (m_reachability == REACHABLE_BLOCKS)
2890fc04c29Smrg set_all_edges_as_executable (cfun);
2900fc04c29Smrg
29110d565efSmrg basic_block dest;
29210d565efSmrg basic_block *worklist = XNEWVEC (basic_block,
29310d565efSmrg n_basic_blocks_for_fn (cfun) * 2);
29410d565efSmrg int sp = 0;
29510d565efSmrg
29610d565efSmrg while (true)
29710d565efSmrg {
29810d565efSmrg /* Don't worry about unreachable blocks. */
29910d565efSmrg if (EDGE_COUNT (bb->preds) > 0
30010d565efSmrg || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
30110d565efSmrg || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
30210d565efSmrg {
303c7a68eb7Smrg edge taken_edge = NULL;
30410d565efSmrg
30510d565efSmrg /* Callback for subclasses to do custom things before we have walked
30610d565efSmrg the dominator children, but before we walk statements. */
30710d565efSmrg if (this->bb_reachable (cfun, bb))
30810d565efSmrg {
309c7a68eb7Smrg taken_edge = before_dom_children (bb);
310c7a68eb7Smrg if (taken_edge && taken_edge != STOP)
31110d565efSmrg {
31210d565efSmrg edge_iterator ei;
31310d565efSmrg edge e;
31410d565efSmrg FOR_EACH_EDGE (e, ei, bb->succs)
31510d565efSmrg if (e != taken_edge)
31610d565efSmrg e->flags &= ~EDGE_EXECUTABLE;
31710d565efSmrg }
31810d565efSmrg }
31910d565efSmrg else
32010d565efSmrg propagate_unreachable_to_edges (bb, dump_file, dump_flags);
32110d565efSmrg
32210d565efSmrg /* Mark the current BB to be popped out of the recursion stack
32310d565efSmrg once children are processed. */
32410d565efSmrg worklist[sp++] = bb;
32510d565efSmrg worklist[sp++] = NULL;
32610d565efSmrg
327c7a68eb7Smrg /* If the callback returned NONE then we are supposed to
328c7a68eb7Smrg stop and not even propagate EDGE_EXECUTABLE further. */
329c7a68eb7Smrg if (taken_edge != STOP)
330c7a68eb7Smrg {
33110d565efSmrg int saved_sp = sp;
33210d565efSmrg for (dest = first_dom_son (m_dom_direction, bb);
33310d565efSmrg dest; dest = next_dom_son (m_dom_direction, dest))
33410d565efSmrg worklist[sp++] = dest;
335c7a68eb7Smrg /* Sort worklist after RPO order if requested. */
336c7a68eb7Smrg if (sp - saved_sp > 1
337c7a68eb7Smrg && m_dom_direction == CDI_DOMINATORS
338c7a68eb7Smrg && m_bb_to_rpo)
339*ec02198aSmrg sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp,
340*ec02198aSmrg m_bb_to_rpo);
34110d565efSmrg }
34210d565efSmrg }
34310d565efSmrg /* NULL is used to mark pop operations in the recursion stack. */
34410d565efSmrg while (sp > 0 && !worklist[sp - 1])
34510d565efSmrg {
34610d565efSmrg --sp;
34710d565efSmrg bb = worklist[--sp];
34810d565efSmrg
34910d565efSmrg /* Callback allowing subclasses to do custom things after we have
35010d565efSmrg walked dominator children, but before we walk statements. */
35110d565efSmrg if (bb_reachable (cfun, bb))
35210d565efSmrg after_dom_children (bb);
35310d565efSmrg else if (m_unreachable_dom == bb)
35410d565efSmrg m_unreachable_dom = NULL;
35510d565efSmrg }
35610d565efSmrg if (sp)
35710d565efSmrg bb = worklist[--sp];
35810d565efSmrg else
35910d565efSmrg break;
36010d565efSmrg }
36110d565efSmrg free (worklist);
36210d565efSmrg }
363