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