SpillUtils.cpp Source File (original) (raw)

19namespace llvm {

21namespace coro {

23namespace {

25typedef SmallPtrSet<BasicBlock *, 8> VisitedBlocksSet;

29static bool isCoroutineStructureIntrinsic(Instruction &I) {

30 return isa(&I) || isa(&I) ||

31 isa(&I);

32}

36static bool isSuspendReachableFrom(BasicBlock *From,

37 VisitedBlocksSet &VisitedOrFreeBBs) {

41 if (!VisitedOrFreeBBs.insert(From).second)

42 return false;

46 return true;

50 if (isSuspendReachableFrom(Succ, VisitedOrFreeBBs))

51 return true;

52 }

54 return false;

55}

59static bool isLocalAlloca(CoroAllocaAllocInst *AI) {

62 VisitedBlocksSet VisitedOrFreeBBs;

63 for (auto *User : AI->users()) {

64 if (auto FI = dyn_cast(User))

65 VisitedOrFreeBBs.insert(FI->getParent());

66 }

68 return !isSuspendReachableFrom(AI->getParent(), VisitedOrFreeBBs);

69}

74static Instruction *

75lowerNonLocalAlloca(CoroAllocaAllocInst *AI, const coro::Shape &Shape,

76 SmallVectorImpl<Instruction *> &DeadInsts) {

77 IRBuilder<> Builder(AI);

78 auto Alloc = Shape.emitAlloc(Builder, AI->getSize(), nullptr);

80 for (User *U : AI->users()) {

81 if (isa(U)) {

82 U->replaceAllUsesWith(Alloc);

83 } else {

84 auto FI = cast(U);

85 Builder.SetInsertPoint(FI);

86 Shape.emitDealloc(Builder, Alloc, nullptr);

87 }

88 DeadInsts.push_back(cast(U));

89 }

92 DeadInsts.push_back(AI);

95 return cast(Alloc);

96}

100

101

102

103

104

105

106

107static Instruction *splitBeforeCatchSwitch(CatchSwitchInst *CatchSwitch) {

108 BasicBlock *CurrentBlock = CatchSwitch->getParent();

109 BasicBlock *NewBlock = CurrentBlock->splitBasicBlock(CatchSwitch);

110 CurrentBlock->getTerminator()->eraseFromParent();

111

112 auto *CleanupPad =

114 auto *CleanupRet =

116 return CleanupRet;

117}

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150namespace {

151struct AllocaUseVisitor : PtrUseVisitor {

152 using Base = PtrUseVisitor;

153 AllocaUseVisitor(const DataLayout &DL, const DominatorTree &DT,

154 const coro::Shape &CoroShape,

155 const SuspendCrossingInfo &Checker,

156 bool ShouldUseLifetimeStartInfo)

157 : PtrUseVisitor(DL), DT(DT), CoroShape(CoroShape), Checker(Checker),

158 ShouldUseLifetimeStartInfo(ShouldUseLifetimeStartInfo) {

159 for (AnyCoroSuspendInst *SuspendInst : CoroShape.CoroSuspends)

160 CoroSuspendBBs.insert(SuspendInst->getParent());

161 }

162

163 void visit(Instruction &I) {

165 Base::visit(I);

166

167

168 if (PI.isEscaped() &&

169 !DT.dominates(CoroShape.CoroBegin, PI.getEscapingInst())) {

170 MayWriteBeforeCoroBegin = true;

171 }

172 }

173

174

175 void visit(Instruction *I) { return visit(*I); }

176

177 void visitPHINode(PHINode &I) {

178 enqueueUsers(I);

179 handleAlias(I);

180 }

181

182 void visitSelectInst(SelectInst &I) {

183 enqueueUsers(I);

184 handleAlias(I);

185 }

186

187 void visitStoreInst(StoreInst &SI) {

188

189

190 handleMayWrite(SI);

191

192 if (SI.getValueOperand() != U->get())

193 return;

194

195

196

197

198

199

200

201

202

203

204

205 auto IsSimpleStoreThenLoad = [&]() {

206 auto *AI = dyn_cast(SI.getPointerOperand());

207

208

209

210 if (!AI)

211 return false;

212

213 SmallVector<Instruction *, 4> StoreAliases = {AI};

214 while (!StoreAliases.empty()) {

215 Instruction *I = StoreAliases.pop_back_val();

216 for (User *U : I->users()) {

217

218

219 if (auto *LI = dyn_cast(U)) {

220 enqueueUsers(*LI);

221 handleAlias(*LI);

222 continue;

223 }

224

225

226 if (auto *S = dyn_cast(U))

227 if (S->getPointerOperand() == I)

228 continue;

229 if (auto *II = dyn_cast(U))

230 if (II->isLifetimeStartOrEnd())

231 continue;

232

233

234 if (auto *BI = dyn_cast(U)) {

235 StoreAliases.push_back(BI);

236 continue;

237 }

238 return false;

239 }

240 }

241

242 return true;

243 };

244

245 if (!IsSimpleStoreThenLoad())

246 PI.setEscaped(&SI);

247 }

248

249

250 void visitMemIntrinsic(MemIntrinsic &MI) { handleMayWrite(MI); }

251

252 void visitBitCastInst(BitCastInst &BC) {

253 Base::visitBitCastInst(BC);

254 handleAlias(BC);

255 }

256

257 void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC) {

258 Base::visitAddrSpaceCastInst(ASC);

259 handleAlias(ASC);

260 }

261

262 void visitGetElementPtrInst(GetElementPtrInst &GEPI) {

263

264 Base::visitGetElementPtrInst(GEPI);

265 handleAlias(GEPI);

266 }

267

268 void visitIntrinsicInst(IntrinsicInst &II) {

269

270

271

272 if (!IsOffsetKnown || Offset .isZero())

273 return Base::visitIntrinsicInst(II);

274 switch (II.getIntrinsicID()) {

275 default:

276 return Base::visitIntrinsicInst(II);

277 case Intrinsic::lifetime_start:

278 LifetimeStarts.insert(&II);

279 LifetimeStartBBs.push_back(II.getParent());

280 break;

281 case Intrinsic::lifetime_end:

282 LifetimeEndBBs.insert(II.getParent());

283 break;

284 }

285 }

286

287 void visitCallBase(CallBase &CB) {

288 for (unsigned Op = 0, OpCount = CB.arg_size(); Op < OpCount; ++Op)

289 if (U->get() == CB.getArgOperand(Op) && !CB.doesNotCapture(Op))

290 PI.setEscaped(&CB);

291 handleMayWrite(CB);

292 }

293

294 bool getShouldLiveOnFrame() const {

295 if (!ShouldLiveOnFrame)

296 ShouldLiveOnFrame = computeShouldLiveOnFrame();

297 return *ShouldLiveOnFrame;

298 }

299

300 bool getMayWriteBeforeCoroBegin() const { return MayWriteBeforeCoroBegin; }

301

302 DenseMap<Instruction *, std::optional> getAliasesCopy() const {

303 assert(getShouldLiveOnFrame() && "This method should only be called if the "

304 "alloca needs to live on the frame.");

305 for (const auto &P : AliasOffetMap)

306 if (.second)

308 "created before CoroBegin.");

309 return AliasOffetMap;

310 }

311

312private:

313 const DominatorTree &DT;

314 const coro::Shape &CoroShape;

315 const SuspendCrossingInfo &Checker;

316

317

318

319 DenseMap<Instruction *, std::optional> AliasOffetMap{};

320 SmallPtrSet<Instruction *, 4> Users{};

321 SmallPtrSet<IntrinsicInst *, 2> LifetimeStarts{};

322 SmallVector<BasicBlock *> LifetimeStartBBs{};

323 SmallPtrSet<BasicBlock *, 2> LifetimeEndBBs{};

324 SmallPtrSet<const BasicBlock *, 2> CoroSuspendBBs{};

325 bool MayWriteBeforeCoroBegin{false};

326 bool ShouldUseLifetimeStartInfo{true};

327

328 mutable std::optional ShouldLiveOnFrame{};

329

330 bool computeShouldLiveOnFrame() const {

331

332

333

334

335 if (ShouldUseLifetimeStartInfo && !LifetimeStarts.empty()) {

336

337

338 if (LifetimeEndBBs.empty())

339 return true;

340

341

342

343

346 &LifetimeEndBBs, &DT))

347 return true;

348

349

350

351

352

353 if (PI.isEscaped()) {

354 for (auto *A : LifetimeStarts) {

355 for (auto *B : LifetimeStarts) {

356 if (Checker.hasPathOrLoopCrossingSuspendPoint(A->getParent(),

357 B->getParent()))

358 return true;

359 }

360 }

361 }

362 return false;

363 }

364

365

366

367

368

369

370

371

372

373

374 if (PI.isEscaped())

375 return true;

376

377 for (auto *U1 : Users)

378 for (auto *U2 : Users)

379 if (Checker.isDefinitionAcrossSuspend(*U1, U2))

380 return true;

381

382 return false;

383 }

