28 if (
auto Call = dyn_cast<CallBase>(&
I))
34 if (findCallInst(*BB.getTerminator()) ||
35 llvm::any_of(BB.instructionsWithoutDebug(), findCallInst))
51 assert(BB !=
nullptr &&
"Traversing Null BB to find calls?");
54 auto CalledValue = Call->getCalledOperand()->stripPointerCasts();
55 if (
auto DirectCall = dyn_cast<Function>(CalledValue))
59 if (
auto CI = dyn_cast<CallInst>(&
I))
74size_t BlockFreqQuery::numBBToGet(
size_t numBB) {
82 return (numBB / 2) + (numBB / 4);
94 auto IBBs = findBBwithCalls(
F);
101 for (
const auto I : IBBs)
102 BBFreqs.
push_back({
I, BFI.getBlockFreq(
I).getFrequency()});
104 assert(IBBs.size() == BBFreqs.
size() &&
"BB Count Mismatch");
106 llvm::sort(BBFreqs, [](
decltype(BBFreqs)::const_reference BBF,
107 decltype(BBFreqs)::const_reference BBS) {
108 return BBF.second > BBS.second ?
true :
false;
112 auto Topk = numBBToGet(BBFreqs.
size());
114 for (
size_t i = 0; i < Topk; i++)
117 assert(!Calles.
empty() &&
"Running Analysis on Function with no calls?");
119 CallerAndCalles.
insert({
F.getName(), std::move(Calles)});
121 return CallerAndCalles;
125std::size_t SequenceBBQuery::getHottestBlocks(std::size_t TotalBlocks) {
126 if (TotalBlocks == 1)
128 return TotalBlocks / 2;
133SequenceBBQuery::rearrangeBB(
const Function &
F,
const BlockListTy &BBList) {
138 RearrangedBBSet.push_back(&
Block);
140 assert(RearrangedBBSet.size() == BBList.size() &&
141 "BasicBlock missing while rearranging?");
142 return RearrangedBBSet;
145void SequenceBBQuery::traverseToEntryBlock(
const BasicBlock *AtBB,
146 const BlockListTy &CallerBlocks,
147 const BackEdgesInfoTy &BackEdgesInfo,
149 VisitedBlocksInfoTy &VisitedBlocks) {
150 auto Itr = VisitedBlocks.find(AtBB);
151 if (Itr != VisitedBlocks.end()) {
152 if (!Itr->second.Upward)
154 Itr->second.Upward =
false;
157 WalkDirection BlockHint;
158 BlockHint.Upward =
false;
161 BlockHint.CallerBlock =
true;
162 VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));
176 for (
auto &
I : BackEdgesInfo)
177 if (
I.second == AtBB)
181 for (; PIt != EIt; ++PIt)
184 traverseToEntryBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,
188void SequenceBBQuery::traverseToExitBlock(
const BasicBlock *AtBB,
189 const BlockListTy &CallerBlocks,
190 const BackEdgesInfoTy &BackEdgesInfo,
192 VisitedBlocksInfoTy &VisitedBlocks) {
193 auto Itr = VisitedBlocks.find(AtBB);
194 if (Itr != VisitedBlocks.end()) {
195 if (!Itr->second.Downward)
197 Itr->second.Downward =
false;
200 WalkDirection BlockHint;
201 BlockHint.Downward =
false;
204 BlockHint.CallerBlock =
true;
205 VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));
217 for (
auto &
I : BackEdgesInfo)
219 SuccSkipNodes.
insert(
I.second);
221 for (; PIt != EIt; ++PIt)
223 traverseToExitBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,
231SequenceBBQuery::queryCFG(
Function &
F,
const BlockListTy &CallerBlocks) {
245 for (
const auto I : CallerBlocks)
246 BBFreqs.push_back({
I,
BFI.getBlockFreq(
I).getFrequency()});
248 llvm::sort(BBFreqs, [](
decltype(BBFreqs)::const_reference Bbf,
249 decltype(BBFreqs)::const_reference Bbs) {
250 return Bbf.second > Bbs.second;
255 HotBlocksRef.drop_back(BBFreqs.size() - getHottestBlocks(BBFreqs.size()));
264 for (
auto I : HotBlocksRef) {
265 traverseToEntryBlock(
I.first, CallerBlocks, BackEdgesInfo, BPI,
267 traverseToExitBlock(
I.first, CallerBlocks, BackEdgesInfo, BPI,
272 for (
auto &
I : VisitedBlocks)
273 if (
I.second.CallerBlock)
274 MinCallerBlocks.push_back(std::move(
I.first));
276 return rearrangeBB(
F, MinCallerBlocks);
286 CallerBlocks = findBBwithCalls(
F);
287 if (CallerBlocks.
empty())
291 SequencedBlocks = rearrangeBB(
F, CallerBlocks);
293 SequencedBlocks = queryCFG(
F, CallerBlocks);
295 for (
const auto *BB : SequencedBlocks)
298 CallerAndCalles.
insert({
F.getName(), std::move(Calles)});
299 return CallerAndCalles;
This file defines the DenseMap class.
This header defines various interfaces for pass management in LLVM.
static const Function * getCalledFunction(const Value *V)
uint64_t IntrinsicInst * II
FunctionAnalysisManager FAM
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
auto pred_end(const MachineBasicBlock *BB)
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)
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
auto pred_begin(const MachineBasicBlock *BB)
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.