Line data Source code
1 : //===- SafeStackColoring.cpp - SafeStack frame coloring -------------------===//
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 : #include "SafeStackColoring.h"
11 : #include "llvm/ADT/BitVector.h"
12 : #include "llvm/ADT/DenseMap.h"
13 : #include "llvm/ADT/DepthFirstIterator.h"
14 : #include "llvm/ADT/SmallVector.h"
15 : #include "llvm/Config/llvm-config.h"
16 : #include "llvm/IR/BasicBlock.h"
17 : #include "llvm/IR/CFG.h"
18 : #include "llvm/IR/Instruction.h"
19 : #include "llvm/IR/Instructions.h"
20 : #include "llvm/IR/IntrinsicInst.h"
21 : #include "llvm/IR/Intrinsics.h"
22 : #include "llvm/IR/User.h"
23 : #include "llvm/Support/Casting.h"
24 : #include "llvm/Support/CommandLine.h"
25 : #include "llvm/Support/Compiler.h"
26 : #include "llvm/Support/Debug.h"
27 : #include "llvm/Support/raw_ostream.h"
28 : #include <cassert>
29 : #include <tuple>
30 : #include <utility>
31 :
32 : using namespace llvm;
33 : using namespace llvm::safestack;
34 :
35 : #define DEBUG_TYPE "safestackcoloring"
36 :
37 : // Disabled by default due to PR32143.
38 : static cl::opt<bool> ClColoring("safe-stack-coloring",
39 : cl::desc("enable safe stack coloring"),
40 : cl::Hidden, cl::init(false));
41 :
42 232 : const StackColoring::LiveRange &StackColoring::getLiveRange(AllocaInst *AI) {
43 232 : const auto IT = AllocaNumbering.find(AI);
44 : assert(IT != AllocaNumbering.end());
45 464 : return LiveRanges[IT->second];
46 : }
47 :
48 448 : bool StackColoring::readMarker(Instruction *I, bool *IsStart) {
49 : auto *II = dyn_cast<IntrinsicInst>(I);
50 182 : if (!II || (II->getIntrinsicID() != Intrinsic::lifetime_start &&
51 : II->getIntrinsicID() != Intrinsic::lifetime_end))
52 : return false;
53 :
54 180 : *IsStart = II->getIntrinsicID() == Intrinsic::lifetime_start;
55 180 : return true;
56 : }
57 :
58 152 : void StackColoring::removeAllMarkers() {
59 332 : for (auto *I : Markers) {
60 180 : auto *Op = dyn_cast<Instruction>(I->getOperand(1));
61 180 : I->eraseFromParent();
62 : // Remove the operand bitcast, too, if it has no more uses left.
63 180 : if (Op && Op->use_empty())
64 78 : Op->eraseFromParent();
65 : }
66 152 : }
67 :
68 152 : void StackColoring::collectMarkers() {
69 152 : InterestingAllocas.resize(NumAllocas);
70 : DenseMap<BasicBlock *, SmallDenseMap<Instruction *, Marker>> BBMarkerSet;
71 :
72 : // Compute the set of start/end markers per basic block.
73 384 : for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
74 464 : AllocaInst *AI = Allocas[AllocaNo];
75 : SmallVector<Instruction *, 8> WorkList;
76 232 : WorkList.push_back(AI);
77 560 : while (!WorkList.empty()) {
78 : Instruction *I = WorkList.pop_back_val();
79 872 : for (User *U : I->users()) {
80 : if (auto *BI = dyn_cast<BitCastInst>(U)) {
81 96 : WorkList.push_back(BI);
82 364 : continue;
83 : }
84 448 : auto *UI = dyn_cast<Instruction>(U);
85 448 : if (!UI)
86 : continue;
87 : bool IsStart;
88 448 : if (!readMarker(UI, &IsStart))
89 : continue;
90 180 : if (IsStart)
91 : InterestingAllocas.set(AllocaNo);
92 180 : BBMarkerSet[UI->getParent()][UI] = {AllocaNo, IsStart};
93 180 : Markers.push_back(UI);
94 : }
95 : }
96 : }
97 :
98 : // Compute instruction numbering. Only the following instructions are
99 : // considered:
100 : // * Basic block entries
101 : // * Lifetime markers
102 : // For each basic block, compute
103 : // * the list of markers in the instruction order
104 : // * the sets of allocas whose lifetime starts or ends in this BB
105 : LLVM_DEBUG(dbgs() << "Instructions:\n");
106 152 : unsigned InstNo = 0;
107 561 : for (BasicBlock *BB : depth_first(&F)) {
108 : LLVM_DEBUG(dbgs() << " " << InstNo << ": BB " << BB->getName() << "\n");
109 257 : unsigned BBStart = InstNo++;
110 :
111 257 : BlockLifetimeInfo &BlockInfo = BlockLiveness[BB];
112 257 : BlockInfo.Begin.resize(NumAllocas);
113 257 : BlockInfo.End.resize(NumAllocas);
114 257 : BlockInfo.LiveIn.resize(NumAllocas);
115 257 : BlockInfo.LiveOut.resize(NumAllocas);
116 :
117 : auto &BlockMarkerSet = BBMarkerSet[BB];
118 257 : if (BlockMarkerSet.empty()) {
119 187 : unsigned BBEnd = InstNo;
120 187 : BlockInstRange[BB] = std::make_pair(BBStart, BBEnd);
121 : continue;
122 : }
123 :
124 : auto ProcessMarker = [&](Instruction *I, const Marker &M) {
125 : LLVM_DEBUG(dbgs() << " " << InstNo << ": "
126 : << (M.IsStart ? "start " : "end ") << M.AllocaNo
127 : << ", " << *I << "\n");
128 :
129 : BBMarkers[BB].push_back({InstNo, M});
130 :
131 : InstructionNumbering[I] = InstNo++;
132 :
133 : if (M.IsStart) {
134 : if (BlockInfo.End.test(M.AllocaNo))
135 : BlockInfo.End.reset(M.AllocaNo);
136 : BlockInfo.Begin.set(M.AllocaNo);
137 : } else {
138 : if (BlockInfo.Begin.test(M.AllocaNo))
139 : BlockInfo.Begin.reset(M.AllocaNo);
140 : BlockInfo.End.set(M.AllocaNo);
141 : }
142 70 : };
143 :
144 70 : if (BlockMarkerSet.size() == 1) {
145 26 : ProcessMarker(BlockMarkerSet.begin()->getFirst(),
146 52 : BlockMarkerSet.begin()->getSecond());
147 : } else {
148 : // Scan the BB to determine the marker order.
149 503 : for (Instruction &I : *BB) {
150 459 : auto It = BlockMarkerSet.find(&I);
151 459 : if (It == BlockMarkerSet.end())
152 305 : continue;
153 154 : ProcessMarker(&I, It->getSecond());
154 : }
155 : }
156 :
157 70 : unsigned BBEnd = InstNo;
158 70 : BlockInstRange[BB] = std::make_pair(BBStart, BBEnd);
159 : }
160 152 : NumInst = InstNo;
161 152 : }
162 :
163 37 : void StackColoring::calculateLocalLiveness() {
164 : bool changed = true;
165 90 : while (changed) {
166 : changed = false;
167 :
168 244 : for (BasicBlock *BB : depth_first(&F)) {
169 138 : BlockLifetimeInfo &BlockInfo = BlockLiveness[BB];
170 :
171 : // Compute LiveIn by unioning together the LiveOut sets of all preds.
172 : BitVector LocalLiveIn;
173 138 : for (auto *PredBB : predecessors(BB)) {
174 106 : LivenessMap::const_iterator I = BlockLiveness.find(PredBB);
175 : // If a predecessor is unreachable, ignore it.
176 106 : if (I == BlockLiveness.end())
177 : continue;
178 105 : LocalLiveIn |= I->second.LiveOut;
179 : }
180 :
181 : // Compute LiveOut by subtracting out lifetimes that end in this
182 : // block, then adding in lifetimes that begin in this block. If
183 : // we have both BEGIN and END markers in the same basic block
184 : // then we know that the BEGIN marker comes after the END,
185 : // because we already handle the case where the BEGIN comes
186 : // before the END when collecting the markers (and building the
187 : // BEGIN/END vectors).
188 138 : BitVector LocalLiveOut = LocalLiveIn;
189 138 : LocalLiveOut.reset(BlockInfo.End);
190 138 : LocalLiveOut |= BlockInfo.Begin;
191 :
192 : // Update block LiveIn set, noting whether it has changed.
193 138 : if (LocalLiveIn.test(BlockInfo.LiveIn)) {
194 : changed = true;
195 30 : BlockInfo.LiveIn |= LocalLiveIn;
196 : }
197 :
198 : // Update block LiveOut set, noting whether it has changed.
199 138 : if (LocalLiveOut.test(BlockInfo.LiveOut)) {
200 : changed = true;
201 38 : BlockInfo.LiveOut |= LocalLiveOut;
202 : }
203 : }
204 : } // while changed.
205 37 : }
206 :
207 37 : void StackColoring::calculateLiveIntervals() {
208 121 : for (auto IT : BlockLiveness) {
209 84 : BasicBlock *BB = IT.getFirst();
210 : BlockLifetimeInfo &BlockInfo = IT.getSecond();
211 : unsigned BBStart, BBEnd;
212 84 : std::tie(BBStart, BBEnd) = BlockInstRange[BB];
213 :
214 : BitVector Started, Ended;
215 84 : Started.resize(NumAllocas);
216 84 : Ended.resize(NumAllocas);
217 : SmallVector<unsigned, 8> Start;
218 84 : Start.resize(NumAllocas);
219 :
220 : // LiveIn ranges start at the first instruction.
221 379 : for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
222 295 : if (BlockInfo.LiveIn.test(AllocaNo)) {
223 : Started.set(AllocaNo);
224 120 : Start[AllocaNo] = BBStart;
225 : }
226 : }
227 :
228 348 : for (auto &It : BBMarkers[BB]) {
229 180 : unsigned InstNo = It.first;
230 180 : bool IsStart = It.second.IsStart;
231 180 : unsigned AllocaNo = It.second.AllocaNo;
232 :
233 180 : if (IsStart) {
234 : assert(!Started.test(AllocaNo) || Start[AllocaNo] == BBStart);
235 95 : if (!Started.test(AllocaNo)) {
236 : Started.set(AllocaNo);
237 : Ended.reset(AllocaNo);
238 186 : Start[AllocaNo] = InstNo;
239 : }
240 : } else {
241 : assert(!Ended.test(AllocaNo));
242 85 : if (Started.test(AllocaNo)) {
243 166 : LiveRanges[AllocaNo].AddRange(Start[AllocaNo], InstNo);
244 : Started.reset(AllocaNo);
245 : }
246 : Ended.set(AllocaNo);
247 : }
248 : }
249 :
250 379 : for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
251 295 : if (Started.test(AllocaNo))
252 140 : LiveRanges[AllocaNo].AddRange(Start[AllocaNo], BBEnd);
253 : }
254 37 : }
255 :
256 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
257 : LLVM_DUMP_METHOD void StackColoring::dumpAllocas() {
258 : dbgs() << "Allocas:\n";
259 : for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)
260 : dbgs() << " " << AllocaNo << ": " << *Allocas[AllocaNo] << "\n";
261 : }
262 :
263 : LLVM_DUMP_METHOD void StackColoring::dumpBlockLiveness() {
264 : dbgs() << "Block liveness:\n";
265 : for (auto IT : BlockLiveness) {
266 : BasicBlock *BB = IT.getFirst();
267 : BlockLifetimeInfo &BlockInfo = BlockLiveness[BB];
268 : auto BlockRange = BlockInstRange[BB];
269 : dbgs() << " BB [" << BlockRange.first << ", " << BlockRange.second
270 : << "): begin " << BlockInfo.Begin << ", end " << BlockInfo.End
271 : << ", livein " << BlockInfo.LiveIn << ", liveout "
272 : << BlockInfo.LiveOut << "\n";
273 : }
274 : }
275 :
276 : LLVM_DUMP_METHOD void StackColoring::dumpLiveRanges() {
277 : dbgs() << "Alloca liveness:\n";
278 : for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) {
279 : LiveRange &Range = LiveRanges[AllocaNo];
280 : dbgs() << " " << AllocaNo << ": " << Range << "\n";
281 : }
282 : }
283 : #endif
284 :
285 152 : void StackColoring::run() {
286 : LLVM_DEBUG(dumpAllocas());
287 :
288 384 : for (unsigned I = 0; I < NumAllocas; ++I)
289 464 : AllocaNumbering[Allocas[I]] = I;
290 152 : LiveRanges.resize(NumAllocas);
291 :
292 152 : collectMarkers();
293 :
294 152 : if (!ClColoring) {
295 251 : for (auto &R : LiveRanges) {
296 : R.SetMaximum(1);
297 : R.AddRange(0, 1);
298 : }
299 : return;
300 : }
301 :
302 133 : for (auto &R : LiveRanges)
303 96 : R.SetMaximum(NumInst);
304 133 : for (unsigned I = 0; I < NumAllocas; ++I)
305 96 : if (!InterestingAllocas.test(I))
306 10 : LiveRanges[I] = getFullLiveRange();
307 :
308 37 : calculateLocalLiveness();
309 : LLVM_DEBUG(dumpBlockLiveness());
310 37 : calculateLiveIntervals();
311 : LLVM_DEBUG(dumpLiveRanges());
312 : }
|
