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