Home | History | Annotate | Line # | Download | only in IPO 
      1 //===- Transforms/IPO/SampleContextTracker.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 context-sensitive profile tracker used
     11 /// by CSSPGO.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #ifndef LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
     16 #define LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
     17 
     18 #include "llvm/ADT/SmallVector.h"
     19 #include "llvm/ADT/StringMap.h"
     20 #include "llvm/ADT/StringRef.h"
     21 #include "llvm/IR/DebugInfoMetadata.h"
     22 #include "llvm/IR/Instructions.h"
     23 #include "llvm/ProfileData/SampleProf.h"
     24 #include <list>
     25 #include <map>
     26 #include <vector>
     27 
     28 using namespace llvm;
     29 using namespace sampleprof;
     30 
     31 namespace llvm {
     32 
     33 // Internal trie tree representation used for tracking context tree and sample
     34 // profiles. The path from root node to a given node represents the context of
     35 // that nodes' profile.
     36 class ContextTrieNode {
     37 public:
     38   ContextTrieNode(ContextTrieNode *Parent = nullptr,
     39                   StringRef FName = StringRef(),
     40                   FunctionSamples *FSamples = nullptr,
     41                   LineLocation CallLoc = {0, 0})
     42       : ParentContext(Parent), FuncName(FName), FuncSamples(FSamples),
     43         CallSiteLoc(CallLoc){};
     44   ContextTrieNode *getChildContext(const LineLocation &CallSite,
     45                                    StringRef CalleeName);
     46   ContextTrieNode *getHottestChildContext(const LineLocation &CallSite);
     47   ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite,
     48                                            StringRef CalleeName,
     49                                            bool AllowCreate = true);
     50 
     51   ContextTrieNode &moveToChildContext(const LineLocation &CallSite,
     52                                       ContextTrieNode &&NodeToMove,
     53                                       StringRef ContextStrToRemove,
     54                                       bool DeleteNode = true);
     55   void removeChildContext(const LineLocation &CallSite, StringRef CalleeName);
     56   std::map<uint32_t, ContextTrieNode> &getAllChildContext();
     57   StringRef getFuncName() const;
     58   FunctionSamples *getFunctionSamples() const;
     59   void setFunctionSamples(FunctionSamples *FSamples);
     60   LineLocation getCallSiteLoc() const;
     61   ContextTrieNode *getParentContext() const;
     62   void setParentContext(ContextTrieNode *Parent);
     63   void dump();
     64 
     65 private:
     66   static uint32_t nodeHash(StringRef ChildName, const LineLocation &Callsite);
     67 
     68   // Map line+discriminator location to child context
     69   std::map<uint32_t, ContextTrieNode> AllChildContext;
     70 
     71   // Link to parent context node
     72   ContextTrieNode *ParentContext;
     73 
     74   // Function name for current context
     75   StringRef FuncName;
     76 
     77   // Function Samples for current context
     78   FunctionSamples *FuncSamples;
     79 
     80   // Callsite location in parent context
     81   LineLocation CallSiteLoc;
     82 };
     83 
     84 // Profile tracker that manages profiles and its associated context. It
     85 // provides interfaces used by sample profile loader to query context profile or
     86 // base profile for given function or location; it also manages context tree
     87 // manipulation that is needed to accommodate inline decisions so we have
     88 // accurate post-inline profile for functions. Internally context profiles
     89 // are organized in a trie, with each node representing profile for specific
     90 // calling context and the context is identified by path from root to the node.
     91 class SampleContextTracker {
     92 public:
     93   using ContextSamplesTy = SmallVector<FunctionSamples *, 16>;
     94 
     95   SampleContextTracker(StringMap<FunctionSamples> &Profiles);
     96   // Query context profile for a specific callee with given name at a given
     97   // call-site. The full context is identified by location of call instruction.
     98   FunctionSamples *getCalleeContextSamplesFor(const CallBase &Inst,
     99                                               StringRef CalleeName);
    100   // Get samples for indirect call targets for call site at given location.
    101   std::vector<const FunctionSamples *>
    102   getIndirectCalleeContextSamplesFor(const DILocation *DIL);
    103   // Query context profile for a given location. The full context
    104   // is identified by input DILocation.
    105   FunctionSamples *getContextSamplesFor(const DILocation *DIL);
    106   // Query context profile for a given sample contxt of a function.
    107   FunctionSamples *getContextSamplesFor(const SampleContext &Context);
    108   // Get all context profile for given function.
    109   ContextSamplesTy &getAllContextSamplesFor(const Function &Func);
    110   ContextSamplesTy &getAllContextSamplesFor(StringRef Name);
    111   // Query base profile for a given function. A base profile is a merged view
    112   // of all context profiles for contexts that are not inlined.
    113   FunctionSamples *getBaseSamplesFor(const Function &Func,
    114                                      bool MergeContext = true);
    115   // Query base profile for a given function by name.
    116   FunctionSamples *getBaseSamplesFor(StringRef Name, bool MergeContext = true);
    117   // Retrieve the context trie node for given profile context
    118   ContextTrieNode *getContextFor(const SampleContext &Context);
    119   // Mark a context profile as inlined when function is inlined.
    120   // This makes sure that inlined context profile will be excluded in
    121   // function's base profile.
    122   void markContextSamplesInlined(const FunctionSamples *InlinedSamples);
    123   ContextTrieNode &getRootContext();
    124   void promoteMergeContextSamplesTree(const Instruction &Inst,
    125                                       StringRef CalleeName);
    126   // Dump the internal context profile trie.
    127   void dump();
    128 
    129 private:
    130   ContextTrieNode *getContextFor(const DILocation *DIL);
    131   ContextTrieNode *getCalleeContextFor(const DILocation *DIL,
    132                                        StringRef CalleeName);
    133   ContextTrieNode *getOrCreateContextPath(const SampleContext &Context,
    134                                           bool AllowCreate);
    135   ContextTrieNode *getTopLevelContextNode(StringRef FName);
    136   ContextTrieNode &addTopLevelContextNode(StringRef FName);
    137   ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &NodeToPromo);
    138   void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode,
    139                         StringRef ContextStrToRemove);
    140   ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &FromNode,
    141                                                   ContextTrieNode &ToNodeParent,
    142                                                   StringRef ContextStrToRemove);
    143 
    144   // Map from function name to context profiles (excluding base profile)
    145   StringMap<ContextSamplesTy> FuncToCtxtProfiles;
    146 
    147   // Root node for context trie tree
    148   ContextTrieNode RootContext;
    149 };
    150 
    151 } // end namespace llvm
    152 #endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
    153