[RFC PATCH] restrict_based_on_field attribute

[Jakub Jelinek <jakub at redhat dot com>]

Hi!

std::vector acts roughly as something having a restrict pointer field,
i.e. two different std::vector objects will have the pointers pointing to
a different array, unfortunately unlike e.g. std::valarray we have 3
different pointers pointing into the array instead of 1, and we can't change
it without breaking the ABI.  This patch adds an extension, where several
pointer fields in the same structure can be marked as being a group for
restrict purposes (so the ISO C99 restrict wording would for them not
mandate that all accesses are made through pointers based on say _M_start,
but through pointers based on any of the fields in the group (_M_start,
_M_finish or _M_end_of_storage in the std::vector case).

With the patch (on top of the
http://gcc.gnu.org/ml/gcc-patches/2011-09/msg01605.html
patch) e.g.
void
f2 (std::vector<int> &__restrict a, std::vector<int> &__restrict b, std::vector<int> &__restrict c, int z)
{
  int i;
  for (i = 0; i < z; i++)
    {
      a[i] = b[i] + c[i];
      a[i] += b[i] * c[i];
    }
}
can be vectorized without any runtime overlap tests.

The patch is still incomplete, I haven't added docs, nor testcases
and haven't tweaked expected line numbers in 4
23_containers/vector/requirements/dr438 libstdc++-v3 tests, but
has been otherwise bootstrapped/regtested on x86_64-linux and i686-linux.

If you have ideas for a better attribute name, etc., please let me know.

2011-10-03  Jakub Jelinek  <jakub@redhat.com>

	* c-decl.c (finish_struct): Call finish_restrict_based_on_field.
	* tree-ssa-structalias.c (NO_RESTRICT_ID): Define.
	(struct variable_info): Add restrict_id field.
	(new_var_info): Initialize it.
	(make_constraint_from_restrict): Change return type to varinfo_t,
	return vi.
	(struct restrict_id_struct): New type.
	(make_constraint_from_restrict_id): New function.
	(struct fieldoff): Add restrict_id field.
	(push_fields_onto_fieldstack): Add restrictstack argument,
	initialize restrict_id fields, handle fields with
	restrict_based_on_field attribute.
	(create_variable_info_for_1): Adjust caller, initialize
	restrict_id fields.
	(create_variable_info_for, intra_create_variable_infos): Call
	make_constraint_from_restrict_id instead of
	make_constraint_from_restrict where appropriate.
gcc/cp/
	* class.c (finish_struct_1): Call finish_restrict_based_on_field.
gcc/c-family/
	* c-common.h (finish_restrict_based_on_field): New prototype.
	* c-common.c (handle_restrict_based_on_field_attribute,
	finish_restrict_based_on_field): New functions.
	(c_common_attribute_table): Add restrict_based_on_field attribute.
	(attribute_takes_identifier_p): Return true for
	restrict_based_on_field attribute.
libstdc++-v3/
	* include/bits/stl_vector.h (struct _Vector_impl): Add
	__restrict_based_on_field__ attributes to _M_start, _M_finish
	and _M_end_of_storage.

--- gcc/c-decl.c.jj	2011-10-03 14:27:47.000000000 +0200
+++ gcc/c-decl.c	2011-10-03 15:20:53.000000000 +0200
@@ -7198,6 +7198,8 @@ finish_struct (location_t loc, tree t, t
       }
   }
 
