osprey-gcc-4.2.0/gcc/dominance.c File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "obstack.h"
#include "basic-block.h"
#include "toplev.h"
#include "et-forest.h"
#include "timevar.h"

Include dependency graph for dominance.c:

Go to the source code of this file.

Data Types
type	dom_info
Defines
#define	init_ar(var, type, num, content)
Typedefs
typedef unsigned int	TBB
Functions/Subroutines
static void	init_dom_info (struct dom_info *, enum cdi_direction)
static void	free_dom_info (struct dom_info *)
static void	calc_dfs_tree_nonrec (struct dom_info *, basic_block, enum cdi_direction)
static void	calc_dfs_tree (struct dom_info *, enum cdi_direction)
static void	compress (struct dom_info *, TBB)
static TBB	eval (struct dom_info *, TBB)
static void	link_roots (struct dom_info *, TBB, TBB)
static void	calc_idoms (struct dom_info *, enum cdi_direction)
void	debug_dominance_info (enum cdi_direction)
static void	assign_dfs_numbers (struct et_node *node, int *num)
static void	compute_dom_fast_query (enum cdi_direction dir)
void	calculate_dominance_info (enum cdi_direction dir)
void	free_dominance_info (enum cdi_direction dir)
basic_block	get_immediate_dominator (enum cdi_direction dir, basic_block bb)
void	set_immediate_dominator (enum cdi_direction dir, basic_block bb, basic_block dominated_by)
int	get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs)
unsigned	get_dominated_by_region (enum cdi_direction dir, basic_block *region, unsigned n_region, basic_block *doms)
void	redirect_immediate_dominators (enum cdi_direction dir, basic_block bb, basic_block to)
basic_block	nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
basic_block	nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
bool	dominated_by_p (enum cdi_direction dir, basic_block bb1, basic_block bb2)
unsigned	bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
unsigned	bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
void	verify_dominators (enum cdi_direction dir)
basic_block	recount_dominator (enum cdi_direction dir, basic_block bb)
void	iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n)
void	add_to_dominance_info (enum cdi_direction dir, basic_block bb)
void	delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
basic_block	first_dom_son (enum cdi_direction dir, basic_block bb)
basic_block	next_dom_son (enum cdi_direction dir, basic_block bb)
bool	dom_info_available_p (enum cdi_direction dir)
Variables
enum dom_state	dom_computed [2]
static unsigned	n_bbs_in_dom_tree [2]

---

Define Documentation

#define init_ar	(	var,
		type,
		num,
		content		)

Value:

do                \
    {               \
      unsigned int i = 1;    /* Catch content == i.  */   \
      if (! (content))            \
  (var) = XCNEWVEC (type, num);       \
      else              \
  {             \
    (var) = XNEWVEC (type, (num));      \
    for (i = 0; i < num; i++)       \
      (var)[i] = (content);       \
  }             \
    }               \
  while (0)

Definition at line 131 of file dominance.c.

---

Typedef Documentation

typedef unsigned int TBB

Definition at line 58 of file dominance.c.

---

Function Documentation

void add_to_dominance_info	(	enum cdi_direction	dir,
		basic_block	bb
	)

Definition at line 1048 of file dominance.c.

References dom_computed, DOM_NO_FAST_QUERY, DOM_OK, et_new_tree(), gcc_assert, and n_bbs_in_dom_tree.

static void assign_dfs_numbers	(	struct et_node *	node,
		int *	num
	)			[static]

Definition at line 569 of file dominance.c.

References assign_dfs_numbers(), et_node::dfs_num_in, et_node::dfs_num_out, et_node::right, and et_node::son.

unsigned bb_dom_dfs_in	(	enum cdi_direction	dir,
		basic_block	bb
	)

Definition at line 915 of file dominance.c.

References et_node::dfs_num_in, dom_computed, DOM_OK, gcc_assert, and n.

Referenced by prune_unused_phi_nodes().

