Go to the documentation of this file.
14 #ifndef LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H
15 #define LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H
28 class MachineBasicBlock;
29 class MachineFunction;
31 namespace afdo_detail {
33 template <
class BlockT>
struct TypeMap {};
87 using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
95 :
F(
F), Successors(Successors), SampleBlockWeights(SampleBlockWeights) {}
104 void findUnlikelyJumps(
const std::vector<const BasicBlockT *> &BasicBlocks,
120 template <
typename BT>
132 for (
const auto &
BB :
F) {
142 std::vector<const BasicBlockT *> BasicBlocks;
144 BasicBlocks.reserve(Reachable.
size());
145 for (
const auto &
BB :
F) {
147 BlockIndex[&
BB] = BasicBlocks.
size();
148 BasicBlocks.push_back(&
BB);
152 BlockWeights.
clear();
154 bool HasSamples =
false;
155 for (
const auto *
BB : BasicBlocks) {
156 auto It = SampleBlockWeights.find(
BB);
157 if (It != SampleBlockWeights.end() && It->second > 0) {
159 BlockWeights[
BB] = It->second;
163 if (BasicBlocks.size() <= 1 || !HasSamples) {
169 Func.Blocks.reserve(BasicBlocks.size());
171 for (
const auto *
BB : BasicBlocks) {
173 if (SampleBlockWeights.find(
BB) != SampleBlockWeights.end()) {
174 Block.UnknownWeight =
false;
175 Block.Weight = SampleBlockWeights[
BB];
177 Block.UnknownWeight =
true;
180 Block.Index = Func.Blocks.size();
181 Func.Blocks.push_back(Block);
184 for (
const auto *
BB : BasicBlocks) {
185 for (
auto *Succ : Successors[
BB]) {
186 if (!BlockIndex.
count(Succ))
190 Jump.
Target = BlockIndex[Succ];
191 Func.Jumps.push_back(Jump);
193 Func.Blocks[BlockIndex[
BB]].HasSelfEdge =
true;
197 for (
auto &Jump : Func.Jumps) {
198 Func.Blocks[Jump.Source].SuccJumps.push_back(&Jump);
199 Func.Blocks[Jump.Target].PredJumps.push_back(&Jump);
203 findUnlikelyJumps(BasicBlocks, Successors, Func);
206 for (
size_t I = 0;
I < Func.Blocks.size();
I++) {
207 if (Func.Blocks[
I].isEntry()) {
219 for (
const auto *
BB : BasicBlocks) {
220 BlockWeights[
BB] = Func.Blocks[BlockIndex[
BB]].Flow;
222 for (
auto &Jump : Func.Jumps) {
223 Edge E = std::make_pair(BasicBlocks[Jump.Source], BasicBlocks[Jump.Target]);
224 EdgeWeights[
E] = Jump.Flow;
229 for (
auto &
I : BlockWeights) {
233 for (
auto &
I : EdgeWeights) {
237 InverseReachable.
contains(
I.first.second));
242 template <
typename BT>
244 const std::vector<const BasicBlockT *> &BasicBlocks,
248 inline void SampleProfileInference<BasicBlock>::findUnlikelyJumps(
249 const std::vector<const BasicBlockT *> &BasicBlocks,
250 BlockEdgeMap &Successors, FlowFunction &Func) {
251 for (
auto &Jump : Func.Jumps) {
252 const auto *
BB = BasicBlocks[Jump.Source];
253 const auto *Succ = BasicBlocks[Jump.Target];
254 const Instruction *TI =
BB->getTerminator();
257 if (Successors[
BB].
size() == 2 && Successors[
BB].back() == Succ) {
258 if (isa<InvokeInst>(TI)) {
259 Jump.IsUnlikely =
true;
262 const Instruction *SuccTI = Succ->getTerminator();
264 if (SuccTI->getNumSuccessors() == 0) {
265 if (isa<UnreachableInst>(SuccTI)) {
266 Jump.IsUnlikely =
true;
272 template <
typename BT>
273 inline bool SampleProfileInference<BT>::isExit(
const BasicBlockT *
BB) {
274 return BB->succ_empty();
278 inline bool SampleProfileInference<BasicBlock>::isExit(
const BasicBlock *
BB) {
283 #endif // LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H
void applyFlowInference(FlowFunction &Func)
Apply the profile inference algorithm for a given flow function.
This is an optimization pass for GlobalISel generic memory operations.
void apply(BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights)
Apply the profile inference algorithm for a given function.
uint64_t Entry
The index of the entry block.
std::vector< FlowJump > Jumps
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool succ_empty(const Instruction *I)
LLVM Basic Block Representation.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
typename afdo_detail::TypeMap< BT >::BasicBlockT BasicBlockT
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
A wrapper of a binary basic block.
bool isExit() const
Check if it is an exit block in the function.
DenseMap< const BasicBlockT *, uint64_t > BlockWeightMap
SampleProfileInference(FunctionT &F, BlockEdgeMap &Successors, BlockWeightMap &SampleBlockWeights)
typename afdo_detail::TypeMap< BT >::FunctionT FunctionT
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
@ BasicBlock
Various leaf nodes.
DenseMap< const BasicBlockT *, SmallVector< const BasicBlockT *, 8 > > BlockEdgeMap
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
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.
std::pair< const BasicBlockT *, const BasicBlockT * > Edge
std::vector< FlowBlock > Blocks
A wrapper of binary function with basic blocks and jumps.
Sample profile inference pass.
bool isEntry() const
Check if it is the entry block in the function.
std::vector< FlowJump * > SuccJumps
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
iterator_range< idf_ext_iterator< T, SetTy > > inverse_depth_first_ext(const T &G, SetTy &S)
bool contains(ConstPtrType Ptr) const
std::vector< FlowJump * > PredJumps
DenseMap< Edge, uint64_t > EdgeWeightMap
A wrapper of a jump between two basic blocks.