PR rtl-optimization/28071 (domwalk recursion)

[Jan Hubicka <jh at suse dot cz>]

Hi,
at -O3 the testcase builds huge CFG with depth of dominator tree about
15000 blocks.  This makes GCC to run out of stack space when not built
with optimization and without checking even on Linux.
In RTL world we avoid recusion whose depth depends on CFG size, it is
probably good time to start re-inforcing this on trees.  This patch
avoids recusion on domwalk that is source of most of the stack space
consumption.  The patch does not make non-bootstrapped compiler to work
for me as tree-into-ssa contains one recursive walk of dominator tree
written by hand, but it still shave of few seconds out of the
compilation.

For GCC modules test I also get speedup of about 2 seconds out of 4
minutes.

If accepted, i will send patches for the other few recursive walks as
followups.

Except for fair amount of re-indenting the patch is rather easy. It is
simply using already existing stack walk_data->block_data_stack for the
stack of basic blocks too.

:ADDPATCH middle-end:

Honza

2006-07-27  Jan Hubicka  <jh@suse.cz>
	PR rtl-optimization/28071
	(walk_dominator_tree): Rewrite to be non-recursive.
Index: domwalk.c
===================================================================
*** domwalk.c	(revision 115712)
--- domwalk.c	(working copy)
*************** Boston, MA 02110-1301, USA.  */
*** 137,246 ****
     actions during the dominator walk as well as a stack of block local
     data maintained during the dominator walk.
  
!    BB is the basic block we are currently visiting.  */
  
  void
  walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb)
  {
!   void *bd = NULL;
!   basic_block dest;
!   block_stmt_iterator bsi;
!   bool is_interesting;
! 
!   /* If block BB is not interesting to the caller, then none of the
!      callbacks that walk the statements in BB are going to be
!      executed.  */
!   is_interesting = bb->index < 0
! 		   || walk_data->interesting_blocks == NULL
! 		   || TEST_BIT (walk_data->interesting_blocks, bb->index);
! 
!   /* Callback to initialize the local data structure.  */
!   if (walk_data->initialize_block_local_data)
      {
!       bool recycled;
  
!       /* First get some local data, reusing any local data pointer we may
! 	 have saved.  */
!       if (VEC_length (void_p, walk_data->free_block_data) > 0)
! 	{
! 	  bd = VEC_pop (void_p, walk_data->free_block_data);
! 	  recycled = 1;
! 	}
!       else
  	{
! 	  bd = xcalloc (1, walk_data->block_local_data_size);
! 	  recycled = 0;
! 	}
! 
!       /* Push the local data into the local data stack.  */
!       VEC_safe_push (void_p, heap, walk_data->block_data_stack, bd);
! 
!       /* Call the initializer.  */
!       walk_data->initialize_block_local_data (walk_data, bb, recycled);
! 
!     }
! 
!   /* Callback for operations to execute before we have walked the
!      dominator children, but before we walk statements.  */
!   if (walk_data->before_dom_children_before_stmts)
!     (*walk_data->before_dom_children_before_stmts) (walk_data, bb);
! 
!   /* Statement walk before walking dominator children.  */
!   if (is_interesting && walk_data->before_dom_children_walk_stmts)
!     {
!       if (walk_data->walk_stmts_backward)
! 	for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
! 	  (*walk_data->before_dom_children_walk_stmts) (walk_data, bb, bsi);
!       else
! 	for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
! 	  (*walk_data->before_dom_children_walk_stmts) (walk_data, bb, bsi);
!     }
  
!   /* Callback for operations to execute before we have walked the
!      dominator children, and after we walk statements.  */
!   if (walk_data->before_dom_children_after_stmts)
!     (*walk_data->before_dom_children_after_stmts) (walk_data, bb);
! 
!   /* Recursively call ourselves on the dominator children of BB.  */
!   for (dest = first_dom_son (walk_data->dom_direction, bb);
!        dest;
!        dest = next_dom_son (walk_data->dom_direction, dest))
!     {
!       /* The destination block may have become unreachable, in
! 	 which case there's no point in optimizing it.  */
!       if (EDGE_COUNT (dest->preds) > 0)
! 	walk_dominator_tree (walk_data, dest);
!     }
  
!   /* Callback for operations to execute after we have walked the
!      dominator children, but before we walk statements.  */
!   if (walk_data->after_dom_children_before_stmts)
!     (*walk_data->after_dom_children_before_stmts) (walk_data, bb);
  
!   /* Statement walk after walking dominator children.  */
!   if (is_interesting && walk_data->after_dom_children_walk_stmts)
!     {
!       if (walk_data->walk_stmts_backward)
! 	for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
! 	  (*walk_data->after_dom_children_walk_stmts) (walk_data, bb, bsi);
!       else
! 	for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
! 	  (*walk_data->after_dom_children_walk_stmts) (walk_data, bb, bsi);
!     }
  
!   /* Callback for operations to execute after we have walked the
!      dominator children and after we have walked statements.  */
!   if (walk_data->after_dom_children_after_stmts)
!     (*walk_data->after_dom_children_after_stmts) (walk_data, bb);
  
!   if (walk_data->initialize_block_local_data)
!     {
!       /* And save the block data so that we can re-use it.  */
!       VEC_safe_push (void_p, heap, walk_data->free_block_data, bd);
  
!       /* And finally pop the record off the block local data stack.  */
!       VEC_pop (void_p, walk_data->block_data_stack);
      }
  }
  
  void
