Hi, all
According to the document "LLVM Alias Analysis Infrastructure", I
evaluated the AA performance by using the paramenters '-basicaa -ds-aa
-anders-aa'. The source code 'test.c' is listed as follow:
//------------=== Source code ===------------//
#include<stdlib.h>
typedef struct
{
int x;
int y;
} Location;
Location* getNewLocation(int x, int y)
{
Location* newLoc = (Location *)malloc(sizeof(Location));
newLoc->x = x;
newLoc->y = y;
return newLoc;
}
Location* getDifference(Location *a, Location *b)
{
Location* newLoc = (Location *)malloc(sizeof(Location));
newLoc->x = a->x - b->x;
newLoc->y = a->y - b->y;
return newLoc;
}
int main()
{
Location *loc1 = getNewLocation(0, 0);
Location *loc2 = getNewLocation(1, 2);
Location *loc3 = getDifference(loc1, loc2);
free(loc1);
free(loc2);
free(loc3);
return 0;
}
//------------=== End ===------------//
The whole process:
llvm-gcc -emit-llvm -O0 -c test.c -o test.bc
opt test.bc -load libLLVMDataStructure.so -basic-aa -ds-aa -anders-aa
-aa-eval -print-all-alias-modref-info
The corresponding IR content of main is:
define i32 @main() nounwind {
entry:
%retval = alloca i32
%loc3 = alloca %struct.Location*
%loc2 = alloca %struct.Location*
%loc1 = alloca %struct.Location*
%0 = alloca i32
%"alloca point" = bitcast i32 0 to i32
%1 = call %struct.Location* @getNewLocation(i32 0, i32 0) nounwind
store %struct.Location* %1, %struct.Location** %loc1, align 4
%2 = call %struct.Location* @getNewLocation(i32 1, i32 2) nounwind
store %struct.Location* %2, %struct.Location** %loc2, align 4
%3 = load %struct.Location** %loc1, align 4
%4 = load %struct.Location** %loc2, align 4
%5 = call %struct.Location* @sub(%struct.Location* %3, %
struct.Location* %4) nounwind
store %struct.Location* %5, %struct.Location** %loc3, align 4
%6 = load %struct.Location** %loc1, align 4
%7 = bitcast %struct.Location* %6 to i8*
call void @free(i8* %7) nounwind
%8 = load %struct.Location** %loc2, align 4
%9 = bitcast %struct.Location* %8 to i8*
call void @free(i8* %9) nounwind
%10 = load %struct.Location** %loc3, align 4
%11 = bitcast %struct.Location* %10 to i8*
call void @free(i8* %11) nounwind
store i32 0, i32* %0, align 4
%12 = load i32* %0, align 4
store i32 %12, i32* %retval, align 4
br label %return
return: ; preds = %entry
%retval1 = load i32* %retval
ret i32 %retval1
}
The analysis result of function main is(Strip NoAlias):
MayAlias: %struct.Location* %1, %struct.Location* %2
But, in my opinion, %1 and %2 should be NoAlias. And, there's no
dependence between
%1 = call %struct.Location* @getNewLocation(i32 0, i32 0) nounwind
and
%2 = call %struct.Location* @getNewLocation(i32 1, i32 2) nounwind
%1 and %2 are considered as MayAlias results that while using
llvm::MemoryDependenceAnalysis, %2 is dependent on %1(clobber). But in
fact it's not.
Maybe a flow-sensitive, context-sensitive alias analysis algorithm is
needed to generate more precise result? Correct me, if I'm wrong. Thank
you.
Hi,> llvm-gcc -emit-llvm -O0 -c test.c -o test.bctry compiling with optimization. Ciao, Duncan.
On 2009-06-29 11:16, Wenzhi Tao wrote:> Hi, all > > According to the document "LLVM Alias Analysis Infrastructure", I > evaluated the AA performance by using the paramenters '-basicaa -ds-aa > -anders-aa'. The source code 'test.c' is listed as follow: > [...] > The whole process: > > llvm-gcc -emit-llvm -O0 -c test.c -o test.bc > > opt test.bc -load libLLVMDataStructure.so -basic-aa -ds-aa -anders-aa > -aa-eval -print-all-alias-modref-info >Try this: opt -mem2reg -functionattrs -basic-aa -aa-eval -print-all-alias-modref-info test.bc It shows: NoAlias: %struct.Location* %0, %struct.Location* %1> %1 and %2 are considered as MayAlias results that while using > llvm::MemoryDependenceAnalysis, %2 is dependent on %1(clobber). But in > fact it's not. > > Maybe a flow-sensitive, context-sensitive alias analysis algorithm is > needed to generate more precise result? Correct me, if I'm wrong. Thank > you. >Running the functionattrs pass should be enough to add the 'noalias' marker on getNewLocation(), and then even basic-aa can see that loc1 and loc2 are NoAlias. You also need to run -mem2reg, because otherwise -functionattrs doesn't see that the return value is coming from a malloc (which already has noalias attribute). Best regards, --Edwin
Hi Duncan,
I tried to perform alias analysis after optimization(O1, since O2 and
O3 implement inlining).
opt -O1 test.bc -o o1.bc
The content of main() is listed as follow:
define i32 @main() nounwind {
entry:
%0 = tail call %struct.Location* @getNewLocation(i32 0, i32 0)
nounwind ; <%struct.Location*> [#uses=2]
%1 = tail call %struct.Location* @getNewLocation(i32 1, i32 2)
nounwind ; <%struct.Location*> [#uses=2]
%2 = tail call %struct.Location* @sub(%struct.Location* %0, %
struct.Location* %1) nounwind ; <%struct.Location*> [#uses=1]
%3 = bitcast %struct.Location* %0 to i8* ; <i8*> [#uses=1]
tail call void @free(i8* %3) nounwind
%4 = bitcast %struct.Location* %1 to i8* ; <i8*> [#uses=1]
tail call void @free(i8* %4) nounwind
%5 = bitcast %struct.Location* %2 to i8* ; <i8*> [#uses=1]
tail call void @free(i8* %5) nounwind
ret i32 0
}
Then, the AA result with option "-basicaa -ds-aa -anders-aa" is:
MayAlias: %struct.Location* %0, %struct.Location* %1
MayAlias: %struct.Location* %0, %struct.Location* %2
MayAlias: %struct.Location* %1, %struct.Location* %2
%0 and %1 are still considered as 'may alias'.
在 2009-06-29一的 10:36 +0200，Duncan Sands写道：> Hi,
>
> > llvm-gcc -emit-llvm -O0 -c test.c -o test.bc
>
> try compiling with optimization.
>
> Ciao,
>
> Duncan.
>
Hi,
Thanks for your advice. I have tried this way:
opt -mem2reg test.bc -o mem2reg.bc
llvm-dis mem2reg.bc
opt -functionattrs -basicaa -aa-eval -print-all-alias-modref-info
mem2reg.bc
The content of main() in mem2reg.ll:
define i32 @main() nounwind {
entry:
%"alloca point" = bitcast i32 0 to i32 ; <i32> [#uses=0]
%0 = call %struct.Location* @getNewLocation(i32 0, i32 0) nounwind ; <
%struct.Location*> [#uses=2]
%1 = call %struct.Location* @getNewLocation(i32 1, i32 2) nounwind ; <
%struct.Location*> [#uses=2]
%2 = call %struct.Location* @sub(%struct.Location* %0, %
struct.Location* %1) nounwind ; <%struct.Location*> [#uses=1]
%3 = bitcast %struct.Location* %0 to i8* ; <i8*> [#uses=1]
call void @free(i8* %3) nounwind
%4 = bitcast %struct.Location* %1 to i8* ; <i8*> [#uses=1]
call void @free(i8* %4) nounwind
%5 = bitcast %struct.Location* %2 to i8* ; <i8*> [#uses=1]
call void @free(i8* %5) nounwind
br label %return
return: ; preds = %entry
ret i32 0
}
The result of -aa-eval:
MayAlias: %struct.Location* %0, %struct.Location* %1
MayAlias: %struct.Location* %0, %struct.Location* %2
MayAlias: %struct.Location* %1, %struct.Location* %2
Even when I add the AA option "-ds-aa -anders-aa", the result keeps
unchanged. en, I don't know if I miss some steps or the method doesn't
work at all.
在 2009-06-29一的 11:48 +0300，Török Edwin写道：> On 2009-06-29 11:16, Wenzhi Tao wrote:
> > Hi, all
> >
> > According to the document "LLVM Alias Analysis
Infrastructure", I
> > evaluated the AA performance by using the paramenters '-basicaa
-ds-aa
> > -anders-aa'. The source code 'test.c' is listed as follow:
> > [...]
> > The whole process:
> >
> > llvm-gcc -emit-llvm -O0 -c test.c -o test.bc
> >
> > opt test.bc -load libLLVMDataStructure.so -basic-aa -ds-aa -anders-aa
> > -aa-eval -print-all-alias-modref-info
> >
>
> Try this:
> opt -mem2reg -functionattrs -basic-aa -aa-eval
> -print-all-alias-modref-info test.bc
>
> It shows:
> NoAlias: %struct.Location* %0, %struct.Location* %1
>
> > %1 and %2 are considered as MayAlias results that while using
> > llvm::MemoryDependenceAnalysis, %2 is dependent on %1(clobber). But in
> > fact it's not.
> >
> > Maybe a flow-sensitive, context-sensitive alias analysis algorithm is
> > needed to generate more precise result? Correct me, if I'm wrong.
Thank
> > you.
> >
>
> Running the functionattrs pass should be enough to add the
'noalias'
> marker on getNewLocation(), and then even basic-aa can see that loc1 and
> loc2 are NoAlias.
> You also need to run -mem2reg, because otherwise -functionattrs doesn't
> see that the return value is coming from a malloc (which already has
> noalias attribute).
>
> Best regards,
> --Edwin
>
>