1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
#pragma once
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif
//===- 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/SmallSet.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/Instructions.h"
#include "llvm/ProfileData/SampleProf.h"
#include <list>
#include <map>
#include <vector>
using namespace llvm;
using namespace sampleprof;
namespace llvm {
// 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 CalleeName);
ContextTrieNode *getHottestChildContext(const LineLocation &CallSite);
ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite,
StringRef CalleeName,
bool AllowCreate = true);
ContextTrieNode &moveToChildContext(const LineLocation &CallSite,
ContextTrieNode &&NodeToMove,
StringRef ContextStrToRemove,
bool DeleteNode = true);
void removeChildContext(const LineLocation &CallSite, StringRef CalleeName);
std::map<uint32_t, ContextTrieNode> &getAllChildContext();
const StringRef getFuncName() const;
FunctionSamples *getFunctionSamples() const;
void setFunctionSamples(FunctionSamples *FSamples);
LineLocation getCallSiteLoc() const;
ContextTrieNode *getParentContext() const;
void setParentContext(ContextTrieNode *Parent);
void dump();
private:
static uint32_t nodeHash(StringRef ChildName, const LineLocation &Callsite);
// Map line+discriminator location to child context
std::map<uint32_t, ContextTrieNode> AllChildContext;
// Link to parent context node
ContextTrieNode *ParentContext;
// Function name for current context
StringRef FuncName;
// Function Samples for current context
FunctionSamples *FuncSamples;
// 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 = SmallSet<FunctionSamples *, 16>;
SampleContextTracker(StringMap<FunctionSamples> &Profiles);
// 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);
// 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);
// 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);
void promoteMergeContextSamplesTree(const Instruction &Inst,
StringRef CalleeName);
void addCallGraphEdges(CallGraph &CG, StringMap<Function *> &SymbolMap);
// Dump the internal context profile trie.
void dump();
private:
ContextTrieNode *getContextFor(const DILocation *DIL);
ContextTrieNode *getContextFor(const SampleContext &Context);
ContextTrieNode *getCalleeContextFor(const DILocation *DIL,
StringRef CalleeName);
ContextTrieNode *getOrCreateContextPath(const SampleContext &Context,
bool AllowCreate);
ContextTrieNode *getTopLevelContextNode(StringRef FName);
ContextTrieNode &addTopLevelContextNode(StringRef FName);
ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &NodeToPromo);
void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode,
StringRef ContextStrToRemove);
ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &FromNode,
ContextTrieNode &ToNodeParent,
StringRef ContextStrToRemove);
// Map from function name to context profiles (excluding base profile)
StringMap<ContextSamplesTy> FuncToCtxtProfileSet;
// Root node for context trie tree
ContextTrieNode RootContext;
};
} // end namespace llvm
#endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif
|
