[llvm][MachineOutliner] Add support for repeating machine outliner N times.

[plotfi]

Summary

This has been discussed for a while now, that rerunning the outliner can have some size wins.
So I am posting this change for review to address this.

Special Thanks to Kyungwoo Lee for experimenting on this.

[paquette]

This is pretty cool, thanks for working on this.

This needs a couple tests. A few things I can think of:

1. Show that the outliner will stop when there are no changes, even if you haven't run the specified number of rounds
2. Show that adding extra iterations actually produces more outlining
3. Show what happens when you outline from an outlined function

I think that the easiest way to test (1) is to add some debug output which we can test. E.g. "did not outline on iteration <iteration> out of <number of iterations>"

Also, do you think you could test the code size + compile time impact of this patch on CTMark at -Oz for AArch64? I think that two or three data points would be sufficient. Say, 1 round versus 2 rounds versus 5 rounds versus 10 rounds.

(If it turns out that compile time is an issue, I suspect we might be able to save *some* time by keeping track of which functions and basic blocks can never be outlined from, for example.)

It would also be nice to know how many rounds on average this provides benefit for. I think 1 iteration is the correct default; this is more for my own curiosity.

llvm/lib/CodeGen/MachineOutliner.cpp

100

Maybe "outlining-iterations" to imply that it's something plural?

100

What should happen if this is set to 0? Is there a way to specify a minimum value here?

903

We can probably just remove the entire comment from runOnModule now, since it would all be folded into the comment on doOutline

907

\p M

1438

I don't think this if is necessary. Since Iterations is 1 by default, the loop should only run once when Iterations is not specified.

1441–1445

I think this can be simplified:

for(...)
  if (!doOutline(M))
    return false;
return true;

[plotfi]

llvm/lib/CodeGen/MachineOutliner.cpp

100

I changed it to "outliner-reruns", so 0 just means don't do any reruns. This way it has to run the outliner at least once.

1438

I've decided for now that it would be good to keep the reruning aspect of this patch separate from the existing behavior. I'm still looking to add some good tests here, stay tuned.

[tellenbach]

I'd actually prefer an option outliner-runs that is defaulted to 1 rather than a rerun option. From a user perspective I'd be unclear what outliner-reruns=0 exactly means? Does that mean one run or zero?

As @paquette already said this definitely needs tests for all supported targets. I just want to mention that an outlined function doesn't run through the ordinary lowering passes so some information might be missing that the outliner relies on.

A first example that comes to my mind: My patch https://reviews.llvm.org/D69097 introduces return address signing for outlined functions on AArch64 targets. However, these functions currently get signed based on the signing behaviour of candidates rather than their own signing-related function attributes. The outlined functions actually do not even have these attributes. That means a rerun of the outliner would not catch up that the outlined function has been signed and that a new outlined function could also need signing.

[tellenbach]

llvm/lib/CodeGen/MachineOutliner.cpp

99

Could this be renamed to something like machine-outliner-[re]runs? I find an option outliner... to be somewhat ambiguous (there is e.g. outlining during HotColdSpilling) and the prefix machine would be more consistent here.

[plotfi]

llvm/lib/CodeGen/MachineOutliner.cpp

99

Sounds good to me. Although, this is explicitly reruns. When it is set to 0, there should be only one run. I don't think it makes sense to enable the pass and have a flag where it does not run.

[tellenbach]

Reverse ping: Is this revision still active?

D71027 introduces similar functionality so a short clarification on the status of D69446 would be appreciated.

Thanks!

llvm/lib/CodeGen/MachineOutliner.cpp

 // functions. Since the outliner is confined to a single module (modulo LTO),
 // this is off by default. It should, however, be the default behaviour in
 // LTO.
 static cl::opt<bool> EnableLinkOnceODROutlining(
     "enable-linkonceodr-outlining", cl::Hidden,
     cl::desc("Enable the machine outliner on linkonceodr functions"),
     cl::init(false));
 
+static cl::opt<unsigned> OutlinerReruns(
+    "outliner-reruns", cl::init(0), cl::Hidden,
+    cl::desc(
+        "Number of times to rerun the outliner after the initial outline"));
+
 namespace {
 
 /// Represents an undefined index in the suffix tree.
 const unsigned EmptyIdx = -1;
 
 /// A node in a suffix tree which represents a substring or suffix.
 ///
 /// Each node has either no children or at least two children, with the root
bool outline(Module &M, std::vector<OutlinedFunction> &FunctionList,
                InstructionMapper &Mapper, unsigned &OutlinedFunctionNum);
 
   /// Creates a function for \p OF and inserts it into the module.
   MachineFunction *createOutlinedFunction(Module &M, OutlinedFunction &OF,
                                           InstructionMapper &Mapper,
                                           unsigned Name);
 
   /// Calls 'doOutline()'.
   bool runOnModule(Module &M) override;
 
   /// Construct a suffix tree on the instructions in \p M and outline repeated
   /// strings from that tree.
   bool doOutline(Module &M, unsigned &OutlinedFunctionNum);
 
   /// Return a DISubprogram for OF if one exists, and null otherwise. Helper
   /// function for remark emission.
   DISubprogram *getSubprogramOrNull(const OutlinedFunction &OF) {
     DISubprogram *SP;
     for (const Candidate &C : OF.Candidates)
       if (C.getMF() && (SP = C.getMF()->getFunction().getSubprogram()))
         return SP;
bool MachineOutliner::runOnModule(Module &M) {
   if (M.empty())
     return false;
 
   // Number to append to the current outlined function.
   unsigned OutlinedFunctionNum = 0;
 
   if (!doOutline(M, OutlinedFunctionNum))
     return false;
+
+  for (unsigned I = 0; I < OutlinerReruns; ++I)
+    if (!doOutline(M, OutlinedFunctionNum))
+      return true;
+
   return true;
 }
 
 bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
   MachineModuleInfo &MMI = getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
 
   // If the user passed -enable-machine-outliner=always or
   // -enable-machine-outliner, the pass will run on all functions in the module.
   // Otherwise, if the target supports default outlining, it will run on all
   // functions deemed by the target to be worth outlining from by default. Tell
   // the user how the outliner is running.
   LLVM_DEBUG({
     dbgs() << "Machine Outliner: Running on ";
     if (RunOnAllFunctions)