StackLifetime.cpp Source File (original) (raw)

15#include "llvm/Config/llvm-config.h"

27#include

28#include

30using namespace llvm;

32#define DEBUG_TYPE "stack-lifetime"

36 const auto IT = AllocaNumbering.find(AI);

37 assert(IT != AllocaNumbering.end());

38 return LiveRanges[IT->second];

39}

42 return BlockInstRange.contains(I->getParent());

43}

48 auto ItBB = BlockInstRange.find(BB);

49 assert(ItBB != BlockInstRange.end() && "Unreachable is not expected");

52 auto It = std::upper_bound(Instructions.begin() + ItBB->getSecond().first + 1,

53 Instructions.begin() + ItBB->getSecond().second, I,

55 return L->comesBefore(R);

56 });

57 --It;

58 unsigned InstNum = It - Instructions.begin();

60}

62void StackLifetime::collectMarkers() {

63 InterestingAllocas.resize(NumAllocas);

65 BBMarkerSet;

71 if ( || ->isLifetimeStartOrEnd())

72 continue;

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 }

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.AllocaNo

113 << ", " << *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

132 for (const Instruction &I : *BB) {

134 if ()

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() {

149

150

151

152

153

155

157

158 for (const BasicBlock *BB : depth_first(&F)) {

159 BlockLifetimeInfo &BlockInfo = BlockLiveness.find(BB)->getSecond();

160

161

162 BitVector BitsIn;

163 for (const auto *PredBB : predecessors(BB)) {

165

166 if (I == BlockLiveness.end())

167 continue;

168 BitsIn |= I->second.LiveOut;

169 }

170

171

173 BitsIn.resize(NumAllocas, true);

174

175

176 if (BitsIn.test(BlockInfo.LiveIn)) {

177 BlockInfo.LiveIn |= BitsIn;

178 }

179

180

181

182

183

184

185

186

187 switch (Type) {

189 BitsIn.reset(BlockInfo.End);

190

191 BitsIn |= BlockInfo.Begin;

192 break;

194 BitsIn.reset(BlockInfo.Begin);

195

196 BitsIn |= BlockInfo.End;

197 break;

198 }

199

200

201 if (BitsIn.test(BlockInfo.LiveOut)) {

203 BlockInfo.LiveOut |= BitsIn;

204 }

205 }

206 }

207

209

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) {

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

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)

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) {

275 const BlockLifetimeInfo &BlockInfo = BlockLiveness.find(BB)->getSecond();

276 auto BlockRange = BlockInstRange.find(BB)->getSecond();

277 dbgs() << " BB (" << BB->getName() << ") [" << BlockRange.first << ", " << BlockRange.second

278 << "): begin " << BlockInfo.Begin << ", end " << BlockInfo.End

279 << ", livein " << BlockInfo.LiveIn << ", liveout "

280 << BlockInfo.LiveOut << "\n";

281 }

282}

283

285 dbgs() << "Alloca liveness:\n";

286 for (unsigned AllocaNo = 0; AllocaNo < NumAllocas; ++AllocaNo)

287 dbgs() << " " << AllocaNo << ": " << LiveRanges[AllocaNo] << "\n";

288}

289#endif

290

294 : F(F), Type(Type), Allocas(Allocas), NumAllocas(Allocas.size()) {

296

297 for (unsigned I = 0; I < NumAllocas; ++I)

298 AllocaNumbering[Allocas[I]] = I;

299

300 collectMarkers();

301}

302

304 LiveRanges.resize(NumAllocas, LiveRange(Instructions.size()));

305 for (unsigned I = 0; I < NumAllocas; ++I)

306 if (!InterestingAllocas.test(I))

308

309 calculateLocalLiveness();

311 calculateLiveIntervals();

313}

314

318

321 for (const auto &KV : SL.AllocaNumbering) {

322 if (SL.LiveRanges[KV.getSecond()].test(InstrNo))

323 Names.push_back(KV.getFirst()->getName());

324 }

326 OS << " ; Alive: <" << llvm::join(Names, " ") << ">\n";

327 }

328

329 void emitBasicBlockStartAnnot(const BasicBlock *BB,

331 auto ItBB = SL.BlockInstRange.find(BB);

332 if (ItBB == SL.BlockInstRange.end())

333 return;

334 printInstrAlive(ItBB->getSecond().first, OS);

335 }

336

339 if (!Instr || !SL.isReachable(Instr))

340 return;

341

343 for (const auto &KV : SL.AllocaNumbering) {

344 if (SL.isAliveAfter(KV.getFirst(), Instr))

345 Names.push_back(KV.getFirst()->getName());

346 }

348 OS << "\n ; Alive: <" << llvm::join(Names, " ") << ">\n";

349 }

350

351public:

353};

354

357 F.print(OS, &AAW);

358}

359

371

375 OS, MapClassName2PassName);

376 OS << '<';

377 switch (Type) {

379 OS << "may";

380 break;

382 OS << "must";

383 break;

384 }

385 OS << '>';

386}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))

Expand Atomic instructions

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

uint64_t IntrinsicInst * II

SI Optimize VGPR LiveRange

This file defines the SmallVector class.

Definition StackLifetime.cpp:316

LifetimeAnnotationWriter(const StackLifetime &SL)

Definition StackLifetime.cpp:352

an instruction to allocate memory on the stack

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

LLVM Basic Block Representation.

bool test(unsigned Idx) const

void resize(unsigned N, bool t=false)

resize - Grow or shrink the bitvector.

bool empty() const

empty - Tests whether there are no bits in this bitvector.

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT, true > const_iterator

A wrapper class for inspecting calls to intrinsic functions.

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)

Definition StackLifetime.cpp:372

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition StackLifetime.cpp:360

This class represents a set of interesting instructions where an alloca is live.

bool test(unsigned Idx) const

Compute live ranges of allocas.

void run()

Definition StackLifetime.cpp:303

void print(raw_ostream &O)

Definition StackLifetime.cpp:355

StackLifetime(const Function &F, ArrayRef< const AllocaInst * > Allocas, LivenessType Type)

Definition StackLifetime.cpp:291

bool isReachable(const Instruction *I) const

Returns true if instruction is reachable from entry.

Definition StackLifetime.cpp:41

LiveRange getFullLiveRange() const

Returns a live range that represents an alloca that is live throughout the entire function.

const LiveRange & getLiveRange(const AllocaInst *AI) const

Returns a set of "interesting" instructions where the given alloca is live.

Definition StackLifetime.cpp:35

bool isAliveAfter(const AllocaInst *AI, const Instruction *I) const

Returns true if the alloca is alive after the instruction.

Definition StackLifetime.cpp:45

StringRef - Represent a constant reference to a string, i.e.

LLVM Value Representation.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

formatted_raw_ostream - A raw_ostream that wraps another one and keeps track of line and column posit...

An efficient, type-erasing, non-owning reference to a callable.

This class implements an extremely fast bulk output stream that can only output to a stream.

@ BasicBlock

Various leaf nodes.

This is an optimization pass for GlobalISel generic memory operations.

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

std::string join(IteratorT Begin, IteratorT End, StringRef Separator)

Joins the strings in the range [Begin, End), adding Separator between the elements.

auto predecessors(const MachineBasicBlock *BB)

iterator_range< df_iterator< T > > depth_first(const T &G)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

A CRTP mix-in to automatically provide informational APIs needed for passes.