dynamic stack space allocation optimization

["David S. Miller" <davem at jenolan dot rutgers dot edu>]

There is a hideous hassle on SETJMP_VIA_SAVE_AREA targets due how
setjmp() happens to be implemented on them, some sparc flavors are a
good example.

The issue is that the allocated stack frame space, once used, can
write over the stack frame areas which a later longjmp() will unwind
to, causing crashes.  The solution in the current tree is to allocate
not only the space needed, but also enough space for another frame, to
avoid this problem.

This is obviously very inefficient since 9 times out of ten a function
calls alloca() and does not use setjmp() at all.

Mon Sep 22 18:29:55 1997  David S. Miller  <davem@tanya.rutgers.edu>

	* explow.c (optimize_save_area_alloca): New function for targets
	where SETJMP_VIA_SAVE_AREA is true.
	(allocate_dynamic_stack_space): On SETJMP_VIA_SAVE_AREA targets,
	compute the amount of stack space needed should we find later on
	that setjmp() is never called by this function, stuff rtl for this
	inside a REG_NOTE of the final SET of stack_pointer_rtx.
	rtl.h (enum reg_note): New note type REG_SAVE_AREA.
	toplev.c (rest_of_compilation): If SETJMP_VIA_SAVE_AREA and
	current_function_calls_alloca, call optimize_save_area_alloca().

--- rtl.h.~1~	Sun Sep 21 20:49:28 1997
+++ rtl.h	Mon Sep 22 18:25:04 1997
@@ -307,7 +307,9 @@
    probability that this call won't return.
      REG_EXEC_COUNT is attached to the first insn of each basic block, and
    the first insn after each CALL_INSN.  It indicates how many times this
-   block was executed.  */
+   block was executed.
+     REG_SAVE_AREA is used to optimize rtl generated by dynamic stack
+   allocations for targets where SETJMP_VIA_SAVE_AREA is true.  */
 
 #define REG_NOTES(INSN)	((INSN)->fld[6].rtx)
 
@@ -317,7 +319,7 @@
 		REG_NONNEG = 8, REG_NO_CONFLICT = 9, REG_UNUSED = 10,
 		REG_CC_SETTER = 11, REG_CC_USER = 12, REG_LABEL = 13,
 		REG_DEP_ANTI = 14, REG_DEP_OUTPUT = 15, REG_BR_PROB = 16,
-		REG_EXEC_COUNT = 17, REG_NOALIAS = 18 };
+		REG_EXEC_COUNT = 17, REG_NOALIAS = 18, REG_SAVE_AREA = 19 };
 /* The base value for branch probability notes.  */
 #define REG_BR_PROB_BASE  10000
 
--- explow.c.~1~	Mon Aug 11 11:57:06 1997
+++ explow.c	Mon Sep 22 19:06:25 1997
@@ -978,6 +978,79 @@
     emit_insn (fcn (stack_pointer_rtx, sa));
 }
 
+#ifdef SETJMP_VIA_SAVE_AREA
+/* Optimize RTL generated by allocate_dynamic_stack_space for targets
+   where SETJMP_VIA_SAVE_AREA is true.  The problem is that on these
+   platforms, the dynamic stack space used can corrupt the original
+   frame, thus causing a crash if a longjmp() unwinds to it.  */
+
+void
+optimize_save_area_alloca (insns)
+     rtx insns;
+{
+  rtx insn;
+
+  for (insn = insns; insn; insn = NEXT_INSN(insn))
+    {
+      rtx note;
+
+      if (GET_CODE (insn) != INSN)
+	continue;
+
+      for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
+	{
+	  if (REG_NOTE_KIND (note) != REG_SAVE_AREA)
+	    continue;
+
+	  if (!current_function_calls_setjmp)
+	    {
+	      rtx pat = PATTERN (insn);
+
+	      /* If we do not see the note in a pattern matching
+		 these precise characteristics, we did something
+		 entirely wrong in allocate_dynamic_stack_space().  */
+	      if (GET_CODE (pat) != SET
+		  || SET_DEST (pat) != stack_pointer_rtx
+		  || GET_CODE (SET_SRC (pat)) != MINUS
+		  || XEXP (SET_SRC (pat), 0) != stack_pointer_rtx)
+		abort();
+
+	      /* This will now be transformed into a (set REG REG)
+		 so we can just blow away all the other notes.  */
+	      XEXP (SET_SRC (pat), 1) = XEXP (note, 0);
+	      REG_NOTES (insn) = NULL_RTX;
+	    }
+	  else
+	    {
+	      /* setjmp() was called, we must remove the REG_SAVE_AREA
+		 note so that later passes do not get confused by its
+		 presence.  */
+	      if (note == REG_NOTES (insn))
+		{
+		  REG_NOTES (insn) = XEXP (note, 1);
+		}
+	      else
+		{
+		  rtx srch;
+
+		  for (srch = REG_NOTES (insn); srch; srch = XEXP (srch, 1))
+		    if (XEXP (srch, 1) == note)
+		      break;
+
+		  if (srch == NULL_RTX)
+		    abort();
+
+		  XEXP (srch, 1) = XEXP (note, 1);
+		}
+	    }
+	  /* Once we've seen the note of interest, we need not look at
+	     the rest of them.  */
+	  break;
+	}
+    }
+}
+#endif /* SETJMP_VIA_SAVE_AREA */
+
 /* Return an rtx representing the address of an area of memory dynamically
    pushed on the stack.  This region of memory is always aligned to
    a multiple of BIGGEST_ALIGNMENT.
@@ -995,6 +1068,10 @@
      rtx target;
      int known_align;
 {
+#ifdef SETJMP_VIA_SAVE_AREA
+  rtx setjmpless_size = NULL_RTX;
+#endif
+
   /* If we're asking for zero bytes, it doesn't matter what we point
      to since we can't dereference it.  But return a reasonable
      address anyway.  */
