[tree-ssa] tree-cfg.c cleanups/fixes when removing blocks with reachable children

[law at redhat dot com]

This code will likely go away once Zdenek's work on killing our container
based IL is complete.  However until then this is a significant improvement
over the existing code.

The fundamental problem is the existing code relied on the badly implemented
find_subblocks to determine what blocks were sub-blocks of a nested control
statement.  find_subblocks merely started at the control statement's block
and iterated forward through the basic blocks checking to see if the
parent was unchanged.  I won't go into all the details, but it should be
sufficient to say this failed in numerous ways -- sometimes claiming too
many blocks where subblocks, sometimes claiming too few blocks were subblocks.

My jump threading through conditional branches change creates code with
less structure and more throughly exercises the code to deal with
unreachable control structures with reachable children.  It became pretty
clear that find_subblocks as it was implemented was unfixable.  Luckily
I had written find_contained_blocks to support EH, which does the same thing,
but actually gets it right :-)

Bootstrapped and regression tested.

	* tree-cfg.c (blocks_unreachable_p, remove_blocks): Use a bitmap
	rather than a varray.
	(REMOVE_ALL_STMTS, REMOVE_NO_STMTS): New defines for remove_bb.
	(REMOVE_NON_CONTROL_STMTS, REMOVE_CONTROL_STMTS): Likewise.
	(remove_unreachable_block): Use find_contained_blocks rather
	than find_subblocks.  If we have a COND_EXPR or SWITCH_EXPR which
	is unreachable, but which has reachable children clear out the
	condition and request all non-control statements be removed
	from the block.
	(remove_bb): Allow better control over what (if any) statements
	are removed.  All callers updated.
	(find_subblocks): Remove.
	(find_contained_blocks): Handle statements with no associated
	basic block.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.149
diff -c -3 -p -r1.1.4.149 tree-cfg.c
*** tree-cfg.c	15 Aug 2003 20:47:54 -0000	1.1.4.149
--- tree-cfg.c	17 Aug 2003 17:59:48 -0000
*************** static struct loops *tree_loop_optimizer
*** 120,132 ****
  static void tree_loop_optimizer_finalize (struct loops *, FILE *);
  
  /* Flowgraph optimization and cleanup.  */
  static void remove_unreachable_blocks (void);
  static void remove_unreachable_block (basic_block);
  static void remove_bb (basic_block, int);
  static void remove_stmt (tree *, bool);
! static bool blocks_unreachable_p (varray_type);
! static void remove_blocks (varray_type);
! static varray_type find_subblocks (basic_block);
  static bool is_parent (basic_block, basic_block);
  static void cleanup_control_flow (void);
  static void cleanup_cond_expr_graph (basic_block);
--- 120,139 ----
  static void tree_loop_optimizer_finalize (struct loops *, FILE *);
  
  /* Flowgraph optimization and cleanup.  */
+ 
+ /* Flags to pass to remove_bb to indicate which (if any) statements
+    should be removed.  */
+ #define REMOVE_ALL_STMTS -1
+ #define REMOVE_NO_STMTS 0
+ #define REMOVE_NON_CONTROL_STMTS 0x1
+ #define REMOVE_CONTROL_STMTS 0x2
+ 
  static void remove_unreachable_blocks (void);
  static void remove_unreachable_block (basic_block);
  static void remove_bb (basic_block, int);
  static void remove_stmt (tree *, bool);
! static bool blocks_unreachable_p (bitmap);
! static void remove_blocks (bitmap);
  static bool is_parent (basic_block, basic_block);
  static void cleanup_control_flow (void);
  static void cleanup_cond_expr_graph (basic_block);
*************** find_contained_blocks (tree *stmt_p, bit
*** 1078,1084 ****
  
        /* Mark this statement's block as being contained.  */
        bb = bb_for_stmt (stmt);
!       bitmap_set_bit (my_blocks, bb->index);
  
        /* And recurse down into control structures.  */
        code = TREE_CODE (stmt);
--- 1085,1092 ----
  
        /* Mark this statement's block as being contained.  */
        bb = bb_for_stmt (stmt);
!       if (bb)
! 	bitmap_set_bit (my_blocks, bb->index);
  
        /* And recurse down into control structures.  */
        code = TREE_CODE (stmt);
*************** remove_unreachable_blocks (void)
*** 1846,1855 ****
  static void
  remove_unreachable_block (basic_block bb)
  {
-   varray_type subblocks;
- 
    if (bb->flags & BB_CONTROL_EXPR)
      {
        /* Before removing an entry block for a compound structure,
           make sure that all its subblocks are unreachable as well.
  	 FIXME: This is lame.  We should linearize this control
--- 1854,1865 ----
  static void
  remove_unreachable_block (basic_block bb)
  {
    if (bb->flags & BB_CONTROL_EXPR)
      {
+       tree *last_p = last_stmt_ptr (bb);
+       tree *dummy_p;
+       bitmap subblocks = BITMAP_XMALLOC ();
+ 
        /* Before removing an entry block for a compound structure,
           make sure that all its subblocks are unreachable as well.
  	 FIXME: This is lame.  We should linearize this control
*************** remove_unreachable_block (basic_block bb
*** 1868,1884 ****
  		    8	  } while (...);
  
  	 The entry block (line 2) is unreachable but its body isn't.  */
!       subblocks = find_subblocks (bb);
        if (blocks_unreachable_p (subblocks))
  	{
  	  remove_blocks (subblocks);
- 	  remove_bb (bb, 1);
  	}
        else
! 	remove_bb (bb, 0);
      }
    else
!     remove_bb (bb, 1);
  }
  
  
--- 1878,1909 ----
  		    8	  } while (...);
  
  	 The entry block (line 2) is unreachable but its body isn't.  */
