[dax@gurulabs.com: PATCH: `__norestrict' type qualifier (fwd)]

[dax@gurulabs.com: PATCH: `__norestrict' type qualifier (fwd)]

[Richard Stallman]

The proposal below looks like a good idea to me, at least in
principle.  This would give people a straightforward and reliable
solution to use when they get the new warning that we are discussing.

Since this really is a new feature, we have to judge it as one; it
needs to be clear to document, and reliable to use.  I don't know
whether this feature can be described and implemented reliably, but I
think that should be possible.  "Apply the same rules that apply to
char *" seems like a clear basis for the specification; and as long as
GCC reliably implements the ISO C aliasing rules for char *, it should
be able to implement this with equal reliability.

The other change I've proposed, to keep many cases of old code working
for now, remains a good idea even if this new feature is added.
They complement each other.


------- Start of forwarded message -------
Date: Sat, 11 Sep 1999 01:15:58 -0600 (MDT)
From: Dax Kelson <dax@gurulabs.com>
X-Sender: dkelson@ultra1.inconnect.com
To: jbuck@synopsys.COM
cc: rms@gnu.org
Subject: PATCH: `__norestrict' type qualifier (fwd)
Content-Type: TEXT/PLAIN; charset=US-ASCII
Content-Length: 10202


Isn't this post from July relevent to the current alias dicussion?

Dax Kelson

- ---------- Forwarded message ----------
Date: 17 Jul 1999 15:26:14 -0400
From: Patrick J. LoPresti <patl@cag.lcs.mit.edu>
To: egcs@egcs.cygnus.com
Cc: torvalds@transmeta.com
Subject: PATCH: `__norestrict' type qualifier

Just in time for 2.95!

OK, maybe not.

The following patch adds support for a "__norestrict" type qualifier.
It is used to mark a pointer type as potentially aliasing all of
memory.  For example:

  *(unsigned int *__norestrict)p ^= ~0;

...flips the 32 (or 64) bits pointed at by p, no matter what type p
has.

The rationale for this is straightforward; it is a logical extension
of the "char *" exception for type aliasing.  Obviously (?) the ISO
folks realized that people use char * to access raw memory, so they
allowed char * to alias anything.  The problem is that nobody who
cares about performance uses char * for this purpose on modern
machines; they use a pointer to something with the "natural" word size
of the architecture.

Lots of code (especially in the Linux kernel) is written this way, and
it is not easy to rewrite using unions or macros (according to the
maintainers).  The `__norestrict' keyword makes it easy to convert
such code so that it can work in the presence of type-based alias
analysis.

Two notes:

  1) This is not well-tested, although it seems to work.  Many thanks
     to the author (Mark Mitchell?) of the current alias analysis
     support.  That well-commented and well-structured code made this
     extension fairly trivial, even for a GCC neophyte like me.

  2) I have not even glanced at the other front ends (e.g., C++), so
     there may be some additional work needed there to get this
     finished.  I am willing to do that work, but I didn't want to
     spend any more time on something which the GCC maintainers might
     reject out-of-hand...

 - Pat

======================================================================

diff -u -r gcc-orig/c-aux-info.c gcc/c-aux-info.c
- --- gcc-orig/c-aux-info.c	Sat Apr 17 13:14:45 1999
+++ gcc/c-aux-info.c	Sat Jul 17 14:17:25 1999
@@ -524,6 +524,8 @@
     ret_val = concat ("volatile ", ret_val, NULL_PTR);
   if (TYPE_RESTRICT (t))
     ret_val = concat ("restrict ", ret_val, NULL_PTR);
+  if (TYPE_NORESTRICT (t))
+    ret_val = concat ("__norestrict ", ret_val, NULL_PTR);
   return ret_val;
 }
 
diff -u -r gcc-orig/c-common.c gcc/c-common.c
- --- gcc-orig/c-common.c	Tue Apr 13 17:04:06 1999
+++ gcc/c-common.c	Sat Jul 17 14:17:23 1999
@@ -2980,12 +2980,12 @@
      values, so even though it should be illegal to use `restrict'
      with such an entity we don't flag that here.  Thus, special case
      code for that case is required in the C++ front-end.  */
- -  if ((type_quals & TYPE_QUAL_RESTRICT)
+  if ((type_quals & (TYPE_QUAL_RESTRICT | TYPE_QUAL_NORESTRICT))
       && (!POINTER_TYPE_P (type)
 	  || !C_TYPE_OBJECT_OR_INCOMPLETE_P (TREE_TYPE (type))))
     {
- -      error ("invalid use of `restrict'");
- -      type_quals &= ~TYPE_QUAL_RESTRICT;
+      error ("invalid use of `restrict' or `__norestrict'");
+      type_quals &= ~(TYPE_QUAL_RESTRICT | TYPE_QUAL_NORESTRICT);
     }
 
   if (TREE_CODE (type) == ARRAY_TYPE)
@@ -3038,6 +3038,18 @@
 				    DECL_POINTER_ALIAS_SET (decl));
 	    }
 	}
