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.find(
I->getParent()) != BlockInstRange.end();
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();
71 if (!AllocaSizeInBits)
73 int64_t AllocaSize = AllocaSizeInBits.getValue() / 8;
78 int64_t LifetimeSize = Size->getSExtValue();
80 if (LifetimeSize != -1 && LifetimeSize != AllocaSize)
86 void StackLifetime::collectMarkers() {
87 InterestingAllocas.
resize(NumAllocas);
101 HasUnknownLifetimeStartOrEnd =
true;
104 auto It = AllocaNumbering.find(AI);
105 if (It == AllocaNumbering.end())
107 auto AllocaNo = It->second;
110 InterestingAllocas.
set(AllocaNo);
111 BBMarkerSet[
BB][II] = {AllocaNo, IsStart};
126 auto BBStart = Instructions.size();
127 Instructions.push_back(
nullptr);
129 BlockLifetimeInfo &BlockInfo =
130 BlockLiveness.
try_emplace(
BB, NumAllocas).first->getSecond();
132 auto &BlockMarkerSet = BBMarkerSet[
BB];
133 if (BlockMarkerSet.empty()) {
134 BlockInstRange[
BB] = std::make_pair(BBStart, Instructions.size());
140 << (
M.IsStart ?
"start " :
"end ") <<
M.AllocaNo
141 <<
", " << *
I <<
"\n");
143 BBMarkers[
BB].push_back({Instructions.size(), M});
144 Instructions.push_back(
I);
147 BlockInfo.End.reset(
M.AllocaNo);
148 BlockInfo.Begin.set(
M.AllocaNo);
150 BlockInfo.Begin.reset(
M.AllocaNo);
151 BlockInfo.End.set(
M.AllocaNo);
155 if (BlockMarkerSet.size() == 1) {
156 ProcessMarker(BlockMarkerSet.begin()->getFirst(),
157 BlockMarkerSet.begin()->getSecond());
164 auto It = BlockMarkerSet.find(II);
165 if (It == BlockMarkerSet.end())
167 ProcessMarker(II, It->getSecond());
171 BlockInstRange[
BB] = std::make_pair(BBStart, Instructions.size());
175 void StackLifetime::calculateLocalLiveness() {
181 BlockLifetimeInfo &BlockInfo = BlockLiveness.
find(
BB)->getSecond();
188 if (
I == BlockLiveness.
end())
192 LocalLiveIn |=
I->second.LiveOut;
195 if (LocalLiveIn.
empty())
196 LocalLiveIn =
I->second.LiveOut;
198 LocalLiveIn &=
I->second.LiveOut;
211 LocalLiveOut.
reset(BlockInfo.End);
212 LocalLiveOut |= BlockInfo.Begin;
215 if (LocalLiveIn.
test(BlockInfo.LiveIn)) {
216 BlockInfo.LiveIn |= LocalLiveIn;
220 if (LocalLiveOut.
test(BlockInfo.LiveOut)) {
222 BlockInfo.LiveOut |= LocalLiveOut;
228 void StackLifetime::calculateLiveIntervals() {
229 for (
auto IT : BlockLiveness) {
231 BlockLifetimeInfo &BlockInfo =
IT.getSecond();
232 unsigned BBStart, BBEnd;
233 std::tie(BBStart, BBEnd) = BlockInstRange[
BB];
236 Started.
resize(NumAllocas);
239 Start.resize(NumAllocas);
242 for (
unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
243 if (BlockInfo.LiveIn.test(AllocaNo)) {
244 Started.
set(AllocaNo);
245 Start[AllocaNo] = BBStart;
249 for (
auto &It : BBMarkers[
BB]) {
250 unsigned InstNo = It.first;
251 bool IsStart = It.second.IsStart;
252 unsigned AllocaNo = It.second.AllocaNo;
255 if (!Started.
test(AllocaNo)) {
256 Started.
set(AllocaNo);
257 Ended.
reset(AllocaNo);
258 Start[AllocaNo] = InstNo;
261 if (Started.
test(AllocaNo)) {
262 LiveRanges[AllocaNo].addRange(Start[AllocaNo], InstNo);
263 Started.
reset(AllocaNo);
269 for (
unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
270 if (Started.
test(AllocaNo))
271 LiveRanges[AllocaNo].addRange(Start[AllocaNo], BBEnd);
275 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
277 dbgs() <<
"Allocas:\n";
278 for (
unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
279 dbgs() <<
" " << AllocaNo <<
": " << *Allocas[AllocaNo] <<
"\n";
283 dbgs() <<
"Block liveness:\n";
284 for (
auto IT : BlockLiveness) {
286 const BlockLifetimeInfo &BlockInfo = BlockLiveness.find(
BB)->getSecond();
287 auto BlockRange = BlockInstRange.find(
BB)->getSecond();
288 dbgs() <<
" BB (" <<
BB->getName() <<
") [" << BlockRange.first <<
", " << BlockRange.second
289 <<
"): begin " << BlockInfo.Begin <<
", end " << BlockInfo.End
290 <<
", livein " << BlockInfo.LiveIn <<
", liveout "
291 << BlockInfo.LiveOut <<
"\n";
296 dbgs() <<
"Alloca liveness:\n";
297 for (
unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
298 dbgs() <<
" " << AllocaNo <<
": " << LiveRanges[AllocaNo] <<
"\n";
305 :
F(
F),
Type(
Type), Allocas(Allocas), NumAllocas(Allocas.
size()) {
308 for (
unsigned I = 0;
I < NumAllocas; ++
I)
309 AllocaNumbering[Allocas[
I]] =
I;
315 if (HasUnknownLifetimeStartOrEnd) {
323 LiveRanges.resize(NumAllocas,
LiveRange(Instructions.size()));
329 LiveRanges.resize(NumAllocas,
LiveRange(Instructions.size()));
330 for (
unsigned I = 0;
I < NumAllocas; ++
I)
331 if (!InterestingAllocas.
test(
I))
334 calculateLocalLiveness();
336 calculateLiveIntervals();
346 for (
const auto &KV : SL.AllocaNumbering) {
347 if (SL.LiveRanges[KV.getSecond()].test(InstrNo))
348 Names.push_back(KV.getFirst()->getName());
351 OS <<
" ; Alive: <" << llvm::join(Names,
" ") <<
">\n";
356 auto ItBB = SL.BlockInstRange.find(
BB);
357 if (ItBB == SL.BlockInstRange.end())
359 printInstrAlive(ItBB->getSecond().first, OS);
363 const Instruction *Instr = dyn_cast<Instruction>(&V);
368 for (
const auto &KV : SL.AllocaNumbering) {
370 Names.push_back(KV.getFirst()->getName());
373 OS <<
"\n ; Alive: <" << llvm::join(Names,
" ") <<
">\n";
389 if (
const AllocaInst *AI = dyn_cast<AllocaInst>(&
I))
390 Allocas.push_back(AI);
400 OS, MapClassName2PassName);