/* Calculate (post)dominators in slightly super-linear time.
- Copyright (C) 2000, 2003, 2004, 2005, 2006, 2007, 2008 Free
- Software Foundation, Inc.
+ Copyright (C) 2000, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
+ Free Software Foundation, Inc.
Contributed by Michael Matz (matz@ifh.de).
This file is part of GCC.
#include "hard-reg-set.h"
#include "obstack.h"
#include "basic-block.h"
-#include "toplev.h"
+#include "diagnostic-core.h"
#include "et-forest.h"
#include "timevar.h"
#include "vecprim.h"
#include "pointer-set.h"
#include "graphds.h"
+#include "bitmap.h"
/* We name our nodes with integers, beginning with 1. Zero is reserved for
'undefined' or 'end of list'. The name of each node is given by the dfs
/* Set the immediate dominator of the block possibly removing
existing edge. NULL can be used to remove any edge. */
-inline void
+void
set_immediate_dominator (enum cdi_direction dir, basic_block bb,
basic_block dominated_by)
{
}
/* Returns the list of basic blocks including BB dominated by BB, in the
- direction DIR. The vector will be sorted in preorder. */
+ direction DIR up to DEPTH in the dominator tree. The DEPTH of zero will
+ produce a vector containing all dominated blocks. The vector will be sorted
+ in preorder. */
VEC (basic_block, heap) *
-get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
+get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth)
{
VEC(basic_block, heap) *bbs = NULL;
unsigned i;
+ unsigned next_level_start;
i = 0;
VEC_safe_push (basic_block, heap, bbs, bb);
+ next_level_start = 1; /* = VEC_length (basic_block, bbs); */
do
{
son;
son = next_dom_son (dir, son))
VEC_safe_push (basic_block, heap, bbs, son);
+
+ if (i == next_level_start && --depth)
+ next_level_start = VEC_length (basic_block, bbs);
}
- while (i < VEC_length (basic_block, bbs));
+ while (i < next_level_start);
return bbs;
}
+/* Returns the list of basic blocks including BB dominated by BB, in the
+ direction DIR. The vector will be sorted in preorder. */
+
+VEC (basic_block, heap) *
+get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
+{
+ return get_dominated_to_depth (dir, bb, 0);
+}
+
/* Redirect all edges pointing to BB to TO. */
void
redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
}
/* Verify invariants of dominator structure. */
-void
+DEBUG_FUNCTION void
verify_dominators (enum cdi_direction dir)
{
int err = 0;
for (i = nc - 1; i >= 0; i--)
{
dom = NULL;
- for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
+ FOR_EACH_VEC_ELT (int, sccs[i], si, a)
{
bb = VEC_index (basic_block, bbs, a);
FOR_EACH_EDGE (e, ei, bb->preds)
}
gcc_assert (dom != NULL);
- for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
+ FOR_EACH_VEC_ELT (int, sccs[i], si, a)
{
bb = VEC_index (basic_block, bbs, a);
set_immediate_dominator (CDI_DOMINATORS, bb, dom);
conservatively correct, setting the dominators using the
heuristics in prune_bbs_to_update_dominators could
create cycles in the dominance "tree", and cause ICE. */
- for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
}
/* Construct the graph G. */
map = pointer_map_create ();
- for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
{
/* If the dominance tree is conservatively correct, split it now. */
if (conservative)
g = new_graph (n + 1);
for (y = 0; y < g->n_vertices; y++)
g->vertices[y].data = BITMAP_ALLOC (NULL);
- for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
{
FOR_EACH_EDGE (e, ei, bb->preds)
{
dom_i = (size_t) *pointer_map_contains (map, dom);
/* Do not include parallel edges to G. */
- if (bitmap_bit_p ((bitmap) g->vertices[dom_i].data, i))
+ if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
continue;
- bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i);
add_edge (g, dom_i, i);
}
}
return dom_computed[dir_index] != DOM_NONE;
}
-void
+DEBUG_FUNCTION void
debug_dominance_info (enum cdi_direction dir)
{
basic_block bb, bb2;
/* Prints to stderr representation of the dominance tree (for direction DIR)
rooted in ROOT. */
-void
+DEBUG_FUNCTION void
debug_dominance_tree (enum cdi_direction dir, basic_block root)
{
debug_dominance_tree_1 (dir, root, 0, false);