Patch for memory explosion with templates/inlines

Mark Mitchell mmitchell@usa.net
Thu Dec 18 01:28:00 GMT 1997


Attached below is a patch that reduces memory usage enormously for
code making use of templates and inline functions.  The problem occurred
if an instantiation of one inline caused the instantiation of
another.  The inner inline would use some labels, thereby bumping
label_num.  Then, the outer inline would allocate copies of all those
labels.  If the nesting goes several (e.g., 10) levels deep, all of a
sudden we were allocating 660,000 labels at a go in
expand_inline_function, quite quickly exhausting virtual memory.  The
patch below does the allocation of the labels lazily, which solves the
problem. 

Thanks to Gerald for providing a test case.  In it's boiled down form
it looked like:

    #include <vector>

    class IDENT
    {
    };

    class ATOM
    {
    public:
      vector<IDENT>* params;

      ~ATOM() { delete params; }
    };


    void testDEPGRAPH()
    {
      vector<vector<vector<ATOM> > > componentConstraints;
    }

It was the destructor for componentConstraints that caused the
trouble: it triggered an inline expansion chain about 20 levels deep. 

This program exhausted VM using -O1 on my Linux/GNU box.  Now, it
compiles comfortably.  I suspect that this patch will improve
compile-time performance even on programs that compiled sucessfully
before.

-- 
Mark Mitchell		mmitchell@usa.net
Stanford University	http://www.stanford.edu

1997-12-18  Mark Mitchell  <mmitchell@usa.net>

	* integrate.c (get_label_from_map): New function.
	(expand_inline_function): Use it.  Initialize the label_map to
	NULL_RTX instead of gen_label_rtx.
	(copy_rtx_and_substitute): Use get_label_from_map.
	* integrate.h (get_label_from_map): New function.
	(set_label_from_map): New macro.
	* unroll.c (unroll_loop): Use them.
	(copy_loop_body): Ditto.
	
cvs diff: Diffing .
Index: integrate.c
===================================================================
RCS file: /home/mitchell/Repository/egcs/gcc/integrate.c,v
retrieving revision 1.1.1.3
diff -c -p -r1.1.1.3 integrate.c
*** integrate.c	1997/12/17 06:29:27	1.1.1.3
--- integrate.c	1997/12/18 09:06:56
*************** static void set_block_abstract_flags PRO
*** 77,82 ****
--- 77,101 ----
  
  void set_decl_abstract_flags	PROTO((tree, int));
  
+ /* Returns the Ith entry in the label_map contained in MAP.  If the
+    Ith entry has not yet been set, it is assumed to be a fresh label.
+    Essentially, we use this function to perform a lazy initialization
+    of label_map, thereby avoiding huge memory explosions when the
+    label_map gets very large.  */
+ rtx
+ get_label_from_map (map, i)
+      struct inline_remap* map;
+      int i;
+ {
+   rtx x = map->label_map[i];
+ 
+   if (x == NULL_RTX)
+     x = map->label_map[i] = gen_label_rtx();
+ 
+   return x;
+ }
+ 
+ 
  /* Zero if the current function (whose FUNCTION_DECL is FNDECL)
     is safe and reasonable to integrate into other functions.
     Nonzero means value is a warning message with a single %s
*************** expand_inline_function (fndecl, parms, t
*** 1767,1773 ****
  
    /* Make new label equivalences for the labels in the called function.  */
    for (i = min_labelno; i < max_labelno; i++)
!     map->label_map[i] = gen_label_rtx ();
  
    /* Perform postincrements before actually calling the function.  */
    emit_queue ();
--- 1786,1792 ----
  
    /* Make new label equivalences for the labels in the called function.  */
    for (i = min_labelno; i < max_labelno; i++)
!     map->label_map[i] = NULL_RTX;
  
    /* Perform postincrements before actually calling the function.  */
    emit_queue ();
