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