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/IR/IntrinsicInst.h" 17 #include "llvm/IR/PassManager.h" 18 #include "llvm/Support/raw_ostream.h" 19 #include <cassert> 20 #include <utility> 21 22 namespace llvm { 23 24 class AllocaInst; 25 class BasicBlock; 26 class Function; 27 class Instruction; 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 void dumpAllocas() const; 125 void dumpBlockLiveness() const; 126 void dumpLiveRanges() const; 127 128 void collectMarkers(); 129 void calculateLocalLiveness(); 130 void calculateLiveIntervals(); 131 132 public: 133 StackLifetime(const Function &F, ArrayRef<const AllocaInst *> Allocas, 134 LivenessType Type); 135 136 void run(); 137 138 iterator_range< 139 filter_iterator<ArrayRef<const IntrinsicInst *>::const_iterator, 140 std::function<bool(const IntrinsicInst *)>>> 141 getMarkers() const { 142 std::function<bool(const IntrinsicInst *)> NotNull( 143 [](const IntrinsicInst *I) -> bool { return I; }); 144 return make_filter_range(Instructions, NotNull); 145 } 146 147 /// Returns a set of "interesting" instructions where the given alloca is 148 /// live. Not all instructions in a function are interesting: we pick a set 149 /// that is large enough for LiveRange::Overlaps to be correct. 150 const LiveRange &getLiveRange(const AllocaInst *AI) const; 151 152 /// Returns true if instruction is reachable from entry. 153 bool isReachable(const Instruction *I) const; 154 155 /// Returns true if the alloca is alive after the instruction. 156 bool isAliveAfter(const AllocaInst *AI, const Instruction *I) const; 157 158 /// Returns a live range that represents an alloca that is live throughout the 159 /// entire function. 160 LiveRange getFullLiveRange() const { 161 return LiveRange(Instructions.size(), true); 162 } 163 164 void print(raw_ostream &O); 165 }; 166 167 static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) { 168 OS << "{"; 169 int Idx = V.find_first(); 170 bool First = true; 171 while (Idx >= 0) { 172 if (!First) { 173 OS << ", "; 174 } 175 First = false; 176 OS << Idx; 177 Idx = V.find_next(Idx); 178 } 179 OS << "}"; 180 return OS; 181 } 182 183 inline raw_ostream &operator<<(raw_ostream &OS, 184 const StackLifetime::LiveRange &R) { 185 return OS << R.Bits; 186 } 187 188 /// Printer pass for testing. 189 class StackLifetimePrinterPass 190 : public PassInfoMixin<StackLifetimePrinterPass> { 191 StackLifetime::LivenessType Type; 192 raw_ostream &OS; 193 194 public: 195 StackLifetimePrinterPass(raw_ostream &OS, StackLifetime::LivenessType Type) 196 : Type(Type), OS(OS) {} 197 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 198 }; 199 200 } // end namespace llvm 201 202 #endif // LLVM_ANALYSIS_STACKLIFETIME_H 203