Wrong AliasAnalysis::getModRefInfo result

Project Infrastructure LLVM Dev List Archives
#1

Just want to test out the LLVM’s AliasAnalysis::getModRefInfo API. The input C code is very simple:

void foo(int *a, int *b)
{
for(int i=0; i<10; i++)
b[i] = a[i]*a[i];
}

int main()
{
int a[10];
int b[10];

for(int i=0; i<10; i++)
a[i] = i;

foo(a,b);

return 0;
}

Obviously, for “foo”, it only reads from array “a” and only writes to array “b”.

The LLVM pass:
virtual bool runOnFunction(Function &F) {
++HelloCounter;
errs() << "Hello: ";
errs().write_escaped(F.getName()) << ‘\n’;

AliasAnalysis &AA = getAnalysis();
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
Instruction *Inst = &*I;
if ( CallInst *ci = dyn_cast(Inst) ){
ci->dump();
for(int i = 0; i < ci->getNumArgOperands(); i++){
Value *v = ci->getArgOperand(i);
if (GetElementPtrInst *vi = dyn_cast(v)){
Value *vPtr = vi->getPointerOperand();
vPtr->dump();
if ( AllocaInst *allo = dyn_cast(vPtr) ) {
const Type *t = allo->getAllocatedType();
if ( const ArrayType *at = dyn_cast(t) ) {
int64_t size = at->getNumElements() * at->getElementType()->getPrimitiveSizeInBits() / 8;
ImmutableCallSite cs(ci);
AliasAnalysis::Location loc(v, size);
errs() << AA.getModRefInfo(ci, loc) << “\n”;
}
}
}
}
}
}

return false;
}

However, the result is “3” for both a and b, which is both read and write. What’s the problem? I am not quite sure if I get the AliasAnalysis::Location right, what is exactly “address-units” for the size of the location? And did I get the starting address of the Location right? I tried v, vi and vPtr, same result.

Any insight helps,
Welson

#2

Something must be wrong, more probable on my side. So the C source code is unchanged, I just did another experiment to first extract all the GEPs in the code, and call AliasAnalysis::alias on each pair of GEPs. Here is the code:

AliasAnalysis &AA = getAnalysis();
TargetData &TD = getAnalysis();

for (Module::iterator it = M.begin(); it != M.end(); it++){
Function &F = *it;
errs().write_escaped(F.getName()) << ‘\n’;
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
Instruction *Inst = &*I;
if ( GetElementPtrInst *gep = dyn_cast(Inst) )
geps.push_back(gep);
}
}

