[PGO][CHR] Add opt remarks.

[davidxl]

lib/Transforms/Instrumentation/ControlHeightReduction.cpp

1166

Can you make the missed reason string clearer?

1202

Similarly here.

1328

You can pass the argument to the ORE object with ore::NV type:

OptimizationMarkMissed ORE(DEBUG_TYPE, ....);
ORE << "Drop scope with < " << ore::NV("CHRMergeThreshold", CHRMergeThreshold) << ...

1827

use ore::NV to pass argument.

2026

The message already includes the module name, so there is no need to do it here.

Also the function name can be passed as NV:

ORE<< ore::NV("Function", &F) << "Reduced .... by " << ore::NV("NumBranchesDelta", Stats.NumBranchesDelta) << " (static ) ...." ...

[hjyamauchi]

Comments addressed.

[davidxl]

lgtm

lib/Transforms/Instrumentation/ControlHeightReduction.cpp

 
 #include "llvm/Transforms/Instrumentation/ControlHeightReduction.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/MDBuilder.h"
private:
   CHRScope(SmallVector<RegInfo, 8> &RegInfosIn,
            SmallVector<CHRScope *, 8> &SubsIn)
     : RegInfos(RegInfosIn), Subs(SubsIn), BranchInsertPoint(nullptr) {}
 };
 
 class CHR {
  public:
   CHR(Function &Fin, BlockFrequencyInfo &BFIin, DominatorTree &DTin,
-      ProfileSummaryInfo &PSIin, RegionInfo &RIin)
-      : F(Fin), BFI(BFIin), DT(DTin), PSI(PSIin), RI(RIin) {}
+      ProfileSummaryInfo &PSIin, RegionInfo &RIin,
+      OptimizationRemarkEmitter &OREin)
+      : F(Fin), BFI(BFIin), DT(DTin), PSI(PSIin), RI(RIin), ORE(OREin) {}
 
   ~CHR() {
     for (CHRScope *Scope : Scopes) {
       delete Scope;
     }
   }
 
   bool run();
void addToMergedCondition(bool IsTrueBiased, Value *Cond,
                             IRBuilder<> &IRB,
                             Value *&MergedCondition);
 
   Function &F;
   BlockFrequencyInfo &BFI;
   DominatorTree &DT;
   ProfileSummaryInfo &PSI;
   RegionInfo &RI;
+  OptimizationRemarkEmitter &ORE;
   CHRStats Stats;
 
   // All the true-biased regions in the function
   DenseSet<Region *> TrueBiasedRegionsGlobal;
   // All the false-biased regions in the function
   DenseSet<Region *> FalseBiasedRegionsGlobal;
   // All the true-biased selects in the function
   DenseSet<SelectInst *> TrueBiasedSelectsGlobal;
