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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
//===- StackLifetime.h - Alloca Lifetime Analysis --------------*- 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_ANALYSIS_STACKLIFETIME_H
#define LLVM_ANALYSIS_STACKLIFETIME_H
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <utility>
namespace llvm {
class AllocaInst;
class BasicBlock;
class Function;
class Instruction;
/// 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 StackLifetime {
/// 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 {
explicit BlockLifetimeInfo(unsigned Size)
: Begin(Size), End(Size), LiveIn(Size), LiveOut(Size) {}
/// 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:
class LifetimeAnnotationWriter;
/// This class represents a set of interesting instructions where an alloca is
/// live.
class LiveRange {
BitVector Bits;
friend raw_ostream &operator<<(raw_ostream &OS,
const StackLifetime::LiveRange &R);
public:
LiveRange(unsigned Size, bool Set = false) : Bits(Size, Set) {}
void addRange(unsigned Start, unsigned End) { Bits.set(Start, End); }
bool overlaps(const LiveRange &Other) const {
return Bits.anyCommon(Other.Bits);
}
void join(const LiveRange &Other) { Bits |= Other.Bits; }
bool test(unsigned Idx) const { return Bits.test(Idx); }
};
// Controls what is "alive" if control flow may reach the instruction
// with a different liveness of the alloca.
enum class LivenessType {
May, // May be alive on some path.
Must, // Must be alive on every path.
};
private:
const Function &F;
LivenessType Type;
/// Maps active slots (per bit) for each basic block.
using LivenessMap = DenseMap<const BasicBlock *, BlockLifetimeInfo>;
LivenessMap BlockLiveness;
/// Interesting instructions. Instructions of the same block are adjustent
/// preserve in-block order.
SmallVector<const IntrinsicInst *, 64> Instructions;
/// 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<const AllocaInst *> Allocas;
unsigned NumAllocas;
DenseMap<const 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;
struct Marker {
unsigned AllocaNo;
bool IsStart;
};
/// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo.
DenseMap<const BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>>
BBMarkers;
bool HasUnknownLifetimeStartOrEnd = false;
void dumpAllocas() const;
void dumpBlockLiveness() const;
void dumpLiveRanges() const;
void collectMarkers();
void calculateLocalLiveness();
void calculateLiveIntervals();
public:
StackLifetime(const Function &F, ArrayRef<const AllocaInst *> Allocas,
LivenessType Type);
void run();
iterator_range<
filter_iterator<ArrayRef<const IntrinsicInst *>::const_iterator,
std::function<bool(const IntrinsicInst *)>>>
getMarkers() const {
std::function<bool(const IntrinsicInst *)> NotNull(
[](const IntrinsicInst *I) -> bool { return I; });
return make_filter_range(Instructions, NotNull);
}
/// 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(const AllocaInst *AI) const;
/// Returns true if instruction is reachable from entry.
bool isReachable(const Instruction *I) const;
/// Returns true if the alloca is alive after the instruction.
bool isAliveAfter(const AllocaInst *AI, const Instruction *I) const;
/// Returns a live range that represents an alloca that is live throughout the
/// entire function.
LiveRange getFullLiveRange() const {
return LiveRange(Instructions.size(), true);
}
void print(raw_ostream &O);
};
static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) {
OS << "{";
ListSeparator LS;
for (int Idx = V.find_first(); Idx >= 0; Idx = V.find_next(Idx))
OS << LS << Idx;
OS << "}";
return OS;
}
inline raw_ostream &operator<<(raw_ostream &OS,
const StackLifetime::LiveRange &R) {
return OS << R.Bits;
}
/// Printer pass for testing.
class StackLifetimePrinterPass
: public PassInfoMixin<StackLifetimePrinterPass> {
StackLifetime::LivenessType Type;
raw_ostream &OS;
public:
StackLifetimePrinterPass(raw_ostream &OS, StackLifetime::LivenessType Type)
: Type(Type), OS(OS) {}
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
};
} // end namespace llvm
#endif // LLVM_ANALYSIS_STACKLIFETIME_H
|
