[LLVMdev] C99 restrict

[Christopher Lamb]

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.
>
> 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.

>   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;
	}
}


> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070326/634d2e7a/attachment.html>