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