*************** expand_inline_function (fndecl, parms, t
*** 1966,1972 ****
  	  break;
  
  	case CODE_LABEL:
! 	  copy = emit_label (map->label_map[CODE_LABEL_NUMBER (insn)]);
  	  LABEL_NAME (copy) = LABEL_NAME (insn);
  	  map->const_age++;
  	  break;
--- 1985,1993 ----
  	  break;
  
  	case CODE_LABEL:
! 	  copy = 
! 	    emit_label (get_label_from_map(map,
! 					   CODE_LABEL_NUMBER (insn)));
  	  LABEL_NAME (copy) = LABEL_NAME (insn);
  	  map->const_age++;
  	  break;
*************** expand_inline_function (fndecl, parms, t
*** 1989,1995 ****
  	      if (copy && (NOTE_LINE_NUMBER (copy) == NOTE_INSN_EH_REGION_BEG
  			   || NOTE_LINE_NUMBER (copy) == NOTE_INSN_EH_REGION_END))
  		{
! 		  rtx label = map->label_map[NOTE_BLOCK_NUMBER (copy)];
  
  		  /* We have to forward these both to match the new exception
  		     region.  */
--- 2010,2017 ----
  	      if (copy && (NOTE_LINE_NUMBER (copy) == NOTE_INSN_EH_REGION_BEG
  			   || NOTE_LINE_NUMBER (copy) == NOTE_INSN_EH_REGION_END))
  		{
! 		  rtx label =
! 		    get_label_from_map (map, NOTE_BLOCK_NUMBER (copy));
  
  		  /* We have to forward these both to match the new exception
  		     region.  */
*************** copy_rtx_and_substitute (orig, map)
*** 2404,2417 ****
        return gen_rtx (code, VOIDmode, copy);
  
      case CODE_LABEL:
!       LABEL_PRESERVE_P (map->label_map[CODE_LABEL_NUMBER (orig)])
  	= LABEL_PRESERVE_P (orig);
!       return map->label_map[CODE_LABEL_NUMBER (orig)];
  
      case LABEL_REF:
        copy = gen_rtx (LABEL_REF, mode,
  		      LABEL_REF_NONLOCAL_P (orig) ? XEXP (orig, 0)
! 		      : map->label_map[CODE_LABEL_NUMBER (XEXP (orig, 0))]);
        LABEL_OUTSIDE_LOOP_P (copy) = LABEL_OUTSIDE_LOOP_P (orig);
  
        /* The fact that this label was previously nonlocal does not mean
--- 2426,2440 ----
        return gen_rtx (code, VOIDmode, copy);
  
      case CODE_LABEL:
!       LABEL_PRESERVE_P (get_label_from_map (map, CODE_LABEL_NUMBER (orig)))
  	= LABEL_PRESERVE_P (orig);
!       return get_label_from_map (map, CODE_LABEL_NUMBER (orig));
  
      case LABEL_REF:
        copy = gen_rtx (LABEL_REF, mode,
  		      LABEL_REF_NONLOCAL_P (orig) ? XEXP (orig, 0)
! 		      : get_label_from_map (map, 
! 					    CODE_LABEL_NUMBER (XEXP (orig, 0))));
        LABEL_OUTSIDE_LOOP_P (copy) = LABEL_OUTSIDE_LOOP_P (orig);
  
        /* The fact that this label was previously nonlocal does not mean
Index: integrate.h
===================================================================
RCS file: /home/mitchell/Repository/egcs/gcc/integrate.h,v
retrieving revision 1.1.1.1
diff -c -p -r1.1.1.1 integrate.h
*** integrate.h	1997/11/08 17:53:40	1.1.1.1
--- integrate.h	1997/12/18 09:08:18
*************** extern void try_constants PROTO((rtx, st
*** 122,127 ****
--- 122,134 ----
  
  extern void mark_stores PROTO((rtx, rtx));
  
+ /* Return the label indicated.  */
+ extern rtx get_label_from_map PROTO((struct inline_remap *, int));
+ 
+ /* Set the label indicated.  */
+ #define set_label_in_map(map, i, x) \
+   ((map)->label_map[i] = (x))
+ 
  /* Unfortunately, we need a global copy of const_equiv map for communication
     with a function called from note_stores.  Be *very* careful that this
     is used properly in the presence of recursion.  */
Index: unroll.c
===================================================================
RCS file: /home/mitchell/Repository/egcs/gcc/unroll.c,v
retrieving revision 1.1.1.3
diff -c -p -r1.1.1.3 unroll.c
*** unroll.c	1997/12/08 07:30:41	1.1.1.3
--- unroll.c	1997/12/18 08:58:07
*************** unroll_loop (loop_end, insn_count, loop_
*** 691,698 ****
        else if (GET_CODE (insn) == JUMP_INSN)
  	{
  	  if (JUMP_LABEL (insn))
! 	    map->label_map[CODE_LABEL_NUMBER (JUMP_LABEL (insn))]
! 	      = JUMP_LABEL (insn);
  	  else if (GET_CODE (PATTERN (insn)) == ADDR_VEC
  		   || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
  	    {
--- 691,699 ----
        else if (GET_CODE (insn) == JUMP_INSN)
  	{
  	  if (JUMP_LABEL (insn))
! 	    set_label_in_map (map,
! 			      CODE_LABEL_NUMBER (JUMP_LABEL (insn)),
! 			      JUMP_LABEL (insn));
  	  else if (GET_CODE (PATTERN (insn)) == ADDR_VEC
  		   || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
  	    {
*************** unroll_loop (loop_end, insn_count, loop_
*** 704,710 ****
  	      for (i = 0; i < len; i++)
  		{
  		  label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
! 		  map->label_map[CODE_LABEL_NUMBER (label)] = label;
  		}
  	    }
  	}
--- 705,713 ----
  	      for (i = 0; i < len; i++)
  		{
  		  label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
! 		  set_label_in_map (map,
! 				    CODE_LABEL_NUMBER (label),
! 				    label);
  		}
  	    }
  	}
*************** unroll_loop (loop_end, insn_count, loop_
*** 1043,1049 ****
  
  	      for (j = 0; j < max_labelno; j++)
  		if (local_label[j])
! 		  map->label_map[j] = gen_label_rtx ();
  
  	      for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; j++)
  		if (local_regno[j])
--- 1046,1052 ----
  
  	      for (j = 0; j < max_labelno; j++)
  		if (local_label[j])
! 		  set_label_in_map (map, j, gen_label_rtx ());
  
  	      for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; j++)
  		if (local_regno[j])
*************** unroll_loop (loop_end, insn_count, loop_
*** 1205,1211 ****
  
        for (j = 0; j < max_labelno; j++)
  	if (local_label[j])
! 	  map->label_map[j] = gen_label_rtx ();
  
        for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; j++)
  	if (local_regno[j])
--- 1208,1214 ----
  
        for (j = 0; j < max_labelno; j++)
  	if (local_label[j])
! 	  set_label_in_map (map, j, gen_label_rtx ());
  
        for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; j++)
  	if (local_regno[j])
*************** unroll_loop (loop_end, insn_count, loop_
*** 1222,1229 ****
  	  insn = PREV_INSN (copy_start);
  	  pattern = PATTERN (insn);
  	  
! 	  tem = map->label_map[CODE_LABEL_NUMBER
! 			       (XEXP (SET_SRC (pattern), 0))];
  	  SET_SRC (pattern) = gen_rtx (LABEL_REF, VOIDmode, tem);
  
  	  /* Set the jump label so that it can be used by later loop unrolling
--- 1225,1233 ----
  	  insn = PREV_INSN (copy_start);
  	  pattern = PATTERN (insn);
  	  
! 	  tem = get_label_from_map (map,
! 				    CODE_LABEL_NUMBER
! 				    (XEXP (SET_SRC (pattern), 0)));
  	  SET_SRC (pattern) = gen_rtx (LABEL_REF, VOIDmode, tem);
  
  	  /* Set the jump label so that it can be used by later loop unrolling
*************** copy_loop_body (copy_start, copy_end, ma
*** 1630,1639 ****
    if (! last_iteration)
      {
        final_label = gen_label_rtx ();
!       map->label_map[CODE_LABEL_NUMBER (start_label)] = final_label;
      }
    else
!     map->label_map[CODE_LABEL_NUMBER (start_label)] = start_label;
  
    start_sequence ();
    
--- 1634,1644 ----
    if (! last_iteration)
      {
        final_label = gen_label_rtx ();
!       set_label_in_map (map, CODE_LABEL_NUMBER (start_label),
! 			final_label); 
      }
    else
!     set_label_in_map (map, CODE_LABEL_NUMBER (start_label), start_label);
  
    start_sequence ();
    
*************** copy_loop_body (copy_start, copy_end, ma
*** 1918,1925 ****
  	      if (invert_exp (pattern, copy))
  		{
  		  if (! redirect_exp (&pattern,
! 				      map->label_map[CODE_LABEL_NUMBER
! 						     (JUMP_LABEL (insn))],
  				      exit_label, copy))
  		    abort ();
  		}
--- 1923,1931 ----
  	      if (invert_exp (pattern, copy))
  		{
  		  if (! redirect_exp (&pattern,
! 				      get_label_from_map (map,
! 							  CODE_LABEL_NUMBER
! 							  (JUMP_LABEL (insn))),
  				      exit_label, copy))
  		    abort ();
  		}
*************** copy_loop_body (copy_start, copy_end, ma
*** 1936,1943 ****
  		  emit_label_after (lab, jmp);
  		  LABEL_NUSES (lab) = 0;
  		  if (! redirect_exp (&pattern,
! 				      map->label_map[CODE_LABEL_NUMBER
! 						     (JUMP_LABEL (insn))],
  				      lab, copy))
  		    abort ();
  		}
--- 1942,1950 ----
  		  emit_label_after (lab, jmp);
  		  LABEL_NUSES (lab) = 0;
  		  if (! redirect_exp (&pattern,
! 				      get_label_from_map (map,
! 							  CODE_LABEL_NUMBER
! 							  (JUMP_LABEL (insn))),
  				      lab, copy))
  		    abort ();
  		}
*************** copy_loop_body (copy_start, copy_end, ma
*** 1980,1986 ****
  		     for a switch statement.  This label must have been mapped,
  		     so just use the label_map to get the new jump label.  */
  		  JUMP_LABEL (copy)
! 		    = map->label_map[CODE_LABEL_NUMBER (JUMP_LABEL (insn))];
  		}
  	  
  	      /* If this is a non-local jump, then must increase the label
--- 1987,1994 ----
  		     for a switch statement.  This label must have been mapped,
  		     so just use the label_map to get the new jump label.  */
  		  JUMP_LABEL (copy)
! 		    = get_label_from_map (map, 
! 					  CODE_LABEL_NUMBER (JUMP_LABEL (insn))); 
  		}
  	  
  	      /* If this is a non-local jump, then must increase the label
*************** copy_loop_body (copy_start, copy_end, ma
*** 2058,2064 ****
  
  	  if (insn != start_label)
  	    {
! 	      copy = emit_label (map->label_map[CODE_LABEL_NUMBER (insn)]);
  	      map->const_age++;
  	    }
  	  break;
--- 2066,2073 ----
  
  	  if (insn != start_label)
  	    {
! 	      copy = emit_label (get_label_from_map (map,
! 						     CODE_LABEL_NUMBER (insn)));
  	      map->const_age++;
  	    }
  	  break;



More information about the Gcc-bugs mailing list