Home | History | Annotate | Line # | Download | only in IPO 
      1 //===- Transforms/IPO/SampleProfileProbe.h ----------*- C++ -*-===//
      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 /// \file
     10 /// This file provides the interface for the pseudo probe implementation for
     11 /// AutoFDO.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #ifndef LLVM_TRANSFORMS_IPO_SAMPLEPROFILEPROBE_H
     16 #define LLVM_TRANSFORMS_IPO_SAMPLEPROFILEPROBE_H
     17 
     18 #include "llvm/ADT/DenseMap.h"
     19 #include "llvm/Analysis/CallGraphSCCPass.h"
     20 #include "llvm/Analysis/LazyCallGraph.h"
     21 #include "llvm/Analysis/LoopInfo.h"
     22 #include "llvm/IR/PassInstrumentation.h"
     23 #include "llvm/IR/PassManager.h"
     24 #include "llvm/IR/PseudoProbe.h"
     25 #include "llvm/ProfileData/SampleProf.h"
     26 #include "llvm/Target/TargetMachine.h"
     27 #include <unordered_map>
     28 
     29 namespace llvm {
     30 
     31 class Module;
     32 
     33 using namespace sampleprof;
     34 using BlockIdMap = std::unordered_map<BasicBlock *, uint32_t>;
     35 using InstructionIdMap = std::unordered_map<Instruction *, uint32_t>;
     36 // Map from tuples of Probe id and inline stack hash code to distribution
     37 // factors.
     38 using ProbeFactorMap = std::unordered_map<std::pair<uint64_t, uint64_t>, float,
     39                                           pair_hash<uint64_t, uint64_t>>;
     40 using FuncProbeFactorMap = StringMap<ProbeFactorMap>;
     41 
     42 enum class PseudoProbeReservedId { Invalid = 0, Last = Invalid };
     43 
     44 class PseudoProbeDescriptor {
     45   uint64_t FunctionGUID;
     46   uint64_t FunctionHash;
     47 
     48 public:
     49   PseudoProbeDescriptor(uint64_t GUID, uint64_t Hash)
     50       : FunctionGUID(GUID), FunctionHash(Hash) {}
     51   uint64_t getFunctionGUID() const { return FunctionGUID; }
     52   uint64_t getFunctionHash() const { return FunctionHash; }
     53 };
     54 
     55 // A pseudo probe verifier that can be run after each IR passes to detect the
     56 // violation of updating probe factors. In principle, the sum of distribution
     57 // factor for a probe should be identical before and after a pass. For a
     58 // function pass, the factor sum for a probe would be typically 100%.
     59 class PseudoProbeVerifier {
     60 public:
     61   void registerCallbacks(PassInstrumentationCallbacks &PIC);
     62 
     63   // Implementation of pass instrumentation callbacks for new pass manager.
     64   void runAfterPass(StringRef PassID, Any IR);
     65 
     66 private:
     67   // Allow a little bias due the rounding to integral factors.
     68   constexpr static float DistributionFactorVariance = 0.02f;
     69   // Distribution factors from last pass.
     70   FuncProbeFactorMap FunctionProbeFactors;
     71 
     72   void collectProbeFactors(const BasicBlock *BB, ProbeFactorMap &ProbeFactors);
     73   void runAfterPass(const Module *M);
     74   void runAfterPass(const LazyCallGraph::SCC *C);
     75   void runAfterPass(const Function *F);
     76   void runAfterPass(const Loop *L);
     77   bool shouldVerifyFunction(const Function *F);
     78   void verifyProbeFactors(const Function *F,
     79                           const ProbeFactorMap &ProbeFactors);
     80 };
     81 
     82 // This class serves sample counts correlation for SampleProfileLoader by
     83 // analyzing pseudo probes and their function descriptors injected by
     84 // SampleProfileProber.
     85 class PseudoProbeManager {
     86   DenseMap<uint64_t, PseudoProbeDescriptor> GUIDToProbeDescMap;
     87 
     88   const PseudoProbeDescriptor *getDesc(const Function &F) const;
     89 
     90 public:
     91   PseudoProbeManager(const Module &M);
     92   bool moduleIsProbed(const Module &M) const;
     93   bool profileIsValid(const Function &F, const FunctionSamples &Samples) const;
     94 };
     95 
     96 /// Sample profile pseudo prober.
     97 ///
     98 /// Insert pseudo probes for block sampling and value sampling.
     99 class SampleProfileProber {
    100 public:
    101   // Give an empty module id when the prober is not used for instrumentation.
    102   SampleProfileProber(Function &F, const std::string &CurModuleUniqueId);
    103   void instrumentOneFunc(Function &F, TargetMachine *TM);
    104 
    105 private:
    106   Function *getFunction() const { return F; }
    107   uint64_t getFunctionHash() const { return FunctionHash; }
    108   uint32_t getBlockId(const BasicBlock *BB) const;
    109   uint32_t getCallsiteId(const Instruction *Call) const;
    110   void computeCFGHash();
    111   void computeProbeIdForBlocks();
    112   void computeProbeIdForCallsites();
    113 
    114   Function *F;
    115 
    116   /// The current module ID that is used to name a static object as a comdat
    117   /// group.
    118   std::string CurModuleUniqueId;
    119 
    120   /// A CFG hash code used to identify a function code changes.
    121   uint64_t FunctionHash;
    122 
    123   /// Map basic blocks to the their pseudo probe ids.
    124   BlockIdMap BlockProbeIds;
    125 
    126   /// Map indirect calls to the their pseudo probe ids.
    127   InstructionIdMap CallProbeIds;
    128 
    129   /// The ID of the last probe, Can be used to number a new probe.
    130   uint32_t LastProbeId;
    131 };
    132 
    133 class SampleProfileProbePass : public PassInfoMixin<SampleProfileProbePass> {
    134   TargetMachine *TM;
    135 
    136 public:
    137   SampleProfileProbePass(TargetMachine *TM) : TM(TM) {}
    138   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
    139 };
    140 
    141 // Pseudo probe distribution factor updater.
    142 // Sample profile annotation can happen in both LTO prelink and postlink. The
    143 // postlink-time re-annotation can degrade profile quality because of prelink
    144 // code duplication transformation, such as loop unrolling, jump threading,
    145 // indirect call promotion etc. As such, samples corresponding to a source
    146 // location may be aggregated multiple times in postlink. With a concept of
    147 // distribution factor for pseudo probes, samples can be distributed among
    148 // duplicated probes reasonable based on the assumption that optimizations
    149 // duplicating code well-maintain the branch frequency information (BFI). This
    150 // pass updates distribution factors for each pseudo probe at the end of the
    151 // prelink pipeline, to reflect an estimated portion of the real execution
    152 // count.
    153 class PseudoProbeUpdatePass : public PassInfoMixin<PseudoProbeUpdatePass> {
    154   void runOnFunction(Function &F, FunctionAnalysisManager &FAM);
    155 
    156 public:
    157   PseudoProbeUpdatePass() {}
    158   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
    159 };
    160 
    161 } // end namespace llvm
    162 #endif // LLVM_TRANSFORMS_IPO_SAMPLEPROFILEPROBE_H
    163