errs() << “List of GEPs:\n”;
for(std::list<GetElementPtrInst* >::iterator itGep1
= geps.begin(); itGep1 != geps.end(); itGep1++){
GetElementPtrInst *gep1 = *itGep1;
Type *t1 = ((PointerType )gep1->getType())->getElementType();
int64_t size1 = TD.getTypeAllocSize(t1);
std::list<GetElementPtrInst >::iterator itGep2 = itGep1;
for(; itGep2 != geps.end(); itGep2++){
GetElementPtrInst *gep2 = *itGep2;
gep1->dump();
errs() << “–>”;
gep2->dump();

Type *t2 = ((PointerType *)gep2->getType())->getElementType();
int64_t size2 = TD.getTypeAllocSize(t2);
AliasAnalysis::AliasResult aa = AA.alias(gep1, size1,
errs() << " alias: " << aa << “\n”;
}
}

Here is the result:
%9 = getelementptr inbounds i32* %8, i32 %7
→ %9 = getelementptr inbounds i32* %8, i32 %7
alias: 1
%9 = getelementptr inbounds i32* %8, i32 %7
→ %13 = getelementptr inbounds i32* %12, i32 %11
alias: 1
%9 = getelementptr inbounds i32* %8, i32 %7
→ %18 = getelementptr inbounds i32* %17, i32 %16
alias: 1
%9 = getelementptr inbounds i32* %8, i32 %7
→ %8 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 %7
alias: 1
%9 = getelementptr inbounds i32* %8, i32 %7
→ %13 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 0
alias: 1
%9 = getelementptr inbounds i32* %8, i32 %7
→ %14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
alias: 1
%13 = getelementptr inbounds i32* %12, i32 %11
→ %13 = getelementptr inbounds i32* %12, i32 %11
alias: 1
%13 = getelementptr inbounds i32* %12, i32 %11
→ %18 = getelementptr inbounds i32* %17, i32 %16
alias: 1
%13 = getelementptr inbounds i32* %12, i32 %11
→ %8 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 %7
alias: 1
%13 = getelementptr inbounds i32* %12, i32 %11
→ %13 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 0
alias: 1
%13 = getelementptr inbounds i32* %12, i32 %11
→ %14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
alias: 1
%18 = getelementptr inbounds i32* %17, i32 %16
→ %18 = getelementptr inbounds i32* %17, i32 %16
alias: 1
%18 = getelementptr inbounds i32* %17, i32 %16
→ %8 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 %7
alias: 1
%18 = getelementptr inbounds i32* %17, i32 %16
→ %13 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 0
alias: 1
%18 = getelementptr inbounds i32* %17, i32 %16
→ %14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
alias: 1
%8 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 %7
→ %8 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 %7
alias: 1
%8 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 %7
→ %13 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 0
alias: 1
%8 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 %7
→ %14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
alias: 1
%13 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 0
→ %13 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 0
alias: 1
%13 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 0
→ %14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
alias: 1
%14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
→ %14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
alias: 1

How can be each pair MayAlias? That’s simply wrong! For example:

%13 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 0
→ %14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
Must not alias,

while
%14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
→ %14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
Must alias.

Can someone help identifying where is wrong with my code?

Thanks!
Welson

#3

Hi Welson, the default alias analysis is -no-aa. As the name suggests it
just returns MayAlias for everything. Maybe you are using that one?

Best wishes, Duncan.

#4

Thanks Duncan! You are right! If I type the command “opt -basicaa -mypass …”, then the output makes sense.

Now, how can you specify which AA to use in the code?

Regards,
Welson

#5

Actually, with -basicaa, the alias result only makes sense for instructions in the same scope:

%9 = getelementptr inbounds i32* %8, i32 %7
→ %13 = getelementptr inbounds i32* %12, i32 %11
May Alias

%9 = getelementptr inbounds i32* %8, i32 %7
→ %18 = getelementptr inbounds i32* %17, i32 %16
May Alias

%9 = getelementptr inbounds i32* %8, i32 %7
→ %8 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 %7
May Alias

%9 = getelementptr inbounds i32* %8, i32 %7
→ %13 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 0
May Alias

%9 = getelementptr inbounds i32* %8, i32 %7
→ %14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
May Alias

%13 = getelementptr inbounds i32* %12, i32 %11
→ %18 = getelementptr inbounds i32* %17, i32 %16
May Alias

%13 = getelementptr inbounds i32* %12, i32 %11
→ %8 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 %7
May Alias

%13 = getelementptr inbounds i32* %12, i32 %11
→ %13 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 0
May Alias

%13 = getelementptr inbounds i32* %12, i32 %11
→ %14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
May Alias

%18 = getelementptr inbounds i32* %17, i32 %16
→ %8 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 %7
May Alias

%18 = getelementptr inbounds i32* %17, i32 %16
→ %13 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 0
May Alias

%18 = getelementptr inbounds i32* %17, i32 %16
→ %14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
May Alias

%8 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 %7
→ %13 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 0
Partial Alias

%8 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 %7
→ %14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
No Alias

%13 = getelementptr inbounds [10 x i32]* %a, i32 0, i32 0
→ %14 = getelementptr inbounds [10 x i32]* %b, i32 0, i32 0
No Alias

The real information I am after is the getModRefInfo() result, however, even with AA turned on, the modref info is still useless for a function call.
call void @Z3fooPiS(i32* %13, i32* %14)
%a = alloca [10 x i32], align 4
3
%b = alloca [10 x i32], align 4
3

Are there any other projects or examples that use LLVM AA infrastructure to perform array ModRef analysis?

Thanks,
Welson