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 BlockInfo.LiveIn |= LocalLiveIn; 207 } 208 209 // Update block LiveOut set, noting whether it has changed. 210 if (LocalLiveOut.test(BlockInfo.LiveOut)) { 211 Changed = true; 212 BlockInfo.LiveOut |= LocalLiveOut; 213 } 214 } 215 } // while changed. 216 } 217 218 void StackLifetime::calculateLiveIntervals() { 219 for (auto IT : BlockLiveness) { 220 const BasicBlock *BB = IT.getFirst(); 221 BlockLifetimeInfo &BlockInfo = IT.getSecond(); 222 unsigned BBStart, BBEnd; 223 std::tie(BBStart, BBEnd) = BlockInstRange[BB]; 224 225 BitVector Started, Ended; 226 Started.resize(NumAllocas); 227 Ended.resize(NumAllocas); 228 SmallVector<unsigned, 8> Start; 229 Start.resize(NumAllocas); 230 231 // LiveIn ranges start at the first instruction. 232 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) { 233 if (BlockInfo.LiveIn.test(AllocaNo)) { 234 Started.set(AllocaNo); 235 Start[AllocaNo] = BBStart; 236 } 237 } 238 239 for (auto &It : BBMarkers[BB]) { 240 unsigned InstNo = It.first; 241 bool IsStart = It.second.IsStart; 242 unsigned AllocaNo = It.second.AllocaNo; 243 244 if (IsStart) { 245 assert(!Started.test(AllocaNo) || Start[AllocaNo] == BBStart); 246 if (!Started.test(AllocaNo)) { 247 Started.set(AllocaNo); 248 Ended.reset(AllocaNo); 249 Start[AllocaNo] = InstNo; 250 } 251 } else { 252 assert(!Ended.test(AllocaNo)); 253 if (Started.test(AllocaNo)) { 254 LiveRanges[AllocaNo].addRange(Start[AllocaNo], InstNo); 255 Started.reset(AllocaNo); 256 } 257 Ended.set(AllocaNo); 258 } 259 } 260 261 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) 262 if (Started.test(AllocaNo)) 263 LiveRanges[AllocaNo].addRange(Start[AllocaNo], BBEnd); 264 } 265 } 266 267 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 268 LLVM_DUMP_METHOD void StackLifetime::dumpAllocas() const { 269 dbgs() << "Allocas:\n"; 270 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) 271 dbgs() << " " << AllocaNo << ": " << *Allocas[AllocaNo] << "\n"; 272 } 273 274 LLVM_DUMP_METHOD void StackLifetime::dumpBlockLiveness() const { 275 dbgs() << "Block liveness:\n"; 276 for (auto IT : BlockLiveness) { 277 const BasicBlock *BB = IT.getFirst(); 278 const BlockLifetimeInfo &BlockInfo = BlockLiveness.find(BB)->getSecond(); 279 auto BlockRange = BlockInstRange.find(BB)->getSecond(); 280 dbgs() << " BB [" << BlockRange.first << ", " << BlockRange.second 281 << "): begin " << BlockInfo.Begin << ", end " << BlockInfo.End 282 << ", livein " << BlockInfo.LiveIn << ", liveout " 283 << BlockInfo.LiveOut << "\n"; 284 } 285 } 286 287 LLVM_DUMP_METHOD void StackLifetime::dumpLiveRanges() const { 288 dbgs() << "Alloca liveness:\n"; 289 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) 290 dbgs() << " " << AllocaNo << ": " << LiveRanges[AllocaNo] << "\n"; 291 } 292 #endif 293 294 StackLifetime::StackLifetime(const Function &F, 295 ArrayRef<const AllocaInst *> Allocas, 296 LivenessType Type) 297 : F(F), Type(Type), Allocas(Allocas), NumAllocas(Allocas.size()) { 298 LLVM_DEBUG(dumpAllocas()); 299 300 for (unsigned I = 0; I < NumAllocas; ++I) 301 AllocaNumbering[Allocas[I]] = I; 302 303 collectMarkers(); 304 } 305 306 void StackLifetime::run() { 307 LiveRanges.resize(NumAllocas, LiveRange(Instructions.size())); 308 for (unsigned I = 0; I < NumAllocas; ++I) 309 if (!InterestingAllocas.test(I)) 310 LiveRanges[I] = getFullLiveRange(); 311 312 calculateLocalLiveness(); 313 LLVM_DEBUG(dumpBlockLiveness()); 314 calculateLiveIntervals(); 315 LLVM_DEBUG(dumpLiveRanges()); 316 } 317 318 class StackLifetime::LifetimeAnnotationWriter 319 : public AssemblyAnnotationWriter { 320 const StackLifetime &SL; 321 322 void printInstrAlive(unsigned InstrNo, formatted_raw_ostream &OS) { 323 SmallVector<StringRef, 16> Names; 324 for (const auto &KV : SL.AllocaNumbering) { 325 if (SL.LiveRanges[KV.getSecond()].test(InstrNo)) 326 Names.push_back(KV.getFirst()->getName()); 327 } 328 llvm::sort(Names); 329 OS << " ; Alive: <" << llvm::join(Names, " ") << ">\n"; 330 } 331 332 void emitBasicBlockStartAnnot(const BasicBlock *BB, 333 formatted_raw_ostream &OS) override { 334 auto ItBB = SL.BlockInstRange.find(BB); 335 if (ItBB == SL.BlockInstRange.end()) 336 return; // Unreachable. 337 printInstrAlive(ItBB->getSecond().first, OS); 338 } 339 340 void printInfoComment(const Value &V, formatted_raw_ostream &OS) override { 341 const Instruction *Instr = dyn_cast<Instruction>(&V); 342 if (!Instr || !SL.isReachable(Instr)) 343 return; 344 345 SmallVector<StringRef, 16> Names; 346 for (const auto &KV : SL.AllocaNumbering) { 347 if (SL.isAliveAfter(KV.getFirst(), Instr)) 348 Names.push_back(KV.getFirst()->getName()); 349 } 350 llvm::sort(Names); 351 OS << "\n ; Alive: <" << llvm::join(Names, " ") << ">\n"; 352 } 353 354 public: 355 LifetimeAnnotationWriter(const StackLifetime &SL) : SL(SL) {} 356 }; 357 358 void StackLifetime::print(raw_ostream &OS) { 359 LifetimeAnnotationWriter AAW(*this); 360 F.print(OS, &AAW); 361 } 362 363 PreservedAnalyses StackLifetimePrinterPass::run(Function &F, 364 FunctionAnalysisManager &AM) { 365 SmallVector<const AllocaInst *, 8> Allocas; 366 for (auto &I : instructions(F)) 367 if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) 368 Allocas.push_back(AI); 369 StackLifetime SL(F, Allocas, Type); 370 SL.run(); 371 SL.print(OS); 372 return PreservedAnalyses::all(); 373 } 374