49#include <unordered_map>
54#define DEBUG_TYPE "memprof-context-disambiguation"
57 "Number of function clones created during whole program analysis");
59 "Number of function clones created during ThinLTO backend");
61 "Number of functions that had clones created during ThinLTO backend");
62STATISTIC(AllocTypeNotCold,
"Number of not cold static allocations (possibly "
63 "cloned) during whole program analysis");
64STATISTIC(AllocTypeCold,
"Number of cold static allocations (possibly cloned) "
65 "during whole program analysis");
67 "Number of not cold static allocations (possibly cloned) during "
69STATISTIC(AllocTypeColdThinBackend,
"Number of cold static allocations "
70 "(possibly cloned) during ThinLTO backend");
72 "Number of original (not cloned) allocations with memprof profiles "
73 "during ThinLTO backend");
75 AllocVersionsThinBackend,
76 "Number of allocation versions (including clones) during ThinLTO backend");
78 "Maximum number of allocation versions created for an original "
79 "allocation during ThinLTO backend");
81 "Number of unclonable ambigous allocations during ThinLTO backend");
83 "Number of edges removed due to mismatched callees (profiled vs IR)");
85 "Number of profiled callees found via tail calls");
87 "Aggregate depth of profiled callees found via tail calls");
89 "Maximum depth of profiled callees found via tail calls");
91 "Number of profiled callees found via multiple tail call chains");
96 cl::desc(
"Specify the path prefix of the MemProf dot files."));
100 cl::desc(
"Export graph to dot files."));
104 cl::desc(
"Dump CallingContextGraph to stdout after each stage."));
108 cl::desc(
"Perform verification checks on CallingContextGraph."));
112 cl::desc(
"Perform frequent verification checks on nodes."));
115 "memprof-import-summary",
116 cl::desc(
"Import summary to use for testing the ThinLTO backend via opt"),
122 cl::desc(
"Max depth to recursively search for missing "
123 "frames through tail calls."));
134 cl::desc(
"Linking with hot/cold operator new interfaces"));
139 "Require target function definition when promoting indirect calls"));
159template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
160class CallsiteContextGraph {
162 CallsiteContextGraph() =
default;
163 CallsiteContextGraph(
const CallsiteContextGraph &) =
default;
164 CallsiteContextGraph(CallsiteContextGraph &&) =
default;
171 void identifyClones();
178 bool assignFunctions();
185 const CallsiteContextGraph &CCG) {
191 const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *>;
193 const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *>;
195 void exportToDot(std::string Label)
const;
198 struct FuncInfo final
199 :
public std::pair<FuncTy *, unsigned > {
200 using Base = std::pair<FuncTy *, unsigned>;
201 FuncInfo(
const Base &
B) :
Base(
B) {}
202 FuncInfo(FuncTy *
F =
nullptr,
unsigned CloneNo = 0) :
Base(
F, CloneNo) {}
203 explicit operator bool()
const {
return this->first !=
nullptr; }
204 FuncTy *
func()
const {
return this->first; }
205 unsigned cloneNo()
const {
return this->second; }
209 struct CallInfo final :
public std::pair<CallTy, unsigned > {
210 using Base = std::pair<CallTy, unsigned>;
212 CallInfo(CallTy Call =
nullptr,
unsigned CloneNo = 0)
214 explicit operator bool()
const {
return (
bool)this->first; }
215 CallTy call()
const {
return this->first; }
216 unsigned cloneNo()
const {
return this->second; }
217 void setCloneNo(
unsigned N) { this->second =
N; }
219 if (!
operator bool()) {
225 OS <<
"\t(clone " << cloneNo() <<
")";
248 bool Recursive =
false;
275 std::vector<std::shared_ptr<ContextEdge>> CalleeEdges;
279 std::vector<std::shared_ptr<ContextEdge>> CallerEdges;
283 const std::vector<std::shared_ptr<ContextEdge>> *
284 getEdgesWithAllocInfo()
const {
287 if (!CalleeEdges.empty())
289 if (!CallerEdges.empty()) {
302 auto *Edges = getEdgesWithAllocInfo();
306 for (
auto &Edge : *Edges)
307 Count += Edge->getContextIds().size();
309 for (
auto &Edge : *Edges)
310 ContextIds.
insert(Edge->getContextIds().begin(),
311 Edge->getContextIds().end());
317 uint8_t computeAllocType()
const {
318 auto *Edges = getEdgesWithAllocInfo();
320 return (
uint8_t)AllocationType::None;
324 for (
auto &Edge : *Edges) {
335 bool emptyContextIds()
const {
336 auto *Edges = getEdgesWithAllocInfo();
339 for (
auto &Edge : *Edges) {
340 if (!Edge->getContextIds().empty())
347 std::vector<ContextNode *> Clones;
350 ContextNode *CloneOf =
nullptr;
352 ContextNode(
bool IsAllocation) : IsAllocation(IsAllocation),
Call() {}
354 ContextNode(
bool IsAllocation,
CallInfo C)
355 : IsAllocation(IsAllocation),
Call(
C) {}
357 void addClone(ContextNode *Clone) {
359 CloneOf->Clones.push_back(Clone);
360 Clone->CloneOf = CloneOf;
362 Clones.push_back(Clone);
364 Clone->CloneOf =
this;
368 ContextNode *getOrigNode() {
375 unsigned int ContextId);
377 ContextEdge *findEdgeFromCallee(
const ContextNode *Callee);
378 ContextEdge *findEdgeFromCaller(
const ContextNode *Caller);
379 void eraseCalleeEdge(
const ContextEdge *Edge);
380 void eraseCallerEdge(
const ContextEdge *Edge);
384 bool hasCall()
const {
return (
bool)
Call.call(); }
390 bool isRemoved()
const {
393 return AllocTypes == (
uint8_t)AllocationType::None;
421 ContextIds(
std::
move(ContextIds)) {}
427 inline void clear() {
429 AllocTypes = (
uint8_t)AllocationType::None;
437 inline bool isRemoved()
const {
438 if (Callee || Caller)
459 void removeNoneTypeCalleeEdges(ContextNode *
Node);
460 void removeNoneTypeCallerEdges(ContextNode *
Node);
462 recursivelyRemoveNoneTypeCalleeEdges(ContextNode *
Node,
468 template <
class NodeT,
class IteratorT>
469 std::vector<uint64_t>
474 ContextNode *addAllocNode(
CallInfo Call,
const FuncTy *
F);
477 template <
class NodeT,
class IteratorT>
478 void addStackNodesForMIB(ContextNode *AllocNode,
487 void updateStackNodes();
491 void handleCallsitesWithMultipleTargets();
497 bool partitionCallsByCallee(
499 std::vector<std::pair<CallInfo, ContextNode *>> &NewCallToNode);
506 std::map<const ContextNode *, const FuncTy *> NodeToCallingFunc;
509 using EdgeIter =
typename std::vector<std::shared_ptr<ContextEdge>>::iterator;
514 struct CallContextInfo {
518 std::vector<uint64_t> StackIds;
532 void removeEdgeFromGraph(ContextEdge *Edge, EdgeIter *EI =
nullptr,
533 bool CalleeIter =
true);
541 void assignStackNodesPostOrder(
554 void propagateDuplicateContextIds(
560 void connectNewNode(ContextNode *NewNode, ContextNode *OrigNode,
568 return static_cast<const DerivedCCG *
>(
this)->getStackId(IdOrIndex);
578 calleesMatch(CallTy Call, EdgeIter &EI,
583 const FuncTy *getCalleeFunc(CallTy Call) {
584 return static_cast<DerivedCCG *
>(
this)->getCalleeFunc(Call);
590 bool calleeMatchesFunc(
591 CallTy Call,
const FuncTy *Func,
const FuncTy *CallerFunc,
592 std::vector<std::pair<CallTy, FuncTy *>> &FoundCalleeChain) {
593 return static_cast<DerivedCCG *
>(
this)->calleeMatchesFunc(
594 Call, Func, CallerFunc, FoundCalleeChain);
598 bool sameCallee(CallTy Call1, CallTy Call2) {
599 return static_cast<DerivedCCG *
>(
this)->sameCallee(Call1, Call2);
604 std::vector<uint64_t> getStackIdsWithContextNodesForCall(CallTy Call) {
605 return static_cast<DerivedCCG *
>(
this)->getStackIdsWithContextNodesForCall(
610 uint64_t getLastStackId(CallTy Call) {
611 return static_cast<DerivedCCG *
>(
this)->getLastStackId(Call);
616 AllocType == AllocationType::Cold ? AllocTypeCold++ : AllocTypeNotCold++;
617 static_cast<DerivedCCG *
>(
this)->updateAllocationCall(Call,
AllocType);
622 void updateCall(
CallInfo &CallerCall, FuncInfo CalleeFunc) {
623 static_cast<DerivedCCG *
>(
this)->updateCall(CallerCall, CalleeFunc);
629 FuncInfo cloneFunctionForCallsite(
630 FuncInfo &Func,
CallInfo &Call, std::map<CallInfo, CallInfo> &CallMap,
631 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
632 return static_cast<DerivedCCG *
>(
this)->cloneFunctionForCallsite(
633 Func, Call, CallMap, CallsWithMetadataInFunc, CloneNo);
638 std::string getLabel(
const FuncTy *Func,
const CallTy Call,
639 unsigned CloneNo)
const {
640 return static_cast<const DerivedCCG *
>(
this)->getLabel(Func, Call, CloneNo);
644 ContextNode *createNewNode(
bool IsAllocation,
const FuncTy *
F =
nullptr,
646 NodeOwner.push_back(std::make_unique<ContextNode>(IsAllocation,
C));
647 auto *NewNode = NodeOwner.back().get();
649 NodeToCallingFunc[NewNode] =
F;
654 ContextNode *getNodeForInst(
const CallInfo &
C);
655 ContextNode *getNodeForAlloc(
const CallInfo &
C);
656 ContextNode *getNodeForStackId(
uint64_t StackId);
679 moveEdgeToNewCalleeClone(
const std::shared_ptr<ContextEdge> &Edge,
680 EdgeIter *CallerEdgeI =
nullptr,
688 void moveEdgeToExistingCalleeClone(
const std::shared_ptr<ContextEdge> &Edge,
689 ContextNode *NewCallee,
690 EdgeIter *CallerEdgeI =
nullptr,
691 bool NewClone =
false,
700 void moveCalleeEdgeToNewCaller(EdgeIter &CalleeEdgeI, ContextNode *NewCaller);
728 std::vector<std::unique_ptr<ContextNode>> NodeOwner;
734 unsigned int LastContextId = 0;
737template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
739 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode;
740template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
742 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge;
743template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
745 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::FuncInfo;
746template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
748 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::CallInfo;
751class ModuleCallsiteContextGraph
752 :
public CallsiteContextGraph<ModuleCallsiteContextGraph, Function,
755 ModuleCallsiteContextGraph(
760 friend CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
765 bool calleeMatchesFunc(
767 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain);
769 bool findProfiledCalleeThroughTailCalls(
771 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain,
772 bool &FoundMultipleCalleeChains);
774 std::vector<uint64_t> getStackIdsWithContextNodesForCall(
Instruction *Call);
776 void updateCall(
CallInfo &CallerCall, FuncInfo CalleeFunc);
777 CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
779 cloneFunctionForCallsite(FuncInfo &Func,
CallInfo &Call,
780 std::map<CallInfo, CallInfo> &CallMap,
781 std::vector<CallInfo> &CallsWithMetadataInFunc,
784 unsigned CloneNo)
const;
793struct IndexCall :
public PointerUnion<CallsiteInfo *, AllocInfo *> {
795 IndexCall(std::nullptr_t) : IndexCall() {}
800 IndexCall *operator->() {
return this; }
805 if (
auto *AI = llvm::dyn_cast_if_present<AllocInfo *>(getBase())) {
808 auto *CI = llvm::dyn_cast_if_present<CallsiteInfo *>(getBase());
816class IndexCallsiteContextGraph
817 :
public CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
820 IndexCallsiteContextGraph(
825 ~IndexCallsiteContextGraph() {
830 for (
auto &
I : FunctionCalleesToSynthesizedCallsiteInfos) {
832 for (
auto &Callsite :
I.second)
833 FS->addCallsite(*Callsite.second);
838 friend CallsiteContextGraph<IndexCallsiteContextGraph,
FunctionSummary,
843 bool calleeMatchesFunc(
846 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain);
847 bool sameCallee(IndexCall &Call1, IndexCall &Call2);
848 bool findProfiledCalleeThroughTailCalls(
850 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain,
851 bool &FoundMultipleCalleeChains);
852 uint64_t getLastStackId(IndexCall &Call);
853 std::vector<uint64_t> getStackIdsWithContextNodesForCall(IndexCall &Call);
855 void updateCall(
CallInfo &CallerCall, FuncInfo CalleeFunc);
858 cloneFunctionForCallsite(FuncInfo &Func,
CallInfo &Call,
859 std::map<CallInfo, CallInfo> &CallMap,
860 std::vector<CallInfo> &CallsWithMetadataInFunc,
862 std::string getLabel(
const FunctionSummary *Func,
const IndexCall &Call,
863 unsigned CloneNo)
const;
867 std::map<const FunctionSummary *, ValueInfo> FSToVIMap;
878 std::map<ValueInfo, std::unique_ptr<CallsiteInfo>>>
879 FunctionCalleesToSynthesizedCallsiteInfos;
891 :
public DenseMapInfo<std::pair<IndexCall, unsigned>> {};
894 :
public DenseMapInfo<PointerUnion<CallsiteInfo *, AllocInfo *>> {};
907 ((
uint8_t)AllocationType::NotCold | (
uint8_t)AllocationType::Cold))
908 return AllocationType::NotCold;
916template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
918 const std::vector<uint8_t> &InAllocTypes,
919 const std::vector<std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>>>
923 assert(InAllocTypes.size() == Edges.size());
925 InAllocTypes.begin(), InAllocTypes.end(), Edges.begin(), Edges.end(),
927 const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &r) {
931 if (l == (uint8_t)AllocationType::None ||
932 r->AllocTypes == (uint8_t)AllocationType::None)
934 return allocTypeToUse(l) == allocTypeToUse(r->AllocTypes);
943template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
944bool allocTypesMatchClone(
945 const std::vector<uint8_t> &InAllocTypes,
946 const ContextNode<DerivedCCG, FuncTy, CallTy> *Clone) {
947 const ContextNode<DerivedCCG, FuncTy, CallTy> *
Node = Clone->CloneOf;
951 assert(InAllocTypes.size() ==
Node->CalleeEdges.size());
955 for (
const auto &E : Clone->CalleeEdges) {
957 EdgeCalleeMap[E->Callee] = E->AllocTypes;
961 for (
unsigned I = 0;
I <
Node->CalleeEdges.size();
I++) {
962 auto Iter = EdgeCalleeMap.
find(
Node->CalleeEdges[
I]->Callee);
964 if (Iter == EdgeCalleeMap.
end())
969 if (InAllocTypes[
I] == (
uint8_t)AllocationType::None ||
970 Iter->second == (
uint8_t)AllocationType::None)
972 if (allocTypeToUse(Iter->second) != allocTypeToUse(InAllocTypes[
I]))
980template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
981typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
982CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForInst(
984 ContextNode *
Node = getNodeForAlloc(
C);
988 return NonAllocationCallToContextNodeMap.lookup(
C);
991template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
992typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
993CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForAlloc(
995 return AllocationCallToContextNodeMap.lookup(
C);
998template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
999typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1000CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForStackId(
1002 auto StackEntryNode = StackEntryIdToContextNodeMap.find(StackId);
1003 if (StackEntryNode != StackEntryIdToContextNodeMap.end())
1004 return StackEntryNode->second;
1008template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1009void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1011 unsigned int ContextId) {
1012 for (
auto &Edge : CallerEdges) {
1013 if (Edge->Caller == Caller) {
1015 Edge->getContextIds().insert(ContextId);
1019 std::shared_ptr<ContextEdge> Edge = std::make_shared<ContextEdge>(
1021 CallerEdges.push_back(Edge);
1022 Caller->CalleeEdges.push_back(Edge);
1025template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1026void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::removeEdgeFromGraph(
1027 ContextEdge *Edge, EdgeIter *EI,
bool CalleeIter) {
1028 assert(!EI || (*EI)->get() == Edge);
1033 auto *
Callee = Edge->Callee;
1034 auto *
Caller = Edge->Caller;
1042 Callee->eraseCallerEdge(Edge);
1043 Caller->eraseCalleeEdge(Edge);
1044 }
else if (CalleeIter) {
1045 Callee->eraseCallerEdge(Edge);
1046 *EI =
Caller->CalleeEdges.erase(*EI);
1048 Caller->eraseCalleeEdge(Edge);
1049 *EI =
Callee->CallerEdges.erase(*EI);
1053template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1054void CallsiteContextGraph<
1055 DerivedCCG, FuncTy, CallTy>::removeNoneTypeCalleeEdges(ContextNode *
Node) {
1056 for (
auto EI =
Node->CalleeEdges.begin(); EI !=
Node->CalleeEdges.end();) {
1058 if (Edge->AllocTypes == (
uint8_t)AllocationType::None) {
1059 assert(Edge->ContextIds.empty());
1060 removeEdgeFromGraph(Edge.get(), &EI,
true);
1066template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1067void CallsiteContextGraph<
1068 DerivedCCG, FuncTy, CallTy>::removeNoneTypeCallerEdges(ContextNode *
Node) {
1069 for (
auto EI =
Node->CallerEdges.begin(); EI !=
Node->CallerEdges.end();) {
1071 if (Edge->AllocTypes == (
uint8_t)AllocationType::None) {
1072 assert(Edge->ContextIds.empty());
1073 Edge->Caller->eraseCalleeEdge(Edge.get());
1074 EI =
Node->CallerEdges.erase(EI);
1080template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1081typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge *
1082CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1083 findEdgeFromCallee(
const ContextNode *Callee) {
1084 for (
const auto &Edge : CalleeEdges)
1085 if (Edge->Callee == Callee)
1090template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1091typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge *
1092CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1093 findEdgeFromCaller(
const ContextNode *Caller) {
1094 for (
const auto &Edge : CallerEdges)
1095 if (Edge->Caller == Caller)
1100template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1101void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1102 eraseCalleeEdge(
const ContextEdge *Edge) {
1104 CalleeEdges, [Edge](
const std::shared_ptr<ContextEdge> &CalleeEdge) {
1105 return CalleeEdge.get() == Edge;
1107 assert(EI != CalleeEdges.end());
1108 CalleeEdges.erase(EI);
1111template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1112void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1113 eraseCallerEdge(
const ContextEdge *Edge) {
1115 CallerEdges, [Edge](
const std::shared_ptr<ContextEdge> &CallerEdge) {
1116 return CallerEdge.get() == Edge;
1118 assert(EI != CallerEdges.end());
1119 CallerEdges.erase(EI);
1122template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1123uint8_t CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::computeAllocType(
1126 (
uint8_t)AllocationType::Cold | (
uint8_t)AllocationType::NotCold;
1128 for (
auto Id : ContextIds) {
1137template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1139CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::intersectAllocTypesImpl(
1142 (
uint8_t)AllocationType::Cold | (
uint8_t)AllocationType::NotCold;
1144 for (
auto Id : Node1Ids) {
1145 if (!Node2Ids.
count(Id))
1155template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1156uint8_t CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::intersectAllocTypes(
1158 if (Node1Ids.
size() < Node2Ids.
size())
1159 return intersectAllocTypesImpl(Node1Ids, Node2Ids);
1161 return intersectAllocTypesImpl(Node2Ids, Node1Ids);
1164template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1165typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1166CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::addAllocNode(
1168 assert(!getNodeForAlloc(Call));
1169 ContextNode *AllocNode = createNewNode(
true,
F, Call);
1170 AllocationCallToContextNodeMap[
Call] = AllocNode;
1172 AllocNode->OrigStackOrAllocId = LastContextId;
1175 AllocNode->AllocTypes = (
uint8_t)AllocationType::None;
1184 if (AllocTypes & (
uint8_t)AllocationType::NotCold)
1186 if (AllocTypes & (
uint8_t)AllocationType::Cold)
1191template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1192template <
class NodeT,
class IteratorT>
1193void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::addStackNodesForMIB(
1202 ContextIdToAllocationType[++LastContextId] =
AllocType;
1206 auto &
Entry = ContextIdToContextSizeInfos[LastContextId];
1216 ContextNode *PrevNode = AllocNode;
1223 ContextIter != StackContext.
end(); ++ContextIter) {
1224 auto StackId = getStackId(*ContextIter);
1225 ContextNode *
StackNode = getNodeForStackId(StackId);
1228 StackEntryIdToContextNodeMap[StackId] =
StackNode;
1229 StackNode->OrigStackOrAllocId = StackId;
1240template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1242CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::duplicateContextIds(
1246 for (
auto OldId : StackSequenceContextIds) {
1247 NewContextIds.
insert(++LastContextId);
1248 OldToNewContextIds[OldId].insert(LastContextId);
1249 assert(ContextIdToAllocationType.count(OldId));
1251 ContextIdToAllocationType[LastContextId] = ContextIdToAllocationType[OldId];
1253 return NewContextIds;
1256template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1257void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
1258 propagateDuplicateContextIds(
1263 for (
auto Id : ContextIds)
1264 if (
auto NewId = OldToNewContextIds.find(Id);
1265 NewId != OldToNewContextIds.end())
1266 NewIds.
insert(NewId->second.begin(), NewId->second.end());
1271 auto UpdateCallers = [&](ContextNode *
Node,
1273 auto &&UpdateCallers) ->
void {
1274 for (
const auto &Edge :
Node->CallerEdges) {
1275 auto Inserted = Visited.insert(Edge.get());
1278 ContextNode *NextNode = Edge->Caller;
1282 if (!NewIdsToAdd.
empty()) {
1283 Edge->getContextIds().insert(NewIdsToAdd.
begin(), NewIdsToAdd.
end());
1284 UpdateCallers(NextNode, Visited, UpdateCallers);
1290 for (
auto &Entry : AllocationCallToContextNodeMap) {
1292 UpdateCallers(
Node, Visited, UpdateCallers);
1296template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1297void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::connectNewNode(
1298 ContextNode *NewNode, ContextNode *OrigNode,
bool TowardsCallee,
1303 TowardsCallee ? OrigNode->CalleeEdges : OrigNode->CallerEdges;
1305 for (
auto EI = OrigEdges.begin(); EI != OrigEdges.end();) {
1311 set_subtract(Edge->getContextIds(), RemainingContextIds, NewEdgeContextIds,
1312 NotFoundContextIds);
1313 RemainingContextIds.
swap(NotFoundContextIds);
1315 if (NewEdgeContextIds.
empty()) {
1319 if (TowardsCallee) {
1320 uint8_t NewAllocType = computeAllocType(NewEdgeContextIds);
1321 auto NewEdge = std::make_shared<ContextEdge>(
1322 Edge->Callee, NewNode, NewAllocType, std::move(NewEdgeContextIds));
1323 NewNode->CalleeEdges.push_back(NewEdge);
1324 NewEdge->Callee->CallerEdges.push_back(NewEdge);
1326 uint8_t NewAllocType = computeAllocType(NewEdgeContextIds);
1327 auto NewEdge = std::make_shared<ContextEdge>(
1328 NewNode, Edge->Caller, NewAllocType, std::move(NewEdgeContextIds));
1329 NewNode->CallerEdges.push_back(NewEdge);
1330 NewEdge->Caller->CalleeEdges.push_back(NewEdge);
1333 if (Edge->getContextIds().empty()) {
1334 removeEdgeFromGraph(Edge.get(), &EI, TowardsCallee);
1341template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1343 const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &Edge) {
1347 assert(!Edge->ContextIds.empty());
1350template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1352 bool CheckEdges =
true) {
1353 if (
Node->isRemoved())
1357 auto NodeContextIds =
Node->getContextIds();
1361 if (
Node->CallerEdges.size()) {
1363 Node->CallerEdges.front()->ContextIds);
1366 checkEdge<DerivedCCG, FuncTy, CallTy>(Edge);
1367 set_union(CallerEdgeContextIds, Edge->ContextIds);
1371 assert(NodeContextIds == CallerEdgeContextIds ||
1374 if (
Node->CalleeEdges.size()) {
1376 Node->CalleeEdges.front()->ContextIds);
1379 checkEdge<DerivedCCG, FuncTy, CallTy>(Edge);
1380 set_union(CalleeEdgeContextIds, Edge->getContextIds());
1382 assert(NodeContextIds == CalleeEdgeContextIds);
1391 for (
const auto &E :
Node->CalleeEdges)
1397template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1398void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
1399 assignStackNodesPostOrder(
1402 &StackIdToMatchingCalls,
1411 auto CallerEdges =
Node->CallerEdges;
1412 for (
auto &Edge : CallerEdges) {
1414 if (Edge->isRemoved()) {
1418 assignStackNodesPostOrder(Edge->Caller, Visited, StackIdToMatchingCalls,
1419 CallToMatchingCall);
1428 if (
Node->IsAllocation ||
1429 !StackIdToMatchingCalls.count(
Node->OrigStackOrAllocId))
1432 auto &Calls = StackIdToMatchingCalls[
Node->OrigStackOrAllocId];
1436 if (Calls.size() == 1) {
1437 auto &[
Call, Ids,
Func, SavedContextIds] = Calls[0];
1438 if (Ids.size() == 1) {
1439 assert(SavedContextIds.empty());
1442 if (
Node->Recursive)
1444 Node->setCall(Call);
1445 NonAllocationCallToContextNodeMap[
Call] =
Node;
1455 ContextNode *LastNode = getNodeForStackId(LastId);
1460 ContextNode *LastNode =
Node;
1467 bool PrevIterCreatedNode =
false;
1468 bool CreatedNode =
false;
1469 for (
unsigned I = 0;
I < Calls.size();
1470 I++, PrevIterCreatedNode = CreatedNode) {
1471 CreatedNode =
false;
1472 auto &[
Call, Ids,
Func, SavedContextIds] = Calls[
I];
1475 if (SavedContextIds.empty()) {
1480 if (!CallToMatchingCall.
contains(Call))
1482 auto MatchingCall = CallToMatchingCall[
Call];
1483 if (!NonAllocationCallToContextNodeMap.contains(MatchingCall)) {
1487 assert(
I > 0 && !PrevIterCreatedNode);
1490 NonAllocationCallToContextNodeMap[MatchingCall]->MatchingCalls.push_back(
1495 assert(LastId == Ids.back());
1504 ContextNode *PrevNode = LastNode;
1508 for (
auto IdIter = Ids.rbegin() + 1; IdIter != Ids.rend(); IdIter++) {
1510 ContextNode *CurNode = getNodeForStackId(Id);
1514 assert(!CurNode->Recursive);
1516 auto *Edge = CurNode->findEdgeFromCaller(PrevNode);
1528 if (SavedContextIds.empty()) {
1537 ContextNode *NewNode = createNewNode(
false, Func, Call);
1538 NonAllocationCallToContextNodeMap[
Call] = NewNode;
1540 NewNode->AllocTypes = computeAllocType(SavedContextIds);
1542 ContextNode *FirstNode = getNodeForStackId(Ids[0]);
1548 connectNewNode(NewNode, FirstNode,
true, SavedContextIds);
1553 connectNewNode(NewNode, LastNode,
false, SavedContextIds);
1558 for (
auto Id : Ids) {
1559 ContextNode *CurNode = getNodeForStackId(Id);
1566 auto *PrevEdge = CurNode->findEdgeFromCallee(PrevNode);
1568 set_subtract(PrevEdge->getContextIds(), SavedContextIds);
1569 if (PrevEdge->getContextIds().empty())
1570 removeEdgeFromGraph(PrevEdge);
1575 CurNode->AllocTypes = CurNode->CalleeEdges.empty()
1576 ? (
uint8_t)AllocationType::None
1577 : CurNode->computeAllocType();
1581 checkNode<DerivedCCG, FuncTy, CallTy>(NewNode,
true);
1582 for (
auto Id : Ids) {
1583 ContextNode *CurNode = getNodeForStackId(Id);
1586 checkNode<DerivedCCG, FuncTy, CallTy>(CurNode,
true);
1592template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1593void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::updateStackNodes() {
1602 for (
auto &[Func, CallsWithMetadata] : FuncToCallsWithMetadata) {
1603 for (
auto &Call : CallsWithMetadata) {
1605 if (AllocationCallToContextNodeMap.count(Call))
1607 auto StackIdsWithContextNodes =
1608 getStackIdsWithContextNodesForCall(
Call.call());
1611 if (StackIdsWithContextNodes.empty())
1615 StackIdToMatchingCalls[StackIdsWithContextNodes.back()].push_back(
1616 {
Call.call(), StackIdsWithContextNodes, Func, {}});
1631 for (
auto &It : StackIdToMatchingCalls) {
1632 auto &Calls = It.getSecond();
1634 if (Calls.size() == 1) {
1635 auto &Ids = Calls[0].StackIds;
1636 if (Ids.size() == 1)
1650 for (
const auto &[
Idx, CallCtxInfo] :
enumerate(Calls))
1651 FuncToIndex.
insert({CallCtxInfo.Func,
Idx});
1653 Calls.begin(), Calls.end(),
1654 [&FuncToIndex](
const CallContextInfo &
A,
const CallContextInfo &
B) {
1655 return A.StackIds.size() > B.StackIds.size() ||
1656 (A.StackIds.size() == B.StackIds.size() &&
1657 (A.StackIds < B.StackIds ||
1658 (A.StackIds == B.StackIds &&
1659 FuncToIndex[A.Func] < FuncToIndex[B.Func])));
1666 ContextNode *LastNode = getNodeForStackId(LastId);
1670 if (LastNode->Recursive)
1686 for (
unsigned I = 0;
I < Calls.size();
I++) {
1687 auto &[
Call, Ids,
Func, SavedContextIds] = Calls[
I];
1688 assert(SavedContextIds.empty());
1689 assert(LastId == Ids.back());
1694 if (
I > 0 && Ids != Calls[
I - 1].StackIds)
1695 MatchingIdsFuncSet.
clear();
1704 ContextNode *PrevNode = LastNode;
1705 ContextNode *CurNode = LastNode;
1710 for (
auto IdIter = Ids.rbegin() + 1; IdIter != Ids.rend(); IdIter++) {
1712 CurNode = getNodeForStackId(Id);
1716 if (CurNode->Recursive) {
1721 auto *Edge = CurNode->findEdgeFromCaller(PrevNode);
1739 set_intersect(StackSequenceContextIds, Edge->getContextIds());
1742 if (StackSequenceContextIds.
empty()) {
1755 if (Ids.back() != getLastStackId(Call)) {
1756 for (
const auto &PE : LastNode->CallerEdges) {
1757 set_subtract(StackSequenceContextIds, PE->getContextIds());
1758 if (StackSequenceContextIds.
empty())
1762 if (StackSequenceContextIds.
empty())
1774 MatchingIdsFuncSet.
insert(Func);
1781 bool DuplicateContextIds =
false;
1782 for (
unsigned J =
I + 1; J < Calls.size(); J++) {
1783 auto &CallCtxInfo = Calls[J];
1784 auto &NextIds = CallCtxInfo.StackIds;
1787 auto *NextFunc = CallCtxInfo.Func;
1788 if (NextFunc != Func) {
1791 DuplicateContextIds =
true;
1794 auto &NextCall = CallCtxInfo.Call;
1795 CallToMatchingCall[NextCall] =
Call;
1806 OldToNewContextIds.
reserve(OldToNewContextIds.
size() +
1807 StackSequenceContextIds.
size());
1810 ? duplicateContextIds(StackSequenceContextIds, OldToNewContextIds)
1811 : StackSequenceContextIds;
1812 assert(!SavedContextIds.empty());
1814 if (!DuplicateContextIds) {
1818 set_subtract(LastNodeContextIds, StackSequenceContextIds);
1819 if (LastNodeContextIds.
empty())
1826 propagateDuplicateContextIds(OldToNewContextIds);
1837 for (
auto &Entry : AllocationCallToContextNodeMap)
1838 assignStackNodesPostOrder(
Entry.second, Visited, StackIdToMatchingCalls,
1839 CallToMatchingCall);
1846 Call->getMetadata(LLVMContext::MD_callsite));
1847 return CallsiteContext.
back();
1850uint64_t IndexCallsiteContextGraph::getLastStackId(IndexCall &Call) {
1853 CallsiteContext(dyn_cast_if_present<CallsiteInfo *>(
Call.getBase()));
1855 return Index.getStackIdAtIndex(CallsiteContext.
back());
1872std::string ModuleCallsiteContextGraph::getLabel(
const Function *Func,
1874 unsigned CloneNo)
const {
1875 return (
Twine(
Call->getFunction()->getName()) +
" -> " +
1876 cast<CallBase>(Call)->getCalledFunction()->getName())
1880std::string IndexCallsiteContextGraph::getLabel(
const FunctionSummary *Func,
1881 const IndexCall &Call,
1882 unsigned CloneNo)
const {
1883 auto VI = FSToVIMap.find(Func);
1884 assert(VI != FSToVIMap.end());
1885 if (isa<AllocInfo *>(
Call.getBase()))
1886 return (
VI->second.name() +
" -> alloc").str();
1888 auto *Callsite = dyn_cast_if_present<CallsiteInfo *>(
Call.getBase());
1889 return (
VI->second.name() +
" -> " +
1891 Callsite->Clones[CloneNo]))
1896std::vector<uint64_t>
1897ModuleCallsiteContextGraph::getStackIdsWithContextNodesForCall(
1900 Call->getMetadata(LLVMContext::MD_callsite));
1901 return getStackIdsWithContextNodes<MDNode, MDNode::op_iterator>(
1905std::vector<uint64_t>
1906IndexCallsiteContextGraph::getStackIdsWithContextNodesForCall(IndexCall &Call) {
1909 CallsiteContext(dyn_cast_if_present<CallsiteInfo *>(
Call.getBase()));
1915template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1916template <
class NodeT,
class IteratorT>
1917std::vector<uint64_t>
1918CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getStackIdsWithContextNodes(
1920 std::vector<uint64_t> StackIds;
1921 for (
auto IdOrIndex : CallsiteContext) {
1922 auto StackId = getStackId(IdOrIndex);
1923 ContextNode *
Node = getNodeForStackId(StackId);
1926 StackIds.push_back(StackId);
1931ModuleCallsiteContextGraph::ModuleCallsiteContextGraph(
1934 :
Mod(
M), OREGetter(OREGetter) {
1936 std::vector<CallInfo> CallsWithMetadata;
1937 for (
auto &BB :
F) {
1938 for (
auto &
I : BB) {
1939 if (!isa<CallBase>(
I))
1941 if (
auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof)) {
1942 CallsWithMetadata.push_back(&
I);
1943 auto *AllocNode = addAllocNode(&
I, &
F);
1944 auto *CallsiteMD =
I.getMetadata(LLVMContext::MD_callsite);
1948 for (
auto &MDOp : MemProfMD->operands()) {
1949 auto *MIBMD = cast<const MDNode>(MDOp);
1950 std::vector<ContextTotalSize> ContextSizeInfo;
1952 if (MIBMD->getNumOperands() > 2) {
1953 for (
unsigned I = 2;
I < MIBMD->getNumOperands();
I++) {
1954 MDNode *ContextSizePair =
1955 dyn_cast<MDNode>(MIBMD->getOperand(
I));
1957 uint64_t FullStackId = mdconst::dyn_extract<ConstantInt>(
1960 uint64_t TotalSize = mdconst::dyn_extract<ConstantInt>(
1963 ContextSizeInfo.push_back({FullStackId, TotalSize});
1969 addStackNodesForMIB<MDNode, MDNode::op_iterator>(
1970 AllocNode, StackContext, CallsiteContext,
1973 assert(AllocNode->AllocTypes != (
uint8_t)AllocationType::None);
1976 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
1977 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
1980 else if (
I.getMetadata(LLVMContext::MD_callsite)) {
1981 CallsWithMetadata.push_back(&
I);
1985 if (!CallsWithMetadata.empty())
1986 FuncToCallsWithMetadata[&
F] = CallsWithMetadata;
1990 dbgs() <<
"CCG before updating call stack chains:\n";
1995 exportToDot(
"prestackupdate");
1999 handleCallsitesWithMultipleTargets();
2002 for (
auto &FuncEntry : FuncToCallsWithMetadata)
2003 for (
auto &Call : FuncEntry.second)
2004 Call.call()->setMetadata(LLVMContext::MD_callsite,
nullptr);
2007IndexCallsiteContextGraph::IndexCallsiteContextGraph(
2012 for (
auto &
I : Index) {
2014 for (
auto &S :
VI.getSummaryList()) {
2023 !isPrevailing(
VI.getGUID(), S.get()))
2025 auto *
FS = dyn_cast<FunctionSummary>(S.get());
2028 std::vector<CallInfo> CallsWithMetadata;
2029 if (!
FS->allocs().empty()) {
2030 for (
auto &AN :
FS->mutableAllocs()) {
2035 if (AN.MIBs.empty())
2037 IndexCall AllocCall(&AN);
2038 CallsWithMetadata.push_back(AllocCall);
2039 auto *AllocNode = addAllocNode(AllocCall, FS);
2047 AN.ContextSizeInfos.size() == AN.MIBs.size());
2049 for (
auto &MIB : AN.MIBs) {
2052 std::vector<ContextTotalSize> ContextSizeInfo;
2054 for (
auto [FullStackId, TotalSize] : AN.ContextSizeInfos[
I])
2055 ContextSizeInfo.push_back({FullStackId, TotalSize});
2057 addStackNodesForMIB<MIBInfo, SmallVector<unsigned>::const_iterator>(
2058 AllocNode, StackContext, EmptyContext, MIB.AllocType,
2062 assert(AllocNode->AllocTypes != (
uint8_t)AllocationType::None);
2067 AN.Versions[0] = (
uint8_t)allocTypeToUse(AllocNode->AllocTypes);
2071 if (!
FS->callsites().empty())
2072 for (
auto &SN :
FS->mutableCallsites()) {
2073 IndexCall StackNodeCall(&SN);
2074 CallsWithMetadata.push_back(StackNodeCall);
2077 if (!CallsWithMetadata.empty())
2078 FuncToCallsWithMetadata[
FS] = CallsWithMetadata;
2080 if (!
FS->allocs().empty() || !
FS->callsites().empty())
2086 dbgs() <<
"CCG before updating call stack chains:\n";
2091 exportToDot(
"prestackupdate");
2095 handleCallsitesWithMultipleTargets();
2098template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2099void CallsiteContextGraph<DerivedCCG, FuncTy,
2100 CallTy>::handleCallsitesWithMultipleTargets() {
2115 std::vector<std::pair<CallInfo, ContextNode *>> NewCallToNode;
2116 for (
auto &Entry : NonAllocationCallToContextNodeMap) {
2126 std::vector<CallInfo> AllCalls;
2127 AllCalls.reserve(
Node->MatchingCalls.size() + 1);
2128 AllCalls.push_back(
Node->Call);
2129 AllCalls.insert(AllCalls.end(),
Node->MatchingCalls.begin(),
2130 Node->MatchingCalls.end());
2143 if (partitionCallsByCallee(
Node, AllCalls, NewCallToNode))
2146 auto It = AllCalls.begin();
2148 for (; It != AllCalls.end(); ++It) {
2151 for (
auto EI =
Node->CalleeEdges.begin(); EI !=
Node->CalleeEdges.end();
2154 if (!Edge->Callee->hasCall())
2156 assert(NodeToCallingFunc.count(Edge->Callee));
2158 if (!calleesMatch(
ThisCall.call(), EI, TailCallToContextNodeMap)) {
2167 if (
Node->Call != ThisCall) {
2168 Node->setCall(ThisCall);
2179 Node->MatchingCalls.clear();
2182 if (It == AllCalls.end()) {
2183 RemovedEdgesWithMismatchedCallees++;
2192 for (++It; It != AllCalls.end(); ++It) {
2196 Node->MatchingCalls.push_back(ThisCall);
2205 NonAllocationCallToContextNodeMap.remove_if([](
const auto &it) {
2206 return !it.second->hasCall() || it.second->Call != it.first;
2210 for (
auto &[Call,
Node] : NewCallToNode)
2211 NonAllocationCallToContextNodeMap[
Call] =
Node;
2215 for (
auto &[Call,
Node] : TailCallToContextNodeMap)
2216 NonAllocationCallToContextNodeMap[
Call] =
Node;
2219template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2220bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::partitionCallsByCallee(
2222 std::vector<std::pair<CallInfo, ContextNode *>> &NewCallToNode) {
2226 struct CallsWithSameCallee {
2227 std::vector<CallInfo> Calls;
2228 ContextNode *
Node =
nullptr;
2234 for (
auto ThisCall : AllCalls) {
2235 auto *
F = getCalleeFunc(
ThisCall.call());
2237 CalleeFuncToCallInfo[
F].Calls.push_back(ThisCall);
2246 for (
const auto &Edge :
Node->CalleeEdges) {
2247 if (!Edge->Callee->hasCall())
2249 const FuncTy *ProfiledCalleeFunc = NodeToCallingFunc[Edge->Callee];
2250 if (CalleeFuncToCallInfo.
contains(ProfiledCalleeFunc))
2251 CalleeNodeToCallInfo[Edge->Callee] =
2252 &CalleeFuncToCallInfo[ProfiledCalleeFunc];
2258 if (CalleeNodeToCallInfo.
empty())
2270 ContextNode *UnmatchedCalleesNode =
nullptr;
2272 bool UsedOrigNode =
false;
2274 for (
auto EI =
Node->CalleeEdges.begin(); EI !=
Node->CalleeEdges.end();) {
2276 if (!Edge->Callee->hasCall()) {
2283 ContextNode *CallerNodeToUse =
nullptr;
2287 if (!CalleeNodeToCallInfo.
contains(Edge->Callee)) {
2288 if (!UnmatchedCalleesNode)
2289 UnmatchedCalleesNode =
2290 createNewNode(
false, NodeToCallingFunc[
Node]);
2291 CallerNodeToUse = UnmatchedCalleesNode;
2295 auto *
Info = CalleeNodeToCallInfo[Edge->Callee];
2298 if (!UsedOrigNode) {
2301 Node->MatchingCalls.clear();
2302 UsedOrigNode =
true;
2305 createNewNode(
false, NodeToCallingFunc[
Node]);
2309 Info->Node->setCall(
Info->Calls.front());
2310 Info->Node->MatchingCalls.insert(
Info->Node->MatchingCalls.end(),
2311 Info->Calls.begin() + 1,
2316 NewCallToNode.push_back({
Info->Node->Call,
Info->Node});
2318 CallerNodeToUse =
Info->Node;
2322 if (CallerNodeToUse ==
Node) {
2327 moveCalleeEdgeToNewCaller(EI, CallerNodeToUse);
2334 for (
auto &
I : CalleeNodeToCallInfo)
2335 removeNoneTypeCallerEdges(
I.second->Node);
2336 if (UnmatchedCalleesNode)
2337 removeNoneTypeCallerEdges(UnmatchedCalleesNode);
2338 removeNoneTypeCallerEdges(
Node);
2351 return Index.getStackIdAtIndex(IdOrIndex);
2354template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2355bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::calleesMatch(
2356 CallTy Call, EdgeIter &EI,
2359 const FuncTy *ProfiledCalleeFunc = NodeToCallingFunc[Edge->Callee];
2360 const FuncTy *CallerFunc = NodeToCallingFunc[Edge->Caller];
2363 std::vector<std::pair<CallTy, FuncTy *>> FoundCalleeChain;
2364 if (!calleeMatchesFunc(Call, ProfiledCalleeFunc, CallerFunc,
2369 if (FoundCalleeChain.empty())
2372 auto AddEdge = [Edge, &EI](ContextNode *
Caller, ContextNode *
Callee) {
2373 auto *CurEdge =
Callee->findEdgeFromCaller(Caller);
2377 CurEdge->ContextIds.insert(Edge->ContextIds.begin(),
2378 Edge->ContextIds.end());
2379 CurEdge->AllocTypes |= Edge->AllocTypes;
2384 auto NewEdge = std::make_shared<ContextEdge>(
2385 Callee, Caller, Edge->AllocTypes, Edge->ContextIds);
2386 Callee->CallerEdges.push_back(NewEdge);
2387 if (Caller == Edge->Caller) {
2391 EI =
Caller->CalleeEdges.insert(EI, NewEdge);
2394 "Iterator position not restored after insert and increment");
2396 Caller->CalleeEdges.push_back(NewEdge);
2401 auto *CurCalleeNode = Edge->Callee;
2402 for (
auto &[NewCall, Func] : FoundCalleeChain) {
2403 ContextNode *NewNode =
nullptr;
2405 if (TailCallToContextNodeMap.
count(NewCall)) {
2406 NewNode = TailCallToContextNodeMap[NewCall];
2407 NewNode->AllocTypes |= Edge->AllocTypes;
2409 FuncToCallsWithMetadata[
Func].push_back({NewCall});
2411 NewNode = createNewNode(
false, Func, NewCall);
2412 TailCallToContextNodeMap[NewCall] = NewNode;
2413 NewNode->AllocTypes = Edge->AllocTypes;
2417 AddEdge(NewNode, CurCalleeNode);
2419 CurCalleeNode = NewNode;
2423 AddEdge(Edge->Caller, CurCalleeNode);
2427 auto *
Caller = Edge->Caller;
2431 removeEdgeFromGraph(Edge.get(), &EI,
true);
2443bool ModuleCallsiteContextGraph::findProfiledCalleeThroughTailCalls(
2445 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain,
2446 bool &FoundMultipleCalleeChains) {
2453 FoundCalleeChain.push_back({Callsite,
F});
2456 auto *CalleeFunc = dyn_cast<Function>(CurCallee);
2458 auto *Alias = dyn_cast<GlobalAlias>(CurCallee);
2460 CalleeFunc = dyn_cast<Function>(Alias->getAliasee());
2468 bool FoundSingleCalleeChain =
false;
2469 for (
auto &BB : *CalleeFunc) {
2470 for (
auto &
I : BB) {
2471 auto *CB = dyn_cast<CallBase>(&
I);
2472 if (!CB || !CB->isTailCall())
2474 auto *CalledValue = CB->getCalledOperand();
2475 auto *CalledFunction = CB->getCalledFunction();
2476 if (CalledValue && !CalledFunction) {
2477 CalledValue = CalledValue->stripPointerCasts();
2479 CalledFunction = dyn_cast<Function>(CalledValue);
2483 if (
auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
2484 assert(!CalledFunction &&
2485 "Expected null called function in callsite for alias");
2486 CalledFunction = dyn_cast<Function>(GA->getAliaseeObject());
2488 if (!CalledFunction)
2490 if (CalledFunction == ProfiledCallee) {
2491 if (FoundSingleCalleeChain) {
2492 FoundMultipleCalleeChains =
true;
2495 FoundSingleCalleeChain =
true;
2496 FoundProfiledCalleeCount++;
2497 FoundProfiledCalleeDepth +=
Depth;
2498 if (
Depth > FoundProfiledCalleeMaxDepth)
2499 FoundProfiledCalleeMaxDepth =
Depth;
2500 SaveCallsiteInfo(&
I, CalleeFunc);
2501 }
else if (findProfiledCalleeThroughTailCalls(
2502 ProfiledCallee, CalledFunction,
Depth + 1,
2503 FoundCalleeChain, FoundMultipleCalleeChains)) {
2506 assert(!FoundMultipleCalleeChains);
2507 if (FoundSingleCalleeChain) {
2508 FoundMultipleCalleeChains =
true;
2511 FoundSingleCalleeChain =
true;
2512 SaveCallsiteInfo(&
I, CalleeFunc);
2513 }
else if (FoundMultipleCalleeChains)
2518 return FoundSingleCalleeChain;
2522 auto *CB = dyn_cast<CallBase>(Call);
2523 if (!CB->getCalledOperand() || CB->isIndirectCall())
2525 auto *CalleeVal = CB->getCalledOperand()->stripPointerCasts();
2526 auto *Alias = dyn_cast<GlobalAlias>(CalleeVal);
2528 return dyn_cast<Function>(Alias->getAliasee());
2529 return dyn_cast<Function>(CalleeVal);
2532bool ModuleCallsiteContextGraph::calleeMatchesFunc(
2534 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain) {
2535 auto *CB = dyn_cast<CallBase>(Call);
2536 if (!CB->getCalledOperand() || CB->isIndirectCall())
2538 auto *CalleeVal = CB->getCalledOperand()->stripPointerCasts();
2539 auto *CalleeFunc = dyn_cast<Function>(CalleeVal);
2540 if (CalleeFunc == Func)
2542 auto *Alias = dyn_cast<GlobalAlias>(CalleeVal);
2543 if (Alias && Alias->getAliasee() == Func)
2554 bool FoundMultipleCalleeChains =
false;
2555 if (!findProfiledCalleeThroughTailCalls(Func, CalleeVal,
Depth,
2557 FoundMultipleCalleeChains)) {
2558 LLVM_DEBUG(
dbgs() <<
"Not found through unique tail call chain: "
2559 <<
Func->getName() <<
" from " << CallerFunc->
getName()
2560 <<
" that actually called " << CalleeVal->getName()
2561 << (FoundMultipleCalleeChains
2562 ?
" (found multiple possible chains)"
2565 if (FoundMultipleCalleeChains)
2566 FoundProfiledCalleeNonUniquelyCount++;
2573bool ModuleCallsiteContextGraph::sameCallee(
Instruction *Call1,
2575 auto *CB1 = cast<CallBase>(Call1);
2576 if (!CB1->getCalledOperand() || CB1->isIndirectCall())
2578 auto *CalleeVal1 = CB1->getCalledOperand()->stripPointerCasts();
2579 auto *CalleeFunc1 = dyn_cast<Function>(CalleeVal1);
2580 auto *CB2 = cast<CallBase>(Call2);
2581 if (!CB2->getCalledOperand() || CB2->isIndirectCall())
2583 auto *CalleeVal2 = CB2->getCalledOperand()->stripPointerCasts();
2584 auto *CalleeFunc2 = dyn_cast<Function>(CalleeVal2);
2585 return CalleeFunc1 == CalleeFunc2;
2588bool IndexCallsiteContextGraph::findProfiledCalleeThroughTailCalls(
2590 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain,
2591 bool &FoundMultipleCalleeChains) {
2600 if (!FunctionCalleesToSynthesizedCallsiteInfos.count(FS) ||
2601 !FunctionCalleesToSynthesizedCallsiteInfos[
FS].count(Callee))
2604 FunctionCalleesToSynthesizedCallsiteInfos[FS][Callee] =
2607 FunctionCalleesToSynthesizedCallsiteInfos[
FS][
Callee].get();
2608 FoundCalleeChain.push_back({NewCallsiteInfo,
FS});
2615 bool FoundSingleCalleeChain =
false;
2618 !isPrevailing(CurCallee.
getGUID(), S.get()))
2620 auto *
FS = dyn_cast<FunctionSummary>(S->getBaseObject());
2623 auto FSVI = CurCallee;
2624 auto *AS = dyn_cast<AliasSummary>(S.get());
2626 FSVI = AS->getAliaseeVI();
2627 for (
auto &CallEdge :
FS->calls()) {
2628 if (!CallEdge.second.hasTailCall())
2630 if (CallEdge.first == ProfiledCallee) {
2631 if (FoundSingleCalleeChain) {
2632 FoundMultipleCalleeChains =
true;
2635 FoundSingleCalleeChain =
true;
2636 FoundProfiledCalleeCount++;
2637 FoundProfiledCalleeDepth +=
Depth;
2638 if (
Depth > FoundProfiledCalleeMaxDepth)
2639 FoundProfiledCalleeMaxDepth =
Depth;
2640 CreateAndSaveCallsiteInfo(CallEdge.first, FS);
2642 assert(!FSToVIMap.count(FS) || FSToVIMap[FS] == FSVI);
2643 FSToVIMap[
FS] = FSVI;
2644 }
else if (findProfiledCalleeThroughTailCalls(
2645 ProfiledCallee, CallEdge.first,
Depth + 1,
2646 FoundCalleeChain, FoundMultipleCalleeChains)) {
2649 assert(!FoundMultipleCalleeChains);
2650 if (FoundSingleCalleeChain) {
2651 FoundMultipleCalleeChains =
true;
2654 FoundSingleCalleeChain =
true;
2655 CreateAndSaveCallsiteInfo(CallEdge.first, FS);
2657 assert(!FSToVIMap.count(FS) || FSToVIMap[FS] == FSVI);
2658 FSToVIMap[
FS] = FSVI;
2659 }
else if (FoundMultipleCalleeChains)
2664 return FoundSingleCalleeChain;
2668IndexCallsiteContextGraph::getCalleeFunc(IndexCall &Call) {
2670 dyn_cast_if_present<CallsiteInfo *>(
Call.getBase())->Callee;
2671 if (
Callee.getSummaryList().empty())
2673 return dyn_cast<FunctionSummary>(
Callee.getSummaryList()[0]->getBaseObject());
2676bool IndexCallsiteContextGraph::calleeMatchesFunc(
2679 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain) {
2681 dyn_cast_if_present<CallsiteInfo *>(
Call.getBase())->Callee;
2685 Callee.getSummaryList().empty()
2687 : dyn_cast<AliasSummary>(
Callee.getSummaryList()[0].get());
2688 assert(FSToVIMap.count(Func));
2689 auto FuncVI = FSToVIMap[
Func];
2690 if (Callee == FuncVI ||
2705 bool FoundMultipleCalleeChains =
false;
2706 if (!findProfiledCalleeThroughTailCalls(
2707 FuncVI, Callee,
Depth, FoundCalleeChain, FoundMultipleCalleeChains)) {
2708 LLVM_DEBUG(
dbgs() <<
"Not found through unique tail call chain: " << FuncVI
2709 <<
" from " << FSToVIMap[CallerFunc]
2710 <<
" that actually called " << Callee
2711 << (FoundMultipleCalleeChains
2712 ?
" (found multiple possible chains)"
2715 if (FoundMultipleCalleeChains)
2716 FoundProfiledCalleeNonUniquelyCount++;
2723bool IndexCallsiteContextGraph::sameCallee(IndexCall &Call1, IndexCall &Call2) {
2725 dyn_cast_if_present<CallsiteInfo *>(Call1.getBase())->Callee;
2727 dyn_cast_if_present<CallsiteInfo *>(Call2.getBase())->Callee;
2728 return Callee1 == Callee2;
2731template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2732void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::dump()
2738template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2739void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::print(
2741 OS <<
"Node " <<
this <<
"\n";
2745 OS <<
" (recursive)";
2747 if (!MatchingCalls.
empty()) {
2748 OS <<
"\tMatchingCalls:\n";
2749 for (
auto &MatchingCall : MatchingCalls) {
2751 MatchingCall.print(
OS);
2756 OS <<
"\tContextIds:";
2758 auto ContextIds = getContextIds();
2759 std::vector<uint32_t> SortedIds(ContextIds.begin(), ContextIds.end());
2760 std::sort(SortedIds.begin(), SortedIds.end());
2761 for (
auto Id : SortedIds)
2764 OS <<
"\tCalleeEdges:\n";
2765 for (
auto &Edge : CalleeEdges)
2766 OS <<
"\t\t" << *Edge <<
"\n";
2767 OS <<
"\tCallerEdges:\n";
2768 for (
auto &Edge : CallerEdges)
2769 OS <<
"\t\t" << *Edge <<
"\n";
2770 if (!Clones.empty()) {
2773 for (
auto *Clone : Clones)
2776 }
else if (CloneOf) {
2777 OS <<
"\tClone of " << CloneOf <<
"\n";
2781template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2782void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge::dump()
2788template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2789void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge::print(
2793 OS <<
" ContextIds:";
2794 std::vector<uint32_t> SortedIds(ContextIds.begin(), ContextIds.end());
2795 std::sort(SortedIds.begin(), SortedIds.end());
2796 for (
auto Id : SortedIds)
2800template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2801void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::dump()
const {
2805template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2806void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::print(
2808 OS <<
"Callsite Context Graph:\n";
2809 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
2810 for (
const auto Node : nodes<GraphType>(
this)) {
2811 if (
Node->isRemoved())
2818template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2819void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::printTotalSizes(
2821 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
2822 for (
const auto Node : nodes<GraphType>(
this)) {
2823 if (
Node->isRemoved())
2825 if (!
Node->IsAllocation)
2828 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
2829 std::sort(SortedIds.begin(), SortedIds.end());
2830 for (
auto Id : SortedIds) {
2831 auto TypeI = ContextIdToAllocationType.find(Id);
2832 assert(TypeI != ContextIdToAllocationType.end());
2833 auto CSI = ContextIdToContextSizeInfos.find(Id);
2834 if (CSI != ContextIdToContextSizeInfos.end()) {
2835 for (
auto &Info : CSI->second) {
2836 OS <<
"MemProf hinting: "
2838 <<
" full allocation context " <<
Info.FullStackId
2839 <<
" with total size " <<
Info.TotalSize <<
" is "
2847template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2848void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::check()
const {
2849 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
2850 for (
const auto Node : nodes<GraphType>(
this)) {
2851 checkNode<DerivedCCG, FuncTy, CallTy>(
Node,
false);
2852 for (
auto &Edge :
Node->CallerEdges)
2853 checkEdge<DerivedCCG, FuncTy, CallTy>(Edge);
2857template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2859 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
2860 using NodeRef =
const ContextNode<DerivedCCG, FuncTy, CallTy> *;
2862 using NodePtrTy = std::unique_ptr<ContextNode<DerivedCCG, FuncTy, CallTy>>;
2878 return G->NodeOwner.begin()->get();
2881 using EdgePtrTy = std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>>;
2882 static const ContextNode<DerivedCCG, FuncTy, CallTy> *
2890 decltype(&GetCallee)>;
2901template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2906 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
2912 std::string LabelString =
2913 (
Twine(
"OrigId: ") + (Node->IsAllocation ?
"Alloc" :
"") +
2914 Twine(Node->OrigStackOrAllocId))
2916 LabelString +=
"\n";
2917 if (Node->hasCall()) {
2918 auto Func =
G->NodeToCallingFunc.find(Node);
2919 assert(Func !=
G->NodeToCallingFunc.end());
2921 G->getLabel(Func->second, Node->Call.call(), Node->Call.cloneNo());
2923 LabelString +=
"null call";
2924 if (Node->Recursive)
2925 LabelString +=
" (recursive)";
2927 LabelString +=
" (external)";
2933 std::string AttributeString = (
Twine(
"tooltip=\"") + getNodeId(Node) +
" " +
2934 getContextIds(Node->getContextIds()) +
"\"")
2937 (
Twine(
",fillcolor=\"") + getColor(Node->AllocTypes) +
"\"").str();
2938 AttributeString +=
",style=\"filled\"";
2939 if (Node->CloneOf) {
2940 AttributeString +=
",color=\"blue\"";
2941 AttributeString +=
",style=\"filled,bold,dashed\"";
2943 AttributeString +=
",style=\"filled\"";
2944 return AttributeString;
2949 auto &Edge = *(ChildIter.getCurrent());
2950 return (
Twine(
"tooltip=\"") + getContextIds(Edge->ContextIds) +
"\"" +
2951 Twine(
",fillcolor=\"") + getColor(Edge->AllocTypes) +
"\"")
2958 return Node->isRemoved();
2963 std::string IdString =
"ContextIds:";
2964 if (ContextIds.
size() < 100) {
2965 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
2966 std::sort(SortedIds.begin(), SortedIds.end());
2967 for (
auto Id : SortedIds)
2968 IdString += (
" " +
Twine(Id)).str();
2970 IdString += (
" (" +
Twine(ContextIds.
size()) +
" ids)").str();
2975 static std::string getColor(
uint8_t AllocTypes) {
2984 return "mediumorchid1";
2988 static std::string getNodeId(NodeRef
Node) {
2989 std::stringstream SStream;
2990 SStream << std::hex <<
"N0x" << (
unsigned long long)
Node;
2991 std::string
Result = SStream.str();
2996template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2997void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::exportToDot(
2998 std::string Label)
const {
3003template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3004typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
3005CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::moveEdgeToNewCalleeClone(
3006 const std::shared_ptr<ContextEdge> &Edge, EdgeIter *CallerEdgeI,
3008 ContextNode *
Node = Edge->Callee;
3010 ContextNode *Clone =
3011 createNewNode(
Node->IsAllocation, NodeToCallingFunc[
Node],
Node->Call);
3012 Node->addClone(Clone);
3013 Clone->MatchingCalls =
Node->MatchingCalls;
3014 moveEdgeToExistingCalleeClone(Edge, Clone, CallerEdgeI,
true,
3019template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3020void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
3021 moveEdgeToExistingCalleeClone(
const std::shared_ptr<ContextEdge> &Edge,
3022 ContextNode *NewCallee, EdgeIter *CallerEdgeI,
3027 assert(NewCallee->getOrigNode() == Edge->Callee->getOrigNode());
3029 ContextNode *OldCallee = Edge->Callee;
3033 auto ExistingEdgeToNewCallee = NewCallee->findEdgeFromCaller(Edge->Caller);
3037 if (ContextIdsToMove.
empty())
3038 ContextIdsToMove = Edge->getContextIds();
3042 if (Edge->getContextIds().size() == ContextIdsToMove.
size()) {
3045 NewCallee->AllocTypes |= Edge->AllocTypes;
3047 if (ExistingEdgeToNewCallee) {
3050 ExistingEdgeToNewCallee->getContextIds().
insert(ContextIdsToMove.
begin(),
3051 ContextIdsToMove.
end());
3052 ExistingEdgeToNewCallee->AllocTypes |= Edge->AllocTypes;
3053 assert(Edge->ContextIds == ContextIdsToMove);
3054 removeEdgeFromGraph(Edge.get(), CallerEdgeI,
false);
3057 Edge->Callee = NewCallee;
3058 NewCallee->CallerEdges.push_back(Edge);
3061 *CallerEdgeI = OldCallee->CallerEdges.erase(*CallerEdgeI);
3063 OldCallee->eraseCallerEdge(Edge.get());
3072 auto CallerEdgeAllocType = computeAllocType(ContextIdsToMove);
3073 if (ExistingEdgeToNewCallee) {
3076 ExistingEdgeToNewCallee->getContextIds().insert(ContextIdsToMove.
begin(),
3077 ContextIdsToMove.
end());
3078 ExistingEdgeToNewCallee->AllocTypes |= CallerEdgeAllocType;
3081 auto NewEdge = std::make_shared<ContextEdge>(
3082 NewCallee, Edge->Caller, CallerEdgeAllocType, ContextIdsToMove);
3083 Edge->Caller->CalleeEdges.push_back(NewEdge);
3084 NewCallee->CallerEdges.push_back(NewEdge);
3088 NewCallee->AllocTypes |= CallerEdgeAllocType;
3090 Edge->AllocTypes = computeAllocType(Edge->ContextIds);
3095 for (
auto &OldCalleeEdge : OldCallee->CalleeEdges) {
3100 set_subtract(OldCalleeEdge->getContextIds(), EdgeContextIdsToMove);
3101 OldCalleeEdge->AllocTypes =
3102 computeAllocType(OldCalleeEdge->getContextIds());
3109 if (
auto *NewCalleeEdge =
3110 NewCallee->findEdgeFromCallee(OldCalleeEdge->Callee)) {
3111 NewCalleeEdge->getContextIds().insert(EdgeContextIdsToMove.
begin(),
3112 EdgeContextIdsToMove.
end());
3113 NewCalleeEdge->AllocTypes |= computeAllocType(EdgeContextIdsToMove);
3117 auto NewEdge = std::make_shared<ContextEdge>(
3118 OldCalleeEdge->Callee, NewCallee,
3119 computeAllocType(EdgeContextIdsToMove), EdgeContextIdsToMove);
3120 NewCallee->CalleeEdges.push_back(NewEdge);
3121 NewEdge->Callee->CallerEdges.push_back(NewEdge);
3125 OldCallee->AllocTypes = OldCallee->computeAllocType();
3128 OldCallee->emptyContextIds());
3130 checkNode<DerivedCCG, FuncTy, CallTy>(OldCallee,
false);
3131 checkNode<DerivedCCG, FuncTy, CallTy>(NewCallee,
false);
3132 for (
const auto &OldCalleeEdge : OldCallee->CalleeEdges)
3133 checkNode<DerivedCCG, FuncTy, CallTy>(OldCalleeEdge->Callee,
3135 for (
const auto &NewCalleeEdge : NewCallee->CalleeEdges)
3136 checkNode<DerivedCCG, FuncTy, CallTy>(NewCalleeEdge->Callee,
3141template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3142void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
3143 moveCalleeEdgeToNewCaller(EdgeIter &CalleeEdgeI, ContextNode *NewCaller) {
3144 auto Edge = *CalleeEdgeI;
3146 ContextNode *OldCaller = Edge->Caller;
3150 auto ExistingEdgeToNewCaller = NewCaller->findEdgeFromCallee(Edge->Callee);
3152 CalleeEdgeI = OldCaller->CalleeEdges.erase(CalleeEdgeI);
3153 if (ExistingEdgeToNewCaller) {
3156 ExistingEdgeToNewCaller->getContextIds().insert(
3157 Edge->getContextIds().begin(), Edge->getContextIds().end());
3158 ExistingEdgeToNewCaller->AllocTypes |= Edge->AllocTypes;
3159 Edge->ContextIds.clear();
3161 Edge->Callee->eraseCallerEdge(Edge.get());
3164 Edge->Caller = NewCaller;
3165 NewCaller->CalleeEdges.push_back(Edge);
3170 NewCaller->AllocTypes |= Edge->AllocTypes;
3177 bool IsNewNode = NewCaller->CallerEdges.empty();
3179 for (
auto &OldCallerEdge : OldCaller->CallerEdges) {
3184 set_subtract(OldCallerEdge->getContextIds(), EdgeContextIdsToMove);
3185 OldCallerEdge->AllocTypes =
3186 computeAllocType(OldCallerEdge->getContextIds());
3191 auto *ExistingCallerEdge =
3192 NewCaller->findEdgeFromCaller(OldCallerEdge->Caller);
3193 assert(IsNewNode || ExistingCallerEdge);
3194 if (ExistingCallerEdge) {
3195 ExistingCallerEdge->getContextIds().insert(EdgeContextIdsToMove.
begin(),
3196 EdgeContextIdsToMove.
end());
3197 ExistingCallerEdge->AllocTypes |= computeAllocType(EdgeContextIdsToMove);
3200 auto NewEdge = std::make_shared<ContextEdge>(
3201 NewCaller, OldCallerEdge->Caller,
3202 computeAllocType(EdgeContextIdsToMove), EdgeContextIdsToMove);
3203 NewCaller->CallerEdges.push_back(NewEdge);
3204 NewEdge->Caller->CalleeEdges.push_back(NewEdge);
3208 OldCaller->AllocTypes = OldCaller->computeAllocType();
3211 OldCaller->emptyContextIds());
3213 checkNode<DerivedCCG, FuncTy, CallTy>(OldCaller,
false);
3214 checkNode<DerivedCCG, FuncTy, CallTy>(NewCaller,
false);
3215 for (
const auto &OldCallerEdge : OldCaller->CallerEdges)
3216 checkNode<DerivedCCG, FuncTy, CallTy>(OldCallerEdge->Caller,
3218 for (
const auto &NewCallerEdge : NewCaller->CallerEdges)
3219 checkNode<DerivedCCG, FuncTy, CallTy>(NewCallerEdge->Caller,
3224template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3225void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
3226 recursivelyRemoveNoneTypeCalleeEdges(
3232 removeNoneTypeCalleeEdges(
Node);
3234 for (
auto *Clone :
Node->Clones)
3235 recursivelyRemoveNoneTypeCalleeEdges(Clone, Visited);
3239 auto CallerEdges =
Node->CallerEdges;
3240 for (
auto &Edge : CallerEdges) {
3242 if (Edge->isRemoved()) {
3246 recursivelyRemoveNoneTypeCalleeEdges(Edge->Caller, Visited);
3250template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3251void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones() {
3253 for (
auto &Entry : AllocationCallToContextNodeMap) {
3255 identifyClones(
Entry.second, Visited,
Entry.second->getContextIds());
3258 for (
auto &Entry : AllocationCallToContextNodeMap)
3259 recursivelyRemoveNoneTypeCalleeEdges(
Entry.second, Visited);
3272template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3273void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones(
3277 checkNode<DerivedCCG, FuncTy, CallTy>(
Node,
false);
3285 if (!
Node->hasCall())
3300 auto CallerEdges =
Node->CallerEdges;
3301 for (
auto &Edge : CallerEdges) {
3303 if (Edge->isRemoved()) {
3308 if (!Visited.
count(Edge->Caller) && !Edge->Caller->CloneOf) {
3309 identifyClones(Edge->Caller, Visited, AllocContextIds);
3332 const unsigned AllocTypeCloningPriority[] = { 3, 4,
3335 std::stable_sort(
Node->CallerEdges.begin(),
Node->CallerEdges.end(),
3336 [&](
const std::shared_ptr<ContextEdge> &
A,
3337 const std::shared_ptr<ContextEdge> &
B) {
3340 if (A->ContextIds.empty())
3346 if (B->ContextIds.empty())
3349 if (A->AllocTypes == B->AllocTypes)
3352 return *A->ContextIds.begin() < *B->ContextIds.begin();
3353 return AllocTypeCloningPriority[A->AllocTypes] <
3354 AllocTypeCloningPriority[B->AllocTypes];
3364 for (
auto EI =
Node->CallerEdges.begin(); EI !=
Node->CallerEdges.end();) {
3365 auto CallerEdge = *EI;
3374 if (!CallerEdge->Caller->hasCall()) {
3381 auto CallerEdgeContextsForAlloc =
3383 if (CallerEdgeContextsForAlloc.empty()) {
3387 auto CallerAllocTypeForAlloc = computeAllocType(CallerEdgeContextsForAlloc);
3391 std::vector<uint8_t> CalleeEdgeAllocTypesForCallerEdge;
3392 CalleeEdgeAllocTypesForCallerEdge.reserve(
Node->CalleeEdges.size());
3393 for (
auto &CalleeEdge :
Node->CalleeEdges)
3394 CalleeEdgeAllocTypesForCallerEdge.push_back(intersectAllocTypes(
3395 CalleeEdge->getContextIds(), CallerEdgeContextsForAlloc));
3410 if (allocTypeToUse(CallerAllocTypeForAlloc) ==
3411 allocTypeToUse(
Node->AllocTypes) &&
3412 allocTypesMatch<DerivedCCG, FuncTy, CallTy>(
3413 CalleeEdgeAllocTypesForCallerEdge,
Node->CalleeEdges)) {
3420 ContextNode *Clone =
nullptr;
3421 for (
auto *CurClone :
Node->Clones) {
3422 if (allocTypeToUse(CurClone->AllocTypes) !=
3423 allocTypeToUse(CallerAllocTypeForAlloc))
3430 assert(!BothSingleAlloc ||
3431 CurClone->AllocTypes == CallerAllocTypeForAlloc);
3437 if (BothSingleAlloc || allocTypesMatchClone<DerivedCCG, FuncTy, CallTy>(
3438 CalleeEdgeAllocTypesForCallerEdge, CurClone)) {
3446 moveEdgeToExistingCalleeClone(CallerEdge, Clone, &EI,
false,
3447 CallerEdgeContextsForAlloc);
3450 moveEdgeToNewCalleeClone(CallerEdge, &EI, CallerEdgeContextsForAlloc);
3465 checkNode<DerivedCCG, FuncTy, CallTy>(
Node,
false);
3468void ModuleCallsiteContextGraph::updateAllocationCall(
3472 "memprof", AllocTypeString);
3473 cast<CallBase>(
Call.call())->addFnAttr(
A);
3474 OREGetter(
Call.call()->getFunction())
3476 <<
ore::NV(
"AllocationCall",
Call.call()) <<
" in clone "
3478 <<
" marked with memprof allocation attribute "
3479 <<
ore::NV(
"Attribute", AllocTypeString));
3482void IndexCallsiteContextGraph::updateAllocationCall(
CallInfo &Call,
3486 assert(AI->Versions.size() >
Call.cloneNo());
3490void ModuleCallsiteContextGraph::updateCall(
CallInfo &CallerCall,
3491 FuncInfo CalleeFunc) {
3492 if (CalleeFunc.cloneNo() > 0)
3493 cast<CallBase>(CallerCall.call())->setCalledFunction(CalleeFunc.func());
3494 OREGetter(CallerCall.call()->getFunction())
3496 <<
ore::NV(
"Call", CallerCall.call()) <<
" in clone "
3497 <<
ore::NV(
"Caller", CallerCall.call()->getFunction())
3498 <<
" assigned to call function clone "
3499 <<
ore::NV(
"Callee", CalleeFunc.func()));
3502void IndexCallsiteContextGraph::updateCall(
CallInfo &CallerCall,
3503 FuncInfo CalleeFunc) {
3504 auto *CI = CallerCall.call().dyn_cast<
CallsiteInfo *>();
3506 "Caller cannot be an allocation which should not have profiled calls");
3507 assert(CI->Clones.size() > CallerCall.cloneNo());
3508 CI->Clones[CallerCall.cloneNo()] = CalleeFunc.cloneNo();
3511CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
3513ModuleCallsiteContextGraph::cloneFunctionForCallsite(
3514 FuncInfo &Func,
CallInfo &Call, std::map<CallInfo, CallInfo> &CallMap,
3515 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
3521 NewFunc->setName(
Name);
3522 for (
auto &Inst : CallsWithMetadataInFunc) {
3524 assert(Inst.cloneNo() == 0);
3525 CallMap[Inst] = {cast<Instruction>(VMap[Inst.call()]), CloneNo};
3527 OREGetter(
Func.func())
3529 <<
"created clone " <<
ore::NV(
"NewFunction", NewFunc));
3530 return {NewFunc, CloneNo};
3534 IndexCall>::FuncInfo
3535IndexCallsiteContextGraph::cloneFunctionForCallsite(
3536 FuncInfo &Func,
CallInfo &Call, std::map<CallInfo, CallInfo> &CallMap,
3537 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
3552 for (
auto &Inst : CallsWithMetadataInFunc) {
3554 assert(Inst.cloneNo() == 0);
3555 if (
auto *AI = Inst.call().dyn_cast<
AllocInfo *>()) {
3556 assert(AI->Versions.size() == CloneNo);
3559 AI->Versions.push_back(0);
3562 assert(CI && CI->Clones.size() == CloneNo);
3565 CI->Clones.push_back(0);
3567 CallMap[Inst] = {Inst.call(), CloneNo};
3569 return {
Func.func(), CloneNo};
3603template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3604bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::assignFunctions() {
3605 bool Changed =
false;
3613 auto RecordCalleeFuncOfCallsite = [&](ContextNode *
Caller,
3614 const FuncInfo &CalleeFunc) {
3616 CallsiteToCalleeFuncCloneMap[
Caller] = CalleeFunc;
3621 for (
auto &[Func, CallsWithMetadata] : FuncToCallsWithMetadata) {
3622 FuncInfo OrigFunc(Func);
3626 std::map<FuncInfo, std::map<CallInfo, CallInfo>> FuncClonesToCallMap;
3627 for (
auto &Call : CallsWithMetadata) {
3628 ContextNode *
Node = getNodeForInst(Call);
3635 "Not having a call should have prevented cloning");
3639 std::map<FuncInfo, ContextNode *> FuncCloneToCurNodeCloneMap;
3643 auto AssignCallsiteCloneToFuncClone = [&](
const FuncInfo &FuncClone,
3645 ContextNode *CallsiteClone,
3648 FuncCloneToCurNodeCloneMap[FuncClone] = CallsiteClone;
3650 assert(FuncClonesToCallMap.count(FuncClone));
3651 std::map<CallInfo, CallInfo> &CallMap = FuncClonesToCallMap[FuncClone];
3653 if (CallMap.count(Call))
3654 CallClone = CallMap[
Call];
3655 CallsiteClone->setCall(CallClone);
3657 for (
auto &MatchingCall :
Node->MatchingCalls) {
3659 if (CallMap.count(MatchingCall))
3660 CallClone = CallMap[MatchingCall];
3662 MatchingCall = CallClone;
3669 std::deque<ContextNode *> ClonesWorklist;
3671 if (!
Node->emptyContextIds())
3672 ClonesWorklist.push_back(
Node);
3673 ClonesWorklist.insert(ClonesWorklist.end(),
Node->Clones.begin(),
3674 Node->Clones.end());
3679 unsigned NodeCloneCount = 0;
3680 while (!ClonesWorklist.empty()) {
3681 ContextNode *Clone = ClonesWorklist.front();
3682 ClonesWorklist.pop_front();
3685 checkNode<DerivedCCG, FuncTy, CallTy>(Clone);
3691 if (FuncClonesToCallMap.size() < NodeCloneCount) {
3693 if (NodeCloneCount == 1) {
3698 Clone->CallerEdges, [&](
const std::shared_ptr<ContextEdge> &E) {
3699 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
3703 FuncClonesToCallMap[OrigFunc] = {};
3704 AssignCallsiteCloneToFuncClone(
3705 OrigFunc, Call, Clone,
3706 AllocationCallToContextNodeMap.count(Call));
3707 for (
auto &CE : Clone->CallerEdges) {
3709 if (!
CE->Caller->hasCall())
3711 RecordCalleeFuncOfCallsite(
CE->Caller, OrigFunc);
3721 FuncInfo PreviousAssignedFuncClone;
3723 Clone->CallerEdges, [&](
const std::shared_ptr<ContextEdge> &E) {
3724 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
3726 bool CallerAssignedToCloneOfFunc =
false;
3727 if (EI != Clone->CallerEdges.end()) {
3728 const std::shared_ptr<ContextEdge> &Edge = *EI;
3729 PreviousAssignedFuncClone =
3730 CallsiteToCalleeFuncCloneMap[Edge->Caller];
3731 CallerAssignedToCloneOfFunc =
true;
3736 std::map<CallInfo, CallInfo> NewCallMap;
3737 unsigned CloneNo = FuncClonesToCallMap.size();
3738 assert(CloneNo > 0 &&
"Clone 0 is the original function, which "
3739 "should already exist in the map");
3740 FuncInfo NewFuncClone = cloneFunctionForCallsite(
3741 OrigFunc, Call, NewCallMap, CallsWithMetadata, CloneNo);
3742 FuncClonesToCallMap.emplace(NewFuncClone, std::move(NewCallMap));
3743 FunctionClonesAnalysis++;
3749 if (!CallerAssignedToCloneOfFunc) {
3750 AssignCallsiteCloneToFuncClone(
3751 NewFuncClone, Call, Clone,
3752 AllocationCallToContextNodeMap.count(Call));
3753 for (
auto &CE : Clone->CallerEdges) {
3755 if (!
CE->Caller->hasCall())
3757 RecordCalleeFuncOfCallsite(
CE->Caller, NewFuncClone);
3769 auto CallerEdges = Clone->CallerEdges;
3770 for (
auto CE : CallerEdges) {
3772 if (
CE->isRemoved()) {
3778 if (!
CE->Caller->hasCall())
3781 if (!CallsiteToCalleeFuncCloneMap.
count(
CE->Caller) ||
3785 CallsiteToCalleeFuncCloneMap[
CE->Caller] !=
3786 PreviousAssignedFuncClone)
3789 RecordCalleeFuncOfCallsite(
CE->Caller, NewFuncClone);
3802 auto CalleeEdges =
CE->Caller->CalleeEdges;
3803 for (
auto CalleeEdge : CalleeEdges) {
3806 if (CalleeEdge->isRemoved()) {
3811 ContextNode *
Callee = CalleeEdge->Callee;
3815 if (Callee == Clone || !
Callee->hasCall())
3817 ContextNode *NewClone = moveEdgeToNewCalleeClone(CalleeEdge);
3818 removeNoneTypeCalleeEdges(NewClone);
3821 removeNoneTypeCalleeEdges(Callee);
3826 if (CallsiteToCalleeFuncCloneMap.
count(Callee))
3827 RecordCalleeFuncOfCallsite(
3828 NewClone, CallsiteToCalleeFuncCloneMap[Callee]);
3837 OrigCall.setCloneNo(0);
3838 std::map<CallInfo, CallInfo> &CallMap =
3839 FuncClonesToCallMap[NewFuncClone];
3840 assert(CallMap.count(OrigCall));
3841 CallInfo NewCall(CallMap[OrigCall]);
3843 NewClone->setCall(NewCall);
3845 for (
auto &MatchingCall : NewClone->MatchingCalls) {
3846 CallInfo OrigMatchingCall(MatchingCall);
3847 OrigMatchingCall.setCloneNo(0);
3848 assert(CallMap.count(OrigMatchingCall));
3849 CallInfo NewCall(CallMap[OrigMatchingCall]);
3852 MatchingCall = NewCall;
3875 std::map<FuncInfo, ContextNode *> FuncCloneToNewCallsiteCloneMap;
3876 FuncInfo FuncCloneAssignedToCurCallsiteClone;
3879 for (
auto EI = Clone->CallerEdges.begin();
3880 EI != Clone->CallerEdges.end();) {
3883 if (!Edge->Caller->hasCall()) {
3889 if (CallsiteToCalleeFuncCloneMap.
count(Edge->Caller)) {
3890 FuncInfo FuncCloneCalledByCaller =
3891 CallsiteToCalleeFuncCloneMap[Edge->Caller];
3901 if ((FuncCloneToCurNodeCloneMap.count(FuncCloneCalledByCaller) &&
3902 FuncCloneToCurNodeCloneMap[FuncCloneCalledByCaller] !=
3910 (FuncCloneAssignedToCurCallsiteClone &&
3911 FuncCloneAssignedToCurCallsiteClone !=
3912 FuncCloneCalledByCaller)) {
3927 if (FuncCloneToNewCallsiteCloneMap.count(
3928 FuncCloneCalledByCaller)) {
3929 ContextNode *NewClone =
3930 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller];
3931 moveEdgeToExistingCalleeClone(Edge, NewClone, &EI);
3933 removeNoneTypeCalleeEdges(NewClone);
3936 ContextNode *NewClone = moveEdgeToNewCalleeClone(Edge, &EI);
3937 removeNoneTypeCalleeEdges(NewClone);
3938 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller] =
3941 ClonesWorklist.push_back(NewClone);
3942 assert(EI == Clone->CallerEdges.end() ||
3948 removeNoneTypeCalleeEdges(Clone);
3957 if (!FuncCloneAssignedToCurCallsiteClone) {
3958 FuncCloneAssignedToCurCallsiteClone = FuncCloneCalledByCaller;
3960 AssignCallsiteCloneToFuncClone(
3961 FuncCloneCalledByCaller, Call, Clone,
3962 AllocationCallToContextNodeMap.count(Call));
3966 assert(FuncCloneAssignedToCurCallsiteClone ==
3967 FuncCloneCalledByCaller);
3976 if (!FuncCloneAssignedToCurCallsiteClone) {
3981 for (
auto &CF : FuncClonesToCallMap) {
3982 if (!FuncCloneToCurNodeCloneMap.count(CF.first)) {
3983 FuncCloneAssignedToCurCallsiteClone = CF.first;
3987 assert(FuncCloneAssignedToCurCallsiteClone);
3989 AssignCallsiteCloneToFuncClone(
3990 FuncCloneAssignedToCurCallsiteClone, Call, Clone,
3991 AllocationCallToContextNodeMap.count(Call));
3993 assert(FuncCloneToCurNodeCloneMap
3994 [FuncCloneAssignedToCurCallsiteClone] == Clone);
3996 RecordCalleeFuncOfCallsite(Edge->Caller,
3997 FuncCloneAssignedToCurCallsiteClone);
4004 checkNode<DerivedCCG, FuncTy, CallTy>(
Node);
4005 for (
const auto &PE :
Node->CalleeEdges)
4006 checkNode<DerivedCCG, FuncTy, CallTy>(PE->Callee);
4007 for (
const auto &CE :
Node->CallerEdges)
4008 checkNode<DerivedCCG, FuncTy, CallTy>(
CE->Caller);
4009 for (
auto *Clone :
Node->Clones) {
4010 checkNode<DerivedCCG, FuncTy, CallTy>(Clone);
4011 for (
const auto &PE : Clone->CalleeEdges)
4012 checkNode<DerivedCCG, FuncTy, CallTy>(PE->Callee);
4013 for (
const auto &CE : Clone->CallerEdges)
4014 checkNode<DerivedCCG, FuncTy, CallTy>(
CE->Caller);
4020 auto UpdateCalls = [&](ContextNode *
Node,
4022 auto &&UpdateCalls) {
4027 for (
auto *Clone :
Node->Clones)
4028 UpdateCalls(Clone, Visited, UpdateCalls);
4030 for (
auto &Edge :
Node->CallerEdges)
4031 UpdateCalls(Edge->Caller, Visited, UpdateCalls);
4035 if (!
Node->hasCall() ||
Node->emptyContextIds())
4038 if (
Node->IsAllocation) {
4039 updateAllocationCall(
Node->Call, allocTypeToUse(
Node->AllocTypes));
4044 if (!CallsiteToCalleeFuncCloneMap.
count(
Node))
4047 auto CalleeFunc = CallsiteToCalleeFuncCloneMap[
Node];
4048 updateCall(
Node->Call, CalleeFunc);
4050 for (
auto &Call :
Node->MatchingCalls)
4051 updateCall(Call, CalleeFunc);
4060 for (
auto &Entry : AllocationCallToContextNodeMap)
4061 UpdateCalls(
Entry.second, Visited, UpdateCalls);
4075 FunctionsClonedThinBackend++;
4076 for (
unsigned I = 1;
I < NumClones;
I++) {
4077 VMaps.
emplace_back(std::make_unique<ValueToValueMapTy>());
4079 FunctionClonesThinBackend++;
4082 for (
auto &BB : *NewF) {
4083 for (
auto &Inst : BB) {
4084 Inst.setMetadata(LLVMContext::MD_memprof,
nullptr);
4085 Inst.setMetadata(LLVMContext::MD_callsite,
nullptr);
4089 auto *PrevF = M.getFunction(
Name);
4093 assert(PrevF->isDeclaration());
4094 NewF->takeName(PrevF);
4095 PrevF->replaceAllUsesWith(NewF);
4096 PrevF->eraseFromParent();
4098 NewF->setName(
Name);
4100 <<
"created clone " <<
ore::NV(
"NewFunction", NewF));
4103 if (!FuncToAliasMap.count(&
F))
4105 for (
auto *
A : FuncToAliasMap[&
F]) {
4107 auto *PrevA = M.getNamedAlias(
Name);
4109 A->getType()->getPointerAddressSpace(),
4110 A->getLinkage(),
Name, NewF);
4111 NewA->copyAttributesFrom(
A);
4115 assert(PrevA->isDeclaration());
4116 NewA->takeName(PrevA);
4117 PrevA->replaceAllUsesWith(NewA);
4118 PrevA->eraseFromParent();
4160bool MemProfContextDisambiguation::initializeIndirectCallPromotionInfo(
4162 ICallAnalysis = std::make_unique<ICallPromotionAnalysis>();
4163 Symtab = std::make_unique<InstrProfSymtab>();
4174 if (
Error E = Symtab->create(M,
true,
false)) {
4175 std::string SymtabFailure =
toString(std::move(
E));
4176 M.getContext().emitError(
"Failed to create symtab: " + SymtabFailure);
4182bool MemProfContextDisambiguation::applyImport(
Module &M) {
4184 bool Changed =
false;
4189 std::map<const Function *, SmallPtrSet<const GlobalAlias *, 1>>
4191 for (
auto &
A :
M.aliases()) {
4192 auto *Aliasee =
A.getAliaseeObject();
4193 if (
auto *
F = dyn_cast<Function>(Aliasee))
4194 FuncToAliasMap[
F].insert(&
A);
4197 if (!initializeIndirectCallPromotionInfo(M))
4207 bool ClonesCreated =
false;
4208 unsigned NumClonesCreated = 0;
4209 auto CloneFuncIfNeeded = [&](
unsigned NumClones) {
4219 if (ClonesCreated) {
4220 assert(NumClonesCreated == NumClones);
4227 ClonesCreated =
true;
4228 NumClonesCreated = NumClones;
4234 CloneFuncIfNeeded(
StackNode.Clones.size());
4241 auto CalleeOrigName = CalledFunction->getName();
4242 for (
unsigned J = 0; J <
StackNode.Clones.size(); J++) {
4247 auto NewF =
M.getOrInsertFunction(
4249 CalledFunction->getFunctionType());
4255 CBClone = cast<CallBase>((*VMaps[J - 1])[CB]);
4258 <<
ore::NV(
"Call", CBClone) <<
" in clone "
4260 <<
" assigned to call function clone "
4261 <<
ore::NV(
"Callee", NewF.getCallee()));
4279 auto SrcModuleMD =
F.getMetadata(
"thinlto_src_module");
4281 "enable-import-metadata is needed to emit thinlto_src_module");
4283 dyn_cast<MDString>(SrcModuleMD->getOperand(0))->getString();
4285 if (GVS->modulePath() == SrcModule) {
4286 GVSummary = GVS.get();
4290 assert(GVSummary && GVSummary->modulePath() == SrcModule);
4295 if (isa<AliasSummary>(GVSummary))
4298 auto *
FS = cast<FunctionSummary>(GVSummary->getBaseObject());
4300 if (
FS->allocs().empty() &&
FS->callsites().empty())
4303 auto SI =
FS->callsites().begin();
4304 auto AI =
FS->allocs().begin();
4312 for (
auto CallsiteIt =
FS->callsites().rbegin();
4313 CallsiteIt !=
FS->callsites().rend(); CallsiteIt++) {
4314 auto &Callsite = *CallsiteIt;
4318 if (!Callsite.StackIdIndices.empty())
4320 MapTailCallCalleeVIToCallsite.
insert({Callsite.Callee, Callsite});
4329 for (
auto &BB :
F) {
4330 for (
auto &
I : BB) {
4331 auto *CB = dyn_cast<CallBase>(&
I);
4336 auto *CalledValue = CB->getCalledOperand();
4337 auto *CalledFunction = CB->getCalledFunction();
4338 if (CalledValue && !CalledFunction) {
4339 CalledValue = CalledValue->stripPointerCasts();
4341 CalledFunction = dyn_cast<Function>(CalledValue);
4345 if (
auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
4346 assert(!CalledFunction &&
4347 "Expected null called function in callsite for alias");
4348 CalledFunction = dyn_cast<Function>(GA->getAliaseeObject());
4352 I.getMetadata(LLVMContext::MD_callsite));
4353 auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof);
4357 if (CB->getAttributes().hasFnAttr(
"memprof")) {
4359 CB->getAttributes().getFnAttr(
"memprof").getValueAsString() ==
"cold"
4360 ? AllocTypeColdThinBackend++
4361 : AllocTypeNotColdThinBackend++;
4362 OrigAllocsThinBackend++;
4363 AllocVersionsThinBackend++;
4364 if (!MaxAllocVersionsThinBackend)
4365 MaxAllocVersionsThinBackend = 1;
4372 auto &AllocNode = *(AI++);
4376 auto MIBIter = AllocNode.MIBs.begin();
4377 for (
auto &MDOp : MemProfMD->operands()) {
4378 assert(MIBIter != AllocNode.MIBs.end());
4380 MIBIter->StackIdIndices.begin();
4381 auto *MIBMD = cast<const MDNode>(MDOp);
4385 auto ContextIterBegin =
4389 (ContextIterBegin != StackContext.
end() &&
4390 *ContextIterBegin == 0)
4393 for (
auto ContextIter = ContextIterBegin;
4394 ContextIter != StackContext.
end(); ++ContextIter) {
4398 if (LastStackContextId == *ContextIter)
4400 LastStackContextId = *ContextIter;
4401 assert(StackIdIndexIter != MIBIter->StackIdIndices.end());
4410 CloneFuncIfNeeded(AllocNode.Versions.size());
4412 OrigAllocsThinBackend++;
4413 AllocVersionsThinBackend += AllocNode.Versions.size();
4414 if (MaxAllocVersionsThinBackend < AllocNode.Versions.size())
4415 MaxAllocVersionsThinBackend = AllocNode.Versions.size();
4422 if (AllocNode.Versions.size() == 1) {
4427 UnclonableAllocsThinBackend++;
4433 return Type == ((uint8_t)AllocationType::NotCold |
4434 (uint8_t)AllocationType::Cold);
4438 for (
unsigned J = 0; J < AllocNode.Versions.size(); J++) {
4444 : AllocTypeNotColdThinBackend++;
4456 CBClone = cast<CallBase>((*VMaps[J - 1])[CB]);
4459 <<
ore::NV(
"AllocationCall", CBClone) <<
" in clone "
4461 <<
" marked with memprof allocation attribute "
4462 <<
ore::NV(
"Attribute", AllocTypeString));
4464 }
else if (!CallsiteContext.empty()) {
4465 if (!CalledFunction) {
4468 auto *CI = dyn_cast<CallInst>(CB);
4469 assert(!CI || !CI->isInlineAsm());
4472 assert(CalledValue && !isa<Constant>(CalledValue));
4479 recordICPInfo(CB,
FS->callsites(), SI, ICallAnalysisInfo);
4485 CloneFuncIfNeeded(NumClones);
4490 assert(SI !=
FS->callsites().end());
4496 auto StackIdIndexIter =
StackNode.StackIdIndices.begin();
4497 for (
auto StackId : CallsiteContext) {
4505 CloneCallsite(
StackNode, CB, CalledFunction);
4507 }
else if (CB->isTailCall() && CalledFunction) {
4512 if (CalleeVI && MapTailCallCalleeVIToCallsite.
count(CalleeVI)) {
4513 auto Callsite = MapTailCallCalleeVIToCallsite.
find(CalleeVI);
4514 assert(Callsite != MapTailCallCalleeVIToCallsite.
end());
4515 CloneCallsite(Callsite->second, CB, CalledFunction);
4522 performICP(M,
FS->callsites(), VMaps, ICallAnalysisInfo, ORE);
4532 for (
auto &BB :
F) {
4533 for (
auto &
I : BB) {
4534 if (!isa<CallBase>(
I))
4536 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
4537 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
4545unsigned MemProfContextDisambiguation::recordICPInfo(
4552 auto CandidateProfileData =
4553 ICallAnalysis->getPromotionCandidatesForInstruction(CB, TotalCount,
4555 if (CandidateProfileData.empty())
4561 bool ICPNeeded =
false;
4562 unsigned NumClones = 0;
4563 size_t CallsiteInfoStartIndex = std::distance(AllCallsites.
begin(), SI);
4564 for (
const auto &Candidate : CandidateProfileData) {
4566 auto CalleeValueInfo =
4571 assert(!CalleeValueInfo ||
SI->Callee == CalleeValueInfo);
4578 [](
unsigned CloneNo) { return CloneNo != 0; });
4588 ICallAnalysisInfo.
push_back({CB, CandidateProfileData.vec(), NumCandidates,
4589 TotalCount, CallsiteInfoStartIndex});
4593void MemProfContextDisambiguation::performICP(
4595 ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps,
4604 for (
auto &
Info : ICallAnalysisInfo) {
4606 auto CallsiteIndex =
Info.CallsiteInfoStartIndex;
4607 auto TotalCount =
Info.TotalCount;
4608 unsigned NumPromoted = 0;
4609 unsigned NumClones = 0;
4611 for (
auto &Candidate :
Info.CandidateProfileData) {
4612 auto &
StackNode = AllCallsites[CallsiteIndex++];
4622 Function *TargetFunction = Symtab->getFunction(Candidate.Value);
4623 if (TargetFunction ==
nullptr ||
4632 <<
"Memprof cannot promote indirect call: target with md5sum "
4633 <<
ore::NV(
"target md5sum", Candidate.Value) <<
" not found";
4642 const char *Reason =
nullptr;
4646 <<
"Memprof cannot promote indirect call to "
4647 <<
ore::NV(
"TargetFunction", TargetFunction)
4648 <<
" with count of " <<
ore::NV(
"TotalCount", TotalCount)
4660 for (
unsigned J = 0; J < NumClones; J++) {
4663 CBClone = cast<CallBase>((*VMaps[J - 1])[CB]);
4669 TotalCount, isSamplePGO, &ORE);
4670 auto *TargetToUse = TargetFunction;
4675 cast<Function>(
M.getOrInsertFunction(
4683 <<
ore::NV(
"Call", CBClone) <<
" in clone "
4685 <<
" promoted and assigned to call function clone "
4686 <<
ore::NV(
"Callee", TargetToUse));
4690 TotalCount -= Candidate.Count;
4696 for (
unsigned J = 0; J < NumClones; J++) {
4699 CBClone = cast<CallBase>((*VMaps[J - 1])[CB]);
4701 CBClone->
setMetadata(LLVMContext::MD_prof,
nullptr);
4704 if (TotalCount != 0)
4707 TotalCount, IPVK_IndirectCallTarget,
Info.NumCandidates);
4712template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4713bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::process() {
4715 dbgs() <<
"CCG before cloning:\n";
4719 exportToDot(
"postbuild");
4732 dbgs() <<
"CCG after cloning:\n";
4736 exportToDot(
"cloned");
4738 bool Changed = assignFunctions();
4741 dbgs() <<
"CCG after assigning function clones:\n";
4745 exportToDot(
"clonefuncassign");
4748 printTotalSizes(
errs());
4753bool MemProfContextDisambiguation::processModule(
4760 return applyImport(M);
4773 ModuleCallsiteContextGraph CCG(M, OREGetter);
4774 return CCG.process();
4779 : ImportSummary(Summary), isSamplePGO(isSamplePGO) {
4780 if (ImportSummary) {
4790 auto ReadSummaryFile =
4792 if (!ReadSummaryFile) {
4799 if (!ImportSummaryForTestingOrErr) {
4805 ImportSummaryForTesting = std::move(*ImportSummaryForTestingOrErr);
4806 ImportSummary = ImportSummaryForTesting.get();
4815 if (!processModule(M, OREGetter))
4832 IndexCallsiteContextGraph CCG(
Index, isPrevailing);
static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Analysis containing CSE Info
#define LLVM_ATTRIBUTE_UNUSED
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
Module.h This file contains the declarations for the Module class.
This file implements a map that provides insertion order iteration.
static SmallVector< std::unique_ptr< ValueToValueMapTy >, 4 > createFunctionClones(Function &F, unsigned NumClones, Module &M, OptimizationRemarkEmitter &ORE, std::map< const Function *, SmallPtrSet< const GlobalAlias *, 1 > > &FuncToAliasMap)
static cl::opt< unsigned > TailCallSearchDepth("memprof-tail-call-search-depth", cl::init(5), cl::Hidden, cl::desc("Max depth to recursively search for missing " "frames through tail calls."))
static bool isMemProfClone(const Function &F)
static cl::opt< bool > ExportToDot("memprof-export-to-dot", cl::init(false), cl::Hidden, cl::desc("Export graph to dot files."))
static void checkEdge(const std::shared_ptr< ContextEdge< DerivedCCG, FuncTy, CallTy > > &Edge)
bool checkColdOrNotCold(uint8_t AllocType)
static ValueInfo findValueInfoForFunc(const Function &F, const Module &M, const ModuleSummaryIndex *ImportSummary)
static std::string getAllocTypeString(uint8_t AllocTypes)
cl::opt< bool > MemProfReportHintedSizes
static cl::opt< bool > VerifyCCG("memprof-verify-ccg", cl::init(false), cl::Hidden, cl::desc("Perform verification checks on CallingContextGraph."))
static void checkNode(const ContextNode< DerivedCCG, FuncTy, CallTy > *Node, bool CheckEdges=true)
static std::string getMemProfFuncName(Twine Base, unsigned CloneNo)
static cl::opt< std::string > MemProfImportSummary("memprof-import-summary", cl::desc("Import summary to use for testing the ThinLTO backend via opt"), cl::Hidden)
static const std::string MemProfCloneSuffix
static cl::opt< std::string > DotFilePathPrefix("memprof-dot-file-path-prefix", cl::init(""), cl::Hidden, cl::value_desc("filename"), cl::desc("Specify the path prefix of the MemProf dot files."))
static cl::opt< bool > VerifyNodes("memprof-verify-nodes", cl::init(false), cl::Hidden, cl::desc("Perform frequent verification checks on nodes."))
static cl::opt< bool > DumpCCG("memprof-dump-ccg", cl::init(false), cl::Hidden, cl::desc("Dump CallingContextGraph to stdout after each stage."))
cl::opt< bool > MemProfReportHintedSizes("memprof-report-hinted-sizes", cl::init(false), cl::Hidden, cl::desc("Report total allocation sizes of hinted allocations"))
This is the interface to build a ModuleSummaryIndex for a module.
ModuleSummaryIndex.h This file contains the declarations the classes that hold the module index and s...
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
FunctionAnalysisManager FAM
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines generic set operations that may be used on set's of different types,...
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
void print(OutputBuffer &OB) const
DomTreeNode::const_iterator end() const
Alias summary information.
ValueInfo getAliaseeVI() const
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool empty() const
empty - Check if the array is empty.
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array.
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
void addFnAttr(Attribute::AttrKind Kind)
Adds the attribute to the function.
void setCalledFunction(Function *Fn)
Sets the function called, including updating the function type.
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Implements a dense probed hash-table based set.
Lightweight error class with error context and mandatory checking.
Function summary information to aid decisions and implementation of importing.
FunctionType * getFunctionType() const
Returns the FunctionType for me.
static GlobalAlias * create(Type *Ty, unsigned AddressSpace, LinkageTypes Linkage, const Twine &Name, Constant *Aliasee, Module *Parent)
If a parent module is specified, the alias is automatically inserted into the end of the specified mo...
Function and variable summary information to aid decisions and implementation of importing.
static bool isLocalLinkage(LinkageTypes Linkage)
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
GUID getGUID() const
Return a 64-bit global unique ID constructed from global value name (i.e.
std::string getGlobalIdentifier() const
Return the modified name for this global value suitable to be used as the key for a global lookup (e....
@ InternalLinkage
Rename collisions when linking (static functions).
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
const Function * getFunction() const
Return the function this instruction belongs to.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
const MDOperand & getOperand(unsigned I) const
unsigned getNumOperands() const
Return number of MDNode operands.
This class implements a map that also provides access to all stored values in a deterministic order.
size_type count(const KeyT &Key) const
MemProfContextDisambiguation(const ModuleSummaryIndex *Summary=nullptr, bool isSamplePGO=false)
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
static ErrorOr< std::unique_ptr< MemoryBuffer > > getFile(const Twine &Filename, bool IsText=false, bool RequiresNullTerminator=true, bool IsVolatile=false, std::optional< Align > Alignment=std::nullopt)
Open the specified file as a MemoryBuffer, returning a new MemoryBuffer if successful,...
Class to hold module path string table and global value map, and encapsulate methods for operating on...
static StringRef getOriginalNameBeforePromote(StringRef Name)
Helper to obtain the unpromoted name for a global value (or the original name if not promoted).
ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const
Return a ValueInfo for the index value_type (convenient when iterating index).
uint64_t getStackIdAtIndex(unsigned Index) const
GlobalValueSummary * findSummaryInModule(ValueInfo VI, StringRef ModuleId) const
Find the summary for ValueInfo VI in module ModuleId, or nullptr if not found.
GlobalValue::GUID getGUIDFromOriginalID(GlobalValue::GUID OriginalID) const
Return the GUID for OriginalId in the OidGuidMap.
A Module instance is used to store all the information related to an LLVM module.
A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM Value Representation.
StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const ValueT &V)
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
void swap(DenseSetImpl &RHS)
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
An efficient, type-erasing, non-owning reference to a callable.
Helper class to iterate through stack ids in both metadata (memprof MIB and callsite) and the corresp...
CallStackIterator end() const
CallStackIterator beginAfterSharedPrefix(CallStack &Other)
This class implements an extremely fast bulk output stream that can only output to a stream.
@ C
The default llvm calling convention, compatible with C.
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
AllocationType getMIBAllocType(const MDNode *MIB)
Returns the allocation type from an MIB metadata node.
bool hasSingleAllocType(uint8_t AllocTypes)
True if the AllocTypes bitmask contains just a single type.
std::string getAllocTypeAttributeString(AllocationType Type)
Returns the string to use in attributes with the given type.
MDNode * getMIBStackNode(const MDNode *MIB)
Returns the stack node from an MIB metadata node.
DiagnosticInfoOptimizationBase::Argument NV
CallBase & promoteIndirectCall(CallBase &CB, Function *F, uint64_t Count, uint64_t TotalCount, bool AttachProfToDirectCall, OptimizationRemarkEmitter *ORE)
NodeAddr< FuncNode * > Func
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
void logAllUnhandledErrors(Error E, raw_ostream &OS, Twine ErrorBanner={})
Log all errors (if any) in E to OS.
bool isLegalToPromote(const CallBase &CB, Function *Callee, const char **FailureReason=nullptr)
Return true if the given indirect call site can be made to call Callee.
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
cl::opt< bool > MemProfRequireDefinitionForPromotion("memprof-require-definition-for-promotion", cl::init(false), cl::Hidden, cl::desc("Require target function definition when promoting indirect calls"))
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void set_subtract(S1Ty &S1, const S2Ty &S2)
set_subtract(A, B) - Compute A := A - B
raw_ostream & WriteGraph(raw_ostream &O, const GraphType &G, bool ShortNames=false, const Twine &Title="")
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Expected< std::unique_ptr< ModuleSummaryIndex > > getModuleSummaryIndex(MemoryBufferRef Buffer)
Parse the specified bitcode buffer, returning the module summary index.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void annotateValueSite(Module &M, Instruction &Inst, const InstrProfRecord &InstrProfR, InstrProfValueKind ValueKind, uint32_t SiteIndx, uint32_t MaxMDCount=3)
Get the value profile data for value site SiteIdx from InstrProfR and annotate the instruction Inst w...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
bool set_union(S1Ty &S1, const S2Ty &S2)
set_union(A, B) - Compute A := A u B, return whether A changed.
cl::opt< bool > SupportsHotColdNew
Indicate we are linking with an allocator that supports hot/cold operator new interfaces.
S1Ty set_intersection(const S1Ty &S1, const S2Ty &S2)
set_intersection(A, B) - Return A ^ B
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
cl::opt< bool > EnableMemProfContextDisambiguation
Enable MemProf context disambiguation for thin link.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Expected< T > errorOrToExpected(ErrorOr< T > &&EO)
Convert an ErrorOr<T> to an Expected<T>.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
const char * toString(DWARFSectionKind Kind)
Function * CloneFunction(Function *F, ValueToValueMapTy &VMap, ClonedCodeInfo *CodeInfo=nullptr)
Return a copy of the specified function and add it to that function's module.
bool mayHaveMemprofSummary(const CallBase *CB)
Returns true if the instruction could have memprof metadata, used to ensure consistency between summa...
Implement std::hash so that hash_code can be used in STL containers.
DOTGraphTraits(bool IsSimple=false)
typename GTraits::NodeRef NodeRef
static std::string getEdgeAttributes(NodeRef, ChildIteratorType ChildIter, GraphType)
const CallsiteContextGraph< DerivedCCG, FuncTy, CallTy > * GraphType
typename GTraits::ChildIteratorType ChildIteratorType
static bool isNodeHidden(NodeRef Node, GraphType)
static std::string getNodeLabel(NodeRef Node, GraphType G)
static std::string getNodeAttributes(NodeRef Node, GraphType)
static NodeRef getNode(const NodePtrTy &P)
static const ContextNode< DerivedCCG, FuncTy, CallTy > * GetCallee(const EdgePtrTy &P)
static ChildIteratorType child_end(NodeRef N)
std::shared_ptr< ContextEdge< DerivedCCG, FuncTy, CallTy > > EdgePtrTy
const CallsiteContextGraph< DerivedCCG, FuncTy, CallTy > * GraphType
const ContextNode< DerivedCCG, FuncTy, CallTy > * NodeRef
static ChildIteratorType child_begin(NodeRef N)
std::unique_ptr< ContextNode< DerivedCCG, FuncTy, CallTy > > NodePtrTy
static NodeRef getEntryNode(GraphType G)
static nodes_iterator nodes_begin(GraphType G)
static nodes_iterator nodes_end(GraphType G)
Summary of memprof metadata on allocations.
SmallVector< uint8_t > Versions
Summary of memprof callsite metadata.
SmallVector< unsigned > Clones
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
DefaultDOTGraphTraits - This class provides the default implementations of all of the DOTGraphTraits ...
An information struct used to provide DenseMap with the various necessary components for a given valu...
Used in the streaming interface as the general argument type.
typename GraphType::UnknownGraphTypeError NodeRef
Struct that holds a reference to a particular GUID in a global value summary.
ArrayRef< std::unique_ptr< GlobalValueSummary > > getSummaryList() const
GlobalValue::GUID getGUID() const