[LLVMdev] Pointer aliasing

[Duncan Sands]

Hi Brent,

> Hi Duncan, you have misunderstood me I think.

that's quite possible - I haven't been following this thread.

   Of course in this case
> you have to reload the doubles since as you say the pointers may be
> aliasing each other.  I just wrote it this way to show the kind of
> code one gets if one cannot specify that pointers do now alias -- not
> adding the __restrict__ to the function arguments gives the same code
> as in my example with the local variables (with or without the
> restrict).
>
> If you could you answer the question in my email I would be grateful.
> Given that I am generating IR directly, is it possible for me to mark
> locals pointers as non-aliasing?

I don't know.

   When you said LLVM cannot do it, did
> you mean clang cannot or the backend cannot?

I didn't say this, maybe you are confusing with someone else.

   Is the 2 function
> solution I outlined in my previous email my only option?

I don't know.  Sorry not to be more helpful!

Ciao, Duncan.

>
> Thanks,
> Brent
>
>
> On Thu, Jan 26, 2012 at 12:45 AM, Duncan Sands<baldrick at free.fr>  wrote:
>> 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
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev