1 //===-- SafeStackColoring.h - SafeStack frame coloring ---------*- C++ -*--===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H 11 #define LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H 12 13 #include "llvm/ADT/BitVector.h" 14 #include "llvm/ADT/DenseMap.h" 15 #include "llvm/ADT/SmallVector.h" 16 #include "llvm/IR/Function.h" 17 #include "llvm/Support/raw_os_ostream.h" 18 19 namespace llvm { 20 class AllocaInst; 21 22 namespace safestack { 23 /// Compute live ranges of allocas. 24 /// Live ranges are represented as sets of "interesting" instructions, which are 25 /// defined as instructions that may start or end an alloca's lifetime. These 26 /// are: 27 /// * lifetime.start and lifetime.end intrinsics 28 /// * first instruction of any basic block 29 /// Interesting instructions are numbered in the depth-first walk of the CFG, 30 /// and in the program order inside each basic block. 31 class StackColoring { 32 /// A class representing liveness information for a single basic block. 33 /// Each bit in the BitVector represents the liveness property 34 /// for a different stack slot. 35 struct BlockLifetimeInfo { 36 /// Which slots BEGINs in each basic block. 37 BitVector Begin; 38 /// Which slots ENDs in each basic block. 39 BitVector End; 40 /// Which slots are marked as LIVE_IN, coming into each basic block. 41 BitVector LiveIn; 42 /// Which slots are marked as LIVE_OUT, coming out of each basic block. 43 BitVector LiveOut; 44 }; 45 46 public: 47 /// This class represents a set of interesting instructions where an alloca is 48 /// live. 49 struct LiveRange { 50 BitVector bv; SetMaximumLiveRange51 void SetMaximum(int size) { bv.resize(size); } AddRangeLiveRange52 void AddRange(unsigned start, unsigned end) { bv.set(start, end); } OverlapsLiveRange53 bool Overlaps(const LiveRange &Other) const { 54 return bv.anyCommon(Other.bv); 55 } JoinLiveRange56 void Join(const LiveRange &Other) { bv |= Other.bv; } 57 }; 58 59 private: 60 Function &F; 61 62 /// Maps active slots (per bit) for each basic block. 63 typedef DenseMap<BasicBlock *, BlockLifetimeInfo> LivenessMap; 64 LivenessMap BlockLiveness; 65 66 /// Number of interesting instructions. 67 int NumInst; 68 /// Numeric ids for interesting instructions. 69 DenseMap<Instruction *, unsigned> InstructionNumbering; 70 /// A range [Start, End) of instruction ids for each basic block. 71 /// Instructions inside each BB have monotonic and consecutive ids. 72 DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange; 73 74 ArrayRef<AllocaInst *> Allocas; 75 unsigned NumAllocas; 76 DenseMap<AllocaInst *, unsigned> AllocaNumbering; 77 /// LiveRange for allocas. 78 SmallVector<LiveRange, 8> LiveRanges; 79 80 /// The set of allocas that have at least one lifetime.start. All other 81 /// allocas get LiveRange that corresponds to the entire function. 82 BitVector InterestingAllocas; 83 SmallVector<Instruction *, 8> Markers; 84 85 struct Marker { 86 unsigned AllocaNo; 87 bool IsStart; 88 }; 89 90 /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo. 91 DenseMap<BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>> BBMarkers; 92 93 void dumpAllocas(); 94 void dumpBlockLiveness(); 95 void dumpLiveRanges(); 96 97 bool readMarker(Instruction *I, bool *IsStart); 98 void collectMarkers(); 99 void calculateLocalLiveness(); 100 void calculateLiveIntervals(); 101 102 public: StackColoring(Function & F,ArrayRef<AllocaInst * > Allocas)103 StackColoring(Function &F, ArrayRef<AllocaInst *> Allocas) 104 : F(F), NumInst(-1), Allocas(Allocas), NumAllocas(Allocas.size()) {} 105 106 void run(); 107 void removeAllMarkers(); 108 109 /// Returns a set of "interesting" instructions where the given alloca is 110 /// live. Not all instructions in a function are interesting: we pick a set 111 /// that is large enough for LiveRange::Overlaps to be correct. 112 const LiveRange &getLiveRange(AllocaInst *AI); 113 114 /// Returns a live range that represents an alloca that is live throughout the 115 /// entire function. getFullLiveRange()116 LiveRange getFullLiveRange() { 117 assert(NumInst >= 0); 118 LiveRange R; 119 R.SetMaximum(NumInst); 120 R.AddRange(0, NumInst); 121 return R; 122 } 123 }; 124 125 static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) { 126 OS << "{"; 127 int idx = V.find_first(); 128 bool first = true; 129 while (idx >= 0) { 130 if (!first) { 131 OS << ", "; 132 } 133 first = false; 134 OS << idx; 135 idx = V.find_next(idx); 136 } 137 OS << "}"; 138 return OS; 139 } 140 141 static inline raw_ostream &operator<<(raw_ostream &OS, 142 const StackColoring::LiveRange &R) { 143 return OS << R.bv; 144 } 145 146 } // namespace safestack 147 } // namespace llvm 148 149 #endif // LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H 150