[LLVMdev] Pointer aliasing

Tue Jan 24 07:34:51 PST 2012

Hi Brent,

I think this is a problem in the easy-cse transform. In this transform 
load operations can be replaced by their subexpression, in this case the 
propagated constant, based on the value of the 'CurrentGeneration' of 
memory writes. This implies that any store operation invalidates the 
knowledge about previously stored subexpressions.

In general, this is a safe assumption but in this case it is missing 
quite some optimization potential.

The effect of this can be shown by moving the line %6 one up, to before 
the previous store operation. This doesn't change the program behaviour 
but does influence the optimization.

More info on this is in lib/Transforms/Scalar/EarlyCSE.cpp (line 415 is 
a good start)

I don't have time to improve this at this moment so I'll leave that to 
you (or anyone else that feels inspired).

Cheers,
Roel

On 01/24/2012 03:59 PM, Brent Walker wrote:
> Hi Roel,
> the code you list below is precisely what I expect to get (of course
> the stores must happen but the constant folding should happen as
> well).
>
> It all looks very strange.  LLVM is behaving as if the __restrict__
> keyword was not used at all.  Even more strange is the fact that for
> this function:
>
> double f(double *__restrict__ x, double *__restrict__ y, double *__restrict__ z)
> {
>    *x = 1.0;
>    *y = *x + 2;
>    *z = *x + 3;
>
>    return *x + *y + *z;
> }
>
> everything works as expected:
>
> define double @_Z1fPdS_S_(double* noalias nocapture %x, double*
> noalias nocapture %y, double* noalias nocapture %z) nounwind uwtable {
>    store double 1.000000e+00, double* %x, align 8, !tbaa !0
>    store double 3.000000e+00, double* %y, align 8, !tbaa !0
>    store double 4.000000e+00, double* %z, align 8, !tbaa !0
>    ret double 8.000000e+00
> }
>
> !0 = metadata !{metadata !"double", metadata !1}
> !1 = metadata !{metadata !"omnipotent char", metadata !2}
> !2 = metadata !{metadata !"Simple C/C++ TBAA", null}
>
> So I can't figure out what the mechanism is for telling llvm that two
> pointers that are local variables (and not input arguments) to a
> function do not alias each other.  I hope one of the developers can
> shed some light on this.
>
> Thank you in advance for any help,
> Brent
>
>
> On Tue, Jan 24, 2012 at 9:01 PM, Roel Jordans<r.jordans at tue.nl>  wrote:
>> Hi Brent,
>>
>> Looking at your code I can see at least one reason why some of the store
>> operations remain in the output since you are (through x, y, and z)
>> writing in memory which exists outside of your function (p).
>>
>> Constant propagation also seems to work in the first few lines, *y = *x
>> +1 (%3) is stored directly.
>>
>> The strange thing to me is that the same doesn't happen for *z = *x + 2.
>> Here *x is loaded again and the addition is still performed...
>>
>>   From this point on, constant propagation seems to stop working
>> completely. Looking at the IR I would have expected something like the
>> following:
>>
>> define double @f(double** nocapture %p) nounwind uwtable {
>>     %1 = load double** %p, align 8, !tbaa !0
>>     %2 = getelementptr inbounds double** %p, i64 1
>>     %3 = load double** %2, align 8, !tbaa !0
>>     %4 = getelementptr inbounds double** %p, i64 2
>>     %5 = load double** %4, align 8, !tbaa !0
>>     store double 1.000000e+00, double* %1, align 8, !tbaa !3
>>     store double 3.000000e+00, double* %3, align 8, !tbaa !3
>>     store double 4.000000e+00, double* %5, align 8, !tbaa !3
>>     ret double 8.000000e+00
>> }
>>
>> !0 = metadata !{metadata !"any pointer", metadata !1}
>> !1 = metadata !{metadata !"omnipotent char", metadata !2}
>> !2 = metadata !{metadata !"Simple C/C++ TBAA", null}
>> !3 = metadata !{metadata !"double", metadata !1}
>>
>> I am afraid I can't really help you in telling what went wrong here and
>> caused the missing optimizations, but I agree with you that the result
>> in not what I would have expected.
>>
>> Cheers,
>> Roel
>> On 01/23/2012 03:31 AM, Brent Walker wrote:
>>> Hi LLVMers,
>>> I would like to ask a question regarding aliasing.  Suppose I have the
>>> following program:
>>>
>>> double f(double** p )
>>> {
>>>      double a,b,c;
>>>      double * x =&a;
>>>      double * y =&b;
>>>      double * z =&c;
>>>
>>>      *x = 1;
>>>      *y = *x + 2;
>>>      *z = *x + 3;
>>>
>>>      return *x+*y+*z;
>>> }
>>>
>>> LLVM can tell that the three pointers do not alias each other so can
>>> perform the constant folding at compile time.
>>>
>>> define double @f(double** nocapture %p) nounwind uwtable readnone {
>>>     ret double 8.000000e+00
>>> }
>>>
>>> Now consider the function below.  I know (in my particluar case) that
>>> the pointers in the p array do not alias each other.  I tried to
>>> communicate this information to llvm/clang via the __restrict__
>>> qualifier but it does not seem to have an effect.  Can you please
>>> suggest what is wrong.  How can I achieve what I want?
>>>
>>> double f(double** p )
>>> {
>>>      double *__restrict__ x = p[0];
>>>      double *__restrict__ y = p[1];
>>>      double *__restrict__ z = p[2];
>>>
>>>      *x = 1;
>>>      *y = *x + 2;
>>>      *z = *x + 3;
>>>
>>>      return *x+*y+*z;
>>> }
>>>
>>> define double @f(double** nocapture %p) nounwind uwtable {
>>>     %1 = load double** %p, align 8, !tbaa !0
>>>     %2 = getelementptr inbounds double** %p, i64 1
>>>     %3 = load double** %2, align 8, !tbaa !0
>>>     %4 = getelementptr inbounds double** %p, i64 2
>>>     %5 = load double** %4, align 8, !tbaa !0
>>>     store double 1.000000e+00, double* %1, align 8, !tbaa !3
>>>     store double 3.000000e+00, double* %3, align 8, !tbaa !3
>>>     %6 = load double* %1, align 8, !tbaa !3
>>>     %7 = fadd double %6, 3.000000e+00
>>>     store double %7, double* %5, align 8, !tbaa !3
>>>     %8 = load double* %1, align 8, !tbaa !3
>>>     %9 = load double* %3, align 8, !tbaa !3
>>>     %10 = fadd double %8, %9
>>>     %11 = fadd double %10, %7
>>>     ret double %11
>>> }
>>>
>>> !0 = metadata !{metadata !"any pointer", metadata !1}
>>> !1 = metadata !{metadata !"omnipotent char", metadata !2}
>>> !2 = metadata !{metadata !"Simple C/C++ TBAA", null}
>>> !3 = metadata !{metadata !"double", metadata !1}
>>>
>>> Thank you for any help.
>>>
>>> Brent
>>> _______________________________________________
>>> 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