Some questions about phase ordering in OPT and LLC

Ricardo_Nobre · May 9, 2016, 5:43pm

Hi,

I'm a PhD student doing phase ordering as part of my PhD topic and I would like to ask some questions about LLVM.

Executing the following command to see what passes does OPT execute when targeting a SPARC V8 processor:

/opt/clang+llvm-3.7.1-x86_64-linux-gnu-ubuntu-15.10/bin/llvm-as < /dev/null | /opt/clang+llvm-3.7.1-x86_64-linux-gnu-ubuntu-15.10/bin/opt -O3 -march=sparc -mcpu=v8 -disable-output -debug-pass=Arguments

I get the following output:
Pass Arguments: -tti -no-aa -tbaa -scoped-noalias -assumption-cache-tracker -targetlibinfo -basicaa -verify -simplifycfg -domtree -sroa -early-cse -lower-expect
Pass Arguments: -targetlibinfo -tti -no-aa -tbaa -scoped-noalias -assumption-cache-tracker -basicaa -ipsccp -globalopt -deadargelim -domtree -instcombine -simplifycfg -basiccg -prune-eh -inline-cost -inline -functionattrs -argpromotion -domtree -sroa -early-cse -lazy-value-info -jump-threading -correlated-propagation -simplifycfg -domtree -instcombine -tailcallelim -simplifycfg -reassociate -domtree -loops -loop-simplify -lcssa -loop-rotate -licm -loop-unswitch -instcombine -scalar-evolution -loop-simplify -lcssa -indvars -loop-idiom -loop-deletion -loop-unroll -mldst-motion -domtree -memdep -gvn -memdep -memcpyopt -sccp -domtree -bdce -instcombine -lazy-value-info -jump-threading -correlated-propagation -domtree -memdep -dse -loops -loop-simplify -lcssa -licm -adce -simplifycfg -domtree -instcombine -barrier -float2int -domtree -loops -loop-simplify -lcssa -loop-rotate -branch-prob -block-freq -scalar-evolution -loop-accesses -loop-vectorize -instcombine -scalar-evolution -slp-vectorizer -simplifycfg -domtree -instcombine -loops -loop-simplify -lcssa -scalar-evolution -loop-unroll -instcombine -loop-simplify -lcssa -licm -scalar-evolution -alignment-from-assumptions -strip-dead-prototypes -elim-avail-extern -globaldce -constmerge -verify

Why are there two "Pass Arguments"?
What does it mean?

What passes should I pass the 'opt' tool (the LLVM Optimizer) so that it is equivalent to the use of -O3 with 'opt'?
The ones of the first "Pass Arguments", or the second?

I'm testing different phase orders, and one of the exploration schemes I want to try is to start with the equivalent of -O3 and iteratively apply small changes (e.g. swap passes in the compiler pass sequence equivalent to -O3), and compile and test with those different sequences.

Additionally, I'm a bit confused about what passes does 'llc' (the LLVM static compiler) apply by default, when passing to it a LLVM IR previously optimized using the 'opt' tool.

'llc --help' says that the default is -O2:
"Optimization level. [-O0, -O1, -O2, or -O3] (default = '-O2')"

But is this -O2 the same as the -O2 from the 'opt' tool?

Does it mean that if I generate an optimized LLVM IR with 'opt' (with -O2) and pass it to 'llc', it will by default apply all passes in -O2 a second time?
Or do 'opt -O2' and 'llc -O2' represent different passes?

Thanks in advance,
Ricardo

mehdi_amini · May 9, 2016, 8:07pm

Hi,

I'm a PhD student doing phase ordering as part of my PhD topic and I would like to ask some questions about LLVM.

Executing the following command to see what passes does OPT execute when targeting a SPARC V8 processor:

/opt/clang+llvm-3.7.1-x86_64-linux-gnu-ubuntu-15.10/bin/llvm-as < /dev/null | /opt/clang+llvm-3.7.1-x86_64-linux-gnu-ubuntu-15.10/bin/opt -O3 -march=sparc -mcpu=v8 -disable-output -debug-pass=Arguments

