[LLVMdev] C99 restrict

[Dan Gohman]

On Mon, Mar 26, 2007 at 12:47:04PM -0500, Christopher Lamb wrote:
> 
> 
> On Mar 26, 2007, at 10:10 AM, Dan Gohman wrote:
> 
> >On Mon, Mar 26, 2007 at 02:14:56AM -0500, Christopher Lamb wrote:
> >>
> >>
> >>On Mar 25, 2007, at 5:22 PM, Chris Lattner wrote:
> >>
> >>>On Sun, 25 Mar 2007, Christopher Lamb wrote:
> >>>>What about an approach not unlike how debugging information is
> >>>>handled? That
> >>>>is have an llvm intrinsic that encodes the known alias free range
> >>>>for a
> >>>>pointer.
> >>>
> >>>That is another great possibility.  One issue is that I haven't had
> >>>time
> >>>to study the implications of C99 restrict, so I don't feel
> >>>qualified to
> >>>propose a concrete solution yet.  Ideally, the mechanism added to  
> >>>LLVM
> >>>would be able to handle restrict as well as fortran argument
> >>>parameters
> >>>(even if the fortran functions are inlined!), etc.  IOW, we don't
> >>>want to
> >>>have an feature that just implements C99 restrict, we want a more
> >>>general
> >>>mechanism which C99 restrict can be implemented in terms of.  It  
> >>>seems
> >>>like an intrinsic would be a good way to do that.
> >>
> >>Certainly language independence is a requirement.
> >>
> >>I think your point about inlined functions is also valid for restrict
> >>parameters to functions that have been inlined in C/C++. The aliasing
> >>guarantees are limited to within that function's scope For an
> >>intrinsics approach this would require intrinsics which estrict/
> >>unrestrict the pointer bounding it's life within the function where
> >>it is declared restrict. The other approach would be to add
> >>attributes that mark all uses of the pointers as explicitly alias
> >>free, which would be much more invasive.
> >
> >For representing scoping information, a relatively non-invasive
> >approach is to introduce a special "copy" operation, which in LLVM
> >might look like
> >  %a = copy %b
> >This operation has to be somewhat special in that can't be folded away
> >in most cases, but it can otherwise be pretty straight-forward to
> >optimizers. The idea is to allow %a to be used in whatever alias
> >intrinsics are available without tainting %b. An inliner would  
> >generate
> >these special instructions for each of the arguments, and then all
> >references to the arguments within the inlined body would be made
> >through these copies.

BTW, I misspoke here; this doesn't address the scoping problem.

> >
> >An alias-free attribute wouldn't be usable in general because pointers
> >are almost never completely alias-free. For example in C:
> 
> From my understanding the 'restrict' qualifier is a directive to the  
> compiler that the pointer or reference should be treated as alias  
> free within the scope of the function, regardless. For the below code  
> alias(p, q) == No, and alias(p, r) == No, even though q is "based-on"  
> p and r may be "based-on" p.  This is both the power and danger of  
> 'restrict', as it is up to the programmer to use it correctly.

The definition of restrict is more involved than that. A restrict-qualified
pointer may alias a pointer "based-on" it. And if the "based-on" relationships
aren't known, then the answer to the associated alias queries must be Maybe.

In the test I posted below, the program is correct if x, y, and z are all
the same, so the stores cannot be reordered.

> >  int * restrict p = ...;
> >  p[x] = 0;
> >  p[y] = 1;
> >  int * q = p + z;
> >  *q = 2;
> >  *p = 3;
> >  int * r = foo(p);
> >  *r = 4;
> >
> >Translated to LLVM:
> >
> >  %t0 = getelementptr %p, %x
> >  store 0, %t0
> >  %t1 = getelementptr %p, %y
> >  store 1, %t1
> >  %q = getelementptr %p, %z
> >  store 2, %q
> >  store 3, %p
> >  %r = call @foo(%p)
> >  store 4, %r
> >
> >C's restrict keyword allows pointers to be "based-on" restrict- 
> >qualified
> >pointers, such as q in this example. The definition of "based-on" does
> >not require the relationship to be obvious though. r in this  
> >example may
> >or may not be "based-on" p, so an optimizer must make very  
> >conservative
> >assumptions unless it can get more information about foo.
> 
> My understanding of 'restrict' is that the compiler isn't required to  
> check that the semantics of restrict aren't violated. I would assume  
> that FORTRAN arguments are the same way, since determining whether or  
> not the semantics of are being violated is just as hard as normal  
> alias analysis.
> 
> It may even be incorrect for the compiler to enforce the semantics of  
> restrict pointers (with an error), even when the compilers alias  
> analysis determines that there is a may-alias relationship between to  
> pointers. Take the following example, which the compiler is now free  
> to unroll and reschedule:
> 
> struct element { int a, b; };
> 
> void swap(element * arr, int size)
> {
> 	int * __restrict a = &arr[0].a;
> 	int * __restrict b = &arr[0].b;
> 	for (int i=0; i!=size; ++i)
> 	{
> 		int tmp = a[i];
> 		a[i] = b[i];
> 		b[i] = tmp;
> 		a += 2;
> 		b += 2;
> 	}
> }

Yes; this test case is relatively simple to analyze.

> >Beyond C, some form of "based-on" relationship would also be needed  
> >for
> >LLVM IR, at least so that it could cope with things like %t0 and %t1
> >aliasing each other and %p in this example.
> >
> >Dan
> >
> >-- 
> >Dan Gohman, Cray Inc.
> 
> --
> Christopher Lamb
> christopher.lamb at gmail.com

> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev