Incorrect result in LLVM Alias Analysis

I want to check if the values a and b in the program alias.

int main() {
int *a,*b;
a=(int *)malloc(sizeof(int));
b=(int *)malloc(sizeof(int));
*a=10;
*b=8;
return 0;
}

I use the below code for this (getAnalysisUsage method has been defined)

AliasAnalysis::Location loc1=AliasAnalysis::Location(k1); //a
AliasAnalysis::Location loc2=AliasAnalysis::Location(k2); //b
AliasAnalysis::AliasResult ar=AA.alias(loc1,loc2);

But I get ar=1 i.e May Alias result. Where am I going wrong? I have included -basicaa option in the opt command for running this.

I use the below code for this (getAnalysisUsage method has been defined)

AliasAnalysis::Location loc1=AliasAnalysis::Location(k1); //a
AliasAnalysis::Location loc2=AliasAnalysis::Location(k2); //b
AliasAnalysis::AliasResult ar=AA.alias(loc1,loc2);

But I get ar=1 i.e May Alias result. Where am I going wrong? I have
included -basicaa option in the opt command for running this.

  LLVM alias analysis might be not so powerful at this moment, I guess.

Regards,
chenwj

I want to check if the values a and b in the program alias.

int main() {
int *a,*b;
a=(int *)malloc(sizeof(int));
b=(int *)malloc(sizeof(int));
*a=10;
*b=8;
return 0;
}

Silly question: did you '#include <stdlib.h>' in your test program?
Does your malloc() declaration include '__attribute__ ((malloc))'?
If malloc() is seen as an implicit def or does not have the special malloc
attribute attached to it (which tells the compiler "non-NULL pointers
returned from this function will not alias any other pointer that's valid
at the time of the call"), the compiler cannot tell out-of-hand that a and
b do not alias.

Hi Adarsh,

I want to check if the values a and b in the program alias.

int main() {
int *a,*b;
a=(int *)malloc(sizeof(int));
b=(int *)malloc(sizeof(int));
*a=10;
*b=8;
return 0;
}

I use the below code for this (getAnalysisUsage method has been defined)

AliasAnalysis::Location loc1=AliasAnalysis::Location(k1); //a
AliasAnalysis::Location loc2=AliasAnalysis::Location(k2); //b
AliasAnalysis::AliasResult ar=AA.alias(loc1,loc2);

But I get ar=1 i.e May Alias result. Where am I going wrong?

did you run a basic set of optimizers first? Alias analysis assumes that
at least mem2reg has been run. Otherwise it returns conservatively correct
but useless answers for everything.

  I have included

-basicaa option in the opt command for running this.

Ciao, Duncan.

I have used the following command,
opt -load LLVComMan.so -ComMan -memdep -tbaa -mem2reg maptest.ll -S
What option other than -mem2reg should be included in this case to get the
right results? Does the order in which I specify the optimizations to be run
make a difference?

Duncan Sands wrote:

I have used the follwing command,
opt -load LLVComMan.so -ComMan -memdep -tbaa -mem2reg maptest.ll -S
What option other than -mem2reg should be included in this case to get the
right results? Does the order in which I specify the optimizations to be run
make a difference?

Duncan Sands wrote:

Hi Adarsh,

I have used the follwing command,
opt -load LLVComMan.so -ComMan -memdep -tbaa -mem2reg maptest.ll -S
What option other than -mem2reg should be included in this case to get the
right results? Does the order in which I specify the optimizations to be run
make a difference?

what is in maptest.ll?

Ciao, Duncan.

It contains the bitcode file(without any optimization) of the below program,
void map(int *a)
{
  *a=20;
}
int main(){
int *a=(int *)malloc(sizeof(int));
*a=15;
map(a);
return 0;
}
I want to check if the pointer operand of each store instruction aliases
with the function's arguments. I have used below code for this,
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
               AU.addRequiredTransitive<AliasAnalysis>();
    AU.addPreserved<AliasAnalysis>();
}
virtual bool runOnFunction(Function &F) {
    AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
                 for(Function::iterator i=F.begin();i!=F.end();++i){
      for(BasicBlock::iterator j=i->begin();j!=i->end();++j)
      {
        if(dyn_cast<StoreInst>(j))
                                   {
                     StoreInst *SI=dyn_cast<StoreInst>(j);
                     AliasAnalysis::Location LocA = AA.getLocation(SI);
                     for(Function::arg_iterator k=F.arg_begin();
k!=F.arg_end();++k)
                                               {
                          Value *v=dyn_cast<Value>(k);
                          AliasAnalysis::Location
loc=AliasAnalysis::Location(v);
                          AliasAnalysis::AliasResult ar=AA.alias(LocA,loc);
                                                }
                                    }
                              }
                        }
But I get 'May Alias' result for the store instruction that assigns the
value of 'a' to 20 in the 'map' function.Is the result not supposed to be
'Must alias'?

Duncan Sands wrote:

Hi Adarsh,

It contains the bitcode file(without any optimization) of the below program,

sorry for not being clear. I meant: please provide the bitcode. One
possibility is that the malloc return value is not being marked "noalias"
by the front-end.

Ciao, Duncan.

Here's the bitcode of maptest.ll.
; ModuleID = 'maptest.c'
target datalayout =
"e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32"
target triple = "i386-pc-linux-gnu"

define void @map(i32* %a) nounwind {
  %1 = alloca i32*, align 4
  store i32* %a, i32** %1, align 4
  %2 = load i32** %1, align 4
  store i32 20, i32* %2
  ret void
}

define i32 @main() nounwind {
  %1 = alloca i32, align 4
  %a = alloca i32*, align 4
  store i32 0, i32* %1
  %2 = call i8* @malloc(i32 4)
  %3 = bitcast i8* %2 to i32*
  store i32* %3, i32** %a, align 4
  %4 = load i32** %a, align 4
  store i32 15, i32* %4
  %5 = load i32** %a, align 4
  call void @map(i32* %5)
  ret i32 0
}

declare noalias i8* @malloc(i32) nounwind

Regards,
Adarsh H.V.

Adarsh HV wrote:

Hi Adarsh,

I have used the follwing command,
opt -load LLVComMan.so -ComMan -memdep -tbaa -mem2reg maptest.ll -S
What option other than -mem2reg should be included in this case to get the
right results? Does the order in which I specify the optimizations to be run
make a difference?

you should be using -basicaa not -tbaa. TBAA won't do anything here because you
don't have any tbaa metadata. Also, specifying tbaa won't automagically cause
basicaa to be used too: if you want them both (and to chain to each other) then
you need to specify both of them AFAIK.

Notice "must alias" in what follows.

$ opt -basicaa -mem2reg adarsh.ll -disable-output -aa-eval
===== Alias Analysis Evaluator Report =====
   1 Total Alias Queries Performed
   0 no alias responses (0.0%)
   0 may alias responses (0.0%)
   0 partial alias responses (0.0%)
   1 must alias responses (100.0%)
   Alias Analysis Evaluator Pointer Alias Summary: 0%/0%/0%/100%
   6 Total ModRef Queries Performed
   0 no mod/ref responses (0.0%)
   0 mod responses (0.0%)
   0 ref responses (0.0%)
   6 mod & ref responses (100.0%)
   Alias Analysis Evaluator Mod/Ref Summary: 0%/0%/0%/100%

Ciao, Duncan.