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