1 //===- StackLifetime.cpp - Alloca Lifetime Analysis -----------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/Analysis/StackLifetime.h"
10 #include "llvm/ADT/DepthFirstIterator.h"
11 #include "llvm/ADT/STLExtras.h"
12 #include "llvm/ADT/SmallVector.h"
13 #include "llvm/ADT/StringExtras.h"
14 #include "llvm/Analysis/ValueTracking.h"
15 #include "llvm/Config/llvm-config.h"
16 #include "llvm/IR/AssemblyAnnotationWriter.h"
17 #include "llvm/IR/BasicBlock.h"
18 #include "llvm/IR/CFG.h"
19 #include "llvm/IR/InstIterator.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/IntrinsicInst.h"
22 #include "llvm/IR/Value.h"
23 #include "llvm/Support/Casting.h"
24 #include "llvm/Support/Compiler.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/FormattedStream.h"
27 #include <algorithm>
28 #include <tuple>
29
30 using namespace llvm;
31
32 #define DEBUG_TYPE "stack-lifetime"
33
34 const StackLifetime::LiveRange &
getLiveRange(const AllocaInst * AI) const35 StackLifetime::getLiveRange(const AllocaInst *AI) const {
36 const auto IT = AllocaNumbering.find(AI);
37 assert(IT != AllocaNumbering.end());
38 return LiveRanges[IT->second];
39 }
40
isReachable(const Instruction * I) const41 bool StackLifetime::isReachable(const Instruction *I) const {
42 return BlockInstRange.find(I->getParent()) != BlockInstRange.end();
43 }
44
isAliveAfter(const AllocaInst * AI,const Instruction * I) const45 bool StackLifetime::isAliveAfter(const AllocaInst *AI,
46 const Instruction *I) const {
47 const BasicBlock *BB = I->getParent();
48 auto ItBB = BlockInstRange.find(BB);
49 assert(ItBB != BlockInstRange.end() && "Unreachable is not expected");
50
51 // Search the block for the first instruction following 'I'.
52 auto It = std::upper_bound(Instructions.begin() + ItBB->getSecond().first + 1,
53 Instructions.begin() + ItBB->getSecond().second, I,
54 [](const Instruction *L, const Instruction *R) {
55 return L->comesBefore(R);
56 });
57 --It;
58 unsigned InstNum = It - Instructions.begin();
59 return getLiveRange(AI).test(InstNum);
60 }
61
62 // Returns unique alloca annotated by lifetime marker only if
63 // markers has the same size and points to the alloca start.
findMatchingAlloca(const IntrinsicInst & II,const DataLayout & DL)64 static const AllocaInst *findMatchingAlloca(const IntrinsicInst &II,
65 const DataLayout &DL) {
66 const AllocaInst *AI = findAllocaForValue(II.getArgOperand(1), true);
67 if (!AI)
68 return nullptr;
69
70 auto AllocaSizeInBits = AI->getAllocationSizeInBits(DL);
71 if (!AllocaSizeInBits)
72 return nullptr;
73 int64_t AllocaSize = *AllocaSizeInBits / 8;
74
75 auto *Size = dyn_cast<ConstantInt>(II.getArgOperand(0));
76 if (!Size)
77 return nullptr;
78 int64_t LifetimeSize = Size->getSExtValue();
79
80 if (LifetimeSize != -1 && LifetimeSize != AllocaSize)
81 return nullptr;
82
83 return AI;
84 }
85
collectMarkers()86 void StackLifetime::collectMarkers() {
87 InterestingAllocas.resize(NumAllocas);
88 DenseMap<const BasicBlock *, SmallDenseMap<const IntrinsicInst *, Marker>>
89 BBMarkerSet;
90
91 const DataLayout &DL = F.getParent()->getDataLayout();
92
93 // Compute the set of start/end markers per basic block.
94 for (const BasicBlock *BB : depth_first(&F)) {
95 for (const Instruction &I : *BB) {
96 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
97 if (!II || !II->isLifetimeStartOrEnd())
98 continue;
99 const AllocaInst *AI = findMatchingAlloca(*II, DL);
100 if (!AI) {
101 HasUnknownLifetimeStartOrEnd = true;
102 continue;
103 }
104 auto It = AllocaNumbering.find(AI);
105 if (It == AllocaNumbering.end())
106 continue;
107 auto AllocaNo = It->second;
108 bool IsStart = II->getIntrinsicID() == Intrinsic::lifetime_start;
109 if (IsStart)
110 InterestingAllocas.set(AllocaNo);
111 BBMarkerSet[BB][II] = {AllocaNo, IsStart};
112 }
113 }
114
115 // Compute instruction numbering. Only the following instructions are
116 // considered:
117 // * Basic block entries
118 // * Lifetime markers
119 // For each basic block, compute
120 // * the list of markers in the instruction order
121 // * the sets of allocas whose lifetime starts or ends in this BB
122 LLVM_DEBUG(dbgs() << "Instructions:\n");
123 for (const BasicBlock *BB : depth_first(&F)) {
124 LLVM_DEBUG(dbgs() << " " << Instructions.size() << ": BB " << BB->getName()
125 << "\n");
126 auto BBStart = Instructions.size();
127 Instructions.push_back(nullptr);
128
129 BlockLifetimeInfo &BlockInfo =
130 BlockLiveness.try_emplace(BB, NumAllocas).first->getSecond();
131
132 auto &BlockMarkerSet = BBMarkerSet[BB];
133 if (BlockMarkerSet.empty()) {
134 BlockInstRange[BB] = std::make_pair(BBStart, Instructions.size());
135 continue;
136 }
137
138 auto ProcessMarker = [&](const IntrinsicInst *I, const Marker &M) {
139 LLVM_DEBUG(dbgs() << " " << Instructions.size() << ": "
140 << (M.IsStart ? "start " : "end ") << M.AllocaNo
141 << ", " << *I << "\n");
142
143 BBMarkers[BB].push_back({Instructions.size(), M});
144 Instructions.push_back(I);
145
146 if (M.IsStart) {
147 BlockInfo.End.reset(M.AllocaNo);
148 BlockInfo.Begin.set(M.AllocaNo);
149 } else {
150 BlockInfo.Begin.reset(M.AllocaNo);
151 BlockInfo.End.set(M.AllocaNo);
152 }
153 };
154
155 if (BlockMarkerSet.size() == 1) {
156 ProcessMarker(BlockMarkerSet.begin()->getFirst(),
157 BlockMarkerSet.begin()->getSecond());
158 } else {
159 // Scan the BB to determine the marker order.
160 for (const Instruction &I : *BB) {
161 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
162 if (!II)
163 continue;
164 auto It = BlockMarkerSet.find(II);
165 if (It == BlockMarkerSet.end())
166 continue;
167 ProcessMarker(II, It->getSecond());
168 }
169 }
170
171 BlockInstRange[BB] = std::make_pair(BBStart, Instructions.size());
172 }
173 }
174
calculateLocalLiveness()175 void StackLifetime::calculateLocalLiveness() {
176 bool Changed = true;
177 while (Changed) {
178 Changed = false;
179
180 for (const BasicBlock *BB : depth_first(&F)) {
181 BlockLifetimeInfo &BlockInfo = BlockLiveness.find(BB)->getSecond();
182
183 // Compute LiveIn by unioning together the LiveOut sets of all preds.
184 BitVector LocalLiveIn;
185 for (const auto *PredBB : predecessors(BB)) {
186 LivenessMap::const_iterator I = BlockLiveness.find(PredBB);
187 // If a predecessor is unreachable, ignore it.
188 if (I == BlockLiveness.end())
189 continue;
190 switch (Type) {
191 case LivenessType::May:
192 LocalLiveIn |= I->second.LiveOut;
193 break;
194 case LivenessType::Must:
195 if (LocalLiveIn.empty())
196 LocalLiveIn = I->second.LiveOut;
197 else
198 LocalLiveIn &= I->second.LiveOut;
199 break;
200 }
201 }
202
203 // Compute LiveOut by subtracting out lifetimes that end in this
204 // block, then adding in lifetimes that begin in this block. If
205 // we have both BEGIN and END markers in the same basic block
206 // then we know that the BEGIN marker comes after the END,
207 // because we already handle the case where the BEGIN comes
208 // before the END when collecting the markers (and building the
209 // BEGIN/END vectors).
210 BitVector LocalLiveOut = LocalLiveIn;
211 LocalLiveOut.reset(BlockInfo.End);
212 LocalLiveOut |= BlockInfo.Begin;
213
214 // Update block LiveIn set, noting whether it has changed.
215 if (LocalLiveIn.test(BlockInfo.LiveIn)) {
216 BlockInfo.LiveIn |= LocalLiveIn;
217 }
218
219 // Update block LiveOut set, noting whether it has changed.
220 if (LocalLiveOut.test(BlockInfo.LiveOut)) {
221 Changed = true;
222 BlockInfo.LiveOut |= LocalLiveOut;
223 }
224 }
225 } // while changed.
226 }
227
calculateLiveIntervals()228 void StackLifetime::calculateLiveIntervals() {
229 for (auto IT : BlockLiveness) {
230 const BasicBlock *BB = IT.getFirst();
231 BlockLifetimeInfo &BlockInfo = IT.getSecond();
232 unsigned BBStart, BBEnd;
233 std::tie(BBStart, BBEnd) = BlockInstRange[BB];
234
235 BitVector Started, Ended;
236 Started.resize(NumAllocas);
237 Ended.resize(NumAllocas);
238 SmallVector<unsigned, 8> Start;
239 Start.resize(NumAllocas);
240
241 // LiveIn ranges start at the first instruction.
242 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
243 if (BlockInfo.LiveIn.test(AllocaNo)) {
244 Started.set(AllocaNo);
245 Start[AllocaNo] = BBStart;
246 }
247 }
248
249 for (auto &It : BBMarkers[BB]) {
250 unsigned InstNo = It.first;
251 bool IsStart = It.second.IsStart;
252 unsigned AllocaNo = It.second.AllocaNo;
253
254 if (IsStart) {
255 if (!Started.test(AllocaNo)) {
256 Started.set(AllocaNo);
257 Ended.reset(AllocaNo);
258 Start[AllocaNo] = InstNo;
259 }
260 } else {
261 if (Started.test(AllocaNo)) {
262 LiveRanges[AllocaNo].addRange(Start[AllocaNo], InstNo);
263 Started.reset(AllocaNo);
264 }
265 Ended.set(AllocaNo);
266 }
267 }
268
269 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
270 if (Started.test(AllocaNo))
271 LiveRanges[AllocaNo].addRange(Start[AllocaNo], BBEnd);
272 }
273 }
274
275 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dumpAllocas() const276 LLVM_DUMP_METHOD void StackLifetime::dumpAllocas() const {
277 dbgs() << "Allocas:\n";
278 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
279 dbgs() << " " << AllocaNo << ": " << *Allocas[AllocaNo] << "\n";
280 }
281
dumpBlockLiveness() const282 LLVM_DUMP_METHOD void StackLifetime::dumpBlockLiveness() const {
283 dbgs() << "Block liveness:\n";
284 for (auto IT : BlockLiveness) {
285 const BasicBlock *BB = IT.getFirst();
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";
292 }
293 }
294
dumpLiveRanges() const295 LLVM_DUMP_METHOD void StackLifetime::dumpLiveRanges() const {
296 dbgs() << "Alloca liveness:\n";
297 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
298 dbgs() << " " << AllocaNo << ": " << LiveRanges[AllocaNo] << "\n";
299 }
300 #endif
301
StackLifetime(const Function & F,ArrayRef<const AllocaInst * > Allocas,LivenessType Type)302 StackLifetime::StackLifetime(const Function &F,
303 ArrayRef<const AllocaInst *> Allocas,
304 LivenessType Type)
305 : F(F), Type(Type), Allocas(Allocas), NumAllocas(Allocas.size()) {
306 LLVM_DEBUG(dumpAllocas());
307
308 for (unsigned I = 0; I < NumAllocas; ++I)
309 AllocaNumbering[Allocas[I]] = I;
310
311 collectMarkers();
312 }
313
run()314 void StackLifetime::run() {
315 if (HasUnknownLifetimeStartOrEnd) {
316 // There is marker which we can't assign to a specific alloca, so we
317 // fallback to the most conservative results for the type.
318 switch (Type) {
319 case LivenessType::May:
320 LiveRanges.resize(NumAllocas, getFullLiveRange());
321 break;
322 case LivenessType::Must:
323 LiveRanges.resize(NumAllocas, LiveRange(Instructions.size()));
324 break;
325 }
326 return;
327 }
328
329 LiveRanges.resize(NumAllocas, LiveRange(Instructions.size()));
330 for (unsigned I = 0; I < NumAllocas; ++I)
331 if (!InterestingAllocas.test(I))
332 LiveRanges[I] = getFullLiveRange();
333
334 calculateLocalLiveness();
335 LLVM_DEBUG(dumpBlockLiveness());
336 calculateLiveIntervals();
337 LLVM_DEBUG(dumpLiveRanges());
338 }
339
340 class StackLifetime::LifetimeAnnotationWriter
341 : public AssemblyAnnotationWriter {
342 const StackLifetime &SL;
343
printInstrAlive(unsigned InstrNo,formatted_raw_ostream & OS)344 void printInstrAlive(unsigned InstrNo, formatted_raw_ostream &OS) {
345 SmallVector<StringRef, 16> Names;
346 for (const auto &KV : SL.AllocaNumbering) {
347 if (SL.LiveRanges[KV.getSecond()].test(InstrNo))
348 Names.push_back(KV.getFirst()->getName());
349 }
350 llvm::sort(Names);
351 OS << " ; Alive: <" << llvm::join(Names, " ") << ">\n";
352 }
353
emitBasicBlockStartAnnot(const BasicBlock * BB,formatted_raw_ostream & OS)354 void emitBasicBlockStartAnnot(const BasicBlock *BB,
355 formatted_raw_ostream &OS) override {
356 auto ItBB = SL.BlockInstRange.find(BB);
357 if (ItBB == SL.BlockInstRange.end())
358 return; // Unreachable.
359 printInstrAlive(ItBB->getSecond().first, OS);
360 }
361
printInfoComment(const Value & V,formatted_raw_ostream & OS)362 void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
363 const Instruction *Instr = dyn_cast<Instruction>(&V);
364 if (!Instr || !SL.isReachable(Instr))
365 return;
366
367 SmallVector<StringRef, 16> Names;
368 for (const auto &KV : SL.AllocaNumbering) {
369 if (SL.isAliveAfter(KV.getFirst(), Instr))
370 Names.push_back(KV.getFirst()->getName());
371 }
372 llvm::sort(Names);
373 OS << "\n ; Alive: <" << llvm::join(Names, " ") << ">\n";
374 }
375
376 public:
LifetimeAnnotationWriter(const StackLifetime & SL)377 LifetimeAnnotationWriter(const StackLifetime &SL) : SL(SL) {}
378 };
379
print(raw_ostream & OS)380 void StackLifetime::print(raw_ostream &OS) {
381 LifetimeAnnotationWriter AAW(*this);
382 F.print(OS, &AAW);
383 }
384
run(Function & F,FunctionAnalysisManager & AM)385 PreservedAnalyses StackLifetimePrinterPass::run(Function &F,
386 FunctionAnalysisManager &AM) {
387 SmallVector<const AllocaInst *, 8> Allocas;
388 for (auto &I : instructions(F))
389 if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I))
390 Allocas.push_back(AI);
391 StackLifetime SL(F, Allocas, Type);
392 SL.run();
393 SL.print(OS);
394 return PreservedAnalyses::all();
395 }
396
printPipeline(raw_ostream & OS,function_ref<StringRef (StringRef)> MapClassName2PassName)397 void StackLifetimePrinterPass::printPipeline(
398 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
399 static_cast<PassInfoMixin<StackLifetimePrinterPass> *>(this)->printPipeline(
400 OS, MapClassName2PassName);
401 OS << "<";
402 switch (Type) {
403 case StackLifetime::LivenessType::May:
404 OS << "may";
405 break;
406 case StackLifetime::LivenessType::Must:
407 OS << "must";
408 break;
409 }
410 OS << ">";
411 }
412