1 //===- SafeStackColoring.h - SafeStack frame coloring ----------*- C++ -*--===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H
11 #define LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H
13 #include "llvm/ADT/ArrayRef.h"
14 #include "llvm/ADT/BitVector.h"
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/Support/raw_ostream.h"
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
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.
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 {
43 /// Which slots BEGINs in each basic block.
46 /// Which slots ENDs in each basic block.
49 /// Which slots are marked as LIVE_IN, coming into each basic block.
52 /// Which slots are marked as LIVE_OUT, coming out of each basic block.
57 /// This class represents a set of interesting instructions where an alloca is
62 void SetMaximum(int size) { bv.resize(size); }
63 void AddRange(unsigned start, unsigned end) { bv.set(start, end); }
65 bool Overlaps(const LiveRange &Other) const {
66 return bv.anyCommon(Other.bv);
69 void Join(const LiveRange &Other) { bv |= Other.bv; }
75 /// Maps active slots (per bit) for each basic block.
76 using LivenessMap = DenseMap<BasicBlock *, BlockLifetimeInfo>;
77 LivenessMap BlockLiveness;
79 /// Number of interesting instructions.
82 /// Numeric ids for interesting instructions.
83 DenseMap<Instruction *, unsigned> InstructionNumbering;
85 /// A range [Start, End) of instruction ids for each basic block.
86 /// Instructions inside each BB have monotonic and consecutive ids.
87 DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange;
89 ArrayRef<AllocaInst *> Allocas;
91 DenseMap<AllocaInst *, unsigned> AllocaNumbering;
93 /// LiveRange for allocas.
94 SmallVector<LiveRange, 8> LiveRanges;
96 /// The set of allocas that have at least one lifetime.start. All other
97 /// allocas get LiveRange that corresponds to the entire function.
98 BitVector InterestingAllocas;
99 SmallVector<Instruction *, 8> Markers;
106 /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo.
107 DenseMap<BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>> BBMarkers;
110 void dumpBlockLiveness();
111 void dumpLiveRanges();
113 bool readMarker(Instruction *I, bool *IsStart);
114 void collectMarkers();
115 void calculateLocalLiveness();
116 void calculateLiveIntervals();
119 StackColoring(Function &F, ArrayRef<AllocaInst *> Allocas)
120 : F(F), Allocas(Allocas), NumAllocas(Allocas.size()) {}
123 void removeAllMarkers();
125 /// Returns a set of "interesting" instructions where the given alloca is
126 /// live. Not all instructions in a function are interesting: we pick a set
127 /// that is large enough for LiveRange::Overlaps to be correct.
128 const LiveRange &getLiveRange(AllocaInst *AI);
130 /// Returns a live range that represents an alloca that is live throughout the
132 LiveRange getFullLiveRange() {
133 assert(NumInst >= 0);
135 R.SetMaximum(NumInst);
136 R.AddRange(0, NumInst);
141 static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) {
143 int idx = V.find_first();
151 idx = V.find_next(idx);
157 static inline raw_ostream &operator<<(raw_ostream &OS,
158 const StackColoring::LiveRange &R) {
162 } // end namespace safestack
164 } // end namespace llvm
166 #endif // LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H