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