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 not cold static allocations (possibly cloned) during "
73STATISTIC(AllocTypeColdThinBackend,
"Number of cold static allocations "
74 "(possibly cloned) during ThinLTO backend");
76 "Number of original (not cloned) allocations with memprof profiles "
77 "during ThinLTO backend");
79 AllocVersionsThinBackend,
80 "Number of allocation versions (including clones) during ThinLTO backend");
82 "Maximum number of allocation versions created for an original "
83 "allocation during ThinLTO backend");
85 "Number of unclonable ambigous allocations during ThinLTO backend");
87 "Number of edges removed due to mismatched callees (profiled vs IR)");
89 "Number of profiled callees found via tail calls");
91 "Aggregate depth of profiled callees found via tail calls");
93 "Maximum depth of profiled callees found via tail calls");
95 "Number of profiled callees found via multiple tail call chains");
97 "Number of tail calls in chains to profiled callees that are "
98 "indirect (thin link)");
99STATISTIC(IndirectTailCallsRecordedForICPThinBackend,
100 "Number of indirect tail calls recorded for ICP for cloning during "
102STATISTIC(DeferredBackedges,
"Number of backedges with deferred cloning");
103STATISTIC(NewMergedNodes,
"Number of new nodes created during merging");
104STATISTIC(NonNewMergedNodes,
"Number of non new nodes used during merging");
106 "Number of missing alloc nodes for context ids");
108 "Number of calls skipped during cloning due to unexpected operand");
110 "Number of callsites assigned to call multiple non-matching clones");
111STATISTIC(TotalMergeInvokes,
"Number of merge invocations for nodes");
112STATISTIC(TotalMergeIters,
"Number of merge iterations for nodes");
113STATISTIC(MaxMergeIters,
"Max merge iterations for nodes");
114STATISTIC(NumImportantContextIds,
"Number of important context ids");
115STATISTIC(NumFixupEdgeIdsInserted,
"Number of fixup edge ids inserted");
116STATISTIC(NumFixupEdgesAdded,
"Number of fixup edges added");
117STATISTIC(NumFixedContexts,
"Number of contexts with fixed edges");
119 "Number of callsite clones without an edge to a callee's clones "
120 "assigned the callee function clone of their original node");
122 "Number of calls in function clones whose callee was taken from a "
123 "callsite clone an implicit caller requires");
125 "Number of context ids with call stacks trimmed at a callsite");
127 "Number of callsite clones without an edge to a callee's clones "
128 "left in a function clone calling a conflicting callee clone");
130 "Number of aliasees prevailing in a different module than its alias");
132 "Number of summary callsites assigned to call a cloned callee (thin "
135 "Number of summary callsites assigned to call a cloned callee with "
136 "an indirect call edge (thin link)");
138 "Number of summary indirect call edges to cloned callees marked as "
139 "requiring a declaration import (thin link)");
144 cl::desc(
"Specify the path prefix of the MemProf dot files."));
148 cl::desc(
"Export graph to dot files."));
153 cl::desc(
"Iteratively apply merging on a node to catch new callers"));
163 "memprof-dot-scope",
cl::desc(
"Scope of graph to export to dot"),
168 "Export only nodes with contexts feeding given "
169 "-memprof-dot-alloc-id"),
171 "Export only nodes with given -memprof-dot-context-id")));
175 cl::desc(
"Id of alloc to export if -memprof-dot-scope=alloc "
176 "or to highlight if -memprof-dot-scope=all"));
180 cl::desc(
"Id of context to export if -memprof-dot-scope=context or to "
181 "highlight otherwise"));
185 cl::desc(
"Dump CallingContextGraph to stdout after each stage."));
189 cl::desc(
"Perform verification checks on CallingContextGraph."));
193 cl::desc(
"Perform frequent verification checks on nodes."));
196 "memprof-import-summary",
197 cl::desc(
"Import summary to use for testing the ThinLTO backend via opt"),
203 cl::desc(
"Max depth to recursively search for missing "
204 "frames through tail calls."));
211 cl::desc(
"Search for missing frames through indirect tail calls to their "
212 "profiled targets (ThinLTO)."));
217 cl::desc(
"Allow cloning of callsites involved in recursive cycles"));
221 cl::desc(
"Allow cloning of contexts through recursive cycles"));
228 cl::desc(
"Merge clones before assigning functions"));
237 cl::desc(
"Allow cloning of contexts having recursive cycles"));
243 cl::desc(
"Minimum absolute count for promoted target to be inlinable"));
247 "enable-memprof-context-disambiguation",
cl::Hidden,
248 cl::desc(
"Enable MemProf context disambiguation"));
254 cl::desc(
"Linking with hot/cold operator new interfaces"));
259 "Require target function definition when promoting indirect calls"));
282 cl::desc(
"Import at least a declaration of the indirect call targets of "
283 "callsites assigned to call a cloned callee (needed for MemProf "
284 "ICP in the ThinLTO backend)"));
296 cl::desc(
"Append post-cloning call path and matching details to each "
297 "-memprof-report-hinted-sizes line"));
304 cl::desc(
"Maximum number of functions printed in full for a post-cloning "
305 "call path in the -memprof-report-hinted-sizes-detail suffix; "
306 "longer paths are elided in the middle"));
310 cl::desc(
"Number of largest cold contexts to consider important"));
314 cl::desc(
"Enables edge fixup for important contexts"));
334template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
335class CallsiteContextGraph {
337 CallsiteContextGraph() =
default;
338 CallsiteContextGraph(
const CallsiteContextGraph &) =
default;
339 CallsiteContextGraph(CallsiteContextGraph &&) =
default;
343 EmitRemark =
nullptr,
344 bool AllowExtraAnalysis =
false);
348 void identifyClones();
355 bool assignFunctions();
361 EmitRemark =
nullptr)
const;
364 const CallsiteContextGraph &CCG) {
369 friend struct GraphTraits<
370 const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *>;
371 friend struct DOTGraphTraits<
372 const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *>;
374 void exportToDot(std::string Label)
const;
377 struct FuncInfo final
378 :
public std::pair<FuncTy *, unsigned > {
379 using Base = std::pair<FuncTy *, unsigned>;
380 FuncInfo(
const Base &
B) : Base(
B) {}
381 FuncInfo(FuncTy *
F =
nullptr,
unsigned CloneNo = 0) : Base(
F, CloneNo) {}
382 explicit operator bool()
const {
return this->first !=
nullptr; }
383 FuncTy *func()
const {
return this->first; }
384 unsigned cloneNo()
const {
return this->second; }
388 struct CallInfo final :
public std::pair<CallTy, unsigned > {
389 using Base = std::pair<CallTy, unsigned>;
390 CallInfo(
const Base &
B) : Base(
B) {}
391 CallInfo(CallTy
Call =
nullptr,
unsigned CloneNo = 0)
392 : Base(
Call, CloneNo) {}
393 explicit operator bool()
const {
return (
bool)this->first; }
394 CallTy call()
const {
return this->first; }
395 unsigned cloneNo()
const {
return this->second; }
396 void setCloneNo(
unsigned N) { this->second =
N; }
397 void print(raw_ostream &OS)
const {
398 if (!
operator bool()) {
404 OS <<
"\t(clone " << cloneNo() <<
")";
410 friend raw_ostream &
operator<<(raw_ostream &OS,
const CallInfo &
Call) {
430 bool Recursive =
false;
434 uint8_t AllocTypes = 0;
457 std::vector<std::shared_ptr<ContextEdge>> CalleeEdges;
461 std::vector<std::shared_ptr<ContextEdge>> CallerEdges;
465 bool useCallerEdgesForContextInfo()
const {
470 assert(!CalleeEdges.empty() || CallerEdges.empty() || IsAllocation ||
482 DenseSet<uint32_t> getContextIds()
const {
488 for (
auto &
Edge : CalleeEdges.empty() ? CallerEdges : CalleeEdges)
490 DenseSet<uint32_t> ContextIds;
493 CalleeEdges, useCallerEdgesForContextInfo()
495 : std::vector<std::shared_ptr<ContextEdge>>());
496 for (
const auto &
Edge : Edges)
503 uint8_t computeAllocType()
const {
505 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
506 uint8_t
AllocType = (uint8_t)AllocationType::None;
508 CalleeEdges, useCallerEdgesForContextInfo()
510 : std::vector<std::shared_ptr<ContextEdge>>());
511 for (
const auto &
Edge : Edges) {
522 bool emptyContextIds()
const {
524 CalleeEdges, useCallerEdgesForContextInfo()
526 : std::vector<std::shared_ptr<ContextEdge>>());
527 for (
const auto &
Edge : Edges) {
528 if (!
Edge->getContextIds().empty())
535 bool hasContextId(uint32_t Id)
const {
537 CalleeEdges, useCallerEdgesForContextInfo()
539 : std::vector<std::shared_ptr<ContextEdge>>());
540 for (
const auto &
Edge : Edges) {
541 if (
Edge->getContextIds().contains(Id))
548 std::vector<ContextNode *> Clones;
551 ContextNode *CloneOf =
nullptr;
553 ContextNode(
bool IsAllocation) : IsAllocation(IsAllocation), Call() {}
555 ContextNode(
bool IsAllocation, CallInfo
C)
556 : IsAllocation(IsAllocation), Call(
C) {}
558 void addClone(ContextNode *Clone) {
560 CloneOf->Clones.push_back(Clone);
561 Clone->CloneOf = CloneOf;
563 Clones.push_back(Clone);
565 Clone->CloneOf =
this;
569 ContextNode *getOrigNode() {
575 const ContextNode *getOrigNode()
const {
582 unsigned int ContextId);
584 ContextEdge *findEdgeFromCallee(
const ContextNode *Callee);
585 ContextEdge *findEdgeFromCaller(
const ContextNode *Caller);
586 void eraseCalleeEdge(
const ContextEdge *
Edge);
587 void eraseCallerEdge(
const ContextEdge *
Edge);
589 void setCall(CallInfo
C) { Call = std::move(
C); }
591 bool hasCall()
const {
return (
bool)Call.call(); }
593 void printCall(raw_ostream &OS)
const { Call.print(OS); }
597 bool isRemoved()
const {
603 (AllocTypes == (uint8_t)AllocationType::None) ==
605 return AllocTypes == (uint8_t)AllocationType::None;
609 void print(raw_ostream &OS)
const;
611 friend raw_ostream &
operator<<(raw_ostream &OS,
const ContextNode &Node) {
625 uint8_t AllocTypes = 0;
633 bool IsBackedge =
false;
636 DenseSet<uint32_t> ContextIds;
638 ContextEdge(ContextNode *Callee, ContextNode *Caller, uint8_t
AllocType,
639 DenseSet<uint32_t> ContextIds)
640 : Callee(Callee), Caller(Caller), AllocTypes(
AllocType),
641 ContextIds(std::
move(ContextIds)) {}
643 DenseSet<uint32_t> &getContextIds() {
return ContextIds; }
647 inline void clear() {
649 AllocTypes = (uint8_t)AllocationType::None;
657 inline bool isRemoved()
const {
658 if (Callee || Caller)
663 assert(AllocTypes == (uint8_t)AllocationType::None);
664 assert(ContextIds.empty());
669 void print(raw_ostream &OS)
const;
671 friend raw_ostream &
operator<<(raw_ostream &OS,
const ContextEdge &
Edge) {
679 void removeNoneTypeCalleeEdges(ContextNode *Node);
680 void removeNoneTypeCallerEdges(ContextNode *Node);
682 recursivelyRemoveNoneTypeCalleeEdges(ContextNode *Node,
683 DenseSet<const ContextNode *> &Visited);
688 template <
class NodeT,
class IteratorT>
689 std::vector<uint64_t>
690 getStackIdsWithContextNodes(CallStack<NodeT, IteratorT> &CallsiteContext);
694 ContextNode *addAllocNode(CallInfo
Call,
const FuncTy *
F);
697 template <
class NodeT,
class IteratorT>
698 void addStackNodesForMIB(
699 ContextNode *AllocNode, CallStack<NodeT, IteratorT> &StackContext,
702 std::map<uint64_t, uint32_t> &TotalSizeToContextIdTopNCold);
707 void updateStackNodes();
716 void fixupImportantContexts();
720 void handleCallsitesWithMultipleTargets();
723 void markBackedges();
733 bool partitionCallsByCallee(
735 std::vector<std::pair<CallInfo, ContextNode *>> &NewCallToNode);
739 MapVector<FuncTy *, std::vector<CallInfo>> FuncToCallsWithMetadata;
742 std::map<const ContextNode *, const FuncTy *> NodeToCallingFunc;
744 const FuncTy *getCallingFunc(
const ContextNode *
N)
const {
745 auto It = NodeToCallingFunc.find(
N);
746 return It != NodeToCallingFunc.end() ? It->second :
nullptr;
754 DenseSet<const FuncTy *> FunctionsWithCallers;
758 DenseSet<uint32_t> DotAllocContextIds;
761 using EdgeIter =
typename std::vector<std::shared_ptr<ContextEdge>>::iterator;
766 struct CallContextInfo {
770 std::vector<uint64_t> StackIds;
775 DenseSet<uint32_t> ContextIds;
784 void removeEdgeFromGraph(ContextEdge *
Edge, EdgeIter *EI =
nullptr,
785 bool CalleeIter =
true);
793 void assignStackNodesPostOrder(
794 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
795 DenseMap<
uint64_t, std::vector<CallContextInfo>> &StackIdToMatchingCalls,
796 DenseMap<CallInfo, CallInfo> &CallToMatchingCall,
797 const DenseSet<uint32_t> &ImportantContextIds);
802 DenseSet<uint32_t> duplicateContextIds(
803 const DenseSet<uint32_t> &StackSequenceContextIds,
804 DenseMap<uint32_t, DenseSet<uint32_t>> &OldToNewContextIds);
807 void propagateDuplicateContextIds(
808 const DenseMap<uint32_t, DenseSet<uint32_t>> &OldToNewContextIds);
813 void connectNewNode(ContextNode *NewNode, ContextNode *OrigNode,
814 bool TowardsCallee,
const DenseSet<uint32_t> &ContextIds);
820 return static_cast<const DerivedCCG *
>(
this)->getStackId(IdOrIndex);
830 calleesMatch(CallTy
Call, EdgeIter &EI,
831 MapVector<CallInfo, ContextNode *> &TailCallToContextNodeMap);
835 const FuncTy *getCalleeFunc(CallTy
Call) {
836 return static_cast<DerivedCCG *
>(
this)->getCalleeFunc(
Call);
842 bool calleeMatchesFunc(
843 CallTy
Call,
const FuncTy *Func,
const FuncTy *CallerFunc,
844 std::vector<std::pair<CallTy, FuncTy *>> &FoundCalleeChain) {
845 return static_cast<DerivedCCG *
>(
this)->calleeMatchesFunc(
846 Call, Func, CallerFunc, FoundCalleeChain);
850 bool sameCallee(CallTy Call1, CallTy Call2) {
851 return static_cast<DerivedCCG *
>(
this)->sameCallee(Call1, Call2);
856 std::vector<uint64_t> getStackIdsWithContextNodesForCall(CallTy
Call) {
857 return static_cast<DerivedCCG *
>(
this)->getStackIdsWithContextNodesForCall(
863 return static_cast<DerivedCCG *
>(
this)->getLastStackId(
Call);
868 AllocType == AllocationType::Cold ? AllocTypeCold++ : AllocTypeNotCold++;
869 static_cast<DerivedCCG *
>(
this)->updateAllocationCall(
Call,
AllocType);
874 return static_cast<const DerivedCCG *
>(
this)->getAllocationCallType(
Call);
879 void updateCall(CallInfo &CallerCall, FuncInfo CalleeFunc) {
880 static_cast<DerivedCCG *
>(
this)->updateCall(CallerCall, CalleeFunc);
886 FuncInfo cloneFunctionForCallsite(
887 FuncInfo &Func, CallInfo &
Call, DenseMap<CallInfo, CallInfo> &CallMap,
888 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
889 return static_cast<DerivedCCG *
>(
this)->cloneFunctionForCallsite(
890 Func,
Call, CallMap, CallsWithMetadataInFunc, CloneNo);
895 std::string getLabel(
const FuncTy *Func,
const CallTy
Call,
896 unsigned CloneNo)
const {
897 return static_cast<const DerivedCCG *
>(
this)->getLabel(Func,
Call, CloneNo);
901 std::string getFuncName(
const FuncTy *Func,
unsigned CloneNo = 0)
const {
902 return static_cast<const DerivedCCG *
>(
this)->getFuncName(Func, CloneNo);
907 bool isFuncDead(
const FuncTy *Func)
const {
908 return static_cast<const DerivedCCG *
>(
this)->isFuncDead(Func);
912 void populateFunctionsWithCallers() {
913 static_cast<DerivedCCG *
>(
this)->populateFunctionsWithCallers();
918 void capturePreCloningContextInfo();
923 std::string formatContextReportSuffix(
const ContextNode *Node,
927 ContextNode *createNewNode(
bool IsAllocation,
const FuncTy *
F =
nullptr,
928 CallInfo
C = CallInfo()) {
929 NodeOwner.push_back(std::make_unique<ContextNode>(IsAllocation,
C));
930 auto *NewNode = NodeOwner.back().get();
932 NodeToCallingFunc[NewNode] =
F;
933 NewNode->NodeId = NodeOwner.size();
938 ContextNode *getNodeForInst(
const CallInfo &
C);
939 ContextNode *getNodeForAlloc(
const CallInfo &
C);
940 ContextNode *getNodeForStackId(
uint64_t StackId);
944 uint8_t computeAllocType(DenseSet<uint32_t> &ContextIds)
const;
949 uint8_t intersectAllocTypesImpl(
const DenseSet<uint32_t> &Node1Ids,
950 const DenseSet<uint32_t> &Node2Ids)
const;
954 uint8_t intersectAllocTypes(
const DenseSet<uint32_t> &Node1Ids,
955 const DenseSet<uint32_t> &Node2Ids)
const;
962 moveEdgeToNewCalleeClone(
const std::shared_ptr<ContextEdge> &
Edge,
963 DenseSet<uint32_t> ContextIdsToMove = {});
969 void moveEdgeToExistingCalleeClone(
const std::shared_ptr<ContextEdge> &
Edge,
970 ContextNode *NewCallee,
971 bool NewClone =
false,
972 DenseSet<uint32_t> ContextIdsToMove = {});
979 void moveCalleeEdgeToNewCaller(
const std::shared_ptr<ContextEdge> &
Edge,
980 ContextNode *NewCaller);
983 void markBackedges(ContextNode *Node, DenseSet<const ContextNode *> &Visited,
984 DenseSet<const ContextNode *> &CurrentStack);
988 mergeClones(ContextNode *Node, DenseSet<const ContextNode *> &Visited,
989 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode);
991 void mergeNodeCalleeClones(
992 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
993 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode);
996 void findOtherCallersToShareMerge(
997 ContextNode *Node, std::vector<std::shared_ptr<ContextEdge>> &CalleeEdges,
998 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode,
999 DenseSet<ContextNode *> &OtherCallersToShareMerge);
1005 void identifyClones(ContextNode *Node, DenseSet<const ContextNode *> &Visited,
1006 const DenseSet<uint32_t> &AllocContextIds);
1011 struct ImplicitSource {
1013 const ContextNode *Source;
1021 using ImplicitSourceMap =
1022 DenseMap<std::pair<const ContextNode *, unsigned>, ImplicitSource>;
1029 void assignImplicitCallers(
1030 ContextNode *Node,
const DenseSet<uint32_t> &TrimmedContextIds,
1031 DenseMap<ContextNode *, FuncInfo> &CallsiteToCalleeFuncCloneMap,
1032 const std::map<FuncInfo, ContextNode *> &FuncCloneToCurNodeCloneMap,
1033 ImplicitSourceMap &ImplicitSources);
1039 static const ContextNode *resolveImplicitSource(
const ContextNode *Node,
1040 const ImplicitSource &Src);
1043 DenseMap<uint32_t, AllocationType> ContextIdToAllocationType;
1049 DenseMap<uint32_t, std::vector<ContextTotalSize>> ContextIdToContextSizeInfos;
1055 DenseMap<uint64_t, ContextNode *> StackEntryIdToContextNodeMap;
1059 struct ImportantContextInfo {
1061 std::vector<uint64_t> StackIds;
1064 unsigned MaxLength = 0;
1068 std::map<std::vector<uint64_t>, ContextNode *> StackIdsToNode;
1072 DenseMap<uint32_t, ImportantContextInfo> ImportantContextIdInfo;
1077 void recordStackNode(std::vector<uint64_t> &StackIds, ContextNode *Node,
1081 const DenseSet<uint32_t> &NodeContextIds,
1082 const DenseSet<uint32_t> &ImportantContextIds) {
1087 DenseSet<uint32_t> Ids =
1091 auto Size = StackIds.size();
1092 for (
auto Id : Ids) {
1093 auto &
Entry = ImportantContextIdInfo[
Id];
1102 MapVector<CallInfo, ContextNode *> AllocationCallToContextNodeMap;
1103 MapVector<CallInfo, ContextNode *> NonAllocationCallToContextNodeMap;
1106 std::vector<std::unique_ptr<ContextNode>> NodeOwner;
1112 unsigned int LastContextId = 0;
1120 struct PreCloningContextInfo {
1124 std::vector<const ContextNode *> Chain;
1134 unsigned MaxMatchedFrame = 0;
1137 bool OutermostMatchedNodeHasOtherCallers =
false;
1142 bool StoppedAtRecursive =
false;
1143 bool StoppedAtMismatchedCallee =
false;
1146 const FuncTy *UnmatchedCallingFunc =
nullptr;
1149 DenseMap<uint32_t, PreCloningContextInfo> PreCloningContextInfoMap;
1152 DenseSet<const ContextNode *> PreCloningAllocHasMatchedCaller;
1155 DenseMap<const FuncTy *, unsigned> FuncToNumClones;
1160 DenseMap<std::pair<const ContextNode *, unsigned>,
unsigned>
1161 OrigNodeAndCloneToCalleeClone;
1165 DenseMap<std::pair<const ContextNode *, unsigned>,
const ContextNode *>
1166 OrigAllocAndCloneToNode;
1169template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1171 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode;
1172template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1174 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge;
1175template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1177 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::FuncInfo;
1178template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1180 typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::CallInfo;
1183class ModuleCallsiteContextGraph
1184 :
public CallsiteContextGraph<ModuleCallsiteContextGraph, Function,
1187 ModuleCallsiteContextGraph(
1189 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter);
1192 friend CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
1197 bool calleeMatchesFunc(
1199 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain);
1200 bool sameCallee(Instruction *Call1, Instruction *Call2);
1201 bool findProfiledCalleeThroughTailCalls(
1203 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain,
1204 bool &FoundMultipleCalleeChains);
1206 std::vector<uint64_t> getStackIdsWithContextNodesForCall(Instruction *
Call);
1209 void updateCall(CallInfo &CallerCall, FuncInfo CalleeFunc);
1210 CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
1212 cloneFunctionForCallsite(FuncInfo &Func, CallInfo &
Call,
1213 DenseMap<CallInfo, CallInfo> &CallMap,
1214 std::vector<CallInfo> &CallsWithMetadataInFunc,
1216 std::string getLabel(
const Function *Func,
const Instruction *
Call,
1217 unsigned CloneNo)
const;
1218 std::string getFuncName(
const Function *Func,
unsigned CloneNo = 0)
const;
1219 bool isFuncDead(
const Function *Func)
const {
return false; }
1220 void populateFunctionsWithCallers();
1223 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter;
1229struct IndexCall :
public PointerUnion<CallsiteInfo *, AllocInfo *> {
1230 IndexCall() : PointerUnion() {}
1231 IndexCall(std::nullptr_t) : IndexCall() {}
1232 IndexCall(CallsiteInfo *StackNode) : PointerUnion(StackNode) {}
1233 IndexCall(AllocInfo *AllocNode) : PointerUnion(AllocNode) {}
1234 IndexCall(PointerUnion PT) : PointerUnion(PT) {}
1236 IndexCall *operator->() {
return this; }
1238 void print(raw_ostream &OS)
const {
1239 PointerUnion<CallsiteInfo *, AllocInfo *>
Base = *
this;
1264class IndexCallsiteContextGraph
1265 :
public CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
1268 IndexCallsiteContextGraph(
1269 ModuleSummaryIndex &Index,
1273 ~IndexCallsiteContextGraph() {
1278 for (
auto &
I : FunctionCalleesToSynthesizedCallsiteInfos) {
1280 for (
auto &Callsite :
I.second)
1281 FS->addCallsite(std::move(*Callsite.second));
1286 friend CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
1290 const FunctionSummary *getCalleeFunc(IndexCall &
Call);
1291 bool calleeMatchesFunc(
1292 IndexCall &
Call,
const FunctionSummary *Func,
1293 const FunctionSummary *CallerFunc,
1294 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain);
1295 bool sameCallee(IndexCall &Call1, IndexCall &Call2);
1296 bool findProfiledCalleeThroughTailCalls(
1297 ValueInfo ProfiledCallee, ValueInfo CurCallee,
unsigned Depth,
1298 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain,
1299 bool &FoundMultipleCalleeChains);
1301 std::vector<uint64_t> getStackIdsWithContextNodesForCall(IndexCall &
Call);
1304 void updateCall(CallInfo &CallerCall, FuncInfo CalleeFunc);
1305 CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
1306 IndexCall>::FuncInfo
1307 cloneFunctionForCallsite(FuncInfo &Func, CallInfo &
Call,
1308 DenseMap<CallInfo, CallInfo> &CallMap,
1309 std::vector<CallInfo> &CallsWithMetadataInFunc,
1311 std::string getLabel(
const FunctionSummary *Func,
const IndexCall &
Call,
1312 unsigned CloneNo)
const;
1313 std::string getFuncName(
const FunctionSummary *Func,
1314 unsigned CloneNo = 0)
const;
1315 bool isFuncDead(
const FunctionSummary *Func)
const;
1316 void populateFunctionsWithCallers();
1317 DenseSet<GlobalValue::GUID> findAliaseeGUIDsPrevailingInDifferentModule();
1321 std::map<const FunctionSummary *, ValueInfo> FSToVIMap;
1323 const ModuleSummaryIndex &Index;
1331 DenseMap<FunctionSummary *,
1332 std::map<ValueInfo, std::unique_ptr<CallsiteInfo>>>
1333 FunctionCalleesToSynthesizedCallsiteInfos;
1344 :
public DenseMapInfo<std::pair<IndexCall, unsigned>> {};
1347 :
public DenseMapInfo<PointerUnion<CallsiteInfo *, AllocInfo *>> {};
1368template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1369bool allocTypesMatch(
1370 const std::vector<uint8_t> &InAllocTypes,
1371 const std::vector<std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>>>
1375 assert(InAllocTypes.size() == Edges.size());
1377 InAllocTypes.begin(), InAllocTypes.end(), Edges.begin(), Edges.end(),
1379 const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &r) {
1383 if (l == (uint8_t)AllocationType::None ||
1384 r->AllocTypes == (uint8_t)AllocationType::None)
1386 return allocTypeToUse(l) == allocTypeToUse(r->AllocTypes);
1395template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1396bool allocTypesMatchClone(
1397 const std::vector<uint8_t> &InAllocTypes,
1398 const ContextNode<DerivedCCG, FuncTy, CallTy> *Clone) {
1399 const ContextNode<DerivedCCG, FuncTy, CallTy> *
Node = Clone->CloneOf;
1403 assert(InAllocTypes.size() ==
Node->CalleeEdges.size());
1407 for (
const auto &
E : Clone->CalleeEdges) {
1409 EdgeCalleeMap[
E->Callee] =
E->AllocTypes;
1413 for (
unsigned I = 0;
I <
Node->CalleeEdges.size();
I++) {
1414 auto Iter = EdgeCalleeMap.
find(
Node->CalleeEdges[
I]->Callee);
1416 if (Iter == EdgeCalleeMap.
end())
1424 if (allocTypeToUse(Iter->second) != allocTypeToUse(InAllocTypes[
I]))
1432template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1433typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1434CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForInst(
1435 const CallInfo &
C) {
1436 ContextNode *
Node = getNodeForAlloc(
C);
1440 return NonAllocationCallToContextNodeMap.lookup(
C);
1443template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1444typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1445CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForAlloc(
1446 const CallInfo &
C) {
1447 return AllocationCallToContextNodeMap.lookup(
C);
1450template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1451typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1452CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getNodeForStackId(
1454 auto StackEntryNode = StackEntryIdToContextNodeMap.
find(StackId);
1455 if (StackEntryNode != StackEntryIdToContextNodeMap.
end())
1456 return StackEntryNode->second;
1460template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1461void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1463 unsigned int ContextId) {
1464 for (
auto &
Edge : CallerEdges) {
1465 if (
Edge->Caller == Caller) {
1467 Edge->getContextIds().insert(ContextId);
1471 std::shared_ptr<ContextEdge>
Edge = std::make_shared<ContextEdge>(
1472 this, Caller, (uint8_t)
AllocType, DenseSet<uint32_t>({ContextId}));
1473 CallerEdges.push_back(
Edge);
1477template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1478void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::removeEdgeFromGraph(
1479 ContextEdge *
Edge, EdgeIter *EI,
bool CalleeIter) {
1495 auto CalleeCallerCount =
Callee->CallerEdges.size();
1496 auto CallerCalleeCount =
Caller->CalleeEdges.size();
1501 }
else if (CalleeIter) {
1503 *EI =
Caller->CalleeEdges.erase(*EI);
1506 *EI =
Callee->CallerEdges.erase(*EI);
1508 assert(
Callee->CallerEdges.size() < CalleeCallerCount);
1509 assert(
Caller->CalleeEdges.size() < CallerCalleeCount);
1512template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1513void CallsiteContextGraph<
1514 DerivedCCG, FuncTy, CallTy>::removeNoneTypeCalleeEdges(ContextNode *Node) {
1515 for (
auto EI =
Node->CalleeEdges.begin(); EI !=
Node->CalleeEdges.end();) {
1517 if (
Edge->AllocTypes == (uint8_t)AllocationType::None) {
1519 removeEdgeFromGraph(
Edge.get(), &EI,
true);
1525template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1526void CallsiteContextGraph<
1527 DerivedCCG, FuncTy, CallTy>::removeNoneTypeCallerEdges(ContextNode *Node) {
1528 for (
auto EI =
Node->CallerEdges.begin(); EI !=
Node->CallerEdges.end();) {
1530 if (
Edge->AllocTypes == (uint8_t)AllocationType::None) {
1532 Edge->Caller->eraseCalleeEdge(
Edge.get());
1533 EI =
Node->CallerEdges.erase(EI);
1539template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1540typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge *
1541CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1542 findEdgeFromCallee(
const ContextNode *Callee) {
1543 for (
const auto &
Edge : CalleeEdges)
1544 if (
Edge->Callee == Callee)
1549template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1550typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge *
1551CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1552 findEdgeFromCaller(
const ContextNode *Caller) {
1553 for (
const auto &
Edge : CallerEdges)
1554 if (
Edge->Caller == Caller)
1559template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1560void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1561 eraseCalleeEdge(
const ContextEdge *
Edge) {
1563 CalleeEdges, [
Edge](
const std::shared_ptr<ContextEdge> &CalleeEdge) {
1564 return CalleeEdge.get() ==
Edge;
1566 assert(EI != CalleeEdges.end());
1567 CalleeEdges.erase(EI);
1570template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1571void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::
1572 eraseCallerEdge(
const ContextEdge *
Edge) {
1574 CallerEdges, [
Edge](
const std::shared_ptr<ContextEdge> &CallerEdge) {
1575 return CallerEdge.get() ==
Edge;
1577 assert(EI != CallerEdges.end());
1578 CallerEdges.erase(EI);
1581template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1582uint8_t CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::computeAllocType(
1583 DenseSet<uint32_t> &ContextIds)
const {
1585 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
1586 uint8_t
AllocType = (uint8_t)AllocationType::None;
1587 for (
auto Id : ContextIds) {
1588 AllocType |= (uint8_t)ContextIdToAllocationType.
at(Id);
1596template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1598CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::intersectAllocTypesImpl(
1599 const DenseSet<uint32_t> &Node1Ids,
1600 const DenseSet<uint32_t> &Node2Ids)
const {
1602 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
1603 uint8_t
AllocType = (uint8_t)AllocationType::None;
1604 for (
auto Id : Node1Ids) {
1605 if (!Node2Ids.
count(Id))
1607 AllocType |= (uint8_t)ContextIdToAllocationType.
at(Id);
1615template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1616uint8_t CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::intersectAllocTypes(
1617 const DenseSet<uint32_t> &Node1Ids,
1618 const DenseSet<uint32_t> &Node2Ids)
const {
1619 if (Node1Ids.
size() < Node2Ids.
size())
1620 return intersectAllocTypesImpl(Node1Ids, Node2Ids);
1622 return intersectAllocTypesImpl(Node2Ids, Node1Ids);
1625template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1626typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
1627CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::addAllocNode(
1628 CallInfo
Call,
const FuncTy *
F) {
1630 ContextNode *AllocNode = createNewNode(
true,
F,
Call);
1631 AllocationCallToContextNodeMap[
Call] = AllocNode;
1633 AllocNode->OrigStackOrAllocId = LastContextId;
1636 AllocNode->AllocTypes = (uint8_t)AllocationType::None;
1652template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1653template <
class NodeT,
class IteratorT>
1654void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::addStackNodesForMIB(
1655 ContextNode *AllocNode, CallStack<NodeT, IteratorT> &StackContext,
1658 std::map<uint64_t, uint32_t> &TotalSizeToContextIdTopNCold) {
1664 ContextIdToAllocationType[++LastContextId] =
AllocType;
1666 bool IsImportant =
false;
1667 if (!ContextSizeInfo.
empty()) {
1668 auto &
Entry = ContextIdToContextSizeInfos[LastContextId];
1673 for (
auto &CSI : ContextSizeInfo)
1674 TotalCold += CSI.TotalSize;
1680 TotalCold > TotalSizeToContextIdTopNCold.begin()->first) {
1683 auto IdToRemove = TotalSizeToContextIdTopNCold.begin()->second;
1684 TotalSizeToContextIdTopNCold.erase(
1685 TotalSizeToContextIdTopNCold.begin());
1687 ImportantContextIdInfo.
erase(IdToRemove);
1689 TotalSizeToContextIdTopNCold[TotalCold] = LastContextId;
1693 Entry.insert(
Entry.begin(), ContextSizeInfo.begin(), ContextSizeInfo.end());
1697 AllocNode->AllocTypes |= (uint8_t)
AllocType;
1702 ContextNode *PrevNode = AllocNode;
1706 SmallSet<uint64_t, 8> StackIdSet;
1709 ContextIter != StackContext.
end(); ++ContextIter) {
1710 auto StackId = getStackId(*ContextIter);
1712 ImportantContextIdInfo[LastContextId].StackIds.push_back(StackId);
1713 ContextNode *StackNode = getNodeForStackId(StackId);
1715 StackNode = createNewNode(
false);
1716 StackEntryIdToContextNodeMap[StackId] = StackNode;
1717 StackNode->OrigStackOrAllocId = StackId;
1722 auto Ins = StackIdSet.
insert(StackId);
1724 StackNode->Recursive =
true;
1726 StackNode->AllocTypes |= (uint8_t)
AllocType;
1727 PrevNode->addOrUpdateCallerEdge(StackNode,
AllocType, LastContextId);
1728 PrevNode = StackNode;
1732template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1734CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::duplicateContextIds(
1735 const DenseSet<uint32_t> &StackSequenceContextIds,
1736 DenseMap<uint32_t, DenseSet<uint32_t>> &OldToNewContextIds) {
1737 DenseSet<uint32_t> NewContextIds;
1738 for (
auto OldId : StackSequenceContextIds) {
1739 NewContextIds.
insert(++LastContextId);
1740 OldToNewContextIds[OldId].insert(LastContextId);
1743 ContextIdToAllocationType[LastContextId] = ContextIdToAllocationType[OldId];
1744 auto CSI = ContextIdToContextSizeInfos.
find(OldId);
1745 if (CSI != ContextIdToContextSizeInfos.
end())
1746 ContextIdToContextSizeInfos[LastContextId] = CSI->second;
1747 if (DotAllocContextIds.
contains(OldId))
1748 DotAllocContextIds.
insert(LastContextId);
1750 return NewContextIds;
1753template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1754void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
1755 propagateDuplicateContextIds(
1756 const DenseMap<uint32_t, DenseSet<uint32_t>> &OldToNewContextIds) {
1758 auto GetNewIds = [&OldToNewContextIds](
const DenseSet<uint32_t> &ContextIds) {
1759 DenseSet<uint32_t> NewIds;
1760 for (
auto Id : ContextIds)
1761 if (
auto NewId = OldToNewContextIds.find(Id);
1762 NewId != OldToNewContextIds.end())
1768 auto UpdateCallers = [&](ContextNode *
Node,
1769 DenseSet<const ContextEdge *> &Visited,
1770 auto &&UpdateCallers) ->
void {
1771 for (
const auto &
Edge :
Node->CallerEdges) {
1775 ContextNode *NextNode =
Edge->Caller;
1776 DenseSet<uint32_t> NewIdsToAdd = GetNewIds(
Edge->getContextIds());
1779 if (!NewIdsToAdd.
empty()) {
1780 Edge->getContextIds().insert_range(NewIdsToAdd);
1781 UpdateCallers(NextNode, Visited, UpdateCallers);
1786 DenseSet<const ContextEdge *> Visited;
1787 for (
auto &Entry : AllocationCallToContextNodeMap) {
1789 UpdateCallers(Node, Visited, UpdateCallers);
1793template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1794void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::connectNewNode(
1795 ContextNode *NewNode, ContextNode *OrigNode,
bool TowardsCallee,
1796 const DenseSet<uint32_t> &ContextIds) {
1798 TowardsCallee ? OrigNode->CalleeEdges : OrigNode->CallerEdges;
1800 for (
auto EI = OrigEdges.begin(); EI != OrigEdges.end();) {
1802 DenseSet<uint32_t> NewEdgeContextIds;
1807 if (NewEdgeContextIds.
empty()) {
1811 if (TowardsCallee) {
1812 uint8_t NewAllocType = computeAllocType(NewEdgeContextIds);
1813 auto NewEdge = std::make_shared<ContextEdge>(
1814 Edge->Callee, NewNode, NewAllocType, std::move(NewEdgeContextIds));
1815 NewNode->CalleeEdges.push_back(NewEdge);
1816 NewEdge->Callee->CallerEdges.push_back(NewEdge);
1818 uint8_t NewAllocType = computeAllocType(NewEdgeContextIds);
1819 auto NewEdge = std::make_shared<ContextEdge>(
1820 NewNode,
Edge->Caller, NewAllocType, std::move(NewEdgeContextIds));
1821 NewNode->CallerEdges.push_back(NewEdge);
1822 NewEdge->Caller->CalleeEdges.push_back(NewEdge);
1825 if (
Edge->getContextIds().empty()) {
1826 removeEdgeFromGraph(
Edge.get(), &EI, TowardsCallee);
1833template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1835 const std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>> &Edge) {
1839 assert(!Edge->ContextIds.empty());
1842template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1844 bool CheckEdges =
true) {
1845 if (
Node->isRemoved())
1849 auto NodeContextIds =
Node->getContextIds();
1853 if (
Node->CallerEdges.size()) {
1855 Node->CallerEdges.front()->ContextIds);
1859 set_union(CallerEdgeContextIds, Edge->ContextIds);
1866 NodeContextIds == CallerEdgeContextIds ||
1869 if (
Node->CalleeEdges.size()) {
1871 Node->CalleeEdges.front()->ContextIds);
1875 set_union(CalleeEdgeContextIds, Edge->getContextIds());
1881 NodeContextIds == CalleeEdgeContextIds);
1890 for (
const auto &
E :
Node->CalleeEdges)
1896template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
1897void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
1898 assignStackNodesPostOrder(ContextNode *Node,
1899 DenseSet<const ContextNode *> &Visited,
1900 DenseMap<
uint64_t, std::vector<CallContextInfo>>
1901 &StackIdToMatchingCalls,
1902 DenseMap<CallInfo, CallInfo> &CallToMatchingCall,
1903 const DenseSet<uint32_t> &ImportantContextIds) {
1911 auto CallerEdges =
Node->CallerEdges;
1912 for (
auto &
Edge : CallerEdges) {
1914 if (
Edge->isRemoved()) {
1918 assignStackNodesPostOrder(
Edge->Caller, Visited, StackIdToMatchingCalls,
1919 CallToMatchingCall, ImportantContextIds);
1928 if (
Node->IsAllocation ||
1929 !StackIdToMatchingCalls.count(
Node->OrigStackOrAllocId))
1932 auto &Calls = StackIdToMatchingCalls[
Node->OrigStackOrAllocId];
1936 if (Calls.size() == 1) {
1937 auto &[
Call, Ids,
Func, SavedContextIds] = Calls[0];
1938 if (Ids.size() == 1) {
1939 assert(SavedContextIds.empty());
1941 assert(Node == getNodeForStackId(Ids[0]));
1942 if (
Node->Recursive)
1945 NonAllocationCallToContextNodeMap[
Call] =
Node;
1947 recordStackNode(Ids, Node,
Node->getContextIds(), ImportantContextIds);
1956 ContextNode *LastNode = getNodeForStackId(LastId);
1959 assert(LastNode == Node);
1961 ContextNode *LastNode =
Node;
1966 DenseSet<uint32_t> LastNodeContextIds = LastNode->getContextIds();
1968 [[maybe_unused]]
bool PrevIterCreatedNode =
false;
1969 bool CreatedNode =
false;
1970 for (
unsigned I = 0;
I < Calls.size();
1971 I++, PrevIterCreatedNode = CreatedNode) {
1972 CreatedNode =
false;
1973 auto &[
Call, Ids,
Func, SavedContextIds] = Calls[
I];
1976 if (SavedContextIds.empty()) {
1983 auto MatchingCall = CallToMatchingCall[
Call];
1984 if (!NonAllocationCallToContextNodeMap.contains(MatchingCall)) {
1988 assert(
I > 0 && !PrevIterCreatedNode);
1991 NonAllocationCallToContextNodeMap[MatchingCall]->MatchingCalls.push_back(
1996 assert(LastId == Ids.back());
2005 ContextNode *PrevNode = LastNode;
2009 for (
auto IdIter = Ids.rbegin() + 1; IdIter != Ids.rend(); IdIter++) {
2011 ContextNode *CurNode = getNodeForStackId(Id);
2015 assert(!CurNode->Recursive);
2017 auto *
Edge = CurNode->findEdgeFromCaller(PrevNode);
2029 if (SavedContextIds.empty()) {
2038 ContextNode *NewNode = createNewNode(
false, Func,
Call);
2039 NonAllocationCallToContextNodeMap[
Call] = NewNode;
2041 NewNode->AllocTypes = computeAllocType(SavedContextIds);
2043 ContextNode *FirstNode = getNodeForStackId(Ids[0]);
2049 connectNewNode(NewNode, FirstNode,
true, SavedContextIds);
2054 connectNewNode(NewNode, LastNode,
false, SavedContextIds);
2059 for (
auto Id : Ids) {
2060 ContextNode *CurNode = getNodeForStackId(Id);
2067 auto *PrevEdge = CurNode->findEdgeFromCallee(PrevNode);
2074 set_subtract(PrevEdge->getContextIds(), SavedContextIds);
2075 if (PrevEdge->getContextIds().empty())
2076 removeEdgeFromGraph(PrevEdge);
2081 CurNode->AllocTypes = CurNode->CalleeEdges.empty()
2082 ? (uint8_t)AllocationType::None
2083 : CurNode->computeAllocType();
2087 recordStackNode(Ids, NewNode, SavedContextIds, ImportantContextIds);
2091 for (
auto Id : Ids) {
2092 ContextNode *CurNode = getNodeForStackId(Id);
2101template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2102void CallsiteContextGraph<DerivedCCG, FuncTy,
2103 CallTy>::fixupImportantContexts() {
2104 if (ImportantContextIdInfo.
empty())
2108 NumImportantContextIds = ImportantContextIdInfo.
size();
2114 exportToDot(
"beforestackfixup");
2139 for (
auto &[CurContextId, Info] : ImportantContextIdInfo) {
2140 if (
Info.StackIdsToNode.empty())
2143 ContextNode *PrevNode =
nullptr;
2144 ContextNode *CurNode =
nullptr;
2145 DenseSet<const ContextEdge *> VisitedEdges;
2146 ArrayRef<uint64_t> AllStackIds(
Info.StackIds);
2149 for (
unsigned I = 0;
I < AllStackIds.size();
I++, PrevNode = CurNode) {
2153 auto LenToEnd = AllStackIds.size() -
I;
2161 auto CheckStackIds = AllStackIds.slice(
I, Len);
2162 auto EntryIt =
Info.StackIdsToNode.find(CheckStackIds);
2163 if (EntryIt ==
Info.StackIdsToNode.end())
2165 CurNode = EntryIt->second;
2182 auto *CurEdge = PrevNode->findEdgeFromCaller(CurNode);
2185 if (CurEdge->getContextIds().insert(CurContextId).second) {
2186 NumFixupEdgeIdsInserted++;
2191 NumFixupEdgesAdded++;
2192 DenseSet<uint32_t> ContextIds({CurContextId});
2193 auto AllocType = computeAllocType(ContextIds);
2194 auto NewEdge = std::make_shared<ContextEdge>(
2195 PrevNode, CurNode,
AllocType, std::move(ContextIds));
2196 PrevNode->CallerEdges.push_back(NewEdge);
2197 CurNode->CalleeEdges.push_back(NewEdge);
2199 CurEdge = NewEdge.get();
2202 VisitedEdges.
insert(CurEdge);
2205 for (
auto &
Edge : PrevNode->CallerEdges) {
2209 Edge->getContextIds().erase(CurContextId);
2217template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2218void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::updateStackNodes() {
2226 DenseMap<uint64_t, std::vector<CallContextInfo>> StackIdToMatchingCalls;
2227 for (
auto &[Func, CallsWithMetadata] : FuncToCallsWithMetadata) {
2228 for (
auto &
Call : CallsWithMetadata) {
2230 if (AllocationCallToContextNodeMap.count(
Call))
2232 auto StackIdsWithContextNodes =
2233 getStackIdsWithContextNodesForCall(
Call.call());
2236 if (StackIdsWithContextNodes.empty())
2240 StackIdToMatchingCalls[StackIdsWithContextNodes.back()].push_back(
2241 {
Call.call(), StackIdsWithContextNodes,
Func, {}});
2251 DenseMap<uint32_t, DenseSet<uint32_t>> OldToNewContextIds;
2255 DenseMap<CallInfo, CallInfo> CallToMatchingCall;
2256 for (
auto &It : StackIdToMatchingCalls) {
2257 auto &Calls = It.getSecond();
2259 if (Calls.size() == 1) {
2260 auto &Ids = Calls[0].StackIds;
2261 if (Ids.size() == 1)
2274 DenseMap<const FuncTy *, unsigned> FuncToIndex;
2275 for (
const auto &[Idx, CallCtxInfo] :
enumerate(Calls))
2276 FuncToIndex.
insert({CallCtxInfo.Func,
Idx});
2279 [&FuncToIndex](
const CallContextInfo &
A,
const CallContextInfo &
B) {
2280 return A.StackIds.size() >
B.StackIds.size() ||
2281 (
A.StackIds.size() ==
B.StackIds.size() &&
2282 (
A.StackIds <
B.StackIds ||
2283 (
A.StackIds ==
B.StackIds &&
2284 FuncToIndex[
A.Func] < FuncToIndex[
B.Func])));
2291 ContextNode *LastNode = getNodeForStackId(LastId);
2295 if (LastNode->Recursive)
2300 DenseSet<uint32_t> LastNodeContextIds = LastNode->getContextIds();
2308 DenseSet<const FuncTy *> MatchingIdsFuncSet;
2311 for (
unsigned I = 0;
I < Calls.size();
I++) {
2312 auto &[
Call, Ids,
Func, SavedContextIds] = Calls[
I];
2313 assert(SavedContextIds.empty());
2314 assert(LastId == Ids.back());
2319 if (
I > 0 && Ids != Calls[
I - 1].StackIds)
2320 MatchingIdsFuncSet.
clear();
2327 DenseSet<uint32_t> StackSequenceContextIds = LastNodeContextIds;
2329 ContextNode *PrevNode = LastNode;
2330 ContextNode *CurNode = LastNode;
2335 for (
auto IdIter = Ids.rbegin() + 1; IdIter != Ids.rend(); IdIter++) {
2337 CurNode = getNodeForStackId(Id);
2341 if (CurNode->Recursive) {
2346 auto *
Edge = CurNode->findEdgeFromCaller(PrevNode);
2367 if (StackSequenceContextIds.
empty()) {
2380 if (Ids.back() != getLastStackId(
Call)) {
2381 for (
const auto &PE : LastNode->CallerEdges) {
2382 set_subtract(StackSequenceContextIds, PE->getContextIds());
2383 if (StackSequenceContextIds.
empty())
2387 if (StackSequenceContextIds.
empty())
2399 MatchingIdsFuncSet.
insert(Func);
2406 bool DuplicateContextIds =
false;
2407 for (
unsigned J =
I + 1; J < Calls.size(); J++) {
2408 auto &CallCtxInfo = Calls[J];
2409 auto &NextIds = CallCtxInfo.StackIds;
2412 auto *NextFunc = CallCtxInfo.Func;
2413 if (NextFunc != Func) {
2416 DuplicateContextIds =
true;
2419 auto &NextCall = CallCtxInfo.Call;
2420 CallToMatchingCall[NextCall] =
Call;
2431 OldToNewContextIds.
reserve(OldToNewContextIds.
size() +
2432 StackSequenceContextIds.
size());
2435 ? duplicateContextIds(StackSequenceContextIds, OldToNewContextIds)
2436 : StackSequenceContextIds;
2437 assert(!SavedContextIds.empty());
2439 if (!DuplicateContextIds) {
2443 set_subtract(LastNodeContextIds, StackSequenceContextIds);
2444 if (LastNodeContextIds.
empty())
2451 propagateDuplicateContextIds(OldToNewContextIds);
2461 DenseSet<const ContextNode *> Visited;
2463 ImportantContextIdInfo.keys());
2464 for (
auto &Entry : AllocationCallToContextNodeMap)
2465 assignStackNodesPostOrder(
Entry.second, Visited, StackIdToMatchingCalls,
2466 CallToMatchingCall, ImportantContextIds);
2468 fixupImportantContexts();
2474uint64_t ModuleCallsiteContextGraph::getLastStackId(Instruction *
Call) {
2475 CallStack<MDNode, MDNode::op_iterator> CallsiteContext(
2477 return CallsiteContext.
back();
2480uint64_t IndexCallsiteContextGraph::getLastStackId(IndexCall &
Call) {
2482 CallStack<CallsiteInfo, SmallVector<unsigned>::const_iterator>
2485 return Index.getStackIdAtIndex(CallsiteContext.
back());
2507 auto Pos =
F.getName().find_last_of(
'.');
2510 bool Err =
F.getName().drop_front(Pos + 1).getAsInteger(10, CloneNo);
2516std::string ModuleCallsiteContextGraph::getLabel(
const Function *Func,
2517 const Instruction *
Call,
2518 unsigned CloneNo)
const {
2524std::string IndexCallsiteContextGraph::getLabel(
const FunctionSummary *Func,
2525 const IndexCall &
Call,
2526 unsigned CloneNo)
const {
2527 auto VI = FSToVIMap.find(Func);
2528 assert(VI != FSToVIMap.end());
2531 return CallerName +
" -> alloc";
2534 return CallerName +
" -> " +
2536 Callsite->Clones[CloneNo]);
2540std::string ModuleCallsiteContextGraph::getFuncName(
const Function *Func,
2541 unsigned CloneNo)
const {
2547void ModuleCallsiteContextGraph::populateFunctionsWithCallers() {
2550 for (
const auto &
F :
Mod)
2552 FunctionsWithCallers.
insert(&
F);
2555std::string IndexCallsiteContextGraph::getFuncName(
const FunctionSummary *Func,
2556 unsigned CloneNo)
const {
2559 auto VI = FSToVIMap.find(Func);
2560 if (VI != FSToVIMap.end()) {
2561 if (!
VI->second.name().empty())
2569bool IndexCallsiteContextGraph::isFuncDead(
const FunctionSummary *Func)
const {
2570 return Index.withGlobalValueDeadStripping() &&
Func && !
Func->isLive();
2573void IndexCallsiteContextGraph::populateFunctionsWithCallers() {
2574 for (
const auto &
I : Index) {
2576 for (
const auto &S :
VI.getSummaryList()) {
2578 !isPrevailing(
VI.getGUID(), S.get()))
2580 if (
Index.withGlobalValueDeadStripping() && !S->isLive())
2582 auto AddReferenced = [&](ValueInfo RefVI) {
2583 for (
const auto &RefS : RefVI.getSummaryList()) {
2584 const GlobalValueSummary *
Base = RefS->getBaseObject();
2586 FunctionsWithCallers.
insert(RefFS);
2590 for (
const auto &RefVI : S->refs())
2591 AddReferenced(RefVI);
2594 for (
const auto &CallEdge :
FS->calls())
2595 AddReferenced(CallEdge.first);
2600std::vector<uint64_t>
2601ModuleCallsiteContextGraph::getStackIdsWithContextNodesForCall(
2602 Instruction *
Call) {
2603 CallStack<MDNode, MDNode::op_iterator> CallsiteContext(
2605 return getStackIdsWithContextNodes<MDNode, MDNode::op_iterator>(
2609std::vector<uint64_t>
2610IndexCallsiteContextGraph::getStackIdsWithContextNodesForCall(IndexCall &
Call) {
2612 CallStack<CallsiteInfo, SmallVector<unsigned>::const_iterator>
2614 return getStackIdsWithContextNodes<CallsiteInfo,
2615 SmallVector<unsigned>::const_iterator>(
2619template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2620template <
class NodeT,
class IteratorT>
2621std::vector<uint64_t>
2622CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::getStackIdsWithContextNodes(
2623 CallStack<NodeT, IteratorT> &CallsiteContext) {
2624 std::vector<uint64_t> StackIds;
2625 for (
auto IdOrIndex : CallsiteContext) {
2626 auto StackId = getStackId(IdOrIndex);
2627 ContextNode *
Node = getNodeForStackId(StackId);
2630 StackIds.push_back(StackId);
2635ModuleCallsiteContextGraph::ModuleCallsiteContextGraph(
2637 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter)
2638 :
Mod(
M), OREGetter(OREGetter) {
2642 std::map<uint64_t, uint32_t> TotalSizeToContextIdTopNCold;
2644 std::vector<CallInfo> CallsWithMetadata;
2645 for (
auto &BB :
F) {
2646 for (
auto &
I : BB) {
2649 if (
auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof)) {
2650 CallsWithMetadata.push_back(&
I);
2651 auto *AllocNode = addAllocNode(&
I, &
F);
2652 auto *CallsiteMD =
I.getMetadata(LLVMContext::MD_callsite);
2656 for (
auto &MDOp : MemProfMD->operands()) {
2658 std::vector<ContextTotalSize> ContextSizeInfo;
2660 if (MIBMD->getNumOperands() > 2) {
2661 for (
unsigned I = 2;
I < MIBMD->getNumOperands();
I++) {
2662 MDNode *ContextSizePair =
2671 ContextSizeInfo.push_back({FullStackId, TotalSize});
2677 addStackNodesForMIB<MDNode, MDNode::op_iterator>(
2678 AllocNode, StackContext, CallsiteContext,
2680 TotalSizeToContextIdTopNCold);
2685 DotAllocContextIds = AllocNode->getContextIds();
2689 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
2690 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
2693 else if (
I.getMetadata(LLVMContext::MD_callsite)) {
2694 CallsWithMetadata.push_back(&
I);
2698 if (!CallsWithMetadata.empty())
2699 FuncToCallsWithMetadata[&
F] = CallsWithMetadata;
2703 dbgs() <<
"CCG before updating call stack chains:\n";
2708 exportToDot(
"prestackupdate");
2713 exportToDot(
"poststackupdate");
2715 handleCallsitesWithMultipleTargets();
2720 for (
auto &FuncEntry : FuncToCallsWithMetadata)
2721 for (
auto &
Call : FuncEntry.second)
2722 Call.call()->setMetadata(LLVMContext::MD_callsite,
nullptr);
2728IndexCallsiteContextGraph::findAliaseeGUIDsPrevailingInDifferentModule() {
2729 DenseSet<GlobalValue::GUID> AliaseeGUIDs;
2730 for (
auto &
I : Index) {
2732 for (
auto &S :
VI.getSummaryList()) {
2737 auto *AliaseeSummary = &AS->getAliasee();
2745 !isPrevailing(
VI.getGUID(), S.get()))
2750 auto AliaseeGUID = AS->getAliaseeGUID();
2752 if (!isPrevailing(AliaseeGUID, AliaseeSummary))
2753 AliaseeGUIDs.
insert(AliaseeGUID);
2756 AliaseesPrevailingInDiffModuleFromAlias += AliaseeGUIDs.
size();
2757 return AliaseeGUIDs;
2760IndexCallsiteContextGraph::IndexCallsiteContextGraph(
2761 ModuleSummaryIndex &Index,
2771 findAliaseeGUIDsPrevailingInDifferentModule();
2775 std::map<uint64_t, uint32_t> TotalSizeToContextIdTopNCold;
2780 for (
const auto &
I : Index.sortedGlobalValueSummariesRange()) {
2781 auto VI = Index.getValueInfo(
I);
2782 if (GUIDsToSkip.
contains(VI.getGUID()))
2784 for (
auto &S : VI.getSummaryList()) {
2793 !isPrevailing(VI.getGUID(), S.get()))
2798 std::vector<CallInfo> CallsWithMetadata;
2799 if (!
FS->allocs().empty()) {
2800 for (
auto &AN :
FS->mutableAllocs()) {
2805 if (AN.MIBs.empty())
2807 IndexCall AllocCall(&AN);
2808 CallsWithMetadata.push_back(AllocCall);
2809 auto *AllocNode = addAllocNode(AllocCall, FS);
2817 AN.ContextSizeInfos.size() == AN.MIBs.size());
2819 for (
auto &MIB : AN.MIBs) {
2822 std::vector<ContextTotalSize> ContextSizeInfo;
2823 if (!AN.ContextSizeInfos.empty()) {
2824 for (
auto [FullStackId, TotalSize] : AN.ContextSizeInfos[
I])
2825 ContextSizeInfo.push_back({FullStackId, TotalSize});
2827 addStackNodesForMIB<MIBInfo, SmallVector<unsigned>::const_iterator>(
2828 AllocNode, StackContext, EmptyContext, MIB.AllocType,
2829 ContextSizeInfo, TotalSizeToContextIdTopNCold);
2835 DotAllocContextIds = AllocNode->getContextIds();
2841 AN.Versions[0] = (
uint8_t)allocTypeToUse(AllocNode->AllocTypes);
2845 if (!
FS->callsites().empty())
2846 for (
auto &SN :
FS->mutableCallsites()) {
2847 IndexCall StackNodeCall(&SN);
2848 CallsWithMetadata.push_back(StackNodeCall);
2851 if (!CallsWithMetadata.empty())
2852 FuncToCallsWithMetadata[
FS] = CallsWithMetadata;
2854 if (!
FS->allocs().empty() || !
FS->callsites().empty())
2860 dbgs() <<
"CCG before updating call stack chains:\n";
2865 exportToDot(
"prestackupdate");
2870 exportToDot(
"poststackupdate");
2872 handleCallsitesWithMultipleTargets();
2877template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2878void CallsiteContextGraph<DerivedCCG, FuncTy,
2879 CallTy>::handleCallsitesWithMultipleTargets() {
2894 std::vector<std::pair<CallInfo, ContextNode *>> NewCallToNode;
2895 for (
auto &Entry : NonAllocationCallToContextNodeMap) {
2896 auto *
Node = Entry.second;
2905 std::vector<CallInfo> AllCalls;
2906 AllCalls.reserve(
Node->MatchingCalls.size() + 1);
2907 AllCalls.push_back(
Node->Call);
2921 if (partitionCallsByCallee(
Node, AllCalls, NewCallToNode))
2924 auto It = AllCalls.begin();
2926 for (; It != AllCalls.end(); ++It) {
2929 for (
auto EI =
Node->CalleeEdges.begin(); EI !=
Node->CalleeEdges.end();
2932 if (!Edge->Callee->hasCall())
2934 assert(NodeToCallingFunc.count(Edge->Callee));
2936 if (!calleesMatch(
ThisCall.call(), EI, TailCallToContextNodeMap)) {
2945 if (
Node->Call != ThisCall) {
2946 Node->setCall(ThisCall);
2957 Node->MatchingCalls.clear();
2960 if (It == AllCalls.end()) {
2961 RemovedEdgesWithMismatchedCallees++;
2965 Node->setCall(CallInfo());
2970 for (++It; It != AllCalls.end(); ++It) {
2974 Node->MatchingCalls.push_back(ThisCall);
2983 NonAllocationCallToContextNodeMap.remove_if([](
const auto &it) {
2984 return !it.second->hasCall() || it.second->Call != it.first;
2988 for (
auto &[
Call,
Node] : NewCallToNode)
2989 NonAllocationCallToContextNodeMap[
Call] =
Node;
2993 for (
auto &[
Call,
Node] : TailCallToContextNodeMap)
2994 NonAllocationCallToContextNodeMap[
Call] =
Node;
2997template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
2998bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::partitionCallsByCallee(
3000 std::vector<std::pair<CallInfo, ContextNode *>> &NewCallToNode) {
3004 struct CallsWithSameCallee {
3005 std::vector<CallInfo> Calls;
3006 ContextNode *
Node =
nullptr;
3012 for (
auto ThisCall : AllCalls) {
3013 auto *
F = getCalleeFunc(
ThisCall.call());
3015 CalleeFuncToCallInfo[
F].Calls.push_back(ThisCall);
3024 for (
const auto &Edge :
Node->CalleeEdges) {
3025 if (!Edge->Callee->hasCall())
3027 const FuncTy *ProfiledCalleeFunc = NodeToCallingFunc[Edge->Callee];
3028 if (CalleeFuncToCallInfo.
contains(ProfiledCalleeFunc))
3029 CalleeNodeToCallInfo[Edge->Callee] =
3030 &CalleeFuncToCallInfo[ProfiledCalleeFunc];
3036 if (CalleeNodeToCallInfo.
empty())
3048 ContextNode *UnmatchedCalleesNode =
nullptr;
3050 bool UsedOrigNode =
false;
3055 auto CalleeEdges =
Node->CalleeEdges;
3056 for (
auto &Edge : CalleeEdges) {
3057 if (!Edge->Callee->hasCall())
3062 ContextNode *CallerNodeToUse =
nullptr;
3066 if (!CalleeNodeToCallInfo.
contains(Edge->Callee)) {
3067 if (!UnmatchedCalleesNode)
3068 UnmatchedCalleesNode =
3069 createNewNode(
false, NodeToCallingFunc[
Node]);
3070 CallerNodeToUse = UnmatchedCalleesNode;
3074 auto *Info = CalleeNodeToCallInfo[Edge->Callee];
3077 if (!UsedOrigNode) {
3080 Node->MatchingCalls.clear();
3081 UsedOrigNode =
true;
3084 createNewNode(
false, NodeToCallingFunc[
Node]);
3085 assert(!Info->Calls.empty());
3088 Info->Node->setCall(Info->Calls.front());
3094 NewCallToNode.push_back({Info->Node->Call, Info->Node});
3096 CallerNodeToUse = Info->Node;
3100 if (CallerNodeToUse ==
Node)
3103 moveCalleeEdgeToNewCaller(Edge, CallerNodeToUse);
3110 for (
auto &
I : CalleeNodeToCallInfo)
3111 removeNoneTypeCallerEdges(
I.second->Node);
3112 if (UnmatchedCalleesNode)
3113 removeNoneTypeCallerEdges(UnmatchedCalleesNode);
3114 removeNoneTypeCallerEdges(
Node);
3127 return Index.getStackIdAtIndex(IdOrIndex);
3130template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3131bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::calleesMatch(
3132 CallTy
Call, EdgeIter &EI,
3133 MapVector<CallInfo, ContextNode *> &TailCallToContextNodeMap) {
3135 const FuncTy *ProfiledCalleeFunc = NodeToCallingFunc[
Edge->Callee];
3136 const FuncTy *CallerFunc = NodeToCallingFunc[
Edge->Caller];
3139 std::vector<std::pair<CallTy, FuncTy *>> FoundCalleeChain;
3140 if (!calleeMatchesFunc(
Call, ProfiledCalleeFunc, CallerFunc,
3145 if (FoundCalleeChain.empty())
3149 auto *CurEdge =
Callee->findEdgeFromCaller(Caller);
3153 CurEdge->ContextIds.insert_range(
Edge->ContextIds);
3154 CurEdge->AllocTypes |=
Edge->AllocTypes;
3159 auto NewEdge = std::make_shared<ContextEdge>(
3160 Callee, Caller,
Edge->AllocTypes,
Edge->ContextIds);
3161 Callee->CallerEdges.push_back(NewEdge);
3162 if (Caller ==
Edge->Caller) {
3166 EI =
Caller->CalleeEdges.insert(EI, NewEdge);
3169 "Iterator position not restored after insert and increment");
3171 Caller->CalleeEdges.push_back(NewEdge);
3176 auto *CurCalleeNode =
Edge->Callee;
3177 for (
auto &[NewCall, Func] : FoundCalleeChain) {
3178 ContextNode *NewNode =
nullptr;
3180 if (TailCallToContextNodeMap.
count(NewCall)) {
3181 NewNode = TailCallToContextNodeMap[NewCall];
3182 NewNode->AllocTypes |=
Edge->AllocTypes;
3184 FuncToCallsWithMetadata[
Func].push_back({NewCall});
3186 NewNode = createNewNode(
false, Func, NewCall);
3187 TailCallToContextNodeMap[NewCall] = NewNode;
3188 NewNode->AllocTypes =
Edge->AllocTypes;
3192 AddEdge(NewNode, CurCalleeNode);
3194 CurCalleeNode = NewNode;
3198 AddEdge(
Edge->Caller, CurCalleeNode);
3206 removeEdgeFromGraph(
Edge.get(), &EI,
true);
3218bool ModuleCallsiteContextGraph::findProfiledCalleeThroughTailCalls(
3220 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain,
3221 bool &FoundMultipleCalleeChains) {
3228 FoundCalleeChain.push_back({Callsite,
F});
3243 bool FoundSingleCalleeChain =
false;
3244 for (
auto &BB : *CalleeFunc) {
3245 for (
auto &
I : BB) {
3247 if (!CB || !CB->isTailCall())
3249 auto *CalledValue = CB->getCalledOperand();
3250 auto *CalledFunction = CB->getCalledFunction();
3251 if (CalledValue && !CalledFunction) {
3252 CalledValue = CalledValue->stripPointerCasts();
3259 assert(!CalledFunction &&
3260 "Expected null called function in callsite for alias");
3263 if (!CalledFunction)
3265 if (CalledFunction == ProfiledCallee) {
3266 if (FoundSingleCalleeChain) {
3267 FoundMultipleCalleeChains =
true;
3270 FoundSingleCalleeChain =
true;
3271 FoundProfiledCalleeCount++;
3272 FoundProfiledCalleeDepth +=
Depth;
3273 if (
Depth > FoundProfiledCalleeMaxDepth)
3274 FoundProfiledCalleeMaxDepth =
Depth;
3275 SaveCallsiteInfo(&
I, CalleeFunc);
3276 }
else if (findProfiledCalleeThroughTailCalls(
3277 ProfiledCallee, CalledFunction,
Depth + 1,
3278 FoundCalleeChain, FoundMultipleCalleeChains)) {
3281 assert(!FoundMultipleCalleeChains);
3282 if (FoundSingleCalleeChain) {
3283 FoundMultipleCalleeChains =
true;
3286 FoundSingleCalleeChain =
true;
3287 SaveCallsiteInfo(&
I, CalleeFunc);
3288 }
else if (FoundMultipleCalleeChains)
3293 return FoundSingleCalleeChain;
3296const Function *ModuleCallsiteContextGraph::getCalleeFunc(Instruction *
Call) {
3298 if (!CB->getCalledOperand() || CB->isIndirectCall())
3300 auto *CalleeVal = CB->getCalledOperand()->stripPointerCasts();
3307bool ModuleCallsiteContextGraph::calleeMatchesFunc(
3309 std::vector<std::pair<Instruction *, Function *>> &FoundCalleeChain) {
3311 if (!CB->getCalledOperand() || CB->isIndirectCall())
3313 auto *CalleeVal = CB->getCalledOperand()->stripPointerCasts();
3315 if (CalleeFunc == Func)
3318 if (Alias && Alias->getAliasee() == Func)
3329 bool FoundMultipleCalleeChains =
false;
3330 if (!findProfiledCalleeThroughTailCalls(Func, CalleeVal,
Depth,
3332 FoundMultipleCalleeChains)) {
3333 LLVM_DEBUG(
dbgs() <<
"Not found through unique tail call chain: "
3334 <<
Func->getName() <<
" from " << CallerFunc->
getName()
3335 <<
" that actually called " << CalleeVal->getName()
3336 << (FoundMultipleCalleeChains
3337 ?
" (found multiple possible chains)"
3340 if (FoundMultipleCalleeChains)
3341 FoundProfiledCalleeNonUniquelyCount++;
3348bool ModuleCallsiteContextGraph::sameCallee(Instruction *Call1,
3349 Instruction *Call2) {
3351 if (!CB1->getCalledOperand() || CB1->isIndirectCall())
3353 auto *CalleeVal1 = CB1->getCalledOperand()->stripPointerCasts();
3356 if (!CB2->getCalledOperand() || CB2->isIndirectCall())
3358 auto *CalleeVal2 = CB2->getCalledOperand()->stripPointerCasts();
3360 return CalleeFunc1 == CalleeFunc2;
3363bool IndexCallsiteContextGraph::findProfiledCalleeThroughTailCalls(
3364 ValueInfo ProfiledCallee, ValueInfo CurCallee,
unsigned Depth,
3365 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain,
3366 bool &FoundMultipleCalleeChains) {
3372 auto CreateAndSaveCallsiteInfo = [&](ValueInfo
Callee, FunctionSummary *
FS) {
3375 if (!FunctionCalleesToSynthesizedCallsiteInfos.count(FS) ||
3376 !FunctionCalleesToSynthesizedCallsiteInfos[FS].count(Callee))
3379 FunctionCalleesToSynthesizedCallsiteInfos[
FS][
Callee] =
3380 std::make_unique<CallsiteInfo>(Callee, SmallVector<unsigned>());
3381 CallsiteInfo *NewCallsiteInfo =
3382 FunctionCalleesToSynthesizedCallsiteInfos[
FS][
Callee].get();
3383 FoundCalleeChain.push_back({NewCallsiteInfo,
FS});
3390 bool FoundSingleCalleeChain =
false;
3393 !isPrevailing(CurCallee.
getGUID(), S.get()))
3398 auto FSVI = CurCallee;
3401 FSVI = AS->getAliaseeVI();
3402 for (
auto &CallEdge :
FS->calls()) {
3403 if (!CallEdge.second.hasTailCall())
3410 if (CallEdge.first == ProfiledCallee) {
3411 if (FoundSingleCalleeChain) {
3412 FoundMultipleCalleeChains =
true;
3415 FoundSingleCalleeChain =
true;
3416 FoundProfiledCalleeCount++;
3417 FoundProfiledCalleeDepth +=
Depth;
3418 if (
Depth > FoundProfiledCalleeMaxDepth)
3419 FoundProfiledCalleeMaxDepth =
Depth;
3420 if (CallEdge.second.hasIndirectCall())
3421 FoundProfiledCalleeIndirectTailCallCount++;
3422 CreateAndSaveCallsiteInfo(CallEdge.first, FS);
3424 assert(!FSToVIMap.count(FS) || FSToVIMap[FS] == FSVI);
3425 FSToVIMap[
FS] = FSVI;
3426 }
else if (findProfiledCalleeThroughTailCalls(
3427 ProfiledCallee, CallEdge.first,
Depth + 1,
3428 FoundCalleeChain, FoundMultipleCalleeChains)) {
3431 assert(!FoundMultipleCalleeChains);
3432 if (FoundSingleCalleeChain) {
3433 FoundMultipleCalleeChains =
true;
3436 FoundSingleCalleeChain =
true;
3437 if (CallEdge.second.hasIndirectCall())
3438 FoundProfiledCalleeIndirectTailCallCount++;
3439 CreateAndSaveCallsiteInfo(CallEdge.first, FS);
3441 assert(!FSToVIMap.count(FS) || FSToVIMap[FS] == FSVI);
3442 FSToVIMap[
FS] = FSVI;
3443 }
else if (FoundMultipleCalleeChains)
3448 return FoundSingleCalleeChain;
3451const FunctionSummary *
3452IndexCallsiteContextGraph::getCalleeFunc(IndexCall &
Call) {
3454 if (
Callee.getSummaryList().empty())
3459bool IndexCallsiteContextGraph::calleeMatchesFunc(
3460 IndexCall &
Call,
const FunctionSummary *Func,
3461 const FunctionSummary *CallerFunc,
3462 std::vector<std::pair<IndexCall, FunctionSummary *>> &FoundCalleeChain) {
3466 AliasSummary *Alias =
3467 Callee.getSummaryList().empty()
3470 assert(FSToVIMap.count(Func));
3471 auto FuncVI = FSToVIMap[
Func];
3472 if (Callee == FuncVI ||
3487 bool FoundMultipleCalleeChains =
false;
3488 if (!findProfiledCalleeThroughTailCalls(
3489 FuncVI, Callee,
Depth, FoundCalleeChain, FoundMultipleCalleeChains)) {
3490 LLVM_DEBUG(
dbgs() <<
"Not found through unique tail call chain: " << FuncVI
3491 <<
" from " << FSToVIMap[CallerFunc]
3492 <<
" that actually called " << Callee
3493 << (FoundMultipleCalleeChains
3494 ?
" (found multiple possible chains)"
3497 if (FoundMultipleCalleeChains)
3498 FoundProfiledCalleeNonUniquelyCount++;
3505bool IndexCallsiteContextGraph::sameCallee(IndexCall &Call1, IndexCall &Call2) {
3508 return Callee1 == Callee2;
3511template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3512void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::dump()
3518template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3519void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode::print(
3520 raw_ostream &OS)
const {
3521 OS <<
"Node " <<
this <<
"\n";
3525 OS <<
" (recursive)";
3527 if (!MatchingCalls.
empty()) {
3528 OS <<
"\tMatchingCalls:\n";
3529 for (
auto &MatchingCall : MatchingCalls) {
3531 MatchingCall.print(OS);
3535 OS <<
"\tNodeId: " <<
NodeId <<
"\n";
3537 OS <<
"\tContextIds:";
3539 auto ContextIds = getContextIds();
3540 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
3541 std::sort(SortedIds.begin(), SortedIds.end());
3542 for (
auto Id : SortedIds)
3545 OS <<
"\tCalleeEdges:\n";
3546 for (
auto &
Edge : CalleeEdges)
3547 OS <<
"\t\t" << *
Edge <<
" (Callee NodeId: " <<
Edge->Callee->NodeId
3549 OS <<
"\tCallerEdges:\n";
3550 for (
auto &
Edge : CallerEdges)
3551 OS <<
"\t\t" << *
Edge <<
" (Caller NodeId: " <<
Edge->Caller->NodeId
3553 if (!Clones.empty()) {
3556 for (
auto *
C : Clones)
3557 OS <<
LS <<
C <<
" NodeId: " <<
C->NodeId;
3559 }
else if (CloneOf) {
3560 OS <<
"\tClone of " << CloneOf <<
" NodeId: " << CloneOf->NodeId <<
"\n";
3564template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3565void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge::dump()
3571template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3572void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextEdge::print(
3573 raw_ostream &OS)
const {
3574 OS <<
"Edge from Callee " <<
Callee <<
" to Caller: " <<
Caller
3575 << (IsBackedge ?
" (BE)" :
"")
3577 OS <<
" ContextIds:";
3578 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
3579 std::sort(SortedIds.begin(), SortedIds.end());
3580 for (
auto Id : SortedIds)
3584template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3585void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::dump()
const {
3589template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3590void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::print(
3591 raw_ostream &OS)
const {
3592 OS <<
"Callsite Context Graph:\n";
3593 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
3595 if (
Node->isRemoved())
3602template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3603void CallsiteContextGraph<DerivedCCG, FuncTy,
3604 CallTy>::capturePreCloningContextInfo() {
3605 for (
const auto &Entry : AllocationCallToContextNodeMap) {
3606 const ContextNode *AllocNode =
Entry.second;
3610 for (
const auto &
Edge : AllocNode->CallerEdges) {
3611 if (!
Edge->isRemoved() &&
Edge->Caller->hasCall()) {
3612 PreCloningAllocHasMatchedCaller.insert(AllocNode);
3616 DenseSet<uint32_t> ContextIds = AllocNode->getContextIds();
3617 for (uint32_t Id : ContextIds) {
3618 PreCloningContextInfo
Info;
3624 Info.Chain.push_back(AllocNode);
3625 SmallPtrSet<const ContextNode *, 16> Visited;
3626 Visited.
insert(AllocNode);
3627 const ContextNode *Cur = AllocNode;
3629 const ContextNode *
Next =
nullptr;
3630 for (
const auto &
Edge : Cur->CallerEdges) {
3631 if (
Edge->isRemoved() ||
Edge->IsBackedge)
3633 if (
Edge->getContextIds().contains(Id) &&
3640 for (
const auto &
Edge : Cur->CallerEdges) {
3641 if (
Edge->isRemoved())
3643 if (
Edge->getContextIds().contains(Id) &&
3660 Info.MaxMatchedFrame = 0;
3661 for (
unsigned I = 1;
I <
Info.Chain.size(); ++
I) {
3662 if (
Info.Chain[
I]->hasCall()) {
3663 Info.MaxMatchedFrame =
I;
3665 const ContextNode *Unmatched =
Info.Chain[
I];
3666 Info.UnmatchedStackId = Unmatched->OrigStackOrAllocId;
3667 Info.StoppedAtRecursive = Unmatched->Recursive;
3671 if (
auto It = NodeToCallingFunc.find(Unmatched);
3672 It != NodeToCallingFunc.end()) {
3673 Info.StoppedAtMismatchedCallee =
true;
3674 Info.UnmatchedCallingFunc = It->second;
3684 if (
Info.MaxMatchedFrame > 0 &&
3685 Info.MaxMatchedFrame + 1 ==
Info.Chain.size()) {
3686 const ContextNode *OutermostMatchedNode =
3688 for (
const auto &
Edge : OutermostMatchedNode->CallerEdges) {
3689 if (!
Edge->isRemoved() &&
Edge->Caller->hasCall()) {
3690 Info.OutermostMatchedNodeHasOtherCallers =
true;
3696 PreCloningContextInfoMap[
Id] = std::move(Info);
3701template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3703CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::formatContextReportSuffix(
3704 const ContextNode *Node, uint32_t Id)
const {
3705 auto InfoIt = PreCloningContextInfoMap.find(Id);
3706 if (InfoIt == PreCloningContextInfoMap.end())
3708 const PreCloningContextInfo &
Info = InfoIt->second;
3715 const ContextNode *OrigAlloc =
Node->getOrigNode();
3716 const FuncTy *AllocFunc = getCallingFunc(OrigAlloc);
3717 unsigned AllocCloneNo =
Node->Call.cloneNo();
3718 std::string AllocFuncStr = getFuncName(AllocFunc, AllocCloneNo);
3719 if (isFuncDead(AllocFunc)) {
3720 AllocFuncStr +=
" (dead)";
3721 }
else if (!PreCloningAllocHasMatchedCaller.contains(OrigAlloc) &&
3722 Info.Chain.size() > 1) {
3726 AllocFuncStr += AllocFunc && !FunctionsWithCallers.
contains(AllocFunc)
3727 ?
" (no references in IR/summary)"
3728 :
" (no matched callers)";
3734 unsigned TotalFrames =
Info.Chain.size() > 0 ?
Info.Chain.size() - 1 : 0;
3735 unsigned Matched =
Info.MaxMatchedFrame;
3736 std::string StatusStr;
3737 if (TotalFrames == 0) {
3738 StatusStr =
"inlined into leaf";
3739 }
else if (Matched < TotalFrames) {
3744 if (
Info.StoppedAtRecursive)
3745 StatusStr =
"unmatched recursive callsite";
3746 else if (
Info.StoppedAtMismatchedCallee)
3747 StatusStr =
"unmatched callsite (mismatched callee in " +
3748 getFuncName(
Info.UnmatchedCallingFunc, 0) +
")";
3750 StatusStr =
"unmatched callsite";
3751 StatusStr +=
" at frame " + std::to_string(Matched + 1) +
"/" +
3752 std::to_string(TotalFrames) +
" (stack id " +
3753 std::to_string(
Info.UnmatchedStackId) +
")";
3755 const ContextNode *OutermostMatchedNode =
Info.Chain[Matched];
3756 const FuncTy *OutermostMatchedFunc = getCallingFunc(OutermostMatchedNode);
3757 unsigned NumOutermostMatchedFuncClones =
3758 std::max<unsigned>(1, FuncToNumClones.lookup(OutermostMatchedFunc));
3759 bool HasCallersAbove =
3760 NumOutermostMatchedFuncClones > 1 ||
3761 Info.OutermostMatchedNodeHasOtherCallers ||
3762 (OutermostMatchedFunc &&
3763 FunctionsWithCallers.
contains(OutermostMatchedFunc));
3764 if (HasCallersAbove) {
3765 StatusStr =
"trimmed at frame " + std::to_string(Matched) +
" in " +
3766 getFuncName(OutermostMatchedFunc, 0);
3768 StatusStr =
"matched " + std::to_string(Matched) +
" frames to " +
3769 getFuncName(OutermostMatchedFunc, 0);
3778 std::string ReachesStr;
3780 const ContextNode *OutermostMatchedNode =
Info.Chain[Matched];
3781 const FuncTy *OutermostMatchedFunc = getCallingFunc(OutermostMatchedNode);
3782 unsigned NumOutermostMatchedFuncClones =
3783 std::max<unsigned>(1, FuncToNumClones.lookup(OutermostMatchedFunc));
3784 ReachesStr =
"; reaches ";
3789 SmallSet<unsigned, 4> ReportedAllocClones;
3790 bool FirstPath =
true;
3791 for (
unsigned OutermostMatchedFuncClone = 0;
3792 OutermostMatchedFuncClone < NumOutermostMatchedFuncClones;
3793 ++OutermostMatchedFuncClone) {
3797 std::vector<const FuncTy *> PathFuncs(Matched + 1);
3798 std::vector<unsigned> PathClones(Matched + 1);
3799 PathFuncs[0] = OutermostMatchedFunc;
3800 PathClones[0] = OutermostMatchedFuncClone;
3801 unsigned CurClone = OutermostMatchedFuncClone;
3802 for (
unsigned Step = 0; Step < Matched; ++Step) {
3803 unsigned FrameIdx = Matched - Step;
3804 const ContextNode *CallNode =
Info.Chain[FrameIdx];
3805 unsigned NextClone =
3806 OrigNodeAndCloneToCalleeClone.lookup({CallNode, CurClone});
3807 const FuncTy *CalleeFunc = getCallingFunc(
Info.Chain[FrameIdx - 1]);
3808 PathFuncs[Step + 1] = CalleeFunc;
3809 PathClones[Step + 1] = NextClone;
3810 CurClone = NextClone;
3813 if (!ReportedAllocClones.
insert(CurClone).second)
3819 const ContextNode *ReachedAlloc =
3820 OrigAllocAndCloneToNode.lookup({OrigAlloc, CurClone});
3824 std::string ReachedTypeStr;
3827 (uint8_t)getAllocationCallType(ReachedAlloc->Call));
3828 else if (CurClone == 0)
3832 ReachedTypeStr =
"None";
3838 std::string PathStr;
3839 bool SkippedPrev =
false;
3840 bool PrintFullPath =
3842 for (
unsigned S = 0; S <= Matched; ++S) {
3843 bool IsCloned = PathClones[S] > 0;
3844 bool PrevCloned = S > 0 ? (PathClones[S - 1] > 0) : IsCloned;
3845 bool NextCloned = S + 1 <= Matched ? (PathClones[S + 1] > 0) : IsCloned;
3846 bool Include = PrintFullPath || (S <= 1) || (S + 1 >= Matched) ||
3847 (IsCloned != PrevCloned) || (IsCloned != NextCloned);
3850 PathStr +=
" -> ...";
3855 SkippedPrev =
false;
3856 if (!PathStr.empty())
3858 PathStr += getFuncName(PathFuncs[S], PathClones[S]);
3860 ReachesStr += ReachedTypeStr +
" via " + PathStr;
3864 return " [alloc in " + AllocFuncStr +
"; " + StatusStr + ReachesStr +
"]";
3867template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3868void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::printTotalSizes(
3870 function_ref<
void(StringRef, StringRef,
const Twine &)> EmitRemark)
const {
3871 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
3873 if (
Node->isRemoved())
3875 if (!
Node->IsAllocation)
3877 DenseSet<uint32_t> ContextIds =
Node->getContextIds();
3878 auto AllocTypeFromCall = getAllocationCallType(
Node->Call);
3879 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
3880 std::sort(SortedIds.begin(), SortedIds.end());
3881 for (
auto Id : SortedIds) {
3882 auto TypeI = ContextIdToAllocationType.
find(Id);
3883 assert(TypeI != ContextIdToAllocationType.
end());
3885 bool ComputedSuffix =
false;
3886 auto GetSuffix = [&]() ->
const std::string & {
3887 if (!ComputedSuffix) {
3889 ? formatContextReportSuffix(Node, Id)
3891 ComputedSuffix =
true;
3895 auto CSI = ContextIdToContextSizeInfos.
find(Id);
3896 if (CSI != ContextIdToContextSizeInfos.
end()) {
3897 for (
auto &Info : CSI->second) {
3900 " full allocation context " + std::to_string(
Info.FullStackId) +
3901 " with total size " + std::to_string(
Info.TotalSize) +
" is " +
3903 if (allocTypeToUse(
Node->AllocTypes) != AllocTypeFromCall)
3905 " due to cold byte percent";
3907 Msg +=
" (internal context id " + std::to_string(Id) +
")";
3909 OS <<
Msg << GetSuffix() <<
"\n";
3919 if (allocTypeToUse(
Node->AllocTypes) != AllocTypeFromCall)
3921 " due to cold byte percent";
3923 Msg +=
" (internal context id " + std::to_string(Id) +
")";
3925 OS <<
Msg << GetSuffix() <<
"\n";
3933template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3934void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::check()
const {
3935 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
3938 for (
auto &
Edge :
Node->CallerEdges)
3943template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
3945 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
3946 using NodeRef =
const ContextNode<DerivedCCG, FuncTy, CallTy> *;
3948 using NodePtrTy = std::unique_ptr<ContextNode<DerivedCCG, FuncTy, CallTy>>;
3964 return G->NodeOwner.begin()->get();
3967 using EdgePtrTy = std::shared_ptr<ContextEdge<DerivedCCG, FuncTy, CallTy>>;
3968 static const ContextNode<DerivedCCG, FuncTy, CallTy> *
3987template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4001 using GraphType =
const CallsiteContextGraph<DerivedCCG, FuncTy, CallTy> *;
4007 std::string LabelString =
4008 (
Twine(
"OrigId: ") + (
Node->IsAllocation ?
"Alloc" :
"") +
4011 LabelString +=
"\n";
4012 if (
Node->hasCall()) {
4013 auto Func =
G->NodeToCallingFunc.find(
Node);
4014 assert(Func !=
G->NodeToCallingFunc.end());
4016 G->getLabel(Func->second,
Node->Call.call(),
Node->Call.cloneNo());
4017 for (
auto &MatchingCall :
Node->MatchingCalls) {
4018 LabelString +=
"\n";
4019 LabelString +=
G->getLabel(Func->second, MatchingCall.call(),
4020 MatchingCall.cloneNo());
4023 LabelString +=
"null call";
4024 if (
Node->Recursive)
4025 LabelString +=
" (recursive)";
4027 LabelString +=
" (external)";
4033 auto ContextIds =
Node->getContextIds();
4037 bool Highlight =
false;
4046 std::string AttributeString = (
Twine(
"tooltip=\"") + getNodeId(
Node) +
" " +
4047 getContextIds(ContextIds) +
"\"")
4051 AttributeString +=
",fontsize=\"30\"";
4053 (
Twine(
",fillcolor=\"") + getColor(
Node->AllocTypes, Highlight) +
"\"")
4055 if (
Node->CloneOf) {
4056 AttributeString +=
",color=\"blue\"";
4057 AttributeString +=
",style=\"filled,bold,dashed\"";
4059 AttributeString +=
",style=\"filled\"";
4060 return AttributeString;
4065 auto &Edge = *(ChildIter.getCurrent());
4070 bool Highlight =
false;
4079 auto Color = getColor(Edge->AllocTypes, Highlight);
4080 std::string AttributeString =
4081 (
Twine(
"tooltip=\"") + getContextIds(Edge->ContextIds) +
"\"" +
4083 Twine(
",fillcolor=\"") + Color +
"\"" +
Twine(
",color=\"") + Color +
4086 if (Edge->IsBackedge)
4087 AttributeString +=
",style=\"dotted\"";
4090 AttributeString +=
",penwidth=\"2.0\",weight=\"2\"";
4091 return AttributeString;
4097 if (
Node->isRemoved())
4110 std::string IdString =
"ContextIds:";
4111 if (ContextIds.
size() < 100) {
4112 std::vector<uint32_t> SortedIds(ContextIds.
begin(), ContextIds.
end());
4113 std::sort(SortedIds.begin(), SortedIds.end());
4114 for (
auto Id : SortedIds)
4115 IdString += (
" " +
Twine(Id)).str();
4117 IdString += (
" (" + Twine(ContextIds.
size()) +
" ids)").str();
4122 static std::string getColor(uint8_t AllocTypes,
bool Highlight) {
4128 if (AllocTypes == (uint8_t)AllocationType::NotCold)
4130 return !
DoHighlight || Highlight ?
"brown1" :
"lightpink";
4131 if (AllocTypes == (uint8_t)AllocationType::Cold)
4132 return !
DoHighlight || Highlight ?
"cyan" :
"lightskyblue";
4134 ((uint8_t)AllocationType::NotCold | (uint8_t)AllocationType::Cold))
4135 return Highlight ?
"magenta" :
"mediumorchid1";
4139 static std::string getNodeId(NodeRef Node) {
4140 std::stringstream SStream;
4141 SStream << std::hex <<
"N0x" << (
unsigned long long)Node;
4142 std::string
Result = SStream.str();
4151template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4156template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4157void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::exportToDot(
4158 std::string Label)
const {
4163template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4164typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
4165CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::moveEdgeToNewCalleeClone(
4166 const std::shared_ptr<ContextEdge> &
Edge,
4167 DenseSet<uint32_t> ContextIdsToMove) {
4169 assert(NodeToCallingFunc.count(Node));
4170 ContextNode *Clone =
4171 createNewNode(
Node->IsAllocation, NodeToCallingFunc[Node],
Node->Call);
4172 Node->addClone(Clone);
4173 Clone->MatchingCalls =
Node->MatchingCalls;
4174 moveEdgeToExistingCalleeClone(
Edge, Clone,
true,
4179template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4180void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
4181 moveEdgeToExistingCalleeClone(
const std::shared_ptr<ContextEdge> &
Edge,
4182 ContextNode *NewCallee,
bool NewClone,
4183 DenseSet<uint32_t> ContextIdsToMove) {
4186 assert(NewCallee->getOrigNode() ==
Edge->Callee->getOrigNode());
4188 bool EdgeIsRecursive =
Edge->Callee ==
Edge->Caller;
4190 ContextNode *OldCallee =
Edge->Callee;
4194 auto ExistingEdgeToNewCallee = NewCallee->findEdgeFromCaller(
Edge->Caller);
4198 if (ContextIdsToMove.
empty())
4199 ContextIdsToMove =
Edge->getContextIds();
4203 if (
Edge->getContextIds().size() == ContextIdsToMove.
size()) {
4206 NewCallee->AllocTypes |=
Edge->AllocTypes;
4208 if (ExistingEdgeToNewCallee) {
4211 ExistingEdgeToNewCallee->getContextIds().insert_range(ContextIdsToMove);
4212 ExistingEdgeToNewCallee->AllocTypes |=
Edge->AllocTypes;
4213 assert(
Edge->ContextIds == ContextIdsToMove);
4214 removeEdgeFromGraph(
Edge.get());
4217 Edge->Callee = NewCallee;
4218 NewCallee->CallerEdges.push_back(
Edge);
4220 OldCallee->eraseCallerEdge(
Edge.get());
4227 auto CallerEdgeAllocType = computeAllocType(ContextIdsToMove);
4228 if (ExistingEdgeToNewCallee) {
4231 ExistingEdgeToNewCallee->getContextIds().insert_range(ContextIdsToMove);
4232 ExistingEdgeToNewCallee->AllocTypes |= CallerEdgeAllocType;
4235 auto NewEdge = std::make_shared<ContextEdge>(
4236 NewCallee,
Edge->Caller, CallerEdgeAllocType, ContextIdsToMove);
4237 Edge->Caller->CalleeEdges.push_back(NewEdge);
4238 NewCallee->CallerEdges.push_back(NewEdge);
4242 NewCallee->AllocTypes |= CallerEdgeAllocType;
4244 Edge->AllocTypes = computeAllocType(
Edge->ContextIds);
4249 for (
auto &OldCalleeEdge : OldCallee->CalleeEdges) {
4250 ContextNode *CalleeToUse = OldCalleeEdge->Callee;
4254 if (CalleeToUse == OldCallee) {
4258 if (EdgeIsRecursive) {
4262 CalleeToUse = NewCallee;
4266 DenseSet<uint32_t> EdgeContextIdsToMove =
4268 set_subtract(OldCalleeEdge->getContextIds(), EdgeContextIdsToMove);
4269 OldCalleeEdge->AllocTypes =
4270 computeAllocType(OldCalleeEdge->getContextIds());
4277 if (
auto *NewCalleeEdge = NewCallee->findEdgeFromCallee(CalleeToUse)) {
4278 NewCalleeEdge->getContextIds().insert_range(EdgeContextIdsToMove);
4279 NewCalleeEdge->AllocTypes |= computeAllocType(EdgeContextIdsToMove);
4283 auto NewEdge = std::make_shared<ContextEdge>(
4284 CalleeToUse, NewCallee, computeAllocType(EdgeContextIdsToMove),
4285 EdgeContextIdsToMove);
4286 NewCallee->CalleeEdges.push_back(NewEdge);
4287 NewEdge->Callee->CallerEdges.push_back(NewEdge);
4291 OldCallee->AllocTypes = OldCallee->computeAllocType();
4293 assert((OldCallee->AllocTypes == (uint8_t)AllocationType::None) ==
4294 OldCallee->emptyContextIds());
4298 for (
const auto &OldCalleeEdge : OldCallee->CalleeEdges)
4301 for (
const auto &NewCalleeEdge : NewCallee->CalleeEdges)
4307template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4308void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
4309 moveCalleeEdgeToNewCaller(
const std::shared_ptr<ContextEdge> &
Edge,
4310 ContextNode *NewCaller) {
4311 auto *OldCallee =
Edge->Callee;
4312 auto *NewCallee = OldCallee;
4315 bool Recursive =
Edge->Caller ==
Edge->Callee;
4317 NewCallee = NewCaller;
4319 ContextNode *OldCaller =
Edge->Caller;
4320 OldCaller->eraseCalleeEdge(
Edge.get());
4324 auto ExistingEdgeToNewCaller = NewCaller->findEdgeFromCallee(NewCallee);
4326 if (ExistingEdgeToNewCaller) {
4329 ExistingEdgeToNewCaller->getContextIds().insert_range(
4330 Edge->getContextIds());
4331 ExistingEdgeToNewCaller->AllocTypes |=
Edge->AllocTypes;
4332 Edge->ContextIds.clear();
4333 Edge->AllocTypes = (uint8_t)AllocationType::None;
4334 OldCallee->eraseCallerEdge(
Edge.get());
4337 Edge->Caller = NewCaller;
4338 NewCaller->CalleeEdges.push_back(
Edge);
4340 assert(NewCallee == NewCaller);
4343 Edge->Callee = NewCallee;
4344 NewCallee->CallerEdges.push_back(
Edge);
4345 OldCallee->eraseCallerEdge(
Edge.get());
4351 NewCaller->AllocTypes |=
Edge->AllocTypes;
4358 bool IsNewNode = NewCaller->CallerEdges.empty();
4367 for (
auto &OldCallerEdge : OldCaller->CallerEdges) {
4368 auto OldCallerCaller = OldCallerEdge->Caller;
4372 OldCallerEdge->getContextIds(),
Edge->getContextIds());
4373 if (OldCaller == OldCallerCaller) {
4374 OldCallerCaller = NewCaller;
4380 set_subtract(OldCallerEdge->getContextIds(), EdgeContextIdsToMove);
4381 OldCallerEdge->AllocTypes =
4382 computeAllocType(OldCallerEdge->getContextIds());
4387 auto *ExistingCallerEdge = NewCaller->findEdgeFromCaller(OldCallerCaller);
4391 if (ExistingCallerEdge) {
4392 ExistingCallerEdge->getContextIds().insert_range(EdgeContextIdsToMove);
4393 ExistingCallerEdge->AllocTypes |=
4394 computeAllocType(EdgeContextIdsToMove);
4397 auto NewEdge = std::make_shared<ContextEdge>(
4398 NewCaller, OldCallerCaller, computeAllocType(EdgeContextIdsToMove),
4399 EdgeContextIdsToMove);
4400 NewCaller->CallerEdges.push_back(NewEdge);
4401 NewEdge->Caller->CalleeEdges.push_back(NewEdge);
4406 OldCaller->AllocTypes = OldCaller->computeAllocType();
4408 assert((OldCaller->AllocTypes == (uint8_t)AllocationType::None) ==
4409 OldCaller->emptyContextIds());
4413 for (
const auto &OldCallerEdge : OldCaller->CallerEdges)
4416 for (
const auto &NewCallerEdge : NewCaller->CallerEdges)
4422template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4423void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
4424 recursivelyRemoveNoneTypeCalleeEdges(
4425 ContextNode *Node, DenseSet<const ContextNode *> &Visited) {
4430 removeNoneTypeCalleeEdges(Node);
4432 for (
auto *Clone :
Node->Clones)
4433 recursivelyRemoveNoneTypeCalleeEdges(Clone, Visited);
4437 auto CallerEdges =
Node->CallerEdges;
4438 for (
auto &
Edge : CallerEdges) {
4440 if (
Edge->isRemoved()) {
4444 recursivelyRemoveNoneTypeCalleeEdges(
Edge->Caller, Visited);
4449template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4450void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::markBackedges() {
4455 DenseSet<const ContextNode *> Visited;
4456 DenseSet<const ContextNode *> CurrentStack;
4457 for (
auto &Entry : NonAllocationCallToContextNodeMap) {
4459 if (
Node->isRemoved())
4462 if (!
Node->CallerEdges.empty())
4464 markBackedges(Node, Visited, CurrentStack);
4470template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4471void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::markBackedges(
4472 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
4473 DenseSet<const ContextNode *> &CurrentStack) {
4474 auto I = Visited.
insert(Node);
4478 for (
auto &CalleeEdge :
Node->CalleeEdges) {
4479 auto *
Callee = CalleeEdge->Callee;
4480 if (Visited.
count(Callee)) {
4483 if (CurrentStack.
count(Callee))
4484 CalleeEdge->IsBackedge =
true;
4487 CurrentStack.
insert(Callee);
4488 markBackedges(Callee, Visited, CurrentStack);
4489 CurrentStack.
erase(Callee);
4493template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4494void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones() {
4495 DenseSet<const ContextNode *> Visited;
4496 for (
auto &Entry : AllocationCallToContextNodeMap) {
4498 identifyClones(
Entry.second, Visited,
Entry.second->getContextIds());
4501 for (
auto &Entry : AllocationCallToContextNodeMap)
4502 recursivelyRemoveNoneTypeCalleeEdges(
Entry.second, Visited);
4515template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
4516void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::identifyClones(
4517 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
4518 const DenseSet<uint32_t> &AllocContextIds) {
4528 if (!
Node->hasCall())
4547 auto CallerEdges =
Node->CallerEdges;
4548 for (
auto &
Edge : CallerEdges) {
4550 if (
Edge->isRemoved()) {
4556 if (
Edge->IsBackedge) {
4563 if (!Visited.
count(
Edge->Caller) && !
Edge->Caller->CloneOf) {
4564 identifyClones(
Edge->Caller, Visited, AllocContextIds);
4587 const unsigned AllocTypeCloningPriority[] = { 3, 4,
4591 [&](
const std::shared_ptr<ContextEdge> &
A,
4592 const std::shared_ptr<ContextEdge> &
B) {
4595 if (A->ContextIds.empty())
4601 if (B->ContextIds.empty())
4604 if (A->AllocTypes == B->AllocTypes)
4607 return A->Caller->NodeId < B->Caller->NodeId;
4608 return AllocTypeCloningPriority[A->AllocTypes] <
4609 AllocTypeCloningPriority[B->AllocTypes];
4612 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
4614 DenseSet<uint32_t> RecursiveContextIds;
4619 DenseSet<uint32_t> AllCallerContextIds;
4620 for (
auto &CE :
Node->CallerEdges) {
4623 AllCallerContextIds.
reserve(
CE->getContextIds().size());
4624 for (
auto Id :
CE->getContextIds())
4625 if (!AllCallerContextIds.
insert(Id).second)
4626 RecursiveContextIds.
insert(Id);
4636 auto CallerEdges =
Node->CallerEdges;
4637 for (
auto &CallerEdge : CallerEdges) {
4639 if (CallerEdge->isRemoved()) {
4643 assert(CallerEdge->Callee == Node);
4652 if (!CallerEdge->Caller->hasCall())
4657 auto CallerEdgeContextsForAlloc =
4659 if (!RecursiveContextIds.
empty())
4660 CallerEdgeContextsForAlloc =
4662 if (CallerEdgeContextsForAlloc.empty())
4665 auto CallerAllocTypeForAlloc = computeAllocType(CallerEdgeContextsForAlloc);
4669 std::vector<uint8_t> CalleeEdgeAllocTypesForCallerEdge;
4670 CalleeEdgeAllocTypesForCallerEdge.reserve(
Node->CalleeEdges.size());
4671 for (
auto &CalleeEdge :
Node->CalleeEdges)
4672 CalleeEdgeAllocTypesForCallerEdge.push_back(intersectAllocTypes(
4673 CalleeEdge->getContextIds(), CallerEdgeContextsForAlloc));
4689 assert(CallerEdge->AllocTypes != (uint8_t)AllocationType::None);
4690 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
4691 if (!CallerEdge->IsBackedge &&
4692 allocTypeToUse(CallerAllocTypeForAlloc) ==
4693 allocTypeToUse(
Node->AllocTypes) &&
4694 allocTypesMatch<DerivedCCG, FuncTy, CallTy>(
4695 CalleeEdgeAllocTypesForCallerEdge,
Node->CalleeEdges)) {
4699 if (CallerEdge->IsBackedge) {
4703 DeferredBackedges++;
4716 if (CallerEdge->IsBackedge && !CallerEdge->Caller->CloneOf &&
4717 !Visited.
count(CallerEdge->Caller)) {
4718 const auto OrigIdCount = CallerEdge->getContextIds().size();
4721 identifyClones(CallerEdge->Caller, Visited, CallerEdgeContextsForAlloc);
4722 removeNoneTypeCalleeEdges(CallerEdge->Caller);
4726 bool UpdatedEdge =
false;
4727 if (OrigIdCount > CallerEdge->getContextIds().size()) {
4728 for (
auto E :
Node->CallerEdges) {
4730 if (
E->Caller->CloneOf != CallerEdge->Caller)
4734 auto CallerEdgeContextsForAllocNew =
4736 if (CallerEdgeContextsForAllocNew.empty())
4746 CallerEdgeContextsForAlloc.swap(CallerEdgeContextsForAllocNew);
4756 if (CallerEdge->isRemoved())
4766 CallerEdgeContextsForAlloc, CallerEdge->getContextIds());
4767 if (CallerEdgeContextsForAlloc.empty())
4772 CallerAllocTypeForAlloc = computeAllocType(CallerEdgeContextsForAlloc);
4773 CalleeEdgeAllocTypesForCallerEdge.clear();
4774 for (
auto &CalleeEdge :
Node->CalleeEdges) {
4775 CalleeEdgeAllocTypesForCallerEdge.push_back(intersectAllocTypes(
4776 CalleeEdge->getContextIds(), CallerEdgeContextsForAlloc));
4782 ContextNode *Clone =
nullptr;
4783 for (
auto *CurClone :
Node->Clones) {
4784 if (allocTypeToUse(CurClone->AllocTypes) !=
4785 allocTypeToUse(CallerAllocTypeForAlloc))
4792 assert(!BothSingleAlloc ||
4793 CurClone->AllocTypes == CallerAllocTypeForAlloc);
4799 if (BothSingleAlloc || allocTypesMatchClone<DerivedCCG, FuncTy, CallTy>(
4800 CalleeEdgeAllocTypesForCallerEdge, CurClone)) {
4808 moveEdgeToExistingCalleeClone(CallerEdge, Clone,
false,
4809 CallerEdgeContextsForAlloc);
4811 Clone = moveEdgeToNewCalleeClone(CallerEdge, CallerEdgeContextsForAlloc);
4814 assert(Clone->AllocTypes != (uint8_t)AllocationType::None);
4821 assert(
Node->AllocTypes != (uint8_t)AllocationType::None);
4827void ModuleCallsiteContextGraph::updateAllocationCall(
4832 "memprof", AllocTypeString);
4835 .emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofAttribute",
Call.call())
4836 <<
ore::NV(
"AllocationCall",
Call.call()) <<
" in clone "
4838 <<
" marked with memprof allocation attribute "
4839 <<
ore::NV(
"Attribute", AllocTypeString));
4842void IndexCallsiteContextGraph::updateAllocationCall(CallInfo &
Call,
4846 assert(AI->Versions.size() >
Call.cloneNo());
4851ModuleCallsiteContextGraph::getAllocationCallType(
const CallInfo &
Call)
const {
4853 if (!CB->getAttributes().hasFnAttr(
"memprof"))
4854 return AllocationType::None;
4855 return CB->getAttributes().getFnAttr(
"memprof").getValueAsString() ==
"cold"
4856 ? AllocationType::Cold
4857 : AllocationType::NotCold;
4861IndexCallsiteContextGraph::getAllocationCallType(
const CallInfo &
Call)
const {
4863 assert(AI->Versions.size() >
Call.cloneNo());
4867void ModuleCallsiteContextGraph::updateCall(CallInfo &CallerCall,
4868 FuncInfo CalleeFunc) {
4869 auto *CurF = getCalleeFunc(CallerCall.call());
4870 auto NewCalleeCloneNo = CalleeFunc.cloneNo();
4877 if (CurCalleeCloneNo != NewCalleeCloneNo) {
4879 << CurCalleeCloneNo <<
" now " << NewCalleeCloneNo
4881 MismatchedCloneAssignments++;
4884 if (NewCalleeCloneNo > 0)
4885 cast<CallBase>(CallerCall.call())->setCalledFunction(CalleeFunc.func());
4886 OREGetter(CallerCall.call()->getFunction())
4887 .emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofCall", CallerCall.call())
4888 <<
ore::NV(
"Call", CallerCall.call()) <<
" in clone "
4889 <<
ore::NV(
"Caller", CallerCall.call()->getFunction())
4890 <<
" assigned to call function clone "
4891 <<
ore::NV(
"Callee", CalleeFunc.func()));
4894void IndexCallsiteContextGraph::updateCall(CallInfo &CallerCall,
4895 FuncInfo CalleeFunc) {
4898 "Caller cannot be an allocation which should not have profiled calls");
4899 assert(CI->Clones.size() > CallerCall.cloneNo());
4900 auto NewCalleeCloneNo = CalleeFunc.cloneNo();
4901 auto &CurCalleeCloneNo = CI->Clones[CallerCall.cloneNo()];
4906 if (CurCalleeCloneNo != 0 && CurCalleeCloneNo != NewCalleeCloneNo) {
4908 << CurCalleeCloneNo <<
" now " << NewCalleeCloneNo
4910 MismatchedCloneAssignments++;
4912 CurCalleeCloneNo = NewCalleeCloneNo;
4924 SP->replaceLinkageName(MDName);
4928 TempDISubprogram NewDecl = Decl->
clone();
4929 NewDecl->replaceLinkageName(MDName);
4933CallsiteContextGraph<ModuleCallsiteContextGraph,
Function,
4935ModuleCallsiteContextGraph::cloneFunctionForCallsite(
4936 FuncInfo &Func, CallInfo &
Call, DenseMap<CallInfo, CallInfo> &CallMap,
4937 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
4942 assert(!
Func.func()->getParent()->getFunction(Name));
4943 NewFunc->setName(Name);
4945 for (
auto &Inst : CallsWithMetadataInFunc) {
4947 assert(Inst.cloneNo() == 0);
4950 OREGetter(
Func.func())
4951 .emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofClone",
Func.func())
4952 <<
"created clone " <<
ore::NV(
"NewFunction", NewFunc));
4953 return {NewFunc, CloneNo};
4956CallsiteContextGraph<IndexCallsiteContextGraph, FunctionSummary,
4957 IndexCall>::FuncInfo
4958IndexCallsiteContextGraph::cloneFunctionForCallsite(
4959 FuncInfo &Func, CallInfo &
Call, DenseMap<CallInfo, CallInfo> &CallMap,
4960 std::vector<CallInfo> &CallsWithMetadataInFunc,
unsigned CloneNo) {
4974 for (
auto &Inst : CallsWithMetadataInFunc) {
4976 assert(Inst.cloneNo() == 0);
4978 assert(AI->Versions.size() == CloneNo);
4981 AI->Versions.push_back(0);
4984 assert(CI && CI->Clones.size() == CloneNo);
4987 CI->Clones.push_back(0);
4989 CallMap[Inst] = {Inst.call(), CloneNo};
4991 return {
Func.func(), CloneNo};
5008template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5009void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::mergeClones() {
5015 DenseMap<uint32_t, ContextNode *> ContextIdToAllocationNode;
5016 for (
auto &Entry : AllocationCallToContextNodeMap) {
5018 for (
auto Id :
Node->getContextIds())
5019 ContextIdToAllocationNode[
Id] =
Node->getOrigNode();
5020 for (
auto *Clone :
Node->Clones) {
5021 for (
auto Id : Clone->getContextIds())
5022 ContextIdToAllocationNode[
Id] = Clone->getOrigNode();
5029 DenseSet<const ContextNode *> Visited;
5030 for (
auto &Entry : AllocationCallToContextNodeMap) {
5033 mergeClones(Node, Visited, ContextIdToAllocationNode);
5039 auto Clones =
Node->Clones;
5040 for (
auto *Clone : Clones)
5041 mergeClones(Clone, Visited, ContextIdToAllocationNode);
5045 dbgs() <<
"CCG after merging:\n";
5049 exportToDot(
"aftermerge");
5057template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5058void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::mergeClones(
5059 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
5060 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode) {
5070 bool FoundUnvisited =
true;
5072 while (FoundUnvisited) {
5074 FoundUnvisited =
false;
5077 auto CallerEdges =
Node->CallerEdges;
5078 for (
auto CallerEdge : CallerEdges) {
5080 if (CallerEdge->Callee != Node)
5085 FoundUnvisited =
true;
5086 mergeClones(CallerEdge->Caller, Visited, ContextIdToAllocationNode);
5090 TotalMergeInvokes++;
5091 TotalMergeIters += Iters;
5092 if (Iters > MaxMergeIters)
5093 MaxMergeIters = Iters;
5096 mergeNodeCalleeClones(Node, Visited, ContextIdToAllocationNode);
5099template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5100void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::mergeNodeCalleeClones(
5101 ContextNode *Node, DenseSet<const ContextNode *> &Visited,
5102 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode) {
5104 if (
Node->emptyContextIds())
5109 MapVector<ContextNode *, std::vector<std::shared_ptr<ContextEdge>>>
5110 OrigNodeToCloneEdges;
5111 for (
const auto &
E :
Node->CalleeEdges) {
5116 OrigNodeToCloneEdges[
Base].push_back(
E);
5122 auto CalleeCallerEdgeLessThan = [](
const std::shared_ptr<ContextEdge> &
A,
5123 const std::shared_ptr<ContextEdge> &
B) {
5124 if (
A->Callee->CallerEdges.size() !=
B->Callee->CallerEdges.size())
5125 return A->Callee->CallerEdges.size() <
B->Callee->CallerEdges.size();
5126 if (
A->Callee->CloneOf && !
B->Callee->CloneOf)
5128 else if (!
A->Callee->CloneOf &&
B->Callee->CloneOf)
5131 return A->Callee->NodeId <
B->Callee->NodeId;
5136 for (
auto Entry : OrigNodeToCloneEdges) {
5139 auto &CalleeEdges =
Entry.second;
5140 auto NumCalleeClones = CalleeEdges.size();
5142 if (NumCalleeClones == 1)
5153 DenseSet<ContextNode *> OtherCallersToShareMerge;
5154 findOtherCallersToShareMerge(Node, CalleeEdges, ContextIdToAllocationNode,
5155 OtherCallersToShareMerge);
5160 ContextNode *MergeNode =
nullptr;
5161 DenseMap<ContextNode *, unsigned> CallerToMoveCount;
5162 for (
auto CalleeEdge : CalleeEdges) {
5163 auto *OrigCallee = CalleeEdge->Callee;
5169 if (CalleeEdge->Callee->CallerEdges.size() == 1) {
5170 MergeNode = OrigCallee;
5171 NonNewMergedNodes++;
5178 if (!OtherCallersToShareMerge.
empty()) {
5179 bool MoveAllCallerEdges =
true;
5180 for (
auto CalleeCallerE : OrigCallee->CallerEdges) {
5181 if (CalleeCallerE == CalleeEdge)
5183 if (!OtherCallersToShareMerge.
contains(CalleeCallerE->Caller)) {
5184 MoveAllCallerEdges =
false;
5190 if (MoveAllCallerEdges) {
5191 MergeNode = OrigCallee;
5192 NonNewMergedNodes++;
5199 assert(MergeNode != OrigCallee);
5200 moveEdgeToExistingCalleeClone(CalleeEdge, MergeNode,
5203 MergeNode = moveEdgeToNewCalleeClone(CalleeEdge);
5208 if (!OtherCallersToShareMerge.
empty()) {
5212 auto OrigCalleeCallerEdges = OrigCallee->CallerEdges;
5213 for (
auto &CalleeCallerE : OrigCalleeCallerEdges) {
5214 if (CalleeCallerE == CalleeEdge)
5216 if (!OtherCallersToShareMerge.
contains(CalleeCallerE->Caller))
5218 CallerToMoveCount[CalleeCallerE->Caller]++;
5219 moveEdgeToExistingCalleeClone(CalleeCallerE, MergeNode,
5223 removeNoneTypeCalleeEdges(OrigCallee);
5224 removeNoneTypeCalleeEdges(MergeNode);
5242template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5243void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::
5244 findOtherCallersToShareMerge(
5246 std::vector<std::shared_ptr<ContextEdge>> &CalleeEdges,
5247 DenseMap<uint32_t, ContextNode *> &ContextIdToAllocationNode,
5248 DenseSet<ContextNode *> &OtherCallersToShareMerge) {
5249 auto NumCalleeClones = CalleeEdges.size();
5252 DenseMap<ContextNode *, unsigned> OtherCallersToSharedCalleeEdgeCount;
5255 unsigned PossibleOtherCallerNodes = 0;
5259 if (CalleeEdges[0]->
Callee->CallerEdges.size() < 2)
5265 DenseMap<ContextEdge *, DenseSet<ContextNode *>> CalleeEdgeToAllocNodes;
5266 for (
auto CalleeEdge : CalleeEdges) {
5267 assert(CalleeEdge->Callee->CallerEdges.size() > 1);
5270 for (
auto CalleeCallerEdges : CalleeEdge->Callee->CallerEdges) {
5271 if (CalleeCallerEdges->Caller == Node) {
5272 assert(CalleeCallerEdges == CalleeEdge);
5275 OtherCallersToSharedCalleeEdgeCount[CalleeCallerEdges->Caller]++;
5278 if (OtherCallersToSharedCalleeEdgeCount[CalleeCallerEdges->Caller] ==
5280 PossibleOtherCallerNodes++;
5284 for (
auto Id : CalleeEdge->getContextIds()) {
5285 auto *
Alloc = ContextIdToAllocationNode.
lookup(Id);
5289 MissingAllocForContextId++;
5292 CalleeEdgeToAllocNodes[CalleeEdge.get()].
insert(
Alloc);
5299 for (
auto CalleeEdge : CalleeEdges) {
5300 assert(CalleeEdge->Callee->CallerEdges.size() > 1);
5302 if (!PossibleOtherCallerNodes)
5304 auto &CurCalleeAllocNodes = CalleeEdgeToAllocNodes[CalleeEdge.get()];
5306 for (
auto &CalleeCallerE : CalleeEdge->Callee->CallerEdges) {
5308 if (CalleeCallerE == CalleeEdge)
5312 if (OtherCallersToSharedCalleeEdgeCount[CalleeCallerE->Caller] !=
5317 for (
auto Id : CalleeCallerE->getContextIds()) {
5318 auto *
Alloc = ContextIdToAllocationNode.
lookup(Id);
5323 if (!CurCalleeAllocNodes.contains(
Alloc)) {
5324 OtherCallersToSharedCalleeEdgeCount[CalleeCallerE->Caller] = 0;
5325 PossibleOtherCallerNodes--;
5332 if (!PossibleOtherCallerNodes)
5337 for (
auto &[OtherCaller,
Count] : OtherCallersToSharedCalleeEdgeCount) {
5338 if (
Count != NumCalleeClones)
5340 OtherCallersToShareMerge.
insert(OtherCaller);
5344template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5345const typename CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::ContextNode *
5346CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::resolveImplicitSource(
5347 const ContextNode *Node,
const ImplicitSource &Src) {
5348 if (!Src.Source->emptyContextIds())
5354 if (
Node->hasContextId(Src.ContextId))
5356 for (
const ContextNode *
C :
Node->Clones)
5357 if (
C->hasContextId(Src.ContextId))
5362 assert(
false &&
"trimmed context id on no clone of its callsite node");
5404template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5405void CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::assignImplicitCallers(
5406 ContextNode *Node,
const DenseSet<uint32_t> &TrimmedContextIds,
5407 DenseMap<ContextNode *, FuncInfo> &CallsiteToCalleeFuncCloneMap,
5408 const std::map<FuncInfo, ContextNode *> &FuncCloneToCurNodeCloneMap,
5409 ImplicitSourceMap &ImplicitSources) {
5410 auto HasEdgeToNodeFamily = [&](
const ContextNode *
N) {
5412 [&](
const std::shared_ptr<ContextEdge> &
E) {
5413 return E->Callee->getOrigNode() == Node;
5447 auto ImpliesContextIds =
5448 [&](ContextNode *
K, ContextNode *
Y,
const DenseSet<uint32_t> &Ids,
5449 DenseMap<std::pair<ContextNode *, ContextNode *>, DenseSet<uint32_t>>
5451 auto &&ImpliesContextIds) ->
bool {
5452 assert(
K->getOrigNode() ==
Y->getOrigNode());
5453 DenseSet<uint32_t> &VisitedIds = Visited[{
K,
Y}];
5454 DenseSet<uint32_t> NewIds;
5456 if (VisitedIds.
insert(Id).second)
5464 DenseSet<uint32_t> IdsOnCallerEdges;
5465 for (
auto &YEdge :
Y->CallerEdges) {
5466 DenseSet<uint32_t> IdsFromZ =
5468 if (IdsFromZ.
empty())
5471 IdsFromCallers.
push_back({YEdge->Caller, std::move(IdsFromZ)});
5475 if (IdsOnCallerEdges.
size() < NewIds.
size())
5479 for (
auto &[Z, IdsFromZ] : IdsFromCallers) {
5480 for (
auto &KEdge :
K->CallerEdges) {
5481 ContextNode *
C = KEdge->Caller;
5482 if (
C == Z ||
C->getOrigNode() !=
Z->getOrigNode())
5486 DenseSet<uint32_t> IdsNotOnC;
5487 for (
auto Id : IdsFromZ)
5488 if (!
C->hasContextId(Id))
5490 if (!IdsNotOnC.
empty() &&
5491 ImpliesContextIds(
C, Z, IdsNotOnC, Visited, ImpliesContextIds))
5500 auto SameVersion = [&](
const ContextNode *
A,
const ContextNode *
B) {
5503 if (
Node->IsAllocation)
5504 return allocTypeToUse(
A->AllocTypes) == allocTypeToUse(
B->AllocTypes);
5505 auto AIt = CallsiteToCalleeFuncCloneMap.
find(
A);
5506 auto BIt = CallsiteToCalleeFuncCloneMap.
find(
B);
5507 return AIt != CallsiteToCalleeFuncCloneMap.
end() &&
5508 BIt != CallsiteToCalleeFuncCloneMap.
end() &&
5509 AIt->second == BIt->second;
5513 DenseSet<const ContextNode *> ImplicitCallers;
5518 auto ProcessCaller = [&](
const std::shared_ptr<ContextEdge> &
Edge) {
5519 ContextNode *
Y =
Edge->Caller;
5520 ContextNode *Orig =
Y->getOrigNode();
5521 if (!
Y->hasCall() || Orig->Clones.empty())
5523 DenseSet<uint32_t> TrimmedIds =
5525 if (TrimmedIds.
empty())
5527 auto YIt = CallsiteToCalleeFuncCloneMap.
find(
Y);
5528 if (YIt == CallsiteToCalleeFuncCloneMap.
end())
5531 const FuncInfo YFuncClone = YIt->second;
5534 auto RequiredIt = FuncCloneToCurNodeCloneMap.find(YFuncClone);
5535 assert(RequiredIt != FuncCloneToCurNodeCloneMap.end());
5536 const ContextNode *
Required = RequiredIt->second;
5544 auto RecordImplicitSource = [&](
const FuncInfo &
F,
const ContextNode *Src) {
5547 if (
F.cloneNo() != 0)
5548 ImplicitSources.try_emplace({
Node,
F.cloneNo()},
5549 ImplicitSource{Src, *TrimmedIds.
begin()});
5555 if (K ==
Y || !
K->hasCall() ||
K->emptyContextIds() ||
5556 HasEdgeToNodeFamily(K) || ImplicitCallers.
contains(K))
5558 DenseMap<std::pair<ContextNode *, ContextNode *>, DenseSet<uint32_t>>
5560 if (!ImpliesContextIds(K,
Y, TrimmedIds, Visited, ImpliesContextIds))
5563 ImplicitCallers.
insert(K);
5564 auto KIt = CallsiteToCalleeFuncCloneMap.
find(K);
5565 if (KIt == CallsiteToCalleeFuncCloneMap.
end()) {
5568 CallsiteToCalleeFuncCloneMap[
K] = YFuncClone;
5569 RecordImplicitSource(YFuncClone, Required);
5570 NumImplicitCallersAssigned++;
5573 const FuncInfo KFuncClone = KIt->second;
5574 if (KFuncClone == YFuncClone) {
5576 RecordImplicitSource(YFuncClone, Required);
5579 unsigned KCloneNo = KFuncClone.cloneNo();
5580 auto KNodeCloneIt = FuncCloneToCurNodeCloneMap.find(KFuncClone);
5581 if (KNodeCloneIt == FuncCloneToCurNodeCloneMap.end()) {
5583 if (KCloneNo == 0) {
5587 if (
Node->IsAllocation) {
5588 if (allocTypeToUse(
Required->AllocTypes) == AllocationType::NotCold)
5590 }
else if (
auto It = CallsiteToCalleeFuncCloneMap.
find(Required);
5591 It != CallsiteToCalleeFuncCloneMap.
end() &&
5592 It->second.cloneNo() == 0)
5598 auto [It,
Inserted] = ImplicitSources.try_emplace(
5601 NumImplicitCallersSourced++;
5602 if (SameVersion(It->second.Source, Required))
5605 }
else if (SameVersion(KNodeCloneIt->second, Required)) {
5608 RecordImplicitSource(KFuncClone, KNodeCloneIt->second);
5612 NumImplicitCallersUnresolved++;
5618 for (
auto &
Edge :
Node->CallerEdges)
5619 ProcessCaller(
Edge);
5620 for (
auto *Clone :
Node->Clones)
5621 for (
auto &
Edge : Clone->CallerEdges)
5622 ProcessCaller(
Edge);
5666template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
5667bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::assignFunctions() {
5675 DenseSet<uint32_t> TrimmedContextIds;
5676 for (
auto &NodePtr : NodeOwner) {
5677 ContextNode *
N = NodePtr.get();
5678 if (
N->IsAllocation ||
N->CalleeEdges.empty() ||
5679 (
N->CallerEdges.empty() &&
N->Clones.empty() && !
N->CloneOf))
5684 DenseSet<uint32_t> CallerIds;
5685 for (
auto &
E :
N->CallerEdges)
5687 for (
auto &CalleeEdge :
N->CalleeEdges)
5688 for (
auto Id : CalleeEdge->getContextIds())
5690 TrimmedContextIds.
insert(Id);
5692 NumTrimmedContextIds += TrimmedContextIds.
size();
5696 DenseMap<ContextNode *, FuncInfo> CallsiteToCalleeFuncCloneMap;
5700 auto RecordCalleeFuncOfCallsite = [&](ContextNode *
Caller,
5701 const FuncInfo &CalleeFunc) {
5703 CallsiteToCalleeFuncCloneMap[
Caller] = CalleeFunc;
5707 struct FuncCloneInfo {
5712 DenseMap<CallInfo, CallInfo> CallMap;
5748 struct UnassignedCallCloneInfo {
5750 const ContextNode *
Source =
nullptr;
5752 DenseMap<const ContextNode *, std::map<unsigned, UnassignedCallCloneInfo>>
5753 UnassignedCallClones;
5757 for (
auto &[Func, CallsWithMetadata] : FuncToCallsWithMetadata) {
5758 FuncInfo OrigFunc(Func);
5763 std::vector<FuncCloneInfo> FuncCloneInfos;
5770 std::vector<unsigned> FuncCloneParent;
5773 ImplicitSourceMap ImplicitSources;
5780 struct OrigCallsInfo {
5784 DenseMap<const ContextNode *, OrigCallsInfo> OrigNodeToOrigCalls;
5785 for (
auto &
Call : CallsWithMetadata) {
5786 ContextNode *
Node = getNodeForInst(
Call);
5788 OrigNodeToOrigCalls[
Node] = {
Call,
Node->MatchingCalls};
5790 for (
auto &
Call : CallsWithMetadata) {
5791 ContextNode *
Node = getNodeForInst(
Call);
5795 if (!Node ||
Node->Clones.empty())
5798 "Not having a call should have prevented cloning");
5802 std::map<FuncInfo, ContextNode *> FuncCloneToCurNodeCloneMap;
5806 auto AssignCallsiteCloneToFuncClone = [&](
const FuncInfo &FuncClone,
5808 ContextNode *CallsiteClone,
5811 FuncCloneToCurNodeCloneMap[FuncClone] = CallsiteClone;
5813 assert(FuncCloneInfos.size() > FuncClone.cloneNo());
5814 DenseMap<CallInfo, CallInfo> &CallMap =
5815 FuncCloneInfos[FuncClone.cloneNo()].CallMap;
5816 CallInfo CallClone(
Call);
5817 if (
auto It = CallMap.
find(
Call); It != CallMap.
end())
5818 CallClone = It->second;
5819 CallsiteClone->setCall(CallClone);
5825 CallsiteClone->MatchingCalls.clear();
5826 for (
const CallInfo &OrigMatchingCall :
5827 OrigNodeToOrigCalls[Node].MatchingCalls) {
5828 CallInfo CallClone(OrigMatchingCall);
5829 if (
auto It = CallMap.
find(OrigMatchingCall); It != CallMap.
end())
5830 CallClone = It->second;
5831 CallsiteClone->MatchingCalls.push_back(CallClone);
5839 auto MoveEdgeToNewCalleeCloneAndSetUp =
5840 [&](
const std::shared_ptr<ContextEdge> &
Edge) {
5841 ContextNode *OrigCallee =
Edge->Callee;
5842 ContextNode *NewClone = moveEdgeToNewCalleeClone(
Edge);
5843 removeNoneTypeCalleeEdges(NewClone);
5844 assert(NewClone->AllocTypes != (uint8_t)AllocationType::None);
5848 if (CallsiteToCalleeFuncCloneMap.
count(OrigCallee))
5849 RecordCalleeFuncOfCallsite(
5850 NewClone, CallsiteToCalleeFuncCloneMap[OrigCallee]);
5857 std::deque<ContextNode *> ClonesWorklist;
5859 if (!
Node->emptyContextIds())
5860 ClonesWorklist.push_back(Node);
5866 unsigned NodeCloneCount = 0;
5867 while (!ClonesWorklist.empty()) {
5868 ContextNode *Clone = ClonesWorklist.front();
5869 ClonesWorklist.pop_front();
5878 if (FuncCloneInfos.size() < NodeCloneCount) {
5880 if (NodeCloneCount == 1) {
5885 Clone->CallerEdges, [&](
const std::shared_ptr<ContextEdge> &
E) {
5886 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
5890 FuncCloneInfos.push_back(
5891 {OrigFunc, DenseMap<CallInfo, CallInfo>()});
5892 FuncCloneParent.push_back(0);
5893 AssignCallsiteCloneToFuncClone(
5894 OrigFunc,
Call, Clone,
5895 AllocationCallToContextNodeMap.count(
Call));
5896 for (
auto &CE : Clone->CallerEdges) {
5898 if (!
CE->Caller->hasCall())
5900 RecordCalleeFuncOfCallsite(
CE->Caller, OrigFunc);
5910 FuncInfo PreviousAssignedFuncClone;
5912 Clone->CallerEdges, [&](
const std::shared_ptr<ContextEdge> &
E) {
5913 return CallsiteToCalleeFuncCloneMap.count(E->Caller);
5915 bool CallerAssignedToCloneOfFunc =
false;
5916 if (EI != Clone->CallerEdges.end()) {
5917 const std::shared_ptr<ContextEdge> &
Edge = *EI;
5918 PreviousAssignedFuncClone =
5919 CallsiteToCalleeFuncCloneMap[
Edge->Caller];
5920 CallerAssignedToCloneOfFunc =
true;
5925 DenseMap<CallInfo, CallInfo> NewCallMap;
5926 unsigned CloneNo = FuncCloneInfos.size();
5927 assert(CloneNo > 0 &&
"Clone 0 is the original function, which "
5928 "should already exist in the map");
5929 FuncInfo NewFuncClone = cloneFunctionForCallsite(
5930 OrigFunc,
Call, NewCallMap, CallsWithMetadata, CloneNo);
5931 FuncCloneInfos.push_back({NewFuncClone, std::move(NewCallMap)});
5934 FuncCloneParent.push_back(CallerAssignedToCloneOfFunc
5935 ? PreviousAssignedFuncClone.cloneNo()
5937 FunctionClonesAnalysis++;
5943 if (!CallerAssignedToCloneOfFunc) {
5944 AssignCallsiteCloneToFuncClone(
5945 NewFuncClone,
Call, Clone,
5946 AllocationCallToContextNodeMap.count(
Call));
5947 for (
auto &CE : Clone->CallerEdges) {
5949 if (!
CE->Caller->hasCall())
5951 RecordCalleeFuncOfCallsite(
CE->Caller, NewFuncClone);
5963 auto CallerEdges = Clone->CallerEdges;
5964 for (
auto CE : CallerEdges) {
5966 if (
CE->isRemoved()) {
5972 if (!
CE->Caller->hasCall())
5975 if (!CallsiteToCalleeFuncCloneMap.
count(
CE->Caller) ||
5979 CallsiteToCalleeFuncCloneMap[
CE->Caller] !=
5980 PreviousAssignedFuncClone)
5983 RecordCalleeFuncOfCallsite(
CE->Caller, NewFuncClone);
5996 auto CalleeEdges =
CE->Caller->CalleeEdges;
5997 for (
auto CalleeEdge : CalleeEdges) {
6000 if (CalleeEdge->isRemoved()) {
6005 ContextNode *
Callee = CalleeEdge->Callee;
6009 if (Callee == Clone || !
Callee->hasCall())
6014 if (Callee == CalleeEdge->Caller)
6016 ContextNode *NewClone =
6017 MoveEdgeToNewCalleeCloneAndSetUp(CalleeEdge);
6020 removeNoneTypeCalleeEdges(Callee);
6033 auto &OrigCalls = OrigNodeToOrigCalls[
Callee->getOrigNode()];
6034 DenseMap<CallInfo, CallInfo> &CallMap =
6035 FuncCloneInfos[NewFuncClone.cloneNo()].CallMap;
6037 CallInfo NewCall(CallMap[OrigCalls.Call]);
6039 NewClone->setCall(NewCall);
6041 NewClone->MatchingCalls.clear();
6042 for (
auto &OrigMatchingCall : OrigCalls.MatchingCalls) {
6044 CallInfo NewCall(CallMap[OrigMatchingCall]);
6046 NewClone->MatchingCalls.push_back(NewCall);
6055 auto FindFirstAvailFuncClone = [&]() {
6060 for (
auto &CF : FuncCloneInfos) {
6061 if (!FuncCloneToCurNodeCloneMap.count(CF.FuncClone))
6062 return CF.FuncClone;
6065 "Expected an available func clone for this callsite clone");
6082 std::map<FuncInfo, ContextNode *> FuncCloneToNewCallsiteCloneMap;
6083 FuncInfo FuncCloneAssignedToCurCallsiteClone;
6087 auto CloneCallerEdges = Clone->CallerEdges;
6088 for (
auto &
Edge : CloneCallerEdges) {
6092 if (
Edge->isRemoved())
6095 if (!
Edge->Caller->hasCall())
6099 if (CallsiteToCalleeFuncCloneMap.
count(
Edge->Caller)) {
6100 FuncInfo FuncCloneCalledByCaller =
6101 CallsiteToCalleeFuncCloneMap[
Edge->Caller];
6111 if ((FuncCloneToCurNodeCloneMap.count(FuncCloneCalledByCaller) &&
6112 FuncCloneToCurNodeCloneMap[FuncCloneCalledByCaller] !=
6120 (FuncCloneAssignedToCurCallsiteClone &&
6121 FuncCloneAssignedToCurCallsiteClone !=
6122 FuncCloneCalledByCaller)) {
6137 if (FuncCloneToNewCallsiteCloneMap.count(
6138 FuncCloneCalledByCaller)) {
6139 ContextNode *NewClone =
6140 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller];
6141 moveEdgeToExistingCalleeClone(
Edge, NewClone);
6143 removeNoneTypeCalleeEdges(NewClone);
6146 ContextNode *NewClone = MoveEdgeToNewCalleeCloneAndSetUp(
Edge);
6147 FuncCloneToNewCallsiteCloneMap[FuncCloneCalledByCaller] =
6150 ClonesWorklist.push_back(NewClone);
6154 removeNoneTypeCalleeEdges(Clone);
6162 if (!FuncCloneAssignedToCurCallsiteClone) {
6163 FuncCloneAssignedToCurCallsiteClone = FuncCloneCalledByCaller;
6165 AssignCallsiteCloneToFuncClone(
6166 FuncCloneCalledByCaller,
Call, Clone,
6167 AllocationCallToContextNodeMap.count(
Call));
6171 assert(FuncCloneAssignedToCurCallsiteClone ==
6172 FuncCloneCalledByCaller);
6181 if (!FuncCloneAssignedToCurCallsiteClone) {
6182 FuncCloneAssignedToCurCallsiteClone = FindFirstAvailFuncClone();
6183 assert(FuncCloneAssignedToCurCallsiteClone);
6185 AssignCallsiteCloneToFuncClone(
6186 FuncCloneAssignedToCurCallsiteClone,
Call, Clone,
6187 AllocationCallToContextNodeMap.count(
Call));
6189 assert(FuncCloneToCurNodeCloneMap
6190 [FuncCloneAssignedToCurCallsiteClone] == Clone);
6192 RecordCalleeFuncOfCallsite(
Edge->Caller,
6193 FuncCloneAssignedToCurCallsiteClone);
6213 if (!FuncCloneAssignedToCurCallsiteClone) {
6214 FuncCloneAssignedToCurCallsiteClone = FindFirstAvailFuncClone();
6215 assert(FuncCloneAssignedToCurCallsiteClone &&
6216 "No available func clone for this callsite clone");
6217 AssignCallsiteCloneToFuncClone(
6218 FuncCloneAssignedToCurCallsiteClone,
Call, Clone,
6219 AllocationCallToContextNodeMap.contains(
Call));
6222 assignImplicitCallers(Node, TrimmedContextIds,
6223 CallsiteToCalleeFuncCloneMap,
6224 FuncCloneToCurNodeCloneMap, ImplicitSources);
6227 for (
const auto &PE :
Node->CalleeEdges)
6229 for (
const auto &CE :
Node->CallerEdges)
6231 for (
auto *Clone :
Node->Clones) {
6233 for (
const auto &PE : Clone->CalleeEdges)
6235 for (
const auto &CE : Clone->CallerEdges)
6242 FuncToNumClones[
Func] = std::max<unsigned>(1, FuncCloneInfos.size());
6243 if (FuncCloneInfos.size() < 2)
6249 for (
auto &
Call : CallsWithMetadata) {
6250 ContextNode *
Node = getNodeForInst(
Call);
6251 if (!Node || !
Node->hasCall() ||
Node->emptyContextIds())
6256 DenseMap<unsigned, const ContextNode *> FuncCloneToNodeClone;
6257 FuncCloneToNodeClone[
Node->Call.cloneNo()] =
Node;
6265 for (
auto *
C :
Node->Clones)
6266 if (!
C->emptyContextIds() ||
6267 !ImplicitSources.contains({Node, C->Call.cloneNo()}))
6268 FuncCloneToNodeClone[
C->Call.cloneNo()] =
C;
6271 if (FuncCloneToNodeClone.
size() >= FuncCloneInfos.size())
6274 for (
auto &FC : FuncCloneInfos) {
6275 unsigned I =
FC.FuncClone.cloneNo();
6278 if (
I == 0 || FuncCloneToNodeClone.
contains(
I)) {
6286 auto &
Info = UnassignedCallClones[
Node][
I];
6287 auto &CallVector =
Info.Calls;
6288 for (
unsigned P =
I;;
P = FuncCloneParent[
P]) {
6289 if (
auto It = ImplicitSources.find({Node, P});
6290 It != ImplicitSources.end()) {
6291 Info.Source = resolveImplicitSource(Node, It->second);
6294 if (
auto It = FuncCloneToNodeClone.
find(
P);
6295 It != FuncCloneToNodeClone.
end()) {
6296 Info.Source = It->second;
6302 DenseMap<CallInfo, CallInfo> &CallMap =
FC.CallMap;
6303 if (
auto It = CallMap.
find(
Call); It != CallMap.
end()) {
6304 CallInfo CallClone = It->second;
6305 CallVector.push_back(CallClone);
6309 assert(
false &&
"Expected to find call in CallMap");
6315 for (
const CallInfo &OrigMatchingCall :
6316 OrigNodeToOrigCalls[Node].MatchingCalls) {
6317 if (
auto It = CallMap.
find(OrigMatchingCall); It != CallMap.
end()) {
6318 CallInfo CallClone = It->second;
6319 CallVector.push_back(CallClone);
6323 assert(
false &&
"Expected to find call in CallMap");
6331 (uint8_t)AllocationType::Cold | (uint8_t)AllocationType::NotCold;
6333 auto UpdateCalls = [&](ContextNode *
Node,
6334 DenseSet<const ContextNode *> &Visited,
6335 auto &&UpdateCalls) {
6336 auto Inserted = Visited.insert(Node);
6340 for (
auto *Clone :
Node->Clones)
6341 UpdateCalls(Clone, Visited, UpdateCalls);
6343 for (
auto &
Edge :
Node->CallerEdges)
6344 UpdateCalls(
Edge->Caller, Visited, UpdateCalls);
6348 if (!
Node->hasCall() ||
Node->emptyContextIds())
6354 auto GetUnassignedCallClones = [&](ContextNode *
Node) {
6357 auto UnassignedIt = UnassignedCallClones.
find(Node);
6358 if (UnassignedIt == UnassignedCallClones.
end())
6360 DenseSet<unsigned> NodeCallClones;
6361 for (
auto *
C :
Node->Clones)
6362 if (!
C->emptyContextIds())
6363 NodeCallClones.
insert(
C->Call.cloneNo());
6364 for (
auto &[CloneNo, Info] : UnassignedIt->second) {
6368 if (NodeCallClones.
contains(CloneNo))
6375 if (
Node->IsAllocation) {
6376 auto GetAllocTypeToUse = [&](
const ContextNode *
Node) {
6377 auto AT = allocTypeToUse(
Node->AllocTypes);
6383 !ContextIdToContextSizeInfos.
empty()) {
6386 for (
auto Id :
Node->getContextIds()) {
6387 auto TypeI = ContextIdToAllocationType.
find(Id);
6388 assert(TypeI != ContextIdToAllocationType.
end());
6389 auto CSI = ContextIdToContextSizeInfos.
find(Id);
6390 if (CSI != ContextIdToContextSizeInfos.
end()) {
6391 for (
auto &Info : CSI->second) {
6393 if (TypeI->second == AllocationType::Cold)
6394 TotalCold +=
Info.TotalSize;
6399 AT = AllocationType::Cold;
6403 updateAllocationCall(
Node->Call, GetAllocTypeToUse(Node));
6405 OrigAllocAndCloneToNode[{
Node->getOrigNode(),
Node->Call.cloneNo()}] =
6410 for (
auto &[Source, Calls] : GetUnassignedCallClones(Node)) {
6411 auto AT = GetAllocTypeToUse(Source);
6412 for (
auto &
Call : Calls) {
6413 updateAllocationCall(
Call, AT);
6416 OrigAllocAndCloneToNode[{
Node->getOrigNode(),
Call.cloneNo()}] =
6423 auto CalleeFuncIt = CallsiteToCalleeFuncCloneMap.
find(Node);
6424 if (CalleeFuncIt != CallsiteToCalleeFuncCloneMap.
end()) {
6425 auto &CalleeFunc = CalleeFuncIt->second;
6426 updateCall(
Node->Call, CalleeFunc);
6428 OrigNodeAndCloneToCalleeClone[{
6429 Node->getOrigNode(),
Node->Call.cloneNo()}] = CalleeFunc.cloneNo();
6431 for (
auto &
Call :
Node->MatchingCalls)
6432 updateCall(
Call, CalleeFunc);
6438 for (
auto &[Source, Calls] : GetUnassignedCallClones(Node)) {
6439 auto It = CallsiteToCalleeFuncCloneMap.
find(Source);
6441 if (It == CallsiteToCalleeFuncCloneMap.
end())
6443 if (It == CallsiteToCalleeFuncCloneMap.
end())
6445 for (
auto &
Call : Calls) {
6446 updateCall(
Call, It->second);
6448 OrigNodeAndCloneToCalleeClone[{
Node->getOrigNode(),
Call.cloneNo()}] =
6449 It->second.cloneNo();
6459 DenseSet<const ContextNode *> Visited;
6460 for (
auto &Entry : AllocationCallToContextNodeMap)
6461 UpdateCalls(
Entry.second, Visited, UpdateCalls);
6483 for (
auto [Index, SN] :
enumerate(FS->callsites())) {
6488 SN.Clones.size() >
I &&
6489 "Callsite summary has fewer entries than other summaries in function");
6490 if (SN.Clones.size() <=
I || !SN.Clones[
I])
6492 AddRecord(
'c', Index, SN.Clones[
I]);
6495 for (
auto [Index, AN] :
enumerate(FS->allocs())) {
6499 assert(AN.Versions.size() >
I &&
6500 "Alloc summary has fewer entries than other summaries in function");
6501 if (AN.Versions.size() <=
I ||
6504 AddRecord(
'a', Index, AN.Versions[
I]);
6513 for (
auto &SN : FS->callsites()) {
6514 assert(SN.Clones.size() >
I && SN.Clones.size() > J &&
6515 "Callsite summary has fewer entries than other summaries in "
6517 if (SN.Clones[
I] != SN.Clones[J])
6520 for (
auto &AN : FS->allocs()) {
6521 assert(AN.Versions.size() >
I && AN.Versions.size() > J &&
6522 "Alloc summary has fewer entries than other summaries in function");
6523 if (AN.Versions[
I] != AN.Versions[J])
6539 NewGV->takeName(DeclGV);
6546 auto CloneFuncAliases = [&](
Function *NewF,
unsigned I) {
6547 if (!FuncToAliasMap.count(&
F))
6549 for (
auto *
A : FuncToAliasMap[&
F]) {
6551 auto *PrevA = M.getNamedAlias(AliasName);
6553 A->getType()->getPointerAddressSpace(),
6554 A->getLinkage(), AliasName, NewF);
6555 NewA->copyAttributesFrom(
A);
6557 TakeDeclNameAndReplace(PrevA, NewA);
6566 FunctionsClonedThinBackend++;
6583 for (
unsigned I = 1;
I < NumClones;
I++) {
6584 VMaps.
emplace_back(std::make_unique<ValueToValueMapTy>());
6590 if (
auto It = HashToFunc.
find(Hash); It != HashToFunc.
end()) {
6591 FunctionCloneDuplicatesThinBackend++;
6592 auto [Func, OrigI] = It->second;
6594 "Duplicate clone hash collision");
6595 if (Func->hasAvailableExternallyLinkage()) {
6601 auto Decl = M.getOrInsertFunction(Name, Func->getFunctionType());
6603 <<
"created clone decl " <<
ore::NV(
"Decl", Decl.getCallee()));
6606 auto *PrevF = M.getFunction(Name);
6609 TakeDeclNameAndReplace(PrevF, Alias);
6611 <<
"created clone alias " <<
ore::NV(
"Alias", Alias));
6614 CloneFuncAliases(Func,
I);
6618 HashToFunc[Hash] = {NewF,
I};
6619 FunctionClonesThinBackend++;
6622 for (
auto &BB : *NewF) {
6623 for (
auto &Inst : BB) {
6624 Inst.setMetadata(LLVMContext::MD_memprof,
nullptr);
6625 Inst.setMetadata(LLVMContext::MD_callsite,
nullptr);
6628 auto *PrevF = M.getFunction(Name);
6630 TakeDeclNameAndReplace(PrevF, NewF);
6632 NewF->setName(Name);
6635 <<
"created clone " <<
ore::NV(
"NewFunction", NewF));
6638 CloneFuncAliases(NewF,
I);
6647 const Function *CallingFunc =
nullptr) {
6666 auto SrcFileMD =
F.getMetadata(
"thinlto_src_file");
6672 if (!SrcFileMD &&
F.isDeclaration()) {
6676 SrcFileMD = CallingFunc->getMetadata(
"thinlto_src_file");
6681 assert(SrcFileMD || OrigName ==
F.getName());
6683 StringRef SrcFile = M.getSourceFileName();
6695 if (!TheFnVI && OrigName ==
F.getName() &&
F.hasLocalLinkage() &&
6696 F.getName().contains(
'.')) {
6697 OrigName =
F.getName().rsplit(
'.').first;
6706 assert(TheFnVI ||
F.isDeclaration());
6719 &OrigNameGUIDToTailCallCallsite,
6721 auto End = MapTailCallCalleeVIToCallsite.
end();
6725 auto It = MapTailCallCalleeVIToCallsite.
find(VI);
6734 auto It = MapTailCallCalleeVIToCallsite.
find(LocalVI);
6745 if (!OrigNameGUIDToTailCallCallsite) {
6748 OrigNameGUIDToTailCallCallsite.emplace();
6749 for (
const auto &[CalleeVI, Callsite] : MapTailCallCalleeVIToCallsite) {
6755 auto [It, Inserted] = OrigNameGUIDToTailCallCallsite->try_emplace(
6759 if (!Inserted && It->second != &Callsite)
6760 It->second =
nullptr;
6763 return OrigNameGUIDToTailCallCallsite->lookup(CandidateGUID);
6766bool MemProfContextDisambiguation::initializeIndirectCallPromotionInfo(
6768 ICallAnalysis = std::make_unique<ICallPromotionAnalysis>();
6769 Symtab = std::make_unique<InstrProfSymtab>();
6780 if (
Error E = Symtab->create(M,
true,
false)) {
6781 std::string SymtabFailure =
toString(std::move(
E));
6782 M.getContext().emitError(
"Failed to create symtab: " + SymtabFailure);
6795 auto MIBIter = AllocNode.
MIBs.begin();
6796 for (
auto &MDOp : MemProfMD->
operands()) {
6805 if (MIBIter->StackIdIndices.empty()) {
6809 auto StackIdIndexIter = MIBIter->StackIdIndices.begin();
6814 auto ContextIterBegin =
6818 (ContextIterBegin != StackContext.
end() && *ContextIterBegin == 0) ? 1
6820 for (
auto ContextIter = ContextIterBegin; ContextIter != StackContext.
end();
6825 if (LastStackContextId == *ContextIter)
6827 LastStackContextId = *ContextIter;
6828 assert(StackIdIndexIter != MIBIter->StackIdIndices.end());
6838bool MemProfContextDisambiguation::applyImport(
Module &M) {
6845 std::map<const Function *, SmallPtrSet<const GlobalAlias *, 1>>
6847 for (
auto &
A :
M.aliases()) {
6848 auto *Aliasee =
A.getAliaseeObject();
6850 FuncToAliasMap[
F].insert(&
A);
6853 if (!initializeIndirectCallPromotionInfo(M))
6860 OptimizationRemarkEmitter ORE(&
F);
6863 bool ClonesCreated =
false;
6864 unsigned NumClonesCreated = 0;
6865 auto CloneFuncIfNeeded = [&](
unsigned NumClones, FunctionSummary *
FS) {
6875 if (ClonesCreated) {
6876 assert(NumClonesCreated == NumClones);
6883 ClonesCreated =
true;
6884 NumClonesCreated = NumClones;
6887 auto CloneCallsite = [&](
const CallsiteInfo &StackNode, CallBase *CB,
6888 Function *CalledFunction, FunctionSummary *
FS) {
6890 CloneFuncIfNeeded(StackNode.
Clones.
size(), FS);
6902 if (CalledFunction != CB->getCalledOperand() &&
6903 (!GA || CalledFunction != GA->getAliaseeObject())) {
6904 SkippedCallsCloning++;
6910 auto CalleeOrigName = CalledFunction->getName();
6911 for (
unsigned J = 0; J < StackNode.
Clones.
size(); J++) {
6914 if (J > 0 && VMaps[J - 1]->
empty())
6918 if (!StackNode.
Clones[J])
6920 auto NewF =
M.getOrInsertFunction(
6922 CalledFunction->getFunctionType());
6936 ORE.emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofCall", CBClone)
6937 <<
ore::NV(
"Call", CBClone) <<
" in clone "
6939 <<
" assigned to call function clone "
6940 <<
ore::NV(
"Callee", NewF.getCallee()));
6954 ImportSummary->findSummaryInModule(TheFnVI,
M.getModuleIdentifier());
6958 auto SrcModuleMD =
F.getMetadata(
"thinlto_src_module");
6960 "enable-import-metadata is needed to emit thinlto_src_module");
6961 StringRef SrcModule =
6964 if (GVS->modulePath() == SrcModule) {
6965 GVSummary = GVS.get();
6990 if (
FS->allocs().empty() &&
FS->callsites().empty())
6993 auto SI =
FS->callsites().begin();
6994 auto AI =
FS->allocs().begin();
6999 DenseMap<ValueInfo, CallsiteInfo> MapTailCallCalleeVIToCallsite;
7002 for (
auto CallsiteIt =
FS->callsites().rbegin();
7003 CallsiteIt !=
FS->callsites().rend(); CallsiteIt++) {
7004 auto &Callsite = *CallsiteIt;
7008 if (!Callsite.StackIdIndices.empty())
7010 MapTailCallCalleeVIToCallsite.
insert({Callsite.Callee, Callsite});
7014 std::optional<DenseMap<uint64_t, const CallsiteInfo *>>
7015 OrigNameGUIDToTailCallCallsite;
7023 for (
auto &BB :
F) {
7024 for (
auto &
I : BB) {
7030 auto *CalledValue = CB->getCalledOperand();
7031 auto *CalledFunction = CB->getCalledFunction();
7032 if (CalledValue && !CalledFunction) {
7033 CalledValue = CalledValue->stripPointerCasts();
7040 assert(!CalledFunction &&
7041 "Expected null called function in callsite for alias");
7045 CallStack<MDNode, MDNode::op_iterator> CallsiteContext(
7046 I.getMetadata(LLVMContext::MD_callsite));
7047 auto *MemProfMD =
I.getMetadata(LLVMContext::MD_memprof);
7053 if (CB->getAttributes().hasFnAttr(
"memprof") && !MemProfMD) {
7054 CB->getAttributes().getFnAttr(
"memprof").getValueAsString() ==
"cold"
7055 ? AllocTypeColdThinBackend++
7056 : AllocTypeNotColdThinBackend++;
7057 OrigAllocsThinBackend++;
7058 AllocVersionsThinBackend++;
7059 if (!MaxAllocVersionsThinBackend)
7060 MaxAllocVersionsThinBackend = 1;
7067 auto &AllocNode = *(AI++);
7075 CloneFuncIfNeeded(AllocNode.Versions.size(), FS);
7077 OrigAllocsThinBackend++;
7078 AllocVersionsThinBackend += AllocNode.Versions.size();
7079 if (MaxAllocVersionsThinBackend < AllocNode.Versions.size())
7080 MaxAllocVersionsThinBackend = AllocNode.Versions.size();
7090 if (AllocNode.Versions.size() == 1 &&
7093 AllocationType::NotCold ||
7095 AllocationType::None);
7096 UnclonableAllocsThinBackend++;
7102 return Type == ((uint8_t)AllocationType::NotCold |
7103 (uint8_t)AllocationType::Cold);
7107 for (
unsigned J = 0; J < AllocNode.Versions.size(); J++) {
7110 if (J > 0 && VMaps[J - 1]->
empty())
7113 if (AllocNode.Versions[J] == (uint8_t)AllocationType::None)
7116 AllocTy == AllocationType::Cold ? AllocTypeColdThinBackend++
7117 : AllocTypeNotColdThinBackend++;
7132 ORE.emit(OptimizationRemark(
DEBUG_TYPE,
"MemprofAttribute", CBClone)
7133 <<
ore::NV(
"AllocationCall", CBClone) <<
" in clone "
7135 <<
" marked with memprof allocation attribute "
7136 <<
ore::NV(
"Attribute", AllocTypeString));
7138 }
else if (!CallsiteContext.empty()) {
7139 if (!CalledFunction) {
7143 assert(!CI || !CI->isInlineAsm());
7153 auto NumClones = recordICPInfo(
7155 [&](
const InstrProfValueData &Candidate) {
7156 assert(SI !=
FS->callsites().end());
7158 auto CalleeValueInfo =
7159 ImportSummary->getValueInfo(Candidate.Value);
7161 ImportSummary->getGUIDFromOriginalID(Candidate.Value);
7169 assert(!CalleeValueInfo ||
SI->Callee == CalleeValueInfo ||
7170 (
SI->Callee &&
SI->Callee.getGUID() == LocalGUID));
7179 CloneFuncIfNeeded(NumClones, FS);
7184 assert(SI !=
FS->callsites().end());
7185 auto &StackNode = *(
SI++);
7191 for (
auto StackId : CallsiteContext) {
7193 assert(ImportSummary->getStackIdAtIndex(*StackIdIndexIter) ==
7199 CloneCallsite(StackNode, CB, CalledFunction, FS);
7201 }
else if (CB->isTailCall() && CalledFunction) {
7204 ValueInfo CalleeVI =
7206 if (CalleeVI && MapTailCallCalleeVIToCallsite.
count(CalleeVI)) {
7207 auto Callsite = MapTailCallCalleeVIToCallsite.
find(CalleeVI);
7208 assert(Callsite != MapTailCallCalleeVIToCallsite.
end());
7209 CloneCallsite(Callsite->second, CB, CalledFunction, FS);
7211 }
else if (CB->isTailCall() && !CalledFunction &&
7212 !MapTailCallCalleeVIToCallsite.
empty()) {
7218 auto PrevNumICallAnalysisInfo = ICallAnalysisInfo.
size();
7219 auto NumClones = recordICPInfo(
7221 [&](
const InstrProfValueData &Candidate) {
7223 Candidate.Value, MapTailCallCalleeVIToCallsite,
7224 OrigNameGUIDToTailCallCallsite, ImportSummary, *Symtab);
7227 if (ICallAnalysisInfo.
size() > PrevNumICallAnalysisInfo)
7228 IndirectTailCallsRecordedForICPThinBackend++;
7230 CloneFuncIfNeeded(NumClones, FS);
7236 performICP(M, VMaps, ICallAnalysisInfo, ORE);
7246 for (
auto &BB :
F) {
7247 for (
auto &
I : BB) {
7250 I.setMetadata(LLVMContext::MD_memprof,
nullptr);
7251 I.setMetadata(LLVMContext::MD_callsite,
nullptr);
7259unsigned MemProfContextDisambiguation::recordICPInfo(
7261 function_ref<
const CallsiteInfo *(
const InstrProfValueData &)> GetCallsite,
7264 uint32_t NumCandidates;
7266 auto CandidateProfileData =
7267 ICallAnalysis->getPromotionCandidatesForInstruction(
7268 CB, TotalCount, NumCandidates,
7270 if (CandidateProfileData.empty())
7276 bool ICPNeeded =
false;
7277 unsigned NumClones = 0;
7279 for (
const auto &Candidate : CandidateProfileData) {
7280 const CallsiteInfo *Callsite = GetCallsite(Candidate);
7288 [](
unsigned CloneNo) { return CloneNo != 0; });
7298 ICallAnalysisInfo.
push_back({CB, CandidateProfileData.vec(), NumCandidates,
7299 TotalCount, NumClones, std::move(Callsites)});
7303void MemProfContextDisambiguation::performICP(
7306 OptimizationRemarkEmitter &ORE) {
7313 for (
auto &Info : ICallAnalysisInfo) {
7315 auto TotalCount =
Info.TotalCount;
7316 unsigned NumClones =
Info.NumClones;
7319 assert(
Info.CandidateProfileData.size() ==
Info.Callsites.size());
7320 for (
unsigned I = 0;
I <
Info.CandidateProfileData.size();
I++) {
7321 auto &Candidate =
Info.CandidateProfileData[
I];
7322 const CallsiteInfo *StackNode =
Info.Callsites[
I];
7330 Function *TargetFunction = Symtab->getFunction(Candidate.Value);
7341 if (!TargetFunction && StackNode && StackNode->
Callee &&
7344 if (TargetFunction ==
nullptr ||
7352 return OptimizationRemarkMissed(
DEBUG_TYPE,
"UnableToFindTarget", CB)
7353 <<
"Memprof cannot promote indirect call: target with md5sum "
7354 <<
ore::NV(
"target md5sum", Candidate.Value) <<
" not found";
7359 RemainingCandidates.
push_back(Candidate);
7364 const char *Reason =
nullptr;
7367 return OptimizationRemarkMissed(
DEBUG_TYPE,
"UnableToPromote", CB)
7368 <<
"Memprof cannot promote indirect call to "
7369 <<
ore::NV(
"TargetFunction", TargetFunction)
7370 <<
" with count of " <<
ore::NV(
"TotalCount", TotalCount)
7373 RemainingCandidates.
push_back(Candidate);
7382 CallBase *CBClone = CB;
7383 for (
unsigned J = 0; J < NumClones; J++) {
7386 if (J > 0 && VMaps[J - 1]->
empty())
7396 TotalCount, isSamplePGO, &ORE);
7397 auto *TargetToUse = TargetFunction;
7400 if (StackNode && StackNode->
Clones[J]) {
7419 <<
ore::NV(
"Call", CBClone) <<
" in clone "
7421 <<
" promoted and assigned to call function clone "
7422 <<
ore::NV(
"Callee", TargetToUse));
7426 TotalCount -= Candidate.Count;
7430 CallBase *CBClone = CB;
7431 for (
unsigned J = 0; J < NumClones; J++) {
7434 if (J > 0 && VMaps[J - 1]->
empty())
7440 CBClone->
setMetadata(LLVMContext::MD_prof,
nullptr);
7443 if (TotalCount != 0)
7445 IPVK_IndirectCallTarget,
Info.NumCandidates);
7450template <
typename DerivedCCG,
typename FuncTy,
typename CallTy>
7451bool CallsiteContextGraph<DerivedCCG, FuncTy, CallTy>::process(
7452 function_ref<
void(StringRef, StringRef,
const Twine &)> EmitRemark,
7453 bool AllowExtraAnalysis) {
7455 dbgs() <<
"CCG before cloning:\n";
7459 exportToDot(
"postbuild");
7468 capturePreCloningContextInfo();
7477 dbgs() <<
"CCG after cloning:\n";
7481 exportToDot(
"cloned");
7483 bool Changed = assignFunctions();
7486 dbgs() <<
"CCG after assigning function clones:\n";
7490 exportToDot(
"clonefuncassign");
7499 populateFunctionsWithCallers();
7500 printTotalSizes(
errs(), EmitRemark);
7506bool MemProfContextDisambiguation::processModule(
7508 llvm::function_ref<OptimizationRemarkEmitter &(
Function *)> OREGetter) {
7513 return applyImport(M);
7526 ModuleCallsiteContextGraph CCG(M, OREGetter);
7529 return CCG.process();
7534 : ImportSummary(Summary), isSamplePGO(isSamplePGO) {
7539 "-memprof-dot-scope=alloc requires -memprof-dot-alloc-id");
7543 "-memprof-dot-scope=context requires -memprof-dot-context-id");
7547 "-memprof-dot-scope=all can't have both -memprof-dot-alloc-id and "
7548 "-memprof-dot-context-id");
7549 if (ImportSummary) {
7559 auto ReadSummaryFile =
7561 if (!ReadSummaryFile) {
7568 if (!ImportSummaryForTestingOrErr) {
7574 ImportSummaryForTesting = std::move(*ImportSummaryForTestingOrErr);
7575 ImportSummary = ImportSummaryForTesting.get();
7584 if (!processModule(M, OREGetter))
7607 for (
auto &
I : Index) {
7608 auto VI = Index.getValueInfo(
I);
7609 for (
auto &S : VI.getSummaryList()) {
7613 !isPrevailing(VI.getGUID(), S.get()))
7616 if (!FS || FS->callsites().empty())
7618 CalleeToEdge.
clear();
7619 for (
auto &CI : FS->callsites()) {
7620 if (!CI.Callee ||
llvm::all_of(CI.Clones, [](
unsigned CloneNo) {
7621 return CloneNo == 0;
7628 NumClonedCalleeCallsites++;
7630 if (CalleeToEdge.
empty())
7631 for (
auto &[CalleeVI, Edge] : FS->mutableCalls())
7632 CalleeToEdge[CalleeVI] = &Edge;
7633 auto It = CalleeToEdge.
find(CI.Callee);
7634 if (It == CalleeToEdge.
end())
7641 if (!Edge->hasIndirectCall())
7643 NumClonedCalleeIndirectCallsites++;
7644 if (!Edge->requiresDeclImport()) {
7645 Edge->setRequiresDeclImport(
true);
7646 NumClonedCalleeEdgesMarkedRequiresDeclImport++;
7667 bool AllowExtraAnalysis =
7672 IndexCallsiteContextGraph CCG(Index, isPrevailing);
7673 Changed = CCG.process(EmitRemark, AllowExtraAnalysis);
7696 for (
auto &BB :
F) {
7697 for (
auto &
I : BB) {
7701 if (CI->hasFnAttr(
"memprof")) {
7702 CI->removeFnAttr(
"memprof");
7705 if (!CI->hasMetadata(LLVMContext::MD_callsite)) {
7706 assert(!CI->hasMetadata(LLVMContext::MD_memprof));
7712 CI->setMetadata(LLVMContext::MD_memprof,
nullptr);
7713 CI->setMetadata(LLVMContext::MD_callsite,
nullptr);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
Unify divergent function exit nodes
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
Module.h This file contains the declarations for the Module class.
Machine Check Debug Module
This file implements a map that provides insertion order iteration.
static cl::opt< unsigned > TailCallSearchDepth("memprof-tail-call-search-depth", cl::init(5), cl::Hidden, cl::desc("Max depth to recursively search for missing " "frames through tail calls."))
uint64_t ComputeHash(const FunctionSummary *FS, unsigned I)
static cl::opt< DotScope > DotGraphScope("memprof-dot-scope", cl::desc("Scope of graph to export to dot"), cl::Hidden, cl::init(DotScope::All), cl::values(clEnumValN(DotScope::All, "all", "Export full callsite graph"), clEnumValN(DotScope::Alloc, "alloc", "Export only nodes with contexts feeding given " "-memprof-dot-alloc-id"), clEnumValN(DotScope::Context, "context", "Export only nodes with given -memprof-dot-context-id")))
static cl::opt< bool > DoMergeIteration("memprof-merge-iteration", cl::init(true), cl::Hidden, cl::desc("Iteratively apply merging on a node to catch new callers"))
static const CallsiteInfo * findIndirectTailCallCallsite(uint64_t CandidateGUID, const DenseMap< ValueInfo, CallsiteInfo > &MapTailCallCalleeVIToCallsite, std::optional< DenseMap< uint64_t, const CallsiteInfo * > > &OrigNameGUIDToTailCallCallsite, const ModuleSummaryIndex *ImportSummary, InstrProfSymtab &Symtab)
static bool isMemProfClone(const Function &F)
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 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 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 ValueInfo findValueInfoForFunc(const Function &F, const Module &M, const ModuleSummaryIndex *ImportSummary, const Function *CallingFunc=nullptr)
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 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),...
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
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
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.
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.
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.
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.
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 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.
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)
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 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...