I get the following output:
Pass Arguments: -tti -no-aa -tbaa -scoped-noalias -assumption-cache-tracker -targetlibinfo -basicaa -verify -simplifycfg -domtree -sroa -early-cse -lower-expect
Pass Arguments: -targetlibinfo -tti -no-aa -tbaa -scoped-noalias -assumption-cache-tracker -basicaa -ipsccp -globalopt -deadargelim -domtree -instcombine -simplifycfg -basiccg -prune-eh -inline-cost -inline -functionattrs -argpromotion -domtree -sroa -early-cse -lazy-value-info -jump-threading -correlated-propagation -simplifycfg -domtree -instcombine -tailcallelim -simplifycfg -reassociate -domtree -loops -loop-simplify -lcssa -loop-rotate -licm -loop-unswitch -instcombine -scalar-evolution -loop-simplify -lcssa -indvars -loop-idiom -loop-deletion -loop-unroll -mldst-motion -domtree -memdep -gvn -memdep -memcpyopt -sccp -domtree -bdce -instcombine -lazy-value-info -jump-threading -correlated-propagation -domtree -memdep -dse -loops -loop-simplify -lcssa -licm -adce -simplifycfg -domtree -instcombine -barrier -float2int -domtree -loops -loop-simplify -lcssa -loop-rotate -branch-prob -block-freq -scalar-evolution -loop-accesses -loop-vectorize -instcombine -scalar-evolution -slp-vectorizer -simplifycfg -domtree -instcombine -loops -loop-simplify -lcssa -scalar-evolution -loop-unroll -instcombine -loop-simplify -lcssa -licm -scalar-evolution -alignment-from-assumptions -strip-dead-prototypes -elim-avail-extern -globaldce -constmerge -verify

Why are there two "Pass Arguments"?
What does it mean?

There are two PassManager instantiated and ran on the IR. I am not aware of a good reason for that (the first one is created with PassManagerBuilder::populateFunctionPassManager() and the second one with PassManagerBuilder::populateModulePassManager()).

You can look at AddOptimizationPasses() in opt.cpp.

What passes should I pass the 'opt' tool (the LLVM Optimizer) so that it is equivalent to the use of -O3 with 'opt'?
The ones of the first "Pass Arguments", or the second?

Both, with two separate opt invocation...

I'm testing different phase orders, and one of the exploration schemes I want to try is to start with the equivalent of -O3 and iteratively apply small changes (e.g. swap passes in the compiler pass sequence equivalent to -O3), and compile and test with those different sequences.

Additionally, I'm a bit confused about what passes does 'llc' (the LLVM static compiler) apply by default, when passing to it a LLVM IR previously optimized using the 'opt' tool.

'llc --help' says that the default is -O2:
"Optimization level. [-O0, -O1, -O2, or -O3] (default = '-O2')"

But is this -O2 the same as the -O2 from the 'opt' tool?

Does it mean that if I generate an optimized LLVM IR with 'opt' (with -O2) and pass it to 'llc', it will by default apply all passes in -O2 a second time?
Or do 'opt -O2' and 'llc -O2' represent different passes?

The optimization level for llc has nothing to do with opt, it controls only the codegen (target specific). In any case, llc won't re-run the optimizer pipeline.

See llc.cpp, the logic is easy to follow.

  CodeGenOpt::Level OLvl = CodeGenOpt::Default;
  switch (OptLevel) {
  default:
    errs() << argv[0] << ": invalid optimization level.\n";
    return 1;
  case ' ': break;
  case '0': OLvl = CodeGenOpt::None; break;
  case '1': OLvl = CodeGenOpt::Less; break;
  case '2': OLvl = CodeGenOpt::Default; break;
  case '3': OLvl = CodeGenOpt::Aggressive; break;
  }

serge_guelton2 · May 9, 2016, 9:31pm

As far as I understand, the two passmanager do not interleave their
passes. It first runs all the function passes and below. Then all the
module passes. So if you specify:

opt -mymodulepass0 -myfunctionpass -mymodulepass1

What you actually get is:

1. myfunctionpass on each function
2. mymodulepass0
3. mymodulepass0

mehdi_amini · May 9, 2016, 9:55pm

(I assume your 3 was intended to be mymodulepass1 right?)

So AFAIK no, you should get the order you specified on the command line, i.e.

1. mymodulepass0
2. myfunctionpass on each function
3. mymodulepass1

serge_guelton2 · May 10, 2016, 5:16am

>> You can look at AddOptimizationPasses() in opt.cpp.
>
> As far as I understand, the two passmanager do not interleave their
> passes. It first runs all the function passes and below. Then all the
> module passes. So if you specify:
>
> opt -mymodulepass0 -myfunctionpass -mymodulepass1
>
> What you actually get is:
>
> 1. myfunctionpass on each function
> 2. mymodulepass0
> 3. mymodulepass0

(I assume your 3 was intended to be mymodulepass1 right?)

(yes)

So AFAIK no, you should get the order you specified on the command line, i.e.

1. mymodulepass0
2. myfunctionpass on each function
3. mymodulepass1

MMMh, from opt.cpp, there's a first call to:

  if (OptLevelO1 || OptLevelO2 || OptLevelOs || OptLevelOz || OptLevelO3) {
    FPasses->doInitialization();
    for (Function &F : *M)
      FPasses->run(F);
    FPasses->doFinalization();
  }