+  finish_restrict_based_on_field (t);
+
   for (x = TYPE_MAIN_VARIANT (t); x; x = TYPE_NEXT_VARIANT (x))
     {
       TYPE_FIELDS (x) = TYPE_FIELDS (t);
--- gcc/cp/class.c.jj	2011-10-03 14:27:49.000000000 +0200
+++ gcc/cp/class.c	2011-10-03 15:20:53.000000000 +0200
@@ -5811,6 +5811,8 @@ finish_struct_1 (tree t)
   /* Build the VTT for T.  */
   build_vtt (t);
 
+  finish_restrict_based_on_field (t);
+
   /* This warning does not make sense for Java classes, since they
      cannot have destructors.  */
   if (!TYPE_FOR_JAVA (t) && warn_nonvdtor && TYPE_POLYMORPHIC_P (t))
--- gcc/c-family/c-common.h.jj	2011-10-03 14:27:48.000000000 +0200
+++ gcc/c-family/c-common.h	2011-10-03 15:20:53.000000000 +0200
@@ -544,6 +544,7 @@ extern tree build_indirect_ref (location
 
 extern int c_expand_decl (tree);
 
+extern void finish_restrict_based_on_field (tree);
 extern int field_decl_cmp (const void *, const void *);
 extern void resort_sorted_fields (void *, void *, gt_pointer_operator,
 				  void *);
--- gcc/c-family/c-common.c.jj	2011-10-03 14:27:47.000000000 +0200
+++ gcc/c-family/c-common.c	2011-10-03 15:20:53.000000000 +0200
@@ -373,6 +373,8 @@ static tree handle_alloc_size_attribute 
 static tree handle_target_attribute (tree *, tree, tree, int, bool *);
 static tree handle_optimize_attribute (tree *, tree, tree, int, bool *);
 static tree handle_no_split_stack_attribute (tree *, tree, tree, int, bool *);
+static tree handle_restrict_based_on_field_attribute (tree *, tree, tree,
+						      int, bool *);
 static tree handle_fnspec_attribute (tree *, tree, tree, int, bool *);
 
 static void check_function_nonnull (tree, int, tree *);
@@ -704,6 +706,9 @@ const struct attribute_spec c_common_att
 			      handle_optimize_attribute, false },
   { "no_split_stack",	      0, 0, true,  false, false,
 			      handle_no_split_stack_attribute, false },
+  { "restrict_based_on_field",1, 1, true,  false, false,
+			      handle_restrict_based_on_field_attribute,
+			      false },
   /* For internal use (marking of builtins and runtime functions) only.
      The name contains space to prevent its usage in source code.  */
   { "fn spec",	 	      1, 1, false, true, true,
@@ -5790,7 +5795,8 @@ attribute_takes_identifier_p (const_tree
     return true;
   else if (!strcmp ("mode", spec->name)
 	   || !strcmp ("format", spec->name)
-	   || !strcmp ("cleanup", spec->name))
+	   || !strcmp ("cleanup", spec->name)
+	   || !strcmp ("restrict_based_on_field", spec->name))
     return true;
   else
     return targetm.attribute_takes_identifier_p (attr_id);
@@ -6286,6 +6292,33 @@ handle_transparent_union_attribute (tree
   return NULL_TREE;
 }
 
+/* Handle a "restrict_based_on_field" attribute; arguments as in
+   struct attribute_spec.handler.  */
+
+static tree
+handle_restrict_based_on_field_attribute (tree *node, tree name, tree args,
+					  int ARG_UNUSED (flags),
+					  bool *no_add_attrs)
+{
+  if (TREE_CODE (*node) == FIELD_DECL)
+    {
+      /* Do nothing else, just set the attribute.  We'll get at
+	 it later with lookup_attribute.  */
+      if (TREE_CODE (TREE_VALUE (args)) != IDENTIFIER_NODE)
+	{
+	  warning (OPT_Wattributes, "invalid argument to %qE attribute", name);
+	  *no_add_attrs = true;
+	}
+    }
+  else
+    {
+      warning (OPT_Wattributes, "%qE attribute ignored", name);
+      *no_add_attrs = true;
+    }
+
+  return NULL_TREE;
+}
+
 /* Subroutine of handle_{con,de}structor_attribute.  Evaluate ARGS to
    get the requested priority for a constructor or destructor,
    possibly issuing diagnostics for invalid or reserved
@@ -9919,4 +9952,132 @@ c_common_init_ts (void)
   MARK_TS_TYPED (EXCESS_PRECISION_EXPR);
 }
 
+/* Finalize restrict_based_on_field attributes in a structure.  */
+
+void
+finish_restrict_based_on_field (tree type)
+{
+  tree fld;
+  bool any_attrs_seen = false;
+  VEC(tree,heap) *self_flds = NULL;
+
+  for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
+    if (TREE_CODE (fld) == FIELD_DECL)
+      {
+	tree attr = lookup_attribute ("restrict_based_on_field",
+				      DECL_ATTRIBUTES (fld));
+	if (attr == NULL_TREE)
+	  continue;
+
+	if (DECL_NAME (fld) == NULL_TREE)
+	  {
+	    warning_at (DECL_SOURCE_LOCATION (fld), OPT_Wattributes,
+			"%qE attribute ignored on nameless fields",
+			TREE_PURPOSE (attr));
+	    DECL_ATTRIBUTES (fld)
+	      = remove_attribute ("restrict_based_on_field",
+				  DECL_ATTRIBUTES (fld));
+	  }
+
+	any_attrs_seen = true;
+	if (TREE_CODE (TREE_VALUE (TREE_VALUE (attr)))
+	    != IDENTIFIER_NODE)
+	  {
+	    gcc_assert (DECL_P (TREE_VALUE (TREE_VALUE (attr)))
+			&& DECL_NAME (TREE_VALUE (TREE_VALUE (attr)))
+			   != NULL_TREE);
+	    TREE_VALUE (TREE_VALUE (attr))
+	      = DECL_NAME (TREE_VALUE (TREE_VALUE (attr)));
+	    gcc_assert (TREE_CODE (TREE_VALUE (TREE_VALUE (attr)))
+			== IDENTIFIER_NODE);
+	  }
+	if (DECL_NAME (fld) == TREE_VALUE (TREE_VALUE (attr)))
+	  VEC_safe_push (tree, heap, self_flds, fld);
+      }
+  if (!any_attrs_seen)
+    return;
+
+  if (VEC_length (tree, self_flds) > 15)
+    VEC_qsort (tree, self_flds, field_decl_cmp);
+
+  for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
+    if (TREE_CODE (fld) == FIELD_DECL)
+      {
+	unsigned int i;
+	tree bfld = NULL_TREE, tem, id;
+	tree attr = lookup_attribute ("restrict_based_on_field",
+				      DECL_ATTRIBUTES (fld));
+	if (attr == NULL_TREE)
+	  continue;
+
+	id = TREE_VALUE (TREE_VALUE (attr));
+	if (DECL_NAME (fld) == id)
+	  bfld = fld;
+	else if (VEC_length (tree, self_flds) > 15)
+	  {
+	    unsigned int bot, top, half;
+	    tree *field_array = VEC_address (tree, self_flds);
+
+	    tem = NULL_TREE;
+	    bot = 0;
+	    top = VEC_length (tree, self_flds);
+	    while (top - bot > 1)
+	      {
+		half = (top - bot + 1) >> 1;
+		tem = field_array[bot + half];
+		if (DECL_NAME (tem) == id)
+		  break;
+		if (DECL_NAME (tem) < id)
+		  bot += half;
+		else
+		  top = bot + half;
+	      }
+
+	    if (DECL_NAME (field_array[bot]) == id)
+	      bfld = field_array[bot];
+	    else if (DECL_NAME (tem) == id)
+	      bfld = tem;
+	  }
+	else
+	  {
+	    FOR_EACH_VEC_ELT (tree, self_flds, i, tem)
+	      if (DECL_NAME (tem) == id)
+		{
+		  bfld = tem;
+		  break;
+		}
+	  }
+
+	if (bfld == NULL_TREE)
+	  warning_at (DECL_SOURCE_LOCATION (fld), OPT_Wattributes,
+		      "%qE attribute whose argument is not "
+		      "self-referencing field ignored",
+		      TREE_PURPOSE (attr));
+	else if (!POINTER_TYPE_P (TREE_TYPE (fld))
+		 || !POINTER_TYPE_P (TREE_TYPE (bfld)))
+	  {
+	    warning_at (DECL_SOURCE_LOCATION (fld), OPT_Wattributes,
+			"%qE attribute ignored on non-pointer field",
+			TREE_PURPOSE (attr));
+	    bfld = NULL_TREE;
+	  }
+	else if (TYPE_RESTRICT (TREE_TYPE (fld))
+		 || TYPE_RESTRICT (TREE_TYPE (bfld)))
+	  {
+	    warning_at (DECL_SOURCE_LOCATION (fld), OPT_Wattributes,
+			"%qE attribute ignored on restrict pointer field",
+			TREE_PURPOSE (attr));
+	    bfld = NULL_TREE;
+	  }
+	if (bfld == NULL_TREE)
+	  DECL_ATTRIBUTES (fld)
+	    = remove_attribute ("restrict_based_on_field",
+				DECL_ATTRIBUTES (fld));
+	else
+	  TREE_VALUE (TREE_VALUE (attr)) = bfld;
+      }
+
+  VEC_free (tree, heap, self_flds);
+}
+
 #include "gt-c-family-c-common.h"
--- gcc/tree-ssa-structalias.c.jj	2011-10-03 14:28:05.000000000 +0200
+++ gcc/tree-ssa-structalias.c	2011-10-03 15:20:53.000000000 +0200
@@ -276,6 +276,11 @@ struct variable_info
   /* True if this represents a IPA function info.  */
   unsigned int is_fn_info : 1;
 
+#define NO_RESTRICT_ID 31
+  /* restrict_based_on_field attribute groups, or NO_RESTRICT_ID
+     if normal __restrict pointer.  */
+  unsigned int restrict_id : 5;
+
   /* A link to the variable for the next field in this structure.  */
   struct variable_info *next;
 
@@ -353,6 +358,7 @@ new_var_info (tree t, const char *name)
   ret->is_restrict_var = false;
   ret->may_have_pointers = true;
   ret->only_restrict_pointers = false;
+  ret->restrict_id = NO_RESTRICT_ID;
   ret->is_global_var = (t == NULL_TREE);
   ret->is_fn_info = false;
   if (t && DECL_P (t))
@@ -3658,7 +3664,7 @@ make_constraint_from_heapvar (varinfo_t 
    constraint from it to LHS.  Set flags according to a tag used
    for tracking restrict pointers.  */
 
-static void
+static varinfo_t
 make_constraint_from_restrict (varinfo_t lhs, const char *name)
 {
   varinfo_t vi;
@@ -3667,6 +3673,43 @@ make_constraint_from_restrict (varinfo_t
   vi->is_global_var = 0;
   vi->is_special_var = 1;
   vi->may_have_pointers = 0;
+  return vi;
+}
+
+/* Structure which caches make_constraint_from_restrict return values
+   for restrict_ids.  */
+
+struct restrict_id_struct
+{
+  unsigned int len;
+  varinfo_t array[NO_RESTRICT_ID];
+};
+
+/* If varinfo_t for RESTRICT_ID is already cached in RIS, use it
+   as constraint, otherwise call make_constraint_from_restrict and
+   remember it.  */
+
+static void
+make_constraint_from_restrict_id (varinfo_t lhs, const char *name,
+				  unsigned int restrict_id,
+				  struct restrict_id_struct *ris)
+{
+  if (restrict_id >= NO_RESTRICT_ID)
+    {
+      make_constraint_from_restrict (lhs, name);
+      return;
+    }
+
+  if (restrict_id >= ris->len)
+    {
+      memset (&ris->array[ris->len], '\0',
+	      (restrict_id + 1 - ris->len) * sizeof (ris->array[0]));
+      ris->len = restrict_id + 1;
+    }
+  if (ris->array[restrict_id] != NULL)
+    make_constraint_from (lhs, ris->array[restrict_id]->id);
+  else
+    ris->array[restrict_id] = make_constraint_from_restrict (lhs, name);
 }
 
 /* In IPA mode there are varinfos for different aspects of reach
@@ -4966,6 +5009,8 @@ struct fieldoff
   unsigned may_have_pointers : 1;
 
   unsigned only_restrict_pointers : 1;
+
+  unsigned restrict_id : 5;
 };
 typedef struct fieldoff fieldoff_s;
 
@@ -5061,7 +5106,8 @@ field_must_have_pointers (tree t)
 
 static bool
 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
-			     HOST_WIDE_INT offset)
+			     HOST_WIDE_INT offset,
+			     VEC(tree,heap) **restrictstack)
 {
   tree field;
   bool empty_p = true;
@@ -5085,8 +5131,8 @@ push_fields_onto_fieldstack (tree type, 
 	    || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
 	    || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
 	  push = true;
-	else if (!push_fields_onto_fieldstack
-		    (TREE_TYPE (field), fieldstack, offset + foff)
+	else if (!push_fields_onto_fieldstack (TREE_TYPE (field), fieldstack,
+					       offset + foff, restrictstack)
 		 && (DECL_SIZE (field)
 		     && !integer_zerop (DECL_SIZE (field))))
 	  /* Empty structures may have actual size, like in C++.  So
@@ -5114,6 +5160,7 @@ push_fields_onto_fieldstack (tree type, 
 		pair->must_have_pointers = false;
 		pair->may_have_pointers = false;
 		pair->only_restrict_pointers = false;
+		pair->restrict_id = NO_RESTRICT_ID;
 	      }
 
 	    if (!DECL_SIZE (field)
@@ -5146,6 +5193,34 @@ push_fields_onto_fieldstack (tree type, 
 		  = (!has_unknown_size
 		     && POINTER_TYPE_P (TREE_TYPE (field))
 		     && TYPE_RESTRICT (TREE_TYPE (field)));
+		pair->restrict_id = NO_RESTRICT_ID;
+		if (!has_unknown_size
+		    && POINTER_TYPE_P (TREE_TYPE (field))
+		    && !pair->only_restrict_pointers)
+		  {
+		    tree attr = lookup_attribute ("restrict_based_on_field",
+						  DECL_ATTRIBUTES (field));
+		    if (attr != NULL_TREE)
+		      {
+			tree fld;
+			unsigned int i;
+
+			FOR_EACH_VEC_ELT (tree, *restrictstack, i, fld)
+			  if (fld == TREE_VALUE (TREE_VALUE (attr)))
+			    break;
+			if (i == VEC_length (tree, *restrictstack))
+			  {
+			    if (i < NO_RESTRICT_ID)
+			      VEC_safe_push (tree, heap, *restrictstack,
+					     TREE_VALUE (TREE_VALUE (attr)));
+			  }
+			if (i < VEC_length (tree, *restrictstack))
+			  {
+			    pair->only_restrict_pointers = true;
+			    pair->restrict_id = i;
+			  }
+		      }
+		  }
 	      }
 	  }
 
@@ -5416,8 +5491,10 @@ create_variable_info_for_1 (tree decl, c
       fieldoff_s *fo = NULL;
       bool notokay = false;
       unsigned int i;
+      VEC(tree,heap) *restrictstack = NULL;
 
-      push_fields_onto_fieldstack (decl_type, &fieldstack, 0);
+      push_fields_onto_fieldstack (decl_type, &fieldstack, 0, &restrictstack);
+      VEC_free (tree, heap, restrictstack);
 
       for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
 	if (fo->has_unknown_size
@@ -5482,6 +5559,7 @@ create_variable_info_for_1 (tree decl, c
       newvi->fullsize = vi->fullsize;
       newvi->may_have_pointers = fo->may_have_pointers;
       newvi->only_restrict_pointers = fo->only_restrict_pointers;
+      newvi->restrict_id = fo->restrict_id;
       if (i + 1 < VEC_length (fieldoff_s, fieldstack))
 	newvi->next = new_var_info (decl, name);
     }
@@ -5496,12 +5574,14 @@ create_variable_info_for (tree decl, con
 {
   varinfo_t vi = create_variable_info_for_1 (decl, name);
   unsigned int id = vi->id;
+  struct restrict_id_struct ris;
 
   insert_vi_for_tree (decl, vi);
 
   if (TREE_CODE (decl) != VAR_DECL)
     return id;
 
+  ris.len = 0;
   /* Create initial constraints for globals.  */
   for (; vi; vi = vi->next)
     {
@@ -5510,10 +5590,12 @@ create_variable_info_for (tree decl, con
 	continue;
 
       /* Mark global restrict qualified pointers.  */
-      if ((POINTER_TYPE_P (TREE_TYPE (decl))
-	   && TYPE_RESTRICT (TREE_TYPE (decl)))
-	  || vi->only_restrict_pointers)
+      if (POINTER_TYPE_P (TREE_TYPE (decl))
+	  && TYPE_RESTRICT (TREE_TYPE (decl)))
 	make_constraint_from_restrict (vi, "GLOBAL_RESTRICT");
+      else if (vi->only_restrict_pointers)
+	make_constraint_from_restrict_id (vi, "GLOBAL_RESTRICT",
+					  vi->restrict_id, &ris);
 
       /* In non-IPA mode the initializer from nonlocal is all we need.  */
       if (!in_ipa_mode
@@ -5605,7 +5687,9 @@ intra_create_variable_infos (void)
   for (t = DECL_ARGUMENTS (current_function_decl); t; t = DECL_CHAIN (t))
     {
       varinfo_t p;
+      struct restrict_id_struct ris;
 
+      ris.len = 0;
       /* For restrict qualified pointers to objects passed by
          reference build a real representative for the pointed-to object.
 	 Treat restrict qualified references the same.  */
@@ -5631,7 +5715,8 @@ intra_create_variable_infos (void)
 	    if (vi->may_have_pointers)
 	      {
 		if (vi->only_restrict_pointers)
-		  make_constraint_from_restrict (vi, "GLOBAL_RESTRICT");
+		  make_constraint_from_restrict_id (vi, "GLOBAL_RESTRICT",
+						    vi->restrict_id, &ris);
 		make_copy_constraint (vi, nonlocal_id);
 	      }
 	  continue;
@@ -5642,7 +5727,8 @@ intra_create_variable_infos (void)
 	  if (p->may_have_pointers)
 	    make_constraint_from (p, nonlocal_id);
 	  if (p->only_restrict_pointers)
-	    make_constraint_from_restrict (p, "PARM_RESTRICT");
+	    make_constraint_from_restrict_id (p, "PARM_RESTRICT",
+					      p->restrict_id, &ris);
 	}
       if (POINTER_TYPE_P (TREE_TYPE (t))
 	  && TYPE_RESTRICT (TREE_TYPE (t)))
--- libstdc++-v3/include/bits/stl_vector.h.jj	2011-08-18 08:36:12.000000000 +0200
+++ libstdc++-v3/include/bits/stl_vector.h	2011-10-03 15:45:26.000000000 +0200
@@ -77,9 +77,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       struct _Vector_impl 
       : public _Tp_alloc_type
       {
-	pointer _M_start;
-	pointer _M_finish;
-	pointer _M_end_of_storage;
+	/* These pointers act like restricted pointers, except that there
+	   are 3 pointers pointing into the same array instead of just one.
+	   That is, if any part of the array pointed by _M_start is
+	   modified, it can be accessed through either pointers based
+	   on the _M_start field, or based on the _M_finish field, or
+	   _M_end_of_storage field.  */
+	pointer _M_start
+	  __attribute__((__restrict_based_on_field__ (_M_start)));
+	pointer _M_finish
+	  __attribute__((__restrict_based_on_field__ (_M_start)));
+	pointer _M_end_of_storage
+	  __attribute__((__restrict_based_on_field__ (_M_start)));
 
 	_Vector_impl()
 	: _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0)

	Jakub