27 bool IndirectCall =
false) {
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))
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)
107 assert(IBBs.size() == BBFreqs.
size() &&
"BB Count Mismatch");
110 [](decltype(BBFreqs)::const_reference BBF,
111 decltype(BBFreqs)::const_reference BBS) {
112 return BBF.second > BBS.second ?
true :
false;
116 auto Topk = numBBToGet(BBFreqs.
size());
118 for (
size_t i = 0; i < Topk; i++)
121 assert(!Calles.
empty() &&
"Running Analysis on Function with no calls?");
125 return CallerAndCalles;
129 std::size_t SequenceBBQuery::getHottestBlocks(std::size_t TotalBlocks) {
130 if (TotalBlocks == 1)
132 return TotalBlocks / 2;
137 SequenceBBQuery::rearrangeBB(
const Function &
F,
const BlockListTy &BBList) {
140 for (
auto &Block :
F.getBasicBlockList())
142 RearrangedBBSet.push_back(&Block);
144 assert(RearrangedBBSet.size() == BBList.size() &&
145 "BasicBlock missing while rearranging?");
146 return RearrangedBBSet;
149 void SequenceBBQuery::traverseToEntryBlock(
const BasicBlock *AtBB,
150 const BlockListTy &CallerBlocks,
151 const BackEdgesInfoTy &BackEdgesInfo,
153 VisitedBlocksInfoTy &VisitedBlocks) {
154 auto Itr = VisitedBlocks.find(AtBB);
155 if (Itr != VisitedBlocks.end()) {
156 if (!Itr->second.Upward)
158 Itr->second.Upward =
false;
161 WalkDirection BlockHint;
162 BlockHint.Upward =
false;
165 BlockHint.CallerBlock =
true;
166 VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));
180 for (
auto &
I : BackEdgesInfo)
181 if (
I.second == AtBB)
185 for (; PIt != EIt; ++PIt)
188 traverseToEntryBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,
192 void SequenceBBQuery::traverseToExitBlock(
const BasicBlock *AtBB,
193 const BlockListTy &CallerBlocks,
194 const BackEdgesInfoTy &BackEdgesInfo,
196 VisitedBlocksInfoTy &VisitedBlocks) {
197 auto Itr = VisitedBlocks.find(AtBB);
198 if (Itr != VisitedBlocks.end()) {
199 if (!Itr->second.Downward)
201 Itr->second.Downward =
false;
204 WalkDirection BlockHint;
205 BlockHint.Downward =
false;
208 BlockHint.CallerBlock =
true;
209 VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));
221 for (
auto &
I : BackEdgesInfo)
223 SuccSkipNodes.
insert(
I.second);
225 for (; PIt != EIt; ++PIt)
227 traverseToExitBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI,
235 SequenceBBQuery::queryCFG(
Function &
F,
const BlockListTy &CallerBlocks) {
249 for (
const auto I : CallerBlocks)
250 BBFreqs.push_back({
I,
BFI.getBlockFreq(
I).getFrequency()});
252 llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference Bbf,
253 decltype(BBFreqs)::const_reference Bbs) {
254 return Bbf.second > Bbs.second;
259 HotBlocksRef.drop_back(BBFreqs.size() - getHottestBlocks(BBFreqs.size()));
268 for (
auto I : HotBlocksRef) {
269 traverseToEntryBlock(
I.first, CallerBlocks, BackEdgesInfo, BPI,
271 traverseToExitBlock(
I.first, CallerBlocks, BackEdgesInfo, BPI,
276 for (
auto &
I : VisitedBlocks)
277 if (
I.second.CallerBlock)
278 MinCallerBlocks.push_back(
std::move(
I.first));
280 return rearrangeBB(
F, MinCallerBlocks);
290 CallerBlocks = findBBwithCalls(
F);
291 if (CallerBlocks.
empty())
295 SequencedBlocks = rearrangeBB(
F, CallerBlocks);
297 SequencedBlocks = queryCFG(
F, CallerBlocks);
299 for (
auto BB : SequencedBlocks)
303 return CallerAndCalles;
reference emplace_back(ArgTypes &&... Args)
Interfaces for registering analysis passes, producing common pass manager configurations,...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
This class represents lattice values for constants.
LLVM_NODISCARD bool empty() const
Implements a dense probed hash-table based set.
void push_back(const T &Elt)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
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...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
SmallVector< const BasicBlock *, 8 > BlockListTy
SmallVector< std::pair< const BasicBlock *, uint64_t >, 8 > BlockFreqInfoTy
This class provides access to building LLVM's passes.
void findCalles(const BasicBlock *, DenseSet< StringRef > &)
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...
Analysis pass which computes BranchProbabilityInfo.
ResultTy operator()(Function &F)
bool isStraightLine(const Function &F)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Interval::succ_iterator succ_end(Interval *I)
ResultTy operator()(Function &F)
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=false) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
LLVM Basic Block Representation.
std::pair< iterator, bool > insert(const ValueT &V)
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...
void registerFunctionAnalyses(FunctionAnalysisManager &FAM)
Registers all available function analysis passes.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Interval::pred_iterator pred_end(Interval *I)
void sort(IteratorTy Start, IteratorTy End)
Analysis pass which computes BlockFrequencyInfo.
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.
DenseMap< const BasicBlock *, WalkDirection > VisitedBlocksInfoTy
SmallVector< std::pair< const BasicBlock *, const BasicBlock * >, 8 > BackEdgesInfoTy
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static const Function * getCalledFunction(const Value *V, bool LookThroughBitCast, bool &IsNoBuiltin)
Analysis providing branch probability information.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const
Test if an edge is hot relative to other out-edges of the Src.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.