alias result

Hi all,

I am implementing a pass which needs aliasanalysis in llvm.

My pass firstly records all store or load instructions as follows:
loc[cnt++] = AA.getLocation(si/li);

Then, get each pairwise alias result.
AliasAnalysis::AliasResult ar = AA.alias(loc[i], loc[j]);
switch(ar){ case 0,1,2,3;}

And the command is: opt -load mypass.so -mypass -basicaa test.bc

The store/load in test.bc:

(1): store i64* %thd, i64** %t, align 8 //int64 *t = &thd;
(2): %1 = load i64** %t, align 8 //load t
(3): store i64* %1, i64** %t2, align 8 //int64 *t2 = t;
(4): %2 = load i64** %t, align 8 //load t
(5): %3 = load i64** %t2, align 8 //load t2

It seems that all these 5 instructions should be aliased to each other.

But the result should that only (1,2) (1,4) (2,4) (3,5) are must alias. Others are no alias.

Who can explain these results? Any hits would be appreciated. Thank you.

From: "Haopeng Liu" <hyliuhp@gmail.com>
To: llvmdev@cs.uiuc.edu
Sent: Monday, February 16, 2015 12:12:18 PM
Subject: [LLVMdev] alias result

Hi all,

I am implementing a pass which needs aliasanalysis in llvm.

My pass firstly records all store or load instructions as follows:
loc[cnt++] = AA.getLocation(si/li);

Then, get each pairwise alias result.
AliasAnalysis::AliasResult ar = AA.alias(loc[i], loc[j]);
switch(ar){ case 0,1,2,3;}

And the command is: opt -load mypass.so -mypass -basicaa test.bc

The store/load in test.bc:

(1): store i64* %thd, i64** %t, align 8 //int64 *t = &thd;
(2): %1 = load i64** %t, align 8 //load t
(3): store i64* %1, i64** %t2, align 8 //int64 *t2 = t;
(4): %2 = load i64** %t, align 8 //load t
(5): %3 = load i64** %t2, align 8 //load t2

It seems that all these 5 instructions should be aliased to each
other.

But the result should that only (1,2) (1,4) (2,4) (3,5) are must
alias.
Others are no alias.

Where do %t and %t2 come from?

-Hal

t and t2 are two pointers defined in .c file.

The definitions in .bc are:
%thd = alloc i64, align 8
%t = alloca i64*, align 8
%t2 = alloca i64*, align 8

.c file likes this:
int thd;
int *t = &thd;
int *t2 = t;

From: "Haopeng Liu" <hyliuhp@gmail.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: llvmdev@cs.uiuc.edu
Sent: Monday, February 16, 2015 12:37:06 PM
Subject: Re: [LLVMdev] alias result

t and t2 are two pointers defined in .c file.

The definitions in .bc are:
%thd = alloc i64, align 8
%t = alloca i64*, align 8
%t2 = alloca i64*, align 8

.c file likes this:
int thd;
int *t = &thd;
int *t2 = t;

Okay, those point to distinct local stack allocations. Why do you expect them to alias?

-Hal

Yes, in my example, %1 and %2 point to t. %3 points to t2.

But t and t2 point to the same var, is it? That's where I'm confused.

From: "Haopeng Liu" <hyliuhp@gmail.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: llvmdev@cs.uiuc.edu
Sent: Monday, February 16, 2015 1:38:40 PM
Subject: Re: [LLVMdev] alias result

Yes, in my example, %1 and %2 point to t. %3 points to t2.

But t and t2 point to the same var, is it? That's where I'm confused.

So you believe that:

>>>> (1): store i64* %thd, i64** %t, align 8 //int64 *t = &thd;

...

>>>> (3): store i64* %1, i64** %t2, align 8 //int64 *t2 = t;

calling AA.getLocation on these two instructions, and then calling alias on them should not return NoAlias? I think your confusion is regarding what getLocation does. It is not referring to the stored value, but the location where those values are being stored (%t and %t2 in this case). Those won't alias, because %t and %t2 point to disjoint local stack locations.

-Hal

Oh, got it. Thanks for your explain. I misunderstand what getLocation does.

If I would like to get the result of alias analysis referring to the stored value, what should I do in llvm?

From: "Haopeng Liu" <hyliuhp@gmail.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: llvmdev@cs.uiuc.edu
Sent: Monday, February 16, 2015 1:59:44 PM
Subject: Re: [LLVMdev] alias result

Oh, got it. Thanks for your explain. I misunderstand what getLocation
does.

If I would like to get the result of alias analysis referring to the
stored value, what should I do in llvm?

if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
  Value *V = SI->getValueOperand();
  if (V->getType()->isPointerTy()) {
    // Now you know that you're storing a pointer-typed value V.
    Loc = AliasAnalysis::Location(V);
  }
}

-Hal

Thanks for your suggestion. I tried your method.

%thd = alloc i64, align 8
%t = alloc i64*, align 8
%t2 = alloc i64*, align8

1). store i64* %thd, i64** %t, align 8 //int64 *t = &thd;
2). store i64* %thd, i64** %t2, align 8 // int64 *t2 = &thd;

It can find that t and t2 point to the same var by using getValueOperand() and isPointerTy(). Then judge that %t and %t2 are must alias.

But another example is that:

%thd = alloc i64, align 8
%t = alloc i64*, align 8
%t2 = alloc i64*, align8

1). store i64* %thd, i64** %t, align 8 //int64 *t = &thd;
2). %1 = load i64** %t, align 8
3). store i64* %1, i64** %t2, align 8 // int64 *t2 = t; (%t2=%1=%t)

How to judge that (%t, %1, %t2) are must alias in this case?

-Haopeng