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)");
150 cl::desc(
"Specify the path prefix of the MemProf dot files."));
154 cl::desc(
"Export graph to dot files."));
159 cl::desc(
"Iteratively apply merging on a node to catch new callers"));
169 "memprof-dot-scope",
cl::desc(
"Scope of graph to export to dot"),
174 "Export only nodes with contexts feeding given "
175 "-memprof-dot-alloc-id"),
177 "Export only nodes with given -memprof-dot-context-id")));
181 cl::desc(
"Id of alloc to export if -memprof-dot-scope=alloc "
182 "or to highlight if -memprof-dot-scope=all"));
186 cl::desc(
"Id of context to export if -memprof-dot-scope=context or to "
187 "highlight otherwise"));
191 cl::desc(
"Dump CallingContextGraph to stdout after each stage."));
195 cl::desc(
"Perform verification checks on CallingContextGraph."));
199 cl::desc(
"Perform frequent verification checks on nodes."));
202 "memprof-import-summary",
203 cl::desc(
"Import summary to use for testing the ThinLTO backend via opt"),
209 cl::desc(
"Max depth to recursively search for missing "
210 "frames through tail calls."));
217 cl::desc(
"Search for missing frames through indirect tail calls to their "
218 "profiled targets (ThinLTO)."));
223 cl::desc(
"Allow cloning of callsites involved in recursive cycles"));
227 cl::desc(
"Allow cloning of contexts through recursive cycles"));
234 cl::desc(
"Merge clones before assigning functions"));
243 cl::desc(
"Allow cloning of contexts having recursive cycles"));
249 cl::desc(
"Minimum absolute count for promoted target to be inlinable"));
253 "enable-memprof-context-disambiguation",
cl::Hidden,
254 cl::desc(
"Enable MemProf context disambiguation"));
260 cl::desc(
"Linking with hot/cold operator new interfaces"));
265 "Require target function definition when promoting indirect calls"));
288 cl::desc(
"Import at least a declaration of the indirect call targets of "
289 "callsites assigned to call a cloned callee (needed for MemProf "
290 "ICP in the ThinLTO backend)"));
303 cl::desc(
"Append post-cloning call path and matching details to each "
304 "-memprof-report-hinted-sizes line"));
311 cl::desc(
"Maximum number of functions printed in full for a post-cloning "
312 "call path in the -memprof-report-hinted-sizes-detail suffix; "
313 "longer paths are elided in the middle"));
317 cl::desc(
"Number of largest cold contexts to consider important"));
321 cl::desc(
"Enables edge fixup for important contexts"));
341template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
342class CallsiteContextGraph {
344 CallsiteContextGraph() =
default;
345 CallsiteContextGraph(
const CallsiteContextGraph &) =
default;
346 CallsiteContextGraph(CallsiteContextGraph &&) =
default;
350 EmitRemark =
nullptr,
351 bool AllowExtraAnalysis =
false);
355 void identifyClones();
362 bool assignFunctions();
368 EmitRemark =
nullptr)
const;
371 const CallsiteContextGraph &CCG) {
376 friend struct GraphTraits<
377 const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *>;
378 friend struct DOTGraphTraits<
379 const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *>;
381 void exportToDot(std::string Label)
const;
384 struct FuncInfo final
385 :
public std::pair<FuncTy *, unsigned > {
386 using Base = std::pair<FuncTy *, unsigned>;
387 FuncInfo(
const Base &
B) : Base(
B) {}
388 FuncInfo(FuncTy *
F =
nullptr,
unsigned CloneNo = 0) : Base(
F, CloneNo) {}
389 explicit operator bool()
const {
return this->first !=
nullptr; }
390 FuncTy *func()
const {
return this->first; }
391 unsigned cloneNo()
const {
return this->second; }
395 struct CallInfo final :
public std::pair<CallTy, unsigned > {
396 using Base = std::pair<CallTy, unsigned>;
397 CallInfo(
const Base &
B) : Base(
B) {}
398 CallInfo(CallTy
Call =
nullptr,
unsigned CloneNo = 0)
399 : Base(
Call, CloneNo) {}
400 explicit operator bool()
const {
return (
bool)this->first; }
401 CallTy call()
const {
return this->first; }
402 unsigned cloneNo()
const {
return this->second; }
403 void setCloneNo(
unsigned N) { this->second =
N; }
404 void print(raw_ostream &OS)
const {
405 if (!
operator bool()) {
411 OS <<
"\t(clone " << cloneNo() <<
")";
417 friend raw_ostream &
operator<<(raw_ostream &OS,
const CallInfo &
Call) {
437 bool Recursive =
false;
441 uint8_t AllocTypes = 0;
464 std::vector<std::shared_ptr<ContextEdge>> CalleeEdges;
468 std::vector<std::shared_ptr<ContextEdge>> CallerEdges;
472 bool useCallerEdgesForContextInfo()
const {
477 assert(!CalleeEdges.empty() || CallerEdges.empty() || IsAllocation ||
489 DenseSet<uint32_t> getContextIds()
const {
495 for (
auto &
Edge : CalleeEdges.empty() ? CallerEdges : CalleeEdges)
497 DenseSet<uint32_t> ContextIds;
500 CalleeEdges, useCallerEdgesForContextInfo()
502 : std::vector<std::shared_ptr<ContextEdge>>());
503 for (
const auto &
Edge : Edges)
510 uint8_t computeAllocType()
const {
512 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
513 uint8_t
AllocType = (uint8_t)AllocationType::None;
515 CalleeEdges, useCallerEdgesForContextInfo()
517 : std::vector<std::shared_ptr<ContextEdge>>());
518 for (
const auto &
Edge : Edges) {
529 bool emptyContextIds()
const {
531 CalleeEdges, useCallerEdgesForContextInfo()
533 : std::vector<std::shared_ptr<ContextEdge>>());
534 for (
const auto &
Edge : Edges) {
535 if (!
Edge->getContextIds().empty())
542 bool hasContextId(uint32_t Id)
const {
544 CalleeEdges, useCallerEdgesForContextInfo()
546 : std::vector<std::shared_ptr<ContextEdge>>());
547 for (
const auto &
Edge : Edges) {
548 if (
Edge->getContextIds().contains(Id))
555 std::vector<ContextNode *> Clones;
558 ContextNode *CloneOf =
nullptr;
560 ContextNode(
bool IsAllocation) : IsAllocation(IsAllocation), Call() {}
562 ContextNode(
bool IsAllocation, CallInfo
C)
563 : IsAllocation(IsAllocation), Call(
C) {}
565 void addClone(ContextNode *Clone) {
567 CloneOf->Clones.push_back(Clone);
568 Clone->CloneOf = CloneOf;
570 Clones.push_back(Clone);
572 Clone->CloneOf =
this;
576 ContextNode *getOrigNode() {
582 const ContextNode *getOrigNode()
const {
589 unsigned int ContextId);
591 ContextEdge *findEdgeFromCallee(
const ContextNode *Callee);
592 ContextEdge *findEdgeFromCaller(
const ContextNode *Caller);
593 void eraseCalleeEdge(
const ContextEdge *
Edge);
594 void eraseCallerEdge(
const ContextEdge *
Edge);
596 void setCall(CallInfo
C) { Call = std::move(
C); }
598 bool hasCall()
const {
return (
bool)Call.call(); }
600 void printCall(raw_ostream &OS)
const { Call.print(OS); }
604 bool isRemoved()
const {
610 (AllocTypes == (uint8_t)AllocationType::None) ==
612 return AllocTypes == (uint8_t)AllocationType::None;
616 void print(raw_ostream &OS)
const;
618 friend raw_ostream &
operator<<(raw_ostream &OS,
const ContextNode &Node) {
632 uint8_t AllocTypes = 0;
640 bool IsBackedge =
false;
643 DenseSet<uint32_t> ContextIds;
645 ContextEdge(ContextNode *Callee, ContextNode *Caller, uint8_t
AllocType,
646 DenseSet<uint32_t> ContextIds)
647 : Callee(Callee), Caller(Caller), AllocTypes(
AllocType),
648 ContextIds(std::
move(ContextIds)) {}
650 DenseSet<uint32_t> &getContextIds() {
return ContextIds; }
654 inline void clear() {
656 AllocTypes = (uint8_t)AllocationType::None;
664 inline bool isRemoved()
const {
665 if (Callee || Caller)
670 assert(AllocTypes == (uint8_t)AllocationType::None);
671 assert(ContextIds.empty());
676 void print(raw_ostream &OS)
const;
678 friend raw_ostream &
operator<<(raw_ostream &OS,
const ContextEdge &
Edge) {
686 void removeNoneTypeCalleeEdges(ContextNode *Node);
687 void removeNoneTypeCallerEdges(ContextNode *Node);
689 recursivelyRemoveNoneTypeCalleeEdges(ContextNode *Node,
690 DenseSet<const ContextNode *> &Visited);
695 template <
class NodeT,
class IteratorT>
696 std::vector<ContextNode *>
697 getStackNodesForCallsite(CallStack<NodeT, IteratorT> &CallsiteContext);
701 ContextNode *addAllocNode(CallInfo
Call,
const FuncTy *
F);
704 template <
class NodeT,
class IteratorT>
705 void addStackNodesForMIB(
706 ContextNode *AllocNode, CallStack<NodeT, IteratorT> &StackContext,
709 std::map<uint64_t, uint32_t> &TotalSizeToContextIdTopNCold);
714 void updateStackNodes();
723 void fixupImportantContexts();
727 void handleCallsitesWithMultipleTargets();
730 void markBackedges();
740 bool partitionCallsByCallee(
742 std::vector<std::pair<CallInfo, ContextNode *>> &NewCallToNode);
746 MapVector<FuncTy *, std::vector<CallInfo>> FuncToCallsWithMetadata;
749 std::map<const ContextNode *, const FuncTy *> NodeToCallingFunc;
751 const FuncTy *getCallingFunc(
const ContextNode *
N)
const {
752 auto It = NodeToCallingFunc.find(
N);
753 return It != NodeToCallingFunc.end() ? It->second :
nullptr;
761 DenseSet<const FuncTy *> FunctionsWithCallers;
765 DenseSet<uint32_t> DotAllocContextIds;
768 using EdgeIter =
typename std::vector<std::shared_ptr<ContextEdge>>::iterator;
773 struct CallContextInfo {
781 std::vector<ContextNode *> StackNodes;
786 DenseSet<uint32_t> ContextIds;
795 void removeEdgeFromGraph(ContextEdge *
Edge, EdgeIter *EI =
nullptr,
796 bool CalleeIter =
true);
804 void assignStackNodesPostOrder(
805 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
806 DenseMap<
uint64_t, std::vector<CallContextInfo>> &StackIdToMatchingCalls,
807 DenseMap<CallInfo, CallInfo> &CallToMatchingCall,
808 const DenseSet<uint32_t> &ImportantContextIds);
813 DenseSet<uint32_t> duplicateContextIds(
814 const DenseSet<uint32_t> &StackSequenceContextIds,
815 DenseMap<uint32_t, DenseSet<uint32_t>> &OldToNewContextIds);
818 void propagateDuplicateContextIds(
819 const DenseMap<uint32_t, DenseSet<uint32_t>> &OldToNewContextIds);
824 void connectNewNode(ContextNode *NewNode, ContextNode *OrigNode,
825 bool TowardsCallee,
const DenseSet<uint32_t> &ContextIds);
831 return static_cast<const DerivedCCG *
>(
this)->getStackId(IdOrIndex);
841 calleesMatch(CallTy
Call, EdgeIter &EI,
842 MapVector<CallInfo, ContextNode *> &TailCallToContextNodeMap);
846 const FuncTy *getCalleeFunc(CallTy
Call) {
847 return static_cast<DerivedCCG *
>(
this)->getCalleeFunc(
Call);
853 bool calleeMatchesFunc(
854 CallTy
Call,
const FuncTy *Func,
const FuncTy *CallerFunc,
855 std::vector<std::pair<CallTy, FuncTy *>> &FoundCalleeChain) {
856 return static_cast<DerivedCCG *
>(
this)->calleeMatchesFunc(
857 Call, Func, CallerFunc, FoundCalleeChain);
861 bool sameCallee(CallTy Call1, CallTy Call2) {
862 return static_cast<DerivedCCG *
>(
this)->sameCallee(Call1, Call2);
867 std::vector<ContextNode *> getStackNodesForCall(CallTy
Call) {
868 return static_cast<DerivedCCG *
>(
this)->getStackNodesForCall(
Call);
873 return static_cast<DerivedCCG *
>(
this)->getLastStackId(
Call);
881 AllocTypeAmbiguous++;
884 static_cast<DerivedCCG *
>(
this)->updateAllocationCall(
Call,
AllocType);
889 return static_cast<const DerivedCCG *
>(
this)->getAllocationCallType(
Call);
894 void updateCall(CallInfo &CallerCall, FuncInfo CalleeFunc) {
895 static_cast<DerivedCCG *
>(
this)->updateCall(CallerCall, CalleeFunc);
901 FuncInfo cloneFunctionForCallsite(
902 FuncInfo &Func, CallInfo &
Call, DenseMap<CallInfo, CallInfo> &CallMap,
903 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
904 return static_cast<DerivedCCG *
>(
this)->cloneFunctionForCallsite(
905 Func,
Call, CallMap, CallsWithMetadataInFunc, CloneNo);
910 std::string getLabel(
const FuncTy *Func,
const CallTy
Call,
911 unsigned CloneNo)
const {
912 return static_cast<const DerivedCCG *
>(
this)->getLabel(Func,
Call, CloneNo);
916 std::string getFuncName(
const FuncTy *Func,
unsigned CloneNo = 0)
const {
917 return static_cast<const DerivedCCG *
>(
this)->getFuncName(Func, CloneNo);
922 bool isFuncDead(
const FuncTy *Func)
const {
923 return static_cast<const DerivedCCG *
>(
this)->isFuncDead(Func);
927 void populateFunctionsWithCallers() {
928 static_cast<DerivedCCG *
>(
this)->populateFunctionsWithCallers();
933 void capturePreCloningContextInfo();
938 std::string formatContextReportSuffix(
const ContextNode *Node,
942 ContextNode *createNewNode(
bool IsAllocation,
const FuncTy *
F =
nullptr,
943 CallInfo
C = CallInfo()) {
944 NodeOwner.push_back(std::make_unique<ContextNode>(IsAllocation,
C));
945 auto *NewNode = NodeOwner.back().get();
947 NodeToCallingFunc[NewNode] =
F;
948 NewNode->NodeId = NodeOwner.size();
953 ContextNode *getNodeForInst(
const CallInfo &
C);
954 ContextNode *getNodeForAlloc(
const CallInfo &
C);
955 ContextNode *getNodeForStackId(
uint64_t StackId);
959 uint8_t computeAllocType(DenseSet<uint32_t> &ContextIds)
const;
964 uint8_t intersectAllocTypesImpl(
const DenseSet<uint32_t> &Node1Ids,
965 const DenseSet<uint32_t> &Node2Ids)
const;
969 uint8_t intersectAllocTypes(
const DenseSet<uint32_t> &Node1Ids,
970 const DenseSet<uint32_t> &Node2Ids)
const;
977 moveEdgeToNewCalleeClone(
const std::shared_ptr<ContextEdge> &
Edge,
978 DenseSet<uint32_t> ContextIdsToMove = {});
984 void moveEdgeToExistingCalleeClone(
const std::shared_ptr<ContextEdge> &
Edge,
985 ContextNode *NewCallee,
986 bool NewClone =
false,
987 DenseSet<uint32_t> ContextIdsToMove = {});
994 void moveCalleeEdgeToNewCaller(
const std::shared_ptr<ContextEdge> &
Edge,
995 ContextNode *NewCaller);
998 void markBackedges(ContextNode *Node, DenseSet<const ContextNode *> &Visited,
999 DenseSet<const ContextNode *> &CurrentStack);
1003 mergeClones(ContextNode *Node, DenseSet<const ContextNode *> &Visited,
1004 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode);
1006 void mergeNodeCalleeClones(
1007 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
1008 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode);
1011 void findOtherCallersToShareMerge(
1012 ContextNode *Node, std::vector<std::shared_ptr<ContextEdge>> &CalleeEdges,
1013 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode,
1014 DenseSet<ContextNode *> &OtherCallersToShareMerge);
1020 void identifyClones(ContextNode *Node, DenseSet<const ContextNode *> &Visited,
1021 const DenseSet<uint32_t> &AllocContextIds);
1026 struct ImplicitSource {
1028 const ContextNode *Source;
1036 using ImplicitSourceMap =
1037 DenseMap<std::pair<const ContextNode *, unsigned>, ImplicitSource>;
1044 void assignImplicitCallers(
1045 ContextNode *Node,
const DenseSet<uint32_t> &TrimmedContextIds,
1046 DenseMap<ContextNode *, FuncInfo> &CallsiteToCalleeFuncCloneMap,
1047 const std::map<FuncInfo, ContextNode *> &FuncCloneToCurNodeCloneMap,
1048 ImplicitSourceMap &ImplicitSources);
1054 static const ContextNode *resolveImplicitSource(
const ContextNode *Node,
1055 const ImplicitSource &Src);
1058 DenseMap<uint32_t, AllocationType> ContextIdToAllocationType;
1064 DenseMap<uint32_t, std::vector<ContextTotalSize>> ContextIdToContextSizeInfos;
1070 DenseMap<uint64_t, ContextNode *> StackEntryIdToContextNodeMap;
1074 struct ImportantContextInfo {
1076 std::vector<uint64_t> StackIds;
1079 unsigned MaxLength = 0;
1083 std::map<std::vector<uint64_t>, ContextNode *> StackIdsToNode;
1087 DenseMap<uint32_t, ImportantContextInfo> ImportantContextIdInfo;
1096 const DenseSet<uint32_t> &NodeContextIds,
1097 const DenseSet<uint32_t> &ImportantContextIds) {
1102 DenseSet<uint32_t> Ids =
1106 std::vector<uint64_t> StackIds;
1107 StackIds.reserve(StackNodes.
size());
1108 for (
const ContextNode *
N : StackNodes)
1109 StackIds.push_back(
N->OrigStackOrAllocId);
1110 auto Size = StackIds.size();
1111 for (
auto Id : Ids) {
1112 auto &
Entry = ImportantContextIdInfo[
Id];
1121 MapVector<CallInfo, ContextNode *> AllocationCallToContextNodeMap;
1122 MapVector<CallInfo, ContextNode *> NonAllocationCallToContextNodeMap;
1125 std::vector<std::unique_ptr<ContextNode>> NodeOwner;
1131 unsigned int LastContextId = 0;
1139 struct PreCloningContextInfo {
1143 std::vector<const ContextNode *> Chain;
1153 unsigned MaxMatchedFrame = 0;
1156 bool OutermostMatchedNodeHasOtherCallers =
false;
1161 bool StoppedAtRecursive =
false;
1162 bool StoppedAtMismatchedCallee =
false;
1165 const FuncTy *UnmatchedCallingFunc =
nullptr;
1168 DenseMap<uint32_t, PreCloningContextInfo> PreCloningContextInfoMap;
1171 DenseSet<const ContextNode *> PreCloningAllocHasMatchedCaller;
1174 DenseMap<const FuncTy *, unsigned> FuncToNumClones;
1179 DenseMap<std::pair<const ContextNode *, unsigned>,
unsigned>
1180 OrigNodeAndCloneToCalleeClone;
1184 DenseMap<std::pair<const ContextNode *, unsigned>,
const ContextNode *>
1185 OrigAllocAndCloneToNode;
1188template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1190 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode;
1191template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1193 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge;
1194template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1196 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::FuncInfo;
1197template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1199 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::CallInfo;
1202class ModuleCallsiteContextGraph
1203 :
public CallsiteContextGraph<ModuleCallsiteContextGraph, Function,
1206 ModuleCallsiteContextGraph(
1208 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter);
1211 friend CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
1216 bool calleeMatchesFunc(
1218 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain);
1219 bool sameCallee(Instruction *Call1, Instruction *Call2);
1220 bool findProfiledCalleeThroughTailCalls(
1222 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain,
1223 bool &FoundMultipleCalleeChains);
1225 std::vector<ContextNode *> getStackNodesForCall(Instruction *
Call);
1228 void updateCall(CallInfo &CallerCall, FuncInfo CalleeFunc);
1229 CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
1231 cloneFunctionForCallsite(FuncInfo &Func, CallInfo &
Call,
1232 DenseMap<CallInfo, CallInfo> &CallMap,
1233 std::vector<CallInfo> &CallsWithMetadataInFunc,
1235 std::string getLabel(
const Function *Func,
const Instruction *
Call,
1236 unsigned CloneNo)
const;
1237 std::string getFuncName(
const Function *Func,
unsigned CloneNo = 0)
const;
1238 bool isFuncDead(
const Function *Func)
const {
return false; }
1239 void populateFunctionsWithCallers();
1242 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter;
1248struct IndexCall :
public PointerUnion<CallsiteInfo *, AllocInfo *> {
1249 IndexCall() : PointerUnion() {}
1250 IndexCall(std::nullptr_t) : IndexCall() {}
1251 IndexCall(CallsiteInfo *StackNode) : PointerUnion(StackNode) {}
1252 IndexCall(AllocInfo *AllocNode) : PointerUnion(AllocNode) {}
1253 IndexCall(PointerUnion PT) : PointerUnion(PT) {}
1255 IndexCall *operator->() {
return this; }
1257 void print(raw_ostream &OS)
const {
1258 PointerUnion<CallsiteInfo *, AllocInfo *>
Base = *
this;
1283class IndexCallsiteContextGraph
1284 :
public CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
1287 IndexCallsiteContextGraph(
1288 ModuleSummaryIndex &Index,
1292 ~IndexCallsiteContextGraph() {
1297 for (
auto &
I : FunctionCalleesToSynthesizedCallsiteInfos) {
1299 for (
auto &Callsite :
I.second)
1300 FS->addCallsite(std::move(*Callsite.second));
1305 friend CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
1309 const FunctionSummary *getCalleeFunc(IndexCall &
Call);
1310 bool calleeMatchesFunc(
1311 IndexCall &
Call,
const FunctionSummary *Func,
1312 const FunctionSummary *CallerFunc,
1313 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain);
1314 bool sameCallee(IndexCall &Call1, IndexCall &Call2);
1315 bool findProfiledCalleeThroughTailCalls(
1316 ValueInfo ProfiledCallee, ValueInfo CurCallee,
unsigned Depth,
1317 std::vector<std::pair<ValueInfo, FunctionSummary *>> &FoundCalleeChain,
1318 bool &FoundMultipleCalleeChains);
1320 std::vector<ContextNode *> getStackNodesForCall(IndexCall &
Call);
1323 void updateCall(CallInfo &CallerCall, FuncInfo CalleeFunc);
1324 CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
1325 IndexCall>::FuncInfo
1326 cloneFunctionForCallsite(FuncInfo &Func, CallInfo &
Call,
1327 DenseMap<CallInfo, CallInfo> &CallMap,
1328 std::vector<CallInfo> &CallsWithMetadataInFunc,
1330 std::string getLabel(
const FunctionSummary *Func,
const IndexCall &
Call,
1331 unsigned CloneNo)
const;
1332 std::string getFuncName(
const FunctionSummary *Func,
1333 unsigned CloneNo = 0)
const;
1334 bool isFuncDead(
const FunctionSummary *Func)
const;
1335 void populateFunctionsWithCallers();
1336 DenseSet<GlobalValue::GUID> findAliaseeGUIDsPrevailingInDifferentModule();
1340 std::map<const FunctionSummary *, ValueInfo> FSToVIMap;
1342 const ModuleSummaryIndex &Index;
1350 DenseMap<FunctionSummary *,
1351 std::map<ValueInfo, std::unique_ptr<CallsiteInfo>>>
1352 FunctionCalleesToSynthesizedCallsiteInfos;
1363 :
public DenseMapInfo<std::pair<IndexCall, unsigned>> {};
1366 :
public DenseMapInfo<PointerUnion<CallsiteInfo *, AllocInfo *>> {};
1387template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1388bool allocTypesMatch(
1389 const std::vector<uint8_t> &InAllocTypes,
1390 const std::vector<std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>>>
1394 assert(InAllocTypes.size() == Edges.size());
1396 InAllocTypes.begin(), InAllocTypes.end(), Edges.begin(), Edges.end(),
1398 const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &r) {
1402 if (l == (uint8_t)AllocationType::None ||
1403 r->AllocTypes == (uint8_t)AllocationType::None)
1405 return allocTypeToUse(l) == allocTypeToUse(r->AllocTypes);
1414template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1415bool allocTypesMatchClone(
1416 const std::vector<uint8_t> &InAllocTypes,
1417 const ContextNode<DerivedCCG, FuncTy, CallTy> *Clone) {
1418 const ContextNode<DerivedCCG, FuncTy, CallTy> *
Node = Clone->CloneOf;
1422 assert(InAllocTypes.size() ==
Node->CalleeEdges.size());
1426 for (
const auto &
E : Clone->CalleeEdges) {
1428 EdgeCalleeMap[
E->Callee] =
E->AllocTypes;
1432 for (
unsigned I = 0;
I <
Node->CalleeEdges.size();
I++) {
1433 auto Iter = EdgeCalleeMap.
find(
Node->CalleeEdges[
I]->Callee);
1435 if (Iter == EdgeCalleeMap.
end())
1443 if (allocTypeToUse(Iter->second) != allocTypeToUse(InAllocTypes[
I]))
1451template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1452typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1453CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForInst(
1454 const CallInfo &
C) {
1455 ContextNode *
Node = getNodeForAlloc(
C);
1459 return NonAllocationCallToContextNodeMap.lookup(
C);
1462template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1463typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1464CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForAlloc(
1465 const CallInfo &
C) {
1466 return AllocationCallToContextNodeMap.lookup(
C);
1469template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1470typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1471CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForStackId(
1473 auto StackEntryNode = StackEntryIdToContextNodeMap.
find(StackId);
1474 if (StackEntryNode != StackEntryIdToContextNodeMap.
end())
1475 return StackEntryNode->second;
1479template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1480void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1482 unsigned int ContextId) {
1483 for (
auto &
Edge : CallerEdges) {
1484 if (
Edge->Caller == Caller) {
1486 Edge->getContextIds().insert(ContextId);
1490 std::shared_ptr<ContextEdge>
Edge = std::make_shared<ContextEdge>(
1491 this, Caller, (uint8_t)
AllocType, DenseSet<uint32_t>({ContextId}));
1492 CallerEdges.push_back(
Edge);
1496template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1497void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::removeEdgeFromGraph(
1498 ContextEdge *
Edge, EdgeIter *EI,
bool CalleeIter) {
1514 auto CalleeCallerCount =
Callee->CallerEdges.size();
1515 auto CallerCalleeCount =
Caller->CalleeEdges.size();
1520 }
else if (CalleeIter) {
1522 *EI =
Caller->CalleeEdges.erase(*EI);
1525 *EI =
Callee->CallerEdges.erase(*EI);
1527 assert(
Callee->CallerEdges.size() < CalleeCallerCount);
1528 assert(
Caller->CalleeEdges.size() < CallerCalleeCount);
1531template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1532void CallsiteContextGraph<
1533 DerivedCCG, FuncTy, CallTy>::removeNoneTypeCalleeEdges(ContextNode *Node) {
1534 for (
auto EI =
Node->CalleeEdges.begin(); EI !=
Node->CalleeEdges.end();) {
1536 if (
Edge->AllocTypes == (uint8_t)AllocationType::None) {
1538 removeEdgeFromGraph(
Edge.get(), &EI,
true);
1544template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1545void CallsiteContextGraph<
1546 DerivedCCG, FuncTy, CallTy>::removeNoneTypeCallerEdges(ContextNode *Node) {
1547 for (
auto EI =
Node->CallerEdges.begin(); EI !=
Node->CallerEdges.end();) {
1549 if (
Edge->AllocTypes == (uint8_t)AllocationType::None) {
1551 Edge->Caller->eraseCalleeEdge(
Edge.get());
1552 EI =
Node->CallerEdges.erase(EI);
1558template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1559typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge *
1560CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1561 findEdgeFromCallee(
const ContextNode *Callee) {
1562 for (
const auto &
Edge : CalleeEdges)
1563 if (
Edge->Callee == Callee)
1568template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1569typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge *
1570CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1571 findEdgeFromCaller(
const ContextNode *Caller) {
1572 for (
const auto &
Edge : CallerEdges)
1573 if (
Edge->Caller == Caller)
1578template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1579void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1580 eraseCalleeEdge(
const ContextEdge *
Edge) {
1582 CalleeEdges, [
Edge](
const std::shared_ptr<ContextEdge> &CalleeEdge) {
1583 return CalleeEdge.get() ==
Edge;
1585 assert(EI != CalleeEdges.end());
1586 CalleeEdges.erase(EI);
1589template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1590void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1591 eraseCallerEdge(
const ContextEdge *
Edge) {
1593 CallerEdges, [
Edge](
const std::shared_ptr<ContextEdge> &CallerEdge) {
1594 return CallerEdge.get() ==
Edge;
1596 assert(EI != CallerEdges.end());
1597 CallerEdges.erase(EI);
1600template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1601uint8_t CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::computeAllocType(
1602 DenseSet<uint32_t> &ContextIds)
const {
1604 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
1605 uint8_t
AllocType = (uint8_t)AllocationType::None;
1606 for (
auto Id : ContextIds) {
1607 AllocType |= (uint8_t)ContextIdToAllocationType.
at(Id);
1615template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1617CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::intersectAllocTypesImpl(
1618 const DenseSet<uint32_t> &Node1Ids,
1619 const DenseSet<uint32_t> &Node2Ids)
const {
1621 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
1622 uint8_t
AllocType = (uint8_t)AllocationType::None;
1623 for (
auto Id : Node1Ids) {
1624 if (!Node2Ids.
count(Id))
1626 AllocType |= (uint8_t)ContextIdToAllocationType.
at(Id);
1634template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1635uint8_t CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::intersectAllocTypes(
1636 const DenseSet<uint32_t> &Node1Ids,
1637 const DenseSet<uint32_t> &Node2Ids)
const {
1638 if (Node1Ids.
size() < Node2Ids.
size())
1639 return intersectAllocTypesImpl(Node1Ids, Node2Ids);
1641 return intersectAllocTypesImpl(Node2Ids, Node1Ids);
1644template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1645typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1646CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::addAllocNode(
1647 CallInfo
Call,
const FuncTy *
F) {
1649 ContextNode *AllocNode = createNewNode(
true,
F,
Call);
1650 AllocationCallToContextNodeMap[
Call] = AllocNode;
1652 AllocNode->OrigStackOrAllocId = LastContextId;
1655 AllocNode->AllocTypes = (uint8_t)AllocationType::None;
1671template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1672template <
class NodeT,
class IteratorT>
1673void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::addStackNodesForMIB(
1674 ContextNode *AllocNode, CallStack<NodeT, IteratorT> &StackContext,
1677 std::map<uint64_t, uint32_t> &TotalSizeToContextIdTopNCold) {
1683 ContextIdToAllocationType[++LastContextId] =
AllocType;
1685 bool IsImportant =
false;
1686 if (!ContextSizeInfo.
empty()) {
1687 auto &
Entry = ContextIdToContextSizeInfos[LastContextId];
1692 for (
auto &CSI : ContextSizeInfo)
1693 TotalCold += CSI.TotalSize;
1699 TotalCold > TotalSizeToContextIdTopNCold.begin()->first) {
1702 auto IdToRemove = TotalSizeToContextIdTopNCold.begin()->second;
1703 TotalSizeToContextIdTopNCold.erase(
1704 TotalSizeToContextIdTopNCold.begin());
1706 ImportantContextIdInfo.
erase(IdToRemove);
1708 TotalSizeToContextIdTopNCold[TotalCold] = LastContextId;
1712 Entry.insert(
Entry.begin(), ContextSizeInfo.begin(), ContextSizeInfo.end());
1716 AllocNode->AllocTypes |= (uint8_t)
AllocType;
1721 ContextNode *PrevNode = AllocNode;
1725 SmallSet<uint64_t, 8> StackIdSet;
1728 ContextIter != StackContext.
end(); ++ContextIter) {
1729 auto StackId = getStackId(*ContextIter);
1731 ImportantContextIdInfo[LastContextId].StackIds.push_back(StackId);
1732 ContextNode *StackNode = getNodeForStackId(StackId);
1734 StackNode = createNewNode(
false);
1735 StackEntryIdToContextNodeMap[StackId] = StackNode;
1736 StackNode->OrigStackOrAllocId = StackId;
1741 auto Ins = StackIdSet.
insert(StackId);
1743 StackNode->Recursive =
true;
1745 StackNode->AllocTypes |= (uint8_t)
AllocType;
1746 PrevNode->addOrUpdateCallerEdge(StackNode,
AllocType, LastContextId);
1747 PrevNode = StackNode;
1751template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1753CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::duplicateContextIds(
1754 const DenseSet<uint32_t> &StackSequenceContextIds,
1755 DenseMap<uint32_t, DenseSet<uint32_t>> &OldToNewContextIds) {
1756 DenseSet<uint32_t> NewContextIds;
1757 for (
auto OldId : StackSequenceContextIds) {
1758 NewContextIds.
insert(++LastContextId);
1759 OldToNewContextIds[OldId].insert(LastContextId);
1762 ContextIdToAllocationType[LastContextId] = ContextIdToAllocationType[OldId];
1763 auto CSI = ContextIdToContextSizeInfos.
find(OldId);
1764 if (CSI != ContextIdToContextSizeInfos.
end())
1765 ContextIdToContextSizeInfos[LastContextId] = CSI->second;
1766 if (DotAllocContextIds.
contains(OldId))
1767 DotAllocContextIds.
insert(LastContextId);
1769 return NewContextIds;
1772template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1773void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
1774 propagateDuplicateContextIds(
1775 const DenseMap<uint32_t, DenseSet<uint32_t>> &OldToNewContextIds) {
1777 auto GetNewIds = [&OldToNewContextIds](
const DenseSet<uint32_t> &ContextIds) {
1778 DenseSet<uint32_t> NewIds;
1779 for (
auto Id : ContextIds)
1780 if (
auto NewId = OldToNewContextIds.find(Id);
1781 NewId != OldToNewContextIds.end())
1787 auto UpdateCallers = [&](ContextNode *
Node,
1788 DenseSet<const ContextEdge *> &Visited,
1789 auto &&UpdateCallers) ->
void {
1790 for (
const auto &
Edge :
Node->CallerEdges) {
1794 ContextNode *NextNode =
Edge->Caller;
1795 DenseSet<uint32_t> NewIdsToAdd = GetNewIds(
Edge->getContextIds());
1798 if (!NewIdsToAdd.
empty()) {
1799 Edge->getContextIds().insert_range(NewIdsToAdd);
1800 UpdateCallers(NextNode, Visited, UpdateCallers);
1805 DenseSet<const ContextEdge *> Visited;
1806 for (
auto &Entry : AllocationCallToContextNodeMap) {
1808 UpdateCallers(Node, Visited, UpdateCallers);
1812template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1813void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::connectNewNode(
1814 ContextNode *NewNode, ContextNode *OrigNode,
bool TowardsCallee,
1815 const DenseSet<uint32_t> &ContextIds) {
1817 TowardsCallee ? OrigNode->CalleeEdges : OrigNode->CallerEdges;
1819 for (
auto EI = OrigEdges.begin(); EI != OrigEdges.end();) {
1821 DenseSet<uint32_t> NewEdgeContextIds;
1826 if (NewEdgeContextIds.
empty()) {
1830 if (TowardsCallee) {
1831 uint8_t NewAllocType = computeAllocType(NewEdgeContextIds);
1832 auto NewEdge = std::make_shared<ContextEdge>(
1833 Edge->Callee, NewNode, NewAllocType, std::move(NewEdgeContextIds));
1834 NewNode->CalleeEdges.push_back(NewEdge);
1835 NewEdge->Callee->CallerEdges.push_back(NewEdge);
1837 uint8_t NewAllocType = computeAllocType(NewEdgeContextIds);
1838 auto NewEdge = std::make_shared<ContextEdge>(
1839 NewNode,
Edge->Caller, NewAllocType, std::move(NewEdgeContextIds));
1840 NewNode->CallerEdges.push_back(NewEdge);
1841 NewEdge->Caller->CalleeEdges.push_back(NewEdge);
1845 if (
Edge->getContextIds().empty()) {
1846 removeEdgeFromGraph(
Edge.get(), &EI, TowardsCallee);
1849 Edge->AllocTypes = computeAllocType(
Edge->getContextIds());
1854template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1856 const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &Edge) {
1860 assert(!Edge->ContextIds.empty());
1863template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1865 bool CheckEdges =
true) {
1866 if (
Node->isRemoved())
1870 auto NodeContextIds =
Node->getContextIds();
1874 if (
Node->CallerEdges.size()) {
1876 Node->CallerEdges.front()->ContextIds);
1880 set_union(CallerEdgeContextIds, Edge->ContextIds);
1887 NodeContextIds == CallerEdgeContextIds ||
1890 if (
Node->CalleeEdges.size()) {
1892 Node->CalleeEdges.front()->ContextIds);
1896 set_union(CalleeEdgeContextIds, Edge->getContextIds());
1902 NodeContextIds == CalleeEdgeContextIds);
1911 for (
const auto &
E :
Node->CalleeEdges)
1917template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1918void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
1919 assignStackNodesPostOrder(ContextNode *Node,
1920 DenseSet<const ContextNode *> &Visited,
1921 DenseMap<
uint64_t, std::vector<CallContextInfo>>
1922 &StackIdToMatchingCalls,
1923 DenseMap<CallInfo, CallInfo> &CallToMatchingCall,
1924 const DenseSet<uint32_t> &ImportantContextIds) {
1932 auto CallerEdges =
Node->CallerEdges;
1933 for (
auto &
Edge : CallerEdges) {
1935 if (
Edge->isRemoved()) {
1939 assignStackNodesPostOrder(
Edge->Caller, Visited, StackIdToMatchingCalls,
1940 CallToMatchingCall, ImportantContextIds);
1949 if (
Node->IsAllocation ||
1950 !StackIdToMatchingCalls.count(
Node->OrigStackOrAllocId))
1953 auto &Calls = StackIdToMatchingCalls[
Node->OrigStackOrAllocId];
1957 if (Calls.size() == 1) {
1958 auto &[
Call, StackNodes,
Func, SavedContextIds] = Calls[0];
1959 if (StackNodes.size() == 1) {
1960 assert(SavedContextIds.empty());
1962 assert(Node == StackNodes[0]);
1963 if (
Node->Recursive)
1966 NonAllocationCallToContextNodeMap[
Call] =
Node;
1968 recordStackNode(StackNodes, Node,
Node->getContextIds(),
1969 ImportantContextIds);
1978 ContextNode *LastNode = getNodeForStackId(LastId);
1981 assert(LastNode == Node);
1983 ContextNode *LastNode =
Node;
1988 DenseSet<uint32_t> LastNodeContextIds = LastNode->getContextIds();
1990 [[maybe_unused]]
bool PrevIterCreatedNode =
false;
1991 bool CreatedNode =
false;
1992 for (
unsigned I = 0;
I < Calls.size();
1993 I++, PrevIterCreatedNode = CreatedNode) {
1994 CreatedNode =
false;
1995 auto &[
Call, StackNodes,
Func, SavedContextIds] = Calls[
I];
1998 if (SavedContextIds.empty()) {
2005 auto MatchingCall = CallToMatchingCall[
Call];
2006 if (!NonAllocationCallToContextNodeMap.contains(MatchingCall)) {
2010 assert(
I > 0 && !PrevIterCreatedNode);
2013 NonAllocationCallToContextNodeMap[MatchingCall]->MatchingCalls.push_back(
2018 assert(LastNode == StackNodes.back());
2027 ContextNode *PrevNode = LastNode;
2031 for (
auto NodeIter = StackNodes.rbegin() + 1; NodeIter != StackNodes.rend();
2033 ContextNode *CurNode = *NodeIter;
2037 assert(!CurNode->Recursive);
2039 auto *
Edge = CurNode->findEdgeFromCaller(PrevNode);
2051 if (SavedContextIds.empty()) {
2060 ContextNode *NewNode = createNewNode(
false, Func,
Call);
2061 NonAllocationCallToContextNodeMap[
Call] = NewNode;
2063 NewNode->AllocTypes = computeAllocType(SavedContextIds);
2065 ContextNode *FirstNode = StackNodes[0];
2071 connectNewNode(NewNode, FirstNode,
true, SavedContextIds);
2076 connectNewNode(NewNode, LastNode,
false, SavedContextIds);
2081 for (ContextNode *CurNode : StackNodes) {
2088 auto *PrevEdge = CurNode->findEdgeFromCallee(PrevNode);
2095 set_subtract(PrevEdge->getContextIds(), SavedContextIds);
2096 if (PrevEdge->getContextIds().empty())
2097 removeEdgeFromGraph(PrevEdge);
2099 PrevEdge->AllocTypes = computeAllocType(PrevEdge->getContextIds());
2104 CurNode->AllocTypes = CurNode->CalleeEdges.empty()
2105 ? (uint8_t)AllocationType::None
2106 : CurNode->computeAllocType();
2110 recordStackNode(StackNodes, NewNode, SavedContextIds, ImportantContextIds);
2114 for (ContextNode *CurNode : StackNodes) {
2123template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2124void CallsiteContextGraph<DerivedCCG, FuncTy,
2125 CallTy>::fixupImportantContexts() {
2126 if (ImportantContextIdInfo.
empty())
2130 NumImportantContextIds = ImportantContextIdInfo.
size();
2136 exportToDot(
"beforestackfixup");
2161 for (
auto &[CurContextId, Info] : ImportantContextIdInfo) {
2162 if (
Info.StackIdsToNode.empty())
2165 ContextNode *PrevNode =
nullptr;
2166 ContextNode *CurNode =
nullptr;
2167 DenseSet<const ContextEdge *> VisitedEdges;
2168 ArrayRef<uint64_t> AllStackIds(
Info.StackIds);
2171 for (
unsigned I = 0;
I < AllStackIds.size();
I++, PrevNode = CurNode) {
2175 auto LenToEnd = AllStackIds.size() -
I;
2183 auto CheckStackIds = AllStackIds.slice(
I, Len);
2184 auto EntryIt =
Info.StackIdsToNode.find(CheckStackIds);
2185 if (EntryIt ==
Info.StackIdsToNode.end())
2187 CurNode = EntryIt->second;
2204 auto *CurEdge = PrevNode->findEdgeFromCaller(CurNode);
2207 if (CurEdge->getContextIds().insert(CurContextId).second) {
2208 NumFixupEdgeIdsInserted++;
2213 NumFixupEdgesAdded++;
2214 DenseSet<uint32_t> ContextIds({CurContextId});
2215 auto AllocType = computeAllocType(ContextIds);
2216 auto NewEdge = std::make_shared<ContextEdge>(
2217 PrevNode, CurNode,
AllocType, std::move(ContextIds));
2218 PrevNode->CallerEdges.push_back(NewEdge);
2219 CurNode->CalleeEdges.push_back(NewEdge);
2221 CurEdge = NewEdge.get();
2224 VisitedEdges.
insert(CurEdge);
2227 for (
auto &
Edge : PrevNode->CallerEdges) {
2231 Edge->getContextIds().erase(CurContextId);
2239template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2240void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::updateStackNodes() {
2248 DenseMap<uint64_t, std::vector<CallContextInfo>> StackIdToMatchingCalls;
2249 for (
auto &[Func, CallsWithMetadata] : FuncToCallsWithMetadata) {
2250 for (
auto &
Call : CallsWithMetadata) {
2252 if (AllocationCallToContextNodeMap.count(
Call))
2254 std::vector<ContextNode *> StackNodes = getStackNodesForCall(
Call.call());
2257 if (StackNodes.empty())
2261 uint64_t LastId = StackNodes.back()->OrigStackOrAllocId;
2262 StackIdToMatchingCalls[LastId].push_back(
2263 {
Call.call(), std::move(StackNodes),
Func, {}});
2273 DenseMap<uint32_t, DenseSet<uint32_t>> OldToNewContextIds;
2277 DenseMap<CallInfo, CallInfo> CallToMatchingCall;
2278 for (
auto &It : StackIdToMatchingCalls) {
2279 auto &Calls = It.getSecond();
2281 if (Calls.size() == 1) {
2282 auto &StackNodes = Calls[0].StackNodes;
2283 if (StackNodes.size() == 1)
2296 DenseMap<const FuncTy *, unsigned> FuncToIndex;
2297 for (
const auto &[Idx, CallCtxInfo] :
enumerate(Calls))
2298 FuncToIndex.
insert({CallCtxInfo.Func,
Idx});
2301 return std::lexicographical_compare(
2302 A.begin(),
A.end(),
B.begin(),
B.end(),
2303 [](
const ContextNode *
X,
const ContextNode *
Y) {
2304 return X->OrigStackOrAllocId < Y->OrigStackOrAllocId;
2307 auto CallLess = [&FuncToIndex, &StackIdsLess](
const CallContextInfo &
A,
2308 const CallContextInfo &
B) {
2309 return A.StackNodes.size() >
B.StackNodes.size() ||
2310 (
A.StackNodes.size() ==
B.StackNodes.size() &&
2311 (StackIdsLess(
A.StackNodes,
B.StackNodes) ||
2312 (
A.StackNodes ==
B.StackNodes &&
2313 FuncToIndex[
A.Func] < FuncToIndex[
B.Func])));
2322 ContextNode *LastNode = Calls[0].StackNodes.back();
2325 assert(LastNode == getNodeForStackId(LastId));
2327 if (LastNode->Recursive)
2332 DenseSet<uint32_t> LastNodeContextIds = LastNode->getContextIds();
2340 DenseSet<const FuncTy *> MatchingIdsFuncSet;
2343 for (
unsigned I = 0;
I < Calls.size();
I++) {
2344 auto &[
Call, StackNodes,
Func, SavedContextIds] = Calls[
I];
2345 assert(SavedContextIds.empty());
2346 assert(LastNode == StackNodes.back());
2351 if (
I > 0 && StackNodes != Calls[
I - 1].StackNodes)
2352 MatchingIdsFuncSet.
clear();
2359 DenseSet<uint32_t> StackSequenceContextIds = LastNodeContextIds;
2361 ContextNode *PrevNode = LastNode;
2362 ContextNode *CurNode = LastNode;
2367 for (
auto NodeIter = StackNodes.rbegin() + 1;
2368 NodeIter != StackNodes.rend(); NodeIter++) {
2369 CurNode = *NodeIter;
2373 if (CurNode->Recursive) {
2378 auto *
Edge = CurNode->findEdgeFromCaller(PrevNode);
2399 if (StackSequenceContextIds.
empty()) {
2412 if (LastId != getLastStackId(
Call)) {
2413 for (
const auto &PE : LastNode->CallerEdges) {
2414 set_subtract(StackSequenceContextIds, PE->getContextIds());
2415 if (StackSequenceContextIds.
empty())
2419 if (StackSequenceContextIds.
empty())
2431 MatchingIdsFuncSet.
insert(Func);
2440 bool DuplicateContextIds =
false;
2441 for (
unsigned J =
I + 1; J < Calls.size(); J++) {
2442 auto &CallCtxInfo = Calls[J];
2443 if (CallCtxInfo.StackNodes != StackNodes)
2445 auto *NextFunc = CallCtxInfo.Func;
2446 if (NextFunc != Func) {
2449 DuplicateContextIds =
true;
2452 auto &NextCall = CallCtxInfo.Call;
2453 CallToMatchingCall[NextCall] =
Call;
2464 OldToNewContextIds.
reserve(OldToNewContextIds.
size() +
2465 StackSequenceContextIds.
size());
2468 ? duplicateContextIds(StackSequenceContextIds, OldToNewContextIds)
2469 : StackSequenceContextIds;
2470 assert(!SavedContextIds.empty());
2472 if (!DuplicateContextIds) {
2476 set_subtract(LastNodeContextIds, StackSequenceContextIds);
2477 if (LastNodeContextIds.
empty())
2484 propagateDuplicateContextIds(OldToNewContextIds);
2494 DenseSet<const ContextNode *> Visited;
2496 ImportantContextIdInfo.keys());
2497 for (
auto &Entry : AllocationCallToContextNodeMap)
2498 assignStackNodesPostOrder(
Entry.second, Visited, StackIdToMatchingCalls,
2499 CallToMatchingCall, ImportantContextIds);
2501 fixupImportantContexts();
2507uint64_t ModuleCallsiteContextGraph::getLastStackId(Instruction *
Call) {
2508 CallStack<MDNode, MDNode::op_iterator> CallsiteContext(
2510 return CallsiteContext.
back();
2513uint64_t IndexCallsiteContextGraph::getLastStackId(IndexCall &
Call) {
2515 CallStack<CallsiteInfo, SmallVector<unsigned>::const_iterator>
2518 return Index.getStackIdAtIndex(CallsiteContext.
back());
2534 auto Pos =
F.getName().find_last_of(
'.');
2537 bool Err =
F.getName().drop_front(Pos + 1).getAsInteger(10, CloneNo);
2543std::string ModuleCallsiteContextGraph::getLabel(
const Function *Func,
2544 const Instruction *
Call,
2545 unsigned CloneNo)
const {
2551std::string IndexCallsiteContextGraph::getLabel(
const FunctionSummary *Func,
2552 const IndexCall &
Call,
2553 unsigned CloneNo)
const {
2554 auto VI = FSToVIMap.find(Func);
2555 assert(VI != FSToVIMap.end());
2558 return CallerName +
" -> alloc";
2561 return CallerName +
" -> " +
2563 Callsite->Clones[CloneNo]);
2567std::string ModuleCallsiteContextGraph::getFuncName(
const Function *Func,
2568 unsigned CloneNo)
const {
2574void ModuleCallsiteContextGraph::populateFunctionsWithCallers() {
2577 for (
const auto &
F :
Mod)
2579 FunctionsWithCallers.
insert(&
F);
2582std::string IndexCallsiteContextGraph::getFuncName(
const FunctionSummary *Func,
2583 unsigned CloneNo)
const {
2586 auto VI = FSToVIMap.find(Func);
2587 if (VI != FSToVIMap.end()) {
2588 if (!
VI->second.name().empty())
2596bool IndexCallsiteContextGraph::isFuncDead(
const FunctionSummary *Func)
const {
2597 return Index.withGlobalValueDeadStripping() &&
Func && !
Func->isLive();
2600void IndexCallsiteContextGraph::populateFunctionsWithCallers() {
2601 for (
const auto &
I : Index) {
2603 for (
const auto &S :
VI.getSummaryList()) {
2605 !isPrevailing(
VI.getGUID(), S.get()))
2607 if (
Index.withGlobalValueDeadStripping() && !S->isLive())
2609 auto AddReferenced = [&](ValueInfo RefVI) {
2610 for (
const auto &RefS : RefVI.getSummaryList()) {
2611 const GlobalValueSummary *
Base = RefS->getBaseObject();
2613 FunctionsWithCallers.
insert(RefFS);
2617 for (
const auto &RefVI : S->refs())
2618 AddReferenced(RefVI);
2621 for (
const auto &CallEdge :
FS->calls())
2622 AddReferenced(CallEdge.first);
2627std::vector<ModuleCallsiteContextGraph::ContextNode *>
2628ModuleCallsiteContextGraph::getStackNodesForCall(Instruction *
Call) {
2629 CallStack<MDNode, MDNode::op_iterator> CallsiteContext(
2631 return getStackNodesForCallsite<MDNode, MDNode::op_iterator>(CallsiteContext);
2634std::vector<IndexCallsiteContextGraph::ContextNode *>
2635IndexCallsiteContextGraph::getStackNodesForCall(IndexCall &
Call) {
2637 CallStack<CallsiteInfo, SmallVector<unsigned>::const_iterator>
2639 return getStackNodesForCallsite<CallsiteInfo,
2640 SmallVector<unsigned>::const_iterator>(
2644template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2645template <
class NodeT,
class IteratorT>
2647 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *>
2648CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getStackNodesForCallsite(
2649 CallStack<NodeT, IteratorT> &CallsiteContext) {
2650 std::vector<ContextNode *> StackNodes;
2651 for (
auto IdOrIndex : CallsiteContext) {
2652 auto StackId = getStackId(IdOrIndex);
2653 ContextNode *
Node = getNodeForStackId(StackId);
2656 StackNodes.push_back(Node);
2661ModuleCallsiteContextGraph::ModuleCallsiteContextGraph(
2663 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter)
2664 :
Mod(
M), OREGetter(OREGetter) {
2668 std::map<uint64_t, uint32_t> TotalSizeToContextIdTopNCold;
2670 std::vector<CallInfo> CallsWithMetadata;
2671 for (
auto &BB :
F) {
2672 for (
auto &
I : BB) {
2675 if (
auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof)) {
2676 CallsWithMetadata.push_back(&
I);
2677 auto *AllocNode = addAllocNode(&
I, &
F);
2678 auto *CallsiteMD =
I.getMetadata(LLVMContext::MD_callsite);
2682 for (
auto &MDOp : MemProfMD->operands()) {
2684 std::vector<ContextTotalSize> ContextSizeInfo;
2686 if (MIBMD->getNumOperands() > 2) {
2687 for (
unsigned I = 2;
I < MIBMD->getNumOperands();
I++) {
2688 MDNode *ContextSizePair =
2697 ContextSizeInfo.push_back({FullStackId, TotalSize});
2703 addStackNodesForMIB<MDNode, MDNode::op_iterator>(
2704 AllocNode, StackContext, CallsiteContext,
2706 TotalSizeToContextIdTopNCold);
2711 DotAllocContextIds = AllocNode->getContextIds();
2715 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
2716 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
2719 else if (
I.getMetadata(LLVMContext::MD_callsite)) {
2720 CallsWithMetadata.push_back(&
I);
2724 if (!CallsWithMetadata.empty())
2725 FuncToCallsWithMetadata[&
F] = CallsWithMetadata;
2729 dbgs() <<
"CCG before updating call stack chains:\n";
2734 exportToDot(
"prestackupdate");
2739 exportToDot(
"poststackupdate");
2741 handleCallsitesWithMultipleTargets();
2746 for (
auto &FuncEntry : FuncToCallsWithMetadata)
2747 for (
auto &
Call : FuncEntry.second)
2748 Call.call()->setMetadata(LLVMContext::MD_callsite,
nullptr);
2754IndexCallsiteContextGraph::findAliaseeGUIDsPrevailingInDifferentModule() {
2755 DenseSet<GlobalValue::GUID> AliaseeGUIDs;
2756 for (
auto &
I : Index) {
2758 for (
auto &S :
VI.getSummaryList()) {
2763 auto *AliaseeSummary = &AS->getAliasee();
2771 !isPrevailing(
VI.getGUID(), S.get()))
2776 auto AliaseeGUID = AS->getAliaseeGUID();
2778 if (!isPrevailing(AliaseeGUID, AliaseeSummary))
2779 AliaseeGUIDs.
insert(AliaseeGUID);
2782 AliaseesPrevailingInDiffModuleFromAlias += AliaseeGUIDs.
size();
2783 return AliaseeGUIDs;
2786IndexCallsiteContextGraph::IndexCallsiteContextGraph(
2787 ModuleSummaryIndex &Index,
2797 findAliaseeGUIDsPrevailingInDifferentModule();
2801 std::map<uint64_t, uint32_t> TotalSizeToContextIdTopNCold;
2806 for (
const auto &
I : Index.sortedGlobalValueSummariesRange()) {
2807 auto VI = Index.getValueInfo(
I);
2808 if (GUIDsToSkip.
contains(VI.getGUID()))
2810 for (
auto &S : VI.getSummaryList()) {
2819 !isPrevailing(VI.getGUID(), S.get()))
2824 std::vector<CallInfo> CallsWithMetadata;
2825 if (!
FS->allocs().empty()) {
2826 for (
auto &AN :
FS->mutableAllocs()) {
2831 if (AN.MIBs.empty())
2833 IndexCall AllocCall(&AN);
2834 CallsWithMetadata.push_back(AllocCall);
2835 auto *AllocNode = addAllocNode(AllocCall, FS);
2843 AN.ContextSizeInfos.size() == AN.MIBs.size());
2845 for (
auto &MIB : AN.MIBs) {
2848 std::vector<ContextTotalSize> ContextSizeInfo;
2849 if (!AN.ContextSizeInfos.empty()) {
2850 for (
auto [FullStackId, TotalSize] : AN.ContextSizeInfos[
I])
2851 ContextSizeInfo.push_back({FullStackId, TotalSize});
2853 addStackNodesForMIB<MIBInfo, SmallVector<unsigned>::const_iterator>(
2854 AllocNode, StackContext, EmptyContext, MIB.AllocType,
2855 ContextSizeInfo, TotalSizeToContextIdTopNCold);
2861 DotAllocContextIds = AllocNode->getContextIds();
2867 AN.Versions[0] = (
uint8_t)allocTypeToUse(AllocNode->AllocTypes);
2871 if (!
FS->callsites().empty())
2872 for (
auto &SN :
FS->mutableCallsites()) {
2873 IndexCall StackNodeCall(&SN);
2874 CallsWithMetadata.push_back(StackNodeCall);
2877 if (!CallsWithMetadata.empty())
2878 FuncToCallsWithMetadata[
FS] = CallsWithMetadata;
2880 if (!
FS->allocs().empty() || !
FS->callsites().empty())
2886 dbgs() <<
"CCG before updating call stack chains:\n";
2891 exportToDot(
"prestackupdate");
2896 exportToDot(
"poststackupdate");
2898 handleCallsitesWithMultipleTargets();
2903template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2904void CallsiteContextGraph<DerivedCCG, FuncTy,
2905 CallTy>::handleCallsitesWithMultipleTargets() {
2920 std::vector<std::pair<CallInfo, ContextNode *>> NewCallToNode;
2921 for (
auto &Entry : NonAllocationCallToContextNodeMap) {
2922 auto *
Node = Entry.second;
2931 std::vector<CallInfo> AllCalls;
2932 AllCalls.reserve(
Node->MatchingCalls.size() + 1);
2933 AllCalls.push_back(
Node->Call);
2947 if (partitionCallsByCallee(
Node, AllCalls, NewCallToNode))
2950 auto It = AllCalls.begin();
2952 for (; It != AllCalls.end(); ++It) {
2955 for (
auto EI =
Node->CalleeEdges.begin(); EI !=
Node->CalleeEdges.end();
2958 if (!Edge->Callee->hasCall())
2960 assert(NodeToCallingFunc.count(Edge->Callee));
2962 if (!calleesMatch(
ThisCall.call(), EI, TailCallToContextNodeMap)) {
2971 if (
Node->Call != ThisCall) {
2972 Node->setCall(ThisCall);
2983 Node->MatchingCalls.clear();
2986 if (It == AllCalls.end()) {
2987 RemovedEdgesWithMismatchedCallees++;
2991 Node->setCall(CallInfo());
2996 for (++It; It != AllCalls.end(); ++It) {
3000 Node->MatchingCalls.push_back(ThisCall);
3009 NonAllocationCallToContextNodeMap.remove_if([](
const auto &it) {
3010 return !it.second->hasCall() || it.second->Call != it.first;
3014 for (
auto &[
Call,
Node] : NewCallToNode)
3015 NonAllocationCallToContextNodeMap[
Call] =
Node;
3019 for (
auto &[
Call,
Node] : TailCallToContextNodeMap)
3020 NonAllocationCallToContextNodeMap[
Call] =
Node;
3023template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3024bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::partitionCallsByCallee(
3026 std::vector<std::pair<CallInfo, ContextNode *>> &NewCallToNode) {
3030 struct CallsWithSameCallee {
3031 std::vector<CallInfo> Calls;
3032 ContextNode *
Node =
nullptr;
3038 for (
auto ThisCall : AllCalls) {
3039 auto *
F = getCalleeFunc(
ThisCall.call());
3041 CalleeFuncToCallInfo[
F].Calls.push_back(ThisCall);
3050 for (
const auto &Edge :
Node->CalleeEdges) {
3051 if (!Edge->Callee->hasCall())
3053 const FuncTy *ProfiledCalleeFunc = NodeToCallingFunc[Edge->Callee];
3054 if (CalleeFuncToCallInfo.
contains(ProfiledCalleeFunc))
3055 CalleeNodeToCallInfo[Edge->Callee] =
3056 &CalleeFuncToCallInfo[ProfiledCalleeFunc];
3062 if (CalleeNodeToCallInfo.
empty())
3074 ContextNode *UnmatchedCalleesNode =
nullptr;
3076 bool UsedOrigNode =
false;
3081 auto CalleeEdges =
Node->CalleeEdges;
3082 for (
auto &Edge : CalleeEdges) {
3083 if (!Edge->Callee->hasCall())
3088 ContextNode *CallerNodeToUse =
nullptr;
3092 if (!CalleeNodeToCallInfo.
contains(Edge->Callee)) {
3093 if (!UnmatchedCalleesNode)
3094 UnmatchedCalleesNode =
3095 createNewNode(
false, NodeToCallingFunc[
Node]);
3096 CallerNodeToUse = UnmatchedCalleesNode;
3100 auto *Info = CalleeNodeToCallInfo[Edge->Callee];
3103 if (!UsedOrigNode) {
3106 Node->MatchingCalls.clear();
3107 UsedOrigNode =
true;
3110 createNewNode(
false, NodeToCallingFunc[
Node]);
3111 assert(!Info->Calls.empty());
3114 Info->Node->setCall(Info->Calls.front());
3120 NewCallToNode.push_back({Info->Node->Call, Info->Node});
3122 CallerNodeToUse = Info->Node;
3126 if (CallerNodeToUse ==
Node)
3129 moveCalleeEdgeToNewCaller(Edge, CallerNodeToUse);
3136 for (
auto &
I : CalleeNodeToCallInfo)
3137 removeNoneTypeCallerEdges(
I.second->Node);
3138 if (UnmatchedCalleesNode)
3139 removeNoneTypeCallerEdges(UnmatchedCalleesNode);
3140 removeNoneTypeCallerEdges(
Node);
3153 return Index.getStackIdAtIndex(IdOrIndex);
3156template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3157bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::calleesMatch(
3158 CallTy
Call, EdgeIter &EI,
3159 MapVector<CallInfo, ContextNode *> &TailCallToContextNodeMap) {
3161 const FuncTy *ProfiledCalleeFunc = NodeToCallingFunc[
Edge->Callee];
3162 const FuncTy *CallerFunc = NodeToCallingFunc[
Edge->Caller];
3165 std::vector<std::pair<CallTy, FuncTy *>> FoundCalleeChain;
3166 if (!calleeMatchesFunc(
Call, ProfiledCalleeFunc, CallerFunc,
3171 if (FoundCalleeChain.empty())
3175 auto *CurEdge =
Callee->findEdgeFromCaller(Caller);
3179 CurEdge->ContextIds.insert_range(
Edge->ContextIds);
3180 CurEdge->AllocTypes |=
Edge->AllocTypes;
3185 auto NewEdge = std::make_shared<ContextEdge>(
3186 Callee, Caller,
Edge->AllocTypes,
Edge->ContextIds);
3187 Callee->CallerEdges.push_back(NewEdge);
3188 if (Caller ==
Edge->Caller) {
3192 EI =
Caller->CalleeEdges.insert(EI, NewEdge);
3195 "Iterator position not restored after insert and increment");
3197 Caller->CalleeEdges.push_back(NewEdge);
3202 auto *CurCalleeNode =
Edge->Callee;
3203 for (
auto &[NewCall, Func] : FoundCalleeChain) {
3204 ContextNode *NewNode =
nullptr;
3206 if (TailCallToContextNodeMap.
count(NewCall)) {
3207 NewNode = TailCallToContextNodeMap[NewCall];
3208 NewNode->AllocTypes |=
Edge->AllocTypes;
3210 FuncToCallsWithMetadata[
Func].push_back({NewCall});
3212 NewNode = createNewNode(
false, Func, NewCall);
3213 TailCallToContextNodeMap[NewCall] = NewNode;
3214 NewNode->AllocTypes =
Edge->AllocTypes;
3218 AddEdge(NewNode, CurCalleeNode);
3220 CurCalleeNode = NewNode;
3224 AddEdge(
Edge->Caller, CurCalleeNode);
3232 removeEdgeFromGraph(
Edge.get(), &EI,
true);
3244bool ModuleCallsiteContextGraph::findProfiledCalleeThroughTailCalls(
3246 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain,
3247 bool &FoundMultipleCalleeChains) {
3254 FoundCalleeChain.push_back({Callsite,
F});
3269 bool FoundSingleCalleeChain =
false;
3270 for (
auto &BB : *CalleeFunc) {
3271 for (
auto &
I : BB) {
3273 if (!CB || !CB->isTailCall())
3275 auto *CalledValue = CB->getCalledOperand();
3276 auto *CalledFunction = CB->getCalledFunction();
3277 if (CalledValue && !CalledFunction) {
3278 CalledValue = CalledValue->stripPointerCasts();
3285 assert(!CalledFunction &&
3286 "Expected null called function in callsite for alias");
3289 if (!CalledFunction)
3291 if (CalledFunction == ProfiledCallee) {
3292 if (FoundSingleCalleeChain) {
3293 FoundMultipleCalleeChains =
true;
3296 FoundSingleCalleeChain =
true;
3297 FoundProfiledCalleeCount++;
3298 FoundProfiledCalleeDepth +=
Depth;
3299 if (
Depth > FoundProfiledCalleeMaxDepth)
3300 FoundProfiledCalleeMaxDepth =
Depth;
3301 SaveCallsiteInfo(&
I, CalleeFunc);
3302 }
else if (findProfiledCalleeThroughTailCalls(
3303 ProfiledCallee, CalledFunction,
Depth + 1,
3304 FoundCalleeChain, FoundMultipleCalleeChains)) {
3307 assert(!FoundMultipleCalleeChains);
3308 if (FoundSingleCalleeChain) {
3309 FoundMultipleCalleeChains =
true;
3312 FoundSingleCalleeChain =
true;
3313 SaveCallsiteInfo(&
I, CalleeFunc);
3314 }
else if (FoundMultipleCalleeChains)
3319 return FoundSingleCalleeChain;
3322const Function *ModuleCallsiteContextGraph::getCalleeFunc(Instruction *
Call) {
3324 if (!CB->getCalledOperand() || CB->isIndirectCall())
3326 auto *CalleeVal = CB->getCalledOperand()->stripPointerCasts();
3333bool ModuleCallsiteContextGraph::calleeMatchesFunc(
3335 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain) {
3337 if (!CB->getCalledOperand() || CB->isIndirectCall())
3339 auto *CalleeVal = CB->getCalledOperand()->stripPointerCasts();
3341 if (CalleeFunc == Func)
3344 if (Alias && Alias->getAliasee() == Func)
3355 bool FoundMultipleCalleeChains =
false;
3356 if (!findProfiledCalleeThroughTailCalls(Func, CalleeVal,
Depth,
3358 FoundMultipleCalleeChains)) {
3359 LLVM_DEBUG(
dbgs() <<
"Not found through unique tail call chain: "
3360 <<
Func->getName() <<
" from " << CallerFunc->
getName()
3361 <<
" that actually called " << CalleeVal->getName()
3362 << (FoundMultipleCalleeChains
3363 ?
" (found multiple possible chains)"
3366 if (FoundMultipleCalleeChains)
3367 FoundProfiledCalleeNonUniquelyCount++;
3374bool ModuleCallsiteContextGraph::sameCallee(Instruction *Call1,
3375 Instruction *Call2) {
3377 if (!CB1->getCalledOperand() || CB1->isIndirectCall())
3379 auto *CalleeVal1 = CB1->getCalledOperand()->stripPointerCasts();
3382 if (!CB2->getCalledOperand() || CB2->isIndirectCall())
3384 auto *CalleeVal2 = CB2->getCalledOperand()->stripPointerCasts();
3386 return CalleeFunc1 == CalleeFunc2;
3389bool IndexCallsiteContextGraph::findProfiledCalleeThroughTailCalls(
3390 ValueInfo ProfiledCallee, ValueInfo CurCallee,
unsigned Depth,
3391 std::vector<std::pair<ValueInfo, FunctionSummary *>> &FoundCalleeChain,
3392 bool &FoundMultipleCalleeChains) {
3402 auto SaveTailCall = [&](ValueInfo
Callee, FunctionSummary *
FS) {
3403 FoundCalleeChain.push_back({
Callee,
FS});
3410 bool FoundSingleCalleeChain =
false;
3413 !isPrevailing(CurCallee.
getGUID(), S.get()))
3418 auto FSVI = CurCallee;
3421 FSVI = AS->getAliaseeVI();
3422 for (
auto &CallEdge :
FS->calls()) {
3423 if (!CallEdge.second.hasTailCall())
3430 if (CallEdge.first == ProfiledCallee) {
3431 if (FoundSingleCalleeChain) {
3432 FoundMultipleCalleeChains =
true;
3435 FoundSingleCalleeChain =
true;
3436 FoundProfiledCalleeCount++;
3437 FoundProfiledCalleeDepth +=
Depth;
3438 if (
Depth > FoundProfiledCalleeMaxDepth)
3439 FoundProfiledCalleeMaxDepth =
Depth;
3440 if (CallEdge.second.hasIndirectCall())
3441 FoundProfiledCalleeIndirectTailCallCount++;
3442 SaveTailCall(CallEdge.first, FS);
3444 assert(!FSToVIMap.count(FS) || FSToVIMap[FS] == FSVI);
3445 FSToVIMap[
FS] = FSVI;
3446 }
else if (findProfiledCalleeThroughTailCalls(
3447 ProfiledCallee, CallEdge.first,
Depth + 1,
3448 FoundCalleeChain, FoundMultipleCalleeChains)) {
3451 assert(!FoundMultipleCalleeChains);
3452 if (FoundSingleCalleeChain) {
3453 FoundMultipleCalleeChains =
true;
3456 FoundSingleCalleeChain =
true;
3457 if (CallEdge.second.hasIndirectCall())
3458 FoundProfiledCalleeIndirectTailCallCount++;
3459 SaveTailCall(CallEdge.first, FS);
3461 assert(!FSToVIMap.count(FS) || FSToVIMap[FS] == FSVI);
3462 FSToVIMap[
FS] = FSVI;
3463 }
else if (FoundMultipleCalleeChains)
3468 return FoundSingleCalleeChain;
3471const FunctionSummary *
3472IndexCallsiteContextGraph::getCalleeFunc(IndexCall &
Call) {
3474 if (
Callee.getSummaryList().empty())
3479bool IndexCallsiteContextGraph::calleeMatchesFunc(
3480 IndexCall &
Call,
const FunctionSummary *Func,
3481 const FunctionSummary *CallerFunc,
3482 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain) {
3486 AliasSummary *Alias =
3487 Callee.getSummaryList().empty()
3490 assert(FSToVIMap.count(Func));
3491 auto FuncVI = FSToVIMap[
Func];
3492 if (Callee == FuncVI ||
3507 bool FoundMultipleCalleeChains =
false;
3508 std::vector<std::pair<ValueInfo, FunctionSummary *>> FoundCalleeVIChain;
3509 if (!findProfiledCalleeThroughTailCalls(FuncVI, Callee,
Depth,
3511 FoundMultipleCalleeChains)) {
3512 LLVM_DEBUG(
dbgs() <<
"Not found through unique tail call chain: " << FuncVI
3513 <<
" from " << FSToVIMap[CallerFunc]
3514 <<
" that actually called " << Callee
3515 << (FoundMultipleCalleeChains
3516 ?
" (found multiple possible chains)"
3519 if (FoundMultipleCalleeChains)
3520 FoundProfiledCalleeNonUniquelyCount++;
3529 for (
auto &[CalleeVI, FS] : FoundCalleeVIChain) {
3530 auto &CallsiteInfoPtr =
3531 FunctionCalleesToSynthesizedCallsiteInfos[
FS][CalleeVI];
3532 if (!CallsiteInfoPtr)
3536 std::make_unique<CallsiteInfo>(CalleeVI, SmallVector<unsigned>());
3537 FoundCalleeChain.push_back({CallsiteInfoPtr.get(),
FS});
3543bool IndexCallsiteContextGraph::sameCallee(IndexCall &Call1, IndexCall &Call2) {
3546 return Callee1 == Callee2;
3549template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3550void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::dump()
3556template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3557void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::print(
3558 raw_ostream &OS)
const {
3559 OS <<
"Node " <<
this <<
"\n";
3563 OS <<
" (recursive)";
3565 if (!MatchingCalls.
empty()) {
3566 OS <<
"\tMatchingCalls:\n";
3567 for (
auto &MatchingCall : MatchingCalls) {
3569 MatchingCall.print(OS);
3573 OS <<
"\tNodeId: " <<
NodeId <<
"\n";
3575 OS <<
"\tContextIds:";
3577 auto ContextIds = getContextIds();
3578 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
3579 std::sort(SortedIds.begin(), SortedIds.end());
3580 for (
auto Id : SortedIds)
3583 OS <<
"\tCalleeEdges:\n";
3584 for (
auto &
Edge : CalleeEdges)
3585 OS <<
"\t\t" << *
Edge <<
" (Callee NodeId: " <<
Edge->Callee->NodeId
3587 OS <<
"\tCallerEdges:\n";
3588 for (
auto &
Edge : CallerEdges)
3589 OS <<
"\t\t" << *
Edge <<
" (Caller NodeId: " <<
Edge->Caller->NodeId
3591 if (!Clones.empty()) {
3594 for (
auto *
C : Clones)
3595 OS <<
LS <<
C <<
" NodeId: " <<
C->NodeId;
3597 }
else if (CloneOf) {
3598 OS <<
"\tClone of " << CloneOf <<
" NodeId: " << CloneOf->NodeId <<
"\n";
3602template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3603void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge::dump()
3609template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3610void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge::print(
3611 raw_ostream &OS)
const {
3612 OS <<
"Edge from Callee " <<
Callee <<
" to Caller: " <<
Caller
3613 << (IsBackedge ?
" (BE)" :
"")
3615 OS <<
" ContextIds:";
3616 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
3617 std::sort(SortedIds.begin(), SortedIds.end());
3618 for (
auto Id : SortedIds)
3622template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3623void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::dump()
const {
3627template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3628void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::print(
3629 raw_ostream &OS)
const {
3630 OS <<
"Callsite Context Graph:\n";
3631 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
3633 if (
Node->isRemoved())
3640template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3641void CallsiteContextGraph<DerivedCCG, FuncTy,
3642 CallTy>::capturePreCloningContextInfo() {
3643 for (
const auto &Entry : AllocationCallToContextNodeMap) {
3644 const ContextNode *AllocNode =
Entry.second;
3648 for (
const auto &
Edge : AllocNode->CallerEdges) {
3649 if (!
Edge->isRemoved() &&
Edge->Caller->hasCall()) {
3650 PreCloningAllocHasMatchedCaller.insert(AllocNode);
3654 DenseSet<uint32_t> ContextIds = AllocNode->getContextIds();
3655 for (uint32_t Id : ContextIds) {
3656 PreCloningContextInfo
Info;
3662 Info.Chain.push_back(AllocNode);
3663 SmallPtrSet<const ContextNode *, 16> Visited;
3664 Visited.
insert(AllocNode);
3665 const ContextNode *Cur = AllocNode;
3667 const ContextNode *
Next =
nullptr;
3668 for (
const auto &
Edge : Cur->CallerEdges) {
3669 if (
Edge->isRemoved() ||
Edge->IsBackedge)
3671 if (
Edge->getContextIds().contains(Id) &&
3678 for (
const auto &
Edge : Cur->CallerEdges) {
3679 if (
Edge->isRemoved())
3681 if (
Edge->getContextIds().contains(Id) &&
3698 Info.MaxMatchedFrame = 0;
3699 for (
unsigned I = 1;
I <
Info.Chain.size(); ++
I) {
3700 if (
Info.Chain[
I]->hasCall()) {
3701 Info.MaxMatchedFrame =
I;
3703 const ContextNode *Unmatched =
Info.Chain[
I];
3704 Info.UnmatchedStackId = Unmatched->OrigStackOrAllocId;
3705 Info.StoppedAtRecursive = Unmatched->Recursive;
3709 if (
auto It = NodeToCallingFunc.find(Unmatched);
3710 It != NodeToCallingFunc.end()) {
3711 Info.StoppedAtMismatchedCallee =
true;
3712 Info.UnmatchedCallingFunc = It->second;
3722 if (
Info.MaxMatchedFrame > 0 &&
3723 Info.MaxMatchedFrame + 1 ==
Info.Chain.size()) {
3724 const ContextNode *OutermostMatchedNode =
3726 for (
const auto &
Edge : OutermostMatchedNode->CallerEdges) {
3727 if (!
Edge->isRemoved() &&
Edge->Caller->hasCall()) {
3728 Info.OutermostMatchedNodeHasOtherCallers =
true;
3734 PreCloningContextInfoMap[
Id] = std::move(Info);
3739template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3741CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::formatContextReportSuffix(
3742 const ContextNode *Node, uint32_t Id)
const {
3743 auto InfoIt = PreCloningContextInfoMap.find(Id);
3744 if (InfoIt == PreCloningContextInfoMap.end())
3746 const PreCloningContextInfo &
Info = InfoIt->second;
3753 const ContextNode *OrigAlloc =
Node->getOrigNode();
3754 const FuncTy *AllocFunc = getCallingFunc(OrigAlloc);
3755 unsigned AllocCloneNo =
Node->Call.cloneNo();
3756 std::string AllocFuncStr = getFuncName(AllocFunc, AllocCloneNo);
3757 if (isFuncDead(AllocFunc)) {
3758 AllocFuncStr +=
" (dead)";
3759 }
else if (!PreCloningAllocHasMatchedCaller.contains(OrigAlloc) &&
3760 Info.Chain.size() > 1) {
3764 AllocFuncStr += AllocFunc && !FunctionsWithCallers.
contains(AllocFunc)
3765 ?
" (no references in IR/summary)"
3766 :
" (no matched callers)";
3772 unsigned TotalFrames =
Info.Chain.size() > 0 ?
Info.Chain.size() - 1 : 0;
3773 unsigned Matched =
Info.MaxMatchedFrame;
3774 std::string StatusStr;
3775 if (TotalFrames == 0) {
3776 StatusStr =
"inlined into leaf";
3777 }
else if (Matched < TotalFrames) {
3782 if (
Info.StoppedAtRecursive)
3783 StatusStr =
"unmatched recursive callsite";
3784 else if (
Info.StoppedAtMismatchedCallee)
3785 StatusStr =
"unmatched callsite (mismatched callee in " +
3786 getFuncName(
Info.UnmatchedCallingFunc, 0) +
")";
3788 StatusStr =
"unmatched callsite";
3789 StatusStr +=
" at frame " + std::to_string(Matched + 1) +
"/" +
3790 std::to_string(TotalFrames) +
" (stack id " +
3791 std::to_string(
Info.UnmatchedStackId) +
")";
3793 const ContextNode *OutermostMatchedNode =
Info.Chain[Matched];
3794 const FuncTy *OutermostMatchedFunc = getCallingFunc(OutermostMatchedNode);
3795 unsigned NumOutermostMatchedFuncClones =
3796 std::max<unsigned>(1, FuncToNumClones.lookup(OutermostMatchedFunc));
3797 bool HasCallersAbove =
3798 NumOutermostMatchedFuncClones > 1 ||
3799 Info.OutermostMatchedNodeHasOtherCallers ||
3800 (OutermostMatchedFunc &&
3801 FunctionsWithCallers.
contains(OutermostMatchedFunc));
3802 if (HasCallersAbove) {
3803 StatusStr =
"trimmed at frame " + std::to_string(Matched) +
" in " +
3804 getFuncName(OutermostMatchedFunc, 0);
3806 StatusStr =
"matched " + std::to_string(Matched) +
" frames to " +
3807 getFuncName(OutermostMatchedFunc, 0);
3816 std::string ReachesStr;
3818 const ContextNode *OutermostMatchedNode =
Info.Chain[Matched];
3819 const FuncTy *OutermostMatchedFunc = getCallingFunc(OutermostMatchedNode);
3820 unsigned NumOutermostMatchedFuncClones =
3821 std::max<unsigned>(1, FuncToNumClones.lookup(OutermostMatchedFunc));
3822 ReachesStr =
"; reaches ";
3827 SmallSet<unsigned, 4> ReportedAllocClones;
3828 bool FirstPath =
true;
3829 for (
unsigned OutermostMatchedFuncClone = 0;
3830 OutermostMatchedFuncClone < NumOutermostMatchedFuncClones;
3831 ++OutermostMatchedFuncClone) {
3835 std::vector<const FuncTy *> PathFuncs(Matched + 1);
3836 std::vector<unsigned> PathClones(Matched + 1);
3837 PathFuncs[0] = OutermostMatchedFunc;
3838 PathClones[0] = OutermostMatchedFuncClone;
3839 unsigned CurClone = OutermostMatchedFuncClone;
3840 for (
unsigned Step = 0; Step < Matched; ++Step) {
3841 unsigned FrameIdx = Matched - Step;
3842 const ContextNode *CallNode =
Info.Chain[FrameIdx];
3843 unsigned NextClone =
3844 OrigNodeAndCloneToCalleeClone.lookup({CallNode, CurClone});
3845 const FuncTy *CalleeFunc = getCallingFunc(
Info.Chain[FrameIdx - 1]);
3846 PathFuncs[Step + 1] = CalleeFunc;
3847 PathClones[Step + 1] = NextClone;
3848 CurClone = NextClone;
3851 if (!ReportedAllocClones.
insert(CurClone).second)
3857 const ContextNode *ReachedAlloc =
3858 OrigAllocAndCloneToNode.lookup({OrigAlloc, CurClone});
3862 std::string ReachedTypeStr;
3865 (uint8_t)getAllocationCallType(ReachedAlloc->Call));
3866 else if (CurClone == 0)
3870 ReachedTypeStr =
"None";
3876 std::string PathStr;
3877 bool SkippedPrev =
false;
3878 bool PrintFullPath =
3880 for (
unsigned S = 0; S <= Matched; ++S) {
3881 bool IsCloned = PathClones[S] > 0;
3882 bool PrevCloned = S > 0 ? (PathClones[S - 1] > 0) : IsCloned;
3883 bool NextCloned = S + 1 <= Matched ? (PathClones[S + 1] > 0) : IsCloned;
3884 bool Include = PrintFullPath || (S <= 1) || (S + 1 >= Matched) ||
3885 (IsCloned != PrevCloned) || (IsCloned != NextCloned);
3888 PathStr +=
" -> ...";
3893 SkippedPrev =
false;
3894 if (!PathStr.empty())
3896 PathStr += getFuncName(PathFuncs[S], PathClones[S]);
3898 ReachesStr += ReachedTypeStr +
" via " + PathStr;
3902 return " [alloc in " + AllocFuncStr +
"; " + StatusStr + ReachesStr +
"]";
3905template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3906void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::printTotalSizes(
3908 function_ref<
void(StringRef, StringRef,
const Twine &)> EmitRemark)
const {
3909 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
3911 if (
Node->isRemoved())
3913 if (!
Node->IsAllocation)
3915 DenseSet<uint32_t> ContextIds =
Node->getContextIds();
3916 auto AllocTypeFromCall = getAllocationCallType(
Node->Call);
3917 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
3918 std::sort(SortedIds.begin(), SortedIds.end());
3919 for (
auto Id : SortedIds) {
3920 auto TypeI = ContextIdToAllocationType.
find(Id);
3921 assert(TypeI != ContextIdToAllocationType.
end());
3923 bool ComputedSuffix =
false;
3924 auto GetSuffix = [&]() ->
const std::string & {
3925 if (!ComputedSuffix) {
3927 ? formatContextReportSuffix(Node, Id)
3929 ComputedSuffix =
true;
3933 auto CSI = ContextIdToContextSizeInfos.
find(Id);
3934 if (CSI != ContextIdToContextSizeInfos.
end()) {
3935 for (
auto &Info : CSI->second) {
3938 " full allocation context " + std::to_string(
Info.FullStackId) +
3939 " with total size " + std::to_string(
Info.TotalSize) +
" is " +
3941 if (allocTypeToUse(
Node->AllocTypes) !=
3942 allocTypeToUse((uint8_t)AllocTypeFromCall))
3944 " due to cold byte percent";
3946 Msg +=
" (internal context id " + std::to_string(Id) +
")";
3948 OS <<
Msg << GetSuffix() <<
"\n";
3958 if (allocTypeToUse(
Node->AllocTypes) !=
3959 allocTypeToUse((uint8_t)AllocTypeFromCall))
3961 " due to cold byte percent";
3963 Msg +=
" (internal context id " + std::to_string(Id) +
")";
3965 OS <<
Msg << GetSuffix() <<
"\n";
3973template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3974void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::check()
const {
3975 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
3978 for (
auto &
Edge :
Node->CallerEdges)
3983template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3985 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
3986 using NodeRef =
const ContextNode<DerivedCCG, FuncTy, CallTy> *;
3988 using NodePtrTy = std::unique_ptr<ContextNode<DerivedCCG, FuncTy, CallTy>>;
4004 return G->NodeOwner.begin()->get();
4007 using EdgePtrTy = std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>>;
4008 static const ContextNode<DerivedCCG, FuncTy, CallTy> *
4027template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4041 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
4047 std::string LabelString =
4048 (
Twine(
"OrigId: ") + (
Node->IsAllocation ?
"Alloc" :
"") +
4051 LabelString +=
"\n";
4052 if (
Node->hasCall()) {
4053 auto Func =
G->NodeToCallingFunc.find(
Node);
4054 assert(Func !=
G->NodeToCallingFunc.end());
4056 G->getLabel(Func->second,
Node->Call.call(),
Node->Call.cloneNo());
4057 for (
auto &MatchingCall :
Node->MatchingCalls) {
4058 LabelString +=
"\n";
4059 LabelString +=
G->getLabel(Func->second, MatchingCall.call(),
4060 MatchingCall.cloneNo());
4063 LabelString +=
"null call";
4064 if (
Node->Recursive)
4065 LabelString +=
" (recursive)";
4067 LabelString +=
" (external)";
4073 auto ContextIds =
Node->getContextIds();
4077 bool Highlight =
false;
4086 std::string AttributeString = (
Twine(
"tooltip=\"") + getNodeId(
Node) +
" " +
4087 getContextIds(ContextIds) +
"\"")
4091 AttributeString +=
",fontsize=\"30\"";
4093 (
Twine(
",fillcolor=\"") + getColor(
Node->AllocTypes, Highlight) +
"\"")
4095 if (
Node->CloneOf) {
4096 AttributeString +=
",color=\"blue\"";
4097 AttributeString +=
",style=\"filled,bold,dashed\"";
4099 AttributeString +=
",style=\"filled\"";
4100 return AttributeString;
4105 auto &Edge = *(ChildIter.getCurrent());
4110 bool Highlight =
false;
4119 auto Color = getColor(Edge->AllocTypes, Highlight);
4120 std::string AttributeString =
4121 (
Twine(
"tooltip=\"") + getContextIds(Edge->ContextIds) +
"\"" +
4123 Twine(
",fillcolor=\"") + Color +
"\"" +
Twine(
",color=\"") + Color +
4126 if (Edge->IsBackedge)
4127 AttributeString +=
",style=\"dotted\"";
4130 AttributeString +=
",penwidth=\"2.0\",weight=\"2\"";
4131 return AttributeString;
4137 if (
Node->isRemoved())
4150 std::string IdString =
"ContextIds:";
4151 if (ContextIds.
size() < 100) {
4152 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
4153 std::sort(SortedIds.begin(), SortedIds.end());
4154 for (
auto Id : SortedIds)
4155 IdString += (
" " +
Twine(Id)).str();
4157 IdString += (
" (" + Twine(ContextIds.
size()) +
" ids)").str();
4162 static std::string getColor(uint8_t AllocTypes,
bool Highlight) {
4168 if (AllocTypes == (uint8_t)AllocationType::NotCold)
4170 return !
DoHighlight || Highlight ?
"brown1" :
"lightpink";
4171 if (AllocTypes == (uint8_t)AllocationType::Cold)
4172 return !
DoHighlight || Highlight ?
"cyan" :
"lightskyblue";
4174 ((uint8_t)AllocationType::NotCold | (uint8_t)AllocationType::Cold))
4175 return Highlight ?
"magenta" :
"mediumorchid1";
4179 static std::string getNodeId(NodeRef Node) {
4180 std::stringstream SStream;
4181 SStream << std::hex <<
"N0x" << (
unsigned long long)Node;
4182 std::string
Result = SStream.str();
4191template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4196template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4197void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::exportToDot(
4198 std::string Label)
const {
4203template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4204typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
4205CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::moveEdgeToNewCalleeClone(
4206 const std::shared_ptr<ContextEdge> &
Edge,
4207 DenseSet<uint32_t> ContextIdsToMove) {
4209 assert(NodeToCallingFunc.count(Node));
4210 ContextNode *Clone =
4211 createNewNode(
Node->IsAllocation, NodeToCallingFunc[Node],
Node->Call);
4212 Node->addClone(Clone);
4213 Clone->MatchingCalls =
Node->MatchingCalls;
4214 moveEdgeToExistingCalleeClone(
Edge, Clone,
true,
4219template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4220void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
4221 moveEdgeToExistingCalleeClone(
const std::shared_ptr<ContextEdge> &
Edge,
4222 ContextNode *NewCallee,
bool NewClone,
4223 DenseSet<uint32_t> ContextIdsToMove) {
4226 assert(NewCallee->getOrigNode() ==
Edge->Callee->getOrigNode());
4228 bool EdgeIsRecursive =
Edge->Callee ==
Edge->Caller;
4230 ContextNode *OldCallee =
Edge->Callee;
4234 auto ExistingEdgeToNewCallee = NewCallee->findEdgeFromCaller(
Edge->Caller);
4238 if (ContextIdsToMove.
empty())
4239 ContextIdsToMove =
Edge->getContextIds();
4243 if (
Edge->getContextIds().size() == ContextIdsToMove.
size()) {
4246 NewCallee->AllocTypes |=
Edge->AllocTypes;
4248 if (ExistingEdgeToNewCallee) {
4251 ExistingEdgeToNewCallee->getContextIds().insert_range(ContextIdsToMove);
4252 ExistingEdgeToNewCallee->AllocTypes |=
Edge->AllocTypes;
4253 assert(
Edge->ContextIds == ContextIdsToMove);
4254 removeEdgeFromGraph(
Edge.get());
4257 Edge->Callee = NewCallee;
4258 NewCallee->CallerEdges.push_back(
Edge);
4260 OldCallee->eraseCallerEdge(
Edge.get());
4267 auto CallerEdgeAllocType = computeAllocType(ContextIdsToMove);
4268 if (ExistingEdgeToNewCallee) {
4271 ExistingEdgeToNewCallee->getContextIds().insert_range(ContextIdsToMove);
4272 ExistingEdgeToNewCallee->AllocTypes |= CallerEdgeAllocType;
4275 auto NewEdge = std::make_shared<ContextEdge>(
4276 NewCallee,
Edge->Caller, CallerEdgeAllocType, ContextIdsToMove);
4277 Edge->Caller->CalleeEdges.push_back(NewEdge);
4278 NewCallee->CallerEdges.push_back(NewEdge);
4282 NewCallee->AllocTypes |= CallerEdgeAllocType;
4284 Edge->AllocTypes = computeAllocType(
Edge->ContextIds);
4289 for (
auto &OldCalleeEdge : OldCallee->CalleeEdges) {
4290 ContextNode *CalleeToUse = OldCalleeEdge->Callee;
4294 if (CalleeToUse == OldCallee) {
4298 if (EdgeIsRecursive) {
4302 CalleeToUse = NewCallee;
4306 DenseSet<uint32_t> EdgeContextIdsToMove =
4308 set_subtract(OldCalleeEdge->getContextIds(), EdgeContextIdsToMove);
4309 OldCalleeEdge->AllocTypes =
4310 computeAllocType(OldCalleeEdge->getContextIds());
4317 if (
auto *NewCalleeEdge = NewCallee->findEdgeFromCallee(CalleeToUse)) {
4318 NewCalleeEdge->getContextIds().insert_range(EdgeContextIdsToMove);
4319 NewCalleeEdge->AllocTypes |= computeAllocType(EdgeContextIdsToMove);
4323 auto NewEdge = std::make_shared<ContextEdge>(
4324 CalleeToUse, NewCallee, computeAllocType(EdgeContextIdsToMove),
4325 EdgeContextIdsToMove);
4326 NewCallee->CalleeEdges.push_back(NewEdge);
4327 NewEdge->Callee->CallerEdges.push_back(NewEdge);
4331 OldCallee->AllocTypes = OldCallee->computeAllocType();
4333 assert((OldCallee->AllocTypes == (uint8_t)AllocationType::None) ==
4334 OldCallee->emptyContextIds());
4338 for (
const auto &OldCalleeEdge : OldCallee->CalleeEdges)
4341 for (
const auto &NewCalleeEdge : NewCallee->CalleeEdges)
4347template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4348void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
4349 moveCalleeEdgeToNewCaller(
const std::shared_ptr<ContextEdge> &
Edge,
4350 ContextNode *NewCaller) {
4351 auto *OldCallee =
Edge->Callee;
4352 auto *NewCallee = OldCallee;
4355 bool Recursive =
Edge->Caller ==
Edge->Callee;
4357 NewCallee = NewCaller;
4359 ContextNode *OldCaller =
Edge->Caller;
4360 OldCaller->eraseCalleeEdge(
Edge.get());
4364 auto ExistingEdgeToNewCaller = NewCaller->findEdgeFromCallee(NewCallee);
4366 if (ExistingEdgeToNewCaller) {
4369 ExistingEdgeToNewCaller->getContextIds().insert_range(
4370 Edge->getContextIds());
4371 ExistingEdgeToNewCaller->AllocTypes |=
Edge->AllocTypes;
4372 Edge->ContextIds.clear();
4373 Edge->AllocTypes = (uint8_t)AllocationType::None;
4374 OldCallee->eraseCallerEdge(
Edge.get());
4377 Edge->Caller = NewCaller;
4378 NewCaller->CalleeEdges.push_back(
Edge);
4380 assert(NewCallee == NewCaller);
4383 Edge->Callee = NewCallee;
4384 NewCallee->CallerEdges.push_back(
Edge);
4385 OldCallee->eraseCallerEdge(
Edge.get());
4391 NewCaller->AllocTypes |=
Edge->AllocTypes;
4398 bool IsNewNode = NewCaller->CallerEdges.empty();
4407 for (
auto &OldCallerEdge : OldCaller->CallerEdges) {
4408 auto OldCallerCaller = OldCallerEdge->Caller;
4412 OldCallerEdge->getContextIds(),
Edge->getContextIds());
4413 if (OldCaller == OldCallerCaller) {
4414 OldCallerCaller = NewCaller;
4420 set_subtract(OldCallerEdge->getContextIds(), EdgeContextIdsToMove);
4421 OldCallerEdge->AllocTypes =
4422 computeAllocType(OldCallerEdge->getContextIds());
4427 auto *ExistingCallerEdge = NewCaller->findEdgeFromCaller(OldCallerCaller);
4431 if (ExistingCallerEdge) {
4432 ExistingCallerEdge->getContextIds().insert_range(EdgeContextIdsToMove);
4433 ExistingCallerEdge->AllocTypes |=
4434 computeAllocType(EdgeContextIdsToMove);
4437 auto NewEdge = std::make_shared<ContextEdge>(
4438 NewCaller, OldCallerCaller, computeAllocType(EdgeContextIdsToMove),
4439 EdgeContextIdsToMove);
4440 NewCaller->CallerEdges.push_back(NewEdge);
4441 NewEdge->Caller->CalleeEdges.push_back(NewEdge);
4446 OldCaller->AllocTypes = OldCaller->computeAllocType();
4448 assert((OldCaller->AllocTypes == (uint8_t)AllocationType::None) ==
4449 OldCaller->emptyContextIds());
4453 for (
const auto &OldCallerEdge : OldCaller->CallerEdges)
4456 for (
const auto &NewCallerEdge : NewCaller->CallerEdges)
4462template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4463void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
4464 recursivelyRemoveNoneTypeCalleeEdges(
4465 ContextNode *Node, DenseSet<const ContextNode *> &Visited) {
4470 removeNoneTypeCalleeEdges(Node);
4472 for (
auto *Clone :
Node->Clones)
4473 recursivelyRemoveNoneTypeCalleeEdges(Clone, Visited);
4477 auto CallerEdges =
Node->CallerEdges;
4478 for (
auto &
Edge : CallerEdges) {
4480 if (
Edge->isRemoved()) {
4484 recursivelyRemoveNoneTypeCalleeEdges(
Edge->Caller, Visited);
4489template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4490void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::markBackedges() {
4495 DenseSet<const ContextNode *> Visited;
4496 DenseSet<const ContextNode *> CurrentStack;
4497 for (
auto &Entry : NonAllocationCallToContextNodeMap) {
4499 if (
Node->isRemoved())
4502 if (!
Node->CallerEdges.empty())
4504 markBackedges(Node, Visited, CurrentStack);
4510template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4511void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::markBackedges(
4512 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
4513 DenseSet<const ContextNode *> &CurrentStack) {
4514 auto I = Visited.
insert(Node);
4518 for (
auto &CalleeEdge :
Node->CalleeEdges) {
4519 auto *
Callee = CalleeEdge->Callee;
4520 if (Visited.
count(Callee)) {
4523 if (CurrentStack.
count(Callee))
4524 CalleeEdge->IsBackedge =
true;
4527 CurrentStack.
insert(Callee);
4528 markBackedges(Callee, Visited, CurrentStack);
4529 CurrentStack.
erase(Callee);
4533template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4534void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones() {
4535 DenseSet<const ContextNode *> Visited;
4536 for (
auto &Entry : AllocationCallToContextNodeMap) {
4538 identifyClones(
Entry.second, Visited,
Entry.second->getContextIds());
4541 for (
auto &Entry : AllocationCallToContextNodeMap)
4542 recursivelyRemoveNoneTypeCalleeEdges(
Entry.second, Visited);
4555template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4556void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones(
4557 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
4558 const DenseSet<uint32_t> &AllocContextIds) {
4568 if (!
Node->hasCall())
4587 auto CallerEdges =
Node->CallerEdges;
4588 for (
auto &
Edge : CallerEdges) {
4590 if (
Edge->isRemoved()) {
4596 if (
Edge->IsBackedge) {
4603 if (!Visited.
count(
Edge->Caller) && !
Edge->Caller->CloneOf) {
4604 identifyClones(
Edge->Caller, Visited, AllocContextIds);
4627 const unsigned AllocTypeCloningPriority[] = { 3, 4,
4631 [&](
const std::shared_ptr<ContextEdge> &
A,
4632 const std::shared_ptr<ContextEdge> &
B) {
4635 if (A->ContextIds.empty())
4641 if (B->ContextIds.empty())
4644 if (A->AllocTypes == B->AllocTypes)
4647 return A->Caller->NodeId < B->Caller->NodeId;
4648 return AllocTypeCloningPriority[A->AllocTypes] <
4649 AllocTypeCloningPriority[B->AllocTypes];
4652 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
4654 DenseSet<uint32_t> RecursiveContextIds;
4659 DenseSet<uint32_t> AllCallerContextIds;
4660 for (
auto &CE :
Node->CallerEdges) {
4663 AllCallerContextIds.
reserve(
CE->getContextIds().size());
4664 for (
auto Id :
CE->getContextIds())
4665 if (!AllCallerContextIds.
insert(Id).second)
4666 RecursiveContextIds.
insert(Id);
4676 auto CallerEdges =
Node->CallerEdges;
4677 for (
auto &CallerEdge : CallerEdges) {
4679 if (CallerEdge->isRemoved()) {
4683 assert(CallerEdge->Callee == Node);
4692 if (!CallerEdge->Caller->hasCall())
4697 auto CallerEdgeContextsForAlloc =
4699 if (!RecursiveContextIds.
empty())
4700 CallerEdgeContextsForAlloc =
4702 if (CallerEdgeContextsForAlloc.empty())
4705 auto CallerAllocTypeForAlloc = computeAllocType(CallerEdgeContextsForAlloc);
4709 std::vector<uint8_t> CalleeEdgeAllocTypesForCallerEdge;
4710 CalleeEdgeAllocTypesForCallerEdge.reserve(
Node->CalleeEdges.size());
4711 for (
auto &CalleeEdge :
Node->CalleeEdges)
4712 CalleeEdgeAllocTypesForCallerEdge.push_back(intersectAllocTypes(
4713 CalleeEdge->getContextIds(), CallerEdgeContextsForAlloc));
4729 assert(CallerEdge->AllocTypes != (uint8_t)AllocationType::None);
4730 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
4731 if (!CallerEdge->IsBackedge &&
4732 allocTypeToUse(CallerAllocTypeForAlloc) ==
4733 allocTypeToUse(
Node->AllocTypes) &&
4734 allocTypesMatch<DerivedCCG, FuncTy, CallTy>(
4735 CalleeEdgeAllocTypesForCallerEdge,
Node->CalleeEdges)) {
4739 if (CallerEdge->IsBackedge) {
4743 DeferredBackedges++;
4756 if (CallerEdge->IsBackedge && !CallerEdge->Caller->CloneOf &&
4757 !Visited.
count(CallerEdge->Caller)) {
4758 const auto OrigIdCount = CallerEdge->getContextIds().size();
4761 identifyClones(CallerEdge->Caller, Visited, CallerEdgeContextsForAlloc);
4762 removeNoneTypeCalleeEdges(CallerEdge->Caller);
4766 bool UpdatedEdge =
false;
4767 if (OrigIdCount > CallerEdge->getContextIds().size()) {
4768 for (
auto E :
Node->CallerEdges) {
4770 if (
E->Caller->CloneOf != CallerEdge->Caller)
4774 auto CallerEdgeContextsForAllocNew =
4776 if (CallerEdgeContextsForAllocNew.empty())
4786 CallerEdgeContextsForAlloc.swap(CallerEdgeContextsForAllocNew);
4796 if (CallerEdge->isRemoved())
4806 CallerEdgeContextsForAlloc, CallerEdge->getContextIds());
4807 if (CallerEdgeContextsForAlloc.empty())
4812 CallerAllocTypeForAlloc = computeAllocType(CallerEdgeContextsForAlloc);
4813 CalleeEdgeAllocTypesForCallerEdge.clear();
4814 for (
auto &CalleeEdge :
Node->CalleeEdges) {
4815 CalleeEdgeAllocTypesForCallerEdge.push_back(intersectAllocTypes(
4816 CalleeEdge->getContextIds(), CallerEdgeContextsForAlloc));
4822 ContextNode *Clone =
nullptr;
4823 for (
auto *CurClone :
Node->Clones) {
4824 if (allocTypeToUse(CurClone->AllocTypes) !=
4825 allocTypeToUse(CallerAllocTypeForAlloc))
4832 assert(!BothSingleAlloc ||
4833 CurClone->AllocTypes == CallerAllocTypeForAlloc);
4839 if (BothSingleAlloc || allocTypesMatchClone<DerivedCCG, FuncTy, CallTy>(
4840 CalleeEdgeAllocTypesForCallerEdge, CurClone)) {
4848 moveEdgeToExistingCalleeClone(CallerEdge, Clone,
false,
4849 CallerEdgeContextsForAlloc);
4851 Clone = moveEdgeToNewCalleeClone(CallerEdge, CallerEdgeContextsForAlloc);
4854 assert(Clone->AllocTypes != (uint8_t)AllocationType::None);
4861 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
4867void ModuleCallsiteContextGraph::updateAllocationCall(
4883 .emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofAttribute",
Call.call())
4884 <<
ore::NV(
"AllocationCall",
Call.call()) <<
" in clone "
4886 <<
" marked with memprof allocation attribute "
4887 <<
ore::NV(
"Attribute", AllocTypeString));
4890void IndexCallsiteContextGraph::updateAllocationCall(CallInfo &
Call,
4894 assert(AI->Versions.size() >
Call.cloneNo());
4899ModuleCallsiteContextGraph::getAllocationCallType(
const CallInfo &
Call)
const {
4901 if (!CB->getAttributes().hasFnAttr(
"memprof"))
4902 return AllocationType::None;
4903 StringRef AllocTypeString =
4904 CB->getAttributes().getFnAttr(
"memprof").getValueAsString();
4905 if (AllocTypeString ==
"cold")
4906 return AllocationType::Cold;
4907 if (AllocTypeString ==
"ambiguous")
4909 (uint8_t)AllocationType::Cold);
4910 return AllocationType::NotCold;
4914IndexCallsiteContextGraph::getAllocationCallType(
const CallInfo &
Call)
const {
4916 assert(AI->Versions.size() >
Call.cloneNo());
4920void ModuleCallsiteContextGraph::updateCall(CallInfo &CallerCall,
4921 FuncInfo CalleeFunc) {
4922 auto *CurF = getCalleeFunc(CallerCall.call());
4923 auto NewCalleeCloneNo = CalleeFunc.cloneNo();
4930 if (CurCalleeCloneNo != NewCalleeCloneNo) {
4932 << CurCalleeCloneNo <<
" now " << NewCalleeCloneNo
4934 MismatchedCloneAssignments++;
4937 if (NewCalleeCloneNo > 0)
4938 cast<CallBase>(CallerCall.call())->setCalledFunction(CalleeFunc.func());
4939 OREGetter(CallerCall.call()->getFunction())
4940 .emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofCall", CallerCall.call())
4941 <<
ore::NV(
"Call", CallerCall.call()) <<
" in clone "
4942 <<
ore::NV(
"Caller", CallerCall.call()->getFunction())
4943 <<
" assigned to call function clone "
4944 <<
ore::NV(
"Callee", CalleeFunc.func()));
4947void IndexCallsiteContextGraph::updateCall(CallInfo &CallerCall,
4948 FuncInfo CalleeFunc) {
4951 "Caller cannot be an allocation which should not have profiled calls");
4952 assert(CI->Clones.size() > CallerCall.cloneNo());
4953 auto NewCalleeCloneNo = CalleeFunc.cloneNo();
4954 auto &CurCalleeCloneNo = CI->Clones[CallerCall.cloneNo()];
4959 if (CurCalleeCloneNo != 0 && CurCalleeCloneNo != NewCalleeCloneNo) {
4961 << CurCalleeCloneNo <<
" now " << NewCalleeCloneNo
4963 MismatchedCloneAssignments++;
4965 CurCalleeCloneNo = NewCalleeCloneNo;
4977 SP->replaceLinkageName(MDName);
4981 TempDISubprogram NewDecl = Decl->
clone();
4982 NewDecl->replaceLinkageName(MDName);
4986CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
4988ModuleCallsiteContextGraph::cloneFunctionForCallsite(
4989 FuncInfo &Func, CallInfo &
Call, DenseMap<CallInfo, CallInfo> &CallMap,
4990 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
4995 assert(!
Func.func()->getParent()->getFunction(Name));
4996 NewFunc->setName(Name);
4998 for (
auto &Inst : CallsWithMetadataInFunc) {
5000 assert(Inst.cloneNo() == 0);
5003 OREGetter(
Func.func())
5004 .emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofClone",
Func.func())
5005 <<
"created clone " <<
ore::NV(
"NewFunction", NewFunc));
5006 return {NewFunc, CloneNo};
5009CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
5010 IndexCall>::FuncInfo
5011IndexCallsiteContextGraph::cloneFunctionForCallsite(
5012 FuncInfo &Func, CallInfo &
Call, DenseMap<CallInfo, CallInfo> &CallMap,
5013 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
5027 for (
auto &Inst : CallsWithMetadataInFunc) {
5029 assert(Inst.cloneNo() == 0);
5031 assert(AI->Versions.size() == CloneNo);
5034 AI->Versions.push_back(0);
5037 assert(CI && CI->Clones.size() == CloneNo);
5040 CI->Clones.push_back(0);
5042 CallMap[Inst] = {Inst.call(), CloneNo};
5044 return {
Func.func(), CloneNo};
5061template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5062void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::mergeClones() {
5068 DenseMap<uint32_t, ContextNode *> ContextIdToAllocationNode;
5069 for (
auto &Entry : AllocationCallToContextNodeMap) {
5071 for (
auto Id :
Node->getContextIds())
5072 ContextIdToAllocationNode[
Id] =
Node->getOrigNode();
5073 for (
auto *Clone :
Node->Clones) {
5074 for (
auto Id : Clone->getContextIds())
5075 ContextIdToAllocationNode[
Id] = Clone->getOrigNode();
5082 DenseSet<const ContextNode *> Visited;
5083 for (
auto &Entry : AllocationCallToContextNodeMap) {
5086 mergeClones(Node, Visited, ContextIdToAllocationNode);
5092 auto Clones =
Node->Clones;
5093 for (
auto *Clone : Clones)
5094 mergeClones(Clone, Visited, ContextIdToAllocationNode);
5098 dbgs() <<
"CCG after merging:\n";
5102 exportToDot(
"aftermerge");
5110template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5111void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::mergeClones(
5112 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
5113 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode) {
5123 bool FoundUnvisited =
true;
5125 while (FoundUnvisited) {
5127 FoundUnvisited =
false;
5130 auto CallerEdges =
Node->CallerEdges;
5131 for (
auto CallerEdge : CallerEdges) {
5133 if (CallerEdge->Callee != Node)
5138 FoundUnvisited =
true;
5139 mergeClones(CallerEdge->Caller, Visited, ContextIdToAllocationNode);
5143 TotalMergeInvokes++;
5144 TotalMergeIters += Iters;
5145 if (Iters > MaxMergeIters)
5146 MaxMergeIters = Iters;
5149 mergeNodeCalleeClones(Node, Visited, ContextIdToAllocationNode);
5152template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5153void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::mergeNodeCalleeClones(
5154 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
5155 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode) {
5157 if (
Node->emptyContextIds())
5162 MapVector<ContextNode *, std::vector<std::shared_ptr<ContextEdge>>>
5163 OrigNodeToCloneEdges;
5164 for (
const auto &
E :
Node->CalleeEdges) {
5169 OrigNodeToCloneEdges[
Base].push_back(
E);
5175 auto CalleeCallerEdgeLessThan = [](
const std::shared_ptr<ContextEdge> &
A,
5176 const std::shared_ptr<ContextEdge> &
B) {
5177 if (
A->Callee->CallerEdges.size() !=
B->Callee->CallerEdges.size())
5178 return A->Callee->CallerEdges.size() <
B->Callee->CallerEdges.size();
5179 if (
A->Callee->CloneOf && !
B->Callee->CloneOf)
5181 else if (!
A->Callee->CloneOf &&
B->Callee->CloneOf)
5184 return A->Callee->NodeId <
B->Callee->NodeId;
5189 for (
auto Entry : OrigNodeToCloneEdges) {
5192 auto &CalleeEdges =
Entry.second;
5193 auto NumCalleeClones = CalleeEdges.size();
5195 if (NumCalleeClones == 1)
5206 DenseSet<ContextNode *> OtherCallersToShareMerge;
5207 findOtherCallersToShareMerge(Node, CalleeEdges, ContextIdToAllocationNode,
5208 OtherCallersToShareMerge);
5213 ContextNode *MergeNode =
nullptr;
5214 DenseMap<ContextNode *, unsigned> CallerToMoveCount;
5215 for (
auto CalleeEdge : CalleeEdges) {
5216 auto *OrigCallee = CalleeEdge->Callee;
5222 if (CalleeEdge->Callee->CallerEdges.size() == 1) {
5223 MergeNode = OrigCallee;
5224 NonNewMergedNodes++;
5231 if (!OtherCallersToShareMerge.
empty()) {
5232 bool MoveAllCallerEdges =
true;
5233 for (
auto CalleeCallerE : OrigCallee->CallerEdges) {
5234 if (CalleeCallerE == CalleeEdge)
5236 if (!OtherCallersToShareMerge.
contains(CalleeCallerE->Caller)) {
5237 MoveAllCallerEdges =
false;
5243 if (MoveAllCallerEdges) {
5244 MergeNode = OrigCallee;
5245 NonNewMergedNodes++;
5252 assert(MergeNode != OrigCallee);
5253 moveEdgeToExistingCalleeClone(CalleeEdge, MergeNode,
5256 MergeNode = moveEdgeToNewCalleeClone(CalleeEdge);
5261 if (!OtherCallersToShareMerge.
empty()) {
5265 auto OrigCalleeCallerEdges = OrigCallee->CallerEdges;
5266 for (
auto &CalleeCallerE : OrigCalleeCallerEdges) {
5267 if (CalleeCallerE == CalleeEdge)
5269 if (!OtherCallersToShareMerge.
contains(CalleeCallerE->Caller))
5271 CallerToMoveCount[CalleeCallerE->Caller]++;
5272 moveEdgeToExistingCalleeClone(CalleeCallerE, MergeNode,
5276 removeNoneTypeCalleeEdges(OrigCallee);
5277 removeNoneTypeCalleeEdges(MergeNode);
5295template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5296void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
5297 findOtherCallersToShareMerge(
5299 std::vector<std::shared_ptr<ContextEdge>> &CalleeEdges,
5300 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode,
5301 DenseSet<ContextNode *> &OtherCallersToShareMerge) {
5302 auto NumCalleeClones = CalleeEdges.size();
5305 DenseMap<ContextNode *, unsigned> OtherCallersToSharedCalleeEdgeCount;
5308 unsigned PossibleOtherCallerNodes = 0;
5312 if (CalleeEdges[0]->
Callee->CallerEdges.size() < 2)
5318 DenseMap<ContextEdge *, DenseSet<ContextNode *>> CalleeEdgeToAllocNodes;
5319 for (
auto CalleeEdge : CalleeEdges) {
5320 assert(CalleeEdge->Callee->CallerEdges.size() > 1);
5323 for (
auto CalleeCallerEdges : CalleeEdge->Callee->CallerEdges) {
5324 if (CalleeCallerEdges->Caller == Node) {
5325 assert(CalleeCallerEdges == CalleeEdge);
5328 OtherCallersToSharedCalleeEdgeCount[CalleeCallerEdges->Caller]++;
5331 if (OtherCallersToSharedCalleeEdgeCount[CalleeCallerEdges->Caller] ==
5333 PossibleOtherCallerNodes++;
5337 for (
auto Id : CalleeEdge->getContextIds()) {
5338 auto *
Alloc = ContextIdToAllocationNode.
lookup(Id);
5342 MissingAllocForContextId++;
5345 CalleeEdgeToAllocNodes[CalleeEdge.get()].
insert(
Alloc);
5352 for (
auto CalleeEdge : CalleeEdges) {
5353 assert(CalleeEdge->Callee->CallerEdges.size() > 1);
5355 if (!PossibleOtherCallerNodes)
5357 auto &CurCalleeAllocNodes = CalleeEdgeToAllocNodes[CalleeEdge.get()];
5359 for (
auto &CalleeCallerE : CalleeEdge->Callee->CallerEdges) {
5361 if (CalleeCallerE == CalleeEdge)
5365 if (OtherCallersToSharedCalleeEdgeCount[CalleeCallerE->Caller] !=
5370 for (
auto Id : CalleeCallerE->getContextIds()) {
5371 auto *
Alloc = ContextIdToAllocationNode.
lookup(Id);
5376 if (!CurCalleeAllocNodes.contains(
Alloc)) {
5377 OtherCallersToSharedCalleeEdgeCount[CalleeCallerE->Caller] = 0;
5378 PossibleOtherCallerNodes--;
5385 if (!PossibleOtherCallerNodes)
5390 for (
auto &[OtherCaller,
Count] : OtherCallersToSharedCalleeEdgeCount) {
5391 if (
Count != NumCalleeClones)
5393 OtherCallersToShareMerge.
insert(OtherCaller);
5397template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5398const typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
5399CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::resolveImplicitSource(
5400 const ContextNode *Node,
const ImplicitSource &Src) {
5401 if (!Src.Source->emptyContextIds())
5407 if (
Node->hasContextId(Src.ContextId))
5409 for (
const ContextNode *
C :
Node->Clones)
5410 if (
C->hasContextId(Src.ContextId))
5415 assert(
false &&
"trimmed context id on no clone of its callsite node");
5457template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5458void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::assignImplicitCallers(
5459 ContextNode *Node,
const DenseSet<uint32_t> &TrimmedContextIds,
5460 DenseMap<ContextNode *, FuncInfo> &CallsiteToCalleeFuncCloneMap,
5461 const std::map<FuncInfo, ContextNode *> &FuncCloneToCurNodeCloneMap,
5462 ImplicitSourceMap &ImplicitSources) {
5463 auto HasEdgeToNodeFamily = [&](
const ContextNode *
N) {
5465 [&](
const std::shared_ptr<ContextEdge> &
E) {
5466 return E->Callee->getOrigNode() == Node;
5500 auto ImpliesContextIds =
5501 [&](ContextNode *
K, ContextNode *
Y,
const DenseSet<uint32_t> &Ids,
5502 DenseMap<std::pair<ContextNode *, ContextNode *>, DenseSet<uint32_t>>
5504 auto &&ImpliesContextIds) ->
bool {
5505 assert(
K->getOrigNode() ==
Y->getOrigNode());
5506 DenseSet<uint32_t> &VisitedIds = Visited[{
K,
Y}];
5507 DenseSet<uint32_t> NewIds;
5509 if (VisitedIds.
insert(Id).second)
5517 DenseSet<uint32_t> IdsOnCallerEdges;
5518 for (
auto &YEdge :
Y->CallerEdges) {
5519 DenseSet<uint32_t> IdsFromZ =
5521 if (IdsFromZ.
empty())
5524 IdsFromCallers.
push_back({YEdge->Caller, std::move(IdsFromZ)});
5528 if (IdsOnCallerEdges.
size() < NewIds.
size())
5532 for (
auto &[Z, IdsFromZ] : IdsFromCallers) {
5533 for (
auto &KEdge :
K->CallerEdges) {
5534 ContextNode *
C = KEdge->Caller;
5535 if (
C == Z ||
C->getOrigNode() !=
Z->getOrigNode())
5539 DenseSet<uint32_t> IdsNotOnC;
5540 for (
auto Id : IdsFromZ)
5541 if (!
C->hasContextId(Id))
5543 if (!IdsNotOnC.
empty() &&
5544 ImpliesContextIds(
C, Z, IdsNotOnC, Visited, ImpliesContextIds))
5553 auto SameVersion = [&](
const ContextNode *
A,
const ContextNode *
B) {
5556 if (
Node->IsAllocation)
5557 return allocTypeToUse(
A->AllocTypes) == allocTypeToUse(
B->AllocTypes);
5558 auto AIt = CallsiteToCalleeFuncCloneMap.
find(
A);
5559 auto BIt = CallsiteToCalleeFuncCloneMap.
find(
B);
5560 return AIt != CallsiteToCalleeFuncCloneMap.
end() &&
5561 BIt != CallsiteToCalleeFuncCloneMap.
end() &&
5562 AIt->second == BIt->second;
5566 DenseSet<const ContextNode *> ImplicitCallers;
5571 auto ProcessCaller = [&](
const std::shared_ptr<ContextEdge> &
Edge) {
5572 ContextNode *
Y =
Edge->Caller;
5573 ContextNode *Orig =
Y->getOrigNode();
5574 if (!
Y->hasCall() || Orig->Clones.empty())
5576 DenseSet<uint32_t> TrimmedIds =
5578 if (TrimmedIds.
empty())
5580 auto YIt = CallsiteToCalleeFuncCloneMap.
find(
Y);
5581 if (YIt == CallsiteToCalleeFuncCloneMap.
end())
5584 const FuncInfo YFuncClone = YIt->second;
5587 auto RequiredIt = FuncCloneToCurNodeCloneMap.find(YFuncClone);
5588 assert(RequiredIt != FuncCloneToCurNodeCloneMap.end());
5589 const ContextNode *
Required = RequiredIt->second;
5597 auto RecordImplicitSource = [&](
const FuncInfo &
F,
const ContextNode *Src) {
5600 if (
F.cloneNo() != 0)
5601 ImplicitSources.try_emplace({
Node,
F.cloneNo()},
5602 ImplicitSource{Src, *TrimmedIds.
begin()});
5608 if (K ==
Y || !
K->hasCall() ||
K->emptyContextIds() ||
5609 HasEdgeToNodeFamily(K) || ImplicitCallers.
contains(K))
5611 DenseMap<std::pair<ContextNode *, ContextNode *>, DenseSet<uint32_t>>
5613 if (!ImpliesContextIds(K,
Y, TrimmedIds, Visited, ImpliesContextIds))
5616 ImplicitCallers.
insert(K);
5617 auto KIt = CallsiteToCalleeFuncCloneMap.
find(K);
5618 if (KIt == CallsiteToCalleeFuncCloneMap.
end()) {
5621 CallsiteToCalleeFuncCloneMap[
K] = YFuncClone;
5622 RecordImplicitSource(YFuncClone, Required);
5623 NumImplicitCallersAssigned++;
5626 const FuncInfo KFuncClone = KIt->second;
5627 if (KFuncClone == YFuncClone) {
5629 RecordImplicitSource(YFuncClone, Required);
5632 unsigned KCloneNo = KFuncClone.cloneNo();
5633 auto KNodeCloneIt = FuncCloneToCurNodeCloneMap.find(KFuncClone);
5634 if (KNodeCloneIt == FuncCloneToCurNodeCloneMap.end()) {
5636 if (KCloneNo == 0) {
5640 if (
Node->IsAllocation) {
5641 if (allocTypeToUse(
Required->AllocTypes) == AllocationType::NotCold)
5643 }
else if (
auto It = CallsiteToCalleeFuncCloneMap.
find(Required);
5644 It != CallsiteToCalleeFuncCloneMap.
end() &&
5645 It->second.cloneNo() == 0)
5651 auto [It,
Inserted] = ImplicitSources.try_emplace(
5654 NumImplicitCallersSourced++;
5655 if (SameVersion(It->second.Source, Required))
5658 }
else if (SameVersion(KNodeCloneIt->second, Required)) {
5661 RecordImplicitSource(KFuncClone, KNodeCloneIt->second);
5665 NumImplicitCallersUnresolved++;
5671 for (
auto &
Edge :
Node->CallerEdges)
5672 ProcessCaller(
Edge);
5673 for (
auto *Clone :
Node->Clones)
5674 for (
auto &
Edge : Clone->CallerEdges)
5675 ProcessCaller(
Edge);
5719template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5720bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::assignFunctions() {
5728 DenseSet<uint32_t> TrimmedContextIds;
5729 for (
auto &NodePtr : NodeOwner) {
5730 ContextNode *
N = NodePtr.get();
5731 if (
N->IsAllocation ||
N->CalleeEdges.empty() ||
5732 (
N->CallerEdges.empty() &&
N->Clones.empty() && !
N->CloneOf))
5737 DenseSet<uint32_t> CallerIds;
5738 for (
auto &
E :
N->CallerEdges)
5740 for (
auto &CalleeEdge :
N->CalleeEdges)
5741 for (
auto Id : CalleeEdge->getContextIds())
5743 TrimmedContextIds.
insert(Id);
5745 NumTrimmedContextIds += TrimmedContextIds.
size();
5749 DenseMap<ContextNode *, FuncInfo> CallsiteToCalleeFuncCloneMap;
5753 auto RecordCalleeFuncOfCallsite = [&](ContextNode *
Caller,
5754 const FuncInfo &CalleeFunc) {
5756 CallsiteToCalleeFuncCloneMap[
Caller] = CalleeFunc;
5760 struct FuncCloneInfo {
5765 DenseMap<CallInfo, CallInfo> CallMap;
5801 struct UnassignedCallCloneInfo {
5803 const ContextNode *
Source =
nullptr;
5805 DenseMap<const ContextNode *, std::map<unsigned, UnassignedCallCloneInfo>>
5806 UnassignedCallClones;
5810 for (
auto &[Func, CallsWithMetadata] : FuncToCallsWithMetadata) {
5811 FuncInfo OrigFunc(Func);
5816 std::vector<FuncCloneInfo> FuncCloneInfos;
5823 std::vector<unsigned> FuncCloneParent;
5826 ImplicitSourceMap ImplicitSources;
5833 struct OrigCallsInfo {
5837 DenseMap<const ContextNode *, OrigCallsInfo> OrigNodeToOrigCalls;
5838 for (
auto &
Call : CallsWithMetadata) {
5839 ContextNode *
Node = getNodeForInst(
Call);
5841 OrigNodeToOrigCalls[
Node] = {
Call,
Node->MatchingCalls};
5843 for (
auto &
Call : CallsWithMetadata) {
5844 ContextNode *
Node = getNodeForInst(
Call);
5848 if (!Node ||
Node->Clones.empty())
5851 "Not having a call should have prevented cloning");
5855 std::map<FuncInfo, ContextNode *> FuncCloneToCurNodeCloneMap;
5859 auto AssignCallsiteCloneToFuncClone = [&](
const FuncInfo &FuncClone,
5861 ContextNode *CallsiteClone,
5864 FuncCloneToCurNodeCloneMap[FuncClone] = CallsiteClone;
5866 assert(FuncCloneInfos.size() > FuncClone.cloneNo());
5867 DenseMap<CallInfo, CallInfo> &CallMap =
5868 FuncCloneInfos[FuncClone.cloneNo()].CallMap;
5869 CallInfo CallClone(
Call);
5870 if (
auto It = CallMap.
find(
Call); It != CallMap.
end())
5871 CallClone = It->second;
5872 CallsiteClone->setCall(CallClone);
5878 CallsiteClone->MatchingCalls.clear();
5879 for (
const CallInfo &OrigMatchingCall :
5880 OrigNodeToOrigCalls[Node].MatchingCalls) {
5881 CallInfo CallClone(OrigMatchingCall);
5882 if (
auto It = CallMap.
find(OrigMatchingCall); It != CallMap.
end())
5883 CallClone = It->second;
5884 CallsiteClone->MatchingCalls.push_back(CallClone);
5892 auto MoveEdgeToNewCalleeCloneAndSetUp =
5893 [&](
const std::shared_ptr<ContextEdge> &
Edge) {
5894 ContextNode *OrigCallee =
Edge->Callee;
5895 ContextNode *NewClone = moveEdgeToNewCalleeClone(
Edge);
5896 removeNoneTypeCalleeEdges(NewClone);
5897 assert(NewClone->AllocTypes != (uint8_t)AllocationType::None);
5901 if (CallsiteToCalleeFuncCloneMap.
count(OrigCallee))
5902 RecordCalleeFuncOfCallsite(
5903 NewClone, CallsiteToCalleeFuncCloneMap[OrigCallee]);
5910 std::deque<ContextNode *> ClonesWorklist;
5912 if (!
Node->emptyContextIds())
5913 ClonesWorklist.push_back(Node);
5919 unsigned NodeCloneCount = 0;
5920 while (!ClonesWorklist.empty()) {
5921 ContextNode *Clone = ClonesWorklist.front();
5922 ClonesWorklist.pop_front();
5931 if (FuncCloneInfos.size() < NodeCloneCount) {
5933 if (NodeCloneCount == 1) {
5938 Clone->CallerEdges, [&](
const std::shared_ptr<ContextEdge> &
E) {
5939 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
5943 FuncCloneInfos.push_back(
5944 {OrigFunc, DenseMap<CallInfo, CallInfo>()});
5945 FuncCloneParent.push_back(0);
5946 AssignCallsiteCloneToFuncClone(
5947 OrigFunc,
Call, Clone,
5948 AllocationCallToContextNodeMap.count(
Call));
5949 for (
auto &CE : Clone->CallerEdges) {
5951 if (!
CE->Caller->hasCall())
5953 RecordCalleeFuncOfCallsite(
CE->Caller, OrigFunc);
5963 FuncInfo PreviousAssignedFuncClone;
5965 Clone->CallerEdges, [&](
const std::shared_ptr<ContextEdge> &
E) {
5966 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
5968 bool CallerAssignedToCloneOfFunc =
false;
5969 if (EI != Clone->CallerEdges.end()) {
5970 const std::shared_ptr<ContextEdge> &
Edge = *EI;
5971 PreviousAssignedFuncClone =
5972 CallsiteToCalleeFuncCloneMap[
Edge->Caller];
5973 CallerAssignedToCloneOfFunc =
true;
5978 DenseMap<CallInfo, CallInfo> NewCallMap;
5979 unsigned CloneNo = FuncCloneInfos.size();
5980 assert(CloneNo > 0 &&
"Clone 0 is the original function, which "
5981 "should already exist in the map");
5982 FuncInfo NewFuncClone = cloneFunctionForCallsite(
5983 OrigFunc,
Call, NewCallMap, CallsWithMetadata, CloneNo);
5984 FuncCloneInfos.push_back({NewFuncClone, std::move(NewCallMap)});
5987 FuncCloneParent.push_back(CallerAssignedToCloneOfFunc
5988 ? PreviousAssignedFuncClone.cloneNo()
5990 FunctionClonesAnalysis++;
5996 if (!CallerAssignedToCloneOfFunc) {
5997 AssignCallsiteCloneToFuncClone(
5998 NewFuncClone,
Call, Clone,
5999 AllocationCallToContextNodeMap.count(
Call));
6000 for (
auto &CE : Clone->CallerEdges) {
6002 if (!
CE->Caller->hasCall())
6004 RecordCalleeFuncOfCallsite(
CE->Caller, NewFuncClone);
6016 auto CallerEdges = Clone->CallerEdges;
6017 for (
auto CE : CallerEdges) {
6019 if (
CE->isRemoved()) {
6025 if (!
CE->Caller->hasCall())
6028 if (!CallsiteToCalleeFuncCloneMap.
count(
CE->Caller) ||
6032 CallsiteToCalleeFuncCloneMap[
CE->Caller] !=
6033 PreviousAssignedFuncClone)
6036 RecordCalleeFuncOfCallsite(
CE->Caller, NewFuncClone);
6049 auto CalleeEdges =
CE->Caller->CalleeEdges;
6050 for (
auto CalleeEdge : CalleeEdges) {
6053 if (CalleeEdge->isRemoved()) {
6058 ContextNode *
Callee = CalleeEdge->Callee;
6062 if (Callee == Clone || !
Callee->hasCall())
6067 if (Callee == CalleeEdge->Caller)
6069 ContextNode *NewClone =
6070 MoveEdgeToNewCalleeCloneAndSetUp(CalleeEdge);
6073 removeNoneTypeCalleeEdges(Callee);
6086 auto &OrigCalls = OrigNodeToOrigCalls[
Callee->getOrigNode()];
6087 DenseMap<CallInfo, CallInfo> &CallMap =
6088 FuncCloneInfos[NewFuncClone.cloneNo()].CallMap;
6090 CallInfo NewCall(CallMap[OrigCalls.Call]);
6092 NewClone->setCall(NewCall);
6094 NewClone->MatchingCalls.clear();
6095 for (
auto &OrigMatchingCall : OrigCalls.MatchingCalls) {
6097 CallInfo NewCall(CallMap[OrigMatchingCall]);
6099 NewClone->MatchingCalls.push_back(NewCall);
6108 auto FindFirstAvailFuncClone = [&]() {
6113 for (
auto &CF : FuncCloneInfos) {
6114 if (!FuncCloneToCurNodeCloneMap.count(CF.FuncClone))
6115 return CF.FuncClone;
6118 "Expected an available func clone for this callsite clone");
6135 std::map<FuncInfo, ContextNode *> FuncCloneToNewCallsiteCloneMap;
6136 FuncInfo FuncCloneAssignedToCurCallsiteClone;
6140 auto CloneCallerEdges = Clone->CallerEdges;
6141 for (
auto &
Edge : CloneCallerEdges) {
6145 if (
Edge->isRemoved())
6148 if (!
Edge->Caller->hasCall())
6152 if (CallsiteToCalleeFuncCloneMap.
count(
Edge->Caller)) {
6153 FuncInfo FuncCloneCalledByCaller =
6154 CallsiteToCalleeFuncCloneMap[
Edge->Caller];
6164 if ((FuncCloneToCurNodeCloneMap.count(FuncCloneCalledByCaller) &&
6165 FuncCloneToCurNodeCloneMap[FuncCloneCalledByCaller] !=
6173 (FuncCloneAssignedToCurCallsiteClone &&
6174 FuncCloneAssignedToCurCallsiteClone !=
6175 FuncCloneCalledByCaller)) {
6190 if (FuncCloneToNewCallsiteCloneMap.count(
6191 FuncCloneCalledByCaller)) {
6192 ContextNode *NewClone =
6193 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller];
6194 moveEdgeToExistingCalleeClone(
Edge, NewClone);
6196 removeNoneTypeCalleeEdges(NewClone);
6199 ContextNode *NewClone = MoveEdgeToNewCalleeCloneAndSetUp(
Edge);
6200 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller] =
6203 ClonesWorklist.push_back(NewClone);
6207 removeNoneTypeCalleeEdges(Clone);
6215 if (!FuncCloneAssignedToCurCallsiteClone) {
6216 FuncCloneAssignedToCurCallsiteClone = FuncCloneCalledByCaller;
6218 AssignCallsiteCloneToFuncClone(
6219 FuncCloneCalledByCaller,
Call, Clone,
6220 AllocationCallToContextNodeMap.count(
Call));
6224 assert(FuncCloneAssignedToCurCallsiteClone ==
6225 FuncCloneCalledByCaller);
6234 if (!FuncCloneAssignedToCurCallsiteClone) {
6235 FuncCloneAssignedToCurCallsiteClone = FindFirstAvailFuncClone();
6236 assert(FuncCloneAssignedToCurCallsiteClone);
6238 AssignCallsiteCloneToFuncClone(
6239 FuncCloneAssignedToCurCallsiteClone,
Call, Clone,
6240 AllocationCallToContextNodeMap.count(
Call));
6242 assert(FuncCloneToCurNodeCloneMap
6243 [FuncCloneAssignedToCurCallsiteClone] == Clone);
6245 RecordCalleeFuncOfCallsite(
Edge->Caller,
6246 FuncCloneAssignedToCurCallsiteClone);
6266 if (!FuncCloneAssignedToCurCallsiteClone) {
6267 FuncCloneAssignedToCurCallsiteClone = FindFirstAvailFuncClone();
6268 assert(FuncCloneAssignedToCurCallsiteClone &&
6269 "No available func clone for this callsite clone");
6270 AssignCallsiteCloneToFuncClone(
6271 FuncCloneAssignedToCurCallsiteClone,
Call, Clone,
6272 AllocationCallToContextNodeMap.contains(
Call));
6275 assignImplicitCallers(Node, TrimmedContextIds,
6276 CallsiteToCalleeFuncCloneMap,
6277 FuncCloneToCurNodeCloneMap, ImplicitSources);
6280 for (
const auto &PE :
Node->CalleeEdges)
6282 for (
const auto &CE :
Node->CallerEdges)
6284 for (
auto *Clone :
Node->Clones) {
6286 for (
const auto &PE : Clone->CalleeEdges)
6288 for (
const auto &CE : Clone->CallerEdges)
6295 FuncToNumClones[
Func] = std::max<unsigned>(1, FuncCloneInfos.size());
6296 if (FuncCloneInfos.size() < 2)
6302 for (
auto &
Call : CallsWithMetadata) {
6303 ContextNode *
Node = getNodeForInst(
Call);
6304 if (!Node || !
Node->hasCall() ||
Node->emptyContextIds())
6309 DenseMap<unsigned, const ContextNode *> FuncCloneToNodeClone;
6310 FuncCloneToNodeClone[
Node->Call.cloneNo()] =
Node;
6318 for (
auto *
C :
Node->Clones)
6319 if (!
C->emptyContextIds() ||
6320 !ImplicitSources.contains({Node, C->Call.cloneNo()}))
6321 FuncCloneToNodeClone[
C->Call.cloneNo()] =
C;
6324 if (FuncCloneToNodeClone.
size() >= FuncCloneInfos.size())
6327 for (
auto &FC : FuncCloneInfos) {
6328 unsigned I =
FC.FuncClone.cloneNo();
6331 if (
I == 0 || FuncCloneToNodeClone.
contains(
I)) {
6339 auto &
Info = UnassignedCallClones[
Node][
I];
6340 auto &CallVector =
Info.Calls;
6341 for (
unsigned P =
I;;
P = FuncCloneParent[
P]) {
6342 if (
auto It = ImplicitSources.find({Node, P});
6343 It != ImplicitSources.end()) {
6344 Info.Source = resolveImplicitSource(Node, It->second);
6347 if (
auto It = FuncCloneToNodeClone.
find(
P);
6348 It != FuncCloneToNodeClone.
end()) {
6349 Info.Source = It->second;
6355 DenseMap<CallInfo, CallInfo> &CallMap =
FC.CallMap;
6356 if (
auto It = CallMap.
find(
Call); It != CallMap.
end()) {
6357 CallInfo CallClone = It->second;
6358 CallVector.push_back(CallClone);
6362 assert(
false &&
"Expected to find call in CallMap");
6368 for (
const CallInfo &OrigMatchingCall :
6369 OrigNodeToOrigCalls[Node].MatchingCalls) {
6370 if (
auto It = CallMap.
find(OrigMatchingCall); It != CallMap.
end()) {
6371 CallInfo CallClone = It->second;
6372 CallVector.push_back(CallClone);
6376 assert(
false &&
"Expected to find call in CallMap");
6384 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
6386 auto UpdateCalls = [&](ContextNode *
Node,
6387 DenseSet<const ContextNode *> &Visited,
6388 auto &&UpdateCalls) {
6389 auto Inserted = Visited.insert(Node);
6393 for (
auto *Clone :
Node->Clones)
6394 UpdateCalls(Clone, Visited, UpdateCalls);
6396 for (
auto &
Edge :
Node->CallerEdges)
6397 UpdateCalls(
Edge->Caller, Visited, UpdateCalls);
6401 if (!
Node->hasCall() ||
Node->emptyContextIds())
6407 auto GetUnassignedCallClones = [&](ContextNode *
Node) {
6410 auto UnassignedIt = UnassignedCallClones.
find(Node);
6411 if (UnassignedIt == UnassignedCallClones.
end())
6413 DenseSet<unsigned> NodeCallClones;
6414 for (
auto *
C :
Node->Clones)
6415 if (!
C->emptyContextIds())
6416 NodeCallClones.
insert(
C->Call.cloneNo());
6417 for (
auto &[CloneNo, Info] : UnassignedIt->second) {
6421 if (NodeCallClones.
contains(CloneNo))
6428 if (
Node->IsAllocation) {
6429 auto GetAllocTypeToUse = [&](
const ContextNode *
Node) {
6430 auto AT = allocTypeToUse(
Node->AllocTypes);
6442 !ContextIdToContextSizeInfos.
empty()) {
6445 for (
auto Id :
Node->getContextIds()) {
6446 auto TypeI = ContextIdToAllocationType.
find(Id);
6447 assert(TypeI != ContextIdToAllocationType.
end());
6448 auto CSI = ContextIdToContextSizeInfos.
find(Id);
6449 if (CSI != ContextIdToContextSizeInfos.
end()) {
6450 for (
auto &Info : CSI->second) {
6452 if (TypeI->second == AllocationType::Cold)
6453 TotalCold +=
Info.TotalSize;
6458 AT = AllocationType::Cold;
6462 updateAllocationCall(
Node->Call, GetAllocTypeToUse(Node));
6464 OrigAllocAndCloneToNode[{
Node->getOrigNode(),
Node->Call.cloneNo()}] =
6469 for (
auto &[Source, Calls] : GetUnassignedCallClones(Node)) {
6470 auto AT = GetAllocTypeToUse(Source);
6471 for (
auto &
Call : Calls) {
6472 updateAllocationCall(
Call, AT);
6475 OrigAllocAndCloneToNode[{
Node->getOrigNode(),
Call.cloneNo()}] =
6482 auto CalleeFuncIt = CallsiteToCalleeFuncCloneMap.
find(Node);
6483 if (CalleeFuncIt != CallsiteToCalleeFuncCloneMap.
end()) {
6484 auto &CalleeFunc = CalleeFuncIt->second;
6485 updateCall(
Node->Call, CalleeFunc);
6487 OrigNodeAndCloneToCalleeClone[{
6488 Node->getOrigNode(),
Node->Call.cloneNo()}] = CalleeFunc.cloneNo();
6490 for (
auto &
Call :
Node->MatchingCalls)
6491 updateCall(
Call, CalleeFunc);
6497 for (
auto &[Source, Calls] : GetUnassignedCallClones(Node)) {
6498 auto It = CallsiteToCalleeFuncCloneMap.
find(Source);
6500 if (It == CallsiteToCalleeFuncCloneMap.
end())
6502 if (It == CallsiteToCalleeFuncCloneMap.
end())
6504 for (
auto &
Call : Calls) {
6505 updateCall(
Call, It->second);
6507 OrigNodeAndCloneToCalleeClone[{
Node->getOrigNode(),
Call.cloneNo()}] =
6508 It->second.cloneNo();
6518 DenseSet<const ContextNode *> Visited;
6519 for (
auto &Entry : AllocationCallToContextNodeMap)
6520 UpdateCalls(
Entry.second, Visited, UpdateCalls);
6542 for (
auto [Index, SN] :
enumerate(FS->callsites())) {
6547 SN.Clones.size() >
I &&
6548 "Callsite summary has fewer entries than other summaries in function");
6549 if (SN.Clones.size() <=
I || !SN.Clones[
I])
6551 AddRecord(
'c', Index, SN.Clones[
I]);
6554 for (
auto [Index, AN] :
enumerate(FS->allocs())) {
6558 assert(AN.Versions.size() >
I &&
6559 "Alloc summary has fewer entries than other summaries in function");
6560 if (AN.Versions.size() <=
I ||
6563 AddRecord(
'a', Index, AN.Versions[
I]);
6572 for (
auto &SN : FS->callsites()) {
6573 assert(SN.Clones.size() >
I && SN.Clones.size() > J &&
6574 "Callsite summary has fewer entries than other summaries in "
6576 if (SN.Clones[
I] != SN.Clones[J])
6579 for (
auto &AN : FS->allocs()) {
6580 assert(AN.Versions.size() >
I && AN.Versions.size() > J &&
6581 "Alloc summary has fewer entries than other summaries in function");
6582 if (AN.Versions[
I] != AN.Versions[J])
6598 NewGV->takeName(DeclGV);
6605 auto CloneFuncAliases = [&](
Function *NewF,
unsigned I) {
6606 if (!FuncToAliasMap.count(&
F))
6608 for (
auto *
A : FuncToAliasMap[&
F]) {
6610 auto *PrevA = M.getNamedAlias(AliasName);
6612 A->getType()->getPointerAddressSpace(),
6613 A->getLinkage(), AliasName, NewF);
6614 NewA->copyAttributesFrom(
A);
6616 TakeDeclNameAndReplace(PrevA, NewA);
6625 FunctionsClonedThinBackend++;
6642 for (
unsigned I = 1;
I < NumClones;
I++) {
6643 VMaps.
emplace_back(std::make_unique<ValueToValueMapTy>());
6649 if (
auto It = HashToFunc.
find(Hash); It != HashToFunc.
end()) {
6650 FunctionCloneDuplicatesThinBackend++;
6651 auto [Func, OrigI] = It->second;
6653 "Duplicate clone hash collision");
6654 if (Func->hasAvailableExternallyLinkage()) {
6660 auto Decl = M.getOrInsertFunction(Name, Func->getFunctionType());
6662 <<
"created clone decl " <<
ore::NV(
"Decl", Decl.getCallee()));
6665 auto *PrevF = M.getFunction(Name);
6668 TakeDeclNameAndReplace(PrevF, Alias);
6670 <<
"created clone alias " <<
ore::NV(
"Alias", Alias));
6673 CloneFuncAliases(Func,
I);
6677 HashToFunc[Hash] = {NewF,
I};
6678 FunctionClonesThinBackend++;
6681 for (
auto &BB : *NewF) {
6682 for (
auto &Inst : BB) {
6683 Inst.setMetadata(LLVMContext::MD_memprof,
nullptr);
6684 Inst.setMetadata(LLVMContext::MD_callsite,
nullptr);
6687 auto *PrevF = M.getFunction(Name);
6689 TakeDeclNameAndReplace(PrevF, NewF);
6691 NewF->setName(Name);
6694 <<
"created clone " <<
ore::NV(
"NewFunction", NewF));
6697 CloneFuncAliases(NewF,
I);
6706static std::optional<GlobalValue::GUID>
6708 if (
auto *MD =
F.getMetadata(
"thinlto_alias_guid"))
6710 return std::nullopt;
6717 const Function *CallingFunc =
nullptr) {
6721 assert(AliasVI &&
"Expected ValueInfo for imported alias GUID");
6744 MDNode *SrcFileMD = GO ? GO->getMetadata(
"thinlto_src_file") :
nullptr;
6754 SrcFileMD = CallingFunc->getMetadata(
"thinlto_src_file");
6761 StringRef SrcFile = M.getSourceFileName();
6798 &OrigNameGUIDToTailCallCallsite,
6802 auto End = MapTailCallCalleeVIToCallsite.
end();
6806 auto It = MapTailCallCalleeVIToCallsite.
find(VI);
6815 auto It = MapTailCallCalleeVIToCallsite.
find(LocalVI);
6825 if (!OrigNameGUIDToTailCallCallsite) {
6828 OrigNameGUIDToTailCallCallsite.emplace();
6829 for (
const auto &[CalleeVI, Callsite] : MapTailCallCalleeVIToCallsite) {
6838 AliasVIToGV.emplace();
6844 AliasVIToGV->try_emplace(VI, &
A);
6847 Callee = AliasVIToGV->lookup(CalleeVI);
6853 auto [It, Inserted] = OrigNameGUIDToTailCallCallsite->try_emplace(
6857 if (!Inserted && It->second != &Callsite)
6858 It->second =
nullptr;
6861 return OrigNameGUIDToTailCallCallsite->lookup(CandidateGUID);
6864bool MemProfContextDisambiguation::initializeIndirectCallPromotionInfo(
6866 ICallAnalysis = std::make_unique<ICallPromotionAnalysis>();
6867 Symtab = std::make_unique<InstrProfSymtab>();
6885 AliaseeGUIDToImportedAlias.reset();
6886 if (
Error E = Symtab->create(M,
true,
false,
6888 std::string SymtabFailure =
toString(std::move(
E));
6889 M.getContext().emitError(
"Failed to create symtab: " + SymtabFailure);
6902 auto MIBIter = AllocNode.
MIBs.begin();
6903 for (
auto &MDOp : MemProfMD->
operands()) {
6912 if (MIBIter->StackIdIndices.empty()) {
6916 auto StackIdIndexIter = MIBIter->StackIdIndices.begin();
6921 auto ContextIterBegin =
6925 (ContextIterBegin != StackContext.
end() && *ContextIterBegin == 0) ? 1
6927 for (
auto ContextIter = ContextIterBegin; ContextIter != StackContext.
end();
6932 if (LastStackContextId == *ContextIter)
6934 LastStackContextId = *ContextIter;
6935 assert(StackIdIndexIter != MIBIter->StackIdIndices.end());
6945bool MemProfContextDisambiguation::applyImport(
Module &M) {
6952 std::map<const Function *, SmallPtrSet<const GlobalAlias *, 1>>
6954 for (
auto &
A :
M.aliases()) {
6955 auto *Aliasee =
A.getAliaseeObject();
6957 FuncToAliasMap[
F].insert(&
A);
6960 if (!initializeIndirectCallPromotionInfo(M))
6966 std::optional<DenseMap<ValueInfo, const GlobalAlias *>> AliasVIToGV;
6972 OptimizationRemarkEmitter ORE(&
F);
6975 bool ClonesCreated =
false;
6976 unsigned NumClonesCreated = 0;
6977 auto CloneFuncIfNeeded = [&](
unsigned NumClones, FunctionSummary *
FS) {
6987 if (ClonesCreated) {
6988 assert(NumClonesCreated == NumClones);
6995 ClonesCreated =
true;
6996 NumClonesCreated = NumClones;
6999 auto CloneCallsite = [&](
const CallsiteInfo &StackNode, CallBase *CB,
7000 Function *CalledFunction, FunctionSummary *
FS) {
7002 CloneFuncIfNeeded(StackNode.
Clones.
size(), FS);
7014 if (CalledFunction != CB->getCalledOperand() &&
7015 (!GA || CalledFunction != GA->getAliaseeObject())) {
7016 SkippedCallsCloning++;
7022 auto CalleeOrigName = CalledFunction->getName();
7023 for (
unsigned J = 0; J < StackNode.
Clones.
size(); J++) {
7026 if (J > 0 && VMaps[J - 1]->
empty())
7030 if (!StackNode.
Clones[J])
7032 auto NewF =
M.getOrInsertFunction(
7034 CalledFunction->getFunctionType());
7048 ORE.emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofCall", CBClone)
7049 <<
ore::NV(
"Call", CBClone) <<
" in clone "
7051 <<
" assigned to call function clone "
7052 <<
ore::NV(
"Callee", NewF.getCallee()));
7066 ImportSummary->findSummaryInModule(TheFnVI,
M.getModuleIdentifier());
7070 auto SrcModuleMD =
F.getMetadata(
"thinlto_src_module");
7072 "enable-import-metadata is needed to emit thinlto_src_module");
7073 StringRef SrcModule =
7076 if (GVS->modulePath() == SrcModule) {
7077 GVSummary = GVS.get();
7081 assert(GVSummary && GVSummary->modulePath() == SrcModule);
7091 if (
FS->allocs().empty() &&
FS->callsites().empty())
7094 auto SI =
FS->callsites().begin();
7095 auto AI =
FS->allocs().begin();
7100 DenseMap<ValueInfo, CallsiteInfo> MapTailCallCalleeVIToCallsite;
7103 for (
auto CallsiteIt =
FS->callsites().rbegin();
7104 CallsiteIt !=
FS->callsites().rend(); CallsiteIt++) {
7105 auto &Callsite = *CallsiteIt;
7109 if (!Callsite.StackIdIndices.empty())
7111 MapTailCallCalleeVIToCallsite.
insert({Callsite.Callee, Callsite});
7115 std::optional<DenseMap<uint64_t, const CallsiteInfo *>>
7116 OrigNameGUIDToTailCallCallsite;
7124 for (
auto &BB :
F) {
7125 for (
auto &
I : BB) {
7131 auto *CalledValue = CB->getCalledOperand();
7132 auto *CalledFunction = CB->getCalledFunction();
7133 if (CalledValue && !CalledFunction) {
7134 CalledValue = CalledValue->stripPointerCasts();
7141 assert(!CalledFunction &&
7142 "Expected null called function in callsite for alias");
7146 CallStack<MDNode, MDNode::op_iterator> CallsiteContext(
7147 I.getMetadata(LLVMContext::MD_callsite));
7148 auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof);
7154 if (CB->getAttributes().hasFnAttr(
"memprof") && !MemProfMD) {
7155 CB->getAttributes().getFnAttr(
"memprof").getValueAsString() ==
"cold"
7156 ? AllocTypeColdThinBackend++
7157 : AllocTypeNotColdThinBackend++;
7158 OrigAllocsThinBackend++;
7159 AllocVersionsThinBackend++;
7160 if (!MaxAllocVersionsThinBackend)
7161 MaxAllocVersionsThinBackend = 1;
7168 auto &AllocNode = *(AI++);
7176 CloneFuncIfNeeded(AllocNode.Versions.size(), FS);
7178 OrigAllocsThinBackend++;
7179 AllocVersionsThinBackend += AllocNode.Versions.size();
7180 if (MaxAllocVersionsThinBackend < AllocNode.Versions.size())
7181 MaxAllocVersionsThinBackend = AllocNode.Versions.size();
7193 if (AllocNode.Versions.size() == 1 &&
7195 UnclonableAllocsThinBackend++;
7198 for (
unsigned J = 0; J < AllocNode.Versions.size(); J++) {
7201 if (J > 0 && VMaps[J - 1]->
empty())
7204 if (AllocNode.Versions[J] == (uint8_t)AllocationType::None)
7212 AllocTy = AllocationType::NotCold;
7214 if (AllocTy == AllocationType::Cold)
7215 AllocTypeColdThinBackend++;
7216 else if (IsAmbiguous)
7217 AllocTypeAmbiguousThinBackend++;
7219 AllocTypeNotColdThinBackend++;
7239 ORE.emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofAttribute", CBClone)
7240 <<
ore::NV(
"AllocationCall", CBClone) <<
" in clone "
7242 <<
" marked with memprof allocation attribute "
7243 <<
ore::NV(
"Attribute", AllocTypeString));
7245 }
else if (!CallsiteContext.empty()) {
7246 if (!CalledFunction) {
7250 assert(!CI || !CI->isInlineAsm());
7260 auto NumClones = recordICPInfo(
7262 [&](
const InstrProfValueData &Candidate) {
7263 assert(SI !=
FS->callsites().end());
7265 auto CalleeValueInfo =
7266 ImportSummary->getValueInfo(Candidate.Value);
7268 ImportSummary->getGUIDFromOriginalID(Candidate.Value);
7276 assert(!CalleeValueInfo ||
SI->Callee == CalleeValueInfo ||
7277 (
SI->Callee &&
SI->Callee.getGUID() == LocalGUID));
7286 CloneFuncIfNeeded(NumClones, FS);
7291 assert(SI !=
FS->callsites().end());
7292 auto &StackNode = *(
SI++);
7298 for (
auto StackId : CallsiteContext) {
7300 assert(ImportSummary->getStackIdAtIndex(*StackIdIndexIter) ==
7306 CloneCallsite(StackNode, CB, CalledFunction, FS);
7308 }
else if (CB->isTailCall() && CalledFunction) {
7313 if (CalleeVI && MapTailCallCalleeVIToCallsite.
count(CalleeVI)) {
7314 auto Callsite = MapTailCallCalleeVIToCallsite.
find(CalleeVI);
7315 assert(Callsite != MapTailCallCalleeVIToCallsite.
end());
7316 CloneCallsite(Callsite->second, CB, CalledFunction, FS);
7318 }
else if (CB->isTailCall() && !CalledFunction &&
7319 !MapTailCallCalleeVIToCallsite.
empty()) {
7325 auto PrevNumICallAnalysisInfo = ICallAnalysisInfo.
size();
7326 auto NumClones = recordICPInfo(
7328 [&](
const InstrProfValueData &Candidate) {
7330 Candidate.Value, MapTailCallCalleeVIToCallsite,
7331 OrigNameGUIDToTailCallCallsite, AliasVIToGV, M,
7332 ImportSummary, *Symtab);
7335 if (ICallAnalysisInfo.
size() > PrevNumICallAnalysisInfo)
7336 IndirectTailCallsRecordedForICPThinBackend++;
7338 CloneFuncIfNeeded(NumClones, FS);
7344 performICP(M, VMaps, ICallAnalysisInfo, ORE);
7354 for (
auto &BB :
F) {
7355 for (
auto &
I : BB) {
7358 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
7359 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
7367unsigned MemProfContextDisambiguation::recordICPInfo(
7369 function_ref<
const CallsiteInfo *(
const InstrProfValueData &)> GetCallsite,
7372 uint32_t NumCandidates;
7374 auto CandidateProfileData =
7375 ICallAnalysis->getPromotionCandidatesForInstruction(
7376 CB, TotalCount, NumCandidates,
7378 if (CandidateProfileData.empty())
7384 bool ICPNeeded =
false;
7385 unsigned NumClones = 0;
7387 for (
const auto &Candidate : CandidateProfileData) {
7388 const CallsiteInfo *Callsite = GetCallsite(Candidate);
7396 [](
unsigned CloneNo) { return CloneNo != 0; });
7406 ICallAnalysisInfo.
push_back({CB, CandidateProfileData.vec(), NumCandidates,
7407 TotalCount, NumClones, std::move(Callsites)});
7411void MemProfContextDisambiguation::performICP(
7414 OptimizationRemarkEmitter &ORE) {
7421 for (
auto &Info : ICallAnalysisInfo) {
7423 auto TotalCount =
Info.TotalCount;
7424 unsigned NumClones =
Info.NumClones;
7427 assert(
Info.CandidateProfileData.size() ==
Info.Callsites.size());
7428 for (
unsigned I = 0;
I <
Info.CandidateProfileData.size();
I++) {
7429 auto &Candidate =
Info.CandidateProfileData[
I];
7430 const CallsiteInfo *StackNode =
Info.Callsites[
I];
7438 Function *TargetFunction = Symtab->getFunction(Candidate.Value);
7449 if (!TargetFunction && StackNode && StackNode->
Callee &&
7460 if (!TargetFunction) {
7461 if (!AliaseeGUIDToImportedAlias) {
7462 AliaseeGUIDToImportedAlias.emplace();
7466 if (
auto AliaseeGUID = Fn.getGUIDIfAssigned())
7467 AliaseeGUIDToImportedAlias->try_emplace(*AliaseeGUID, &Fn);
7470 TargetFunction = AliaseeGUIDToImportedAlias->lookup(Candidate.Value);
7471 if (!TargetFunction && StackNode && StackNode->
Callee &&
7474 AliaseeGUIDToImportedAlias->lookup(StackNode->
Callee.
getGUID());
7476 if (TargetFunction ==
nullptr ||
7484 return OptimizationRemarkMissed(
DEBUG_TYPE,
"UnableToFindTarget", CB)
7485 <<
"Memprof cannot promote indirect call: target with md5sum "
7486 <<
ore::NV(
"target md5sum", Candidate.Value) <<
" not found";
7491 RemainingCandidates.
push_back(Candidate);
7496 const char *Reason =
nullptr;
7499 return OptimizationRemarkMissed(
DEBUG_TYPE,
"UnableToPromote", CB)
7500 <<
"Memprof cannot promote indirect call to "
7501 <<
ore::NV(
"TargetFunction", TargetFunction)
7502 <<
" with count of " <<
ore::NV(
"TotalCount", TotalCount)
7505 RemainingCandidates.
push_back(Candidate);
7514 CallBase *CBClone = CB;
7515 for (
unsigned J = 0; J < NumClones; J++) {
7518 if (J > 0 && VMaps[J - 1]->
empty())
7528 TotalCount, isSamplePGO, &ORE);
7529 auto *TargetToUse = TargetFunction;
7532 if (StackNode && StackNode->
Clones[J]) {
7551 <<
ore::NV(
"Call", CBClone) <<
" in clone "
7553 <<
" promoted and assigned to call function clone "
7554 <<
ore::NV(
"Callee", TargetToUse));
7558 TotalCount -= Candidate.Count;
7562 CallBase *CBClone = CB;
7563 for (
unsigned J = 0; J < NumClones; J++) {
7566 if (J > 0 && VMaps[J - 1]->
empty())
7572 CBClone->
setMetadata(LLVMContext::MD_prof,
nullptr);
7575 if (TotalCount != 0)
7577 IPVK_IndirectCallTarget,
Info.NumCandidates);
7582template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
7583bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::process(
7584 function_ref<
void(StringRef, StringRef,
const Twine &)> EmitRemark,
7585 bool AllowExtraAnalysis) {
7587 dbgs() <<
"CCG before cloning:\n";
7591 exportToDot(
"postbuild");
7600 capturePreCloningContextInfo();
7609 dbgs() <<
"CCG after cloning:\n";
7613 exportToDot(
"cloned");
7615 bool Changed = assignFunctions();
7618 dbgs() <<
"CCG after assigning function clones:\n";
7622 exportToDot(
"clonefuncassign");
7631 populateFunctionsWithCallers();
7632 printTotalSizes(
errs(), EmitRemark);
7638bool MemProfContextDisambiguation::processModule(
7640 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter) {
7645 return applyImport(M);
7658 ModuleCallsiteContextGraph CCG(M, OREGetter);
7661 return CCG.process();
7666 : ImportSummary(Summary), isSamplePGO(isSamplePGO) {
7671 "-memprof-dot-scope=alloc requires -memprof-dot-alloc-id");
7675 "-memprof-dot-scope=context requires -memprof-dot-context-id");
7679 "-memprof-dot-scope=all can't have both -memprof-dot-alloc-id and "
7680 "-memprof-dot-context-id");
7681 if (ImportSummary) {
7691 auto ReadSummaryFile =
7693 if (!ReadSummaryFile) {
7700 if (!ImportSummaryForTestingOrErr) {
7706 ImportSummaryForTesting = std::move(*ImportSummaryForTestingOrErr);
7707 ImportSummary = ImportSummaryForTesting.get();
7716 if (!processModule(M, OREGetter))
7739 for (
auto &
I : Index) {
7740 auto VI = Index.getValueInfo(
I);
7741 for (
auto &S : VI.getSummaryList()) {
7745 !isPrevailing(VI.getGUID(), S.get()))
7748 if (!FS || FS->callsites().empty())
7750 CalleeToEdge.
clear();
7751 for (
auto &CI : FS->callsites()) {
7752 if (!CI.Callee ||
llvm::all_of(CI.Clones, [](
unsigned CloneNo) {
7753 return CloneNo == 0;
7760 NumClonedCalleeCallsites++;
7762 if (CalleeToEdge.
empty())
7763 for (
auto &[CalleeVI, Edge] : FS->mutableCalls())
7764 CalleeToEdge[CalleeVI] = &Edge;
7765 auto It = CalleeToEdge.
find(CI.Callee);
7766 if (It == CalleeToEdge.
end())
7773 if (!Edge->hasIndirectCall())
7775 NumClonedCalleeIndirectCallsites++;
7776 if (!Edge->requiresDeclImport()) {
7777 Edge->setRequiresDeclImport(
true);
7778 NumClonedCalleeEdgesMarkedRequiresDeclImport++;
7799 bool AllowExtraAnalysis =
7804 IndexCallsiteContextGraph CCG(Index, isPrevailing);
7805 Changed = CCG.process(EmitRemark, AllowExtraAnalysis);
7828 for (
auto &BB :
F) {
7829 for (
auto &
I : BB) {
7833 if (CI->hasFnAttr(
"memprof")) {
7834 CI->removeFnAttr(
"memprof");
7837 if (!CI->hasMetadata(LLVMContext::MD_callsite)) {
7838 assert(!CI->hasMetadata(LLVMContext::MD_memprof));
7844 CI->setMetadata(LLVMContext::MD_memprof,
nullptr);
7845 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 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.
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...
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)
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...