then a few lines later, a call to:

Passes.run(*M);

where Passes is the Module pass Manager and FPasses is the Function Pass
Manager. Each is filled in AddOptimizationPasses with different passes.
I don't see the point where the two manage interleave their passes.

mehdi_amini · May 10, 2016, 3:35pm

It seems like we need to clarify that we're talking about the same thing: i.e. opt -O3 or opt -mypass?

The code you show correspond to the two separated pass managers I was mentioning in my first answer about how to read the output of -debug-pass=Arguments for opt -O3. As you can see in the if condition in the snippet you post, it is only used when a -O is passed to opt, and not when you invoke opt using ` opt -mymodulepass0 -myfunctionpass -mymodulepass1`.

The terminology is a bit confusing because "Function Pass Manager" can also correspond to "class FunctionPassManager".
Indeed when you're invoking `opt -mymodulepass0 -myfunctionpass -mymodulepass1`, here is what happens:
- a PassManager is created
- mymodulepass0 is inserted in the PassManager
- when myfunctionpass is added to the same PassManager, because it is a FunctionPass, there is an implicit FunctionPassManager which is created to wrap it (see FunctionPass::assignPassManager()). The FunctionPassManager offers a "ModulePass" like interface and can be added in the same PassManager as mymodulepass0.
- mymodulepass1 is inserted in the PassManager. If you added another function pass before, it would be in the same FunctionPassManager (there is some magic to find the most nested PassManager that can accommodate the pass you are adding, see FunctionPass::assignPassManager() again).

-debug-pass=Structure helps to represent the pass manager nesting:

$ echo "" | opt -globalopt -instcombine -reassociate -globalopt -debug-pass=Structure -o /dev/null
Pass Arguments: -targetlibinfo -assumption-cache-tracker -globalopt -domtree -instcombine -reassociate -globalopt -verify -verify-di
Target Library Information
Assumption Cache Tracker
  ModulePass Manager
    Global Variable Optimizer
    FunctionPass Manager
      Dominator Tree Construction
      Combine redundant instructions
      Reassociate expressions
    Global Variable Optimizer
    FunctionPass Manager
      Module Verifier
    Debug Info Verifier
    Bitcode Writer

You can see that "Combine redundant instructions" (-instcombine) and "Reassociate expressions" (-reassociate) are handled by a "FunctionPass Manager" nested in a "ModulePass Manager". You can also see that "Global Variable Optimizer" (-globalopt) runs before and after the two function passes.

Cheers,

Mehdi

serge_guelton2 · May 12, 2016, 4:03pm

That's a perfect clarification, thanks a lot o/

solidak · April 6, 2020, 3:52pm

Hey,

I'm writing an LLVM function pass. So far, the "Programmer's Manual" was a tremendous help.

I have a function `foo(int a, int b)`, where in some instances, I'll need to replace it's call with `bar(int a, int b)`.

The way I wanted to do it is to basically:
* Locate the `foo()` I need to replace
* Make a `CallInst` to `bar()`
* Populate `CallInst::Create` with the arguments of `foo()`
* Make a call to `ReplaceInstWithInst()` to have it work

Everything is working just fine, but the arguments of `foo()` are not getting copied to `bar()`. When the replacement call is executed, the arguments of `bar()` are just null.

Here's the relevant code:

bool runOnFunction(Function& F) override
{
     CallInst* call_to_foo = 0;
     Function* foo_func = 0;

     /*
     Loop over all calls in the function and populate foo_func when you find it.

     If we reached below, that means the current function we're in has a call to
     foo() (inside call_to_foo) that we need to replace with bar(). Also, foo_func
     is pointing to a foo Function
     */

     Function* bar_func = get_bar_func();

     // Collect foo args
     // I believe here is the issue: the arguments are not copied
     //  properly or there must be a deep-copy of sorts for it to work
     std::vector<Value*> bar_func_args;
     for (size_t i = 0; i < foo_func->arg_size(); i++) {
         Argument* arg = foo_func->arg_begin() + i;
         bar_func_args.push_back(arg);
     }

     auto* inst_to_replace = CallInst::Create(
         bar_func, ArrayRef<Value*>(bar_func_args),
         "bar_func");

     ReplaceInstWithInst(
     call_inst->getParent()->getInstList(),
     BBI, inst_to_replace);

     return true;
}

Any help would be tremendously appreciated.

topperc · April 9, 2020, 2:19am

Is foo_func a Function*? If so that’s just the function declaration. You need to copy the arguments from the CallInst that calls foo.

solidak · April 14, 2020, 9:10pm

Hey Craig. Thank you for answering my question. You’re correct, I did stupid and used the arguments from the Function*. The arguments of the CallInst worked perfectly.

Many thanks!