PR rtl-optimization/PR28071 (quadratic memory consumption in gimple split_block)

[Jan Hubicka <jh at suse dot cz>]

Hi,
the testcase in PR28071 consume over 1GB of memory.  Quite amusingly majority
of the memory is consumed by stmt_list nodes produced by tree_split_block
called from inliner.
The patch avoids the quadratic memory behaviour.  It keeps the runtime
behaviour but inliner is by far not the slowest pass around on this testcase.
The splitting can be made linear if inliner was walking function body backward
or probably better tree_split_block was splitting the other way around
(renumbering the first block), but this is probably not stage3 matherial.

Bootstrapped/regtested i686-linux.

:ADDPATCH middle-end:

2006-07-24  Jan Hubicka  <jh@suse.cz>
	PR rtl-optimization/28071
	* tree-cfg.c (tree_split_block): Do allocate new stmt_list nodes.
Index: tree-cfg.c
===================================================================
*** tree-cfg.c	(revision 115645)
--- tree-cfg.c	(working copy)
*************** tree_redirect_edge_and_branch_force (edg
*** 4158,4164 ****
  static basic_block
  tree_split_block (basic_block bb, void *stmt)
  {
!   block_stmt_iterator bsi, bsi_tgt;
    tree act;
    basic_block new_bb;
    edge e;
--- 4158,4165 ----
  static basic_block
  tree_split_block (basic_block bb, void *stmt)
  {
!   block_stmt_iterator bsi;
!   tree_stmt_iterator tsi_tgt;
    tree act;
    basic_block new_bb;
    edge e;
*************** tree_split_block (basic_block bb, void *
*** 4192,4204 ****
  	}
      }
  
!   bsi_tgt = bsi_start (new_bb);
!   while (!bsi_end_p (bsi))
!     {
!       act = bsi_stmt (bsi);
!       bsi_remove (&bsi, false);
!       bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
!     }
  
    return new_bb;
  }
--- 4193,4209 ----
  	}
      }
  
!   if (bsi_end_p (bsi))
!     return new_bb;
! 
!   /* Split the statement list - avoid re-creating new containers as this
!      brings ugly quadratic memory consumption in the inliner.  
!      (We are still quadratic since we need to update stmt BB pointers,
!      sadly) */
!   new_bb->stmt_list = tsi_split_statement_list_before (&bsi.tsi);
!   for (tsi_tgt = tsi_start (new_bb->stmt_list);
!        !tsi_end_p (tsi_tgt); tsi_next (&tsi_tgt))
!     set_bb_for_stmt (tsi_stmt (tsi_tgt), new_bb);
  
    return new_bb;
  }