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