384

385 void handleMayWrite(const Instruction &I) {

386 if (!DT.dominates(CoroShape.CoroBegin, &I))

387 MayWriteBeforeCoroBegin = true;

388 }

389

390 bool usedAfterCoroBegin(Instruction &I) {

391 for (auto &U : I.uses())

392 if (DT.dominates(CoroShape.CoroBegin, U))

393 return true;

394 return false;

395 }

396

397 void handleAlias(Instruction &I) {

398

399

400

401 if (DT.dominates(CoroShape.CoroBegin, &I) || !usedAfterCoroBegin(I))

402 return;

403

404 if (!IsOffsetKnown) {

405 AliasOffetMap[&I].reset();

406 } else {

407 auto [Itr, Inserted] = AliasOffetMap.try_emplace(&I, Offset);

408 if (!Inserted && Itr->second && *Itr->second != Offset) {

409

410

411 Itr->second.reset();

412 }

413 }

414 }

415};

416}

417

418static void collectFrameAlloca(AllocaInst *AI, const coro::Shape &Shape,

419 const SuspendCrossingInfo &Checker,

420 SmallVectorImpl &Allocas,

421 const DominatorTree &DT) {

422 if (Shape.CoroSuspends.empty())

423 return;

424

425

426

427 if (AI == Shape.SwitchLowering.PromiseAlloca)

428 return;

429

430

431

432 if (AI->hasMetadata(LLVMContext::MD_coro_outside_frame))

433 return;

434

435

436

437

438 bool ShouldUseLifetimeStartInfo =

441 AllocaUseVisitor Visitor{AI->getDataLayout(), DT, Shape, Checker,

442 ShouldUseLifetimeStartInfo};

443 Visitor.visitPtr(*AI);

444 if (!Visitor.getShouldLiveOnFrame())

445 return;

446 Allocas.emplace_back(AI, Visitor.getAliasesCopy(),

447 Visitor.getMayWriteBeforeCoroBegin());

448}

