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