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"));
116 cl::desc(
"The maximum ratio between densities of two chains for merging"));
123 cl::desc(
"The size of a line in the cache"));
127 cl::desc(
"The maximum size of a chain to create"));
131 cl::desc(
"The power exponent for the distance-based locality"));
135 cl::desc(
"The scale factor for the frequency-based locality"));
140constexpr double EPS = 1e-8;
145 if (JumpDist > JumpMaxDist)
147 double Prob = 1.0 -
static_cast<double>(JumpDist) / JumpMaxDist;
148 return Weight * Prob * Count;
154 uint64_t Count,
bool IsConditional) {
156 if (SrcAddr + SrcSize == DstAddr) {
157 return jumpExtTSPScore(0, 1, Count,
162 if (SrcAddr + SrcSize < DstAddr) {
163 const uint64_t Dist = DstAddr - (SrcAddr + SrcSize);
169 const uint64_t Dist = SrcAddr + SrcSize - DstAddr;
177enum class MergeTypeT :
int { X_Y, Y_X, X1_Y_X2, Y_X2_X1, X2_X1_Y };
182 explicit MergeGainT() =
default;
183 explicit MergeGainT(
double Score,
size_t MergeOffset, MergeTypeT MergeType)
184 : Score(Score), MergeOffset(MergeOffset), MergeType(MergeType) {}
186 double score()
const {
return Score; }
188 size_t mergeOffset()
const {
return MergeOffset; }
190 MergeTypeT mergeType()
const {
return MergeType; }
192 void setMergeType(MergeTypeT Ty) { MergeType = Ty; }
196 return (
Other.Score > EPS &&
Other.Score > Score + EPS);
200 void updateIfLessThan(
const MergeGainT &
Other) {
207 size_t MergeOffset{0};
208 MergeTypeT MergeType{MergeTypeT::X_Y};
218 NodeT(
const NodeT &) =
delete;
219 NodeT(NodeT &&) =
default;
220 NodeT &operator=(
const NodeT &) =
delete;
221 NodeT &operator=(NodeT &&) =
default;
226 bool isEntry()
const {
return Index == 0; }
229 bool isSuccessor(
const NodeT *
Other)
const;
246 ChainT *CurChain{
nullptr};
250 NodeT *ForcedSucc{
nullptr};
252 NodeT *ForcedPred{
nullptr};
254 std::vector<JumpT *> OutJumps;
256 std::vector<JumpT *> InJumps;
261 JumpT(
const JumpT &) =
delete;
262 JumpT(JumpT &&) =
default;
263 JumpT &operator=(
const JumpT &) =
delete;
264 JumpT &operator=(JumpT &&) =
default;
266 explicit JumpT(NodeT *Source, NodeT *
Target,
uint64_t ExecutionCount)
276 bool IsConditional{
false};
283 ChainT(
const ChainT &) =
delete;
284 ChainT(ChainT &&) =
default;
285 ChainT &operator=(
const ChainT &) =
delete;
286 ChainT &operator=(ChainT &&) =
default;
292 size_t numBlocks()
const {
return Nodes.size(); }
294 double density()
const {
return ExecutionCount /
Size; }
296 bool isEntry()
const {
return Nodes[0]->Index == 0; }
298 bool isCold()
const {
299 for (NodeT *
Node : Nodes) {
300 if (
Node->ExecutionCount > 0)
306 ChainEdge *getEdge(ChainT *
Other)
const {
307 for (
const auto &[Chain, ChainEdge] : Edges) {
314 void removeEdge(ChainT *
Other) {
315 auto It = Edges.begin();
316 while (It != Edges.end()) {
317 if (It->first ==
Other) {
326 Edges.push_back(std::make_pair(
Other, Edge));
329 void merge(ChainT *
Other, std::vector<NodeT *> MergedBlocks) {
330 Nodes = std::move(MergedBlocks);
332 ExecutionCount +=
Other->ExecutionCount;
334 Id = Nodes[0]->Index;
336 for (
size_t Idx = 0;
Idx < Nodes.size();
Idx++) {
337 Nodes[
Idx]->CurChain =
this;
338 Nodes[
Idx]->CurIndex =
Idx;
342 void mergeEdges(ChainT *
Other);
346 Nodes.shrink_to_fit();
348 Edges.shrink_to_fit();
357 double ExecutionCount{0};
361 std::vector<NodeT *> Nodes;
363 std::vector<std::pair<ChainT *, ChainEdge *>> Edges;
370 ChainEdge(
const ChainEdge &) =
delete;
371 ChainEdge(ChainEdge &&) =
default;
372 ChainEdge &operator=(
const ChainEdge &) =
delete;
373 ChainEdge &operator=(ChainEdge &&) =
delete;
375 explicit ChainEdge(JumpT *Jump)
376 : SrcChain(Jump->
Source->CurChain), DstChain(Jump->
Target->CurChain),
379 ChainT *srcChain()
const {
return SrcChain; }
381 ChainT *dstChain()
const {
return DstChain; }
383 bool isSelfEdge()
const {
return SrcChain == DstChain; }
385 const std::vector<JumpT *> &jumps()
const {
return Jumps; }
387 void appendJump(JumpT *Jump) { Jumps.push_back(Jump); }
389 void moveJumps(ChainEdge *
Other) {
390 Jumps.insert(Jumps.end(),
Other->Jumps.begin(),
Other->Jumps.end());
391 Other->Jumps.clear();
392 Other->Jumps.shrink_to_fit();
395 void changeEndpoint(ChainT *
From, ChainT *To) {
396 if (
From == SrcChain)
398 if (
From == DstChain)
402 bool hasCachedMergeGain(ChainT *Src, ChainT *Dst)
const {
403 return Src == SrcChain ? CacheValidForward : CacheValidBackward;
406 MergeGainT getCachedMergeGain(ChainT *Src, ChainT *Dst)
const {
407 return Src == SrcChain ? CachedGainForward : CachedGainBackward;
410 void setCachedMergeGain(ChainT *Src, ChainT *Dst, MergeGainT MergeGain) {
411 if (Src == SrcChain) {
412 CachedGainForward = MergeGain;
413 CacheValidForward =
true;
415 CachedGainBackward = MergeGain;
416 CacheValidBackward =
true;
420 void invalidateCache() {
421 CacheValidForward =
false;
422 CacheValidBackward =
false;
425 void setMergeGain(MergeGainT Gain) { CachedGain = Gain; }
427 MergeGainT getMergeGain()
const {
return CachedGain; }
429 double gain()
const {
return CachedGain.score(); }
433 ChainT *SrcChain{
nullptr};
435 ChainT *DstChain{
nullptr};
437 std::vector<JumpT *> Jumps;
439 MergeGainT CachedGain;
445 MergeGainT CachedGainForward;
446 MergeGainT CachedGainBackward;
448 bool CacheValidForward{
false};
449 bool CacheValidBackward{
false};
452bool NodeT::isSuccessor(
const NodeT *
Other)
const {
453 for (JumpT *Jump : OutJumps)
454 if (Jump->Target ==
Other)
461 for (JumpT *Jump : OutJumps)
462 Count += Jump->ExecutionCount;
468 for (JumpT *Jump : InJumps)
469 Count += Jump->ExecutionCount;
473void ChainT::mergeEdges(ChainT *
Other) {
475 for (
const auto &[DstChain, DstEdge] :
Other->Edges) {
476 ChainT *TargetChain = DstChain ==
Other ? this : DstChain;
477 ChainEdge *CurEdge = getEdge(TargetChain);
478 if (CurEdge ==
nullptr) {
479 DstEdge->changeEndpoint(
Other,
this);
480 this->
addEdge(TargetChain, DstEdge);
481 if (DstChain !=
this && DstChain !=
Other)
482 DstChain->addEdge(
this, DstEdge);
484 CurEdge->moveJumps(DstEdge);
487 if (DstChain !=
Other)
488 DstChain->removeEdge(
Other);
492using NodeIter = std::vector<NodeT *>::const_iterator;
493static std::vector<NodeT *> EmptyList;
498 MergedNodesT(NodeIter Begin1, NodeIter End1,
499 NodeIter Begin2 = EmptyList.begin(),
500 NodeIter End2 = EmptyList.end(),
501 NodeIter Begin3 = EmptyList.begin(),
502 NodeIter End3 = EmptyList.end())
503 : Begin1(Begin1), End1(End1), Begin2(Begin2), End2(End2), Begin3(Begin3),
506 template <
typename F>
void forEach(
const F &Func)
const {
507 for (
auto It = Begin1; It != End1; It++)
509 for (
auto It = Begin2; It != End2; It++)
511 for (
auto It = Begin3; It != End3; It++)
515 std::vector<NodeT *> getNodes()
const {
516 std::vector<NodeT *>
Result;
517 Result.reserve(std::distance(Begin1, End1) + std::distance(Begin2, End2) +
518 std::distance(Begin3, End3));
525 const NodeT *getFirstNode()
const {
return *Begin1; }
538 MergedJumpsT(
const std::vector<JumpT *> *Jumps1,
539 const std::vector<JumpT *> *Jumps2 =
nullptr) {
540 assert(!Jumps1->empty() &&
"cannot merge empty jump list");
541 JumpArray[0] = Jumps1;
542 JumpArray[1] = Jumps2;
545 template <
typename F>
void forEach(
const F &Func)
const {
546 for (
auto Jumps : JumpArray)
547 if (Jumps !=
nullptr)
548 for (JumpT *Jump : *Jumps)
553 std::array<const std::vector<JumpT *> *, 2> JumpArray{
nullptr,
nullptr};
561MergedNodesT mergeNodes(
const std::vector<NodeT *> &
X,
562 const std::vector<NodeT *> &
Y,
size_t MergeOffset,
563 MergeTypeT MergeType) {
565 NodeIter BeginX1 =
X.begin();
566 NodeIter EndX1 =
X.begin() + MergeOffset;
567 NodeIter BeginX2 =
X.begin() + MergeOffset;
568 NodeIter EndX2 =
X.end();
569 NodeIter BeginY =
Y.begin();
570 NodeIter EndY =
Y.end();
574 case MergeTypeT::X_Y:
575 return MergedNodesT(BeginX1, EndX2, BeginY, EndY);
576 case MergeTypeT::Y_X:
577 return MergedNodesT(BeginY, EndY, BeginX1, EndX2);
578 case MergeTypeT::X1_Y_X2:
579 return MergedNodesT(BeginX1, EndX1, BeginY, EndY, BeginX2, EndX2);
580 case MergeTypeT::Y_X2_X1:
581 return MergedNodesT(BeginY, EndY, BeginX2, EndX2, BeginX1, EndX1);
582 case MergeTypeT::X2_X1_Y:
583 return MergedNodesT(BeginX2, EndX2, BeginX1, EndX1, BeginY, EndY);
593 : NumNodes(NodeSizes.
size()) {
594 initialize(NodeSizes, NodeCounts, EdgeCounts);
598 std::vector<uint64_t>
run() {
609 return concatChains();
618 AllNodes.reserve(NumNodes);
623 if (
Idx == 0 && ExecutionCount == 0)
625 AllNodes.emplace_back(
Idx,
Size, ExecutionCount);
629 SuccNodes.resize(NumNodes);
630 PredNodes.resize(NumNodes);
631 std::vector<uint64_t> OutDegree(NumNodes, 0);
632 AllJumps.reserve(EdgeCounts.
size());
633 for (
auto Edge : EdgeCounts) {
634 ++OutDegree[Edge.src];
636 if (Edge.src == Edge.dst)
639 SuccNodes[Edge.src].push_back(Edge.dst);
640 PredNodes[Edge.dst].push_back(Edge.src);
641 if (Edge.count > 0) {
642 NodeT &PredNode = AllNodes[Edge.src];
643 NodeT &SuccNode = AllNodes[Edge.dst];
644 AllJumps.emplace_back(&PredNode, &SuccNode, Edge.count);
645 SuccNode.InJumps.push_back(&AllJumps.back());
646 PredNode.OutJumps.push_back(&AllJumps.back());
648 PredNode.ExecutionCount = std::max(PredNode.ExecutionCount, Edge.count);
649 SuccNode.ExecutionCount = std::max(SuccNode.ExecutionCount, Edge.count);
652 for (JumpT &Jump : AllJumps) {
653 assert(OutDegree[Jump.Source->Index] > 0 &&
654 "incorrectly computed out-degree of the block");
655 Jump.IsConditional = OutDegree[Jump.Source->Index] > 1;
659 AllChains.reserve(NumNodes);
660 HotChains.reserve(NumNodes);
661 for (NodeT &
Node : AllNodes) {
663 AllChains.emplace_back(
Node.Index, &
Node);
664 Node.CurChain = &AllChains.back();
665 if (
Node.ExecutionCount > 0)
666 HotChains.push_back(&AllChains.back());
670 AllEdges.reserve(AllJumps.size());
671 for (NodeT &PredNode : AllNodes) {
672 for (JumpT *Jump : PredNode.OutJumps) {
673 assert(Jump->ExecutionCount > 0 &&
"incorrectly initialized jump");
674 NodeT *SuccNode = Jump->Target;
675 ChainEdge *CurEdge = PredNode.CurChain->getEdge(SuccNode->CurChain);
677 if (CurEdge !=
nullptr) {
678 assert(SuccNode->CurChain->getEdge(PredNode.CurChain) !=
nullptr);
679 CurEdge->appendJump(Jump);
683 AllEdges.emplace_back(Jump);
684 PredNode.CurChain->addEdge(SuccNode->CurChain, &AllEdges.back());
685 SuccNode->CurChain->addEdge(PredNode.CurChain, &AllEdges.back());
694 void mergeForcedPairs() {
696 for (NodeT &
Node : AllNodes) {
697 if (SuccNodes[
Node.Index].size() == 1 &&
698 PredNodes[SuccNodes[
Node.Index][0]].size() == 1 &&
699 SuccNodes[
Node.Index][0] != 0) {
700 size_t SuccIndex = SuccNodes[
Node.Index][0];
701 Node.ForcedSucc = &AllNodes[SuccIndex];
702 AllNodes[SuccIndex].ForcedPred = &
Node;
712 for (NodeT &
Node : AllNodes) {
713 if (
Node.ForcedSucc ==
nullptr ||
Node.ForcedPred ==
nullptr)
716 NodeT *SuccNode =
Node.ForcedSucc;
717 while (SuccNode !=
nullptr && SuccNode != &
Node) {
718 SuccNode = SuccNode->ForcedSucc;
720 if (SuccNode ==
nullptr)
723 AllNodes[
Node.ForcedPred->Index].ForcedSucc =
nullptr;
724 Node.ForcedPred =
nullptr;
728 for (NodeT &
Node : AllNodes) {
729 if (
Node.ForcedPred ==
nullptr &&
Node.ForcedSucc !=
nullptr) {
730 const NodeT *CurBlock = &
Node;
731 while (CurBlock->ForcedSucc !=
nullptr) {
732 const NodeT *NextBlock = CurBlock->ForcedSucc;
733 mergeChains(
Node.CurChain, NextBlock->CurChain, 0, MergeTypeT::X_Y);
734 CurBlock = NextBlock;
741 void mergeChainPairs() {
743 auto compareChainPairs = [](
const ChainT *A1,
const ChainT *B1,
744 const ChainT *A2,
const ChainT *B2) {
745 return std::make_tuple(A1->Id, B1->Id) < std::make_tuple(A2->Id, B2->Id);
748 while (HotChains.size() > 1) {
749 ChainT *BestChainPred =
nullptr;
750 ChainT *BestChainSucc =
nullptr;
753 for (ChainT *ChainPred : HotChains) {
755 for (
const auto &[ChainSucc, Edge] : ChainPred->Edges) {
757 if (Edge->isSelfEdge())
761 if (ChainPred->numBlocks() + ChainSucc->numBlocks() >=
MaxChainSize)
767 const double ChainPredDensity = ChainPred->density();
768 const double ChainSuccDensity = ChainSucc->density();
769 assert(ChainPredDensity > 0.0 && ChainSuccDensity > 0.0 &&
770 "incorrectly computed chain densities");
771 auto [MinDensity, MaxDensity] =
772 std::minmax(ChainPredDensity, ChainSuccDensity);
773 const double Ratio = MaxDensity / MinDensity;
778 MergeGainT CurGain = getBestMergeGain(ChainPred, ChainSucc, Edge);
779 if (CurGain.score() <= EPS)
782 if (BestGain < CurGain ||
783 (std::abs(CurGain.score() - BestGain.score()) < EPS &&
784 compareChainPairs(ChainPred, ChainSucc, BestChainPred,
787 BestChainPred = ChainPred;
788 BestChainSucc = ChainSucc;
794 if (BestGain.score() <= EPS)
798 mergeChains(BestChainPred, BestChainSucc, BestGain.mergeOffset(),
799 BestGain.mergeType());
806 void mergeColdChains() {
807 for (
size_t SrcBB = 0; SrcBB < NumNodes; SrcBB++) {
810 size_t NumSuccs = SuccNodes[SrcBB].size();
811 for (
size_t Idx = 0;
Idx < NumSuccs;
Idx++) {
812 size_t DstBB = SuccNodes[SrcBB][NumSuccs -
Idx - 1];
813 ChainT *SrcChain = AllNodes[SrcBB].CurChain;
814 ChainT *DstChain = AllNodes[DstBB].CurChain;
815 if (SrcChain != DstChain && !DstChain->isEntry() &&
816 SrcChain->Nodes.back()->Index == SrcBB &&
817 DstChain->Nodes.front()->Index == DstBB &&
818 SrcChain->isCold() == DstChain->isCold()) {
819 mergeChains(SrcChain, DstChain, 0, MergeTypeT::X_Y);
826 double extTSPScore(
const MergedNodesT &Nodes,
827 const MergedJumpsT &Jumps)
const {
829 Nodes.forEach([&](
const NodeT *
Node) {
830 Node->EstimatedAddr = CurAddr;
831 CurAddr +=
Node->Size;
835 Jumps.forEach([&](
const JumpT *Jump) {
836 const NodeT *SrcBlock = Jump->Source;
837 const NodeT *DstBlock = Jump->Target;
838 Score += ::extTSPScore(SrcBlock->EstimatedAddr, SrcBlock->Size,
839 DstBlock->EstimatedAddr, Jump->ExecutionCount,
840 Jump->IsConditional);
851 MergeGainT getBestMergeGain(ChainT *ChainPred, ChainT *ChainSucc,
852 ChainEdge *Edge)
const {
853 if (Edge->hasCachedMergeGain(ChainPred, ChainSucc))
854 return Edge->getCachedMergeGain(ChainPred, ChainSucc);
856 assert(!Edge->jumps().empty() &&
"trying to merge chains w/o jumps");
858 ChainEdge *EdgePP = ChainPred->getEdge(ChainPred);
859 MergedJumpsT Jumps(&Edge->jumps(), EdgePP ? &EdgePP->jumps() :
nullptr);
862 MergeGainT Gain = MergeGainT();
866 auto tryChainMerging = [&](
size_t Offset,
867 const std::vector<MergeTypeT> &MergeTypes) {
873 if (
Node->ForcedSucc !=
nullptr)
877 for (
const MergeTypeT &MergeType : MergeTypes) {
878 Gain.updateIfLessThan(
879 computeMergeGain(ChainPred, ChainSucc, Jumps,
Offset, MergeType));
884 Gain.updateIfLessThan(
885 computeMergeGain(ChainPred, ChainSucc, Jumps, 0, MergeTypeT::X_Y));
888 for (JumpT *Jump : ChainSucc->Nodes.front()->InJumps) {
889 const NodeT *SrcBlock = Jump->Source;
890 if (SrcBlock->CurChain != ChainPred)
892 size_t Offset = SrcBlock->CurIndex + 1;
893 tryChainMerging(
Offset, {MergeTypeT::X1_Y_X2, MergeTypeT::X2_X1_Y});
897 for (JumpT *Jump : ChainSucc->Nodes.back()->OutJumps) {
898 const NodeT *DstBlock = Jump->Target;
899 if (DstBlock->CurChain != ChainPred)
901 size_t Offset = DstBlock->CurIndex;
902 tryChainMerging(
Offset, {MergeTypeT::X1_Y_X2, MergeTypeT::Y_X2_X1});
911 const NodeT *BB = ChainPred->Nodes[
Offset - 1];
912 const NodeT *BB2 = ChainPred->Nodes[
Offset];
913 if (BB->isSuccessor(BB2))
918 tryChainMerging(
Offset, {MergeTypeT::X1_Y_X2, MergeTypeT::Y_X2_X1,
919 MergeTypeT::X2_X1_Y});
923 Edge->setCachedMergeGain(ChainPred, ChainSucc, Gain);
931 MergeGainT computeMergeGain(
const ChainT *ChainPred,
const ChainT *ChainSucc,
932 const MergedJumpsT &Jumps,
size_t MergeOffset,
933 MergeTypeT MergeType)
const {
934 MergedNodesT MergedNodes =
935 mergeNodes(ChainPred->Nodes, ChainSucc->Nodes, MergeOffset, MergeType);
938 if ((ChainPred->isEntry() || ChainSucc->isEntry()) &&
939 !MergedNodes.getFirstNode()->isEntry())
943 double NewScore = extTSPScore(MergedNodes, Jumps);
944 double CurScore = ChainPred->Score;
945 return MergeGainT(NewScore - CurScore, MergeOffset, MergeType);
950 void mergeChains(ChainT *Into, ChainT *
From,
size_t MergeOffset,
951 MergeTypeT MergeType) {
952 assert(Into !=
From &&
"a chain cannot be merged with itself");
955 MergedNodesT MergedNodes =
956 mergeNodes(Into->Nodes,
From->Nodes, MergeOffset, MergeType);
957 Into->merge(
From, MergedNodes.getNodes());
960 Into->mergeEdges(
From);
964 ChainEdge *SelfEdge = Into->getEdge(Into);
965 if (SelfEdge !=
nullptr) {
966 MergedNodes = MergedNodesT(Into->Nodes.begin(), Into->Nodes.end());
967 MergedJumpsT MergedJumps(&SelfEdge->jumps());
968 Into->Score = extTSPScore(MergedNodes, MergedJumps);
975 for (
auto EdgeIt : Into->Edges)
976 EdgeIt.second->invalidateCache();
980 std::vector<uint64_t> concatChains() {
982 std::vector<const ChainT *> SortedChains;
983 for (ChainT &Chain : AllChains) {
984 if (!Chain.Nodes.empty())
985 SortedChains.push_back(&Chain);
989 std::sort(SortedChains.begin(), SortedChains.end(),
990 [&](
const ChainT *L,
const ChainT *R) {
992 if (L->isEntry() != R->isEntry())
996 return std::make_tuple(-L->density(), L->Id) <
997 std::make_tuple(-R->density(), R->Id);
1001 std::vector<uint64_t> Order;
1002 Order.reserve(NumNodes);
1003 for (
const ChainT *Chain : SortedChains)
1004 for (NodeT *
Node : Chain->Nodes)
1005 Order.push_back(
Node->Index);
1011 const size_t NumNodes;
1014 std::vector<std::vector<uint64_t>> SuccNodes;
1017 std::vector<std::vector<uint64_t>> PredNodes;
1020 std::vector<NodeT> AllNodes;
1023 std::vector<JumpT> AllJumps;
1026 std::vector<ChainT> AllChains;
1029 std::vector<ChainEdge> AllEdges;
1032 std::vector<ChainT *> HotChains;
1043 initialize(NodeSizes, NodeCounts, EdgeCounts, EdgeOffsets);
1047 std::vector<uint64_t>
run() {
1052 return concatChains();
1062 AllNodes.reserve(NumNodes);
1066 AllNodes.emplace_back(
Node,
Size, ExecutionCount);
1067 TotalSamples += ExecutionCount;
1068 if (ExecutionCount > 0)
1073 SuccNodes.resize(NumNodes);
1074 PredNodes.resize(NumNodes);
1075 AllJumps.reserve(EdgeCounts.
size());
1076 for (
size_t I = 0;
I < EdgeCounts.
size();
I++) {
1077 auto [Pred, Succ, Count] = EdgeCounts[
I];
1082 SuccNodes[Pred].push_back(Succ);
1083 PredNodes[Succ].push_back(Pred);
1085 NodeT &PredNode = AllNodes[Pred];
1086 NodeT &SuccNode = AllNodes[Succ];
1087 AllJumps.emplace_back(&PredNode, &SuccNode, Count);
1088 AllJumps.
back().Offset = EdgeOffsets[
I];
1089 SuccNode.InJumps.push_back(&AllJumps.back());
1090 PredNode.OutJumps.push_back(&AllJumps.back());
1092 PredNode.ExecutionCount = std::max(PredNode.ExecutionCount, Count);
1093 SuccNode.ExecutionCount = std::max(SuccNode.ExecutionCount, Count);
1098 AllChains.reserve(NumNodes);
1099 for (NodeT &
Node : AllNodes) {
1101 Node.ExecutionCount = std::max(
Node.ExecutionCount,
Node.inCount());
1102 Node.ExecutionCount = std::max(
Node.ExecutionCount,
Node.outCount());
1104 AllChains.emplace_back(
Node.Index, &
Node);
1105 Node.CurChain = &AllChains.back();
1109 AllEdges.reserve(AllJumps.size());
1110 for (NodeT &PredNode : AllNodes) {
1111 for (JumpT *Jump : PredNode.OutJumps) {
1112 NodeT *SuccNode = Jump->Target;
1113 ChainEdge *CurEdge = PredNode.CurChain->getEdge(SuccNode->CurChain);
1115 if (CurEdge !=
nullptr) {
1116 assert(SuccNode->CurChain->getEdge(PredNode.CurChain) !=
nullptr);
1117 CurEdge->appendJump(Jump);
1121 AllEdges.emplace_back(Jump);
1122 PredNode.CurChain->addEdge(SuccNode->CurChain, &AllEdges.back());
1123 SuccNode->CurChain->addEdge(PredNode.CurChain, &AllEdges.back());
1129 void mergeChainPairs() {
1131 auto GainComparator = [](ChainEdge *
L, ChainEdge *
R) {
1132 return std::make_tuple(-
L->gain(),
L->srcChain()->Id,
L->dstChain()->Id) <
1133 std::make_tuple(-
R->gain(),
R->srcChain()->Id,
R->dstChain()->Id);
1135 std::set<ChainEdge *,
decltype(GainComparator)>
Queue(GainComparator);
1138 [[maybe_unused]]
size_t NumActiveChains = 0;
1139 for (NodeT &
Node : AllNodes) {
1140 if (
Node.ExecutionCount == 0)
1143 for (
const auto &[
_, Edge] :
Node.CurChain->Edges) {
1145 if (Edge->isSelfEdge())
1148 if (Edge->gain() != -1.0)
1152 MergeGainT Gain = getBestMergeGain(Edge);
1153 Edge->setMergeGain(Gain);
1155 if (Edge->gain() > EPS)
1161 while (!
Queue.empty()) {
1163 ChainEdge *BestEdge = *
Queue.begin();
1165 ChainT *BestSrcChain = BestEdge->srcChain();
1166 ChainT *BestDstChain = BestEdge->dstChain();
1169 for (
const auto &[
_, ChainEdge] : BestSrcChain->Edges)
1170 Queue.erase(ChainEdge);
1171 for (
const auto &[
_, ChainEdge] : BestDstChain->Edges)
1172 Queue.erase(ChainEdge);
1175 MergeGainT BestGain = BestEdge->getMergeGain();
1176 mergeChains(BestSrcChain, BestDstChain, BestGain.mergeOffset(),
1177 BestGain.mergeType());
1181 for (
const auto &[
_, Edge] : BestSrcChain->Edges) {
1183 if (Edge->isSelfEdge())
1185 if (Edge->srcChain()->numBlocks() + Edge->dstChain()->numBlocks() >
1190 MergeGainT Gain = getBestMergeGain(Edge);
1191 Edge->setMergeGain(Gain);
1193 if (Edge->gain() > EPS)
1198 LLVM_DEBUG(
dbgs() <<
"Cache-directed function sorting reduced the number"
1199 <<
" of chains from " << NumNodes <<
" to "
1200 << NumActiveChains <<
"\n");
1209 MergeGainT getBestMergeGain(ChainEdge *Edge)
const {
1210 assert(!Edge->jumps().empty() &&
"trying to merge chains w/o jumps");
1212 MergedJumpsT Jumps(&Edge->jumps());
1213 ChainT *SrcChain = Edge->srcChain();
1214 ChainT *DstChain = Edge->dstChain();
1217 MergeGainT Gain = MergeGainT();
1221 auto tryChainMerging = [&](
const std::vector<MergeTypeT> &MergeTypes) {
1224 for (
const MergeTypeT &MergeType : MergeTypes) {
1225 MergeGainT NewGain =
1226 computeMergeGain(SrcChain, DstChain, Jumps, MergeType);
1230 if (std::abs(Gain.score() - NewGain.score()) < EPS) {
1231 if ((MergeType == MergeTypeT::X_Y && SrcChain->Id < DstChain->Id) ||
1232 (MergeType == MergeTypeT::Y_X && SrcChain->Id > DstChain->Id)) {
1235 }
else if (NewGain.score() > Gain.score() + EPS) {
1242 tryChainMerging({MergeTypeT::X_Y, MergeTypeT::Y_X});
1250 MergeGainT computeMergeGain(ChainT *ChainPred, ChainT *ChainSucc,
1251 const MergedJumpsT &Jumps,
1252 MergeTypeT MergeType)
const {
1254 double FreqGain = freqBasedLocalityGain(ChainPred, ChainSucc);
1257 size_t MergeOffset = 0;
1259 mergeNodes(ChainPred->Nodes, ChainSucc->Nodes, MergeOffset, MergeType);
1260 double DistGain = distBasedLocalityGain(MergedBlocks, Jumps);
1262 double GainScore = DistGain +
Config.FrequencyScale * FreqGain;
1264 if (GainScore >= 0.0)
1265 GainScore /= std::min(ChainPred->Size, ChainSucc->Size);
1267 return MergeGainT(GainScore, MergeOffset, MergeType);
1271 double freqBasedLocalityGain(ChainT *ChainPred, ChainT *ChainSucc)
const {
1272 auto missProbability = [&](
double ChainDensity) {
1273 double PageSamples = ChainDensity *
Config.CacheSize;
1274 if (PageSamples >= TotalSamples)
1276 double P = PageSamples / TotalSamples;
1277 return pow(1.0 -
P,
static_cast<double>(
Config.CacheEntries));
1282 ChainPred->ExecutionCount * missProbability(ChainPred->density()) +
1283 ChainSucc->ExecutionCount * missProbability(ChainSucc->density());
1286 double MergedCounts = ChainPred->ExecutionCount + ChainSucc->ExecutionCount;
1287 double MergedSize = ChainPred->Size + ChainSucc->Size;
1288 double MergedDensity =
static_cast<double>(MergedCounts) / MergedSize;
1289 double NewScore = MergedCounts * missProbability(MergedDensity);
1291 return CurScore - NewScore;
1296 uint64_t Dist = SrcAddr <= DstAddr ? DstAddr - SrcAddr : SrcAddr - DstAddr;
1297 double D = Dist == 0 ? 0.1 :
static_cast<double>(Dist);
1298 return static_cast<double>(Count) * std::pow(
D, -
Config.DistancePower);
1302 double distBasedLocalityGain(
const MergedNodesT &Nodes,
1303 const MergedJumpsT &Jumps)
const {
1305 Nodes.forEach([&](
const NodeT *
Node) {
1306 Node->EstimatedAddr = CurAddr;
1307 CurAddr +=
Node->Size;
1310 double CurScore = 0;
1311 double NewScore = 0;
1312 Jumps.forEach([&](
const JumpT *Jump) {
1313 uint64_t SrcAddr = Jump->Source->EstimatedAddr + Jump->Offset;
1314 uint64_t DstAddr = Jump->Target->EstimatedAddr;
1315 NewScore += distScore(SrcAddr, DstAddr, Jump->ExecutionCount);
1316 CurScore += distScore(0, TotalSize, Jump->ExecutionCount);
1318 return NewScore - CurScore;
1323 void mergeChains(ChainT *Into, ChainT *
From,
size_t MergeOffset,
1324 MergeTypeT MergeType) {
1325 assert(Into !=
From &&
"a chain cannot be merged with itself");
1328 MergedNodesT MergedNodes =
1329 mergeNodes(Into->Nodes,
From->Nodes, MergeOffset, MergeType);
1330 Into->merge(
From, MergedNodes.getNodes());
1333 Into->mergeEdges(
From);
1338 std::vector<uint64_t> concatChains() {
1340 std::vector<const ChainT *> SortedChains;
1342 for (ChainT &Chain : AllChains) {
1343 if (!Chain.Nodes.empty()) {
1344 SortedChains.push_back(&Chain);
1347 double ExecutionCount = 0;
1348 for (NodeT *
Node : Chain.Nodes) {
1349 Size +=
static_cast<double>(
Node->Size);
1350 ExecutionCount +=
static_cast<double>(
Node->ExecutionCount);
1353 ChainDensity[&Chain] = ExecutionCount /
Size;
1358 std::sort(SortedChains.begin(), SortedChains.end(),
1359 [&](
const ChainT *L,
const ChainT *R) {
1360 const double DL = ChainDensity[L];
1361 const double DR = ChainDensity[R];
1363 return std::make_tuple(-DL, L->Id) <
1364 std::make_tuple(-DR, R->Id);
1368 std::vector<uint64_t> Order;
1369 Order.reserve(NumNodes);
1370 for (
const ChainT *Chain : SortedChains)
1371 for (NodeT *
Node : Chain->Nodes)
1372 Order.push_back(
Node->Index);
1381 const size_t NumNodes;
1384 std::vector<std::vector<uint64_t>> SuccNodes;
1387 std::vector<std::vector<uint64_t>> PredNodes;
1390 std::vector<NodeT> AllNodes;
1393 std::vector<JumpT> AllJumps;
1396 std::vector<ChainT> AllChains;
1399 std::vector<ChainEdge> AllEdges;
1410std::vector<uint64_t>
1415 assert(NodeCounts.
size() == NodeSizes.
size() &&
"Incorrect input");
1416 assert(NodeSizes.
size() > 2 &&
"Incorrect input");
1419 ExtTSPImpl Alg(NodeSizes, NodeCounts, EdgeCounts);
1420 std::vector<uint64_t> Result = Alg.run();
1423 assert(Result.front() == 0 &&
"Original entry point is not preserved");
1424 assert(Result.size() == NodeSizes.
size() &&
"Incorrect size of layout");
1433 std::vector<uint64_t>
Addr(NodeSizes.
size(), 0);
1437 std::vector<uint64_t> OutDegree(NodeSizes.
size(), 0);
1438 for (
auto Edge : EdgeCounts)
1439 ++OutDegree[Edge.src];
1443 for (
auto Edge : EdgeCounts) {
1444 bool IsConditional = OutDegree[Edge.src] > 1;
1445 Score += ::extTSPScore(
Addr[Edge.src], NodeSizes[Edge.src],
Addr[Edge.dst],
1446 Edge.count, IsConditional);
1454 std::vector<uint64_t> Order(NodeSizes.
size());
1466 assert(FuncCounts.
size() == FuncSizes.
size() &&
"Incorrect input");
1469 CDSortImpl Alg(
Config, FuncSizes, FuncCounts, CallCounts, CallOffsets);
1470 std::vector<uint64_t> Result = Alg.run();
1471 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< unsigned > CacheSize("cdsort-cache-size", cl::ReallyHidden, cl::desc("The size of a line in the cache"))
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 > FrequencyScale("cdsort-frequency-scale", cl::ReallyHidden, cl::desc("The scale factor for the frequency-based locality"))
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< double > DistancePower("cdsort-distance-power", cl::ReallyHidden, cl::desc("The power exponent for the distance-based locality"))
static cl::opt< unsigned > MaxChainSize("ext-tsp-max-chain-size", cl::ReallyHidden, cl::init(512), cl::desc("The maximum size of a chain to create"))
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< 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< 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< unsigned > CDMaxChainSize("cdsort-max-chain-size", cl::ReallyHidden, cl::desc("The maximum size of a chain to create"))
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< unsigned > CacheEntries("cdsort-cache-entries", cl::ReallyHidden, cl::desc("The size of the cache"))
static cl::opt< double > MaxMergeDensityRatio("ext-tsp-max-merge-density-ratio", cl::ReallyHidden, cl::init(100), cl::desc("The maximum ratio between densities of two chains for merging"))
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
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
cl::opt< bool > EnableExtTspBlockPlacement
Algorithm-specific params for Cache-Directed Sort.