[SampleFDO] Flow Sensitive Sample FDO (FSAFDO) profile loader

[xur]

Summary

This patch implements Flow Sensitive Sample FDO (FSAFDO) profile loader.
We have two additional profile loaders for FS profile, one before RegAlloc and one before BlockPlacement.

Use "-enable-fs-discriminator=true -disable-ra-fsprofile-loader=false -disable-layout-fsprofile-loader=false" to turn on the FS profile loaders, if sample-profile-use is specified.

[wmi]

llvm/include/llvm/IR/DebugInfoMetadata.h

2229–2230

EnableFSDiscriminator has been handled above already?

llvm/lib/CodeGen/FlowSensitiveSampleProfile.cpp

276

We may want to set remapping file otherwise remapping cannot be effective enough when FSAFDO is enabled.

[wmi]

llvm/lib/CodeGen/FlowSensitiveSampleProfile.cpp

165

What is its difference with the generic version of SampleProfileLoaderBaseImpl<BT>::buildEdges? They look similar.

[wmi]

llvm/lib/CodeGen/FlowSensitiveSampleProfile.cpp

242

Looks like the BB prob update shouldn't be guarded by ShowFSBranchProb.

245–248

Nit: Diff = std::abs(OldProb - NewProb);

249–265

Enclose the block of debug output with LLVM_DEBUG({ ... }).

[xur]

llvm/include/llvm/IR/DebugInfoMetadata.h

2229–2230

Good catch. This is from a bad merge. Fixed.

llvm/lib/CodeGen/FlowSensitiveSampleProfile.cpp

165

There are basically the same. We have this just because IR and MIR have different interfaces for predecessors and successors. In IR, there is a utility iteration while MIR's iterators are with CFG.
I could add utilities in MIR to remove this specialization.

242

Yes. that's correct. I added this option just before sending the review to suppress the debug output. It's not added correctly. fixed

276

OK. Seems that I need to pass the remap file name the same way as profile file name. Will fix.

[wenlei]

llvm/lib/CodeGen/FlowSensitiveSampleProfile.cpp

291

FSProfileLoader inherits from SampleProfileLoaderBaseImpl<MachineBasicBlock>, so it's for MIR only, why do we still have a templated runOnFunction?

If we want something that serves both IR and MIR, perhaps it can go into base. Or more generally, how do we plan to support IR FS-loader?

293

Why do we keep dominator tree and loop info?

305

When do we want to run FS loader but not setting branch probabilities?

llvm/lib/CodeGen/TargetPassConfig.cpp

1126

nit: for readability, the EnableFSDiscriminator check inside getFSProfileFile can be removed, and loader pass can be guarded under the same if check for disc pass.

1128

I'm wondering if there's a need for users to control which pass to have profile loading independently, at least for tuning purpose? i.e. some switch like disable-ra-fsprofile-load, disable-layout-fsprofile-load.

[hoy]

llvm/lib/CodeGen/FlowSensitiveSampleProfile.cpp

34

typo: senstive

35

Wondering why needs this switch. The whole point of FSProfileLoader is to overwrite branch weights?

llvm/lib/Passes/PassBuilder.cpp

1121

Can this be moved into the constructor of PGOOptions so that it looks more consistent with the rest of PGO setup?

[xur]

Thanks all for the review comments! My replies are inlined.

llvm/lib/CodeGen/FlowSensitiveSampleProfile.cpp

34

Fixed

35

some of the benefits are from the improved profile (i.e. using sum rather max) that helps SampleLoder (inline for example).
This option help to measure it.
I tested it in many of my experiments. But I agree that it does not need to expose to the users.
I will remove this.

291

Not sure I follow the question here. Basically this is MIR version of runOnFunction.
APIs etc are different from IR version of runOnFunction. If we want IR FS-loader, that should be based on SampleProfileLoader (need to remove the inline related code).

293

Profile loader does not invalid these infos (this is different in SampleLoader, where inline will change it)

305