@@ -1048,6 +1125,45 @@
     rtx dynamic_offset
       = expand_binop (Pmode, sub_optab, virtual_stack_dynamic_rtx,
 		      stack_pointer_rtx, NULL_RTX, 1, OPTAB_LIB_WIDEN);
+
+    if (!current_function_calls_setjmp)
+      {
+	int align = STACK_BOUNDARY / BITS_PER_UNIT;
+
+	/* See optimize_save_area_alloca() to understand what is being
+	   set up here.  */
+
+#if !defined(STACK_BOUNDARY) || !defined(MUST_ALIGN) || (STACK_BOUNDARY != BIGGEST_ALIGNMENT)
+	/* If anyone creates a target with these characteristics, let them
+	   know that our optimization cannot work correctly in such a case.  */
+	abort();
+#endif
+
+	if (GET_CODE (size) == CONST_INT)
+	  {
+	    int new = INTVAL (size) / align * align;
+
+	    if (INTVAL (size) != new)
+	      setjmpless_size = GEN_INT (new);
+	    else
+	      setjmpless_size = size;
+	  }
+	else
+	  {
+	    /* Since we know overflow is not possible, we avoid using
+	       CEIL_DIV_EXPR and use TRUNC_DIV_EXPR instead.  */
+	    setjmpless_size = expand_divmod (0, TRUNC_DIV_EXPR, Pmode, size,
+					     GEN_INT (align), NULL_RTX, 1);
+	    setjmpless_size = expand_mult (Pmode, setjmpless_size,
+					   GEN_INT (align), NULL_RTX, 1);
+	  }
+	/* Our optimization works based upon being able to perform a simple
+	   transformation of this RTL into a (set REG REG) so make sure things
+	   did in fact end up in a REG.  */
+	if (!arith_operand (setjmpless_size, Pmode))
+	  setjmpless_size = force_reg (Pmode, setjmpless_size);
+      }
+
     size = expand_binop (Pmode, add_optab, size, dynamic_offset,
 			 NULL_RTX, 1, OPTAB_LIB_WIDEN);
   }
@@ -1117,6 +1233,15 @@
     {
       size = convert_modes (Pmode, ptr_mode, size, 1);
       anti_adjust_stack (size);
+#ifdef SETJMP_VIA_SAVE_AREA
+      if (setjmpless_size != NULL_RTX)
+	{
+	  rtx note_target = get_last_insn ();
+
+	  REG_NOTES (note_target) = gen_rtx (EXPR_LIST, REG_SAVE_AREA,
+					     setjmpless_size, REG_NOTES (note_target));
+	}
+#endif /* SETJMP_VIA_SAVE_AREA */
     }
 
 #ifdef STACK_GROWS_DOWNWARD
--- toplev.c.~1~	Mon Sep 15 22:07:28 1997
+++ toplev.c	Mon Sep 22 18:28:26 1997
@@ -3152,6 +3152,12 @@
 
   unshare_all_rtl (insns);
 
+#ifdef SETJMP_VIA_SAVE_AREA
+  /* This must be performed before virutal register instantiation.  */
+  if (current_function_calls_alloca)
+    optimize_save_area_alloca (insns);
+#endif
+
   /* Instantiate all virtual registers.  */
 
   instantiate_virtual_regs (current_function_decl, get_insns ());