+    }
+  if (type_quals & TYPE_QUAL_NORESTRICT)
+    {
+      if (!TREE_TYPE (decl)
+	  || !POINTER_TYPE_P (TREE_TYPE (decl))
+	  || !C_TYPE_OBJECT_OR_INCOMPLETE_P (TREE_TYPE (TREE_TYPE (decl))))
+	error ("invalid use of `__norestrict'");
+      else if (flag_strict_aliasing)
+        {
+          /* Unrestricted pointers can alias anything. */
+          DECL_POINTER_ALIAS_SET (decl) = 0;
+        }
     }
 }
 
diff -u -r gcc-orig/c-decl.c gcc/c-decl.c
- --- gcc-orig/c-decl.c	Mon Apr 12 10:05:29 1999
+++ gcc/c-decl.c	Sat Jul 17 14:17:25 1999
@@ -4383,6 +4383,7 @@
   int longlong = 0;
   int constp;
   int restrictp;
+  int norestrictp;
   int volatilep;
   int type_quals = TYPE_UNQUALIFIED;
   int inlinep;
@@ -4700,19 +4701,26 @@
      declaration contains the `const'.  */
   constp = !! (specbits & 1 << (int) RID_CONST) + TYPE_READONLY (type);
   restrictp = !! (specbits & 1 << (int) RID_RESTRICT) + TYPE_RESTRICT (type);
+  norestrictp = (!! (specbits & 1 << (int) RID_NORESTRICT)
+                 + TYPE_NORESTRICT (type));
   volatilep = !! (specbits & 1 << (int) RID_VOLATILE) + TYPE_VOLATILE (type);
   inlinep = !! (specbits & (1 << (int) RID_INLINE));
   if (constp > 1)
     pedwarn ("duplicate `const'");
   if (restrictp > 1)
     pedwarn ("duplicate `restrict'");
+  if (norestrictp > 1)
+    pedwarn ("duplicate `__norestrict'");
   if (volatilep > 1)
     pedwarn ("duplicate `volatile'");
+  if (restrictp && norestrictp)
+    error ("Both `restrict' and `__norestrict' applied to same type");
   if (! flag_gen_aux_info && (TYPE_QUALS (type)))
     type = TYPE_MAIN_VARIANT (type);
   type_quals = ((constp ? TYPE_QUAL_CONST : 0)
 		| (restrictp ? TYPE_QUAL_RESTRICT : 0)
- -		| (volatilep ? TYPE_QUAL_VOLATILE : 0));
+		| (volatilep ? TYPE_QUAL_VOLATILE : 0)
+                | (norestrictp ? TYPE_QUAL_NORESTRICT : 0));
 
   /* Warn if two storage classes are given. Default to `auto'.  */
 
@@ -5075,6 +5083,8 @@
 		    volatilep++;
 		  else if (qualifier == ridpointers[(int) RID_RESTRICT])
 		    restrictp++;
+                  else if (qualifier == ridpointers[(int) RID_NORESTRICT])
+                    norestrictp++;
 		  else if (!erred)
 		    {
 		      erred = 1;
@@ -5087,10 +5097,15 @@
 		pedwarn ("duplicate `volatile'");
 	      if (restrictp > 1)
 		pedwarn ("duplicate `restrict'");
+	      if (norestrictp > 1)
+		pedwarn ("duplicate `__norestrict'");
+              if (restrictp && norestrictp)
+                error ("`restrict' and `__norestrict' applied to same type");
 
 	      type_quals = ((constp ? TYPE_QUAL_CONST : 0)
 			    | (restrictp ? TYPE_QUAL_RESTRICT : 0)
- -			    | (volatilep ? TYPE_QUAL_VOLATILE : 0));
+			    | (volatilep ? TYPE_QUAL_VOLATILE : 0)
+                            | (norestrictp ? TYPE_QUAL_NORESTRICT : 0));
 	    }
 
 	  declarator = TREE_OPERAND (declarator, 0);

diff -u -r gcc-orig/c-lex.c gcc/c-lex.c
- --- gcc-orig/c-lex.c	Sat Mar 20 14:21:23 1999
+++ gcc/c-lex.c	Sat Jul 17 14:17:24 1999
@@ -257,6 +257,7 @@
   ridpointers[(int) RID_INLINE] = get_identifier ("inline");
   ridpointers[(int) RID_CONST] = get_identifier ("const");
   ridpointers[(int) RID_RESTRICT] = get_identifier ("restrict");
+  ridpointers[(int) RID_NORESTRICT] = get_identifier ("norestrict");
   ridpointers[(int) RID_VOLATILE] = get_identifier ("volatile");
   ridpointers[(int) RID_AUTO] = get_identifier ("auto");
   ridpointers[(int) RID_STATIC] = get_identifier ("static");

diff -u -r gcc-orig/c-lex.h gcc/c-lex.h
- --- gcc-orig/c-lex.h	Thu Feb 18 15:38:39 1999
+++ gcc/c-lex.h	Sat Jul 17 14:17:24 1999
@@ -41,6 +41,7 @@
   RID_SIGNED,
   RID_CONST,
   RID_RESTRICT,
+  RID_NORESTRICT,
   RID_VOLATILE,
   RID_INLINE,
   RID_NOALIAS,

