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 ?
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
> 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. > > -EliActually I think it's much simpler than that... http://llvm.org/releases/1.3/docs/AliasAnalysis.html#basic-aa it says says "Different fields of a structure do not alias." This is the case here : we have two different fields of a struct however it mistakenly thinks they alias.
FYI,
the case below can be folded with -scev-aa -licm,
to hoist this->_length on former loop.
class LittleList2X {
public:
int _length;
double _data[8];
LittleList2X( int length )
{
_length = length;
int i = 0;
#if 1
for( ; i<_length && i <= 0x1FFFFFFE; i++ )
_data[i] = 0;
#endif
for( ; i<_length; i++ )
_data[i] = 0;
}
};
Rationale: the pass ScalarEvolution discovers range of &_data[i] must be
finite.
(impossible when i >= 0x1FFFFFFF on p:32 target)
...Takumi
2010/6/17 Pierre C <lists at peufeu.com>:>
> 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 ?
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>