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