more alloca removal [Re: tail recursion]

[Richard Henderson <rth at cygnus dot com>]

On Thu, Nov 04, 1999 at 02:15:58PM +0100, Wilhelm B. Kloke wrote:
> Here is the program to generate temp.c:
> (For the data preiosu the number 3000 had  to be changed to 1000).

[ Generates 3000 statements of 40 random add/sub/mult operations. ]

With the following alloca removal patch, I can compile your test
case.  It still takes (at -O1) about 30 minutes to compile, and has
a peak memory usage of 835M.  The interesting time statistic is

	global-alloc: 1687.729456 (97%)


r~


        * cse.c (cse_main): Use xmalloc, not alloca.
        (cse_basic_block): Likewise.
        * local-alloc.c (local_alloc): Likewise.

Index: cse.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cse.c,v
retrieving revision 1.107
diff -c -p -d -r1.107 cse.c
*** cse.c	1999/11/02 16:00:03	1.107
--- cse.c	1999/11/04 20:42:58
*************** cse_main (f, nregs, after_loop, file)
*** 6877,6884 ****
  
    max_insn_uid = get_max_uid ();
  
!   reg_next_eqv = (int *) alloca (nregs * sizeof (int));
!   reg_prev_eqv = (int *) alloca (nregs * sizeof (int));
  
  #ifdef LOAD_EXTEND_OP
  
--- 6877,6884 ----
  
    max_insn_uid = get_max_uid ();
  
!   reg_next_eqv = (int *) xmalloc (nregs * sizeof (int));
!   reg_prev_eqv = (int *) xmalloc (nregs * sizeof (int));
  
  #ifdef LOAD_EXTEND_OP
  
*************** cse_main (f, nregs, after_loop, file)
*** 6896,6903 ****
    /* Find the largest uid.  */
  
    max_uid = get_max_uid ();
!   uid_cuid = (int *) alloca ((max_uid + 1) * sizeof (int));
!   bzero ((char *) uid_cuid, (max_uid + 1) * sizeof (int));
  
    /* Compute the mapping from uids to cuids.
       CUIDs are numbers assigned to insns, like uids,
--- 6896,6902 ----
    /* Find the largest uid.  */
  
    max_uid = get_max_uid ();
!   uid_cuid = (int *) xcalloc (max_uid + 1, sizeof (int));
  
    /* Compute the mapping from uids to cuids.
       CUIDs are numbers assigned to insns, like uids,
*************** cse_main (f, nregs, after_loop, file)
*** 7024,7029 ****
--- 7023,7031 ----
  
    /* Clean up.  */
    end_alias_analysis ();
+   free (uid_cuid);
+   free (reg_next_eqv);
+   free (reg_prev_eqv);
  
    return cse_jumps_altered || recorded_label_ref;
  }
*************** cse_basic_block (from, to, next_branch, 
*** 7050,7065 ****
    /* Each of these arrays is undefined before max_reg, so only allocate
       the space actually needed and adjust the start below.  */
  
!   qty_first_reg = (int *) alloca ((max_qty - max_reg) * sizeof (int));
!   qty_last_reg = (int *) alloca ((max_qty - max_reg) * sizeof (int));
!   qty_mode = (enum machine_mode *) alloca ((max_qty - max_reg)
  					   * sizeof (enum machine_mode));
!   qty_const = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx));
!   qty_const_insn = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx));
    qty_comparison_code
!     = (enum rtx_code *) alloca ((max_qty - max_reg) * sizeof (enum rtx_code));
!   qty_comparison_qty = (int *) alloca ((max_qty - max_reg) * sizeof (int));
!   qty_comparison_const = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx));
  
    qty_first_reg -= max_reg;
    qty_last_reg -= max_reg;
--- 7052,7067 ----
    /* Each of these arrays is undefined before max_reg, so only allocate
       the space actually needed and adjust the start below.  */
  
!   qty_first_reg = (int *) xmalloc ((max_qty - max_reg) * sizeof (int));
!   qty_last_reg = (int *) xmalloc ((max_qty - max_reg) * sizeof (int));
!   qty_mode = (enum machine_mode *) xmalloc ((max_qty - max_reg)
  					   * sizeof (enum machine_mode));
!   qty_const = (rtx *) xmalloc ((max_qty - max_reg) * sizeof (rtx));
!   qty_const_insn = (rtx *) xmalloc ((max_qty - max_reg) * sizeof (rtx));
    qty_comparison_code
!     = (enum rtx_code *) xmalloc ((max_qty - max_reg) * sizeof (enum rtx_code));
!   qty_comparison_qty = (int *) xmalloc ((max_qty - max_reg) * sizeof (int));
!   qty_comparison_const = (rtx *) xmalloc ((max_qty - max_reg) * sizeof (rtx));
  
    qty_first_reg -= max_reg;
    qty_last_reg -= max_reg;