unsigned bb_dom_dfs_out	(	enum cdi_direction	dir,
		basic_block	bb
	)

Definition at line 926 of file dominance.c.

References et_node::dfs_num_out, dom_computed, DOM_OK, gcc_assert, and n.

Referenced by prune_unused_phi_nodes().

static void calc_dfs_tree	(	struct dom_info *	di,
		enum cdi_direction	reverse
	)			[static]

Definition at line 314 of file dominance.c.

References b, bitmap_set_bit(), calc_dfs_tree_nonrec(), dom_info::dfs_order, dom_info::dfs_parent, dom_info::dfs_to_bb, dom_info::dfsnum, EDGE_COUNT, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, dom_info::fake_exit_edge, FOR_EACH_BB_REVERSE, gcc_assert, basic_block_def::index, last_basic_block, n_basic_blocks, and dom_info::nodes.

static void calc_dfs_tree_nonrec	(	struct dom_info *	di,
		basic_block	bb,
		enum cdi_direction	reverse
	)			[static]

Definition at line 202 of file dominance.c.

References edge::dest, dom_info::dfs_order, dom_info::dfs_parent, dom_info::dfs_to_bb, dom_info::dfsnum, ei_edge(), ei_end_p(), ei_next(), ei_start, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, free(), gcc_assert, basic_block_def::index, last_basic_block, n_basic_blocks, sp, edge::src, stack, and XNEWVEC.

static void calc_idoms	(	struct dom_info *	di,
		enum cdi_direction	reverse
	)			[static]

Definition at line 474 of file dominance.c.

References b, bitmap_bit_p(), dom_info::bucket, edge::dest, dom_info::dfs_order, dom_info::dfs_parent, dom_info::dfs_to_bb, dom_info::dom, ei_edge(), ei_end_p(), ei_next(), ei_start, ENTRY_BLOCK_PTR, eval(), EXIT_BLOCK_PTR, dom_info::fake_exit_edge, basic_block_def::index, edge_iterator::index, dom_info::key, last_basic_block, link_roots(), dom_info::next_bucket, dom_info::nodes, and edge::src.

void calculate_dominance_info

(

enum cdi_direction

dir

)

Definition at line 612 of file dominance.c.

References b, calc_dfs_tree(), calc_idoms(), compute_dom_fast_query(), d, dom_info::dfs_order, dom_info::dfs_to_bb, dom_info::dom, dom_computed, dom_info_available_p(), DOM_NO_FAST_QUERY, DOM_OK, ENTRY_BLOCK_PTR, et_forest_add_edge(), et_forest_add_node(), et_forest_create(), et_new_tree(), et_set_father(), EXIT_BLOCK_PTR, FOR_ALL_BB, FOR_EACH_BB, free_dom_info(), gcc_assert, basic_block_def::index, info, init_dom_info(), last_basic_block, n_basic_blocks, n_bbs_in_dom_tree, SET_BB_NODE, timevar_pop, timevar_push, VARRAY_GENERIC_PTR_INIT, and xmalloc().

static void compress	(	struct dom_info *	di,
		TBB	v
	)			[static]

Definition at line 383 of file dominance.c.

References compress(), dom_info::key, dom_info::path_min, and dom_info::set_chain.

static void compute_dom_fast_query

(

enum cdi_direction

dir

)

[static]

Definition at line 589 of file dominance.c.

References assign_dfs_numbers(), dom_computed, dom_info_available_p(), DOM_OK, FOR_ALL_BB, and gcc_assert.

void debug_dominance_info

(

enum cdi_direction

dir

)

void delete_from_dominance_info	(	enum cdi_direction	dir,
		basic_block	bb
	)

Definition at line 1062 of file dominance.c.

References dom_computed, DOM_NO_FAST_QUERY, DOM_OK, et_free_tree(), gcc_assert, n_bbs_in_dom_tree, and NULL.

bool dom_info_available_p

(

enum cdi_direction

dir

)

Definition at line 1099 of file dominance.c.