449

450}

451

454

456 for (User *U : A.users())

457 if (Checker.isDefinitionAcrossSuspend(A, U))

458 Spills[&A].push_back(cast(U));

459}

460

467

469

470

471 if (isCoroutineStructureIntrinsic(I) || &I == Shape.CoroBegin)

472 continue;

473

474

475 if (auto AI = dyn_cast(&I)) {

476

477 if (isLocalAlloca(AI)) {

479 continue;

480 }

481

482

483

484

485

486

487 auto Alloc = lowerNonLocalAlloca(AI, Shape, DeadInstructions);

488

490 if (Checker.isDefinitionAcrossSuspend(*Alloc, U))

491 Spills[Alloc].push_back(cast(U));

492 }

493 continue;

494 }

495

496

497 if (isa(I))

498 continue;

499

500 if (auto *AI = dyn_cast(&I)) {

501 collectFrameAlloca(AI, Shape, Checker, Allocas, DT);

502 continue;

503 }

504

505 for (User *U : I.users())

506 if (Checker.isDefinitionAcrossSuspend(I, U)) {

507

508 if (I.getType()->isTokenTy())

510 "token definition is separated from the use by a suspend point");

511 Spills[&I].push_back(cast(U));

512 }

513 }

514}

515

518

519

520

521

522 for (auto &Iter : Spills) {

523 auto *V = Iter.first;

528 if (Checker.isDefinitionAcrossSuspend(*V, DVI))

529 Spills[V].push_back(DVI);

530

532 if (Checker.isDefinitionAcrossSuspend(*V, DVR->Marker->MarkedInstr))

533 Spills[V].push_back(DVR->Marker->MarkedInstr);

534 }

535}

536

537

538

545

546

547 auto collectUsers = [&](Value *Def) {

548 for (User *U : Def->users()) {

549 auto Inst = cast(U);

550 if (Inst->getParent() != CoroBegin->getParent() ||

552 continue;

553 if (ToMove.insert(Inst))

555 }

556 };

557 std::for_each(Spills.begin(), Spills.end(),

558 [&](auto &I) { collectUsers(I.first); });

559 std::for_each(Allocas.begin(), Allocas.end(),

560 [&](auto &I) { collectUsers(I.Alloca); });

561

562

563 while (!Worklist.empty()) {

565 for (User *U : Def->users()) {

566 auto Inst = cast(U);

567 if (Dom.dominates(CoroBegin, Inst))

568 continue;

569 if (ToMove.insert(Inst))

571 }

572 }

573

574

577

579 });

580

584}

585

