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 void StackLifetime::collectMarkers() { 68 InterestingAllocas.resize(NumAllocas); 69 DenseMap<const BasicBlock *, SmallDenseMap<const IntrinsicInst *, Marker>> 70 BBMarkerSet; 71 72 // Compute the set of start/end markers per basic block. 73 for (const BasicBlock *BB : depth_first(&F)) { 74 for (const Instruction &I : *BB) { 75 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I); 76 if (!II || !II->isLifetimeStartOrEnd()) 77 continue; 78 const AllocaInst *AI = llvm::findAllocaForValue(II->getArgOperand(1)); 79 if (!AI) { 80 HasUnknownLifetimeStartOrEnd = true; 81 continue; 82 } 83 bool IsStart = II->getIntrinsicID() == Intrinsic::lifetime_start; 84 unsigned AllocaNo = AllocaNumbering[AI]; 85 if (IsStart) 86 InterestingAllocas.set(AllocaNo); 87 BBMarkerSet[BB][II] = {AllocaNo, IsStart}; 88 } 89 } 90 91 // Compute instruction numbering. Only the following instructions are 92 // considered: 93 // * Basic block entries 94 // * Lifetime markers 95 // For each basic block, compute 96 // * the list of markers in the instruction order 97 // * the sets of allocas whose lifetime starts or ends in this BB 98 LLVM_DEBUG(dbgs() << "Instructions:\n"); 99 for (const BasicBlock *BB : depth_first(&F)) { 100 LLVM_DEBUG(dbgs() << " " << Instructions.size() << ": BB " << BB->getName() 101 << "\n"); 102 auto BBStart = Instructions.size(); 103 Instructions.push_back(nullptr); 104 105 BlockLifetimeInfo &BlockInfo = 106 BlockLiveness.try_emplace(BB, NumAllocas).first->getSecond(); 107 108 auto &BlockMarkerSet = BBMarkerSet[BB]; 109 if (BlockMarkerSet.empty()) { 110 BlockInstRange[BB] = std::make_pair(BBStart, Instructions.size()); 111 continue; 112 } 113 114 auto ProcessMarker = [&](const IntrinsicInst *I, const Marker &M) { 115 LLVM_DEBUG(dbgs() << " " << Instructions.size() << ": " 116 << (M.IsStart ? "start " : "end ") << M.AllocaNo 117 << ", " << *I << "\n"); 118 119 BBMarkers[BB].push_back({Instructions.size(), M}); 120 Instructions.push_back(I); 121 122 if (M.IsStart) { 123 BlockInfo.End.reset(M.AllocaNo); 124 BlockInfo.Begin.set(M.AllocaNo); 125 } else { 126 BlockInfo.Begin.reset(M.AllocaNo); 127 BlockInfo.End.set(M.AllocaNo); 128 } 129 }; 130 131 if (BlockMarkerSet.size() == 1) { 132 ProcessMarker(BlockMarkerSet.begin()->getFirst(), 133 BlockMarkerSet.begin()->getSecond()); 134 } else { 135 // Scan the BB to determine the marker order. 136 for (const Instruction &I : *BB) { 137 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I); 138 if (!II) 139 continue; 140 auto It = BlockMarkerSet.find(II); 141 if (It == BlockMarkerSet.end()) 142 continue; 143 ProcessMarker(II, It->getSecond()); 144 } 145 } 146 147 BlockInstRange[BB] = std::make_pair(BBStart, Instructions.size()); 148 } 149 } 150 151 void StackLifetime::calculateLocalLiveness() { 152 bool Changed = true; 153 while (Changed) { 154 Changed = false; 155 156 for (const BasicBlock *BB : depth_first(&F)) { 157 BlockLifetimeInfo &BlockInfo = BlockLiveness.find(BB)->getSecond(); 158 159 // Compute LiveIn by unioning together the LiveOut sets of all preds. 160 BitVector LocalLiveIn; 161 for (auto *PredBB : predecessors(BB)) { 162 LivenessMap::const_iterator I = BlockLiveness.find(PredBB); 163 // If a predecessor is unreachable, ignore it. 164 if (I == BlockLiveness.end()) 165 continue; 166 switch (Type) { 167 case LivenessType::May: 168 LocalLiveIn |= I->second.LiveOut; 169 break; 170 case LivenessType::Must: 171 if (LocalLiveIn.empty()) 172 LocalLiveIn = I->second.LiveOut; 173 else 174 LocalLiveIn &= I->second.LiveOut; 175 break; 176 } 177 } 178 179 // Compute LiveOut by subtracting out lifetimes that end in this 180 // block, then adding in lifetimes that begin in this block. If 181 // we have both BEGIN and END markers in the same basic block 182 // then we know that the BEGIN marker comes after the END, 183 // because we already handle the case where the BEGIN comes 184 // before the END when collecting the markers (and building the 185 // BEGIN/END vectors). 186 BitVector LocalLiveOut = LocalLiveIn; 187 LocalLiveOut.reset(BlockInfo.End); 188 LocalLiveOut |= BlockInfo.Begin; 189 190 // Update block LiveIn set, noting whether it has changed. 191 if (LocalLiveIn.test(BlockInfo.LiveIn)) { 192 BlockInfo.LiveIn |= LocalLiveIn; 193 } 194 195 // Update block LiveOut set, noting whether it has changed. 196 if (LocalLiveOut.test(BlockInfo.LiveOut)) { 197 Changed = true; 198 BlockInfo.LiveOut |= LocalLiveOut; 199 } 200 } 201 } // while changed. 202 } 203 204 void StackLifetime::calculateLiveIntervals() { 205 for (auto IT : BlockLiveness) { 206 const BasicBlock *BB = IT.getFirst(); 207 BlockLifetimeInfo &BlockInfo = IT.getSecond(); 208 unsigned BBStart, BBEnd; 209 std::tie(BBStart, BBEnd) = BlockInstRange[BB]; 210 211 BitVector Started, Ended; 212 Started.resize(NumAllocas); 213 Ended.resize(NumAllocas); 214 SmallVector<unsigned, 8> Start; 215 Start.resize(NumAllocas); 216 217 // LiveIn ranges start at the first instruction. 218 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) { 219 if (BlockInfo.LiveIn.test(AllocaNo)) { 220 Started.set(AllocaNo); 221 Start[AllocaNo] = BBStart; 222 } 223 } 224 225 for (auto &It : BBMarkers[BB]) { 226 unsigned InstNo = It.first; 227 bool IsStart = It.second.IsStart; 228 unsigned AllocaNo = It.second.AllocaNo; 229 230 if (IsStart) { 231 assert(!Started.test(AllocaNo) || Start[AllocaNo] == BBStart); 232 if (!Started.test(AllocaNo)) { 233 Started.set(AllocaNo); 234 Ended.reset(AllocaNo); 235 Start[AllocaNo] = InstNo; 236 } 237 } else { 238 assert(!Ended.test(AllocaNo)); 239 if (Started.test(AllocaNo)) { 240 LiveRanges[AllocaNo].addRange(Start[AllocaNo], InstNo); 241 Started.reset(AllocaNo); 242 } 243 Ended.set(AllocaNo); 244 } 245 } 246 247 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) 248 if (Started.test(AllocaNo)) 249 LiveRanges[AllocaNo].addRange(Start[AllocaNo], BBEnd); 250 } 251 } 252 253 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 254 LLVM_DUMP_METHOD void StackLifetime::dumpAllocas() const { 255 dbgs() << "Allocas:\n"; 256 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) 257 dbgs() << " " << AllocaNo << ": " << *Allocas[AllocaNo] << "\n"; 258 } 259 260 LLVM_DUMP_METHOD void StackLifetime::dumpBlockLiveness() const { 261 dbgs() << "Block liveness:\n"; 262 for (auto IT : BlockLiveness) { 263 const BasicBlock *BB = IT.getFirst(); 264 const BlockLifetimeInfo &BlockInfo = BlockLiveness.find(BB)->getSecond(); 265 auto BlockRange = BlockInstRange.find(BB)->getSecond(); 266 dbgs() << " BB [" << BlockRange.first << ", " << BlockRange.second 267 << "): begin " << BlockInfo.Begin << ", end " << BlockInfo.End 268 << ", livein " << BlockInfo.LiveIn << ", liveout " 269 << BlockInfo.LiveOut << "\n"; 270 } 271 } 272 273 LLVM_DUMP_METHOD void StackLifetime::dumpLiveRanges() const { 274 dbgs() << "Alloca liveness:\n"; 275 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo) 276 dbgs() << " " << AllocaNo << ": " << LiveRanges[AllocaNo] << "\n"; 277 } 278 #endif 279 280 StackLifetime::StackLifetime(const Function &F, 281 ArrayRef<const AllocaInst *> Allocas, 282 LivenessType Type) 283 : F(F), Type(Type), Allocas(Allocas), NumAllocas(Allocas.size()) { 284 LLVM_DEBUG(dumpAllocas()); 285 286 for (unsigned I = 0; I < NumAllocas; ++I) 287 AllocaNumbering[Allocas[I]] = I; 288 289 collectMarkers(); 290 } 291 292 void StackLifetime::run() { 293 if (HasUnknownLifetimeStartOrEnd) { 294 // There is marker which we can't assign to a specific alloca, so we 295 // fallback to the most conservative results for the type. 296 switch (Type) { 297 case LivenessType::May: 298 LiveRanges.resize(NumAllocas, getFullLiveRange()); 299 break; 300 case LivenessType::Must: 301 LiveRanges.resize(NumAllocas, LiveRange(Instructions.size())); 302 break; 303 } 304 return; 305 } 306 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