Question regarding the alias analysis chaining behaviour

Hi,
I am using LLVM 2.4 on a Linux RHEL5 machine. I was trying to figure out how the chaining of the alias analysis passes works in LLVM. Here are the command I used to test the chaining part.

  1. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc -no-aa -anders-aa -licm
    Result: Anderson’s AA and No Alias Analysis both are called.
  2. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc -basicaa -anders-aa -licm
    Result: Anderson’s AA and Basic AA both are called.
  3. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc -basicaa -licm
    Result: Only Basic AA is called. (When I use -no-aa instead of -basicaa, only the NoAA is called).
  4. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc -basicaa -anders-aa -licm -licm
    Result: First licm gets a mix of both AA passes (basic and anders), second licm only gets basic.
  5. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc -basicaa -anders-aa -licm -basicaa -anders-aa -licm
    Result: Both licm instances get a mix of Anders and Basic AA.

Am I to conclude that the Anderson’s Alias Analysis is only applied to LICM? and other passes which require alias analysis use BasicAA or NoAA depending which on which one is specified on the command line? Is this the reason I am seeing calls to different AAs when although I specify an AA which neither Basic nor No AA?

I read on llvm docs that it is not possible to actually specify one user-created alias analysis on the command line which is applied to all subsequent passes on the command line. Does this mean that there is a constraint on the command line user-created AA… which is that it only applies to the top-level pass (licm above) specified immediately after the user-created AA?

I read in the same llvm doc that the “superclass” (The main Alias Analysis pass I assume) decides which response to use when the user-defined AA overrides the default methods. However, in my current version, I don’t see code for deciding between the two AAs. Is this an artifact of the older version I am using?

Thanks for your response.

Rajesh

dirac wrote:

Hi,
    I am using LLVM 2.4 on a Linux RHEL5 machine. I was trying to figure
out how the chaining of the alias analysis passes works in LLVM. Here
are the command I used to test the chaining part.
  1. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc
-no-aa -anders-aa -licm
   Result: Anderson's AA and No Alias Analysis both are called.
   2. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc
-basicaa -anders-aa -licm
   Result: Anderson's AA and Basic AA both are called.
   3. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc
-basicaa -licm
   Result: Only Basic AA is called. (When I use -no-aa instead of
-basicaa, only the NoAA is called).
   4. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc
-basicaa -anders-aa -licm -licm
   Result: First licm gets a mix of both AA passes (basic and anders),
second licm only gets basic.
   5. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc
-basicaa -anders-aa -licm -basicaa -anders-aa -licm
   Result: Both licm instances get a mix of Anders and Basic AA.

   Am I to conclude that the Anderson's Alias Analysis is only applied
to LICM? and other passes which require alias analysis use BasicAA or
NoAA depending which on which one is specified on the command line? Is
this the reason I am seeing calls to different AAs when although I
specify an AA which neither Basic nor No AA?

   I read on llvm docs that it is not possible to actually specify one
user-created alias analysis on the command line which is applied to all
subsequent passes on the command line. Does this mean that there is a
constraint on the command line user-created AA... which is that it only
applies to the top-level pass (licm above) specified immediately after
the user-created AA?

The AA that you specify will be created when you specify it and live until that pass is invalidated (not explicitly preserved by a pass that runs). The next time a pass requires AA, the pass manager will create the default AA (BasicAA) and not the one you put on the command line.

You can view what the pass manager is actually doing with "opt -debug-pass=Structure ...".

Nick

[+llvmdev]

Rajeshwar Vanka wrote:

From: Nick Lewycky [mailto:nicholas@mxc.ca]
Sent: Wednesday, November 24, 2010 3:51 PM
To: dirac
Cc: llvmdev@cs.uiuc.edu
Subject: Re: [LLVMdev] Question regarding the alias analysis chaining
behaviour

dirac wrote:

Hi,
     I am using LLVM 2.4 on a Linux RHEL5 machine. I was trying to figure
out how the chaining of the alias analysis passes works in LLVM. Here
are the command I used to test the chaining part.
   1. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc
-no-aa -anders-aa -licm
    Result: Anderson's AA and No Alias Analysis both are called.
    2. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc
-basicaa -anders-aa -licm
    Result: Anderson's AA and Basic AA both are called.
    3. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc
-basicaa -licm
    Result: Only Basic AA is called. (When I use -no-aa instead of
-basicaa, only the NoAA is called).
    4. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc
-basicaa -anders-aa -licm -licm
    Result: First licm gets a mix of both AA passes (basic and anders),
second licm only gets basic.
    5. ./opt hello_world_1_nest_func.bc -o hello_world_1_nest_func_AA.bc
-basicaa -anders-aa -licm -basicaa -anders-aa -licm
    Result: Both licm instances get a mix of Anders and Basic AA.

    Am I to conclude that the Anderson's Alias Analysis is only applied
to LICM? and other passes which require alias analysis use BasicAA or
NoAA depending which on which one is specified on the command line? Is
this the reason I am seeing calls to different AAs when although I
specify an AA which neither Basic nor No AA?

    I read on llvm docs that it is not possible to actually specify one
user-created alias analysis on the command line which is applied to all
subsequent passes on the command line. Does this mean that there is a
constraint on the command line user-created AA... which is that it only
applies to the top-level pass (licm above) specified immediately after
the user-created AA?

The AA that you specify will be created when you specify it and live
until that pass is invalidated (not explicitly preserved by a pass that
runs). The next time a pass requires AA, the pass manager will create
the default AA (BasicAA) and not the one you put on the command line.

You can view what the pass manager is actually doing with "opt
-debug-pass=Structure ...".

Nick

So, what you are saying is that if I create an AA, and that is used by a
pass X, then
the AA I create will only be alive until that pass remains valid? I am a
little confused here.

From my understanding, an AA will be created only once, and its information

is updated using
Copy/delete/replace Value functions. Does this not apply to an AA pass that
I create?

The BasicAA pass is created only once because it is an ImmutablePass. I should've asked what type of Pass your custom AA is, but this is a common problem where someone writes an AA as a FunctionPass (or uses Andersen's AA before we removed it from the tree) and it doesn't live through the whole execution.

See http://llvm.org/docs/WritingAnLLVMPass.html#passtype and below for a list of the passes and their requirements. (Yes, BasicAA really does meet the requirements for an immutable pass. It stores no state and the copy/delete/replace functions are all no-ops.)

Nick

I thought analysis passes just rebuilt their state after they got
invalidated. Shouldn't that happen with an AA pass as well? Or is AA
special?

I thought analysis passes just rebuilt their state after they got
invalidated. Shouldn't that happen with an AA pass as well? Or is AA
special?

Yes, AA is "somehow" special. This is well known deficiency of pass
manager, it will rebuild only default implementation, not all the
required stuff in the chain.

Kenneth Uildriks wrote:

The AA that you specify will be created when you specify it and live
until that pass is invalidated (not explicitly preserved by a pass that
runs). The next time a pass requires AA, the pass manager will create
the default AA (BasicAA) and not the one you put on the command line.

I thought analysis passes just rebuilt their state after they got
invalidated. Shouldn't that happen with an AA pass as well? Or is AA
special?

What makes AA special is that it's in an AnalysisGroup. Yes analyses will be recreated when required by the running pass, but in this case the passes require "anything in the AA group" and by default the PassManager will satisfy that by creating BasicAA, not the pass you just wrote and stuck in the optz'n list at some point. If you insert an AA pass at some point then the pass manager will return that one until it's invalidated, but will create BasicAA next time.

Nick

So the trouble is in the way AnalysisGroups are handled, then? Is
there a desire or plan to change it so that the pass continues to
exist even when it's invalidated and needs to be recomputed?

Hi Kenneth,

So the trouble is in the way AnalysisGroups are handled, then? Is
there a desire or plan to change it so that the pass continues to
exist even when it's invalidated and needs to be recomputed?

This is definitely a bug which needs to be fixed. Noone just expressed
the willingness to fix it :slight_smile:

I'll take a look at it over the weekend.