[outliner] Use profile data to avoid outlining hot blocks

[ellis]

Summary

If profile data is available then we can use it to avoid outlining hot blocks by using the -machine-outliner-use-profile-data backend flag. If profile data is not available then we fall back to the target defaults.

[paquette]

Can you add test cases for:

• hot block + optsize minsize
• cold block + optsize minsize

?

[ellis]

Add tests for hot/cold functions with optsize minsize.

[kyulee]

llvm/lib/CodeGen/MachineOutliner.cpp

919

I'm not sure I understand this correctly. When UseProfileData is true, do we ignore the other two conditions?

[ellis]

llvm/lib/CodeGen/MachineOutliner.cpp

919

There are basically three reasons why the machine outliner would run.

1. If RunOnAllFunctions is true
2. If shouldOutlineFromFunctionByDefault() is true. a. Currently this only happens when targeting arm64 with minsize.
3. If we pass -machine-outliner-use-profile-data

On second thought I should also check F.hasProfileData() so that we don't conservatively assume unprofiled functions are always hot.

[ellis]

Check if profile data is available before trying to use and add a test to make sure we enable outlining for minsize functions without profiles.

[ellis]

Remove dependency on isBlockRarelyExecuted() that I created in D124490 and replace with ProfileSummaryInfo API to determine if a block is hot.

[ellis]

I'm also wondering if I should use the isHotBlockNthPercentile() function and add an option to specify the percentile. Maybe something like -machine-outliner-cutoff-prof=99900.

[wenlei]

llvm/lib/CodeGen/MachineOutliner.cpp

119

I don't think we do this for other passes. Once the plumbing for BFI/MBFI is done for passes to leverage profile info, we just always do that. Using profile should indeed always be better if heuristic is reasonable. Why you need a flag for this case?

If you need some confidence in profile quality, you can check on profile (PSI->hasInstrumentationProfile()) etc.

374

Why do we require BFI instead of MBFI given this is dealing with MIR.

944

Usually we call higher level API like isHotBlock instead of isHotBlockNthPercentile. You can tweak the global percentile by -profile-summary-cutoff-hot.

[ellis]

Remove -machine-outliner-use-profile-data.

[ellis]

I'm planning changes to this for now, see the TODO comments.

llvm/lib/CodeGen/MachineOutliner.cpp

374

I would have liked to use LazyMachineBlockFrequencyInfoPass instead, but it seems that does not work here because this is a ModulePass instead of a MachineFunctionPass.

llvm/lib/CodeGen/MachineOutliner.cpp

 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
 ///
 //===----------------------------------------------------------------------===//
 #include "llvm/CodeGen/MachineOutliner.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/Twine.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
+#include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/IRBuilder.h"

 /// as the outliner will run at least one time. The default value is set to 0,
 /// meaning the outliner will run one time and rerun zero times after that.
 static cl::opt<unsigned> OutlinerReruns(
     "machine-outliner-reruns", cl::init(0), cl::Hidden,
     cl::desc(
         "Number of times to rerun the outliner after the initial outline"));
 
 namespace {
 
 /// Maps \p MachineInstrs to unsigned integers and stores the mappings.
 struct InstructionMapper {
 
   /// The next available integer to assign to a \p MachineInstr that
   /// cannot be outlined.
   ///
   /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
   unsigned IllegalInstrNumber = -3;
struct MachineOutliner : public ModulePass {
   /// Set when the pass is constructed in TargetPassConfig.
   bool RunOnAllFunctions = true;
 
   StringRef getPassName() const override { return "Machine Outliner"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<MachineModuleInfoWrapperPass>();
     AU.addPreserved<MachineModuleInfoWrapperPass>();
+    if (!RunOnAllFunctions) {
+      // FIXME: This breaks some tests.
+      // TODO: As it is now, this code turns on the machine outliner for
+      // everyone (even those that don't target AArch64) that provides profile
+      // data unless they supply `-enable-machine-outliner=never`. The
+      // alternative is to add another option like
+      // `-enable-machine-outliner=profile_guided`.
+      AU.addRequired<BlockFrequencyInfoWrapperPass>();
+      AU.addRequired<ProfileSummaryInfoWrapperPass>();
+    }
     AU.setPreservesAll();
     ModulePass::getAnalysisUsage(AU);
   }
 
   MachineOutliner() : ModulePass(ID) {
     initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
   }
 
bool MachineOutliner::outline(Module &M,
   }
 
   LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
   return OutlinedSomething;
 }
 
 void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M,
                                      MachineModuleInfo &MMI) {
+  ProfileSummaryInfo *PSI = nullptr;
+  if (auto *Wrapper = getAnalysisIfAvailable<ProfileSummaryInfoWrapperPass>())
+    PSI = &Wrapper->getPSI();
+
   // Build instruction mappings for each function in the module. Start by
   // iterating over each Function in M.
   for (Function &F : M) {
 
     // If there's nothing in F, then there's no reason to try and outline from
     // it.
     if (F.empty())
       continue;
 
     // There's something in F. Check if it has a MachineFunction associated with
     // it.
     MachineFunction *MF = MMI.getMachineFunction(F);
 
     // If it doesn't, then there's nothing to outline from. Move to the next
     // Function.
     if (!MF)
       continue;
 
     const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
 
-    if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF))
+    BlockFrequencyInfo *BFI = nullptr;
+    if (PSI && PSI->hasInstrumentationProfile() && F.hasProfileData())
+      BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
+
+    if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF) &&
+        !BFI)
       continue;
 
     // We have a MachineFunction. Ask the target if it's suitable for outlining.
     // If it isn't, then move on to the next Function in the module.
     if (!TII->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs))
       continue;
 
     // We have a function suitable for outlining. Iterate over every
     // MachineBasicBlock in MF and try to map its instructions to a list of
     // unsigned integers.
     for (MachineBasicBlock &MBB : *MF) {
       // If there isn't anything in MBB, then there's no point in outlining from
       // it.
       // If there are fewer than 2 instructions in the MBB, then it can't ever
       // contain something worth outlining.
       // FIXME: This should be based off of the maximum size in B of an outlined
       // call versus the size in B of the MBB.
       if (MBB.empty() || MBB.size() < 2)
         continue;
 
       // Check if MBB could be the target of an indirect branch. If it is, then
       // we don't want to outline from it.
       if (MBB.hasAddressTaken())
         continue;
 
+      // TODO: We could either avoid outlining hot blocks, or only consider
+      // outlining cold blocks.
+      // If profile data is available to the machine outliner, then do not
+      // outline hot blocks.
+      if (BFI && PSI->isHotBlock(MBB.getBasicBlock(), BFI))
+        continue;
+
       // MBB is suitable for outlining. Map it to a list of unsigneds.
       Mapper.convertToUnsignedVec(MBB, *TII);
     }
 
     // Statistics.
     UnsignedVecSize = Mapper.UnsignedVec.size();
   }
 }

