Limitations of Alias Analysis?

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,
  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写道:

I'm getting NoAlias with the given steps; are you using trunk LLVM?

-Eli

Hi Eli,
  I'm using trunk LLVM:

SVN-URL: http://llvm.org/svn/llvm-project/llvm/trunk
Version: 74580

  The result of llvm-config --version is '2.6svn'.

  And, when I try the released version 2.5, it still reports that %0 and
%1 are MayAlias. I wonder why I can't get the same result with you.
Thank you.

在 2009-06-29一的 20:35 -0700,Eli Friedman写道: