Patch to reduce stack sizes

Patch to reduce stack sizes

[Bernd Schmidt]

[-- Attachment #1: Type: text/plain, Size: 954 bytes --]

I've noticed every now and then while working on optimizations that when
code generation is only slightly changed, the size of the stack frame
can vary by more than one would expect.  I decided to find out why, and
found the problem in reload.

In reload's main loop, we align the stack frame in every iteration, so
something like the following sequence can happen:
  spill a register to a new 4-byte stack slot
  align the stack to 16 bytes
  spill another 4-byte register
  align the stack to 16 bytes again
which ends up wasting huge amounts of stack space.

The following patch fixes it; assign_stack_local now keeps track of
unused areas in the stack frame and tries to use them first.  In many
cases on i686, this can reduce stack frames by 16 bytes or sometimes
more.  Testing on ARM also showed some improvement.

Bootstrapped and regression tested on i686-linux, also bootstrapped on
ia64-linux (as a !FRAME_GROWS_DOWNWARD target).  Ok?


Bernd

[-- Attachment #2: savestack-v4.diff --]
[-- Type: text/plain, Size: 10558 bytes --]

	* function.c (try_fit_stack_local, add_frame_space): New static
	functions.
	(assign_stack_local_1): Use them.  Look for opportunities to use
	space previously wasted on alignment.
	* function.h (struct frame_space): New.
	(struct rtl_data): Add FRAME_SPACE_LIST member.
	* reload1.c (something_was_spilled): New static variable.
	(alter_reg): Set it.
	(reload): Test it in addition to testing if the frame size changed.

Index: function.c
===================================================================
--- function.c	(revision 158639)
+++ function.c	(working copy)
@@ -278,6 +278,75 @@ get_stack_local_alignment (tree type, en
   return STACK_SLOT_ALIGNMENT (type, mode, alignment);
 }
 
+/* Determine whether it is possible to fit a stack slot of size SIZE and
+   alignment ALIGNMENT into an area in the stack frame that starts at
+   frame offset START and has a length of LENGTH.  If so, store the frame
+   offset to be used for the stack slot in *POFFSET and return true;
+   return false otherwise.  This function will extend the frame size when
+   given a start/length pair that lies at the end of the frame.  */
+
+static bool
+try_fit_stack_local (HOST_WIDE_INT start, HOST_WIDE_INT length,
+		     HOST_WIDE_INT size, unsigned int alignment,
+		     HOST_WIDE_INT *poffset)
+{
+  HOST_WIDE_INT this_frame_offset;
+  int frame_off, frame_alignment, frame_phase;
+
+  /* Calculate how many bytes the start of local variables is off from
+     stack alignment.  */
+  frame_alignment = PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT;
+  frame_off = STARTING_FRAME_OFFSET % frame_alignment;
+  frame_phase = frame_off ? frame_alignment - frame_off : 0;
+
+  /* Round the frame offset to the specified alignment.  */
+
+  /*  We must be careful here, since FRAME_OFFSET might be negative and
+      division with a negative dividend isn't as well defined as we might
+      like.  So we instead assume that ALIGNMENT is a power of two and
+      use logical operations which are unambiguous.  */
+  if (FRAME_GROWS_DOWNWARD)
+    this_frame_offset
+      = (FLOOR_ROUND (start + length - size - frame_phase,
+		      (unsigned HOST_WIDE_INT) alignment)
+	 + frame_phase);
+  else
+    this_frame_offset
+      = (CEIL_ROUND (start - frame_phase,
+		     (unsigned HOST_WIDE_INT) alignment)
+	 + frame_phase);
+
+  /* See if it fits.  If this space is at the edge of the frame,
+     consider extending the frame to make it fit.  Our caller relies on
+     this when allocating a new slot.  */
+  if (frame_offset == start && this_frame_offset < frame_offset)
+    frame_offset = this_frame_offset;
+  else if (this_frame_offset < start)
+    return false;
+  else if (start + length == frame_offset
+	   && this_frame_offset + size > start + length)
+    frame_offset = this_frame_offset + size;
+  else if (this_frame_offset + size > start + length)
+    return false;
+
+  *poffset = this_frame_offset;
+  return true;
+}
+
+/* Create a new frame_space structure describing free space in the stack
+   frame beginning at START and ending at END, and chain it into the
+   function's frame_space_list.  */
+
+static void
+add_frame_space (HOST_WIDE_INT start, HOST_WIDE_INT end)
+{
+  struct frame_space *space = GGC_NEW (struct frame_space);
+  space->next = crtl->frame_space_list;
+  crtl->frame_space_list = space;
+  space->start = start;
+  space->length = end - start;
+}
+
 /* Allocate a stack slot of SIZE bytes and return a MEM rtx for it
    with machine mode MODE.
 
@@ -298,8 +367,8 @@ assign_stack_local_1 (enum machine_mode 
 {
   rtx x, addr;
   int bigend_correction = 0;
+  HOST_WIDE_INT slot_offset, old_frame_offset;
   unsigned int alignment, alignment_in_bits;
-  int frame_off, frame_alignment, frame_phase;
 
   if (align == 0)
     {
@@ -318,9 +387,6 @@ assign_stack_local_1 (enum machine_mode 
 
   alignment_in_bits = alignment * BITS_PER_UNIT;
 
-  if (FRAME_GROWS_DOWNWARD)
-    frame_offset -= size;
-
   /* Ignore alignment if it exceeds MAX_SUPPORTED_STACK_ALIGNMENT.  */
   if (alignment_in_bits > MAX_SUPPORTED_STACK_ALIGNMENT)
     {
@@ -363,35 +429,55 @@ assign_stack_local_1 (enum machine_mode 
   if (crtl->max_used_stack_slot_alignment < alignment_in_bits)
     crtl->max_used_stack_slot_alignment = alignment_in_bits;
 
-  /* Calculate how many bytes the start of local variables is off from
-     stack alignment.  */
-  frame_alignment = PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT;
-  frame_off = STARTING_FRAME_OFFSET % frame_alignment;
-  frame_phase = frame_off ? frame_alignment - frame_off : 0;
+  if (mode != BLKmode || size != 0)
+    {
+      struct frame_space **psp;
 
-  /* Round the frame offset to the specified alignment.  The default is
-     to always honor requests to align the stack but a port may choose to
-     do its own stack alignment by defining STACK_ALIGNMENT_NEEDED.  */
-  if (STACK_ALIGNMENT_NEEDED
-      || mode != BLKmode
-      || size != 0)
+      for (psp = &crtl->frame_space_list; *psp; psp = &(*psp)->next)
+	{
+	  struct frame_space *space = *psp;
+	  if (!try_fit_stack_local (space->start, space->length, size,
+				    alignment, &slot_offset))
+	    continue;
+	  *psp = space->next;
+	  if (slot_offset > space->start)
+	    add_frame_space (space->start, slot_offset);
+	  if (slot_offset + size < space->start + space->length)
+	    add_frame_space (slot_offset + size,
+			     space->start + space->length);
+	  goto found_space;
+	}
+    }
+  else if (!STACK_ALIGNMENT_NEEDED)
     {
-      /*  We must be careful here, since FRAME_OFFSET might be negative and
-	  division with a negative dividend isn't as well defined as we might
-	  like.  So we instead assume that ALIGNMENT is a power of two and
-	  use logical operations which are unambiguous.  */
-      if (FRAME_GROWS_DOWNWARD)
-	frame_offset
-	  = (FLOOR_ROUND (frame_offset - frame_phase,
-			  (unsigned HOST_WIDE_INT) alignment)
-	     + frame_phase);
-      else
-	frame_offset
-	  = (CEIL_ROUND (frame_offset - frame_phase,
-			 (unsigned HOST_WIDE_INT) alignment)
-	     + frame_phase);
+      slot_offset = frame_offset;
+      goto found_space;
     }
 
+  old_frame_offset = frame_offset;
+
+  if (FRAME_GROWS_DOWNWARD)
+    {
+      frame_offset -= size;
+      try_fit_stack_local (frame_offset, size, size, alignment, &slot_offset);
+
+      if (slot_offset > frame_offset)
+	add_frame_space (frame_offset, slot_offset);
+      if (slot_offset + size < old_frame_offset)
+	add_frame_space (slot_offset + size, old_frame_offset);
+    }
+  else
+    {
+      frame_offset += size;
+      try_fit_stack_local (old_frame_offset, size, size, alignment, &slot_offset);
+
+      if (slot_offset > old_frame_offset)
+	add_frame_space (old_frame_offset, slot_offset);
+      if (slot_offset + size < frame_offset)
+	add_frame_space (slot_offset + size, frame_offset);
+    }
+
+ found_space:
   /* On a big-endian machine, if we are allocating more space than we will use,
      use the least significant bytes of those that are allocated.  */
   if (BYTES_BIG_ENDIAN && mode != BLKmode && GET_MODE_SIZE (mode) < size)
@@ -402,17 +488,14 @@ assign_stack_local_1 (enum machine_mode 
   if (virtuals_instantiated)
     addr = plus_constant (frame_pointer_rtx,
 			  trunc_int_for_mode
-			  (frame_offset + bigend_correction
+			  (slot_offset + bigend_correction
 			   + STARTING_FRAME_OFFSET, Pmode));
   else
     addr = plus_constant (virtual_stack_vars_rtx,
 			  trunc_int_for_mode
-			  (frame_offset + bigend_correction,
+			  (slot_offset + bigend_correction,
 			   Pmode));
 
-  if (!FRAME_GROWS_DOWNWARD)
-    frame_offset += size;
-
   x = gen_rtx_MEM (mode, addr);
   set_mem_align (x, alignment_in_bits);
   MEM_NOTRAP_P (x) = 1;
Index: function.h
===================================================================
--- function.h	(revision 158639)
+++ function.h	(working copy)
@@ -242,6 +242,17 @@ struct GTY(()) function_subsections {
   const char *unlikely_text_section_name;
 };
 
+/* Describe an empty area of space in the stack frame.  These can be chained
+   into a list; this is used to keep track of space wasted for alignment
+   reasons.  */
+struct GTY(()) frame_space
+{
+  struct frame_space *next;
+
+  HOST_WIDE_INT start;
+  HOST_WIDE_INT length;
+};
+
 /* Datastructures maintained for currently processed function in RTL form.  */
 struct GTY(()) rtl_data {
   struct expr_status expr;
@@ -289,6 +300,9 @@ struct GTY(()) rtl_data {
      Made for the sake of unshare_all_rtl.  */
   rtx x_stack_slot_list;
 
+  /* List of empty areas in the stack frame.  */
+  struct frame_space *frame_space_list;
+
   /* Place after which to insert the tail_recursion_label if we need one.  */
   rtx x_stack_check_probe_note;
 
Index: reload1.c
===================================================================
--- reload1.c	(revision 158639)
+++ reload1.c	(working copy)
@@ -702,6 +702,8 @@ has_nonexceptional_receiver (void)
 static int something_needs_elimination;
 /* Set during calculate_needs if an insn needs an operand changed.  */
 static int something_needs_operands_changed;
+/* Set by alter_regs if we spilled a register to the stack.  */
+static bool something_was_spilled;
 
 /* Nonzero means we couldn't get enough spill regs.  */
 static int failure;
@@ -981,6 +983,7 @@ reload (rtx first, int global)
       HOST_WIDE_INT starting_frame_size;
 
       starting_frame_size = get_frame_size ();
+      something_was_spilled = false;
 
       set_initial_elim_offsets ();
       set_initial_label_offsets ();
@@ -1046,7 +1049,7 @@ reload (rtx first, int global)
 	setup_save_areas ();
 
       /* If we allocated another stack slot, redo elimination bookkeeping.  */
-      if (starting_frame_size != get_frame_size ())
+      if (something_was_spilled || starting_frame_size != get_frame_size ())
 	continue;
       if (starting_frame_size && crtl->stack_alignment_needed)
 	{
@@ -1084,7 +1087,7 @@ reload (rtx first, int global)
 
       /* If we allocated any new memory locations, make another pass
 	 since it might have changed elimination offsets.  */
-      if (starting_frame_size != get_frame_size ())
+      if (something_was_spilled || starting_frame_size != get_frame_size ())
 	something_changed = 1;
 
       /* Even if the frame size remained the same, we might still have
@@ -2223,6 +2226,8 @@ alter_reg (int i, int from_reg, bool don
       unsigned int min_align = reg_max_ref_width[i] * BITS_PER_UNIT;
       int adjust = 0;
 
+      something_was_spilled = true;
+
       if (ira_conflicts_p)
 	{
 	  /* Mark the spill for IRA.  */

Re: Patch to reduce stack sizes

[Jeff Law]

On 05/06/10 18:22, Bernd Schmidt wrote:
> I've noticed every now and then while working on optimizations that when
> code generation is only slightly changed, the size of the stack frame
> can vary by more than one would expect.  I decided to find out why, and
> found the problem in reload.
>
> In reload's main loop, we align the stack frame in every iteration, so
> something like the following sequence can happen:
>    spill a register to a new 4-byte stack slot
>    align the stack to 16 bytes
>    spill another 4-byte register
>    align the stack to 16 bytes again
> which ends up wasting huge amounts of stack space.
>
> The following patch fixes it; assign_stack_local now keeps track of
> unused areas in the stack frame and tries to use them first.  In many
> cases on i686, this can reduce stack frames by 16 bytes or sometimes
> more.  Testing on ARM also showed some improvement.
>
> Bootstrapped and regression tested on i686-linux, also bootstrapped on
> ia64-linux (as a !FRAME_GROWS_DOWNWARD target).  Ok?
>    
Haven't looked at the patch yet, but I will say YIPPIE!  I noticed this 
a while back and it annoyed me, but I didn't fix it at the time.  I 
think there's some PRs in bugzilla related to this issue.

jeff

Re: Patch to reduce stack sizes

[Jeff Law]

On 05/06/10 18:22, Bernd Schmidt wrote:
> I've noticed every now and then while working on optimizations that when
> code generation is only slightly changed, the size of the stack frame
> can vary by more than one would expect.  I decided to find out why, and
> found the problem in reload.
>
> In reload's main loop, we align the stack frame in every iteration, so
> something like the following sequence can happen:
>    spill a register to a new 4-byte stack slot
>    align the stack to 16 bytes
>    spill another 4-byte register
>    align the stack to 16 bytes again
> which ends up wasting huge amounts of stack space.
>
> The following patch fixes it; assign_stack_local now keeps track of
> unused areas in the stack frame and tries to use them first.  In many
> cases on i686, this can reduce stack frames by 16 bytes or sometimes
> more.  Testing on ARM also showed some improvement.
>
> Bootstrapped and regression tested on i686-linux, also bootstrapped on
> ia64-linux (as a !FRAME_GROWS_DOWNWARD target).  Ok?
>    
I couldn't absolutely convince myself that the !FRAME_GROWS_DOWNWARD 
case was correct, nor could I convince myself it was incorrect.  I'll 
trust that in the unlikely event something proves problematical that 
you'll take care of it promptly.

Approved,

Jeff

Re: Patch to reduce stack sizes

[Bernd Schmidt]

On 05/11/2010 06:57 AM, Jeff Law wrote:

> I couldn't absolutely convince myself that the !FRAME_GROWS_DOWNWARD
> case was correct, nor could I convince myself it was incorrect.  I'll
> trust that in the unlikely event something proves problematical that
> you'll take care of it promptly.
> 
> Approved,

Thanks, committed.  Anything in particular you felt uneasy about?


Bernd

Re: Patch to reduce stack sizes

[Jeff Law]

On 05/17/10 05:17, Bernd Schmidt wrote:
> On 05/11/2010 06:57 AM, Jeff Law wrote:
>
>    
>> I couldn't absolutely convince myself that the !FRAME_GROWS_DOWNWARD
>> case was correct, nor could I convince myself it was incorrect.  I'll
>> trust that in the unlikely event something proves problematical that
>> you'll take care of it promptly.
>>
>> Approved,
>>      
> Thanks, committed.  Anything in particular you felt uneasy about?
>    
I was primarily worried about the offset calculations; for some reason 
reading that code always makes my head hurt.  Given that it bootstrapped 
on ia64, I'm not terribly worried.

THanks,
Jeff

Re: Patch to reduce stack sizes

[Sebastian Pop]

Hi,

On Mon, May 17, 2010 at 10:11, Jeff Law <law@redhat.com> wrote:
> On 05/17/10 05:17, Bernd Schmidt wrote:
>>
>> On 05/11/2010 06:57 AM, Jeff Law wrote:
>>
>>
>>>
>>> I couldn't absolutely convince myself that the !FRAME_GROWS_DOWNWARD
>>> case was correct, nor could I convince myself it was incorrect.  I'll
>>> trust that in the unlikely event something proves problematical that
>>> you'll take care of it promptly.
>>>
>>> Approved,
>>>
>>
>> Thanks, committed.  Anything in particular you felt uneasy about?
>>
>
> I was primarily worried about the offset calculations; for some reason
> reading that code always makes my head hurt.  Given that it bootstrapped on
> ia64, I'm not terribly worried.
>

With this patch bootstrap fails at -O3 with:
../../gcc/function.c:466:23: error: ‘slot_offset’ may be used
uninitialized in this function [-Werror=uninitialized]

This patch solves the problem:

diff --git a/gcc/function.c b/gcc/function.c
index 5d0e7e5..2c87dec 100644
--- a/gcc/function.c
+++ b/gcc/function.c
@@ -367,7 +367,7 @@ assign_stack_local_1 (enum machine_mode mode,
HOST_WIDE_INT size,
 {
   rtx x, addr;
   int bigend_correction = 0;
-  HOST_WIDE_INT slot_offset, old_frame_offset;
+  HOST_WIDE_INT slot_offset = 0, old_frame_offset;
   unsigned int alignment, alignment_in_bits;

   if (align == 0)

Re: Patch to reduce stack sizes

[Jeff Law]

On 05/23/10 22:15, Sebastian Pop wrote:
> Hi,
>
> On Mon, May 17, 2010 at 10:11, Jeff Law<law@redhat.com>  wrote:
>    
>> On 05/17/10 05:17, Bernd Schmidt wrote:
>>      
>>> On 05/11/2010 06:57 AM, Jeff Law wrote:
>>>
>>>
>>>        
>>>> I couldn't absolutely convince myself that the !FRAME_GROWS_DOWNWARD
>>>> case was correct, nor could I convince myself it was incorrect.  I'll
>>>> trust that in the unlikely event something proves problematical that
>>>> you'll take care of it promptly.
>>>>
>>>> Approved,
>>>>
>>>>          
>>> Thanks, committed.  Anything in particular you felt uneasy about?
>>>
>>>        
>> I was primarily worried about the offset calculations; for some reason
>> reading that code always makes my head hurt.  Given that it bootstrapped on
>> ia64, I'm not terribly worried.
>>
>>      
> With this patch bootstrap fails at -O3 with:
> ../../gcc/function.c:466:23: error: ‘slot_offset’ may be used
> uninitialized in this function [-Werror=uninitialized]
>
> This patch solves the problem:
>
> diff --git a/gcc/function.c b/gcc/function.c
> index 5d0e7e5..2c87dec 100644
> --- a/gcc/function.c
> +++ b/gcc/function.c
> @@ -367,7 +367,7 @@ assign_stack_local_1 (enum machine_mode mode,
> HOST_WIDE_INT size,
>   {
>     rtx x, addr;
>     int bigend_correction = 0;
> -  HOST_WIDE_INT slot_offset, old_frame_offset;
> +  HOST_WIDE_INT slot_offset = 0, old_frame_offset;
>     unsigned int alignment, alignment_in_bits;
>    
I'm assuming the path where slot_offset is used without being 
initialized is the case where we did not find a suitable hole 
pre-existing in the stack and the call to try_fit_stack_local later 
returns false in this code (thus slot_offset doesn't get initialized?)



   if (FRAME_GROWS_DOWNWARD)
     {
       frame_offset -= size;
       try_fit_stack_local (frame_offset, size, size, alignment, 
&slot_offset);

       if (slot_offset > frame_offset)
         add_frame_space (frame_offset, slot_offset);
       if (slot_offset + size < old_frame_offset)
         add_frame_space (slot_offset + size, old_frame_offset);
     }
   else
     {
       frame_offset += size;
       try_fit_stack_local (old_frame_offset, size, size, alignment, 
&slot_offset);

       if (slot_offset > old_frame_offset)
         add_frame_space (old_frame_offset, slot_offset);
       if (slot_offset + size < frame_offset)
         add_frame_space (slot_offset + size, frame_offset);
     }

Or is there another execution path that's causing the problem?

Jeff

Re: Patch to reduce stack sizes

[Sebastian Pop]

On Mon, May 24, 2010 at 11:18, Jeff Law <law@redhat.com> wrote:
> Or is there another execution path that's causing the problem?

I think that at -O3 the function try_fit_stack_local gets inlined, and
that initializes poffset only at the very bottom, and other cases that
return false do not initialize it.  I think that explains why at -O2 it
does not triggers the uninitialized variable warning.

Sebastian

Re: Patch to reduce stack sizes

[Jeff Law]

On 05/24/10 12:05, Sebastian Pop wrote:
> On Mon, May 24, 2010 at 11:18, Jeff Law<law@redhat.com>  wrote:
>    
>> Or is there another execution path that's causing the problem?
>>      
> I think that at -O3 the function try_fit_stack_local gets inlined, and
> that initializes poffset only at the very bottom, and other cases that
> return false do not initialize it.  I think that explains why at -O2 it
> does not triggers the uninitialized variable warning.
>    
Right.  And thus what should be the behaviour of the two callers that 
don't check the return value of try_fit_stack_local when it return 
false?  Or are we sure it can never return false from those calls?

jeff

Re: Patch to reduce stack sizes

[Bernd Schmidt]

On 05/24/2010 08:15 PM, Jeff Law wrote:
> On 05/24/10 12:05, Sebastian Pop wrote:
>> On Mon, May 24, 2010 at 11:18, Jeff Law<law@redhat.com>  wrote:
>>   
>>> Or is there another execution path that's causing the problem?
>>>      
>> I think that at -O3 the function try_fit_stack_local gets inlined, and
>> that initializes poffset only at the very bottom, and other cases that
>> return false do not initialize it.  I think that explains why at -O2 it
>> does not triggers the uninitialized variable warning.
>>    
> Right.  And thus what should be the behaviour of the two callers that
> don't check the return value of try_fit_stack_local when it return
> false?  Or are we sure it can never return false from those calls?

The last two?  It's designed so that try_fit_stack_local must always
succeed when we get there.


Bernd

Re: Patch to reduce stack sizes

[Jeff Law]

On 05/24/10 13:48, Bernd Schmidt wrote:
> On 05/24/2010 08:15 PM, Jeff Law wrote:
>    
>> On 05/24/10 12:05, Sebastian Pop wrote:
>>      
>>> On Mon, May 24, 2010 at 11:18, Jeff Law<law@redhat.com>   wrote:
>>>
>>>        
>>>> Or is there another execution path that's causing the problem?
>>>>
>>>>          
>>> I think that at -O3 the function try_fit_stack_local gets inlined, and
>>> that initializes poffset only at the very bottom, and other cases that
>>> return false do not initialize it.  I think that explains why at -O2 it
>>> does not triggers the uninitialized variable warning.
>>>
>>>        
>> Right.  And thus what should be the behaviour of the two callers that
>> don't check the return value of try_fit_stack_local when it return
>> false?  Or are we sure it can never return false from those calls?
>>      
> The last two?  It's designed so that try_fit_stack_local must always
> succeed when we get there.
>    
OK.  Then the trivial initialization to zero should be safe.    Thanks 
for the confirmation about the behaviour of try_fit_stack_local.

Sebastian -- consider your patch approved.

Thanks,
Jeff

Re: Patch to reduce stack sizes

[Sebastian Pop]

On Mon, May 24, 2010 at 16:03, Jeff Law <law@redhat.com> wrote:
> Sebastian -- consider your patch approved.
>

Committed to trunk as r159797.

Sebastian