llvm/test/CodeGen/AArch64/machine-outliner-profile.ll

+; RUN: llc -mtriple=aarch64-linux-gnu < %s | FileCheck %s
+
+declare void @z(i32, i32, i32, i32)
+
+; CHECK-LABEL: cold:
+define void @cold() !prof !20 {
+entry:
+; CHECK: [[OUTLINED:OUTLINED_FUNCTION_[0-9]+]]
+  tail call void @z(i32 1, i32 2, i32 3, i32 4)
+  ret void
+; CHECK: .cfi_endproc
+}
+
+; CHECK-LABEL: hot:
+define void @hot() !prof !21 {
+entry:
+; CHECK-NOT: [[OUTLINED]]
+  tail call void @z(i32 1, i32 2, i32 3, i32 4)
+  ret void
+; CHECK: .cfi_endproc
+}
+
+; CHECK-LABEL: minsize_cold:
+define void @minsize_cold() optsize minsize !prof !20 {
+entry:
+; CHECK: [[OUTLINED]]
+  tail call void @z(i32 1, i32 2, i32 3, i32 4)
+  ret void
+; CHECK: .cfi_endproc
+}
+
+; CHECK-LABEL: minsize_hot:
+define void @minsize_hot() optsize minsize !prof !21 {
+entry:
+; CHECK-NOT: [[OUTLINED]]
+  tail call void @z(i32 1, i32 2, i32 3, i32 4)
+  ret void
+; CHECK: .cfi_endproc
+}
+
+; CHECK-LABEL: no_profile:
+define void @no_profile() {
+entry:
+; CHECK-NOT: [[OUTLINED]]
+  tail call void @z(i32 1, i32 2, i32 3, i32 4)
+  ret void
+; CHECK: .cfi_endproc
+}
+
+; CHECK-LABEL: minsize_no_profile:
+define void @minsize_no_profile() optsize minsize {
+entry:
+; CHECK: [[OUTLINED]]
+  tail call void @z(i32 1, i32 2, i32 3, i32 4)
+  ret void
+; CHECK: .cfi_endproc
+}
+
+; CHECK: [[OUTLINED]]:
+; CHECK-SAME: // @{{.*}} Tail Call
+; CHECK:      mov     w0, #1
+; CHECK-NEXT: mov     w1, #2
+; CHECK-NEXT: mov     w2, #3
+; CHECK-NEXT: mov     w3, #4
+; CHECK-NEXT: b       z
+
+!llvm.module.flags = !{!1}
+!20 = !{!"function_entry_count", i64 0}
+!21 = !{!"function_entry_count", i64 100}
+
+!1 = !{i32 1, !"ProfileSummary", !2}
+!2 = !{!3, !4, !5, !6, !7, !8, !9, !10}
+!3 = !{!"ProfileFormat", !"InstrProf"}
+!4 = !{!"TotalCount", i64 200}
+!5 = !{!"MaxCount", i64 100}
+!6 = !{!"MaxInternalCount", i64 0}
+!7 = !{!"MaxFunctionCount", i64 100}
+!8 = !{!"NumCounts", i64 4}
+!9 = !{!"NumFunctions", i64 4}
+!10 = !{!"DetailedSummary", !11}
+!11 = !{!12, !13}
+!12 = !{i32 990000, i64 10, i32 4}
+!13 = !{i32 999999, i64 10, i32 4}