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 | |
21 | namespace llvm { |
22 | |
23 | class AllocaInst; |
24 | class BasicBlock; |
25 | class Function; |
26 | class Instruction; |
27 | class 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. |
37 | class 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 | |
58 | public: |
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 | |
88 | private: |
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 | |
134 | public: |
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 | |
169 | static 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 | |
178 | inline raw_ostream &operator<<(raw_ostream &OS, |
179 | const StackLifetime::LiveRange &R) { |
180 | return OS << R.Bits; |
181 | } |
182 | |
183 | /// Printer pass for testing. |
184 | class StackLifetimePrinterPass |
185 | : public PassInfoMixin<StackLifetimePrinterPass> { |
186 | StackLifetime::LivenessType Type; |
187 | raw_ostream &OS; |
188 | |
189 | public: |
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 | |