1//===- StackLifetime.h - Alloca Lifetime Analysis --------------*- C++ -*--===//
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#ifndef LLVM_ANALYSIS_STACKLIFETIME_H
10#define LLVM_ANALYSIS_STACKLIFETIME_H
11
12#include "llvm/ADT/ArrayRef.h"
13#include "llvm/ADT/BitVector.h"
14#include "llvm/ADT/DenseMap.h"
15#include "llvm/ADT/SmallVector.h"
16#include "llvm/ADT/StringExtras.h"
17#include "llvm/IR/PassManager.h"
18#include "llvm/Support/raw_ostream.h"
19#include <utility>
20
21namespace llvm {
22
23class AllocaInst;
24class BasicBlock;
25class Function;
26class Instruction;
27class IntrinsicInst;
28
29/// Compute live ranges of allocas.
30/// Live ranges are represented as sets of "interesting" instructions, which are
31/// defined as instructions that may start or end an alloca's lifetime. These
32/// are:
33/// * lifetime.start and lifetime.end intrinsics
34/// * first instruction of any basic block
35/// Interesting instructions are numbered in the depth-first walk of the CFG,
36/// and in the program order inside each basic block.
37class StackLifetime {
38 /// A class representing liveness information for a single basic block.
39 /// Each bit in the BitVector represents the liveness property
40 /// for a different stack slot.
41 struct BlockLifetimeInfo {
42 explicit BlockLifetimeInfo(unsigned Size)
43 : Begin(Size), End(Size), LiveIn(Size), LiveOut(Size) {}
44
45 /// Which slots BEGINs in each basic block.
46 BitVector Begin;
47
48 /// Which slots ENDs in each basic block.
49 BitVector End;
50
51 /// Which slots are marked as LIVE_IN, coming into each basic block.
52 BitVector LiveIn;
53
54 /// Which slots are marked as LIVE_OUT, coming out of each basic block.
55 BitVector LiveOut;
56 };
57
58public:
59 class LifetimeAnnotationWriter;
60
61 /// This class represents a set of interesting instructions where an alloca is
62 /// live.
63 class LiveRange {
64 BitVector Bits;
65 friend raw_ostream &operator<<(raw_ostream &OS,
66 const StackLifetime::LiveRange &R);
67
68 public:
69 LiveRange(unsigned Size, bool Set = false) : Bits(Size, Set) {}
70 void addRange(unsigned Start, unsigned End) { Bits.set(I: Start, E: End); }
71
72 bool overlaps(const LiveRange &Other) const {
73 return Bits.anyCommon(RHS: Other.Bits);
74 }
75
76 void join(const LiveRange &Other) { Bits |= Other.Bits; }
77
78 bool test(unsigned Idx) const { return Bits.test(Idx); }
79 };
80
81 // Controls what is "alive" if control flow may reach the instruction
82 // with a different liveness of the alloca.
83 enum class LivenessType {
84 May, // May be alive on some path.
85 Must, // Must be alive on every path.
86 };
87
88private:
89 const Function &F;
90 LivenessType Type;
91
92 /// Maps active slots (per bit) for each basic block.
93 using LivenessMap = DenseMap<const BasicBlock *, BlockLifetimeInfo>;
94 LivenessMap BlockLiveness;
95
96 /// Interesting instructions. Instructions of the same block are adjustent
97 /// preserve in-block order.
98 SmallVector<const IntrinsicInst *, 64> Instructions;
99
100 /// A range [Start, End) of instruction ids for each basic block.
101 /// Instructions inside each BB have monotonic and consecutive ids.
102 DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange;
103
104 ArrayRef<const AllocaInst *> Allocas;
105 unsigned NumAllocas;
106 DenseMap<const AllocaInst *, unsigned> AllocaNumbering;
107
108 /// LiveRange for allocas.
109 SmallVector<LiveRange, 8> LiveRanges;
110
111 /// The set of allocas that have at least one lifetime.start. All other
112 /// allocas get LiveRange that corresponds to the entire function.
113 BitVector InterestingAllocas;
114
115 struct Marker {
116 unsigned AllocaNo;
117 bool IsStart;
118 };
119
120 /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo.
121 DenseMap<const BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>>
122 BBMarkers;
123
124 bool HasUnknownLifetimeStartOrEnd = false;
125
126 void dumpAllocas() const;
127 void dumpBlockLiveness() const;
128 void dumpLiveRanges() const;
129
130 void collectMarkers();
131 void calculateLocalLiveness();
132 void calculateLiveIntervals();
133
134public:
135 StackLifetime(const Function &F, ArrayRef<const AllocaInst *> Allocas,
136 LivenessType Type);
137
138 void run();
139
140 iterator_range<
141 filter_iterator<ArrayRef<const IntrinsicInst *>::const_iterator,
142 std::function<bool(const IntrinsicInst *)>>>
143 getMarkers() const {
144 std::function<bool(const IntrinsicInst *)> NotNull(
145 [](const IntrinsicInst *I) -> bool { return I; });
146 return make_filter_range(Range: Instructions, Pred: NotNull);
147 }
148
149 /// Returns a set of "interesting" instructions where the given alloca is
150 /// live. Not all instructions in a function are interesting: we pick a set
151 /// that is large enough for LiveRange::Overlaps to be correct.
152 const LiveRange &getLiveRange(const AllocaInst *AI) const;
153
154 /// Returns true if instruction is reachable from entry.
155 bool isReachable(const Instruction *I) const;
156
157 /// Returns true if the alloca is alive after the instruction.
158 bool isAliveAfter(const AllocaInst *AI, const Instruction *I) const;
159
160 /// Returns a live range that represents an alloca that is live throughout the
161 /// entire function.
162 LiveRange getFullLiveRange() const {
163 return LiveRange(Instructions.size(), true);
164 }
165
166 void print(raw_ostream &O);
167};
168
169static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) {
170 OS << "{";
171 ListSeparator LS;
172 for (int Idx = V.find_first(); Idx >= 0; Idx = V.find_next(Prev: Idx))
173 OS << LS << Idx;
174 OS << "}";
175 return OS;
176}
177
178inline raw_ostream &operator<<(raw_ostream &OS,
179 const StackLifetime::LiveRange &R) {
180 return OS << R.Bits;
181}
182
183/// Printer pass for testing.
184class StackLifetimePrinterPass
185 : public PassInfoMixin<StackLifetimePrinterPass> {
186 StackLifetime::LivenessType Type;
187 raw_ostream &OS;
188
189public:
190 StackLifetimePrinterPass(raw_ostream &OS, StackLifetime::LivenessType Type)
191 : Type(Type), OS(OS) {}
192 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
193 static bool isRequired() { return true; }
194 void printPipeline(raw_ostream &OS,
195 function_ref<StringRef(StringRef)> MapClassName2PassName);
196};
197
198} // end namespace llvm
199
200#endif // LLVM_ANALYSIS_STACKLIFETIME_H
201

source code of llvm/include/llvm/Analysis/StackLifetime.h