Support repeated machine outlining

[jinlin]

Summary

The following change is to allow the machine outlining can be applied for Nth times, where N is specified by the compiler option. By default the value of N is 1. The motivation is that the repeated machine outlining can further reduce code size. Please refer to the presentation "Improving Swift Binary Size via Link Time Optimization" in LLVM Developers' Meeting in 2019.

[tellenbach]

Hi,

D69446 seems to introduce something similar. Are these patches related or is this just coincidence?

[jinlin]

In D71027#1772074, @tellenbach wrote:

Hi,

D69446 seems to introduce something similar. Are these patches related or is this just coincidence?

Thank you for pointing out this. It could be by coincidence. I have presented this in LLVM Developers' Meeting in 10/22/2019. I didn't realize someone submitted D69446 on 10/25/2019.

In D71027, I have also fixed incorrect logic in maintaining the side-effect information for outlined function at line 1295. This bug shows up during repeated machine outliner.

Please let me know if you have any questions.

[tellenbach]

Okay, thanks for clarifying.

In D71027#1772142, @jinlin wrote:

In D71027, I have also fixed incorrect logic in maintaining the side-effect information for outlined function at line 1295. This bug shows up during repeated machine outliner.

Would it be possible to separate both patches? The fix can then be reviewed independently from repeated outlining itself.

[jinlin]

In D71027#1774949, @tellenbach wrote:

Okay, thanks for clarifying.

In D71027#1772142, @jinlin wrote:

In D71027, I have also fixed incorrect logic in maintaining the side-effect information for outlined function at line 1295. This bug shows up during repeated machine outliner.

Would it be possible to separate both patches? The fix can then be reviewed independently from repeated outlining itself.

Sure. I have updated the patch. Please note that the repeating machine outliner may not work correctly without fixing the logic at line 1265.

[tellenbach]

In D71027#1775515, @jinlin wrote:

Sure. I have updated the patch. Please note that the repeating machine outliner may not work correctly without fixing the logic at line 1265.

Thanks! I've commented on D69446 to see if the revision is still active. So I suggest giving this some more time.

[jinlin]

In D71027#1775926, @tellenbach wrote:

In D71027#1775515, @jinlin wrote:

Sure. I have updated the patch. Please note that the repeating machine outliner may not work correctly without fixing the logic at line 1265.

Thanks! I've commented on D69446 to see if the revision is still active. So I suggest giving this some more time.

Is there any update for D69446? I am writing the test case for D71217. The changes D71027 have to be checked in first. Thanks.

[tellenbach]

In D71027#1862192, @jinlin wrote:

Is there any update for D69446? I am writing the test case for D71217. The changes D71027 have to be checked in first. Thanks.

Unfortunately no update so far. If it's okay for the other reviewers (@paquette @aschwaighofer) I suggest reviewing @jinlin 's patches.

[jinlin]

Update the test from IR file to MIR file.

[jinlin]

Simplified the test case.

[paquette]

llvm/lib/CodeGen/MachineOutliner.cpp

1511–1513

I think that allowing the number of repeats to be 0 is unintuitive.

Would it be possible to output an error when the number of repeats is less than 1 instead of silently changing it?

1516–1518

Can you add some debug output here that says why the outliner stopped running?

E.g.

• "Stopped outlining because I >= NumRepeats"
• "Stopped outlining at iteration I because no changes were found"

This debug output could then be used in a separate testcase showing that repeated outlining terminates as expected.

llvm/test/CodeGen/AArch64/machine-outliner-iterative.mir

66–72

The IR instructions inside each of the IR functions here should not be necessary.

[jinlin]

llvm/lib/CodeGen/MachineOutliner.cpp

1511–1513

Done.

1516–1518

Done.

llvm/test/CodeGen/AArch64/machine-outliner-iterative.mir

66–72

Please let me know how to make it work. Initially I used those instructions to generate the first iteration machine outlining functions. If I simply remove them, it will not work.

[jinlin]

llvm/test/CodeGen/AArch64/machine-outliner-iterative.mir

