non-local goto optimization

[Nathan Sidwell <nathan at codesourcery dot com>]

This patch improves non-local goto code generation to not spill unnecessary 
registers.  This primarily improves SJLJ exception targets (eg vxworks) with 
lots of caller-save registers (eg Power & MIPS).  It will also improve functions 
with non-local gotos from nested functions.

The observation is that with sjlj exceptions we save all the caller-save 
registers in a function that has an exception receiver.  We need to do this 
because we must preserve those caller-save registers should we catch an 
exception and return normally.

However, we only need to save those registers when we do return normally after 
catching the exception.  If we always rethrow the exception (in a cleanup for 
example), there is no need for us to preserve the caller save registers because 
we don't restore them along that path.

This bites C++ code like
void Foo ()
{
	X x; // has a dtor
	... do something from whence an exception may propagate
}

A cleanup is inserted to run x's destructor, that cleanup always rethrows.

This optimization adds a has_nonexceptional_receiver flag to the function data 
structure.  This is set whenever there's a non-local label that can return normally.

This optimization walks the bb graph marking all the blocks that have a 
non-exceptional path to the exit block.  These are all the blocks that may 
return normally.  We then walk the blocks again and check whether any block 
marked in the first walk has an exceptional incoming edge.  If so, we know we 
have an exception receiver with a normal return.  Otherwise we have none. Thanks 
to Richard Sandiford for suggesting this approach, rather than a front-end hack.

Reload is changed to check the has_nonexceptional_receiver rather than the 
has_nonlocal_label flag to determine whether caller-saves should be spilled.

Finally, builtin_unwind_init sets has_nonexceptional_receiver rather than 
has_nonlocal_label to initialize the unwinding state.

I could not repurpose has_nonlocal_label, because it appeared to have other uses.

The new optimization is between life and combine, but could be pretty much 
anywhere in the RTL passes.

This patch has been tested on mips-vxworks and i86-linux.

ok?
--
Nathan Sidwell    ::   http://www.codesourcery.com   ::         CodeSourcery
nathan@codesourcery.com    ::     http://www.planetfall.pwp.blueyonder.co.uk

2007-04-23  Nathan Sidwell  <nathan@codesourcery.com>

	* tree-pass.h (pass_nonexceptional_receiver): Declare.
	* flow.c (has_nonexceptional_receiver,
	rest_of_handle_nonexceptional_reciever,
	pass_nonexceptional_receiver): New.
	* function.h (struct function): Add has_nonexceptional_receiver.
	(current_function_has_nonexceptional_receiver): Define.
	* except.c (expand_builtin_unwind_init): Set
	current_function_has_nonexceptional_receiver.
	* passes.c (init_optimization_passes): Add
	pass_nonexceptional_receiver.
	* reload1.c (reload): Check
	current_function_has_nonexceptional_receiver not
	current_function_has_nonlocal_label for saving caller saves.

Index: tree-pass.h
===================================================================
--- tree-pass.h	(revision 123987)
+++ tree-pass.h	(working copy)
@@ -380,6 +380,7 @@ extern struct tree_opt_pass pass_remove_
 extern struct tree_opt_pass pass_postreload_cse;
 extern struct tree_opt_pass pass_gcse2;
 extern struct tree_opt_pass pass_flow2;
+extern struct tree_opt_pass pass_nonexceptional_receiver;
 extern struct tree_opt_pass pass_stack_adjustments;
 extern struct tree_opt_pass pass_peephole2;
 extern struct tree_opt_pass pass_if_after_reload;
Index: flow.c
===================================================================
--- flow.c	(revision 123987)
+++ flow.c	(working copy)
@@ -4778,3 +4778,88 @@ struct tree_opt_pass pass_flow2 =
   'w'                                   /* letter */
 };
 