diff -u -r gcc-orig/c-parse.gperf gcc/c-parse.gperf
- --- gcc-orig/c-parse.gperf	Wed Mar 31 02:43:51 1999
+++ gcc/c-parse.gperf	Sat Jul 17 13:53:22 1999
@@ -33,6 +33,8 @@
 __iterator, SCSPEC, RID_ITERATOR
 __iterator__, SCSPEC, RID_ITERATOR
 __label__, LABEL, NORID
+__norestrict, TYPE_QUAL, RID_NORESTRICT
+__norestrict__, TYPE_QUAL, RID_NORESTRICT
 __real, REALPART, NORID
 __real__, REALPART, NORID
 __restrict, TYPE_QUAL, RID_RESTRICT

diff -u -r gcc-orig/c-parse.in gcc/c-parse.in
- --- gcc-orig/c-parse.in	Mon Apr 26 18:35:50 1999
+++ gcc/c-parse.in	Sat Jul 17 14:17:24 1999
@@ -116,7 +116,8 @@
    yylval contains an IDENTIFIER_NODE which indicates which one.  */
 %token TYPESPEC
 
- -/* Reserved words that qualify type: "const", "volatile", or "restrict".
+/* Reserved words that qualify type: "const", "volatile", "restrict",
+   or "__norestrict".
    yylval contains an IDENTIFIER_NODE which indicates which one.  */
 %token TYPE_QUAL
 
diff -u -r gcc-orig/tree.c gcc/tree.c
- --- gcc-orig/tree.c	Sat Apr 17 07:43:57 1999
+++ gcc/tree.c	Sat Jul 17 14:17:25 1999
@@ -3608,6 +3608,7 @@
   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
+  TYPE_NORESTRICT (type) = (type_quals & TYPE_QUAL_NORESTRICT) != 0;
 }
 
 /* Given a type node TYPE and a TYPE_QUALIFIER_SET, return a type for

diff -u -r gcc-orig/tree.h gcc/tree.h
- --- gcc-orig/tree.h	Sun May  2 13:43:32 1999
+++ gcc/tree.h	Sat Jul 17 14:17:26 1999
@@ -834,6 +834,9 @@
    the term.  */
 #define TYPE_RESTRICT(NODE) (TYPE_CHECK (NODE)->type.restrict_flag)
 
+/* Nonzero if type is `norestrict'-qualified. */
+#define TYPE_NORESTRICT(NODE) (TYPE_CHECK (NODE)->type.norestrict_flag)
+
 /* There is a TYPE_QUAL value for each type qualifier.  They can be
    combined by bitwise-or to form the complete set of qualifiers for a
    type.  */
@@ -842,12 +845,14 @@
 #define TYPE_QUAL_CONST    0x1
 #define TYPE_QUAL_VOLATILE 0x2
 #define TYPE_QUAL_RESTRICT 0x4
+#define TYPE_QUAL_NORESTRICT 0x8
 
 /* The set of type qualifiers for this type.  */
- -#define TYPE_QUALS(NODE)			\
- -  ((TYPE_READONLY(NODE) * TYPE_QUAL_CONST) |	\
- -   (TYPE_VOLATILE(NODE) * TYPE_QUAL_VOLATILE) |	\
- -   (TYPE_RESTRICT(NODE) * TYPE_QUAL_RESTRICT))
+#define TYPE_QUALS(NODE)			        \
+  ((TYPE_READONLY(NODE) * TYPE_QUAL_CONST) |	        \
+   (TYPE_VOLATILE(NODE) * TYPE_QUAL_VOLATILE) |	        \
+   (TYPE_RESTRICT(NODE) * TYPE_QUAL_RESTRICT) |         \
+   (TYPE_NORESTRICT(NODE) * TYPE_QUAL_NORESTRICT))
 
 /* These flags are available for each language front end to use internally.  */
 #define TYPE_LANG_FLAG_0(NODE) (TYPE_CHECK (NODE)->type.lang_flag_0)
@@ -901,6 +906,7 @@
   unsigned transparent_union_flag : 1;
   unsigned packed_flag : 1;
   unsigned restrict_flag : 1;
+  unsigned norestrict_flag : 1;
 
   unsigned lang_flag_0 : 1;
   unsigned lang_flag_1 : 1;
@@ -909,7 +915,7 @@
   unsigned lang_flag_4 : 1;
   unsigned lang_flag_5 : 1;
   unsigned lang_flag_6 : 1;
- -  /* room for 3 more bits */
+  /* room for 2 more bits */
 
   unsigned int align;
   union tree_node *pointer_to;
------- End of forwarded message -------

Re: [dax@gurulabs.com: PATCH: `__norestrict' type qualifier (fwd)]

[Jamie Lokier]

Richard Stallman wrote:
> Since this really is a new feature, we have to judge it as one; it
> needs to be clear to document, and reliable to use.  I don't know
> whether this feature can be described and implemented reliably, but I
> think that should be possible.  "Apply the same rules that apply to
> char *" seems like a clear basis for the specification; and as long as
> GCC reliably implements the ISO C aliasing rules for char *, it should
> be able to implement this with equal reliability.

"Apply the same rules that apply to char *" gives us a sensible rule,
for the type alias tests in the compiler.  I think it is quite a clear
rule.

For the user, we should take care what we promise.  As the sprinkle of
mb(), rmb() and wmb() through Linux shows, and a recent misunderstanding
of the barrier properties of `volatile', C memory ordering rules in
general can be confusing.

ISO C doesn't talk about type aliasing.  It talks about permitted access
through pointers.  It doesn't define what happens when one object is
accessed through another pointer type.  Obviously we know what kind of
code is preferred:

   1. fast;
   2. shouldn't make any special effort for unaligned data;
   3. the read/write operation should use the machine operation of the
      cast-to type, not the cast-from type with conversion in registers.

A naive definition in memcpy() terms did not satisfy 1 or 2 for some
types.  We have an example of code that gives the wrong answer if 3 is
not satisfied.

After a few iterations I came up with this, which everyone was too busy
to disagree with :-)

