55#define DEBUG_TYPE "memprof-context-disambiguation"
58 "Number of function clones created during whole program analysis");
60 "Number of function clones created during ThinLTO backend");
62 "Number of functions that had clones created during ThinLTO backend");
64 FunctionCloneDuplicatesThinBackend,
65 "Number of function clone duplicates detected during ThinLTO backend");
66STATISTIC(AllocTypeNotCold,
"Number of not cold static allocations (possibly "
67 "cloned) during whole program analysis");
68STATISTIC(AllocTypeCold,
"Number of cold static allocations (possibly cloned) "
69 "during whole program analysis");
71 "Number of ambiguous static allocations (possibly cloned) during "
72 "whole program analysis");
74 "Number of not cold static allocations (possibly cloned) during "
76STATISTIC(AllocTypeColdThinBackend,
"Number of cold static allocations "
77 "(possibly cloned) during ThinLTO backend");
79 "Number of ambiguous static allocations (possibly cloned) during "
82 "Number of original (not cloned) allocations with memprof profiles "
83 "during ThinLTO backend");
85 AllocVersionsThinBackend,
86 "Number of allocation versions (including clones) during ThinLTO backend");
88 "Maximum number of allocation versions created for an original "
89 "allocation during ThinLTO backend");
91 "Number of unclonable ambigous allocations during ThinLTO backend");
93 "Number of edges removed due to mismatched callees (profiled vs IR)");
95 "Number of profiled callees found via tail calls");
97 "Aggregate depth of profiled callees found via tail calls");
99 "Maximum depth of profiled callees found via tail calls");
101 "Number of profiled callees found via multiple tail call chains");
103 "Number of tail calls in chains to profiled callees that are "
104 "indirect (thin link)");
106 "Number of indirect tail calls recorded for ICP for cloning during "
108STATISTIC(DeferredBackedges,
"Number of backedges with deferred cloning");
109STATISTIC(NewMergedNodes,
"Number of new nodes created during merging");
110STATISTIC(NonNewMergedNodes,
"Number of non new nodes used during merging");
112 "Number of missing alloc nodes for context ids");
114 "Number of calls skipped during cloning due to unexpected operand");
116 "Number of callsites assigned to call multiple non-matching clones");
117STATISTIC(TotalMergeInvokes,
"Number of merge invocations for nodes");
118STATISTIC(TotalMergeIters,
"Number of merge iterations for nodes");
119STATISTIC(MaxMergeIters,
"Max merge iterations for nodes");
120STATISTIC(NumImportantContextIds,
"Number of important context ids");
121STATISTIC(NumFixupEdgeIdsInserted,
"Number of fixup edge ids inserted");
122STATISTIC(NumFixupEdgesAdded,
"Number of fixup edges added");
123STATISTIC(NumFixedContexts,
"Number of contexts with fixed edges");
125 "Number of callsite clones without an edge to a callee's clones "
126 "assigned the callee function clone of their original node");
128 "Number of calls in function clones whose callee was taken from a "
129 "callsite clone an implicit caller requires");
131 "Number of context ids with call stacks trimmed at a callsite");
133 "Number of callsite clones without an edge to a callee's clones "
134 "left in a function clone calling a conflicting callee clone");
136 "Number of aliasees prevailing in a different module than its alias");
138 "Number of summary callsites assigned to call a cloned callee (thin "
141 "Number of summary callsites assigned to call a cloned callee with "
142 "an indirect call edge (thin link)");
144 "Number of summary indirect call edges to cloned callees marked as "
145 "requiring a declaration import (thin link)");
147 "Number of calls assigned contexts trimmed within their inlined "
148 "stack id sequence");
150 "Number of (duplicated) context ids for contexts trimmed within a "
151 "call's inlined stack id sequence");
156 cl::desc(
"Specify the path prefix of the MemProf dot files."));
160 cl::desc(
"Export graph to dot files."));
165 cl::desc(
"Iteratively apply merging on a node to catch new callers"));
175 "memprof-dot-scope",
cl::desc(
"Scope of graph to export to dot"),
180 "Export only nodes with contexts feeding given "
181 "-memprof-dot-alloc-id"),
183 "Export only nodes with given -memprof-dot-context-id")));
187 cl::desc(
"Id of alloc to export if -memprof-dot-scope=alloc "
188 "or to highlight if -memprof-dot-scope=all"));
192 cl::desc(
"Id of context to export if -memprof-dot-scope=context or to "
193 "highlight otherwise"));
197 cl::desc(
"Dump CallingContextGraph to stdout after each stage."));
201 cl::desc(
"Perform verification checks on CallingContextGraph."));
205 cl::desc(
"Perform frequent verification checks on nodes."));
208 "memprof-import-summary",
209 cl::desc(
"Import summary to use for testing the ThinLTO backend via opt"),
215 cl::desc(
"Max depth to recursively search for missing "
216 "frames through tail calls."));
223 cl::desc(
"Search for missing frames through indirect tail calls to their "
224 "profiled targets (ThinLTO)."));
229 cl::desc(
"Allow cloning of callsites involved in recursive cycles"));
233 cl::desc(
"Allow cloning of contexts through recursive cycles"));
240 cl::desc(
"Merge clones before assigning functions"));
249 cl::desc(
"Allow cloning of contexts having recursive cycles"));
263 cl::desc(
"Assign contexts trimmed within a call's inlined stack id "
264 "sequence to that call"));
270 cl::desc(
"Minimum absolute count for promoted target to be inlinable"));
274 "enable-memprof-context-disambiguation",
cl::Hidden,
275 cl::desc(
"Enable MemProf context disambiguation"));
281 cl::desc(
"Linking with hot/cold operator new interfaces"));
286 "Require target function definition when promoting indirect calls"));
309 cl::desc(
"Import at least a declaration of the indirect call targets of "
310 "callsites assigned to call a cloned callee (needed for MemProf "
311 "ICP in the ThinLTO backend)"));
324 cl::desc(
"Append post-cloning call path and matching details to each "
325 "-memprof-report-hinted-sizes line"));
332 cl::desc(
"Maximum number of functions printed in full for a post-cloning "
333 "call path in the -memprof-report-hinted-sizes-detail suffix; "
334 "longer paths are elided in the middle"));
338 cl::desc(
"Number of largest cold contexts to consider important"));
342 cl::desc(
"Enables edge fixup for important contexts"));
362template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
363class CallsiteContextGraph {
365 CallsiteContextGraph() =
default;
366 CallsiteContextGraph(
const CallsiteContextGraph &) =
default;
367 CallsiteContextGraph(CallsiteContextGraph &&) =
default;
371 EmitRemark =
nullptr,
372 bool AllowExtraAnalysis =
false);
376 void identifyClones();
383 bool assignFunctions();
389 EmitRemark =
nullptr)
const;
392 const CallsiteContextGraph &CCG) {
397 friend struct GraphTraits<
398 const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *>;
399 friend struct DOTGraphTraits<
400 const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *>;
402 void exportToDot(std::string Label)
const;
405 struct FuncInfo final
406 :
public std::pair<FuncTy *, unsigned > {
407 using Base = std::pair<FuncTy *, unsigned>;
408 FuncInfo(
const Base &
B) : Base(
B) {}
409 FuncInfo(FuncTy *
F =
nullptr,
unsigned CloneNo = 0) : Base(
F, CloneNo) {}
410 explicit operator bool()
const {
return this->first !=
nullptr; }
411 FuncTy *func()
const {
return this->first; }
412 unsigned cloneNo()
const {
return this->second; }
416 struct CallInfo final :
public std::pair<CallTy, unsigned > {
417 using Base = std::pair<CallTy, unsigned>;
418 CallInfo(
const Base &
B) : Base(
B) {}
419 CallInfo(CallTy
Call =
nullptr,
unsigned CloneNo = 0)
420 : Base(
Call, CloneNo) {}
421 explicit operator bool()
const {
return (
bool)this->first; }
422 CallTy call()
const {
return this->first; }
423 unsigned cloneNo()
const {
return this->second; }
424 void setCloneNo(
unsigned N) { this->second =
N; }
425 void print(raw_ostream &OS)
const {
426 if (!
operator bool()) {
432 OS <<
"\t(clone " << cloneNo() <<
")";
438 friend raw_ostream &
operator<<(raw_ostream &OS,
const CallInfo &
Call) {
458 bool Recursive =
false;
462 uint8_t AllocTypes = 0;
485 std::vector<std::shared_ptr<ContextEdge>> CalleeEdges;
489 std::vector<std::shared_ptr<ContextEdge>> CallerEdges;
493 bool useCallerEdgesForContextInfo()
const {
498 assert(!CalleeEdges.empty() || CallerEdges.empty() || IsAllocation ||
510 DenseSet<uint32_t> getContextIds()
const {
516 for (
auto &
Edge : CalleeEdges.empty() ? CallerEdges : CalleeEdges)
518 DenseSet<uint32_t> ContextIds;
521 CalleeEdges, useCallerEdgesForContextInfo()
523 : std::vector<std::shared_ptr<ContextEdge>>());
524 for (
const auto &
Edge : Edges)
531 uint8_t computeAllocType()
const {
533 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
534 uint8_t
AllocType = (uint8_t)AllocationType::None;
536 CalleeEdges, useCallerEdgesForContextInfo()
538 : std::vector<std::shared_ptr<ContextEdge>>());
539 for (
const auto &
Edge : Edges) {
550 bool emptyContextIds()
const {
552 CalleeEdges, useCallerEdgesForContextInfo()
554 : std::vector<std::shared_ptr<ContextEdge>>());
555 for (
const auto &
Edge : Edges) {
556 if (!
Edge->getContextIds().empty())
563 bool hasContextId(uint32_t Id)
const {
565 CalleeEdges, useCallerEdgesForContextInfo()
567 : std::vector<std::shared_ptr<ContextEdge>>());
568 for (
const auto &
Edge : Edges) {
569 if (
Edge->getContextIds().contains(Id))
578 void removeContextIdsNotPresent(DenseSet<uint32_t> &Ids)
const {
579 DenseSet<uint32_t> NotFound = Ids;
581 CalleeEdges, useCallerEdgesForContextInfo()
583 : std::vector<std::shared_ptr<ContextEdge>>());
584 for (
const auto &
Edge : Edges) {
585 const auto &EdgeIds =
Edge->getContextIds();
587 if (EdgeIds.size() < NotFound.size()) {
588 for (
auto Id : EdgeIds)
592 [&EdgeIds](uint32_t Id) {
return EdgeIds.contains(Id); });
594 if (NotFound.empty())
601 std::vector<ContextNode *> Clones;
604 ContextNode *CloneOf =
nullptr;
606 ContextNode(
bool IsAllocation) : IsAllocation(IsAllocation), Call() {}
608 ContextNode(
bool IsAllocation, CallInfo
C)
609 : IsAllocation(IsAllocation), Call(
C) {}
611 void addClone(ContextNode *Clone) {
613 CloneOf->Clones.push_back(Clone);
614 Clone->CloneOf = CloneOf;
616 Clones.push_back(Clone);
618 Clone->CloneOf =
this;
622 ContextNode *getOrigNode() {
628 const ContextNode *getOrigNode()
const {
635 unsigned int ContextId);
637 ContextEdge *findEdgeFromCallee(
const ContextNode *Callee);
638 ContextEdge *findEdgeFromCaller(
const ContextNode *Caller);
639 void eraseCalleeEdge(
const ContextEdge *
Edge);
640 void eraseCallerEdge(
const ContextEdge *
Edge);
642 void setCall(CallInfo
C) { Call = std::move(
C); }
644 bool hasCall()
const {
return (
bool)Call.call(); }
646 void printCall(raw_ostream &OS)
const { Call.print(OS); }
650 bool isRemoved()
const {
656 (AllocTypes == (uint8_t)AllocationType::None) ==
658 return AllocTypes == (uint8_t)AllocationType::None;
662 void print(raw_ostream &OS)
const;
664 friend raw_ostream &
operator<<(raw_ostream &OS,
const ContextNode &Node) {
678 uint8_t AllocTypes = 0;
686 bool IsBackedge =
false;
689 DenseSet<uint32_t> ContextIds;
691 ContextEdge(ContextNode *Callee, ContextNode *Caller, uint8_t
AllocType,
692 DenseSet<uint32_t> ContextIds)
693 : Callee(Callee), Caller(Caller), AllocTypes(
AllocType),
694 ContextIds(std::
move(ContextIds)) {}
696 DenseSet<uint32_t> &getContextIds() {
return ContextIds; }
700 inline void clear() {
702 AllocTypes = (uint8_t)AllocationType::None;
710 inline bool isRemoved()
const {
711 if (Callee || Caller)
716 assert(AllocTypes == (uint8_t)AllocationType::None);
717 assert(ContextIds.empty());
722 void print(raw_ostream &OS)
const;
724 friend raw_ostream &
operator<<(raw_ostream &OS,
const ContextEdge &
Edge) {
732 void removeNoneTypeCalleeEdges(ContextNode *Node);
733 void removeNoneTypeCallerEdges(ContextNode *Node);
735 recursivelyRemoveNoneTypeCalleeEdges(ContextNode *Node,
736 DenseSet<const ContextNode *> &Visited);
741 template <
class NodeT,
class IteratorT>
742 std::vector<ContextNode *>
743 getStackNodesForCallsite(CallStack<NodeT, IteratorT> &CallsiteContext);
747 ContextNode *addAllocNode(CallInfo
Call,
const FuncTy *
F);
750 template <
class NodeT,
class IteratorT>
751 void addStackNodesForMIB(
752 ContextNode *AllocNode, CallStack<NodeT, IteratorT> &StackContext,
755 std::map<uint64_t, uint32_t> &TotalSizeToContextIdTopNCold);
760 void updateStackNodes();
769 void fixupImportantContexts();
773 void handleCallsitesWithMultipleTargets();
776 void markBackedges();
786 bool partitionCallsByCallee(
788 std::vector<std::pair<CallInfo, ContextNode *>> &NewCallToNode);
792 MapVector<FuncTy *, std::vector<CallInfo>> FuncToCallsWithMetadata;
795 std::map<const ContextNode *, const FuncTy *> NodeToCallingFunc;
797 const FuncTy *getCallingFunc(
const ContextNode *
N)
const {
798 auto It = NodeToCallingFunc.find(
N);
799 return It != NodeToCallingFunc.end() ? It->second :
nullptr;
807 DenseSet<const FuncTy *> FunctionsWithCallers;
811 DenseSet<uint32_t> DotAllocContextIds;
814 using EdgeIter =
typename std::vector<std::shared_ptr<ContextEdge>>::iterator;
819 struct CallContextInfo {
827 std::vector<ContextNode *> StackNodes;
832 DenseSet<uint32_t> ContextIds;
837 DenseSet<uint32_t> TrimmedInlinedDupIds;
846 void removeEdgeFromGraph(ContextEdge *
Edge, EdgeIter *EI =
nullptr,
847 bool CalleeIter =
true);
855 void assignStackNodesPostOrder(
856 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
857 DenseMap<
uint64_t, std::vector<CallContextInfo>> &StackIdToMatchingCalls,
858 DenseMap<CallInfo, CallInfo> &CallToMatchingCall,
859 const DenseSet<uint32_t> &ImportantContextIds);
865 DenseSet<uint32_t> duplicateContextIds(
866 const DenseSet<uint32_t> &StackSequenceContextIds,
867 DenseMap<uint32_t, DenseSet<uint32_t>> &OldToNewContextIds,
868 function_ref<
void(uint32_t OldId, uint32_t NewId)> OnDuplicate =
nullptr);
871 void propagateDuplicateContextIds(
872 const DenseMap<uint32_t, DenseSet<uint32_t>> &OldToNewContextIds);
878 struct TrimmedAtNodeCache {
879 DenseMap<const ContextNode *, unsigned> NodeToIndex;
880 std::vector<DenseSet<uint32_t>> TrimmedAtNodeIds;
888 TrimmedAtNodeCache &Cache);
893 void connectNewNode(ContextNode *NewNode, ContextNode *OrigNode,
894 bool TowardsCallee,
const DenseSet<uint32_t> &ContextIds);
900 return static_cast<const DerivedCCG *
>(
this)->getStackId(IdOrIndex);
910 calleesMatch(CallTy
Call, EdgeIter &EI,
911 MapVector<CallInfo, ContextNode *> &TailCallToContextNodeMap);
915 const FuncTy *getCalleeFunc(CallTy
Call) {
916 return static_cast<DerivedCCG *
>(
this)->getCalleeFunc(
Call);
922 bool calleeMatchesFunc(
923 CallTy
Call,
const FuncTy *Func,
const FuncTy *CallerFunc,
924 std::vector<std::pair<CallTy, FuncTy *>> &FoundCalleeChain) {
925 return static_cast<DerivedCCG *
>(
this)->calleeMatchesFunc(
926 Call, Func, CallerFunc, FoundCalleeChain);
930 bool sameCallee(CallTy Call1, CallTy Call2) {
931 return static_cast<DerivedCCG *
>(
this)->sameCallee(Call1, Call2);
936 std::vector<ContextNode *> getStackNodesForCall(CallTy
Call) {
937 return static_cast<DerivedCCG *
>(
this)->getStackNodesForCall(
Call);
942 return static_cast<DerivedCCG *
>(
this)->getLastStackId(
Call);
950 AllocTypeAmbiguous++;
953 static_cast<DerivedCCG *
>(
this)->updateAllocationCall(
Call,
AllocType);
958 return static_cast<const DerivedCCG *
>(
this)->getAllocationCallType(
Call);
963 void updateCall(CallInfo &CallerCall, FuncInfo CalleeFunc) {
964 static_cast<DerivedCCG *
>(
this)->updateCall(CallerCall, CalleeFunc);
970 FuncInfo cloneFunctionForCallsite(
971 FuncInfo &Func, CallInfo &
Call, DenseMap<CallInfo, CallInfo> &CallMap,
972 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
973 return static_cast<DerivedCCG *
>(
this)->cloneFunctionForCallsite(
974 Func,
Call, CallMap, CallsWithMetadataInFunc, CloneNo);
979 std::string getLabel(
const FuncTy *Func,
const CallTy
Call,
980 unsigned CloneNo)
const {
981 return static_cast<const DerivedCCG *
>(
this)->getLabel(Func,
Call, CloneNo);
985 std::string getFuncName(
const FuncTy *Func,
unsigned CloneNo = 0)
const {
986 return static_cast<const DerivedCCG *
>(
this)->getFuncName(Func, CloneNo);
991 bool isFuncDead(
const FuncTy *Func)
const {
992 return static_cast<const DerivedCCG *
>(
this)->isFuncDead(Func);
996 void populateFunctionsWithCallers() {
997 static_cast<DerivedCCG *
>(
this)->populateFunctionsWithCallers();
1002 void capturePreCloningContextInfo();
1007 std::string formatContextReportSuffix(
const ContextNode *Node,
1011 ContextNode *createNewNode(
bool IsAllocation,
const FuncTy *
F =
nullptr,
1012 CallInfo
C = CallInfo()) {
1013 NodeOwner.push_back(std::make_unique<ContextNode>(IsAllocation,
C));
1014 auto *NewNode = NodeOwner.back().get();
1016 NodeToCallingFunc[NewNode] =
F;
1017 NewNode->NodeId = NodeOwner.size();
1022 ContextNode *getNodeForInst(
const CallInfo &
C);
1023 ContextNode *getNodeForAlloc(
const CallInfo &
C);
1024 ContextNode *getNodeForStackId(
uint64_t StackId);
1028 uint8_t computeAllocType(DenseSet<uint32_t> &ContextIds)
const;
1033 uint8_t intersectAllocTypesImpl(
const DenseSet<uint32_t> &Node1Ids,
1034 const DenseSet<uint32_t> &Node2Ids)
const;
1038 uint8_t intersectAllocTypes(
const DenseSet<uint32_t> &Node1Ids,
1039 const DenseSet<uint32_t> &Node2Ids)
const;
1046 moveEdgeToNewCalleeClone(
const std::shared_ptr<ContextEdge> &
Edge,
1047 DenseSet<uint32_t> ContextIdsToMove = {});
1053 void moveEdgeToExistingCalleeClone(
const std::shared_ptr<ContextEdge> &
Edge,
1054 ContextNode *NewCallee,
1055 bool NewClone =
false,
1056 DenseSet<uint32_t> ContextIdsToMove = {});
1063 void moveCalleeEdgeToNewCaller(
const std::shared_ptr<ContextEdge> &
Edge,
1064 ContextNode *NewCaller);
1067 void markBackedges(ContextNode *Node, DenseSet<const ContextNode *> &Visited,
1068 DenseSet<const ContextNode *> &CurrentStack);
1072 mergeClones(ContextNode *Node, DenseSet<const ContextNode *> &Visited,
1073 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode);
1075 void mergeNodeCalleeClones(
1076 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
1077 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode);
1080 void findOtherCallersToShareMerge(
1081 ContextNode *Node, std::vector<std::shared_ptr<ContextEdge>> &CalleeEdges,
1082 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode,
1083 DenseSet<ContextNode *> &OtherCallersToShareMerge);
1089 void identifyClones(ContextNode *Node, DenseSet<const ContextNode *> &Visited,
1090 const DenseSet<uint32_t> &AllocContextIds);
1095 struct ImplicitSource {
1097 const ContextNode *Source;
1105 using ImplicitSourceMap =
1106 DenseMap<std::pair<const ContextNode *, unsigned>, ImplicitSource>;
1113 void assignImplicitCallers(
1114 ContextNode *Node,
const DenseSet<uint32_t> &TrimmedContextIds,
1115 DenseMap<ContextNode *, FuncInfo> &CallsiteToCalleeFuncCloneMap,
1116 const std::map<FuncInfo, ContextNode *> &FuncCloneToCurNodeCloneMap,
1117 ImplicitSourceMap &ImplicitSources);
1123 static const ContextNode *resolveImplicitSource(
const ContextNode *Node,
1124 const ImplicitSource &Src);
1127 DenseMap<uint32_t, AllocationType> ContextIdToAllocationType;
1133 DenseMap<uint32_t, std::vector<ContextTotalSize>> ContextIdToContextSizeInfos;
1139 DenseMap<uint64_t, ContextNode *> StackEntryIdToContextNodeMap;
1143 struct ImportantContextInfo {
1145 std::vector<uint64_t> StackIds;
1148 unsigned MaxLength = 0;
1152 std::map<std::vector<uint64_t>, ContextNode *> StackIdsToNode;
1156 DenseMap<uint32_t, ImportantContextInfo> ImportantContextIdInfo;
1165 const DenseSet<uint32_t> &NodeContextIds,
1166 const DenseSet<uint32_t> &ImportantContextIds) {
1171 DenseSet<uint32_t> Ids =
1175 std::vector<uint64_t> StackIds;
1176 StackIds.reserve(StackNodes.
size());
1177 for (
const ContextNode *
N : StackNodes)
1178 StackIds.push_back(
N->OrigStackOrAllocId);
1179 auto Size = StackIds.size();
1180 for (
auto Id : Ids) {
1181 auto &
Entry = ImportantContextIdInfo[
Id];
1190 MapVector<CallInfo, ContextNode *> AllocationCallToContextNodeMap;
1191 MapVector<CallInfo, ContextNode *> NonAllocationCallToContextNodeMap;
1194 std::vector<std::unique_ptr<ContextNode>> NodeOwner;
1200 unsigned int LastContextId = 0;
1208 struct PreCloningContextInfo {
1212 std::vector<const ContextNode *> Chain;
1222 unsigned MaxMatchedFrame = 0;
1225 bool OutermostMatchedNodeHasOtherCallers =
false;
1230 bool StoppedAtRecursive =
false;
1231 bool StoppedAtMismatchedCallee =
false;
1234 const FuncTy *UnmatchedCallingFunc =
nullptr;
1237 DenseMap<uint32_t, PreCloningContextInfo> PreCloningContextInfoMap;
1240 DenseSet<const ContextNode *> PreCloningAllocHasMatchedCaller;
1243 DenseMap<const FuncTy *, unsigned> FuncToNumClones;
1248 DenseMap<std::pair<const ContextNode *, unsigned>,
unsigned>
1249 OrigNodeAndCloneToCalleeClone;
1253 DenseMap<std::pair<const ContextNode *, unsigned>,
const ContextNode *>
1254 OrigAllocAndCloneToNode;
1257template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1259 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode;
1260template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1262 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge;
1263template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1265 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::FuncInfo;
1266template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1268 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::CallInfo;
1271class ModuleCallsiteContextGraph
1272 :
public CallsiteContextGraph<ModuleCallsiteContextGraph, Function,
1275 ModuleCallsiteContextGraph(
1277 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter);
1280 friend CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
1285 bool calleeMatchesFunc(
1287 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain);
1288 bool sameCallee(Instruction *Call1, Instruction *Call2);
1289 bool findProfiledCalleeThroughTailCalls(
1291 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain,
1292 bool &FoundMultipleCalleeChains);
1294 std::vector<ContextNode *> getStackNodesForCall(Instruction *
Call);
1297 void updateCall(CallInfo &CallerCall, FuncInfo CalleeFunc);
1298 CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
1300 cloneFunctionForCallsite(FuncInfo &Func, CallInfo &
Call,
1301 DenseMap<CallInfo, CallInfo> &CallMap,
1302 std::vector<CallInfo> &CallsWithMetadataInFunc,
1304 std::string getLabel(
const Function *Func,
const Instruction *
Call,
1305 unsigned CloneNo)
const;
1306 std::string getFuncName(
const Function *Func,
unsigned CloneNo = 0)
const;
1307 bool isFuncDead(
const Function *Func)
const {
return false; }
1308 void populateFunctionsWithCallers();
1311 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter;
1317struct IndexCall :
public PointerUnion<CallsiteInfo *, AllocInfo *> {
1318 IndexCall() : PointerUnion() {}
1319 IndexCall(std::nullptr_t) : IndexCall() {}
1320 IndexCall(CallsiteInfo *StackNode) : PointerUnion(StackNode) {}
1321 IndexCall(AllocInfo *AllocNode) : PointerUnion(AllocNode) {}
1322 IndexCall(PointerUnion PT) : PointerUnion(PT) {}
1324 IndexCall *operator->() {
return this; }
1326 void print(raw_ostream &OS)
const {
1327 PointerUnion<CallsiteInfo *, AllocInfo *>
Base = *
this;
1352class IndexCallsiteContextGraph
1353 :
public CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
1356 IndexCallsiteContextGraph(
1357 ModuleSummaryIndex &Index,
1361 ~IndexCallsiteContextGraph() {
1366 for (
auto &
I : FunctionCalleesToSynthesizedCallsiteInfos) {
1368 for (
auto &Callsite :
I.second)
1369 FS->addCallsite(std::move(*Callsite.second));
1374 friend CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
1378 const FunctionSummary *getCalleeFunc(IndexCall &
Call);
1379 bool calleeMatchesFunc(
1380 IndexCall &
Call,
const FunctionSummary *Func,
1381 const FunctionSummary *CallerFunc,
1382 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain);
1383 bool sameCallee(IndexCall &Call1, IndexCall &Call2);
1384 bool findProfiledCalleeThroughTailCalls(
1385 ValueInfo ProfiledCallee, ValueInfo CurCallee,
unsigned Depth,
1386 std::vector<std::pair<ValueInfo, FunctionSummary *>> &FoundCalleeChain,
1387 bool &FoundMultipleCalleeChains);
1389 std::vector<ContextNode *> getStackNodesForCall(IndexCall &
Call);
1392 void updateCall(CallInfo &CallerCall, FuncInfo CalleeFunc);
1393 CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
1394 IndexCall>::FuncInfo
1395 cloneFunctionForCallsite(FuncInfo &Func, CallInfo &
Call,
1396 DenseMap<CallInfo, CallInfo> &CallMap,
1397 std::vector<CallInfo> &CallsWithMetadataInFunc,
1399 std::string getLabel(
const FunctionSummary *Func,
const IndexCall &
Call,
1400 unsigned CloneNo)
const;
1401 std::string getFuncName(
const FunctionSummary *Func,
1402 unsigned CloneNo = 0)
const;
1403 bool isFuncDead(
const FunctionSummary *Func)
const;
1404 void populateFunctionsWithCallers();
1405 DenseSet<GlobalValue::GUID> findAliaseeGUIDsPrevailingInDifferentModule();
1409 std::map<const FunctionSummary *, ValueInfo> FSToVIMap;
1411 const ModuleSummaryIndex &Index;
1419 DenseMap<FunctionSummary *,
1420 std::map<ValueInfo, std::unique_ptr<CallsiteInfo>>>
1421 FunctionCalleesToSynthesizedCallsiteInfos;
1432 :
public DenseMapInfo<std::pair<IndexCall, unsigned>> {};
1435 :
public DenseMapInfo<PointerUnion<CallsiteInfo *, AllocInfo *>> {};
1456template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1457bool allocTypesMatch(
1458 const std::vector<uint8_t> &InAllocTypes,
1459 const std::vector<std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>>>
1463 assert(InAllocTypes.size() == Edges.size());
1465 InAllocTypes.begin(), InAllocTypes.end(), Edges.begin(), Edges.end(),
1467 const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &r) {
1471 if (l == (uint8_t)AllocationType::None ||
1472 r->AllocTypes == (uint8_t)AllocationType::None)
1474 return allocTypeToUse(l) == allocTypeToUse(r->AllocTypes);
1483template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1484bool allocTypesMatchClone(
1485 const std::vector<uint8_t> &InAllocTypes,
1486 const ContextNode<DerivedCCG, FuncTy, CallTy> *Clone) {
1487 const ContextNode<DerivedCCG, FuncTy, CallTy> *
Node = Clone->CloneOf;
1491 assert(InAllocTypes.size() ==
Node->CalleeEdges.size());
1495 for (
const auto &
E : Clone->CalleeEdges) {
1497 EdgeCalleeMap[
E->Callee] =
E->AllocTypes;
1501 for (
unsigned I = 0;
I <
Node->CalleeEdges.size();
I++) {
1502 auto Iter = EdgeCalleeMap.
find(
Node->CalleeEdges[
I]->Callee);
1504 if (Iter == EdgeCalleeMap.
end())
1512 if (allocTypeToUse(Iter->second) != allocTypeToUse(InAllocTypes[
I]))
1520template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1521typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1522CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForInst(
1523 const CallInfo &
C) {
1524 ContextNode *
Node = getNodeForAlloc(
C);
1528 return NonAllocationCallToContextNodeMap.lookup(
C);
1531template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1532typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1533CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForAlloc(
1534 const CallInfo &
C) {
1535 return AllocationCallToContextNodeMap.lookup(
C);
1538template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1539typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1540CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForStackId(
1542 auto StackEntryNode = StackEntryIdToContextNodeMap.
find(StackId);
1543 if (StackEntryNode != StackEntryIdToContextNodeMap.
end())
1544 return StackEntryNode->second;
1548template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1549void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1551 unsigned int ContextId) {
1552 for (
auto &
Edge : CallerEdges) {
1553 if (
Edge->Caller == Caller) {
1555 Edge->getContextIds().insert(ContextId);
1559 std::shared_ptr<ContextEdge>
Edge = std::make_shared<ContextEdge>(
1560 this, Caller, (uint8_t)
AllocType, DenseSet<uint32_t>({ContextId}));
1561 CallerEdges.push_back(
Edge);
1565template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1566void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::removeEdgeFromGraph(
1567 ContextEdge *
Edge, EdgeIter *EI,
bool CalleeIter) {
1583 auto CalleeCallerCount =
Callee->CallerEdges.size();
1584 auto CallerCalleeCount =
Caller->CalleeEdges.size();
1589 }
else if (CalleeIter) {
1591 *EI =
Caller->CalleeEdges.erase(*EI);
1594 *EI =
Callee->CallerEdges.erase(*EI);
1596 assert(
Callee->CallerEdges.size() < CalleeCallerCount);
1597 assert(
Caller->CalleeEdges.size() < CallerCalleeCount);
1600template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1601void CallsiteContextGraph<
1602 DerivedCCG, FuncTy, CallTy>::removeNoneTypeCalleeEdges(ContextNode *Node) {
1603 for (
auto EI =
Node->CalleeEdges.begin(); EI !=
Node->CalleeEdges.end();) {
1605 if (
Edge->AllocTypes == (uint8_t)AllocationType::None) {
1607 removeEdgeFromGraph(
Edge.get(), &EI,
true);
1613template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1614void CallsiteContextGraph<
1615 DerivedCCG, FuncTy, CallTy>::removeNoneTypeCallerEdges(ContextNode *Node) {
1616 for (
auto EI =
Node->CallerEdges.begin(); EI !=
Node->CallerEdges.end();) {
1618 if (
Edge->AllocTypes == (uint8_t)AllocationType::None) {
1620 Edge->Caller->eraseCalleeEdge(
Edge.get());
1621 EI =
Node->CallerEdges.erase(EI);
1627template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1628typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge *
1629CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1630 findEdgeFromCallee(
const ContextNode *Callee) {
1631 for (
const auto &
Edge : CalleeEdges)
1632 if (
Edge->Callee == Callee)
1637template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1638typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge *
1639CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1640 findEdgeFromCaller(
const ContextNode *Caller) {
1641 for (
const auto &
Edge : CallerEdges)
1642 if (
Edge->Caller == Caller)
1647template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1648void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1649 eraseCalleeEdge(
const ContextEdge *
Edge) {
1651 CalleeEdges, [
Edge](
const std::shared_ptr<ContextEdge> &CalleeEdge) {
1652 return CalleeEdge.get() ==
Edge;
1654 assert(EI != CalleeEdges.end());
1655 CalleeEdges.erase(EI);
1658template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1659void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1660 eraseCallerEdge(
const ContextEdge *
Edge) {
1662 CallerEdges, [
Edge](
const std::shared_ptr<ContextEdge> &CallerEdge) {
1663 return CallerEdge.get() ==
Edge;
1665 assert(EI != CallerEdges.end());
1666 CallerEdges.erase(EI);
1669template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1670uint8_t CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::computeAllocType(
1671 DenseSet<uint32_t> &ContextIds)
const {
1673 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
1674 uint8_t
AllocType = (uint8_t)AllocationType::None;
1675 for (
auto Id : ContextIds) {
1676 AllocType |= (uint8_t)ContextIdToAllocationType.
at(Id);
1684template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1686CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::intersectAllocTypesImpl(
1687 const DenseSet<uint32_t> &Node1Ids,
1688 const DenseSet<uint32_t> &Node2Ids)
const {
1690 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
1691 uint8_t
AllocType = (uint8_t)AllocationType::None;
1692 for (
auto Id : Node1Ids) {
1693 if (!Node2Ids.
count(Id))
1695 AllocType |= (uint8_t)ContextIdToAllocationType.
at(Id);
1703template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1704uint8_t CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::intersectAllocTypes(
1705 const DenseSet<uint32_t> &Node1Ids,
1706 const DenseSet<uint32_t> &Node2Ids)
const {
1707 if (Node1Ids.
size() < Node2Ids.
size())
1708 return intersectAllocTypesImpl(Node1Ids, Node2Ids);
1710 return intersectAllocTypesImpl(Node2Ids, Node1Ids);
1713template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1714typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1715CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::addAllocNode(
1716 CallInfo
Call,
const FuncTy *
F) {
1718 ContextNode *AllocNode = createNewNode(
true,
F,
Call);
1719 AllocationCallToContextNodeMap[
Call] = AllocNode;
1721 AllocNode->OrigStackOrAllocId = LastContextId;
1724 AllocNode->AllocTypes = (uint8_t)AllocationType::None;
1740template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1741template <
class NodeT,
class IteratorT>
1742void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::addStackNodesForMIB(
1743 ContextNode *AllocNode, CallStack<NodeT, IteratorT> &StackContext,
1746 std::map<uint64_t, uint32_t> &TotalSizeToContextIdTopNCold) {
1752 ContextIdToAllocationType[++LastContextId] =
AllocType;
1754 bool IsImportant =
false;
1755 if (!ContextSizeInfo.
empty()) {
1756 auto &
Entry = ContextIdToContextSizeInfos[LastContextId];
1761 for (
auto &CSI : ContextSizeInfo)
1762 TotalCold += CSI.TotalSize;
1768 TotalCold > TotalSizeToContextIdTopNCold.begin()->first) {
1771 auto IdToRemove = TotalSizeToContextIdTopNCold.begin()->second;
1772 TotalSizeToContextIdTopNCold.erase(
1773 TotalSizeToContextIdTopNCold.begin());
1775 ImportantContextIdInfo.
erase(IdToRemove);
1777 TotalSizeToContextIdTopNCold[TotalCold] = LastContextId;
1781 Entry.insert(
Entry.begin(), ContextSizeInfo.begin(), ContextSizeInfo.end());
1785 AllocNode->AllocTypes |= (uint8_t)
AllocType;
1790 ContextNode *PrevNode = AllocNode;
1794 SmallSet<uint64_t, 8> StackIdSet;
1797 ContextIter != StackContext.
end(); ++ContextIter) {
1798 auto StackId = getStackId(*ContextIter);
1800 ImportantContextIdInfo[LastContextId].StackIds.push_back(StackId);
1801 ContextNode *StackNode = getNodeForStackId(StackId);
1803 StackNode = createNewNode(
false);
1804 StackEntryIdToContextNodeMap[StackId] = StackNode;
1805 StackNode->OrigStackOrAllocId = StackId;
1810 auto Ins = StackIdSet.
insert(StackId);
1812 StackNode->Recursive =
true;
1814 StackNode->AllocTypes |= (uint8_t)
AllocType;
1815 PrevNode->addOrUpdateCallerEdge(StackNode,
AllocType, LastContextId);
1816 PrevNode = StackNode;
1820template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1822CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::duplicateContextIds(
1823 const DenseSet<uint32_t> &StackSequenceContextIds,
1824 DenseMap<uint32_t, DenseSet<uint32_t>> &OldToNewContextIds,
1825 function_ref<
void(uint32_t OldId, uint32_t NewId)> OnDuplicate) {
1826 DenseSet<uint32_t> NewContextIds;
1827 NewContextIds.
reserve(StackSequenceContextIds.
size());
1828 for (
auto OldId : StackSequenceContextIds) {
1829 NewContextIds.
insert(++LastContextId);
1830 OldToNewContextIds[OldId].insert(LastContextId);
1832 OnDuplicate(OldId, LastContextId);
1835 ContextIdToAllocationType[LastContextId] = ContextIdToAllocationType[OldId];
1836 auto CSI = ContextIdToContextSizeInfos.
find(OldId);
1837 if (CSI != ContextIdToContextSizeInfos.
end())
1838 ContextIdToContextSizeInfos[LastContextId] = CSI->second;
1839 if (DotAllocContextIds.
contains(OldId))
1840 DotAllocContextIds.
insert(LastContextId);
1842 return NewContextIds;
1845template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1846void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
1847 propagateDuplicateContextIds(
1848 const DenseMap<uint32_t, DenseSet<uint32_t>> &OldToNewContextIds) {
1850 auto GetNewIds = [&OldToNewContextIds](
const DenseSet<uint32_t> &ContextIds) {
1851 DenseSet<uint32_t> NewIds;
1852 for (
auto Id : ContextIds)
1853 if (
auto NewId = OldToNewContextIds.find(Id);
1854 NewId != OldToNewContextIds.end())
1860 auto UpdateCallers = [&](ContextNode *
Node,
1861 DenseSet<const ContextEdge *> &Visited,
1862 auto &&UpdateCallers) ->
void {
1863 for (
const auto &
Edge :
Node->CallerEdges) {
1867 ContextNode *NextNode =
Edge->Caller;
1868 DenseSet<uint32_t> NewIdsToAdd = GetNewIds(
Edge->getContextIds());
1871 if (!NewIdsToAdd.
empty()) {
1872 Edge->getContextIds().insert_range(NewIdsToAdd);
1873 UpdateCallers(NextNode, Visited, UpdateCallers);
1878 DenseSet<const ContextEdge *> Visited;
1879 for (
auto &Entry : AllocationCallToContextNodeMap) {
1881 UpdateCallers(Node, Visited, UpdateCallers);
1885template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1886void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::connectNewNode(
1887 ContextNode *NewNode, ContextNode *OrigNode,
bool TowardsCallee,
1888 const DenseSet<uint32_t> &ContextIds) {
1890 TowardsCallee ? OrigNode->CalleeEdges : OrigNode->CallerEdges;
1892 for (
auto EI = OrigEdges.begin(); EI != OrigEdges.end();) {
1894 DenseSet<uint32_t> NewEdgeContextIds;
1899 if (NewEdgeContextIds.
empty()) {
1903 if (TowardsCallee) {
1904 uint8_t NewAllocType = computeAllocType(NewEdgeContextIds);
1905 auto NewEdge = std::make_shared<ContextEdge>(
1906 Edge->Callee, NewNode, NewAllocType, std::move(NewEdgeContextIds));
1907 NewNode->CalleeEdges.push_back(NewEdge);
1908 NewEdge->Callee->CallerEdges.push_back(NewEdge);
1910 uint8_t NewAllocType = computeAllocType(NewEdgeContextIds);
1911 auto NewEdge = std::make_shared<ContextEdge>(
1912 NewNode,
Edge->Caller, NewAllocType, std::move(NewEdgeContextIds));
1913 NewNode->CallerEdges.push_back(NewEdge);
1914 NewEdge->Caller->CalleeEdges.push_back(NewEdge);
1918 if (
Edge->getContextIds().empty()) {
1919 removeEdgeFromGraph(
Edge.get(), &EI, TowardsCallee);
1922 Edge->AllocTypes = computeAllocType(
Edge->getContextIds());
1927template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1929 const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &Edge) {
1933 assert(!Edge->ContextIds.empty());
1936template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1938 bool CheckEdges =
true) {
1939 if (
Node->isRemoved())
1943 auto NodeContextIds =
Node->getContextIds();
1947 if (
Node->CallerEdges.size()) {
1949 Node->CallerEdges.front()->ContextIds);
1953 set_union(CallerEdgeContextIds, Edge->ContextIds);
1960 NodeContextIds == CallerEdgeContextIds ||
1963 if (
Node->CalleeEdges.size()) {
1965 Node->CalleeEdges.front()->ContextIds);
1969 set_union(CalleeEdgeContextIds, Edge->getContextIds());
1975 NodeContextIds == CalleeEdgeContextIds);
1984 for (
const auto &
E :
Node->CalleeEdges)
1990template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1991void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
1992 assignStackNodesPostOrder(ContextNode *Node,
1993 DenseSet<const ContextNode *> &Visited,
1994 DenseMap<
uint64_t, std::vector<CallContextInfo>>
1995 &StackIdToMatchingCalls,
1996 DenseMap<CallInfo, CallInfo> &CallToMatchingCall,
1997 const DenseSet<uint32_t> &ImportantContextIds) {
2005 auto CallerEdges =
Node->CallerEdges;
2006 for (
auto &
Edge : CallerEdges) {
2008 if (
Edge->isRemoved()) {
2012 assignStackNodesPostOrder(
Edge->Caller, Visited, StackIdToMatchingCalls,
2013 CallToMatchingCall, ImportantContextIds);
2022 if (
Node->IsAllocation ||
2023 !StackIdToMatchingCalls.count(
Node->OrigStackOrAllocId))
2026 auto &Calls = StackIdToMatchingCalls[
Node->OrigStackOrAllocId];
2030 if (Calls.size() == 1) {
2031 auto &[
Call, StackNodes,
Func, SavedContextIds, TrimmedInlinedDupIds] =
2033 if (StackNodes.size() == 1) {
2034 assert(SavedContextIds.empty());
2036 assert(TrimmedInlinedDupIds.empty());
2038 assert(Node == StackNodes[0]);
2039 if (
Node->Recursive)
2042 NonAllocationCallToContextNodeMap[
Call] =
Node;
2044 recordStackNode(StackNodes, Node,
Node->getContextIds(),
2045 ImportantContextIds);
2054 ContextNode *LastNode = getNodeForStackId(LastId);
2057 assert(LastNode == Node);
2059 ContextNode *LastNode =
Node;
2064 DenseSet<uint32_t> LastNodeContextIds = LastNode->getContextIds();
2066 [[maybe_unused]]
bool PrevIterCreatedNode =
false;
2067 bool CreatedNode =
false;
2068 for (
unsigned I = 0;
I < Calls.size();
2069 I++, PrevIterCreatedNode = CreatedNode) {
2070 CreatedNode =
false;
2071 auto &[
Call, StackNodes,
Func, SavedContextIds, TrimmedInlinedDupIds] =
2075 if (SavedContextIds.empty() && TrimmedInlinedDupIds.empty()) {
2082 auto MatchingCall = CallToMatchingCall[
Call];
2083 if (!NonAllocationCallToContextNodeMap.contains(MatchingCall)) {
2087 assert(
I > 0 && !PrevIterCreatedNode);
2090 NonAllocationCallToContextNodeMap[MatchingCall]->MatchingCalls.push_back(
2095 assert(LastNode == StackNodes.back());
2104 ContextNode *PrevNode = LastNode;
2105 bool Skip = SavedContextIds.empty();
2108 for (
auto NodeIter = StackNodes.rbegin() + 1;
2109 !Skip && NodeIter != StackNodes.rend(); NodeIter++) {
2110 ContextNode *CurNode = *NodeIter;
2114 assert(!CurNode->Recursive);
2116 auto *
Edge = CurNode->findEdgeFromCaller(PrevNode);
2128 if (SavedContextIds.empty()) {
2134 SavedContextIds.clear();
2141 if (!TrimmedInlinedDupIds.empty()) {
2142 StackNodes[0]->removeContextIdsNotPresent(TrimmedInlinedDupIds);
2143 SavedContextIds.insert_range(TrimmedInlinedDupIds);
2145 if (SavedContextIds.empty())
2149 ContextNode *NewNode = createNewNode(
false, Func,
Call);
2150 NonAllocationCallToContextNodeMap[
Call] = NewNode;
2152 NewNode->AllocTypes = computeAllocType(SavedContextIds);
2154 ContextNode *FirstNode = StackNodes[0];
2160 connectNewNode(NewNode, FirstNode,
true, SavedContextIds);
2165 connectNewNode(NewNode, LastNode,
false, SavedContextIds);
2170 for (ContextNode *CurNode : StackNodes) {
2177 auto *PrevEdge = CurNode->findEdgeFromCallee(PrevNode);
2184 set_subtract(PrevEdge->getContextIds(), SavedContextIds);
2185 if (PrevEdge->getContextIds().empty())
2186 removeEdgeFromGraph(PrevEdge);
2188 PrevEdge->AllocTypes = computeAllocType(PrevEdge->getContextIds());
2193 CurNode->AllocTypes = CurNode->CalleeEdges.empty()
2194 ? (uint8_t)AllocationType::None
2195 : CurNode->computeAllocType();
2199 recordStackNode(StackNodes, NewNode, SavedContextIds, ImportantContextIds);
2203 for (ContextNode *CurNode : StackNodes) {
2212template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2213void CallsiteContextGraph<DerivedCCG, FuncTy,
2214 CallTy>::fixupImportantContexts() {
2215 if (ImportantContextIdInfo.
empty())
2219 NumImportantContextIds = ImportantContextIdInfo.
size();
2225 exportToDot(
"beforestackfixup");
2250 for (
auto &[CurContextId, Info] : ImportantContextIdInfo) {
2251 if (
Info.StackIdsToNode.empty())
2254 ContextNode *PrevNode =
nullptr;
2255 ContextNode *CurNode =
nullptr;
2256 DenseSet<const ContextEdge *> VisitedEdges;
2257 ArrayRef<uint64_t> AllStackIds(
Info.StackIds);
2260 for (
unsigned I = 0;
I < AllStackIds.size();
I++, PrevNode = CurNode) {
2264 auto LenToEnd = AllStackIds.size() -
I;
2272 auto CheckStackIds = AllStackIds.slice(
I, Len);
2273 auto EntryIt =
Info.StackIdsToNode.find(CheckStackIds);
2274 if (EntryIt ==
Info.StackIdsToNode.end())
2276 CurNode = EntryIt->second;
2293 auto *CurEdge = PrevNode->findEdgeFromCaller(CurNode);
2296 if (CurEdge->getContextIds().insert(CurContextId).second) {
2297 NumFixupEdgeIdsInserted++;
2302 NumFixupEdgesAdded++;
2303 DenseSet<uint32_t> ContextIds({CurContextId});
2304 auto AllocType = computeAllocType(ContextIds);
2305 auto NewEdge = std::make_shared<ContextEdge>(
2306 PrevNode, CurNode,
AllocType, std::move(ContextIds));
2307 PrevNode->CallerEdges.push_back(NewEdge);
2308 CurNode->CalleeEdges.push_back(NewEdge);
2310 CurEdge = NewEdge.get();
2313 VisitedEdges.
insert(CurEdge);
2316 for (
auto &
Edge : PrevNode->CallerEdges) {
2320 Edge->getContextIds().erase(CurContextId);
2338template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2339DenseSet<uint32_t> CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
2341 TrimmedAtNodeCache &Cache) {
2343 DenseSet<uint32_t>
Result;
2348 auto GetTrimmedAtNodeIndex = [&Cache](
const ContextNode *
Node) {
2350 Cache.NodeToIndex.try_emplace(Node, Cache.TrimmedAtNodeIds.size());
2351 unsigned Index = It->second;
2356 DenseSet<uint32_t> &Trimmed = Cache.TrimmedAtNodeIds.emplace_back();
2357 for (
const auto &CalleeEdge :
Node->CalleeEdges)
2359 for (
const auto &CallerEdge :
Node->CallerEdges) {
2361 if (Trimmed.
empty())
2369 SmallVector<unsigned, 8> TrimmedAtNodeIdsIndices;
2370 bool AnyTrimmed =
false;
2371 for (ContextNode *Node : StackNodes.
drop_back()) {
2373 if (
Node->Recursive)
2375 unsigned Index = GetTrimmedAtNodeIndex(Node);
2376 AnyTrimmed |= !Cache.TrimmedAtNodeIds[
Index].empty();
2377 TrimmedAtNodeIdsIndices.
push_back(Index);
2396 Result = Cache.TrimmedAtNodeIds[TrimmedAtNodeIdsIndices[0]];
2397 DenseSet<uint32_t> PrefixContextIds;
2398 for (
unsigned I = 1;
I < TrimmedAtNodeIdsIndices.
size();
I++) {
2399 auto *
Edge = StackNodes[
I]->findEdgeFromCallee(StackNodes[
I - 1]);
2403 PrefixContextIds =
Edge->getContextIds();
2406 if (PrefixContextIds.
empty())
2409 PrefixContextIds, Cache.TrimmedAtNodeIds[TrimmedAtNodeIdsIndices[
I]]));
2414template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2415void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::updateStackNodes() {
2423 DenseMap<uint64_t, std::vector<CallContextInfo>> StackIdToMatchingCalls;
2424 for (
auto &[Func, CallsWithMetadata] : FuncToCallsWithMetadata) {
2425 for (
auto &
Call : CallsWithMetadata) {
2427 if (AllocationCallToContextNodeMap.count(
Call))
2429 std::vector<ContextNode *> StackNodes = getStackNodesForCall(
Call.call());
2432 if (StackNodes.empty())
2436 uint64_t LastId = StackNodes.back()->OrigStackOrAllocId;
2437 StackIdToMatchingCalls[LastId].push_back(
2438 {
Call.call(), std::move(StackNodes),
Func, {}, {}});
2454 return std::lexicographical_compare(
2455 A.begin(),
A.end(),
B.begin(),
B.end(),
2456 [](
const ContextNode *
X,
const ContextNode *
Y) {
2457 return X->OrigStackOrAllocId < Y->OrigStackOrAllocId;
2463 DenseMap<CallInfo, CallInfo> CallToMatchingCall;
2464 for (
auto &Entry : StackIdToMatchingCalls) {
2465 auto &Calls =
Entry.second;
2466 if (Calls.size() == 1)
2468 DenseMap<const FuncTy *, unsigned> FuncToIndex;
2469 for (
const auto &[Idx, CallCtxInfo] :
enumerate(Calls))
2470 FuncToIndex.
insert({CallCtxInfo.Func,
Idx});
2471 auto CallLess = [&FuncToIndex, &StackIdsLess](
const CallContextInfo &
A,
2472 const CallContextInfo &
B) {
2473 return A.StackNodes.size() >
B.StackNodes.size() ||
2474 (
A.StackNodes.size() ==
B.StackNodes.size() &&
2475 (StackIdsLess(
A.StackNodes,
B.StackNodes) ||
2476 (
A.StackNodes ==
B.StackNodes &&
2477 FuncToIndex[
A.Func] < FuncToIndex[
B.Func])));
2484 unsigned FirstInRun = 0;
2485 for (
unsigned I = 1;
I < Calls.size();
I++) {
2486 if (Calls[
I].Func != Calls[FirstInRun].Func ||
2487 Calls[
I].StackNodes != Calls[FirstInRun].StackNodes) {
2491 CallToMatchingCall[Calls[
I].Call] = Calls[FirstInRun].Call;
2501 DenseMap<uint32_t, DenseSet<uint32_t>> OldToNewContextIds;
2517 std::vector<ArrayRef<ContextNode *>> TrimmedInlinedDupCreatorNodes;
2520 DenseMap<uint32_t, SmallVector<std::pair<uint32_t, unsigned>, 1>>
2521 OrigToTrimmedInlinedDups;
2523 TrimmedAtNodeCache Cache;
2524 for (
auto &Entry : StackIdToMatchingCalls) {
2525 auto &Calls =
Entry.second;
2528 if (Calls[0].StackNodes.back()->Recursive)
2530 for (
unsigned I = 0;
I < Calls.size();
I++) {
2531 auto &CallCtxInfo = Calls[
I];
2532 auto &StackNodes = CallCtxInfo.StackNodes;
2535 if (StackNodes.size() < 2)
2539 if (CallToMatchingCall.
contains(CallCtxInfo.Call))
2541 auto Trimmed = computeTrimmedInlinedContextIds(StackNodes, Cache);
2542 if (Trimmed.
empty())
2544 unsigned CreatorIdx = TrimmedInlinedDupCreatorNodes.size();
2545 TrimmedInlinedDupCreatorNodes.push_back(StackNodes);
2546 CallCtxInfo.TrimmedInlinedDupIds = duplicateContextIds(
2547 Trimmed, OldToNewContextIds, [&](uint32_t OldId, uint32_t NewId) {
2548 OrigToTrimmedInlinedDups[OldId].push_back({NewId, CreatorIdx});
2550 NumCallsAssignedTrimmedInlinedContexts++;
2551 NumTrimmedInlinedContextIds += Trimmed.
size();
2570 auto AddTrimmedInlinedDups = [&](DenseSet<uint32_t> &SavedContextIds,
2571 const ContextNode *LastNode) {
2572 SmallVector<uint32_t> DupIdsToAdd;
2575 for (
auto [DupId, CreatorIdx] : Dups) {
2577 TrimmedInlinedDupCreatorNodes[CreatorIdx];
2592 if (OrigToTrimmedInlinedDups.
size() < SavedContextIds.
size()) {
2593 for (
auto &[OrigId, Dups] : OrigToTrimmedInlinedDups)
2594 if (SavedContextIds.
contains(OrigId))
2597 for (
auto Id : SavedContextIds) {
2598 auto It = OrigToTrimmedInlinedDups.find(Id);
2599 if (It != OrigToTrimmedInlinedDups.end())
2600 AddDups(It->second);
2603 SavedContextIds.insert_range(DupIdsToAdd);
2605 for (
auto &It : StackIdToMatchingCalls) {
2606 auto &Calls = It.getSecond();
2608 if (Calls.size() == 1) {
2609 auto &StackNodes = Calls[0].StackNodes;
2610 if (StackNodes.size() == 1)
2619 ContextNode *LastNode = Calls[0].StackNodes.back();
2622 assert(LastNode == getNodeForStackId(LastId));
2624 if (LastNode->Recursive)
2629 DenseSet<uint32_t> LastNodeContextIds = LastNode->getContextIds();
2637 DenseSet<const FuncTy *> MatchingIdsFuncSet;
2640 for (
unsigned I = 0;
I < Calls.size();
I++) {
2641 auto &[
Call, StackNodes,
Func, SavedContextIds, TrimmedInlinedDupIds] =
2643 assert(SavedContextIds.empty());
2644 assert(LastNode == StackNodes.back());
2649 if (
I > 0 && StackNodes != Calls[
I - 1].StackNodes)
2650 MatchingIdsFuncSet.
clear();
2657 bool DuplicateContextIds =
false;
2658 for (
unsigned J =
I + 1; J < Calls.size(); J++) {
2659 auto &CallCtxInfo = Calls[J];
2660 if (CallCtxInfo.StackNodes != StackNodes)
2662 auto *NextFunc = CallCtxInfo.Func;
2663 if (NextFunc != Func) {
2666 DuplicateContextIds =
true;
2678 DenseSet<uint32_t> StackSequenceContextIds = LastNodeContextIds;
2680 ContextNode *PrevNode = LastNode;
2681 ContextNode *CurNode = LastNode;
2686 for (
auto NodeIter = StackNodes.rbegin() + 1;
2687 NodeIter != StackNodes.rend(); NodeIter++) {
2688 CurNode = *NodeIter;
2692 if (CurNode->Recursive) {
2697 auto *
Edge = CurNode->findEdgeFromCaller(PrevNode);
2718 if (StackSequenceContextIds.
empty()) {
2731 if (LastId != getLastStackId(
Call)) {
2732 for (
const auto &PE : LastNode->CallerEdges) {
2733 set_subtract(StackSequenceContextIds, PE->getContextIds());
2734 if (StackSequenceContextIds.
empty())
2738 if (StackSequenceContextIds.
empty())
2750 MatchingIdsFuncSet.
insert(Func);
2759 OldToNewContextIds.
reserve(OldToNewContextIds.
size() +
2760 StackSequenceContextIds.
size());
2763 ? duplicateContextIds(StackSequenceContextIds, OldToNewContextIds)
2764 : StackSequenceContextIds;
2765 assert(!SavedContextIds.empty());
2766 if (!OrigToTrimmedInlinedDups.empty())
2767 AddTrimmedInlinedDups(SavedContextIds, LastNode);
2769 if (!DuplicateContextIds) {
2773 set_subtract(LastNodeContextIds, StackSequenceContextIds);
2774 if (LastNodeContextIds.
empty())
2781 propagateDuplicateContextIds(OldToNewContextIds);
2791 DenseSet<const ContextNode *> Visited;
2793 ImportantContextIdInfo.keys());
2794 for (
auto &Entry : AllocationCallToContextNodeMap)
2795 assignStackNodesPostOrder(
Entry.second, Visited, StackIdToMatchingCalls,
2796 CallToMatchingCall, ImportantContextIds);
2798 fixupImportantContexts();
2804uint64_t ModuleCallsiteContextGraph::getLastStackId(Instruction *
Call) {
2805 CallStack<MDNode, MDNode::op_iterator> CallsiteContext(
2807 return CallsiteContext.
back();
2810uint64_t IndexCallsiteContextGraph::getLastStackId(IndexCall &
Call) {
2812 CallStack<CallsiteInfo, SmallVector<unsigned>::const_iterator>
2815 return Index.getStackIdAtIndex(CallsiteContext.
back());
2831 auto Pos =
F.getName().find_last_of(
'.');
2834 bool Err =
F.getName().drop_front(Pos + 1).getAsInteger(10, CloneNo);
2840std::string ModuleCallsiteContextGraph::getLabel(
const Function *Func,
2841 const Instruction *
Call,
2842 unsigned CloneNo)
const {
2848std::string IndexCallsiteContextGraph::getLabel(
const FunctionSummary *Func,
2849 const IndexCall &
Call,
2850 unsigned CloneNo)
const {
2851 auto VI = FSToVIMap.find(Func);
2852 assert(VI != FSToVIMap.end());
2855 return CallerName +
" -> alloc";
2858 return CallerName +
" -> " +
2860 Callsite->Clones[CloneNo]);
2864std::string ModuleCallsiteContextGraph::getFuncName(
const Function *Func,
2865 unsigned CloneNo)
const {
2871void ModuleCallsiteContextGraph::populateFunctionsWithCallers() {
2874 for (
const auto &
F :
Mod)
2876 FunctionsWithCallers.
insert(&
F);
2879std::string IndexCallsiteContextGraph::getFuncName(
const FunctionSummary *Func,
2880 unsigned CloneNo)
const {
2883 auto VI = FSToVIMap.find(Func);
2884 if (VI != FSToVIMap.end()) {
2885 if (!
VI->second.name().empty())
2893bool IndexCallsiteContextGraph::isFuncDead(
const FunctionSummary *Func)
const {
2894 return Index.withGlobalValueDeadStripping() &&
Func && !
Func->isLive();
2897void IndexCallsiteContextGraph::populateFunctionsWithCallers() {
2898 for (
const auto &
I : Index) {
2900 for (
const auto &S :
VI.getSummaryList()) {
2902 !isPrevailing(
VI.getGUID(), S.get()))
2904 if (
Index.withGlobalValueDeadStripping() && !S->isLive())
2906 auto AddReferenced = [&](ValueInfo RefVI) {
2907 for (
const auto &RefS : RefVI.getSummaryList()) {
2908 const GlobalValueSummary *
Base = RefS->getBaseObject();
2910 FunctionsWithCallers.
insert(RefFS);
2914 for (
const auto &RefVI : S->refs())
2915 AddReferenced(RefVI);
2918 for (
const auto &CallEdge :
FS->calls())
2919 AddReferenced(CallEdge.first);
2924std::vector<ModuleCallsiteContextGraph::ContextNode *>
2925ModuleCallsiteContextGraph::getStackNodesForCall(Instruction *
Call) {
2926 CallStack<MDNode, MDNode::op_iterator> CallsiteContext(
2928 return getStackNodesForCallsite<MDNode, MDNode::op_iterator>(CallsiteContext);
2931std::vector<IndexCallsiteContextGraph::ContextNode *>
2932IndexCallsiteContextGraph::getStackNodesForCall(IndexCall &
Call) {
2934 CallStack<CallsiteInfo, SmallVector<unsigned>::const_iterator>
2936 return getStackNodesForCallsite<CallsiteInfo,
2937 SmallVector<unsigned>::const_iterator>(
2941template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2942template <
class NodeT,
class IteratorT>
2944 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *>
2945CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getStackNodesForCallsite(
2946 CallStack<NodeT, IteratorT> &CallsiteContext) {
2947 std::vector<ContextNode *> StackNodes;
2948 for (
auto IdOrIndex : CallsiteContext) {
2949 auto StackId = getStackId(IdOrIndex);
2950 ContextNode *
Node = getNodeForStackId(StackId);
2953 StackNodes.push_back(Node);
2958ModuleCallsiteContextGraph::ModuleCallsiteContextGraph(
2960 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter)
2961 :
Mod(
M), OREGetter(OREGetter) {
2965 std::map<uint64_t, uint32_t> TotalSizeToContextIdTopNCold;
2967 std::vector<CallInfo> CallsWithMetadata;
2968 for (
auto &BB :
F) {
2969 for (
auto &
I : BB) {
2972 if (
auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof)) {
2973 CallsWithMetadata.push_back(&
I);
2974 auto *AllocNode = addAllocNode(&
I, &
F);
2975 auto *CallsiteMD =
I.getMetadata(LLVMContext::MD_callsite);
2979 for (
auto &MDOp : MemProfMD->operands()) {
2981 std::vector<ContextTotalSize> ContextSizeInfo;
2983 if (MIBMD->getNumOperands() > 2) {
2984 for (
unsigned I = 2;
I < MIBMD->getNumOperands();
I++) {
2985 MDNode *ContextSizePair =
2994 ContextSizeInfo.push_back({FullStackId, TotalSize});
3000 addStackNodesForMIB<MDNode, MDNode::op_iterator>(
3001 AllocNode, StackContext, CallsiteContext,
3003 TotalSizeToContextIdTopNCold);
3008 DotAllocContextIds = AllocNode->getContextIds();
3012 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
3013 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
3016 else if (
I.getMetadata(LLVMContext::MD_callsite)) {
3017 CallsWithMetadata.push_back(&
I);
3021 if (!CallsWithMetadata.empty())
3022 FuncToCallsWithMetadata[&
F] = CallsWithMetadata;
3026 dbgs() <<
"CCG before updating call stack chains:\n";
3031 exportToDot(
"prestackupdate");
3036 exportToDot(
"poststackupdate");
3038 handleCallsitesWithMultipleTargets();
3043 for (
auto &FuncEntry : FuncToCallsWithMetadata)
3044 for (
auto &
Call : FuncEntry.second)
3045 Call.call()->setMetadata(LLVMContext::MD_callsite,
nullptr);
3051IndexCallsiteContextGraph::findAliaseeGUIDsPrevailingInDifferentModule() {
3052 DenseSet<GlobalValue::GUID> AliaseeGUIDs;
3053 for (
auto &
I : Index) {
3055 for (
auto &S :
VI.getSummaryList()) {
3060 auto *AliaseeSummary = &AS->getAliasee();
3068 !isPrevailing(
VI.getGUID(), S.get()))
3073 auto AliaseeGUID = AS->getAliaseeGUID();
3075 if (!isPrevailing(AliaseeGUID, AliaseeSummary))
3076 AliaseeGUIDs.
insert(AliaseeGUID);
3079 AliaseesPrevailingInDiffModuleFromAlias += AliaseeGUIDs.
size();
3080 return AliaseeGUIDs;
3083IndexCallsiteContextGraph::IndexCallsiteContextGraph(
3084 ModuleSummaryIndex &Index,
3094 findAliaseeGUIDsPrevailingInDifferentModule();
3098 std::map<uint64_t, uint32_t> TotalSizeToContextIdTopNCold;
3103 for (
const auto &
I : Index.sortedGlobalValueSummariesRange()) {
3104 auto VI = Index.getValueInfo(
I);
3105 if (GUIDsToSkip.
contains(VI.getGUID()))
3107 for (
auto &S : VI.getSummaryList()) {
3116 !isPrevailing(VI.getGUID(), S.get()))
3121 std::vector<CallInfo> CallsWithMetadata;
3122 if (!
FS->allocs().empty()) {
3123 for (
auto &AN :
FS->mutableAllocs()) {
3128 if (AN.MIBs.empty())
3130 IndexCall AllocCall(&AN);
3131 CallsWithMetadata.push_back(AllocCall);
3132 auto *AllocNode = addAllocNode(AllocCall, FS);
3140 AN.ContextSizeInfos.size() == AN.MIBs.size());
3142 for (
auto &MIB : AN.MIBs) {
3145 std::vector<ContextTotalSize> ContextSizeInfo;
3146 if (!AN.ContextSizeInfos.empty()) {
3147 for (
auto [FullStackId, TotalSize] : AN.ContextSizeInfos[
I])
3148 ContextSizeInfo.push_back({FullStackId, TotalSize});
3150 addStackNodesForMIB<MIBInfo, SmallVector<unsigned>::const_iterator>(
3151 AllocNode, StackContext, EmptyContext, MIB.AllocType,
3152 ContextSizeInfo, TotalSizeToContextIdTopNCold);
3158 DotAllocContextIds = AllocNode->getContextIds();
3164 AN.Versions[0] = (
uint8_t)allocTypeToUse(AllocNode->AllocTypes);
3168 if (!
FS->callsites().empty())
3169 for (
auto &SN :
FS->mutableCallsites()) {
3170 IndexCall StackNodeCall(&SN);
3171 CallsWithMetadata.push_back(StackNodeCall);
3174 if (!CallsWithMetadata.empty())
3175 FuncToCallsWithMetadata[
FS] = CallsWithMetadata;
3177 if (!
FS->allocs().empty() || !
FS->callsites().empty())
3183 dbgs() <<
"CCG before updating call stack chains:\n";
3188 exportToDot(
"prestackupdate");
3193 exportToDot(
"poststackupdate");
3195 handleCallsitesWithMultipleTargets();
3200template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3201void CallsiteContextGraph<DerivedCCG, FuncTy,
3202 CallTy>::handleCallsitesWithMultipleTargets() {
3217 std::vector<std::pair<CallInfo, ContextNode *>> NewCallToNode;
3218 for (
auto &Entry : NonAllocationCallToContextNodeMap) {
3219 auto *
Node = Entry.second;
3228 std::vector<CallInfo> AllCalls;
3229 AllCalls.reserve(
Node->MatchingCalls.size() + 1);
3230 AllCalls.push_back(
Node->Call);
3244 if (partitionCallsByCallee(
Node, AllCalls, NewCallToNode))
3247 auto It = AllCalls.begin();
3249 for (; It != AllCalls.end(); ++It) {
3252 for (
auto EI =
Node->CalleeEdges.begin(); EI !=
Node->CalleeEdges.end();
3255 if (!Edge->Callee->hasCall())
3257 assert(NodeToCallingFunc.count(Edge->Callee));
3259 if (!calleesMatch(
ThisCall.call(), EI, TailCallToContextNodeMap)) {
3268 if (
Node->Call != ThisCall) {
3269 Node->setCall(ThisCall);
3280 Node->MatchingCalls.clear();
3283 if (It == AllCalls.end()) {
3284 RemovedEdgesWithMismatchedCallees++;
3288 Node->setCall(CallInfo());
3293 for (++It; It != AllCalls.end(); ++It) {
3297 Node->MatchingCalls.push_back(ThisCall);
3306 NonAllocationCallToContextNodeMap.remove_if([](
const auto &it) {
3307 return !it.second->hasCall() || it.second->Call != it.first;
3311 for (
auto &[
Call,
Node] : NewCallToNode)
3312 NonAllocationCallToContextNodeMap[
Call] =
Node;
3316 for (
auto &[
Call,
Node] : TailCallToContextNodeMap)
3317 NonAllocationCallToContextNodeMap[
Call] =
Node;
3320template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3321bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::partitionCallsByCallee(
3323 std::vector<std::pair<CallInfo, ContextNode *>> &NewCallToNode) {
3327 struct CallsWithSameCallee {
3328 std::vector<CallInfo> Calls;
3329 ContextNode *
Node =
nullptr;
3335 for (
auto ThisCall : AllCalls) {
3336 auto *
F = getCalleeFunc(
ThisCall.call());
3338 CalleeFuncToCallInfo[
F].Calls.push_back(ThisCall);
3347 for (
const auto &Edge :
Node->CalleeEdges) {
3348 if (!Edge->Callee->hasCall())
3350 const FuncTy *ProfiledCalleeFunc = NodeToCallingFunc[Edge->Callee];
3351 if (CalleeFuncToCallInfo.
contains(ProfiledCalleeFunc))
3352 CalleeNodeToCallInfo[Edge->Callee] =
3353 &CalleeFuncToCallInfo[ProfiledCalleeFunc];
3359 if (CalleeNodeToCallInfo.
empty())
3371 ContextNode *UnmatchedCalleesNode =
nullptr;
3373 bool UsedOrigNode =
false;
3378 auto CalleeEdges =
Node->CalleeEdges;
3379 for (
auto &Edge : CalleeEdges) {
3380 if (!Edge->Callee->hasCall())
3385 ContextNode *CallerNodeToUse =
nullptr;
3389 if (!CalleeNodeToCallInfo.
contains(Edge->Callee)) {
3390 if (!UnmatchedCalleesNode)
3391 UnmatchedCalleesNode =
3392 createNewNode(
false, NodeToCallingFunc[
Node]);
3393 CallerNodeToUse = UnmatchedCalleesNode;
3397 auto *Info = CalleeNodeToCallInfo[Edge->Callee];
3400 if (!UsedOrigNode) {
3403 Node->MatchingCalls.clear();
3404 UsedOrigNode =
true;
3407 createNewNode(
false, NodeToCallingFunc[
Node]);
3408 assert(!Info->Calls.empty());
3411 Info->Node->setCall(Info->Calls.front());
3417 NewCallToNode.push_back({Info->Node->Call, Info->Node});
3419 CallerNodeToUse = Info->Node;
3423 if (CallerNodeToUse ==
Node)
3426 moveCalleeEdgeToNewCaller(Edge, CallerNodeToUse);
3433 for (
auto &
I : CalleeNodeToCallInfo)
3434 removeNoneTypeCallerEdges(
I.second->Node);
3435 if (UnmatchedCalleesNode)
3436 removeNoneTypeCallerEdges(UnmatchedCalleesNode);
3437 removeNoneTypeCallerEdges(
Node);
3450 return Index.getStackIdAtIndex(IdOrIndex);
3453template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3454bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::calleesMatch(
3455 CallTy
Call, EdgeIter &EI,
3456 MapVector<CallInfo, ContextNode *> &TailCallToContextNodeMap) {
3458 const FuncTy *ProfiledCalleeFunc = NodeToCallingFunc[
Edge->Callee];
3459 const FuncTy *CallerFunc = NodeToCallingFunc[
Edge->Caller];
3462 std::vector<std::pair<CallTy, FuncTy *>> FoundCalleeChain;
3463 if (!calleeMatchesFunc(
Call, ProfiledCalleeFunc, CallerFunc,
3468 if (FoundCalleeChain.empty())
3472 auto *CurEdge =
Callee->findEdgeFromCaller(Caller);
3476 CurEdge->ContextIds.insert_range(
Edge->ContextIds);
3477 CurEdge->AllocTypes |=
Edge->AllocTypes;
3482 auto NewEdge = std::make_shared<ContextEdge>(
3483 Callee, Caller,
Edge->AllocTypes,
Edge->ContextIds);
3484 Callee->CallerEdges.push_back(NewEdge);
3485 if (Caller ==
Edge->Caller) {
3489 EI =
Caller->CalleeEdges.insert(EI, NewEdge);
3492 "Iterator position not restored after insert and increment");
3494 Caller->CalleeEdges.push_back(NewEdge);
3499 auto *CurCalleeNode =
Edge->Callee;
3500 for (
auto &[NewCall, Func] : FoundCalleeChain) {
3501 ContextNode *NewNode =
nullptr;
3503 if (TailCallToContextNodeMap.
count(NewCall)) {
3504 NewNode = TailCallToContextNodeMap[NewCall];
3505 NewNode->AllocTypes |=
Edge->AllocTypes;
3507 FuncToCallsWithMetadata[
Func].push_back({NewCall});
3509 NewNode = createNewNode(
false, Func, NewCall);
3510 TailCallToContextNodeMap[NewCall] = NewNode;
3511 NewNode->AllocTypes =
Edge->AllocTypes;
3515 AddEdge(NewNode, CurCalleeNode);
3517 CurCalleeNode = NewNode;
3521 AddEdge(
Edge->Caller, CurCalleeNode);
3529 removeEdgeFromGraph(
Edge.get(), &EI,
true);
3541bool ModuleCallsiteContextGraph::findProfiledCalleeThroughTailCalls(
3543 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain,
3544 bool &FoundMultipleCalleeChains) {
3551 FoundCalleeChain.push_back({Callsite,
F});
3566 bool FoundSingleCalleeChain =
false;
3567 for (
auto &BB : *CalleeFunc) {
3568 for (
auto &
I : BB) {
3570 if (!CB || !CB->isTailCall())
3572 auto *CalledValue = CB->getCalledOperand();
3573 auto *CalledFunction = CB->getCalledFunction();
3574 if (CalledValue && !CalledFunction) {
3575 CalledValue = CalledValue->stripPointerCasts();
3582 assert(!CalledFunction &&
3583 "Expected null called function in callsite for alias");
3586 if (!CalledFunction)
3588 if (CalledFunction == ProfiledCallee) {
3589 if (FoundSingleCalleeChain) {
3590 FoundMultipleCalleeChains =
true;
3593 FoundSingleCalleeChain =
true;
3594 FoundProfiledCalleeCount++;
3595 FoundProfiledCalleeDepth +=
Depth;
3596 if (
Depth > FoundProfiledCalleeMaxDepth)
3597 FoundProfiledCalleeMaxDepth =
Depth;
3598 SaveCallsiteInfo(&
I, CalleeFunc);
3599 }
else if (findProfiledCalleeThroughTailCalls(
3600 ProfiledCallee, CalledFunction,
Depth + 1,
3601 FoundCalleeChain, FoundMultipleCalleeChains)) {
3604 assert(!FoundMultipleCalleeChains);
3605 if (FoundSingleCalleeChain) {
3606 FoundMultipleCalleeChains =
true;
3609 FoundSingleCalleeChain =
true;
3610 SaveCallsiteInfo(&
I, CalleeFunc);
3611 }
else if (FoundMultipleCalleeChains)
3616 return FoundSingleCalleeChain;
3619const Function *ModuleCallsiteContextGraph::getCalleeFunc(Instruction *
Call) {
3621 if (!CB->getCalledOperand() || CB->isIndirectCall())
3623 auto *CalleeVal = CB->getCalledOperand()->stripPointerCasts();
3630bool ModuleCallsiteContextGraph::calleeMatchesFunc(
3632 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain) {
3634 if (!CB->getCalledOperand() || CB->isIndirectCall())
3636 auto *CalleeVal = CB->getCalledOperand()->stripPointerCasts();
3638 if (CalleeFunc == Func)
3641 if (Alias && Alias->getAliasee() == Func)
3652 bool FoundMultipleCalleeChains =
false;
3653 if (!findProfiledCalleeThroughTailCalls(Func, CalleeVal,
Depth,
3655 FoundMultipleCalleeChains)) {
3656 LLVM_DEBUG(
dbgs() <<
"Not found through unique tail call chain: "
3657 <<
Func->getName() <<
" from " << CallerFunc->
getName()
3658 <<
" that actually called " << CalleeVal->getName()
3659 << (FoundMultipleCalleeChains
3660 ?
" (found multiple possible chains)"
3663 if (FoundMultipleCalleeChains)
3664 FoundProfiledCalleeNonUniquelyCount++;
3671bool ModuleCallsiteContextGraph::sameCallee(Instruction *Call1,
3672 Instruction *Call2) {
3674 if (!CB1->getCalledOperand() || CB1->isIndirectCall())
3676 auto *CalleeVal1 = CB1->getCalledOperand()->stripPointerCasts();
3679 if (!CB2->getCalledOperand() || CB2->isIndirectCall())
3681 auto *CalleeVal2 = CB2->getCalledOperand()->stripPointerCasts();
3683 return CalleeFunc1 == CalleeFunc2;
3686bool IndexCallsiteContextGraph::findProfiledCalleeThroughTailCalls(
3687 ValueInfo ProfiledCallee, ValueInfo CurCallee,
unsigned Depth,
3688 std::vector<std::pair<ValueInfo, FunctionSummary *>> &FoundCalleeChain,
3689 bool &FoundMultipleCalleeChains) {
3699 auto SaveTailCall = [&](ValueInfo
Callee, FunctionSummary *
FS) {
3700 FoundCalleeChain.push_back({
Callee,
FS});
3709 auto IsProfiledCallee = [&](ValueInfo
Callee) {
3710 if (Callee == ProfiledCallee)
3712 for (
auto &S :
Callee.getSummaryList()) {
3714 !isPrevailing(
Callee.getGUID(), S.get()))
3717 return AS && AS->getAliaseeVI() == ProfiledCallee;
3726 bool FoundSingleCalleeChain =
false;
3729 !isPrevailing(CurCallee.
getGUID(), S.get()))
3734 auto FSVI = CurCallee;
3737 FSVI = AS->getAliaseeVI();
3738 for (
auto &CallEdge :
FS->calls()) {
3739 if (!CallEdge.second.hasTailCall())
3746 if (IsProfiledCallee(CallEdge.first)) {
3747 if (FoundSingleCalleeChain) {
3748 FoundMultipleCalleeChains =
true;
3751 FoundSingleCalleeChain =
true;
3752 FoundProfiledCalleeCount++;
3753 FoundProfiledCalleeDepth +=
Depth;
3754 if (
Depth > FoundProfiledCalleeMaxDepth)
3755 FoundProfiledCalleeMaxDepth =
Depth;
3756 if (CallEdge.second.hasIndirectCall())
3757 FoundProfiledCalleeIndirectTailCallCount++;
3758 SaveTailCall(CallEdge.first, FS);
3760 assert(!FSToVIMap.count(FS) || FSToVIMap[FS] == FSVI);
3761 FSToVIMap[
FS] = FSVI;
3762 }
else if (findProfiledCalleeThroughTailCalls(
3763 ProfiledCallee, CallEdge.first,
Depth + 1,
3764 FoundCalleeChain, FoundMultipleCalleeChains)) {
3767 assert(!FoundMultipleCalleeChains);
3768 if (FoundSingleCalleeChain) {
3769 FoundMultipleCalleeChains =
true;
3772 FoundSingleCalleeChain =
true;
3773 if (CallEdge.second.hasIndirectCall())
3774 FoundProfiledCalleeIndirectTailCallCount++;
3775 SaveTailCall(CallEdge.first, FS);
3777 assert(!FSToVIMap.count(FS) || FSToVIMap[FS] == FSVI);
3778 FSToVIMap[
FS] = FSVI;
3779 }
else if (FoundMultipleCalleeChains)
3784 return FoundSingleCalleeChain;
3787const FunctionSummary *
3788IndexCallsiteContextGraph::getCalleeFunc(IndexCall &
Call) {
3790 if (
Callee.getSummaryList().empty())
3795bool IndexCallsiteContextGraph::calleeMatchesFunc(
3796 IndexCall &
Call,
const FunctionSummary *Func,
3797 const FunctionSummary *CallerFunc,
3798 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain) {
3802 AliasSummary *Alias =
3803 Callee.getSummaryList().empty()
3806 assert(FSToVIMap.count(Func));
3807 auto FuncVI = FSToVIMap[
Func];
3808 if (Callee == FuncVI ||
3823 bool FoundMultipleCalleeChains =
false;
3824 std::vector<std::pair<ValueInfo, FunctionSummary *>> FoundCalleeVIChain;
3825 if (!findProfiledCalleeThroughTailCalls(FuncVI, Callee,
Depth,
3827 FoundMultipleCalleeChains)) {
3828 LLVM_DEBUG(
dbgs() <<
"Not found through unique tail call chain: " << FuncVI
3829 <<
" from " << FSToVIMap[CallerFunc]
3830 <<
" that actually called " << Callee
3831 << (FoundMultipleCalleeChains
3832 ?
" (found multiple possible chains)"
3835 if (FoundMultipleCalleeChains)
3836 FoundProfiledCalleeNonUniquelyCount++;
3845 for (
auto &[CalleeVI, FS] : FoundCalleeVIChain) {
3846 auto &CallsiteInfoPtr =
3847 FunctionCalleesToSynthesizedCallsiteInfos[
FS][CalleeVI];
3848 if (!CallsiteInfoPtr)
3852 std::make_unique<CallsiteInfo>(CalleeVI, SmallVector<unsigned>());
3853 FoundCalleeChain.push_back({CallsiteInfoPtr.get(),
FS});
3859bool IndexCallsiteContextGraph::sameCallee(IndexCall &Call1, IndexCall &Call2) {
3862 return Callee1 == Callee2;
3865template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3866void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::dump()
3872template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3873void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::print(
3874 raw_ostream &OS)
const {
3875 OS <<
"Node " <<
this <<
"\n";
3879 OS <<
" (recursive)";
3881 if (!MatchingCalls.
empty()) {
3882 OS <<
"\tMatchingCalls:\n";
3883 for (
auto &MatchingCall : MatchingCalls) {
3885 MatchingCall.print(OS);
3889 OS <<
"\tNodeId: " <<
NodeId <<
"\n";
3891 OS <<
"\tContextIds:";
3893 auto ContextIds = getContextIds();
3894 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
3895 std::sort(SortedIds.begin(), SortedIds.end());
3896 for (
auto Id : SortedIds)
3899 OS <<
"\tCalleeEdges:\n";
3900 for (
auto &
Edge : CalleeEdges)
3901 OS <<
"\t\t" << *
Edge <<
" (Callee NodeId: " <<
Edge->Callee->NodeId
3903 OS <<
"\tCallerEdges:\n";
3904 for (
auto &
Edge : CallerEdges)
3905 OS <<
"\t\t" << *
Edge <<
" (Caller NodeId: " <<
Edge->Caller->NodeId
3907 if (!Clones.empty()) {
3910 for (
auto *
C : Clones)
3911 OS <<
LS <<
C <<
" NodeId: " <<
C->NodeId;
3913 }
else if (CloneOf) {
3914 OS <<
"\tClone of " << CloneOf <<
" NodeId: " << CloneOf->NodeId <<
"\n";
3918template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3919void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge::dump()
3925template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3926void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge::print(
3927 raw_ostream &OS)
const {
3928 OS <<
"Edge from Callee " <<
Callee <<
" to Caller: " <<
Caller
3929 << (IsBackedge ?
" (BE)" :
"")
3931 OS <<
" ContextIds:";
3932 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
3933 std::sort(SortedIds.begin(), SortedIds.end());
3934 for (
auto Id : SortedIds)
3938template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3939void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::dump()
const {
3943template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3944void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::print(
3945 raw_ostream &OS)
const {
3946 OS <<
"Callsite Context Graph:\n";
3947 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
3949 if (
Node->isRemoved())
3956template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3957void CallsiteContextGraph<DerivedCCG, FuncTy,
3958 CallTy>::capturePreCloningContextInfo() {
3959 for (
const auto &Entry : AllocationCallToContextNodeMap) {
3960 const ContextNode *AllocNode =
Entry.second;
3964 for (
const auto &
Edge : AllocNode->CallerEdges) {
3965 if (!
Edge->isRemoved() &&
Edge->Caller->hasCall()) {
3966 PreCloningAllocHasMatchedCaller.insert(AllocNode);
3970 DenseSet<uint32_t> ContextIds = AllocNode->getContextIds();
3971 for (uint32_t Id : ContextIds) {
3972 PreCloningContextInfo
Info;
3978 Info.Chain.push_back(AllocNode);
3979 SmallPtrSet<const ContextNode *, 16> Visited;
3980 Visited.
insert(AllocNode);
3981 const ContextNode *Cur = AllocNode;
3983 const ContextNode *
Next =
nullptr;
3984 for (
const auto &
Edge : Cur->CallerEdges) {
3985 if (
Edge->isRemoved() ||
Edge->IsBackedge)
3987 if (
Edge->getContextIds().contains(Id) &&
3994 for (
const auto &
Edge : Cur->CallerEdges) {
3995 if (
Edge->isRemoved())
3997 if (
Edge->getContextIds().contains(Id) &&
4014 Info.MaxMatchedFrame = 0;
4015 for (
unsigned I = 1;
I <
Info.Chain.size(); ++
I) {
4016 if (
Info.Chain[
I]->hasCall()) {
4017 Info.MaxMatchedFrame =
I;
4019 const ContextNode *Unmatched =
Info.Chain[
I];
4020 Info.UnmatchedStackId = Unmatched->OrigStackOrAllocId;
4021 Info.StoppedAtRecursive = Unmatched->Recursive;
4025 if (
auto It = NodeToCallingFunc.find(Unmatched);
4026 It != NodeToCallingFunc.end()) {
4027 Info.StoppedAtMismatchedCallee =
true;
4028 Info.UnmatchedCallingFunc = It->second;
4038 if (
Info.MaxMatchedFrame > 0 &&
4039 Info.MaxMatchedFrame + 1 ==
Info.Chain.size()) {
4040 const ContextNode *OutermostMatchedNode =
4042 for (
const auto &
Edge : OutermostMatchedNode->CallerEdges) {
4043 if (!
Edge->isRemoved() &&
Edge->Caller->hasCall()) {
4044 Info.OutermostMatchedNodeHasOtherCallers =
true;
4050 PreCloningContextInfoMap[
Id] = std::move(Info);
4055template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4057CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::formatContextReportSuffix(
4058 const ContextNode *Node, uint32_t Id)
const {
4059 auto InfoIt = PreCloningContextInfoMap.find(Id);
4060 if (InfoIt == PreCloningContextInfoMap.end())
4062 const PreCloningContextInfo &
Info = InfoIt->second;
4069 const ContextNode *OrigAlloc =
Node->getOrigNode();
4070 const FuncTy *AllocFunc = getCallingFunc(OrigAlloc);
4071 unsigned AllocCloneNo =
Node->Call.cloneNo();
4072 std::string AllocFuncStr = getFuncName(AllocFunc, AllocCloneNo);
4073 if (isFuncDead(AllocFunc)) {
4074 AllocFuncStr +=
" (dead)";
4075 }
else if (!PreCloningAllocHasMatchedCaller.contains(OrigAlloc) &&
4076 Info.Chain.size() > 1) {
4080 AllocFuncStr += AllocFunc && !FunctionsWithCallers.
contains(AllocFunc)
4081 ?
" (no references in IR/summary)"
4082 :
" (no matched callers)";
4088 unsigned TotalFrames =
Info.Chain.size() > 0 ?
Info.Chain.size() - 1 : 0;
4089 unsigned Matched =
Info.MaxMatchedFrame;
4090 std::string StatusStr;
4091 if (TotalFrames == 0) {
4092 StatusStr =
"inlined into leaf";
4093 }
else if (Matched < TotalFrames) {
4098 if (
Info.StoppedAtRecursive)
4099 StatusStr =
"unmatched recursive callsite";
4100 else if (
Info.StoppedAtMismatchedCallee)
4101 StatusStr =
"unmatched callsite (mismatched callee in " +
4102 getFuncName(
Info.UnmatchedCallingFunc, 0) +
")";
4104 StatusStr =
"unmatched callsite";
4105 StatusStr +=
" at frame " + std::to_string(Matched + 1) +
"/" +
4106 std::to_string(TotalFrames) +
" (stack id " +
4107 std::to_string(
Info.UnmatchedStackId) +
")";
4109 const ContextNode *OutermostMatchedNode =
Info.Chain[Matched];
4110 const FuncTy *OutermostMatchedFunc = getCallingFunc(OutermostMatchedNode);
4111 unsigned NumOutermostMatchedFuncClones =
4112 std::max<unsigned>(1, FuncToNumClones.lookup(OutermostMatchedFunc));
4113 bool HasCallersAbove =
4114 NumOutermostMatchedFuncClones > 1 ||
4115 Info.OutermostMatchedNodeHasOtherCallers ||
4116 (OutermostMatchedFunc &&
4117 FunctionsWithCallers.
contains(OutermostMatchedFunc));
4118 if (HasCallersAbove) {
4119 StatusStr =
"trimmed at frame " + std::to_string(Matched) +
" in " +
4120 getFuncName(OutermostMatchedFunc, 0);
4122 StatusStr =
"matched " + std::to_string(Matched) +
" frames to " +
4123 getFuncName(OutermostMatchedFunc, 0);
4132 std::string ReachesStr;
4134 const ContextNode *OutermostMatchedNode =
Info.Chain[Matched];
4135 const FuncTy *OutermostMatchedFunc = getCallingFunc(OutermostMatchedNode);
4136 unsigned NumOutermostMatchedFuncClones =
4137 std::max<unsigned>(1, FuncToNumClones.lookup(OutermostMatchedFunc));
4138 ReachesStr =
"; reaches ";
4143 SmallSet<unsigned, 4> ReportedAllocClones;
4144 bool FirstPath =
true;
4145 for (
unsigned OutermostMatchedFuncClone = 0;
4146 OutermostMatchedFuncClone < NumOutermostMatchedFuncClones;
4147 ++OutermostMatchedFuncClone) {
4151 std::vector<const FuncTy *> PathFuncs(Matched + 1);
4152 std::vector<unsigned> PathClones(Matched + 1);
4153 PathFuncs[0] = OutermostMatchedFunc;
4154 PathClones[0] = OutermostMatchedFuncClone;
4155 unsigned CurClone = OutermostMatchedFuncClone;
4156 for (
unsigned Step = 0; Step < Matched; ++Step) {
4157 unsigned FrameIdx = Matched - Step;
4158 const ContextNode *CallNode =
Info.Chain[FrameIdx];
4159 unsigned NextClone =
4160 OrigNodeAndCloneToCalleeClone.lookup({CallNode, CurClone});
4161 const FuncTy *CalleeFunc = getCallingFunc(
Info.Chain[FrameIdx - 1]);
4162 PathFuncs[Step + 1] = CalleeFunc;
4163 PathClones[Step + 1] = NextClone;
4164 CurClone = NextClone;
4167 if (!ReportedAllocClones.
insert(CurClone).second)
4173 const ContextNode *ReachedAlloc =
4174 OrigAllocAndCloneToNode.lookup({OrigAlloc, CurClone});
4178 std::string ReachedTypeStr;
4181 (uint8_t)getAllocationCallType(ReachedAlloc->Call));
4182 else if (CurClone == 0)
4186 ReachedTypeStr =
"None";
4192 std::string PathStr;
4193 bool SkippedPrev =
false;
4194 bool PrintFullPath =
4196 for (
unsigned S = 0; S <= Matched; ++S) {
4197 bool IsCloned = PathClones[S] > 0;
4198 bool PrevCloned = S > 0 ? (PathClones[S - 1] > 0) : IsCloned;
4199 bool NextCloned = S + 1 <= Matched ? (PathClones[S + 1] > 0) : IsCloned;
4200 bool Include = PrintFullPath || (S <= 1) || (S + 1 >= Matched) ||
4201 (IsCloned != PrevCloned) || (IsCloned != NextCloned);
4204 PathStr +=
" -> ...";
4209 SkippedPrev =
false;
4210 if (!PathStr.empty())
4212 PathStr += getFuncName(PathFuncs[S], PathClones[S]);
4214 ReachesStr += ReachedTypeStr +
" via " + PathStr;
4218 return " [alloc in " + AllocFuncStr +
"; " + StatusStr + ReachesStr +
"]";
4221template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4222void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::printTotalSizes(
4224 function_ref<
void(StringRef, StringRef,
const Twine &)> EmitRemark)
const {
4225 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
4227 if (
Node->isRemoved())
4229 if (!
Node->IsAllocation)
4231 DenseSet<uint32_t> ContextIds =
Node->getContextIds();
4232 auto AllocTypeFromCall = getAllocationCallType(
Node->Call);
4233 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
4234 std::sort(SortedIds.begin(), SortedIds.end());
4235 for (
auto Id : SortedIds) {
4236 auto TypeI = ContextIdToAllocationType.
find(Id);
4237 assert(TypeI != ContextIdToAllocationType.
end());
4239 bool ComputedSuffix =
false;
4240 auto GetSuffix = [&]() ->
const std::string & {
4241 if (!ComputedSuffix) {
4243 ? formatContextReportSuffix(Node, Id)
4245 ComputedSuffix =
true;
4249 auto CSI = ContextIdToContextSizeInfos.
find(Id);
4250 if (CSI != ContextIdToContextSizeInfos.
end()) {
4251 for (
auto &Info : CSI->second) {
4254 " full allocation context " + std::to_string(
Info.FullStackId) +
4255 " with total size " + std::to_string(
Info.TotalSize) +
" is " +
4257 if (allocTypeToUse(
Node->AllocTypes) !=
4258 allocTypeToUse((uint8_t)AllocTypeFromCall))
4260 " due to cold byte percent";
4262 Msg +=
" (internal context id " + std::to_string(Id) +
")";
4264 OS <<
Msg << GetSuffix() <<
"\n";
4274 if (allocTypeToUse(
Node->AllocTypes) !=
4275 allocTypeToUse((uint8_t)AllocTypeFromCall))
4277 " due to cold byte percent";
4279 Msg +=
" (internal context id " + std::to_string(Id) +
")";
4281 OS <<
Msg << GetSuffix() <<
"\n";
4289template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4290void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::check()
const {
4291 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
4294 for (
auto &
Edge :
Node->CallerEdges)
4299template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4301 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
4302 using NodeRef =
const ContextNode<DerivedCCG, FuncTy, CallTy> *;
4304 using NodePtrTy = std::unique_ptr<ContextNode<DerivedCCG, FuncTy, CallTy>>;
4320 return G->NodeOwner.begin()->get();
4323 using EdgePtrTy = std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>>;
4324 static const ContextNode<DerivedCCG, FuncTy, CallTy> *
4343template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4357 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
4363 std::string LabelString =
4364 (
Twine(
"OrigId: ") + (
Node->IsAllocation ?
"Alloc" :
"") +
4367 LabelString +=
"\n";
4368 if (
Node->hasCall()) {
4369 auto Func =
G->NodeToCallingFunc.find(
Node);
4370 assert(Func !=
G->NodeToCallingFunc.end());
4372 G->getLabel(Func->second,
Node->Call.call(),
Node->Call.cloneNo());
4373 for (
auto &MatchingCall :
Node->MatchingCalls) {
4374 LabelString +=
"\n";
4375 LabelString +=
G->getLabel(Func->second, MatchingCall.call(),
4376 MatchingCall.cloneNo());
4379 LabelString +=
"null call";
4380 if (
Node->Recursive)
4381 LabelString +=
" (recursive)";
4383 LabelString +=
" (external)";
4389 auto ContextIds =
Node->getContextIds();
4393 bool Highlight =
false;
4402 std::string AttributeString = (
Twine(
"tooltip=\"") + getNodeId(
Node) +
" " +
4403 getContextIds(ContextIds) +
"\"")
4407 AttributeString +=
",fontsize=\"30\"";
4409 (
Twine(
",fillcolor=\"") + getColor(
Node->AllocTypes, Highlight) +
"\"")
4411 if (
Node->CloneOf) {
4412 AttributeString +=
",color=\"blue\"";
4413 AttributeString +=
",style=\"filled,bold,dashed\"";
4415 AttributeString +=
",style=\"filled\"";
4416 return AttributeString;
4421 auto &Edge = *(ChildIter.getCurrent());
4426 bool Highlight =
false;
4435 auto Color = getColor(Edge->AllocTypes, Highlight);
4436 std::string AttributeString =
4437 (
Twine(
"tooltip=\"") + getContextIds(Edge->ContextIds) +
"\"" +
4439 Twine(
",fillcolor=\"") + Color +
"\"" +
Twine(
",color=\"") + Color +
4442 if (Edge->IsBackedge)
4443 AttributeString +=
",style=\"dotted\"";
4446 AttributeString +=
",penwidth=\"2.0\",weight=\"2\"";
4447 return AttributeString;
4453 if (
Node->isRemoved())
4466 std::string IdString =
"ContextIds:";
4467 if (ContextIds.
size() < 100) {
4468 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
4469 std::sort(SortedIds.begin(), SortedIds.end());
4470 for (
auto Id : SortedIds)
4471 IdString += (
" " +
Twine(Id)).str();
4473 IdString += (
" (" + Twine(ContextIds.
size()) +
" ids)").str();
4478 static std::string getColor(uint8_t AllocTypes,
bool Highlight) {
4484 if (AllocTypes == (uint8_t)AllocationType::NotCold)
4486 return !
DoHighlight || Highlight ?
"brown1" :
"lightpink";
4487 if (AllocTypes == (uint8_t)AllocationType::Cold)
4488 return !
DoHighlight || Highlight ?
"cyan" :
"lightskyblue";
4490 ((uint8_t)AllocationType::NotCold | (uint8_t)AllocationType::Cold))
4491 return Highlight ?
"magenta" :
"mediumorchid1";
4495 static std::string getNodeId(NodeRef Node) {
4496 std::stringstream SStream;
4497 SStream << std::hex <<
"N0x" << (
unsigned long long)Node;
4498 std::string
Result = SStream.str();
4507template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4512template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4513void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::exportToDot(
4514 std::string Label)
const {
4519template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4520typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
4521CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::moveEdgeToNewCalleeClone(
4522 const std::shared_ptr<ContextEdge> &
Edge,
4523 DenseSet<uint32_t> ContextIdsToMove) {
4525 assert(NodeToCallingFunc.count(Node));
4526 ContextNode *Clone =
4527 createNewNode(
Node->IsAllocation, NodeToCallingFunc[Node],
Node->Call);
4528 Node->addClone(Clone);
4529 Clone->MatchingCalls =
Node->MatchingCalls;
4530 moveEdgeToExistingCalleeClone(
Edge, Clone,
true,
4535template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4536void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
4537 moveEdgeToExistingCalleeClone(
const std::shared_ptr<ContextEdge> &
Edge,
4538 ContextNode *NewCallee,
bool NewClone,
4539 DenseSet<uint32_t> ContextIdsToMove) {
4542 assert(NewCallee->getOrigNode() ==
Edge->Callee->getOrigNode());
4544 bool EdgeIsRecursive =
Edge->Callee ==
Edge->Caller;
4546 ContextNode *OldCallee =
Edge->Callee;
4550 auto ExistingEdgeToNewCallee = NewCallee->findEdgeFromCaller(
Edge->Caller);
4554 if (ContextIdsToMove.
empty())
4555 ContextIdsToMove =
Edge->getContextIds();
4559 if (
Edge->getContextIds().size() == ContextIdsToMove.
size()) {
4562 NewCallee->AllocTypes |=
Edge->AllocTypes;
4564 if (ExistingEdgeToNewCallee) {
4567 ExistingEdgeToNewCallee->getContextIds().insert_range(ContextIdsToMove);
4568 ExistingEdgeToNewCallee->AllocTypes |=
Edge->AllocTypes;
4569 assert(
Edge->ContextIds == ContextIdsToMove);
4570 removeEdgeFromGraph(
Edge.get());
4573 Edge->Callee = NewCallee;
4574 NewCallee->CallerEdges.push_back(
Edge);
4576 OldCallee->eraseCallerEdge(
Edge.get());
4583 auto CallerEdgeAllocType = computeAllocType(ContextIdsToMove);
4584 if (ExistingEdgeToNewCallee) {
4587 ExistingEdgeToNewCallee->getContextIds().insert_range(ContextIdsToMove);
4588 ExistingEdgeToNewCallee->AllocTypes |= CallerEdgeAllocType;
4591 auto NewEdge = std::make_shared<ContextEdge>(
4592 NewCallee,
Edge->Caller, CallerEdgeAllocType, ContextIdsToMove);
4593 Edge->Caller->CalleeEdges.push_back(NewEdge);
4594 NewCallee->CallerEdges.push_back(NewEdge);
4598 NewCallee->AllocTypes |= CallerEdgeAllocType;
4600 Edge->AllocTypes = computeAllocType(
Edge->ContextIds);
4605 for (
auto &OldCalleeEdge : OldCallee->CalleeEdges) {
4606 ContextNode *CalleeToUse = OldCalleeEdge->Callee;
4610 if (CalleeToUse == OldCallee) {
4614 if (EdgeIsRecursive) {
4618 CalleeToUse = NewCallee;
4622 DenseSet<uint32_t> EdgeContextIdsToMove =
4624 set_subtract(OldCalleeEdge->getContextIds(), EdgeContextIdsToMove);
4625 OldCalleeEdge->AllocTypes =
4626 computeAllocType(OldCalleeEdge->getContextIds());
4633 if (
auto *NewCalleeEdge = NewCallee->findEdgeFromCallee(CalleeToUse)) {
4634 NewCalleeEdge->getContextIds().insert_range(EdgeContextIdsToMove);
4635 NewCalleeEdge->AllocTypes |= computeAllocType(EdgeContextIdsToMove);
4639 auto NewEdge = std::make_shared<ContextEdge>(
4640 CalleeToUse, NewCallee, computeAllocType(EdgeContextIdsToMove),
4641 EdgeContextIdsToMove);
4642 NewCallee->CalleeEdges.push_back(NewEdge);
4643 NewEdge->Callee->CallerEdges.push_back(NewEdge);
4647 OldCallee->AllocTypes = OldCallee->computeAllocType();
4649 assert((OldCallee->AllocTypes == (uint8_t)AllocationType::None) ==
4650 OldCallee->emptyContextIds());
4654 for (
const auto &OldCalleeEdge : OldCallee->CalleeEdges)
4657 for (
const auto &NewCalleeEdge : NewCallee->CalleeEdges)
4663template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4664void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
4665 moveCalleeEdgeToNewCaller(
const std::shared_ptr<ContextEdge> &
Edge,
4666 ContextNode *NewCaller) {
4667 auto *OldCallee =
Edge->Callee;
4668 auto *NewCallee = OldCallee;
4671 bool Recursive =
Edge->Caller ==
Edge->Callee;
4673 NewCallee = NewCaller;
4675 ContextNode *OldCaller =
Edge->Caller;
4676 OldCaller->eraseCalleeEdge(
Edge.get());
4680 auto ExistingEdgeToNewCaller = NewCaller->findEdgeFromCallee(NewCallee);
4682 if (ExistingEdgeToNewCaller) {
4685 ExistingEdgeToNewCaller->getContextIds().insert_range(
4686 Edge->getContextIds());
4687 ExistingEdgeToNewCaller->AllocTypes |=
Edge->AllocTypes;
4688 Edge->ContextIds.clear();
4689 Edge->AllocTypes = (uint8_t)AllocationType::None;
4690 OldCallee->eraseCallerEdge(
Edge.get());
4693 Edge->Caller = NewCaller;
4694 NewCaller->CalleeEdges.push_back(
Edge);
4696 assert(NewCallee == NewCaller);
4699 Edge->Callee = NewCallee;
4700 NewCallee->CallerEdges.push_back(
Edge);
4701 OldCallee->eraseCallerEdge(
Edge.get());
4707 NewCaller->AllocTypes |=
Edge->AllocTypes;
4714 bool IsNewNode = NewCaller->CallerEdges.empty();
4723 for (
auto &OldCallerEdge : OldCaller->CallerEdges) {
4724 auto OldCallerCaller = OldCallerEdge->Caller;
4728 OldCallerEdge->getContextIds(),
Edge->getContextIds());
4729 if (OldCaller == OldCallerCaller) {
4730 OldCallerCaller = NewCaller;
4736 set_subtract(OldCallerEdge->getContextIds(), EdgeContextIdsToMove);
4737 OldCallerEdge->AllocTypes =
4738 computeAllocType(OldCallerEdge->getContextIds());
4743 auto *ExistingCallerEdge = NewCaller->findEdgeFromCaller(OldCallerCaller);
4747 if (ExistingCallerEdge) {
4748 ExistingCallerEdge->getContextIds().insert_range(EdgeContextIdsToMove);
4749 ExistingCallerEdge->AllocTypes |=
4750 computeAllocType(EdgeContextIdsToMove);
4753 auto NewEdge = std::make_shared<ContextEdge>(
4754 NewCaller, OldCallerCaller, computeAllocType(EdgeContextIdsToMove),
4755 EdgeContextIdsToMove);
4756 NewCaller->CallerEdges.push_back(NewEdge);
4757 NewEdge->Caller->CalleeEdges.push_back(NewEdge);
4762 OldCaller->AllocTypes = OldCaller->computeAllocType();
4764 assert((OldCaller->AllocTypes == (uint8_t)AllocationType::None) ==
4765 OldCaller->emptyContextIds());
4769 for (
const auto &OldCallerEdge : OldCaller->CallerEdges)
4772 for (
const auto &NewCallerEdge : NewCaller->CallerEdges)
4778template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4779void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
4780 recursivelyRemoveNoneTypeCalleeEdges(
4781 ContextNode *Node, DenseSet<const ContextNode *> &Visited) {
4786 removeNoneTypeCalleeEdges(Node);
4788 for (
auto *Clone :
Node->Clones)
4789 recursivelyRemoveNoneTypeCalleeEdges(Clone, Visited);
4793 auto CallerEdges =
Node->CallerEdges;
4794 for (
auto &
Edge : CallerEdges) {
4796 if (
Edge->isRemoved()) {
4800 recursivelyRemoveNoneTypeCalleeEdges(
Edge->Caller, Visited);
4805template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4806void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::markBackedges() {
4811 DenseSet<const ContextNode *> Visited;
4812 DenseSet<const ContextNode *> CurrentStack;
4813 for (
auto &Entry : NonAllocationCallToContextNodeMap) {
4815 if (
Node->isRemoved())
4818 if (!
Node->CallerEdges.empty())
4820 markBackedges(Node, Visited, CurrentStack);
4826template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4827void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::markBackedges(
4828 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
4829 DenseSet<const ContextNode *> &CurrentStack) {
4830 auto I = Visited.
insert(Node);
4834 for (
auto &CalleeEdge :
Node->CalleeEdges) {
4835 auto *
Callee = CalleeEdge->Callee;
4836 if (Visited.
count(Callee)) {
4839 if (CurrentStack.
count(Callee))
4840 CalleeEdge->IsBackedge =
true;
4843 CurrentStack.
insert(Callee);
4844 markBackedges(Callee, Visited, CurrentStack);
4845 CurrentStack.
erase(Callee);
4849template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4850void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones() {
4851 DenseSet<const ContextNode *> Visited;
4852 for (
auto &Entry : AllocationCallToContextNodeMap) {
4854 identifyClones(
Entry.second, Visited,
Entry.second->getContextIds());
4857 for (
auto &Entry : AllocationCallToContextNodeMap)
4858 recursivelyRemoveNoneTypeCalleeEdges(
Entry.second, Visited);
4871template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4872void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones(
4873 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
4874 const DenseSet<uint32_t> &AllocContextIds) {
4884 if (!
Node->hasCall())
4903 auto CallerEdges =
Node->CallerEdges;
4904 for (
auto &
Edge : CallerEdges) {
4906 if (
Edge->isRemoved()) {
4912 if (
Edge->IsBackedge) {
4919 if (!Visited.
count(
Edge->Caller) && !
Edge->Caller->CloneOf) {
4920 identifyClones(
Edge->Caller, Visited, AllocContextIds);
4943 const unsigned AllocTypeCloningPriority[] = { 3, 4,
4947 [&](
const std::shared_ptr<ContextEdge> &
A,
4948 const std::shared_ptr<ContextEdge> &
B) {
4951 if (A->ContextIds.empty())
4957 if (B->ContextIds.empty())
4960 if (A->AllocTypes == B->AllocTypes)
4963 return A->Caller->NodeId < B->Caller->NodeId;
4964 return AllocTypeCloningPriority[A->AllocTypes] <
4965 AllocTypeCloningPriority[B->AllocTypes];
4968 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
4970 DenseSet<uint32_t> RecursiveContextIds;
4975 DenseSet<uint32_t> AllCallerContextIds;
4976 for (
auto &CE :
Node->CallerEdges) {
4979 AllCallerContextIds.
reserve(
CE->getContextIds().size());
4980 for (
auto Id :
CE->getContextIds())
4981 if (!AllCallerContextIds.
insert(Id).second)
4982 RecursiveContextIds.
insert(Id);
4992 auto CallerEdges =
Node->CallerEdges;
4993 for (
auto &CallerEdge : CallerEdges) {
4995 if (CallerEdge->isRemoved()) {
4999 assert(CallerEdge->Callee == Node);
5008 if (!CallerEdge->Caller->hasCall())
5013 auto CallerEdgeContextsForAlloc =
5015 if (!RecursiveContextIds.
empty())
5016 CallerEdgeContextsForAlloc =
5018 if (CallerEdgeContextsForAlloc.empty())
5021 auto CallerAllocTypeForAlloc = computeAllocType(CallerEdgeContextsForAlloc);
5025 std::vector<uint8_t> CalleeEdgeAllocTypesForCallerEdge;
5026 CalleeEdgeAllocTypesForCallerEdge.reserve(
Node->CalleeEdges.size());
5027 for (
auto &CalleeEdge :
Node->CalleeEdges)
5028 CalleeEdgeAllocTypesForCallerEdge.push_back(intersectAllocTypes(
5029 CalleeEdge->getContextIds(), CallerEdgeContextsForAlloc));
5045 assert(CallerEdge->AllocTypes != (uint8_t)AllocationType::None);
5046 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
5047 if (!CallerEdge->IsBackedge &&
5048 allocTypeToUse(CallerAllocTypeForAlloc) ==
5049 allocTypeToUse(
Node->AllocTypes) &&
5050 allocTypesMatch<DerivedCCG, FuncTy, CallTy>(
5051 CalleeEdgeAllocTypesForCallerEdge,
Node->CalleeEdges)) {
5055 if (CallerEdge->IsBackedge) {
5059 DeferredBackedges++;
5072 if (CallerEdge->IsBackedge && !CallerEdge->Caller->CloneOf &&
5073 !Visited.
count(CallerEdge->Caller)) {
5074 const auto OrigIdCount = CallerEdge->getContextIds().size();
5077 identifyClones(CallerEdge->Caller, Visited, CallerEdgeContextsForAlloc);
5078 removeNoneTypeCalleeEdges(CallerEdge->Caller);
5082 bool UpdatedEdge =
false;
5083 if (OrigIdCount > CallerEdge->getContextIds().size()) {
5084 for (
auto E :
Node->CallerEdges) {
5086 if (
E->Caller->CloneOf != CallerEdge->Caller)
5090 auto CallerEdgeContextsForAllocNew =
5092 if (CallerEdgeContextsForAllocNew.empty())
5102 CallerEdgeContextsForAlloc.swap(CallerEdgeContextsForAllocNew);
5112 if (CallerEdge->isRemoved())
5122 CallerEdgeContextsForAlloc, CallerEdge->getContextIds());
5123 if (CallerEdgeContextsForAlloc.empty())
5128 CallerAllocTypeForAlloc = computeAllocType(CallerEdgeContextsForAlloc);
5129 CalleeEdgeAllocTypesForCallerEdge.clear();
5130 for (
auto &CalleeEdge :
Node->CalleeEdges) {
5131 CalleeEdgeAllocTypesForCallerEdge.push_back(intersectAllocTypes(
5132 CalleeEdge->getContextIds(), CallerEdgeContextsForAlloc));
5138 ContextNode *Clone =
nullptr;
5139 for (
auto *CurClone :
Node->Clones) {
5140 if (allocTypeToUse(CurClone->AllocTypes) !=
5141 allocTypeToUse(CallerAllocTypeForAlloc))
5148 assert(!BothSingleAlloc ||
5149 CurClone->AllocTypes == CallerAllocTypeForAlloc);
5155 if (BothSingleAlloc || allocTypesMatchClone<DerivedCCG, FuncTy, CallTy>(
5156 CalleeEdgeAllocTypesForCallerEdge, CurClone)) {
5164 moveEdgeToExistingCalleeClone(CallerEdge, Clone,
false,
5165 CallerEdgeContextsForAlloc);
5167 Clone = moveEdgeToNewCalleeClone(CallerEdge, CallerEdgeContextsForAlloc);
5170 assert(Clone->AllocTypes != (uint8_t)AllocationType::None);
5177 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
5183void ModuleCallsiteContextGraph::updateAllocationCall(
5199 .emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofAttribute",
Call.call())
5200 <<
ore::NV(
"AllocationCall",
Call.call()) <<
" in clone "
5202 <<
" marked with memprof allocation attribute "
5203 <<
ore::NV(
"Attribute", AllocTypeString));
5206void IndexCallsiteContextGraph::updateAllocationCall(CallInfo &
Call,
5210 assert(AI->Versions.size() >
Call.cloneNo());
5215ModuleCallsiteContextGraph::getAllocationCallType(
const CallInfo &
Call)
const {
5217 if (!CB->getAttributes().hasFnAttr(
"memprof"))
5218 return AllocationType::None;
5219 StringRef AllocTypeString =
5220 CB->getAttributes().getFnAttr(
"memprof").getValueAsString();
5221 if (AllocTypeString ==
"cold")
5222 return AllocationType::Cold;
5223 if (AllocTypeString ==
"ambiguous")
5225 (uint8_t)AllocationType::Cold);
5226 return AllocationType::NotCold;
5230IndexCallsiteContextGraph::getAllocationCallType(
const CallInfo &
Call)
const {
5232 assert(AI->Versions.size() >
Call.cloneNo());
5236void ModuleCallsiteContextGraph::updateCall(CallInfo &CallerCall,
5237 FuncInfo CalleeFunc) {
5238 auto *CurF = getCalleeFunc(CallerCall.call());
5239 auto NewCalleeCloneNo = CalleeFunc.cloneNo();
5246 if (CurCalleeCloneNo != NewCalleeCloneNo) {
5248 << CurCalleeCloneNo <<
" now " << NewCalleeCloneNo
5250 MismatchedCloneAssignments++;
5253 if (NewCalleeCloneNo > 0)
5254 cast<CallBase>(CallerCall.call())->setCalledFunction(CalleeFunc.func());
5255 OREGetter(CallerCall.call()->getFunction())
5256 .emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofCall", CallerCall.call())
5257 <<
ore::NV(
"Call", CallerCall.call()) <<
" in clone "
5258 <<
ore::NV(
"Caller", CallerCall.call()->getFunction())
5259 <<
" assigned to call function clone "
5260 <<
ore::NV(
"Callee", CalleeFunc.func()));
5263void IndexCallsiteContextGraph::updateCall(CallInfo &CallerCall,
5264 FuncInfo CalleeFunc) {
5267 "Caller cannot be an allocation which should not have profiled calls");
5268 assert(CI->Clones.size() > CallerCall.cloneNo());
5269 auto NewCalleeCloneNo = CalleeFunc.cloneNo();
5270 auto &CurCalleeCloneNo = CI->Clones[CallerCall.cloneNo()];
5275 if (CurCalleeCloneNo != 0 && CurCalleeCloneNo != NewCalleeCloneNo) {
5277 << CurCalleeCloneNo <<
" now " << NewCalleeCloneNo
5279 MismatchedCloneAssignments++;
5281 CurCalleeCloneNo = NewCalleeCloneNo;
5293 SP->replaceLinkageName(MDName);
5297 TempDISubprogram NewDecl = Decl->
clone();
5298 NewDecl->replaceLinkageName(MDName);
5302CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
5304ModuleCallsiteContextGraph::cloneFunctionForCallsite(
5305 FuncInfo &Func, CallInfo &
Call, DenseMap<CallInfo, CallInfo> &CallMap,
5306 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
5313 NewFunc->setMetadata(LLVMContext::MD_kcfi_type,
nullptr);
5315 assert(!
Func.func()->getParent()->getFunction(Name));
5316 NewFunc->setName(Name);
5318 for (
auto &Inst : CallsWithMetadataInFunc) {
5320 assert(Inst.cloneNo() == 0);
5323 OREGetter(
Func.func())
5324 .emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofClone",
Func.func())
5325 <<
"created clone " <<
ore::NV(
"NewFunction", NewFunc));
5326 return {NewFunc, CloneNo};
5329CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
5330 IndexCall>::FuncInfo
5331IndexCallsiteContextGraph::cloneFunctionForCallsite(
5332 FuncInfo &Func, CallInfo &
Call, DenseMap<CallInfo, CallInfo> &CallMap,
5333 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
5347 for (
auto &Inst : CallsWithMetadataInFunc) {
5349 assert(Inst.cloneNo() == 0);
5351 assert(AI->Versions.size() == CloneNo);
5354 AI->Versions.push_back(0);
5357 assert(CI && CI->Clones.size() == CloneNo);
5360 CI->Clones.push_back(0);
5362 CallMap[Inst] = {Inst.call(), CloneNo};
5364 return {
Func.func(), CloneNo};
5381template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5382void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::mergeClones() {
5388 DenseMap<uint32_t, ContextNode *> ContextIdToAllocationNode;
5389 for (
auto &Entry : AllocationCallToContextNodeMap) {
5391 for (
auto Id :
Node->getContextIds())
5392 ContextIdToAllocationNode[
Id] =
Node->getOrigNode();
5393 for (
auto *Clone :
Node->Clones) {
5394 for (
auto Id : Clone->getContextIds())
5395 ContextIdToAllocationNode[
Id] = Clone->getOrigNode();
5402 DenseSet<const ContextNode *> Visited;
5403 for (
auto &Entry : AllocationCallToContextNodeMap) {
5406 mergeClones(Node, Visited, ContextIdToAllocationNode);
5412 auto Clones =
Node->Clones;
5413 for (
auto *Clone : Clones)
5414 mergeClones(Clone, Visited, ContextIdToAllocationNode);
5418 dbgs() <<
"CCG after merging:\n";
5422 exportToDot(
"aftermerge");
5430template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5431void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::mergeClones(
5432 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
5433 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode) {
5443 bool FoundUnvisited =
true;
5445 while (FoundUnvisited) {
5447 FoundUnvisited =
false;
5450 auto CallerEdges =
Node->CallerEdges;
5451 for (
auto CallerEdge : CallerEdges) {
5453 if (CallerEdge->Callee != Node)
5458 FoundUnvisited =
true;
5459 mergeClones(CallerEdge->Caller, Visited, ContextIdToAllocationNode);
5463 TotalMergeInvokes++;
5464 TotalMergeIters += Iters;
5465 if (Iters > MaxMergeIters)
5466 MaxMergeIters = Iters;
5469 mergeNodeCalleeClones(Node, Visited, ContextIdToAllocationNode);
5472template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5473void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::mergeNodeCalleeClones(
5474 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
5475 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode) {
5477 if (
Node->emptyContextIds())
5482 MapVector<ContextNode *, std::vector<std::shared_ptr<ContextEdge>>>
5483 OrigNodeToCloneEdges;
5484 for (
const auto &
E :
Node->CalleeEdges) {
5489 OrigNodeToCloneEdges[
Base].push_back(
E);
5495 auto CalleeCallerEdgeLessThan = [](
const std::shared_ptr<ContextEdge> &
A,
5496 const std::shared_ptr<ContextEdge> &
B) {
5497 if (
A->Callee->CallerEdges.size() !=
B->Callee->CallerEdges.size())
5498 return A->Callee->CallerEdges.size() <
B->Callee->CallerEdges.size();
5499 if (
A->Callee->CloneOf && !
B->Callee->CloneOf)
5501 else if (!
A->Callee->CloneOf &&
B->Callee->CloneOf)
5504 return A->Callee->NodeId <
B->Callee->NodeId;
5509 for (
auto Entry : OrigNodeToCloneEdges) {
5512 auto &CalleeEdges =
Entry.second;
5513 auto NumCalleeClones = CalleeEdges.size();
5515 if (NumCalleeClones == 1)
5526 DenseSet<ContextNode *> OtherCallersToShareMerge;
5527 findOtherCallersToShareMerge(Node, CalleeEdges, ContextIdToAllocationNode,
5528 OtherCallersToShareMerge);
5533 ContextNode *MergeNode =
nullptr;
5534 DenseMap<ContextNode *, unsigned> CallerToMoveCount;
5535 for (
auto CalleeEdge : CalleeEdges) {
5536 auto *OrigCallee = CalleeEdge->Callee;
5542 if (CalleeEdge->Callee->CallerEdges.size() == 1) {
5543 MergeNode = OrigCallee;
5544 NonNewMergedNodes++;
5551 if (!OtherCallersToShareMerge.
empty()) {
5552 bool MoveAllCallerEdges =
true;
5553 for (
auto CalleeCallerE : OrigCallee->CallerEdges) {
5554 if (CalleeCallerE == CalleeEdge)
5556 if (!OtherCallersToShareMerge.
contains(CalleeCallerE->Caller)) {
5557 MoveAllCallerEdges =
false;
5563 if (MoveAllCallerEdges) {
5564 MergeNode = OrigCallee;
5565 NonNewMergedNodes++;
5572 assert(MergeNode != OrigCallee);
5573 moveEdgeToExistingCalleeClone(CalleeEdge, MergeNode,
5576 MergeNode = moveEdgeToNewCalleeClone(CalleeEdge);
5581 if (!OtherCallersToShareMerge.
empty()) {
5585 auto OrigCalleeCallerEdges = OrigCallee->CallerEdges;
5586 for (
auto &CalleeCallerE : OrigCalleeCallerEdges) {
5587 if (CalleeCallerE == CalleeEdge)
5589 if (!OtherCallersToShareMerge.
contains(CalleeCallerE->Caller))
5591 CallerToMoveCount[CalleeCallerE->Caller]++;
5592 moveEdgeToExistingCalleeClone(CalleeCallerE, MergeNode,
5596 removeNoneTypeCalleeEdges(OrigCallee);
5597 removeNoneTypeCalleeEdges(MergeNode);
5615template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5616void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
5617 findOtherCallersToShareMerge(
5619 std::vector<std::shared_ptr<ContextEdge>> &CalleeEdges,
5620 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode,
5621 DenseSet<ContextNode *> &OtherCallersToShareMerge) {
5622 auto NumCalleeClones = CalleeEdges.size();
5625 DenseMap<ContextNode *, unsigned> OtherCallersToSharedCalleeEdgeCount;
5628 unsigned PossibleOtherCallerNodes = 0;
5632 if (CalleeEdges[0]->
Callee->CallerEdges.size() < 2)
5638 DenseMap<ContextEdge *, DenseSet<ContextNode *>> CalleeEdgeToAllocNodes;
5639 for (
auto CalleeEdge : CalleeEdges) {
5640 assert(CalleeEdge->Callee->CallerEdges.size() > 1);
5643 for (
auto CalleeCallerEdges : CalleeEdge->Callee->CallerEdges) {
5644 if (CalleeCallerEdges->Caller == Node) {
5645 assert(CalleeCallerEdges == CalleeEdge);
5648 OtherCallersToSharedCalleeEdgeCount[CalleeCallerEdges->Caller]++;
5651 if (OtherCallersToSharedCalleeEdgeCount[CalleeCallerEdges->Caller] ==
5653 PossibleOtherCallerNodes++;
5657 for (
auto Id : CalleeEdge->getContextIds()) {
5658 auto *
Alloc = ContextIdToAllocationNode.
lookup(Id);
5662 MissingAllocForContextId++;
5665 CalleeEdgeToAllocNodes[CalleeEdge.get()].
insert(
Alloc);
5672 for (
auto CalleeEdge : CalleeEdges) {
5673 assert(CalleeEdge->Callee->CallerEdges.size() > 1);
5675 if (!PossibleOtherCallerNodes)
5677 auto &CurCalleeAllocNodes = CalleeEdgeToAllocNodes[CalleeEdge.get()];
5679 for (
auto &CalleeCallerE : CalleeEdge->Callee->CallerEdges) {
5681 if (CalleeCallerE == CalleeEdge)
5685 if (OtherCallersToSharedCalleeEdgeCount[CalleeCallerE->Caller] !=
5690 for (
auto Id : CalleeCallerE->getContextIds()) {
5691 auto *
Alloc = ContextIdToAllocationNode.
lookup(Id);
5696 if (!CurCalleeAllocNodes.contains(
Alloc)) {
5697 OtherCallersToSharedCalleeEdgeCount[CalleeCallerE->Caller] = 0;
5698 PossibleOtherCallerNodes--;
5705 if (!PossibleOtherCallerNodes)
5710 for (
auto &[OtherCaller,
Count] : OtherCallersToSharedCalleeEdgeCount) {
5711 if (
Count != NumCalleeClones)
5713 OtherCallersToShareMerge.
insert(OtherCaller);
5717template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5718const typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
5719CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::resolveImplicitSource(
5720 const ContextNode *Node,
const ImplicitSource &Src) {
5721 if (!Src.Source->emptyContextIds())
5727 if (
Node->hasContextId(Src.ContextId))
5729 for (
const ContextNode *
C :
Node->Clones)
5730 if (
C->hasContextId(Src.ContextId))
5735 assert(
false &&
"trimmed context id on no clone of its callsite node");
5777template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5778void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::assignImplicitCallers(
5779 ContextNode *Node,
const DenseSet<uint32_t> &TrimmedContextIds,
5780 DenseMap<ContextNode *, FuncInfo> &CallsiteToCalleeFuncCloneMap,
5781 const std::map<FuncInfo, ContextNode *> &FuncCloneToCurNodeCloneMap,
5782 ImplicitSourceMap &ImplicitSources) {
5783 auto HasEdgeToNodeFamily = [&](
const ContextNode *
N) {
5785 [&](
const std::shared_ptr<ContextEdge> &
E) {
5786 return E->Callee->getOrigNode() == Node;
5820 auto ImpliesContextIds =
5821 [&](ContextNode *
K, ContextNode *
Y,
const DenseSet<uint32_t> &Ids,
5822 DenseMap<std::pair<ContextNode *, ContextNode *>, DenseSet<uint32_t>>
5824 auto &&ImpliesContextIds) ->
bool {
5825 assert(
K->getOrigNode() ==
Y->getOrigNode());
5826 DenseSet<uint32_t> &VisitedIds = Visited[{
K,
Y}];
5827 DenseSet<uint32_t> NewIds;
5829 if (VisitedIds.
insert(Id).second)
5837 DenseSet<uint32_t> IdsOnCallerEdges;
5838 for (
auto &YEdge :
Y->CallerEdges) {
5839 DenseSet<uint32_t> IdsFromZ =
5841 if (IdsFromZ.
empty())
5844 IdsFromCallers.
push_back({YEdge->Caller, std::move(IdsFromZ)});
5848 if (IdsOnCallerEdges.
size() < NewIds.
size())
5852 for (
auto &[Z, IdsFromZ] : IdsFromCallers) {
5853 for (
auto &KEdge :
K->CallerEdges) {
5854 ContextNode *
C = KEdge->Caller;
5855 if (
C == Z ||
C->getOrigNode() !=
Z->getOrigNode())
5859 DenseSet<uint32_t> IdsNotOnC;
5860 for (
auto Id : IdsFromZ)
5861 if (!
C->hasContextId(Id))
5863 if (!IdsNotOnC.
empty() &&
5864 ImpliesContextIds(
C, Z, IdsNotOnC, Visited, ImpliesContextIds))
5873 auto SameVersion = [&](
const ContextNode *
A,
const ContextNode *
B) {
5876 if (
Node->IsAllocation)
5877 return allocTypeToUse(
A->AllocTypes) == allocTypeToUse(
B->AllocTypes);
5878 auto AIt = CallsiteToCalleeFuncCloneMap.
find(
A);
5879 auto BIt = CallsiteToCalleeFuncCloneMap.
find(
B);
5880 return AIt != CallsiteToCalleeFuncCloneMap.
end() &&
5881 BIt != CallsiteToCalleeFuncCloneMap.
end() &&
5882 AIt->second == BIt->second;
5886 DenseSet<const ContextNode *> ImplicitCallers;
5891 auto ProcessCaller = [&](
const std::shared_ptr<ContextEdge> &
Edge) {
5892 ContextNode *
Y =
Edge->Caller;
5893 ContextNode *Orig =
Y->getOrigNode();
5894 if (!
Y->hasCall() || Orig->Clones.empty())
5896 DenseSet<uint32_t> TrimmedIds =
5898 if (TrimmedIds.
empty())
5900 auto YIt = CallsiteToCalleeFuncCloneMap.
find(
Y);
5901 if (YIt == CallsiteToCalleeFuncCloneMap.
end())
5904 const FuncInfo YFuncClone = YIt->second;
5907 auto RequiredIt = FuncCloneToCurNodeCloneMap.find(YFuncClone);
5908 assert(RequiredIt != FuncCloneToCurNodeCloneMap.end());
5909 const ContextNode *
Required = RequiredIt->second;
5917 auto RecordImplicitSource = [&](
const FuncInfo &
F,
const ContextNode *Src) {
5920 if (
F.cloneNo() != 0)
5921 ImplicitSources.try_emplace({
Node,
F.cloneNo()},
5922 ImplicitSource{Src, *TrimmedIds.
begin()});
5928 if (K ==
Y || !
K->hasCall() ||
K->emptyContextIds() ||
5929 HasEdgeToNodeFamily(K) || ImplicitCallers.
contains(K))
5931 DenseMap<std::pair<ContextNode *, ContextNode *>, DenseSet<uint32_t>>
5933 if (!ImpliesContextIds(K,
Y, TrimmedIds, Visited, ImpliesContextIds))
5936 ImplicitCallers.
insert(K);
5937 auto KIt = CallsiteToCalleeFuncCloneMap.
find(K);
5938 if (KIt == CallsiteToCalleeFuncCloneMap.
end()) {
5941 CallsiteToCalleeFuncCloneMap[
K] = YFuncClone;
5942 RecordImplicitSource(YFuncClone, Required);
5943 NumImplicitCallersAssigned++;
5946 const FuncInfo KFuncClone = KIt->second;
5947 if (KFuncClone == YFuncClone) {
5949 RecordImplicitSource(YFuncClone, Required);
5952 unsigned KCloneNo = KFuncClone.cloneNo();
5953 auto KNodeCloneIt = FuncCloneToCurNodeCloneMap.find(KFuncClone);
5954 if (KNodeCloneIt == FuncCloneToCurNodeCloneMap.end()) {
5956 if (KCloneNo == 0) {
5960 if (
Node->IsAllocation) {
5961 if (allocTypeToUse(
Required->AllocTypes) == AllocationType::NotCold)
5963 }
else if (
auto It = CallsiteToCalleeFuncCloneMap.
find(Required);
5964 It != CallsiteToCalleeFuncCloneMap.
end() &&
5965 It->second.cloneNo() == 0)
5971 auto [It,
Inserted] = ImplicitSources.try_emplace(
5974 NumImplicitCallersSourced++;
5975 if (SameVersion(It->second.Source, Required))
5978 }
else if (SameVersion(KNodeCloneIt->second, Required)) {
5981 RecordImplicitSource(KFuncClone, KNodeCloneIt->second);
5985 NumImplicitCallersUnresolved++;
5991 for (
auto &
Edge :
Node->CallerEdges)
5992 ProcessCaller(
Edge);
5993 for (
auto *Clone :
Node->Clones)
5994 for (
auto &
Edge : Clone->CallerEdges)
5995 ProcessCaller(
Edge);
6039template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
6040bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::assignFunctions() {
6048 DenseSet<uint32_t> TrimmedContextIds;
6049 for (
auto &NodePtr : NodeOwner) {
6050 ContextNode *
N = NodePtr.get();
6051 if (
N->IsAllocation ||
N->CalleeEdges.empty() ||
6052 (
N->CallerEdges.empty() &&
N->Clones.empty() && !
N->CloneOf))
6057 DenseSet<uint32_t> CallerIds;
6058 for (
auto &
E :
N->CallerEdges)
6060 for (
auto &CalleeEdge :
N->CalleeEdges)
6061 for (
auto Id : CalleeEdge->getContextIds())
6063 TrimmedContextIds.
insert(Id);
6065 NumTrimmedContextIds += TrimmedContextIds.
size();
6069 DenseMap<ContextNode *, FuncInfo> CallsiteToCalleeFuncCloneMap;
6073 auto RecordCalleeFuncOfCallsite = [&](ContextNode *
Caller,
6074 const FuncInfo &CalleeFunc) {
6076 CallsiteToCalleeFuncCloneMap[
Caller] = CalleeFunc;
6080 struct FuncCloneInfo {
6085 DenseMap<CallInfo, CallInfo> CallMap;
6121 struct UnassignedCallCloneInfo {
6123 const ContextNode *
Source =
nullptr;
6125 DenseMap<const ContextNode *, std::map<unsigned, UnassignedCallCloneInfo>>
6126 UnassignedCallClones;
6130 for (
auto &[Func, CallsWithMetadata] : FuncToCallsWithMetadata) {
6131 FuncInfo OrigFunc(Func);
6136 std::vector<FuncCloneInfo> FuncCloneInfos;
6143 std::vector<unsigned> FuncCloneParent;
6146 ImplicitSourceMap ImplicitSources;
6153 struct OrigCallsInfo {
6157 DenseMap<const ContextNode *, OrigCallsInfo> OrigNodeToOrigCalls;
6158 for (
auto &
Call : CallsWithMetadata) {
6159 ContextNode *
Node = getNodeForInst(
Call);
6161 OrigNodeToOrigCalls[
Node] = {
Call,
Node->MatchingCalls};
6163 for (
auto &
Call : CallsWithMetadata) {
6164 ContextNode *
Node = getNodeForInst(
Call);
6168 if (!Node ||
Node->Clones.empty())
6171 "Not having a call should have prevented cloning");
6175 std::map<FuncInfo, ContextNode *> FuncCloneToCurNodeCloneMap;
6179 auto AssignCallsiteCloneToFuncClone = [&](
const FuncInfo &FuncClone,
6181 ContextNode *CallsiteClone,
6184 FuncCloneToCurNodeCloneMap[FuncClone] = CallsiteClone;
6186 assert(FuncCloneInfos.size() > FuncClone.cloneNo());
6187 DenseMap<CallInfo, CallInfo> &CallMap =
6188 FuncCloneInfos[FuncClone.cloneNo()].CallMap;
6189 CallInfo CallClone(
Call);
6190 if (
auto It = CallMap.
find(
Call); It != CallMap.
end())
6191 CallClone = It->second;
6192 CallsiteClone->setCall(CallClone);
6198 CallsiteClone->MatchingCalls.clear();
6199 for (
const CallInfo &OrigMatchingCall :
6200 OrigNodeToOrigCalls[Node].MatchingCalls) {
6201 CallInfo CallClone(OrigMatchingCall);
6202 if (
auto It = CallMap.
find(OrigMatchingCall); It != CallMap.
end())
6203 CallClone = It->second;
6204 CallsiteClone->MatchingCalls.push_back(CallClone);
6212 auto MoveEdgeToNewCalleeCloneAndSetUp =
6213 [&](
const std::shared_ptr<ContextEdge> &
Edge) {
6214 ContextNode *OrigCallee =
Edge->Callee;
6215 ContextNode *NewClone = moveEdgeToNewCalleeClone(
Edge);
6216 removeNoneTypeCalleeEdges(NewClone);
6217 assert(NewClone->AllocTypes != (uint8_t)AllocationType::None);
6221 if (CallsiteToCalleeFuncCloneMap.
count(OrigCallee))
6222 RecordCalleeFuncOfCallsite(
6223 NewClone, CallsiteToCalleeFuncCloneMap[OrigCallee]);
6230 std::deque<ContextNode *> ClonesWorklist;
6232 if (!
Node->emptyContextIds())
6233 ClonesWorklist.push_back(Node);
6239 unsigned NodeCloneCount = 0;
6240 while (!ClonesWorklist.empty()) {
6241 ContextNode *Clone = ClonesWorklist.front();
6242 ClonesWorklist.pop_front();
6251 if (FuncCloneInfos.size() < NodeCloneCount) {
6253 if (NodeCloneCount == 1) {
6258 Clone->CallerEdges, [&](
const std::shared_ptr<ContextEdge> &
E) {
6259 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
6263 FuncCloneInfos.push_back(
6264 {OrigFunc, DenseMap<CallInfo, CallInfo>()});
6265 FuncCloneParent.push_back(0);
6266 AssignCallsiteCloneToFuncClone(
6267 OrigFunc,
Call, Clone,
6268 AllocationCallToContextNodeMap.count(
Call));
6269 for (
auto &CE : Clone->CallerEdges) {
6271 if (!
CE->Caller->hasCall())
6273 RecordCalleeFuncOfCallsite(
CE->Caller, OrigFunc);
6283 FuncInfo PreviousAssignedFuncClone;
6285 Clone->CallerEdges, [&](
const std::shared_ptr<ContextEdge> &
E) {
6286 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
6288 bool CallerAssignedToCloneOfFunc =
false;
6289 if (EI != Clone->CallerEdges.end()) {
6290 const std::shared_ptr<ContextEdge> &
Edge = *EI;
6291 PreviousAssignedFuncClone =
6292 CallsiteToCalleeFuncCloneMap[
Edge->Caller];
6293 CallerAssignedToCloneOfFunc =
true;
6298 DenseMap<CallInfo, CallInfo> NewCallMap;
6299 unsigned CloneNo = FuncCloneInfos.size();
6300 assert(CloneNo > 0 &&
"Clone 0 is the original function, which "
6301 "should already exist in the map");
6302 FuncInfo NewFuncClone = cloneFunctionForCallsite(
6303 OrigFunc,
Call, NewCallMap, CallsWithMetadata, CloneNo);
6304 FuncCloneInfos.push_back({NewFuncClone, std::move(NewCallMap)});
6307 FuncCloneParent.push_back(CallerAssignedToCloneOfFunc
6308 ? PreviousAssignedFuncClone.cloneNo()
6310 FunctionClonesAnalysis++;
6316 if (!CallerAssignedToCloneOfFunc) {
6317 AssignCallsiteCloneToFuncClone(
6318 NewFuncClone,
Call, Clone,
6319 AllocationCallToContextNodeMap.count(
Call));
6320 for (
auto &CE : Clone->CallerEdges) {
6322 if (!
CE->Caller->hasCall())
6324 RecordCalleeFuncOfCallsite(
CE->Caller, NewFuncClone);
6336 auto CallerEdges = Clone->CallerEdges;
6337 for (
auto CE : CallerEdges) {
6339 if (
CE->isRemoved()) {
6345 if (!
CE->Caller->hasCall())
6348 if (!CallsiteToCalleeFuncCloneMap.
count(
CE->Caller) ||
6352 CallsiteToCalleeFuncCloneMap[
CE->Caller] !=
6353 PreviousAssignedFuncClone)
6356 RecordCalleeFuncOfCallsite(
CE->Caller, NewFuncClone);
6369 auto CalleeEdges =
CE->Caller->CalleeEdges;
6370 for (
auto CalleeEdge : CalleeEdges) {
6373 if (CalleeEdge->isRemoved()) {
6378 ContextNode *
Callee = CalleeEdge->Callee;
6382 if (Callee == Clone || !
Callee->hasCall())
6387 if (Callee == CalleeEdge->Caller)
6389 ContextNode *NewClone =
6390 MoveEdgeToNewCalleeCloneAndSetUp(CalleeEdge);
6393 removeNoneTypeCalleeEdges(Callee);
6406 auto &OrigCalls = OrigNodeToOrigCalls[
Callee->getOrigNode()];
6407 DenseMap<CallInfo, CallInfo> &CallMap =
6408 FuncCloneInfos[NewFuncClone.cloneNo()].CallMap;
6410 CallInfo NewCall(CallMap[OrigCalls.Call]);
6412 NewClone->setCall(NewCall);
6414 NewClone->MatchingCalls.clear();
6415 for (
auto &OrigMatchingCall : OrigCalls.MatchingCalls) {
6417 CallInfo NewCall(CallMap[OrigMatchingCall]);
6419 NewClone->MatchingCalls.push_back(NewCall);
6428 auto FindFirstAvailFuncClone = [&]() {
6433 for (
auto &CF : FuncCloneInfos) {
6434 if (!FuncCloneToCurNodeCloneMap.count(CF.FuncClone))
6435 return CF.FuncClone;
6438 "Expected an available func clone for this callsite clone");
6455 std::map<FuncInfo, ContextNode *> FuncCloneToNewCallsiteCloneMap;
6456 FuncInfo FuncCloneAssignedToCurCallsiteClone;
6460 auto CloneCallerEdges = Clone->CallerEdges;
6461 for (
auto &
Edge : CloneCallerEdges) {
6465 if (
Edge->isRemoved())
6468 if (!
Edge->Caller->hasCall())
6472 if (CallsiteToCalleeFuncCloneMap.
count(
Edge->Caller)) {
6473 FuncInfo FuncCloneCalledByCaller =
6474 CallsiteToCalleeFuncCloneMap[
Edge->Caller];
6484 if ((FuncCloneToCurNodeCloneMap.count(FuncCloneCalledByCaller) &&
6485 FuncCloneToCurNodeCloneMap[FuncCloneCalledByCaller] !=
6493 (FuncCloneAssignedToCurCallsiteClone &&
6494 FuncCloneAssignedToCurCallsiteClone !=
6495 FuncCloneCalledByCaller)) {
6510 if (FuncCloneToNewCallsiteCloneMap.count(
6511 FuncCloneCalledByCaller)) {
6512 ContextNode *NewClone =
6513 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller];
6514 moveEdgeToExistingCalleeClone(
Edge, NewClone);
6516 removeNoneTypeCalleeEdges(NewClone);
6519 ContextNode *NewClone = MoveEdgeToNewCalleeCloneAndSetUp(
Edge);
6520 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller] =
6523 ClonesWorklist.push_back(NewClone);
6527 removeNoneTypeCalleeEdges(Clone);
6535 if (!FuncCloneAssignedToCurCallsiteClone) {
6536 FuncCloneAssignedToCurCallsiteClone = FuncCloneCalledByCaller;
6538 AssignCallsiteCloneToFuncClone(
6539 FuncCloneCalledByCaller,
Call, Clone,
6540 AllocationCallToContextNodeMap.count(
Call));
6544 assert(FuncCloneAssignedToCurCallsiteClone ==
6545 FuncCloneCalledByCaller);
6554 if (!FuncCloneAssignedToCurCallsiteClone) {
6555 FuncCloneAssignedToCurCallsiteClone = FindFirstAvailFuncClone();
6556 assert(FuncCloneAssignedToCurCallsiteClone);
6558 AssignCallsiteCloneToFuncClone(
6559 FuncCloneAssignedToCurCallsiteClone,
Call, Clone,
6560 AllocationCallToContextNodeMap.count(
Call));
6562 assert(FuncCloneToCurNodeCloneMap
6563 [FuncCloneAssignedToCurCallsiteClone] == Clone);
6565 RecordCalleeFuncOfCallsite(
Edge->Caller,
6566 FuncCloneAssignedToCurCallsiteClone);
6586 if (!FuncCloneAssignedToCurCallsiteClone) {
6587 FuncCloneAssignedToCurCallsiteClone = FindFirstAvailFuncClone();
6588 assert(FuncCloneAssignedToCurCallsiteClone &&
6589 "No available func clone for this callsite clone");
6590 AssignCallsiteCloneToFuncClone(
6591 FuncCloneAssignedToCurCallsiteClone,
Call, Clone,
6592 AllocationCallToContextNodeMap.contains(
Call));
6595 assignImplicitCallers(Node, TrimmedContextIds,
6596 CallsiteToCalleeFuncCloneMap,
6597 FuncCloneToCurNodeCloneMap, ImplicitSources);
6600 for (
const auto &PE :
Node->CalleeEdges)
6602 for (
const auto &CE :
Node->CallerEdges)
6604 for (
auto *Clone :
Node->Clones) {
6606 for (
const auto &PE : Clone->CalleeEdges)
6608 for (
const auto &CE : Clone->CallerEdges)
6615 FuncToNumClones[
Func] = std::max<unsigned>(1, FuncCloneInfos.size());
6616 if (FuncCloneInfos.size() < 2)
6622 for (
auto &
Call : CallsWithMetadata) {
6623 ContextNode *
Node = getNodeForInst(
Call);
6624 if (!Node || !
Node->hasCall() ||
Node->emptyContextIds())
6629 DenseMap<unsigned, const ContextNode *> FuncCloneToNodeClone;
6630 FuncCloneToNodeClone[
Node->Call.cloneNo()] =
Node;
6638 for (
auto *
C :
Node->Clones)
6639 if (!
C->emptyContextIds() ||
6640 !ImplicitSources.contains({Node, C->Call.cloneNo()}))
6641 FuncCloneToNodeClone[
C->Call.cloneNo()] =
C;
6644 if (FuncCloneToNodeClone.
size() >= FuncCloneInfos.size())
6647 for (
auto &FC : FuncCloneInfos) {
6648 unsigned I =
FC.FuncClone.cloneNo();
6651 if (
I == 0 || FuncCloneToNodeClone.
contains(
I)) {
6659 auto &
Info = UnassignedCallClones[
Node][
I];
6660 auto &CallVector =
Info.Calls;
6661 for (
unsigned P =
I;;
P = FuncCloneParent[
P]) {
6662 if (
auto It = ImplicitSources.find({Node, P});
6663 It != ImplicitSources.end()) {
6664 Info.Source = resolveImplicitSource(Node, It->second);
6667 if (
auto It = FuncCloneToNodeClone.
find(
P);
6668 It != FuncCloneToNodeClone.
end()) {
6669 Info.Source = It->second;
6675 DenseMap<CallInfo, CallInfo> &CallMap =
FC.CallMap;
6676 if (
auto It = CallMap.
find(
Call); It != CallMap.
end()) {
6677 CallInfo CallClone = It->second;
6678 CallVector.push_back(CallClone);
6682 assert(
false &&
"Expected to find call in CallMap");
6688 for (
const CallInfo &OrigMatchingCall :
6689 OrigNodeToOrigCalls[Node].MatchingCalls) {
6690 if (
auto It = CallMap.
find(OrigMatchingCall); It != CallMap.
end()) {
6691 CallInfo CallClone = It->second;
6692 CallVector.push_back(CallClone);
6696 assert(
false &&
"Expected to find call in CallMap");
6704 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
6706 auto UpdateCalls = [&](ContextNode *
Node,
6707 DenseSet<const ContextNode *> &Visited,
6708 auto &&UpdateCalls) {
6709 auto Inserted = Visited.insert(Node);
6713 for (
auto *Clone :
Node->Clones)
6714 UpdateCalls(Clone, Visited, UpdateCalls);
6716 for (
auto &
Edge :
Node->CallerEdges)
6717 UpdateCalls(
Edge->Caller, Visited, UpdateCalls);
6721 if (!
Node->hasCall() ||
Node->emptyContextIds())
6727 auto GetUnassignedCallClones = [&](ContextNode *
Node) {
6730 auto UnassignedIt = UnassignedCallClones.
find(Node);
6731 if (UnassignedIt == UnassignedCallClones.
end())
6733 DenseSet<unsigned> NodeCallClones;
6734 for (
auto *
C :
Node->Clones)
6735 if (!
C->emptyContextIds())
6736 NodeCallClones.
insert(
C->Call.cloneNo());
6737 for (
auto &[CloneNo, Info] : UnassignedIt->second) {
6741 if (NodeCallClones.
contains(CloneNo))
6748 if (
Node->IsAllocation) {
6749 auto GetAllocTypeToUse = [&](
const ContextNode *
Node) {
6750 auto AT = allocTypeToUse(
Node->AllocTypes);
6762 !ContextIdToContextSizeInfos.
empty()) {
6765 for (
auto Id :
Node->getContextIds()) {
6766 auto TypeI = ContextIdToAllocationType.
find(Id);
6767 assert(TypeI != ContextIdToAllocationType.
end());
6768 auto CSI = ContextIdToContextSizeInfos.
find(Id);
6769 if (CSI != ContextIdToContextSizeInfos.
end()) {
6770 for (
auto &Info : CSI->second) {
6772 if (TypeI->second == AllocationType::Cold)
6773 TotalCold +=
Info.TotalSize;
6778 AT = AllocationType::Cold;
6782 updateAllocationCall(
Node->Call, GetAllocTypeToUse(Node));
6784 OrigAllocAndCloneToNode[{
Node->getOrigNode(),
Node->Call.cloneNo()}] =
6789 for (
auto &[Source, Calls] : GetUnassignedCallClones(Node)) {
6790 auto AT = GetAllocTypeToUse(Source);
6791 for (
auto &
Call : Calls) {
6792 updateAllocationCall(
Call, AT);
6795 OrigAllocAndCloneToNode[{
Node->getOrigNode(),
Call.cloneNo()}] =
6802 auto CalleeFuncIt = CallsiteToCalleeFuncCloneMap.
find(Node);
6803 if (CalleeFuncIt != CallsiteToCalleeFuncCloneMap.
end()) {
6804 auto &CalleeFunc = CalleeFuncIt->second;
6805 updateCall(
Node->Call, CalleeFunc);
6807 OrigNodeAndCloneToCalleeClone[{
6808 Node->getOrigNode(),
Node->Call.cloneNo()}] = CalleeFunc.cloneNo();
6810 for (
auto &
Call :
Node->MatchingCalls)
6811 updateCall(
Call, CalleeFunc);
6817 for (
auto &[Source, Calls] : GetUnassignedCallClones(Node)) {
6818 auto It = CallsiteToCalleeFuncCloneMap.
find(Source);
6820 if (It == CallsiteToCalleeFuncCloneMap.
end())
6822 if (It == CallsiteToCalleeFuncCloneMap.
end())
6824 for (
auto &
Call : Calls) {
6825 updateCall(
Call, It->second);
6827 OrigNodeAndCloneToCalleeClone[{
Node->getOrigNode(),
Call.cloneNo()}] =
6828 It->second.cloneNo();
6838 DenseSet<const ContextNode *> Visited;
6839 for (
auto &Entry : AllocationCallToContextNodeMap)
6840 UpdateCalls(
Entry.second, Visited, UpdateCalls);
6862 for (
auto [Index, SN] :
enumerate(FS->callsites())) {
6867 SN.Clones.size() >
I &&
6868 "Callsite summary has fewer entries than other summaries in function");
6869 if (SN.Clones.size() <=
I || !SN.Clones[
I])
6871 AddRecord(
'c', Index, SN.Clones[
I]);
6874 for (
auto [Index, AN] :
enumerate(FS->allocs())) {
6878 assert(AN.Versions.size() >
I &&
6879 "Alloc summary has fewer entries than other summaries in function");
6880 if (AN.Versions.size() <=
I ||
6883 AddRecord(
'a', Index, AN.Versions[
I]);
6892 for (
auto &SN : FS->callsites()) {
6893 assert(SN.Clones.size() >
I && SN.Clones.size() > J &&
6894 "Callsite summary has fewer entries than other summaries in "
6896 if (SN.Clones[
I] != SN.Clones[J])
6899 for (
auto &AN : FS->allocs()) {
6900 assert(AN.Versions.size() >
I && AN.Versions.size() > J &&
6901 "Alloc summary has fewer entries than other summaries in function");
6902 if (AN.Versions[
I] != AN.Versions[J])
6918 NewGV->takeName(DeclGV);
6925 auto CloneFuncAliases = [&](
Function *NewF,
unsigned I) {
6926 if (!FuncToAliasMap.count(&
F))
6928 for (
auto *
A : FuncToAliasMap[&
F]) {
6930 auto *PrevA = M.getNamedAlias(AliasName);
6932 A->getType()->getPointerAddressSpace(),
6933 A->getLinkage(), AliasName, NewF);
6934 NewA->copyAttributesFrom(
A);
6936 TakeDeclNameAndReplace(PrevA, NewA);
6945 FunctionsClonedThinBackend++;
6962 for (
unsigned I = 1;
I < NumClones;
I++) {
6963 VMaps.
emplace_back(std::make_unique<ValueToValueMapTy>());
6969 if (
auto It = HashToFunc.
find(Hash); It != HashToFunc.
end()) {
6970 FunctionCloneDuplicatesThinBackend++;
6971 auto [Func, OrigI] = It->second;
6973 "Duplicate clone hash collision");
6974 if (Func->hasAvailableExternallyLinkage()) {
6980 auto Decl = M.getOrInsertFunction(Name, Func->getFunctionType());
6982 <<
"created clone decl " <<
ore::NV(
"Decl", Decl.getCallee()));
6985 auto *PrevF = M.getFunction(Name);
6988 TakeDeclNameAndReplace(PrevF, Alias);
6990 <<
"created clone alias " <<
ore::NV(
"Alias", Alias));
6993 CloneFuncAliases(Func,
I);
6997 HashToFunc[Hash] = {NewF,
I};
6998 FunctionClonesThinBackend++;
7000 NewF->
setMetadata(LLVMContext::MD_kcfi_type,
nullptr);
7003 for (
auto &BB : *NewF) {
7004 for (
auto &Inst : BB) {
7005 Inst.setMetadata(LLVMContext::MD_memprof,
nullptr);
7006 Inst.setMetadata(LLVMContext::MD_callsite,
nullptr);
7009 auto *PrevF = M.getFunction(Name);
7011 TakeDeclNameAndReplace(PrevF, NewF);
7013 NewF->setName(Name);
7016 <<
"created clone " <<
ore::NV(
"NewFunction", NewF));
7019 CloneFuncAliases(NewF,
I);
7028static std::optional<GlobalValue::GUID>
7030 if (
auto *MD =
F.getMetadata(
"thinlto_alias_guid"))
7032 return std::nullopt;
7039 const Function *CallingFunc =
nullptr) {
7043 assert(AliasVI &&
"Expected ValueInfo for imported alias GUID");
7066 MDNode *SrcFileMD = GO ? GO->getMetadata(
"thinlto_src_file") :
nullptr;
7076 SrcFileMD = CallingFunc->getMetadata(
"thinlto_src_file");
7083 StringRef SrcFile = M.getSourceFileName();
7120 &OrigNameGUIDToTailCallCallsite,
7124 auto End = MapTailCallCalleeVIToCallsite.
end();
7128 auto It = MapTailCallCalleeVIToCallsite.
find(VI);
7137 auto It = MapTailCallCalleeVIToCallsite.
find(LocalVI);
7147 if (!OrigNameGUIDToTailCallCallsite) {
7150 OrigNameGUIDToTailCallCallsite.emplace();
7151 for (
const auto &[CalleeVI, Callsite] : MapTailCallCalleeVIToCallsite) {
7160 AliasVIToGV.emplace();
7166 AliasVIToGV->try_emplace(VI, &
A);
7169 Callee = AliasVIToGV->lookup(CalleeVI);
7175 auto [It, Inserted] = OrigNameGUIDToTailCallCallsite->try_emplace(
7179 if (!Inserted && It->second != &Callsite)
7180 It->second =
nullptr;
7183 return OrigNameGUIDToTailCallCallsite->lookup(CandidateGUID);
7186bool MemProfContextDisambiguation::initializeIndirectCallPromotionInfo(
7188 ICallAnalysis = std::make_unique<ICallPromotionAnalysis>();
7189 Symtab = std::make_unique<InstrProfSymtab>();
7207 AliaseeGUIDToImportedAlias.reset();
7208 if (
Error E = Symtab->create(M,
true,
false,
7210 std::string SymtabFailure =
toString(std::move(
E));
7211 M.getContext().emitError(
"Failed to create symtab: " + SymtabFailure);
7224 auto MIBIter = AllocNode.
MIBs.begin();
7225 for (
auto &MDOp : MemProfMD->
operands()) {
7234 if (MIBIter->StackIdIndices.empty()) {
7238 auto StackIdIndexIter = MIBIter->StackIdIndices.begin();
7243 auto ContextIterBegin =
7247 (ContextIterBegin != StackContext.
end() && *ContextIterBegin == 0) ? 1
7249 for (
auto ContextIter = ContextIterBegin; ContextIter != StackContext.
end();
7254 if (LastStackContextId == *ContextIter)
7256 LastStackContextId = *ContextIter;
7257 assert(StackIdIndexIter != MIBIter->StackIdIndices.end());
7267bool MemProfContextDisambiguation::applyImport(
Module &M) {
7274 std::map<const Function *, SmallPtrSet<const GlobalAlias *, 1>>
7276 for (
auto &
A :
M.aliases()) {
7277 auto *Aliasee =
A.getAliaseeObject();
7279 FuncToAliasMap[
F].insert(&
A);
7282 if (!initializeIndirectCallPromotionInfo(M))
7288 std::optional<DenseMap<ValueInfo, const GlobalAlias *>> AliasVIToGV;
7294 OptimizationRemarkEmitter ORE(&
F);
7297 bool ClonesCreated =
false;
7298 unsigned NumClonesCreated = 0;
7299 auto CloneFuncIfNeeded = [&](
unsigned NumClones, FunctionSummary *
FS) {
7309 if (ClonesCreated) {
7310 assert(NumClonesCreated == NumClones);
7317 ClonesCreated =
true;
7318 NumClonesCreated = NumClones;
7321 auto CloneCallsite = [&](
const CallsiteInfo &StackNode, CallBase *CB,
7322 Function *CalledFunction, FunctionSummary *
FS) {
7324 CloneFuncIfNeeded(StackNode.
Clones.
size(), FS);
7336 if (CalledFunction != CB->getCalledOperand() &&
7337 (!GA || CalledFunction != GA->getAliaseeObject())) {
7338 SkippedCallsCloning++;
7344 auto CalleeOrigName = CalledFunction->getName();
7345 for (
unsigned J = 0; J < StackNode.
Clones.
size(); J++) {
7348 if (J > 0 && VMaps[J - 1]->
empty())
7352 if (!StackNode.
Clones[J])
7354 auto NewF =
M.getOrInsertFunction(
7356 CalledFunction->getFunctionType());
7370 ORE.emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofCall", CBClone)
7371 <<
ore::NV(
"Call", CBClone) <<
" in clone "
7373 <<
" assigned to call function clone "
7374 <<
ore::NV(
"Callee", NewF.getCallee()));
7388 ImportSummary->findSummaryInModule(TheFnVI,
M.getModuleIdentifier());
7392 auto SrcModuleMD =
F.getMetadata(
"thinlto_src_module");
7394 "enable-import-metadata is needed to emit thinlto_src_module");
7395 StringRef SrcModule =
7398 if (GVS->modulePath() == SrcModule) {
7399 GVSummary = GVS.get();
7403 assert(GVSummary && GVSummary->modulePath() == SrcModule);
7413 if (
FS->allocs().empty() &&
FS->callsites().empty())
7416 auto SI =
FS->callsites().begin();
7417 auto AI =
FS->allocs().begin();
7422 DenseMap<ValueInfo, CallsiteInfo> MapTailCallCalleeVIToCallsite;
7425 for (
auto CallsiteIt =
FS->callsites().rbegin();
7426 CallsiteIt !=
FS->callsites().rend(); CallsiteIt++) {
7427 auto &Callsite = *CallsiteIt;
7431 if (!Callsite.StackIdIndices.empty())
7433 MapTailCallCalleeVIToCallsite.
insert({Callsite.Callee, Callsite});
7437 std::optional<DenseMap<uint64_t, const CallsiteInfo *>>
7438 OrigNameGUIDToTailCallCallsite;
7446 for (
auto &BB :
F) {
7447 for (
auto &
I : BB) {
7453 auto *CalledValue = CB->getCalledOperand();
7454 auto *CalledFunction = CB->getCalledFunction();
7455 if (CalledValue && !CalledFunction) {
7456 CalledValue = CalledValue->stripPointerCasts();
7463 assert(!CalledFunction &&
7464 "Expected null called function in callsite for alias");
7468 CallStack<MDNode, MDNode::op_iterator> CallsiteContext(
7469 I.getMetadata(LLVMContext::MD_callsite));
7470 auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof);
7476 if (CB->getAttributes().hasFnAttr(
"memprof") && !MemProfMD) {
7477 CB->getAttributes().getFnAttr(
"memprof").getValueAsString() ==
"cold"
7478 ? AllocTypeColdThinBackend++
7479 : AllocTypeNotColdThinBackend++;
7480 OrigAllocsThinBackend++;
7481 AllocVersionsThinBackend++;
7482 if (!MaxAllocVersionsThinBackend)
7483 MaxAllocVersionsThinBackend = 1;
7490 auto &AllocNode = *(AI++);
7498 CloneFuncIfNeeded(AllocNode.Versions.size(), FS);
7500 OrigAllocsThinBackend++;
7501 AllocVersionsThinBackend += AllocNode.Versions.size();
7502 if (MaxAllocVersionsThinBackend < AllocNode.Versions.size())
7503 MaxAllocVersionsThinBackend = AllocNode.Versions.size();
7515 if (AllocNode.Versions.size() == 1 &&
7517 UnclonableAllocsThinBackend++;
7520 for (
unsigned J = 0; J < AllocNode.Versions.size(); J++) {
7523 if (J > 0 && VMaps[J - 1]->
empty())
7526 if (AllocNode.Versions[J] == (uint8_t)AllocationType::None)
7534 AllocTy = AllocationType::NotCold;
7536 if (AllocTy == AllocationType::Cold)
7537 AllocTypeColdThinBackend++;
7538 else if (IsAmbiguous)
7539 AllocTypeAmbiguousThinBackend++;
7541 AllocTypeNotColdThinBackend++;
7561 ORE.emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofAttribute", CBClone)
7562 <<
ore::NV(
"AllocationCall", CBClone) <<
" in clone "
7564 <<
" marked with memprof allocation attribute "
7565 <<
ore::NV(
"Attribute", AllocTypeString));
7567 }
else if (!CallsiteContext.empty()) {
7568 if (!CalledFunction) {
7572 assert(!CI || !CI->isInlineAsm());
7582 auto NumClones = recordICPInfo(
7584 [&](
const InstrProfValueData &Candidate) {
7585 assert(SI !=
FS->callsites().end());
7587 auto CalleeValueInfo =
7588 ImportSummary->getValueInfo(Candidate.Value);
7590 ImportSummary->getGUIDFromOriginalID(Candidate.Value);
7598 assert(!CalleeValueInfo ||
SI->Callee == CalleeValueInfo ||
7599 (
SI->Callee &&
SI->Callee.getGUID() == LocalGUID));
7608 CloneFuncIfNeeded(NumClones, FS);
7613 assert(SI !=
FS->callsites().end());
7614 auto &StackNode = *(
SI++);
7620 for (
auto StackId : CallsiteContext) {
7622 assert(ImportSummary->getStackIdAtIndex(*StackIdIndexIter) ==
7628 CloneCallsite(StackNode, CB, CalledFunction, FS);
7630 }
else if (CB->isTailCall() && CalledFunction) {
7635 if (CalleeVI && MapTailCallCalleeVIToCallsite.
count(CalleeVI)) {
7636 auto Callsite = MapTailCallCalleeVIToCallsite.
find(CalleeVI);
7637 assert(Callsite != MapTailCallCalleeVIToCallsite.
end());
7638 CloneCallsite(Callsite->second, CB, CalledFunction, FS);
7640 }
else if (CB->isTailCall() && !CalledFunction &&
7641 !MapTailCallCalleeVIToCallsite.
empty()) {
7647 auto PrevNumICallAnalysisInfo = ICallAnalysisInfo.
size();
7648 auto NumClones = recordICPInfo(
7650 [&](
const InstrProfValueData &Candidate) {
7652 Candidate.Value, MapTailCallCalleeVIToCallsite,
7653 OrigNameGUIDToTailCallCallsite, AliasVIToGV, M,
7654 ImportSummary, *Symtab);
7657 if (ICallAnalysisInfo.
size() > PrevNumICallAnalysisInfo)
7658 IndirectTailCallsRecordedForICPThinBackend++;
7660 CloneFuncIfNeeded(NumClones, FS);
7666 performICP(M, VMaps, ICallAnalysisInfo, ORE);
7676 for (
auto &BB :
F) {
7677 for (
auto &
I : BB) {
7680 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
7681 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
7689unsigned MemProfContextDisambiguation::recordICPInfo(
7691 function_ref<
const CallsiteInfo *(
const InstrProfValueData &)> GetCallsite,
7694 uint32_t NumCandidates;
7696 auto CandidateProfileData =
7697 ICallAnalysis->getPromotionCandidatesForInstruction(
7698 CB, TotalCount, NumCandidates,
7700 if (CandidateProfileData.empty())
7706 bool ICPNeeded =
false;
7707 unsigned NumClones = 0;
7709 for (
const auto &Candidate : CandidateProfileData) {
7710 const CallsiteInfo *Callsite = GetCallsite(Candidate);
7718 [](
unsigned CloneNo) { return CloneNo != 0; });
7728 ICallAnalysisInfo.
push_back({CB, CandidateProfileData.vec(), NumCandidates,
7729 TotalCount, NumClones, std::move(Callsites)});
7733void MemProfContextDisambiguation::performICP(
7736 OptimizationRemarkEmitter &ORE) {
7743 for (
auto &Info : ICallAnalysisInfo) {
7745 auto TotalCount =
Info.TotalCount;
7746 unsigned NumClones =
Info.NumClones;
7749 assert(
Info.CandidateProfileData.size() ==
Info.Callsites.size());
7750 for (
unsigned I = 0;
I <
Info.CandidateProfileData.size();
I++) {
7751 auto &Candidate =
Info.CandidateProfileData[
I];
7752 const CallsiteInfo *StackNode =
Info.Callsites[
I];
7760 Function *TargetFunction = Symtab->getFunction(Candidate.Value);
7771 if (!TargetFunction && StackNode && StackNode->
Callee &&
7782 if (!TargetFunction) {
7783 if (!AliaseeGUIDToImportedAlias) {
7784 AliaseeGUIDToImportedAlias.emplace();
7788 if (
auto AliaseeGUID = Fn.getGUIDIfAssigned())
7789 AliaseeGUIDToImportedAlias->try_emplace(*AliaseeGUID, &Fn);
7792 TargetFunction = AliaseeGUIDToImportedAlias->lookup(Candidate.Value);
7793 if (!TargetFunction && StackNode && StackNode->
Callee &&
7796 AliaseeGUIDToImportedAlias->lookup(StackNode->
Callee.
getGUID());
7798 if (TargetFunction ==
nullptr ||
7806 return OptimizationRemarkMissed(
DEBUG_TYPE,
"UnableToFindTarget", CB)
7807 <<
"Memprof cannot promote indirect call: target with md5sum "
7808 <<
ore::NV(
"target md5sum", Candidate.Value) <<
" not found";
7813 RemainingCandidates.
push_back(Candidate);
7818 const char *Reason =
nullptr;
7821 return OptimizationRemarkMissed(
DEBUG_TYPE,
"UnableToPromote", CB)
7822 <<
"Memprof cannot promote indirect call to "
7823 <<
ore::NV(
"TargetFunction", TargetFunction)
7824 <<
" with count of " <<
ore::NV(
"TotalCount", TotalCount)
7827 RemainingCandidates.
push_back(Candidate);
7836 CallBase *CBClone = CB;
7837 for (
unsigned J = 0; J < NumClones; J++) {
7840 if (J > 0 && VMaps[J - 1]->
empty())
7850 TotalCount, isSamplePGO, &ORE);
7851 auto *TargetToUse = TargetFunction;
7854 if (StackNode && StackNode->
Clones[J]) {
7873 <<
ore::NV(
"Call", CBClone) <<
" in clone "
7875 <<
" promoted and assigned to call function clone "
7876 <<
ore::NV(
"Callee", TargetToUse));
7880 TotalCount -= Candidate.Count;
7884 CallBase *CBClone = CB;
7885 for (
unsigned J = 0; J < NumClones; J++) {
7888 if (J > 0 && VMaps[J - 1]->
empty())
7894 CBClone->
setMetadata(LLVMContext::MD_prof,
nullptr);
7897 if (TotalCount != 0)
7899 IPVK_IndirectCallTarget,
Info.NumCandidates);
7904template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
7905bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::process(
7906 function_ref<
void(StringRef, StringRef,
const Twine &)> EmitRemark,
7907 bool AllowExtraAnalysis) {
7909 dbgs() <<
"CCG before cloning:\n";
7913 exportToDot(
"postbuild");
7922 capturePreCloningContextInfo();
7931 dbgs() <<
"CCG after cloning:\n";
7935 exportToDot(
"cloned");
7937 bool Changed = assignFunctions();
7940 dbgs() <<
"CCG after assigning function clones:\n";
7944 exportToDot(
"clonefuncassign");
7953 populateFunctionsWithCallers();
7954 printTotalSizes(
errs(), EmitRemark);
7960bool MemProfContextDisambiguation::processModule(
7962 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter) {
7967 return applyImport(M);
7980 ModuleCallsiteContextGraph CCG(M, OREGetter);
7983 return CCG.process();
7988 : ImportSummary(Summary), isSamplePGO(isSamplePGO) {
7993 "-memprof-dot-scope=alloc requires -memprof-dot-alloc-id");
7997 "-memprof-dot-scope=context requires -memprof-dot-context-id");
8001 "-memprof-dot-scope=all can't have both -memprof-dot-alloc-id and "
8002 "-memprof-dot-context-id");
8003 if (ImportSummary) {
8013 auto ReadSummaryFile =
8015 if (!ReadSummaryFile) {
8022 if (!ImportSummaryForTestingOrErr) {
8028 ImportSummaryForTesting = std::move(*ImportSummaryForTestingOrErr);
8029 ImportSummary = ImportSummaryForTesting.get();
8038 if (!processModule(M, OREGetter))
8061 for (
auto &
I : Index) {
8062 auto VI = Index.getValueInfo(
I);
8063 for (
auto &S : VI.getSummaryList()) {
8067 !isPrevailing(VI.getGUID(), S.get()))
8070 if (!FS || FS->callsites().empty())
8072 CalleeToEdge.
clear();
8073 for (
auto &CI : FS->callsites()) {
8074 if (!CI.Callee ||
llvm::all_of(CI.Clones, [](
unsigned CloneNo) {
8075 return CloneNo == 0;
8082 NumClonedCalleeCallsites++;
8084 if (CalleeToEdge.
empty())
8085 for (
auto &[CalleeVI, Edge] : FS->mutableCalls())
8086 CalleeToEdge[CalleeVI] = &Edge;
8087 auto It = CalleeToEdge.
find(CI.Callee);
8088 if (It == CalleeToEdge.
end())
8095 if (!Edge->hasIndirectCall())
8097 NumClonedCalleeIndirectCallsites++;
8098 if (!Edge->requiresDeclImport()) {
8099 Edge->setRequiresDeclImport(
true);
8100 NumClonedCalleeEdgesMarkedRequiresDeclImport++;
8121 bool AllowExtraAnalysis =
8126 IndexCallsiteContextGraph CCG(Index, isPrevailing);
8127 Changed = CCG.process(EmitRemark, AllowExtraAnalysis);
8150 for (
auto &BB :
F) {
8151 for (
auto &
I : BB) {
8155 if (CI->hasFnAttr(
"memprof")) {
8156 CI->removeFnAttr(
"memprof");
8159 if (!CI->hasMetadata(LLVMContext::MD_callsite)) {
8160 assert(!CI->hasMetadata(LLVMContext::MD_memprof));
8166 CI->setMetadata(LLVMContext::MD_memprof,
nullptr);
8167 CI->setMetadata(LLVMContext::MD_callsite,
nullptr);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
Unify divergent function exit nodes
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
Module.h This file contains the declarations for the Module class.
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
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."))
uint64_t ComputeHash(const FunctionSummary *FS, unsigned I)
static cl::opt< DotScope > DotGraphScope("memprof-dot-scope", cl::desc("Scope of graph to export to dot"), cl::Hidden, cl::init(DotScope::All), cl::values(clEnumValN(DotScope::All, "all", "Export full callsite graph"), clEnumValN(DotScope::Alloc, "alloc", "Export only nodes with contexts feeding given " "-memprof-dot-alloc-id"), clEnumValN(DotScope::Context, "context", "Export only nodes with given -memprof-dot-context-id")))
static cl::opt< bool > DoMergeIteration("memprof-merge-iteration", cl::init(true), cl::Hidden, cl::desc("Iteratively apply merging on a node to catch new callers"))
static cl::opt< unsigned > AllocIdForDot("memprof-dot-alloc-id", cl::init(0), cl::Hidden, cl::desc("Id of alloc to export if -memprof-dot-scope=alloc " "or to highlight if -memprof-dot-scope=all"))
static bool clonesHaveSameVersions(const FunctionSummary *FS, unsigned I, unsigned J)
static std::optional< GlobalValue::GUID > getImportedAliasGUID(const Function &F)
static void updateClonedCalleeEdgesForImport(ModuleSummaryIndex &Index, llvm::function_ref< bool(GlobalValue::GUID, const GlobalValueSummary *)> isPrevailing)
static cl::opt< unsigned > ContextIdForDot("memprof-dot-context-id", cl::init(0), cl::Hidden, cl::desc("Id of context to export if -memprof-dot-scope=context or to " "highlight otherwise"))
static cl::opt< bool > ExportToDot("memprof-export-to-dot", cl::init(false), cl::Hidden, cl::desc("Export graph to dot files."))
static ValueInfo findValueInfoForGV(const GlobalValue &GV, const Module &M, const ModuleSummaryIndex *ImportSummary, const Function *CallingFunc=nullptr)
static void checkEdge(const std::shared_ptr< ContextEdge< DerivedCCG, FuncTy, CallTy > > &Edge)
static cl::opt< bool > AllowRecursiveCallsites("memprof-allow-recursive-callsites", cl::init(true), cl::Hidden, cl::desc("Allow cloning of callsites involved in recursive cycles"))
bool checkColdOrNotCold(uint8_t AllocType)
static cl::opt< bool > CloneRecursiveContexts("memprof-clone-recursive-contexts", cl::init(true), cl::Hidden, cl::desc("Allow cloning of contexts through recursive cycles"))
static std::string getAllocTypeString(uint8_t AllocTypes)
static cl::opt< bool > IndirectTailCallSearch("memprof-indirect-tail-call-search", cl::init(true), cl::Hidden, cl::desc("Search for missing frames through indirect tail calls to their " "profiled targets (ThinLTO)."))
bool DOTGraphTraits< constCallsiteContextGraph< DerivedCCG, FuncTy, CallTy > * >::DoHighlight
static cl::opt< bool > AssignTrimmedInlinedContexts("memprof-assign-trimmed-inlined-contexts", cl::init(true), cl::Hidden, cl::desc("Assign contexts trimmed within a call's inlined stack id " "sequence to that call"))
static unsigned getMemProfCloneNum(const Function &F)
static cl::opt< unsigned > MemProfICPNoInlineThreshold("memprof-icp-noinline-threshold", cl::init(0), cl::Hidden, cl::desc("Minimum absolute count for promoted target to be inlinable"))
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, FunctionSummary *FS)
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 cl::opt< bool > MergeClones("memprof-merge-clones", cl::init(true), cl::Hidden, cl::desc("Merge clones before assigning functions"))
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 CallsiteInfo * findIndirectTailCallCallsite(uint64_t CandidateGUID, const DenseMap< ValueInfo, CallsiteInfo > &MapTailCallCalleeVIToCallsite, std::optional< DenseMap< uint64_t, const CallsiteInfo * > > &OrigNameGUIDToTailCallCallsite, std::optional< DenseMap< ValueInfo, const GlobalAlias * > > &AliasVIToGV, const Module &M, const ModuleSummaryIndex *ImportSummary, InstrProfSymtab &Symtab)
static void updateSubprogramLinkageName(Function *NewFunc, StringRef Name)
static cl::opt< bool > AllowRecursiveContexts("memprof-allow-recursive-contexts", cl::init(true), cl::Hidden, cl::desc("Allow cloning of contexts having recursive cycles"))
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 void checkAllocContextIds(const AllocInfo &AllocNode, const MDNode *MemProfMD, const CallStack< MDNode, MDNode::op_iterator > &CallsiteContext, const ModuleSummaryIndex *ImportSummary)
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...
if(auto Err=PB.parsePassPipeline(MPM, Passes)) return wrap(std MPM run * Mod
FunctionAnalysisManager FAM
std::pair< BasicBlock *, BasicBlock * > Edge
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)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
ValueInfo getAliaseeVI() const
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
Get the array size.
ArrayRef< T > drop_back(size_t N=1) const
Drop the last N elements of the array.
bool empty() const
Check if the array is empty.
static LLVM_ABI Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
void addFnAttr(Attribute::AttrKind Kind)
Adds the attribute to the function.
void setCalledOperand(Value *V)
Subprogram description. Uses SubclassData1.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
iterator find(const_arg_type_t< KeyT > Val)
ValueT & at(const_arg_type_t< KeyT > Val)
Return the entry for the specified key, or abort if no such entry exists.
void reserve(size_type NumEntries)
Grow the DenseMap so that it can contain at least NumEntries items before resizing again.
bool erase(const KeyT &Val)
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
Function summary information to aid decisions and implementation of importing.
FunctionType * getFunctionType() const
Returns the FunctionType for me.
DISubprogram * getSubprogram() const
Get the attached subprogram.
const Function & getFunction() const
static LLVM_ABI 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...
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set a particular kind of metadata attachment.
Function and variable summary information to aid decisions and implementation of importing.
static LLVM_ABI GUID getGUIDAssumingExternalLinkage(StringRef GlobalName)
Return a 64-bit global unique ID constructed from the name of a global symbol.
static bool isLocalLinkage(LinkageTypes Linkage)
LLVM_ABI bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
uint64_t GUID
Declare a type to represent a global unique identifier for a global value.
bool hasLocalLinkage() const
Module * getParent()
Get the module that this global value is contained inside of...
LLVM_ABI void eraseFromParent()
This method unlinks 'this' from the containing module and deletes it.
LLVM_ABI GUID getGUID() const
Return a 64-bit global unique ID for this value.
static LLVM_ABI std::string getGlobalIdentifier(StringRef Name, GlobalValue::LinkageTypes Linkage, StringRef FileName)
Return the modified name for a global value suitable to be used as the key for a global lookup (e....
bool isWeakForLinker() const
@ InternalLinkage
Rename collisions when linking (static functions).
A symbol table used for function [IR]PGO name look-up with keys (such as pointers,...
Function * getFunction(uint64_t FuncMD5Hash) const
Return function from the name's md5 hash. Return nullptr if not found.
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
This is an important class for using LLVM in a threaded context.
const MDOperand & getOperand(unsigned I) const
ArrayRef< MDOperand > operands() const
unsigned getNumOperands() const
Return number of MDNode operands.
LLVM_ABI TempMDNode clone() const
Create a (temporary) clone of this.
static std::enable_if_t< std::is_base_of< MDNode, T >::value, T * > replaceWithUniqued(std::unique_ptr< T, TempMDNodeDeleter > N)
Replace a temporary node with a uniqued one.
static LLVM_ABI MDString * get(LLVMContext &Context, StringRef Str)
This class implements a map that also provides access to all stored values in a deterministic order.
size_type count(const KeyT &Key) const
LLVM_ABI MemProfContextDisambiguation(const ModuleSummaryIndex *Summary=nullptr, bool isSamplePGO=false)
LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
LLVM_ABI 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
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.
LLVMContext & getContext() const
Get the global data context.
A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...
A discriminated union of two or more pointer types, with the discriminator in the low bits of the poi...
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.
A class that wrap the SHA1 algorithm.
LLVM_ABI void update(ArrayRef< uint8_t > Data)
Digest more data.
LLVM_ABI std::array< uint8_t, 20 > result()
Return the current raw 160-bits SHA1 for the digested data since the last call to init().
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void push_back(const T &Elt)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Represent a constant reference to a string, i.e.
bool contains(StringRef Other) const
Return true if the given string is a substring of *this, and false otherwise.
std::pair< StringRef, StringRef > rsplit(StringRef Separator) const
Split into two substrings around the last occurrence of a separator string.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
LLVM_ABI void print(raw_ostream &O, bool IsForDebug=false) const
Implement operator<< on Value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const ValueT &V)
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
bool erase(const ValueT &V)
void insert_range(Range &&R)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
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 beginAfterSharedPrefix(const CallStack &Other)
CallStackIterator end() const
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ CE
Windows NT (Windows on ARM)
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
initializer< Ty > init(const Ty &Val)
std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > dyn_extract(Y &&MD)
Extract a Value from Metadata, if any.
std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > extract(Y &&MD)
Extract a Value from Metadata.
LLVM_ABI AllocationType getMIBAllocType(const MDNode *MIB)
Returns the allocation type from an MIB metadata node.
LLVM_ABI bool metadataMayIncludeContextSizeInfo()
Whether the alloc memprof metadata may include context size info for some MIBs (but possibly not all)...
LLVM_ABI bool hasSingleAllocType(uint8_t AllocTypes)
True if the AllocTypes bitmask contains just a single type.
LLVM_ABI bool isAmbiguousAllocType(uint8_t AllocTypes)
True if the AllocTypes bitmask contains both NotCold and Cold, i.e.
LLVM_ABI std::string getAllocTypeAttributeString(AllocationType Type)
Returns the string to use in attributes with the given type.
LLVM_ABI MDNode * getMIBStackNode(const MDNode *MIB)
Returns the stack node from an MIB metadata node.
LLVM_ABI void removeAnyExistingAmbiguousAttribute(CallBase *CB)
Removes any existing "ambiguous" memprof attribute.
LLVM_ABI void addAmbiguousAttribute(CallBase *CB)
Adds an "ambiguous" memprof attribute to call with a matched allocation profile but that we haven't y...
DiagnosticInfoOptimizationBase::Argument NV
LLVM_ABI CallBase & promoteIndirectCall(CallBase &CB, Function *F, uint64_t Count, uint64_t TotalCount, bool AttachProfToDirectCall, OptimizationRemarkEmitter *ORE)
NodeAddr< NodeBase * > Node
NodeAddr< FuncNode * > Func
friend class Instruction
Iterator for Instructions in a `BasicBlock.
uint64_t read64le(const void *P)
void write32le(void *P, uint32_t V)
This is an optimization pass for GlobalISel generic memory operations.
cl::opt< unsigned > MinClonedColdBytePercent("memprof-cloning-cold-threshold", cl::init(100), cl::Hidden, cl::desc("Min percent of cold bytes to hint alloc cold during cloning"))
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
LLVM_ABI void logAllUnhandledErrors(Error E, raw_ostream &OS, Twine ErrorBanner={})
Log all errors (if any) in E to OS.
void stable_sort(R &&Range)
cl::opt< bool > MemProfReportHintedSizes("memprof-report-hinted-sizes", cl::init(false), cl::Hidden, cl::desc("Report total allocation sizes of hinted allocations"))
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool isLegalToPromote(const CallBase &CB, Function *Callee, const char **FailureReason=nullptr)
Return true if the given indirect call site can be made to call Callee.
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
cl::opt< bool > MemProfUseAmbiguousAttributes
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool mayHaveMemprofSummary(const CallBase *CB)
Returns true if the instruction could have memprof metadata, used to ensure consistency between summa...
constexpr from_range_t from_range
static cl::opt< bool > MemProfRequireDefinitionForPromotion("memprof-require-definition-for-promotion", cl::init(false), cl::Hidden, cl::desc("Require target function definition when promoting indirect calls"))
auto dyn_cast_if_present(const Y &Val)
dyn_cast_if_present<X> - Functionally identical to dyn_cast, except that a null (or none in the case ...
cl::opt< unsigned > MemProfTopNImportant("memprof-top-n-important", cl::init(10), cl::Hidden, cl::desc("Number of largest cold contexts to consider important"))
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
static cl::opt< bool > MemProfImportClonedIndirectTargets("memprof-import-cloned-indirect-targets", cl::init(true), cl::Hidden, cl::desc("Import at least a declaration of the indirect call targets of " "callsites assigned to call a cloned callee (needed for MemProf " "ICP in the ThinLTO backend)"))
void set_subtract(S1Ty &S1, const S2Ty &S2)
set_subtract(A, B) - Compute A := A - B
InnerAnalysisManagerProxy< FunctionAnalysisManager, Module > FunctionAnalysisManagerModuleProxy
Provide the FunctionAnalysisManager to Module proxy.
raw_ostream & WriteGraph(raw_ostream &O, const GraphType &G, bool ShortNames=false, const Twine &Title="")
bool isa_and_nonnull(const Y &Val)
bool set_intersects(const S1Ty &S1, const S2Ty &S2)
set_intersects(A, B) - Return true iff A ^ B is non empty
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&...Ranges)
Returns a concatenated range across two or more ranges.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
LLVM_ABI Expected< std::unique_ptr< ModuleSummaryIndex > > getModuleSummaryIndex(MemoryBufferRef Buffer)
Parse the specified bitcode buffer, returning the module summary index.
auto dyn_cast_or_null(const Y &Val)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI void annotateValueSite(Module &M, Instruction &Inst, const InstrProfRecord &InstrProfR, InstrProfValueKind ValueKind, uint32_t SiteIndx, uint32_t MaxMDCount=3)
Get the value profile data for value site SiteIdx from InstrProfR and annotate the instruction Inst w...
static cl::opt< bool > MemProfReportHintedSizesDetail("memprof-report-hinted-sizes-detail", cl::init(false), cl::Hidden, cl::desc("Append post-cloning call path and matching details to each " "-memprof-report-hinted-sizes line"))
LLVM_ABI 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.
LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)
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.
static cl::opt< unsigned > MemProfReportHintedSizesDetailMaxPathLen("memprof-report-hinted-sizes-detail-max-path-len", cl::init(7), cl::Hidden, cl::desc("Maximum number of functions printed in full for a post-cloning " "call path in the -memprof-report-hinted-sizes-detail suffix; " "longer paths are elided in the middle"))
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
S1Ty set_intersection(const S1Ty &S1, const S2Ty &S2)
set_intersection(A, B) - Return A ^ B
LLVM_ABI raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
LLVM_ABI unsigned getMaxSummaryIndirectEdges(const LLVMContext &C)
Return -module-summary-max-indirect-edges.
cl::opt< bool > EnableMemProfContextDisambiguation
Enable MemProf context disambiguation for thin link.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
S1Ty set_difference(const S1Ty &S1, const S2Ty &S2)
set_difference(A, B) - Return A - B
bool isMemProfClone(const GlobalValue &GV)
Returns true if GV is a MemProf context-disambiguated clone.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Expected< T > errorOrToExpected(ErrorOr< T > &&EO)
Convert an ErrorOr<T> to an Expected<T>.
ArrayRef(const T &OneElt) -> ArrayRef< T >
std::string toString(const APInt &I, unsigned Radix, bool Signed, bool formatAsCLiteral=false, bool UpperCase=true, bool InsertSeparators=false)
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Next
constexpr StringLiteral MemProfCloneSuffix
@ End
Run the machine verifier once, at the end of the pipeline.
LLVM_ABI Function * CloneFunction(Function *F, ValueToValueMapTy &VMap, ClonedCodeInfo *CodeInfo=nullptr)
Return a copy of the specified function and add it to that function's module.
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
cl::opt< bool > MemProfFixupImportant("memprof-fixup-important", cl::init(true), cl::Hidden, cl::desc("Enables edge fixup for important contexts"))
DOTGraphTraits(bool IsSimple=false)
typename GTraits::NodeRef NodeRef
static std::string getEdgeAttributes(NodeRef, ChildIteratorType ChildIter, GraphType G)
const CallsiteContextGraph< DerivedCCG, FuncTy, CallTy > * GraphType
typename GTraits::ChildIteratorType ChildIteratorType
static std::string getNodeAttributes(NodeRef Node, GraphType G)
static bool isNodeHidden(NodeRef Node, GraphType G)
static std::string getNodeLabel(NodeRef Node, GraphType G)
GraphTraits< GraphType > GTraits
static NodeRef getNode(const NodePtrTy &P)
static const ContextNode< DerivedCCG, FuncTy, CallTy > * GetCallee(const EdgePtrTy &P)
static ChildIteratorType child_end(NodeRef N)
std::unique_ptr< ContextNode< DerivedCCG, FuncTy, CallTy > > NodePtrTy
mapped_iterator< typename std::vector< std::shared_ptr< ContextEdge< DerivedCCG, FuncTy, CallTy > > >::const_iterator, decltype(&GetCallee)> ChildIteratorType
const CallsiteContextGraph< DerivedCCG, FuncTy, CallTy > * GraphType
const ContextNode< DerivedCCG, FuncTy, CallTy > * NodeRef
mapped_iterator< typename std::vector< NodePtrTy >::const_iterator, decltype(&getNode)> nodes_iterator
static ChildIteratorType child_begin(NodeRef N)
static NodeRef getEntryNode(GraphType G)
static nodes_iterator nodes_begin(GraphType G)
static nodes_iterator nodes_end(GraphType G)
std::shared_ptr< ContextEdge< DerivedCCG, FuncTy, CallTy > > EdgePtrTy
Summary of memprof metadata on allocations.
std::vector< MIBInfo > MIBs
Class to accumulate and hold information about a callee.
Summary of memprof callsite metadata.
SmallVector< unsigned > StackIdIndices
SmallVector< unsigned > Clones
DefaultDOTGraphTraits(bool simple=false)
An information struct used to provide DenseMap with the various necessary components for a given valu...
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
PointerUnion< CallsiteInfo *, AllocInfo * > SimpleType
static SimpleType getSimplifiedValue(IndexCall &Val)
const PointerUnion< CallsiteInfo *, AllocInfo * > SimpleType
static SimpleType getSimplifiedValue(const IndexCall &Val)
Define a template that can be specialized by smart pointers to reflect the fact that they are automat...