[PATCH] Fix PR71253

[Richard Biener <rguenther at suse dot de>]

I am currently testing the following patch that makes the control 
dependences data structures survive edge redirection when the
pass knows it doesn't alter control dependences.

It basically replaces the edge list with a vector of BB indices
(so even removing BBs and still querying the control dependences
is possible if you handle NULL edge src/dests).

Bootstrap and regtest running on x86_64-unknown-linux-gnu.

Richard.

2016-05-24  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/71253
	* cfganal.h (control_dependences): Make robust against edge
	and BB removal.
	(control_dependences::control_dependences): Remove edge_list argument.
	(control_dependences::get_edge): Remove.
	(control_dependences::get_edge_src): Add.
	(control_dependences::get_edge_dest): Likewise.
	(control_dependences::m_el): Make a vector of edge src/dest index.
	* cfganal.c (control_dependences::find_control_dependence): Adjust.
	(control_dependences::control_dependences): Likewise.
	(control_dependences::~control_dependence): Likewise.
	(control_dependences::get_edge): Remove.
	(control_dependences::get_edge_src): Add.
	(control_dependences::get_edge_dest): Likewise.
	* tree-ssa-dce.c (mark_control_dependent_edges_necessary): Use
	get_edge_src.
	(perform_tree_ssa_dce): Adjust.
	* tree-loop-distribution.c (create_edge_for_control_dependence): Use
	get_edge_src.
	(pass_loop_distribution::execute): Adjust.  Do loop destroying
	conditional on changed.

	* gcc.dg/torture/pr71253.c: New testcase.

Index: gcc/cfganal.c
===================================================================
*** gcc/cfganal.c	(revision 236630)
--- gcc/cfganal.c	(working copy)
*************** control_dependences::find_control_depend
*** 408,450 ****
    basic_block current_block;
    basic_block ending_block;
  
!   gcc_assert (INDEX_EDGE_PRED_BB (m_el, edge_index)
! 	      != EXIT_BLOCK_PTR_FOR_FN (cfun));
  
!   if (INDEX_EDGE_PRED_BB (m_el, edge_index) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
      ending_block = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
    else
!     ending_block = find_pdom (INDEX_EDGE_PRED_BB (m_el, edge_index));
  
!   for (current_block = INDEX_EDGE_SUCC_BB (m_el, edge_index);
         current_block != ending_block
         && current_block != EXIT_BLOCK_PTR_FOR_FN (cfun);
         current_block = find_pdom (current_block))
!     {
!       edge e = INDEX_EDGE (m_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)
!   : m_el (edges)
  {
    timevar_push (TV_CONTROL_DEPENDENCES);
    control_dependence_map.create (last_basic_block_for_fn (cfun));
    for (int i = 0; i < last_basic_block_for_fn (cfun); ++i)
      control_dependence_map.quick_push (BITMAP_ALLOC (NULL));
!   for (int i = 0; i < NUM_EDGES (m_el); ++i)
      find_control_dependence (i);
    timevar_pop (TV_CONTROL_DEPENDENCES);
  }
  
--- 408,461 ----
    basic_block current_block;
    basic_block ending_block;
  
!   gcc_assert (get_edge_src (edge_index) != EXIT_BLOCK_PTR_FOR_FN (cfun));
  
!   /* For abnormal edges, we don't make current_block control
!      dependent because instructions that throw are always necessary
!      anyway.  */
!   edge e = find_edge (get_edge_src (edge_index), get_edge_dest (edge_index));
!   if (e->flags & EDGE_ABNORMAL)
!     return;
! 
!   if (get_edge_src (edge_index) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
      ending_block = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
    else
!     ending_block = find_pdom (get_edge_src (edge_index));
  
!   for (current_block = get_edge_dest (edge_index);
         current_block != ending_block
         && current_block != EXIT_BLOCK_PTR_FOR_FN (cfun);
         current_block = find_pdom (current_block))
!     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 ()
  {
    timevar_push (TV_CONTROL_DEPENDENCES);
+ 
+   /* Initialize the edge list.  */
+   int num_edges = 0;
+   basic_block bb;
+   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ 		  EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
+     num_edges += EDGE_COUNT (bb->succs);
+   m_el.create (num_edges);
+   edge e;
+   edge_iterator ei;
+   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ 		  EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
+     FOR_EACH_EDGE (e, ei, bb->succs)
+       m_el.quick_push (std::make_pair (e->src->index, e->dest->index));
+ 
    control_dependence_map.create (last_basic_block_for_fn (cfun));
    for (int i = 0; i < last_basic_block_for_fn (cfun); ++i)
      control_dependence_map.quick_push (BITMAP_ALLOC (NULL));
!   for (int i = 0; i < num_edges; ++i)
      find_control_dependence (i);
+ 
    timevar_pop (TV_CONTROL_DEPENDENCES);
  }
  
*************** control_dependences::~control_dependence
*** 455,461 ****
    for (unsigned i = 0; i < control_dependence_map.length (); ++i)
      BITMAP_FREE (control_dependence_map[i]);
    control_dependence_map.release ();
!   free_edge_list (m_el);
  }
  
  /* Returns the bitmap of edges the basic-block I is dependent on.  */
--- 466,472 ----
    for (unsigned i = 0; i < control_dependence_map.length (); ++i)
      BITMAP_FREE (control_dependence_map[i]);
    control_dependence_map.release ();
!   m_el.release ();
  }
  
  /* Returns the bitmap of edges the basic-block I is dependent on.  */
*************** control_dependences::get_edges_dependent
*** 466,477 ****
    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 (m_el, i);
  }
  
  
