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(Start, End); } 71 72 bool overlaps(const LiveRange &Other) const { 73 return Bits.anyCommon(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(Instructions, 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(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