if (BI && BI->isConditional()) {
         RegInfo RI(R);
         RI.HasBranch = checkBiasedBranch(
             BI, R, TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,
             BranchBiasMap);
         Result = new CHRScope(RI);
         Scopes.insert(Result);
         CHR_DEBUG(dbgs() << "Found a region with a branch\n");
         ++Stats.NumBranches;
+        if (!RI.HasBranch) {
+          ORE.emit([&]() {
+            return OptimizationRemarkMissed(DEBUG_TYPE, "BranchNotBiased", BI)
+                << "Branch not biased";
+          });
+        }
       }
     }
   }
   {
     // Try to look for selects in the direct child blocks (as opposed to in
     // subregions) of R.
     // ...
     // if (..) { // Some subregion
if (Exit) {
     if (Selects.size() > 0) {
       auto AddSelects = [&](RegInfo &RI) {
         for (auto *SI : Selects)
           if (checkBiasedSelect(SI, RI.R,
                                 TrueBiasedSelectsGlobal,
                                 FalseBiasedSelectsGlobal,
                                 SelectBiasMap))
             RI.Selects.push_back(SI);
+          else
+            ORE.emit([&]() {
+              return OptimizationRemarkMissed(DEBUG_TYPE, "SelectNotBiased", SI)
+                  << "Select not biased";
+            });
       };
       if (!Result) {
         CHR_DEBUG(dbgs() << "Found a select-only region\n");
         RegInfo RI(R);
         AddSelects(RI);
         Result = new CHRScope(RI);
         Scopes.insert(Result);
       } else {
for (auto it = Selects.begin(); it != Selects.end(); ) {
       if (SI == InsertPoint) {
         ++it;
         continue;
       }
       bool IsHoistable = checkHoistValue(SI->getCondition(), InsertPoint,
                                          DT, Unhoistables, nullptr);
       if (!IsHoistable) {
         CHR_DEBUG(dbgs() << "Dropping select " << *SI << "\n");
+        ORE.emit([&]() {
+          return OptimizationRemarkMissed(DEBUG_TYPE,
+                                          "DropUnhoistableSelect", SI)
+              << "Dropped unhoistable select";
+        });
         it = Selects.erase(it);
         // Since we are dropping the select here, we also drop it from
         // Unhoistables.
         Unhoistables.erase(SI);
       } else
         ++it;
     }
     // Update InsertPoint after potentially removing selects.
     InsertPoint = getBranchInsertPoint(RI);
     CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n");
     if (RI.HasBranch && InsertPoint != Branch) {
       bool IsHoistable = checkHoistValue(Branch->getCondition(), InsertPoint,
                                          DT, Unhoistables, nullptr);
       if (!IsHoistable) {
         // If the branch isn't hoistable, drop the selects in the entry
         // block, preferring the branch, which makes the branch the hoist
         // point.
         assert(InsertPoint != Branch && "Branch must not be the hoist point");
         CHR_DEBUG(dbgs() << "Dropping selects in entry block \n");
         CHR_DEBUG(
             for (SelectInst *SI : Selects) {
               dbgs() << "SI " << *SI << "\n";
             });
+        for (SelectInst *SI : Selects) {
+          ORE.emit([&]() {
+            return OptimizationRemarkMissed(DEBUG_TYPE,
+                                            "DropSelectUnhoistableBranch", SI)
+                << "Dropped select due to unhoistable branch";
+          });
+        }
         Selects.erase(std::remove_if(Selects.begin(), Selects.end(),
                                      [EntryBB](SelectInst *SI) {
                                        return SI->getParent() == EntryBB;
                                      }), Selects.end());
         Unhoistables.clear();
         InsertPoint = Branch;
       }
     }
if (RI.R == RegInfos[0].R) {
       if (Outer) {
         CHR_DEBUG(dbgs() << "Outer " << *Outer << "\n");
         CHR_DEBUG(dbgs() << "Should split from outer at "
                   << RI.R->getNameStr() << "\n");
         if (shouldSplit(OuterInsertPoint, *OuterConditionValues,
                         ConditionValues, DT, Unhoistables)) {
           PrevConditionValues = ConditionValues;
           PrevInsertPoint = InsertPoint;
+          ORE.emit([&]() {
+            return OptimizationRemarkMissed(DEBUG_TYPE,
+                                            "SplitScopeFromOuter",
+                                            RI.R->getEntry()->getTerminator())
+                << "Split scope from outer due to unhoistable branch/select "
+                << "and/or lack of common condition values";
+          });
         } else {
           // Not splitting from the outer. Use the outer bases and insert
           // point. Union the bases.
           PrevSplitFromOuter = false;
           PrevConditionValues = *OuterConditionValues;
           PrevConditionValues.insert(ConditionValues.begin(),
                                      ConditionValues.end());
           PrevInsertPoint = OuterInsertPoint;
if (RI.R == RegInfos[0].R) {
         Splits.push_back(Scope);
         SplitsSplitFromOuter.push_back(PrevSplitFromOuter);
         SplitsConditionValues.push_back(PrevConditionValues);
         SplitsInsertPoints.push_back(PrevInsertPoint);
         Scope = Tail;
         PrevConditionValues = ConditionValues;
         PrevInsertPoint = InsertPoint;
         PrevSplitFromOuter = true;
+        ORE.emit([&]() {
+          return OptimizationRemarkMissed(DEBUG_TYPE,
+                                          "SplitScopeFromPrev",
+                                          RI.R->getEntry()->getTerminator())
+              << "Split scope from previous due to unhoistable branch/select "
+              << "and/or lack of common condition values";
+        });
       } else {
         // Not splitting. Union the bases. Keep the hoist point.
         PrevConditionValues.insert(ConditionValues.begin(), ConditionValues.end());
       }
     }
   }
   Splits.push_back(Scope);
   SplitsSplitFromOuter.push_back(PrevSplitFromOuter);
void CHR::filterScopes(SmallVectorImpl<CHRScope *> &Input,
   for (CHRScope *Scope : Input) {
     // Filter out the ones with only one region and no subs.
     if (!hasAtLeastTwoBiasedBranches(Scope)) {
       CHR_DEBUG(dbgs() << "Filtered out by biased branches truthy-regions "
                 << Scope->TrueBiasedRegions.size()
                 << " falsy-regions " << Scope->FalseBiasedRegions.size()
                 << " true-selects " << Scope->TrueBiasedSelects.size()
                 << " false-selects " << Scope->FalseBiasedSelects.size() << "\n");
+      ORE.emit([&]() {
+        return OptimizationRemarkMissed(
+            DEBUG_TYPE,
+            "DropScopeWithOneBranchOrSelect",
+            Scope->RegInfos[0].R->getEntry()->getTerminator())
+            << "Drop scope with < "
+            << ore::NV("CHRMergeThreshold", CHRMergeThreshold)
+            << " biased branch(es) or select(s)";
+      });
       continue;
     }
     Output.push_back(Scope);
   }
 }
 
 void CHR::setCHRRegions(SmallVectorImpl<CHRScope *> &Input,
                         SmallVectorImpl<CHRScope *> &Output) {
for (RegInfo &RI : Scope->CHRRegions) {
     }
     for (SelectInst *SI : RI.Selects) {
       fixupSelect(SI, Scope, IRB, MergedCondition, CHRBranchBias);
       ++NumCHRedBranches;
     }
   }
   Stats.NumBranchesDelta += NumCHRedBranches - 1;
   Stats.WeightedNumBranchesDelta += (NumCHRedBranches - 1) * ProfileCount;
+  ORE.emit([&]() {
+    return OptimizationRemark(DEBUG_TYPE,
+                              "CHR",
+                              // Refer to the hot (original) path
+                              MergedBR->getSuccessor(0)->getTerminator())
+        << "Merged " << ore::NV("NumCHRedBranches", NumCHRedBranches)
+        << " branches or selects";
+  });
   MergedBR->setCondition(MergedCondition);
   SmallVector<uint32_t, 2> Weights;
   Weights.push_back(static_cast<uint32_t>(CHRBranchBias.scale(1000)));
   Weights.push_back(static_cast<uint32_t>(CHRBranchBias.getCompl().scale(1000)));
   MDBuilder MDB(F.getContext());
   MergedBR->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
   CHR_DEBUG(dbgs() << "CHR branch bias " << Weights[0] << ":" << Weights[1]
             << "\n");
bool Changed = false;
 
     // Apply the CHR transformation.
     if (!SortedScopes.empty()) {
       transformScopes(SortedScopes);
       Changed = true;
     }
   }
 
-  if (Changed)
+  if (Changed) {
     CHR_DEBUG(dumpIR(F, "after", &Stats));
+    ORE.emit([&]() {
+      return OptimizationRemark(DEBUG_TYPE, "Stats", &F)
+          << ore::NV("Function", &F) << " "
+          << "Reduced the number of branches in hot paths by "
+          << ore::NV("NumBranchesDelta", Stats.NumBranchesDelta)
+          << " (static) and "
+          << ore::NV("WeightedNumBranchesDelta", Stats.WeightedNumBranchesDelta)
+          << " (weighted by PGO count)";
+    });
+  }
 
   return Changed;
 }
 
 bool ControlHeightReductionLegacyPass::runOnFunction(Function &F) {
   BlockFrequencyInfo &BFI =
       getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   ProfileSummaryInfo &PSI =
       *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
   RegionInfo &RI = getAnalysis<RegionInfoPass>().getRegionInfo();
-  return CHR(F, BFI, DT, PSI, RI).run();
+  std::unique_ptr<OptimizationRemarkEmitter> OwnedORE =
+      llvm::make_unique<OptimizationRemarkEmitter>(&F);
+  return CHR(F, BFI, DT, PSI, RI, *OwnedORE.get()).run();
 }
 
 namespace llvm {
 
 ControlHeightReductionPass::ControlHeightReductionPass() {
   parseCHRFilterFiles();
 }
 
 PreservedAnalyses ControlHeightReductionPass::run(
     Function &F,
     FunctionAnalysisManager &FAM) {
   auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
   auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
   auto &MAMProxy = FAM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
   auto &MAM = MAMProxy.getManager();
   auto &PSI = *MAM.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
   auto &RI = FAM.getResult<RegionInfoAnalysis>(F);
-  bool Changed = CHR(F, BFI, DT, PSI, RI).run();
+  auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
+  bool Changed = CHR(F, BFI, DT, PSI, RI, ORE).run();
   if (!Changed)
     return PreservedAnalyses::all();
   auto PA = PreservedAnalyses();
   PA.preserve<GlobalsAA>();
   return PA;
 }
 
 } // namespace llvm