--- 137,277 ----
     actions during the dominator walk as well as a stack of block local
     data maintained during the dominator walk.
  
!    BB is the basic block we are currently visiting.
!    
!    Avoid recursion so we don't consume unbounded stack.  */
  
  void
  walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb)
  {
!   do
      {
!       void *bd = NULL;
!       basic_block dest;
!       block_stmt_iterator bsi;
!       bool is_interesting;
! 
!       /* If block BB is not interesting to the caller, then none of the
!          callbacks that walk the statements in BB are going to be
!          executed.  */
!       is_interesting = bb->index < 0
! 	|| walk_data->interesting_blocks == NULL
! 	|| TEST_BIT (walk_data->interesting_blocks, bb->index);
  
!       /* Callback to initialize the local data structure.  */
!       if (walk_data->initialize_block_local_data)
  	{
! 	  bool recycled;
  
! 	  /* First get some local data, reusing any local data pointer we may
! 	     have saved.  */
! 	  if (VEC_length (void_p, walk_data->free_block_data) > 0)
! 	    {
! 	      bd = VEC_pop (void_p, walk_data->free_block_data);
! 	      recycled = 1;
! 	    }
! 	  else
! 	    {
! 	      bd = xcalloc (1, walk_data->block_local_data_size);
! 	      recycled = 0;
! 	    }
  
! 	  /* Push the local data into the local data stack.  */
! 	  VEC_safe_push (void_p, heap, walk_data->block_data_stack, bd);
  
! 	  /* Call the initializer.  */
! 	  walk_data->initialize_block_local_data (walk_data, bb, recycled);
! 	}
  
!       /* Callback for operations to execute before we have walked the
!          dominator children, but before we walk statements.  */
!       if (walk_data->before_dom_children_before_stmts)
! 	(*walk_data->before_dom_children_before_stmts) (walk_data, bb);
  
!       /* Statement walk before walking dominator children.  */
!       if (is_interesting && walk_data->before_dom_children_walk_stmts)
! 	{
! 	  if (walk_data->walk_stmts_backward)
! 	    for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
! 	      (*walk_data->before_dom_children_walk_stmts) (walk_data, bb,
! 							    bsi);
! 	  else
! 	    for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
! 	      (*walk_data->before_dom_children_walk_stmts) (walk_data, bb,
! 							    bsi);
! 	}
  
!       /* Callback for operations to execute before we have walked the
!          dominator children, and after we walk statements.  */
!       if (walk_data->before_dom_children_after_stmts)
! 	(*walk_data->before_dom_children_after_stmts) (walk_data, bb);
! 
!       VEC_safe_push (void_p, heap, walk_data->block_data_stack, bb);
! 
!       /* Look for the first son.  */
!       for (dest = first_dom_son (walk_data->dom_direction, bb);
! 	   dest; dest = next_dom_son (walk_data->dom_direction, dest))
! 	{
! 	  /* The destination block may have become unreachable, in
! 	     which case there's no point in optimizing it.  */
! 	  if (EDGE_COUNT (dest->preds) > 0 && dest != EXIT_BLOCK_PTR)
! 	    break;
! 	}
!       if (dest)
! 	bb = dest;
!       else 
! 	{
! 	  do
! 	    {
! 	      bb = VEC_pop (void_p, walk_data->block_data_stack);
! 	      is_interesting = bb->index < 0
! 		|| walk_data->interesting_blocks == NULL
! 		|| TEST_BIT (walk_data->interesting_blocks, bb->index);
! 
! 	      /* Callback for operations to execute after we have walked the
! 	         dominator children, but before we walk statements.  */
! 	      if (walk_data->after_dom_children_before_stmts)
! 		(*walk_data->after_dom_children_before_stmts) (walk_data, bb);
! 
! 	      /* Statement walk after walking dominator children.  */
! 	      if (is_interesting && walk_data->after_dom_children_walk_stmts)
! 		{
! 		  if (walk_data->walk_stmts_backward)
! 		    for (bsi = bsi_last (bb); !bsi_end_p (bsi);
! 			 bsi_prev (&bsi))
! 		      (*walk_data->after_dom_children_walk_stmts) (walk_data,
! 								   bb, bsi);
! 		  else
! 		    for (bsi = bsi_start (bb); !bsi_end_p (bsi);
! 			 bsi_next (&bsi))
! 		      (*walk_data->after_dom_children_walk_stmts) (walk_data,
! 								   bb, bsi);
! 		}
! 
! 	      /* Callback for operations to execute after we have walked the
! 	         dominator children and after we have walked statements.  */
! 	      if (walk_data->after_dom_children_after_stmts)
! 		(*walk_data->after_dom_children_after_stmts) (walk_data, bb);
! 
! 	      if (walk_data->initialize_block_local_data)
! 		{
! 		  /* Pop the record off the block local data stack.  */
! 		  bd = VEC_pop (void_p, walk_data->block_data_stack);
! 		  /* And save the block data so that we can re-use it.  */
! 		  VEC_safe_push (void_p, heap, walk_data->free_block_data,
! 				 bd);
! 		}
! 	      if (!VEC_empty (void_p, walk_data->block_data_stack))
! 		do
! 		  bb = next_dom_son (walk_data->dom_direction, bb);
! 		while (bb && EDGE_COUNT (bb->preds) == 0);
! 	      else
! 		bb = NULL;
! 	    }
! 	  while (!bb && !VEC_empty (void_p, walk_data->block_data_stack));
! 	}
      }
+   while (bb);
  }
  
  void