Oh, to the compiler implementors: I think the implementation is exactly
the rule "Apply the same rules that apply to char *" :-)

                          ------------------

The C9X draft defines alignment already:

       3.1
       [#1] alignment
       requirement that objects of a particular type be located  on
       storage   boundaries  with  addresses  that  are  particular
       multiples of a byte address

Conversions between different pointer types are defined thus (though
access through the wrong pointer type is undefined):

       6.3.2.3  Pointers
       [#7]  A  pointer  to  an  object  or  incomplete type may be
       converted to a pointer to a different object  or  incomplete
       type.   If the resulting pointer is not correctly aligned50)
       for  the  pointed-to  type,  the  behavior   is   undefined.
       Otherwise,  when  converted  back  again,  the  result shall
       compare equal to the original pointer.  When a pointer to an
       object  is  converted  to a pointer to a character type, the
       result points to the lowest addressed byte  of  the  object.

That brings on a new proposed definition.  Remember this is all so GCC can
generate good code, that's our excuse for discussing it on this list... ;-)

I think this fixes every problem raised so far:

    For conversion to and from other pointer types, pointers of type
    `__norestrict B *', for all B, are subject to the same guarantees and
    restrictions as pointers of type `B *'.  See 6.3.2.3 [#7].

    In particular, if the result of converting a pointer to `__norestrict B
    *' is not correctly aligned for the type B, the behaviour is undefined.

    Reading through a pointer of type `__norestrict B *' shall have the
    same, implementation-defined behaviour as converting the pointer to
    type `const char *', copying sizeof B characters from that address into
    field `a' of a temporary of type `union { char a [sizeof B]; B b; }',
    and then reading field `b'.

    Writing through a pointer of type `__norestrict B *' shall have the
    same, implementation-defined behaviour as writing to field `b' of a
    temporary of type `union { char a [sizeof B]; B b; }', converting the
    pointer to type `char *', and then copying sizeof B characters to that
    address from field `a'.

    The order of character copies is not defined -- they may occur
    simultaneously, independently or in any combination.  A volatile
    qualification on B does not change this.  A const qualification is
    honoured by disallowing writes in the usual way.


-- Jamie

Re: [dax@gurulabs.com: PATCH: `__norestrict' type qualifier (fwd)]

[patl]

As author of that patch, here is my $0.02.

First, as Richard Henderson pointed out when we discussed this before,
`__typealias' is a better name than `__norestrict'.  An informal
description of the behavior meshes nicely with Mark Mitchell's
informal description of the alias analysis rules; namely, that this
type qualifier allows access to the same memory through different
types of pointer.

Jamie's precise specification, which amounts to saying that
`__typealias' is shorthand for "the union hack", should also be given
in the documentation and used to resolve any arguments about the
behavior of the extension.  Jamie's spec could also be used to propose
this type qualifier to the standards bodies.

I am willing to do whatever work the GCC maintainers want to make my
patch acceptable to them, assuming they are amenable to the idea at
all.  Are they?

 - Pat

Re: [dax@gurulabs.com: PATCH: `__norestrict' type qualifier (fwd)]

[Jamie Lokier]

Patrick J. LoPresti wrote:
> used to resolve any arguments about the behavior of the extension.

To conform to this, you need to fix up the other type-based alias
analysis that's been in the compiler for a long time: MEM_IN_STRUCT_P.
That would be a good thing, because currently -fno-strict-aliasing does
not turn off this alias assumption.

Perhaps MEM_IN_STRUCT_P can be completely removed now there is a general
type alias framework?

-- Jamie

Re: [dax@gurulabs.com: PATCH: `__norestrict' type qualifier (fwd)]

[Jeffrey A Law]

  In message < 19990914173757.B12177@pcep-jamie.cern.ch >you write:
  > Patrick J. LoPresti wrote:
  > > used to resolve any arguments about the behavior of the extension.
  > 
  > To conform to this, you need to fix up the other type-based alias
  > analysis that's been in the compiler for a long time: MEM_IN_STRUCT_P.
  > That would be a good thing, because currently -fno-strict-aliasing does
  > not turn off this alias assumption.
  > 
  > Perhaps MEM_IN_STRUCT_P can be completely removed now there is a general
  > type alias framework?
MEM_IN_STRUCT_P is still valuable according to my tests a few months ago.

I'm curious, what code do you (or anyone) have that violates the 
MEM_IN_STRUCT_P
assumptions.  [As opposed to bugs in MEM_IN_STRUCT_P, of which there have been
many, but with the revamp from last year, it ought to be correct now. ]

jeff

Re: [dax@gurulabs.com: PATCH: `__norestrict' type qualifier (fwd)]

[Jamie Lokier]

Richard Stallman wrote:
> Since this really is a new feature, we have to judge it as one; it
> needs to be clear to document, and reliable to use.  I don't know
> whether this feature can be described and implemented reliably, but I
> think that should be possible.  "Apply the same rules that apply to
> char *" seems like a clear basis for the specification; and as long as
> GCC reliably implements the ISO C aliasing rules for char *, it should
> be able to implement this with equal reliability.

"Apply the same rules that apply to char *" gives us a sensible rule,
for the type alias tests in the compiler.  I think it is quite a clear
rule.

For the user, we should take care what we promise.  As the sprinkle of
mb(), rmb() and wmb() through Linux shows, and a recent misunderstanding
of the barrier properties of `volatile', C memory ordering rules in
general can be confusing.

ISO C doesn't talk about type aliasing.  It talks about permitted access
through pointers.  It doesn't define what happens when one object is
accessed through another pointer type.  Obviously we know what kind of
code is preferred:

   1. fast;
   2. shouldn't make any special effort for unaligned data;
   3. the read/write operation should use the machine operation of the
      cast-to type, not the cast-from type with conversion in registers.

A naive definition in memcpy() terms did not satisfy 1 or 2 for some
types.  We have an example of code that gives the wrong answer if 3 is
not satisfied.

After a few iterations I came up with this, which everyone was too busy
to disagree with :-)

Oh, to the compiler implementors: I think the implementation is exactly
the rule "Apply the same rules that apply to char *" :-)

                          ------------------

The C9X draft defines alignment already:

       3.1
       [#1] alignment
       requirement that objects of a particular type be located  on
       storage   boundaries  with  addresses  that  are  particular
       multiples of a byte address

Conversions between different pointer types are defined thus (though
access through the wrong pointer type is undefined):

       6.3.2.3  Pointers
       [#7]  A  pointer  to  an  object  or  incomplete type may be
       converted to a pointer to a different object  or  incomplete
       type.   If the resulting pointer is not correctly aligned50)
       for  the  pointed-to  type,  the  behavior   is   undefined.
       Otherwise,  when  converted  back  again,  the  result shall
       compare equal to the original pointer.  When a pointer to an
       object  is  converted  to a pointer to a character type, the
       result points to the lowest addressed byte  of  the  object.

That brings on a new proposed definition.  Remember this is all so GCC can
generate good code, that's our excuse for discussing it on this list... ;-)

I think this fixes every problem raised so far:

    For conversion to and from other pointer types, pointers of type
    `__norestrict B *', for all B, are subject to the same guarantees and
    restrictions as pointers of type `B *'.  See 6.3.2.3 [#7].

    In particular, if the result of converting a pointer to `__norestrict B
    *' is not correctly aligned for the type B, the behaviour is undefined.

    Reading through a pointer of type `__norestrict B *' shall have the
    same, implementation-defined behaviour as converting the pointer to
    type `const char *', copying sizeof B characters from that address into
    field `a' of a temporary of type `union { char a [sizeof B]; B b; }',
    and then reading field `b'.

    Writing through a pointer of type `__norestrict B *' shall have the
    same, implementation-defined behaviour as writing to field `b' of a
    temporary of type `union { char a [sizeof B]; B b; }', converting the
    pointer to type `char *', and then copying sizeof B characters to that
    address from field `a'.

    The order of character copies is not defined -- they may occur
    simultaneously, independently or in any combination.  A volatile
    qualification on B does not change this.  A const qualification is
    honoured by disallowing writes in the usual way.


-- Jamie

Re: [dax@gurulabs.com: PATCH: `__norestrict' type qualifier (fwd)]

[Jamie Lokier]

Patrick J. LoPresti wrote:
> used to resolve any arguments about the behavior of the extension.

To conform to this, you need to fix up the other type-based alias
analysis that's been in the compiler for a long time: MEM_IN_STRUCT_P.
That would be a good thing, because currently -fno-strict-aliasing does
not turn off this alias assumption.

Perhaps MEM_IN_STRUCT_P can be completely removed now there is a general
type alias framework?

-- Jamie

[dax@gurulabs.com: PATCH: `__norestrict' type qualifier (fwd)]

[Richard Stallman]

The proposal below looks like a good idea to me, at least in
principle.  This would give people a straightforward and reliable
solution to use when they get the new warning that we are discussing.

Since this really is a new feature, we have to judge it as one; it
needs to be clear to document, and reliable to use.  I don't know
whether this feature can be described and implemented reliably, but I
think that should be possible.  "Apply the same rules that apply to
char *" seems like a clear basis for the specification; and as long as
GCC reliably implements the ISO C aliasing rules for char *, it should
be able to implement this with equal reliability.

The other change I've proposed, to keep many cases of old code working
for now, remains a good idea even if this new feature is added.
They complement each other.


------- Start of forwarded message -------
Date: Sat, 11 Sep 1999 01:15:58 -0600 (MDT)
From: Dax Kelson <dax@gurulabs.com>
X-Sender: dkelson@ultra1.inconnect.com
To: jbuck@synopsys.COM
cc: rms@gnu.org
Subject: PATCH: `__norestrict' type qualifier (fwd)
Content-Type: TEXT/PLAIN; charset=US-ASCII
Content-Length: 10202


Isn't this post from July relevent to the current alias dicussion?

Dax Kelson

- ---------- Forwarded message ----------
Date: 17 Jul 1999 15:26:14 -0400
From: Patrick J. LoPresti <patl@cag.lcs.mit.edu>
To: egcs@egcs.cygnus.com
Cc: torvalds@transmeta.com
Subject: PATCH: `__norestrict' type qualifier

Just in time for 2.95!

OK, maybe not.

The following patch adds support for a "__norestrict" type qualifier.
It is used to mark a pointer type as potentially aliasing all of
memory.  For example:

  *(unsigned int *__norestrict)p ^= ~0;

...flips the 32 (or 64) bits pointed at by p, no matter what type p
has.

The rationale for this is straightforward; it is a logical extension
of the "char *" exception for type aliasing.  Obviously (?) the ISO
folks realized that people use char * to access raw memory, so they
allowed char * to alias anything.  The problem is that nobody who
cares about performance uses char * for this purpose on modern
machines; they use a pointer to something with the "natural" word size
of the architecture.

Lots of code (especially in the Linux kernel) is written this way, and
it is not easy to rewrite using unions or macros (according to the
maintainers).  The `__norestrict' keyword makes it easy to convert
such code so that it can work in the presence of type-based alias
analysis.

Two notes:

  1) This is not well-tested, although it seems to work.  Many thanks
     to the author (Mark Mitchell?) of the current alias analysis
     support.  That well-commented and well-structured code made this
     extension fairly trivial, even for a GCC neophyte like me.

  2) I have not even glanced at the other front ends (e.g., C++), so
     there may be some additional work needed there to get this
     finished.  I am willing to do that work, but I didn't want to
     spend any more time on something which the GCC maintainers might
     reject out-of-hand...

 - Pat

======================================================================

diff -u -r gcc-orig/c-aux-info.c gcc/c-aux-info.c
- --- gcc-orig/c-aux-info.c	Sat Apr 17 13:14:45 1999
+++ gcc/c-aux-info.c	Sat Jul 17 14:17:25 1999
@@ -524,6 +524,8 @@
     ret_val = concat ("volatile ", ret_val, NULL_PTR);
   if (TYPE_RESTRICT (t))
     ret_val = concat ("restrict ", ret_val, NULL_PTR);
+  if (TYPE_NORESTRICT (t))
+    ret_val = concat ("__norestrict ", ret_val, NULL_PTR);
   return ret_val;
 }
 
diff -u -r gcc-orig/c-common.c gcc/c-common.c
- --- gcc-orig/c-common.c	Tue Apr 13 17:04:06 1999
+++ gcc/c-common.c	Sat Jul 17 14:17:23 1999
@@ -2980,12 +2980,12 @@
      values, so even though it should be illegal to use `restrict'
      with such an entity we don't flag that here.  Thus, special case
      code for that case is required in the C++ front-end.  */
- -  if ((type_quals & TYPE_QUAL_RESTRICT)
+  if ((type_quals & (TYPE_QUAL_RESTRICT | TYPE_QUAL_NORESTRICT))
       && (!POINTER_TYPE_P (type)
 	  || !C_TYPE_OBJECT_OR_INCOMPLETE_P (TREE_TYPE (type))))
     {
- -      error ("invalid use of `restrict'");
- -      type_quals &= ~TYPE_QUAL_RESTRICT;
+      error ("invalid use of `restrict' or `__norestrict'");
+      type_quals &= ~(TYPE_QUAL_RESTRICT | TYPE_QUAL_NORESTRICT);
     }
 
   if (TREE_CODE (type) == ARRAY_TYPE)
@@ -3038,6 +3038,18 @@
 				    DECL_POINTER_ALIAS_SET (decl));
 	    }
 	}
+    }
+  if (type_quals & TYPE_QUAL_NORESTRICT)
+    {
+      if (!TREE_TYPE (decl)
+	  || !POINTER_TYPE_P (TREE_TYPE (decl))
+	  || !C_TYPE_OBJECT_OR_INCOMPLETE_P (TREE_TYPE (TREE_TYPE (decl))))
+	error ("invalid use of `__norestrict'");
+      else if (flag_strict_aliasing)
+        {
+          /* Unrestricted pointers can alias anything. */
+          DECL_POINTER_ALIAS_SET (decl) = 0;
+        }
     }
 }
 