References dom_computed, and DOM_NONE.

Referenced by calculate_dominance_info(), compute_dom_fast_query(), expand_complex_div_wide(), free_dominance_info(), make_forwarder_block(), mf_build_check_statement_for(), remove_forwarder_block(), split_block(), and verify_dominators().

bool dominated_by_p	(	enum cdi_direction	dir,
		basic_block	bb1,
		basic_block	bb2
	)

Definition at line 899 of file dominance.c.

References et_node::dfs_num_in, et_node::dfs_num_out, dom_computed, DOM_OK, et_below(), and gcc_assert.

static TBB eval	(	struct dom_info *	di,
		TBB	v
	)			[inline, static]

Definition at line 403 of file dominance.c.

References compress(), dom_info::key, dom_info::path_min, and dom_info::set_chain.

basic_block first_dom_son	(	enum cdi_direction	dir,
		basic_block	bb
	)

Definition at line 1078 of file dominance.c.

References et_node::data, NULL, and et_node::son.

Referenced by break_up_subtract_bb(), build_omp_regions_1(), compute_antic_aux(), compute_avail(), eliminate_degenerate_phis_1(), fill_sons_in_loop(), find_assert_locations(), gather_blocks_in_sese_region(), get_dominated_by_region(), insert_aux(), loopify(), prepare_block_for_update(), reassociate_bb(), remove_path(), sink_code_in_bb(), and walk_dominator_tree().

static void free_dom_info

(

struct dom_info *

di

)

[static]

Definition at line 179 of file dominance.c.

References BITMAP_FREE, dom_info::bucket, dom_info::dfs_order, dom_info::dfs_parent, dom_info::dfs_to_bb, dom_info::dom, dom_info::fake_exit_edge, free(), dom_info::key, dom_info::next_bucket, dom_info::path_min, dom_info::set_chain, dom_info::set_child, and dom_info::set_size.

void free_dominance_info

(

enum cdi_direction

dir

)

Definition at line 654 of file dominance.c.

References delete_from_dominance_info(), dom_computed, dom_info_available_p(), DOM_NONE, et_free_pools(), et_free_tree_force(), FOR_ALL_BB, gcc_assert, n_bbs_in_dom_tree, and NULL.

int get_dominated_by	(	enum cdi_direction	dir,
		basic_block	bb,
		basic_block **	bbs
	)

Definition at line 714 of file dominance.c.

References et_node::data, dom_computed, gcc_assert, n, node, NULL, et_node::right, et_node::son, xmalloc(), and XNEWVEC.

unsigned get_dominated_by_region	(	enum cdi_direction	dir,
		basic_block *	region,
		unsigned	n_region,
		basic_block *	doms
	)

Definition at line 744 of file dominance.c.

References BB_DUPLICATED, first_dom_son(), basic_block_def::flags, flags, for(), i, and next_dom_son().

Referenced by tree_duplicate_sese_region().

basic_block get_immediate_dominator	(	enum cdi_direction	dir,
		basic_block	bb
	)

Definition at line 675 of file dominance.c.

References et_node::data, dom_computed, et_node::father, gcc_assert, node, and NULL.

static void init_dom_info	(	struct dom_info *	di,
		enum cdi_direction	dir
	)			[static]

Definition at line 150 of file dominance.c.

References BITMAP_ALLOC, dom_info::bucket, dom_info::dfs_order, dom_info::dfs_parent, dom_info::dfs_to_bb, dom_info::dfsnum, dom_info::dom, dom_info::fake_exit_edge, i, init_ar, dom_info::key, last_basic_block, n_basic_blocks, dom_info::next_bucket, dom_info::nodes, NULL, dom_info::path_min, dom_info::set_chain, dom_info::set_child, and dom_info::set_size.

void iterate_fix_dominators	(	enum cdi_direction	dir,
		basic_block *	bbs,
		int	n
	)

Definition at line 1018 of file dominance.c.

