15#include "llvm/Config/llvm-config.h"
32#define DEBUG_TYPE "stack-lifetime"
36 const auto IT = AllocaNumbering.find(AI);
38 return LiveRanges[
IT->second];
42 return BlockInstRange.contains(
I->getParent());
48 auto ItBB = BlockInstRange.find(BB);
49 assert(ItBB != BlockInstRange.end() &&
"Unreachable is not expected");
52 auto It = std::upper_bound(Instructions.begin() + ItBB->getSecond().first + 1,
53 Instructions.begin() + ItBB->getSecond().second,
I,
55 return L->comesBefore(R);
58 unsigned InstNum = It - Instructions.begin();
62void StackLifetime::collectMarkers() {
63 InterestingAllocas.
resize(NumAllocas);
71 if (!
II || !
II->isLifetimeStartOrEnd())
76 auto It = AllocaNumbering.find(AI);
77 if (It == AllocaNumbering.end())
79 auto AllocaNo = It->second;
80 bool IsStart =
II->getIntrinsicID() == Intrinsic::lifetime_start;
82 InterestingAllocas.
set(AllocaNo);
83 BBMarkerSet[BB][
II] = {AllocaNo, IsStart};
96 LLVM_DEBUG(
dbgs() <<
" " << Instructions.size() <<
": BB " << BB->getName()
98 auto BBStart = Instructions.size();
99 Instructions.push_back(
nullptr);
101 BlockLifetimeInfo &BlockInfo =
102 BlockLiveness.try_emplace(BB, NumAllocas).first->getSecond();
104 auto &BlockMarkerSet = BBMarkerSet[BB];
105 if (BlockMarkerSet.empty()) {
106 BlockInstRange[BB] = std::make_pair(BBStart, Instructions.size());
110 auto ProcessMarker = [&](
const IntrinsicInst *
I,
const Marker &
M) {
112 << (
M.IsStart ?
"start " :
"end ") <<
M.AllocaNo
113 <<
", " << *
I <<
"\n");
115 BBMarkers[BB].push_back({Instructions.size(),
M});
116 Instructions.push_back(
I);
119 BlockInfo.End.reset(
M.AllocaNo);
120 BlockInfo.Begin.set(
M.AllocaNo);
122 BlockInfo.Begin.reset(
M.AllocaNo);
123 BlockInfo.End.set(
M.AllocaNo);
127 if (BlockMarkerSet.size() == 1) {
128 ProcessMarker(BlockMarkerSet.begin()->getFirst(),
129 BlockMarkerSet.begin()->getSecond());
132 for (
const Instruction &
I : *BB) {
136 auto It = BlockMarkerSet.find(
II);
137 if (It == BlockMarkerSet.end())
139 ProcessMarker(
II, It->getSecond());
143 BlockInstRange[BB] = std::make_pair(BBStart, Instructions.size());
147void StackLifetime::calculateLocalLiveness() {
159 BlockLifetimeInfo &BlockInfo = BlockLiveness.find(BB)->getSecond();
166 if (
I == BlockLiveness.end())
168 BitsIn |=
I->second.LiveOut;
173 BitsIn.
resize(NumAllocas,
true);
176 if (!BitsIn.
subsetOf(BlockInfo.LiveIn)) {
177 BlockInfo.LiveIn |= BitsIn;
189 BitsIn.
reset(BlockInfo.End);
191 BitsIn |= BlockInfo.Begin;
194 BitsIn.
reset(BlockInfo.Begin);
196 BitsIn |= BlockInfo.End;
201 if (!BitsIn.
subsetOf(BlockInfo.LiveOut)) {
203 BlockInfo.LiveOut |= BitsIn;
210 for (
auto &[BB, BlockInfo] : BlockLiveness) {
211 BlockInfo.LiveIn.flip();
212 BlockInfo.LiveOut.flip();
217void StackLifetime::calculateLiveIntervals() {
218 for (
auto IT : BlockLiveness) {
220 BlockLifetimeInfo &BlockInfo =
IT.getSecond();
221 unsigned BBStart, BBEnd;
222 std::tie(BBStart, BBEnd) = BlockInstRange[BB];
224 BitVector Started, Ended;
225 Started.
resize(NumAllocas);
227 SmallVector<unsigned, 8>
Start;
228 Start.resize(NumAllocas);
231 for (
unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
232 if (BlockInfo.LiveIn.test(AllocaNo)) {
233 Started.
set(AllocaNo);
234 Start[AllocaNo] = BBStart;
238 for (
auto &It : BBMarkers[BB]) {
239 unsigned InstNo = It.first;
240 bool IsStart = It.second.IsStart;
241 unsigned AllocaNo = It.second.AllocaNo;
244 if (!Started.
test(AllocaNo)) {
245 Started.
set(AllocaNo);
246 Ended.
reset(AllocaNo);
247 Start[AllocaNo] = InstNo;
250 if (Started.
test(AllocaNo)) {
251 LiveRanges[AllocaNo].addRange(Start[AllocaNo], InstNo);
252 Started.
reset(AllocaNo);
258 for (
unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
259 if (Started.
test(AllocaNo))
260 LiveRanges[AllocaNo].addRange(Start[AllocaNo], BBEnd);
264#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
266 dbgs() <<
"Allocas:\n";
267 for (
unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
268 dbgs() <<
" " << AllocaNo <<
": " << *Allocas[AllocaNo] <<
"\n";
272 dbgs() <<
"Block liveness:\n";
273 for (
auto IT : BlockLiveness) {
275 const BlockLifetimeInfo &BlockInfo = BlockLiveness.find(BB)->getSecond();
276 auto BlockRange = BlockInstRange.find(BB)->getSecond();
277 dbgs() <<
" BB (" << BB->
getName() <<
") [" << BlockRange.first <<
", " << BlockRange.second
278 <<
"): begin " << BlockInfo.Begin <<
", end " << BlockInfo.End
279 <<
", livein " << BlockInfo.LiveIn <<
", liveout "
280 << BlockInfo.LiveOut <<
"\n";
285 dbgs() <<
"Alloca liveness:\n";
286 for (
unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
287 dbgs() <<
" " << AllocaNo <<
": " << LiveRanges[AllocaNo] <<
"\n";
294 : F(F), Type(Type), Allocas(Allocas), NumAllocas(Allocas.
size()) {
297 for (
unsigned I = 0;
I < NumAllocas; ++
I)
298 AllocaNumbering[Allocas[
I]] =
I;
304 LiveRanges.resize(NumAllocas,
LiveRange(Instructions.size()));
305 for (
unsigned I = 0;
I < NumAllocas; ++
I)
306 if (!InterestingAllocas.test(
I))
309 calculateLocalLiveness();
311 calculateLiveIntervals();
321 for (
const auto &KV : SL.AllocaNumbering) {
322 if (SL.LiveRanges[KV.getSecond()].test(InstrNo))
323 Names.
push_back(KV.getFirst()->getName());
326 OS <<
" ; Alive: <" <<
llvm::join(Names,
" ") <<
">\n";
329 void emitBasicBlockStartAnnot(
const BasicBlock *BB,
331 auto ItBB = SL.BlockInstRange.find(BB);
332 if (ItBB == SL.BlockInstRange.end())
334 printInstrAlive(ItBB->getSecond().first, OS);
339 if (!Instr || !SL.isReachable(Instr))
343 for (
const auto &KV : SL.AllocaNumbering) {
344 if (SL.isAliveAfter(KV.getFirst(), Instr))
345 Names.
push_back(KV.getFirst()->getName());
348 OS <<
"\n ; Alive: <" <<
llvm::join(Names,
" ") <<
">\n";
374 static_cast<PassInfoMixin<StackLifetimePrinterPass> *
>(
this)->
printPipeline(
375 OS, MapClassName2PassName);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
Expand Atomic instructions
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
Hexagon Lower HLX Pair Allocas
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
uint64_t IntrinsicInst * II
SI Optimize VGPR LiveRange
This file defines the SmallVector class.
LifetimeAnnotationWriter(const StackLifetime &SL)
an instruction to allocate memory on the stack
Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
bool test(unsigned Idx) const
Returns true if bit Idx is set.
BitVector & reset()
Reset all bits in the bitvector.
void resize(unsigned N, bool t=false)
Grow or shrink the bitvector.
BitVector & set()
Set all bits in the bitvector.
bool empty() const
Returns whether there are no bits in this bitvector.
bool subsetOf(const BitVector &RHS) const
Check if This is a subset of RHS.
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT, true > const_iterator
A wrapper class for inspecting calls to intrinsic functions.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
This class represents a set of interesting instructions where an alloca is live.
bool test(unsigned Idx) const
Compute live ranges of allocas.
LLVM_ABI void print(raw_ostream &O)
LLVM_ABI StackLifetime(const Function &F, ArrayRef< const AllocaInst * > Allocas, LivenessType Type)
LLVM_ABI bool isReachable(const Instruction *I) const
Returns true if instruction is reachable from entry.
LiveRange getFullLiveRange() const
Returns a live range that represents an alloca that is live throughout the entire function.
LLVM_ABI const LiveRange & getLiveRange(const AllocaInst *AI) const
Returns a set of "interesting" instructions where the given alloca is live.
LLVM_ABI bool isAliveAfter(const AllocaInst *AI, const Instruction *I) const
Returns true if the alloca is alive after the instruction.
Represent a constant reference to a string, i.e.
LLVM Value Representation.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
@ BasicBlock
Various leaf nodes.
This is an optimization pass for GlobalISel generic memory operations.
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.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
std::string join(IteratorT Begin, IteratorT End, StringRef Separator)
Joins the strings in the range [Begin, End), adding Separator between the elements.
auto predecessors(const MachineBasicBlock *BB)
iterator_range< df_iterator< T > > depth_first(const T &G)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.