diff -u -r gcc-orig/c-decl.c gcc/c-decl.c
- --- gcc-orig/c-decl.c	Mon Apr 12 10:05:29 1999
+++ gcc/c-decl.c	Sat Jul 17 14:17:25 1999
@@ -4383,6 +4383,7 @@
   int longlong = 0;
   int constp;
   int restrictp;
+  int norestrictp;
   int volatilep;
   int type_quals = TYPE_UNQUALIFIED;
   int inlinep;
@@ -4700,19 +4701,26 @@
      declaration contains the `const'.  */
   constp = !! (specbits & 1 << (int) RID_CONST) + TYPE_READONLY (type);
   restrictp = !! (specbits & 1 << (int) RID_RESTRICT) + TYPE_RESTRICT (type);
+  norestrictp = (!! (specbits & 1 << (int) RID_NORESTRICT)
+                 + TYPE_NORESTRICT (type));
   volatilep = !! (specbits & 1 << (int) RID_VOLATILE) + TYPE_VOLATILE (type);
   inlinep = !! (specbits & (1 << (int) RID_INLINE));
   if (constp > 1)
     pedwarn ("duplicate `const'");
   if (restrictp > 1)
     pedwarn ("duplicate `restrict'");
+  if (norestrictp > 1)
+    pedwarn ("duplicate `__norestrict'");
   if (volatilep > 1)
     pedwarn ("duplicate `volatile'");
