RFC: Add ADD_RESTRICT tree code

RFC: Add ADD_RESTRICT tree code

[Michael Matz]

Hi,

this adds a mean to retain restrict information without relying on 
restrict casts.  In the patch it's emitted by the gimplifier when it sees 
a norestrict->restrict cast (which from then on is useless), at which 
point also the tag of that restrict pointer is generated.  That's later 
used by the aliasing machinery to associate it with a restrict tag uid.

In particular it will be possible to associate pointers coming from 
different inline instance of the same function with the same restrict tag, 
and hence make them conflict.

This patch will fix the currently XFAILed tree-ssa/restrict-4.c again, as 
well as fix PR 50419.  It also still fixes the original testcase of 
PR 49279.  But it will break the checked in testcase for this bug report.  
I believe the checked in testcase is invalid as follows:

struct S { int a; int *__restrict p; };

int
foo (int *p, int *q)
{
  struct S s, *t;
  s.a = 1;
  s.p = p;       // 1
  t = wrap(&s);  // 2 t=&s in effect, but GCC doesn't see this
  t->p = q;      // 3
  s.p[0] = 0;    // 4
  t->p[0] = 1;   // 5
  return s.p[0]; // 6
}

Assignment 2 means that t->p points to s.p.  Assignment 3 changes t->p and 
s.p, but the change to s.p doesn't occur through a pointer based on t->p 
or any other restrict pointer, in fact it doesn't occur through any 
explicit initialization or assignment, but rather through in indirect 
access via a different pointer.  Hence the accesses to the same memory 
object at s.p[0] and t->p[0] were undefined because both accesses weren't 
through pointers based on each other.

I expect some bike shedding about the name of the tree code, hence only 
RFC, no Changelog or anything.  It's only ligthly tested in so far as it's 
currently in the target libs of a regstrap on x86_64-linux.


Ciao,
Michael.

