Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- Transforms/IPO/SampleContextTracker.h --------------------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

/// \file

/// This file provides the interface for context-sensitive profile tracker used

/// by CSSPGO.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H

#define LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H

#include "llvm/ADT/StringMap.h"

#include "llvm/ADT/StringRef.h"

#include "llvm/ADT/iterator.h"

#include "llvm/ProfileData/SampleProf.h"

#include <map>

#include <queue>

#include <vector>

namespace llvm {

class CallBase;

class DILocation;

class Function;

class Instruction;

// Internal trie tree representation used for tracking context tree and sample

// profiles. The path from root node to a given node represents the context of

// that nodes' profile.

class ContextTrieNode {

public:

  ContextTrieNode(ContextTrieNode *Parent = nullptr,

                  StringRef FName = StringRef(),

                  FunctionSamples *FSamples = nullptr,

                  LineLocation CallLoc = {0, 0})

      : ParentContext(Parent), FuncName(FName), FuncSamples(FSamples),

        CallSiteLoc(CallLoc){};

  ContextTrieNode *getChildContext(const LineLocation &CallSite,

                                   StringRef ChildName);

  ContextTrieNode *getHottestChildContext(const LineLocation &CallSite);

  ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite,

                                           StringRef ChildName,

                                           bool AllowCreate = true);

  void removeChildContext(const LineLocation &CallSite, StringRef ChildName);

  std::map<uint64_t, ContextTrieNode> &getAllChildContext();

  StringRef getFuncName() const;

  FunctionSamples *getFunctionSamples() const;

  void setFunctionSamples(FunctionSamples *FSamples);

  std::optional<uint32_t> getFunctionSize() const;

  void addFunctionSize(uint32_t FSize);

  LineLocation getCallSiteLoc() const;

  ContextTrieNode *getParentContext() const;

  void setParentContext(ContextTrieNode *Parent);

  void setCallSiteLoc(const LineLocation &Loc);

  void dumpNode();

  void dumpTree();

private:

  // Map line+discriminator location to child context

  std::map<uint64_t, ContextTrieNode> AllChildContext;

  // Link to parent context node

  ContextTrieNode *ParentContext;

  // Function name for current context

  StringRef FuncName;

  // Function Samples for current context

  FunctionSamples *FuncSamples;

  // Function size for current context

  std::optional<uint32_t> FuncSize;

  // Callsite location in parent context

  LineLocation CallSiteLoc;

};

// Profile tracker that manages profiles and its associated context. It

// provides interfaces used by sample profile loader to query context profile or

// base profile for given function or location; it also manages context tree

// manipulation that is needed to accommodate inline decisions so we have

// accurate post-inline profile for functions. Internally context profiles

// are organized in a trie, with each node representing profile for specific

// calling context and the context is identified by path from root to the node.

class SampleContextTracker {

public:

  using ContextSamplesTy = std::vector<FunctionSamples *>;

  SampleContextTracker() = default;

  SampleContextTracker(SampleProfileMap &Profiles,

                       const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap);

  // Populate the FuncToCtxtProfiles map after the trie is built.

  void populateFuncToCtxtMap();

  // Query context profile for a specific callee with given name at a given

  // call-site. The full context is identified by location of call instruction.

  FunctionSamples *getCalleeContextSamplesFor(const CallBase &Inst,

                                              StringRef CalleeName);

  // Get samples for indirect call targets for call site at given location.

  std::vector<const FunctionSamples *>

  getIndirectCalleeContextSamplesFor(const DILocation *DIL);

  // Query context profile for a given location. The full context

  // is identified by input DILocation.

  FunctionSamples *getContextSamplesFor(const DILocation *DIL);

  // Query context profile for a given sample contxt of a function.

  FunctionSamples *getContextSamplesFor(const SampleContext &Context);

  // Get all context profile for given function.

  ContextSamplesTy &getAllContextSamplesFor(const Function &Func);

  ContextSamplesTy &getAllContextSamplesFor(StringRef Name);

  ContextTrieNode *getOrCreateContextPath(const SampleContext &Context,

                                          bool AllowCreate);

  // Query base profile for a given function. A base profile is a merged view

  // of all context profiles for contexts that are not inlined.

