[LLVMdev] Strange pointer aliasing behaviour

[Eli Friedman]

On Wed, Jun 16, 2010 at 1:39 PM, Pierre C <lists at peufeu.com> wrote:
>
> I'm hitting a strange pointer aliasing "bug". Here is a test case :
>
> /* SOURCE CODE */
>
> #define little_list_size 8
>
> class LittleList1 {
> public:
>        int     _length;
>        double  _data[ little_list_size ];
>
>        LittleList1( int length )
>        {
>                _length = length;
>                for( int i=0; i<length; i++ )
>                        _data[i] = 0;
>        }
> };
>
> class LittleList2 {
> public:
>        int     _length;
>        double  _data[ little_list_size ];
>
>        LittleList2( int length )
>        {
>                _length = length;
>                for( int i=0; i<_length; i++ )
>                        _data[i] = 0;
>        }
> };
>
> int func1()
> {
>        LittleList1 l(4);
>        return l._length;
> }
>
> int func2()
> {
>        LittleList2 l(4);
>        return l._length;
> }
>
> /* END SOURCE CODE */
>
> The only difference between the 2 classes is in the constructor, in the
> line :
>        for( int i=0; i<_length; i++ )
>
> One has "length" which is a function parameter, the other has "_length"
> which is the class member which was initialized in the same constructor.
>
> Now let's compile and optimize :
>
> llvm-g++ -emit-llvm -Winline -O3 -Iinclude  -c test2.cpp -o test2.bc
> opt -S -O3 -print-alias-sets -count-aa test2.bc
>
> Result :
>
> %struct.LittleList1 = type { i32, [8 x double] }
>
> ********
> Here, func1() is perfectly optimized :
> ********
>
> define i32 @_Z5func1v() nounwind readnone {
> entry:
>   ret i32 4
> }
>
>
> ********
> func2() should give the exact same result as func1, however ...
>
> Alias Set Tracker: 1 alias sets for 2 pointer values.
>   AliasSet[0x0x8ca140,2] may alias, Mod/Ref   Pointers: (i32* %0, 4),
> (double* %scevgep.i, 8)
>
> A spurious alias comes up between the 2 fields of the struct (which should
> in theory not happen).
> So, it reloads _length at each iteration, thus no optimization takes place
> and the code below is generated :
>
> ********
>
> define i32 @_Z5func2v() nounwind readnone {
> entry:
>   %l = alloca %struct.LittleList1, align 8        ; <%struct.LittleList1*>
> [#uses=2]
>   %0 = getelementptr inbounds %struct.LittleList1* %l, i64 0, i32 0 ;
> <i32*> [#uses=2]
>   store i32 4, i32* %0, align 8
>   br label %bb.i
>
> bb.i:                                             ; preds = %bb.i, %entry
>   %indvar.i = phi i64 [ %tmp, %bb.i ], [ 0, %entry ] ; <i64> [#uses=2]
>   %tmp = add i64 %indvar.i, 1                     ; <i64> [#uses=2]
>   %tmp2.i = trunc i64 %tmp to i32                 ; <i32> [#uses=1]
>   %scevgep.i = getelementptr %struct.LittleList1* %l, i64 0, i32 1, i64
> %indvar.i ; <double*> [#uses=1]
>   store double 0.000000e+00, double* %scevgep.i, align 8
>   %1 = load i32* %0, align 8                      ; <i32> [#uses=2]
>   %2 = icmp sgt i32 %1, %tmp2.i                   ; <i1> [#uses=1]
>   br i1 %2, label %bb.i, label %_ZN11LittleList2C1Ei.exit
>
> _ZN11LittleList2C1Ei.exit:                        ; preds = %bb.i
>   ret i32 %1
>
> ********
>
> g++ correctly resolves this alias and both functions are compiled to
> "return 4".
> llvm-gcc (and opt) detect a spurious alias on func2() (all alias passes
> seem to do the same here) which prevents optimizations, and in other cases
> more complex than this simple test, it also prevents loop unrolling and
> many other optimizations.
>
> Can I do something to fix this ?

There are essentially two ways to "solve" this issue: one is
type-based alias analysis, i.e. assuming "double" and "int" don't
alias; LLVM doesn't implement this at the moment.  The other is to
attempt to analyze the loop and prove that %indvar.i is never
negative; LLVM doesn't implement anything like this at the moment
either.

-Eli