/* Generic dominator tree walker
- Copyright (C) 2003-2017 Free Software Foundation, Inc.
+ Copyright (C) 2003-2020 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
This file is part of GCC.
which is currently an abstraction over walking tree statements. Thus
the dominator walker is currently only useful for trees. */
-/* Reverse postorder index of each basic block. */
-static int *bb_postorder;
-
static int
-cmp_bb_postorder (const void *a, const void *b)
+cmp_bb_postorder (const void *a, const void *b, void *data)
{
basic_block bb1 = *(const basic_block *)(a);
basic_block bb2 = *(const basic_block *)(b);
+ int *bb_postorder = (int *)data;
/* Place higher completion number first (pop off lower number first). */
return bb_postorder[bb2->index] - bb_postorder[bb1->index];
}
i.e. by descending number in BB_POSTORDER array. */
static void
-sort_bbs_postorder (basic_block *bbs, int n)
+sort_bbs_postorder (basic_block *bbs, int n, int *bb_postorder)
{
if (__builtin_expect (n == 2, true))
{
bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2;
}
else
- qsort (bbs, n, sizeof *bbs, cmp_bb_postorder);
+ gcc_sort_r (bbs, n, sizeof *bbs, cmp_bb_postorder, bb_postorder);
}
-/* Constructor for a dom walker.
+/* Set EDGE_EXECUTABLE on every edge within FN's CFG. */
- If SKIP_UNREACHBLE_BLOCKS is true, then we need to set
- EDGE_EXECUTABLE on every edge in the CFG. */
-dom_walker::dom_walker (cdi_direction direction,
- bool skip_unreachable_blocks)
- : m_dom_direction (direction),
- m_skip_unreachable_blocks (skip_unreachable_blocks),
- m_unreachable_dom (NULL)
+void
+set_all_edges_as_executable (function *fn)
{
- /* If we are not skipping unreachable blocks, then there is nothing
- to do. */
- if (!m_skip_unreachable_blocks)
- return;
-
basic_block bb;
- FOR_ALL_BB_FN (bb, cfun)
+ FOR_ALL_BB_FN (bb, fn)
{
edge_iterator ei;
edge e;
}
}
+/* Constructor for a dom walker. */
+
+dom_walker::dom_walker (cdi_direction direction,
+ enum reachability reachability,
+ int *bb_index_to_rpo)
+ : m_dom_direction (direction),
+ m_reachability (reachability),
+ m_user_bb_to_rpo (bb_index_to_rpo != NULL),
+ m_unreachable_dom (NULL),
+ m_bb_to_rpo (bb_index_to_rpo)
+{
+}
+
+/* Destructor. */
+
+dom_walker::~dom_walker ()
+{
+ if (! m_user_bb_to_rpo)
+ free (m_bb_to_rpo);
+}
+
/* Return TRUE if BB is reachable, false otherwise. */
bool
{
/* If we're not skipping unreachable blocks, then assume everything
is reachable. */
- if (!m_skip_unreachable_blocks)
+ if (m_reachability == ALL_BLOCKS)
return true;
/* If any of the predecessor edges that do not come from blocks dominated
m_unreachable_dom = bb;
}
+const edge dom_walker::STOP = (edge)-1;
+
/* Recursively walk the dominator tree.
BB is the basic block we are currently visiting. */
void
dom_walker::walk (basic_block bb)
{
- basic_block dest;
- basic_block *worklist = XNEWVEC (basic_block,
- n_basic_blocks_for_fn (cfun) * 2);
- int sp = 0;
- int *postorder, postorder_num;
-
- if (m_dom_direction == CDI_DOMINATORS)
+ /* Compute the basic-block index to RPO mapping lazily. */
+ if (!m_bb_to_rpo
+ && m_dom_direction == CDI_DOMINATORS)
{
- postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
- postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true);
- bb_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
+ int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+ int postorder_num = pre_and_rev_post_order_compute (NULL, postorder,
+ true);
+ m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
for (int i = 0; i < postorder_num; ++i)
- bb_postorder[postorder[i]] = i;
+ m_bb_to_rpo[postorder[i]] = i;
free (postorder);
}
+ /* Set up edge flags if need be. */
+ if (m_reachability == REACHABLE_BLOCKS)
+ set_all_edges_as_executable (cfun);
+
+ basic_block dest;
+ basic_block *worklist = XNEWVEC (basic_block,
+ n_basic_blocks_for_fn (cfun) * 2);
+ int sp = 0;
+
while (true)
{
/* Don't worry about unreachable blocks. */
|| bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
|| bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
{
+ edge taken_edge = NULL;
/* Callback for subclasses to do custom things before we have walked
the dominator children, but before we walk statements. */
if (this->bb_reachable (cfun, bb))
{
- edge taken_edge = before_dom_children (bb);
- if (taken_edge)
+ taken_edge = before_dom_children (bb);
+ if (taken_edge && taken_edge != STOP)
{
edge_iterator ei;
edge e;
worklist[sp++] = bb;
worklist[sp++] = NULL;
- int saved_sp = sp;
- for (dest = first_dom_son (m_dom_direction, bb);
- dest; dest = next_dom_son (m_dom_direction, dest))
- worklist[sp++] = dest;
- if (sp - saved_sp > 1 && m_dom_direction == CDI_DOMINATORS)
- sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp);
+ /* If the callback returned NONE then we are supposed to
+ stop and not even propagate EDGE_EXECUTABLE further. */
+ if (taken_edge != STOP)
+ {
+ int saved_sp = sp;
+ for (dest = first_dom_son (m_dom_direction, bb);
+ dest; dest = next_dom_son (m_dom_direction, dest))
+ worklist[sp++] = dest;
+ /* Sort worklist after RPO order if requested. */
+ if (sp - saved_sp > 1
+ && m_dom_direction == CDI_DOMINATORS
+ && m_bb_to_rpo)
+ sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp,
+ m_bb_to_rpo);
+ }
}
/* NULL is used to mark pop operations in the recursion stack. */
while (sp > 0 && !worklist[sp - 1])
else
break;
}
- if (m_dom_direction == CDI_DOMINATORS)
- {
- free (bb_postorder);
- bb_postorder = NULL;
- }
free (worklist);
}
projects / thirdparty / gcc.git / blobdiff