[PATCH] C++-ify and move control dependence code

[PATCH] C++-ify and move control dependence code

[Richard Biener]

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.  */
  

Re: [PATCH] C++-ify and move control dependence code

[Jeff Law]

On 09/05/2013 08:05 AM, Richard Biener wrote:
>
> 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.
I like it.  I'd actually moved the control dependence stuff out of DCE 
in the past as well, but never pushed it upstream.  I actually put it 
into its own files which were trivially small.

This was done in the context of implementing Click's GCM algorithm -- in 
the end the GCM bits didn't do significantly better than the existing 
sinking code at moving stuff onto more control dependent paths (after 
fixing minor oversights in our existing code).

Jeff

Re: [PATCH] C++-ify and move control dependence code

[Steven Bosscher]

On Thu, Sep 5, 2013 at 4:05 PM, Richard Biener wrote:
>
> 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.

I'd recommend re-implementing the control dependence code, then. The
current implementation is basically taken from old RTL-SSA dce.c and
uses a now old-fashioned view of the CFG, e.g. using edge lists.
You're probably better off starting from the dominance frontiers code
(control dependence is the same as dominance frontiers on the reverse
CFG).

Ceterum censeo edge_listem esse delendam.

Ciao!
Steven

Re: [PATCH] C++-ify and move control dependence code

[Richard Biener]

On 9/5/13 11:58 PM, Steven Bosscher wrote:
> On Thu, Sep 5, 2013 at 4:05 PM, Richard Biener wrote:
>>
>> 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.
> 
> I'd recommend re-implementing the control dependence code, then. The
> current implementation is basically taken from old RTL-SSA dce.c and
> uses a now old-fashioned view of the CFG, e.g. using edge lists.
> You're probably better off starting from the dominance frontiers code
> (control dependence is the same as dominance frontiers on the reverse
> CFG).
> 
> Ceterum censeo edge_listem esse delendam.

Well, I'm not in a position to do the re-implementation at the moment.
Would a re-implementation give me control-dependence in a more useful
way for PHI nodes?  That is, what block is an incoming edge (to compute
the PHI arg) control dependent on?  The current DCE query looks for
control dependece of the incoming edges predecessor, but for

   if
    |\
    | <empty>
    |  /
   PHI <1, 2>

this gets us the right answer for the edge from the <empty> block
but a wrong one for the one that uses the if block (as DCE has to
consider all incoming edges that probably doesn't matter as it
just gets one step ahead here instead of waiting for the control
dependence of the if block being marked).

Thanks,
Richard.

> Ciao!
> Steven
> 

Re: [PATCH] C++-ify and move control dependence code

[Steven Bosscher]

On Fri, Sep 6, 2013 at 8:41 AM, Richard Biener wrote:
>> I'd recommend re-implementing the control dependence code, then. The
>> current implementation is basically taken from old RTL-SSA dce.c and
>> uses a now old-fashioned view of the CFG, e.g. using edge lists.
>> You're probably better off starting from the dominance frontiers code
>> (control dependence is the same as dominance frontiers on the reverse
>> CFG).
...
> Well, I'm not in a position to do the re-implementation at the moment.

You don't have to. You just copy the dominance frontier code and make
it work on the reverse CFG. That shouldn't take more than half an hour
or so, and the result is much easier to interpret/validate than the
edge list stuff so you'll probably get that half our back easily when
working on control dependence consumers.

In fact, I already made those changes some time ago, see the cfganal.c
parts of http://gcc.gnu.org/ml/gcc-patches/2013-01/txt00046.txt


> Would a re-implementation give me control-dependence in a more useful
> way for PHI nodes?  That is, what block is an incoming edge (to compute
> the PHI arg) control dependent on?

I suppose so, yes. The inverse dominance-frontiers output is a
relation between basic blocks, i.e. not edge based. So you'd get
B=e->src and take the control dependencies of B.


> The current DCE query looks for
> control dependece of the incoming edges predecessor, but for
>
>    if
>     |\
>     | <empty>
>     |  /
>    PHI <1, 2>
>
> this gets us the right answer for the edge from the <empty> block
> but a wrong one for the one that uses the if block (as DCE has to
> consider all incoming edges that probably doesn't matter as it
> just gets one step ahead here instead of waiting for the control
> dependence of the if block being marked).

I'm not sure I'm following what you're trying to say here, but if I
understand correctly, then there should be a check in DCE that the PHI
block does not post-dominate its predecessor.

In any case, I recommend you don't start from the DCE control
dependence code. It is relatively slow (Harvey's algorithm is optimal,
Morgan's is quadratic in the number of edges), and it doesn't compute
control dependence for abnormal edges (I hacked that out, it made
control dependence calculation too slow). You'll want "proper",
correct control dependence, and the code in tree-ssa-dce.c is tweaked
for the purpose of DCE.

Ciao!
Steven