Re: [PATCH 212/236] Use rtx_expr_list for expr_status.x_forced_labels

[David Malcolm <dmalcolm at redhat dot com>]

On Thu, 2014-08-07 at 13:32 +0200, Bernd Schmidt wrote:
> On 08/06/2014 07:23 PM, David Malcolm wrote:
> > diff --git a/gcc/function.h b/gcc/function.h
> > index 28a20f3..ba7597c 100644
> > --- a/gcc/function.h
> > +++ b/gcc/function.h
> > @@ -135,7 +135,7 @@ struct GTY(()) expr_status {
> >     rtx x_apply_args_value;
> >
> >     /* List of labels that must never be deleted.  */
> > -  rtx x_forced_labels;
> > +  rtx_expr_list *x_forced_labels;
> >   };
> >
> 
> As I said at the Cauldron, this sort of thing seems like the wrong thing 
> to do - when eliminating our own ancient list implementations we should 
> just go to normal C++ such as list<rtx>, or maybe even just a vec in 
> this case and some others. This applies to both expr_list and insn_list 
> - in the end we really shouldn't have either rtx_expr_list or rtx_insn_list.

Thanks.

As I see it, if we want to eliminate EXPR_LIST, INSN_LIST (and
INT_LIST?) in favor of more optimal data structures, then identifying
everywhere they're used seems to me like a good first step, and that's
one of the benefits of these patches.

These patches don't fundamentally change the data structures we're
currently using - they just make them more visible.

As an experiment, I've now tried converting forced_labels to a different
data structure: from an EXPR_LIST to a:
  vec<rtx_code_label *, va_gc> *

I'm attaching the result (I haven't bootstrapped it yet, though it does
compile and run OK on a simple testcase).

I don't know if such a change is an improvement (perhaps a set would be
better than a list, to get better than O(N) when determining if a label
is forced?), but my feeling is that the patchkit makes this kind of
experimentation *much* easier, since
it highlights where we're using EXPR_LIST, thus suggesting targets for
data structure overhauls.

Dave

commit 012a3d7ebbfed963db2a8f6f1275c451cbe25d5a
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Thu Aug 7 11:14:54 2014 -0400

    Experimentally use a vec rather than an EXPR_LIST for forced_labels
    
    gcc/
    	* function.h (struct expr_status): Convert field "x_forced_labels"
    	from rtx_expr_list * to vec<rtx_code_label *, va_gc> *.
    	(rtl_data::mark_label_as_forced): New method.
    	(rtl_data::label_forced_p): New method.
    
    	* cfgbuild.c (make_edges): Rewrite forced_labels iteration from a
    	walk down an EXPR_LIST to instead use FOR_EACH_VEC_ELT.
    	* cfgrtl.c (can_delete_label_p): Replace determination of "label"
    	being forced from using in_expr_list_p to using the new
    	rtl_data::label_forced_p method.
    	* dwarf2cfi.c (create_trace_edges): Rewrite forced_labels iteration from a
    	walk down an EXPR_LIST to instead use FOR_EACH_VEC_ELT.
    	* except.c (sjlj_emit_dispatch_table): When marking dispatch_label
    	as a forced label, replace the prepend to an EXPR_LIST logic with
    	a call to the new method rtl_data::mark_label_as_forced.
    	* function.c (rtl_data::mark_label_as_forced): New method,
    	allocating/growing a vec if necessary.
    	(rtl_data::label_forced_p): New method.  Replace linear walk
    	down a linked list with linear search through a vec.
    	* jump.c (rebuild_jump_labels_1): Update for conversion of
    	forced_labels from an EXPR_LIST to a vec.
    	* reload1.c (set_initial_label_offsets): Likewise.
    	* stmt.c (force_label_rtx): When marking "ref" as a forced label,
    	replace the prepend to an EXPR_LIST logic with a call to the new
    	method rtl_data::mark_label_as_forced, adding a checked cast to
    	rtx_code_label *.
    	(expand_label): Likewise for "label_r".