66–72

Now I understand what you mean. I have updated the test based on your suggestions. Thank you.

[tellenbach]

llvm/lib/CodeGen/MachineOutliner.cpp

102

Could we rename this to something like machine-outline-repeat-counts or machine-outline-runs? The term outlining itself is somewhat ambigious and the prefix machine would be more consistent.

103

Same here: I suggest something like *...to apply machine outlining*

[tellenbach]

llvm/lib/CodeGen/MachineOutliner.cpp

1511

Why is this indirection necessary?

llvm/test/CodeGen/AArch64/machine-outliner-iterative.mir

2

Could you run this test with a higher number for -outline-repeat-count to verfiy that the outlining stops when no changes are found and nothing changes (beside the name of the outlined functions)?

[jinlin]

llvm/lib/CodeGen/MachineOutliner.cpp

102

Done.

103

Done.

1511

I have removed this extra variable.

[jinlin]

llvm/test/CodeGen/AArch64/machine-outliner-iterative.mir

2

I have updated the test case to verify that no more machine outlining is performance after the iteration is greater than 2.

[tellenbach]

LGTM, but let's wait a bit for other comments.

[paquette]

llvm/test/CodeGen/AArch64/machine-outliner-iterative.mir

2–3

I think that it would make sense to use different check prefixes for each level of outlining. That would make it easier to show explicitly what happens when you add extra iterations.

# RUN: llc -mtriple=aarch64--- -run-pass=prologepilog -run-pass=machine-outliner -machine-outline-runs=2 -verify-machineinstrs %s -o - | FileCheck %s --check-prefix TWO-RUNS

# RUN: llc -mtriple=aarch64--- -run-pass=prologepilog -run-pass=machine-outliner -machine-outline-runs=4 -verify-machineinstrs %s -o - | FileCheck %s --check-prefix FOUR-RUNS

Also you shouldn't need --run-pass=prologepilog here.

114–116

Can you check which instructions are in these functions?

[jinlin]

llvm/test/CodeGen/AArch64/machine-outliner-iterative.mir

2–3

Done.

114–116

Done.

[paquette]

Thanks for updating this!

I have a couple nits, but I think this is pretty close to being ready. :)

llvm/lib/CodeGen/MachineOutliner.cpp

1513

Grammar nit: "Expect NumRepeat for machine outlining to be greater than or equal to 1"

1517

Nit: pull I into the loop:

for (unsigned I = 0; I < NumRepeat; I++) {
 // ...
}

1519–1520

Can we have a small testcase showing that this happens?

1525–1526

Can we have a small testcase showing that this happens?

llvm/test/CodeGen/AArch64/machine-outliner-iterative.mir

140–141

Can you add a comment explaining why these functions are not expected?

[jinlin]

llvm/lib/CodeGen/MachineOutliner.cpp

1513

Done.

llvm/test/CodeGen/AArch64/machine-outliner-iterative.mir

140–141

Done.

[jinlin]

llvm/lib/CodeGen/MachineOutliner.cpp

1517

Done.

1519–1520

The prefix FOUR-RUN shows that the machine outliner stops at 3rd iteration since no changes were found.

1525–1526

The prefix ONE-RUN shows that the machine outliner stops at 1st first iteration since NumRepeat is 1.

[paquette]

LGTM!

[jinlin]

In D71027#1925639, @paquette wrote:

LGTM!

Thank you Jessica and David for reviewing my changes. Appreciate your excellent suggestions.

[jinlin]

I have made minor changes in test case llvm/test/CodeGen/AArch64/machine-outliner-iterative.mir.

[jinlin]

Testing Time: 128.22s

Expected Passes    : 36105
Expected Failures  : 163
Unsupported Tests  : 336

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));
 
