48#include <unordered_map>
53#define DEBUG_TYPE "memprof-context-disambiguation"
56 "Number of function clones created during whole program analysis");
58 "Number of function clones created during ThinLTO backend");
60 "Number of functions that had clones created during ThinLTO backend");
61STATISTIC(AllocTypeNotCold,
"Number of not cold static allocations (possibly "
62 "cloned) during whole program analysis");
63STATISTIC(AllocTypeCold,
"Number of cold static allocations (possibly cloned) "
64 "during whole program analysis");
66 "Number of not cold static allocations (possibly cloned) during "
68STATISTIC(AllocTypeColdThinBackend,
"Number of cold static allocations "
69 "(possibly cloned) during ThinLTO backend");
71 "Number of original (not cloned) allocations with memprof profiles "
72 "during ThinLTO backend");
74 AllocVersionsThinBackend,
75 "Number of allocation versions (including clones) during ThinLTO backend");
77 "Maximum number of allocation versions created for an original "
78 "allocation during ThinLTO backend");
80 "Number of unclonable ambigous allocations during ThinLTO backend");
82 "Number of edges removed due to mismatched callees (profiled vs IR)");
84 "Number of profiled callees found via tail calls");
86 "Aggregate depth of profiled callees found via tail calls");
88 "Maximum depth of profiled callees found via tail calls");
90 "Number of profiled callees found via multiple tail call chains");
95 cl::desc(
"Specify the path prefix of the MemProf dot files."));
99 cl::desc(
"Export graph to dot files."));
103 cl::desc(
"Dump CallingContextGraph to stdout after each stage."));
107 cl::desc(
"Perform verification checks on CallingContextGraph."));
111 cl::desc(
"Perform frequent verification checks on nodes."));
114 "memprof-import-summary",
115 cl::desc(
"Import summary to use for testing the ThinLTO backend via opt"),
121 cl::desc(
"Max depth to recursively search for missing "
122 "frames through tail calls."));
133 cl::desc(
"Linking with hot/cold operator new interfaces"));
151template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
152class CallsiteContextGraph {
154 CallsiteContextGraph() =
default;
155 CallsiteContextGraph(
const CallsiteContextGraph &) =
default;
156 CallsiteContextGraph(CallsiteContextGraph &&) =
default;
163 void identifyClones();
170 bool assignFunctions();
176 const CallsiteContextGraph &CCG) {
182 const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *>;
184 const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *>;
186 void exportToDot(std::string Label)
const;
189 struct FuncInfo final
190 :
public std::pair<FuncTy *, unsigned > {
191 using Base = std::pair<FuncTy *, unsigned>;
192 FuncInfo(
const Base &
B) :
Base(
B) {}
193 FuncInfo(FuncTy *
F =
nullptr,
unsigned CloneNo = 0) :
Base(
F, CloneNo) {}
194 explicit operator bool()
const {
return this->first !=
nullptr; }
195 FuncTy *func()
const {
return this->first; }
196 unsigned cloneNo()
const {
return this->second; }
200 struct CallInfo final :
public std::pair<CallTy, unsigned > {
201 using Base = std::pair<CallTy, unsigned>;
203 CallInfo(CallTy Call =
nullptr,
unsigned CloneNo = 0)
205 explicit operator bool()
const {
return (
bool)this->first; }
206 CallTy call()
const {
return this->first; }
207 unsigned cloneNo()
const {
return this->second; }
208 void setCloneNo(
unsigned N) { this->second =
N; }
210 if (!
operator bool()) {
216 OS <<
"\t(clone " << cloneNo() <<
")";
239 bool Recursive =
false;
255 uint8_t AllocTypes = 0;
259 std::vector<std::shared_ptr<ContextEdge>> CalleeEdges;
263 std::vector<std::shared_ptr<ContextEdge>> CallerEdges;
269 std::vector<ContextNode *> Clones;
272 ContextNode *CloneOf =
nullptr;
274 ContextNode(
bool IsAllocation) : IsAllocation(IsAllocation),
Call() {}
276 ContextNode(
bool IsAllocation,
CallInfo C)
277 : IsAllocation(IsAllocation),
Call(
C) {}
279 void addClone(ContextNode *Clone) {
281 CloneOf->Clones.push_back(Clone);
282 Clone->CloneOf = CloneOf;
284 Clones.push_back(Clone);
286 Clone->CloneOf =
this;
290 ContextNode *getOrigNode() {
297 unsigned int ContextId);
299 ContextEdge *findEdgeFromCallee(
const ContextNode *Callee);
300 ContextEdge *findEdgeFromCaller(
const ContextNode *Caller);
301 void eraseCalleeEdge(
const ContextEdge *Edge);
302 void eraseCallerEdge(
const ContextEdge *Edge);
306 bool hasCall()
const {
return (
bool)
Call.call(); }
312 bool isRemoved()
const {
315 if (ContextIds.
empty())
316 assert(CalleeEdges.empty() && CallerEdges.empty() &&
317 "Context ids empty but at least one of callee and caller edges "
319 return ContextIds.
empty();
339 uint8_t AllocTypes = 0;
344 ContextEdge(ContextNode *Callee, ContextNode *Caller, uint8_t
AllocType,
347 ContextIds(ContextIds) {}
362 void removeNoneTypeCalleeEdges(ContextNode *
Node);
364 recursivelyRemoveNoneTypeCalleeEdges(ContextNode *
Node,
370 template <
class NodeT,
class IteratorT>
371 std::vector<uint64_t>
376 ContextNode *addAllocNode(
CallInfo Call,
const FuncTy *
F);
379 template <
class NodeT,
class IteratorT>
380 void addStackNodesForMIB(ContextNode *AllocNode,
388 void updateStackNodes();
392 void handleCallsitesWithMultipleTargets();
399 std::map<const ContextNode *, const FuncTy *> NodeToCallingFunc;
402 using EdgeIter =
typename std::vector<std::shared_ptr<ContextEdge>>::iterator;
404 using CallContextInfo = std::tuple<CallTy, std::vector<uint64_t>,
413 void assignStackNodesPostOrder(
425 void propagateDuplicateContextIds(
431 void connectNewNode(ContextNode *NewNode, ContextNode *OrigNode,
438 return static_cast<const DerivedCCG *
>(
this)->getStackId(IdOrIndex);
449 calleesMatch(CallTy Call, EdgeIter &EI,
455 bool calleeMatchesFunc(
456 CallTy Call,
const FuncTy *Func,
const FuncTy *CallerFunc,
457 std::vector<std::pair<CallTy, FuncTy *>> &FoundCalleeChain) {
458 return static_cast<DerivedCCG *
>(
this)->calleeMatchesFunc(
459 Call, Func, CallerFunc, FoundCalleeChain);
464 std::vector<uint64_t> getStackIdsWithContextNodesForCall(CallTy Call) {
465 return static_cast<DerivedCCG *
>(
this)->getStackIdsWithContextNodesForCall(
470 uint64_t getLastStackId(CallTy Call) {
471 return static_cast<DerivedCCG *
>(
this)->getLastStackId(Call);
476 AllocType == AllocationType::Cold ? AllocTypeCold++ : AllocTypeNotCold++;
477 static_cast<DerivedCCG *
>(
this)->updateAllocationCall(Call,
AllocType);
482 void updateCall(
CallInfo &CallerCall, FuncInfo CalleeFunc) {
483 static_cast<DerivedCCG *
>(
this)->updateCall(CallerCall, CalleeFunc);
489 FuncInfo cloneFunctionForCallsite(
490 FuncInfo &Func,
CallInfo &Call, std::map<CallInfo, CallInfo> &CallMap,
491 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
492 return static_cast<DerivedCCG *
>(
this)->cloneFunctionForCallsite(
493 Func, Call, CallMap, CallsWithMetadataInFunc, CloneNo);
498 std::string getLabel(
const FuncTy *Func,
const CallTy Call,
499 unsigned CloneNo)
const {
500 return static_cast<const DerivedCCG *
>(
this)->getLabel(Func, Call, CloneNo);
504 ContextNode *getNodeForInst(
const CallInfo &
C);
505 ContextNode *getNodeForAlloc(
const CallInfo &
C);
506 ContextNode *getNodeForStackId(
uint64_t StackId);
509 void unsetNodeForInst(
const CallInfo &
C);
531 moveEdgeToNewCalleeClone(
const std::shared_ptr<ContextEdge> &Edge,
532 EdgeIter *CallerEdgeI =
nullptr);
538 void moveEdgeToExistingCalleeClone(
const std::shared_ptr<ContextEdge> &Edge,
539 ContextNode *NewCallee,
540 EdgeIter *CallerEdgeI =
nullptr,
541 bool NewClone =
false);
546 void identifyClones(ContextNode *
Node,
550 std::map<uint32_t, AllocationType> ContextIdToAllocationType;
556 std::map<uint64_t, ContextNode *> StackEntryIdToContextNodeMap;
563 std::vector<std::unique_ptr<ContextNode>> NodeOwner;
569 unsigned int LastContextId = 0;
572template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
574 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode;
575template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
577 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge;
578template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
580 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::FuncInfo;
581template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
583 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::CallInfo;
586class ModuleCallsiteContextGraph
587 :
public CallsiteContextGraph<ModuleCallsiteContextGraph, Function,
590 ModuleCallsiteContextGraph(
595 friend CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
599 bool calleeMatchesFunc(
601 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain);
602 bool findProfiledCalleeThroughTailCalls(
604 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain,
605 bool &FoundMultipleCalleeChains);
607 std::vector<uint64_t> getStackIdsWithContextNodesForCall(
Instruction *Call);
609 void updateCall(
CallInfo &CallerCall, FuncInfo CalleeFunc);
610 CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
612 cloneFunctionForCallsite(FuncInfo &Func,
CallInfo &Call,
613 std::map<CallInfo, CallInfo> &CallMap,
614 std::vector<CallInfo> &CallsWithMetadataInFunc,
617 unsigned CloneNo)
const;
626struct IndexCall :
public PointerUnion<CallsiteInfo *, AllocInfo *> {
628 IndexCall(std::nullptr_t) : IndexCall() {}
633 IndexCall *operator->() {
return this; }
638 if (
auto *AI = llvm::dyn_cast_if_present<AllocInfo *>(getBase())) {
641 auto *CI = llvm::dyn_cast_if_present<CallsiteInfo *>(getBase());
649class IndexCallsiteContextGraph
650 :
public CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
653 IndexCallsiteContextGraph(
658 ~IndexCallsiteContextGraph() {
663 for (
auto &
I : FunctionCalleesToSynthesizedCallsiteInfos) {
665 for (
auto &Callsite :
I.second)
666 FS->addCallsite(*Callsite.second);
671 friend CallsiteContextGraph<IndexCallsiteContextGraph,
FunctionSummary,
675 bool calleeMatchesFunc(
678 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain);
679 bool findProfiledCalleeThroughTailCalls(
681 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain,
682 bool &FoundMultipleCalleeChains);
683 uint64_t getLastStackId(IndexCall &Call);
684 std::vector<uint64_t> getStackIdsWithContextNodesForCall(IndexCall &Call);
686 void updateCall(
CallInfo &CallerCall, FuncInfo CalleeFunc);
689 cloneFunctionForCallsite(FuncInfo &Func,
CallInfo &Call,
690 std::map<CallInfo, CallInfo> &CallMap,
691 std::vector<CallInfo> &CallsWithMetadataInFunc,
693 std::string getLabel(
const FunctionSummary *Func,
const IndexCall &Call,
694 unsigned CloneNo)
const;
698 std::map<const FunctionSummary *, ValueInfo> FSToVIMap;
709 std::map<ValueInfo, std::unique_ptr<CallsiteInfo>>>
710 FunctionCalleesToSynthesizedCallsiteInfos;
722 :
public DenseMapInfo<std::pair<IndexCall, unsigned>> {};
725 :
public DenseMapInfo<PointerUnion<CallsiteInfo *, AllocInfo *>> {};
730struct FieldSeparator {
734 FieldSeparator(
const char *Sep =
", ") : Sep(Sep) {}
751 assert(AllocTypes != (uint8_t)AllocationType::None);
753 ((uint8_t)AllocationType::NotCold | (uint8_t)AllocationType::Cold))
754 return AllocationType::NotCold;
762template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
764 const std::vector<uint8_t> &InAllocTypes,
765 const std::vector<std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>>>
768 InAllocTypes.begin(), InAllocTypes.end(), Edges.begin(),
770 const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &r) {
774 if (l == (uint8_t)AllocationType::None ||
775 r->AllocTypes == (uint8_t)AllocationType::None)
777 return allocTypeToUse(l) == allocTypeToUse(r->AllocTypes);
783template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
784typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
785CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForInst(
787 ContextNode *
Node = getNodeForAlloc(
C);
791 return NonAllocationCallToContextNodeMap.lookup(
C);
794template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
795typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
796CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForAlloc(
798 return AllocationCallToContextNodeMap.lookup(
C);
801template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
802typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
803CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForStackId(
805 auto StackEntryNode = StackEntryIdToContextNodeMap.find(StackId);
806 if (StackEntryNode != StackEntryIdToContextNodeMap.end())
807 return StackEntryNode->second;
811template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
812void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::unsetNodeForInst(
814 AllocationCallToContextNodeMap.erase(
C) ||
815 NonAllocationCallToContextNodeMap.erase(
C);
816 assert(!AllocationCallToContextNodeMap.count(
C) &&
817 !NonAllocationCallToContextNodeMap.count(
C));
820template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
821void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
823 unsigned int ContextId) {
824 for (
auto &Edge : CallerEdges) {
825 if (Edge->Caller == Caller) {
827 Edge->getContextIds().insert(ContextId);
831 std::shared_ptr<ContextEdge> Edge = std::make_shared<ContextEdge>(
833 CallerEdges.push_back(Edge);
834 Caller->CalleeEdges.push_back(Edge);
837template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
838void CallsiteContextGraph<
839 DerivedCCG, FuncTy, CallTy>::removeNoneTypeCalleeEdges(ContextNode *
Node) {
840 for (
auto EI =
Node->CalleeEdges.begin(); EI !=
Node->CalleeEdges.end();) {
842 if (Edge->AllocTypes == (uint8_t)AllocationType::None) {
843 assert(Edge->ContextIds.empty());
844 Edge->Callee->eraseCallerEdge(Edge.get());
845 EI =
Node->CalleeEdges.erase(EI);
851template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
852typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge *
853CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
854 findEdgeFromCallee(
const ContextNode *Callee) {
855 for (
const auto &Edge : CalleeEdges)
856 if (Edge->Callee == Callee)
861template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
862typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge *
863CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
864 findEdgeFromCaller(
const ContextNode *Caller) {
865 for (
const auto &Edge : CallerEdges)
866 if (Edge->Caller == Caller)
871template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
872void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
873 eraseCalleeEdge(
const ContextEdge *Edge) {
875 CalleeEdges, [Edge](
const std::shared_ptr<ContextEdge> &CalleeEdge) {
876 return CalleeEdge.get() == Edge;
878 assert(EI != CalleeEdges.end());
879 CalleeEdges.erase(EI);
882template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
883void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
884 eraseCallerEdge(
const ContextEdge *Edge) {
886 CallerEdges, [Edge](
const std::shared_ptr<ContextEdge> &CallerEdge) {
887 return CallerEdge.get() == Edge;
889 assert(EI != CallerEdges.end());
890 CallerEdges.erase(EI);
893template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
894uint8_t CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::computeAllocType(
897 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
898 uint8_t
AllocType = (uint8_t)AllocationType::None;
899 for (
auto Id : ContextIds) {
900 AllocType |= (uint8_t)ContextIdToAllocationType[Id];
908template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
910CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::intersectAllocTypesImpl(
913 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
914 uint8_t
AllocType = (uint8_t)AllocationType::None;
915 for (
auto Id : Node1Ids) {
916 if (!Node2Ids.
count(Id))
918 AllocType |= (uint8_t)ContextIdToAllocationType[Id];
926template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
927uint8_t CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::intersectAllocTypes(
929 if (Node1Ids.
size() < Node2Ids.
size())
930 return intersectAllocTypesImpl(Node1Ids, Node2Ids);
932 return intersectAllocTypesImpl(Node2Ids, Node1Ids);
935template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
936typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
937CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::addAllocNode(
939 assert(!getNodeForAlloc(Call));
941 std::make_unique<ContextNode>(
true, Call));
942 ContextNode *AllocNode = NodeOwner.back().get();
943 AllocationCallToContextNodeMap[
Call] = AllocNode;
944 NodeToCallingFunc[AllocNode] =
F;
946 AllocNode->OrigStackOrAllocId = LastContextId;
949 AllocNode->AllocTypes = (uint8_t)AllocationType::None;
954template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
955template <
class NodeT,
class IteratorT>
956void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::addStackNodesForMIB(
964 ContextIdToAllocationType[++LastContextId] =
AllocType;
967 AllocNode->AllocTypes |= (uint8_t)
AllocType;
968 AllocNode->ContextIds.insert(LastContextId);
973 ContextNode *PrevNode = AllocNode;
980 ContextIter != StackContext.
end(); ++ContextIter) {
981 auto StackId = getStackId(*ContextIter);
982 ContextNode *StackNode = getNodeForStackId(StackId);
985 std::make_unique<ContextNode>(
false));
986 StackNode = NodeOwner.back().get();
987 StackEntryIdToContextNodeMap[StackId] = StackNode;
988 StackNode->OrigStackOrAllocId = StackId;
992 StackNode->Recursive =
true;
993 StackNode->ContextIds.insert(LastContextId);
994 StackNode->AllocTypes |= (uint8_t)
AllocType;
995 PrevNode->addOrUpdateCallerEdge(StackNode,
AllocType, LastContextId);
996 PrevNode = StackNode;
1000template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1002CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::duplicateContextIds(
1006 for (
auto OldId : StackSequenceContextIds) {
1007 NewContextIds.
insert(++LastContextId);
1008 OldToNewContextIds[OldId].insert(LastContextId);
1009 assert(ContextIdToAllocationType.count(OldId));
1011 ContextIdToAllocationType[LastContextId] = ContextIdToAllocationType[OldId];
1013 return NewContextIds;
1016template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1017void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
1018 propagateDuplicateContextIds(
1023 for (
auto Id : ContextIds)
1024 if (
auto NewId = OldToNewContextIds.find(Id);
1025 NewId != OldToNewContextIds.end())
1026 NewIds.
insert(NewId->second.begin(), NewId->second.end());
1031 auto UpdateCallers = [&](ContextNode *
Node,
1033 auto &&UpdateCallers) ->
void {
1034 for (
const auto &Edge :
Node->CallerEdges) {
1035 auto Inserted = Visited.insert(Edge.get());
1038 ContextNode *NextNode = Edge->Caller;
1042 if (!NewIdsToAdd.
empty()) {
1043 Edge->getContextIds().insert(NewIdsToAdd.
begin(), NewIdsToAdd.
end());
1044 NextNode->ContextIds.insert(NewIdsToAdd.
begin(), NewIdsToAdd.
end());
1045 UpdateCallers(NextNode, Visited, UpdateCallers);
1051 for (
auto &Entry : AllocationCallToContextNodeMap) {
1052 auto *
Node = Entry.second;
1057 Node->ContextIds.insert(NewIdsToAdd.
begin(), NewIdsToAdd.
end());
1058 UpdateCallers(
Node, Visited, UpdateCallers);
1062template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1063void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::connectNewNode(
1064 ContextNode *NewNode, ContextNode *OrigNode,
bool TowardsCallee) {
1069 TowardsCallee ? OrigNode->CalleeEdges : OrigNode->CallerEdges;
1071 for (
auto EI = OrigEdges.begin(); EI != OrigEdges.end();) {
1077 set_subtract(Edge->getContextIds(), RemainingContextIds, NewEdgeContextIds,
1078 NotFoundContextIds);
1079 RemainingContextIds.
swap(NotFoundContextIds);
1081 if (NewEdgeContextIds.
empty()) {
1085 if (TowardsCallee) {
1086 auto NewEdge = std::make_shared<ContextEdge>(
1087 Edge->Callee, NewNode, computeAllocType(NewEdgeContextIds),
1089 NewNode->CalleeEdges.push_back(NewEdge);
1090 NewEdge->Callee->CallerEdges.push_back(NewEdge);
1092 auto NewEdge = std::make_shared<ContextEdge>(
1093 NewNode, Edge->Caller, computeAllocType(NewEdgeContextIds),
1095 NewNode->CallerEdges.push_back(NewEdge);
1096 NewEdge->Caller->CalleeEdges.push_back(NewEdge);
1099 if (Edge->getContextIds().empty()) {
1100 if (TowardsCallee) {
1101 Edge->Callee->eraseCallerEdge(Edge.get());
1102 EI = OrigNode->CalleeEdges.erase(EI);
1104 Edge->Caller->eraseCalleeEdge(Edge.get());
1105 EI = OrigNode->CallerEdges.erase(EI);
1113template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1114void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
1115 assignStackNodesPostOrder(ContextNode *
Node,
1118 &StackIdToMatchingCalls) {
1126 auto CallerEdges =
Node->CallerEdges;
1127 for (
auto &Edge : CallerEdges) {
1131 assignStackNodesPostOrder(Edge->Caller, Visited, StackIdToMatchingCalls);
1140 if (
Node->IsAllocation ||
1141 !StackIdToMatchingCalls.count(
Node->OrigStackOrAllocId))
1144 auto &Calls = StackIdToMatchingCalls[
Node->OrigStackOrAllocId];
1148 if (Calls.size() == 1) {
1149 auto &[
Call, Ids,
Func, SavedContextIds] = Calls[0];
1150 if (Ids.size() == 1) {
1151 assert(SavedContextIds.empty());
1154 if (
Node->Recursive)
1156 Node->setCall(Call);
1157 NonAllocationCallToContextNodeMap[
Call] =
Node;
1166 ContextNode *LastNode = getNodeForStackId(LastId);
1170 for (
unsigned I = 0;
I < Calls.size();
I++) {
1171 auto &[
Call, Ids,
Func, SavedContextIds] = Calls[
I];
1174 if (SavedContextIds.empty())
1177 assert(LastId == Ids.back());
1179 ContextNode *FirstNode = getNodeForStackId(Ids[0]);
1189 ContextNode *PrevNode =
nullptr;
1190 for (
auto Id : Ids) {
1191 ContextNode *CurNode = getNodeForStackId(Id);
1195 assert(!CurNode->Recursive);
1200 auto *Edge = CurNode->findEdgeFromCallee(PrevNode);
1202 SavedContextIds.clear();
1209 if (SavedContextIds.empty())
1212 if (SavedContextIds.empty())
1216 NodeOwner.push_back(
1217 std::make_unique<ContextNode>(
false, Call));
1218 ContextNode *NewNode = NodeOwner.back().get();
1219 NodeToCallingFunc[NewNode] =
Func;
1220 NonAllocationCallToContextNodeMap[
Call] = NewNode;
1221 NewNode->ContextIds = SavedContextIds;
1222 NewNode->AllocTypes = computeAllocType(NewNode->ContextIds);
1227 connectNewNode(NewNode, FirstNode,
true);
1232 connectNewNode(NewNode, LastNode,
false);
1237 for (
auto Id : Ids) {
1238 ContextNode *CurNode = getNodeForStackId(Id);
1244 set_subtract(CurNode->ContextIds, NewNode->ContextIds);
1246 auto *PrevEdge = CurNode->findEdgeFromCallee(PrevNode);
1248 set_subtract(PrevEdge->getContextIds(), NewNode->ContextIds);
1249 if (PrevEdge->getContextIds().empty()) {
1250 PrevNode->eraseCallerEdge(PrevEdge);
1251 CurNode->eraseCalleeEdge(PrevEdge);
1259template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1260void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::updateStackNodes() {
1269 for (
auto &[Func, CallsWithMetadata] : FuncToCallsWithMetadata) {
1270 for (
auto &Call : CallsWithMetadata) {
1272 if (AllocationCallToContextNodeMap.count(Call))
1274 auto StackIdsWithContextNodes =
1275 getStackIdsWithContextNodesForCall(
Call.call());
1278 if (StackIdsWithContextNodes.empty())
1282 StackIdToMatchingCalls[StackIdsWithContextNodes.back()].push_back(
1283 {
Call.call(), StackIdsWithContextNodes, Func, {}});
1294 for (
auto &It : StackIdToMatchingCalls) {
1295 auto &Calls = It.getSecond();
1297 if (Calls.size() == 1) {
1298 auto &Ids = std::get<1>(Calls[0]);
1299 if (Ids.size() == 1)
1308 std::stable_sort(Calls.begin(), Calls.end(),
1309 [](
const CallContextInfo &
A,
const CallContextInfo &
B) {
1310 auto &IdsA = std::get<1>(A);
1311 auto &IdsB = std::get<1>(B);
1312 return IdsA.size() > IdsB.size() ||
1313 (IdsA.size() == IdsB.size() && IdsA < IdsB);
1320 ContextNode *LastNode = getNodeForStackId(LastId);
1324 if (LastNode->Recursive)
1332 for (
unsigned I = 0;
I < Calls.size();
I++) {
1333 auto &[
Call, Ids,
Func, SavedContextIds] = Calls[
I];
1334 assert(SavedContextIds.empty());
1335 assert(LastId == Ids.back());
1343 ContextNode *PrevNode = LastNode;
1344 ContextNode *CurNode = LastNode;
1349 for (
auto IdIter = Ids.rbegin() + 1; IdIter != Ids.rend(); IdIter++) {
1351 CurNode = getNodeForStackId(Id);
1355 if (CurNode->Recursive) {
1360 auto *Edge = CurNode->findEdgeFromCaller(PrevNode);
1378 set_intersect(StackSequenceContextIds, Edge->getContextIds());
1381 if (StackSequenceContextIds.
empty()) {
1394 if (Ids.back() != getLastStackId(Call)) {
1395 for (
const auto &PE : LastNode->CallerEdges) {
1396 set_subtract(StackSequenceContextIds, PE->getContextIds());
1397 if (StackSequenceContextIds.
empty())
1401 if (StackSequenceContextIds.
empty())
1407 bool DuplicateContextIds =
false;
1408 if (
I + 1 < Calls.size()) {
1409 auto NextIds = std::get<1>(Calls[
I + 1]);
1410 DuplicateContextIds = Ids == NextIds;
1419 OldToNewContextIds.
reserve(OldToNewContextIds.
size() +
1420 StackSequenceContextIds.
size());
1423 ? duplicateContextIds(StackSequenceContextIds, OldToNewContextIds)
1424 : StackSequenceContextIds;
1425 assert(!SavedContextIds.empty());
1427 if (!DuplicateContextIds) {
1431 set_subtract(LastNodeContextIds, StackSequenceContextIds);
1432 if (LastNodeContextIds.
empty())
1439 propagateDuplicateContextIds(OldToNewContextIds);
1450 for (
auto &Entry : AllocationCallToContextNodeMap)
1451 assignStackNodesPostOrder(Entry.second, Visited, StackIdToMatchingCalls);
1456 Call->getMetadata(LLVMContext::MD_callsite));
1457 return CallsiteContext.
back();
1460uint64_t IndexCallsiteContextGraph::getLastStackId(IndexCall &Call) {
1463 CallsiteContext(dyn_cast_if_present<CallsiteInfo *>(
Call.getBase()));
1465 return Index.getStackIdAtIndex(CallsiteContext.
back());
1478std::string ModuleCallsiteContextGraph::getLabel(
const Function *Func,
1480 unsigned CloneNo)
const {
1481 return (
Twine(
Call->getFunction()->getName()) +
" -> " +
1482 cast<CallBase>(Call)->getCalledFunction()->getName())
1486std::string IndexCallsiteContextGraph::getLabel(
const FunctionSummary *Func,
1487 const IndexCall &Call,
1488 unsigned CloneNo)
const {
1489 auto VI = FSToVIMap.find(Func);
1490 assert(VI != FSToVIMap.end());
1491 if (isa<AllocInfo *>(
Call.getBase()))
1492 return (
VI->second.name() +
" -> alloc").str();
1494 auto *Callsite = dyn_cast_if_present<CallsiteInfo *>(
Call.getBase());
1495 return (
VI->second.name() +
" -> " +
1497 Callsite->Clones[CloneNo]))
1502std::vector<uint64_t>
1503ModuleCallsiteContextGraph::getStackIdsWithContextNodesForCall(
1506 Call->getMetadata(LLVMContext::MD_callsite));
1507 return getStackIdsWithContextNodes<MDNode, MDNode::op_iterator>(
1511std::vector<uint64_t>
1512IndexCallsiteContextGraph::getStackIdsWithContextNodesForCall(IndexCall &Call) {
1515 CallsiteContext(dyn_cast_if_present<CallsiteInfo *>(
Call.getBase()));
1521template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1522template <
class NodeT,
class IteratorT>
1523std::vector<uint64_t>
1524CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getStackIdsWithContextNodes(
1526 std::vector<uint64_t> StackIds;
1527 for (
auto IdOrIndex : CallsiteContext) {
1528 auto StackId = getStackId(IdOrIndex);
1529 ContextNode *
Node = getNodeForStackId(StackId);
1532 StackIds.push_back(StackId);
1537ModuleCallsiteContextGraph::ModuleCallsiteContextGraph(
1540 :
Mod(
M), OREGetter(OREGetter) {
1542 std::vector<CallInfo> CallsWithMetadata;
1543 for (
auto &BB :
F) {
1544 for (
auto &
I : BB) {
1545 if (!isa<CallBase>(
I))
1547 if (
auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof)) {
1548 CallsWithMetadata.push_back(&
I);
1549 auto *AllocNode = addAllocNode(&
I, &
F);
1550 auto *CallsiteMD =
I.getMetadata(LLVMContext::MD_callsite);
1554 for (
auto &MDOp : MemProfMD->operands()) {
1555 auto *MIBMD = cast<const MDNode>(MDOp);
1559 addStackNodesForMIB<MDNode, MDNode::op_iterator>(
1560 AllocNode, StackContext, CallsiteContext,
1563 assert(AllocNode->AllocTypes != (uint8_t)AllocationType::None);
1566 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
1567 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
1570 else if (
I.getMetadata(LLVMContext::MD_callsite))
1571 CallsWithMetadata.push_back(&
I);
1574 if (!CallsWithMetadata.empty())
1575 FuncToCallsWithMetadata[&
F] = CallsWithMetadata;
1579 dbgs() <<
"CCG before updating call stack chains:\n";
1584 exportToDot(
"prestackupdate");
1588 handleCallsitesWithMultipleTargets();
1591 for (
auto &FuncEntry : FuncToCallsWithMetadata)
1592 for (
auto &Call : FuncEntry.second)
1593 Call.call()->setMetadata(LLVMContext::MD_callsite,
nullptr);
1596IndexCallsiteContextGraph::IndexCallsiteContextGraph(
1603 for (
auto &S :
VI.getSummaryList()) {
1612 !isPrevailing(
VI.getGUID(), S.get()))
1614 auto *
FS = dyn_cast<FunctionSummary>(S.get());
1617 std::vector<CallInfo> CallsWithMetadata;
1618 if (!
FS->allocs().empty()) {
1619 for (
auto &AN :
FS->mutableAllocs()) {
1624 if (AN.MIBs.empty())
1626 CallsWithMetadata.push_back({&AN});
1627 auto *AllocNode = addAllocNode({&AN},
FS);
1634 for (
auto &MIB : AN.MIBs) {
1637 addStackNodesForMIB<MIBInfo, SmallVector<unsigned>::const_iterator>(
1638 AllocNode, StackContext, EmptyContext, MIB.AllocType);
1640 assert(AllocNode->AllocTypes != (uint8_t)AllocationType::None);
1645 AN.Versions[0] = (uint8_t)allocTypeToUse(AllocNode->AllocTypes);
1649 if (!
FS->callsites().empty())
1650 for (
auto &SN :
FS->mutableCallsites())
1651 CallsWithMetadata.push_back({&SN});
1653 if (!CallsWithMetadata.empty())
1654 FuncToCallsWithMetadata[FS] = CallsWithMetadata;
1656 if (!
FS->allocs().empty() || !
FS->callsites().empty())
1662 dbgs() <<
"CCG before updating call stack chains:\n";
1667 exportToDot(
"prestackupdate");
1671 handleCallsitesWithMultipleTargets();
1674template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1675void CallsiteContextGraph<DerivedCCG, FuncTy,
1676 CallTy>::handleCallsitesWithMultipleTargets() {
1691 for (
auto Entry = NonAllocationCallToContextNodeMap.begin();
1692 Entry != NonAllocationCallToContextNodeMap.end();) {
1693 auto *
Node = Entry->second;
1696 bool Removed =
false;
1698 for (
auto EI =
Node->CalleeEdges.begin(); EI !=
Node->CalleeEdges.end();) {
1700 if (!Edge->Callee->hasCall()) {
1704 assert(NodeToCallingFunc.count(Edge->Callee));
1706 if (calleesMatch(Call, EI, TailCallToContextNodeMap))
1708 RemovedEdgesWithMismatchedCallees++;
1712 Entry = NonAllocationCallToContextNodeMap.erase(Entry);
1723 for (
auto &[Call,
Node] : TailCallToContextNodeMap)
1724 NonAllocationCallToContextNodeMap[
Call] =
Node;
1735 return Index.getStackIdAtIndex(IdOrIndex);
1738template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1739bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::calleesMatch(
1740 CallTy Call, EdgeIter &EI,
1743 const FuncTy *ProfiledCalleeFunc = NodeToCallingFunc[Edge->Callee];
1744 const FuncTy *CallerFunc = NodeToCallingFunc[Edge->Caller];
1747 std::vector<std::pair<CallTy, FuncTy *>> FoundCalleeChain;
1748 if (!calleeMatchesFunc(Call, ProfiledCalleeFunc, CallerFunc,
1749 FoundCalleeChain)) {
1755 if (FoundCalleeChain.empty()) {
1760 auto AddEdge = [Edge, &EI](ContextNode *
Caller, ContextNode *
Callee) {
1761 auto *CurEdge =
Callee->findEdgeFromCaller(Caller);
1765 CurEdge->ContextIds.insert(Edge->ContextIds.begin(),
1766 Edge->ContextIds.end());
1767 CurEdge->AllocTypes |= Edge->AllocTypes;
1772 auto NewEdge = std::make_shared<ContextEdge>(
1773 Callee, Caller, Edge->AllocTypes, Edge->ContextIds);
1774 Callee->CallerEdges.push_back(NewEdge);
1775 if (Caller == Edge->Caller) {
1779 EI =
Caller->CalleeEdges.insert(EI, NewEdge);
1782 "Iterator position not restored after insert and increment");
1784 Caller->CalleeEdges.push_back(NewEdge);
1789 auto *CurCalleeNode = Edge->Callee;
1790 for (
auto &[NewCall, Func] : FoundCalleeChain) {
1791 ContextNode *NewNode =
nullptr;
1793 if (TailCallToContextNodeMap.
count(NewCall)) {
1794 NewNode = TailCallToContextNodeMap[NewCall];
1795 NewNode->ContextIds.
insert(Edge->ContextIds.begin(),
1796 Edge->ContextIds.end());
1797 NewNode->AllocTypes |= Edge->AllocTypes;
1799 FuncToCallsWithMetadata[
Func].push_back({NewCall});
1801 NodeOwner.push_back(
1802 std::make_unique<ContextNode>(
false, NewCall));
1803 NewNode = NodeOwner.back().get();
1804 NodeToCallingFunc[NewNode] =
Func;
1805 TailCallToContextNodeMap[NewCall] = NewNode;
1806 NewNode->ContextIds = Edge->ContextIds;
1807 NewNode->AllocTypes = Edge->AllocTypes;
1811 AddEdge(NewNode, CurCalleeNode);
1813 CurCalleeNode = NewNode;
1817 AddEdge(Edge->Caller, CurCalleeNode);
1820 Edge->Callee->eraseCallerEdge(Edge.get());
1821 EI = Edge->Caller->CalleeEdges.erase(EI);
1826bool ModuleCallsiteContextGraph::findProfiledCalleeThroughTailCalls(
1828 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain,
1829 bool &FoundMultipleCalleeChains) {
1836 FoundCalleeChain.push_back({Callsite,
F});
1839 auto *CalleeFunc = dyn_cast<Function>(CurCallee);
1841 auto *Alias = dyn_cast<GlobalAlias>(CurCallee);
1843 CalleeFunc = dyn_cast<Function>(Alias->getAliasee());
1851 bool FoundSingleCalleeChain =
false;
1852 for (
auto &BB : *CalleeFunc) {
1853 for (
auto &
I : BB) {
1854 auto *CB = dyn_cast<CallBase>(&
I);
1855 if (!CB || !CB->isTailCall())
1857 auto *CalledValue = CB->getCalledOperand();
1858 auto *CalledFunction = CB->getCalledFunction();
1859 if (CalledValue && !CalledFunction) {
1860 CalledValue = CalledValue->stripPointerCasts();
1862 CalledFunction = dyn_cast<Function>(CalledValue);
1866 if (
auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
1867 assert(!CalledFunction &&
1868 "Expected null called function in callsite for alias");
1869 CalledFunction = dyn_cast<Function>(GA->getAliaseeObject());
1871 if (!CalledFunction)
1873 if (CalledFunction == ProfiledCallee) {
1874 if (FoundSingleCalleeChain) {
1875 FoundMultipleCalleeChains =
true;
1878 FoundSingleCalleeChain =
true;
1879 FoundProfiledCalleeCount++;
1880 FoundProfiledCalleeDepth +=
Depth;
1881 if (
Depth > FoundProfiledCalleeMaxDepth)
1882 FoundProfiledCalleeMaxDepth =
Depth;
1883 SaveCallsiteInfo(&
I, CalleeFunc);
1884 }
else if (findProfiledCalleeThroughTailCalls(
1885 ProfiledCallee, CalledFunction,
Depth + 1,
1886 FoundCalleeChain, FoundMultipleCalleeChains)) {
1887 if (FoundMultipleCalleeChains)
1889 if (FoundSingleCalleeChain) {
1890 FoundMultipleCalleeChains =
true;
1893 FoundSingleCalleeChain =
true;
1894 SaveCallsiteInfo(&
I, CalleeFunc);
1899 return FoundSingleCalleeChain;
1902bool ModuleCallsiteContextGraph::calleeMatchesFunc(
1904 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain) {
1905 auto *CB = dyn_cast<CallBase>(Call);
1906 if (!CB->getCalledOperand())
1908 auto *CalleeVal = CB->getCalledOperand()->stripPointerCasts();
1909 auto *CalleeFunc = dyn_cast<Function>(CalleeVal);
1910 if (CalleeFunc == Func)
1912 auto *Alias = dyn_cast<GlobalAlias>(CalleeVal);
1913 if (Alias && Alias->getAliasee() == Func)
1924 bool FoundMultipleCalleeChains =
false;
1925 if (!findProfiledCalleeThroughTailCalls(Func, CalleeVal,
Depth,
1927 FoundMultipleCalleeChains)) {
1928 LLVM_DEBUG(
dbgs() <<
"Not found through unique tail call chain: "
1929 <<
Func->getName() <<
" from " << CallerFunc->
getName()
1930 <<
" that actually called " << CalleeVal->getName()
1931 << (FoundMultipleCalleeChains
1932 ?
" (found multiple possible chains)"
1935 if (FoundMultipleCalleeChains)
1936 FoundProfiledCalleeNonUniquelyCount++;
1943bool IndexCallsiteContextGraph::findProfiledCalleeThroughTailCalls(
1945 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain,
1946 bool &FoundMultipleCalleeChains) {
1955 if (!FunctionCalleesToSynthesizedCallsiteInfos.count(FS) ||
1956 !FunctionCalleesToSynthesizedCallsiteInfos[
FS].count(Callee))
1959 FunctionCalleesToSynthesizedCallsiteInfos[FS][Callee] =
1962 FunctionCalleesToSynthesizedCallsiteInfos[
FS][
Callee].get();
1963 FoundCalleeChain.push_back({NewCallsiteInfo,
FS});
1970 bool FoundSingleCalleeChain =
false;
1973 !isPrevailing(CurCallee.
getGUID(), S.get()))
1975 auto *
FS = dyn_cast<FunctionSummary>(S->getBaseObject());
1978 auto FSVI = CurCallee;
1979 auto *AS = dyn_cast<AliasSummary>(S.get());
1981 FSVI = AS->getAliaseeVI();
1982 for (
auto &CallEdge :
FS->calls()) {
1983 if (!CallEdge.second.hasTailCall())
1985 if (CallEdge.first == ProfiledCallee) {
1986 if (FoundSingleCalleeChain) {
1987 FoundMultipleCalleeChains =
true;
1990 FoundSingleCalleeChain =
true;
1991 FoundProfiledCalleeCount++;
1992 FoundProfiledCalleeDepth +=
Depth;
1993 if (
Depth > FoundProfiledCalleeMaxDepth)
1994 FoundProfiledCalleeMaxDepth =
Depth;
1995 CreateAndSaveCallsiteInfo(CallEdge.first, FS);
1997 assert(!FSToVIMap.count(FS) || FSToVIMap[FS] == FSVI);
1998 FSToVIMap[
FS] = FSVI;
1999 }
else if (findProfiledCalleeThroughTailCalls(
2000 ProfiledCallee, CallEdge.first,
Depth + 1,
2001 FoundCalleeChain, FoundMultipleCalleeChains)) {
2002 if (FoundMultipleCalleeChains)
2004 if (FoundSingleCalleeChain) {
2005 FoundMultipleCalleeChains =
true;
2008 FoundSingleCalleeChain =
true;
2009 CreateAndSaveCallsiteInfo(CallEdge.first, FS);
2011 assert(!FSToVIMap.count(FS) || FSToVIMap[FS] == FSVI);
2012 FSToVIMap[
FS] = FSVI;
2017 return FoundSingleCalleeChain;
2020bool IndexCallsiteContextGraph::calleeMatchesFunc(
2023 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain) {
2025 dyn_cast_if_present<CallsiteInfo *>(
Call.getBase())->Callee;
2029 Callee.getSummaryList().empty()
2031 : dyn_cast<AliasSummary>(
Callee.getSummaryList()[0].get());
2032 assert(FSToVIMap.count(Func));
2033 auto FuncVI = FSToVIMap[
Func];
2034 if (Callee == FuncVI ||
2049 bool FoundMultipleCalleeChains =
false;
2050 if (!findProfiledCalleeThroughTailCalls(
2051 FuncVI, Callee,
Depth, FoundCalleeChain, FoundMultipleCalleeChains)) {
2052 LLVM_DEBUG(
dbgs() <<
"Not found through unique tail call chain: " << FuncVI
2053 <<
" from " << FSToVIMap[CallerFunc]
2054 <<
" that actually called " << Callee
2055 << (FoundMultipleCalleeChains
2056 ?
" (found multiple possible chains)"
2059 if (FoundMultipleCalleeChains)
2060 FoundProfiledCalleeNonUniquelyCount++;
2071 if (AllocTypes & (uint8_t)AllocationType::NotCold)
2073 if (AllocTypes & (uint8_t)AllocationType::Cold)
2078template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2079void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::dump()
2085template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2086void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::print(
2088 OS <<
"Node " <<
this <<
"\n";
2092 OS <<
" (recursive)";
2095 OS <<
"\tContextIds:";
2096 std::vector<uint32_t> SortedIds(ContextIds.begin(), ContextIds.end());
2097 std::sort(SortedIds.begin(), SortedIds.end());
2098 for (
auto Id : SortedIds)
2101 OS <<
"\tCalleeEdges:\n";
2102 for (
auto &Edge : CalleeEdges)
2103 OS <<
"\t\t" << *Edge <<
"\n";
2104 OS <<
"\tCallerEdges:\n";
2105 for (
auto &Edge : CallerEdges)
2106 OS <<
"\t\t" << *Edge <<
"\n";
2107 if (!Clones.empty()) {
2110 for (
auto *Clone : Clones)
2113 }
else if (CloneOf) {
2114 OS <<
"\tClone of " << CloneOf <<
"\n";
2118template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2119void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge::dump()
2125template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2126void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge::print(
2130 OS <<
" ContextIds:";
2131 std::vector<uint32_t> SortedIds(ContextIds.begin(), ContextIds.end());
2132 std::sort(SortedIds.begin(), SortedIds.end());
2133 for (
auto Id : SortedIds)
2137template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2138void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::dump()
const {
2142template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2143void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::print(
2145 OS <<
"Callsite Context Graph:\n";
2146 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
2147 for (
const auto Node : nodes<GraphType>(
this)) {
2148 if (
Node->isRemoved())
2155template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2157 const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &Edge) {
2160 assert(Edge->AllocTypes != (uint8_t)AllocationType::None);
2161 assert(!Edge->ContextIds.empty());
2164template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2166 bool CheckEdges =
true) {
2167 if (
Node->isRemoved())
2171 if (
Node->CallerEdges.size()) {
2172 auto EI =
Node->CallerEdges.begin();
2173 auto &FirstEdge = *EI;
2176 for (; EI !=
Node->CallerEdges.end(); EI++) {
2177 const auto &Edge = *EI;
2179 checkEdge<DerivedCCG, FuncTy, CallTy>(Edge);
2180 set_union(CallerEdgeContextIds, Edge->ContextIds);
2184 assert(
Node->ContextIds == CallerEdgeContextIds ||
2187 if (
Node->CalleeEdges.size()) {
2188 auto EI =
Node->CalleeEdges.begin();
2189 auto &FirstEdge = *EI;
2192 for (; EI !=
Node->CalleeEdges.end(); EI++) {
2193 const auto &Edge = *EI;
2195 checkEdge<DerivedCCG, FuncTy, CallTy>(Edge);
2196 set_union(CalleeEdgeContextIds, Edge->ContextIds);
2198 assert(
Node->ContextIds == CalleeEdgeContextIds);
2202template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2203void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::check()
const {
2204 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
2205 for (
const auto Node : nodes<GraphType>(
this)) {
2206 checkNode<DerivedCCG, FuncTy, CallTy>(
Node,
false);
2207 for (
auto &Edge :
Node->CallerEdges)
2208 checkEdge<DerivedCCG, FuncTy, CallTy>(Edge);
2212template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2214 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
2215 using NodeRef =
const ContextNode<DerivedCCG, FuncTy, CallTy> *;
2217 using NodePtrTy = std::unique_ptr<ContextNode<DerivedCCG, FuncTy, CallTy>>;
2222 decltype(&getNode)>;
2233 return G->NodeOwner.begin()->get();
2236 using EdgePtrTy = std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>>;
2237 static const ContextNode<DerivedCCG, FuncTy, CallTy> *
2245 decltype(&GetCallee)>;
2256template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2261 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
2267 std::string LabelString =
2268 (
Twine(
"OrigId: ") + (Node->IsAllocation ?
"Alloc" :
"") +
2269 Twine(Node->OrigStackOrAllocId))
2271 LabelString +=
"\n";
2272 if (Node->hasCall()) {
2273 auto Func =
G->NodeToCallingFunc.find(Node);
2274 assert(Func !=
G->NodeToCallingFunc.end());
2276 G->getLabel(Func->second, Node->Call.call(), Node->Call.cloneNo());
2278 LabelString +=
"null call";
2279 if (Node->Recursive)
2280 LabelString +=
" (recursive)";
2282 LabelString +=
" (external)";
2289 getContextIds(Node->ContextIds) +
"\"")
2292 (
Twine(
",fillcolor=\"") + getColor(Node->AllocTypes) +
"\"").str();
2294 if (Node->CloneOf) {
2304 auto &Edge = *(ChildIter.getCurrent());
2305 return (
Twine(
"tooltip=\"") + getContextIds(Edge->ContextIds) +
"\"" +
2306 Twine(
",fillcolor=\"") + getColor(Edge->AllocTypes) +
"\"")
2313 return Node->isRemoved();
2318 std::string IdString =
"ContextIds:";
2319 if (ContextIds.
size() < 100) {
2320 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
2321 std::sort(SortedIds.begin(), SortedIds.end());
2322 for (
auto Id : SortedIds)
2323 IdString += (
" " +
Twine(Id)).str();
2325 IdString += (
" (" +
Twine(ContextIds.
size()) +
" ids)").str();
2330 static std::string getColor(uint8_t AllocTypes) {
2339 return "mediumorchid1";
2343 static std::string getNodeId(NodeRef
Node) {
2344 std::stringstream SStream;
2345 SStream << std::hex <<
"N0x" << (
unsigned long long)
Node;
2346 std::string
Result = SStream.str();
2351template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2352void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::exportToDot(
2353 std::string Label)
const {
2358template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2359typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
2360CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::moveEdgeToNewCalleeClone(
2361 const std::shared_ptr<ContextEdge> &Edge, EdgeIter *CallerEdgeI) {
2362 ContextNode *
Node = Edge->Callee;
2363 NodeOwner.push_back(
2364 std::make_unique<ContextNode>(
Node->IsAllocation,
Node->Call));
2365 ContextNode *Clone = NodeOwner.back().get();
2366 Node->addClone(Clone);
2368 NodeToCallingFunc[Clone] = NodeToCallingFunc[
Node];
2369 moveEdgeToExistingCalleeClone(Edge, Clone, CallerEdgeI,
true);
2373template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2374void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
2375 moveEdgeToExistingCalleeClone(
const std::shared_ptr<ContextEdge> &Edge,
2376 ContextNode *NewCallee, EdgeIter *CallerEdgeI,
2380 assert(NewCallee->getOrigNode() == Edge->Callee->getOrigNode());
2381 auto &EdgeContextIds = Edge->getContextIds();
2382 ContextNode *OldCallee = Edge->Callee;
2384 *CallerEdgeI = OldCallee->CallerEdges.erase(*CallerEdgeI);
2386 OldCallee->eraseCallerEdge(Edge.get());
2387 Edge->Callee = NewCallee;
2388 NewCallee->CallerEdges.push_back(Edge);
2392 NewCallee->ContextIds.insert(EdgeContextIds.begin(), EdgeContextIds.end());
2393 NewCallee->AllocTypes |= Edge->AllocTypes;
2394 OldCallee->AllocTypes = computeAllocType(OldCallee->ContextIds);
2397 OldCallee->ContextIds.empty());
2401 for (
auto &OldCalleeEdge : OldCallee->CalleeEdges) {
2406 set_subtract(OldCalleeEdge->getContextIds(), EdgeContextIdsToMove);
2407 OldCalleeEdge->AllocTypes =
2408 computeAllocType(OldCalleeEdge->getContextIds());
2415 if (
auto *NewCalleeEdge =
2416 NewCallee->findEdgeFromCallee(OldCalleeEdge->Callee)) {
2417 NewCalleeEdge->getContextIds().insert(EdgeContextIdsToMove.
begin(),
2418 EdgeContextIdsToMove.
end());
2419 NewCalleeEdge->AllocTypes |= computeAllocType(EdgeContextIdsToMove);
2423 auto NewEdge = std::make_shared<ContextEdge>(
2424 OldCalleeEdge->Callee, NewCallee,
2425 computeAllocType(EdgeContextIdsToMove), EdgeContextIdsToMove);
2426 NewCallee->CalleeEdges.push_back(NewEdge);
2427 NewEdge->Callee->CallerEdges.push_back(NewEdge);
2430 checkNode<DerivedCCG, FuncTy, CallTy>(OldCallee,
false);
2431 checkNode<DerivedCCG, FuncTy, CallTy>(NewCallee,
false);
2432 for (
const auto &OldCalleeEdge : OldCallee->CalleeEdges)
2433 checkNode<DerivedCCG, FuncTy, CallTy>(OldCalleeEdge->Callee,
2435 for (
const auto &NewCalleeEdge : NewCallee->CalleeEdges)
2436 checkNode<DerivedCCG, FuncTy, CallTy>(NewCalleeEdge->Callee,
2441template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2442void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
2443 recursivelyRemoveNoneTypeCalleeEdges(
2449 removeNoneTypeCalleeEdges(
Node);
2451 for (
auto *Clone :
Node->Clones)
2452 recursivelyRemoveNoneTypeCalleeEdges(Clone, Visited);
2456 auto CallerEdges =
Node->CallerEdges;
2457 for (
auto &Edge : CallerEdges) {
2459 if (Edge->Callee ==
nullptr && Edge->Caller ==
nullptr) {
2460 assert(!std::count(
Node->CallerEdges.begin(),
Node->CallerEdges.end(),
2464 recursivelyRemoveNoneTypeCalleeEdges(Edge->Caller, Visited);
2468template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2469void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones() {
2471 for (
auto &Entry : AllocationCallToContextNodeMap)
2472 identifyClones(Entry.second, Visited);
2474 for (
auto &Entry : AllocationCallToContextNodeMap)
2475 recursivelyRemoveNoneTypeCalleeEdges(Entry.second, Visited);
2488template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2489void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones(
2492 checkNode<DerivedCCG, FuncTy, CallTy>(
Node,
false);
2500 if (!
Node->hasCall())
2515 auto CallerEdges =
Node->CallerEdges;
2516 for (
auto &Edge : CallerEdges) {
2518 if (Edge->Callee ==
nullptr && Edge->Caller ==
nullptr) {
2523 if (!Visited.
count(Edge->Caller) && !Edge->Caller->CloneOf) {
2524 identifyClones(Edge->Caller, Visited);
2547 const unsigned AllocTypeCloningPriority[] = { 3, 4,
2550 std::stable_sort(
Node->CallerEdges.begin(),
Node->CallerEdges.end(),
2551 [&](
const std::shared_ptr<ContextEdge> &
A,
2552 const std::shared_ptr<ContextEdge> &
B) {
2555 if (A->ContextIds.empty())
2561 if (B->ContextIds.empty())
2564 if (A->AllocTypes == B->AllocTypes)
2567 return *A->ContextIds.begin() < *B->ContextIds.begin();
2568 return AllocTypeCloningPriority[A->AllocTypes] <
2569 AllocTypeCloningPriority[B->AllocTypes];
2579 for (
auto EI =
Node->CallerEdges.begin(); EI !=
Node->CallerEdges.end();) {
2580 auto CallerEdge = *EI;
2589 std::vector<uint8_t> CalleeEdgeAllocTypesForCallerEdge;
2590 CalleeEdgeAllocTypesForCallerEdge.reserve(
Node->CalleeEdges.size());
2591 for (
auto &CalleeEdge :
Node->CalleeEdges)
2592 CalleeEdgeAllocTypesForCallerEdge.push_back(intersectAllocTypes(
2593 CalleeEdge->getContextIds(), CallerEdge->getContextIds()));
2608 if (allocTypeToUse(CallerEdge->AllocTypes) ==
2609 allocTypeToUse(
Node->AllocTypes) &&
2610 allocTypesMatch<DerivedCCG, FuncTy, CallTy>(
2611 CalleeEdgeAllocTypesForCallerEdge,
Node->CalleeEdges)) {
2618 ContextNode *Clone =
nullptr;
2619 for (
auto *CurClone :
Node->Clones) {
2620 if (allocTypeToUse(CurClone->AllocTypes) !=
2621 allocTypeToUse(CallerEdge->AllocTypes))
2624 if (!allocTypesMatch<DerivedCCG, FuncTy, CallTy>(
2625 CalleeEdgeAllocTypesForCallerEdge, CurClone->CalleeEdges))
2633 moveEdgeToExistingCalleeClone(CallerEdge, Clone, &EI);
2635 Clone = moveEdgeToNewCalleeClone(CallerEdge, &EI);
2650 checkNode<DerivedCCG, FuncTy, CallTy>(
Node,
false);
2653void ModuleCallsiteContextGraph::updateAllocationCall(
2657 "memprof", AllocTypeString);
2658 cast<CallBase>(
Call.call())->addFnAttr(
A);
2659 OREGetter(
Call.call()->getFunction())
2661 <<
ore::NV(
"AllocationCall",
Call.call()) <<
" in clone "
2663 <<
" marked with memprof allocation attribute "
2664 <<
ore::NV(
"Attribute", AllocTypeString));
2667void IndexCallsiteContextGraph::updateAllocationCall(
CallInfo &Call,
2671 assert(AI->Versions.size() >
Call.cloneNo());
2675void ModuleCallsiteContextGraph::updateCall(
CallInfo &CallerCall,
2676 FuncInfo CalleeFunc) {
2677 if (CalleeFunc.cloneNo() > 0)
2678 cast<CallBase>(CallerCall.call())->setCalledFunction(CalleeFunc.func());
2679 OREGetter(CallerCall.call()->getFunction())
2681 <<
ore::NV(
"Call", CallerCall.call()) <<
" in clone "
2682 <<
ore::NV(
"Caller", CallerCall.call()->getFunction())
2683 <<
" assigned to call function clone "
2684 <<
ore::NV(
"Callee", CalleeFunc.func()));
2687void IndexCallsiteContextGraph::updateCall(
CallInfo &CallerCall,
2688 FuncInfo CalleeFunc) {
2689 auto *CI = CallerCall.call().dyn_cast<
CallsiteInfo *>();
2691 "Caller cannot be an allocation which should not have profiled calls");
2692 assert(CI->Clones.size() > CallerCall.cloneNo());
2693 CI->Clones[CallerCall.cloneNo()] = CalleeFunc.cloneNo();
2696CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
2698ModuleCallsiteContextGraph::cloneFunctionForCallsite(
2699 FuncInfo &Func,
CallInfo &Call, std::map<CallInfo, CallInfo> &CallMap,
2700 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
2706 NewFunc->setName(
Name);
2707 for (
auto &Inst : CallsWithMetadataInFunc) {
2709 assert(Inst.cloneNo() == 0);
2710 CallMap[Inst] = {cast<Instruction>(VMap[Inst.call()]), CloneNo};
2712 OREGetter(
Func.func())
2714 <<
"created clone " <<
ore::NV(
"NewFunction", NewFunc));
2715 return {NewFunc, CloneNo};
2719 IndexCall>::FuncInfo
2720IndexCallsiteContextGraph::cloneFunctionForCallsite(
2721 FuncInfo &Func,
CallInfo &Call, std::map<CallInfo, CallInfo> &CallMap,
2722 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
2737 for (
auto &Inst : CallsWithMetadataInFunc) {
2739 assert(Inst.cloneNo() == 0);
2740 if (
auto *AI = Inst.call().dyn_cast<
AllocInfo *>()) {
2741 assert(AI->Versions.size() == CloneNo);
2744 AI->Versions.push_back(0);
2747 assert(CI && CI->Clones.size() == CloneNo);
2750 CI->Clones.push_back(0);
2752 CallMap[Inst] = {Inst.call(), CloneNo};
2754 return {
Func.func(), CloneNo};
2788template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2789bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::assignFunctions() {
2790 bool Changed =
false;
2798 auto RecordCalleeFuncOfCallsite = [&](ContextNode *
Caller,
2799 const FuncInfo &CalleeFunc) {
2801 CallsiteToCalleeFuncCloneMap[
Caller] = CalleeFunc;
2806 for (
auto &[Func, CallsWithMetadata] : FuncToCallsWithMetadata) {
2807 FuncInfo OrigFunc(Func);
2811 std::map<FuncInfo, std::map<CallInfo, CallInfo>> FuncClonesToCallMap;
2812 for (
auto &Call : CallsWithMetadata) {
2813 ContextNode *
Node = getNodeForInst(Call);
2820 "Not having a call should have prevented cloning");
2824 std::map<FuncInfo, ContextNode *> FuncCloneToCurNodeCloneMap;
2828 auto AssignCallsiteCloneToFuncClone = [&](
const FuncInfo &FuncClone,
2830 ContextNode *CallsiteClone,
2833 FuncCloneToCurNodeCloneMap[FuncClone] = CallsiteClone;
2835 assert(FuncClonesToCallMap.count(FuncClone));
2836 std::map<CallInfo, CallInfo> &CallMap = FuncClonesToCallMap[FuncClone];
2838 if (CallMap.count(Call))
2839 CallClone = CallMap[
Call];
2840 CallsiteClone->setCall(CallClone);
2846 std::deque<ContextNode *> ClonesWorklist;
2848 if (!
Node->ContextIds.empty())
2849 ClonesWorklist.push_back(
Node);
2850 ClonesWorklist.insert(ClonesWorklist.end(),
Node->Clones.begin(),
2851 Node->Clones.end());
2856 unsigned NodeCloneCount = 0;
2857 while (!ClonesWorklist.empty()) {
2858 ContextNode *Clone = ClonesWorklist.front();
2859 ClonesWorklist.pop_front();
2862 checkNode<DerivedCCG, FuncTy, CallTy>(Clone);
2868 if (FuncClonesToCallMap.size() < NodeCloneCount) {
2870 if (NodeCloneCount == 1) {
2875 Clone->CallerEdges, [&](
const std::shared_ptr<ContextEdge> &E) {
2876 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
2880 FuncClonesToCallMap[OrigFunc] = {};
2881 AssignCallsiteCloneToFuncClone(
2882 OrigFunc, Call, Clone,
2883 AllocationCallToContextNodeMap.count(Call));
2884 for (
auto &CE : Clone->CallerEdges) {
2886 if (!
CE->Caller->hasCall())
2888 RecordCalleeFuncOfCallsite(
CE->Caller, OrigFunc);
2898 FuncInfo PreviousAssignedFuncClone;
2900 Clone->CallerEdges, [&](
const std::shared_ptr<ContextEdge> &E) {
2901 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
2903 bool CallerAssignedToCloneOfFunc =
false;
2904 if (EI != Clone->CallerEdges.end()) {
2905 const std::shared_ptr<ContextEdge> &Edge = *EI;
2906 PreviousAssignedFuncClone =
2907 CallsiteToCalleeFuncCloneMap[Edge->Caller];
2908 CallerAssignedToCloneOfFunc =
true;
2913 std::map<CallInfo, CallInfo> NewCallMap;
2914 unsigned CloneNo = FuncClonesToCallMap.size();
2915 assert(CloneNo > 0 &&
"Clone 0 is the original function, which "
2916 "should already exist in the map");
2917 FuncInfo NewFuncClone = cloneFunctionForCallsite(
2918 OrigFunc, Call, NewCallMap, CallsWithMetadata, CloneNo);
2919 FuncClonesToCallMap.emplace(NewFuncClone, std::move(NewCallMap));
2920 FunctionClonesAnalysis++;
2926 if (!CallerAssignedToCloneOfFunc) {
2927 AssignCallsiteCloneToFuncClone(
2928 NewFuncClone, Call, Clone,
2929 AllocationCallToContextNodeMap.count(Call));
2930 for (
auto &CE : Clone->CallerEdges) {
2932 if (!
CE->Caller->hasCall())
2934 RecordCalleeFuncOfCallsite(
CE->Caller, NewFuncClone);
2943 for (
auto CE : Clone->CallerEdges) {
2948 if (!
CE->Caller->hasCall())
2951 if (!CallsiteToCalleeFuncCloneMap.
count(
CE->Caller) ||
2955 CallsiteToCalleeFuncCloneMap[
CE->Caller] !=
2956 PreviousAssignedFuncClone)
2959 RecordCalleeFuncOfCallsite(
CE->Caller, NewFuncClone);
2969 for (
auto CalleeEdge :
CE->Caller->CalleeEdges) {
2974 ContextNode *
Callee = CalleeEdge->Callee;
2978 if (Callee == Clone || !
Callee->hasCall())
2980 ContextNode *NewClone = moveEdgeToNewCalleeClone(CalleeEdge);
2981 removeNoneTypeCalleeEdges(NewClone);
2984 removeNoneTypeCalleeEdges(Callee);
2989 if (CallsiteToCalleeFuncCloneMap.
count(Callee))
2990 RecordCalleeFuncOfCallsite(
2991 NewClone, CallsiteToCalleeFuncCloneMap[Callee]);
3000 OrigCall.setCloneNo(0);
3001 std::map<CallInfo, CallInfo> &CallMap =
3002 FuncClonesToCallMap[NewFuncClone];
3003 assert(CallMap.count(OrigCall));
3004 CallInfo NewCall(CallMap[OrigCall]);
3006 NewClone->setCall(NewCall);
3028 std::map<FuncInfo, ContextNode *> FuncCloneToNewCallsiteCloneMap;
3029 FuncInfo FuncCloneAssignedToCurCallsiteClone;
3032 for (
auto EI = Clone->CallerEdges.begin();
3033 EI != Clone->CallerEdges.end();) {
3036 if (!Edge->Caller->hasCall()) {
3042 if (CallsiteToCalleeFuncCloneMap.
count(Edge->Caller)) {
3043 FuncInfo FuncCloneCalledByCaller =
3044 CallsiteToCalleeFuncCloneMap[Edge->Caller];
3054 if ((FuncCloneToCurNodeCloneMap.count(FuncCloneCalledByCaller) &&
3055 FuncCloneToCurNodeCloneMap[FuncCloneCalledByCaller] !=
3063 (FuncCloneAssignedToCurCallsiteClone &&
3064 FuncCloneAssignedToCurCallsiteClone !=
3065 FuncCloneCalledByCaller)) {
3080 if (FuncCloneToNewCallsiteCloneMap.count(
3081 FuncCloneCalledByCaller)) {
3082 ContextNode *NewClone =
3083 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller];
3084 moveEdgeToExistingCalleeClone(Edge, NewClone, &EI);
3086 removeNoneTypeCalleeEdges(NewClone);
3089 ContextNode *NewClone = moveEdgeToNewCalleeClone(Edge, &EI);
3090 removeNoneTypeCalleeEdges(NewClone);
3091 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller] =
3094 ClonesWorklist.push_back(NewClone);
3095 assert(EI == Clone->CallerEdges.end() ||
3101 removeNoneTypeCalleeEdges(Clone);
3110 if (!FuncCloneAssignedToCurCallsiteClone) {
3111 FuncCloneAssignedToCurCallsiteClone = FuncCloneCalledByCaller;
3113 AssignCallsiteCloneToFuncClone(
3114 FuncCloneCalledByCaller, Call, Clone,
3115 AllocationCallToContextNodeMap.count(Call));
3119 assert(FuncCloneAssignedToCurCallsiteClone ==
3120 FuncCloneCalledByCaller);
3129 if (!FuncCloneAssignedToCurCallsiteClone) {
3134 for (
auto &CF : FuncClonesToCallMap) {
3135 if (!FuncCloneToCurNodeCloneMap.count(CF.first)) {
3136 FuncCloneAssignedToCurCallsiteClone = CF.first;
3140 assert(FuncCloneAssignedToCurCallsiteClone);
3142 AssignCallsiteCloneToFuncClone(
3143 FuncCloneAssignedToCurCallsiteClone, Call, Clone,
3144 AllocationCallToContextNodeMap.count(Call));
3146 assert(FuncCloneToCurNodeCloneMap
3147 [FuncCloneAssignedToCurCallsiteClone] == Clone);
3149 RecordCalleeFuncOfCallsite(Edge->Caller,
3150 FuncCloneAssignedToCurCallsiteClone);
3157 checkNode<DerivedCCG, FuncTy, CallTy>(
Node);
3158 for (
const auto &PE :
Node->CalleeEdges)
3159 checkNode<DerivedCCG, FuncTy, CallTy>(PE->Callee);
3160 for (
const auto &CE :
Node->CallerEdges)
3161 checkNode<DerivedCCG, FuncTy, CallTy>(
CE->Caller);
3162 for (
auto *Clone :
Node->Clones) {
3163 checkNode<DerivedCCG, FuncTy, CallTy>(Clone);
3164 for (
const auto &PE : Clone->CalleeEdges)
3165 checkNode<DerivedCCG, FuncTy, CallTy>(PE->Callee);
3166 for (
const auto &CE : Clone->CallerEdges)
3167 checkNode<DerivedCCG, FuncTy, CallTy>(
CE->Caller);
3173 auto UpdateCalls = [&](ContextNode *
Node,
3175 auto &&UpdateCalls) {
3180 for (
auto *Clone :
Node->Clones)
3181 UpdateCalls(Clone, Visited, UpdateCalls);
3183 for (
auto &Edge :
Node->CallerEdges)
3184 UpdateCalls(Edge->Caller, Visited, UpdateCalls);
3188 if (!
Node->hasCall() ||
Node->ContextIds.empty())
3191 if (
Node->IsAllocation) {
3192 updateAllocationCall(
Node->Call, allocTypeToUse(
Node->AllocTypes));
3196 if (!CallsiteToCalleeFuncCloneMap.
count(
Node))
3199 auto CalleeFunc = CallsiteToCalleeFuncCloneMap[
Node];
3200 updateCall(
Node->Call, CalleeFunc);
3209 for (
auto &Entry : AllocationCallToContextNodeMap)
3210 UpdateCalls(Entry.second, Visited, UpdateCalls);
3224 FunctionsClonedThinBackend++;
3225 for (
unsigned I = 1;
I < NumClones;
I++) {
3226 VMaps.
emplace_back(std::make_unique<ValueToValueMapTy>());
3228 FunctionClonesThinBackend++;
3231 for (
auto &BB : *NewF) {
3232 for (
auto &Inst : BB) {
3233 Inst.setMetadata(LLVMContext::MD_memprof,
nullptr);
3234 Inst.setMetadata(LLVMContext::MD_callsite,
nullptr);
3238 auto *PrevF = M.getFunction(
Name);
3242 assert(PrevF->isDeclaration());
3243 NewF->takeName(PrevF);
3244 PrevF->replaceAllUsesWith(NewF);
3245 PrevF->eraseFromParent();
3247 NewF->setName(
Name);
3249 <<
"created clone " <<
ore::NV(
"NewFunction", NewF));
3252 if (!FuncToAliasMap.count(&
F))
3254 for (
auto *
A : FuncToAliasMap[&
F]) {
3256 auto *PrevA = M.getNamedAlias(
Name);
3258 A->getType()->getPointerAddressSpace(),
3259 A->getLinkage(),
Name, NewF);
3260 NewA->copyAttributesFrom(
A);
3264 assert(PrevA->isDeclaration());
3265 NewA->takeName(PrevA);
3266 PrevA->replaceAllUsesWith(NewA);
3267 PrevA->eraseFromParent();
3309bool MemProfContextDisambiguation::applyImport(
Module &M) {
3311 bool Changed =
false;
3313 auto IsMemProfClone = [](
const Function &
F) {
3320 std::map<const Function *, SmallPtrSet<const GlobalAlias *, 1>>
3322 for (
auto &
A :
M.aliases()) {
3323 auto *Aliasee =
A.getAliaseeObject();
3324 if (
auto *
F = dyn_cast<Function>(Aliasee))
3325 FuncToAliasMap[
F].insert(&
A);
3329 if (
F.isDeclaration() || IsMemProfClone(
F))
3335 bool ClonesCreated =
false;
3336 unsigned NumClonesCreated = 0;
3337 auto CloneFuncIfNeeded = [&](
unsigned NumClones) {
3347 if (ClonesCreated) {
3348 assert(NumClonesCreated == NumClones);
3355 ClonesCreated =
true;
3356 NumClonesCreated = NumClones;
3366 assert(!IsMemProfClone(*CalledFunction));
3371 auto CalleeOrigName = CalledFunction->getName();
3372 for (
unsigned J = 0; J < StackNode.
Clones.
size(); J++) {
3375 if (!StackNode.
Clones[J])
3377 auto NewF =
M.getOrInsertFunction(
3379 CalledFunction->getFunctionType());
3385 CBClone = cast<CallBase>((*VMaps[J - 1])[CB]);
3388 <<
ore::NV(
"Call", CBClone) <<
" in clone "
3390 <<
" assigned to call function clone "
3391 <<
ore::NV(
"Callee", NewF.getCallee()));
3409 auto SrcModuleMD =
F.getMetadata(
"thinlto_src_module");
3411 "enable-import-metadata is needed to emit thinlto_src_module");
3413 dyn_cast<MDString>(SrcModuleMD->getOperand(0))->getString();
3415 if (GVS->modulePath() == SrcModule) {
3416 GVSummary = GVS.get();
3420 assert(GVSummary && GVSummary->modulePath() == SrcModule);
3425 if (isa<AliasSummary>(GVSummary))
3428 auto *
FS = cast<FunctionSummary>(GVSummary->getBaseObject());
3430 if (
FS->allocs().empty() &&
FS->callsites().empty())
3433 auto SI =
FS->callsites().begin();
3434 auto AI =
FS->allocs().begin();
3442 for (
auto CallsiteIt =
FS->callsites().rbegin();
3443 CallsiteIt !=
FS->callsites().rend(); CallsiteIt++) {
3444 auto &Callsite = *CallsiteIt;
3448 if (!Callsite.StackIdIndices.empty())
3450 MapTailCallCalleeVIToCallsite.
insert({Callsite.Callee, Callsite});
3456 for (
auto &BB :
F) {
3457 for (
auto &
I : BB) {
3458 auto *CB = dyn_cast<CallBase>(&
I);
3463 auto *CalledValue = CB->getCalledOperand();
3464 auto *CalledFunction = CB->getCalledFunction();
3465 if (CalledValue && !CalledFunction) {
3466 CalledValue = CalledValue->stripPointerCasts();
3468 CalledFunction = dyn_cast<Function>(CalledValue);
3472 if (
auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
3473 assert(!CalledFunction &&
3474 "Expected null called function in callsite for alias");
3475 CalledFunction = dyn_cast<Function>(GA->getAliaseeObject());
3479 I.getMetadata(LLVMContext::MD_callsite));
3480 auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof);
3484 if (CB->getAttributes().hasFnAttr(
"memprof")) {
3486 CB->getAttributes().getFnAttr(
"memprof").getValueAsString() ==
"cold"
3487 ? AllocTypeColdThinBackend++
3488 : AllocTypeNotColdThinBackend++;
3489 OrigAllocsThinBackend++;
3490 AllocVersionsThinBackend++;
3491 if (!MaxAllocVersionsThinBackend)
3492 MaxAllocVersionsThinBackend = 1;
3495 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
3502 auto &AllocNode = *(AI++);
3506 auto MIBIter = AllocNode.MIBs.begin();
3507 for (
auto &MDOp : MemProfMD->operands()) {
3508 assert(MIBIter != AllocNode.MIBs.end());
3510 MIBIter->StackIdIndices.begin();
3511 auto *MIBMD = cast<const MDNode>(MDOp);
3515 auto ContextIterBegin =
3519 (ContextIterBegin != StackContext.
end() &&
3520 *ContextIterBegin == 0)
3523 for (
auto ContextIter = ContextIterBegin;
3524 ContextIter != StackContext.
end(); ++ContextIter) {
3528 if (LastStackContextId == *ContextIter)
3530 LastStackContextId = *ContextIter;
3531 assert(StackIdIndexIter != MIBIter->StackIdIndices.end());
3540 CloneFuncIfNeeded(AllocNode.Versions.size());
3542 OrigAllocsThinBackend++;
3543 AllocVersionsThinBackend += AllocNode.Versions.size();
3544 if (MaxAllocVersionsThinBackend < AllocNode.Versions.size())
3545 MaxAllocVersionsThinBackend = AllocNode.Versions.size();
3552 if (AllocNode.Versions.size() == 1) {
3557 UnclonableAllocsThinBackend++;
3563 return Type == ((uint8_t)AllocationType::NotCold |
3564 (uint8_t)AllocationType::Cold);
3568 for (
unsigned J = 0; J < AllocNode.Versions.size(); J++) {
3574 : AllocTypeNotColdThinBackend++;
3586 CBClone = cast<CallBase>((*VMaps[J - 1])[CB]);
3589 <<
ore::NV(
"AllocationCall", CBClone) <<
" in clone "
3591 <<
" marked with memprof allocation attribute "
3592 <<
ore::NV(
"Attribute", AllocTypeString));
3594 }
else if (!CallsiteContext.empty()) {
3596 assert(SI !=
FS->callsites().end());
3597 auto &StackNode = *(
SI++);
3603 for (
auto StackId : CallsiteContext) {
3611 CloneCallsite(StackNode, CB, CalledFunction);
3612 }
else if (CB->isTailCall()) {
3617 if (CalleeVI && MapTailCallCalleeVIToCallsite.
count(CalleeVI)) {
3618 auto Callsite = MapTailCallCalleeVIToCallsite.
find(CalleeVI);
3619 assert(Callsite != MapTailCallCalleeVIToCallsite.
end());
3620 CloneCallsite(Callsite->second, CB, CalledFunction);
3624 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
3625 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
3633template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3634bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::process() {
3636 dbgs() <<
"CCG before cloning:\n";
3640 exportToDot(
"postbuild");
3653 dbgs() <<
"CCG after cloning:\n";
3657 exportToDot(
"cloned");
3659 bool Changed = assignFunctions();
3662 dbgs() <<
"CCG after assigning function clones:\n";
3666 exportToDot(
"clonefuncassign");
3671bool MemProfContextDisambiguation::processModule(
3678 return applyImport(M);
3691 ModuleCallsiteContextGraph CCG(M, OREGetter);
3692 return CCG.process();
3697 : ImportSummary(Summary) {
3698 if (ImportSummary) {
3708 auto ReadSummaryFile =
3710 if (!ReadSummaryFile) {
3717 if (!ImportSummaryForTestingOrErr) {
3723 ImportSummaryForTesting = std::move(*ImportSummaryForTestingOrErr);
3724 ImportSummary = ImportSummaryForTesting.get();
3733 if (!processModule(M, OREGetter))
3750 IndexCallsiteContextGraph CCG(
Index, isPrevailing);
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")
#define LLVM_ATTRIBUTE_UNUSED
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
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 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)
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."))
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...
Module.h This file contains the declarations for the Module class.
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
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.
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.
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.
Function summary information to aid decisions and implementation of importing.
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)
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.
This class implements a map that also provides access to all stored values in a deterministic order.
size_type count(const KeyT &Key) const
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
MemProfContextDisambiguation(const ModuleSummaryIndex *Summary=nullptr)
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 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)
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 swap(DenseSetImpl &RHS)
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.
StringRef AttributeString(unsigned Attribute)
@ 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.
NodeAddr< FuncNode * > Func
This is an optimization pass for GlobalISel generic memory operations.
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.
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<>...
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.
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.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Expected< T > errorOrToExpected(ErrorOr< T > &&EO)
Convert an ErrorOr<T> to an Expected<T>.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
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...
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 > StackIdIndices
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