31 if (
auto Call = dyn_cast<CallBase>(&
I))
37 if (findCallInst(*BB.getTerminator()) ||
38 llvm::any_of(BB.instructionsWithoutDebug(), findCallInst))
54 assert(BB !=
nullptr &&
"Traversing Null BB to find calls?");
57 auto CalledValue = Call->getCalledOperand()->stripPointerCasts();
58 if (
auto DirectCall = dyn_cast<Function>(CalledValue))
62 if (
auto CI = dyn_cast<CallInst>(&
I))
77size_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?");
122 CallerAndCalles.
insert({
F.getName(), std::move(Calles)});
124 return CallerAndCalles;
128std::size_t SequenceBBQuery::getHottestBlocks(std::size_t TotalBlocks) {
129 if (TotalBlocks == 1)
131 return TotalBlocks / 2;
136SequenceBBQuery::rearrangeBB(
const Function &
F,
const BlockListTy &BBList) {
141 RearrangedBBSet.push_back(&
Block);
143 assert(RearrangedBBSet.size() == BBList.size() &&
144 "BasicBlock missing while rearranging?");
145 return RearrangedBBSet;
148void 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,
191void 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,
234SequenceBBQuery::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 (
const auto *BB : SequencedBlocks)
301 CallerAndCalles.
insert({
F.getName(), std::move(Calles)});
302 return CallerAndCalles;
This file defines the DenseMap class.
static const Function * getCalledFunction(const Value *V, bool &IsNoBuiltin)
FunctionAnalysisManager FAM
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Contains the Analyses and Result Interpretation to select likely functions to Speculatively compile b...
A container for analyses that lazily runs them and caches their results.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Analysis pass which computes BlockFrequencyInfo.
Analysis pass which computes BranchProbabilityInfo.
Analysis providing branch probability information.
bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const
Test if an edge is hot relative to other out-edges of the Src.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
This class provides access to building LLVM's passes.
void registerFunctionAnalyses(FunctionAnalysisManager &FAM)
Registers all available function analysis passes.
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
ResultTy operator()(Function &F)
ResultTy operator()(Function &F)
SmallVector< std::pair< const BasicBlock *, uint64_t >, 8 > BlockFreqInfoTy
DenseMap< const BasicBlock *, WalkDirection > VisitedBlocksInfoTy
SmallVector< std::pair< const BasicBlock *, const BasicBlock * >, 8 > BackEdgesInfoTy
SmallVector< const BasicBlock *, 8 > BlockListTy
std::optional< DenseMap< StringRef, DenseSet< StringRef > > > ResultTy
bool isStraightLine(const Function &F)
void findCalles(const BasicBlock *, DenseSet< StringRef > &)
Interfaces for registering analysis passes, producing common pass manager configurations,...
This is an optimization pass for GlobalISel generic memory operations.
Interval::succ_iterator succ_end(Interval *I)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Interval::pred_iterator pred_end(Interval *I)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void sort(IteratorTy Start, IteratorTy End)
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock * > > &Result)
Analyze the specified function to find all of the loop backedges in the function and return them.