• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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