llvm/lib/Analysis/CtxProfAnalysis.cpp

   1 //===- CtxProfAnalysis.cpp - contextual profile analysis ------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Implementation of the contextual profile analysis, which maintains contextual
  10 // profiling info through IPO passes.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Analysis/CtxProfAnalysis.h"
  15 #include "llvm/ADT/STLExtras.h"
  16 #include "llvm/IR/Analysis.h"
  17 #include "llvm/IR/IntrinsicInst.h"
  18 #include "llvm/IR/Module.h"
  19 #include "llvm/IR/PassManager.h"
  20 #include "llvm/ProfileData/PGOCtxProfReader.h"
  21 #include "llvm/Support/CommandLine.h"
  22 #include "llvm/Support/MemoryBuffer.h"
  23
  24 #define DEBUG_TYPE "ctx_prof"
  25
  26 using namespace llvm;
  27 cl::opt<std::string>
  28     UseCtxProfile("use-ctx-profile", cl::init(""), cl::Hidden,
  29                   cl::desc("Use the specified contextual profile file"));
  30
  31 static cl::opt<CtxProfAnalysisPrinterPass::PrintMode> PrintLevel(
  32     "ctx-profile-printer-level",
  33     cl::init(CtxProfAnalysisPrinterPass::PrintMode::YAML), cl::Hidden,
  34     cl::values(clEnumValN(CtxProfAnalysisPrinterPass::PrintMode::Everything,
  35                           "everything", "print everything - most verbose"),
  36                clEnumValN(CtxProfAnalysisPrinterPass::PrintMode::YAML, "yaml",
  37                           "just the yaml representation of the profile")),
  38     cl::desc("Verbosity level of the contextual profile printer pass."));
  39
  40 const char *AssignGUIDPass::GUIDMetadataName = "guid";
  41
  42 PreservedAnalyses AssignGUIDPass::run(Module &M, ModuleAnalysisManager &MAM) {
  43   for (auto &F : M.functions()) {
  44     if (F.isDeclaration())
  45       continue;
  46     if (F.getMetadata(GUIDMetadataName))
  47       continue;
  48     const GlobalValue::GUID GUID = F.getGUID();
  49     F.setMetadata(GUIDMetadataName,
  50                   MDNode::get(M.getContext(),
  51                               {ConstantAsMetadata::get(ConstantInt::get(
  52                                   Type::getInt64Ty(M.getContext()), GUID))}));
  53   }
  54   return PreservedAnalyses::none();
  55 }
  56
  57 GlobalValue::GUID AssignGUIDPass::getGUID(const Function &F) {
  58   if (F.isDeclaration()) {
  59     assert(GlobalValue::isExternalLinkage(F.getLinkage()));
  60     return GlobalValue::getGUID(F.getGlobalIdentifier());
  61   }
  62   auto *MD = F.getMetadata(GUIDMetadataName);
  63   assert(MD && "guid not found for defined function");
  64   return cast<ConstantInt>(cast<ConstantAsMetadata>(MD->getOperand(0))
  65                                ->getValue()
  66                                ->stripPointerCasts())
  67       ->getZExtValue();
  68 }
  69 AnalysisKey CtxProfAnalysis::Key;
  70
  71 CtxProfAnalysis::CtxProfAnalysis(std::optional<StringRef> Profile)
  72     : Profile([&]() -> std::optional<StringRef> {
  73         if (Profile)
  74           return *Profile;
  75         if (UseCtxProfile.getNumOccurrences())
  76           return UseCtxProfile;
  77         return std::nullopt;
  78       }()) {}
  79
  80 PGOContextualProfile CtxProfAnalysis::run(Module &M,
  81                                           ModuleAnalysisManager &MAM) {
  82   if (!Profile)
  83     return {};
  84   ErrorOr<std::unique_ptr<MemoryBuffer>> MB = MemoryBuffer::getFile(*Profile);
  85   if (auto EC = MB.getError()) {
  86     M.getContext().emitError("could not open contextual profile file: " +
  87                              EC.message());
  88     return {};
  89   }
  90   PGOCtxProfileReader Reader(MB.get()->getBuffer());
  91   auto MaybeCtx = Reader.loadContexts();
  92   if (!MaybeCtx) {
  93     M.getContext().emitError("contextual profile file is invalid: " +
  94                              toString(MaybeCtx.takeError()));
  95     return {};
  96   }
  97
  98   DenseSet<GlobalValue::GUID> ProfileRootsInModule;
  99   for (const auto &F : M)
 100     if (!F.isDeclaration())
 101       if (auto GUID = AssignGUIDPass::getGUID(F);
 102           MaybeCtx->find(GUID) != MaybeCtx->end())
 103         ProfileRootsInModule.insert(GUID);
 104
 105   // Trim first the roots that aren't in this module.
 106   for (auto &[RootGuid, _] : llvm::make_early_inc_range(*MaybeCtx))
 107     if (!ProfileRootsInModule.contains(RootGuid))
 108       MaybeCtx->erase(RootGuid);
 109   // If none of the roots are in the module, we have no profile (for this
 110   // module)
 111   if (MaybeCtx->empty())
 112     return {};
 113
 114   // OK, so we have a valid profile and it's applicable to roots in this module.
 115   PGOContextualProfile Result;
 116
 117   for (const auto &F : M) {
 118     if (F.isDeclaration())
 119       continue;
 120     auto GUID = AssignGUIDPass::getGUID(F);
 121     assert(GUID && "guid not found for defined function");
 122     const auto &Entry = F.begin();
 123     uint32_t MaxCounters = 0; // we expect at least a counter.
 124     for (const auto &I : *Entry)
 125       if (auto *C = dyn_cast<InstrProfIncrementInst>(&I)) {
 126         MaxCounters =
 127             static_cast<uint32_t>(C->getNumCounters()->getZExtValue());
 128         break;
 129       }
 130     if (!MaxCounters)
 131       continue;
 132     uint32_t MaxCallsites = 0;
 133     for (const auto &BB : F)
 134       for (const auto &I : BB)
 135         if (auto *C = dyn_cast<InstrProfCallsite>(&I)) {
 136           MaxCallsites =
 137               static_cast<uint32_t>(C->getNumCounters()->getZExtValue());
 138           break;
 139         }
 140     auto [It, Ins] = Result.FuncInfo.insert(
 141         {GUID, PGOContextualProfile::FunctionInfo(F.getName())});
 142     (void)Ins;
 143     assert(Ins);
 144     It->second.NextCallsiteIndex = MaxCallsites;
 145     It->second.NextCounterIndex = MaxCounters;
 146   }
 147   // If we made it this far, the Result is valid - which we mark by setting
 148   // .Profiles.
 149   Result.Profiles = std::move(*MaybeCtx);
 150   Result.initIndex();
 151   return Result;
 152 }
 153
 154 GlobalValue::GUID
 155 PGOContextualProfile::getDefinedFunctionGUID(const Function &F) const {
 156   if (auto It = FuncInfo.find(AssignGUIDPass::getGUID(F)); It != FuncInfo.end())
 157     return It->first;
 158   return 0;
 159 }
 160
 161 CtxProfAnalysisPrinterPass::CtxProfAnalysisPrinterPass(raw_ostream &OS)
 162     : OS(OS), Mode(PrintLevel) {}
 163
 164 PreservedAnalyses CtxProfAnalysisPrinterPass::run(Module &M,
 165                                                   ModuleAnalysisManager &MAM) {
 166   CtxProfAnalysis::Result &C = MAM.getResult<CtxProfAnalysis>(M);
 167   if (!C) {
 168     OS << "No contextual profile was provided.\n";
 169     return PreservedAnalyses::all();
 170   }
 171
 172   if (Mode == PrintMode::Everything) {
 173     OS << "Function Info:\n";
 174     for (const auto &[Guid, FuncInfo] : C.FuncInfo)
 175       OS << Guid << " : " << FuncInfo.Name
 176          << ". MaxCounterID: " << FuncInfo.NextCounterIndex
 177          << ". MaxCallsiteID: " << FuncInfo.NextCallsiteIndex << "\n";
 178   }
 179
 180   if (Mode == PrintMode::Everything)
 181     OS << "\nCurrent Profile:\n";
 182   convertCtxProfToYaml(OS, C.profiles());
 183   OS << "\n";
 184   if (Mode == PrintMode::YAML)
 185     return PreservedAnalyses::all();
 186
 187   OS << "\nFlat Profile:\n";
 188   auto Flat = C.flatten();
 189   for (const auto &[Guid, Counters] : Flat) {
 190     OS << Guid << " : ";
 191     for (auto V : Counters)
 192       OS << V << " ";
 193     OS << "\n";
 194   }
 195   return PreservedAnalyses::all();
 196 }
 197
 198 InstrProfCallsite *CtxProfAnalysis::getCallsiteInstrumentation(CallBase &CB) {
 199   if (!InstrProfCallsite::canInstrumentCallsite(CB))
 200     return nullptr;
 201   for (auto *Prev = CB.getPrevNode(); Prev; Prev = Prev->getPrevNode()) {
 202     if (auto *IPC = dyn_cast<InstrProfCallsite>(Prev))
 203       return IPC;
 204     assert(!isa<CallBase>(Prev) &&
 205            "didn't expect to find another call, that's not the callsite "
 206            "instrumentation, before an instrumentable callsite");
 207   }
 208   return nullptr;
 209 }
 210
 211 InstrProfIncrementInst *CtxProfAnalysis::getBBInstrumentation(BasicBlock &BB) {
 212   for (auto &I : BB)
 213     if (auto *Incr = dyn_cast<InstrProfIncrementInst>(&I))
 214       if (!isa<InstrProfIncrementInstStep>(&I))
 215         return Incr;
 216   return nullptr;
 217 }
 218
 219 InstrProfIncrementInstStep *
 220 CtxProfAnalysis::getSelectInstrumentation(SelectInst &SI) {
 221   Instruction *Prev = &SI;
 222   while ((Prev = Prev->getPrevNode()))
 223     if (auto *Step = dyn_cast<InstrProfIncrementInstStep>(Prev))
 224       return Step;
 225   return nullptr;
 226 }
 227
 228 template <class ProfilesTy, class ProfTy>
 229 static void preorderVisit(ProfilesTy &Profiles,
 230                           function_ref<void(ProfTy &)> Visitor) {
 231   std::function<void(ProfTy &)> Traverser = [&](auto &Ctx) {
 232     Visitor(Ctx);
 233     for (auto &[_, SubCtxSet] : Ctx.callsites())
 234       for (auto &[__, Subctx] : SubCtxSet)
 235         Traverser(Subctx);
 236   };
 237   for (auto &[_, P] : Profiles)
 238     Traverser(P);
 239 }
 240
 241 void PGOContextualProfile::initIndex() {
 242   // Initialize the head of the index list for each function. We don't need it
 243   // after this point.
 244   DenseMap<GlobalValue::GUID, PGOCtxProfContext *> InsertionPoints;
 245   for (auto &[Guid, FI] : FuncInfo)
 246     InsertionPoints[Guid] = &FI.Index;
 247   preorderVisit<PGOCtxProfContext::CallTargetMapTy, PGOCtxProfContext>(
 248       *Profiles, [&](PGOCtxProfContext &Ctx) {
 249         auto InsertIt = InsertionPoints.find(Ctx.guid());
 250         if (InsertIt == InsertionPoints.end())
 251           return;
 252         // Insert at the end of the list. Since we traverse in preorder, it
 253         // means that when we iterate the list from the beginning, we'd
 254         // encounter the contexts in the order we would have, should we have
 255         // performed a full preorder traversal.
 256         InsertIt->second->Next = &Ctx;
 257         Ctx.Previous = InsertIt->second;
 258         InsertIt->second = &Ctx;
 259       });
 260 }
 261
 262 void PGOContextualProfile::update(Visitor V, const Function &F) {
 263   assert(isFunctionKnown(F));
 264   GlobalValue::GUID G = getDefinedFunctionGUID(F);
 265   for (auto *Node = FuncInfo.find(G)->second.Index.Next; Node;
 266        Node = Node->Next)
 267     V(*reinterpret_cast<PGOCtxProfContext *>(Node));
 268 }
 269
 270 void PGOContextualProfile::visit(ConstVisitor V, const Function *F) const {
 271   if (!F)
 272     return preorderVisit<const PGOCtxProfContext::CallTargetMapTy,
 273                          const PGOCtxProfContext>(*Profiles, V);
 274   assert(isFunctionKnown(*F));
 275   GlobalValue::GUID G = getDefinedFunctionGUID(*F);
 276   for (const auto *Node = FuncInfo.find(G)->second.Index.Next; Node;
 277        Node = Node->Next)
 278     V(*reinterpret_cast<const PGOCtxProfContext *>(Node));
 279 }
 280
 281 const CtxProfFlatProfile PGOContextualProfile::flatten() const {
 282   assert(Profiles.has_value());
 283   CtxProfFlatProfile Flat;
 284   preorderVisit<const PGOCtxProfContext::CallTargetMapTy,
 285                 const PGOCtxProfContext>(
 286       *Profiles, [&](const PGOCtxProfContext &Ctx) {
 287         auto [It, Ins] = Flat.insert({Ctx.guid(), {}});
 288         if (Ins) {
 289           llvm::append_range(It->second, Ctx.counters());
 290           return;
 291         }
 292         assert(It->second.size() == Ctx.counters().size() &&
 293                "All contexts corresponding to a function should have the exact "
 294                "same number of counters.");
 295         for (size_t I = 0, E = It->second.size(); I < E; ++I)
 296           It->second[I] += Ctx.counters()[I];
 297       });
 298   return Flat;
 299 }
 300
 301 void CtxProfAnalysis::collectIndirectCallPromotionList(
 302     CallBase &IC, Result &Profile,
 303     SetVector<std::pair<CallBase *, Function *>> &Candidates) {
 304   const auto *Instr = CtxProfAnalysis::getCallsiteInstrumentation(IC);
 305   if (!Instr)
 306     return;
 307   Module &M = *IC.getParent()->getModule();
 308   const uint32_t CallID = Instr->getIndex()->getZExtValue();
 309   Profile.visit(
 310       [&](const PGOCtxProfContext &Ctx) {
 311         const auto &Targets = Ctx.callsites().find(CallID);
 312         if (Targets == Ctx.callsites().end())
 313           return;
 314         for (const auto &[Guid, _] : Targets->second)
 315           if (auto Name = Profile.getFunctionName(Guid); !Name.empty())
 316             if (auto *Target = M.getFunction(Name))
 317               if (Target->hasFnAttribute(Attribute::AlwaysInline))
 318                 Candidates.insert({&IC, Target});
 319       },
 320       IC.getCaller());
 321 }