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);
1844 if (
Edge->getContextIds().empty()) {
1845 removeEdgeFromGraph(
Edge.get(), &EI, TowardsCallee);
1852template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1854 const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &Edge) {
1858 assert(!Edge->ContextIds.empty());
1861template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1863 bool CheckEdges =
true) {
1864 if (
Node->isRemoved())
1868 auto NodeContextIds =
Node->getContextIds();
1872 if (
Node->CallerEdges.size()) {
1874 Node->CallerEdges.front()->ContextIds);
1878 set_union(CallerEdgeContextIds, Edge->ContextIds);
1885 NodeContextIds == CallerEdgeContextIds ||
1888 if (
Node->CalleeEdges.size()) {
1890 Node->CalleeEdges.front()->ContextIds);
1894 set_union(CalleeEdgeContextIds, Edge->getContextIds());
1900 NodeContextIds == CalleeEdgeContextIds);
1909 for (
const auto &
E :
Node->CalleeEdges)
1915template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1916void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
1917 assignStackNodesPostOrder(ContextNode *Node,
1918 DenseSet<const ContextNode *> &Visited,
1919 DenseMap<
uint64_t, std::vector<CallContextInfo>>
1920 &StackIdToMatchingCalls,
1921 DenseMap<CallInfo, CallInfo> &CallToMatchingCall,
1922 const DenseSet<uint32_t> &ImportantContextIds) {
1930 auto CallerEdges =
Node->CallerEdges;
1931 for (
auto &
Edge : CallerEdges) {
1933 if (
Edge->isRemoved()) {
1937 assignStackNodesPostOrder(
Edge->Caller, Visited, StackIdToMatchingCalls,
1938 CallToMatchingCall, ImportantContextIds);
1947 if (
Node->IsAllocation ||
1948 !StackIdToMatchingCalls.count(
Node->OrigStackOrAllocId))
1951 auto &Calls = StackIdToMatchingCalls[
Node->OrigStackOrAllocId];
1955 if (Calls.size() == 1) {
1956 auto &[
Call, StackNodes,
Func, SavedContextIds] = Calls[0];
1957 if (StackNodes.size() == 1) {
1958 assert(SavedContextIds.empty());
1960 assert(Node == StackNodes[0]);
1961 if (
Node->Recursive)
1964 NonAllocationCallToContextNodeMap[
Call] =
Node;
1966 recordStackNode(StackNodes, Node,
Node->getContextIds(),
1967 ImportantContextIds);
1976 ContextNode *LastNode = getNodeForStackId(LastId);
1979 assert(LastNode == Node);
1981 ContextNode *LastNode =
Node;
1986 DenseSet<uint32_t> LastNodeContextIds = LastNode->getContextIds();
1988 [[maybe_unused]]
bool PrevIterCreatedNode =
false;
1989 bool CreatedNode =
false;
1990 for (
unsigned I = 0;
I < Calls.size();
1991 I++, PrevIterCreatedNode = CreatedNode) {
1992 CreatedNode =
false;
1993 auto &[
Call, StackNodes,
Func, SavedContextIds] = Calls[
I];
1996 if (SavedContextIds.empty()) {
2003 auto MatchingCall = CallToMatchingCall[
Call];
2004 if (!NonAllocationCallToContextNodeMap.contains(MatchingCall)) {
2008 assert(
I > 0 && !PrevIterCreatedNode);
2011 NonAllocationCallToContextNodeMap[MatchingCall]->MatchingCalls.push_back(
2016 assert(LastNode == StackNodes.back());
2025 ContextNode *PrevNode = LastNode;
2029 for (
auto NodeIter = StackNodes.rbegin() + 1; NodeIter != StackNodes.rend();
2031 ContextNode *CurNode = *NodeIter;
2035 assert(!CurNode->Recursive);
2037 auto *
Edge = CurNode->findEdgeFromCaller(PrevNode);
2049 if (SavedContextIds.empty()) {
2058 ContextNode *NewNode = createNewNode(
false, Func,
Call);
2059 NonAllocationCallToContextNodeMap[
Call] = NewNode;
2061 NewNode->AllocTypes = computeAllocType(SavedContextIds);
2063 ContextNode *FirstNode = StackNodes[0];
2069 connectNewNode(NewNode, FirstNode,
true, SavedContextIds);
2074 connectNewNode(NewNode, LastNode,
false, SavedContextIds);
2079 for (ContextNode *CurNode : StackNodes) {
2086 auto *PrevEdge = CurNode->findEdgeFromCallee(PrevNode);
2093 set_subtract(PrevEdge->getContextIds(), SavedContextIds);
2094 if (PrevEdge->getContextIds().empty())
2095 removeEdgeFromGraph(PrevEdge);
2100 CurNode->AllocTypes = CurNode->CalleeEdges.empty()
2101 ? (uint8_t)AllocationType::None
2102 : CurNode->computeAllocType();
2106 recordStackNode(StackNodes, NewNode, SavedContextIds, ImportantContextIds);
2110 for (ContextNode *CurNode : StackNodes) {
2119template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2120void CallsiteContextGraph<DerivedCCG, FuncTy,
2121 CallTy>::fixupImportantContexts() {
2122 if (ImportantContextIdInfo.
empty())
2126 NumImportantContextIds = ImportantContextIdInfo.
size();
2132 exportToDot(
"beforestackfixup");
2157 for (
auto &[CurContextId, Info] : ImportantContextIdInfo) {
2158 if (
Info.StackIdsToNode.empty())
2161 ContextNode *PrevNode =
nullptr;
2162 ContextNode *CurNode =
nullptr;
2163 DenseSet<const ContextEdge *> VisitedEdges;
2164 ArrayRef<uint64_t> AllStackIds(
Info.StackIds);
2167 for (
unsigned I = 0;
I < AllStackIds.size();
I++, PrevNode = CurNode) {
2171 auto LenToEnd = AllStackIds.size() -
I;
2179 auto CheckStackIds = AllStackIds.slice(
I, Len);
2180 auto EntryIt =
Info.StackIdsToNode.find(CheckStackIds);
2181 if (EntryIt ==
Info.StackIdsToNode.end())
2183 CurNode = EntryIt->second;
2200 auto *CurEdge = PrevNode->findEdgeFromCaller(CurNode);
2203 if (CurEdge->getContextIds().insert(CurContextId).second) {
2204 NumFixupEdgeIdsInserted++;
2209 NumFixupEdgesAdded++;
2210 DenseSet<uint32_t> ContextIds({CurContextId});
2211 auto AllocType = computeAllocType(ContextIds);
2212 auto NewEdge = std::make_shared<ContextEdge>(
2213 PrevNode, CurNode,
AllocType, std::move(ContextIds));
2214 PrevNode->CallerEdges.push_back(NewEdge);
2215 CurNode->CalleeEdges.push_back(NewEdge);
2217 CurEdge = NewEdge.get();
2220 VisitedEdges.
insert(CurEdge);
2223 for (
auto &
Edge : PrevNode->CallerEdges) {
2227 Edge->getContextIds().erase(CurContextId);
2235template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2236void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::updateStackNodes() {
2244 DenseMap<uint64_t, std::vector<CallContextInfo>> StackIdToMatchingCalls;
2245 for (
auto &[Func, CallsWithMetadata] : FuncToCallsWithMetadata) {
2246 for (
auto &
Call : CallsWithMetadata) {
2248 if (AllocationCallToContextNodeMap.count(
Call))
2250 std::vector<ContextNode *> StackNodes = getStackNodesForCall(
Call.call());
2253 if (StackNodes.empty())
2257 uint64_t LastId = StackNodes.back()->OrigStackOrAllocId;
2258 StackIdToMatchingCalls[LastId].push_back(
2259 {
Call.call(), std::move(StackNodes),
Func, {}});
2269 DenseMap<uint32_t, DenseSet<uint32_t>> OldToNewContextIds;
2273 DenseMap<CallInfo, CallInfo> CallToMatchingCall;
2274 for (
auto &It : StackIdToMatchingCalls) {
2275 auto &Calls = It.getSecond();
2277 if (Calls.size() == 1) {
2278 auto &StackNodes = Calls[0].StackNodes;
2279 if (StackNodes.size() == 1)
2292 DenseMap<const FuncTy *, unsigned> FuncToIndex;
2293 for (
const auto &[Idx, CallCtxInfo] :
enumerate(Calls))
2294 FuncToIndex.
insert({CallCtxInfo.Func,
Idx});
2297 return std::lexicographical_compare(
2298 A.begin(),
A.end(),
B.begin(),
B.end(),
2299 [](
const ContextNode *
X,
const ContextNode *
Y) {
2300 return X->OrigStackOrAllocId < Y->OrigStackOrAllocId;
2303 auto CallLess = [&FuncToIndex, &StackIdsLess](
const CallContextInfo &
A,
2304 const CallContextInfo &
B) {
2305 return A.StackNodes.size() >
B.StackNodes.size() ||
2306 (
A.StackNodes.size() ==
B.StackNodes.size() &&
2307 (StackIdsLess(
A.StackNodes,
B.StackNodes) ||
2308 (
A.StackNodes ==
B.StackNodes &&
2309 FuncToIndex[
A.Func] < FuncToIndex[
B.Func])));
2318 ContextNode *LastNode = Calls[0].StackNodes.back();
2321 assert(LastNode == getNodeForStackId(LastId));
2323 if (LastNode->Recursive)
2328 DenseSet<uint32_t> LastNodeContextIds = LastNode->getContextIds();
2336 DenseSet<const FuncTy *> MatchingIdsFuncSet;
2339 for (
unsigned I = 0;
I < Calls.size();
I++) {
2340 auto &[
Call, StackNodes,
Func, SavedContextIds] = Calls[
I];
2341 assert(SavedContextIds.empty());
2342 assert(LastNode == StackNodes.back());
2347 if (
I > 0 && StackNodes != Calls[
I - 1].StackNodes)
2348 MatchingIdsFuncSet.
clear();
2355 DenseSet<uint32_t> StackSequenceContextIds = LastNodeContextIds;
2357 ContextNode *PrevNode = LastNode;
2358 ContextNode *CurNode = LastNode;
2363 for (
auto NodeIter = StackNodes.rbegin() + 1;
2364 NodeIter != StackNodes.rend(); NodeIter++) {
2365 CurNode = *NodeIter;
2369 if (CurNode->Recursive) {
2374 auto *
Edge = CurNode->findEdgeFromCaller(PrevNode);
2395 if (StackSequenceContextIds.
empty()) {
2408 if (LastId != getLastStackId(
Call)) {
2409 for (
const auto &PE : LastNode->CallerEdges) {
2410 set_subtract(StackSequenceContextIds, PE->getContextIds());
2411 if (StackSequenceContextIds.
empty())
2415 if (StackSequenceContextIds.
empty())
2427 MatchingIdsFuncSet.
insert(Func);
2436 bool DuplicateContextIds =
false;
2437 for (
unsigned J =
I + 1; J < Calls.size(); J++) {
2438 auto &CallCtxInfo = Calls[J];
2439 if (CallCtxInfo.StackNodes != StackNodes)
2441 auto *NextFunc = CallCtxInfo.Func;
2442 if (NextFunc != Func) {
2445 DuplicateContextIds =
true;
2448 auto &NextCall = CallCtxInfo.Call;
2449 CallToMatchingCall[NextCall] =
Call;
2460 OldToNewContextIds.
reserve(OldToNewContextIds.
size() +
2461 StackSequenceContextIds.
size());
2464 ? duplicateContextIds(StackSequenceContextIds, OldToNewContextIds)
2465 : StackSequenceContextIds;
2466 assert(!SavedContextIds.empty());
2468 if (!DuplicateContextIds) {
2472 set_subtract(LastNodeContextIds, StackSequenceContextIds);
2473 if (LastNodeContextIds.
empty())
2480 propagateDuplicateContextIds(OldToNewContextIds);
2490 DenseSet<const ContextNode *> Visited;
2492 ImportantContextIdInfo.keys());
2493 for (
auto &Entry : AllocationCallToContextNodeMap)
2494 assignStackNodesPostOrder(
Entry.second, Visited, StackIdToMatchingCalls,
2495 CallToMatchingCall, ImportantContextIds);
2497 fixupImportantContexts();
2503uint64_t ModuleCallsiteContextGraph::getLastStackId(Instruction *
Call) {
2504 CallStack<MDNode, MDNode::op_iterator> CallsiteContext(
2506 return CallsiteContext.
back();
2509uint64_t IndexCallsiteContextGraph::getLastStackId(IndexCall &
Call) {
2511 CallStack<CallsiteInfo, SmallVector<unsigned>::const_iterator>
2514 return Index.getStackIdAtIndex(CallsiteContext.
back());
2536 auto Pos =
F.getName().find_last_of(
'.');
2539 bool Err =
F.getName().drop_front(Pos + 1).getAsInteger(10, CloneNo);
2545std::string ModuleCallsiteContextGraph::getLabel(
const Function *Func,
2546 const Instruction *
Call,
2547 unsigned CloneNo)
const {
2553std::string IndexCallsiteContextGraph::getLabel(
const FunctionSummary *Func,
2554 const IndexCall &
Call,
2555 unsigned CloneNo)
const {
2556 auto VI = FSToVIMap.find(Func);
2557 assert(VI != FSToVIMap.end());
2560 return CallerName +
" -> alloc";
2563 return CallerName +
" -> " +
2565 Callsite->Clones[CloneNo]);
2569std::string ModuleCallsiteContextGraph::getFuncName(
const Function *Func,
2570 unsigned CloneNo)
const {
2576void ModuleCallsiteContextGraph::populateFunctionsWithCallers() {
2579 for (
const auto &
F :
Mod)
2581 FunctionsWithCallers.
insert(&
F);
2584std::string IndexCallsiteContextGraph::getFuncName(
const FunctionSummary *Func,
2585 unsigned CloneNo)
const {
2588 auto VI = FSToVIMap.find(Func);
2589 if (VI != FSToVIMap.end()) {
2590 if (!
VI->second.name().empty())
2598bool IndexCallsiteContextGraph::isFuncDead(
const FunctionSummary *Func)
const {
2599 return Index.withGlobalValueDeadStripping() &&
Func && !
Func->isLive();
2602void IndexCallsiteContextGraph::populateFunctionsWithCallers() {
2603 for (
const auto &
I : Index) {
2605 for (
const auto &S :
VI.getSummaryList()) {
2607 !isPrevailing(
VI.getGUID(), S.get()))
2609 if (
Index.withGlobalValueDeadStripping() && !S->isLive())
2611 auto AddReferenced = [&](ValueInfo RefVI) {
2612 for (
const auto &RefS : RefVI.getSummaryList()) {
2613 const GlobalValueSummary *
Base = RefS->getBaseObject();
2615 FunctionsWithCallers.
insert(RefFS);
2619 for (
const auto &RefVI : S->refs())
2620 AddReferenced(RefVI);
2623 for (
const auto &CallEdge :
FS->calls())
2624 AddReferenced(CallEdge.first);
2629std::vector<ModuleCallsiteContextGraph::ContextNode *>
2630ModuleCallsiteContextGraph::getStackNodesForCall(Instruction *
Call) {
2631 CallStack<MDNode, MDNode::op_iterator> CallsiteContext(
2633 return getStackNodesForCallsite<MDNode, MDNode::op_iterator>(CallsiteContext);
2636std::vector<IndexCallsiteContextGraph::ContextNode *>
2637IndexCallsiteContextGraph::getStackNodesForCall(IndexCall &
Call) {
2639 CallStack<CallsiteInfo, SmallVector<unsigned>::const_iterator>
2641 return getStackNodesForCallsite<CallsiteInfo,
2642 SmallVector<unsigned>::const_iterator>(
2646template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2647template <
class NodeT,
class IteratorT>
2649 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *>
2650CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getStackNodesForCallsite(
2651 CallStack<NodeT, IteratorT> &CallsiteContext) {
2652 std::vector<ContextNode *> StackNodes;
2653 for (
auto IdOrIndex : CallsiteContext) {
2654 auto StackId = getStackId(IdOrIndex);
2655 ContextNode *
Node = getNodeForStackId(StackId);
2658 StackNodes.push_back(Node);
2663ModuleCallsiteContextGraph::ModuleCallsiteContextGraph(
2665 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter)
2666 :
Mod(
M), OREGetter(OREGetter) {
2670 std::map<uint64_t, uint32_t> TotalSizeToContextIdTopNCold;
2672 std::vector<CallInfo> CallsWithMetadata;
2673 for (
auto &BB :
F) {
2674 for (
auto &
I : BB) {
2677 if (
auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof)) {
2678 CallsWithMetadata.push_back(&
I);
2679 auto *AllocNode = addAllocNode(&
I, &
F);
2680 auto *CallsiteMD =
I.getMetadata(LLVMContext::MD_callsite);
2684 for (
auto &MDOp : MemProfMD->operands()) {
2686 std::vector<ContextTotalSize> ContextSizeInfo;
2688 if (MIBMD->getNumOperands() > 2) {
2689 for (
unsigned I = 2;
I < MIBMD->getNumOperands();
I++) {
2690 MDNode *ContextSizePair =
2699 ContextSizeInfo.push_back({FullStackId, TotalSize});
2705 addStackNodesForMIB<MDNode, MDNode::op_iterator>(
2706 AllocNode, StackContext, CallsiteContext,
2708 TotalSizeToContextIdTopNCold);
2713 DotAllocContextIds = AllocNode->getContextIds();
2717 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
2718 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
2721 else if (
I.getMetadata(LLVMContext::MD_callsite)) {
2722 CallsWithMetadata.push_back(&
I);
2726 if (!CallsWithMetadata.empty())
2727 FuncToCallsWithMetadata[&
F] = CallsWithMetadata;
2731 dbgs() <<
"CCG before updating call stack chains:\n";
2736 exportToDot(
"prestackupdate");
2741 exportToDot(
"poststackupdate");
2743 handleCallsitesWithMultipleTargets();
2748 for (
auto &FuncEntry : FuncToCallsWithMetadata)
2749 for (
auto &
Call : FuncEntry.second)
2750 Call.call()->setMetadata(LLVMContext::MD_callsite,
nullptr);
2756IndexCallsiteContextGraph::findAliaseeGUIDsPrevailingInDifferentModule() {
2757 DenseSet<GlobalValue::GUID> AliaseeGUIDs;
2758 for (
auto &
I : Index) {
2760 for (
auto &S :
VI.getSummaryList()) {
2765 auto *AliaseeSummary = &AS->getAliasee();
2773 !isPrevailing(
VI.getGUID(), S.get()))
2778 auto AliaseeGUID = AS->getAliaseeGUID();
2780 if (!isPrevailing(AliaseeGUID, AliaseeSummary))
2781 AliaseeGUIDs.
insert(AliaseeGUID);
2784 AliaseesPrevailingInDiffModuleFromAlias += AliaseeGUIDs.
size();
2785 return AliaseeGUIDs;
2788IndexCallsiteContextGraph::IndexCallsiteContextGraph(
2789 ModuleSummaryIndex &Index,
2799 findAliaseeGUIDsPrevailingInDifferentModule();
2803 std::map<uint64_t, uint32_t> TotalSizeToContextIdTopNCold;
2808 for (
const auto &
I : Index.sortedGlobalValueSummariesRange()) {
2809 auto VI = Index.getValueInfo(
I);
2810 if (GUIDsToSkip.
contains(VI.getGUID()))
2812 for (
auto &S : VI.getSummaryList()) {
2821 !isPrevailing(VI.getGUID(), S.get()))
2826 std::vector<CallInfo> CallsWithMetadata;
2827 if (!
FS->allocs().empty()) {
2828 for (
auto &AN :
FS->mutableAllocs()) {
2833 if (AN.MIBs.empty())
2835 IndexCall AllocCall(&AN);
2836 CallsWithMetadata.push_back(AllocCall);
2837 auto *AllocNode = addAllocNode(AllocCall, FS);
2845 AN.ContextSizeInfos.size() == AN.MIBs.size());
2847 for (
auto &MIB : AN.MIBs) {
2850 std::vector<ContextTotalSize> ContextSizeInfo;
2851 if (!AN.ContextSizeInfos.empty()) {
2852 for (
auto [FullStackId, TotalSize] : AN.ContextSizeInfos[
I])
2853 ContextSizeInfo.push_back({FullStackId, TotalSize});
2855 addStackNodesForMIB<MIBInfo, SmallVector<unsigned>::const_iterator>(
2856 AllocNode, StackContext, EmptyContext, MIB.AllocType,
2857 ContextSizeInfo, TotalSizeToContextIdTopNCold);
2863 DotAllocContextIds = AllocNode->getContextIds();
2869 AN.Versions[0] = (
uint8_t)allocTypeToUse(AllocNode->AllocTypes);
2873 if (!
FS->callsites().empty())
2874 for (
auto &SN :
FS->mutableCallsites()) {
2875 IndexCall StackNodeCall(&SN);
2876 CallsWithMetadata.push_back(StackNodeCall);
2879 if (!CallsWithMetadata.empty())
2880 FuncToCallsWithMetadata[
FS] = CallsWithMetadata;
2882 if (!
FS->allocs().empty() || !
FS->callsites().empty())
2888 dbgs() <<
"CCG before updating call stack chains:\n";
2893 exportToDot(
"prestackupdate");
2898 exportToDot(
"poststackupdate");
2900 handleCallsitesWithMultipleTargets();
2905template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2906void CallsiteContextGraph<DerivedCCG, FuncTy,
2907 CallTy>::handleCallsitesWithMultipleTargets() {
2922 std::vector<std::pair<CallInfo, ContextNode *>> NewCallToNode;
2923 for (
auto &Entry : NonAllocationCallToContextNodeMap) {
2924 auto *
Node = Entry.second;
2933 std::vector<CallInfo> AllCalls;
2934 AllCalls.reserve(
Node->MatchingCalls.size() + 1);
2935 AllCalls.push_back(
Node->Call);
2949 if (partitionCallsByCallee(
Node, AllCalls, NewCallToNode))
2952 auto It = AllCalls.begin();
2954 for (; It != AllCalls.end(); ++It) {
2957 for (
auto EI =
Node->CalleeEdges.begin(); EI !=
Node->CalleeEdges.end();
2960 if (!Edge->Callee->hasCall())
2962 assert(NodeToCallingFunc.count(Edge->Callee));
2964 if (!calleesMatch(
ThisCall.call(), EI, TailCallToContextNodeMap)) {
2973 if (
Node->Call != ThisCall) {
2974 Node->setCall(ThisCall);
2985 Node->MatchingCalls.clear();
2988 if (It == AllCalls.end()) {
2989 RemovedEdgesWithMismatchedCallees++;
2993 Node->setCall(CallInfo());
2998 for (++It; It != AllCalls.end(); ++It) {
3002 Node->MatchingCalls.push_back(ThisCall);
3011 NonAllocationCallToContextNodeMap.remove_if([](
const auto &it) {
3012 return !it.second->hasCall() || it.second->Call != it.first;
3016 for (
auto &[
Call,
Node] : NewCallToNode)
3017 NonAllocationCallToContextNodeMap[
Call] =
Node;
3021 for (
auto &[
Call,
Node] : TailCallToContextNodeMap)
3022 NonAllocationCallToContextNodeMap[
Call] =
Node;
3025template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3026bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::partitionCallsByCallee(
3028 std::vector<std::pair<CallInfo, ContextNode *>> &NewCallToNode) {
3032 struct CallsWithSameCallee {
3033 std::vector<CallInfo> Calls;
3034 ContextNode *
Node =
nullptr;
3040 for (
auto ThisCall : AllCalls) {
3041 auto *
F = getCalleeFunc(
ThisCall.call());
3043 CalleeFuncToCallInfo[
F].Calls.push_back(ThisCall);
3052 for (
const auto &Edge :
Node->CalleeEdges) {
3053 if (!Edge->Callee->hasCall())
3055 const FuncTy *ProfiledCalleeFunc = NodeToCallingFunc[Edge->Callee];
3056 if (CalleeFuncToCallInfo.
contains(ProfiledCalleeFunc))
3057 CalleeNodeToCallInfo[Edge->Callee] =
3058 &CalleeFuncToCallInfo[ProfiledCalleeFunc];
3064 if (CalleeNodeToCallInfo.
empty())
3076 ContextNode *UnmatchedCalleesNode =
nullptr;
3078 bool UsedOrigNode =
false;
3083 auto CalleeEdges =
Node->CalleeEdges;
3084 for (
auto &Edge : CalleeEdges) {
3085 if (!Edge->Callee->hasCall())
3090 ContextNode *CallerNodeToUse =
nullptr;
3094 if (!CalleeNodeToCallInfo.
contains(Edge->Callee)) {
3095 if (!UnmatchedCalleesNode)
3096 UnmatchedCalleesNode =
3097 createNewNode(
false, NodeToCallingFunc[
Node]);
3098 CallerNodeToUse = UnmatchedCalleesNode;
3102 auto *Info = CalleeNodeToCallInfo[Edge->Callee];
3105 if (!UsedOrigNode) {
3108 Node->MatchingCalls.clear();
3109 UsedOrigNode =
true;
3112 createNewNode(
false, NodeToCallingFunc[
Node]);
3113 assert(!Info->Calls.empty());
3116 Info->Node->setCall(Info->Calls.front());
3122 NewCallToNode.push_back({Info->Node->Call, Info->Node});
3124 CallerNodeToUse = Info->Node;
3128 if (CallerNodeToUse ==
Node)
3131 moveCalleeEdgeToNewCaller(Edge, CallerNodeToUse);
3138 for (
auto &
I : CalleeNodeToCallInfo)
3139 removeNoneTypeCallerEdges(
I.second->Node);
3140 if (UnmatchedCalleesNode)
3141 removeNoneTypeCallerEdges(UnmatchedCalleesNode);
3142 removeNoneTypeCallerEdges(
Node);
3155 return Index.getStackIdAtIndex(IdOrIndex);
3158template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3159bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::calleesMatch(
3160 CallTy
Call, EdgeIter &EI,
3161 MapVector<CallInfo, ContextNode *> &TailCallToContextNodeMap) {
3163 const FuncTy *ProfiledCalleeFunc = NodeToCallingFunc[
Edge->Callee];
3164 const FuncTy *CallerFunc = NodeToCallingFunc[
Edge->Caller];
3167 std::vector<std::pair<CallTy, FuncTy *>> FoundCalleeChain;
3168 if (!calleeMatchesFunc(
Call, ProfiledCalleeFunc, CallerFunc,
3173 if (FoundCalleeChain.empty())
3177 auto *CurEdge =
Callee->findEdgeFromCaller(Caller);
3181 CurEdge->ContextIds.insert_range(
Edge->ContextIds);
3182 CurEdge->AllocTypes |=
Edge->AllocTypes;
3187 auto NewEdge = std::make_shared<ContextEdge>(
3188 Callee, Caller,
Edge->AllocTypes,
Edge->ContextIds);
3189 Callee->CallerEdges.push_back(NewEdge);
3190 if (Caller ==
Edge->Caller) {
3194 EI =
Caller->CalleeEdges.insert(EI, NewEdge);
3197 "Iterator position not restored after insert and increment");
3199 Caller->CalleeEdges.push_back(NewEdge);
3204 auto *CurCalleeNode =
Edge->Callee;
3205 for (
auto &[NewCall, Func] : FoundCalleeChain) {
3206 ContextNode *NewNode =
nullptr;
3208 if (TailCallToContextNodeMap.
count(NewCall)) {
3209 NewNode = TailCallToContextNodeMap[NewCall];
3210 NewNode->AllocTypes |=
Edge->AllocTypes;
3212 FuncToCallsWithMetadata[
Func].push_back({NewCall});
3214 NewNode = createNewNode(
false, Func, NewCall);
3215 TailCallToContextNodeMap[NewCall] = NewNode;
3216 NewNode->AllocTypes =
Edge->AllocTypes;
3220 AddEdge(NewNode, CurCalleeNode);
3222 CurCalleeNode = NewNode;
3226 AddEdge(
Edge->Caller, CurCalleeNode);
3234 removeEdgeFromGraph(
Edge.get(), &EI,
true);
3246bool ModuleCallsiteContextGraph::findProfiledCalleeThroughTailCalls(
3248 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain,
3249 bool &FoundMultipleCalleeChains) {
3256 FoundCalleeChain.push_back({Callsite,
F});
3271 bool FoundSingleCalleeChain =
false;
3272 for (
auto &BB : *CalleeFunc) {
3273 for (
auto &
I : BB) {
3275 if (!CB || !CB->isTailCall())
3277 auto *CalledValue = CB->getCalledOperand();
3278 auto *CalledFunction = CB->getCalledFunction();
3279 if (CalledValue && !CalledFunction) {
3280 CalledValue = CalledValue->stripPointerCasts();
3287 assert(!CalledFunction &&
3288 "Expected null called function in callsite for alias");
3291 if (!CalledFunction)
3293 if (CalledFunction == ProfiledCallee) {
3294 if (FoundSingleCalleeChain) {
3295 FoundMultipleCalleeChains =
true;
3298 FoundSingleCalleeChain =
true;
3299 FoundProfiledCalleeCount++;
3300 FoundProfiledCalleeDepth +=
Depth;
3301 if (
Depth > FoundProfiledCalleeMaxDepth)
3302 FoundProfiledCalleeMaxDepth =
Depth;
3303 SaveCallsiteInfo(&
I, CalleeFunc);
3304 }
else if (findProfiledCalleeThroughTailCalls(
3305 ProfiledCallee, CalledFunction,
Depth + 1,
3306 FoundCalleeChain, FoundMultipleCalleeChains)) {
3309 assert(!FoundMultipleCalleeChains);
3310 if (FoundSingleCalleeChain) {
3311 FoundMultipleCalleeChains =
true;
3314 FoundSingleCalleeChain =
true;
3315 SaveCallsiteInfo(&
I, CalleeFunc);
3316 }
else if (FoundMultipleCalleeChains)
3321 return FoundSingleCalleeChain;
3324const Function *ModuleCallsiteContextGraph::getCalleeFunc(Instruction *
Call) {
3326 if (!CB->getCalledOperand() || CB->isIndirectCall())
3328 auto *CalleeVal = CB->getCalledOperand()->stripPointerCasts();
3335bool ModuleCallsiteContextGraph::calleeMatchesFunc(
3337 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain) {
3339 if (!CB->getCalledOperand() || CB->isIndirectCall())
3341 auto *CalleeVal = CB->getCalledOperand()->stripPointerCasts();
3343 if (CalleeFunc == Func)
3346 if (Alias && Alias->getAliasee() == Func)
3357 bool FoundMultipleCalleeChains =
false;
3358 if (!findProfiledCalleeThroughTailCalls(Func, CalleeVal,
Depth,
3360 FoundMultipleCalleeChains)) {
3361 LLVM_DEBUG(
dbgs() <<
"Not found through unique tail call chain: "
3362 <<
Func->getName() <<
" from " << CallerFunc->
getName()
3363 <<
" that actually called " << CalleeVal->getName()
3364 << (FoundMultipleCalleeChains
3365 ?
" (found multiple possible chains)"
3368 if (FoundMultipleCalleeChains)
3369 FoundProfiledCalleeNonUniquelyCount++;
3376bool ModuleCallsiteContextGraph::sameCallee(Instruction *Call1,
3377 Instruction *Call2) {
3379 if (!CB1->getCalledOperand() || CB1->isIndirectCall())
3381 auto *CalleeVal1 = CB1->getCalledOperand()->stripPointerCasts();
3384 if (!CB2->getCalledOperand() || CB2->isIndirectCall())
3386 auto *CalleeVal2 = CB2->getCalledOperand()->stripPointerCasts();
3388 return CalleeFunc1 == CalleeFunc2;
3391bool IndexCallsiteContextGraph::findProfiledCalleeThroughTailCalls(
3392 ValueInfo ProfiledCallee, ValueInfo CurCallee,
unsigned Depth,
3393 std::vector<std::pair<ValueInfo, FunctionSummary *>> &FoundCalleeChain,
3394 bool &FoundMultipleCalleeChains) {
3404 auto SaveTailCall = [&](ValueInfo
Callee, FunctionSummary *
FS) {
3405 FoundCalleeChain.push_back({
Callee,
FS});
3412 bool FoundSingleCalleeChain =
false;
3415 !isPrevailing(CurCallee.
getGUID(), S.get()))
3420 auto FSVI = CurCallee;
3423 FSVI = AS->getAliaseeVI();
3424 for (
auto &CallEdge :
FS->calls()) {
3425 if (!CallEdge.second.hasTailCall())
3432 if (CallEdge.first == ProfiledCallee) {
3433 if (FoundSingleCalleeChain) {
3434 FoundMultipleCalleeChains =
true;
3437 FoundSingleCalleeChain =
true;
3438 FoundProfiledCalleeCount++;
3439 FoundProfiledCalleeDepth +=
Depth;
3440 if (
Depth > FoundProfiledCalleeMaxDepth)
3441 FoundProfiledCalleeMaxDepth =
Depth;
3442 if (CallEdge.second.hasIndirectCall())
3443 FoundProfiledCalleeIndirectTailCallCount++;
3444 SaveTailCall(CallEdge.first, FS);
3446 assert(!FSToVIMap.count(FS) || FSToVIMap[FS] == FSVI);
3447 FSToVIMap[
FS] = FSVI;
3448 }
else if (findProfiledCalleeThroughTailCalls(
3449 ProfiledCallee, CallEdge.first,
Depth + 1,
3450 FoundCalleeChain, FoundMultipleCalleeChains)) {
3453 assert(!FoundMultipleCalleeChains);
3454 if (FoundSingleCalleeChain) {
3455 FoundMultipleCalleeChains =
true;
3458 FoundSingleCalleeChain =
true;
3459 if (CallEdge.second.hasIndirectCall())
3460 FoundProfiledCalleeIndirectTailCallCount++;
3461 SaveTailCall(CallEdge.first, FS);
3463 assert(!FSToVIMap.count(FS) || FSToVIMap[FS] == FSVI);
3464 FSToVIMap[
FS] = FSVI;
3465 }
else if (FoundMultipleCalleeChains)
3470 return FoundSingleCalleeChain;
3473const FunctionSummary *
3474IndexCallsiteContextGraph::getCalleeFunc(IndexCall &
Call) {
3476 if (
Callee.getSummaryList().empty())
3481bool IndexCallsiteContextGraph::calleeMatchesFunc(
3482 IndexCall &
Call,
const FunctionSummary *Func,
3483 const FunctionSummary *CallerFunc,
3484 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain) {
3488 AliasSummary *Alias =
3489 Callee.getSummaryList().empty()
3492 assert(FSToVIMap.count(Func));
3493 auto FuncVI = FSToVIMap[
Func];
3494 if (Callee == FuncVI ||
3509 bool FoundMultipleCalleeChains =
false;
3510 std::vector<std::pair<ValueInfo, FunctionSummary *>> FoundCalleeVIChain;
3511 if (!findProfiledCalleeThroughTailCalls(FuncVI, Callee,
Depth,
3513 FoundMultipleCalleeChains)) {
3514 LLVM_DEBUG(
dbgs() <<
"Not found through unique tail call chain: " << FuncVI
3515 <<
" from " << FSToVIMap[CallerFunc]
3516 <<
" that actually called " << Callee
3517 << (FoundMultipleCalleeChains
3518 ?
" (found multiple possible chains)"
3521 if (FoundMultipleCalleeChains)
3522 FoundProfiledCalleeNonUniquelyCount++;
3531 for (
auto &[CalleeVI, FS] : FoundCalleeVIChain) {
3532 auto &CallsiteInfoPtr =
3533 FunctionCalleesToSynthesizedCallsiteInfos[
FS][CalleeVI];
3534 if (!CallsiteInfoPtr)
3538 std::make_unique<CallsiteInfo>(CalleeVI, SmallVector<unsigned>());
3539 FoundCalleeChain.push_back({CallsiteInfoPtr.get(),
FS});
3545bool IndexCallsiteContextGraph::sameCallee(IndexCall &Call1, IndexCall &Call2) {
3548 return Callee1 == Callee2;
3551template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3552void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::dump()
3558template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3559void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::print(
3560 raw_ostream &OS)
const {
3561 OS <<
"Node " <<
this <<
"\n";
3565 OS <<
" (recursive)";
3567 if (!MatchingCalls.
empty()) {
3568 OS <<
"\tMatchingCalls:\n";
3569 for (
auto &MatchingCall : MatchingCalls) {
3571 MatchingCall.print(OS);
3575 OS <<
"\tNodeId: " <<
NodeId <<
"\n";
3577 OS <<
"\tContextIds:";
3579 auto ContextIds = getContextIds();
3580 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
3581 std::sort(SortedIds.begin(), SortedIds.end());
3582 for (
auto Id : SortedIds)
3585 OS <<
"\tCalleeEdges:\n";
3586 for (
auto &
Edge : CalleeEdges)
3587 OS <<
"\t\t" << *
Edge <<
" (Callee NodeId: " <<
Edge->Callee->NodeId
3589 OS <<
"\tCallerEdges:\n";
3590 for (
auto &
Edge : CallerEdges)
3591 OS <<
"\t\t" << *
Edge <<
" (Caller NodeId: " <<
Edge->Caller->NodeId
3593 if (!Clones.empty()) {
3596 for (
auto *
C : Clones)
3597 OS <<
LS <<
C <<
" NodeId: " <<
C->NodeId;
3599 }
else if (CloneOf) {
3600 OS <<
"\tClone of " << CloneOf <<
" NodeId: " << CloneOf->NodeId <<
"\n";
3604template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3605void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge::dump()
3611template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3612void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge::print(
3613 raw_ostream &OS)
const {
3614 OS <<
"Edge from Callee " <<
Callee <<
" to Caller: " <<
Caller
3615 << (IsBackedge ?
" (BE)" :
"")
3617 OS <<
" ContextIds:";
3618 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
3619 std::sort(SortedIds.begin(), SortedIds.end());
3620 for (
auto Id : SortedIds)
3624template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3625void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::dump()
const {
3629template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3630void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::print(
3631 raw_ostream &OS)
const {
3632 OS <<
"Callsite Context Graph:\n";
3633 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
3635 if (
Node->isRemoved())
3642template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3643void CallsiteContextGraph<DerivedCCG, FuncTy,
3644 CallTy>::capturePreCloningContextInfo() {
3645 for (
const auto &Entry : AllocationCallToContextNodeMap) {
3646 const ContextNode *AllocNode =
Entry.second;
3650 for (
const auto &
Edge : AllocNode->CallerEdges) {
3651 if (!
Edge->isRemoved() &&
Edge->Caller->hasCall()) {
3652 PreCloningAllocHasMatchedCaller.insert(AllocNode);
3656 DenseSet<uint32_t> ContextIds = AllocNode->getContextIds();
3657 for (uint32_t Id : ContextIds) {
3658 PreCloningContextInfo
Info;
3664 Info.Chain.push_back(AllocNode);
3665 SmallPtrSet<const ContextNode *, 16> Visited;
3666 Visited.
insert(AllocNode);
3667 const ContextNode *Cur = AllocNode;
3669 const ContextNode *
Next =
nullptr;
3670 for (
const auto &
Edge : Cur->CallerEdges) {
3671 if (
Edge->isRemoved() ||
Edge->IsBackedge)
3673 if (
Edge->getContextIds().contains(Id) &&
3680 for (
const auto &
Edge : Cur->CallerEdges) {
3681 if (
Edge->isRemoved())
3683 if (
Edge->getContextIds().contains(Id) &&
3700 Info.MaxMatchedFrame = 0;
3701 for (
unsigned I = 1;
I <
Info.Chain.size(); ++
I) {
3702 if (
Info.Chain[
I]->hasCall()) {
3703 Info.MaxMatchedFrame =
I;
3705 const ContextNode *Unmatched =
Info.Chain[
I];
3706 Info.UnmatchedStackId = Unmatched->OrigStackOrAllocId;
3707 Info.StoppedAtRecursive = Unmatched->Recursive;
3711 if (
auto It = NodeToCallingFunc.find(Unmatched);
3712 It != NodeToCallingFunc.end()) {
3713 Info.StoppedAtMismatchedCallee =
true;
3714 Info.UnmatchedCallingFunc = It->second;
3724 if (
Info.MaxMatchedFrame > 0 &&
3725 Info.MaxMatchedFrame + 1 ==
Info.Chain.size()) {
3726 const ContextNode *OutermostMatchedNode =
3728 for (
const auto &
Edge : OutermostMatchedNode->CallerEdges) {
3729 if (!
Edge->isRemoved() &&
Edge->Caller->hasCall()) {
3730 Info.OutermostMatchedNodeHasOtherCallers =
true;
3736 PreCloningContextInfoMap[
Id] = std::move(Info);
3741template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3743CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::formatContextReportSuffix(
3744 const ContextNode *Node, uint32_t Id)
const {
3745 auto InfoIt = PreCloningContextInfoMap.find(Id);
3746 if (InfoIt == PreCloningContextInfoMap.end())
3748 const PreCloningContextInfo &
Info = InfoIt->second;
3755 const ContextNode *OrigAlloc =
Node->getOrigNode();
3756 const FuncTy *AllocFunc = getCallingFunc(OrigAlloc);
3757 unsigned AllocCloneNo =
Node->Call.cloneNo();
3758 std::string AllocFuncStr = getFuncName(AllocFunc, AllocCloneNo);
3759 if (isFuncDead(AllocFunc)) {
3760 AllocFuncStr +=
" (dead)";
3761 }
else if (!PreCloningAllocHasMatchedCaller.contains(OrigAlloc) &&
3762 Info.Chain.size() > 1) {
3766 AllocFuncStr += AllocFunc && !FunctionsWithCallers.
contains(AllocFunc)
3767 ?
" (no references in IR/summary)"
3768 :
" (no matched callers)";
3774 unsigned TotalFrames =
Info.Chain.size() > 0 ?
Info.Chain.size() - 1 : 0;
3775 unsigned Matched =
Info.MaxMatchedFrame;
3776 std::string StatusStr;
3777 if (TotalFrames == 0) {
3778 StatusStr =
"inlined into leaf";
3779 }
else if (Matched < TotalFrames) {
3784 if (
Info.StoppedAtRecursive)
3785 StatusStr =
"unmatched recursive callsite";
3786 else if (
Info.StoppedAtMismatchedCallee)
3787 StatusStr =
"unmatched callsite (mismatched callee in " +
3788 getFuncName(
Info.UnmatchedCallingFunc, 0) +
")";
3790 StatusStr =
"unmatched callsite";
3791 StatusStr +=
" at frame " + std::to_string(Matched + 1) +
"/" +
3792 std::to_string(TotalFrames) +
" (stack id " +
3793 std::to_string(
Info.UnmatchedStackId) +
")";
3795 const ContextNode *OutermostMatchedNode =
Info.Chain[Matched];
3796 const FuncTy *OutermostMatchedFunc = getCallingFunc(OutermostMatchedNode);
3797 unsigned NumOutermostMatchedFuncClones =
3798 std::max<unsigned>(1, FuncToNumClones.lookup(OutermostMatchedFunc));
3799 bool HasCallersAbove =
3800 NumOutermostMatchedFuncClones > 1 ||
3801 Info.OutermostMatchedNodeHasOtherCallers ||
3802 (OutermostMatchedFunc &&
3803 FunctionsWithCallers.
contains(OutermostMatchedFunc));
3804 if (HasCallersAbove) {
3805 StatusStr =
"trimmed at frame " + std::to_string(Matched) +
" in " +
3806 getFuncName(OutermostMatchedFunc, 0);
3808 StatusStr =
"matched " + std::to_string(Matched) +
" frames to " +
3809 getFuncName(OutermostMatchedFunc, 0);
3818 std::string ReachesStr;
3820 const ContextNode *OutermostMatchedNode =
Info.Chain[Matched];
3821 const FuncTy *OutermostMatchedFunc = getCallingFunc(OutermostMatchedNode);
3822 unsigned NumOutermostMatchedFuncClones =
3823 std::max<unsigned>(1, FuncToNumClones.lookup(OutermostMatchedFunc));
3824 ReachesStr =
"; reaches ";
3829 SmallSet<unsigned, 4> ReportedAllocClones;
3830 bool FirstPath =
true;
3831 for (
unsigned OutermostMatchedFuncClone = 0;
3832 OutermostMatchedFuncClone < NumOutermostMatchedFuncClones;
3833 ++OutermostMatchedFuncClone) {
3837 std::vector<const FuncTy *> PathFuncs(Matched + 1);
3838 std::vector<unsigned> PathClones(Matched + 1);
3839 PathFuncs[0] = OutermostMatchedFunc;
3840 PathClones[0] = OutermostMatchedFuncClone;
3841 unsigned CurClone = OutermostMatchedFuncClone;
3842 for (
unsigned Step = 0; Step < Matched; ++Step) {
3843 unsigned FrameIdx = Matched - Step;
3844 const ContextNode *CallNode =
Info.Chain[FrameIdx];
3845 unsigned NextClone =
3846 OrigNodeAndCloneToCalleeClone.lookup({CallNode, CurClone});
3847 const FuncTy *CalleeFunc = getCallingFunc(
Info.Chain[FrameIdx - 1]);
3848 PathFuncs[Step + 1] = CalleeFunc;
3849 PathClones[Step + 1] = NextClone;
3850 CurClone = NextClone;
3853 if (!ReportedAllocClones.
insert(CurClone).second)
3859 const ContextNode *ReachedAlloc =
3860 OrigAllocAndCloneToNode.lookup({OrigAlloc, CurClone});
3864 std::string ReachedTypeStr;
3867 (uint8_t)getAllocationCallType(ReachedAlloc->Call));
3868 else if (CurClone == 0)
3872 ReachedTypeStr =
"None";
3878 std::string PathStr;
3879 bool SkippedPrev =
false;
3880 bool PrintFullPath =
3882 for (
unsigned S = 0; S <= Matched; ++S) {
3883 bool IsCloned = PathClones[S] > 0;
3884 bool PrevCloned = S > 0 ? (PathClones[S - 1] > 0) : IsCloned;
3885 bool NextCloned = S + 1 <= Matched ? (PathClones[S + 1] > 0) : IsCloned;
3886 bool Include = PrintFullPath || (S <= 1) || (S + 1 >= Matched) ||
3887 (IsCloned != PrevCloned) || (IsCloned != NextCloned);
3890 PathStr +=
" -> ...";
3895 SkippedPrev =
false;
3896 if (!PathStr.empty())
3898 PathStr += getFuncName(PathFuncs[S], PathClones[S]);
3900 ReachesStr += ReachedTypeStr +
" via " + PathStr;
3904 return " [alloc in " + AllocFuncStr +
"; " + StatusStr + ReachesStr +
"]";
3907template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3908void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::printTotalSizes(
3910 function_ref<
void(StringRef, StringRef,
const Twine &)> EmitRemark)
const {
3911 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
3913 if (
Node->isRemoved())
3915 if (!
Node->IsAllocation)
3917 DenseSet<uint32_t> ContextIds =
Node->getContextIds();
3918 auto AllocTypeFromCall = getAllocationCallType(
Node->Call);
3919 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
3920 std::sort(SortedIds.begin(), SortedIds.end());
3921 for (
auto Id : SortedIds) {
3922 auto TypeI = ContextIdToAllocationType.
find(Id);
3923 assert(TypeI != ContextIdToAllocationType.
end());
3925 bool ComputedSuffix =
false;
3926 auto GetSuffix = [&]() ->
const std::string & {
3927 if (!ComputedSuffix) {
3929 ? formatContextReportSuffix(Node, Id)
3931 ComputedSuffix =
true;
3935 auto CSI = ContextIdToContextSizeInfos.
find(Id);
3936 if (CSI != ContextIdToContextSizeInfos.
end()) {
3937 for (
auto &Info : CSI->second) {
3940 " full allocation context " + std::to_string(
Info.FullStackId) +
3941 " with total size " + std::to_string(
Info.TotalSize) +
" is " +
3943 if (allocTypeToUse(
Node->AllocTypes) !=
3944 allocTypeToUse((uint8_t)AllocTypeFromCall))
3946 " due to cold byte percent";
3948 Msg +=
" (internal context id " + std::to_string(Id) +
")";
3950 OS <<
Msg << GetSuffix() <<
"\n";
3960 if (allocTypeToUse(
Node->AllocTypes) !=
3961 allocTypeToUse((uint8_t)AllocTypeFromCall))
3963 " due to cold byte percent";
3965 Msg +=
" (internal context id " + std::to_string(Id) +
")";
3967 OS <<
Msg << GetSuffix() <<
"\n";
3975template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3976void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::check()
const {
3977 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
3980 for (
auto &
Edge :
Node->CallerEdges)
3985template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3987 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
3988 using NodeRef =
const ContextNode<DerivedCCG, FuncTy, CallTy> *;
3990 using NodePtrTy = std::unique_ptr<ContextNode<DerivedCCG, FuncTy, CallTy>>;
4006 return G->NodeOwner.begin()->get();
4009 using EdgePtrTy = std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>>;
4010 static const ContextNode<DerivedCCG, FuncTy, CallTy> *
4029template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4043 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
4049 std::string LabelString =
4050 (
Twine(
"OrigId: ") + (
Node->IsAllocation ?
"Alloc" :
"") +
4053 LabelString +=
"\n";
4054 if (
Node->hasCall()) {
4055 auto Func =
G->NodeToCallingFunc.find(
Node);
4056 assert(Func !=
G->NodeToCallingFunc.end());
4058 G->getLabel(Func->second,
Node->Call.call(),
Node->Call.cloneNo());
4059 for (
auto &MatchingCall :
Node->MatchingCalls) {
4060 LabelString +=
"\n";
4061 LabelString +=
G->getLabel(Func->second, MatchingCall.call(),
4062 MatchingCall.cloneNo());
4065 LabelString +=
"null call";
4066 if (
Node->Recursive)
4067 LabelString +=
" (recursive)";
4069 LabelString +=
" (external)";
4075 auto ContextIds =
Node->getContextIds();
4079 bool Highlight =
false;
4088 std::string AttributeString = (
Twine(
"tooltip=\"") + getNodeId(
Node) +
" " +
4089 getContextIds(ContextIds) +
"\"")
4093 AttributeString +=
",fontsize=\"30\"";
4095 (
Twine(
",fillcolor=\"") + getColor(
Node->AllocTypes, Highlight) +
"\"")
4097 if (
Node->CloneOf) {
4098 AttributeString +=
",color=\"blue\"";
4099 AttributeString +=
",style=\"filled,bold,dashed\"";
4101 AttributeString +=
",style=\"filled\"";
4102 return AttributeString;
4107 auto &Edge = *(ChildIter.getCurrent());
4112 bool Highlight =
false;
4121 auto Color = getColor(Edge->AllocTypes, Highlight);
4122 std::string AttributeString =
4123 (
Twine(
"tooltip=\"") + getContextIds(Edge->ContextIds) +
"\"" +
4125 Twine(
",fillcolor=\"") + Color +
"\"" +
Twine(
",color=\"") + Color +
4128 if (Edge->IsBackedge)
4129 AttributeString +=
",style=\"dotted\"";
4132 AttributeString +=
",penwidth=\"2.0\",weight=\"2\"";
4133 return AttributeString;
4139 if (
Node->isRemoved())
4152 std::string IdString =
"ContextIds:";
4153 if (ContextIds.
size() < 100) {
4154 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
4155 std::sort(SortedIds.begin(), SortedIds.end());
4156 for (
auto Id : SortedIds)
4157 IdString += (
" " +
Twine(Id)).str();
4159 IdString += (
" (" + Twine(ContextIds.
size()) +
" ids)").str();
4164 static std::string getColor(uint8_t AllocTypes,
bool Highlight) {
4170 if (AllocTypes == (uint8_t)AllocationType::NotCold)
4172 return !
DoHighlight || Highlight ?
"brown1" :
"lightpink";
4173 if (AllocTypes == (uint8_t)AllocationType::Cold)
4174 return !
DoHighlight || Highlight ?
"cyan" :
"lightskyblue";
4176 ((uint8_t)AllocationType::NotCold | (uint8_t)AllocationType::Cold))
4177 return Highlight ?
"magenta" :
"mediumorchid1";
4181 static std::string getNodeId(NodeRef Node) {
4182 std::stringstream SStream;
4183 SStream << std::hex <<
"N0x" << (
unsigned long long)Node;
4184 std::string
Result = SStream.str();
4193template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4198template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4199void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::exportToDot(
4200 std::string Label)
const {
4205template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4206typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
4207CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::moveEdgeToNewCalleeClone(
4208 const std::shared_ptr<ContextEdge> &
Edge,
4209 DenseSet<uint32_t> ContextIdsToMove) {
4211 assert(NodeToCallingFunc.count(Node));
4212 ContextNode *Clone =
4213 createNewNode(
Node->IsAllocation, NodeToCallingFunc[Node],
Node->Call);
4214 Node->addClone(Clone);
4215 Clone->MatchingCalls =
Node->MatchingCalls;
4216 moveEdgeToExistingCalleeClone(
Edge, Clone,
true,
4221template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4222void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
4223 moveEdgeToExistingCalleeClone(
const std::shared_ptr<ContextEdge> &
Edge,
4224 ContextNode *NewCallee,
bool NewClone,
4225 DenseSet<uint32_t> ContextIdsToMove) {
4228 assert(NewCallee->getOrigNode() ==
Edge->Callee->getOrigNode());
4230 bool EdgeIsRecursive =
Edge->Callee ==
Edge->Caller;
4232 ContextNode *OldCallee =
Edge->Callee;
4236 auto ExistingEdgeToNewCallee = NewCallee->findEdgeFromCaller(
Edge->Caller);
4240 if (ContextIdsToMove.
empty())
4241 ContextIdsToMove =
Edge->getContextIds();
4245 if (
Edge->getContextIds().size() == ContextIdsToMove.
size()) {
4248 NewCallee->AllocTypes |=
Edge->AllocTypes;
4250 if (ExistingEdgeToNewCallee) {
4253 ExistingEdgeToNewCallee->getContextIds().insert_range(ContextIdsToMove);
4254 ExistingEdgeToNewCallee->AllocTypes |=
Edge->AllocTypes;
4255 assert(
Edge->ContextIds == ContextIdsToMove);
4256 removeEdgeFromGraph(
Edge.get());
4259 Edge->Callee = NewCallee;
4260 NewCallee->CallerEdges.push_back(
Edge);
4262 OldCallee->eraseCallerEdge(
Edge.get());
4269 auto CallerEdgeAllocType = computeAllocType(ContextIdsToMove);
4270 if (ExistingEdgeToNewCallee) {
4273 ExistingEdgeToNewCallee->getContextIds().insert_range(ContextIdsToMove);
4274 ExistingEdgeToNewCallee->AllocTypes |= CallerEdgeAllocType;
4277 auto NewEdge = std::make_shared<ContextEdge>(
4278 NewCallee,
Edge->Caller, CallerEdgeAllocType, ContextIdsToMove);
4279 Edge->Caller->CalleeEdges.push_back(NewEdge);
4280 NewCallee->CallerEdges.push_back(NewEdge);
4284 NewCallee->AllocTypes |= CallerEdgeAllocType;
4286 Edge->AllocTypes = computeAllocType(
Edge->ContextIds);
4291 for (
auto &OldCalleeEdge : OldCallee->CalleeEdges) {
4292 ContextNode *CalleeToUse = OldCalleeEdge->Callee;
4296 if (CalleeToUse == OldCallee) {
4300 if (EdgeIsRecursive) {
4304 CalleeToUse = NewCallee;
4308 DenseSet<uint32_t> EdgeContextIdsToMove =
4310 set_subtract(OldCalleeEdge->getContextIds(), EdgeContextIdsToMove);
4311 OldCalleeEdge->AllocTypes =
4312 computeAllocType(OldCalleeEdge->getContextIds());
4319 if (
auto *NewCalleeEdge = NewCallee->findEdgeFromCallee(CalleeToUse)) {
4320 NewCalleeEdge->getContextIds().insert_range(EdgeContextIdsToMove);
4321 NewCalleeEdge->AllocTypes |= computeAllocType(EdgeContextIdsToMove);
4325 auto NewEdge = std::make_shared<ContextEdge>(
4326 CalleeToUse, NewCallee, computeAllocType(EdgeContextIdsToMove),
4327 EdgeContextIdsToMove);
4328 NewCallee->CalleeEdges.push_back(NewEdge);
4329 NewEdge->Callee->CallerEdges.push_back(NewEdge);
4333 OldCallee->AllocTypes = OldCallee->computeAllocType();
4335 assert((OldCallee->AllocTypes == (uint8_t)AllocationType::None) ==
4336 OldCallee->emptyContextIds());
4340 for (
const auto &OldCalleeEdge : OldCallee->CalleeEdges)
4343 for (
const auto &NewCalleeEdge : NewCallee->CalleeEdges)
4349template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4350void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
4351 moveCalleeEdgeToNewCaller(
const std::shared_ptr<ContextEdge> &
Edge,
4352 ContextNode *NewCaller) {
4353 auto *OldCallee =
Edge->Callee;
4354 auto *NewCallee = OldCallee;
4357 bool Recursive =
Edge->Caller ==
Edge->Callee;
4359 NewCallee = NewCaller;
4361 ContextNode *OldCaller =
Edge->Caller;
4362 OldCaller->eraseCalleeEdge(
Edge.get());
4366 auto ExistingEdgeToNewCaller = NewCaller->findEdgeFromCallee(NewCallee);
4368 if (ExistingEdgeToNewCaller) {
4371 ExistingEdgeToNewCaller->getContextIds().insert_range(
4372 Edge->getContextIds());
4373 ExistingEdgeToNewCaller->AllocTypes |=
Edge->AllocTypes;
4374 Edge->ContextIds.clear();
4375 Edge->AllocTypes = (uint8_t)AllocationType::None;
4376 OldCallee->eraseCallerEdge(
Edge.get());
4379 Edge->Caller = NewCaller;
4380 NewCaller->CalleeEdges.push_back(
Edge);
4382 assert(NewCallee == NewCaller);
4385 Edge->Callee = NewCallee;
4386 NewCallee->CallerEdges.push_back(
Edge);
4387 OldCallee->eraseCallerEdge(
Edge.get());
4393 NewCaller->AllocTypes |=
Edge->AllocTypes;
4400 bool IsNewNode = NewCaller->CallerEdges.empty();
4409 for (
auto &OldCallerEdge : OldCaller->CallerEdges) {
4410 auto OldCallerCaller = OldCallerEdge->Caller;
4414 OldCallerEdge->getContextIds(),
Edge->getContextIds());
4415 if (OldCaller == OldCallerCaller) {
4416 OldCallerCaller = NewCaller;
4422 set_subtract(OldCallerEdge->getContextIds(), EdgeContextIdsToMove);
4423 OldCallerEdge->AllocTypes =
4424 computeAllocType(OldCallerEdge->getContextIds());
4429 auto *ExistingCallerEdge = NewCaller->findEdgeFromCaller(OldCallerCaller);
4433 if (ExistingCallerEdge) {
4434 ExistingCallerEdge->getContextIds().insert_range(EdgeContextIdsToMove);
4435 ExistingCallerEdge->AllocTypes |=
4436 computeAllocType(EdgeContextIdsToMove);
4439 auto NewEdge = std::make_shared<ContextEdge>(
4440 NewCaller, OldCallerCaller, computeAllocType(EdgeContextIdsToMove),
4441 EdgeContextIdsToMove);
4442 NewCaller->CallerEdges.push_back(NewEdge);
4443 NewEdge->Caller->CalleeEdges.push_back(NewEdge);
4448 OldCaller->AllocTypes = OldCaller->computeAllocType();
4450 assert((OldCaller->AllocTypes == (uint8_t)AllocationType::None) ==
4451 OldCaller->emptyContextIds());
4455 for (
const auto &OldCallerEdge : OldCaller->CallerEdges)
4458 for (
const auto &NewCallerEdge : NewCaller->CallerEdges)
4464template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4465void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
4466 recursivelyRemoveNoneTypeCalleeEdges(
4467 ContextNode *Node, DenseSet<const ContextNode *> &Visited) {
4472 removeNoneTypeCalleeEdges(Node);
4474 for (
auto *Clone :
Node->Clones)
4475 recursivelyRemoveNoneTypeCalleeEdges(Clone, Visited);
4479 auto CallerEdges =
Node->CallerEdges;
4480 for (
auto &
Edge : CallerEdges) {
4482 if (
Edge->isRemoved()) {
4486 recursivelyRemoveNoneTypeCalleeEdges(
Edge->Caller, Visited);
4491template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4492void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::markBackedges() {
4497 DenseSet<const ContextNode *> Visited;
4498 DenseSet<const ContextNode *> CurrentStack;
4499 for (
auto &Entry : NonAllocationCallToContextNodeMap) {
4501 if (
Node->isRemoved())
4504 if (!
Node->CallerEdges.empty())
4506 markBackedges(Node, Visited, CurrentStack);
4512template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4513void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::markBackedges(
4514 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
4515 DenseSet<const ContextNode *> &CurrentStack) {
4516 auto I = Visited.
insert(Node);
4520 for (
auto &CalleeEdge :
Node->CalleeEdges) {
4521 auto *
Callee = CalleeEdge->Callee;
4522 if (Visited.
count(Callee)) {
4525 if (CurrentStack.
count(Callee))
4526 CalleeEdge->IsBackedge =
true;
4529 CurrentStack.
insert(Callee);
4530 markBackedges(Callee, Visited, CurrentStack);
4531 CurrentStack.
erase(Callee);
4535template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4536void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones() {
4537 DenseSet<const ContextNode *> Visited;
4538 for (
auto &Entry : AllocationCallToContextNodeMap) {
4540 identifyClones(
Entry.second, Visited,
Entry.second->getContextIds());
4543 for (
auto &Entry : AllocationCallToContextNodeMap)
4544 recursivelyRemoveNoneTypeCalleeEdges(
Entry.second, Visited);
4557template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4558void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones(
4559 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
4560 const DenseSet<uint32_t> &AllocContextIds) {
4570 if (!
Node->hasCall())
4589 auto CallerEdges =
Node->CallerEdges;
4590 for (
auto &
Edge : CallerEdges) {
4592 if (
Edge->isRemoved()) {
4598 if (
Edge->IsBackedge) {
4605 if (!Visited.
count(
Edge->Caller) && !
Edge->Caller->CloneOf) {
4606 identifyClones(
Edge->Caller, Visited, AllocContextIds);
4629 const unsigned AllocTypeCloningPriority[] = { 3, 4,
4633 [&](
const std::shared_ptr<ContextEdge> &
A,
4634 const std::shared_ptr<ContextEdge> &
B) {
4637 if (A->ContextIds.empty())
4643 if (B->ContextIds.empty())
4646 if (A->AllocTypes == B->AllocTypes)
4649 return A->Caller->NodeId < B->Caller->NodeId;
4650 return AllocTypeCloningPriority[A->AllocTypes] <
4651 AllocTypeCloningPriority[B->AllocTypes];
4654 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
4656 DenseSet<uint32_t> RecursiveContextIds;
4661 DenseSet<uint32_t> AllCallerContextIds;
4662 for (
auto &CE :
Node->CallerEdges) {
4665 AllCallerContextIds.
reserve(
CE->getContextIds().size());
4666 for (
auto Id :
CE->getContextIds())
4667 if (!AllCallerContextIds.
insert(Id).second)
4668 RecursiveContextIds.
insert(Id);
4678 auto CallerEdges =
Node->CallerEdges;
4679 for (
auto &CallerEdge : CallerEdges) {
4681 if (CallerEdge->isRemoved()) {
4685 assert(CallerEdge->Callee == Node);
4694 if (!CallerEdge->Caller->hasCall())
4699 auto CallerEdgeContextsForAlloc =
4701 if (!RecursiveContextIds.
empty())
4702 CallerEdgeContextsForAlloc =
4704 if (CallerEdgeContextsForAlloc.empty())
4707 auto CallerAllocTypeForAlloc = computeAllocType(CallerEdgeContextsForAlloc);
4711 std::vector<uint8_t> CalleeEdgeAllocTypesForCallerEdge;
4712 CalleeEdgeAllocTypesForCallerEdge.reserve(
Node->CalleeEdges.size());
4713 for (
auto &CalleeEdge :
Node->CalleeEdges)
4714 CalleeEdgeAllocTypesForCallerEdge.push_back(intersectAllocTypes(
4715 CalleeEdge->getContextIds(), CallerEdgeContextsForAlloc));
4731 assert(CallerEdge->AllocTypes != (uint8_t)AllocationType::None);
4732 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
4733 if (!CallerEdge->IsBackedge &&
4734 allocTypeToUse(CallerAllocTypeForAlloc) ==
4735 allocTypeToUse(
Node->AllocTypes) &&
4736 allocTypesMatch<DerivedCCG, FuncTy, CallTy>(
4737 CalleeEdgeAllocTypesForCallerEdge,
Node->CalleeEdges)) {
4741 if (CallerEdge->IsBackedge) {
4745 DeferredBackedges++;
4758 if (CallerEdge->IsBackedge && !CallerEdge->Caller->CloneOf &&
4759 !Visited.
count(CallerEdge->Caller)) {
4760 const auto OrigIdCount = CallerEdge->getContextIds().size();
4763 identifyClones(CallerEdge->Caller, Visited, CallerEdgeContextsForAlloc);
4764 removeNoneTypeCalleeEdges(CallerEdge->Caller);
4768 bool UpdatedEdge =
false;
4769 if (OrigIdCount > CallerEdge->getContextIds().size()) {
4770 for (
auto E :
Node->CallerEdges) {
4772 if (
E->Caller->CloneOf != CallerEdge->Caller)
4776 auto CallerEdgeContextsForAllocNew =
4778 if (CallerEdgeContextsForAllocNew.empty())
4788 CallerEdgeContextsForAlloc.swap(CallerEdgeContextsForAllocNew);
4798 if (CallerEdge->isRemoved())
4808 CallerEdgeContextsForAlloc, CallerEdge->getContextIds());
4809 if (CallerEdgeContextsForAlloc.empty())
4814 CallerAllocTypeForAlloc = computeAllocType(CallerEdgeContextsForAlloc);
4815 CalleeEdgeAllocTypesForCallerEdge.clear();
4816 for (
auto &CalleeEdge :
Node->CalleeEdges) {
4817 CalleeEdgeAllocTypesForCallerEdge.push_back(intersectAllocTypes(
4818 CalleeEdge->getContextIds(), CallerEdgeContextsForAlloc));
4824 ContextNode *Clone =
nullptr;
4825 for (
auto *CurClone :
Node->Clones) {
4826 if (allocTypeToUse(CurClone->AllocTypes) !=
4827 allocTypeToUse(CallerAllocTypeForAlloc))
4834 assert(!BothSingleAlloc ||
4835 CurClone->AllocTypes == CallerAllocTypeForAlloc);
4841 if (BothSingleAlloc || allocTypesMatchClone<DerivedCCG, FuncTy, CallTy>(
4842 CalleeEdgeAllocTypesForCallerEdge, CurClone)) {
4850 moveEdgeToExistingCalleeClone(CallerEdge, Clone,
false,
4851 CallerEdgeContextsForAlloc);
4853 Clone = moveEdgeToNewCalleeClone(CallerEdge, CallerEdgeContextsForAlloc);
4856 assert(Clone->AllocTypes != (uint8_t)AllocationType::None);
4863 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
4869void ModuleCallsiteContextGraph::updateAllocationCall(
4885 .emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofAttribute",
Call.call())
4886 <<
ore::NV(
"AllocationCall",
Call.call()) <<
" in clone "
4888 <<
" marked with memprof allocation attribute "
4889 <<
ore::NV(
"Attribute", AllocTypeString));
4892void IndexCallsiteContextGraph::updateAllocationCall(CallInfo &
Call,
4896 assert(AI->Versions.size() >
Call.cloneNo());
4901ModuleCallsiteContextGraph::getAllocationCallType(
const CallInfo &
Call)
const {
4903 if (!CB->getAttributes().hasFnAttr(
"memprof"))
4904 return AllocationType::None;
4905 StringRef AllocTypeString =
4906 CB->getAttributes().getFnAttr(
"memprof").getValueAsString();
4907 if (AllocTypeString ==
"cold")
4908 return AllocationType::Cold;
4909 if (AllocTypeString ==
"ambiguous")
4911 (uint8_t)AllocationType::Cold);
4912 return AllocationType::NotCold;
4916IndexCallsiteContextGraph::getAllocationCallType(
const CallInfo &
Call)
const {
4918 assert(AI->Versions.size() >
Call.cloneNo());
4922void ModuleCallsiteContextGraph::updateCall(CallInfo &CallerCall,
4923 FuncInfo CalleeFunc) {
4924 auto *CurF = getCalleeFunc(CallerCall.call());
4925 auto NewCalleeCloneNo = CalleeFunc.cloneNo();
4932 if (CurCalleeCloneNo != NewCalleeCloneNo) {
4934 << CurCalleeCloneNo <<
" now " << NewCalleeCloneNo
4936 MismatchedCloneAssignments++;
4939 if (NewCalleeCloneNo > 0)
4940 cast<CallBase>(CallerCall.call())->setCalledFunction(CalleeFunc.func());
4941 OREGetter(CallerCall.call()->getFunction())
4942 .emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofCall", CallerCall.call())
4943 <<
ore::NV(
"Call", CallerCall.call()) <<
" in clone "
4944 <<
ore::NV(
"Caller", CallerCall.call()->getFunction())
4945 <<
" assigned to call function clone "
4946 <<
ore::NV(
"Callee", CalleeFunc.func()));
4949void IndexCallsiteContextGraph::updateCall(CallInfo &CallerCall,
4950 FuncInfo CalleeFunc) {
4953 "Caller cannot be an allocation which should not have profiled calls");
4954 assert(CI->Clones.size() > CallerCall.cloneNo());
4955 auto NewCalleeCloneNo = CalleeFunc.cloneNo();
4956 auto &CurCalleeCloneNo = CI->Clones[CallerCall.cloneNo()];
4961 if (CurCalleeCloneNo != 0 && CurCalleeCloneNo != NewCalleeCloneNo) {
4963 << CurCalleeCloneNo <<
" now " << NewCalleeCloneNo
4965 MismatchedCloneAssignments++;
4967 CurCalleeCloneNo = NewCalleeCloneNo;
4979 SP->replaceLinkageName(MDName);
4983 TempDISubprogram NewDecl = Decl->
clone();
4984 NewDecl->replaceLinkageName(MDName);
4988CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
4990ModuleCallsiteContextGraph::cloneFunctionForCallsite(
4991 FuncInfo &Func, CallInfo &
Call, DenseMap<CallInfo, CallInfo> &CallMap,
4992 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
4997 assert(!
Func.func()->getParent()->getFunction(Name));
4998 NewFunc->setName(Name);
5000 for (
auto &Inst : CallsWithMetadataInFunc) {
5002 assert(Inst.cloneNo() == 0);
5005 OREGetter(
Func.func())
5006 .emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofClone",
Func.func())
5007 <<
"created clone " <<
ore::NV(
"NewFunction", NewFunc));
5008 return {NewFunc, CloneNo};
5011CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
5012 IndexCall>::FuncInfo
5013IndexCallsiteContextGraph::cloneFunctionForCallsite(
5014 FuncInfo &Func, CallInfo &
Call, DenseMap<CallInfo, CallInfo> &CallMap,
5015 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
5029 for (
auto &Inst : CallsWithMetadataInFunc) {
5031 assert(Inst.cloneNo() == 0);
5033 assert(AI->Versions.size() == CloneNo);
5036 AI->Versions.push_back(0);
5039 assert(CI && CI->Clones.size() == CloneNo);
5042 CI->Clones.push_back(0);
5044 CallMap[Inst] = {Inst.call(), CloneNo};
5046 return {
Func.func(), CloneNo};
5063template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5064void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::mergeClones() {
5070 DenseMap<uint32_t, ContextNode *> ContextIdToAllocationNode;
5071 for (
auto &Entry : AllocationCallToContextNodeMap) {
5073 for (
auto Id :
Node->getContextIds())
5074 ContextIdToAllocationNode[
Id] =
Node->getOrigNode();
5075 for (
auto *Clone :
Node->Clones) {
5076 for (
auto Id : Clone->getContextIds())
5077 ContextIdToAllocationNode[
Id] = Clone->getOrigNode();
5084 DenseSet<const ContextNode *> Visited;
5085 for (
auto &Entry : AllocationCallToContextNodeMap) {
5088 mergeClones(Node, Visited, ContextIdToAllocationNode);
5094 auto Clones =
Node->Clones;
5095 for (
auto *Clone : Clones)
5096 mergeClones(Clone, Visited, ContextIdToAllocationNode);
5100 dbgs() <<
"CCG after merging:\n";
5104 exportToDot(
"aftermerge");
5112template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5113void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::mergeClones(
5114 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
5115 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode) {
5125 bool FoundUnvisited =
true;
5127 while (FoundUnvisited) {
5129 FoundUnvisited =
false;
5132 auto CallerEdges =
Node->CallerEdges;
5133 for (
auto CallerEdge : CallerEdges) {
5135 if (CallerEdge->Callee != Node)
5140 FoundUnvisited =
true;
5141 mergeClones(CallerEdge->Caller, Visited, ContextIdToAllocationNode);
5145 TotalMergeInvokes++;
5146 TotalMergeIters += Iters;
5147 if (Iters > MaxMergeIters)
5148 MaxMergeIters = Iters;
5151 mergeNodeCalleeClones(Node, Visited, ContextIdToAllocationNode);
5154template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5155void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::mergeNodeCalleeClones(
5156 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
5157 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode) {
5159 if (
Node->emptyContextIds())
5164 MapVector<ContextNode *, std::vector<std::shared_ptr<ContextEdge>>>
5165 OrigNodeToCloneEdges;
5166 for (
const auto &
E :
Node->CalleeEdges) {
5171 OrigNodeToCloneEdges[
Base].push_back(
E);
5177 auto CalleeCallerEdgeLessThan = [](
const std::shared_ptr<ContextEdge> &
A,
5178 const std::shared_ptr<ContextEdge> &
B) {
5179 if (
A->Callee->CallerEdges.size() !=
B->Callee->CallerEdges.size())
5180 return A->Callee->CallerEdges.size() <
B->Callee->CallerEdges.size();
5181 if (
A->Callee->CloneOf && !
B->Callee->CloneOf)
5183 else if (!
A->Callee->CloneOf &&
B->Callee->CloneOf)
5186 return A->Callee->NodeId <
B->Callee->NodeId;
5191 for (
auto Entry : OrigNodeToCloneEdges) {
5194 auto &CalleeEdges =
Entry.second;
5195 auto NumCalleeClones = CalleeEdges.size();
5197 if (NumCalleeClones == 1)
5208 DenseSet<ContextNode *> OtherCallersToShareMerge;
5209 findOtherCallersToShareMerge(Node, CalleeEdges, ContextIdToAllocationNode,
5210 OtherCallersToShareMerge);
5215 ContextNode *MergeNode =
nullptr;
5216 DenseMap<ContextNode *, unsigned> CallerToMoveCount;
5217 for (
auto CalleeEdge : CalleeEdges) {
5218 auto *OrigCallee = CalleeEdge->Callee;
5224 if (CalleeEdge->Callee->CallerEdges.size() == 1) {
5225 MergeNode = OrigCallee;
5226 NonNewMergedNodes++;
5233 if (!OtherCallersToShareMerge.
empty()) {
5234 bool MoveAllCallerEdges =
true;
5235 for (
auto CalleeCallerE : OrigCallee->CallerEdges) {
5236 if (CalleeCallerE == CalleeEdge)
5238 if (!OtherCallersToShareMerge.
contains(CalleeCallerE->Caller)) {
5239 MoveAllCallerEdges =
false;
5245 if (MoveAllCallerEdges) {
5246 MergeNode = OrigCallee;
5247 NonNewMergedNodes++;
5254 assert(MergeNode != OrigCallee);
5255 moveEdgeToExistingCalleeClone(CalleeEdge, MergeNode,
5258 MergeNode = moveEdgeToNewCalleeClone(CalleeEdge);
5263 if (!OtherCallersToShareMerge.
empty()) {
5267 auto OrigCalleeCallerEdges = OrigCallee->CallerEdges;
5268 for (
auto &CalleeCallerE : OrigCalleeCallerEdges) {
5269 if (CalleeCallerE == CalleeEdge)
5271 if (!OtherCallersToShareMerge.
contains(CalleeCallerE->Caller))
5273 CallerToMoveCount[CalleeCallerE->Caller]++;
5274 moveEdgeToExistingCalleeClone(CalleeCallerE, MergeNode,
5278 removeNoneTypeCalleeEdges(OrigCallee);
5279 removeNoneTypeCalleeEdges(MergeNode);
5297template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5298void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
5299 findOtherCallersToShareMerge(
5301 std::vector<std::shared_ptr<ContextEdge>> &CalleeEdges,
5302 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode,
5303 DenseSet<ContextNode *> &OtherCallersToShareMerge) {
5304 auto NumCalleeClones = CalleeEdges.size();
5307 DenseMap<ContextNode *, unsigned> OtherCallersToSharedCalleeEdgeCount;
5310 unsigned PossibleOtherCallerNodes = 0;
5314 if (CalleeEdges[0]->
Callee->CallerEdges.size() < 2)
5320 DenseMap<ContextEdge *, DenseSet<ContextNode *>> CalleeEdgeToAllocNodes;
5321 for (
auto CalleeEdge : CalleeEdges) {
5322 assert(CalleeEdge->Callee->CallerEdges.size() > 1);
5325 for (
auto CalleeCallerEdges : CalleeEdge->Callee->CallerEdges) {
5326 if (CalleeCallerEdges->Caller == Node) {
5327 assert(CalleeCallerEdges == CalleeEdge);
5330 OtherCallersToSharedCalleeEdgeCount[CalleeCallerEdges->Caller]++;
5333 if (OtherCallersToSharedCalleeEdgeCount[CalleeCallerEdges->Caller] ==
5335 PossibleOtherCallerNodes++;
5339 for (
auto Id : CalleeEdge->getContextIds()) {
5340 auto *
Alloc = ContextIdToAllocationNode.
lookup(Id);
5344 MissingAllocForContextId++;
5347 CalleeEdgeToAllocNodes[CalleeEdge.get()].
insert(
Alloc);
5354 for (
auto CalleeEdge : CalleeEdges) {
5355 assert(CalleeEdge->Callee->CallerEdges.size() > 1);
5357 if (!PossibleOtherCallerNodes)
5359 auto &CurCalleeAllocNodes = CalleeEdgeToAllocNodes[CalleeEdge.get()];
5361 for (
auto &CalleeCallerE : CalleeEdge->Callee->CallerEdges) {
5363 if (CalleeCallerE == CalleeEdge)
5367 if (OtherCallersToSharedCalleeEdgeCount[CalleeCallerE->Caller] !=
5372 for (
auto Id : CalleeCallerE->getContextIds()) {
5373 auto *
Alloc = ContextIdToAllocationNode.
lookup(Id);
5378 if (!CurCalleeAllocNodes.contains(
Alloc)) {
5379 OtherCallersToSharedCalleeEdgeCount[CalleeCallerE->Caller] = 0;
5380 PossibleOtherCallerNodes--;
5387 if (!PossibleOtherCallerNodes)
5392 for (
auto &[OtherCaller,
Count] : OtherCallersToSharedCalleeEdgeCount) {
5393 if (
Count != NumCalleeClones)
5395 OtherCallersToShareMerge.
insert(OtherCaller);
5399template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5400const typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
5401CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::resolveImplicitSource(
5402 const ContextNode *Node,
const ImplicitSource &Src) {
5403 if (!Src.Source->emptyContextIds())
5409 if (
Node->hasContextId(Src.ContextId))
5411 for (
const ContextNode *
C :
Node->Clones)
5412 if (
C->hasContextId(Src.ContextId))
5417 assert(
false &&
"trimmed context id on no clone of its callsite node");
5459template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5460void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::assignImplicitCallers(
5461 ContextNode *Node,
const DenseSet<uint32_t> &TrimmedContextIds,
5462 DenseMap<ContextNode *, FuncInfo> &CallsiteToCalleeFuncCloneMap,
5463 const std::map<FuncInfo, ContextNode *> &FuncCloneToCurNodeCloneMap,
5464 ImplicitSourceMap &ImplicitSources) {
5465 auto HasEdgeToNodeFamily = [&](
const ContextNode *
N) {
5467 [&](
const std::shared_ptr<ContextEdge> &
E) {
5468 return E->Callee->getOrigNode() == Node;
5502 auto ImpliesContextIds =
5503 [&](ContextNode *
K, ContextNode *
Y,
const DenseSet<uint32_t> &Ids,
5504 DenseMap<std::pair<ContextNode *, ContextNode *>, DenseSet<uint32_t>>
5506 auto &&ImpliesContextIds) ->
bool {
5507 assert(
K->getOrigNode() ==
Y->getOrigNode());
5508 DenseSet<uint32_t> &VisitedIds = Visited[{
K,
Y}];
5509 DenseSet<uint32_t> NewIds;
5511 if (VisitedIds.
insert(Id).second)
5519 DenseSet<uint32_t> IdsOnCallerEdges;
5520 for (
auto &YEdge :
Y->CallerEdges) {
5521 DenseSet<uint32_t> IdsFromZ =
5523 if (IdsFromZ.
empty())
5526 IdsFromCallers.
push_back({YEdge->Caller, std::move(IdsFromZ)});
5530 if (IdsOnCallerEdges.
size() < NewIds.
size())
5534 for (
auto &[Z, IdsFromZ] : IdsFromCallers) {
5535 for (
auto &KEdge :
K->CallerEdges) {
5536 ContextNode *
C = KEdge->Caller;
5537 if (
C == Z ||
C->getOrigNode() !=
Z->getOrigNode())
5541 DenseSet<uint32_t> IdsNotOnC;
5542 for (
auto Id : IdsFromZ)
5543 if (!
C->hasContextId(Id))
5545 if (!IdsNotOnC.
empty() &&
5546 ImpliesContextIds(
C, Z, IdsNotOnC, Visited, ImpliesContextIds))
5555 auto SameVersion = [&](
const ContextNode *
A,
const ContextNode *
B) {
5558 if (
Node->IsAllocation)
5559 return allocTypeToUse(
A->AllocTypes) == allocTypeToUse(
B->AllocTypes);
5560 auto AIt = CallsiteToCalleeFuncCloneMap.
find(
A);
5561 auto BIt = CallsiteToCalleeFuncCloneMap.
find(
B);
5562 return AIt != CallsiteToCalleeFuncCloneMap.
end() &&
5563 BIt != CallsiteToCalleeFuncCloneMap.
end() &&
5564 AIt->second == BIt->second;
5568 DenseSet<const ContextNode *> ImplicitCallers;
5573 auto ProcessCaller = [&](
const std::shared_ptr<ContextEdge> &
Edge) {
5574 ContextNode *
Y =
Edge->Caller;
5575 ContextNode *Orig =
Y->getOrigNode();
5576 if (!
Y->hasCall() || Orig->Clones.empty())
5578 DenseSet<uint32_t> TrimmedIds =
5580 if (TrimmedIds.
empty())
5582 auto YIt = CallsiteToCalleeFuncCloneMap.
find(
Y);
5583 if (YIt == CallsiteToCalleeFuncCloneMap.
end())
5586 const FuncInfo YFuncClone = YIt->second;
5589 auto RequiredIt = FuncCloneToCurNodeCloneMap.find(YFuncClone);
5590 assert(RequiredIt != FuncCloneToCurNodeCloneMap.end());
5591 const ContextNode *
Required = RequiredIt->second;
5599 auto RecordImplicitSource = [&](
const FuncInfo &
F,
const ContextNode *Src) {
5602 if (
F.cloneNo() != 0)
5603 ImplicitSources.try_emplace({
Node,
F.cloneNo()},
5604 ImplicitSource{Src, *TrimmedIds.
begin()});
5610 if (K ==
Y || !
K->hasCall() ||
K->emptyContextIds() ||
5611 HasEdgeToNodeFamily(K) || ImplicitCallers.
contains(K))
5613 DenseMap<std::pair<ContextNode *, ContextNode *>, DenseSet<uint32_t>>
5615 if (!ImpliesContextIds(K,
Y, TrimmedIds, Visited, ImpliesContextIds))
5618 ImplicitCallers.
insert(K);
5619 auto KIt = CallsiteToCalleeFuncCloneMap.
find(K);
5620 if (KIt == CallsiteToCalleeFuncCloneMap.
end()) {
5623 CallsiteToCalleeFuncCloneMap[
K] = YFuncClone;
5624 RecordImplicitSource(YFuncClone, Required);
5625 NumImplicitCallersAssigned++;
5628 const FuncInfo KFuncClone = KIt->second;
5629 if (KFuncClone == YFuncClone) {
5631 RecordImplicitSource(YFuncClone, Required);
5634 unsigned KCloneNo = KFuncClone.cloneNo();
5635 auto KNodeCloneIt = FuncCloneToCurNodeCloneMap.find(KFuncClone);
5636 if (KNodeCloneIt == FuncCloneToCurNodeCloneMap.end()) {
5638 if (KCloneNo == 0) {
5642 if (
Node->IsAllocation) {
5643 if (allocTypeToUse(
Required->AllocTypes) == AllocationType::NotCold)
5645 }
else if (
auto It = CallsiteToCalleeFuncCloneMap.
find(Required);
5646 It != CallsiteToCalleeFuncCloneMap.
end() &&
5647 It->second.cloneNo() == 0)
5653 auto [It,
Inserted] = ImplicitSources.try_emplace(
5656 NumImplicitCallersSourced++;
5657 if (SameVersion(It->second.Source, Required))
5660 }
else if (SameVersion(KNodeCloneIt->second, Required)) {
5663 RecordImplicitSource(KFuncClone, KNodeCloneIt->second);
5667 NumImplicitCallersUnresolved++;
5673 for (
auto &
Edge :
Node->CallerEdges)
5674 ProcessCaller(
Edge);
5675 for (
auto *Clone :
Node->Clones)
5676 for (
auto &
Edge : Clone->CallerEdges)
5677 ProcessCaller(
Edge);
5721template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5722bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::assignFunctions() {
5730 DenseSet<uint32_t> TrimmedContextIds;
5731 for (
auto &NodePtr : NodeOwner) {
5732 ContextNode *
N = NodePtr.get();
5733 if (
N->IsAllocation ||
N->CalleeEdges.empty() ||
5734 (
N->CallerEdges.empty() &&
N->Clones.empty() && !
N->CloneOf))
5739 DenseSet<uint32_t> CallerIds;
5740 for (
auto &
E :
N->CallerEdges)
5742 for (
auto &CalleeEdge :
N->CalleeEdges)
5743 for (
auto Id : CalleeEdge->getContextIds())
5745 TrimmedContextIds.
insert(Id);
5747 NumTrimmedContextIds += TrimmedContextIds.
size();
5751 DenseMap<ContextNode *, FuncInfo> CallsiteToCalleeFuncCloneMap;
5755 auto RecordCalleeFuncOfCallsite = [&](ContextNode *
Caller,
5756 const FuncInfo &CalleeFunc) {
5758 CallsiteToCalleeFuncCloneMap[
Caller] = CalleeFunc;
5762 struct FuncCloneInfo {
5767 DenseMap<CallInfo, CallInfo> CallMap;
5803 struct UnassignedCallCloneInfo {
5805 const ContextNode *
Source =
nullptr;
5807 DenseMap<const ContextNode *, std::map<unsigned, UnassignedCallCloneInfo>>
5808 UnassignedCallClones;
5812 for (
auto &[Func, CallsWithMetadata] : FuncToCallsWithMetadata) {
5813 FuncInfo OrigFunc(Func);
5818 std::vector<FuncCloneInfo> FuncCloneInfos;
5825 std::vector<unsigned> FuncCloneParent;
5828 ImplicitSourceMap ImplicitSources;
5835 struct OrigCallsInfo {
5839 DenseMap<const ContextNode *, OrigCallsInfo> OrigNodeToOrigCalls;
5840 for (
auto &
Call : CallsWithMetadata) {
5841 ContextNode *
Node = getNodeForInst(
Call);
5843 OrigNodeToOrigCalls[
Node] = {
Call,
Node->MatchingCalls};
5845 for (
auto &
Call : CallsWithMetadata) {
5846 ContextNode *
Node = getNodeForInst(
Call);
5850 if (!Node ||
Node->Clones.empty())
5853 "Not having a call should have prevented cloning");
5857 std::map<FuncInfo, ContextNode *> FuncCloneToCurNodeCloneMap;
5861 auto AssignCallsiteCloneToFuncClone = [&](
const FuncInfo &FuncClone,
5863 ContextNode *CallsiteClone,
5866 FuncCloneToCurNodeCloneMap[FuncClone] = CallsiteClone;
5868 assert(FuncCloneInfos.size() > FuncClone.cloneNo());
5869 DenseMap<CallInfo, CallInfo> &CallMap =
5870 FuncCloneInfos[FuncClone.cloneNo()].CallMap;
5871 CallInfo CallClone(
Call);
5872 if (
auto It = CallMap.
find(
Call); It != CallMap.
end())
5873 CallClone = It->second;
5874 CallsiteClone->setCall(CallClone);
5880 CallsiteClone->MatchingCalls.clear();
5881 for (
const CallInfo &OrigMatchingCall :
5882 OrigNodeToOrigCalls[Node].MatchingCalls) {
5883 CallInfo CallClone(OrigMatchingCall);
5884 if (
auto It = CallMap.
find(OrigMatchingCall); It != CallMap.
end())
5885 CallClone = It->second;
5886 CallsiteClone->MatchingCalls.push_back(CallClone);
5894 auto MoveEdgeToNewCalleeCloneAndSetUp =
5895 [&](
const std::shared_ptr<ContextEdge> &
Edge) {
5896 ContextNode *OrigCallee =
Edge->Callee;
5897 ContextNode *NewClone = moveEdgeToNewCalleeClone(
Edge);
5898 removeNoneTypeCalleeEdges(NewClone);
5899 assert(NewClone->AllocTypes != (uint8_t)AllocationType::None);
5903 if (CallsiteToCalleeFuncCloneMap.
count(OrigCallee))
5904 RecordCalleeFuncOfCallsite(
5905 NewClone, CallsiteToCalleeFuncCloneMap[OrigCallee]);
5912 std::deque<ContextNode *> ClonesWorklist;
5914 if (!
Node->emptyContextIds())
5915 ClonesWorklist.push_back(Node);
5921 unsigned NodeCloneCount = 0;
5922 while (!ClonesWorklist.empty()) {
5923 ContextNode *Clone = ClonesWorklist.front();
5924 ClonesWorklist.pop_front();
5933 if (FuncCloneInfos.size() < NodeCloneCount) {
5935 if (NodeCloneCount == 1) {
5940 Clone->CallerEdges, [&](
const std::shared_ptr<ContextEdge> &
E) {
5941 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
5945 FuncCloneInfos.push_back(
5946 {OrigFunc, DenseMap<CallInfo, CallInfo>()});
5947 FuncCloneParent.push_back(0);
5948 AssignCallsiteCloneToFuncClone(
5949 OrigFunc,
Call, Clone,
5950 AllocationCallToContextNodeMap.count(
Call));
5951 for (
auto &CE : Clone->CallerEdges) {
5953 if (!
CE->Caller->hasCall())
5955 RecordCalleeFuncOfCallsite(
CE->Caller, OrigFunc);
5965 FuncInfo PreviousAssignedFuncClone;
5967 Clone->CallerEdges, [&](
const std::shared_ptr<ContextEdge> &
E) {
5968 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
5970 bool CallerAssignedToCloneOfFunc =
false;
5971 if (EI != Clone->CallerEdges.end()) {
5972 const std::shared_ptr<ContextEdge> &
Edge = *EI;
5973 PreviousAssignedFuncClone =
5974 CallsiteToCalleeFuncCloneMap[
Edge->Caller];
5975 CallerAssignedToCloneOfFunc =
true;
5980 DenseMap<CallInfo, CallInfo> NewCallMap;
5981 unsigned CloneNo = FuncCloneInfos.size();
5982 assert(CloneNo > 0 &&
"Clone 0 is the original function, which "
5983 "should already exist in the map");
5984 FuncInfo NewFuncClone = cloneFunctionForCallsite(
5985 OrigFunc,
Call, NewCallMap, CallsWithMetadata, CloneNo);
5986 FuncCloneInfos.push_back({NewFuncClone, std::move(NewCallMap)});
5989 FuncCloneParent.push_back(CallerAssignedToCloneOfFunc
5990 ? PreviousAssignedFuncClone.cloneNo()
5992 FunctionClonesAnalysis++;
5998 if (!CallerAssignedToCloneOfFunc) {
5999 AssignCallsiteCloneToFuncClone(
6000 NewFuncClone,
Call, Clone,
6001 AllocationCallToContextNodeMap.count(
Call));
6002 for (
auto &CE : Clone->CallerEdges) {
6004 if (!
CE->Caller->hasCall())
6006 RecordCalleeFuncOfCallsite(
CE->Caller, NewFuncClone);
6018 auto CallerEdges = Clone->CallerEdges;
6019 for (
auto CE : CallerEdges) {
6021 if (
CE->isRemoved()) {
6027 if (!
CE->Caller->hasCall())
6030 if (!CallsiteToCalleeFuncCloneMap.
count(
CE->Caller) ||
6034 CallsiteToCalleeFuncCloneMap[
CE->Caller] !=
6035 PreviousAssignedFuncClone)
6038 RecordCalleeFuncOfCallsite(
CE->Caller, NewFuncClone);
6051 auto CalleeEdges =
CE->Caller->CalleeEdges;
6052 for (
auto CalleeEdge : CalleeEdges) {
6055 if (CalleeEdge->isRemoved()) {
6060 ContextNode *
Callee = CalleeEdge->Callee;
6064 if (Callee == Clone || !
Callee->hasCall())
6069 if (Callee == CalleeEdge->Caller)
6071 ContextNode *NewClone =
6072 MoveEdgeToNewCalleeCloneAndSetUp(CalleeEdge);
6075 removeNoneTypeCalleeEdges(Callee);
6088 auto &OrigCalls = OrigNodeToOrigCalls[
Callee->getOrigNode()];
6089 DenseMap<CallInfo, CallInfo> &CallMap =
6090 FuncCloneInfos[NewFuncClone.cloneNo()].CallMap;
6092 CallInfo NewCall(CallMap[OrigCalls.Call]);
6094 NewClone->setCall(NewCall);
6096 NewClone->MatchingCalls.clear();
6097 for (
auto &OrigMatchingCall : OrigCalls.MatchingCalls) {
6099 CallInfo NewCall(CallMap[OrigMatchingCall]);
6101 NewClone->MatchingCalls.push_back(NewCall);
6110 auto FindFirstAvailFuncClone = [&]() {
6115 for (
auto &CF : FuncCloneInfos) {
6116 if (!FuncCloneToCurNodeCloneMap.count(CF.FuncClone))
6117 return CF.FuncClone;
6120 "Expected an available func clone for this callsite clone");
6137 std::map<FuncInfo, ContextNode *> FuncCloneToNewCallsiteCloneMap;
6138 FuncInfo FuncCloneAssignedToCurCallsiteClone;
6142 auto CloneCallerEdges = Clone->CallerEdges;
6143 for (
auto &
Edge : CloneCallerEdges) {
6147 if (
Edge->isRemoved())
6150 if (!
Edge->Caller->hasCall())
6154 if (CallsiteToCalleeFuncCloneMap.
count(
Edge->Caller)) {
6155 FuncInfo FuncCloneCalledByCaller =
6156 CallsiteToCalleeFuncCloneMap[
Edge->Caller];
6166 if ((FuncCloneToCurNodeCloneMap.count(FuncCloneCalledByCaller) &&
6167 FuncCloneToCurNodeCloneMap[FuncCloneCalledByCaller] !=
6175 (FuncCloneAssignedToCurCallsiteClone &&
6176 FuncCloneAssignedToCurCallsiteClone !=
6177 FuncCloneCalledByCaller)) {
6192 if (FuncCloneToNewCallsiteCloneMap.count(
6193 FuncCloneCalledByCaller)) {
6194 ContextNode *NewClone =
6195 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller];
6196 moveEdgeToExistingCalleeClone(
Edge, NewClone);
6198 removeNoneTypeCalleeEdges(NewClone);
6201 ContextNode *NewClone = MoveEdgeToNewCalleeCloneAndSetUp(
Edge);
6202 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller] =
6205 ClonesWorklist.push_back(NewClone);
6209 removeNoneTypeCalleeEdges(Clone);
6217 if (!FuncCloneAssignedToCurCallsiteClone) {
6218 FuncCloneAssignedToCurCallsiteClone = FuncCloneCalledByCaller;
6220 AssignCallsiteCloneToFuncClone(
6221 FuncCloneCalledByCaller,
Call, Clone,
6222 AllocationCallToContextNodeMap.count(
Call));
6226 assert(FuncCloneAssignedToCurCallsiteClone ==
6227 FuncCloneCalledByCaller);
6236 if (!FuncCloneAssignedToCurCallsiteClone) {
6237 FuncCloneAssignedToCurCallsiteClone = FindFirstAvailFuncClone();
6238 assert(FuncCloneAssignedToCurCallsiteClone);
6240 AssignCallsiteCloneToFuncClone(
6241 FuncCloneAssignedToCurCallsiteClone,
Call, Clone,
6242 AllocationCallToContextNodeMap.count(
Call));
6244 assert(FuncCloneToCurNodeCloneMap
6245 [FuncCloneAssignedToCurCallsiteClone] == Clone);
6247 RecordCalleeFuncOfCallsite(
Edge->Caller,
6248 FuncCloneAssignedToCurCallsiteClone);
6268 if (!FuncCloneAssignedToCurCallsiteClone) {
6269 FuncCloneAssignedToCurCallsiteClone = FindFirstAvailFuncClone();
6270 assert(FuncCloneAssignedToCurCallsiteClone &&
6271 "No available func clone for this callsite clone");
6272 AssignCallsiteCloneToFuncClone(
6273 FuncCloneAssignedToCurCallsiteClone,
Call, Clone,
6274 AllocationCallToContextNodeMap.contains(
Call));
6277 assignImplicitCallers(Node, TrimmedContextIds,
6278 CallsiteToCalleeFuncCloneMap,
6279 FuncCloneToCurNodeCloneMap, ImplicitSources);
6282 for (
const auto &PE :
Node->CalleeEdges)
6284 for (
const auto &CE :
Node->CallerEdges)
6286 for (
auto *Clone :
Node->Clones) {
6288 for (
const auto &PE : Clone->CalleeEdges)
6290 for (
const auto &CE : Clone->CallerEdges)
6297 FuncToNumClones[
Func] = std::max<unsigned>(1, FuncCloneInfos.size());
6298 if (FuncCloneInfos.size() < 2)
6304 for (
auto &
Call : CallsWithMetadata) {
6305 ContextNode *
Node = getNodeForInst(
Call);
6306 if (!Node || !
Node->hasCall() ||
Node->emptyContextIds())
6311 DenseMap<unsigned, const ContextNode *> FuncCloneToNodeClone;
6312 FuncCloneToNodeClone[
Node->Call.cloneNo()] =
Node;
6320 for (
auto *
C :
Node->Clones)
6321 if (!
C->emptyContextIds() ||
6322 !ImplicitSources.contains({Node, C->Call.cloneNo()}))
6323 FuncCloneToNodeClone[
C->Call.cloneNo()] =
C;
6326 if (FuncCloneToNodeClone.
size() >= FuncCloneInfos.size())
6329 for (
auto &FC : FuncCloneInfos) {
6330 unsigned I =
FC.FuncClone.cloneNo();
6333 if (
I == 0 || FuncCloneToNodeClone.
contains(
I)) {
6341 auto &
Info = UnassignedCallClones[
Node][
I];
6342 auto &CallVector =
Info.Calls;
6343 for (
unsigned P =
I;;
P = FuncCloneParent[
P]) {
6344 if (
auto It = ImplicitSources.find({Node, P});
6345 It != ImplicitSources.end()) {
6346 Info.Source = resolveImplicitSource(Node, It->second);
6349 if (
auto It = FuncCloneToNodeClone.
find(
P);
6350 It != FuncCloneToNodeClone.
end()) {
6351 Info.Source = It->second;
6357 DenseMap<CallInfo, CallInfo> &CallMap =
FC.CallMap;
6358 if (
auto It = CallMap.
find(
Call); It != CallMap.
end()) {
6359 CallInfo CallClone = It->second;
6360 CallVector.push_back(CallClone);
6364 assert(
false &&
"Expected to find call in CallMap");
6370 for (
const CallInfo &OrigMatchingCall :
6371 OrigNodeToOrigCalls[Node].MatchingCalls) {
6372 if (
auto It = CallMap.
find(OrigMatchingCall); It != CallMap.
end()) {
6373 CallInfo CallClone = It->second;
6374 CallVector.push_back(CallClone);
6378 assert(
false &&
"Expected to find call in CallMap");
6386 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
6388 auto UpdateCalls = [&](ContextNode *
Node,
6389 DenseSet<const ContextNode *> &Visited,
6390 auto &&UpdateCalls) {
6391 auto Inserted = Visited.insert(Node);
6395 for (
auto *Clone :
Node->Clones)
6396 UpdateCalls(Clone, Visited, UpdateCalls);
6398 for (
auto &
Edge :
Node->CallerEdges)
6399 UpdateCalls(
Edge->Caller, Visited, UpdateCalls);
6403 if (!
Node->hasCall() ||
Node->emptyContextIds())
6409 auto GetUnassignedCallClones = [&](ContextNode *
Node) {
6412 auto UnassignedIt = UnassignedCallClones.
find(Node);
6413 if (UnassignedIt == UnassignedCallClones.
end())
6415 DenseSet<unsigned> NodeCallClones;
6416 for (
auto *
C :
Node->Clones)
6417 if (!
C->emptyContextIds())
6418 NodeCallClones.
insert(
C->Call.cloneNo());
6419 for (
auto &[CloneNo, Info] : UnassignedIt->second) {
6423 if (NodeCallClones.
contains(CloneNo))
6430 if (
Node->IsAllocation) {
6431 auto GetAllocTypeToUse = [&](
const ContextNode *
Node) {
6432 auto AT = allocTypeToUse(
Node->AllocTypes);
6444 !ContextIdToContextSizeInfos.
empty()) {
6447 for (
auto Id :
Node->getContextIds()) {
6448 auto TypeI = ContextIdToAllocationType.
find(Id);
6449 assert(TypeI != ContextIdToAllocationType.
end());
6450 auto CSI = ContextIdToContextSizeInfos.
find(Id);
6451 if (CSI != ContextIdToContextSizeInfos.
end()) {
6452 for (
auto &Info : CSI->second) {
6454 if (TypeI->second == AllocationType::Cold)
6455 TotalCold +=
Info.TotalSize;
6460 AT = AllocationType::Cold;
6464 updateAllocationCall(
Node->Call, GetAllocTypeToUse(Node));
6466 OrigAllocAndCloneToNode[{
Node->getOrigNode(),
Node->Call.cloneNo()}] =
6471 for (
auto &[Source, Calls] : GetUnassignedCallClones(Node)) {
6472 auto AT = GetAllocTypeToUse(Source);
6473 for (
auto &
Call : Calls) {
6474 updateAllocationCall(
Call, AT);
6477 OrigAllocAndCloneToNode[{
Node->getOrigNode(),
Call.cloneNo()}] =
6484 auto CalleeFuncIt = CallsiteToCalleeFuncCloneMap.
find(Node);
6485 if (CalleeFuncIt != CallsiteToCalleeFuncCloneMap.
end()) {
6486 auto &CalleeFunc = CalleeFuncIt->second;
6487 updateCall(
Node->Call, CalleeFunc);
6489 OrigNodeAndCloneToCalleeClone[{
6490 Node->getOrigNode(),
Node->Call.cloneNo()}] = CalleeFunc.cloneNo();
6492 for (
auto &
Call :
Node->MatchingCalls)
6493 updateCall(
Call, CalleeFunc);
6499 for (
auto &[Source, Calls] : GetUnassignedCallClones(Node)) {
6500 auto It = CallsiteToCalleeFuncCloneMap.
find(Source);
6502 if (It == CallsiteToCalleeFuncCloneMap.
end())
6504 if (It == CallsiteToCalleeFuncCloneMap.
end())
6506 for (
auto &
Call : Calls) {
6507 updateCall(
Call, It->second);
6509 OrigNodeAndCloneToCalleeClone[{
Node->getOrigNode(),
Call.cloneNo()}] =
6510 It->second.cloneNo();
6520 DenseSet<const ContextNode *> Visited;
6521 for (
auto &Entry : AllocationCallToContextNodeMap)
6522 UpdateCalls(
Entry.second, Visited, UpdateCalls);
6544 for (
auto [Index, SN] :
enumerate(FS->callsites())) {
6549 SN.Clones.size() >
I &&
6550 "Callsite summary has fewer entries than other summaries in function");
6551 if (SN.Clones.size() <=
I || !SN.Clones[
I])
6553 AddRecord(
'c', Index, SN.Clones[
I]);
6556 for (
auto [Index, AN] :
enumerate(FS->allocs())) {
6560 assert(AN.Versions.size() >
I &&
6561 "Alloc summary has fewer entries than other summaries in function");
6562 if (AN.Versions.size() <=
I ||
6565 AddRecord(
'a', Index, AN.Versions[
I]);
6574 for (
auto &SN : FS->callsites()) {
6575 assert(SN.Clones.size() >
I && SN.Clones.size() > J &&
6576 "Callsite summary has fewer entries than other summaries in "
6578 if (SN.Clones[
I] != SN.Clones[J])
6581 for (
auto &AN : FS->allocs()) {
6582 assert(AN.Versions.size() >
I && AN.Versions.size() > J &&
6583 "Alloc summary has fewer entries than other summaries in function");
6584 if (AN.Versions[
I] != AN.Versions[J])
6600 NewGV->takeName(DeclGV);
6607 auto CloneFuncAliases = [&](
Function *NewF,
unsigned I) {
6608 if (!FuncToAliasMap.count(&
F))
6610 for (
auto *
A : FuncToAliasMap[&
F]) {
6612 auto *PrevA = M.getNamedAlias(AliasName);
6614 A->getType()->getPointerAddressSpace(),
6615 A->getLinkage(), AliasName, NewF);
6616 NewA->copyAttributesFrom(
A);
6618 TakeDeclNameAndReplace(PrevA, NewA);
6627 FunctionsClonedThinBackend++;
6644 for (
unsigned I = 1;
I < NumClones;
I++) {
6645 VMaps.
emplace_back(std::make_unique<ValueToValueMapTy>());
6651 if (
auto It = HashToFunc.
find(Hash); It != HashToFunc.
end()) {
6652 FunctionCloneDuplicatesThinBackend++;
6653 auto [Func, OrigI] = It->second;
6655 "Duplicate clone hash collision");
6656 if (Func->hasAvailableExternallyLinkage()) {
6662 auto Decl = M.getOrInsertFunction(Name, Func->getFunctionType());
6664 <<
"created clone decl " <<
ore::NV(
"Decl", Decl.getCallee()));
6667 auto *PrevF = M.getFunction(Name);
6670 TakeDeclNameAndReplace(PrevF, Alias);
6672 <<
"created clone alias " <<
ore::NV(
"Alias", Alias));
6675 CloneFuncAliases(Func,
I);
6679 HashToFunc[Hash] = {NewF,
I};
6680 FunctionClonesThinBackend++;
6683 for (
auto &BB : *NewF) {
6684 for (
auto &Inst : BB) {
6685 Inst.setMetadata(LLVMContext::MD_memprof,
nullptr);
6686 Inst.setMetadata(LLVMContext::MD_callsite,
nullptr);
6689 auto *PrevF = M.getFunction(Name);
6691 TakeDeclNameAndReplace(PrevF, NewF);
6693 NewF->setName(Name);
6696 <<
"created clone " <<
ore::NV(
"NewFunction", NewF));
6699 CloneFuncAliases(NewF,
I);
6708static std::optional<GlobalValue::GUID>
6710 if (
auto *MD =
F.getMetadata(
"thinlto_alias_guid"))
6712 return std::nullopt;
6719 const Function *CallingFunc =
nullptr) {
6723 assert(AliasVI &&
"Expected ValueInfo for imported alias GUID");
6746 MDNode *SrcFileMD = GO ? GO->getMetadata(
"thinlto_src_file") :
nullptr;
6756 SrcFileMD = CallingFunc->getMetadata(
"thinlto_src_file");
6763 StringRef SrcFile = M.getSourceFileName();
6800 &OrigNameGUIDToTailCallCallsite,
6804 auto End = MapTailCallCalleeVIToCallsite.
end();
6808 auto It = MapTailCallCalleeVIToCallsite.
find(VI);
6817 auto It = MapTailCallCalleeVIToCallsite.
find(LocalVI);
6827 if (!OrigNameGUIDToTailCallCallsite) {
6830 OrigNameGUIDToTailCallCallsite.emplace();
6831 for (
const auto &[CalleeVI, Callsite] : MapTailCallCalleeVIToCallsite) {
6840 AliasVIToGV.emplace();
6846 AliasVIToGV->try_emplace(VI, &
A);
6849 Callee = AliasVIToGV->lookup(CalleeVI);
6855 auto [It, Inserted] = OrigNameGUIDToTailCallCallsite->try_emplace(
6859 if (!Inserted && It->second != &Callsite)
6860 It->second =
nullptr;
6863 return OrigNameGUIDToTailCallCallsite->lookup(CandidateGUID);
6866bool MemProfContextDisambiguation::initializeIndirectCallPromotionInfo(
6868 ICallAnalysis = std::make_unique<ICallPromotionAnalysis>();
6869 Symtab = std::make_unique<InstrProfSymtab>();
6887 AliaseeGUIDToImportedAlias.reset();
6888 if (
Error E = Symtab->create(M,
true,
false,
6890 std::string SymtabFailure =
toString(std::move(
E));
6891 M.getContext().emitError(
"Failed to create symtab: " + SymtabFailure);
6904 auto MIBIter = AllocNode.
MIBs.begin();
6905 for (
auto &MDOp : MemProfMD->
operands()) {
6914 if (MIBIter->StackIdIndices.empty()) {
6918 auto StackIdIndexIter = MIBIter->StackIdIndices.begin();
6923 auto ContextIterBegin =
6927 (ContextIterBegin != StackContext.
end() && *ContextIterBegin == 0) ? 1
6929 for (
auto ContextIter = ContextIterBegin; ContextIter != StackContext.
end();
6934 if (LastStackContextId == *ContextIter)
6936 LastStackContextId = *ContextIter;
6937 assert(StackIdIndexIter != MIBIter->StackIdIndices.end());
6947bool MemProfContextDisambiguation::applyImport(
Module &M) {
6954 std::map<const Function *, SmallPtrSet<const GlobalAlias *, 1>>
6956 for (
auto &
A :
M.aliases()) {
6957 auto *Aliasee =
A.getAliaseeObject();
6959 FuncToAliasMap[
F].insert(&
A);
6962 if (!initializeIndirectCallPromotionInfo(M))
6968 std::optional<DenseMap<ValueInfo, const GlobalAlias *>> AliasVIToGV;
6974 OptimizationRemarkEmitter ORE(&
F);
6977 bool ClonesCreated =
false;
6978 unsigned NumClonesCreated = 0;
6979 auto CloneFuncIfNeeded = [&](
unsigned NumClones, FunctionSummary *
FS) {
6989 if (ClonesCreated) {
6990 assert(NumClonesCreated == NumClones);
6997 ClonesCreated =
true;
6998 NumClonesCreated = NumClones;
7001 auto CloneCallsite = [&](
const CallsiteInfo &StackNode, CallBase *CB,
7002 Function *CalledFunction, FunctionSummary *
FS) {
7004 CloneFuncIfNeeded(StackNode.
Clones.
size(), FS);
7016 if (CalledFunction != CB->getCalledOperand() &&
7017 (!GA || CalledFunction != GA->getAliaseeObject())) {
7018 SkippedCallsCloning++;
7024 auto CalleeOrigName = CalledFunction->getName();
7025 for (
unsigned J = 0; J < StackNode.
Clones.
size(); J++) {
7028 if (J > 0 && VMaps[J - 1]->
empty())
7032 if (!StackNode.
Clones[J])
7034 auto NewF =
M.getOrInsertFunction(
7036 CalledFunction->getFunctionType());
7050 ORE.emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofCall", CBClone)
7051 <<
ore::NV(
"Call", CBClone) <<
" in clone "
7053 <<
" assigned to call function clone "
7054 <<
ore::NV(
"Callee", NewF.getCallee()));
7068 ImportSummary->findSummaryInModule(TheFnVI,
M.getModuleIdentifier());
7072 auto SrcModuleMD =
F.getMetadata(
"thinlto_src_module");
7074 "enable-import-metadata is needed to emit thinlto_src_module");
7075 StringRef SrcModule =
7078 if (GVS->modulePath() == SrcModule) {
7079 GVSummary = GVS.get();
7083 assert(GVSummary && GVSummary->modulePath() == SrcModule);
7093 if (
FS->allocs().empty() &&
FS->callsites().empty())
7096 auto SI =
FS->callsites().begin();
7097 auto AI =
FS->allocs().begin();
7102 DenseMap<ValueInfo, CallsiteInfo> MapTailCallCalleeVIToCallsite;
7105 for (
auto CallsiteIt =
FS->callsites().rbegin();
7106 CallsiteIt !=
FS->callsites().rend(); CallsiteIt++) {
7107 auto &Callsite = *CallsiteIt;
7111 if (!Callsite.StackIdIndices.empty())
7113 MapTailCallCalleeVIToCallsite.
insert({Callsite.Callee, Callsite});
7117 std::optional<DenseMap<uint64_t, const CallsiteInfo *>>
7118 OrigNameGUIDToTailCallCallsite;
7126 for (
auto &BB :
F) {
7127 for (
auto &
I : BB) {
7133 auto *CalledValue = CB->getCalledOperand();
7134 auto *CalledFunction = CB->getCalledFunction();
7135 if (CalledValue && !CalledFunction) {
7136 CalledValue = CalledValue->stripPointerCasts();
7143 assert(!CalledFunction &&
7144 "Expected null called function in callsite for alias");
7148 CallStack<MDNode, MDNode::op_iterator> CallsiteContext(
7149 I.getMetadata(LLVMContext::MD_callsite));
7150 auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof);
7156 if (CB->getAttributes().hasFnAttr(
"memprof") && !MemProfMD) {
7157 CB->getAttributes().getFnAttr(
"memprof").getValueAsString() ==
"cold"
7158 ? AllocTypeColdThinBackend++
7159 : AllocTypeNotColdThinBackend++;
7160 OrigAllocsThinBackend++;
7161 AllocVersionsThinBackend++;
7162 if (!MaxAllocVersionsThinBackend)
7163 MaxAllocVersionsThinBackend = 1;
7170 auto &AllocNode = *(AI++);
7178 CloneFuncIfNeeded(AllocNode.Versions.size(), FS);
7180 OrigAllocsThinBackend++;
7181 AllocVersionsThinBackend += AllocNode.Versions.size();
7182 if (MaxAllocVersionsThinBackend < AllocNode.Versions.size())
7183 MaxAllocVersionsThinBackend = AllocNode.Versions.size();
7195 if (AllocNode.Versions.size() == 1 &&
7197 UnclonableAllocsThinBackend++;
7200 for (
unsigned J = 0; J < AllocNode.Versions.size(); J++) {
7203 if (J > 0 && VMaps[J - 1]->
empty())
7206 if (AllocNode.Versions[J] == (uint8_t)AllocationType::None)
7214 AllocTy = AllocationType::NotCold;
7216 if (AllocTy == AllocationType::Cold)
7217 AllocTypeColdThinBackend++;
7218 else if (IsAmbiguous)
7219 AllocTypeAmbiguousThinBackend++;
7221 AllocTypeNotColdThinBackend++;
7241 ORE.emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofAttribute", CBClone)
7242 <<
ore::NV(
"AllocationCall", CBClone) <<
" in clone "
7244 <<
" marked with memprof allocation attribute "
7245 <<
ore::NV(
"Attribute", AllocTypeString));
7247 }
else if (!CallsiteContext.empty()) {
7248 if (!CalledFunction) {
7252 assert(!CI || !CI->isInlineAsm());
7262 auto NumClones = recordICPInfo(
7264 [&](
const InstrProfValueData &Candidate) {
7265 assert(SI !=
FS->callsites().end());
7267 auto CalleeValueInfo =
7268 ImportSummary->getValueInfo(Candidate.Value);
7270 ImportSummary->getGUIDFromOriginalID(Candidate.Value);
7278 assert(!CalleeValueInfo ||
SI->Callee == CalleeValueInfo ||
7279 (
SI->Callee &&
SI->Callee.getGUID() == LocalGUID));
7288 CloneFuncIfNeeded(NumClones, FS);
7293 assert(SI !=
FS->callsites().end());
7294 auto &StackNode = *(
SI++);
7300 for (
auto StackId : CallsiteContext) {
7302 assert(ImportSummary->getStackIdAtIndex(*StackIdIndexIter) ==
7308 CloneCallsite(StackNode, CB, CalledFunction, FS);
7310 }
else if (CB->isTailCall() && CalledFunction) {
7315 if (CalleeVI && MapTailCallCalleeVIToCallsite.
count(CalleeVI)) {
7316 auto Callsite = MapTailCallCalleeVIToCallsite.
find(CalleeVI);
7317 assert(Callsite != MapTailCallCalleeVIToCallsite.
end());
7318 CloneCallsite(Callsite->second, CB, CalledFunction, FS);
7320 }
else if (CB->isTailCall() && !CalledFunction &&
7321 !MapTailCallCalleeVIToCallsite.
empty()) {
7327 auto PrevNumICallAnalysisInfo = ICallAnalysisInfo.
size();
7328 auto NumClones = recordICPInfo(
7330 [&](
const InstrProfValueData &Candidate) {
7332 Candidate.Value, MapTailCallCalleeVIToCallsite,
7333 OrigNameGUIDToTailCallCallsite, AliasVIToGV, M,
7334 ImportSummary, *Symtab);
7337 if (ICallAnalysisInfo.
size() > PrevNumICallAnalysisInfo)
7338 IndirectTailCallsRecordedForICPThinBackend++;
7340 CloneFuncIfNeeded(NumClones, FS);
7346 performICP(M, VMaps, ICallAnalysisInfo, ORE);
7356 for (
auto &BB :
F) {
7357 for (
auto &
I : BB) {
7360 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
7361 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
7369unsigned MemProfContextDisambiguation::recordICPInfo(
7371 function_ref<
const CallsiteInfo *(
const InstrProfValueData &)> GetCallsite,
7374 uint32_t NumCandidates;
7376 auto CandidateProfileData =
7377 ICallAnalysis->getPromotionCandidatesForInstruction(
7378 CB, TotalCount, NumCandidates,
7380 if (CandidateProfileData.empty())
7386 bool ICPNeeded =
false;
7387 unsigned NumClones = 0;
7389 for (
const auto &Candidate : CandidateProfileData) {
7390 const CallsiteInfo *Callsite = GetCallsite(Candidate);
7398 [](
unsigned CloneNo) { return CloneNo != 0; });
7408 ICallAnalysisInfo.
push_back({CB, CandidateProfileData.vec(), NumCandidates,
7409 TotalCount, NumClones, std::move(Callsites)});
7413void MemProfContextDisambiguation::performICP(
7416 OptimizationRemarkEmitter &ORE) {
7423 for (
auto &Info : ICallAnalysisInfo) {
7425 auto TotalCount =
Info.TotalCount;
7426 unsigned NumClones =
Info.NumClones;
7429 assert(
Info.CandidateProfileData.size() ==
Info.Callsites.size());
7430 for (
unsigned I = 0;
I <
Info.CandidateProfileData.size();
I++) {
7431 auto &Candidate =
Info.CandidateProfileData[
I];
7432 const CallsiteInfo *StackNode =
Info.Callsites[
I];
7440 Function *TargetFunction = Symtab->getFunction(Candidate.Value);
7451 if (!TargetFunction && StackNode && StackNode->
Callee &&
7462 if (!TargetFunction) {
7463 if (!AliaseeGUIDToImportedAlias) {
7464 AliaseeGUIDToImportedAlias.emplace();
7468 if (
auto AliaseeGUID = Fn.getGUIDIfAssigned())
7469 AliaseeGUIDToImportedAlias->try_emplace(*AliaseeGUID, &Fn);
7472 TargetFunction = AliaseeGUIDToImportedAlias->lookup(Candidate.Value);
7473 if (!TargetFunction && StackNode && StackNode->
Callee &&
7476 AliaseeGUIDToImportedAlias->lookup(StackNode->
Callee.
getGUID());
7478 if (TargetFunction ==
nullptr ||
7486 return OptimizationRemarkMissed(
DEBUG_TYPE,
"UnableToFindTarget", CB)
7487 <<
"Memprof cannot promote indirect call: target with md5sum "
7488 <<
ore::NV(
"target md5sum", Candidate.Value) <<
" not found";
7493 RemainingCandidates.
push_back(Candidate);
7498 const char *Reason =
nullptr;
7501 return OptimizationRemarkMissed(
DEBUG_TYPE,
"UnableToPromote", CB)
7502 <<
"Memprof cannot promote indirect call to "
7503 <<
ore::NV(
"TargetFunction", TargetFunction)
7504 <<
" with count of " <<
ore::NV(
"TotalCount", TotalCount)
7507 RemainingCandidates.
push_back(Candidate);
7516 CallBase *CBClone = CB;
7517 for (
unsigned J = 0; J < NumClones; J++) {
7520 if (J > 0 && VMaps[J - 1]->
empty())
7530 TotalCount, isSamplePGO, &ORE);
7531 auto *TargetToUse = TargetFunction;
7534 if (StackNode && StackNode->
Clones[J]) {
7553 <<
ore::NV(
"Call", CBClone) <<
" in clone "
7555 <<
" promoted and assigned to call function clone "
7556 <<
ore::NV(
"Callee", TargetToUse));
7560 TotalCount -= Candidate.Count;
7564 CallBase *CBClone = CB;
7565 for (
unsigned J = 0; J < NumClones; J++) {
7568 if (J > 0 && VMaps[J - 1]->
empty())
7574 CBClone->
setMetadata(LLVMContext::MD_prof,
nullptr);
7577 if (TotalCount != 0)
7579 IPVK_IndirectCallTarget,
Info.NumCandidates);
7584template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
7585bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::process(
7586 function_ref<
void(StringRef, StringRef,
const Twine &)> EmitRemark,
7587 bool AllowExtraAnalysis) {
7589 dbgs() <<
"CCG before cloning:\n";
7593 exportToDot(
"postbuild");
7602 capturePreCloningContextInfo();
7611 dbgs() <<
"CCG after cloning:\n";
7615 exportToDot(
"cloned");
7617 bool Changed = assignFunctions();
7620 dbgs() <<
"CCG after assigning function clones:\n";
7624 exportToDot(
"clonefuncassign");
7633 populateFunctionsWithCallers();
7634 printTotalSizes(
errs(), EmitRemark);
7640bool MemProfContextDisambiguation::processModule(
7642 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter) {
7647 return applyImport(M);
7660 ModuleCallsiteContextGraph CCG(M, OREGetter);
7663 return CCG.process();
7668 : ImportSummary(Summary), isSamplePGO(isSamplePGO) {
7673 "-memprof-dot-scope=alloc requires -memprof-dot-alloc-id");
7677 "-memprof-dot-scope=context requires -memprof-dot-context-id");
7681 "-memprof-dot-scope=all can't have both -memprof-dot-alloc-id and "
7682 "-memprof-dot-context-id");
7683 if (ImportSummary) {
7693 auto ReadSummaryFile =
7695 if (!ReadSummaryFile) {
7702 if (!ImportSummaryForTestingOrErr) {
7708 ImportSummaryForTesting = std::move(*ImportSummaryForTestingOrErr);
7709 ImportSummary = ImportSummaryForTesting.get();
7718 if (!processModule(M, OREGetter))
7741 for (
auto &
I : Index) {
7742 auto VI = Index.getValueInfo(
I);
7743 for (
auto &S : VI.getSummaryList()) {
7747 !isPrevailing(VI.getGUID(), S.get()))
7750 if (!FS || FS->callsites().empty())
7752 CalleeToEdge.
clear();
7753 for (
auto &CI : FS->callsites()) {
7754 if (!CI.Callee ||
llvm::all_of(CI.Clones, [](
unsigned CloneNo) {
7755 return CloneNo == 0;
7762 NumClonedCalleeCallsites++;
7764 if (CalleeToEdge.
empty())
7765 for (
auto &[CalleeVI, Edge] : FS->mutableCalls())
7766 CalleeToEdge[CalleeVI] = &Edge;
7767 auto It = CalleeToEdge.
find(CI.Callee);
7768 if (It == CalleeToEdge.
end())
7775 if (!Edge->hasIndirectCall())
7777 NumClonedCalleeIndirectCallsites++;
7778 if (!Edge->requiresDeclImport()) {
7779 Edge->setRequiresDeclImport(
true);
7780 NumClonedCalleeEdgesMarkedRequiresDeclImport++;
7801 bool AllowExtraAnalysis =
7806 IndexCallsiteContextGraph CCG(Index, isPrevailing);
7807 Changed = CCG.process(EmitRemark, AllowExtraAnalysis);
7830 for (
auto &BB :
F) {
7831 for (
auto &
I : BB) {
7835 if (CI->hasFnAttr(
"memprof")) {
7836 CI->removeFnAttr(
"memprof");
7839 if (!CI->hasMetadata(LLVMContext::MD_callsite)) {
7840 assert(!CI->hasMetadata(LLVMContext::MD_memprof));
7846 CI->setMetadata(LLVMContext::MD_memprof,
nullptr);
7847 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 bool isMemProfClone(const GlobalValue &GV)
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 const std::string MemProfCloneSuffix
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
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
@ 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...