[LLVMdev] C99 restrict

[Dan Gohman]

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.

An alias-free attribute wouldn't be usable in general because pointers
are almost never completely alias-free. For example in C:

  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.

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.