[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

911

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

911

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

121

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.

380

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

940

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

380

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/BranchProbabilityInfo.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.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/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Mangler.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/SuffixTree.h"
 #include "llvm/Support/raw_ostream.h"
 #include <functional>

 /// Number of times to re-run the outliner. This is not the total number of runs
 /// 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"));
 
+static cl::opt<bool> UseProfileData(
+    "machine-outliner-use-profile-data", cl::init(false), cl::Hidden,
+    cl::desc("Use profile data to avoid outlining hot blocks."));
+
 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.
   ///
struct MachineOutliner : public ModulePass {
   bool RunOnAllFunctions = true;
 
   StringRef getPassName() const override { return "Machine Outliner"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<MachineModuleInfoWrapperPass>();
     AU.addPreserved<MachineModuleInfoWrapperPass>();
     AU.setPreservesAll();
     ModulePass::getAnalysisUsage(AU);
   }
 
   MachineOutliner() : ModulePass(ID) {
     initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
   }
 
   /// Remark output explaining that not outlining a set of candidates would be
   /// better than outlining that set.
for (Function &F : M) {
 
     // 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))
+    Optional<BlockFrequencyInfo> BFI;
+    if (UseProfileData) {
+      DominatorTree DT(F);
+      LoopInfo LI(DT);
+      BranchProbabilityInfo BPI(F, LI);
+      BFI.emplace(F, BPI, LI);
+    }
+
+    if (!RunOnAllFunctions && !TII->shouldOutlineFromFunctionByDefault(*MF) &&
+        !UseProfileData)
       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
for (MachineBasicBlock &MBB : *MF) {
       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;
 
+      // If we have profile data and want to use it, avoid outlining hot blocks.
+      if (UseProfileData &&
+          !BFI->isBlockRarelyExecuted(MBB.getBasicBlock()).getValueOr(false))
+        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 -verify-machineinstrs -enable-machine-outliner -machine-outliner-use-profile-data -mtriple=aarch64-linux-gnu < %s | FileCheck %s
+
+declare void @z(i32, i32, i32, i32)
+
+; CHECK-LABEL: cold:
+define void @cold() !prof !0 {
+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 !1 {
+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: cold2:
+define void @cold2() !prof !0 {
+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
+
+!0 = !{!"function_entry_count", i64 0}
+!1 = !{!"function_entry_count", i64 1}