Choosing Alias Analysis

[David_A_Greene]

Ok, here's a potentialy stupid question: how do I choose the various flavors
of alias analysis on the command line? I followed the alias analysis design
in its use of AnalysisGroup when I did the register coalescing refactoring and
alternative implentations. But I can't figure out how to actually invoke the
different versions. There's no cl_opt for the various alias analysis flavors
so I just assumed it was all built in to AnalysisGroup. Not so, apparently.

So how do I get opt to use Andersens instead of basicaa, for example?

                                               -Dave

[Devang_Patel1]

Following uses basic alias analysis

  $ opt -licm foo.bc -disable-output -debug-pass=Structure

where as

  $ opt -anders-aa -licm foo.bc -disable-output -debug-pass=Structure

uses Andersens analysis algorithm implementation.

[David_A_Greene]

Heh. opt was a particularly bad choice for an example on my part. It has
special code to provide options for all of the optimizations:

  // The OptimizationList is automatically populated with registered Passes by
  // the PassNameParser.
  //
  static cl::list<const PassInfo*, bool, PassNameParser>
  PassList(cl::desc("Optimizations available:"));

A better question to ask is, how do I do this with llvm-gcc? My perusal of
the code doesn't turn up any obvious places for options for alias analysis
are registered.

                                           -Dave

[Devang_Patel1]

As you've figured out, not all options are exposed by llvm-gcc. You'll have to update llvm-gcc.

[David_A_Greene]

So what's the right way to do this? There's the regalloc way, which invents
a whole new class just to register register allocators and provide an option
for picking one. But alias analysis already uses AnalysisGroup so a new class
to register alias analysis passes isn't necessary.

It seems desireable to augment AnalysisGroup with the ability to provide
command-line options. Is this a good strategy or is there a better way?

                                             -Dave

[clattner]

As you've figured out, not all options are exposed by llvm-gcc. You'll
have to update llvm-gcc.

So what's the right way to do this? There's the regalloc way, which invents
a whole new class just to register register allocators and provide an option
for picking one. But alias analysis already uses AnalysisGroup so a new class
to register alias analysis passes isn't necessary.

I'm not sure what you mean. The passmgr already fully supports this.

It seems desireable to augment AnalysisGroup with the ability to provide
command-line options. Is this a good strategy or is there a better way?

Command line options are already fully published by opt. llvm-gcc intentionally does not publish all of the llvm options through cc1. We can add new options, but that has to be an explicit design decision. We do allow you to use some options through -mllvm -foo, but that won't help in this case.

Also note that the current implementation of andersens is "research quality".

-Chris

[David_A_Greene]

> So what's the right way to do this? There's the regalloc way, which
> invents a whole new class just to register register allocators and
> provide an option for picking one. But alias analysis already uses
> AnalysisGroup so a new class to register alias analysis passes isn't
> necessary.

I'm not sure what you mean. The passmgr already fully supports this.

Regalloc doesn't use PassManager to handle its options. It uses a sort of
AnalysisGroup-like scheme to provide the -regalloc=foo option.

> It seems desireable to augment AnalysisGroup with the ability to provide
> command-line options. Is this a good strategy or is there a better way?

Command line options are already fully published by opt. llvm-gcc
intentionally does not publish all of the llvm options through cc1. We
can add new options, but that has to be an explicit design decision. We
do allow you to use some options through -mllvm -foo, but that won't help
in this case.

Also note that the current implementation of andersens is "research
quality".