Index: tree-pretty-print.c
===================================================================
*** tree-pretty-print.c	(revision 179855)
--- tree-pretty-print.c	(working copy)
*************** dump_generic_node (pretty_printer *buffe
*** 1708,1713 ****
--- 1708,1721 ----
        pp_character (buffer, '>');
        break;
  
+     case ADD_RESTRICT:
+       pp_string (buffer, "ADD_RESTRICT <");
+       dump_generic_node (buffer, TREE_OPERAND (node, 0), spc, flags, false);
+       pp_string (buffer, ", ");
+       dump_generic_node (buffer, TREE_OPERAND (node, 1), spc, flags, false);
+       pp_character (buffer, '>');
+       break;
+ 
      case ABS_EXPR:
        pp_string (buffer, "ABS_EXPR <");
        dump_generic_node (buffer, TREE_OPERAND (node, 0), spc, flags, false);
Index: expr.c
===================================================================
*** expr.c	(revision 179855)
--- expr.c	(working copy)
*************** expand_expr_real_2 (sepops ops, rtx targ
*** 7782,7787 ****
--- 7782,7790 ----
  
    switch (code)
      {
+     case ADD_RESTRICT:
+       /* We can handle add_restrict like a conversion, treeop1 will be ignored.
+          FALLTHRU.  */
      case NON_LVALUE_EXPR:
      case PAREN_EXPR:
      CASE_CONVERT:
Index: gimple-pretty-print.c
===================================================================
*** gimple-pretty-print.c	(revision 179855)
--- gimple-pretty-print.c	(working copy)
*************** dump_binary_rhs (pretty_printer *buffer,
*** 334,339 ****
--- 334,340 ----
      case COMPLEX_EXPR:
      case MIN_EXPR:
      case MAX_EXPR:
+     case ADD_RESTRICT:
      case VEC_WIDEN_MULT_HI_EXPR:
      case VEC_WIDEN_MULT_LO_EXPR:
      case VEC_PACK_TRUNC_EXPR:
Index: gimplify.c
===================================================================
*** gimplify.c	(revision 179855)
--- gimplify.c	(working copy)
*************** gimplify_modify_expr (tree *expr_p, gimp
*** 4525,4530 ****
--- 4525,4537 ----
        STRIP_USELESS_TYPE_CONVERSION (*from_p);
        if (!useless_type_conversion_p (TREE_TYPE (*to_p), TREE_TYPE (*from_p)))
  	*from_p = fold_convert_loc (loc, TREE_TYPE (*to_p), *from_p);
+       else if (POINTER_TYPE_P (TREE_TYPE (*from_p))
+ 	       && TYPE_RESTRICT (TREE_TYPE (*to_p))
+ 	       && !TYPE_RESTRICT (TREE_TYPE (*from_p)))
+ 	*from_p = fold_build2_loc (loc, ADD_RESTRICT, TREE_TYPE (*to_p),
+ 				   *from_p,
+ 				   build_int_cst (integer_type_node,
+ 						  allocate_decl_uid ()));
      }
  
    /* See if any simplifications can be done based on what the RHS is.  */
Index: tree.def
===================================================================
*** tree.def	(revision 179855)
--- tree.def	(working copy)
*************** DEFTREECODE (WITH_SIZE_EXPR, "with_size_
*** 961,966 ****
--- 961,968 ----
     generated by the builtin targetm.vectorize.mask_for_load_builtin_decl.  */
  DEFTREECODE (REALIGN_LOAD_EXPR, "realign_load", tcc_expression, 3)
  
+ DEFTREECODE (ADD_RESTRICT, "add_restrict", tcc_binary, 2)
+ 
  /* Low-level memory addressing.  Operands are BASE (address of static or
     global variable or register), OFFSET (integer constant),
     INDEX (register), STEP (integer constant), INDEX2 (register),
Index: tree-inline.c
===================================================================
*** tree-inline.c	(revision 179855)
--- tree-inline.c	(working copy)
*************** estimate_operator_cost (enum tree_code c
*** 3279,3284 ****
--- 3279,3285 ----
      case COMPLEX_EXPR:
      case PAREN_EXPR:
      case VIEW_CONVERT_EXPR:
+     case ADD_RESTRICT:
        return 0;
  
      /* Assign cost of 1 to usual operations.
Index: tree-ssa-structalias.c
===================================================================
*** tree-ssa-structalias.c	(revision 179855)
--- tree-ssa-structalias.c	(working copy)
*************** make_transitive_closure_constraints (var
*** 3602,3632 ****
  /* Temporary storage for fake var decls.  */
  struct obstack fake_var_decl_obstack;
  
! /* Build a fake VAR_DECL acting as referrer to a DECL_UID.  */
  
  static tree
! build_fake_var_decl (tree type)
  {
    tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl);
    memset (decl, 0, sizeof (struct tree_var_decl));
    TREE_SET_CODE (decl, VAR_DECL);
    TREE_TYPE (decl) = type;
!   DECL_UID (decl) = allocate_decl_uid ();
    SET_DECL_PT_UID (decl, -1);
    layout_decl (decl, 0);
    return decl;
  }
  
! /* Create a new artificial heap variable with NAME.
!    Return the created variable.  */
  
  static varinfo_t
! make_heapvar (const char *name)
  {
    varinfo_t vi;
    tree heapvar;
    
!   heapvar = build_fake_var_decl (ptr_type_node);
    DECL_EXTERNAL (heapvar) = 1;
  
    vi = new_var_info (heapvar, name);
--- 3602,3644 ----
  /* Temporary storage for fake var decls.  */
  struct obstack fake_var_decl_obstack;
  
! /* Build a fake VAR_DECL with DECL_UID being UID (which probably has
!    to be ultimately allocated by allocate_decl_uid()).  */
  
  static tree
! build_fake_var_decl_uid (tree type, int uid)
  {
    tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl);
    memset (decl, 0, sizeof (struct tree_var_decl));
    TREE_SET_CODE (decl, VAR_DECL);
    TREE_TYPE (decl) = type;
!   DECL_UID (decl) = uid;
    SET_DECL_PT_UID (decl, -1);
    layout_decl (decl, 0);
    return decl;
  }
  
! /* Build a fake VAR_DECL acting as referrer to a DECL_UID.  */
! 
! static tree
! build_fake_var_decl (tree type)
! {
!   return build_fake_var_decl_uid (type, allocate_decl_uid ());
! }
! 
! /* Create a new artificial heap variable with NAME and UID.
!    If UID is -1 allocate a new one.  Return the created variable.  */
  
  static varinfo_t
! make_heapvar (const char *name, int uid)
  {
    varinfo_t vi;
    tree heapvar;
    
!   if (uid == -1)
!     heapvar = build_fake_var_decl (ptr_type_node);
!   else
!     heapvar = build_fake_var_decl_uid (ptr_type_node, uid);
    DECL_EXTERNAL (heapvar) = 1;
  
    vi = new_var_info (heapvar, name);
*************** make_heapvar (const char *name)
*** 3642,3657 ****
    return vi;
  }
  
! /* Create a new artificial heap variable with NAME and make a
!    constraint from it to LHS.  Return the created variable.  */
  
! static varinfo_t
! make_constraint_from_heapvar (varinfo_t lhs, const char *name)
  {
!   varinfo_t vi = make_heapvar (name);
    make_constraint_from (lhs, vi->id);
! 
!   return vi;
  }
  
  /* Create a new artificial heap variable with NAME and make a
--- 3654,3673 ----
    return vi;
  }
  
! /* Create a new artificial heap variable with NAME and UID and make a
!    constraint from it to LHS.  Set flags according to a tag used
!    for tracking restrict pointers.  */
  
! static void
! make_constraint_from_restrict_uid (varinfo_t lhs, const char *name, int uid)
  {
!   varinfo_t vi;
!   vi = make_heapvar (name, uid);
    make_constraint_from (lhs, vi->id);
!   vi->is_restrict_var = 1;
!   vi->is_global_var = 0;
!   vi->is_special_var = 1;
!   vi->may_have_pointers = 0;
  }
  
  /* Create a new artificial heap variable with NAME and make a
*************** make_constraint_from_heapvar (varinfo_t
*** 3661,3672 ****
  static void
  make_constraint_from_restrict (varinfo_t lhs, const char *name)
  {
!   varinfo_t vi;
!   vi = make_constraint_from_heapvar (lhs, name);
!   vi->is_restrict_var = 1;
!   vi->is_global_var = 0;
!   vi->is_special_var = 1;
!   vi->may_have_pointers = 0;
  }
  
  /* In IPA mode there are varinfos for different aspects of reach
--- 3677,3683 ----
  static void
  make_constraint_from_restrict (varinfo_t lhs, const char *name)
  {
!   make_constraint_from_restrict_uid (lhs, name, -1);
  }
  
  /* In IPA mode there are varinfos for different aspects of reach
*************** handle_lhs_call (gimple stmt, tree lhs,
*** 3846,3852 ****
        varinfo_t vi;
        struct constraint_expr tmpc;
        rhsc = NULL;
!       vi = make_heapvar ("HEAP");
        /* We delay marking allocated storage global until we know if
           it escapes.  */
        DECL_EXTERNAL (vi->decl) = 0;
--- 3857,3863 ----
        varinfo_t vi;
        struct constraint_expr tmpc;
        rhsc = NULL;
!       vi = make_heapvar ("HEAP", -1);
        /* We delay marking allocated storage global until we know if
           it escapes.  */
        DECL_EXTERNAL (vi->decl) = 0;
*************** find_func_aliases (gimple origt)
*** 4494,4499 ****
--- 4505,4515 ----
  	  && (!in_ipa_mode
  	      || DECL_EXTERNAL (lhsop) || TREE_PUBLIC (lhsop)))
  	make_escape_constraint (rhsop);
+       /* Add the specified restrict tag.  */
+       else if (gimple_assign_rhs_code (t) == ADD_RESTRICT)
+ 	make_constraint_from_restrict_uid (get_vi_for_tree (lhsop),
+ 					   "RESTRICT_TAG",
+ 					   TREE_INT_CST_LOW (gimple_assign_rhs2 (t)));
      }
    /* Handle escapes through return.  */
    else if (gimple_code (t) == GIMPLE_RETURN
Index: tree-cfg.c
===================================================================
*** tree-cfg.c	(revision 179855)
--- tree-cfg.c	(working copy)
*************** do_pointer_plus_expr_check:
*** 3567,3572 ****
--- 3567,3587 ----
  	return false;
        }
  
+     case ADD_RESTRICT:
+       {
+ 	if (!POINTER_TYPE_P (rhs1_type)
+ 	    || !useless_type_conversion_p (lhs_type, rhs1_type)
+ 	    || !useless_type_conversion_p (integer_type_node, rhs2_type))
+ 	  {
+ 	    error ("Invalid use of add_restrict");
+ 	    debug_generic_stmt (lhs_type);
+ 	    debug_generic_stmt (rhs1_type);
+ 	    debug_generic_stmt (rhs2_type);
+ 	    return true;
+ 	  }
+ 	return false;
+       }
+ 
      case TRUTH_ANDIF_EXPR:
      case TRUTH_ORIF_EXPR:
      case TRUTH_AND_EXPR:

Re: RFC: Add ADD_RESTRICT tree code

[Jakub Jelinek]

On Wed, Oct 12, 2011 at 07:16:56PM +0200, Michael Matz wrote:
> This patch will fix the currently XFAILed tree-ssa/restrict-4.c again, as 
> well as fix PR 50419.  It also still fixes the original testcase of 
> PR 49279.  But it will break the checked in testcase for this bug report.  
> I believe the checked in testcase is invalid as follows:
> 
> struct S { int a; int *__restrict p; };
> 
> int
> foo (int *p, int *q)
> {
>   struct S s, *t;
>   s.a = 1;
>   s.p = p;       // 1
>   t = wrap(&s);  // 2 t=&s in effect, but GCC doesn't see this
>   t->p = q;      // 3
>   s.p[0] = 0;    // 4
>   t->p[0] = 1;   // 5
>   return s.p[0]; // 6
> }

I'm fairly sure this is completely valid.

> Assignment 2 means that t->p points to s.p.  Assignment 3 changes t->p and 
> s.p, but the change to s.p doesn't occur through a pointer based on t->p 
> or any other restrict pointer, in fact it doesn't occur through any 
> explicit initialization or assignment, but rather through in indirect 
> access via a different pointer.  Hence the accesses to the same memory 
> object at s.p[0] and t->p[0] were undefined because both accesses weren't 
> through pointers based on each other.

Only the field p in the structure is restrict qualified, there is no
restrict qualification on the other pointers (e.g. t is not restrict).
Thus, it is valid that t points to s.  And, s.p[0] access is based on s.p
as well as t->p and similarly t->p[0] access is based on s.p as well as
t->p, in the sense of the ISO C99 restrict wording.  Because, if you change
t->p (or s.p) at some point in between t->p = q; and s.p[0]; (i.e. prior
to the access) to point to a copy of the array, both s.p and t->p change.

"In what follows, a pointer expression E is said to be based on object P if
(at some sequence point in the execution of B prior to the evaluation of E)
modifying P to point to a copy of the array object into which it formerly
pointed would change the value of E.
Note that ‘‘based’’ is defined only for expressions with pointer types."

Which means that for memory restricts (fields in particular) we need to
limit ourselves to the cases where the field is accessed through a
restricted pointer or doesn't have address taken.

	Jakub

Re: RFC: Add ADD_RESTRICT tree code

[Michael Matz]

Hi,

On Wed, 12 Oct 2011, Jakub Jelinek wrote:

> > Assignment 2 means that t->p points to s.p.  Assignment 3 changes t->p and 
> > s.p, but the change to s.p doesn't occur through a pointer based on t->p 
> > or any other restrict pointer, in fact it doesn't occur through any 
> > explicit initialization or assignment, but rather through in indirect 
> > access via a different pointer.  Hence the accesses to the same memory 
> > object at s.p[0] and t->p[0] were undefined because both accesses weren't 
> > through pointers based on each other.
> 
> Only the field p in the structure is restrict qualified, there is no
> restrict qualification on the other pointers (e.g. t is not restrict).
> Thus, it is valid that t points to s.  And, s.p[0] access is based on s.p
> as well as t->p and similarly t->p[0] access is based on s.p as well as
> t->p, in the sense of the ISO C99 restrict wording.

IMO reading the standard to allow an access to be 
based "on s.p _as well as_ t->p" and that this should result in any 
sensible behaviour regarding restrict is interpreting too much into it.  
Let's do away with the fields, trying to capture the core of the 
disagreement.  What you seem to be saying is that this code is 
well-defined and shouldn't return 1:

int foo (int * _a, int * _b)
{
  int * restrict a = _a;
  int * restrict b = _b;
  int * restrict *pa = wrap (&a);                                       
  *pa = _b;         // 1
  *a = 0;
  **pa = 1;
  return *a;
}

I think that would go straight against the intent of restrict.  I'd read 
the standard as making the above trick undefined.

> Because, if you change t->p (or s.p) at some point in between t->p = q; 
> and s.p[0]; (i.e. prior to the access) to point to a copy of the array, 
> both s.p and t->p change.

Yes, but the question is, if the very modification of t->p was valid to 
start with.  In my example above insn 1 is a funny way to write "a = _b", 
i.e. reassigning the already set restrict pointer a to the one that also 
is already in b.  Simplifying the above then leads to:

int foo (int * _a, int * _b)
{
  int * restrict a = _a;
  int * restrict b = _b;
  a = _b;
  *a = 0;
  *b = 1;
  return *a;
}

which I think is undefined because of the fourth clause (multiple 
modifying accesses to the same underlying object X need to go through one 
particular restrict chain).

Seen from another perspective your reading would introduce an 
inconsistency with composition.  Let's assume we have this function 
available:

int tail (int * restrict a, int * restrict b) {
  *a = 0;
  *b = 1;
  return *a;
}

Clearly we can optimize this into { *a=0;*b=1;return 0; } without 
looking at the context.  Now write the testcase or my example above in 
terms of that function:

int goo (int *p, int *q)
{
  struct S s, *t;
  s.a = 1;
  s.p = p;       // 1
  t = wrap(&s);  // 2 t=&s in effect, but GCC doesn't see this
  t->p = q;      // 3
  return tail (s.p, t->p);
}

Now we get the same behaviour of returning a zero.  Something must be 
undefined here, and it's not in tail itself.  It's either the call of 
tail, the implicit modification of s.p with writes to t->p or the 
existence of two separate restrict pointers of the same value.  I think 
the production of two separate equal-value restrict pointers via 
indirect modification is the undefinedness, and _if_ the standard can be 
read in a way that this is supposed to be valid then it needs to be 
clarified to not allow that anymore.

I believe the standard should say something to the effect of disallowing 
modifying restrict pointers after they are initialized/assigned to once.


Ciao,
Michael.

Re: RFC: Add ADD_RESTRICT tree code

[Jakub Jelinek]

On Thu, Oct 13, 2011 at 01:38:44AM +0200, Michael Matz wrote:
> IMO reading the standard to allow an access to be 
> based "on s.p _as well as_ t->p" and that this should result in any 
> sensible behaviour regarding restrict is interpreting too much into it.  

No.  Because s.p and t->p designates (if the wrapper function returns
the address it was passed as the first argument, otherwise may designate)
the same object.  And the based on P relation is basing on objects,
not expressions - "expression E based on object P" in the standard.

> Let's do away with the fields, trying to capture the core of the 
> disagreement.  What you seem to be saying is that this code is 
> well-defined and shouldn't return 1:
> 
> int foo (int * _a, int * _b)
> {
>   int * restrict a = _a;
>   int * restrict b = _b;
>   int * restrict *pa = wrap (&a);                                       
>   *pa = _b;         // 1
>   *a = 0;
>   **pa = 1;
>   return *a;
> }

This is valid.  *pa and a expressions designate (if wrap returns the passed
in pointer) the same object, pa itself is not restrict, thus it is fine
if both of those expressions are used to access the object a.
The store to the restrict object (// 1) is fine, the standard has only
restrictions when you assign to the restrict pointer object a value based
on another restrict pointer (then the inner block resp. return from block
rules apply), in the above case _b is either not based on any restrict
pointer, or could be based on a restrict pointer associated with some outer
block (caller).  Both *a and **pa lvalues have (or may have) address based
on the same restricted pointer object (a).

Of course if you change the above to
int * restrict * restrict pa = wrap (&a);
the testcase would be invalid, because then accesses to a would be done
through both expression based on the restricted pointer pa and through a
directly in the same block.  So, you can disambiguate based on
int *restrict*pa or field restrict, but only if you can first disambiguate
that *pa and a is not actually the same object.  That disambiguation can
be through restrict pa or some other means (PTA/IPA-PTA usual job).

> I think that would go straight against the intent of restrict.  I'd read 
> the standard as making the above trick undefined.

Where exactly?

> > Because, if you change t->p (or s.p) at some point in between t->p = q; 
> > and s.p[0]; (i.e. prior to the access) to point to a copy of the array, 
> > both s.p and t->p change.
> 
> Yes, but the question is, if the very modification of t->p was valid to 
> start with.  In my example above insn 1 is a funny way to write "a = _b", 
> i.e. reassigning the already set restrict pointer a to the one that also 
> is already in b.  Simplifying the above then leads to:
> 
> int foo (int * _a, int * _b)
> {
>   int * restrict a = _a;
>   int * restrict b = _b;
>   a = _b;
>   *a = 0;
>   *b = 1;
>   return *a;
> }
> 
> which I think is undefined because of the fourth clause (multiple 
> modifying accesses to the same underlying object X need to go through one 
> particular restrict chain).

Yes, this one is undefined, *_b object is modified
and accessed here through lvalues based on different restrict pointer
objects (a and b).  Note that in the earlier testcase, although
you have int * restrict b = _b; there, nothing is accessed through lvalue
based on b, unlike here.

> Seen from another perspective your reading would introduce an 
> inconsistency with composition.  Let's assume we have this function 
> available:
> 
> int tail (int * restrict a, int * restrict b) {
>   *a = 0;
>   *b = 1;
>   return *a;
> }
> 
> Clearly we can optimize this into { *a=0;*b=1;return 0; } without 
> looking at the context.  Now write the testcase or my example above in 

Sure.

> terms of that function:
> 
> int goo (int *p, int *q)
> {
>   struct S s, *t;
>   s.a = 1;
>   s.p = p;       // 1
>   t = wrap(&s);  // 2 t=&s in effect, but GCC doesn't see this
>   t->p = q;      // 3
>   return tail (s.p, t->p);
> }
> 
> Now we get the same behaviour of returning a zero.  Something must be 
> undefined here, and it's not in tail itself.  It's either the call of 
> tail, the implicit modification of s.p with writes to t->p or the 
> existence of two separate restrict pointers of the same value.  I think 
> the production of two separate equal-value restrict pointers via 
> indirect modification is the undefinedness, and _if_ the standard can be 
> read in a way that this is supposed to be valid then it needs to be 
> clarified to not allow that anymore.

This is undefined, the undefined behavior happens when running the tail.
The same object X (*q) is modified and accessed through lvalue based on
restricted pointer object a as well as through lvalue based on restricted
pointer b.

> I believe the standard should say something to the effect of disallowing 
> modifying restrict pointers after they are initialized/assigned to once.

The standard doesn't say anything like that, and it would e.g. break all the
code that does:
void foo (int *restrict a, int *restrict b)
{
  int i;
  for (i = 0; i < 50; i++)
    *a++ = *b++;
}
etc.  Furthermore, field restrict would result in not being able to ever
modify the field, e.g. if you have a global object
struct S { int i; char *restrict p; } s;
then you couldn't ever set it (except for = { 3, &foo } static initializer).

So, to your patch, adding ADD_RESTRICT whenever something not TYPE_RESTRICT
is cast to TYPE_RESTRICT in the gimplifier must not include the extra casts
added in the gimplifier in order to store a pointer into a restrict pointer
memory object (field or *ptr etc.).

	Jakub

Re: RFC: Add ADD_RESTRICT tree code

[Richard Guenther]

On Thu, Oct 13, 2011 at 10:41 AM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Thu, Oct 13, 2011 at 01:38:44AM +0200, Michael Matz wrote:
>> IMO reading the standard to allow an access to be
>> based "on s.p _as well as_ t->p" and that this should result in any
>> sensible behaviour regarding restrict is interpreting too much into it.
>
> No.  Because s.p and t->p designates (if the wrapper function returns
> the address it was passed as the first argument, otherwise may designate)
> the same object.  And the based on P relation is basing on objects,
> not expressions - "expression E based on object P" in the standard.
>
>> Let's do away with the fields, trying to capture the core of the
>> disagreement.  What you seem to be saying is that this code is
>> well-defined and shouldn't return 1:
>>
>> int foo (int * _a, int * _b)
>> {
>>   int * restrict a = _a;
>>   int * restrict b = _b;
>>   int * restrict *pa = wrap (&a);
>>   *pa = _b;         // 1
>>   *a = 0;
>>   **pa = 1;
>>   return *a;
>> }
>
> This is valid.  *pa and a expressions designate (if wrap returns the passed
> in pointer) the same object, pa itself is not restrict, thus it is fine
> if both of those expressions are used to access the object a.
> The store to the restrict object (// 1) is fine, the standard has only
> restrictions when you assign to the restrict pointer object a value based
> on another restrict pointer (then the inner block resp. return from block
> rules apply), in the above case _b is either not based on any restrict
> pointer, or could be based on a restrict pointer associated with some outer
> block (caller).  Both *a and **pa lvalues have (or may have) address based
> on the same restricted pointer object (a).
>
> Of course if you change the above to
> int * restrict * restrict pa = wrap (&a);
> the testcase would be invalid, because then accesses to a would be done
> through both expression based on the restricted pointer pa and through a
> directly in the same block.  So, you can disambiguate based on
> int *restrict*pa or field restrict, but only if you can first disambiguate
> that *pa and a is not actually the same object.  That disambiguation can
> be through restrict pa or some other means (PTA/IPA-PTA usual job).
>
>> I think that would go straight against the intent of restrict.  I'd read
>> the standard as making the above trick undefined.
>
> Where exactly?
>
>> > Because, if you change t->p (or s.p) at some point in between t->p = q;
>> > and s.p[0]; (i.e. prior to the access) to point to a copy of the array,
>> > both s.p and t->p change.
>>
>> Yes, but the question is, if the very modification of t->p was valid to
>> start with.  In my example above insn 1 is a funny way to write "a = _b",
>> i.e. reassigning the already set restrict pointer a to the one that also
>> is already in b.  Simplifying the above then leads to:
>>
>> int foo (int * _a, int * _b)
>> {
>>   int * restrict a = _a;
>>   int * restrict b = _b;
>>   a = _b;
>>   *a = 0;
>>   *b = 1;
>>   return *a;
>> }
>>
>> which I think is undefined because of the fourth clause (multiple
>> modifying accesses to the same underlying object X need to go through one
>> particular restrict chain).
>
> Yes, this one is undefined, *_b object is modified
> and accessed here through lvalues based on different restrict pointer
> objects (a and b).  Note that in the earlier testcase, although
> you have int * restrict b = _b; there, nothing is accessed through lvalue
> based on b, unlike here.
>
>> Seen from another perspective your reading would introduce an
>> inconsistency with composition.  Let's assume we have this function
>> available:
>>
>> int tail (int * restrict a, int * restrict b) {
>>   *a = 0;
>>   *b = 1;
>>   return *a;
>> }
>>
>> Clearly we can optimize this into { *a=0;*b=1;return 0; } without
>> looking at the context.  Now write the testcase or my example above in
>
> Sure.
>
>> terms of that function:
>>
>> int goo (int *p, int *q)
>> {
>>   struct S s, *t;
>>   s.a = 1;
>>   s.p = p;       // 1
>>   t = wrap(&s);  // 2 t=&s in effect, but GCC doesn't see this
>>   t->p = q;      // 3
>>   return tail (s.p, t->p);
>> }
>>
>> Now we get the same behaviour of returning a zero.  Something must be
>> undefined here, and it's not in tail itself.  It's either the call of
>> tail, the implicit modification of s.p with writes to t->p or the
>> existence of two separate restrict pointers of the same value.  I think
>> the production of two separate equal-value restrict pointers via
>> indirect modification is the undefinedness, and _if_ the standard can be
>> read in a way that this is supposed to be valid then it needs to be
>> clarified to not allow that anymore.
>
> This is undefined, the undefined behavior happens when running the tail.
> The same object X (*q) is modified and accessed through lvalue based on
> restricted pointer object a as well as through lvalue based on restricted
> pointer b.
>
>> I believe the standard should say something to the effect of disallowing
>> modifying restrict pointers after they are initialized/assigned to once.
>
> The standard doesn't say anything like that, and it would e.g. break all the
> code that does:
> void foo (int *restrict a, int *restrict b)
> {
>  int i;
>  for (i = 0; i < 50; i++)
>    *a++ = *b++;
> }
> etc.  Furthermore, field restrict would result in not being able to ever
> modify the field, e.g. if you have a global object
> struct S { int i; char *restrict p; } s;
> then you couldn't ever set it (except for = { 3, &foo } static initializer).
>
> So, to your patch, adding ADD_RESTRICT whenever something not TYPE_RESTRICT
> is cast to TYPE_RESTRICT in the gimplifier must not include the extra casts
> added in the gimplifier in order to store a pointer into a restrict pointer
> memory object (field or *ptr etc.).

I suggested that for a final patch we only add ADD_RESTRICT in the
gimplifier for restrict qualified parameters, to make the inlining case
work again.  ADD_RESTRICTs for casts to restrict qualified pointers
I would add at parsing time, exactly when a literal cast to a
restrict qualified pointer from a non-restrict qualified pointer happens
in the source.  Everything else sounds too fragile IMHO.

We'd continue to handle restrict on globals from inside points-to analysis.

Thanks,
Richard.

>        Jakub
>

Re: RFC: Add ADD_RESTRICT tree code

[Jakub Jelinek]

On Thu, Oct 13, 2011 at 11:21:58AM +0200, Richard Guenther wrote:
> I suggested that for a final patch we only add ADD_RESTRICT in the
> gimplifier for restrict qualified parameters, to make the inlining case
> work again.  ADD_RESTRICTs for casts to restrict qualified pointers
> I would add at parsing time, exactly when a literal cast to a
> restrict qualified pointer from a non-restrict qualified pointer happens
> in the source.  Everything else sounds too fragile IMHO.

I'd sum up my previous mail as noting that restricted pointers are objects,
so restrict is not property of expressions.  So e.g. I don't think
we should add ADD_RESTRICT (or, at least, not an ADD_RESTRICT with different
tag) on every assignment to a restrict pointer object.
E.g. the restrict tag for cases we don't handle yet currently
(GLOBAL_RESTRICT/PARM_RESTRICT) could be based on a DECL_UID (for fields
on FIELD_DECL uid, I think we are not duplicating the fields anywhere,
for VAR_DECLs based on DECL_ABSTRACT_ORIGIN's DECL_UID?) - by based mean
map those uids using some hash table into the uids of the artificial
restrict vars or something similar.
We probably can't use restrict when we have t->p where p is restrict field
or int *restrict *q with *q directly, it would be PTA's job to find that
out.  Of course if t above is restrict too, it could be handled, as well as
int *restrict *restrict q with *q.

	Jakub

Re: RFC: Add ADD_RESTRICT tree code

[Michael Matz]

Hi,

On Thu, 13 Oct 2011, Jakub Jelinek wrote:

> I'd sum up my previous mail as noting that restricted pointers are objects,
> so restrict is not property of expressions.  So e.g. I don't think
> we should add ADD_RESTRICT (or, at least, not an ADD_RESTRICT with different
> tag) on every assignment to a restrict pointer object.

Yes, if you meant to include "from non-restrict pointer objects".

> E.g. the restrict tag for cases we don't handle yet currently
> (GLOBAL_RESTRICT/PARM_RESTRICT) could be based on a DECL_UID (for fields
> on FIELD_DECL uid, I think we are not duplicating the fields anywhere,
> for VAR_DECLs based on DECL_ABSTRACT_ORIGIN's DECL_UID?)

field_decls are shared between different variants of types.  That should 
lead only to more conflicts between restrict pointers so would be 
conservatively correct, but something to keep in mind.

> We probably can't use restrict when we have t->p where p is restrict field
> or int *restrict *q with *q directly, it would be PTA's job to find that
> out.

Right.  Your reading of the standard (and after thinking about it some 
more last night I agree that it can be read like you do, but I still think 
it's a omission and loophole in it, and goes against the intent of 
restrict which was about making it easy to disambiguate for the compiler) 
implies some IMHO severe limitations on restrict from addressable objects, 
because we can't be sure anymore if something didn't change one restrict 
pointer behind our back to some other restrict pointer making them based 
on each other and some other object:

struct S {int * restrict p;};
void foo (struct S *s, struct S *t) {
  s->p[0] = 0;
  t->p[0] = 1;  // undefined if s->p == t->p; the caller was responsible 
                // to not do that
}

but:

void foo (struct S *a, struct S *b) {
  *some_global_variable = something_else;
  a->p[0] = 0;
  b->p[0] = 1;  // here a->p == b->p can be well defined, when 
                // a == b, and some_global_variable == &a->p.
                // Due to that the caller is _not_ responsible to not
                // call with a == b.
}

I don't immediately see how we can easily disambiguate s->p[0] from 
t->p[0] while also not disambiguating a->p[0] and b->p[0].


Ciao,
Michael.

Re: RFC: Add ADD_RESTRICT tree code

[Jakub Jelinek]

On Thu, Oct 13, 2011 at 02:57:56PM +0200, Michael Matz wrote:
> struct S {int * restrict p;};
> void foo (struct S *s, struct S *t) {
>   s->p[0] = 0;
>   t->p[0] = 1;  // undefined if s->p == t->p; the caller was responsible 
>                 // to not do that

This is undefined only if s->p == t->p && &s->p != &t->p.  If both
s->p and t->p designate the same restricted pointer object,
it is fine.  It is just fine to call the above with:
  struct S u;
  u.p = p;
  foo (&u, &u);
but not with:
  struct S u, v;
  u.p = p;
  v.p = p;
  foo (&u, &v);

If you change it to
void foo (struct S *restrict s, struct S *restrict t)
then obviously even calling it with foo (&u, &u) is invalid.

	Jakub

Re: RFC: Add ADD_RESTRICT tree code

[Michael Matz]

Hi,

On Thu, 13 Oct 2011, Jakub Jelinek wrote:

> On Thu, Oct 13, 2011 at 02:57:56PM +0200, Michael Matz wrote:
> > struct S {int * restrict p;};
> > void foo (struct S *s, struct S *t) {
> >   s->p[0] = 0;
> >   t->p[0] = 1;  // undefined if s->p == t->p; the caller was responsible 
> >                 // to not do that
> 
> This is undefined only if s->p == t->p && &s->p != &t->p.  If both
> s->p and t->p designate the same restricted pointer object,
> it is fine.

Yeah.  But I continue to think that this reading is against the intent (or 
should be).  All the examples in the standard and rationale never say 
anything about pointers to restricted objects and the problematic cases 
one can construct with them, i.e. that one restricted pointer object might 
have different names.  That leads me to think that this aspect simply was 
overlooked or thought to be irrelevant.

I'm leaning towards (for C) to ignore restrict qualifications on all 
indirectly accessed or address-taken objects.  Or better not to ignore the 
restrict but make them conflict with all other pointers, restrict or 
non-restrict (normally non-restrict and restrict don't conflict in 
theory, although for GCC they do).


Ciao,
Michael.

Re: RFC: Add ADD_RESTRICT tree code

[Joseph S. Myers]

On Thu, 13 Oct 2011, Michael Matz wrote:

> Yeah.  But I continue to think that this reading is against the intent (or 
> should be).  All the examples in the standard and rationale never say 
> anything about pointers to restricted objects and the problematic cases 
> one can construct with them, i.e. that one restricted pointer object might 
> have different names.  That leads me to think that this aspect simply was 
> overlooked or thought to be irrelevant.

(Restricted) pointers to restricted objects are exactly what the sentence 
"Every access that modifies X shall be considered also to modify P, for 
the purposes of this subclause." is about.  See my annotation in 
<http://gcc.gnu.org/ml/gcc-bugs/2005-01/msg03394.html>.

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: RFC: Add ADD_RESTRICT tree code

[Richard Guenther]

On Wed, Oct 12, 2011 at 7:16 PM, Michael Matz <matz@suse.de> wrote:
> Hi,
>
> this adds a mean to retain restrict information without relying on
> restrict casts.  In the patch it's emitted by the gimplifier when it sees
> a norestrict->restrict cast (which from then on is useless), at which
> point also the tag of that restrict pointer is generated.  That's later
> used by the aliasing machinery to associate it with a restrict tag uid.
>
> In particular it will be possible to associate pointers coming from
> different inline instance of the same function with the same restrict tag,
> and hence make them conflict.
>
> This patch will fix the currently XFAILed tree-ssa/restrict-4.c again, as
> well as fix PR 50419.  It also still fixes the original testcase of
> PR 49279.  But it will break the checked in testcase for this bug report.
> I believe the checked in testcase is invalid as follows:
>
> struct S { int a; int *__restrict p; };
>
> int
> foo (int *p, int *q)
> {
>  struct S s, *t;
>  s.a = 1;
>  s.p = p;       // 1
>  t = wrap(&s);  // 2 t=&s in effect, but GCC doesn't see this
>  t->p = q;      // 3
>  s.p[0] = 0;    // 4
>  t->p[0] = 1;   // 5
>  return s.p[0]; // 6
> }
>
> Assignment 2 means that t->p points to s.p.  Assignment 3 changes t->p and
> s.p, but the change to s.p doesn't occur through a pointer based on t->p
> or any other restrict pointer, in fact it doesn't occur through any
> explicit initialization or assignment, but rather through in indirect
> access via a different pointer.  Hence the accesses to the same memory
> object at s.p[0] and t->p[0] were undefined because both accesses weren't
> through pointers based on each other.

Ick, that actually shows a bug in points-to handling (well, in
pt_solutions_same_restrict_base handling).  While we correctly
see that p escapes though wrap() and that t points to ESCAPED
we don't check in

bool
pt_solutions_same_restrict_base (struct pt_solution *pt1,
                                 struct pt_solution *pt2)
{
  /* If we deal with points-to solutions of two restrict qualified
     pointers solely rely on the pointed-to variable bitmap intersection.
     For two pointers that are based on each other the bitmaps will
     intersect.  */
  if (pt1->vars_contains_restrict
      && pt2->vars_contains_restrict)
    {
      gcc_assert (pt1->vars && pt2->vars);
      return bitmap_intersect_p (pt1->vars, pt2->vars);
    }

whether the solutions overlap in the ESCAPED bit (remember
ESCAPED contents are not expanded into the pointers pt->vars
bitmaps but just noted as the pt->escaped flag).  We ignore
pt->nonlocal as well, but that was by design ... so, re-try with

Index: tree-ssa-structalias.c
===================================================================
--- tree-ssa-structalias.c      (revision 179962)
+++ tree-ssa-structalias.c      (working copy)
@@ -6079,12 +6079,15 @@ pt_solutions_intersect_1 (struct pt_solu
     return true;

   /* If either points to unknown global memory and the other points to
-     any global memory they alias.  */
-  if ((pt1->nonlocal
-       && (pt2->nonlocal
-          || pt2->vars_contains_global))
-      || (pt2->nonlocal
-         && pt1->vars_contains_global))
+     any global memory they alias.  If both points-to sets are based
+     off a restrict qualified pointer ignore any overlaps with NONLOCAL.  */
+  if (!(pt1->vars_contains_restrict
+       && pt2->vars_contains_restrict)
+      && ((pt1->nonlocal
+          && (pt2->nonlocal
+              || pt2->vars_contains_global))
+         || (pt2->nonlocal
+             && pt1->vars_contains_global)))
     return true;

   /* Check the escaped solution if required.  */
@@ -6148,18 +6151,7 @@ bool
 pt_solutions_same_restrict_base (struct pt_solution *pt1,
                                 struct pt_solution *pt2)
 {
-  /* If we deal with points-to solutions of two restrict qualified
-     pointers solely rely on the pointed-to variable bitmap intersection.
-     For two pointers that are based on each other the bitmaps will
-     intersect.  */
-  if (pt1->vars_contains_restrict
-      && pt2->vars_contains_restrict)
-    {
-      gcc_assert (pt1->vars && pt2->vars);
-      return bitmap_intersect_p (pt1->vars, pt2->vars);
-    }
-
-  return true;
+  return pt_solutions_intersect (pt1, pt2);
 }



> I expect some bike shedding about the name of the tree code, hence only
> RFC, no Changelog or anything.  It's only ligthly tested in so far as it's
> currently in the target libs of a regstrap on x86_64-linux.
>
>
> Ciao,
> Michael.
>
> Index: tree-pretty-print.c
> ===================================================================
> *** tree-pretty-print.c (revision 179855)
> --- tree-pretty-print.c (working copy)
> *************** dump_generic_node (pretty_printer *buffe
> *** 1708,1713 ****
> --- 1708,1721 ----
>        pp_character (buffer, '>');
>        break;
>
> +     case ADD_RESTRICT:
> +       pp_string (buffer, "ADD_RESTRICT <");
> +       dump_generic_node (buffer, TREE_OPERAND (node, 0), spc, flags, false);
> +       pp_string (buffer, ", ");
> +       dump_generic_node (buffer, TREE_OPERAND (node, 1), spc, flags, false);
> +       pp_character (buffer, '>');
> +       break;
> +
>      case ABS_EXPR:
>        pp_string (buffer, "ABS_EXPR <");
>        dump_generic_node (buffer, TREE_OPERAND (node, 0), spc, flags, false);
> Index: expr.c
> ===================================================================
> *** expr.c      (revision 179855)
> --- expr.c      (working copy)
> *************** expand_expr_real_2 (sepops ops, rtx targ
> *** 7782,7787 ****
> --- 7782,7790 ----
>
>    switch (code)
>      {
> +     case ADD_RESTRICT:
> +       /* We can handle add_restrict like a conversion, treeop1 will be ignored.
> +          FALLTHRU.  */
>      case NON_LVALUE_EXPR:
>      case PAREN_EXPR:
>      CASE_CONVERT:
> Index: gimple-pretty-print.c
> ===================================================================
> *** gimple-pretty-print.c       (revision 179855)
> --- gimple-pretty-print.c       (working copy)
> *************** dump_binary_rhs (pretty_printer *buffer,
> *** 334,339 ****
> --- 334,340 ----
>      case COMPLEX_EXPR:
>      case MIN_EXPR:
>      case MAX_EXPR:
> +     case ADD_RESTRICT:
>      case VEC_WIDEN_MULT_HI_EXPR:
>      case VEC_WIDEN_MULT_LO_EXPR:
>      case VEC_PACK_TRUNC_EXPR:
> Index: gimplify.c
> ===================================================================
> *** gimplify.c  (revision 179855)
> --- gimplify.c  (working copy)
> *************** gimplify_modify_expr (tree *expr_p, gimp
> *** 4525,4530 ****
> --- 4525,4537 ----
>        STRIP_USELESS_TYPE_CONVERSION (*from_p);
>        if (!useless_type_conversion_p (TREE_TYPE (*to_p), TREE_TYPE (*from_p)))
>        *from_p = fold_convert_loc (loc, TREE_TYPE (*to_p), *from_p);
> +       else if (POINTER_TYPE_P (TREE_TYPE (*from_p))
> +              && TYPE_RESTRICT (TREE_TYPE (*to_p))
> +              && !TYPE_RESTRICT (TREE_TYPE (*from_p)))
> +       *from_p = fold_build2_loc (loc, ADD_RESTRICT, TREE_TYPE (*to_p),
> +                                  *from_p,
> +                                  build_int_cst (integer_type_node,
> +                                                 allocate_decl_uid ()));
>      }
>
>    /* See if any simplifications can be done based on what the RHS is.  */
> Index: tree.def
> ===================================================================
> *** tree.def    (revision 179855)
> --- tree.def    (working copy)
> *************** DEFTREECODE (WITH_SIZE_EXPR, "with_size_
> *** 961,966 ****
> --- 961,968 ----
>     generated by the builtin targetm.vectorize.mask_for_load_builtin_decl.  */
>  DEFTREECODE (REALIGN_LOAD_EXPR, "realign_load", tcc_expression, 3)
>
> + DEFTREECODE (ADD_RESTRICT, "add_restrict", tcc_binary, 2)
> +
>  /* Low-level memory addressing.  Operands are BASE (address of static or
>     global variable or register), OFFSET (integer constant),
>     INDEX (register), STEP (integer constant), INDEX2 (register),
> Index: tree-inline.c
> ===================================================================
> *** tree-inline.c       (revision 179855)
> --- tree-inline.c       (working copy)
> *************** estimate_operator_cost (enum tree_code c
> *** 3279,3284 ****
> --- 3279,3285 ----
>      case COMPLEX_EXPR:
>      case PAREN_EXPR:
>      case VIEW_CONVERT_EXPR:
> +     case ADD_RESTRICT:
>        return 0;
>
>      /* Assign cost of 1 to usual operations.
> Index: tree-ssa-structalias.c
> ===================================================================
> *** tree-ssa-structalias.c      (revision 179855)
> --- tree-ssa-structalias.c      (working copy)
> *************** make_transitive_closure_constraints (var
> *** 3602,3632 ****
>  /* Temporary storage for fake var decls.  */
>  struct obstack fake_var_decl_obstack;
>
> ! /* Build a fake VAR_DECL acting as referrer to a DECL_UID.  */
>
>  static tree
> ! build_fake_var_decl (tree type)
>  {
>    tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl);
>    memset (decl, 0, sizeof (struct tree_var_decl));
>    TREE_SET_CODE (decl, VAR_DECL);
>    TREE_TYPE (decl) = type;
> !   DECL_UID (decl) = allocate_decl_uid ();
>    SET_DECL_PT_UID (decl, -1);
>    layout_decl (decl, 0);
>    return decl;
>  }
>
> ! /* Create a new artificial heap variable with NAME.
> !    Return the created variable.  */
>
>  static varinfo_t
> ! make_heapvar (const char *name)
>  {
>    varinfo_t vi;
>    tree heapvar;
>
> !   heapvar = build_fake_var_decl (ptr_type_node);
>    DECL_EXTERNAL (heapvar) = 1;
>
>    vi = new_var_info (heapvar, name);
> --- 3602,3644 ----
>  /* Temporary storage for fake var decls.  */
>  struct obstack fake_var_decl_obstack;
>
> ! /* Build a fake VAR_DECL with DECL_UID being UID (which probably has
> !    to be ultimately allocated by allocate_decl_uid()).  */
>
>  static tree
> ! build_fake_var_decl_uid (tree type, int uid)
>  {
>    tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl);
>    memset (decl, 0, sizeof (struct tree_var_decl));
>    TREE_SET_CODE (decl, VAR_DECL);
>    TREE_TYPE (decl) = type;
> !   DECL_UID (decl) = uid;
>    SET_DECL_PT_UID (decl, -1);
>    layout_decl (decl, 0);
>    return decl;
>  }
>
> ! /* Build a fake VAR_DECL acting as referrer to a DECL_UID.  */
> !
> ! static tree
> ! build_fake_var_decl (tree type)
> ! {
> !   return build_fake_var_decl_uid (type, allocate_decl_uid ());
> ! }
> !
> ! /* Create a new artificial heap variable with NAME and UID.
> !    If UID is -1 allocate a new one.  Return the created variable.  */
>
>  static varinfo_t
> ! make_heapvar (const char *name, int uid)
>  {
>    varinfo_t vi;
>    tree heapvar;
>
> !   if (uid == -1)
> !     heapvar = build_fake_var_decl (ptr_type_node);
> !   else
> !     heapvar = build_fake_var_decl_uid (ptr_type_node, uid);
>    DECL_EXTERNAL (heapvar) = 1;
>
>    vi = new_var_info (heapvar, name);
> *************** make_heapvar (const char *name)
> *** 3642,3657 ****
>    return vi;
>  }
>
> ! /* Create a new artificial heap variable with NAME and make a
> !    constraint from it to LHS.  Return the created variable.  */
>
> ! static varinfo_t
> ! make_constraint_from_heapvar (varinfo_t lhs, const char *name)
>  {
> !   varinfo_t vi = make_heapvar (name);
>    make_constraint_from (lhs, vi->id);
> !
> !   return vi;
>  }
>
>  /* Create a new artificial heap variable with NAME and make a
> --- 3654,3673 ----
>    return vi;
>  }
>
> ! /* Create a new artificial heap variable with NAME and UID and make a
> !    constraint from it to LHS.  Set flags according to a tag used
> !    for tracking restrict pointers.  */
>
> ! static void
> ! make_constraint_from_restrict_uid (varinfo_t lhs, const char *name, int uid)
>  {
> !   varinfo_t vi;
> !   vi = make_heapvar (name, uid);
>    make_constraint_from (lhs, vi->id);
> !   vi->is_restrict_var = 1;
> !   vi->is_global_var = 0;
> !   vi->is_special_var = 1;
> !   vi->may_have_pointers = 0;
>  }
>
>  /* Create a new artificial heap variable with NAME and make a
> *************** make_constraint_from_heapvar (varinfo_t
> *** 3661,3672 ****
>  static void
>  make_constraint_from_restrict (varinfo_t lhs, const char *name)
>  {
> !   varinfo_t vi;
> !   vi = make_constraint_from_heapvar (lhs, name);
> !   vi->is_restrict_var = 1;
> !   vi->is_global_var = 0;
> !   vi->is_special_var = 1;
> !   vi->may_have_pointers = 0;
>  }
>
>  /* In IPA mode there are varinfos for different aspects of reach
> --- 3677,3683 ----
>  static void
>  make_constraint_from_restrict (varinfo_t lhs, const char *name)
>  {
> !   make_constraint_from_restrict_uid (lhs, name, -1);
>  }
>
>  /* In IPA mode there are varinfos for different aspects of reach
> *************** handle_lhs_call (gimple stmt, tree lhs,
> *** 3846,3852 ****
>        varinfo_t vi;
>        struct constraint_expr tmpc;
>        rhsc = NULL;
> !       vi = make_heapvar ("HEAP");
>        /* We delay marking allocated storage global until we know if
>           it escapes.  */
>        DECL_EXTERNAL (vi->decl) = 0;
> --- 3857,3863 ----
>        varinfo_t vi;
>        struct constraint_expr tmpc;
>        rhsc = NULL;
> !       vi = make_heapvar ("HEAP", -1);
>        /* We delay marking allocated storage global until we know if
>           it escapes.  */
>        DECL_EXTERNAL (vi->decl) = 0;
> *************** find_func_aliases (gimple origt)
> *** 4494,4499 ****
> --- 4505,4515 ----
>          && (!in_ipa_mode
>              || DECL_EXTERNAL (lhsop) || TREE_PUBLIC (lhsop)))
>        make_escape_constraint (rhsop);
> +       /* Add the specified restrict tag.  */
> +       else if (gimple_assign_rhs_code (t) == ADD_RESTRICT)
> +       make_constraint_from_restrict_uid (get_vi_for_tree (lhsop),
> +                                          "RESTRICT_TAG",
> +                                          TREE_INT_CST_LOW (gimple_assign_rhs2 (t)));
>      }
>    /* Handle escapes through return.  */
>    else if (gimple_code (t) == GIMPLE_RETURN
> Index: tree-cfg.c
> ===================================================================
> *** tree-cfg.c  (revision 179855)
> --- tree-cfg.c  (working copy)
> *************** do_pointer_plus_expr_check:
> *** 3567,3572 ****
> --- 3567,3587 ----
>        return false;
>        }
>
> +     case ADD_RESTRICT:
> +       {
> +       if (!POINTER_TYPE_P (rhs1_type)
> +           || !useless_type_conversion_p (lhs_type, rhs1_type)
> +           || !useless_type_conversion_p (integer_type_node, rhs2_type))
> +         {
> +           error ("Invalid use of add_restrict");
> +           debug_generic_stmt (lhs_type);
> +           debug_generic_stmt (rhs1_type);
> +           debug_generic_stmt (rhs2_type);
> +           return true;
> +         }
> +       return false;
> +       }
> +
>      case TRUTH_ANDIF_EXPR:
>      case TRUTH_ORIF_EXPR:
>      case TRUTH_AND_EXPR:
>

Re: RFC: Add ADD_RESTRICT tree code

[Tobias Burnus]

Given that GCC is again in Stage 1, I would like to bring attention to 
the following RFC patch.

To quote Richard in PR 45586:
"I believe the correct solution will involve implementing the proposal 
for introducing explicit restrict tags and using that in the fortran 
frontend (removing the restrict qualification work). See 
http://gcc.gnu.org/ml/gcc-patches/2011-10/msg01011.html. "

The RFC patch was introduced with the words:

On October 12, 2011, Michael Matz wrote:
> this adds a mean to retain restrict information without relying on
> restrict casts.  In the patch it's emitted by the gimplifier when it sees
> a norestrict->restrict cast (which from then on is useless), at which
> point also the tag of that restrict pointer is generated.  That's later
> used by the aliasing machinery to associate it with a restrict tag uid.
>
> In particular it will be possible to associate pointers coming from
> different inline instance of the same function with the same restrict tag,
> and hence make them conflict.

I think such a patch is useful for C/C++, but it seems to be also the 
best way to fix the tree-checking issues one runs into with Fortran 
code, where a derived-type ("struct") declaration contains fields which 
are allocatables ("restricted" pointers) but they loose their restricted 
property if the type is used to declare a variable with TARGET 
attribute. (For the issue in full glory, read the 93 comments in PR 
fortran/45586.)

Tobias