+/* Determine if the current function has an exception receiver block
+   that reaches the exit block via non-exceptional edges  */
+
+static bool
+has_nonexceptional_receiver (void)
+{
+  edge e;
+  edge_iterator ei;
+  basic_block *tos, *worklist, bb;
+
+  /* If we're not optimizing, then just err on the safe side.  */
+  if (!optimize)
+    return true;
+  
+  /* First determine which blocks can reach exit via normal paths.  */
+  tos = worklist = xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
+
+  FOR_EACH_BB (bb)
+    bb->flags &= ~BB_REACHABLE;
+
+  /* Place the exit block on our worklist.  */
+  EXIT_BLOCK_PTR->flags |= BB_REACHABLE;
+  *tos++ = EXIT_BLOCK_PTR;
+  
+  /* Iterate: find everything reachable from what we've already seen.  */
+  while (tos != worklist)
+    {
+      bb = *--tos;
+
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	if (!(e->flags & EDGE_ABNORMAL))
+	  {
+	    basic_block src = e->src;
+
+	    if (!(src->flags & BB_REACHABLE))
+	      {
+		src->flags |= BB_REACHABLE;
+		*tos++ = src;
+	      }
+	  }
+    }
+  free (worklist);
+
+  /* Now see if there's a reachable block with an exceptional incoming
+     edge.  */
+  FOR_EACH_BB (bb)
+    if (bb->flags & BB_REACHABLE)
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	if (e->flags & EDGE_ABNORMAL)
+	  return true;
+
+  /* No exceptional block reached exit unexceptionally.  */
+  return false;
+}
+
+static unsigned
+rest_of_handle_nonexceptional_receiver (void)
+{
+  /* If we have no receivers, then we can't have a non-exceptional
+     one.  */
+  if (!current_function_has_nonlocal_label)
+    return 0;
+
+  current_function_has_nonexceptional_receiver
+    = has_nonexceptional_receiver ();
+  return 0;
+}
+
+struct tree_opt_pass pass_nonexceptional_receiver =
+{
+  "ner",                                /* name */
+  NULL,                                 /* gate */
+  rest_of_handle_nonexceptional_receiver, /* execute */
+  NULL,                                 /* sub */
+  NULL,                                 /* next */
+  0,                                    /* static_pass_number */
+  0,         				/* tv_id */
+  0,                                    /* properties_required */
+  0,                                    /* properties_provided */
+  0,                                    /* properties_destroyed */
+  TODO_verify_flow,                     /* todo_flags_start */
+  0,                                    /* todo_flags_finish */
+  0                                     /* letter */
+};
+
Index: function.h
===================================================================
--- function.h	(revision 123987)
+++ function.h	(working copy)
@@ -406,6 +406,10 @@ struct function GTY(())
      from nested functions.  */
   unsigned int has_nonlocal_label : 1;
 
+  /* Nonzero if function has non-local label which reaches exit block
+     via non-exceptional route.  */
+  unsigned int has_nonexceptional_receiver : 1;
+  
   /* Nonzero if function being compiled has nonlocal gotos to parent
      function.  */
   unsigned int has_nonlocal_goto : 1;
@@ -523,6 +527,8 @@ extern int trampolines_created;
 #define current_function_uses_const_pool (cfun->uses_const_pool)
 #define current_function_epilogue_delay_list (cfun->epilogue_delay_list)
 #define current_function_has_nonlocal_label (cfun->has_nonlocal_label)
+#define current_function_has_nonexceptional_receiver \
+	(cfun->has_nonexceptional_receiver)
 #define current_function_has_nonlocal_goto (cfun->has_nonlocal_goto)
 
 #define return_label (cfun->x_return_label)
Index: except.c
===================================================================
--- except.c	(revision 123987)
+++ except.c	(working copy)
@@ -2859,7 +2859,7 @@ expand_builtin_unwind_init (void)
 {
   /* Set this so all the registers get saved in our frame; we need to be
      able to copy the saved values for any registers from frames we unwind.  */
-  current_function_has_nonlocal_label = 1;
+  current_function_has_nonexceptional_receiver = 1;
 
 #ifdef SETUP_FRAME_ADDRESSES
   SETUP_FRAME_ADDRESSES ();
Index: passes.c
===================================================================
--- passes.c	(revision 123987)
+++ passes.c	(working copy)
@@ -687,6 +687,7 @@ init_optimization_passes (void)
       NEXT_PASS (pass_rtl_fwprop_addr);
       NEXT_PASS (pass_outof_cfg_layout_mode);
       NEXT_PASS (pass_life);
+      NEXT_PASS (pass_nonexceptional_receiver);
       NEXT_PASS (pass_combine);
       NEXT_PASS (pass_if_after_combine);
       NEXT_PASS (pass_partition_blocks);
Index: reload1.c
===================================================================
--- reload1.c	(revision 123987)
+++ reload1.c	(working copy)
@@ -688,9 +688,10 @@ reload (rtx first, int global)
   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
     mark_home_live (i);
 
-  /* A function that receives a nonlocal goto must save all call-saved
+  /* A function that has a nonlocal label that can reach the exit
+     block via non-exceptional paths must save all call-saved
      registers.  */
-  if (current_function_has_nonlocal_label)
+  if (current_function_has_nonexceptional_receiver)
     for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
       if (! call_used_regs[i] && ! fixed_regs[i] && ! LOCAL_REGNO (i))
 	regs_ever_live[i] = 1;