!       find_contained_blocks (last_p, subblocks, &dummy_p);
        if (blocks_unreachable_p (subblocks))
  	{
  	  remove_blocks (subblocks);
  	}
        else
! 	{
! 
! 	  /* If we have reachable subblocks, then we can not remove
! 	     control statements.  But we also can't simply leave them
! 	     as-is since they may refer to SSA variables which will
! 	     not get renamed since this block has become unreachable.
! 
! 	     So cleanup any variable references in toplevel control
! 	     structures.  This may or may not be sufficient.  */
! 	  if (TREE_CODE (*last_p) == COND_EXPR)
! 	    COND_EXPR_COND (*last_p) = integer_zero_node;
! 	  else if (TREE_CODE (*last_p) == SWITCH_EXPR)
! 	    SWITCH_COND (*last_p) = integer_zero_node;
! 	  remove_bb (bb, REMOVE_NON_CONTROL_STMTS);
! 	}
! 
!       BITMAP_XFREE (subblocks);
      }
    else
!     remove_bb (bb, REMOVE_ALL_STMTS);
  }
  
  
*************** remove_phi_nodes_and_edges_for_unreachab
*** 1920,1926 ****
     compound structure are also removed.  */
  
  static void
! remove_bb (basic_block bb, int remove_stmts)
  {
    block_stmt_iterator i;
    bsi_list_p stack;
--- 1945,1951 ----
     compound structure are also removed.  */
  
  static void
! remove_bb (basic_block bb, int remove_stmt_flags)
  {
    block_stmt_iterator i;
    bsi_list_p stack;
*************** remove_bb (basic_block bb, int remove_st
*** 1943,1953 ****
        tree stmt = bsi_stmt (i);
  
        set_bb_for_stmt (stmt, NULL);
!       if (remove_stmts)
          {
  	  loc.file = get_filename (stmt);
  	  loc.line = get_lineno (stmt);
! 	  bsi_remove (&i);
          }
      }
  
--- 1968,1982 ----
        tree stmt = bsi_stmt (i);
  
        set_bb_for_stmt (stmt, NULL);
!       if (remove_stmt_flags)
          {
+ 	  int ctrl_stmt = is_ctrl_stmt (stmt);
+ 
  	  loc.file = get_filename (stmt);
  	  loc.line = get_lineno (stmt);
! 	  if ((ctrl_stmt && (remove_stmt_flags & REMOVE_CONTROL_STMTS))
! 	      || (!ctrl_stmt && (remove_stmt_flags & REMOVE_NON_CONTROL_STMTS)))
! 	    bsi_remove (&i);
          }
      }
  
*************** remove_bb (basic_block bb, int remove_st
*** 1955,1961 ****
       block is unreachable.  We walk statements backwards in the
       loop above, so the last statement we process is the first statement
       in the block.  */
!   if (remove_stmts && warn_notreached)
      warning ("%Hwill never be executed", &loc);
  
    if (bb->head_tree_p)
--- 1984,1990 ----
       block is unreachable.  We walk statements backwards in the
       loop above, so the last statement we process is the first statement
       in the block.  */
!   if (remove_stmt_flags && warn_notreached)
      warning ("%Hwill never be executed", &loc);
  
    if (bb->head_tree_p)
*************** remove_bb (basic_block bb, int remove_st
*** 1976,2042 ****
  }
  
  
! /* Remove all the blocks in BB_ARRAY.  */
  
  static void
! remove_blocks (varray_type bb_array)
  {
    size_t i;
  
!   for (i = 0; i < VARRAY_ACTIVE_SIZE (bb_array); i++)
      {
!       basic_block bb = VARRAY_BB (bb_array, i);
!       remove_bb (bb, 1);
!     }
  }
  
  
! /* Return true if all the blocks in BB_ARRAY are unreachable.  */
  
  static bool
! blocks_unreachable_p (varray_type bb_array)
  {
    size_t i;
  
!   for (i = 0; i < VARRAY_ACTIVE_SIZE (bb_array); i++)
      {
!       basic_block bb = VARRAY_BB (bb_array, i);
!       if (bb->flags & BB_REACHABLE)
  	return false;
!     }
  
    return true;
  }
  
- 
- /* Find all the blocks in the graph that are included in the compound
-    structure starting at block BB.  */
- 
- static varray_type
- find_subblocks (basic_block bb)
- {
-   varray_type subblocks;
-   basic_block child_bb;
- 
-   VARRAY_BB_INIT (subblocks, 5, "subblocks");
- 
-   if (bb->flags & BB_CONTROL_EXPR)
-     {
-       /* FIXME: This assumes that all the blocks inside a compound a control
- 	 structure are consecutive in the linked list of blocks.  This is
- 	 only true when the flow graph is initially built.  */
-       child_bb = bb->next_bb;
-       while (child_bb != EXIT_BLOCK_PTR && is_parent (bb, child_bb))
- 	{
- 	  VARRAY_PUSH_BB (subblocks, child_bb);
- 	  child_bb = child_bb->next_bb;
- 	}
-     }
- 
-   return subblocks;
- }
- 
- 
  /* Return true if BB is a control parent for CHILD_BB.
  
     Notice that this property is not the same as dominance.  This
--- 2005,2045 ----
  }
  
  
! /* Remove all the blocks in bitmap BLOCKS.  */
  
  static void
! remove_blocks (bitmap blocks)
  {
    size_t i;
  
!   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
      {
!       basic_block bb = BASIC_BLOCK (i);
! 
!       if (bb && bb->index != INVALID_BLOCK)     
! 	remove_bb (bb, REMOVE_ALL_STMTS);
!     });
  }
  
  
! /* Return true if all the blocks in bitmap BLOCKS are unreachable.  */
  
  static bool
! blocks_unreachable_p (bitmap blocks)
  {
    size_t i;
  
!   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
      {
!       basic_block bb = BASIC_BLOCK (i);
! 
!       if (bb && bb->index != INVALID_BLOCK && bb->flags & BB_REACHABLE)
  	return false;
!     });
  
    return true;
  }
  
  /* Return true if BB is a control parent for CHILD_BB.
  
     Notice that this property is not the same as dominance.  This
*************** linearize_cond_expr (tree *entry_p, basi
*** 2632,2640 ****
  	     the disconnected blocks.  Note this will remove any edges
  	     from BB to the disconnected blocks.  */
  	  if (then_block)
