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/Config/llvm-config.h"
12 #include "llvm/IR/BasicBlock.h"
13 #include "llvm/IR/CFG.h"
14 #include "llvm/IR/Instructions.h"
15 #include "llvm/IR/IntrinsicInst.h"
16 #include "llvm/IR/Intrinsics.h"
17 #include "llvm/IR/User.h"
18 #include "llvm/Support/Casting.h"
19 #include "llvm/Support/CommandLine.h"
20 #include "llvm/Support/Compiler.h"
21 #include "llvm/Support/Debug.h"
22 #include <tuple>
23 
24 using namespace llvm;
25 
26 #define DEBUG_TYPE "stack-lifetime"
27 
28 const StackLifetime::LiveRange &
29 StackLifetime::getLiveRange(const AllocaInst *AI) const {
30   const auto IT = AllocaNumbering.find(AI);
31   assert(IT != AllocaNumbering.end());
32   return LiveRanges[IT->second];
33 }
34 
35 static bool readMarker(const Instruction *I, bool *IsStart) {
36   if (!I->isLifetimeStartOrEnd())
37     return false;
38 
39   auto *II = cast<IntrinsicInst>(I);
40   *IsStart = II->getIntrinsicID() == Intrinsic::lifetime_start;
41   return true;
42 }
43 
44 std::vector<const IntrinsicInst *> StackLifetime::getMarkers() const {
45   std::vector<const IntrinsicInst *> Markers;
46   for (auto &M : InstructionNumbering)
47     if (M.getFirst()->isLifetimeStartOrEnd())
48       Markers.push_back(M.getFirst());
49   return Markers;
50 }
51 
52 void StackLifetime::collectMarkers() {
53   InterestingAllocas.resize(NumAllocas);
54   DenseMap<const BasicBlock *, SmallDenseMap<const IntrinsicInst *, Marker>>
55       BBMarkerSet;
56 
57   // Compute the set of start/end markers per basic block.
58   for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
59     const AllocaInst *AI = Allocas[AllocaNo];
60     SmallVector<const Instruction *, 8> WorkList;
61     WorkList.push_back(AI);
62     while (!WorkList.empty()) {
63       const Instruction *I = WorkList.pop_back_val();
64       for (const User *U : I->users()) {
65         if (auto *BI = dyn_cast<BitCastInst>(U)) {
66           WorkList.push_back(BI);
67           continue;
68         }
69         auto *UI = dyn_cast<IntrinsicInst>(U);
70         if (!UI)
71           continue;
72         bool IsStart;
73         if (!readMarker(UI, &IsStart))
74           continue;
75         if (IsStart)
76           InterestingAllocas.set(AllocaNo);
77         BBMarkerSet[UI->getParent()][UI] = {AllocaNo, IsStart};
78       }
79     }
80   }
81 
82   // Compute instruction numbering. Only the following instructions are
83   // considered:
84   // * Basic block entries
85   // * Lifetime markers
86   // For each basic block, compute
87   // * the list of markers in the instruction order
88   // * the sets of allocas whose lifetime starts or ends in this BB
89   LLVM_DEBUG(dbgs() << "Instructions:\n");
90   unsigned InstNo = 0;
91   for (const BasicBlock *BB : depth_first(&F)) {
92     LLVM_DEBUG(dbgs() << "  " << InstNo << ": BB " << BB->getName() << "\n");
93     unsigned BBStart = InstNo++;
94 
95     BlockLifetimeInfo &BlockInfo =
96         BlockLiveness.try_emplace(BB, NumAllocas).first->getSecond();
97 
98     auto &BlockMarkerSet = BBMarkerSet[BB];
99     if (BlockMarkerSet.empty()) {
100       unsigned BBEnd = InstNo;
101       BlockInstRange[BB] = std::make_pair(BBStart, BBEnd);
102       continue;
103     }
104 
105     auto ProcessMarker = [&](const IntrinsicInst *I, const Marker &M) {
106       LLVM_DEBUG(dbgs() << "  " << InstNo << ":  "
107                         << (M.IsStart ? "start " : "end   ") << M.AllocaNo
108                         << ", " << *I << "\n");
109 
110       BBMarkers[BB].push_back({InstNo, M});
111 
112       InstructionNumbering[I] = InstNo++;
113 
114       if (M.IsStart) {
115         BlockInfo.End.reset(M.AllocaNo);
116         BlockInfo.Begin.set(M.AllocaNo);
117       } else {
118         BlockInfo.Begin.reset(M.AllocaNo);
119         BlockInfo.End.set(M.AllocaNo);
120       }
121     };
122 
123     if (BlockMarkerSet.size() == 1) {
124       ProcessMarker(BlockMarkerSet.begin()->getFirst(),
125                     BlockMarkerSet.begin()->getSecond());
126     } else {
127       // Scan the BB to determine the marker order.
128       for (const Instruction &I : *BB) {
129         const IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
130         if (!II)
131           continue;
132         auto It = BlockMarkerSet.find(II);
133         if (It == BlockMarkerSet.end())
134           continue;
135         ProcessMarker(II, It->getSecond());
136       }
137     }
138 
139     unsigned BBEnd = InstNo;
140     BlockInstRange[BB] = std::make_pair(BBStart, BBEnd);
141   }
142   NumInst = InstNo;
143 }
144 
145 void StackLifetime::calculateLocalLiveness() {
146   bool Changed = true;
147   while (Changed) {
148     Changed = false;
149 
150     for (const BasicBlock *BB : depth_first(&F)) {
151       BlockLifetimeInfo &BlockInfo = BlockLiveness.find(BB)->getSecond();
152 
153       // Compute LiveIn by unioning together the LiveOut sets of all preds.
154       BitVector LocalLiveIn;
155       for (auto *PredBB : predecessors(BB)) {
156         LivenessMap::const_iterator I = BlockLiveness.find(PredBB);
157         // If a predecessor is unreachable, ignore it.
158         if (I == BlockLiveness.end())
159           continue;
160         LocalLiveIn |= I->second.LiveOut;
161       }
162 
163       // Compute LiveOut by subtracting out lifetimes that end in this
164       // block, then adding in lifetimes that begin in this block.  If
165       // we have both BEGIN and END markers in the same basic block
166       // then we know that the BEGIN marker comes after the END,
167       // because we already handle the case where the BEGIN comes
168       // before the END when collecting the markers (and building the
169       // BEGIN/END vectors).
170       BitVector LocalLiveOut = LocalLiveIn;
171       LocalLiveOut.reset(BlockInfo.End);
172       LocalLiveOut |= BlockInfo.Begin;
173 
174       // Update block LiveIn set, noting whether it has changed.
175       if (LocalLiveIn.test(BlockInfo.LiveIn)) {
176         Changed = true;
177         BlockInfo.LiveIn |= LocalLiveIn;
178       }
179 
180       // Update block LiveOut set, noting whether it has changed.
181       if (LocalLiveOut.test(BlockInfo.LiveOut)) {
182         Changed = true;
183         BlockInfo.LiveOut |= LocalLiveOut;
184       }
185     }
186   } // while changed.
187 }
188 
189 void StackLifetime::calculateLiveIntervals() {
190   for (auto IT : BlockLiveness) {
191     const BasicBlock *BB = IT.getFirst();
192     BlockLifetimeInfo &BlockInfo = IT.getSecond();
193     unsigned BBStart, BBEnd;
194     std::tie(BBStart, BBEnd) = BlockInstRange[BB];
195 
196     BitVector Started, Ended;
197     Started.resize(NumAllocas);
198     Ended.resize(NumAllocas);
199     SmallVector<unsigned, 8> Start;
200     Start.resize(NumAllocas);
201 
202     // LiveIn ranges start at the first instruction.
203     for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
204       if (BlockInfo.LiveIn.test(AllocaNo)) {
205         Started.set(AllocaNo);
206         Start[AllocaNo] = BBStart;
207       }
208     }
209 
210     for (auto &It : BBMarkers[BB]) {
211       unsigned InstNo = It.first;
212       bool IsStart = It.second.IsStart;
213       unsigned AllocaNo = It.second.AllocaNo;
214 
215       if (IsStart) {
216         assert(!Started.test(AllocaNo) || Start[AllocaNo] == BBStart);
217         if (!Started.test(AllocaNo)) {
218           Started.set(AllocaNo);
219           Ended.reset(AllocaNo);
220           Start[AllocaNo] = InstNo;
221         }
222       } else {
223         assert(!Ended.test(AllocaNo));
224         if (Started.test(AllocaNo)) {
225           LiveRanges[AllocaNo].addRange(Start[AllocaNo], InstNo);
226           Started.reset(AllocaNo);
227         }
228         Ended.set(AllocaNo);
229       }
230     }
231 
232     for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
233       if (Started.test(AllocaNo))
234         LiveRanges[AllocaNo].addRange(Start[AllocaNo], BBEnd);
235   }
236 }
237 
238 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
239 LLVM_DUMP_METHOD void StackLifetime::dumpAllocas() const {
240   dbgs() << "Allocas:\n";
241   for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
242     dbgs() << "  " << AllocaNo << ": " << *Allocas[AllocaNo] << "\n";
243 }
244 
245 LLVM_DUMP_METHOD void StackLifetime::dumpBlockLiveness() const {
246   dbgs() << "Block liveness:\n";
247   for (auto IT : BlockLiveness) {
248     const BasicBlock *BB = IT.getFirst();
249     const BlockLifetimeInfo &BlockInfo = BlockLiveness.find(BB)->getSecond();
250     auto BlockRange = BlockInstRange.find(BB)->getSecond();
251     dbgs() << "  BB [" << BlockRange.first << ", " << BlockRange.second
252            << "): begin " << BlockInfo.Begin << ", end " << BlockInfo.End
253            << ", livein " << BlockInfo.LiveIn << ", liveout "
254            << BlockInfo.LiveOut << "\n";
255   }
256 }
257 
258 LLVM_DUMP_METHOD void StackLifetime::dumpLiveRanges() const {
259   dbgs() << "Alloca liveness:\n";
260   for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
261     dbgs() << "  " << AllocaNo << ": " << LiveRanges[AllocaNo] << "\n";
262 }
263 #endif
264 
265 StackLifetime::StackLifetime(const Function &F,
266                              ArrayRef<const AllocaInst *> Allocas)
267     : F(F), Allocas(Allocas), NumAllocas(Allocas.size()) {
268   LLVM_DEBUG(dumpAllocas());
269 
270   for (unsigned I = 0; I < NumAllocas; ++I)
271     AllocaNumbering[Allocas[I]] = I;
272 
273   collectMarkers();
274 }
275 
276 void StackLifetime::run() {
277   LiveRanges.resize(NumAllocas, LiveRange(NumInst));
278   for (unsigned I = 0; I < NumAllocas; ++I)
279     if (!InterestingAllocas.test(I))
280       LiveRanges[I] = getFullLiveRange();
281 
282   calculateLocalLiveness();
283   LLVM_DEBUG(dumpBlockLiveness());
284   calculateLiveIntervals();
285   LLVM_DEBUG(dumpLiveRanges());
286 }
287