Sorry. This is a list minute bug (as I mentioned in answering Wei's comments)

llvm/lib/CodeGen/TargetPassConfig.cpp

1126

OK. I will change this.

1128

Yes. that's a good suggestion. I havd them in my testing implementation but got it out when sending for review. I will add them back.

llvm/lib/Passes/PassBuilder.cpp

1121

Do you mean we still using FSProfileFile but just move the assignment to PGOOptions constructor? This should do doable.

[hoy]

llvm/lib/Passes/PassBuilder.cpp

1121

Yes, that's what I meant. Currently FSProfileFile is set in postlink for LTO. It shouldn't matter if it is always set, since no prelink pass consumes that now?

[wenlei]

llvm/lib/CodeGen/FlowSensitiveSampleProfile.cpp

110–111

This is more like a MIRProfileLoader as opposed to FSProfileLoader. If we do IR FS profile loading, it will be handled in existing SampleLoader, the name FSProfileLoader would suggest this one handles all FS profile loading for both IR and MIR. Same for FSProfileLoaderPass. We could follow the naming/structure of MIRAddFSDiscriminators too and call it MIRProfileLoader.

291

Basically I was wondering why we use runOnFunction(FunctionT &F) instead of runOnFunction(MachineFunction &F) since this is only meant for MIR? The IR loader has runOnFunction(Function &F..).

293

This is still all per-function info, so it needs to be cleared before we use the profile loader to process the next function, right? or did i miss anything?

[xur]

llvm/lib/CodeGen/FlowSensitiveSampleProfile.cpp

110–111

OK. I totally agree what you said. I will change the name.

291

OK. I see what you meant. This is my bad. I should have used runOnFunction(MachineFunction &F). Note that runOnFucntion is not a templated function: after we propagate "using FunctionT=MachineFunction", this function will become runOnFunction(MachineFunction &F). But I agree this is confusing. I will fix. Thanks!

293

We initialize these data structures per function in setInitVals(). Each function will have its own value and no need to clear.

llvm/lib/Passes/PassBuilder.cpp

1121

Got it. I'll try to fix this.

[xur]

Integrated review comments from Wei, Wenlei and Hongtao. Thanks for all the suggestions/comments!

The only suggested was not applied was the one to use std::abs to BranchProbability -- we don't have the abs operator for BranchProbability. I could add but does not seem worthy.

-Rong

[hoy]

llvm/lib/CodeGen/MIRSampleProfile.cpp

282 ↗

(On Diff #366762)

Wondering whether this is needed when EnableFSBranchProb is false, where the weights computed are saved in an internal buffer and not used anywhere?

llvm/lib/Transforms/IPO/SampleProfile.cpp

371 ↗

(On Diff #366762)

Nit: pls remove this piece.

[wmi]

llvm/include/llvm/Passes/PassBuilder.h

74–76 ↗

(On Diff #366762)

It adds a dependency of LLVMProfileData to LLVMPasses.

Maybe it is better to pass the related information to codegen through param instead of through internal flag? The interface to the codegen is LLVMTargetMachine::addPassesToEmitFile. An example is its param "CodeGenFileType FileType" which is got from configuration in clang/lto backend/thinlto backend/...

[xur]

llvm/include/llvm/Passes/PassBuilder.h

74–76 ↗

(On Diff #366762)

OK. I also find it a bit awkward to use internal flag here. Let me try to use this suggested way.

llvm/lib/CodeGen/MIRSampleProfile.cpp

282 ↗

(On Diff #366762)

Indeed. I think I will remove this option.

llvm/lib/Transforms/IPO/SampleProfile.cpp

371 ↗

(On Diff #366762)

Sorry. I thought I cleaned the code before sending for the review.

[xur]

Integrated recent comments from Wei and Hongtao.

[wmi]

llvm/include/llvm/Target/TargetMachine.h

113–116 ↗

(On Diff #367058)

Feel it is better to move the whole PGOOpt here. Similar as OptLevel above, PGOOpt shows us the major PGO related configuration and it will be available for the MIR passes after it is included in TargetMachine class.

[xur]

llvm/include/llvm/Target/TargetMachine.h

113–116 ↗

(On Diff #367058)

I'm OK with that. But for now, only these two fields are used in MIR (at lease for this patch).
I will make the change if I don't hear objection.

[hoy]

llvm/include/llvm/Target/TargetMachine.h

113–116 ↗

(On Diff #367058)

Moving PGOOpt here sounds good to time. It may be extended for MIR profiling use in the future. Maybe the EnableFSDiscriminator switch can be added into PGOOpt as well?

[xur]

Followed Wei's suggestion to put PGOOptions to TargetMachine.

We could not pass TM to PGOOptions because that would create a circular dependency. We have to set PGOOptions outside of the constructor.
I also split out declaration of PGOptions to a separated head-file, because I don't want include unnecessary declamations to TargetMachine.

[xur]

I just sent out the patch that puts PGOOptions to TargetMachine before
getting this message.
So EnableFSDiscriminator is not included.

If we want to include EnableFSDiscrinator there, we'd better to promote
this to an user visible option (as of now, it's an internal option).
I was thinking this option only serves in the transitional phrase. In the
long term, we will make it default and get rid of it.
So, I did not add it as a user level flag.

If people think we should keep it, i'd happy to change it to a user level
flag and include it in PGOOptions.

[hoy]

Thanks working on including PGOOptions in TargetMachine. It sounds good to me to leave EnableFSDiscrinator as an llvm switch for now.

Thanks,
Hongtao

From: Rong Xu <[e-mail]>
Date: Wednesday, August 18, 2021 at 10:15 AM
To: Hongtao Yu <[e-mail]>
Cc: [e-mail] <[e-mail]>, Wenlei He <[e-mail]>, Hongtao Yu <[e-mail]>, [e-mail] <[e-mail]>, [e-mail] <[e-mail]>, [e-mail] <[e-mail]>, [e-mail] <[e-mail]>, [e-mail] <[e-mail]>, [e-mail] <[e-mail]>, [e-mail] <[e-mail]>, [e-mail] <[e-mail]>, [e-mail] <[e-mail]>, [e-mail] <[e-mail]>, [e-mail] <[e-mail]>, [e-mail] <[e-mail]>, [e-mail] <[e-mail]>
Subject: Re: [PATCH] D107878: [SampleFDO] Flow Sensitive Sample FDO (FSAFDO) profile loader
I just sent out the patch that puts PGOOptions to TargetMachine before getting this message.
So EnableFSDiscriminator is not included.

If we want to include EnableFSDiscrinator there, we'd better to promote this to an user visible option (as of now, it's an internal option).
I was thinking this option only serves in the transitional phrase. In the long term, we will make it default and get rid of it.
So, I did not add it as a user level flag.

If people think we should keep it, i'd happy to change it to a user level flag and include it in PGOOptions.

[xur]

Fix some issues in last patch set.

[wmi]

LGTM. Thanks.

[hoy]

LGTM.

[wenlei]

llvm/lib/CodeGen/FlowSensitiveSampleProfile.cpp

293

Ok, but resetting it isn't going to cause problem either, right? Just trying to understand if there's a correctness issue that requires not resetting these fields. If not, might as well not adding the special case and always reset/clear. Seem unnecessary to skip reset, but not a big deal though.

[xur]

Yes. Resetting them will not cause correctness problems.

Note that SampleProfileLoader is a module scope object -- we initialize
it in a module pass. LoopInfo, DOM etc are a module level analysis obj.
After inline, we need to invalidate and recompute.

This is different for MIRProfileLoader (which is a function level object).
The loopInfo and Dom etc are specific to this function. Since we do not do
any transformation (except changing the BranchProb). I don't think we need
to invalidate them either.

[xur]

Discussed with Wei offline: it's better to set fs profile loader as off by default so people can opt-in (rather opt-out).
Once we are done with more perf testing, we will switch the default to on.

[hoy]

In D107878#2953248, @xur wrote:

Discussed with Wei offline: it's better to set fs profile loader as off by default so people can opt-in (rather opt-out).
Once we are done with more perf testing, we will switch the default to on.

Sounds good to me.

[wenlei]

In D107878#2953248, @xur wrote:

Discussed with Wei offline: it's better to set fs profile loader as off by default so people can opt-in (rather opt-out).
Once we are done with more perf testing, we will switch the default to on.

For FS-AFDO to be the default, we need profile generation part to be available to everyone as well (ideally in llvm-profgen).

[lenary]

llvm/test/CodeGen/X86/fsafdo_test2.ll

3

I think this REQUIRES: asserts if you're checking the debug output?

[wenlei]

llvm/test/CodeGen/X86/fsafdo_test2.ll

3

Should be fixed in D108364

[hoy]

llvm/test/CodeGen/X86/fsafdo_test2.ll

3

That's right. It was just fixed by https://reviews.llvm.org/D108364.

[JDevlieghere]

llvm/include/llvm/CodeGen/MIRSampleProfile.h

59 ↗

(On Diff #367381)

You're instantiating a forward-declared type. This breaks the modules build: https://green.lab.llvm.org/green/job/lldb-cmake/34450/console

llvm/lib/CodeGen/MIRSampleProfile.cpp

289 ↗

(On Diff #367381)

Why is this outside the llvm namespace?

[dexonsmith]

llvm/lib/CodeGen/MIRSampleProfile.cpp

289 ↗

(On Diff #367381)

I think it's common style in LLVM to have function definitions outside of namespaces -- IMO, the odd thing here is that the preceding function definitions were inside the namespace.

[RKSimon]

llvm/lib/LTO/LTOBackend.cpp

234 ↗

(On Diff #367381)

@xur Why does TM need a null check - afaict it's already been dereferenced in the call tree, and will be again below.

Noticed in a scan-build warning: https://llvm.org/reports/scan-build/report-LTOBackend.cpp-runNewPMPasses-34-35dfe9.html#EndPath

llvm/include/llvm/CodeGen/FlowSensitiveSampleProfile.h

+//===----- FlowSensitiveSampleProfile.h: FS SampleFDO Support ---*- c++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the supoorting functions for Flow Sensitive Sample FDO
+// loader.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_FLOWSENSITIVESAMPLEPROFILE_H
+#define LLVM_CODEGEN_FLOWSENSITIVESAMPLEPROFILE_H
+
+#include "llvm/Analysis/ProfileSummaryInfo.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
+#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
+#include "llvm/CodeGen/MachineDominators.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
+#include "llvm/CodeGen/MachinePostDominators.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Module.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/ProfileData/InstrProf.h"
+#include "llvm/ProfileData/SampleProf.h"
+#include "llvm/ProfileData/SampleProfReader.h"
+
+#include <cassert>
+
+namespace llvm {
+
+using namespace sampleprof;
+
+class FSProfileLoader;
+class FSProfileLoaderPass : public MachineFunctionPass {
+  MachineFunction *MF;
+  std::string ProfileFileName;
+  FSDiscriminatorPass P;
+  unsigned LowBit;
+  unsigned HighBit;
+
+public:
+  static char ID;
+  /// FS bits will only use the '1' bits in the Mask.
+  FSProfileLoaderPass(std::string Filename = "",
+                      FSDiscriminatorPass P = FSDiscriminatorPass::Pass1)
+      : MachineFunctionPass(ID), ProfileFileName(Filename), P(P),
+        FSSampleLoader(std::make_unique<FSProfileLoader>(Filename)) {
+    LowBit = getFSPassBitBegin(P);
+    HighBit = getFSPassBitEnd(P);
+    assert(LowBit < HighBit && "HighBit needs to be greater than Lowbit");
+  }
+
+  /// getMachineFunction - Return the last machine function computed.
+  const MachineFunction *getMachineFunction() const { return MF; }
+
+private:
+  void init(MachineFunction &MF);
+  bool runOnMachineFunction(MachineFunction &) override;
+  bool doInitialization(Module &M) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  std::unique_ptr<FSProfileLoader> FSSampleLoader;
+  /// Hold the information of the basic block frequency.
+  MachineBlockFrequencyInfo *MBFI;
+};
+
+} // namespace llvm
+
+#endif // LLVM_CODEGEN_FLOWSENSITIVESAMPLEPROFILE_H

llvm/include/llvm/CodeGen/MachineDominators.h

public:
   void calculate(MachineFunction &F);
 
   bool dominates(const MachineDomTreeNode *A,
                  const MachineDomTreeNode *B) const {
     applySplitCriticalEdges();
     return DT->dominates(A, B);
   }
 
+  void getDescendants(MachineBasicBlock *A,
+                      SmallVectorImpl<MachineBasicBlock *> &Result) {
+    applySplitCriticalEdges();
+    DT->getDescendants(A, Result);
+  }
+
   bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const {
     applySplitCriticalEdges();
     return DT->dominates(A, B);
   }
 
   // dominates - Return true if A dominates B. This performs the
   // special checks necessary if A and B are in the same basic block.
   bool dominates(const MachineInstr *A, const MachineInstr *B) const {

llvm/include/llvm/CodeGen/MachineOptimizationRemarkEmitter.h

public:
   /// remark.  \p Loc is the debug location and \p MBB is the block that the
   /// optimization operates in.
   MachineOptimizationRemarkAnalysis(const char *PassName, StringRef RemarkName,
                                     const DiagnosticLocation &Loc,
                                     const MachineBasicBlock *MBB)
       : DiagnosticInfoMIROptimization(DK_MachineOptimizationRemarkAnalysis,
                                       PassName, RemarkName, Loc, MBB) {}
 
+  MachineOptimizationRemarkAnalysis(const char *PassName, StringRef RemarkName,
+                                    const MachineInstr *MI)
+      : DiagnosticInfoMIROptimization(DK_MachineOptimizationRemarkAnalysis,
+                                      PassName, RemarkName, MI->getDebugLoc(),
+                                      MI->getParent()) {}
+
   static bool classof(const DiagnosticInfo *DI) {
     return DI->getKind() == DK_MachineOptimizationRemarkAnalysis;
   }
 
   /// \see DiagnosticInfoOptimizationBase::isEnabled.
   bool isEnabled() const override {
     const Function &Fn = getFunction();
     LLVMContext &Ctx = Fn.getContext();

llvm/include/llvm/CodeGen/Passes.h

namespace llvm {
   extern char &DetectDeadLanesID;
 
   /// This pass perform post-ra machine sink for COPY instructions.
   extern char &PostRAMachineSinkingID;
 
   /// This pass adds flow sensitive discriminators.
   extern char &MIRAddFSDiscriminatorsID;
 
+  /// This pass reads flow sensitive profile.
+  extern char &FSProfileLoaderPassID;
+
   /// FastRegisterAllocation Pass - This pass register allocates as fast as
   /// possible. It is best suited for debug code where live ranges are short.
   ///
   FunctionPass *createFastRegisterAllocator();
   FunctionPass *createFastRegisterAllocator(RegClassFilterFunc F,
                                             bool ClearVirtRegs);
 
   /// BasicRegisterAllocation Pass - This pass implements a degenerate global
namespace llvm {
   /// Create IR Type Promotion pass. \see TypePromotion.cpp
   FunctionPass *createTypePromotionPass();
 
   /// Add Flow Sensitive Discriminators. PassNum specifies the
   /// sequence number of this pass (starting from 1).
   FunctionPass *
   createMIRAddFSDiscriminatorsPass(sampleprof::FSDiscriminatorPass P);
 
+  /// Read Flow Sensitive Profile.
+  FunctionPass *createFSProfileLoaderPass(std::string File,
+                                          sampleprof::FSDiscriminatorPass P);
+
   /// Creates MIR Debugify pass. \see MachineDebugify.cpp
   ModulePass *createDebugifyMachineModulePass();
 
   /// Creates MIR Strip Debug pass. \see MachineStripDebug.cpp
   /// If OnlyDebugified is true then it will only strip debug info if it was
   /// added by a Debugify pass. The module will be left unchanged if the debug
   /// info was generated by another source such as clang.
   ModulePass *createStripDebugMachineModulePass(bool OnlyDebugified);

llvm/include/llvm/IR/DebugInfoMetadata.h

 unsigned DILocation::getDuplicationFactor() const {
   return getDuplicationFactorFromDiscriminator(getDiscriminator());
 }
 
 unsigned DILocation::getCopyIdentifier() const {
   return getCopyIdentifierFromDiscriminator(getDiscriminator());
 }
 
-Optional<const DILocation *> DILocation::cloneWithBaseDiscriminator(unsigned D) const {
+Optional<const DILocation *>
+DILocation::cloneWithBaseDiscriminator(unsigned D) const {
   unsigned BD, DF, CI;
 
   if (EnableFSDiscriminator) {
     BD = getBaseDiscriminator();
     if (D == BD)
       return this;
     return cloneWithDiscriminator(D);
   }
 
   decodeDiscriminator(getDiscriminator(), BD, DF, CI);
   if (D == BD)
     return this;
+  if (EnableFSDiscriminator)
+    return cloneWithDiscriminator(D);
   if (Optional<unsigned> Encoded = encodeDiscriminator(D, DF, CI))
     return cloneWithDiscriminator(*Encoded);
   return None;
 }
 
-Optional<const DILocation *> DILocation::cloneByMultiplyingDuplicationFactor(unsigned DF) const {
+Optional<const DILocation *>
+DILocation::cloneByMultiplyingDuplicationFactor(unsigned DF) const {
   assert(!EnableFSDiscriminator && "FSDiscriminator should not call this.");
 
   DF *= getDuplicationFactor();
   if (DF <= 1)
     return this;
 
   unsigned BD = getBaseDiscriminator();
   unsigned CI = getCopyIdentifier();

llvm/include/llvm/InitializePasses.h

 
 /// Initialize all passes linked into the CodeGen library.
 void initializeTarget(PassRegistry&);
 
 void initializeAAEvalLegacyPassPass(PassRegistry&);
 void initializeAAResultsWrapperPassPass(PassRegistry&);
 void initializeADCELegacyPassPass(PassRegistry&);
 void initializeAddDiscriminatorsLegacyPassPass(PassRegistry&);
+void initializeAddFSDiscriminatorsPass(PassRegistry &);
 void initializeModuleAddressSanitizerLegacyPassPass(PassRegistry &);
 void initializeASanGlobalsMetadataWrapperPassPass(PassRegistry &);
 void initializeAddressSanitizerLegacyPassPass(PassRegistry &);
 void initializeAggressiveInstCombinerLegacyPassPass(PassRegistry&);
 void initializeAliasSetPrinterPass(PassRegistry&);
 void initializeAlignmentFromAssumptionsPass(PassRegistry&);
 void initializeAlwaysInlinerLegacyPassPass(PassRegistry&);
 void initializeAssumeSimplifyPassLegacyPassPass(PassRegistry &);

 void initializeEntryExitInstrumenterPass(PassRegistry&);
 void initializeExpandMemCmpPassPass(PassRegistry&);
 void initializeExpandPostRAPass(PassRegistry&);
 void initializeExpandReductionsPass(PassRegistry&);
 void initializeExpandVectorPredicationPass(PassRegistry &);
 void initializeMakeGuardsExplicitLegacyPassPass(PassRegistry&);
 void initializeExternalAAWrapperPassPass(PassRegistry&);
 void initializeFEntryInserterPass(PassRegistry&);
+void initializeFSProfileLoaderPassPass(PassRegistry &);
 void initializeFinalizeISelPass(PassRegistry&);
 void initializeFinalizeMachineBundlesPass(PassRegistry&);
 void initializeFixIrreduciblePass(PassRegistry &);
 void initializeFixupStatepointCallerSavedPass(PassRegistry&);
 void initializeFlattenCFGPassPass(PassRegistry&);
 void initializeFloat2IntLegacyPassPass(PassRegistry&);
 void initializeForceFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeForwardControlFlowIntegrityPass(PassRegistry&);

llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h

 
 template <typename BlockT> struct IRTraits;
 template <> struct IRTraits<BasicBlock> {
   using InstructionT = Instruction;
   using BasicBlockT = BasicBlock;
   using FunctionT = Function;
   using BlockFrequencyInfoT = BlockFrequencyInfo;
   using LoopT = Loop;
-  using LoopInfoT = LoopInfo;
+  using LoopInfoPtrT = std::unique_ptr<LoopInfo>;
+  using DominatorTreePtrT = std::unique_ptr<DominatorTree>;
+  using PostDominatorTreeT = PostDominatorTree;
+  using PostDominatorTreePtrT = std::unique_ptr<PostDominatorTree>;
   using OptRemarkEmitterT = OptimizationRemarkEmitter;
   using OptRemarkAnalysisT = OptimizationRemarkAnalysis;
-  using DominatorTreeT = DominatorTree;
-  using PostDominatorTreeT = PostDominatorTree;
   static Function &getFunction(Function &F) { return F; }
   static const BasicBlock *getEntryBB(const Function *F) {
     return &F->getEntryBlock();
   }
 };
 
 } // end namespace afdo_detail
 
 extern cl::opt<unsigned> SampleProfileMaxPropagateIterations;
 extern cl::opt<unsigned> SampleProfileRecordCoverage;
 extern cl::opt<unsigned> SampleProfileSampleCoverage;
 extern cl::opt<bool> NoWarnSampleUnused;
 
 template <typename BT> class SampleProfileLoaderBaseImpl {
 public:
   SampleProfileLoaderBaseImpl(std::string Name) : Filename(Name) {}
   void dump() { Reader->dump(); }
 
   using InstructionT = typename afdo_detail::IRTraits<BT>::InstructionT;
   using BasicBlockT = typename afdo_detail::IRTraits<BT>::BasicBlockT;
   using BlockFrequencyInfoT =
       typename afdo_detail::IRTraits<BT>::BlockFrequencyInfoT;
   using FunctionT = typename afdo_detail::IRTraits<BT>::FunctionT;
   using LoopT = typename afdo_detail::IRTraits<BT>::LoopT;
-  using LoopInfoT = typename afdo_detail::IRTraits<BT>::LoopInfoT;
+  using LoopInfoPtrT = typename afdo_detail::IRTraits<BT>::LoopInfoPtrT;
+  using DominatorTreePtrT =
+      typename afdo_detail::IRTraits<BT>::DominatorTreePtrT;
+  using PostDominatorTreePtrT =
+      typename afdo_detail::IRTraits<BT>::PostDominatorTreePtrT;
+  using PostDominatorTreeT =
+      typename afdo_detail::IRTraits<BT>::PostDominatorTreeT;
   using OptRemarkEmitterT =
       typename afdo_detail::IRTraits<BT>::OptRemarkEmitterT;
   using OptRemarkAnalysisT =
       typename afdo_detail::IRTraits<BT>::OptRemarkAnalysisT;
-  using DominatorTreeT = typename afdo_detail::IRTraits<BT>::DominatorTreeT;
-  using PostDominatorTreeT =
-      typename afdo_detail::IRTraits<BT>::PostDominatorTreeT;
 
   using BlockWeightMap = DenseMap<const BasicBlockT *, uint64_t>;
   using EquivalenceClassMap =
       DenseMap<const BasicBlockT *, const BasicBlockT *>;
   using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
   using EdgeWeightMap = DenseMap<Edge, uint64_t>;
   using BlockEdgeMap =
       DenseMap<const BasicBlockT *, SmallVector<const BasicBlockT *, 8>>;
protected:
   void printEdgeWeight(raw_ostream &OS, Edge E);
   void printBlockWeight(raw_ostream &OS, const BasicBlockT *BB) const;
   void printBlockEquivalence(raw_ostream &OS, const BasicBlockT *BB);
   bool computeBlockWeights(FunctionT &F);
   void findEquivalenceClasses(FunctionT &F);
   void findEquivalencesFor(BasicBlockT *BB1,
                            ArrayRef<BasicBlockT *> Descendants,
                            PostDominatorTreeT *DomTree);
-
   void propagateWeights(FunctionT &F);
   uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
   void buildEdges(FunctionT &F);
   bool propagateThroughEdges(FunctionT &F, bool UpdateBlockCount);
-  void clearFunctionData();
+  void clearFunctionData(bool ResetDT = true);
   void computeDominanceAndLoopInfo(FunctionT &F);
   bool
   computeAndPropagateWeights(FunctionT &F,
                              const DenseSet<GlobalValue::GUID> &InlinedGUIDs);
   void emitCoverageRemarks(FunctionT &F);
 
   /// Map basic blocks to their computed weights.
   ///
protected:
   ///
   /// Two blocks BB1 and BB2 are in the same equivalence class if they
   /// dominate and post-dominate each other, and they are in the same loop
   /// nest. When this happens, the two blocks are guaranteed to execute
   /// the same number of times.
   EquivalenceClassMap EquivalenceClass;
 
   /// Dominance, post-dominance and loop information.
-  std::unique_ptr<DominatorTreeT> DT;
-  std::unique_ptr<PostDominatorTreeT> PDT;
-  std::unique_ptr<LoopInfoT> LI;
+  DominatorTreePtrT DT;
+  PostDominatorTreePtrT PDT;
+  LoopInfoPtrT LI;
 
   /// Predecessors for each basic block in the CFG.
   BlockEdgeMap Predecessors;
 
   /// Successors for each basic block in the CFG.
   BlockEdgeMap Successors;
 
   /// Profile coverage tracker.
protected:
   ProfileSummaryInfo *PSI = nullptr;
 
   /// Optimization Remark Emitter used to emit diagnostic remarks.
   OptRemarkEmitterT *ORE = nullptr;
 };
 
 /// Clear all the per-function data used to load samples and propagate weights.
 template <typename BT>
-void SampleProfileLoaderBaseImpl<BT>::clearFunctionData() {
+void SampleProfileLoaderBaseImpl<BT>::clearFunctionData(bool ResetDT) {
   BlockWeights.clear();
   EdgeWeights.clear();
   VisitedBlocks.clear();
   VisitedEdges.clear();
   EquivalenceClass.clear();
+  if (ResetDT) {
     DT = nullptr;
     PDT = nullptr;
     LI = nullptr;
+  }
   Predecessors.clear();
   Successors.clear();
   CoverageTracker.clear();
 }
 
 #ifndef NDEBUG
 /// Print the weight of edge \p E on stream \p OS.
 ///
for (auto &BB : F) {
     // 2- BB2 post-dominates BB1.
     // 3- BB1 and BB2 are in the same loop nest.
     //
     // If all those conditions hold, it means that BB2 is executed
     // as many times as BB1, so they are placed in the same equivalence
     // class by making BB2's equivalence class be BB1.
     DominatedBBs.clear();
     DT->getDescendants(BB1, DominatedBBs);
-    findEquivalencesFor(BB1, DominatedBBs, PDT.get());
+    findEquivalencesFor(BB1, DominatedBBs, &*PDT);
 
     LLVM_DEBUG(printBlockEquivalence(dbgs(), BB1));
   }
 
   // Assign weights to equivalence classes.
   //
   // All the basic blocks in the same equivalence class will execute
   // the same number of times. Since we know that the head block in
Func.getContext().diagnose(DiagnosticInfoSampleProfile(
           ": Function profile not used",
       DS_Warning));
   return 0;
 }
 
 template <typename BT>
 void SampleProfileLoaderBaseImpl<BT>::computeDominanceAndLoopInfo(
     FunctionT &F) {
-  DT.reset(new DominatorTreeT);
+  DT.reset(new DominatorTree);
   DT->recalculate(F);
 
   PDT.reset(new PostDominatorTree(F));
 
-  LI.reset(new LoopInfoT);
+  LI.reset(new LoopInfo);
   LI->analyze(*DT);
 }
 
 #undef DEBUG_TYPE
 
 } // namespace llvm
 #endif // LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   ExpandMemCmp.cpp
   ExpandPostRAPseudos.cpp
   ExpandReductions.cpp
   ExpandVectorPredication.cpp
   FaultMaps.cpp
   FEntryInserter.cpp
   FinalizeISel.cpp
   FixupStatepointCallerSaved.cpp
+  FlowSensitiveSampleProfile.cpp
   FuncletLayout.cpp
   GCMetadata.cpp
   GCMetadataPrinter.cpp
   GCRootLowering.cpp
   GlobalMerge.cpp
   HardwareLoops.cpp
   IfConversion.cpp
   ImplicitNullChecks.cpp

llvm/lib/CodeGen/FlowSensitiveSampleProfile.cpp

+//===-------- FlowSensitiveSampleProfile.cpp: Flow Sensitive SampleFDO-----===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides the implementation of the flow sensitive SampleFDO.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/FlowSensitiveSampleProfile.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
+#include "llvm/IR/Function.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h"
+#include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"
+
+using namespace llvm;
+using namespace sampleprof;
+using namespace llvm::sampleprofutil;
+using ProfileCount = Function::ProfileCount;
+
+#define DEBUG_TYPE "fs-profile-loader"
+
+static cl::opt<bool>
+    DisableFSProfileLoader("disable-fs-profile-loader", cl::Hidden,
+                           cl::init(false),
+                           cl::desc("Disable flow senstive profile loading"));
+static cl::opt<bool> EnableFSBranchProb(
+    "enable-fs-branchprob", cl::Hidden, cl::init(true),
+    cl::desc("Enable seting flow senstive branch probabilities"));
+static cl::opt<bool> ShowFSBranchProb(
+    "show-fs-branchprob", cl::Hidden, cl::init(false),
+    cl::desc("Print setting flow senstive branch probabilities"));
+static cl::opt<unsigned> FSProfileDebugProbDiffThreshold(
+    "fs-profile-debug-prob-diff-threshold", cl::init(10),
+    cl::desc("Only show debug message if the branch probility is greater than "
+             "this value (in percentage)."));
+
+static cl::opt<unsigned> FSProfileDebugBWThreshold(
+    "fs-profile-debug-bw-threshold", cl::init(10000),
+    cl::desc("Only show debug message if the source branch weight is greater "
+             " than this value."));
+
+static cl::opt<bool> ViewBFIBefore("fs-viewbfi-before", cl::Hidden,
+                                   cl::init(false),
+                                   cl::desc("View BFI before FS loader"));
+static cl::opt<bool> ViewBFIAfter("fs-viewbfi-after", cl::Hidden,
+                                  cl::init(false),
+                                  cl::desc("View BFI after FS loader"));
+
+char FSProfileLoaderPass::ID = 0;
+
+INITIALIZE_PASS_BEGIN(FSProfileLoaderPass, DEBUG_TYPE,
+                      "Load Flow Sensitive Profile",
+                      /* cfg = */ false, /* is_analysis = */ false)
+INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
+INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
+INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
+INITIALIZE_PASS_END(FSProfileLoaderPass, DEBUG_TYPE,
+                    "Load Flow Sensitive Profile",
+                    /* cfg = */ false, /* is_analysis = */ false)
+
+char &llvm::FSProfileLoaderPassID = FSProfileLoaderPass::ID;
+
+FunctionPass *llvm::createFSProfileLoaderPass(std::string File,
+                                              FSDiscriminatorPass P) {
+  return new FSProfileLoaderPass(File, P);
+}
+
+namespace llvm {
+
+// Internal option used to control BFI display only after MBP pass.
+// Defined in CodeGen/MachineBlockFrequencyInfo.cpp:
+// -view-block-layout-with-bfi={none | fraction | integer | count}
+extern cl::opt<GVDAGType> ViewBlockLayoutWithBFI;
+
+// Command line option to specify the name of the function for CFG dump
+// Defined in Analysis/BlockFrequencyInfo.cpp:  -view-bfi-func-name=
+extern cl::opt<std::string> ViewBlockFreqFuncName;
+
+namespace afdo_detail {
+template <> struct IRTraits<MachineBasicBlock> {
+  using InstructionT = MachineInstr;
+  using BasicBlockT = MachineBasicBlock;
+  using FunctionT = MachineFunction;
+  using BlockFrequencyInfoT = MachineBlockFrequencyInfo;
+  using LoopT = MachineLoop;
+  using LoopInfoPtrT = MachineLoopInfo *;
+  using DominatorTreePtrT = MachineDominatorTree *;
+  using PostDominatorTreePtrT = MachinePostDominatorTree *;
+  using PostDominatorTreeT = MachinePostDominatorTree;
+  using OptRemarkEmitterT = MachineOptimizationRemarkEmitter;
+  using OptRemarkAnalysisT = MachineOptimizationRemarkAnalysis;
+  static Function &getFunction(MachineFunction &F) { return F.getFunction(); }
+  static const MachineBasicBlock *getEntryBB(const MachineFunction *F) {
+    return GraphTraits<const MachineFunction *>::getEntryNode(F);
+  }
+};
+} // namespace afdo_detail
+
+class FSProfileLoader final
+    : public SampleProfileLoaderBaseImpl<MachineBasicBlock> {
+public:
+  void setInitVals(MachineDominatorTree *MDT_, MachinePostDominatorTree *MPDT_,
+                   MachineLoopInfo *MLI_, MachineBlockFrequencyInfo *MBFI_,
+                   MachineOptimizationRemarkEmitter *ORE_) {
+    DT = MDT_;
+    PDT = MPDT_;
+    LI = MLI_;
+    MBFI = MBFI_;
+    ORE = ORE_;
+  }
+  void setFSPass(FSDiscriminatorPass Pass) {
+    P = Pass;
+    LowBit = getFSPassBitBegin(P);
+    HighBit = getFSPassBitEnd(P);
+    assert(LowBit < HighBit && "HighBit needs to be greater than Lowbit");
+  }
+
+  FSProfileLoader(StringRef Name)
+      : SampleProfileLoaderBaseImpl(std::string(Name)) {}
+
+  void setBranchProbs(MachineFunction &F);
+  bool runOnFunction(MachineFunction &F);
+  bool doInitialization(Module &M);
+  bool isValid() const { return ProfileIsValid; }
+
+protected:
+  friend class SampleCoverageTracker;
+
+  /// Hold the information of the basic block frequency.
+  MachineBlockFrequencyInfo *MBFI;
+
+  /// PassNum is the sequence number this pass is called, start from 1.
+  FSDiscriminatorPass P;
+
+  // LowBit in the FS discriminator used by this instance. Note the number is
+  // 0-based. Base discrimnator use bit 0 to bit 11.
+  unsigned LowBit;
+  // HighwBit in the FS discriminator used by this instance. Note the number
+  // is 0-based.
+  unsigned HighBit;
+
+  bool ProfileIsValid = true;
+};
+
+template <>
+void SampleProfileLoaderBaseImpl<
+    MachineBasicBlock>::computeDominanceAndLoopInfo(MachineFunction &F) {}
+
+/// Build in/out edge lists for each basic block in the CFG.
+///
+/// We are interested in unique edges. If a block B1 has multiple
+/// edges to another block B2, we only add a single B1->B2 edge.
+template <>
+void SampleProfileLoaderBaseImpl<MachineBasicBlock>::buildEdges(FunctionT &F) {
+  for (auto &BI : F) {
+    BasicBlockT *B1 = &BI;
+
+    // Add predecessors for B1.
+    SmallPtrSet<BasicBlockT *, 16> Visited;
+    if (!Predecessors[B1].empty())
+      llvm_unreachable("Found a stale predecessors list in a basic block.");
+    for (auto *B2 : B1->predecessors()) {
+      if (Visited.insert(B2).second)
+        Predecessors[B1].push_back(B2);
+    }
+
+    // Add successors for B1.
+    Visited.clear();
+    if (!Successors[B1].empty())
+      llvm_unreachable("Found a stale successors list in a basic block.");
+    for (auto *B2 : B1->successors()) {
+      if (Visited.insert(B2).second)
+        Successors[B1].push_back(B2);
+    }
+  }
+}
+
+void FSProfileLoader::setBranchProbs(MachineFunction &F) {
+  LLVM_DEBUG(dbgs() << "\nPropagation complete. Setting branch probs\n");
+  for (auto &BI : F) {
+    MachineBasicBlock *BB = &BI;
+    if (BB->succ_size() < 2)
+      continue;
+    const MachineBasicBlock *EC = EquivalenceClass[BB];
+    uint64_t BBWeight = BlockWeights[EC];
+    uint64_t SumEdgeWeight = 0;
+    for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
+                                          SE = BB->succ_end();
+         SI != SE; ++SI) {
+      MachineBasicBlock *Succ = *SI;
+      Edge E = std::make_pair(BB, Succ);
+      SumEdgeWeight += EdgeWeights[E];
+    }
+
+    if (BBWeight != SumEdgeWeight) {
+      LLVM_DEBUG(dbgs() << "BBweight is not equal to SumEdgeWeight: BBWWeight="
+                        << BBWeight << " SumEdgeWeight= " << SumEdgeWeight
+                        << "\n");
+      BBWeight = SumEdgeWeight;
+    }
+    if (BBWeight == 0) {
+      LLVM_DEBUG(dbgs() << "SKIPPED. All branch weights are zero.\n");
+      continue;
+    }
+
+    uint64_t BBWeight_Orig = BBWeight;
+    uint32_t MaxWeight = std::numeric_limits<uint32_t>::max();
+    uint32_t Factor = 1;
+    if (BBWeight > MaxWeight) {
+      Factor = BBWeight / MaxWeight + 1;
+      BBWeight /= Factor;
+      LLVM_DEBUG(dbgs() << "Scaling weights by " << Factor << "\n");
+    }
+
+    if (ShowFSBranchProb) {
+      for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
+                                            SE = BB->succ_end();
+           SI != SE; ++SI) {
+        MachineBasicBlock *Succ = *SI;
+        Edge E = std::make_pair(BB, Succ);
+        uint64_t EdgeWeight = EdgeWeights[E];
+        EdgeWeight /= Factor;
+
+        assert(BBWeight >= EdgeWeight &&
+               "BBweight is larger than EdgeWeight -- should not happen.\n");
+
+        BranchProbability OldProb = MBFI->getMBPI()->getEdgeProbability(BB, SI);
+        BranchProbability NewProb(EdgeWeight, BBWeight);
+        if (OldProb == NewProb)
+          continue;
+        BB->setSuccProbability(SI, NewProb);
+        bool Show = false;
+        BranchProbability Diff;
+        if (OldProb > NewProb)
+          Diff = OldProb - NewProb;
+        else
+          Diff = NewProb - OldProb;
+        Show =
+            (Diff >= BranchProbability(FSProfileDebugProbDiffThreshold, 100));
+        Show &= (BBWeight_Orig >= FSProfileDebugBWThreshold);
+
+        auto DIL = BB->findBranchDebugLoc();
+        auto SuccDIL = Succ->findBranchDebugLoc();
+        if (Show) {
+          dbgs() << "Set branch fs prob: MBB (" << BB->getNumber() << " -> "
+                 << Succ->getNumber() << "): ";
+          if (DIL)
+            dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
+                   << DIL->getColumn();
+          if (SuccDIL)
+            dbgs() << "-->" << SuccDIL->getFilename() << ":"
+                   << SuccDIL->getLine() << ":" << SuccDIL->getColumn();
+          dbgs() << " W=" << BBWeight_Orig << "  " << OldProb << " --> "
+                 << NewProb << "\n";
+        }
+      }
+    }
+  }
+}
+
+bool FSProfileLoader::doInitialization(Module &M) {
+  auto &Ctx = M.getContext();
+
+  auto ReaderOrErr =
+      sampleprof::SampleProfileReader::create(Filename, Ctx, P, "");
+  if (std::error_code EC = ReaderOrErr.getError()) {
+    std::string Msg = "Could not open profile: " + EC.message();
+    Ctx.diagnose(DiagnosticInfoSampleProfile(Filename, Msg));
+    return false;
+  }
+
+  Reader = std::move(ReaderOrErr.get());
+  Reader->setModule(&M);
+  ProfileIsValid = (Reader->read() == sampleprof_error::success);
+  Reader->getSummary();
+
+  return true;
+}
+
+bool FSProfileLoader::runOnFunction(FunctionT &F) {
+  Function &Func = F.getFunction();
+  clearFunctionData(false);
+  Samples = Reader->getSamplesFor(Func);
+  if (!Samples || Samples->empty())
+    return false;
+
+  if (getFunctionLoc(F) == 0)
+    return false;
+
+  DenseSet<GlobalValue::GUID> InlinedGUIDs;
+  bool Changed = computeAndPropagateWeights(F, InlinedGUIDs);
+
+  // Set the new BPI, BFI.
+  if (EnableFSBranchProb)
+    setBranchProbs(F);
+
+  return Changed;
+}
+
+} // namespace llvm
+
+bool FSProfileLoaderPass::runOnMachineFunction(MachineFunction &mf) {
+  if (DisableFSProfileLoader)
+    return false;
+  if (!FSSampleLoader->isValid())
+    return false;
+
+  MF = &mf;
+  LLVM_DEBUG(dbgs() << "FSProfileLoader pass working on Func: "
+                    << MF->getFunction().getName() << "\n");
+  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
+  FSSampleLoader->setInitVals(
+      &getAnalysis<MachineDominatorTree>(),
+      &getAnalysis<MachinePostDominatorTree>(), &getAnalysis<MachineLoopInfo>(),
+      MBFI, &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE());
+
+  MF->RenumberBlocks();
+  if (ViewBFIBefore && ViewBlockLayoutWithBFI != GVDT_None &&
+      (ViewBlockFreqFuncName.empty() ||
+       MF->getFunction().getName().equals(ViewBlockFreqFuncName))) {
+    MBFI->view("FSP_b." + MF->getName(), false);
+  }
+
+  bool Changed = FSSampleLoader->runOnFunction(mf);
+
+  if (ViewBFIAfter && ViewBlockLayoutWithBFI != GVDT_None &&
+      (ViewBlockFreqFuncName.empty() ||
+       MF->getFunction().getName().equals(ViewBlockFreqFuncName))) {
+    MBFI->view("FSP_a." + MF->getName(), false);
+  }
+
+  return Changed;
+}
+
+bool FSProfileLoaderPass::doInitialization(Module &M) {
+  if (DisableFSProfileLoader)
+    return false;
+  LLVM_DEBUG(dbgs() << "FSProfileLoader pass working on Module " << M.getName()
+                    << "\n");
+
+  FSSampleLoader->setFSPass(P);
+  return FSSampleLoader->doInitialization(M);
+}
+
+void FSProfileLoaderPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  AU.addRequired<MachineBlockFrequencyInfo>();
+  AU.addRequired<MachineDominatorTree>();
+  AU.addRequired<MachinePostDominatorTree>();
+  AU.addRequiredTransitive<MachineLoopInfo>();
+  AU.addRequired<MachineOptimizationRemarkEmitterPass>();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}

llvm/lib/CodeGen/TargetPassConfig.cpp

struct InsertedPass {
   }
 };
 
 } // end anonymous namespace
 
 namespace llvm {
 
 extern cl::opt<bool> EnableFSDiscriminator;
+extern cl::opt<std::string> FSProfileFile;
 
 class PassConfigImpl {
 public:
   // List of passes explicitly substituted by this target. Normally this is
   // empty, but it is a convenient way to suppress or replace specific passes
   // that are part of a standard pass pipeline without overridding the entire
   // pipeline. This mechanism allows target options to inherit a standard pass's
   // user interface. For example, a target may disable a standard pass by

 
 /// -regalloc=... command line option.
 static FunctionPass *useDefaultRegisterAllocator() { return nullptr; }
 static cl::opt<RegisterRegAlloc::FunctionPassCtor, false,
                RegisterPassParser<RegisterRegAlloc>>
     RegAlloc("regalloc", cl::Hidden, cl::init(&useDefaultRegisterAllocator),
              cl::desc("Register allocator to use"));
 
+static std::string getFSProfileFile() {
+  if (FSProfileFile.empty() || !EnableFSDiscriminator)
+    return std::string();
+  return FSProfileFile.getValue();
+}
+
 /// Add the complete set of target-independent postISel code generator passes.
 ///
 /// This can be read as the standard order of major LLVM CodeGen stages. Stages
 /// with nontrivial configuration or multiple passes are broken out below in
 /// add%Stage routines.
 ///
 /// Any TargetPassConfig::addXX routine may be overriden by the Target. The
 /// addPre/Post methods with empty header implementations allow injecting
void TargetPassConfig::addMachinePasses() {
   // Run pre-ra passes.
   addPreRegAlloc();
 
   // Debugifying the register allocator passes seems to provoke some
   // non-determinism that affects CodeGen and there doesn't seem to be a point
   // where it becomes safe again so stop debugifying here.
   DebugifyIsSafe = false;
 
+  if (EnableFSDiscriminator)
+    addPass(createMIRAddFSDiscriminatorsPass(
+        sampleprof::FSDiscriminatorPass::Pass1));
+  std::string FSFile = getFSProfileFile();
+  if (!FSFile.empty())
+    addPass(createFSProfileLoaderPass(FSFile,
+                                      sampleprof::FSDiscriminatorPass::Pass1));
+
   // Run register allocation and passes that are tightly coupled with it,
   // including phi elimination and scheduling.
   if (getOptimizeRegAlloc())
     addOptimizedRegAlloc();
   else
     addFastRegAlloc();
 
   // Run post-ra passes.

 /// Add standard GC passes.
 bool TargetPassConfig::addGCPasses() {
   addPass(&GCMachineCodeAnalysisID, false);
   return true;
 }
 
 /// Add standard basic block placement passes.
 void TargetPassConfig::addBlockPlacement() {
+  if (EnableFSDiscriminator)
+    addPass(createMIRAddFSDiscriminatorsPass(
+        sampleprof::FSDiscriminatorPass::Pass2));
+  std::string FSFile = getFSProfileFile();
+  if (!FSFile.empty())
+    addPass(createFSProfileLoaderPass(FSFile,
+                                      sampleprof::FSDiscriminatorPass::Pass2));
   if (addPass(&MachineBlockPlacementID)) {
     // Run a separate pass to collect block placement statistics.
     if (EnableBlockPlacementStats)
       addPass(&MachineBlockPlacementStatsID);
   }
 }
 
 //===---------------------------------------------------------------------===//

llvm/lib/Passes/PassBuilder.cpp

 extern cl::opt<bool> EnableLoopFlatten;
 extern cl::opt<bool> EnableDFAJumpThreading;
 extern cl::opt<bool> RunNewGVN;
 extern cl::opt<bool> RunPartialInlining;
 extern cl::opt<bool> ExtraVectorizerPasses;
 
 extern cl::opt<bool> FlattenedProfileUsed;
 
+extern cl::opt<std::string> FSProfileFile;
 extern cl::opt<AttributorRunOption> AttributorRun;
 extern cl::opt<bool> EnableKnowledgeRetention;
 
 extern cl::opt<bool> EnableMatrix;
 
 extern cl::opt<bool> DisablePreInliner;
 extern cl::opt<int> PreInlineThreshold;
 } // namespace llvm
PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
   // In SamplePGO ThinLTO backend, we need instcombine before profile annotation
   // to convert bitcast to direct calls so that they can be inlined during the
   // profile annotation prepration step.
   // More details about SamplePGO design can be found in:
   // https://research.google.com/pubs/pub45290.html
   // FIXME: revisit how SampleProfileLoad/Inliner/ICP is structured.
   if (LoadSampleProfile)
     EarlyFPM.addPass(InstCombinePass());
+
   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(EarlyFPM)));
 
   if (LoadSampleProfile) {
     // Annotate sample profile right after early FPM to ensure freshness of
     // the debug info.
     MPM.addPass(SampleProfileLoaderPass(PGOOpt->ProfileFile,
                                         PGOOpt->ProfileRemappingFile, Phase));
     // Cache ProfileSummaryAnalysis once to avoid the potential need to insert
     // RequireAnalysisPass for PSI before subsequent non-module passes.
     MPM.addPass(RequireAnalysisPass<ProfileSummaryAnalysis, Module>());
     // Do not invoke ICP in the LTOPrelink phase as it makes it hard
     // for the profile annotation to be accurate in the LTO backend.
     if (Phase != ThinOrFullLTOPhase::ThinLTOPreLink &&
-        Phase != ThinOrFullLTOPhase::FullLTOPreLink)
+        Phase != ThinOrFullLTOPhase::FullLTOPreLink) {
       // We perform early indirect call promotion here, before globalopt.
       // This is important for the ThinLTO backend phase because otherwise
       // imported available_externally functions look unreferenced and are
       // removed.
       MPM.addPass(
           PGOIndirectCallPromotion(true /* IsInLTO */, true /* SamplePGO */));
+
+      // Set FSProfileFile so that CodeGen can read the profile.
+      FSProfileFile.setValue(PGOOpt->ProfileFile);
+    }
   }
 
   // Try to perform OpenMP specific optimizations on the module. This is a
   // (quick!) no-op if there are no OpenMP runtime calls present in the module.
   if (Level != OptimizationLevel::O0)
     MPM.addPass(OpenMPOptPass());
 
   if (AttributorRun & AttributorRunOption::MODULE)
PassBuilder::buildLTODefaultPipeline(OptimizationLevel Level,
   if (PGOOpt && PGOOpt->Action == PGOOptions::SampleUse) {
     // Load sample profile before running the LTO optimization pipeline.
     MPM.addPass(SampleProfileLoaderPass(PGOOpt->ProfileFile,
                                         PGOOpt->ProfileRemappingFile,
                                         ThinOrFullLTOPhase::FullLTOPostLink));
     // Cache ProfileSummaryAnalysis once to avoid the potential need to insert
     // RequireAnalysisPass for PSI before subsequent non-module passes.
     MPM.addPass(RequireAnalysisPass<ProfileSummaryAnalysis, Module>());
+
+    // Set FSProfileFile so that CodeGen can read the profile.
+    FSProfileFile.setValue(PGOOpt->ProfileFile);
   }
 
   // Remove unused virtual tables to improve the quality of code generated by
   // whole-program devirtualization and bitset lowering.
   MPM.addPass(GlobalDCEPass());
 
   // Force any function attributes we want the rest of the pipeline to observe.
   MPM.addPass(ForceFunctionAttrsPass());

llvm/lib/ProfileData/SampleProf.cpp

 using namespace sampleprof;
 
 static cl::opt<uint64_t> ProfileSymbolListCutOff(
     "profile-symbol-list-cutoff", cl::Hidden, cl::init(-1), cl::ZeroOrMore,
     cl::desc("Cutoff value about how many symbols in profile symbol list "
              "will be used. This is very useful for performance debugging"));
 
 namespace llvm {
+
+cl::opt<std::string>
+    FSProfileFile("fs-profile-file", cl::init(""), cl::value_desc("filename"),
+                  cl::desc("Flow Sensitive profile file name."), cl::Hidden);
+
 namespace sampleprof {
 SampleProfileFormat FunctionSamples::Format;
 bool FunctionSamples::ProfileIsProbeBased = false;
 bool FunctionSamples::ProfileIsCS = false;
 bool FunctionSamples::UseMD5 = false;
 bool FunctionSamples::HasUniqSuffix = true;
 bool FunctionSamples::ProfileIsFS = false;
 } // namespace sampleprof

llvm/test/CodeGen/X86/Inputs/fsloader.afdo

+work:42380966:1346190
+ 1: 1246499
+ 5: 1246499
+foo:28798256:4267
+ 0: 4267
+ 2.1: 255999
+ 4: 264627 bar:250018
+ 4.512: 269485 bar:278102
+ 4.4608: 280297 bar:280933
+ 4.12288: 278916 bar:267752
+ 5: 264627
+ 5.4096: 269485
+ 5.8192: 260670
+ 5.8704: 278916
+ 6: 11541
+ 6.3584: 278916 work:284547
+ 6.4096: 260670 work:249428
+ 6.8704: 11541
+ 7: 272442
+ 7.512: 283590
+ 7.4608: 234082
+ 7.9728: 279149
+ 8: 11541
+ 8.11776: 283590 work:305061
+ 8.12288: 279149 work:281368
+ 8.13824: 234082 work:225786
+ 10: 4050
+bar:9504180:1076805
+ 2: 1056020
+ 3: 1056020
+main:20360:0
+ 0: 0
+ 2.1: 4045
+ 3: 4156 foo:4267
+ 5: 0

llvm/test/CodeGen/X86/fsafdo_test1.ll

 ; RUN: llc -enable-fs-discriminator < %s | FileCheck %s
 ;
 ; Check that fs-afdo discriminators are generated.
 ; CHECK: .loc    1 7 3 is_stmt 0 discriminator 2 # foo.c:7:3
 ; Check: .loc    1 9 5 is_stmt 1 discriminator 2 # foo.c:9:5
-; CHECK: .loc    1 9 5 is_stmt 0 discriminator 268435458 # foo.c:9:5
-; CHECK: .loc    1 7 3 is_stmt 1 discriminator 3892314114 # foo.c:7:3
+; CHECK: .loc    1 9 5 is_stmt 0 discriminator 11266 # foo.c:9:5
+; CHECK: .loc    1 7 3 is_stmt 1 discriminator 11266 # foo.c:7:3
 ; Check that variable __llvm_fs_discriminator__ is generated.
 ; CHECK: .type   __llvm_fs_discriminator__,@object # @__llvm_fs_discriminator__
 ; CHECK: .section        .rodata,"a",@progbits
 ; CHECK: .weak   __llvm_fs_discriminator__
 ; CHECK: __llvm_fs_discriminator__:
 ; CHECK: .byte   1
 ; CHECK: .size   __llvm_fs_discriminator__, 1
 

llvm/test/CodeGen/X86/fsafdo_test2.ll

 ; RUN: llc -enable-fs-discriminator < %s | FileCheck %s
+; RUN: llvm-profdata merge --sample -profile-isfs -o %t.afdo %S/Inputs/fsloader.afdo
+; RUN: llc -enable-fs-discriminator -fs-profile-file=%t.afdo -show-fs-branchprob < %s 2>&1 | FileCheck %s --check-prefix=LOADER
+;
 ;;
 ;; C source code for the test (compiler at -O3):
 ;; // A test case for loop unroll.
 ;;
 ;; __attribute__((noinline)) int bar(int i){
 ;;   volatile int j;
 ;;   j = i;
 ;;   return j;

 ;;   int i;
 ;;   for (i = 0; i < 10000000; i++) {
 ;;     foo();
 ;;   }
 ;; }
 ;;
 ;; Check that fs-afdo discriminators are generated.
 ; CHECK: .loc    1 23 9 is_stmt 0 discriminator 1 # unroll.c:23:9
-; CHECK: .loc    1 23 9 is_stmt 0 discriminator 3892314113 # unroll.c:23:9
-; CHECK: .loc    1 23 9 is_stmt 0 discriminator 2818572289 # unroll.c:23:9
-; CHECK: .loc    1 23 9 is_stmt 0 discriminator 3623878657 # unroll.c:23:9
+; CHECK: .loc    1 23 9 is_stmt 0 discriminator 3585 # unroll.c:23:9
+; CHECK: .loc    1 23 9 is_stmt 0 discriminator 8705 # unroll.c:23:9
+; CHECK: .loc    1 23 9 is_stmt 0 discriminator 4097 # unroll.c:23:9
 ;;
 ;; Check that variable __llvm_fs_discriminator__ is generated.
 ; CHECK: .type   __llvm_fs_discriminator__,@object # @__llvm_fs_discriminator__
 ; CHECK: .section        .rodata,"a",@progbits
 ; CHECK: .weak   __llvm_fs_discriminator__
 ; CHECK: __llvm_fs_discriminator__:
 ; CHECK: .byte   1
 ; CHECK: .size   __llvm_fs_discriminator__, 1
 
+;; Check that new branch probs are generated.
+; LOADER: Set branch fs prob: MBB (1 -> 3): unroll.c:22:11-->unroll.c:24:11 W=283590  0x40000000 / 0x80000000 = 50.00% --> 0x7aca7894 / 0x80000000 = 95.93%
+; LOADER: Set branch fs prob: MBB (1 -> 2): unroll.c:22:11 W=283590  0x40000000 / 0x80000000 = 50.00% --> 0x0535876c / 0x80000000 = 4.07%
+; LOADER: Set branch fs prob: MBB (3 -> 5): unroll.c:24:11-->unroll.c:22:11 W=283590  0x30000000 / 0x80000000 = 37.50% --> 0x7aca7894 / 0x80000000 = 95.93%
+; LOADER: Set branch fs prob: MBB (3 -> 4): unroll.c:24:11 W=283590  0x50000000 / 0x80000000 = 62.50% --> 0x0535876c / 0x80000000 = 4.07%
+; LOADER: Set branch fs prob: MBB (5 -> 8): unroll.c:22:11-->unroll.c:24:11 W=283590  0x40000000 / 0x80000000 = 50.00% --> 0x021c112e / 0x80000000 = 1.65%
+; LOADER: Set branch fs prob: MBB (5 -> 7): unroll.c:22:11 W=283590  0x40000000 / 0x80000000 = 50.00% --> 0x7de3eed2 / 0x80000000 = 98.35%
+; LOADER: Set branch fs prob: MBB (8 -> 10): unroll.c:24:11-->unroll.c:22:11 W=283590  0x30000000 / 0x80000000 = 37.50% --> 0x00000000 / 0x80000000 = 0.00%
+; LOADER: Set branch fs prob: MBB (8 -> 9): unroll.c:24:11 W=283590  0x50000000 / 0x80000000 = 62.50% --> 0x80000000 / 0x80000000 = 100.00%
+; LOADER: Set branch fs prob: MBB (10 -> 12): unroll.c:22:11-->unroll.c:24:11 W=283590  0x40000000 / 0x80000000 = 50.00% --> 0x7aca7894 / 0x80000000 = 95.93%
+; LOADER: Set branch fs prob: MBB (10 -> 11): unroll.c:22:11 W=283590  0x40000000 / 0x80000000 = 50.00% --> 0x0535876c / 0x80000000 = 4.07%
+; LOADER: Set branch fs prob: MBB (12 -> 14): unroll.c:24:11-->unroll.c:22:11 W=283590  0x30000000 / 0x80000000 = 37.50% --> 0x02012507 / 0x80000000 = 1.57%
+; LOADER: Set branch fs prob: MBB (12 -> 13): unroll.c:24:11 W=283590  0x50000000 / 0x80000000 = 62.50% --> 0x7dfedaf9 / 0x80000000 = 98.43%
+; LOADER: Set branch fs prob: MBB (14 -> 16): unroll.c:22:11-->unroll.c:24:11 W=283590  0x40000000 / 0x80000000 = 50.00% --> 0x0a5856e1 / 0x80000000 = 8.08%
+; LOADER: Set branch fs prob: MBB (14 -> 15): unroll.c:22:11 W=283590  0x40000000 / 0x80000000 = 50.00% --> 0x75a7a91f / 0x80000000 = 91.92%
+; LOADER: Set branch fs prob: MBB (16 -> 18): unroll.c:24:11-->unroll.c:19:3 W=283590  0x30000000 / 0x80000000 = 37.50% --> 0x16588166 / 0x80000000 = 17.46%
+; LOADER: Set branch fs prob: MBB (16 -> 17): unroll.c:24:11 W=283590  0x50000000 / 0x80000000 = 62.50% --> 0x69a77e9a / 0x80000000 = 82.54%
+
+
 target triple = "x86_64-unknown-linux-gnu"
 
 @sum = dso_local local_unnamed_addr global i32 0, align 4
 
 declare i32 @bar(i32 %i) #0
 declare void @work(i32 %i) #2
 
 define dso_local void @foo() #0 !dbg !29 {