[LLVMdev] Pointer aliasing

[Duncan Sands]

Hi Brent,

> Unless I can mark these extracted pointers as non-aliasing, performance
> suffers a lot.  It's not just CSE that suffers -- LLVM does not do
> copy propagation either so we keep loading the same values from memory
> over and over again.  See the example here:
>
> double f(double a, double * x, double *y, double * z)
> {
>    *x = a;
>    *y = a+1;
>    *z = *x + 3;
>
>    return *x + *y + *z;
> }

here you are obliged to reload the values since some of the pointers might
be equal.  For example the store to *y will change the value of *x if x and
y are the same pointer.

Ciao, Duncan.

>
> define double @f(double %a, double* nocapture %x, double* nocapture
> %y, double* nocapture %z) nounwind uwtable {
>    store double %a, double* %x, align 8, !tbaa !0
>    %1 = fadd double %a, 1.000000e+00
>    store double %1, double* %y, align 8, !tbaa !0
>    %2 = load double* %x, align 8, !tbaa !0
>    %3 = fadd double %2, 3.000000e+00
>    store double %3, double* %z, align 8, !tbaa !0
>    %4 = load double* %x, align 8, !tbaa !0
>    %5 = load double* %y, align 8, !tbaa !0
>    %6 = fadd double %4, %5
>    %7 = fadd double %6, %3
>    ret double %7
> }
>
> !0 = metadata !{metadata !"double", metadata !1}
> !1 = metadata !{metadata !"omnipotent char", metadata !2}
> !2 = metadata !{metadata !"Simple C/C++ TBAA", null}
>
> (I used arguments here without __restrict__ which has the same effect as
> loading my pointers from context as locals).  As you can see we keep
> loading the value of x from memory, even though we just stored a local
> into it.  Given that I am generating LLVM IR directly (via the C++
> interface) can you suggest someway I could pass the noalias attribute
> onto the locals?
>
> One work around is of course to generate two functions as follows:
>
> double f1( struct ctx* ctx )
> {
>     return f2(ctx->a, ctx->x, ctx->y, ctx->z);
> }
>
> double f2( double a, double *__restrict__ x, double *__restrict__ y,
> double *__restrict__  z)
> {
>      *x = a;
>      *y = a+1;
>      *z = *x + 3;
>
>      return *x + *y + *z;
> }
>
> but if at all possible I would like to avoid such acrobatics.
>
> Thank you in advance for any help.
> Brent
>
>
> On Wed, Jan 25, 2012 at 4:52 AM, Dan Gohman<gohman at apple.com>  wrote:
>> On Jan 24, 2012, at 7:45 AM, Brent Walker wrote:
>>
>>> Can you explain please why it works for this version of the function:
>>>
>>> double f(double *__restrict__ x, double *__restrict__ y, double
>>> *__restrict__ z);
>>>
>>> What is different here?  There are stores here as well.
>>
>> LLVM ignores restrict everywhere except function parameters. This is a
>> compromise aimed at a sweet spot in the balance of compiler complexity
>> vs. optimization opportunity.
>>
>>   - Many analysis and optimization techniques naturally apply to whole
>>    functions. When restrict appears on a local variable inside a
>>    function, its special aliasing property applies to only a subset of
>>    the function. It's awkward to teach such code to understand and
>>    respect local scope boundaries, in general.
>>
>>   - Function boundaries are often the boundaries of analysis.
>>    Interprocedural analysis can be expensive and complex, so many
>>    optimization passes are limited to thinking about one function
>>    at a time. And even interprocedural analysis passes are
>>    bounded by shared library boundaries. While local variables can
>>    often be analyzed automatically (as in your first example),
>>    function paramters are often incoming mystery values, so they
>>    are where restrict is most often interesting.
>>
>> This compromise does mean that some opportunities are lost (as in
>> your second example), but from clang's perspective these cases are
>> rare.
>>
>> Dan
>>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev