[LLVMdev] Choosing Alias Analysis

[David Greene]

On Friday 10 August 2007 13:54, Devang Patel wrote:

> > Or is it sufficient than an Andersen's object is constructed and
> > that that
> > constitutes "availability?"
>
> What do you mean by "available" ? You are using quotes :)

"Available" as referenced by PassSupport.h:

/// RegisterAnalysisGroup - Register a Pass as a member of an analysis 
/// _group_.  Analysis groups are used to define an interface (which need not 
/// derive from Pass) that is required by passes to do their job.  Analysis 
/// Groups differ from normal analyses because any available implementation of 
/// the group will be used if it is available.
///
/// If no analysis implementing the interface is available, a default
/// implementation is created and added.  A pass registers itself as the 
/// default implementation by specifying 'true' as the third template argument 
/// of this class.

> > What happens if multiple alias analyses are
> > constructed?  Is the most-recently constructed one considered the
> > "available"
> > one?
>
> When alias info is invalidated, pass manager is responsible to
> reconstruct alias analysis before a pass that requires alias info is
> executed. If multiple alias analysis are constructed then non default
> alias analysis will get used and recreated as per need.

Yes, but which one gets used?

> Note, the goal of analysis group is to select desired analysis
> implementations during entire run of optimizer. I do [not] think it is
> designed to handle cases where during one instance of optimizer
> multiple instances of analysis implementations are used
> simultaneously. 

But this is the example Chris presented.

> However, this may work for limited case of one 
> default and one non-default analysis implementation but I think it
> will break down when multiple non-default analysis implementations
> are constructed.

Even if it's just one default and one non-default created, which one gets
used when AA is invalidated?  I gather the non-default one will be used
per your description above.

I don't need to be able to choose various different implementations of an
analysis group, I just need to be able to pick and and guarantee it will
always be used.  From our discussion, I think I can do that as long as I
tell the analysis group registrar which one I want by constructing it.

How does the analysis group registrar know when a non-default implementation
has been constructed?

> If a pass requires particular implementation explicitly, i.e
> addRequired<Andersens>() then pass manager will make it available
> irrespective of alias analysis group. However explicitly requiring an
> analysis pass defeats the purpose of analysis group.

Right..

At the moment I'm trying to do what Chris suggested and provide a
cl::opt for coalescers.  I've got about this far:

  llvm::cl::opt<
    llvm::RegisterCoalescer::Ctor,
    false,
    SomeParserToBeDefined >
  Coalescer("coalescer",
                      cl::init(/* Default analysis group constructor */),
                      cl::desc("Pick a coalescer: (default = fill this in)"));

I can't use RegisterPassParser because it expects a function pass
constructor and the RegisterCoalescer interface is not a function pass.

The question I have is how to get this to interact properly with analysis
groups.  The existing coalescer has this:

  // Need to register with PassManager so getAnalysis works
  RegisterPass<SimpleRegisterCoalescing> 
  X("simple-register-coalescing",
    "Simple register coalescing to eliminate all possible register copies 
     (default RC impl)");

  // Declare that we implement the RegisterCoalescer interface
  RegisterAnalysisGroup<RegisterCoalescer, true/*The Default*/> V(X);

My new coalescer does this:

  // Need to register with PassManager so getAnalysis works
  RegisterPass<ConservativeCoalescing> 
  X("conservative-register-coalescing",
    "Conservative register coalescing to eliminate register copies without 
     introducing spills");

  // Declare that we implement the RegisterCoalescer interface
  RegisterAnalysisGroup<RegisterCoalescer> V(X);

I want to be able to pick a coalescer with
--coalescer=simple-register-coalescing 
or
--coalscer=conservative-register-coalescing

I can't use the bare -conservative-register-coalescing Pass option because the 
tool doesn't do the opt-like thing of registering every pass as a command-line 
argument.  It should not do so because we don't want to expose all that to the 
user.

So there are a number of questions I have to answer:

- How do I get at the default analysis group member to pass its constructor to 
  cl::init?

- How do I get the name of the default analysis group member to put in the
  description string?  Presumably this is easy if I can get to the default 
  analysis group member.

- How will this all interact with getAnalysis<RegisterCoalescer>?  How do I 
  inject the constructor selected by --coalescer back into the analysis group 
  so it knows to use that when getAnalysis<RegisterCoalescer> is called?

All these registration and manager classes are really confusing.  I think what 
I need to do is get at PassInfo::getNormalCtor and PassInfo::setNormalCtor
for the InterfaceInfo member of RegisterAnalysisGroup.  Unfortunately,
it's private and doesn't have an accessor.  So I will have to do some hacking
if this is the right direction to go.

Where does the code that actually constructs the implementation of an
analysis group member live?  Where's the code that decides which
implementation of the analysis group to return to the caller of 
getAnalysis<SomeAnalysisGroup>?

Am I at least on the right track?  I still don't have a clue as to how to get 
the Pass or PassInfo for the default implementation of an analysis group
interface.

Perhaps an easier way is to just expose the -simple-register-coalescing
and -conservative-register-coalescing options to the user, but I don't know
how to do that on an individual pass bases.  opt just jams then all in with
PassNameParser.  PassNameParser.h makes reference to a FilteredPassNameParser
that sounds closer to what I want but I can't find the code for that 
anywhere.

                                                      -Dave