Line data Source code
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/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"
19 : #include <cassert>
20 : #include <utility>
21 :
22 : namespace llvm {
23 :
24 : class BasicBlock;
25 : class Function;
26 : class Instruction;
27 :
28 : namespace safestack {
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 StackColoring {
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 0 : struct BlockLifetimeInfo {
43 : /// Which slots BEGINs in each basic block.
44 : BitVector Begin;
45 :
46 : /// Which slots ENDs in each basic block.
47 : BitVector End;
48 :
49 : /// Which slots are marked as LIVE_IN, coming into each basic block.
50 : BitVector LiveIn;
51 :
52 : /// Which slots are marked as LIVE_OUT, coming out of each basic block.
53 : BitVector LiveOut;
54 : };
55 :
56 : public:
57 : /// This class represents a set of interesting instructions where an alloca is
58 : /// live.
59 928 : struct LiveRange {
60 : BitVector bv;
61 :
62 232 : void SetMaximum(int size) { bv.resize(size); }
63 289 : void AddRange(unsigned start, unsigned end) { bv.set(start, end); }
64 :
65 : bool Overlaps(const LiveRange &Other) const {
66 251 : return bv.anyCommon(Other.bv);
67 : }
68 :
69 254 : void Join(const LiveRange &Other) { bv |= Other.bv; }
70 : };
71 :
72 : private:
73 : Function &F;
74 :
75 : /// Maps active slots (per bit) for each basic block.
76 : using LivenessMap = DenseMap<BasicBlock *, BlockLifetimeInfo>;
77 : LivenessMap BlockLiveness;
78 :
79 : /// Number of interesting instructions.
80 : int NumInst = -1;
81 :
82 : /// Numeric ids for interesting instructions.
83 : DenseMap<Instruction *, unsigned> InstructionNumbering;
84 :
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;
88 :
89 : ArrayRef<AllocaInst *> Allocas;
90 : unsigned NumAllocas;
91 : DenseMap<AllocaInst *, unsigned> AllocaNumbering;
92 :
93 : /// LiveRange for allocas.
94 : SmallVector<LiveRange, 8> LiveRanges;
95 :
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;
100 :
101 : struct Marker {
102 : unsigned AllocaNo;
103 : bool IsStart;
104 : };
105 :
106 : /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo.
107 : DenseMap<BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>> BBMarkers;
108 :
109 : void dumpAllocas();
110 : void dumpBlockLiveness();
111 : void dumpLiveRanges();
112 :
113 : bool readMarker(Instruction *I, bool *IsStart);
114 : void collectMarkers();
115 : void calculateLocalLiveness();
116 : void calculateLiveIntervals();
117 :
118 : public:
119 152 : StackColoring(Function &F, ArrayRef<AllocaInst *> Allocas)
120 152 : : F(F), Allocas(Allocas), NumAllocas(Allocas.size()) {}
121 :
122 : void run();
123 : void removeAllMarkers();
124 :
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);
129 :
130 : /// Returns a live range that represents an alloca that is live throughout the
131 : /// entire function.
132 0 : LiveRange getFullLiveRange() {
133 : assert(NumInst >= 0);
134 : LiveRange R;
135 : R.SetMaximum(NumInst);
136 0 : R.AddRange(0, NumInst);
137 0 : return R;
138 : }
139 : };
140 :
141 0 : static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) {
142 0 : OS << "{";
143 : int idx = V.find_first();
144 : bool first = true;
145 0 : while (idx >= 0) {
146 0 : if (!first) {
147 0 : OS << ", ";
148 : }
149 : first = false;
150 : OS << idx;
151 0 : idx = V.find_next(idx);
152 : }
153 0 : OS << "}";
154 0 : return OS;
155 : }
156 :
157 : static inline raw_ostream &operator<<(raw_ostream &OS,
158 : const StackColoring::LiveRange &R) {
159 0 : return OS << R.bv;
160 : }
161 :
162 : } // end namespace safestack
163 :
164 : } // end namespace llvm
165 :
166 : #endif // LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H
|
