52#define DEBUG_TYPE "memprof-context-disambiguation"
55 "Number of function clones created during whole program analysis");
57 "Number of function clones created during ThinLTO backend");
59 "Number of functions that had clones created during ThinLTO backend");
60STATISTIC(AllocTypeNotCold,
"Number of not cold static allocations (possibly "
61 "cloned) during whole program analysis");
62STATISTIC(AllocTypeCold,
"Number of cold static allocations (possibly cloned) "
63 "during whole program analysis");
65 "Number of not cold static allocations (possibly cloned) during "
67STATISTIC(AllocTypeColdThinBackend,
"Number of cold static allocations "
68 "(possibly cloned) during ThinLTO backend");
70 "Number of original (not cloned) allocations with memprof profiles "
71 "during ThinLTO backend");
73 AllocVersionsThinBackend,
74 "Number of allocation versions (including clones) during ThinLTO backend");
76 "Maximum number of allocation versions created for an original "
77 "allocation during ThinLTO backend");
79 "Number of unclonable ambigous allocations during ThinLTO backend");
84 cl::desc(
"Specify the path prefix of the MemProf dot files."));
88 cl::desc(
"Export graph to dot files."));
92 cl::desc(
"Dump CallingContextGraph to stdout after each stage."));
96 cl::desc(
"Perform verification checks on CallingContextGraph."));
100 cl::desc(
"Perform frequent verification checks on nodes."));
103 "memprof-import-summary",
104 cl::desc(
"Import summary to use for testing the ThinLTO backend via opt"),
111 cl::desc(
"Linking with hot/cold operator new interfaces"));
127template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
166 :
public std::pair<FuncTy *, unsigned > {
167 using Base = std::pair<FuncTy *, unsigned>;
170 explicit operator bool()
const {
return this->first !=
nullptr; }
171 FuncTy *
func()
const {
return this->first; }
172 unsigned cloneNo()
const {
return this->second; }
176 struct CallInfo final :
public std::pair<CallTy, unsigned > {
177 using Base = std::pair<CallTy, unsigned>;
179 CallInfo(CallTy Call =
nullptr,
unsigned CloneNo = 0)
180 :
Base(Call, CloneNo) {}
181 explicit operator bool()
const {
return (
bool)this->first; }
182 CallTy
call()
const {
return this->first; }
183 unsigned cloneNo()
const {
return this->second; }
186 if (!
operator bool()) {
273 unsigned int ContextId);
339 template <
class NodeT,
class IteratorT>
340 std::vector<uint64_t>
348 template <
class NodeT,
class IteratorT>
365 std::vector<std::pair<FuncTy *, std::vector<CallInfo>>>
372 using EdgeIter =
typename std::vector<std::shared_ptr<ContextEdge>>::iterator;
374 using CallContextInfo = std::tuple<CallTy, std::vector<uint64_t>,
383 void assignStackNodesPostOrder(
395 void propagateDuplicateContextIds(
408 return static_cast<const DerivedCCG *
>(
this)->getStackId(IdOrIndex);
412 bool calleeMatchesFunc(CallTy Call,
const FuncTy *Func) {
413 return static_cast<DerivedCCG *
>(
this)->calleeMatchesFunc(Call, Func);
418 std::vector<uint64_t> getStackIdsWithContextNodesForCall(CallTy Call) {
419 return static_cast<DerivedCCG *
>(
this)->getStackIdsWithContextNodesForCall(
424 uint64_t getLastStackId(CallTy Call) {
425 return static_cast<DerivedCCG *
>(
this)->getLastStackId(Call);
430 AllocType == AllocationType::Cold ? AllocTypeCold++ : AllocTypeNotCold++;
431 static_cast<DerivedCCG *
>(
this)->updateAllocationCall(Call,
AllocType);
437 static_cast<DerivedCCG *
>(
this)->updateCall(CallerCall, CalleeFunc);
445 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
446 return static_cast<DerivedCCG *
>(
this)->cloneFunctionForCallsite(
447 Func, Call, CallMap, CallsWithMetadataInFunc, CloneNo);
452 std::string getLabel(
const FuncTy *Func,
const CallTy Call,
453 unsigned CloneNo)
const {
454 return static_cast<const DerivedCCG *
>(
this)->getLabel(Func, Call, CloneNo);
463 void unsetNodeForInst(
const CallInfo &
C);
485 moveEdgeToNewCalleeClone(
const std::shared_ptr<ContextEdge> &Edge,
486 EdgeIter *CallerEdgeI =
nullptr);
492 void moveEdgeToExistingCalleeClone(
const std::shared_ptr<ContextEdge> &Edge,
494 EdgeIter *CallerEdgeI =
nullptr,
495 bool NewClone =
false);
504 std::map<uint32_t, AllocationType> ContextIdToAllocationType;
510 std::map<uint64_t, ContextNode *> StackEntryIdToContextNodeMap;
517 std::vector<std::unique_ptr<ContextNode>> NodeOwner;
523 unsigned int LastContextId = 0;
526template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
529template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
532template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
535template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
555 std::vector<uint64_t> getStackIdsWithContextNodesForCall(
Instruction *Call);
561 std::map<CallInfo, CallInfo> &CallMap,
562 std::vector<CallInfo> &CallsWithMetadataInFunc,
565 unsigned CloneNo)
const;
586 if (
auto *AI = llvm::dyn_cast_if_present<AllocInfo *>(
getBase())) {
589 auto *CI = llvm::dyn_cast_if_present<CallsiteInfo *>(
getBase());
613 std::vector<uint64_t> getStackIdsWithContextNodesForCall(
IndexCall &Call);
619 std::map<CallInfo, CallInfo> &CallMap,
620 std::vector<CallInfo> &CallsWithMetadataInFunc,
623 unsigned CloneNo)
const;
627 std::map<const FunctionSummary *, ValueInfo> FSToVIMap;
640 :
public DenseMapInfo<std::pair<IndexCall, unsigned>> {};
643 :
public DenseMapInfo<PointerUnion<CallsiteInfo *, AllocInfo *>> {};
648struct FieldSeparator {
652 FieldSeparator(
const char *Sep =
", ") : Sep(Sep) {}
669 assert(AllocTypes != (uint8_t)AllocationType::None);
671 ((uint8_t)AllocationType::NotCold | (uint8_t)AllocationType::Cold))
672 return AllocationType::NotCold;
680template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
682 const std::vector<uint8_t> &InAllocTypes,
686 InAllocTypes.begin(), InAllocTypes.end(), Edges.begin(),
692 if (l == (uint8_t)AllocationType::None ||
693 r->AllocTypes == (uint8_t)AllocationType::None)
695 return allocTypeToUse(l) == allocTypeToUse(r->AllocTypes);
701template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
709 auto NonAllocCallNode = NonAllocationCallToContextNodeMap.find(
C);
710 if (NonAllocCallNode != NonAllocationCallToContextNodeMap.end()) {
711 return NonAllocCallNode->second;
716template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
720 auto AllocCallNode = AllocationCallToContextNodeMap.find(
C);
721 if (AllocCallNode != AllocationCallToContextNodeMap.end()) {
722 return AllocCallNode->second;
727template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
731 auto StackEntryNode = StackEntryIdToContextNodeMap.find(StackId);
732 if (StackEntryNode != StackEntryIdToContextNodeMap.end())
733 return StackEntryNode->second;
737template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
740 AllocationCallToContextNodeMap.erase(
C) ||
741 NonAllocationCallToContextNodeMap.erase(
C);
742 assert(!AllocationCallToContextNodeMap.count(
C) &&
743 !NonAllocationCallToContextNodeMap.count(
C));
746template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
749 unsigned int ContextId) {
751 if (Edge->Caller == Caller) {
753 Edge->getContextIds().insert(ContextId);
757 std::shared_ptr<ContextEdge> Edge = std::make_shared<ContextEdge>(
760 Caller->CalleeEdges.push_back(Edge);
763template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
766 for (
auto EI = Node->CalleeEdges.begin(); EI != Node->CalleeEdges.end();) {
768 if (Edge->AllocTypes == (uint8_t)AllocationType::None) {
769 assert(Edge->ContextIds.empty());
770 Edge->Callee->eraseCallerEdge(Edge.get());
771 EI = Node->CalleeEdges.erase(EI);
777template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
781 for (
const auto &Edge : CalleeEdges)
782 if (Edge->Callee ==
Callee)
787template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
791 for (
const auto &Edge : CallerEdges)
792 if (Edge->Caller == Caller)
797template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
801 std::find_if(CalleeEdges.begin(), CalleeEdges.end(),
802 [Edge](
const std::shared_ptr<ContextEdge> &CalleeEdge) {
803 return CalleeEdge.get() == Edge;
805 assert(EI != CalleeEdges.end());
806 CalleeEdges.erase(EI);
809template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
813 std::find_if(CallerEdges.begin(), CallerEdges.end(),
814 [Edge](
const std::shared_ptr<ContextEdge> &CallerEdge) {
815 return CallerEdge.get() == Edge;
817 assert(EI != CallerEdges.end());
818 CallerEdges.erase(EI);
821template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
825 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
826 uint8_t
AllocType = (uint8_t)AllocationType::None;
827 for (
auto Id : ContextIds) {
828 AllocType |= (uint8_t)ContextIdToAllocationType[Id];
836template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
841 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
842 uint8_t
AllocType = (uint8_t)AllocationType::None;
843 for (
auto Id : Node1Ids) {
844 if (!Node2Ids.
count(Id))
846 AllocType |= (uint8_t)ContextIdToAllocationType[Id];
854template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
857 if (Node1Ids.
size() < Node2Ids.
size())
858 return intersectAllocTypesImpl(Node1Ids, Node2Ids);
860 return intersectAllocTypesImpl(Node2Ids, Node1Ids);
863template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
867 assert(!getNodeForAlloc(Call));
869 std::make_unique<ContextNode>(
true, Call));
871 AllocationCallToContextNodeMap[Call] = AllocNode;
877 AllocNode->
AllocTypes = (uint8_t)AllocationType::None;
882template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
883template <
class NodeT,
class IteratorT>
892 ContextIdToAllocationType[++LastContextId] =
AllocType;
908 ContextIter != StackContext.
end(); ++ContextIter) {
909 auto StackId = getStackId(*ContextIter);
910 ContextNode *StackNode = getNodeForStackId(StackId);
913 std::make_unique<ContextNode>(
false));
914 StackNode = NodeOwner.back().get();
915 StackEntryIdToContextNodeMap[StackId] = StackNode;
918 auto Ins = StackIdSet.
insert(StackId);
924 PrevNode = StackNode;
928template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
934 for (
auto OldId : StackSequenceContextIds) {
935 NewContextIds.
insert(++LastContextId);
936 OldToNewContextIds[OldId].insert(LastContextId);
937 assert(ContextIdToAllocationType.count(OldId));
939 ContextIdToAllocationType[LastContextId] = ContextIdToAllocationType[OldId];
941 return NewContextIds;
944template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
951 for (
auto Id : ContextIds)
952 if (
auto NewId = OldToNewContextIds.find(Id);
953 NewId != OldToNewContextIds.end())
954 NewIds.
insert(NewId->second.begin(), NewId->second.end());
961 auto &&UpdateCallers) ->
void {
962 for (
const auto &Edge :
Node->CallerEdges) {
963 auto Inserted = Visited.insert(Edge.get());
970 if (!NewIdsToAdd.
empty()) {
971 Edge->getContextIds().insert(NewIdsToAdd.
begin(), NewIdsToAdd.
end());
972 NextNode->ContextIds.insert(NewIdsToAdd.
begin(), NewIdsToAdd.
end());
973 UpdateCallers(NextNode, Visited, UpdateCallers);
979 for (
auto &Entry : AllocationCallToContextNodeMap) {
980 auto *
Node = Entry.second;
985 Node->ContextIds.insert(NewIdsToAdd.
begin(), NewIdsToAdd.
end());
986 UpdateCallers(
Node, Visited, UpdateCallers);
990template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
997 TowardsCallee ? OrigNode->CalleeEdges : OrigNode->CallerEdges;
999 for (
auto EI = OrigEdges.begin(); EI != OrigEdges.end();) {
1005 set_subtract(Edge->getContextIds(), RemainingContextIds, NewEdgeContextIds,
1006 NotFoundContextIds);
1007 RemainingContextIds.
swap(NotFoundContextIds);
1009 if (NewEdgeContextIds.
empty()) {
1013 if (TowardsCallee) {
1014 auto NewEdge = std::make_shared<ContextEdge>(
1015 Edge->Callee, NewNode, computeAllocType(NewEdgeContextIds),
1017 NewNode->CalleeEdges.push_back(NewEdge);
1018 NewEdge->Callee->CallerEdges.push_back(NewEdge);
1020 auto NewEdge = std::make_shared<ContextEdge>(
1021 NewNode, Edge->Caller, computeAllocType(NewEdgeContextIds),
1023 NewNode->CallerEdges.push_back(NewEdge);
1024 NewEdge->Caller->CalleeEdges.push_back(NewEdge);
1027 if (Edge->getContextIds().empty()) {
1028 if (TowardsCallee) {
1029 Edge->Callee->eraseCallerEdge(Edge.get());
1030 EI = OrigNode->CalleeEdges.erase(EI);
1032 Edge->Caller->eraseCalleeEdge(Edge.get());
1033 EI = OrigNode->CallerEdges.erase(EI);
1041template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1046 &StackIdToMatchingCalls) {
1054 auto CallerEdges =
Node->CallerEdges;
1055 for (
auto &Edge : CallerEdges) {
1059 assignStackNodesPostOrder(Edge->Caller, Visited, StackIdToMatchingCalls);
1068 if (
Node->IsAllocation ||
1069 !StackIdToMatchingCalls.count(
Node->OrigStackOrAllocId))
1072 auto &Calls = StackIdToMatchingCalls[
Node->OrigStackOrAllocId];
1076 if (Calls.size() == 1) {
1077 auto &[
Call, Ids,
Func, SavedContextIds] = Calls[0];
1078 if (Ids.size() == 1) {
1079 assert(SavedContextIds.empty());
1082 if (
Node->Recursive)
1084 Node->setCall(Call);
1085 NonAllocationCallToContextNodeMap[
Call] =
Node;
1094 ContextNode *LastNode = getNodeForStackId(LastId);
1098 for (
unsigned I = 0;
I < Calls.size();
I++) {
1099 auto &[
Call, Ids,
Func, SavedContextIds] = Calls[
I];
1102 if (SavedContextIds.empty())
1105 assert(LastId == Ids.back());
1107 ContextNode *FirstNode = getNodeForStackId(Ids[0]);
1118 for (
auto Id : Ids) {
1123 assert(!CurNode->Recursive);
1128 auto *Edge = CurNode->findEdgeFromCallee(PrevNode);
1130 SavedContextIds.clear();
1137 if (SavedContextIds.empty())
1140 if (SavedContextIds.empty())
1144 NodeOwner.push_back(
1145 std::make_unique<ContextNode>(
false, Call));
1148 NonAllocationCallToContextNodeMap[
Call] = NewNode;
1149 NewNode->ContextIds = SavedContextIds;
1150 NewNode->AllocTypes = computeAllocType(NewNode->ContextIds);
1155 connectNewNode(NewNode, FirstNode,
true);
1160 connectNewNode(NewNode, LastNode,
false);
1165 for (
auto Id : Ids) {
1172 set_subtract(CurNode->ContextIds, NewNode->ContextIds);
1174 auto *PrevEdge = CurNode->findEdgeFromCallee(PrevNode);
1176 set_subtract(PrevEdge->getContextIds(), NewNode->ContextIds);
1177 if (PrevEdge->getContextIds().empty()) {
1178 PrevNode->eraseCallerEdge(PrevEdge);
1179 CurNode->eraseCalleeEdge(PrevEdge);
1187template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1198 for (
auto &Call : CallsWithMetadata) {
1200 if (AllocationCallToContextNodeMap.count(Call))
1202 auto StackIdsWithContextNodes =
1203 getStackIdsWithContextNodesForCall(Call.call());
1206 if (StackIdsWithContextNodes.empty())
1210 StackIdToMatchingCalls[StackIdsWithContextNodes.back()].push_back(
1211 {Call.call(), StackIdsWithContextNodes, Func, {}});
1222 for (
auto &It : StackIdToMatchingCalls) {
1223 auto &Calls = It.getSecond();
1225 if (Calls.size() == 1) {
1226 auto &Ids = std::get<1>(Calls[0]);
1227 if (Ids.size() == 1)
1236 std::stable_sort(Calls.begin(), Calls.end(),
1237 [](
const CallContextInfo &
A,
const CallContextInfo &
B) {
1238 auto &IdsA = std::get<1>(A);
1239 auto &IdsB = std::get<1>(B);
1240 return IdsA.size() > IdsB.size() ||
1241 (IdsA.size() == IdsB.size() && IdsA < IdsB);
1248 ContextNode *LastNode = getNodeForStackId(LastId);
1260 for (
unsigned I = 0;
I < Calls.size();
I++) {
1261 auto &[Call, Ids, Func, SavedContextIds] = Calls[
I];
1262 assert(SavedContextIds.empty());
1263 assert(LastId == Ids.back());
1277 for (
auto IdIter = Ids.rbegin() + 1; IdIter != Ids.rend(); IdIter++) {
1279 CurNode = getNodeForStackId(Id);
1306 set_intersect(StackSequenceContextIds, Edge->getContextIds());
1309 if (StackSequenceContextIds.
empty()) {
1322 if (Ids.back() != getLastStackId(Call)) {
1324 set_subtract(StackSequenceContextIds, PE->getContextIds());
1325 if (StackSequenceContextIds.
empty())
1329 if (StackSequenceContextIds.
empty())
1335 bool DuplicateContextIds =
false;
1336 if (
I + 1 < Calls.size()) {
1337 auto NextIds = std::get<1>(Calls[
I + 1]);
1338 DuplicateContextIds = Ids == NextIds;
1347 OldToNewContextIds.
reserve(OldToNewContextIds.
size() +
1348 StackSequenceContextIds.
size());
1351 ? duplicateContextIds(StackSequenceContextIds, OldToNewContextIds)
1352 : StackSequenceContextIds;
1353 assert(!SavedContextIds.empty());
1355 if (!DuplicateContextIds) {
1359 set_subtract(LastNodeContextIds, StackSequenceContextIds);
1360 if (LastNodeContextIds.
empty())
1367 propagateDuplicateContextIds(OldToNewContextIds);
1378 for (
auto &Entry : AllocationCallToContextNodeMap)
1379 assignStackNodesPostOrder(Entry.second, Visited, StackIdToMatchingCalls);
1384 Call->getMetadata(LLVMContext::MD_callsite));
1385 return CallsiteContext.back();
1391 CallsiteContext(dyn_cast_if_present<CallsiteInfo *>(
Call.getBase()));
1393 return Index.getStackIdAtIndex(CallsiteContext.back());
1406std::string ModuleCallsiteContextGraph::getLabel(
const Function *Func,
1408 unsigned CloneNo)
const {
1409 return (
Twine(
Call->getFunction()->getName()) +
" -> " +
1410 cast<CallBase>(Call)->getCalledFunction()->getName())
1414std::string IndexCallsiteContextGraph::getLabel(
const FunctionSummary *Func,
1416 unsigned CloneNo)
const {
1417 auto VI = FSToVIMap.find(Func);
1418 assert(VI != FSToVIMap.end());
1419 if (isa<AllocInfo *>(
Call.getBase()))
1420 return (
VI->second.name() +
" -> alloc").str();
1422 auto *Callsite = dyn_cast_if_present<CallsiteInfo *>(
Call.getBase());
1423 return (
VI->second.name() +
" -> " +
1425 Callsite->Clones[CloneNo]))
1430std::vector<uint64_t>
1431ModuleCallsiteContextGraph::getStackIdsWithContextNodesForCall(
1434 Call->getMetadata(LLVMContext::MD_callsite));
1435 return getStackIdsWithContextNodes<MDNode, MDNode::op_iterator>(
1439std::vector<uint64_t>
1440IndexCallsiteContextGraph::getStackIdsWithContextNodesForCall(
IndexCall &Call) {
1443 CallsiteContext(dyn_cast_if_present<CallsiteInfo *>(
Call.getBase()));
1449template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1450template <
class NodeT,
class IteratorT>
1451std::vector<uint64_t>
1454 std::vector<uint64_t> StackIds;
1455 for (
auto IdOrIndex : CallsiteContext) {
1456 auto StackId = getStackId(IdOrIndex);
1460 StackIds.push_back(StackId);
1467 :
Mod(M), OREGetter(OREGetter) {
1469 std::vector<CallInfo> CallsWithMetadata;
1470 for (
auto &BB :
F) {
1471 for (
auto &
I : BB) {
1472 if (!isa<CallBase>(
I))
1474 if (
auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof)) {
1475 CallsWithMetadata.push_back(&
I);
1477 auto *CallsiteMD =
I.getMetadata(LLVMContext::MD_callsite);
1481 for (
auto &MDOp : MemProfMD->operands()) {
1482 auto *MIBMD = cast<const MDNode>(MDOp);
1486 addStackNodesForMIB<MDNode, MDNode::op_iterator>(
1487 AllocNode, StackContext, CallsiteContext,
1490 assert(AllocNode->AllocTypes != (uint8_t)AllocationType::None);
1493 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
1494 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
1497 else if (
I.getMetadata(LLVMContext::MD_callsite))
1498 CallsWithMetadata.push_back(&
I);
1501 if (!CallsWithMetadata.empty())
1506 dbgs() <<
"CCG before updating call stack chains:\n";
1519 for (
auto &Call : FuncEntry.second)
1520 Call.call()->setMetadata(LLVMContext::MD_callsite,
nullptr);
1530 for (
auto &S :
VI.getSummaryList()) {
1539 !isPrevailing(
VI.getGUID(), S.get()))
1541 auto *FS = dyn_cast<FunctionSummary>(S.get());
1544 std::vector<CallInfo> CallsWithMetadata;
1545 if (!FS->allocs().empty()) {
1546 for (
auto &AN : FS->mutableAllocs()) {
1551 if (AN.MIBs.empty())
1553 CallsWithMetadata.push_back({&AN});
1561 for (
auto &MIB : AN.MIBs) {
1564 addStackNodesForMIB<MIBInfo, SmallVector<unsigned>::const_iterator>(
1565 AllocNode, StackContext, EmptyContext, MIB.AllocType);
1567 assert(AllocNode->AllocTypes != (uint8_t)AllocationType::None);
1572 AN.Versions[0] = (uint8_t)allocTypeToUse(AllocNode->AllocTypes);
1576 if (!FS->callsites().empty())
1577 for (
auto &SN : FS->mutableCallsites())
1578 CallsWithMetadata.push_back({&SN});
1580 if (!CallsWithMetadata.empty())
1583 if (!FS->allocs().empty() || !FS->callsites().empty())
1589 dbgs() <<
"CCG before updating call stack chains:\n";
1594 exportToDot(
"prestackupdate");
1598 handleCallsitesWithMultipleTargets();
1601template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1603 CallTy>::handleCallsitesWithMultipleTargets() {
1613 for (
auto Entry = NonAllocationCallToContextNodeMap.begin();
1614 Entry != NonAllocationCallToContextNodeMap.end();) {
1615 auto *Node = Entry->second;
1616 assert(Node->Clones.empty());
1618 bool Removed =
false;
1619 auto Call = Node->Call.call();
1620 for (
auto &Edge : Node->CalleeEdges) {
1621 if (!Edge->Callee->hasCall())
1623 assert(NodeToCallingFunc.count(Edge->Callee));
1625 if (calleeMatchesFunc(Call, NodeToCallingFunc[Edge->Callee]))
1630 Entry = NonAllocationCallToContextNodeMap.erase(Entry);
1648 return Index.getStackIdAtIndex(IdOrIndex);
1651bool ModuleCallsiteContextGraph::calleeMatchesFunc(
Instruction *Call,
1653 auto *CB = dyn_cast<CallBase>(Call);
1654 if (!CB->getCalledOperand())
1656 auto *CalleeVal = CB->getCalledOperand()->stripPointerCasts();
1657 auto *CalleeFunc = dyn_cast<Function>(CalleeVal);
1658 if (CalleeFunc == Func)
1660 auto *Alias = dyn_cast<GlobalAlias>(CalleeVal);
1661 return Alias && Alias->getAliasee() ==
Func;
1664bool IndexCallsiteContextGraph::calleeMatchesFunc(
IndexCall &Call,
1667 dyn_cast_if_present<CallsiteInfo *>(
Call.getBase())->Callee;
1671 Callee.getSummaryList().empty()
1673 : dyn_cast<AliasSummary>(
Callee.getSummaryList()[0].get());
1674 assert(FSToVIMap.count(Func));
1686 if (AllocTypes & (uint8_t)AllocationType::NotCold)
1688 if (AllocTypes & (uint8_t)AllocationType::Cold)
1693template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1700template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1703 OS <<
"Node " <<
this <<
"\n";
1707 OS <<
" (recursive)";
1710 OS <<
"\tContextIds:";
1711 std::vector<uint32_t> SortedIds(ContextIds.begin(), ContextIds.end());
1712 std::sort(SortedIds.begin(), SortedIds.end());
1713 for (
auto Id : SortedIds)
1716 OS <<
"\tCalleeEdges:\n";
1717 for (
auto &Edge : CalleeEdges)
1718 OS <<
"\t\t" << *Edge <<
"\n";
1719 OS <<
"\tCallerEdges:\n";
1720 for (
auto &Edge : CallerEdges)
1721 OS <<
"\t\t" << *Edge <<
"\n";
1722 if (!Clones.empty()) {
1725 for (
auto *Clone : Clones)
1728 }
else if (CloneOf) {
1729 OS <<
"\tClone of " << CloneOf <<
"\n";
1733template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1740template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1743 OS <<
"Edge from Callee " <<
Callee <<
" to Caller: " << Caller
1745 OS <<
" ContextIds:";
1746 std::vector<uint32_t> SortedIds(ContextIds.begin(), ContextIds.end());
1747 std::sort(SortedIds.begin(), SortedIds.end());
1748 for (
auto Id : SortedIds)
1752template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1757template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1760 OS <<
"Callsite Context Graph:\n";
1762 for (
const auto Node : nodes<GraphType>(
this)) {
1763 if (Node->isRemoved())
1770template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1775 assert(Edge->AllocTypes != (uint8_t)AllocationType::None);
1776 assert(!Edge->ContextIds.empty());
1779template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1781 bool CheckEdges =
true) {
1782 if (
Node->isRemoved())
1786 if (
Node->CallerEdges.size()) {
1787 auto EI =
Node->CallerEdges.begin();
1788 auto &FirstEdge = *EI;
1791 for (; EI !=
Node->CallerEdges.end(); EI++) {
1792 const auto &Edge = *EI;
1794 checkEdge<DerivedCCG, FuncTy, CallTy>(Edge);
1795 set_union(CallerEdgeContextIds, Edge->ContextIds);
1799 assert(
Node->ContextIds == CallerEdgeContextIds ||
1802 if (
Node->CalleeEdges.size()) {
1803 auto EI =
Node->CalleeEdges.begin();
1804 auto &FirstEdge = *EI;
1807 for (; EI !=
Node->CalleeEdges.end(); EI++) {
1808 const auto &Edge = *EI;
1810 checkEdge<DerivedCCG, FuncTy, CallTy>(Edge);
1811 set_union(CalleeEdgeContextIds, Edge->ContextIds);
1813 assert(
Node->ContextIds == CalleeEdgeContextIds);
1817template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1820 for (
const auto Node : nodes<GraphType>(
this)) {
1821 checkNode<DerivedCCG, FuncTy, CallTy>(
Node,
false);
1822 for (
auto &Edge :
Node->CallerEdges)
1823 checkEdge<DerivedCCG, FuncTy, CallTy>(Edge);
1827template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1832 using NodePtrTy = std::unique_ptr<ContextNode<DerivedCCG, FuncTy, CallTy>>;
1837 decltype(&getNode)>;
1848 return G->NodeOwner.begin()->get();
1851 using EdgePtrTy = std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>>;
1860 decltype(&GetCallee)>;
1871template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1882 std::string LabelString =
1883 (
Twine(
"OrigId: ") + (Node->IsAllocation ?
"Alloc" :
"") +
1884 Twine(Node->OrigStackOrAllocId))
1886 LabelString +=
"\n";
1887 if (Node->hasCall()) {
1888 auto Func =
G->NodeToCallingFunc.find(Node);
1889 assert(Func !=
G->NodeToCallingFunc.end());
1891 G->getLabel(Func->second, Node->Call.call(), Node->Call.cloneNo());
1893 LabelString +=
"null call";
1894 if (Node->Recursive)
1895 LabelString +=
" (recursive)";
1897 LabelString +=
" (external)";
1904 getContextIds(Node->ContextIds) +
"\"")
1907 (
Twine(
",fillcolor=\"") + getColor(Node->AllocTypes) +
"\"").str();
1909 if (Node->CloneOf) {
1919 auto &Edge = *(ChildIter.getCurrent());
1920 return (
Twine(
"tooltip=\"") + getContextIds(Edge->ContextIds) +
"\"" +
1921 Twine(
",fillcolor=\"") + getColor(Edge->AllocTypes) +
"\"")
1928 return Node->isRemoved();
1933 std::string IdString =
"ContextIds:";
1934 if (ContextIds.
size() < 100) {
1935 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
1936 std::sort(SortedIds.begin(), SortedIds.end());
1937 for (
auto Id : SortedIds)
1938 IdString += (
" " +
Twine(Id)).str();
1940 IdString += (
" (" +
Twine(ContextIds.
size()) +
" ids)").str();
1945 static std::string getColor(uint8_t AllocTypes) {
1946 if (AllocTypes == (uint8_t)AllocationType::NotCold)
1949 if (AllocTypes == (uint8_t)AllocationType::Cold)
1952 ((uint8_t)AllocationType::NotCold | (uint8_t)AllocationType::Cold))
1954 return "mediumorchid1";
1958 static std::string getNodeId(NodeRef
Node) {
1959 std::stringstream SStream;
1960 SStream << std::hex <<
"N0x" << (
unsigned long long)
Node;
1961 std::string
Result = SStream.str();
1966template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1968 std::string Label)
const {
1973template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1976 const std::shared_ptr<ContextEdge> &Edge, EdgeIter *CallerEdgeI) {
1978 NodeOwner.push_back(
1979 std::make_unique<ContextNode>(
Node->IsAllocation,
Node->Call));
1981 Node->addClone(Clone);
1984 moveEdgeToExistingCalleeClone(Edge, Clone, CallerEdgeI,
true);
1988template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1995 assert(NewCallee->getOrigNode() == Edge->Callee->getOrigNode());
1996 auto &EdgeContextIds = Edge->getContextIds();
1999 *CallerEdgeI = OldCallee->CallerEdges.erase(*CallerEdgeI);
2001 OldCallee->eraseCallerEdge(Edge.get());
2002 Edge->Callee = NewCallee;
2003 NewCallee->CallerEdges.push_back(Edge);
2007 NewCallee->ContextIds.insert(EdgeContextIds.begin(), EdgeContextIds.end());
2008 NewCallee->AllocTypes |= Edge->AllocTypes;
2009 OldCallee->AllocTypes = computeAllocType(OldCallee->ContextIds);
2011 assert((OldCallee->AllocTypes == (uint8_t)AllocationType::None) ==
2012 OldCallee->ContextIds.empty());
2016 for (
auto &OldCalleeEdge : OldCallee->CalleeEdges) {
2021 set_subtract(OldCalleeEdge->getContextIds(), EdgeContextIdsToMove);
2022 OldCalleeEdge->AllocTypes =
2023 computeAllocType(OldCalleeEdge->getContextIds());
2030 if (
auto *NewCalleeEdge =
2031 NewCallee->findEdgeFromCallee(OldCalleeEdge->Callee)) {
2032 NewCalleeEdge->getContextIds().insert(EdgeContextIdsToMove.
begin(),
2033 EdgeContextIdsToMove.
end());
2034 NewCalleeEdge->AllocTypes |= computeAllocType(EdgeContextIdsToMove);
2038 auto NewEdge = std::make_shared<ContextEdge>(
2039 OldCalleeEdge->Callee, NewCallee,
2040 computeAllocType(EdgeContextIdsToMove), EdgeContextIdsToMove);
2041 NewCallee->CalleeEdges.push_back(NewEdge);
2042 NewEdge->Callee->CallerEdges.push_back(NewEdge);
2045 checkNode<DerivedCCG, FuncTy, CallTy>(OldCallee,
false);
2046 checkNode<DerivedCCG, FuncTy, CallTy>(NewCallee,
false);
2047 for (
const auto &OldCalleeEdge : OldCallee->CalleeEdges)
2048 checkNode<DerivedCCG, FuncTy, CallTy>(OldCalleeEdge->Callee,
2050 for (
const auto &NewCalleeEdge : NewCallee->CalleeEdges)
2051 checkNode<DerivedCCG, FuncTy, CallTy>(NewCalleeEdge->Callee,
2056template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2059 for (
auto &Entry : AllocationCallToContextNodeMap)
2065 return (
AllocType == (uint8_t)AllocationType::Cold) ||
2066 (
AllocType == (uint8_t)AllocationType::NotCold) ||
2068 ((uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold));
2071template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2075 checkNode<DerivedCCG, FuncTy, CallTy>(
Node);
2083 if (!
Node->hasCall())
2098 auto CallerEdges =
Node->CallerEdges;
2099 for (
auto &Edge : CallerEdges) {
2101 if (Edge->Callee ==
nullptr && Edge->Caller ==
nullptr) {
2102 assert(!std::count(
Node->CallerEdges.begin(),
Node->CallerEdges.end(),
2107 if (!Visited.
count(Edge->Caller) && !Edge->Caller->CloneOf) {
2131 const unsigned AllocTypeCloningPriority[] = { 3, 4,
2134 std::stable_sort(
Node->CallerEdges.begin(),
Node->CallerEdges.end(),
2135 [&](
const std::shared_ptr<ContextEdge> &
A,
2136 const std::shared_ptr<ContextEdge> &
B) {
2137 assert(checkColdOrNotCold(A->AllocTypes) &&
2138 checkColdOrNotCold(B->AllocTypes));
2140 if (A->AllocTypes == B->AllocTypes)
2143 return *A->ContextIds.begin() < *B->ContextIds.begin();
2144 return AllocTypeCloningPriority[A->AllocTypes] <
2145 AllocTypeCloningPriority[B->AllocTypes];
2148 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
2155 for (
auto EI =
Node->CallerEdges.begin(); EI !=
Node->CallerEdges.end();) {
2156 auto CallerEdge = *EI;
2165 std::vector<uint8_t> CalleeEdgeAllocTypesForCallerEdge;
2166 CalleeEdgeAllocTypesForCallerEdge.reserve(
Node->CalleeEdges.size());
2167 for (
auto &CalleeEdge :
Node->CalleeEdges)
2168 CalleeEdgeAllocTypesForCallerEdge.push_back(intersectAllocTypes(
2169 CalleeEdge->getContextIds(), CallerEdge->getContextIds()));
2182 assert(CallerEdge->AllocTypes != (uint8_t)AllocationType::None);
2183 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
2184 if (allocTypeToUse(CallerEdge->AllocTypes) ==
2185 allocTypeToUse(
Node->AllocTypes) &&
2186 allocTypesMatch<DerivedCCG, FuncTy, CallTy>(
2187 CalleeEdgeAllocTypesForCallerEdge,
Node->CalleeEdges)) {
2195 for (
auto *CurClone :
Node->Clones) {
2196 if (allocTypeToUse(CurClone->AllocTypes) !=
2197 allocTypeToUse(CallerEdge->AllocTypes))
2200 if (!allocTypesMatch<DerivedCCG, FuncTy, CallTy>(
2201 CalleeEdgeAllocTypesForCallerEdge, CurClone->CalleeEdges))
2209 moveEdgeToExistingCalleeClone(CallerEdge, Clone, &EI);
2211 Clone = moveEdgeToNewCalleeClone(CallerEdge, &EI);
2214 Node->AllocTypes != (uint8_t)AllocationType::None);
2216 assert(Clone->AllocTypes != (uint8_t)AllocationType::None);
2218 Clone->CallerEdges, [&](
const std::shared_ptr<ContextEdge> &
E) {
2219 return E->AllocTypes == (uint8_t)AllocationType::None;
2225 for (
auto *Clone :
Node->Clones) {
2228 checkNode<DerivedCCG, FuncTy, CallTy>(Clone);
2238 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
2240 [&](
const std::shared_ptr<ContextEdge> &
E) {
2241 return E->AllocTypes == (uint8_t)AllocationType::None;
2244 [&](
const std::shared_ptr<ContextEdge> &
E) {
2245 return E->AllocTypes == (uint8_t)AllocationType::None;
2249 checkNode<DerivedCCG, FuncTy, CallTy>(
Node);
2252void ModuleCallsiteContextGraph::updateAllocationCall(
2256 "memprof", AllocTypeString);
2257 cast<CallBase>(
Call.call())->addFnAttr(
A);
2258 OREGetter(
Call.call()->getFunction())
2260 <<
ore::NV(
"AllocationCall",
Call.call()) <<
" in clone "
2262 <<
" marked with memprof allocation attribute "
2263 <<
ore::NV(
"Attribute", AllocTypeString));
2266void IndexCallsiteContextGraph::updateAllocationCall(
CallInfo &Call,
2270 assert(AI->Versions.size() >
Call.cloneNo());
2274void ModuleCallsiteContextGraph::updateCall(
CallInfo &CallerCall,
2276 if (CalleeFunc.cloneNo() > 0)
2277 cast<CallBase>(CallerCall.call())->setCalledFunction(CalleeFunc.func());
2278 OREGetter(CallerCall.call()->getFunction())
2280 <<
ore::NV(
"Call", CallerCall.call()) <<
" in clone "
2281 <<
ore::NV(
"Caller", CallerCall.call()->getFunction())
2282 <<
" assigned to call function clone "
2283 <<
ore::NV(
"Callee", CalleeFunc.func()));
2286void IndexCallsiteContextGraph::updateCall(
CallInfo &CallerCall,
2288 auto *CI = CallerCall.call().dyn_cast<
CallsiteInfo *>();
2290 "Caller cannot be an allocation which should not have profiled calls");
2291 assert(CI->Clones.size() > CallerCall.cloneNo());
2292 CI->Clones[CallerCall.cloneNo()] = CalleeFunc.cloneNo();
2297ModuleCallsiteContextGraph::cloneFunctionForCallsite(
2299 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
2305 NewFunc->setName(
Name);
2306 for (
auto &Inst : CallsWithMetadataInFunc) {
2308 assert(Inst.cloneNo() == 0);
2309 CallMap[Inst] = {cast<Instruction>(VMap[Inst.call()]), CloneNo};
2311 OREGetter(
Func.func())
2313 <<
"created clone " <<
ore::NV(
"NewFunction", NewFunc));
2314 return {NewFunc, CloneNo};
2319IndexCallsiteContextGraph::cloneFunctionForCallsite(
2321 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
2336 for (
auto &Inst : CallsWithMetadataInFunc) {
2338 assert(Inst.cloneNo() == 0);
2339 if (
auto *AI = Inst.call().dyn_cast<
AllocInfo *>()) {
2340 assert(AI->Versions.size() == CloneNo);
2343 AI->Versions.push_back(0);
2346 assert(CI && CI->Clones.size() == CloneNo);
2349 CI->Clones.push_back(0);
2351 CallMap[Inst] = {Inst.call(), CloneNo};
2353 return {
Func.func(), CloneNo};
2387template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2389 bool Changed =
false;
2397 auto RecordCalleeFuncOfCallsite = [&](
ContextNode *Caller,
2399 assert(Caller->hasCall());
2400 CallsiteToCalleeFuncCloneMap[Caller] = CalleeFunc;
2410 std::map<FuncInfo, std::map<CallInfo, CallInfo>> FuncClonesToCallMap;
2411 for (
auto &Call : CallsWithMetadata) {
2416 if (!Node || Node->Clones.empty())
2418 assert(Node->hasCall() &&
2419 "Not having a call should have prevented cloning");
2423 std::map<FuncInfo, ContextNode *> FuncCloneToCurNodeCloneMap;
2427 auto AssignCallsiteCloneToFuncClone = [&](
const FuncInfo &FuncClone,
2432 FuncCloneToCurNodeCloneMap[FuncClone] = CallsiteClone;
2434 assert(FuncClonesToCallMap.count(FuncClone));
2435 std::map<CallInfo, CallInfo> &CallMap = FuncClonesToCallMap[FuncClone];
2437 if (CallMap.count(Call))
2438 CallClone = CallMap[Call];
2439 CallsiteClone->setCall(CallClone);
2445 std::deque<ContextNode *> ClonesWorklist;
2447 if (!Node->ContextIds.empty())
2448 ClonesWorklist.push_back(Node);
2449 ClonesWorklist.insert(ClonesWorklist.end(), Node->Clones.begin(),
2450 Node->Clones.end());
2455 unsigned NodeCloneCount = 0;
2456 while (!ClonesWorklist.empty()) {
2458 ClonesWorklist.pop_front();
2461 checkNode<DerivedCCG, FuncTy, CallTy>(Clone);
2467 if (FuncClonesToCallMap.size() < NodeCloneCount) {
2469 if (NodeCloneCount == 1) {
2474 Clone->
CallerEdges, [&](
const std::shared_ptr<ContextEdge> &
E) {
2475 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
2479 FuncClonesToCallMap[OrigFunc] = {};
2480 AssignCallsiteCloneToFuncClone(
2481 OrigFunc, Call, Clone,
2482 AllocationCallToContextNodeMap.count(Call));
2485 if (!CE->Caller->hasCall())
2487 RecordCalleeFuncOfCallsite(CE->Caller, OrigFunc);
2497 FuncInfo PreviousAssignedFuncClone;
2499 Clone->
CallerEdges, [&](
const std::shared_ptr<ContextEdge> &
E) {
2500 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
2502 bool CallerAssignedToCloneOfFunc =
false;
2504 const std::shared_ptr<ContextEdge> &Edge = *EI;
2505 PreviousAssignedFuncClone =
2506 CallsiteToCalleeFuncCloneMap[Edge->Caller];
2507 CallerAssignedToCloneOfFunc =
true;
2512 std::map<CallInfo, CallInfo> NewCallMap;
2513 unsigned CloneNo = FuncClonesToCallMap.size();
2514 assert(CloneNo > 0 &&
"Clone 0 is the original function, which "
2515 "should already exist in the map");
2516 FuncInfo NewFuncClone = cloneFunctionForCallsite(
2517 OrigFunc, Call, NewCallMap, CallsWithMetadata, CloneNo);
2518 FuncClonesToCallMap.emplace(NewFuncClone, std::move(NewCallMap));
2519 FunctionClonesAnalysis++;
2525 if (!CallerAssignedToCloneOfFunc) {
2526 AssignCallsiteCloneToFuncClone(
2527 NewFuncClone, Call, Clone,
2528 AllocationCallToContextNodeMap.count(Call));
2531 if (!CE->Caller->hasCall())
2533 RecordCalleeFuncOfCallsite(CE->Caller, NewFuncClone);
2544 if (!CE->Caller->hasCall())
2547 if (!CallsiteToCalleeFuncCloneMap.
count(CE->Caller) ||
2551 CallsiteToCalleeFuncCloneMap[CE->Caller] !=
2552 PreviousAssignedFuncClone)
2555 RecordCalleeFuncOfCallsite(CE->Caller, NewFuncClone);
2565 for (
auto CalleeEdge : CE->Caller->CalleeEdges) {
2576 ContextNode *NewClone = moveEdgeToNewCalleeClone(CalleeEdge);
2586 RecordCalleeFuncOfCallsite(
2587 NewClone, CallsiteToCalleeFuncCloneMap[
Callee]);
2597 std::map<CallInfo, CallInfo> &CallMap =
2598 FuncClonesToCallMap[NewFuncClone];
2599 assert(CallMap.count(OrigCall));
2600 CallInfo NewCall(CallMap[OrigCall]);
2624 std::map<FuncInfo, ContextNode *> FuncCloneToNewCallsiteCloneMap;
2625 FuncInfo FuncCloneAssignedToCurCallsiteClone;
2632 if (!Edge->Caller->hasCall()) {
2638 if (CallsiteToCalleeFuncCloneMap.
count(Edge->Caller)) {
2640 CallsiteToCalleeFuncCloneMap[Edge->Caller];
2650 if ((FuncCloneToCurNodeCloneMap.count(FuncCloneCalledByCaller) &&
2651 FuncCloneToCurNodeCloneMap[FuncCloneCalledByCaller] !=
2659 (FuncCloneAssignedToCurCallsiteClone &&
2660 FuncCloneAssignedToCurCallsiteClone !=
2661 FuncCloneCalledByCaller)) {
2676 if (FuncCloneToNewCallsiteCloneMap.count(
2677 FuncCloneCalledByCaller)) {
2679 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller];
2680 moveEdgeToExistingCalleeClone(Edge, NewClone, &EI);
2685 ContextNode *NewClone = moveEdgeToNewCalleeClone(Edge, &EI);
2687 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller] =
2690 ClonesWorklist.push_back(NewClone);
2692 Clone->
AllocTypes != (uint8_t)AllocationType::None);
2706 if (!FuncCloneAssignedToCurCallsiteClone) {
2707 FuncCloneAssignedToCurCallsiteClone = FuncCloneCalledByCaller;
2709 AssignCallsiteCloneToFuncClone(
2710 FuncCloneCalledByCaller, Call, Clone,
2711 AllocationCallToContextNodeMap.count(Call));
2715 assert(FuncCloneAssignedToCurCallsiteClone ==
2716 FuncCloneCalledByCaller);
2725 if (!FuncCloneAssignedToCurCallsiteClone) {
2730 for (
auto &CF : FuncClonesToCallMap) {
2731 if (!FuncCloneToCurNodeCloneMap.count(CF.first)) {
2732 FuncCloneAssignedToCurCallsiteClone = CF.first;
2736 assert(FuncCloneAssignedToCurCallsiteClone);
2738 AssignCallsiteCloneToFuncClone(
2739 FuncCloneAssignedToCurCallsiteClone, Call, Clone,
2740 AllocationCallToContextNodeMap.count(Call));
2742 assert(FuncCloneToCurNodeCloneMap
2743 [FuncCloneAssignedToCurCallsiteClone] == Clone);
2745 RecordCalleeFuncOfCallsite(Edge->Caller,
2746 FuncCloneAssignedToCurCallsiteClone);
2753 checkNode<DerivedCCG, FuncTy, CallTy>(Node);
2754 for (
const auto &PE : Node->CalleeEdges)
2755 checkNode<DerivedCCG, FuncTy, CallTy>(PE->Callee);
2756 for (
const auto &CE : Node->CallerEdges)
2757 checkNode<DerivedCCG, FuncTy, CallTy>(CE->Caller);
2758 for (
auto *Clone : Node->Clones) {
2759 checkNode<DerivedCCG, FuncTy, CallTy>(Clone);
2760 for (
const auto &PE : Clone->CalleeEdges)
2761 checkNode<DerivedCCG, FuncTy, CallTy>(PE->Callee);
2762 for (
const auto &CE : Clone->CallerEdges)
2763 checkNode<DerivedCCG, FuncTy, CallTy>(CE->Caller);
2771 auto &&UpdateCalls) {
2772 auto Inserted = Visited.insert(Node);
2773 if (!Inserted.second)
2776 for (
auto *Clone : Node->Clones)
2777 UpdateCalls(Clone, Visited, UpdateCalls);
2779 for (
auto &Edge : Node->CallerEdges)
2780 UpdateCalls(Edge->Caller, Visited, UpdateCalls);
2784 if (!Node->hasCall() || Node->ContextIds.empty())
2787 if (Node->IsAllocation) {
2788 updateAllocationCall(Node->Call, allocTypeToUse(Node->AllocTypes));
2792 if (!CallsiteToCalleeFuncCloneMap.
count(Node))
2795 auto CalleeFunc = CallsiteToCalleeFuncCloneMap[Node];
2796 updateCall(Node->Call, CalleeFunc);
2805 for (
auto &Entry : AllocationCallToContextNodeMap)
2806 UpdateCalls(Entry.second, Visited, UpdateCalls);
2820 FunctionsClonedThinBackend++;
2821 for (
unsigned I = 1;
I < NumClones;
I++) {
2822 VMaps.
emplace_back(std::make_unique<ValueToValueMapTy>());
2824 FunctionClonesThinBackend++;
2827 for (
auto &BB : *NewF) {
2828 for (
auto &Inst : BB) {
2829 Inst.setMetadata(LLVMContext::MD_memprof,
nullptr);
2830 Inst.setMetadata(LLVMContext::MD_callsite,
nullptr);
2834 auto *PrevF = M.getFunction(
Name);
2838 assert(PrevF->isDeclaration());
2839 NewF->takeName(PrevF);
2840 PrevF->replaceAllUsesWith(NewF);
2841 PrevF->eraseFromParent();
2843 NewF->setName(
Name);
2845 <<
"created clone " <<
ore::NV(
"NewFunction", NewF));
2848 if (!FuncToAliasMap.count(&
F))
2850 for (
auto *
A : FuncToAliasMap[&
F]) {
2852 auto *PrevA = M.getNamedAlias(
Name);
2854 A->getType()->getPointerAddressSpace(),
2855 A->getLinkage(),
Name, NewF);
2856 NewA->copyAttributesFrom(
A);
2860 assert(PrevA->isDeclaration());
2861 NewA->takeName(PrevA);
2862 PrevA->replaceAllUsesWith(NewA);
2863 PrevA->eraseFromParent();
2905bool MemProfContextDisambiguation::applyImport(
Module &M) {
2907 bool Changed =
false;
2909 auto IsMemProfClone = [](
const Function &
F) {
2916 std::map<const Function *, SmallPtrSet<const GlobalAlias *, 1>>
2918 for (
auto &
A :
M.aliases()) {
2919 auto *Aliasee =
A.getAliaseeObject();
2920 if (
auto *
F = dyn_cast<Function>(Aliasee))
2921 FuncToAliasMap[
F].insert(&
A);
2925 if (
F.isDeclaration() || IsMemProfClone(
F))
2931 bool ClonesCreated =
false;
2932 unsigned NumClonesCreated = 0;
2933 auto CloneFuncIfNeeded = [&](
unsigned NumClones) {
2943 if (ClonesCreated) {
2944 assert(NumClonesCreated == NumClones);
2951 ClonesCreated =
true;
2952 NumClonesCreated = NumClones;
2965 ImportSummary->findSummaryInModule(TheFnVI,
M.getModuleIdentifier());
2973 if (isa<AliasSummary>(GVSummary))
2976 auto *
FS = cast<FunctionSummary>(GVSummary->getBaseObject());
2978 if (
FS->allocs().empty() &&
FS->callsites().empty())
2981 auto SI =
FS->callsites().begin();
2982 auto AI =
FS->allocs().begin();
2987 for (
auto &BB :
F) {
2988 for (
auto &
I : BB) {
2989 auto *CB = dyn_cast<CallBase>(&
I);
2995 I.getMetadata(LLVMContext::MD_callsite));
2996 auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof);
3000 if (CB->getAttributes().hasFnAttr(
"memprof")) {
3002 CB->getAttributes().getFnAttr(
"memprof").getValueAsString() ==
"cold"
3003 ? AllocTypeColdThinBackend++
3004 : AllocTypeNotColdThinBackend++;
3005 OrigAllocsThinBackend++;
3006 AllocVersionsThinBackend++;
3007 if (!MaxAllocVersionsThinBackend)
3008 MaxAllocVersionsThinBackend = 1;
3011 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
3018 auto &AllocNode = *(AI++);
3022 auto MIBIter = AllocNode.MIBs.begin();
3023 for (
auto &MDOp : MemProfMD->operands()) {
3024 assert(MIBIter != AllocNode.MIBs.end());
3026 MIBIter->StackIdIndices.begin();
3027 auto *MIBMD = cast<const MDNode>(MDOp);
3032 for (
auto ContextIter =
3033 StackContext.beginAfterSharedPrefix(CallsiteContext);
3034 ContextIter != StackContext.end(); ++ContextIter) {
3038 if (!StackIdsFromMetadata.
empty() &&
3039 StackIdsFromMetadata.
back() == *ContextIter)
3041 assert(StackIdIndexIter != MIBIter->StackIdIndices.end());
3042 assert(ImportSummary->getStackIdAtIndex(*StackIdIndexIter) ==
3050 CloneFuncIfNeeded(AllocNode.Versions.size());
3052 OrigAllocsThinBackend++;
3053 AllocVersionsThinBackend += AllocNode.Versions.size();
3054 if (MaxAllocVersionsThinBackend < AllocNode.Versions.size())
3055 MaxAllocVersionsThinBackend = AllocNode.Versions.size();
3062 if (AllocNode.Versions.size() == 1) {
3064 AllocationType::NotCold ||
3066 AllocationType::None);
3067 UnclonableAllocsThinBackend++;
3073 return Type == ((uint8_t)AllocationType::NotCold |
3074 (uint8_t)AllocationType::Cold);
3078 for (
unsigned J = 0; J < AllocNode.Versions.size(); J++) {
3080 if (AllocNode.Versions[J] == (uint8_t)AllocationType::None)
3083 AllocTy == AllocationType::Cold ? AllocTypeColdThinBackend++
3084 : AllocTypeNotColdThinBackend++;
3096 CBClone = cast<CallBase>((*VMaps[J - 1])[CB]);
3099 <<
ore::NV(
"AllocationCall", CBClone) <<
" in clone "
3101 <<
" marked with memprof allocation attribute "
3102 <<
ore::NV(
"Attribute", AllocTypeString));
3104 }
else if (!CallsiteContext.empty()) {
3106 assert(SI !=
FS->callsites().end());
3107 auto &StackNode = *(
SI++);
3112 auto StackIdIndexIter = StackNode.StackIdIndices.begin();
3113 for (
auto StackId : CallsiteContext) {
3114 assert(StackIdIndexIter != StackNode.StackIdIndices.end());
3115 assert(ImportSummary->getStackIdAtIndex(*StackIdIndexIter) ==
3122 CloneFuncIfNeeded(StackNode.Clones.size());
3125 assert(CB->getCalledFunction());
3126 assert(!IsMemProfClone(*CB->getCalledFunction()));
3131 auto CalleeOrigName = CB->getCalledFunction()->getName();
3132 for (
unsigned J = 0; J < StackNode.Clones.size(); J++) {
3135 if (!StackNode.Clones[J])
3137 auto NewF =
M.getOrInsertFunction(
3139 CB->getCalledFunction()->getFunctionType());
3145 CBClone = cast<CallBase>((*VMaps[J - 1])[CB]);
3148 <<
ore::NV(
"Call", CBClone) <<
" in clone "
3150 <<
" assigned to call function clone "
3151 <<
ore::NV(
"Callee", NewF.getCallee()));
3155 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
3156 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
3164template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3167 dbgs() <<
"CCG before cloning:\n";
3184 dbgs() <<
"CCG after cloning:\n";
3193 dbgs() <<
"CCG after assigning function clones:\n";
3202bool MemProfContextDisambiguation::processModule(
3209 return applyImport(M);
3223 return CCG.process();
3228 : ImportSummary(Summary) {
3229 if (ImportSummary) {
3239 auto ReadSummaryFile =
3241 if (!ReadSummaryFile) {
3248 if (!ImportSummaryForTestingOrErr) {
3254 ImportSummaryForTesting = std::move(*ImportSummaryForTestingOrErr);
3255 ImportSummary = ImportSummaryForTesting.get();
3264 if (!processModule(M, OREGetter))
amdgpu Simplify well known AMD library false FunctionCallee Callee
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")
#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.
cl::opt< bool > SupportsHotColdNew
Indicate we are linking with an allocator that supports hot/cold operator new interfaces.
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)
typename CallsiteContextGraph< DerivedCCG, FuncTy, CallTy >::CallInfo CallInfo
typename CallsiteContextGraph< DerivedCCG, FuncTy, CallTy >::FuncInfo FuncInfo
cl::opt< bool > SupportsHotColdNew("supports-hot-cold-new", cl::init(false), cl::Hidden, cl::desc("Linking with hot/cold operator new interfaces"))
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)
typename CallsiteContextGraph< DerivedCCG, FuncTy, CallTy >::ContextNode ContextNode
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."))
typename CallsiteContextGraph< DerivedCCG, FuncTy, CallTy >::ContextEdge ContextEdge
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)
CRTP base for graphs built from either IR or ThinLTO summary index.
void addStackNodesForMIB(ContextNode *AllocNode, CallStack< NodeT, IteratorT > &StackContext, CallStack< NodeT, IteratorT > &CallsiteContext, AllocationType AllocType)
Adds nodes for the given MIB stack ids.
void removeNoneTypeCalleeEdges(ContextNode *Node)
Helper to remove callee edges that have allocation type None (due to not carrying any context ids) af...
CallsiteContextGraph(CallsiteContextGraph &&)=default
std::map< const ContextNode *, const FuncTy * > NodeToCallingFunc
Map from callsite node to the enclosing caller function.
void identifyClones()
Perform cloning on the graph necessary to uniquely identify the allocation behavior of an allocation ...
void updateStackNodes()
Matches all callsite metadata (or summary) to the nodes created for allocation memprof MIB metadata,...
void handleCallsitesWithMultipleTargets()
Update graph to conservatively handle any callsite stack nodes that target multiple different callee ...
bool assignFunctions()
Assign callsite clones to functions, cloning functions as needed to accommodate the combinations of t...
friend raw_ostream & operator<<(raw_ostream &OS, const CallsiteContextGraph &CCG)
std::vector< uint64_t > getStackIdsWithContextNodes(CallStack< NodeT, IteratorT > &CallsiteContext)
Get a list of nodes corresponding to the stack ids in the given callsite context.
CallsiteContextGraph()=default
std::vector< std::pair< FuncTy *, std::vector< CallInfo > > > FuncToCallsWithMetadata
Save lists of calls with MemProf metadata in each function, for faster iteration.
bool process()
Main entry point to perform analysis and transformations on graph.
CallsiteContextGraph(const CallsiteContextGraph &)=default
void print(raw_ostream &OS) const
ContextNode * addAllocNode(CallInfo Call, const FuncTy *F)
Adds nodes for the given allocation and any stack ids on its memprof MIB metadata (or summary).
void exportToDot(std::string Label) const
CRTP derived class for graphs built from summary index (ThinLTO).
IndexCallsiteContextGraph(ModuleSummaryIndex &Index, function_ref< bool(GlobalValue::GUID, const GlobalValueSummary *)> isPrevailing)
CRTP derived class for graphs built from IR (regular LTO).
ModuleCallsiteContextGraph(Module &M, function_ref< OptimizationRemarkEmitter &(Function *)> OREGetter)
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.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
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.
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).
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.
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.
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.
This is an optimization pass for GlobalISel generic memory operations.
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="")
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.
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.
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...
Represents a callsite clone via CallTy and clone number pair.
std::pair< CallTy, unsigned > Base
void print(raw_ostream &OS) const
void setCloneNo(unsigned N)
friend raw_ostream & operator<<(raw_ostream &OS, const CallInfo &Call)
CallInfo(CallTy Call=nullptr, unsigned CloneNo=0)
Edge in the Callsite Context Graph from a ContextNode N to a caller or callee.
DenseSet< uint32_t > ContextIds
void print(raw_ostream &OS) const
DenseSet< uint32_t > & getContextIds()
friend raw_ostream & operator<<(raw_ostream &OS, const ContextEdge &Edge)
ContextEdge(ContextNode *Callee, ContextNode *Caller, uint8_t AllocType, DenseSet< uint32_t > ContextIds)
Node in the Callsite Context Graph.
std::vector< std::shared_ptr< ContextEdge > > CalleeEdges
void addClone(ContextNode *Clone)
DenseSet< uint32_t > ContextIds
void printCall(raw_ostream &OS) const
friend raw_ostream & operator<<(raw_ostream &OS, const ContextNode &Node)
ContextNode * getOrigNode()
void print(raw_ostream &OS) const
void eraseCalleeEdge(const ContextEdge *Edge)
void eraseCallerEdge(const ContextEdge *Edge)
void addOrUpdateCallerEdge(ContextNode *Caller, AllocationType AllocType, unsigned int ContextId)
ContextEdge * findEdgeFromCaller(const ContextNode *Caller)
std::vector< ContextNode * > Clones
ContextEdge * findEdgeFromCallee(const ContextNode *Callee)
std::vector< std::shared_ptr< ContextEdge > > CallerEdges
ContextNode(bool IsAllocation)
uint64_t OrigStackOrAllocId
ContextNode(bool IsAllocation, CallInfo C)
Represents a function clone via FuncTy pointer and clone number pair.
std::pair< FuncTy *, unsigned > Base
FuncInfo(FuncTy *F=nullptr, unsigned CloneNo=0)
DOTGraphTraits(bool IsSimple=false)
typename GTraits::NodeRef NodeRef
static std::string getEdgeAttributes(NodeRef, ChildIteratorType ChildIter, 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 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)
Represents a call in the summary index graph, which can either be an allocation or an interior callsi...
void print(raw_ostream &OS) const
IndexCall(std::nullptr_t)
IndexCall(CallsiteInfo *StackNode)
IndexCall(PointerUnion PT)
IndexCall(AllocInfo *AllocNode)
PointerUnion< CallsiteInfo *, AllocInfo * > getBase() const
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