Home | History | Annotate | Line # | Download | only in IPO 
      1 //===-- ProfiledCallGraph.h - Profiled Call Graph ----------------- 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 #ifndef LLVM_TOOLS_LLVM_PROFGEN_PROFILEDCALLGRAPH_H
     10 #define LLVM_TOOLS_LLVM_PROFGEN_PROFILEDCALLGRAPH_H
     11 
     12 #include "llvm/ADT/GraphTraits.h"
     13 #include "llvm/ADT/StringMap.h"
     14 #include "llvm/ADT/StringRef.h"
     15 #include "llvm/ProfileData/SampleProf.h"
     16 #include "llvm/ProfileData/SampleProfReader.h"
     17 #include "llvm/Transforms/IPO/SampleContextTracker.h"
     18 #include <queue>
     19 #include <set>
     20 #include <string>
     21 
     22 using namespace llvm;
     23 using namespace sampleprof;
     24 
     25 namespace llvm {
     26 namespace sampleprof {
     27 
     28 struct ProfiledCallGraphNode {
     29   ProfiledCallGraphNode(StringRef FName = StringRef()) : Name(FName) {}
     30   StringRef Name;
     31 
     32   struct ProfiledCallGraphNodeComparer {
     33     bool operator()(const ProfiledCallGraphNode *L,
     34                     const ProfiledCallGraphNode *R) const {
     35       return L->Name < R->Name;
     36     }
     37   };
     38   std::set<ProfiledCallGraphNode *, ProfiledCallGraphNodeComparer> Callees;
     39 };
     40 
     41 class ProfiledCallGraph {
     42 public:
     43   using iterator = std::set<ProfiledCallGraphNode *>::iterator;
     44 
     45   // Constructor for non-CS profile.
     46   ProfiledCallGraph(StringMap<FunctionSamples> &ProfileMap) {
     47     assert(!FunctionSamples::ProfileIsCS && "CS profile is not handled here");
     48     for (const auto &Samples : ProfileMap) {
     49       addProfiledCalls(Samples.second);
     50     }
     51   }
     52 
     53   // Constructor for CS profile.
     54   ProfiledCallGraph(SampleContextTracker &ContextTracker) {
     55     // BFS traverse the context profile trie to add call edges for calls shown
     56     // in context.
     57     std::queue<ContextTrieNode *> Queue;
     58     for (auto &Child : ContextTracker.getRootContext().getAllChildContext()) {
     59       ContextTrieNode *Callee = &Child.second;
     60       addProfiledFunction(Callee->getFuncName());
     61       Queue.push(Callee);
     62     }
     63 
     64     while (!Queue.empty()) {
     65       ContextTrieNode *Caller = Queue.front();
     66       Queue.pop();
     67       // Add calls for context. When AddNodeWithSamplesOnly is true, both caller
     68       // and callee need to have context profile.
     69       // Note that callsite target samples are completely ignored since they can
     70       // conflict with the context edges, which are formed by context
     71       // compression during profile generation, for cyclic SCCs. This may
     72       // further result in an SCC order incompatible with the purely
     73       // context-based one, which may in turn block context-based inlining.
     74       for (auto &Child : Caller->getAllChildContext()) {
     75         ContextTrieNode *Callee = &Child.second;
     76         addProfiledFunction(Callee->getFuncName());
     77         Queue.push(Callee);
     78         addProfiledCall(Caller->getFuncName(), Callee->getFuncName());
     79       }
     80     }
     81   }
     82 
     83   iterator begin() { return Root.Callees.begin(); }
     84   iterator end() { return Root.Callees.end(); }
     85   ProfiledCallGraphNode *getEntryNode() { return &Root; }
     86   void addProfiledFunction(StringRef Name) {
     87     if (!ProfiledFunctions.count(Name)) {
     88       // Link to synthetic root to make sure every node is reachable
     89       // from root. This does not affect SCC order.
     90       ProfiledFunctions[Name] = ProfiledCallGraphNode(Name);
     91       Root.Callees.insert(&ProfiledFunctions[Name]);
     92     }
     93   }
     94 
     95   void addProfiledCall(StringRef CallerName, StringRef CalleeName) {
     96     assert(ProfiledFunctions.count(CallerName));
     97     auto CalleeIt = ProfiledFunctions.find(CalleeName);
     98     if (CalleeIt == ProfiledFunctions.end()) {
     99       return;
    100     }
    101     ProfiledFunctions[CallerName].Callees.insert(&CalleeIt->second);
    102   }
    103 
    104   void addProfiledCalls(const FunctionSamples &Samples) {
    105     addProfiledFunction(Samples.getFuncName());
    106 
    107     for (const auto &Sample : Samples.getBodySamples()) {
    108       for (const auto &Target : Sample.second.getCallTargets()) {
    109         addProfiledFunction(Target.first());
    110         addProfiledCall(Samples.getFuncName(), Target.first());
    111       }
    112     }
    113 
    114     for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) {
    115       for (const auto &InlinedSamples : CallsiteSamples.second) {
    116         addProfiledFunction(InlinedSamples.first);
    117         addProfiledCall(Samples.getFuncName(), InlinedSamples.first);
    118         addProfiledCalls(InlinedSamples.second);
    119       }
    120     }
    121   }
    122 
    123 private:
    124   ProfiledCallGraphNode Root;
    125   StringMap<ProfiledCallGraphNode> ProfiledFunctions;
    126 };
    127 
    128 } // end namespace sampleprof
    129 
    130 template <> struct GraphTraits<ProfiledCallGraphNode *> {
    131   using NodeRef = ProfiledCallGraphNode *;
    132   using ChildIteratorType = std::set<ProfiledCallGraphNode *>::iterator;
    133 
    134   static NodeRef getEntryNode(NodeRef PCGN) { return PCGN; }
    135   static ChildIteratorType child_begin(NodeRef N) { return N->Callees.begin(); }
    136   static ChildIteratorType child_end(NodeRef N) { return N->Callees.end(); }
    137 };
    138 
    139 template <>
    140 struct GraphTraits<ProfiledCallGraph *>
    141     : public GraphTraits<ProfiledCallGraphNode *> {
    142   static NodeRef getEntryNode(ProfiledCallGraph *PCG) {
    143     return PCG->getEntryNode();
    144   }
    145 
    146   static ChildIteratorType nodes_begin(ProfiledCallGraph *PCG) {
    147     return PCG->begin();
    148   }
    149 
    150   static ChildIteratorType nodes_end(ProfiledCallGraph *PCG) {
    151     return PCG->end();
    152   }
    153 };
    154 
    155 } // end namespace llvm
    156 
    157 #endif
    158