589 if (auto *Arg = dyn_cast(Def)) {

590

591

593

594

595

596 Arg->getParent()->removeParamAttr(Arg->getArgNo(), Attribute::NoCapture);

597 } else if (auto *CSI = dyn_cast(Def)) {

598

599

600 InsertPt = CSI->getParent()->getSingleSuccessor()->getFirstNonPHIIt();

601 } else {

602 auto *I = cast(Def);

604

605

607 } else if (auto *II = dyn_cast(I)) {

608

609

610 auto *NewBB = SplitEdge(II->getParent(), II->getNormalDest());

611 InsertPt = NewBB->getTerminator()->getIterator();

612 } else if (isa(I)) {

613

615 if (auto *CSI = dyn_cast(DefBlock->getTerminator()))

616 InsertPt = splitBeforeCatchSwitch(CSI)->getIterator();

617 else

619 } else {

620 assert(->isTerminator() && "unexpected terminator");

621

622

623 InsertPt = I->getNextNode()->getIterator();

624 }

625 }

626

627 return InsertPt;

628}

629

630}

631

632}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Expand Atomic instructions

BlockVerifier::State From

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

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

iv Induction Variable Users

uint64_t IntrinsicInst * II

StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)

This file provides a collection of visitors which walk the (instruction) uses of a pointer.

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

void visit(MachineFunction &MF, MachineBasicBlock &Start, std::function< void(MachineBasicBlock *)> op)

This class represents an incoming formal argument to a Function.

LLVM Basic Block Representation.

const_iterator getFirstInsertionPt() const

Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...

InstListType::iterator iterator

Instruction iterators...

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

static CleanupPadInst * Create(Value *ParentPad, ArrayRef< Value * > Args={}, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, InsertPosition InsertBefore=nullptr)

This class represents the llvm.coro.begin or llvm.coro.begin.custom.abi instructions.

This represents the llvm.dbg.value instruction.

Record of a variable value-assignment, aka a non instruction representation of the dbg....

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

void moveBefore(Instruction *MovePos)

Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...

iterator end()

Get an iterator to the end of the SetVector.

iterator begin()

Get an iterator to the beginning of the SetVector.

bool insert(const value_type &X)

Insert a new element into the SetVector.

A SetVector that performs no allocations if smaller than a certain size.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void push_back(const T &Elt)

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

LLVM Value Representation.

const ParentTy * getParent() const

NodeTy * getNextNode()

Get the next node, or nullptr for the list tail.

@ BasicBlock

Various leaf nodes.

@ Async

The "async continuation" lowering, where each suspend point creates a single continuation function.

@ RetconOnce

The "unique returned-continuation" lowering, where each suspend point creates a single continuation f...

@ Retcon

The "returned-continuation" lowering, where each suspend point creates a single continuation function...

BasicBlock::iterator getSpillInsertionPt(const coro::Shape &, Value *Def, const DominatorTree &DT)

bool isSuspendBlock(BasicBlock *BB)

void sinkSpillUsesAfterCoroBegin(const DominatorTree &DT, CoroBeginInst *CoroBegin, coro::SpillInfo &Spills, SmallVectorImpl< coro::AllocaInfo > &Allocas)

Async and Retcon{Once} conventions assume that all spill uses can be sunk after the coro....

void collectSpillsFromArgs(SpillInfo &Spills, Function &F, const SuspendCrossingInfo &Checker)

void collectSpillsFromDbgInfo(SpillInfo &Spills, Function &F, const SuspendCrossingInfo &Checker)

void collectSpillsAndAllocasFromInsts(SpillInfo &Spills, SmallVector< AllocaInfo, 8 > &Allocas, SmallVector< Instruction *, 4 > &DeadInstructions, SmallVector< CoroAllocaAllocInst *, 4 > &LocalAllocas, Function &F, const SuspendCrossingInfo &Checker, const DominatorTree &DT, const coro::Shape &Shape)

This is an optimization pass for GlobalISel generic memory operations.

auto successors(const MachineBasicBlock *BB)

void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)

Finds the llvm.dbg.value intrinsics describing a value.

void sort(IteratorTy Start, IteratorTy End)

void report_fatal_error(Error Err, bool gen_crash_diag=true)

Report a serious error, calling any installed error handler.

bool isManyPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock * > &Worklist, const SmallPtrSetImpl< const BasicBlock * > &StopSet, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)

Determine whether there is a potentially a path from at least one block in 'Worklist' to at least one...

BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")

Split the edge connecting the specified blocks, and return the newly created basic block between From...

A MapVector that performs no allocations if smaller than a certain size.

CoroBeginInst * CoroBegin

BasicBlock::iterator getInsertPtAfterFramePtr() const