+// Set the number of times to repeatedly apply outlining.
+// Defaults to 1, but more repetitions can save additional size.
+static cl::opt<unsigned>
+    NumRepeat("machine-outline-runs", cl::Hidden,
+              cl::desc("The number of times to apply machine outlining"),
+              cl::init(1));
+
 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

 struct MachineOutliner : public ModulePass {
 
   static char ID;
 
   /// Set to true if the outliner should consider functions with
   /// linkonceodr linkage.
   bool OutlineFromLinkOnceODRs = false;
 
+  /// The current repeat number of machine outlining.
+  unsigned OutlineRepeatedNum = 0;
+
   /// Set to true if the outliner should run on all functions in the module
   /// considered safe for outlining.
   /// Set to true by default for compatibility with llc's -run-pass option.
   /// Set when the pass is constructed in TargetPassConfig.
   bool RunOnAllFunctions = true;
 
   StringRef getPassName() const override { return "Machine Outliner"; }
 
struct MachineOutliner : public ModulePass {
   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()'.
+  /// Calls runOnceOnModule NumRepeat times
   bool runOnModule(Module &M) override;
 
+  /// Calls 'doOutline()'.
+  bool runOnceOnModule(Module &M, unsigned Iter);
+
   /// 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) {
     for (const Candidate &C : OF.Candidates)

 }
 
 MachineFunction *MachineOutliner::createOutlinedFunction(
     Module &M, OutlinedFunction &OF, InstructionMapper &Mapper, unsigned Name) {
 
   // Create the function name. This should be unique.
   // FIXME: We should have a better naming scheme. This should be stable,
   // regardless of changes to the outliner's cost model/traversal order.
-  std::string FunctionName = ("OUTLINED_FUNCTION_" + Twine(Name)).str();
+  std::string FunctionName;
+  if (OutlineRepeatedNum > 0)
+    FunctionName = ("OUTLINED_FUNCTION_" + Twine(OutlineRepeatedNum + 1) + "_" +
+                    Twine(Name))
+                       .str();
+  else
+    FunctionName = ("OUTLINED_FUNCTION_" + Twine(Name)).str();
 
   // Create the function using an IR-level function.
   LLVMContext &C = M.getContext();
   Function *F = Function::Create(FunctionType::get(Type::getVoidTy(C), false),
                                  Function::ExternalLinkage, FunctionName, M);
 
   // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
   // which gives us better results when we outline from linkonceodr functions.
MORE.emit([&]() {
                                                     FnCountAfter)
         << "; Delta: "
         << DiagnosticInfoOptimizationBase::Argument("Delta", FnDelta);
       return R;
     });
   }
 }
 