References changed, dom_computed, gcc_assert, get_immediate_dominator(), i, NULL, recount_dominator(), and set_immediate_dominator().

static void link_roots	(	struct dom_info *	di,
		TBB	v,
		TBB	w
	)			[static]

Definition at line 432 of file dominance.c.

References dom_info::key, dom_info::path_min, s, dom_info::set_chain, dom_info::set_child, dom_info::set_size, and tmp.

basic_block nearest_common_dominator	(	enum cdi_direction	dir,
		basic_block	bb1,
		basic_block	bb2
	)

Definition at line 790 of file dominance.c.

References et_node::data, dom_computed, et_nca(), and gcc_assert.

basic_block nearest_common_dominator_for_set	(	enum cdi_direction	dir,
		bitmap	blocks
	)

Definition at line 807 of file dominance.c.

References BASIC_BLOCK, bitmap_first_set_bit(), EXECUTE_IF_SET_IN_BITMAP, first, i, and nearest_common_dominator().

Referenced by insert_updated_phi_nodes_for(), and update_ssa().

basic_block next_dom_son	(	enum cdi_direction	dir,
		basic_block	bb
	)

Definition at line 1089 of file dominance.c.

References et_node::data, et_node::father, next, NULL, and et_node::son.

Referenced by break_up_subtract_bb(), build_omp_regions_1(), compute_antic_aux(), compute_avail(), eliminate_degenerate_phis_1(), fill_sons_in_loop(), find_assert_locations(), gather_blocks_in_sese_region(), get_dominated_by_region(), insert_aux(), loopify(), prepare_block_for_update(), reassociate_bb(), remove_path(), sink_code_in_bb(), and walk_dominator_tree().

basic_block recount_dominator	(	enum cdi_direction	dir,
		basic_block	bb
	)

Definition at line 982 of file dominance.c.

References CDI_DOMINATORS, edge::dest, dom_computed, dominated_by_p(), ENTRY_BLOCK_PTR, FOR_EACH_EDGE, gcc_assert, nearest_common_dominator(), NULL, and edge::src.

void redirect_immediate_dominators	(	enum cdi_direction	dir,
		basic_block	bb,
		basic_block	to
	)

Definition at line 766 of file dominance.c.

References dom_computed, DOM_NO_FAST_QUERY, DOM_OK, et_set_father(), et_split(), gcc_assert, and et_node::son.

void set_immediate_dominator	(	enum cdi_direction	dir,
		basic_block	bb,
		basic_block	dominated_by
	)			[inline]

Definition at line 690 of file dominance.c.

References et_node::data, dom_computed, DOM_NO_FAST_QUERY, DOM_OK, et_set_father(), et_split(), et_node::father, gcc_assert, and node.

void verify_dominators

(

enum cdi_direction

dir

)

Definition at line 936 of file dominance.c.

References CDI_DOMINATORS, dom_info_available_p(), dominated_by_p(), ENTRY_BLOCK_PTR, err, error(), FOR_EACH_BB, gcc_assert, get_immediate_dominator(), basic_block_def::index, NULL, and recount_dominator().

---

Variable Documentation

enum dom_state dom_computed[2]

Definition at line 49 of file dominance.c.

Referenced by add_to_dominance_info(), bb_dom_dfs_in(), bb_dom_dfs_out(), calculate_dominance_info(), combine_blocks(), compute_dom_fast_query(), create_basic_block(), delete_basic_block(), delete_from_dominance_info(), dom_info_available_p(), dominated_by_p(), find_if_header(), free_dominance_info(), get_dominated_by(), get_immediate_dominator(), iterate_fix_dominators(), merge_blocks(), mfb_update_loops(), nearest_common_dominator(), recount_dominator(), redirect_immediate_dominators(), remove_dead_stmt(), set_immediate_dominator(), split_edge(), tree_verify_flow_info(), and verify_ssa().

unsigned n_bbs_in_dom_tree[2] [static]

Definition at line 127 of file dominance.c.