This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] C++-ify and move control dependence code
- From: Richard Biener <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 5 Sep 2013 16:05:44 +0200 (CEST)
- Subject: [PATCH] C++-ify and move control dependence code
- Authentication-results: sourceware.org; auth=none
This C++-ifies and moves the control dependence code from tree-ssa-dce.c
to cfganal.c as I am about to re-use that code from loop distribution.
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
Richard.
2013-09-05 Richard Biener <rguenther@suse.de>
* basic-block.h (class control_dependences): New.
* tree-ssa-dce.c (control_dependence_map): Remove.
(cd): New global.
(EXECUTE_IF_CONTROL_DEPENDENT): Remove.
(set_control_dependence_map_bit, clear_control_dependence_bitmap,
find_pdom, find_control_dependence, find_all_control_dependences):
Move to cfganal.c.
(mark_control_dependent_edges_necessary, find_obviously_necessary_stmts,
propagate_necessity, tree_dce_init, tree_dce_done,
perform_tree_ssa_dce): Adjust.
* cfganal.c (set_control_dependence_map_bit,
clear_control_dependence_bitmap, find_pdom, find_control_dependence,
find_all_control_dependences): Move from tree-ssa-dce.c and
implement as methods of control_dependences class.
(control_dependences::control_dependences): New.
(control_dependences::~control_dependences): Likewise.
(control_dependences::get_edges_dependent_on): Likewise.
(control_dependences::get_edge): Likewise.
Index: gcc/basic-block.h
===================================================================
*** gcc/basic-block.h (revision 202275)
--- gcc/basic-block.h (working copy)
*************** struct edge_list
*** 465,470 ****
--- 465,487 ----
edge *index_to_edge;
};
+ /* Class to compute and manage control dependences on an edge-list. */
+ class control_dependences
+ {
+ public:
+ control_dependences (edge_list *);
+ ~control_dependences ();
+ bitmap get_edges_dependent_on (int);
+ edge get_edge (int);
+
+ private:
+ void set_control_dependence_map_bit (basic_block, int);
+ void clear_control_dependence_bitmap (basic_block);
+ void find_control_dependence (int);
+ vec<bitmap> control_dependence_map;
+ edge_list *el;
+ };
+
/* The base value for branch probability notes and edge probabilities. */
#define REG_BR_PROB_BASE 10000
Index: gcc/tree-ssa-dce.c
===================================================================
*** gcc/tree-ssa-dce.c (revision 202275)
--- gcc/tree-ssa-dce.c (working copy)
*************** static sbitmap bb_contains_live_stmts;
*** 87,93 ****
use a bitmap for each block recording its edges. An array holds the
bitmap. The Ith bit in the bitmap is set if that block is dependent
on the Ith edge. */
! static bitmap *control_dependence_map;
/* Vector indicating that a basic block has already had all the edges
processed that it is control dependent on. */
--- 87,93 ----
use a bitmap for each block recording its edges. An array holds the
bitmap. The Ith bit in the bitmap is set if that block is dependent
on the Ith edge. */
! static control_dependences *cd;
/* Vector indicating that a basic block has already had all the edges
processed that it is control dependent on. */
*************** static sbitmap visited_control_parents;
*** 100,195 ****
to be recomputed. */
static bool cfg_altered;
- /* Execute code that follows the macro for each edge (given number
- EDGE_NUMBER within the CODE) for which the block with index N is
- control dependent. */
- #define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \
- EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \
- (EDGE_NUMBER), (BI))
-
-
- /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
- static inline void
- set_control_dependence_map_bit (basic_block bb, int edge_index)
- {
- if (bb == ENTRY_BLOCK_PTR)
- return;
- gcc_assert (bb != EXIT_BLOCK_PTR);
- bitmap_set_bit (control_dependence_map[bb->index], edge_index);
- }
-
- /* Clear all control dependences for block BB. */
- static inline void
- clear_control_dependence_bitmap (basic_block bb)
- {
- bitmap_clear (control_dependence_map[bb->index]);
- }
-
-
- /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
- This function is necessary because some blocks have negative numbers. */
-
- static inline basic_block
- find_pdom (basic_block block)
- {
- gcc_assert (block != ENTRY_BLOCK_PTR);
-
- if (block == EXIT_BLOCK_PTR)
- return EXIT_BLOCK_PTR;
- else
- {
- basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
- if (! bb)
- return EXIT_BLOCK_PTR;
- return bb;
- }
- }
-
-
- /* Determine all blocks' control dependences on the given edge with edge_list
- EL index EDGE_INDEX, ala Morgan, Section 3.6. */
-
- static void
- find_control_dependence (struct edge_list *el, int edge_index)
- {
- basic_block current_block;
- basic_block ending_block;
-
- gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
-
- if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
- ending_block = single_succ (ENTRY_BLOCK_PTR);
- else
- ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
-
- for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
- current_block != ending_block && current_block != EXIT_BLOCK_PTR;
- current_block = find_pdom (current_block))
- {
- edge e = INDEX_EDGE (el, edge_index);
-
- /* For abnormal edges, we don't make current_block control
- dependent because instructions that throw are always necessary
- anyway. */
- if (e->flags & EDGE_ABNORMAL)
- continue;
-
- set_control_dependence_map_bit (current_block, edge_index);
- }
- }
-
-
- /* Record all blocks' control dependences on all edges in the edge
- list EL, ala Morgan, Section 3.6. */
-
- static void
- find_all_control_dependences (struct edge_list *el)
- {
- int i;
-
- for (i = 0; i < NUM_EDGES (el); ++i)
- find_control_dependence (el, i);
- }
/* If STMT is not already marked necessary, mark it, and add it to the
worklist if ADD_TO_WORKLIST is true. */
--- 100,105 ----
*************** mark_last_stmt_necessary (basic_block bb
*** 400,407 ****
When IGNORE_SELF is true, ignore BB in the list of control dependences. */
static void
! mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el,
! bool ignore_self)
{
bitmap_iterator bi;
unsigned edge_number;
--- 310,316 ----
When IGNORE_SELF is true, ignore BB in the list of control dependences. */
static void
! mark_control_dependent_edges_necessary (basic_block bb, bool ignore_self)
{
bitmap_iterator bi;
unsigned edge_number;
*************** mark_control_dependent_edges_necessary (
*** 412,420 ****
if (bb == ENTRY_BLOCK_PTR)
return;
! EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
{
! basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
if (ignore_self && cd_bb == bb)
{
--- 321,330 ----
if (bb == ENTRY_BLOCK_PTR)
return;
! EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
! 0, edge_number, bi)
{
! basic_block cd_bb = cd->get_edge (edge_number)->src;
if (ignore_self && cd_bb == bb)
{
*************** mark_control_dependent_edges_necessary (
*** 439,445 ****
dependence analysis. */
static void
! find_obviously_necessary_stmts (struct edge_list *el)
{
basic_block bb;
gimple_stmt_iterator gsi;
--- 349,355 ----
dependence analysis. */
static void
! find_obviously_necessary_stmts (bool aggressive)
{
basic_block bb;
gimple_stmt_iterator gsi;
*************** find_obviously_necessary_stmts (struct e
*** 461,467 ****
{
stmt = gsi_stmt (gsi);
gimple_set_plf (stmt, STMT_NECESSARY, false);
! mark_stmt_if_obviously_necessary (stmt, el != NULL);
}
}
--- 371,377 ----
{
stmt = gsi_stmt (gsi);
gimple_set_plf (stmt, STMT_NECESSARY, false);
! mark_stmt_if_obviously_necessary (stmt, aggressive);
}
}
*************** find_obviously_necessary_stmts (struct e
*** 472,478 ****
return;
/* Prevent the empty possibly infinite loops from being removed. */
! if (el)
{
loop_iterator li;
struct loop *loop;
--- 382,388 ----
return;
/* Prevent the empty possibly infinite loops from being removed. */
! if (aggressive)
{
loop_iterator li;
struct loop *loop;
*************** find_obviously_necessary_stmts (struct e
*** 488,494 ****
if (dump_file)
fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
e->src->index, e->dest->index);
! mark_control_dependent_edges_necessary (e->dest, el, false);
}
}
--- 398,404 ----
if (dump_file)
fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
e->src->index, e->dest->index);
! mark_control_dependent_edges_necessary (e->dest, false);
}
}
*************** find_obviously_necessary_stmts (struct e
*** 497,503 ****
{
if (dump_file)
fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
! mark_control_dependent_edges_necessary (loop->latch, el, false);
}
scev_finalize ();
}
--- 407,413 ----
{
if (dump_file)
fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
! mark_control_dependent_edges_necessary (loop->latch, false);
}
scev_finalize ();
}
*************** degenerate_phi_p (gimple phi)
*** 690,699 ****
In conservative mode, EL is NULL. */
static void
! propagate_necessity (struct edge_list *el)
{
gimple stmt;
- bool aggressive = (el ? true : false);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nProcessing worklist:\n");
--- 600,608 ----
In conservative mode, EL is NULL. */
static void
! propagate_necessity (bool aggressive)
{
gimple stmt;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nProcessing worklist:\n");
*************** propagate_necessity (struct edge_list *e
*** 718,724 ****
basic_block bb = gimple_bb (stmt);
if (bb != ENTRY_BLOCK_PTR
&& !bitmap_bit_p (visited_control_parents, bb->index))
! mark_control_dependent_edges_necessary (bb, el, false);
}
if (gimple_code (stmt) == GIMPLE_PHI
--- 627,633 ----
basic_block bb = gimple_bb (stmt);
if (bb != ENTRY_BLOCK_PTR
&& !bitmap_bit_p (visited_control_parents, bb->index))
! mark_control_dependent_edges_necessary (bb, false);
}
if (gimple_code (stmt) == GIMPLE_PHI
*************** propagate_necessity (struct edge_list *e
*** 825,831 ****
else if (arg_bb != ENTRY_BLOCK_PTR
&& !bitmap_bit_p (visited_control_parents,
arg_bb->index))
! mark_control_dependent_edges_necessary (arg_bb, el, true);
}
}
}
--- 734,740 ----
else if (arg_bb != ENTRY_BLOCK_PTR
&& !bitmap_bit_p (visited_control_parents,
arg_bb->index))
! mark_control_dependent_edges_necessary (arg_bb, true);
}
}
}
*************** tree_dce_init (bool aggressive)
*** 1486,1497 ****
if (aggressive)
{
- int i;
-
- control_dependence_map = XNEWVEC (bitmap, last_basic_block);
- for (i = 0; i < last_basic_block; ++i)
- control_dependence_map[i] = BITMAP_ALLOC (NULL);
-
last_stmt_necessary = sbitmap_alloc (last_basic_block);
bitmap_clear (last_stmt_necessary);
bb_contains_live_stmts = sbitmap_alloc (last_basic_block);
--- 1395,1400 ----
*************** tree_dce_done (bool aggressive)
*** 1512,1523 ****
{
if (aggressive)
{
! int i;
!
! for (i = 0; i < last_basic_block; ++i)
! BITMAP_FREE (control_dependence_map[i]);
! free (control_dependence_map);
!
sbitmap_free (visited_control_parents);
sbitmap_free (last_stmt_necessary);
sbitmap_free (bb_contains_live_stmts);
--- 1415,1421 ----
{
if (aggressive)
{
! delete cd;
sbitmap_free (visited_control_parents);
sbitmap_free (last_stmt_necessary);
sbitmap_free (bb_contains_live_stmts);
*************** tree_dce_done (bool aggressive)
*** 1546,1552 ****
static unsigned int
perform_tree_ssa_dce (bool aggressive)
{
- struct edge_list *el = NULL;
bool something_changed = 0;
calculate_dominance_info (CDI_DOMINATORS);
--- 1444,1449 ----
*************** perform_tree_ssa_dce (bool aggressive)
*** 1563,1573 ****
if (aggressive)
{
/* Compute control dependence. */
- timevar_push (TV_CONTROL_DEPENDENCES);
calculate_dominance_info (CDI_POST_DOMINATORS);
! el = create_edge_list ();
! find_all_control_dependences (el);
! timevar_pop (TV_CONTROL_DEPENDENCES);
visited_control_parents = sbitmap_alloc (last_basic_block);
bitmap_clear (visited_control_parents);
--- 1460,1467 ----
if (aggressive)
{
/* Compute control dependence. */
calculate_dominance_info (CDI_POST_DOMINATORS);
! cd = new control_dependences (create_edge_list ());
visited_control_parents = sbitmap_alloc (last_basic_block);
bitmap_clear (visited_control_parents);
*************** perform_tree_ssa_dce (bool aggressive)
*** 1575,1581 ****
mark_dfs_back_edges ();
}
! find_obviously_necessary_stmts (el);
if (aggressive)
loop_optimizer_finalize ();
--- 1469,1475 ----
mark_dfs_back_edges ();
}
! find_obviously_necessary_stmts (aggressive);
if (aggressive)
loop_optimizer_finalize ();
*************** perform_tree_ssa_dce (bool aggressive)
*** 1585,1591 ****
nr_walks = 0;
chain_ovfl = false;
visited = BITMAP_ALLOC (NULL);
! propagate_necessity (el);
BITMAP_FREE (visited);
something_changed |= eliminate_unnecessary_stmts ();
--- 1479,1485 ----
nr_walks = 0;
chain_ovfl = false;
visited = BITMAP_ALLOC (NULL);
! propagate_necessity (aggressive);
BITMAP_FREE (visited);
something_changed |= eliminate_unnecessary_stmts ();
*************** perform_tree_ssa_dce (bool aggressive)
*** 1609,1616 ****
tree_dce_done (aggressive);
- free_edge_list (el);
-
if (something_changed)
return TODO_update_ssa | TODO_cleanup_cfg;
return 0;
--- 1503,1508 ----
Index: gcc/cfganal.c
===================================================================
*** gcc/cfganal.c (revision 202275)
--- gcc/cfganal.c (working copy)
*************** verify_edge_list (FILE *f, struct edge_l
*** 340,345 ****
--- 340,459 ----
}
}
+
+ /* Functions to compute control dependences. */
+
+ /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
+ void
+ control_dependences::set_control_dependence_map_bit (basic_block bb,
+ int edge_index)
+ {
+ if (bb == ENTRY_BLOCK_PTR)
+ return;
+ gcc_assert (bb != EXIT_BLOCK_PTR);
+ bitmap_set_bit (control_dependence_map[bb->index], edge_index);
+ }
+
+ /* Clear all control dependences for block BB. */
+ void
+ control_dependences::clear_control_dependence_bitmap (basic_block bb)
+ {
+ bitmap_clear (control_dependence_map[bb->index]);
+ }
+
+ /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
+ This function is necessary because some blocks have negative numbers. */
+
+ static inline basic_block
+ find_pdom (basic_block block)
+ {
+ gcc_assert (block != ENTRY_BLOCK_PTR);
+
+ if (block == EXIT_BLOCK_PTR)
+ return EXIT_BLOCK_PTR;
+ else
+ {
+ basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
+ if (! bb)
+ return EXIT_BLOCK_PTR;
+ return bb;
+ }
+ }
+
+ /* Determine all blocks' control dependences on the given edge with edge_list
+ EL index EDGE_INDEX, ala Morgan, Section 3.6. */
+
+ void
+ control_dependences::find_control_dependence (int edge_index)
+ {
+ basic_block current_block;
+ basic_block ending_block;
+
+ gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
+
+ if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
+ ending_block = single_succ (ENTRY_BLOCK_PTR);
+ else
+ ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
+
+ for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
+ current_block != ending_block && current_block != EXIT_BLOCK_PTR;
+ current_block = find_pdom (current_block))
+ {
+ edge e = INDEX_EDGE (el, edge_index);
+
+ /* For abnormal edges, we don't make current_block control
+ dependent because instructions that throw are always necessary
+ anyway. */
+ if (e->flags & EDGE_ABNORMAL)
+ continue;
+
+ set_control_dependence_map_bit (current_block, edge_index);
+ }
+ }
+
+ /* Record all blocks' control dependences on all edges in the edge
+ list EL, ala Morgan, Section 3.6. */
+
+ control_dependences::control_dependences (struct edge_list *edges)
+ : el (edges)
+ {
+ timevar_push (TV_CONTROL_DEPENDENCES);
+ control_dependence_map.create (last_basic_block);
+ for (int i = 0; i < last_basic_block; ++i)
+ control_dependence_map.quick_push (BITMAP_ALLOC (NULL));
+ for (int i = 0; i < NUM_EDGES (el); ++i)
+ find_control_dependence (i);
+ timevar_pop (TV_CONTROL_DEPENDENCES);
+ }
+
+ /* Free control dependences and the associated edge list. */
+
+ control_dependences::~control_dependences ()
+ {
+ for (int i = 0; i < last_basic_block; ++i)
+ BITMAP_FREE (control_dependence_map[i]);
+ control_dependence_map.release ();
+ free_edge_list (el);
+ }
+
+ /* Returns the bitmap of edges the basic-block I is dependent on. */
+
+ bitmap
+ control_dependences::get_edges_dependent_on (int i)
+ {
+ return control_dependence_map[i];
+ }
+
+ /* Returns the edge with index I from the edge list. */
+
+ edge
+ control_dependences::get_edge (int i)
+ {
+ return INDEX_EDGE (el, i);
+ }
+
+
/* Given PRED and SUCC blocks, return the edge which connects the blocks.
If no such edge exists, return NULL. */