diff --git a/gcc/cfgbuild.c b/gcc/cfgbuild.c
index ab268ae..1d9e8be 100644
--- a/gcc/cfgbuild.c
+++ b/gcc/cfgbuild.c
@@ -284,8 +284,13 @@ make_edges (basic_block min, basic_block max, int update_p)
 	     everything on the forced_labels list.  */
 	  else if (computed_jump_p (insn))
 	    {
-	      for (rtx_expr_list *x = forced_labels; x; x = x->next ())
-		make_label_edge (edge_cache, bb, x->element (), EDGE_ABNORMAL);
+	      if (forced_labels)
+		{
+		  int i;
+		  rtx_code_label *forced_lab;
+		  FOR_EACH_VEC_ELT (*forced_labels, i, forced_lab)
+		    make_label_edge (edge_cache, bb, forced_lab, EDGE_ABNORMAL);
+		}
 	    }
 
 	  /* Returns create an exit out.  */
diff --git a/gcc/cfgrtl.c b/gcc/cfgrtl.c
index 5e42a97..bb053de 100644
--- a/gcc/cfgrtl.c
+++ b/gcc/cfgrtl.c
@@ -117,7 +117,7 @@ can_delete_label_p (const rtx_code_label *label)
   return (!LABEL_PRESERVE_P (label)
 	  /* User declared labels must be preserved.  */
 	  && LABEL_NAME (label) == 0
-	  && !in_expr_list_p (forced_labels, label));
+	  && !crtl->label_forced_p (label));
 }
 
 /* Delete INSN by patching it out.  */
diff --git a/gcc/dwarf2cfi.c b/gcc/dwarf2cfi.c
index 28d8ff3..55802d0 100644
--- a/gcc/dwarf2cfi.c
+++ b/gcc/dwarf2cfi.c
@@ -2309,8 +2309,13 @@ create_trace_edges (rtx_insn *insn)
 	}
       else if (computed_jump_p (insn))
 	{
-	  for (rtx_expr_list *lab = forced_labels; lab; lab = lab->next ())
-	    maybe_record_trace_start (lab->insn (), insn);
+	  if (forced_labels)
+	    {
+	      int i;
+	      rtx_code_label *forced_lab;
+	      FOR_EACH_VEC_ELT (*forced_labels, i, forced_lab)
+		maybe_record_trace_start (forced_lab, insn);
+	    }
 	}
       else if (returnjump_p (insn))
 	;
diff --git a/gcc/except.c b/gcc/except.c
index 13df541..737cd2f 100644
--- a/gcc/except.c
+++ b/gcc/except.c
@@ -1321,8 +1321,7 @@ sjlj_emit_dispatch_table (rtx_code_label *dispatch_label, int num_dispatch)
      label on the nonlocal_goto_label list.  Since we're modeling these
      CFG edges more exactly, we can use the forced_labels list instead.  */
   LABEL_PRESERVE_P (dispatch_label) = 1;
-  forced_labels
-    = gen_rtx_EXPR_LIST (VOIDmode, dispatch_label, forced_labels);
+  crtl->mark_label_as_forced (dispatch_label);
 #endif
 
   /* Load up exc_ptr and filter values from the function context.  */
diff --git a/gcc/function.c b/gcc/function.c
index 9eee7668..a027260 100644
--- a/gcc/function.c
+++ b/gcc/function.c
@@ -126,6 +126,32 @@ static void prepare_function_start (void);
 static void do_clobber_return_reg (rtx, void *);
 static void do_use_return_reg (rtx, void *);
 
+
+void
+rtl_data::mark_label_as_forced (rtx_code_label *lab)
+{
+  if (!expr.x_forced_labels)
+    vec_alloc (expr.x_forced_labels, 1);
+
+  expr.x_forced_labels->quick_push (lab);
+}
+
+bool
+rtl_data::label_forced_p (const rtx_code_label *lab) const
+{
+  int i;
+  rtx_code_label *forced_lab;
+
+  if (expr.x_forced_labels)
+    FOR_EACH_VEC_ELT (*expr.x_forced_labels, i, forced_lab)
+      if (lab == forced_lab)
+	return true;
+
+  return false;
+}
+
+
+
 /* Stack of nested functions.  */
 /* Keep track of the cfun stack.  */
 
