15 #include "llvm/Config/llvm-config.h" 35 #define DEBUG_TYPE "safestackcoloring" 39 cl::desc(
"enable safe stack coloring"),
43 const auto IT = AllocaNumbering.find(AI);
45 return LiveRanges[
IT->second];
48 bool StackColoring::readMarker(
Instruction *
I,
bool *IsStart) {
52 auto *II = cast<IntrinsicInst>(
I);
58 for (
auto *I : Markers) {
62 if (
Op &&
Op->use_empty())
63 Op->eraseFromParent();
67 void StackColoring::collectMarkers() {
68 InterestingAllocas.
resize(NumAllocas);
72 for (
unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
76 while (!WorkList.
empty()) {
79 if (
auto *BI = dyn_cast<BitCastInst>(U)) {
87 if (!readMarker(UI, &IsStart))
90 InterestingAllocas.
set(AllocaNo);
91 BBMarkerSet[UI->getParent()][UI] = {AllocaNo, IsStart};
92 Markers.push_back(UI);
107 LLVM_DEBUG(
dbgs() <<
" " << InstNo <<
": BB " << BB->getName() <<
"\n");
108 unsigned BBStart = InstNo++;
110 BlockLifetimeInfo &BlockInfo = BlockLiveness[BB];
111 BlockInfo.Begin.resize(NumAllocas);
112 BlockInfo.End.resize(NumAllocas);
113 BlockInfo.LiveIn.resize(NumAllocas);
114 BlockInfo.LiveOut.resize(NumAllocas);
116 auto &BlockMarkerSet = BBMarkerSet[BB];
117 if (BlockMarkerSet.empty()) {
118 unsigned BBEnd = InstNo;
119 BlockInstRange[BB] = std::make_pair(BBStart, BBEnd);
123 auto ProcessMarker = [&](
Instruction *
I,
const Marker &M) {
125 << (M.IsStart ?
"start " :
"end ") << M.AllocaNo
126 <<
", " << *I <<
"\n");
128 BBMarkers[BB].push_back({InstNo, M});
130 InstructionNumbering[
I] = InstNo++;
133 if (BlockInfo.End.test(M.AllocaNo))
134 BlockInfo.End.reset(M.AllocaNo);
135 BlockInfo.Begin.set(M.AllocaNo);
137 if (BlockInfo.Begin.test(M.AllocaNo))
138 BlockInfo.Begin.reset(M.AllocaNo);
139 BlockInfo.End.set(M.AllocaNo);
143 if (BlockMarkerSet.size() == 1) {
144 ProcessMarker(BlockMarkerSet.begin()->getFirst(),
145 BlockMarkerSet.begin()->getSecond());
149 auto It = BlockMarkerSet.find(&I);
150 if (It == BlockMarkerSet.end())
152 ProcessMarker(&I, It->getSecond());
156 unsigned BBEnd = InstNo;
157 BlockInstRange[BB] = std::make_pair(BBStart, BBEnd);
162 void StackColoring::calculateLocalLiveness() {
168 BlockLifetimeInfo &BlockInfo = BlockLiveness[BB];
175 if (I == BlockLiveness.
end())
177 LocalLiveIn |= I->second.LiveOut;
188 LocalLiveOut.
reset(BlockInfo.End);
189 LocalLiveOut |= BlockInfo.Begin;
192 if (LocalLiveIn.
test(BlockInfo.LiveIn)) {
194 BlockInfo.LiveIn |= LocalLiveIn;
198 if (LocalLiveOut.
test(BlockInfo.LiveOut)) {
200 BlockInfo.LiveOut |= LocalLiveOut;
206 void StackColoring::calculateLiveIntervals() {
207 for (
auto IT : BlockLiveness) {
209 BlockLifetimeInfo &BlockInfo =
IT.getSecond();
210 unsigned BBStart, BBEnd;
211 std::tie(BBStart, BBEnd) = BlockInstRange[BB];
214 Started.
resize(NumAllocas);
220 for (
unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
221 if (BlockInfo.LiveIn.test(AllocaNo)) {
222 Started.
set(AllocaNo);
223 Start[AllocaNo] = BBStart;
227 for (
auto &It : BBMarkers[BB]) {
228 unsigned InstNo = It.first;
229 bool IsStart = It.second.IsStart;
230 unsigned AllocaNo = It.second.AllocaNo;
233 assert(!Started.
test(AllocaNo) || Start[AllocaNo] == BBStart);
234 if (!Started.
test(AllocaNo)) {
235 Started.
set(AllocaNo);
236 Ended.
reset(AllocaNo);
237 Start[AllocaNo] = InstNo;
241 if (Started.
test(AllocaNo)) {
242 LiveRanges[AllocaNo].AddRange(Start[AllocaNo], InstNo);
243 Started.
reset(AllocaNo);
249 for (
unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
250 if (Started.
test(AllocaNo))
251 LiveRanges[AllocaNo].AddRange(Start[AllocaNo], BBEnd);
255 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 257 dbgs() <<
"Allocas:\n";
258 for (
unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
259 dbgs() <<
" " << AllocaNo <<
": " << *Allocas[AllocaNo] <<
"\n";
263 dbgs() <<
"Block liveness:\n";
264 for (
auto IT : BlockLiveness) {
266 BlockLifetimeInfo &BlockInfo = BlockLiveness[BB];
267 auto BlockRange = BlockInstRange[BB];
268 dbgs() <<
" BB [" << BlockRange.first <<
", " << BlockRange.second
269 <<
"): begin " << BlockInfo.Begin <<
", end " << BlockInfo.End
270 <<
", livein " << BlockInfo.LiveIn <<
", liveout " 271 << BlockInfo.LiveOut <<
"\n";
276 dbgs() <<
"Alloca liveness:\n";
277 for (
unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
279 dbgs() <<
" " << AllocaNo <<
": " << Range <<
"\n";
287 for (
unsigned I = 0; I < NumAllocas; ++
I)
288 AllocaNumbering[Allocas[I]] = I;
289 LiveRanges.resize(NumAllocas);
294 for (
auto &R : LiveRanges) {
301 for (
auto &R : LiveRanges)
302 R.SetMaximum(NumInst);
303 for (
unsigned I = 0; I < NumAllocas; ++
I)
304 if (!InterestingAllocas.
test(I))
307 calculateLocalLiveness();
309 calculateLiveIntervals();
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
This class represents a set of interesting instructions where an alloca is live.
This class represents lattice values for constants.
void push_back(const T &Elt)
bool test(unsigned Idx) const
const LiveRange & getLiveRange(AllocaInst *AI)
Returns a set of "interesting" instructions where the given alloca is live.
LiveRange getFullLiveRange()
Returns a live range that represents an alloca that is live throughout the entire function...
static cl::opt< bool > ClColoring("safe-stack-coloring", cl::desc("enable safe stack coloring"), cl::Hidden, cl::init(false))
Value * getOperand(unsigned i) const
iterator find(const_arg_type_t< KeyT > Val)
initializer< Ty > init(const Ty &Val)
LLVM Basic Block Representation.
bool isLifetimeStartOrEnd() const
Return true if the instruction is a llvm.lifetime.start or llvm.lifetime.end marker.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
LLVM_NODISCARD T pop_back_val()
pred_range predecessors(BasicBlock *BB)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
iterator_range< user_iterator > users()
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::ZeroOrMore, cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate IT block based on arch"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow deprecated IT based on ARMv8"), clEnumValN(NoRestrictedIT, "arm-no-restrict-it", "Allow IT blocks based on ARMv7")))
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
LLVM_NODISCARD bool empty() const
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
iterator_range< df_iterator< T > > depth_first(const T &G)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
an instruction to allocate memory on the stack