1 //===- StackLifetime.cpp - Alloca Lifetime Analysis -----------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Analysis/StackLifetime.h" 10 #include "llvm/ADT/DepthFirstIterator.h" 11 #include "llvm/ADT/STLExtras.h" 12 #include "llvm/ADT/SmallVector.h" 13 #include "llvm/ADT/StringExtras.h" 14 #include "llvm/Analysis/ValueTracking.h" 15 #include "llvm/Config/llvm-config.h" 16 #include "llvm/IR/AssemblyAnnotationWriter.h" 17 #include "llvm/IR/BasicBlock.h" 18 #include "llvm/IR/CFG.h" 19 #include "llvm/IR/InstIterator.h" 20 #include "llvm/IR/Instructions.h" 21 #include "llvm/IR/IntrinsicInst.h" 22 #include "llvm/IR/Value.h" 23 #include "llvm/Support/Casting.h" 24 #include "llvm/Support/Compiler.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Support/FormattedStream.h" 27 #include <algorithm> 28 #include <tuple> 29 30 using namespace llvm; 31 32 #define DEBUG_TYPE "stack-lifetime" 33 34 const StackLifetime::LiveRange & 35 StackLifetime::getLiveRange(const AllocaInst *AI) const { 36 const auto IT = AllocaNumbering.find(AI); 37 assert(IT != AllocaNumbering.end()); 38 return LiveRanges[IT->second]; 39 } 40 41 bool StackLifetime::isReachable(const Instruction *I) const { 42 return BlockInstRange.contains(I->getParent()); 43 } 44 45 bool StackLifetime::isAliveAfter(const AllocaInst *AI, 46 const Instruction *I) const { 47 const BasicBlock *BB = I->getParent(); 48 auto ItBB = BlockInstRange.find(BB); 49 assert(ItBB != BlockInstRange.end() && "Unreachable is not expected"); 50 51 // Search the block for the first instruction following 'I'. 52 auto It = std::upper_bound(Instructions.begin() + ItBB->getSecond().first + 1, 53 Instructions.begin() + ItBB->getSecond().second, I, 54 [](const Instruction *L, const Instruction *R) { 55 return L->comesBefore(R); 56 }); 57 --It; 58 unsigned InstNum = It - Instructions.begin(); 59 return getLiveRange(AI).test(InstNum); 60 } 61 62 // Returns unique alloca annotated by lifetime marker only if 63 // markers has the same size and points to the alloca start. 64 static const AllocaInst *findMatchingAlloca(const IntrinsicInst &II, 65 const DataLayout &DL) { 66 const AllocaInst *AI = findAllocaForValue(II.getArgOperand(1), true); 67 if (!AI) 68 return nullptr; 69 70 auto AllocaSize = AI->getAllocationSize(DL); 71 if (!AllocaSize) 72 return nullptr; 73 74 auto *Size = dyn_cast<ConstantInt>(II.getArgOperand(0)); 75 if (!Size) 76 return nullptr; 77 int64_t LifetimeSize = Size->getSExtValue(); 78 79 if (LifetimeSize != -1 && uint64_t(LifetimeSize) != *AllocaSize) 80 return nullptr; 81 82 return AI; 83 } 84 85 void StackLifetime::collectMarkers() { 86 InterestingAllocas.resize(NumAllocas); 87 DenseMap<const BasicBlock *, SmallDenseMap<const IntrinsicInst *, Marker>> 88 BBMarkerSet; 89 90 const DataLayout &DL = F.getParent()->getDataLayout(); 91 92 // Compute the set of start/end markers per basic block. 93 for (const BasicBlock *BB : depth_first(&F)) { 94 for (const Instruction &I : *BB) { 95 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I); 96 if (!II || !II->isLifetimeStartOrEnd()) 97 continue; 98 const AllocaInst *AI = findMatchingAlloca(*II, DL); 99 if (!AI) { 100 HasUnknownLifetimeStartOrEnd = true; 101 continue; 102 } 103 auto It = AllocaNumbering.find(AI); 104 if (It == AllocaNumbering.end()) 105 continue; 106 auto AllocaNo = It->second; 107 bool IsStart = II->getIntrinsicID() == Intrinsic::lifetime_start; 108 if (IsStart) 109 InterestingAllocas.set(AllocaNo); 110 BBMarkerSet[BB][II] = {AllocaNo, IsStart}; 111 } 112 } 113 114 // Compute instruction numbering. Only the following instructions are 115 // considered: 116 // * Basic block entries 117 // * Lifetime markers 118 // For each basic block, compute 119 // * the list of markers in the instruction order 120 // * the sets of allocas whose lifetime starts or ends in this BB 121 LLVM_DEBUG(dbgs() << "Instructions:\n"); 122 for (const BasicBlock *BB : depth_first(&F)) { 123 LLVM_DEBUG(dbgs() << " " << Instructions.size() << ": BB " << BB->getName() 124 << "\n"); 125 auto BBStart = Instructions.size(); 126 Instructions.push_back(nullptr); 127 128 BlockLifetimeInfo &BlockInfo = 129 BlockLiveness.try_emplace(BB, NumAllocas).first->getSecond(); 130 131 auto &BlockMarkerSet = BBMarkerSet[BB]; 132 if (BlockMarkerSet.empty()) { 133 BlockInstRange[BB] = std::make_pair(BBStart, Instructions.size()); 134 continue; 135 } 136 137 auto ProcessMarker = [&](const IntrinsicInst *I, const Marker &M) { 138 LLVM_DEBUG(dbgs() << " " << Instructions.size() << ": " 139 << (M.IsStart ? "start " : "end ") << M.AllocaNo 140 << ", " << *I << "\n"); 141 142 BBMarkers[BB].push_back({Instructions.size(), M}); 143 Instructions.push_back(I); 144 145 if (M.IsStart) { 146 BlockInfo.End.reset(M.AllocaNo); 147 BlockInfo.Begin.set(M.AllocaNo); 148 } else { 149 BlockInfo.Begin.reset(M.AllocaNo); 150 BlockInfo.End.set(M.AllocaNo); 151 } 152 }; 153 154 if (BlockMarkerSet.size() == 1) { 155 ProcessMarker(BlockMarkerSet.begin()->getFirst(), 156 BlockMarkerSet.begin()->getSecond()); 157 } else { 158 // Scan the BB to determine the marker order. 159 for (const Instruction &I : *BB) { 160 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I); 161 if (!II) 162 continue; 163 auto It = BlockMarkerSet.find(II); 164 if (It == BlockMarkerSet.end()) 165 continue; 166 ProcessMarker(II, It->getSecond()); 167 } 168 } 169 170 BlockInstRange[BB] = std::make_pair(BBStart, Instructions.size()); 171 } 172 } 173 174 void StackLifetime::calculateLocalLiveness() { 175 bool Changed = true; 176 177 // LiveIn, LiveOut and BitsIn have a different meaning deppends on type. 178 // ::Maybe true bits represent "may be alive" allocas, ::Must true bits 179 // represent "may be dead". After the loop we will convert ::Must bits from 180 // "may be dead" to "must be alive". 181 while (Changed) { 182 // TODO: Consider switching to worklist instead of traversing entire graph. 183 Changed = false; 184 185 for (const BasicBlock *BB : depth_first(&F)) { 186 BlockLifetimeInfo &BlockInfo = BlockLiveness.find(BB)->getSecond(); 187 188 // Compute BitsIn by unioning together the LiveOut sets of all preds. 189 BitVector BitsIn; 190 for (const auto *PredBB : predecessors(BB)) { 191 LivenessMap::const_iterator I = BlockLiveness.find(PredBB); 192 // If a predecessor is unreachable, ignore it. 193 if (I == BlockLiveness.end()) 194 continue; 195 BitsIn |= I->second.LiveOut; 196 } 197 198 // Everything is "may be dead" for entry without predecessors. 199 if (Type == LivenessType::Must && BitsIn.empty()) 200 BitsIn.resize(NumAllocas, true); 201 202 // Update block LiveIn set, noting whether it has changed. 203 if (BitsIn.test(BlockInfo.LiveIn)) { 204 BlockInfo.LiveIn |= BitsIn; 205 } 206 207 // Compute LiveOut by subtracting out lifetimes that end in this 208 // block, then adding in lifetimes that begin in this block. If 209 // we have both BEGIN and END markers in the same basic block 210 // then we know that the BEGIN marker comes after the END, 211 // because we already handle the case where the BEGIN comes 212 // before the END when collecting the markers (and building the 213 // BEGIN/END vectors). 214 switch (Type) { 215 case LivenessType::May: 216 BitsIn.reset(BlockInfo.End); 217 // "may be alive" is set by lifetime start. 218 BitsIn |= BlockInfo.Begin; 219 break; 220 case LivenessType::Must: 221 BitsIn.reset(BlockInfo.Begin); 222 // "may be dead" is set by lifetime end. 223 BitsIn |= BlockInfo.End; 224 break; 225 } 226 227 // Update block LiveOut set, noting whether it has changed. 228 if (BitsIn.test(BlockInfo.LiveOut)) { 229 Changed = true; 230 BlockInfo.LiveOut |= BitsIn; 231 } 232 } 233 } // while changed. 234 235 if (Type == LivenessType::Must) { 236 // Convert from "may be dead" to "must be alive". 237 for (auto &[BB, BlockInfo] : BlockLiveness) { 238 BlockInfo.LiveIn.flip(); 239 BlockInfo.LiveOut.flip(); 240 } 241 } 242 } 243 244 void StackLifetime::calculateLiveIntervals() { 245 for (auto IT : BlockLiveness) { 246 const BasicBlock *BB = IT.getFirst(); 247 BlockLifetimeInfo &BlockInfo = IT.getSecond(); 248 unsigned BBStart, BBEnd; 249 std::tie(BBStart, BBEnd) = BlockInstRange[BB]; 250 251 BitVector Started, Ended; 252 Started.resize(NumAllocas); 253 Ended.resize(NumAllocas); 254 SmallVector<unsigned, 8> Start; 255 Start.resize(NumAllocas); 256 257 // LiveIn ranges start at the first instruction. 258 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) { 259 if (BlockInfo.LiveIn.test(AllocaNo)) { 260 Started.set(AllocaNo); 261 Start[AllocaNo] = BBStart; 262 } 263 } 264 265 for (auto &It : BBMarkers[BB]) { 266 unsigned InstNo = It.first; 267 bool IsStart = It.second.IsStart; 268 unsigned AllocaNo = It.second.AllocaNo; 269 270 if (IsStart) { 271 if (!Started.test(AllocaNo)) { 272 Started.set(AllocaNo); 273 Ended.reset(AllocaNo); 274 Start[AllocaNo] = InstNo; 275 } 276 } else { 277 if (Started.test(AllocaNo)) { 278 LiveRanges[AllocaNo].addRange(Start[AllocaNo], InstNo); 279 Started.reset(AllocaNo); 280 } 281 Ended.set(AllocaNo); 282 } 283 } 284 285 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) 286 if (Started.test(AllocaNo)) 287 LiveRanges[AllocaNo].addRange(Start[AllocaNo], BBEnd); 288 } 289 } 290 291 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 292 LLVM_DUMP_METHOD void StackLifetime::dumpAllocas() const { 293 dbgs() << "Allocas:\n"; 294 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) 295 dbgs() << " " << AllocaNo << ": " << *Allocas[AllocaNo] << "\n"; 296 } 297 298 LLVM_DUMP_METHOD void StackLifetime::dumpBlockLiveness() const { 299 dbgs() << "Block liveness:\n"; 300 for (auto IT : BlockLiveness) { 301 const BasicBlock *BB = IT.getFirst(); 302 const BlockLifetimeInfo &BlockInfo = BlockLiveness.find(BB)->getSecond(); 303 auto BlockRange = BlockInstRange.find(BB)->getSecond(); 304 dbgs() << " BB (" << BB->getName() << ") [" << BlockRange.first << ", " << BlockRange.second 305 << "): begin " << BlockInfo.Begin << ", end " << BlockInfo.End 306 << ", livein " << BlockInfo.LiveIn << ", liveout " 307 << BlockInfo.LiveOut << "\n"; 308 } 309 } 310 311 LLVM_DUMP_METHOD void StackLifetime::dumpLiveRanges() const { 312 dbgs() << "Alloca liveness:\n"; 313 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) 314 dbgs() << " " << AllocaNo << ": " << LiveRanges[AllocaNo] << "\n"; 315 } 316 #endif 317 318 StackLifetime::StackLifetime(const Function &F, 319 ArrayRef<const AllocaInst *> Allocas, 320 LivenessType Type) 321 : F(F), Type(Type), Allocas(Allocas), NumAllocas(Allocas.size()) { 322 LLVM_DEBUG(dumpAllocas()); 323 324 for (unsigned I = 0; I < NumAllocas; ++I) 325 AllocaNumbering[Allocas[I]] = I; 326 327 collectMarkers(); 328 } 329 330 void StackLifetime::run() { 331 if (HasUnknownLifetimeStartOrEnd) { 332 // There is marker which we can't assign to a specific alloca, so we 333 // fallback to the most conservative results for the type. 334 switch (Type) { 335 case LivenessType::May: 336 LiveRanges.resize(NumAllocas, getFullLiveRange()); 337 break; 338 case LivenessType::Must: 339 LiveRanges.resize(NumAllocas, LiveRange(Instructions.size())); 340 break; 341 } 342 return; 343 } 344 345 LiveRanges.resize(NumAllocas, LiveRange(Instructions.size())); 346 for (unsigned I = 0; I < NumAllocas; ++I) 347 if (!InterestingAllocas.test(I)) 348 LiveRanges[I] = getFullLiveRange(); 349 350 calculateLocalLiveness(); 351 LLVM_DEBUG(dumpBlockLiveness()); 352 calculateLiveIntervals(); 353 LLVM_DEBUG(dumpLiveRanges()); 354 } 355 356 class StackLifetime::LifetimeAnnotationWriter 357 : public AssemblyAnnotationWriter { 358 const StackLifetime &SL; 359 360 void printInstrAlive(unsigned InstrNo, formatted_raw_ostream &OS) { 361 SmallVector<StringRef, 16> Names; 362 for (const auto &KV : SL.AllocaNumbering) { 363 if (SL.LiveRanges[KV.getSecond()].test(InstrNo)) 364 Names.push_back(KV.getFirst()->getName()); 365 } 366 llvm::sort(Names); 367 OS << " ; Alive: <" << llvm::join(Names, " ") << ">\n"; 368 } 369 370 void emitBasicBlockStartAnnot(const BasicBlock *BB, 371 formatted_raw_ostream &OS) override { 372 auto ItBB = SL.BlockInstRange.find(BB); 373 if (ItBB == SL.BlockInstRange.end()) 374 return; // Unreachable. 375 printInstrAlive(ItBB->getSecond().first, OS); 376 } 377 378 void printInfoComment(const Value &V, formatted_raw_ostream &OS) override { 379 const Instruction *Instr = dyn_cast<Instruction>(&V); 380 if (!Instr || !SL.isReachable(Instr)) 381 return; 382 383 SmallVector<StringRef, 16> Names; 384 for (const auto &KV : SL.AllocaNumbering) { 385 if (SL.isAliveAfter(KV.getFirst(), Instr)) 386 Names.push_back(KV.getFirst()->getName()); 387 } 388 llvm::sort(Names); 389 OS << "\n ; Alive: <" << llvm::join(Names, " ") << ">\n"; 390 } 391 392 public: 393 LifetimeAnnotationWriter(const StackLifetime &SL) : SL(SL) {} 394 }; 395 396 void StackLifetime::print(raw_ostream &OS) { 397 LifetimeAnnotationWriter AAW(*this); 398 F.print(OS, &AAW); 399 } 400 401 PreservedAnalyses StackLifetimePrinterPass::run(Function &F, 402 FunctionAnalysisManager &AM) { 403 SmallVector<const AllocaInst *, 8> Allocas; 404 for (auto &I : instructions(F)) 405 if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) 406 Allocas.push_back(AI); 407 StackLifetime SL(F, Allocas, Type); 408 SL.run(); 409 SL.print(OS); 410 return PreservedAnalyses::all(); 411 } 412 413 void StackLifetimePrinterPass::printPipeline( 414 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { 415 static_cast<PassInfoMixin<StackLifetimePrinterPass> *>(this)->printPipeline( 416 OS, MapClassName2PassName); 417 OS << '<'; 418 switch (Type) { 419 case StackLifetime::LivenessType::May: 420 OS << "may"; 421 break; 422 case StackLifetime::LivenessType::Must: 423 OS << "must"; 424 break; 425 } 426 OS << '>'; 427 } 428