diff --git a/gcc/function.h b/gcc/function.h
index c2e0366..38909ef 100644
--- a/gcc/function.h
+++ b/gcc/function.h
@@ -135,7 +135,7 @@ struct GTY(()) expr_status {
   rtx x_apply_args_value;
 
   /* List of labels that must never be deleted.  */
-  rtx_expr_list *x_forced_labels;
+  vec<rtx_code_label *, va_gc> *x_forced_labels;
 };
 
 typedef struct call_site_record_d *call_site_record;
@@ -460,6 +460,11 @@ struct GTY(()) rtl_data {
      to eliminable regs (like the frame pointer) are set if an asm
      sets them.  */
   HARD_REG_SET asm_clobbers;
+
+ public:
+   void mark_label_as_forced (rtx_code_label *lab);
+   bool label_forced_p (const rtx_code_label *lab) const;
+
 };
 
 #define return_label (crtl->x_return_label)
diff --git a/gcc/jump.c b/gcc/jump.c
index be6a8fd..fdaaf0e 100644
--- a/gcc/jump.c
+++ b/gcc/jump.c
@@ -74,8 +74,6 @@ static int returnjump_p_1 (rtx *, void *);
 static void
 rebuild_jump_labels_1 (rtx_insn *f, bool count_forced)
 {
-  rtx_expr_list *insn;
-
   timevar_push (TV_REBUILD_JUMP);
   init_label_info (f);
   mark_all_labels (f);
@@ -85,9 +83,14 @@ rebuild_jump_labels_1 (rtx_insn *f, bool count_forced)
      count doesn't drop to zero.  */
 
   if (count_forced)
-    for (insn = forced_labels; insn; insn = insn->next ())
-      if (LABEL_P (insn->element ()))
-	LABEL_NUSES (insn->element ())++;
+    if (forced_labels)
+      {
+	int i;
+	rtx_code_label *forced_lab;
+	FOR_EACH_VEC_ELT (*forced_labels, i, forced_lab)
+	  if (LABEL_P (forced_lab))
+	    LABEL_NUSES (forced_lab)++;
+      }
   timevar_pop (TV_REBUILD_JUMP);
 }
 
diff --git a/gcc/reload1.c b/gcc/reload1.c
index ff9d047c..04867a0 100644
--- a/gcc/reload1.c
+++ b/gcc/reload1.c
@@ -3922,11 +3922,14 @@ set_initial_eh_label_offset (rtx label)
 static void
 set_initial_label_offsets (void)
 {
+  int i;
+  rtx_code_label *lab;
   memset (offsets_known_at, 0, num_labels);
 
-  for (rtx_expr_list *x = forced_labels; x; x = x->next ())
-    if (x->element ())
-      set_label_offsets (x->element (), NULL, 1);
+  if (forced_labels)
+    FOR_EACH_VEC_ELT (*forced_labels, i, lab)
+      if (lab)
+	set_label_offsets (lab, NULL, 1);
 
   for (rtx_expr_list *x = nonlocal_goto_handler_labels; x; x = x->next ())
     if (x->element ())
diff --git a/gcc/stmt.c b/gcc/stmt.c
index af74142..508ef17 100644
--- a/gcc/stmt.c
+++ b/gcc/stmt.c
@@ -140,12 +140,13 @@ label_rtx (tree label)
 rtx
 force_label_rtx (tree label)
 {
-  rtx ref = label_rtx (label);
+  rtx_code_label *ref = as_a <rtx_code_label *> (label_rtx (label));
   tree function = decl_function_context (label);
 
   gcc_assert (function);
 
-  forced_labels = gen_rtx_EXPR_LIST (VOIDmode, ref, forced_labels);
+  crtl->mark_label_as_forced (ref);
+
   return ref;
 }
 
@@ -191,7 +192,7 @@ expand_label (tree label)
     }
 
   if (FORCED_LABEL (label))
-    forced_labels = gen_rtx_EXPR_LIST (VOIDmode, label_r, forced_labels);
+    crtl->mark_label_as_forced (as_a <rtx_code_label *> (label_r));
 
   if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
     maybe_set_first_label_num (label_r);