27 bool IndirectCall =
false) {
31 if (
auto Call = dyn_cast<CallBase>(&
I))
37 if (findCallInst(*
BB.getTerminator()) ||
54 assert(
BB !=
nullptr &&
"Traversing Null BB to find calls?");
57 auto CalledValue = Call->getCalledOperand()->stripPointerCasts();
58 if (
auto DirectCall = dyn_cast<Function>(CalledValue))
61 for (
auto &
I :
BB->instructionsWithoutDebug())
62 if (
auto CI = dyn_cast<CallInst>(&
I))
65 if (
auto II = dyn_cast<InvokeInst>(
BB->getTerminator()))
71 return BB.getSingleSuccessor() != nullptr;
77 size_t BlockFreqQuery::numBBToGet(
size_t numBB) {
85 return (numBB / 2) + (numBB / 4);
97 auto IBBs = findBBwithCalls(
F);
104 for (
const auto I : IBBs)
105 BBFreqs.push_back({
I,
BFI.getBlockFreq(
I).getFrequency()});
107 assert(IBBs.size() == BBFreqs.size() &&
"BB Count Mismatch");
109 llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference BBF,
110 decltype(BBFreqs)::const_reference BBS) {
111 return BBF.second > BBS.second ?
true :
false;
115 auto Topk = numBBToGet(BBFreqs.size());
117 for (
size_t i = 0;
i < Topk;
i++)
120 assert(!Calles.
empty() &&
"Running Analysis on Function with no calls?");
124 return CallerAndCalles;
128 std::size_t SequenceBBQuery::getHottestBlocks(std::size_t TotalBlocks) {
129 if (TotalBlocks == 1)
131 return TotalBlocks / 2;
136 SequenceBBQuery::rearrangeBB(
const Function &
F,
const BlockListTy &BBList) {
139 for (
auto &Block :
F.getBasicBlockList())
141 RearrangedBBSet.push_back(&Block);
143 assert(RearrangedBBSet.size() == BBList.size() &&
144 "BasicBlock missing while rearranging?");
145 return RearrangedBBSet;
148 void SequenceBBQuery::traverseToEntryBlock(
const BasicBlock *AtBB,
149 const BlockListTy &CallerBlocks,
150 const BackEdgesInfoTy &BackEdgesInfo,
152 VisitedBlocksInfoTy &VisitedBlocks) {
153 auto Itr = VisitedBlocks.find(AtBB);
154 if (Itr != VisitedBlocks.end()) {
155 if (!Itr->second.Upward)
157 Itr->second.Upward =
false;
160 WalkDirection BlockHint;
161 BlockHint.Upward =
false;
164 BlockHint.CallerBlock =
true;
165 VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));
179 for (
auto &
I : BackEdgesInfo)
180 if (
I.second == AtBB)
184 for (; PIt != EIt; ++PIt)
187 traverseToEntryBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,
191 void SequenceBBQuery::traverseToExitBlock(
const BasicBlock *AtBB,
192 const BlockListTy &CallerBlocks,
193 const BackEdgesInfoTy &BackEdgesInfo,
195 VisitedBlocksInfoTy &VisitedBlocks) {
196 auto Itr = VisitedBlocks.find(AtBB);
197 if (Itr != VisitedBlocks.end()) {
198 if (!Itr->second.Downward)
200 Itr->second.Downward =
false;
203 WalkDirection BlockHint;
204 BlockHint.Downward =
false;
207 BlockHint.CallerBlock =
true;
208 VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));
220 for (
auto &
I : BackEdgesInfo)
222 SuccSkipNodes.
insert(
I.second);
224 for (; PIt != EIt; ++PIt)
226 traverseToExitBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,
234 SequenceBBQuery::queryCFG(
Function &
F,
const BlockListTy &CallerBlocks) {
248 for (
const auto I : CallerBlocks)
249 BBFreqs.push_back({
I,
BFI.getBlockFreq(
I).getFrequency()});
251 llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference Bbf,
252 decltype(BBFreqs)::const_reference Bbs) {
253 return Bbf.second > Bbs.second;
258 HotBlocksRef.drop_back(BBFreqs.size() - getHottestBlocks(BBFreqs.size()));
267 for (
auto I : HotBlocksRef) {
268 traverseToEntryBlock(
I.first, CallerBlocks, BackEdgesInfo, BPI,
270 traverseToExitBlock(
I.first, CallerBlocks, BackEdgesInfo, BPI,
275 for (
auto &
I : VisitedBlocks)
276 if (
I.second.CallerBlock)
277 MinCallerBlocks.push_back(
std::move(
I.first));
279 return rearrangeBB(
F, MinCallerBlocks);
289 CallerBlocks = findBBwithCalls(
F);
290 if (CallerBlocks.empty())
294 SequencedBlocks = rearrangeBB(
F, CallerBlocks);
296 SequencedBlocks = queryCFG(
F, CallerBlocks);
298 for (
auto BB : SequencedBlocks)
302 return CallerAndCalles;