PR 10776 II

[Jan Hubicka <jh at suse dot cz>]

Hi,
With -O2 I still get explosion, this time in scheduler.  Mainline gets
out of memory after allocating 1GB for dependency chains, 3.0.4 just
loops forever sorting the insn queue.
The explosion is a but I will try to solve later caused by fact that we
produce unnecesary OUTPUT dependencies in between obviously not aliasing
stores, however the fact that scheduler is inherently quadratic remains.

This patch take care of it in easy way of splitting very large basic
blocks.  I don't think this will have important impact on perfomrance of
something (there are no such blocks in SPEC build) and it cuts memory
usage to 50MB and time to 99 seconds.

Bootstrapped/regtested i386 OK?
Honza

2004-01-10  Jan Hubicka  <jh@suse.cz>
	* toplev.c (rest_of_handle_sched, rest_of_handle_sched2): Split
	gigantic blocks.
	* basic-block.h (split_gigantic_basic_blocks): Declare.
	* cfganal.c (split_gigantic_basic_blocks): New function.
	* params.def (PARAM_MAX_SCHEDULER_BLOCK_INSN): New parameter.

Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.860
diff -c -3 -p -r1.860 toplev.c
*** toplev.c	6 Jan 2004 16:51:20 -0000	1.860
--- toplev.c	10 Jan 2004 19:56:48 -0000
*************** rest_of_handle_sched (tree decl, rtx ins
*** 2328,2333 ****
--- 2342,2348 ----
        /* Do control and data sched analysis,
  	 and write some of the results to dump file.  */
  
+       split_gigantic_basic_blocks (PARAM_VALUE (PARAM_MAX_SCHEDULER_BLOCK_INSN));
        schedule_insns (rtl_dump_file);
  
        close_dump_file (DFI_sched, print_rtl_with_bb, insns);
*************** rest_of_handle_sched2 (tree decl, rtx in
*** 2349,2354 ****
--- 2364,2370 ----
  
    split_all_insns (1);
  
+   split_gigantic_basic_blocks (PARAM_VALUE (PARAM_MAX_SCHEDULER_BLOCK_INSN));
    if (flag_sched2_use_superblocks || flag_sched2_use_traces)
      {
        schedule_ebbs (rtl_dump_file);
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.186
diff -c -3 -p -r1.186 basic-block.h
*** basic-block.h	30 Dec 2003 10:40:48 -0000	1.186
--- basic-block.h	10 Jan 2004 19:56:48 -0000
*************** extern void iterate_fix_dominators (enum
*** 640,645 ****
--- 640,646 ----
  extern void verify_dominators (enum cdi_direction);
  extern basic_block first_dom_son (enum cdi_direction, basic_block);
  extern basic_block next_dom_son (enum cdi_direction, basic_block);
+ extern bool split_gigantic_basic_blocks (int);
  
  #include "cfghooks.h"
  
Index: cfganal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfganal.c,v
retrieving revision 1.39
diff -c -3 -p -r1.39 cfganal.c
*** cfganal.c	11 Dec 2003 00:20:36 -0000	1.39
--- cfganal.c	10 Jan 2004 19:56:48 -0000
*************** dfs_enumerate_from (basic_block bb, int 
*** 1144,1146 ****
--- 1144,1176 ----
      rslt[sp]->flags &= ~BB_VISITED;
    return tv;
  }
+ 
+ /* Make avreage basic block to not be bigger than INSNS.  This function can
+    be usefull to limit quadratic behaviour of some slow local algorithms.
+    When splitting, we curefully avoid introducing very small basic block at the
+    end of original block, so the block may be bigger than INSNS.  */
+ bool
+ split_gigantic_basic_blocks (int insns)
+ {
+   basic_block bb;
+ 
+   FOR_EACH_BB (bb)
+     {
+       int num = 0;
+       rtx insn;
+       rtx splitpoint = NULL;
+ 
+       for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
+ 	{
+ 	  if (INSN_P (insn))
+ 	    num++;
+ 	  if (num > insns)
+ 	    {
+ 	      if (splitpoint)
+ 		bb = split_block (bb, splitpoint)->dest;
+ 	      splitpoint = insn;
+ 	      num = 0;
+ 	    }
+ 	}
+     }
+ }
Index: params.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/params.def,v
retrieving revision 1.31
diff -c -3 -p -r1.31 params.def
*** params.def	9 Nov 2003 02:37:54 -0000	1.31
--- params.def	10 Jan 2004 19:56:48 -0000
*************** DEFPARAM(PARAM_MAX_CROSSJUMP_EDGES,
*** 232,242 ****
--- 232,248 ----
  	 "The maximum number of incoming edges to consider for crossjumping",
  	 100)
  
+ /* The maximum size of basic block considered by the scheduler.  */
+ DEFPARAM(PARAM_MAX_SCHEDULER_BLOCK_INSN,
+ 	 "max-scheduler-block-insn",
+ 	 "The maximum number of instructions cosidered to be single basic block for scheduler",
+ 	 200)
+ 
  /* The maximum length of path considered in cse.  */
  DEFPARAM(PARAM_MAX_CSE_PATH_LENGTH,
  	 "max-cse-path-length",
  	 "The maximum length of path considered in cse",
  	 10)
  
  #ifdef ENABLE_GC_ALWAYS_COLLECT
  # define GGC_MIN_EXPAND_DEFAULT 0