+  if (restrictp && norestrictp)
+    error ("Both `restrict' and `__norestrict' applied to same type");
   if (! flag_gen_aux_info && (TYPE_QUALS (type)))
     type = TYPE_MAIN_VARIANT (type);
   type_quals = ((constp ? TYPE_QUAL_CONST : 0)
 		| (restrictp ? TYPE_QUAL_RESTRICT : 0)
- -		| (volatilep ? TYPE_QUAL_VOLATILE : 0));
+		| (volatilep ? TYPE_QUAL_VOLATILE : 0)
+                | (norestrictp ? TYPE_QUAL_NORESTRICT : 0));
 
   /* Warn if two storage classes are given. Default to `auto'.  */
 
@@ -5075,6 +5083,8 @@
 		    volatilep++;
 		  else if (qualifier == ridpointers[(int) RID_RESTRICT])
 		    restrictp++;
+                  else if (qualifier == ridpointers[(int) RID_NORESTRICT])
+                    norestrictp++;
 		  else if (!erred)
 		    {
 		      erred = 1;
@@ -5087,10 +5097,15 @@
 		pedwarn ("duplicate `volatile'");
 	      if (restrictp > 1)
 		pedwarn ("duplicate `restrict'");
+	      if (norestrictp > 1)
+		pedwarn ("duplicate `__norestrict'");
+              if (restrictp && norestrictp)
+                error ("`restrict' and `__norestrict' applied to same type");
 
 	      type_quals = ((constp ? TYPE_QUAL_CONST : 0)
 			    | (restrictp ? TYPE_QUAL_RESTRICT : 0)
- -			    | (volatilep ? TYPE_QUAL_VOLATILE : 0));
+			    | (volatilep ? TYPE_QUAL_VOLATILE : 0)
+                            | (norestrictp ? TYPE_QUAL_NORESTRICT : 0));
 	    }
 
 	  declarator = TREE_OPERAND (declarator, 0);