--- 477,496 ----
    return control_dependence_map[i];
  }
  
! /* Returns the edge source with index I from the edge list.  */
  
! basic_block
! control_dependences::get_edge_src (int i)
! {
!   return BASIC_BLOCK_FOR_FN (cfun, m_el[i].first);
! }
! 
! /* Returns the edge destination with index I from the edge list.  */
! 
! basic_block
! control_dependences::get_edge_dest (int i)
  {
!   return BASIC_BLOCK_FOR_FN (cfun, m_el[i].second);
  }
  
  
Index: gcc/cfganal.h
===================================================================
*** gcc/cfganal.h	(revision 236630)
--- gcc/cfganal.h	(working copy)
*************** struct edge_list
*** 34,50 ****
  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 *m_el;
  };
  
  extern bool mark_dfs_back_edges (void);
--- 34,51 ----
  class control_dependences
  {
  public:
!   control_dependences ();
    ~control_dependences ();
    bitmap get_edges_dependent_on (int);
!   basic_block get_edge_src (int);
!   basic_block get_edge_dest (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;
!   vec<std::pair<int, int> > m_el;
  };
  
  extern bool mark_dfs_back_edges (void);
Index: gcc/tree-ssa-dce.c
===================================================================
*** gcc/tree-ssa-dce.c	(revision 236630)
--- gcc/tree-ssa-dce.c	(working copy)
*************** mark_control_dependent_edges_necessary (
*** 339,345 ****
    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)
  	{
--- 339,345 ----
    EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
  			    0, edge_number, bi)
      {
!       basic_block cd_bb = cd->get_edge_src (edge_number);
  
        if (ignore_self && cd_bb == bb)
  	{
*************** perform_tree_ssa_dce (bool aggressive)
*** 1577,1583 ****
      {
        /* Compute control dependence.  */
        calculate_dominance_info (CDI_POST_DOMINATORS);
!       cd = new control_dependences (create_edge_list ());
  
        visited_control_parents =
  	sbitmap_alloc (last_basic_block_for_fn (cfun));
--- 1577,1583 ----
      {
        /* Compute control dependence.  */
        calculate_dominance_info (CDI_POST_DOMINATORS);
!       cd = new control_dependences ();
  
        visited_control_parents =
  	sbitmap_alloc (last_basic_block_for_fn (cfun));
Index: gcc/tree-loop-distribution.c
===================================================================
*** gcc/tree-loop-distribution.c	(revision 236630)
--- gcc/tree-loop-distribution.c	(working copy)
*************** create_edge_for_control_dependence (stru
*** 278,284 ****
    EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
  			    0, edge_n, bi)
      {
!       basic_block cond_bb = cd->get_edge (edge_n)->src;
        gimple *stmt = last_stmt (cond_bb);
        if (stmt && is_ctrl_stmt (stmt))
  	{
--- 281,287 ----
    EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
  			    0, edge_n, bi)
      {
!       basic_block cond_bb = cd->get_edge_src (edge_n);
        gimple *stmt = last_stmt (cond_bb);
        if (stmt && is_ctrl_stmt (stmt))
  	{
*************** out:
*** 1789,1795 ****
  	    {
  	      calculate_dominance_info (CDI_DOMINATORS);
  	      calculate_dominance_info (CDI_POST_DOMINATORS);
! 	      cd = new control_dependences (create_edge_list ());
  	      free_dominance_info (CDI_POST_DOMINATORS);
  	    }
  	  bool destroy_p;
--- 1802,1808 ----
  	    {
  	      calculate_dominance_info (CDI_DOMINATORS);
  	      calculate_dominance_info (CDI_POST_DOMINATORS);
! 	      cd = new control_dependences ();
  	      free_dominance_info (CDI_POST_DOMINATORS);
  	    }
  	  bool destroy_p;
*************** out:
*** 1815,1828 ****
    if (cd)
      delete cd;
  
-   /* Destroy loop bodies that could not be reused.  Do this late as we
-      otherwise can end up refering to stale data in control dependences.  */
-   unsigned i;
-   FOR_EACH_VEC_ELT (loops_to_be_destroyed, i, loop)
-     destroy_loop (loop);
- 
    if (changed)
      {
        /* Cached scalar evolutions now may refer to wrong or non-existing
  	 loops.  */
        scev_reset_htab ();
--- 1828,1841 ----
    if (cd)
      delete cd;
  
    if (changed)
      {
+       /* Destroy loop bodies that could not be reused.  Do this late as we
+ 	 otherwise can end up refering to stale data in control dependences.  */
+       unsigned i;
+       FOR_EACH_VEC_ELT (loops_to_be_destroyed, i, loop)
+ 	  destroy_loop (loop);
+ 
        /* Cached scalar evolutions now may refer to wrong or non-existing
  	 loops.  */
        scev_reset_htab ();
Index: gcc/testsuite/gcc.dg/torture/pr71253.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr71253.c	(revision 0)
--- gcc/testsuite/gcc.dg/torture/pr71253.c	(working copy)
***************
*** 0 ****
--- 1,35 ----
+ /* { dg-do compile } */
+ /* { dg-additional-options "-ftree-loop-distribution" } */
+ 
+ int jo, af, yb;
+ long int wt;
+ 
+ void
+ nr (void)
+ {
+   int *bf = &yb;
+   for (;;)
+     {
+       while (jo != 0)
+ 	{
+ 	  long int *ad = (long int *) &yb;
+ 	  for (;;)
+ 	    {
+ 	      int fv;
+ 	      for (*ad = 1; *ad < 3; ++(*ad))
+ 		{
+ 		  af = *bf;
+ 		  fv = wt;
+ 		}
+ 	      bf = (int *) &wt;
+ 	      ad = &wt;
+ 	      do
+ 		{
+ 		  jo = wt = ((wt != 0) ? 1 : fv);
+ 		}
+ 	      while (jo != 0);
+ 	    }
+ 	}
+       bf = &af;
+     }
+ }