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

1510–1512

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?

1515–1517

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

65–71

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

[jinlin]

llvm/lib/CodeGen/MachineOutliner.cpp

1510–1512

Done.

1515–1517

Done.

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

65–71

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

65–71

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

1510

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.

1510

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

1512

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

1516

Nit: pull I into the loop:

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

1518–1519

Can we have a small testcase showing that this happens?

1524–1525

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

1512

Done.

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

140–141

Done.

[jinlin]

llvm/lib/CodeGen/MachineOutliner.cpp

1516

Done.

1518–1519

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

1524–1525

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("outline-repeat-count", cl::Hidden,
+              cl::desc("The number of times to apply 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) {
+  unsigned NumRepeats = NumRepeat;
+  if (NumRepeats < 1)
+    NumRepeats = 1;
+
+  bool Changed = false;
+  for (unsigned I = 0; I < NumRepeats; I++) {
+    if (!runOnceOnModule(M, I))
+      return Changed;
+    Changed = true;
+  }
+  return Changed;
+}

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

+# RUN: llc -mtriple=aarch64--- -run-pass=prologepilog -run-pass=machine-outliner -outline-repeat-count=2 -verify-machineinstrs %s -o - | FileCheck %s
+
+# 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"
+
+  %0 = type { %1*, i64 }
+  %1 = type { i64 }
+  %2 = type <{ %0, %3, %6 }>
+  %3 = type <{ %4, %4, %4, %4 }>
+  %4 = type <{ %5 }>
+  %5 = type <{ double }>
+  %6 = type <{ %7 }>
+  %7 = type <{ %8 }>
+  %8 = type <{ %9* }>
+  %9 = type opaque
+  %10 = type <{ %0, %6 }>
+
+  declare void @widget(%0*) local_unnamed_addr
+
+  declare void @foo(i8*, [24 x i8]*, i64, i8*) local_unnamed_addr
+
+  define void @baz.14(%2* %tmp37) {
+  bb:
+    %tmp3 = alloca [24 x i8], align 8
+    %tmp57 = getelementptr inbounds %2, %2* %tmp37, i64 0, i32 2
+    %tmp59 = bitcast %6* %tmp57 to i8*
+    call void @foo(i8* nonnull %tmp59, [24 x i8]* nonnull %tmp3, i64 33, i8* null)
+    %tmp602 = bitcast %2* %tmp37 to %0*
+    call void @widget(%0* %tmp602)
+    ret void
+  }
+
+  define void @baz.15(%2* %tmp38, %10* %tmp11) {
+  bb:
+    %tmp4 = alloca [24 x i8], align 8
+    %tmp101 = getelementptr inbounds %10, %10* %tmp11, i64 0, i32 1
+    %tmp103 = bitcast %6* %tmp101 to i8*
+    call void @foo(i8* nonnull %tmp103, [24 x i8]* nonnull %tmp4, i64 33, i8* null)
+    %tmp1042 = bitcast %2* %tmp38 to %0*
+    call void @widget(%0* %tmp1042)
+    ret void
+  }
+
+  define void @baz.16(%2* %tmp39) {
+  bb:
+    %tmp6 = alloca [24 x i8], align 8
+    %tmp178 = getelementptr inbounds %2, %2* %tmp39, i64 0, i32 2
+    %tmp180 = bitcast %6* %tmp178 to i8*
+    call void @foo(i8* nonnull %tmp180, [24 x i8]* nonnull %tmp6, i64 33, i8* null)
+    %tmp1812 = bitcast %2* %tmp39 to %0*
+    call void @widget(%0* %tmp1812)
+    ret void
+  }
+...
+---
+name:            baz.14
+tracksRegLiveness: true
+stack:
+  - { id: 0, name: tmp3, type: default, offset: 0, size: 24, alignment: 8,
+      stack-id: default, callee-saved-register: '', callee-saved-restored: true,
+      local-offset: -24, debug-info-variable: '', debug-info-expression: '',
+      debug-info-location: '' }
+body:             |
+  bb.0.bb:
+    liveins: $x0
+
+    renamable $x19 = COPY $x0
+    renamable $x0 = nuw ADDXri $x0, 48, 0
+    ADJCALLSTACKDOWN 0, 0, implicit-def dead $sp, implicit $sp
+    $x1 = ADDXri %stack.0.tmp3, 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
+    ADJCALLSTACKUP 0, 0, implicit-def dead $sp, implicit $sp
+    ADJCALLSTACKDOWN 0, 0, implicit-def dead $sp, implicit $sp
+    $x0 = COPY killed renamable $x19
+    BL @widget, csr_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit-def $sp
+    ADJCALLSTACKUP 0, 0, implicit-def dead $sp, implicit $sp
+    RET_ReallyLR
+
+...
+---
+name:            baz.15
+stack:
+  - { id: 0, name: tmp4, type: default, offset: 0, size: 24, alignment: 8,
+      stack-id: default, callee-saved-register: '', callee-saved-restored: true,
+      local-offset: -24, debug-info-variable: '', debug-info-expression: '',
+      debug-info-location: '' }
+body:             |
+  bb.0.bb:
+    liveins: $x0, $x1
+
+    renamable $x19 = COPY $x0
+    renamable $x0 = nuw ADDXri killed renamable $x1, 16, 0
+    ADJCALLSTACKDOWN 0, 0, implicit-def dead $sp, implicit $sp
+    $x1 = ADDXri %stack.0.tmp4, 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
+    ADJCALLSTACKUP 0, 0, implicit-def dead $sp, implicit $sp
+    ADJCALLSTACKDOWN 0, 0, implicit-def dead $sp, implicit $sp
+    $x0 = COPY killed renamable $x19
+    BL @widget, csr_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit-def $sp
+    ADJCALLSTACKUP 0, 0, implicit-def dead $sp, implicit $sp
+    RET_ReallyLR
+
+...
+---
+name:            baz.16
+tracksRegLiveness: true
+stack:
+  - { id: 0, name: tmp6, type: default, offset: 0, size: 24, alignment: 8,
+      stack-id: default, callee-saved-register: '', callee-saved-restored: true,
+      local-offset: -24, debug-info-variable: '', debug-info-expression: '',
+      debug-info-location: '' }
+body:             |
+  bb.0.bb:
+    liveins: $x0
+
+    renamable $x19 = COPY $x0
+    renamable $x0 = nuw ADDXri $x0, 48, 0
+    ADJCALLSTACKDOWN 0, 0, implicit-def dead $sp, implicit $sp
+    $x1 = ADDXri %stack.0.tmp6, 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
+    ADJCALLSTACKUP 0, 0, implicit-def dead $sp, implicit $sp
+    ADJCALLSTACKDOWN 0, 0, implicit-def dead $sp, implicit $sp
+    $x0 = COPY killed renamable $x19
+    BL @widget, csr_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit-def $sp
+    ADJCALLSTACKUP 0, 0, implicit-def dead $sp, implicit $sp
+    RET_ReallyLR
+
+...
+# CHECK: [[OUTLINED:OUTLINED_FUNCTION_2_[0-9]+]]