Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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/StringMap.h"
  19. #include "llvm/ADT/StringRef.h"
  20. #include "llvm/ADT/iterator.h"
  21. #include "llvm/ProfileData/SampleProf.h"
  22. #include <map>
  23. #include <queue>
  24. #include <vector>
  25.  
  26. namespace llvm {
  27. class CallBase;
  28. class DILocation;
  29. class Function;
  30. class Instruction;
  31.  
  32. // Internal trie tree representation used for tracking context tree and sample
  33. // profiles. The path from root node to a given node represents the context of
  34. // that nodes' profile.
  35. class ContextTrieNode {
  36. public:
  37.   ContextTrieNode(ContextTrieNode *Parent = nullptr,
  38.                   StringRef FName = StringRef(),
  39.                   FunctionSamples *FSamples = nullptr,
  40.                   LineLocation CallLoc = {0, 0})
  41.       : ParentContext(Parent), FuncName(FName), FuncSamples(FSamples),
  42.         CallSiteLoc(CallLoc){};
  43.   ContextTrieNode *getChildContext(const LineLocation &CallSite,
  44.                                    StringRef ChildName);
  45.   ContextTrieNode *getHottestChildContext(const LineLocation &CallSite);
  46.   ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite,
  47.                                            StringRef ChildName,
  48.                                            bool AllowCreate = true);
  49.   void removeChildContext(const LineLocation &CallSite, StringRef ChildName);
  50.   std::map<uint64_t, ContextTrieNode> &getAllChildContext();
  51.   StringRef getFuncName() const;
  52.   FunctionSamples *getFunctionSamples() const;
  53.   void setFunctionSamples(FunctionSamples *FSamples);
  54.   std::optional<uint32_t> getFunctionSize() const;
  55.   void addFunctionSize(uint32_t FSize);
  56.   LineLocation getCallSiteLoc() const;
  57.   ContextTrieNode *getParentContext() const;
  58.   void setParentContext(ContextTrieNode *Parent);
  59.   void setCallSiteLoc(const LineLocation &Loc);
  60.   void dumpNode();
  61.   void dumpTree();
  62.  
  63. private:
  64.   // Map line+discriminator location to child context
  65.   std::map<uint64_t, ContextTrieNode> AllChildContext;
  66.  
  67.   // Link to parent context node
  68.   ContextTrieNode *ParentContext;
  69.  
  70.   // Function name for current context
  71.   StringRef FuncName;
  72.  
  73.   // Function Samples for current context
  74.   FunctionSamples *FuncSamples;
  75.  
  76.   // Function size for current context
  77.   std::optional<uint32_t> FuncSize;
  78.  
  79.   // Callsite location in parent context
  80.   LineLocation CallSiteLoc;
  81. };
  82.  
  83. // Profile tracker that manages profiles and its associated context. It
  84. // provides interfaces used by sample profile loader to query context profile or
  85. // base profile for given function or location; it also manages context tree
  86. // manipulation that is needed to accommodate inline decisions so we have
  87. // accurate post-inline profile for functions. Internally context profiles
  88. // are organized in a trie, with each node representing profile for specific
  89. // calling context and the context is identified by path from root to the node.
  90. class SampleContextTracker {
  91. public:
  92.   using ContextSamplesTy = std::vector<FunctionSamples *>;
  93.  
  94.   SampleContextTracker() = default;
  95.   SampleContextTracker(SampleProfileMap &Profiles,
  96.                        const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap);
  97.   // Populate the FuncToCtxtProfiles map after the trie is built.
  98.   void populateFuncToCtxtMap();
  99.   // Query context profile for a specific callee with given name at a given
  100.   // call-site. The full context is identified by location of call instruction.
  101.   FunctionSamples *getCalleeContextSamplesFor(const CallBase &Inst,
  102.                                               StringRef CalleeName);
  103.   // Get samples for indirect call targets for call site at given location.
  104.   std::vector<const FunctionSamples *>
  105.   getIndirectCalleeContextSamplesFor(const DILocation *DIL);
  106.   // Query context profile for a given location. The full context
  107.   // is identified by input DILocation.
  108.   FunctionSamples *getContextSamplesFor(const DILocation *DIL);
  109.   // Query context profile for a given sample contxt of a function.
  110.   FunctionSamples *getContextSamplesFor(const SampleContext &Context);
  111.   // Get all context profile for given function.
  112.   ContextSamplesTy &getAllContextSamplesFor(const Function &Func);
  113.   ContextSamplesTy &getAllContextSamplesFor(StringRef Name);
  114.   ContextTrieNode *getOrCreateContextPath(const SampleContext &Context,
  115.                                           bool AllowCreate);
  116.   // Query base profile for a given function. A base profile is a merged view
  117.   // of all context profiles for contexts that are not inlined.
  118.   FunctionSamples *getBaseSamplesFor(const Function &Func,
  119.                                      bool MergeContext = true);
  120.   // Query base profile for a given function by name.
  121.   FunctionSamples *getBaseSamplesFor(StringRef Name, bool MergeContext = true);
  122.   // Retrieve the context trie node for given profile context
  123.   ContextTrieNode *getContextFor(const SampleContext &Context);
  124.   // Get real function name for a given trie node.
  125.   StringRef getFuncNameFor(ContextTrieNode *Node) const;
  126.   // Mark a context profile as inlined when function is inlined.
  127.   // This makes sure that inlined context profile will be excluded in
  128.   // function's base profile.
  129.   void markContextSamplesInlined(const FunctionSamples *InlinedSamples);
  130.   ContextTrieNode &getRootContext();
  131.   void promoteMergeContextSamplesTree(const Instruction &Inst,
  132.                                       StringRef CalleeName);
  133.  
  134.   // Create a merged conext-less profile map.
  135.   void createContextLessProfileMap(SampleProfileMap &ContextLessProfiles);
  136.   ContextTrieNode *
  137.   getContextNodeForProfile(const FunctionSamples *FSamples) const {
  138.     auto I = ProfileToNodeMap.find(FSamples);
  139.     if (I == ProfileToNodeMap.end())
  140.       return nullptr;
  141.     return I->second;
  142.   }
  143.   StringMap<ContextSamplesTy> &getFuncToCtxtProfiles() {
  144.     return FuncToCtxtProfiles;
  145.   }
  146.  
  147.   class Iterator : public llvm::iterator_facade_base<
  148.                        Iterator, std::forward_iterator_tag, ContextTrieNode *,
  149.                        std::ptrdiff_t, ContextTrieNode **, ContextTrieNode *> {
  150.     std::queue<ContextTrieNode *> NodeQueue;
  151.  
  152.   public:
  153.     explicit Iterator() = default;
  154.     explicit Iterator(ContextTrieNode *Node) { NodeQueue.push(Node); }
  155.     Iterator &operator++() {
  156.       assert(!NodeQueue.empty() && "Iterator already at the end");
  157.       ContextTrieNode *Node = NodeQueue.front();
  158.       NodeQueue.pop();
  159.       for (auto &It : Node->getAllChildContext())
  160.         NodeQueue.push(&It.second);
  161.       return *this;
  162.     }
  163.  
  164.     bool operator==(const Iterator &Other) const {
  165.       if (NodeQueue.empty() && Other.NodeQueue.empty())
  166.         return true;
  167.       if (NodeQueue.empty() || Other.NodeQueue.empty())
  168.         return false;
  169.       return NodeQueue.front() == Other.NodeQueue.front();
  170.     }
  171.  
  172.     ContextTrieNode *operator*() const {
  173.       assert(!NodeQueue.empty() && "Invalid access to end iterator");
  174.       return NodeQueue.front();
  175.     }
  176.   };
  177.  
  178.   Iterator begin() { return Iterator(&RootContext); }
  179.   Iterator end() { return Iterator(); }
  180.  
  181. #ifndef NDEBUG
  182.   // Get a context string from root to current node.
  183.   std::string getContextString(const FunctionSamples &FSamples) const;
  184.   std::string getContextString(ContextTrieNode *Node) const;
  185. #endif
  186.   // Dump the internal context profile trie.
  187.   void dump();
  188.  
  189. private:
  190.   ContextTrieNode *getContextFor(const DILocation *DIL);
  191.   ContextTrieNode *getCalleeContextFor(const DILocation *DIL,
  192.                                        StringRef CalleeName);
  193.   ContextTrieNode *getTopLevelContextNode(StringRef FName);
  194.   ContextTrieNode &addTopLevelContextNode(StringRef FName);
  195.   ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &NodeToPromo);
  196.   void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode);
  197.   ContextTrieNode &
  198.   promoteMergeContextSamplesTree(ContextTrieNode &FromNode,
  199.                                  ContextTrieNode &ToNodeParent);
  200.   ContextTrieNode &moveContextSamples(ContextTrieNode &ToNodeParent,
  201.                                       const LineLocation &CallSite,
  202.                                       ContextTrieNode &&NodeToMove);
  203.   void setContextNode(const FunctionSamples *FSample, ContextTrieNode *Node) {
  204.     ProfileToNodeMap[FSample] = Node;
  205.   }
  206.   // Map from function name to context profiles (excluding base profile)
  207.   StringMap<ContextSamplesTy> FuncToCtxtProfiles;
  208.  
  209.   // Map from current FunctionSample to the belonged context trie.
  210.   std::unordered_map<const FunctionSamples *, ContextTrieNode *>
  211.       ProfileToNodeMap;
  212.  
  213.   // Map from function guid to real function names. Only used in md5 mode.
  214.   const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap;
  215.  
  216.   // Root node for context trie tree
  217.   ContextTrieNode RootContext;
  218. };
  219.  
  220. } // end namespace llvm
  221. #endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
  222.