[LLVMdev] C99 restrict

Christopher Lamb christopher.lamb at gmail.com
Mon Mar 26 22:41:15 PDT 2007


On Mar 27, 2007, at 12:54 AM, Chris Lattner wrote:

> 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*)

In the C99 spec it would appear that declaring a pointer function  
result as restrict has no effect, as it depends purely on whether the  
pointer being assigned to is declared restrict or not. It's pointed  
out here that this also applies to using restrict on the pointer type  
of casts, the restrict qualifier makes no difference in the cast,  
only to the type that's being assigned to.

In this case I'd think that pointer function results would have the  
intrinsic applied to them if they were assigned to a restrict  
pointer. Other than clearing up the pointer function results this  
seems like a good concise proposal.

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

I just read through the C99 formal definition of restrict (http:// 
www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf page 110) with an  
eye to this proposal, and I believe that C99 restrict can be mapped  
onto these semantics. Primarily because the requirement is for access  
though a restrict pointer to be equivalent to accesses to a copy of  
the "object" that the pointer points to.

>   Is "C" really safe?

I'm not sure what you mean by safe, but I think it's consistent with  
C99 restrict.

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

Declaring calloc() to return a restrict pointer would have no  
semantic difference than returning a normal pointer in C99. It would  
need to be assigned to a variable declared as a restrict pointer to  
make a difference.

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

Yes. Yes it is. I think I need more sleep. =) I was trying to cook up  
something like Example 2 (p. 111) from the C99 spec.

--
Christopher Lamb
christopher.lamb at gmail.com




More information about the llvm-dev mailing list