diff -u -r gcc-orig/c-lex.c gcc/c-lex.c
- --- gcc-orig/c-lex.c	Sat Mar 20 14:21:23 1999
+++ gcc/c-lex.c	Sat Jul 17 14:17:24 1999
@@ -257,6 +257,7 @@
   ridpointers[(int) RID_INLINE] = get_identifier ("inline");
   ridpointers[(int) RID_CONST] = get_identifier ("const");
   ridpointers[(int) RID_RESTRICT] = get_identifier ("restrict");
+  ridpointers[(int) RID_NORESTRICT] = get_identifier ("norestrict");
   ridpointers[(int) RID_VOLATILE] = get_identifier ("volatile");
   ridpointers[(int) RID_AUTO] = get_identifier ("auto");
   ridpointers[(int) RID_STATIC] = get_identifier ("static");

diff -u -r gcc-orig/c-lex.h gcc/c-lex.h
- --- gcc-orig/c-lex.h	Thu Feb 18 15:38:39 1999
+++ gcc/c-lex.h	Sat Jul 17 14:17:24 1999
@@ -41,6 +41,7 @@
   RID_SIGNED,
   RID_CONST,
   RID_RESTRICT,
+  RID_NORESTRICT,
   RID_VOLATILE,
   RID_INLINE,
   RID_NOALIAS,

diff -u -r gcc-orig/c-parse.gperf gcc/c-parse.gperf
- --- gcc-orig/c-parse.gperf	Wed Mar 31 02:43:51 1999
+++ gcc/c-parse.gperf	Sat Jul 17 13:53:22 1999
@@ -33,6 +33,8 @@
 __iterator, SCSPEC, RID_ITERATOR
 __iterator__, SCSPEC, RID_ITERATOR
 __label__, LABEL, NORID
+__norestrict, TYPE_QUAL, RID_NORESTRICT
+__norestrict__, TYPE_QUAL, RID_NORESTRICT
 __real, REALPART, NORID
 __real__, REALPART, NORID
 __restrict, TYPE_QUAL, RID_RESTRICT

diff -u -r gcc-orig/c-parse.in gcc/c-parse.in
- --- gcc-orig/c-parse.in	Mon Apr 26 18:35:50 1999
+++ gcc/c-parse.in	Sat Jul 17 14:17:24 1999
@@ -116,7 +116,8 @@
    yylval contains an IDENTIFIER_NODE which indicates which one.  */
 %token TYPESPEC
 