! 	    remove_bb (then_block, 0);
  	  if (else_block)
! 	    remove_bb (else_block, 0);
  
  	  /* And finally remove the useless statement.  */
  	  remove_stmt (entry_p, true);
--- 2635,2643 ----
  	     the disconnected blocks.  Note this will remove any edges
  	     from BB to the disconnected blocks.  */
  	  if (then_block)
! 	    remove_bb (then_block, REMOVE_NO_STMTS);
  	  if (else_block)
! 	    remove_bb (else_block, REMOVE_NO_STMTS);
  
  	  /* And finally remove the useless statement.  */
  	  remove_stmt (entry_p, true);
*************** linearize_cond_expr (tree *entry_p, basi
*** 2651,2657 ****
  	  if (then_block)
  	    {
  	      move_outgoing_edges (bb, then_block);
! 	      remove_bb (then_block, 0);
  	    }
  	  remove_stmt (entry_p, true);
  	}
--- 2654,2660 ----
  	  if (then_block)
  	    {
  	      move_outgoing_edges (bb, then_block);
! 	      remove_bb (then_block, REMOVE_NO_STMTS);
  	    }
  	  remove_stmt (entry_p, true);
  	}
*************** linearize_cond_expr (tree *entry_p, basi
*** 2670,2676 ****
  	  if (else_block)
  	    {
  	      move_outgoing_edges (bb, else_block);
! 	      remove_bb (else_block, 0);
  	    }
  	  remove_stmt (entry_p, true);
  	}
--- 2673,2679 ----
  	  if (else_block)
  	    {
  	      move_outgoing_edges (bb, else_block);
! 	      remove_bb (else_block, REMOVE_NO_STMTS);
  	    }
  	  remove_stmt (entry_p, true);
  	}
*************** merge_tree_blocks (basic_block bb1, basi
*** 4763,4769 ****
    bb2->end_tree_p = NULL;
    bb2->pred = NULL;
    bb2->succ = NULL;
!   remove_bb (bb2, 0);
  }
  
  
--- 4766,4772 ----
    bb2->end_tree_p = NULL;
    bb2->pred = NULL;
    bb2->succ = NULL;
!   remove_bb (bb2, REMOVE_NO_STMTS);
  }