-bool MachineOutliner::runOnModule(Module &M) {
+bool MachineOutliner::runOnceOnModule(Module &M, unsigned Iter) {
   // Check if there's anything in the module. If it's empty, then there's
   // nothing to outline.
   if (M.empty())
     return false;
 
+  OutlineRepeatedNum = Iter;
+
   // Number to append to the current outlined function.
   unsigned OutlinedFunctionNum = 0;
 
   if (!doOutline(M, OutlinedFunctionNum))
     return false;
   return true;
 }
 
bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {
   // If we outlined something, we definitely changed the MI count of the
   // module. If we've asked for size remarks, then output them.
   // FIXME: This should be in the pass manager.
   if (ShouldEmitSizeRemarks && OutlinedSomething)
     emitInstrCountChangedRemark(M, MMI, FunctionToInstrCount);
 
   return OutlinedSomething;
 }
+
+// Apply machine outlining for NumRepeat times.
+bool MachineOutliner::runOnModule(Module &M) {
+  if (NumRepeat < 1)
+    report_fatal_error("Expect NumRepeat for machine outlining "
+                       "to be greater than or equal to 1!\n");
+
+  bool Changed = false;
+  for (unsigned I = 0; I < NumRepeat; I++) {
+    if (!runOnceOnModule(M, I)) {
+      LLVM_DEBUG(dbgs() << "Stopped outlining at iteration " << I
+                        << " because no changes were found.\n";);
+      return Changed;
+    }
+    Changed = true;
+  }
+  LLVM_DEBUG(dbgs() << "Stopped outlining because iteration is "
+                       "equal to " << NumRepeat << "\n";);
+  return Changed;
+}

llvm/test/CodeGen/AArch64/machine-outliner-iterative.mir

+# RUN: llc -mtriple=aarch64--- -run-pass=machine-outliner -machine-outline-runs=2 -verify-machineinstrs %s -o - | FileCheck %s --check-prefix TWO-RUNS
+# RUN: llc -mtriple=aarch64--- -run-pass=machine-outliner -machine-outline-runs=1 -verify-machineinstrs %s -o - | FileCheck %s --check-prefix ONE-RUN
+# RUN: llc -mtriple=aarch64--- -run-pass=machine-outliner -machine-outline-runs=4 -verify-machineinstrs %s -o - | FileCheck %s --check-prefix FOUR-RUNS
+
+# Example of Repeated Instruction Sequence - Iterative Machine Outlining
+#
+#; define void @"$s12"(...) {         define i64 @"$s5” (...) {             define void @"$s13"(...) {
+#   ...                                ...                                   ...
+#   %8 = load i1, i1* %7                                                     %8 = load i1, i1* %7
+#   %9 = load i4, i4*, %6              %9 = load i4, i4*, %6                 %9 = load i4, i4*, %6
+#   store i4 %9, i4* %5                store i4 %9, i4* %5                   store i4 %9, i4* %5
+#   ...                                ...                                   ...
+# }                                  }                                     }
+#
+# After machine outliner (1st time)
+#
+# define void @"$s12"(...) {         define i64 @"$s5” (...) {             define void @"$s13"(...) {
+#   ...                                ...                                   ...
+#   %8 = load i1, i1* %7                                                     %8 = load i1, i1* %7
+#   call void @outlined_function_1_1   call void @outlined_function_1_1      call void @outlined_function_1_1
+#   ...                                ...                                   ...
+# }                                  }                                     }
+#
+# After machine outliner (2nd time)
+#
+# define void @"$s12"(...) {         define i64 @"$s5” (...) {             define void @"$s13"(...) {
+#   ...                                ...                                   ...
+#   call void @outlined_function_2_1   call void @outlined_function_1_1      call void @outlined_function_2_1
+#   ...                                ...                                   ...
+# }                                  }                                     }
+#
+# Check whether machine outliner can further find the outlining opportunity after machine
+# outlining has performed.
+#
+--- |
+  target triple = "aarch64-apple-darwin"
+
+  declare void @foo() local_unnamed_addr
+
+  declare void @widget() local_unnamed_addr
+
+  ; Function Attrs: minsize noredzone optsize
+  define void @baz.14() #0 {
+    ret void
+  }
+
+  ; Function Attrs: minsize noredzone optsize
+  define void @baz.15() #0 {
+    ret void
+  }
+
+  ; Function Attrs: minsize noredzone optsize
+  define void @baz.16() #0 {
+    ret void
+  }
+
+  attributes #0 = { minsize noredzone optsize }
+...
+---
+name:            baz.14
+tracksRegLiveness: true
+stack:
+  - { id: 0, offset: -8, size: 8 }
+  - { id: 1, offset: -16, size: 8 }
+body:             |
+  bb.0:
+    liveins: $x0, $x19, $lr
+
+    early-clobber $sp = frame-setup STPXpre killed $lr, killed $x19, $sp, -2 :: (store 8 into %stack.1), (store 8 into %stack.0)
+    frame-setup CFI_INSTRUCTION def_cfa_offset 16
+    frame-setup CFI_INSTRUCTION offset $w19, -8
+    frame-setup CFI_INSTRUCTION offset $w30, -16
+    renamable $x19 = COPY $x0
+    renamable $x0 = nuw ADDXri $x0, 48, 0
+    $x1 = ADDXri $sp, 0, 0
+    dead $w2 = MOVi32imm 33, implicit-def $x2
+    $x3 = COPY $xzr
+    BL @foo, csr_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit killed $x1, implicit killed $x2, implicit killed $x3, implicit-def $sp
+    $x0 = COPY killed renamable $x19
+    BL @widget, csr_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit-def $sp
+    early-clobber $sp, $lr, $x19 = frame-destroy LDPXpost $sp, 2 :: (load 8 from %stack.1), (load 8 from %stack.0)
+    RET_ReallyLR
+
+...
+---
+name:            baz.15
+stack:
+  - { id: 0, offset: -8, size: 8 }
+  - { id: 1, offset: -16, size: 8 }
+body:             |
+  bb.0:
+    early-clobber $sp = frame-setup STPXpre killed $lr, killed $x19, $sp, -2 :: (store 8 into %stack.1), (store 8 into %stack.0)
+    frame-setup CFI_INSTRUCTION def_cfa_offset 16
+    frame-setup CFI_INSTRUCTION offset $w19, -8
+    frame-setup CFI_INSTRUCTION offset $w30, -16
+    renamable $x19 = COPY $x0
+    renamable $x0 = nuw ADDXri killed renamable $x1, 16, 0
+    $x1 = ADDXri $sp, 0, 0
+    dead $w2 = MOVi32imm 33, implicit-def $x2
+    $x3 = COPY $xzr
+    BL @foo, csr_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit $x1, implicit killed $x2, implicit killed $x3, implicit-def $sp
+    $x0 = COPY killed renamable $x19
+    BL @widget, csr_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit-def $sp
+    early-clobber $sp, $lr, $x19 = frame-destroy LDPXpost $sp, 2 :: (load 8 from %stack.1), (load 8 from %stack.0)
+    RET_ReallyLR
+
+...
+---
+name:            baz.16
+tracksRegLiveness: true
+stack:
+  - { id: 0, offset: -8, size: 8 }
+  - { id: 1, offset: -16, size: 8 }
+body:             |
+  bb.0:
+    liveins: $x0, $x19, $lr
+
+    early-clobber $sp = frame-setup STPXpre killed $lr, killed $x19, $sp, -2 :: (store 8 into %stack.1), (store 8 into %stack.0)
+    frame-setup CFI_INSTRUCTION def_cfa_offset 16
+    frame-setup CFI_INSTRUCTION offset $w19, -8
+    frame-setup CFI_INSTRUCTION offset $w30, -16
+    renamable $x19 = COPY $x0
+    renamable $x0 = nuw ADDXri $x0, 48, 0
+    $x1 = ADDXri $sp, 0, 0
+    dead $w2 = MOVi32imm 33, implicit-def $x2
+    $x3 = COPY $xzr
+    BL @foo, csr_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit killed $x1, implicit killed $x2, implicit killed $x3, implicit-def $sp
+    $x0 = COPY killed renamable $x19
+    BL @widget, csr_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit-def $sp
+    early-clobber $sp, $lr, $x19 = frame-destroy LDPXpost $sp, 2 :: (load 8 from %stack.1), (load 8 from %stack.0)
+    RET_ReallyLR
+
+...
+
+# TWO-RUNS: name:            OUTLINED_FUNCTION_2_0
+# TWO-RUNS-DAG: bb.0:
+# TWO-RUNS-DAG: renamable $x19 = COPY $x0
+# TWO-RUNS-NEXT: renamable $x0 = nuw ADDXri $x0, 48, 0
+# TWO-RUNS-NEXT: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp
+#
+# The machine outliner is expected to stop at the 1st iteration for case ONE-RUN
+# since machine-outline-runs is specified as 1.
+# ONE-RUN-NOT: [[OUTLINED:OUTLINED_FUNCTION_2_[0-9]+]]
+#
+# The machine outliner is expected to stop at the 3rd iteration for case FOUR-RUNS
+# since the MIR has no change at the 3rd iteration.
+# FOUR-RUNS-NOT: [[OUTLINED:OUTLINED_FUNCTION_3_[0-9]+]]
+# FOUR-RUNS-NOT: [[OUTLINED:OUTLINED_FUNCTION_4_[0-9]+]]