[LLVMdev] C99 restrict

[Chris Lattner]

On Mon, 26 Mar 2007, Christopher Lamb wrote:
>>  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.

I think the goal should be to capture the most important information.  The
c99 definition of restrict has some nasty and complex implementation 
issues.  It may not be reasonable or interesting to capture every corner 
case.

A more interesting question is how to represent TBAA information in LLVM 
:).

Here is a sketch of a concrete proposal to get us started:

1. Add a new argument attribute "noalias", which can be applied to pointer
    formals and pointer function results.
2. Add a new intrinsic "i8* @llvm.noalias(i8*)

The semantics of 'noalias' are that they "define a new object".  Any 
pointer derived from it ("it" being the result of a no-alias call result, 
a formal parameter, or the result of llvm.noalias) is considered to not 
alias:

A. any other objects (e.g. global vars, allocas, functions, etc)
B. any other "noalias" objects
C. any other formal argument parameters or call results.

For these purposes, "pointers derived" means getelementptr and bitcast.

Can C99 restrict be mapped onto these semantics?  Is "C" really safe?

With these semantics, it is clear that 'calloc' could be declared to have 
a result pointer that is noalias for example, but I'm not sure if it would 
be safe to map restrict onto it.

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

C99 Restrict is very tricky and subtle.  IIRC, it is defined in terms of 
accesses and objects, not in terms of anything intuitive or natural :)

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

This example is also undefined because of the pointer arithmetic you are 
using.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/