53#define DEBUG_TYPE "code-layout"
58 cl::desc(
"Enable machine block placement based on the ext-tsp model, "
59 "optimizing I-cache utilization."));
62 "ext-tsp-apply-without-profile",
63 cl::desc(
"Whether to apply ext-tsp placement for instances w/o profile"),
71 cl::desc(
"The weight of conditional forward jumps for ExtTSP value"));
75 cl::desc(
"The weight of unconditional forward jumps for ExtTSP value"));
79 cl::desc(
"The weight of conditional backward jumps for ExtTSP value"));
83 cl::desc(
"The weight of unconditional backward jumps for ExtTSP value"));
87 cl::desc(
"The weight of conditional fallthrough jumps for ExtTSP value"));
91 cl::desc(
"The weight of unconditional fallthrough jumps for ExtTSP value"));
95 cl::desc(
"The maximum distance (in bytes) of a forward jump for ExtTSP"));
99 cl::desc(
"The maximum distance (in bytes) of a backward jump for ExtTSP"));
105 cl::desc(
"The maximum size of a chain to create."));
111 cl::desc(
"The maximum size of a chain to apply splitting"));
117 cl::desc(
"The maximum size of a chain to apply splitting"));
124 cl::desc(
"The size of a line in the cache"));
128 cl::desc(
"The power exponent for the distance-based locality"));
132 cl::desc(
"The scale factor for the frequency-based locality"));
137constexpr double EPS = 1e-8;
142 if (JumpDist > JumpMaxDist)
144 double Prob = 1.0 -
static_cast<double>(JumpDist) / JumpMaxDist;
145 return Weight * Prob * Count;
151 uint64_t Count,
bool IsConditional) {
153 if (SrcAddr + SrcSize == DstAddr) {
154 return jumpExtTSPScore(0, 1, Count,
159 if (SrcAddr + SrcSize < DstAddr) {
160 const uint64_t Dist = DstAddr - (SrcAddr + SrcSize);
166 const uint64_t Dist = SrcAddr + SrcSize - DstAddr;
174enum class MergeTypeT :
int { X_Y, Y_X, X1_Y_X2, Y_X2_X1, X2_X1_Y };
179 explicit MergeGainT() =
default;
180 explicit MergeGainT(
double Score,
size_t MergeOffset, MergeTypeT MergeType)
181 : Score(Score), MergeOffset(MergeOffset), MergeType(MergeType) {}
183 double score()
const {
return Score; }
185 size_t mergeOffset()
const {
return MergeOffset; }
187 MergeTypeT mergeType()
const {
return MergeType; }
189 void setMergeType(MergeTypeT Ty) { MergeType = Ty; }
193 return (
Other.Score > EPS &&
Other.Score > Score + EPS);
197 void updateIfLessThan(
const MergeGainT &
Other) {
204 size_t MergeOffset{0};
205 MergeTypeT MergeType{MergeTypeT::X_Y};
215 NodeT(
const NodeT &) =
delete;
216 NodeT(NodeT &&) =
default;
217 NodeT &operator=(
const NodeT &) =
delete;
218 NodeT &operator=(NodeT &&) =
default;
223 bool isEntry()
const {
return Index == 0; }
240 ChainT *CurChain{
nullptr};
244 NodeT *ForcedSucc{
nullptr};
246 NodeT *ForcedPred{
nullptr};
248 std::vector<JumpT *> OutJumps;
250 std::vector<JumpT *> InJumps;
255 JumpT(
const JumpT &) =
delete;
256 JumpT(JumpT &&) =
default;
257 JumpT &operator=(
const JumpT &) =
delete;
258 JumpT &operator=(JumpT &&) =
default;
260 explicit JumpT(NodeT *Source, NodeT *
Target,
uint64_t ExecutionCount)
270 bool IsConditional{
false};
277 ChainT(
const ChainT &) =
delete;
278 ChainT(ChainT &&) =
default;
279 ChainT &operator=(
const ChainT &) =
delete;
280 ChainT &operator=(ChainT &&) =
default;
286 size_t numBlocks()
const {
return Nodes.size(); }
288 double density()
const {
return static_cast<double>(ExecutionCount) / Size; }
290 bool isEntry()
const {
return Nodes[0]->Index == 0; }
292 bool isCold()
const {
293 for (NodeT *
Node : Nodes) {
294 if (
Node->ExecutionCount > 0)
300 ChainEdge *getEdge(ChainT *
Other)
const {
301 for (
const auto &[Chain, ChainEdge] : Edges) {
308 void removeEdge(ChainT *
Other) {
309 auto It = Edges.begin();
310 while (It != Edges.end()) {
311 if (It->first ==
Other) {
320 Edges.push_back(std::make_pair(
Other, Edge));
323 void merge(ChainT *
Other, std::vector<NodeT *> MergedBlocks) {
324 Nodes = std::move(MergedBlocks);
326 ExecutionCount +=
Other->ExecutionCount;
328 Id = Nodes[0]->Index;
330 for (
size_t Idx = 0;
Idx < Nodes.size();
Idx++) {
331 Nodes[
Idx]->CurChain =
this;
332 Nodes[
Idx]->CurIndex =
Idx;
336 void mergeEdges(ChainT *
Other);
340 Nodes.shrink_to_fit();
342 Edges.shrink_to_fit();
354 std::vector<NodeT *> Nodes;
356 std::vector<std::pair<ChainT *, ChainEdge *>> Edges;
363 ChainEdge(
const ChainEdge &) =
delete;
364 ChainEdge(ChainEdge &&) =
default;
365 ChainEdge &operator=(
const ChainEdge &) =
delete;
366 ChainEdge &operator=(ChainEdge &&) =
delete;
368 explicit ChainEdge(JumpT *Jump)
369 : SrcChain(Jump->
Source->CurChain), DstChain(Jump->
Target->CurChain),
372 ChainT *srcChain()
const {
return SrcChain; }
374 ChainT *dstChain()
const {
return DstChain; }
376 bool isSelfEdge()
const {
return SrcChain == DstChain; }
378 const std::vector<JumpT *> &jumps()
const {
return Jumps; }
380 void appendJump(JumpT *Jump) { Jumps.push_back(Jump); }
382 void moveJumps(ChainEdge *
Other) {
383 Jumps.insert(Jumps.end(),
Other->Jumps.begin(),
Other->Jumps.end());
384 Other->Jumps.clear();
385 Other->Jumps.shrink_to_fit();
388 void changeEndpoint(ChainT *
From, ChainT *To) {
389 if (
From == SrcChain)
391 if (
From == DstChain)
395 bool hasCachedMergeGain(ChainT *Src, ChainT *Dst)
const {
396 return Src == SrcChain ? CacheValidForward : CacheValidBackward;
399 MergeGainT getCachedMergeGain(ChainT *Src, ChainT *Dst)
const {
400 return Src == SrcChain ? CachedGainForward : CachedGainBackward;
403 void setCachedMergeGain(ChainT *Src, ChainT *Dst, MergeGainT MergeGain) {
404 if (Src == SrcChain) {
405 CachedGainForward = MergeGain;
406 CacheValidForward =
true;
408 CachedGainBackward = MergeGain;
409 CacheValidBackward =
true;
413 void invalidateCache() {
414 CacheValidForward =
false;
415 CacheValidBackward =
false;
418 void setMergeGain(MergeGainT Gain) { CachedGain = Gain; }
420 MergeGainT getMergeGain()
const {
return CachedGain; }
422 double gain()
const {
return CachedGain.score(); }
426 ChainT *SrcChain{
nullptr};
428 ChainT *DstChain{
nullptr};
430 std::vector<JumpT *> Jumps;
432 MergeGainT CachedGain;
438 MergeGainT CachedGainForward;
439 MergeGainT CachedGainBackward;
441 bool CacheValidForward{
false};
442 bool CacheValidBackward{
false};
447 for (JumpT *Jump : OutJumps)
448 Count += Jump->ExecutionCount;
454 for (JumpT *Jump : InJumps)
455 Count += Jump->ExecutionCount;
459void ChainT::mergeEdges(ChainT *
Other) {
461 for (
const auto &[DstChain, DstEdge] :
Other->Edges) {
462 ChainT *TargetChain = DstChain ==
Other ? this : DstChain;
463 ChainEdge *CurEdge = getEdge(TargetChain);
464 if (CurEdge ==
nullptr) {
465 DstEdge->changeEndpoint(
Other,
this);
466 this->
addEdge(TargetChain, DstEdge);
467 if (DstChain !=
this && DstChain !=
Other)
468 DstChain->addEdge(
this, DstEdge);
470 CurEdge->moveJumps(DstEdge);
473 if (DstChain !=
Other)
474 DstChain->removeEdge(
Other);
478using NodeIter = std::vector<NodeT *>::const_iterator;
483 MergedChain(NodeIter Begin1, NodeIter End1, NodeIter Begin2 = NodeIter(),
484 NodeIter End2 = NodeIter(), NodeIter Begin3 = NodeIter(),
485 NodeIter End3 = NodeIter())
486 : Begin1(Begin1), End1(End1), Begin2(Begin2), End2(End2), Begin3(Begin3),
489 template <
typename F>
void forEach(
const F &Func)
const {
490 for (
auto It = Begin1; It != End1; It++)
492 for (
auto It = Begin2; It != End2; It++)
494 for (
auto It = Begin3; It != End3; It++)
498 std::vector<NodeT *> getNodes()
const {
499 std::vector<NodeT *>
Result;
500 Result.reserve(std::distance(Begin1, End1) + std::distance(Begin2, End2) +
501 std::distance(Begin3, End3));
508 const NodeT *getFirstNode()
const {
return *Begin1; }
524MergedChain mergeNodes(
const std::vector<NodeT *> &
X,
525 const std::vector<NodeT *> &
Y,
size_t MergeOffset,
526 MergeTypeT MergeType) {
528 NodeIter BeginX1 =
X.begin();
529 NodeIter EndX1 =
X.begin() + MergeOffset;
530 NodeIter BeginX2 =
X.begin() + MergeOffset;
531 NodeIter EndX2 =
X.end();
532 NodeIter BeginY =
Y.begin();
533 NodeIter EndY =
Y.end();
537 case MergeTypeT::X_Y:
538 return MergedChain(BeginX1, EndX2, BeginY, EndY);
539 case MergeTypeT::Y_X:
540 return MergedChain(BeginY, EndY, BeginX1, EndX2);
541 case MergeTypeT::X1_Y_X2:
542 return MergedChain(BeginX1, EndX1, BeginY, EndY, BeginX2, EndX2);
543 case MergeTypeT::Y_X2_X1:
544 return MergedChain(BeginY, EndY, BeginX2, EndX2, BeginX1, EndX1);
545 case MergeTypeT::X2_X1_Y:
546 return MergedChain(BeginX2, EndX2, BeginX1, EndX1, BeginY, EndY);
556 : NumNodes(NodeSizes.
size()) {
557 initialize(NodeSizes, NodeCounts, EdgeCounts);
561 std::vector<uint64_t>
run() {
572 return concatChains();
581 AllNodes.reserve(NumNodes);
586 if (
Idx == 0 && ExecutionCount == 0)
588 AllNodes.emplace_back(
Idx,
Size, ExecutionCount);
592 SuccNodes.resize(NumNodes);
593 PredNodes.resize(NumNodes);
594 std::vector<uint64_t> OutDegree(NumNodes, 0);
595 AllJumps.reserve(EdgeCounts.
size());
596 for (
auto Edge : EdgeCounts) {
597 ++OutDegree[Edge.src];
599 if (Edge.src == Edge.dst)
602 SuccNodes[Edge.src].push_back(Edge.dst);
603 PredNodes[Edge.dst].push_back(Edge.src);
604 if (Edge.count > 0) {
605 NodeT &PredNode = AllNodes[Edge.src];
606 NodeT &SuccNode = AllNodes[Edge.dst];
607 AllJumps.emplace_back(&PredNode, &SuccNode, Edge.count);
608 SuccNode.InJumps.push_back(&AllJumps.back());
609 PredNode.OutJumps.push_back(&AllJumps.back());
612 for (JumpT &Jump : AllJumps) {
613 assert(OutDegree[Jump.Source->Index] > 0);
614 Jump.IsConditional = OutDegree[Jump.Source->Index] > 1;
618 AllChains.reserve(NumNodes);
619 HotChains.reserve(NumNodes);
620 for (NodeT &
Node : AllNodes) {
621 AllChains.emplace_back(
Node.Index, &
Node);
622 Node.CurChain = &AllChains.back();
623 if (
Node.ExecutionCount > 0)
624 HotChains.push_back(&AllChains.back());
628 AllEdges.reserve(AllJumps.size());
629 for (NodeT &PredNode : AllNodes) {
630 for (JumpT *Jump : PredNode.OutJumps) {
631 NodeT *SuccNode = Jump->Target;
632 ChainEdge *CurEdge = PredNode.CurChain->getEdge(SuccNode->CurChain);
634 if (CurEdge !=
nullptr) {
635 assert(SuccNode->CurChain->getEdge(PredNode.CurChain) !=
nullptr);
636 CurEdge->appendJump(Jump);
640 AllEdges.emplace_back(Jump);
641 PredNode.CurChain->addEdge(SuccNode->CurChain, &AllEdges.back());
642 SuccNode->CurChain->addEdge(PredNode.CurChain, &AllEdges.back());
651 void mergeForcedPairs() {
653 for (NodeT &
Node : AllNodes) {
654 if (SuccNodes[
Node.Index].size() == 1 &&
655 PredNodes[SuccNodes[
Node.Index][0]].size() == 1 &&
656 SuccNodes[
Node.Index][0] != 0) {
657 size_t SuccIndex = SuccNodes[
Node.Index][0];
658 Node.ForcedSucc = &AllNodes[SuccIndex];
659 AllNodes[SuccIndex].ForcedPred = &
Node;
669 for (NodeT &
Node : AllNodes) {
670 if (
Node.ForcedSucc ==
nullptr ||
Node.ForcedPred ==
nullptr)
673 NodeT *SuccNode =
Node.ForcedSucc;
674 while (SuccNode !=
nullptr && SuccNode != &
Node) {
675 SuccNode = SuccNode->ForcedSucc;
677 if (SuccNode ==
nullptr)
680 AllNodes[
Node.ForcedPred->Index].ForcedSucc =
nullptr;
681 Node.ForcedPred =
nullptr;
685 for (NodeT &
Node : AllNodes) {
686 if (
Node.ForcedPred ==
nullptr &&
Node.ForcedSucc !=
nullptr) {
687 const NodeT *CurBlock = &
Node;
688 while (CurBlock->ForcedSucc !=
nullptr) {
689 const NodeT *NextBlock = CurBlock->ForcedSucc;
690 mergeChains(
Node.CurChain, NextBlock->CurChain, 0, MergeTypeT::X_Y);
691 CurBlock = NextBlock;
698 void mergeChainPairs() {
700 auto compareChainPairs = [](
const ChainT *A1,
const ChainT *B1,
701 const ChainT *A2,
const ChainT *B2) {
703 return A1->Id < A2->Id;
704 return B1->Id < B2->Id;
707 while (HotChains.size() > 1) {
708 ChainT *BestChainPred =
nullptr;
709 ChainT *BestChainSucc =
nullptr;
712 for (ChainT *ChainPred : HotChains) {
714 for (
const auto &[ChainSucc, Edge] : ChainPred->Edges) {
716 if (ChainPred == ChainSucc)
720 if (ChainPred->numBlocks() + ChainSucc->numBlocks() >=
MaxChainSize)
724 MergeGainT CurGain = getBestMergeGain(ChainPred, ChainSucc, Edge);
725 if (CurGain.score() <= EPS)
728 if (BestGain < CurGain ||
729 (std::abs(CurGain.score() - BestGain.score()) < EPS &&
730 compareChainPairs(ChainPred, ChainSucc, BestChainPred,
733 BestChainPred = ChainPred;
734 BestChainSucc = ChainSucc;
740 if (BestGain.score() <= EPS)
744 mergeChains(BestChainPred, BestChainSucc, BestGain.mergeOffset(),
745 BestGain.mergeType());
752 void mergeColdChains() {
753 for (
size_t SrcBB = 0; SrcBB < NumNodes; SrcBB++) {
756 size_t NumSuccs = SuccNodes[SrcBB].size();
757 for (
size_t Idx = 0;
Idx < NumSuccs;
Idx++) {
758 size_t DstBB = SuccNodes[SrcBB][NumSuccs -
Idx - 1];
759 ChainT *SrcChain = AllNodes[SrcBB].CurChain;
760 ChainT *DstChain = AllNodes[DstBB].CurChain;
761 if (SrcChain != DstChain && !DstChain->isEntry() &&
762 SrcChain->Nodes.back()->Index == SrcBB &&
763 DstChain->Nodes.front()->Index == DstBB &&
764 SrcChain->isCold() == DstChain->isCold()) {
765 mergeChains(SrcChain, DstChain, 0, MergeTypeT::X_Y);
772 double extTSPScore(
const MergedChain &MergedBlocks,
773 const std::vector<JumpT *> &Jumps)
const {
777 MergedBlocks.forEach([&](
const NodeT *
Node) {
778 Node->EstimatedAddr = CurAddr;
779 CurAddr +=
Node->Size;
783 for (JumpT *Jump : Jumps) {
784 const NodeT *SrcBlock = Jump->Source;
785 const NodeT *DstBlock = Jump->Target;
786 Score += ::extTSPScore(SrcBlock->EstimatedAddr, SrcBlock->Size,
787 DstBlock->EstimatedAddr, Jump->ExecutionCount,
788 Jump->IsConditional);
799 MergeGainT getBestMergeGain(ChainT *ChainPred, ChainT *ChainSucc,
800 ChainEdge *Edge)
const {
801 if (Edge->hasCachedMergeGain(ChainPred, ChainSucc)) {
802 return Edge->getCachedMergeGain(ChainPred, ChainSucc);
806 auto Jumps = Edge->jumps();
807 ChainEdge *EdgePP = ChainPred->getEdge(ChainPred);
808 if (EdgePP !=
nullptr) {
809 Jumps.insert(Jumps.end(), EdgePP->jumps().begin(), EdgePP->jumps().end());
811 assert(!Jumps.empty() &&
"trying to merge chains w/o jumps");
814 MergeGainT Gain = MergeGainT();
818 auto tryChainMerging = [&](
size_t Offset,
819 const std::vector<MergeTypeT> &MergeTypes) {
825 if (
Node->ForcedSucc !=
nullptr)
829 for (
const MergeTypeT &MergeType : MergeTypes) {
830 Gain.updateIfLessThan(
831 computeMergeGain(ChainPred, ChainSucc, Jumps,
Offset, MergeType));
836 Gain.updateIfLessThan(
837 computeMergeGain(ChainPred, ChainSucc, Jumps, 0, MergeTypeT::X_Y));
841 for (JumpT *Jump : ChainSucc->Nodes.front()->InJumps) {
842 const NodeT *SrcBlock = Jump->Source;
843 if (SrcBlock->CurChain != ChainPred)
845 size_t Offset = SrcBlock->CurIndex + 1;
846 tryChainMerging(
Offset, {MergeTypeT::X1_Y_X2, MergeTypeT::X2_X1_Y});
850 for (JumpT *Jump : ChainSucc->Nodes.back()->OutJumps) {
851 const NodeT *DstBlock = Jump->Target;
852 if (DstBlock->CurChain != ChainPred)
854 size_t Offset = DstBlock->CurIndex;
855 tryChainMerging(
Offset, {MergeTypeT::X1_Y_X2, MergeTypeT::Y_X2_X1});
865 tryChainMerging(
Offset, {MergeTypeT::X1_Y_X2, MergeTypeT::Y_X2_X1,
866 MergeTypeT::X2_X1_Y});
869 Edge->setCachedMergeGain(ChainPred, ChainSucc, Gain);
877 MergeGainT computeMergeGain(
const ChainT *ChainPred,
const ChainT *ChainSucc,
878 const std::vector<JumpT *> &Jumps,
879 size_t MergeOffset, MergeTypeT MergeType)
const {
881 mergeNodes(ChainPred->Nodes, ChainSucc->Nodes, MergeOffset, MergeType);
884 if ((ChainPred->isEntry() || ChainSucc->isEntry()) &&
885 !MergedBlocks.getFirstNode()->isEntry())
889 auto NewGainScore = extTSPScore(MergedBlocks, Jumps) - ChainPred->Score;
890 return MergeGainT(NewGainScore, MergeOffset, MergeType);
895 void mergeChains(ChainT *Into, ChainT *
From,
size_t MergeOffset,
896 MergeTypeT MergeType) {
897 assert(Into !=
From &&
"a chain cannot be merged with itself");
900 MergedChain MergedNodes =
901 mergeNodes(Into->Nodes,
From->Nodes, MergeOffset, MergeType);
902 Into->merge(
From, MergedNodes.getNodes());
905 Into->mergeEdges(
From);
909 ChainEdge *SelfEdge = Into->getEdge(Into);
910 if (SelfEdge !=
nullptr) {
911 MergedNodes = MergedChain(Into->Nodes.begin(), Into->Nodes.end());
912 Into->Score = extTSPScore(MergedNodes, SelfEdge->jumps());
919 for (
auto EdgeIt : Into->Edges)
920 EdgeIt.second->invalidateCache();
924 std::vector<uint64_t> concatChains() {
926 std::vector<const ChainT *> SortedChains;
928 for (ChainT &Chain : AllChains) {
929 if (!Chain.Nodes.empty()) {
930 SortedChains.push_back(&Chain);
933 double ExecutionCount = 0;
934 for (NodeT *
Node : Chain.Nodes) {
935 Size +=
static_cast<double>(
Node->Size);
936 ExecutionCount +=
static_cast<double>(
Node->ExecutionCount);
939 ChainDensity[&Chain] = ExecutionCount /
Size;
944 std::sort(SortedChains.begin(), SortedChains.end(),
945 [&](
const ChainT *L,
const ChainT *R) {
947 if (L->isEntry() != R->isEntry())
950 const double DL = ChainDensity[L];
951 const double DR = ChainDensity[R];
953 return std::make_tuple(-DL, L->Id) <
954 std::make_tuple(-DR, R->Id);
958 std::vector<uint64_t> Order;
959 Order.reserve(NumNodes);
960 for (
const ChainT *Chain : SortedChains)
961 for (NodeT *
Node : Chain->Nodes)
962 Order.push_back(
Node->Index);
968 const size_t NumNodes;
971 std::vector<std::vector<uint64_t>> SuccNodes;
974 std::vector<std::vector<uint64_t>> PredNodes;
977 std::vector<NodeT> AllNodes;
980 std::vector<JumpT> AllJumps;
983 std::vector<ChainT> AllChains;
986 std::vector<ChainEdge> AllEdges;
989 std::vector<ChainT *> HotChains;
1000 initialize(NodeSizes, NodeCounts, EdgeCounts, EdgeOffsets);
1004 std::vector<uint64_t>
run() {
1008 LLVM_DEBUG(
dbgs() <<
"Cache-directed function sorting reduced the number"
1009 <<
" of chains from " << NumNodes <<
" to "
1010 << HotChains.size() <<
"\n");
1013 return concatChains();
1023 AllNodes.reserve(NumNodes);
1027 AllNodes.emplace_back(
Node,
Size, ExecutionCount);
1028 TotalSamples += ExecutionCount;
1029 if (ExecutionCount > 0)
1034 SuccNodes.resize(NumNodes);
1035 PredNodes.resize(NumNodes);
1036 AllJumps.reserve(EdgeCounts.
size());
1037 for (
size_t I = 0;
I < EdgeCounts.
size();
I++) {
1038 auto [Pred, Succ, Count] = EdgeCounts[
I];
1043 SuccNodes[Pred].push_back(Succ);
1044 PredNodes[Succ].push_back(Pred);
1046 NodeT &PredNode = AllNodes[Pred];
1047 NodeT &SuccNode = AllNodes[Succ];
1048 AllJumps.emplace_back(&PredNode, &SuccNode, Count);
1049 AllJumps.
back().Offset = EdgeOffsets[
I];
1050 SuccNode.InJumps.push_back(&AllJumps.back());
1051 PredNode.OutJumps.push_back(&AllJumps.back());
1056 AllChains.reserve(NumNodes);
1057 HotChains.reserve(NumNodes);
1058 for (NodeT &
Node : AllNodes) {
1060 Node.ExecutionCount = std::max(
Node.ExecutionCount,
Node.inCount());
1061 Node.ExecutionCount = std::max(
Node.ExecutionCount,
Node.outCount());
1063 AllChains.emplace_back(
Node.Index, &
Node);
1064 Node.CurChain = &AllChains.back();
1065 if (
Node.ExecutionCount > 0)
1066 HotChains.push_back(&AllChains.back());
1070 AllEdges.reserve(AllJumps.size());
1071 for (NodeT &PredNode : AllNodes) {
1072 for (JumpT *Jump : PredNode.OutJumps) {
1073 NodeT *SuccNode = Jump->Target;
1074 ChainEdge *CurEdge = PredNode.CurChain->getEdge(SuccNode->CurChain);
1076 if (CurEdge !=
nullptr) {
1077 assert(SuccNode->CurChain->getEdge(PredNode.CurChain) !=
nullptr);
1078 CurEdge->appendJump(Jump);
1082 AllEdges.emplace_back(Jump);
1083 PredNode.CurChain->addEdge(SuccNode->CurChain, &AllEdges.back());
1084 SuccNode->CurChain->addEdge(PredNode.CurChain, &AllEdges.back());
1090 void mergeChainPairs() {
1092 auto GainComparator = [](ChainEdge *
L, ChainEdge *
R) {
1093 return std::make_tuple(-
L->gain(),
L->srcChain()->Id,
L->dstChain()->Id) <
1094 std::make_tuple(-
R->gain(),
R->srcChain()->Id,
R->dstChain()->Id);
1096 std::set<ChainEdge *,
decltype(GainComparator)>
Queue(GainComparator);
1099 for (ChainT *ChainPred : HotChains) {
1100 for (
const auto &[
_, Edge] : ChainPred->Edges) {
1102 if (Edge->isSelfEdge())
1105 if (Edge->gain() != -1.0)
1109 MergeGainT Gain = getBestMergeGain(Edge);
1110 Edge->setMergeGain(Gain);
1112 if (Edge->gain() > EPS)
1118 while (!
Queue.empty()) {
1120 ChainEdge *BestEdge = *
Queue.begin();
1123 if (BestEdge->isSelfEdge())
1126 if (BestEdge->gain() <= EPS)
1129 ChainT *BestSrcChain = BestEdge->srcChain();
1130 ChainT *BestDstChain = BestEdge->dstChain();
1133 for (
const auto &[
_, ChainEdge] : BestSrcChain->Edges)
1134 Queue.erase(ChainEdge);
1135 for (
const auto &[
_, ChainEdge] : BestDstChain->Edges)
1136 Queue.erase(ChainEdge);
1139 MergeGainT BestGain = BestEdge->getMergeGain();
1140 mergeChains(BestSrcChain, BestDstChain, BestGain.mergeOffset(),
1141 BestGain.mergeType());
1144 for (
const auto &[
_, Edge] : BestSrcChain->Edges) {
1146 if (Edge->isSelfEdge())
1150 MergeGainT Gain = getBestMergeGain(Edge);
1151 Edge->setMergeGain(Gain);
1153 if (Edge->gain() > EPS)
1165 MergeGainT getBestMergeGain(ChainEdge *Edge)
const {
1167 auto Jumps = Edge->jumps();
1168 assert(!Jumps.empty() &&
"trying to merge chains w/o jumps");
1169 ChainT *SrcChain = Edge->srcChain();
1170 ChainT *DstChain = Edge->dstChain();
1173 MergeGainT Gain = MergeGainT();
1177 auto tryChainMerging = [&](
const std::vector<MergeTypeT> &MergeTypes) {
1180 for (
const MergeTypeT &MergeType : MergeTypes) {
1181 MergeGainT NewGain =
1182 computeMergeGain(SrcChain, DstChain, Jumps, MergeType);
1186 if (std::abs(Gain.score() - NewGain.score()) < EPS) {
1187 if ((MergeType == MergeTypeT::X_Y && SrcChain->Id < DstChain->Id) ||
1188 (MergeType == MergeTypeT::Y_X && SrcChain->Id > DstChain->Id)) {
1191 }
else if (NewGain.score() > Gain.score() + EPS) {
1198 tryChainMerging({MergeTypeT::X_Y, MergeTypeT::Y_X});
1206 MergeGainT computeMergeGain(ChainT *ChainPred, ChainT *ChainSucc,
1207 const std::vector<JumpT *> &Jumps,
1208 MergeTypeT MergeType)
const {
1210 double FreqGain = freqBasedLocalityGain(ChainPred, ChainSucc);
1213 size_t MergeOffset = 0;
1215 mergeNodes(ChainPred->Nodes, ChainSucc->Nodes, MergeOffset, MergeType);
1216 double DistGain = distBasedLocalityGain(MergedBlocks, Jumps);
1218 double GainScore = DistGain +
Config.FrequencyScale * FreqGain;
1220 if (GainScore >= 0.0)
1221 GainScore /= std::min(ChainPred->Size, ChainSucc->Size);
1223 return MergeGainT(GainScore, MergeOffset, MergeType);
1227 double freqBasedLocalityGain(ChainT *ChainPred, ChainT *ChainSucc)
const {
1228 auto missProbability = [&](
double ChainDensity) {
1229 double PageSamples = ChainDensity *
Config.CacheSize;
1230 if (PageSamples >= TotalSamples)
1232 double P = PageSamples / TotalSamples;
1233 return pow(1.0 -
P,
static_cast<double>(
Config.CacheEntries));
1238 ChainPred->ExecutionCount * missProbability(ChainPred->density()) +
1239 ChainSucc->ExecutionCount * missProbability(ChainSucc->density());
1242 double MergedCounts = ChainPred->ExecutionCount + ChainSucc->ExecutionCount;
1243 double MergedSize = ChainPred->Size + ChainSucc->Size;
1244 double MergedDensity =
static_cast<double>(MergedCounts) / MergedSize;
1245 double NewScore = MergedCounts * missProbability(MergedDensity);
1247 return CurScore - NewScore;
1252 uint64_t Dist = SrcAddr <= DstAddr ? DstAddr - SrcAddr : SrcAddr - DstAddr;
1253 double D = Dist == 0 ? 0.1 :
static_cast<double>(Dist);
1254 return static_cast<double>(Count) * std::pow(
D, -
Config.DistancePower);
1258 double distBasedLocalityGain(
const MergedChain &MergedBlocks,
1259 const std::vector<JumpT *> &Jumps)
const {
1263 MergedBlocks.forEach([&](
const NodeT *
Node) {
1264 Node->EstimatedAddr = CurAddr;
1265 CurAddr +=
Node->Size;
1268 double CurScore = 0;
1269 double NewScore = 0;
1270 for (
const JumpT *Arc : Jumps) {
1271 uint64_t SrcAddr = Arc->Source->EstimatedAddr + Arc->Offset;
1272 uint64_t DstAddr = Arc->Target->EstimatedAddr;
1273 NewScore += distScore(SrcAddr, DstAddr, Arc->ExecutionCount);
1274 CurScore += distScore(0, TotalSize, Arc->ExecutionCount);
1276 return NewScore - CurScore;
1281 void mergeChains(ChainT *Into, ChainT *
From,
size_t MergeOffset,
1282 MergeTypeT MergeType) {
1283 assert(Into !=
From &&
"a chain cannot be merged with itself");
1286 MergedChain MergedNodes =
1287 mergeNodes(Into->Nodes,
From->Nodes, MergeOffset, MergeType);
1288 Into->merge(
From, MergedNodes.getNodes());
1291 Into->mergeEdges(
From);
1299 std::vector<uint64_t> concatChains() {
1301 std::vector<const ChainT *> SortedChains;
1303 for (ChainT &Chain : AllChains) {
1304 if (!Chain.Nodes.empty()) {
1305 SortedChains.push_back(&Chain);
1308 double ExecutionCount = 0;
1309 for (NodeT *
Node : Chain.Nodes) {
1310 Size +=
static_cast<double>(
Node->Size);
1311 ExecutionCount +=
static_cast<double>(
Node->ExecutionCount);
1314 ChainDensity[&Chain] = ExecutionCount /
Size;
1319 std::sort(SortedChains.begin(), SortedChains.end(),
1320 [&](
const ChainT *L,
const ChainT *R) {
1321 const double DL = ChainDensity[L];
1322 const double DR = ChainDensity[R];
1324 return std::make_tuple(-DL, L->Id) <
1325 std::make_tuple(-DR, R->Id);
1329 std::vector<uint64_t> Order;
1330 Order.reserve(NumNodes);
1331 for (
const ChainT *Chain : SortedChains)
1332 for (NodeT *
Node : Chain->Nodes)
1333 Order.push_back(
Node->Index);
1342 const size_t NumNodes;
1345 std::vector<std::vector<uint64_t>> SuccNodes;
1348 std::vector<std::vector<uint64_t>> PredNodes;
1351 std::vector<NodeT> AllNodes;
1354 std::vector<JumpT> AllJumps;
1357 std::vector<ChainT> AllChains;
1360 std::vector<ChainEdge> AllEdges;
1363 std::vector<ChainT *> HotChains;
1374std::vector<uint64_t>
1379 assert(NodeCounts.
size() == NodeSizes.
size() &&
"Incorrect input");
1380 assert(NodeSizes.
size() > 2 &&
"Incorrect input");
1383 ExtTSPImpl Alg(NodeSizes, NodeCounts, EdgeCounts);
1384 std::vector<uint64_t> Result = Alg.run();
1387 assert(Result.front() == 0 &&
"Original entry point is not preserved");
1388 assert(Result.size() == NodeSizes.
size() &&
"Incorrect size of layout");
1397 std::vector<uint64_t>
Addr(NodeSizes.
size(), 0);
1401 std::vector<uint64_t> OutDegree(NodeSizes.
size(), 0);
1402 for (
auto Edge : EdgeCounts)
1403 ++OutDegree[Edge.src];
1407 for (
auto Edge : EdgeCounts) {
1408 bool IsConditional = OutDegree[Edge.src] > 1;
1409 Score += ::extTSPScore(
Addr[Edge.src], NodeSizes[Edge.src],
Addr[Edge.dst],
1410 Edge.count, IsConditional);
1418 std::vector<uint64_t> Order(NodeSizes.
size());
1430 assert(FuncCounts.
size() == FuncSizes.
size() &&
"Incorrect input");
1433 CDSortImpl Alg(
Config, FuncSizes, FuncCounts, CallCounts, CallOffsets);
1434 std::vector<uint64_t> Result = Alg.run();
1435 assert(Result.size() == FuncSizes.
size() &&
"Incorrect size of layout");
BlockVerifier::State From
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static cl::opt< double > DistancePower("cds-distance-power", cl::ReallyHidden, cl::desc("The power exponent for the distance-based locality"))
static cl::opt< double > FrequencyScale("cds-frequency-scale", cl::ReallyHidden, cl::desc("The scale factor for the frequency-based locality"))
static cl::opt< unsigned > CacheEntries("cds-cache-entries", cl::ReallyHidden, cl::desc("The size of the cache"))
static cl::opt< bool > EnableChainSplitAlongJumps("ext-tsp-enable-chain-split-along-jumps", cl::ReallyHidden, cl::init(true), cl::desc("The maximum size of a chain to apply splitting"))
static cl::opt< unsigned > ForwardDistance("ext-tsp-forward-distance", cl::ReallyHidden, cl::init(1024), cl::desc("The maximum distance (in bytes) of a forward jump for ExtTSP"))
static cl::opt< unsigned > BackwardDistance("ext-tsp-backward-distance", cl::ReallyHidden, cl::init(640), cl::desc("The maximum distance (in bytes) of a backward jump for ExtTSP"))
static cl::opt< double > BackwardWeightCond("ext-tsp-backward-weight-cond", cl::ReallyHidden, cl::init(0.1), cl::desc("The weight of conditional backward jumps for ExtTSP value"))
static cl::opt< double > ForwardWeightUncond("ext-tsp-forward-weight-uncond", cl::ReallyHidden, cl::init(0.1), cl::desc("The weight of unconditional forward jumps for ExtTSP value"))
static cl::opt< unsigned > ChainSplitThreshold("ext-tsp-chain-split-threshold", cl::ReallyHidden, cl::init(128), cl::desc("The maximum size of a chain to apply splitting"))
static cl::opt< unsigned > MaxChainSize("ext-tsp-max-chain-size", cl::ReallyHidden, cl::init(4096), cl::desc("The maximum size of a chain to create."))
static cl::opt< double > FallthroughWeightUncond("ext-tsp-fallthrough-weight-uncond", cl::ReallyHidden, cl::init(1.05), cl::desc("The weight of unconditional fallthrough jumps for ExtTSP value"))
static cl::opt< unsigned > CacheSize("cds-cache-size", cl::ReallyHidden, cl::desc("The size of a line in the cache"))
static cl::opt< double > BackwardWeightUncond("ext-tsp-backward-weight-uncond", cl::ReallyHidden, cl::init(0.1), cl::desc("The weight of unconditional backward jumps for ExtTSP value"))
static cl::opt< double > ForwardWeightCond("ext-tsp-forward-weight-cond", cl::ReallyHidden, cl::init(0.1), cl::desc("The weight of conditional forward jumps for ExtTSP value"))
static cl::opt< double > FallthroughWeightCond("ext-tsp-fallthrough-weight-cond", cl::ReallyHidden, cl::init(1.0), cl::desc("The weight of conditional fallthrough jumps for ExtTSP value"))
Declares methods and data structures for code layout algorithms.
static void clear(coro::Shape &Shape)
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
std::optional< std::vector< StOtherPiece > > Other
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static void addEdge(SmallVectorImpl< LazyCallGraph::Edge > &Edges, DenseMap< LazyCallGraph::Node *, int > &EdgeIndexMap, LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK)
static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B)
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
size_t size() const
size - Get the array size.
Target - Wrapper for Target specific information.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
initializer< Ty > init(const Ty &Val)
std::vector< uint64_t > computeCacheDirectedLayout(ArrayRef< uint64_t > FuncSizes, ArrayRef< uint64_t > FuncCounts, ArrayRef< EdgeCount > CallCounts, ArrayRef< uint64_t > CallOffsets)
Apply a Cache-Directed Sort for functions represented by a call graph.
double calcExtTspScore(ArrayRef< uint64_t > Order, ArrayRef< uint64_t > NodeSizes, ArrayRef< uint64_t > NodeCounts, ArrayRef< EdgeCount > EdgeCounts)
Estimate the "quality" of a given node order in CFG.
std::vector< uint64_t > computeExtTspLayout(ArrayRef< uint64_t > NodeSizes, ArrayRef< uint64_t > NodeCounts, ArrayRef< EdgeCount > EdgeCounts)
Find a layout of nodes (basic blocks) of a given CFG optimizing jump locality and thus processor I-ca...
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< FuncNode * > Func
This is an optimization pass for GlobalISel generic memory operations.
bool operator<(int64_t V1, const APSInt &V2)
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
cl::opt< bool > ApplyExtTspWithoutProfile
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
cl::opt< bool > EnableExtTspBlockPlacement
Algorithm-specific params for Cache-Directed Sort.