  FunctionSamples *getBaseSamplesFor(const Function &Func,

                                     bool MergeContext = true);

  // Query base profile for a given function by name.

  FunctionSamples *getBaseSamplesFor(StringRef Name, bool MergeContext = true);

  // Retrieve the context trie node for given profile context

  ContextTrieNode *getContextFor(const SampleContext &Context);

  // Get real function name for a given trie node.

  StringRef getFuncNameFor(ContextTrieNode *Node) const;

  // Mark a context profile as inlined when function is inlined.

  // This makes sure that inlined context profile will be excluded in

  // function's base profile.

  void markContextSamplesInlined(const FunctionSamples *InlinedSamples);

  ContextTrieNode &getRootContext();

  void promoteMergeContextSamplesTree(const Instruction &Inst,

                                      StringRef CalleeName);

  // Create a merged conext-less profile map.

  void createContextLessProfileMap(SampleProfileMap &ContextLessProfiles);

  ContextTrieNode *

  getContextNodeForProfile(const FunctionSamples *FSamples) const {

    auto I = ProfileToNodeMap.find(FSamples);

    if (I == ProfileToNodeMap.end())

      return nullptr;

    return I->second;

  }

  StringMap<ContextSamplesTy> &getFuncToCtxtProfiles() {

    return FuncToCtxtProfiles;

  }

  class Iterator : public llvm::iterator_facade_base<

                       Iterator, std::forward_iterator_tag, ContextTrieNode *,

                       std::ptrdiff_t, ContextTrieNode **, ContextTrieNode *> {

    std::queue<ContextTrieNode *> NodeQueue;

  public:

    explicit Iterator() = default;

    explicit Iterator(ContextTrieNode *Node) { NodeQueue.push(Node); }

    Iterator &operator++() {

      assert(!NodeQueue.empty() && "Iterator already at the end");

      ContextTrieNode *Node = NodeQueue.front();

      NodeQueue.pop();

      for (auto &It : Node->getAllChildContext())

        NodeQueue.push(&It.second);

      return *this;

    }

    bool operator==(const Iterator &Other) const {

      if (NodeQueue.empty() && Other.NodeQueue.empty())

        return true;

      if (NodeQueue.empty() || Other.NodeQueue.empty())

        return false;

      return NodeQueue.front() == Other.NodeQueue.front();

    }

    ContextTrieNode *operator*() const {

      assert(!NodeQueue.empty() && "Invalid access to end iterator");

      return NodeQueue.front();

    }

  };

  Iterator begin() { return Iterator(&RootContext); }

  Iterator end() { return Iterator(); }

#ifndef NDEBUG

  // Get a context string from root to current node.

  std::string getContextString(const FunctionSamples &FSamples) const;

  std::string getContextString(ContextTrieNode *Node) const;

#endif

  // Dump the internal context profile trie.

  void dump();

private:

  ContextTrieNode *getContextFor(const DILocation *DIL);

  ContextTrieNode *getCalleeContextFor(const DILocation *DIL,

                                       StringRef CalleeName);

  ContextTrieNode *getTopLevelContextNode(StringRef FName);

  ContextTrieNode &addTopLevelContextNode(StringRef FName);

  ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &NodeToPromo);

  void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode);

  ContextTrieNode &

  promoteMergeContextSamplesTree(ContextTrieNode &FromNode,

                                 ContextTrieNode &ToNodeParent);

  ContextTrieNode &moveContextSamples(ContextTrieNode &ToNodeParent,

                                      const LineLocation &CallSite,

                                      ContextTrieNode &&NodeToMove);

  void setContextNode(const FunctionSamples *FSample, ContextTrieNode *Node) {

    ProfileToNodeMap[FSample] = Node;

  }

  // Map from function name to context profiles (excluding base profile)

  StringMap<ContextSamplesTy> FuncToCtxtProfiles;

  // Map from current FunctionSample to the belonged context trie.

  std::unordered_map<const FunctionSamples *, ContextTrieNode *>

      ProfileToNodeMap;

  // Map from function guid to real function names. Only used in md5 mode.

  const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap;

  // Root node for context trie tree

  ContextTrieNode RootContext;

};

} // end namespace llvm

#endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H