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_TRANSFORMS_IPO_PROFILEDCALLGRAPH_H
10 #define LLVM_TRANSFORMS_IPO_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 
21 namespace llvm {
22 namespace sampleprof {
23 
24 struct ProfiledCallGraphNode;
25 
26 struct ProfiledCallGraphEdge {
27   ProfiledCallGraphEdge(ProfiledCallGraphNode *Source,
28                         ProfiledCallGraphNode *Target, uint64_t Weight)
29       : Source(Source), Target(Target), Weight(Weight) {}
30   ProfiledCallGraphNode *Source;
31   ProfiledCallGraphNode *Target;
32   uint64_t Weight;
33 
34   // The call destination is the only important data here,
35   // allow to transparently unwrap into it.
36   operator ProfiledCallGraphNode *() const { return Target; }
37 };
38 
39 struct ProfiledCallGraphNode {
40 
41   // Sort edges by callee names only since all edges to be compared are from
42   // same caller. Edge weights are not considered either because for the same
43   // callee only the edge with the largest weight is added to the edge set.
44   struct ProfiledCallGraphEdgeComparer {
45     bool operator()(const ProfiledCallGraphEdge &L,
46                     const ProfiledCallGraphEdge &R) const {
47       return L.Target->Name < R.Target->Name;
48     }
49   };
50 
51   using edge = ProfiledCallGraphEdge;
52   using edges = std::set<edge, ProfiledCallGraphEdgeComparer>;
53   using iterator = edges::iterator;
54   using const_iterator = edges::const_iterator;
55 
56   ProfiledCallGraphNode(StringRef FName = StringRef()) : Name(FName) {}
57 
58   StringRef Name;
59   edges Edges;
60 };
61 
62 class ProfiledCallGraph {
63 public:
64   using iterator = ProfiledCallGraphNode::iterator;
65 
66   // Constructor for non-CS profile.
67   ProfiledCallGraph(SampleProfileMap &ProfileMap) {
68     assert(!FunctionSamples::ProfileIsCS &&
69            "CS flat profile is not handled here");
70     for (const auto &Samples : ProfileMap) {
71       addProfiledCalls(Samples.second);
72     }
73   }
74 
75   // Constructor for CS profile.
76   ProfiledCallGraph(SampleContextTracker &ContextTracker) {
77     // BFS traverse the context profile trie to add call edges for calls shown
78     // in context.
79     std::queue<ContextTrieNode *> Queue;
80     for (auto &Child : ContextTracker.getRootContext().getAllChildContext()) {
81       ContextTrieNode *Callee = &Child.second;
82       addProfiledFunction(ContextTracker.getFuncNameFor(Callee));
83       Queue.push(Callee);
84     }
85 
86     while (!Queue.empty()) {
87       ContextTrieNode *Caller = Queue.front();
88       Queue.pop();
89       FunctionSamples *CallerSamples = Caller->getFunctionSamples();
90 
91       // Add calls for context.
92       // Note that callsite target samples are completely ignored since they can
93       // conflict with the context edges, which are formed by context
94       // compression during profile generation, for cyclic SCCs. This may
95       // further result in an SCC order incompatible with the purely
96       // context-based one, which may in turn block context-based inlining.
97       for (auto &Child : Caller->getAllChildContext()) {
98         ContextTrieNode *Callee = &Child.second;
99         addProfiledFunction(ContextTracker.getFuncNameFor(Callee));
100         Queue.push(Callee);
101 
102         // Fetch edge weight from the profile.
103         uint64_t Weight;
104         FunctionSamples *CalleeSamples = Callee->getFunctionSamples();
105         if (!CalleeSamples || !CallerSamples) {
106           Weight = 0;
107         } else {
108           uint64_t CalleeEntryCount = CalleeSamples->getHeadSamplesEstimate();
109           uint64_t CallsiteCount = 0;
110           LineLocation Callsite = Callee->getCallSiteLoc();
111           if (auto CallTargets = CallerSamples->findCallTargetMapAt(Callsite)) {
112             SampleRecord::CallTargetMap &TargetCounts = CallTargets.get();
113             auto It = TargetCounts.find(CalleeSamples->getName());
114             if (It != TargetCounts.end())
115               CallsiteCount = It->second;
116           }
117           Weight = std::max(CallsiteCount, CalleeEntryCount);
118         }
119 
120         addProfiledCall(ContextTracker.getFuncNameFor(Caller),
121                         ContextTracker.getFuncNameFor(Callee), Weight);
122       }
123     }
124   }
125 
126   iterator begin() { return Root.Edges.begin(); }
127   iterator end() { return Root.Edges.end(); }
128   ProfiledCallGraphNode *getEntryNode() { return &Root; }
129   void addProfiledFunction(StringRef Name) {
130     if (!ProfiledFunctions.count(Name)) {
131       // Link to synthetic root to make sure every node is reachable
132       // from root. This does not affect SCC order.
133       ProfiledFunctions[Name] = ProfiledCallGraphNode(Name);
134       Root.Edges.emplace(&Root, &ProfiledFunctions[Name], 0);
135     }
136   }
137 
138 private:
139   void addProfiledCall(StringRef CallerName, StringRef CalleeName,
140                        uint64_t Weight = 0) {
141     assert(ProfiledFunctions.count(CallerName));
142     auto CalleeIt = ProfiledFunctions.find(CalleeName);
143     if (CalleeIt == ProfiledFunctions.end())
144       return;
145     ProfiledCallGraphEdge Edge(&ProfiledFunctions[CallerName],
146                                &CalleeIt->second, Weight);
147     auto &Edges = ProfiledFunctions[CallerName].Edges;
148     auto EdgeIt = Edges.find(Edge);
149     if (EdgeIt == Edges.end()) {
150       Edges.insert(Edge);
151     } else if (EdgeIt->Weight < Edge.Weight) {
152       // Replace existing call edges with same target but smaller weight.
153       Edges.erase(EdgeIt);
154       Edges.insert(Edge);
155     }
156   }
157 
158   void addProfiledCalls(const FunctionSamples &Samples) {
159     addProfiledFunction(Samples.getFuncName());
160 
161     for (const auto &Sample : Samples.getBodySamples()) {
162       for (const auto &Target : Sample.second.getCallTargets()) {
163         addProfiledFunction(Target.first());
164         addProfiledCall(Samples.getFuncName(), Target.first(), Target.second);
165       }
166     }
167 
168     for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) {
169       for (const auto &InlinedSamples : CallsiteSamples.second) {
170         addProfiledFunction(InlinedSamples.first);
171         addProfiledCall(Samples.getFuncName(), InlinedSamples.first,
172                         InlinedSamples.second.getHeadSamplesEstimate());
173         addProfiledCalls(InlinedSamples.second);
174       }
175     }
176   }
177 
178   ProfiledCallGraphNode Root;
179   StringMap<ProfiledCallGraphNode> ProfiledFunctions;
180 };
181 
182 } // end namespace sampleprof
183 
184 template <> struct GraphTraits<ProfiledCallGraphNode *> {
185   using NodeType = ProfiledCallGraphNode;
186   using NodeRef = ProfiledCallGraphNode *;
187   using EdgeType = NodeType::edge;
188   using ChildIteratorType = NodeType::const_iterator;
189 
190   static NodeRef getEntryNode(NodeRef PCGN) { return PCGN; }
191   static ChildIteratorType child_begin(NodeRef N) { return N->Edges.begin(); }
192   static ChildIteratorType child_end(NodeRef N) { return N->Edges.end(); }
193 };
194 
195 template <>
196 struct GraphTraits<ProfiledCallGraph *>
197     : public GraphTraits<ProfiledCallGraphNode *> {
198   static NodeRef getEntryNode(ProfiledCallGraph *PCG) {
199     return PCG->getEntryNode();
200   }
201 
202   static ChildIteratorType nodes_begin(ProfiledCallGraph *PCG) {
203     return PCG->begin();
204   }
205 
206   static ChildIteratorType nodes_end(ProfiledCallGraph *PCG) {
207     return PCG->end();
208   }
209 };
210 
211 } // end namespace llvm
212 
213 #endif
214