- -/* Reserved words that qualify type: "const", "volatile", or "restrict".
+/* Reserved words that qualify type: "const", "volatile", "restrict",
+   or "__norestrict".
    yylval contains an IDENTIFIER_NODE which indicates which one.  */
 %token TYPE_QUAL
 
diff -u -r gcc-orig/tree.c gcc/tree.c
- --- gcc-orig/tree.c	Sat Apr 17 07:43:57 1999
+++ gcc/tree.c	Sat Jul 17 14:17:25 1999
@@ -3608,6 +3608,7 @@
   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
+  TYPE_NORESTRICT (type) = (type_quals & TYPE_QUAL_NORESTRICT) != 0;
 }
 
 /* Given a type node TYPE and a TYPE_QUALIFIER_SET, return a type for

diff -u -r gcc-orig/tree.h gcc/tree.h
- --- gcc-orig/tree.h	Sun May  2 13:43:32 1999
+++ gcc/tree.h	Sat Jul 17 14:17:26 1999
@@ -834,6 +834,9 @@
    the term.  */
 #define TYPE_RESTRICT(NODE) (TYPE_CHECK (NODE)->type.restrict_flag)
 
+/* Nonzero if type is `norestrict'-qualified. */
+#define TYPE_NORESTRICT(NODE) (TYPE_CHECK (NODE)->type.norestrict_flag)
+
 /* There is a TYPE_QUAL value for each type qualifier.  They can be
    combined by bitwise-or to form the complete set of qualifiers for a
    type.  */
@@ -842,12 +845,14 @@
 #define TYPE_QUAL_CONST    0x1
 #define TYPE_QUAL_VOLATILE 0x2
 #define TYPE_QUAL_RESTRICT 0x4
+#define TYPE_QUAL_NORESTRICT 0x8
 
 /* The set of type qualifiers for this type.  */
- -#define TYPE_QUALS(NODE)			\
- -  ((TYPE_READONLY(NODE) * TYPE_QUAL_CONST) |	\
- -   (TYPE_VOLATILE(NODE) * TYPE_QUAL_VOLATILE) |	\
- -   (TYPE_RESTRICT(NODE) * TYPE_QUAL_RESTRICT))
+#define TYPE_QUALS(NODE)			        \
+  ((TYPE_READONLY(NODE) * TYPE_QUAL_CONST) |	        \
+   (TYPE_VOLATILE(NODE) * TYPE_QUAL_VOLATILE) |	        \
+   (TYPE_RESTRICT(NODE) * TYPE_QUAL_RESTRICT) |         \
+   (TYPE_NORESTRICT(NODE) * TYPE_QUAL_NORESTRICT))
 
 /* These flags are available for each language front end to use internally.  */
 #define TYPE_LANG_FLAG_0(NODE) (TYPE_CHECK (NODE)->type.lang_flag_0)
@@ -901,6 +906,7 @@
   unsigned transparent_union_flag : 1;
   unsigned packed_flag : 1;
   unsigned restrict_flag : 1;
+  unsigned norestrict_flag : 1;
 
   unsigned lang_flag_0 : 1;
   unsigned lang_flag_1 : 1;
@@ -909,7 +915,7 @@
   unsigned lang_flag_4 : 1;
   unsigned lang_flag_5 : 1;
   unsigned lang_flag_6 : 1;
- -  /* room for 3 more bits */
+  /* room for 2 more bits */
 
   unsigned int align;
   union tree_node *pointer_to;
------- End of forwarded message -------

Re: [dax@gurulabs.com: PATCH: `__norestrict' type qualifier (fwd)]

[Patrick J. LoPresti]

As author of that patch, here is my $0.02.

First, as Richard Henderson pointed out when we discussed this before,
`__typealias' is a better name than `__norestrict'.  An informal
description of the behavior meshes nicely with Mark Mitchell's
informal description of the alias analysis rules; namely, that this
type qualifier allows access to the same memory through different
types of pointer.

Jamie's precise specification, which amounts to saying that
`__typealias' is shorthand for "the union hack", should also be given
in the documentation and used to resolve any arguments about the
behavior of the extension.  Jamie's spec could also be used to propose
this type qualifier to the standards bodies.

I am willing to do whatever work the GCC maintainers want to make my
patch acceptable to them, assuming they are amenable to the idea at
all.  Are they?

 - Pat

Re: [dax@gurulabs.com: PATCH: `__norestrict' type qualifier (fwd)]

[Jeffrey A Law]

  In message < 19990914173757.B12177@pcep-jamie.cern.ch >you write:
  > Patrick J. LoPresti wrote:
  > > used to resolve any arguments about the behavior of the extension.
  > 
  > To conform to this, you need to fix up the other type-based alias
  > analysis that's been in the compiler for a long time: MEM_IN_STRUCT_P.
  > That would be a good thing, because currently -fno-strict-aliasing does
  > not turn off this alias assumption.
  > 
  > Perhaps MEM_IN_STRUCT_P can be completely removed now there is a general
  > type alias framework?
MEM_IN_STRUCT_P is still valuable according to my tests a few months ago.

I'm curious, what code do you (or anyone) have that violates the 
MEM_IN_STRUCT_P
assumptions.  [As opposed to bugs in MEM_IN_STRUCT_P, of which there have been
many, but with the revamp from last year, it ought to be correct now. ]

jeff