*************** cse_basic_block (from, to, next_branch, 
*** 7235,7240 ****
--- 7237,7251 ----
        && JUMP_LABEL (PREV_INSN (to)) != 0
        && LABEL_NUSES (JUMP_LABEL (PREV_INSN (to))) == 1)
      cse_around_loop (JUMP_LABEL (PREV_INSN (to)));
+ 
+   free (qty_first_reg + max_reg);
+   free (qty_last_reg + max_reg);
+   free (qty_mode + max_reg);
+   free (qty_const + max_reg);
+   free (qty_const_insn + max_reg);
+   free (qty_comparison_code + max_reg);
+   free (qty_comparison_qty + max_reg);
+   free (qty_comparison_const + max_reg);
  
    return to ? NEXT_INSN (to) : 0;
  }
Index: local-alloc.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/local-alloc.c,v
retrieving revision 1.51
diff -c -p -d -r1.51 local-alloc.c
*** local-alloc.c	1999/10/27 19:27:41	1.51
--- local-alloc.c	1999/11/04 20:42:59
*************** local_alloc ()
*** 326,350 ****
       See the declarations of these variables, above,
       for what they mean.  */
  
!   qty_phys_reg = (short *) alloca (max_qty * sizeof (short));
    qty_phys_copy_sugg
!     = (HARD_REG_SET *) alloca (max_qty * sizeof (HARD_REG_SET));
!   qty_phys_num_copy_sugg = (short *) alloca (max_qty * sizeof (short));
!   qty_phys_sugg = (HARD_REG_SET *) alloca (max_qty * sizeof (HARD_REG_SET));
!   qty_phys_num_sugg = (short *) alloca (max_qty * sizeof (short));
!   qty_birth = (int *) alloca (max_qty * sizeof (int));
!   qty_death = (int *) alloca (max_qty * sizeof (int));
!   qty_first_reg = (int *) alloca (max_qty * sizeof (int));
!   qty_size = (int *) alloca (max_qty * sizeof (int));
    qty_mode
!     = (enum machine_mode *) alloca (max_qty * sizeof (enum machine_mode));
!   qty_n_calls_crossed = (int *) alloca (max_qty * sizeof (int));
    qty_min_class
!     = (enum reg_class *) alloca (max_qty * sizeof (enum reg_class));
    qty_alternate_class
!     = (enum reg_class *) alloca (max_qty * sizeof (enum reg_class));
!   qty_n_refs = (int *) alloca (max_qty * sizeof (int));
!   qty_changes_size = (char *) alloca (max_qty * sizeof (char));
  
    reg_qty = (int *) xmalloc (max_regno * sizeof (int));
    reg_offset = (char *) xmalloc (max_regno * sizeof (char));
--- 326,350 ----
       See the declarations of these variables, above,
       for what they mean.  */
  
!   qty_phys_reg = (short *) xmalloc (max_qty * sizeof (short));
    qty_phys_copy_sugg
!     = (HARD_REG_SET *) xmalloc (max_qty * sizeof (HARD_REG_SET));
!   qty_phys_num_copy_sugg = (short *) xmalloc (max_qty * sizeof (short));
!   qty_phys_sugg = (HARD_REG_SET *) xmalloc (max_qty * sizeof (HARD_REG_SET));
!   qty_phys_num_sugg = (short *) xmalloc (max_qty * sizeof (short));
!   qty_birth = (int *) xmalloc (max_qty * sizeof (int));
!   qty_death = (int *) xmalloc (max_qty * sizeof (int));
!   qty_first_reg = (int *) xmalloc (max_qty * sizeof (int));
!   qty_size = (int *) xmalloc (max_qty * sizeof (int));
    qty_mode
!     = (enum machine_mode *) xmalloc (max_qty * sizeof (enum machine_mode));
!   qty_n_calls_crossed = (int *) xmalloc (max_qty * sizeof (int));
    qty_min_class
!     = (enum reg_class *) xmalloc (max_qty * sizeof (enum reg_class));
    qty_alternate_class
!     = (enum reg_class *) xmalloc (max_qty * sizeof (enum reg_class));
!   qty_n_refs = (int *) xmalloc (max_qty * sizeof (int));
!   qty_changes_size = (char *) xmalloc (max_qty * sizeof (char));
  
    reg_qty = (int *) xmalloc (max_regno * sizeof (int));
    reg_offset = (char *) xmalloc (max_regno * sizeof (char));
*************** local_alloc ()
*** 416,424 ****
--- 416,440 ----
  #endif
      }
  
+   free (qty_phys_reg);
+   free (qty_phys_copy_sugg);
+   free (qty_phys_num_copy_sugg);
+   free (qty_phys_sugg);
+   free (qty_birth);
+   free (qty_death);
+   free (qty_first_reg);
+   free (qty_size);
+   free (qty_mode);
+   free (qty_n_calls_crossed);
+   free (qty_min_class);
+   free (qty_alternate_class);
+   free (qty_n_refs);
+   free (qty_changes_size);
+ 
    free (reg_qty);
    free (reg_offset);
    free (reg_next_in_qty);
+ 
    return recorded_label_ref;
  }