Alias analysis is just the closest example of what I really need to do:
provide an option to choose a coalescer. I've got a scheme where
coalescers register with an AnalysisGroup (just like AA) and I need a
way to pick one at runtime. This really has nothing to do with llvm-gcc.
It's a question of how to provide command-line options for choosing
members of an AnalysisGroup where the trick used by opt is not available
(because one doesn't want to expose all of the passes as options).

opt does it by registering each Pass with a command-line option.
Regalloc does it in the special way described above (maybe this is
invokable from llvm-gcc since the cl_opt is a static but I haven't tried it).

My question is whether AnalysisGroup should provide a mechanism to
register command-line options. Then one could pick an alias analysis
with, for example, -alias=andersens. Or -coalscer=aggressive. Or even
-regalloc=linearscan if register allocation were recoded to use AnalysisGroup.

It would be a nice way to unify all of these things.

                                        -Dave

[clattner]

intentionally does not publish all of the llvm options through cc1. We
can add new options, but that has to be an explicit design decision. We
do allow you to use some options through -mllvm -foo, but that won't help
in this case.

Alias analysis is just the closest example of what I really need to do:
provide an option to choose a coalescer. I've got a scheme where
coalescers register with an AnalysisGroup (just like AA) and I need a
way to pick one at runtime. This really has nothing to do with llvm-gcc.
It's a question of how to provide command-line options for choosing
members of an AnalysisGroup where the trick used by opt is not available
(because one doesn't want to expose all of the passes as options).

Ah, I see ok. This is different then.

We don't want the users of the *c compiler* to be able to choose different coallescers. Having selectable coallescers is useful for two communities: 1) people hacking on the compiler 2) people building other tools with other constraints.

As far as the C compiler goes, we want to have just one option that works well, we don't want a million knobs people have to tweak.

We already service #2 through various means, so you really want to help out #1. This is exactly what the -mllvm option is for: to pass random stuff down into the llvm command line option stuff without exposing it to the users through a sanctioned option.

My question is whether AnalysisGroup should provide a mechanism to
register command-line options. Then one could pick an alias analysis
with, for example, -alias=andersens. Or -coalscer=aggressive. Or even
-regalloc=linearscan if register allocation were recoded to use AnalysisGroup.

Interesting question, I don't have an answer to this. To make things more complicated, you can have multiple instances of an analysis group and may want different things at different times:

   -basicaa -licm -something_that_invalidates_aa -andersaa -licm -whatever

In the short term, adding a cl::opt to llvm-backend.cpp seems the easiest way to go, which makes it available through -mllvm.

-Chris

[David_A_Greene]

As far as the C compiler goes, we want to have just one option that works
well, we don't want a million knobs people have to tweak.

Agreed.

Interesting question, I don't have an answer to this. To make things more
complicated, you can have multiple instances of an analysis group and may
want different things at different times:

   -basicaa -licm -something_that_invalidates_aa -andersaa -licm -whatever

Mmm...yeah, that makes life interesting.

In the short term, adding a cl::opt to llvm-backend.cpp seems the easiest
way to go, which makes it available through -mllvm.

Ok, I'll look at doing that. Thanks!

                                              -Dave

[David_A_Greene]

Interesting question, I don't have an answer to this. To make things more
complicated, you can have multiple instances of an analysis group and may
want different things at different times:

   -basicaa -licm -something_that_invalidates_aa -andersaa -licm -whatever

Some questions about that:

How does this interact with analysis groups? When a class is registered as
part of an analysis group there's a boolean template argument indicating
whether it is the default pass for the group. If I say -andersaa on the
command line (say it's the very first option), does that then make Andersen's
the new default alias analysis so that passes that declare a dependence on
AliasAnalysis will now get Andersen's instead of basicaa? Or do I really have
to put -andersaa after every option that could invalidate alias analysis?

From the comments in PassSupport.h, it sounds like the former is true.

Andersen's would be "available" and thus used.

However, what happens when alias analysis information gets invalidated?
Is Andersen's still "available" in the sense analysis groups use it?

If not, it seems it would be tough to make sure Andersen's is always
used everywhere that AliasAnalysis is asked for because there are passes
llvm runs without any command-line directive and those passes could
invalidate AA.

Or is it sufficient than an Andersen's object is constructed and that that
constitutes "availability?" What happens if multiple alias analyses are
constructed? Is the most-recently constructed one considered the "available"
one?

                                               -Dave

[Devang_Patel1]

However, what happens when alias analysis information gets invalidated?

Is Andersen’s still “available” in the sense analysis groups use it?

If not, it seems it would be tough to make sure Andersen’s is always

used everywhere that AliasAnalysis is asked for because there are passes

llvm runs without any command-line directive and those passes could

invalidate AA.

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

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.

Note, the goal of analysis group is to select desired analysis implementations during entire run of optimizer. I do think it is designed to handle cases where during one instance of optimizer multiple instances of analysis implementations are used simultaneously. 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.

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

[Devang_Patel1]

Oops. I meant …

" I do not think it is designed to handle …

[David_A_Greene]

> 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::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

[David_A_Greene]

I found a fairly elegant way to do this. I implemented what I imagine
FilteredPassNameParser would be. If all goes well I'll post a patch for
discussion.

                                                 -Dave

[David_A_Greene]

And here it is. It seems to work well. Should I commit it?

                                            -Dave

//===----------------------------------------------------------------------===//
// FilteredPassNameParser class - Make use of the pass registration
// mechanism to automatically add a command line argument to opt for
// each pass that satisfies a filter criteria. Filter should return
// true for passes to be registered as command-line options.
//
template<typename Filter>
class FilteredPassNameParser : public PassNameParser {
private:
  Filter filter;

public:
  bool ignorablePassImpl(const PassInfo *P) const { return !filter(*P); }
};

//===----------------------------------------------------------------------===//
// PassArgFilter - A filter for use with PassNameFilterParser that only
// accepts a Pass whose Arg matches certain strings.
//
// Use like this:
//
// extern const char AllowedPassArgs = "-anders_aa -dse";
//
// static cl::list<
// const PassInfo*,
// bool,
// FilteredPassNameParser<PassArgFilter<AllowedPassArgs> > >
// PassList(cl::desc("LLVM optimizations available:"));
//
// Only the -anders_aa and -dse options will be available to the user.
//
template<const char *Args>
class PassArgFilter {
public:
  bool operator()(const PassInfo &P) const {
    return std::strstr(Args, P.getPassArgument()) != 0;
  }
};

[David_A_Greene]

Ah, Friday.

Before you C++ zealots point out that Args could contain strings that an
unrelated Pass might match (for example, Args="not-so-bad-aa" matched against
a pass "bad-aa"), let _this_ C++ zealot point out that the proper way to
handle that is through typelists and metaprogramming and that the complexity
of that is probably not going into llvm any time soon.

Have a great weekend all!

                                           -Dave

[Devang_Patel1]

Is this the complete patch ?

As I understand you want to add llvm-gcc command line option, -register-coalescing=<value> where value is either simple or conservative or whatever.

In this case you need to get this through llvm-gcc's (i.e. GCC's) command line options processing. So, why not take advantage of GCC's command line processing setup ? See how -Wformat or Wnormalized or other command line option are handled (start from c.opt). Once llvm-gcc has processed your new command line option all you need to do in llvm-backend.cpp is insert opt level option in llvm_initialize_backend(). See how --dsiable-fp-elim is inserted in the pipeline.

[David_A_Greene]

> And here it is. It seems to work well. Should I commit it?

Is this the complete patch ?

Well, it's not a properly formatted patch, or course, but it is all of the
code that's needed.

As I understand you want to add llvm-gcc command line option, -
register-coalescing=<value> where value is either simple or
conservative or whatever.

No, this isn't for llvm-gcc _per_se_. It's for anyone that wants to register
some passes as command line options but not others. It could be used
by a wide variety of tools. One of those could be llvm-gcc, but that's for
someone else to do.

In this case you need to get this through llvm-gcc's (i.e. GCC's)
command line options processing. So, why not take advantage of GCC's
command line processing setup ?

Because this isn't targeted only at gcc. I don't even have a modified
llvm-gcc. I'm putting this to use in another tool.

                                     -Dave