/* Generic dominator tree walker
- Copyright (C) 2003-2015 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.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
-#include "predict.h"
-#include "hard-reg-set.h"
-#include "input.h"
-#include "function.h"
-#include "dominance.h"
-#include "cfg.h"
+#include "backend.h"
#include "cfganal.h"
-#include "basic-block.h"
#include "domwalk.h"
-#include "sbitmap.h"
+#include "dumpfile.h"
/* This file implements a generic walker for dominator trees.
which is currently an abstraction over walking tree statements. Thus
the dominator walker is currently only useful for trees. */
-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 = *(basic_block *)const_cast<void *>(a);
- basic_block bb2 = *(basic_block *)const_cast<void *>(b);
- if (bb1->index == bb2->index)
- return 0;
+ 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). */
- if (bb_postorder[bb1->index] > bb_postorder[bb2->index])
- return -1;
- return 1;
+ return bb_postorder[bb2->index] - bb_postorder[bb1->index];
+}
+
+/* Permute array BBS of N basic blocks in postorder,
+ i.e. by descending number in BB_POSTORDER array. */
+
+static void
+sort_bbs_postorder (basic_block *bbs, int n, int *bb_postorder)
+{
+ if (__builtin_expect (n == 2, true))
+ {
+ basic_block bb0 = bbs[0], bb1 = bbs[1];
+ if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
+ bbs[0] = bb1, bbs[1] = bb0;
+ }
+ else if (__builtin_expect (n == 3, true))
+ {
+ basic_block bb0 = bbs[0], bb1 = bbs[1], bb2 = bbs[2];
+ if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
+ std::swap (bb0, bb1);
+ if (bb_postorder[bb1->index] < bb_postorder[bb2->index])
+ {
+ std::swap (bb1, bb2);
+ if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
+ std::swap (bb0, bb1);
+ }
+ bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2;
+ }
+ else
+ gcc_sort_r (bbs, n, sizeof *bbs, cmp_bb_postorder, bb_postorder);
+}
+
+/* Set EDGE_EXECUTABLE on every edge within FN's CFG. */
+
+void
+set_all_edges_as_executable (function *fn)
+{
+ basic_block bb;
+ FOR_ALL_BB_FN (bb, fn)
+ {
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ e->flags |= EDGE_EXECUTABLE;
+ }
+}
+
+/* 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
+dom_walker::bb_reachable (struct function *fun, basic_block bb)
+{
+ /* If we're not skipping unreachable blocks, then assume everything
+ is reachable. */
+ if (m_reachability == ALL_BLOCKS)
+ return true;
+
+ /* If any of the predecessor edges that do not come from blocks dominated
+ by us are still marked as possibly executable consider this block
+ reachable. */
+ bool reachable = false;
+ if (!m_unreachable_dom)
+ {
+ reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun);
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (!dominated_by_p (CDI_DOMINATORS, e->src, bb))
+ reachable |= (e->flags & EDGE_EXECUTABLE);
+ }
+
+ return reachable;
+}
+
+/* BB has been determined to be unreachable. Propagate that property
+ to incoming and outgoing edges of BB as appropriate. */
+
+void
+dom_walker::propagate_unreachable_to_edges (basic_block bb,
+ FILE *dump_file,
+ dump_flags_t dump_flags)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Marking all outgoing edges of unreachable "
+ "BB %d as not executable\n", bb->index);
+
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ e->flags &= ~EDGE_EXECUTABLE;
+
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Marking backedge from BB %d into "
+ "unreachable BB %d as not executable\n",
+ e->src->index, bb->index);
+ e->flags &= ~EDGE_EXECUTABLE;
+ }
+ }
+
+ if (!m_unreachable_dom)
+ 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 = inverted_post_order_compute (postorder);
- 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. */
- before_dom_children (bb);
+ if (this->bb_reachable (cfun, bb))
+ {
+ taken_edge = before_dom_children (bb);
+ if (taken_edge && taken_edge != STOP)
+ {
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e != taken_edge)
+ e->flags &= ~EDGE_EXECUTABLE;
+ }
+ }
+ else
+ propagate_unreachable_to_edges (bb, dump_file, dump_flags);
/* Mark the current BB to be popped out of the recursion stack
once children are processed. */
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 (m_dom_direction == CDI_DOMINATORS)
- switch (sp - saved_sp)
- {
- case 0:
- case 1:
- break;
- default:
- qsort (&worklist[saved_sp], sp - saved_sp,
- sizeof (basic_block), cmp_bb_postorder);
- }
+ /* 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])
/* Callback allowing subclasses to do custom things after we have
walked dominator children, but before we walk statements. */
- after_dom_children (bb);
+ if (bb_reachable (cfun, bb))
+ after_dom_children (bb);
+ else if (m_unreachable_dom == bb)
+ m_unreachable_dom = NULL;
}
if (sp)
bb = worklist[--sp];
else
break;
}
- if (m_dom_direction == CDI_DOMINATORS)
- {
- free (bb_postorder);
- bb_postorder = NULL;
- }
free (worklist);
}
projects / thirdparty / gcc.git / blobdiff