[LLVMdev] Limitations of Alias Analysis?

[Wenzhi Tao]

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.