SpillUtils.cpp Source File (original) (raw)

19using namespace llvm;

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

38 return false;

42 return true;

47 return true;

48 }

50 return false;

51}

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

62 }

65}

78 U->replaceAllUsesWith(Alloc);

79 } else {

81 Builder.SetInsertPoint(FI);

83 }

85 }

92}

100

101

102

107

108 auto *CleanupPad =

110 auto *CleanupRet =

112 return CleanupRet;

113}

114

115

116

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

146namespace {

147struct AllocaUseVisitor : PtrUseVisitor {

148 using Base = PtrUseVisitor;

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

150 const coro::Shape &CoroShape,

151 const SuspendCrossingInfo &Checker,

152 bool ShouldUseLifetimeStartInfo)

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

154 ShouldUseLifetimeStartInfo(ShouldUseLifetimeStartInfo) {

155 for (AnyCoroSuspendInst *SuspendInst : CoroShape.CoroSuspends)

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

157 }

158

159 void visit(Instruction &I) {

160 Users.insert(&I);

162

163

164 if (PI.isEscaped() &&

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

166 MayWriteBeforeCoroBegin = true;

167 }

168 }

169

170

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

172

173 void visitPHINode(PHINode &I) {

174 enqueueUsers(I);

175 handleAlias(I);

176 }

177

178 void visitSelectInst(SelectInst &I) {

179 enqueueUsers(I);

180 handleAlias(I);

181 }

182

183 void visitInsertElementInst(InsertElementInst &I) {

184 enqueueUsers(I);

185 handleAlias(I);

186 }

187

188 void visitInsertValueInst(InsertValueInst &I) {

189 enqueueUsers(I);

190 handleAlias(I);

191 }

192

193 void visitStoreInst(StoreInst &SI) {

194

195

196 handleMayWrite(SI);

197

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

199 return;

200

201

202

203

204

205

206

207

208

209

210

211 auto IsSimpleStoreThenLoad = [&]() {

213

214

215

216 if (!AI)

217 return false;

218

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

220 while (!StoreAliases.empty()) {

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

223

224

226 enqueueUsers(*LI);

227 handleAlias(*LI);

228 continue;

229 }

230

231

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

234 continue;

236 continue;

237

238

241 continue;

242 }

243 return false;

244 }

245 }

246

247 return true;

248 };

249

250 if (!IsSimpleStoreThenLoad())

251 PI.setEscaped(&SI);

252 }

253

254

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

256

257 void visitBitCastInst(BitCastInst &BC) {

259 handleAlias(BC);

260 }

261

262 void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC) {

264 handleAlias(ASC);

265 }

266

267 void visitGetElementPtrInst(GetElementPtrInst &GEPI) {

268

270 handleAlias(GEPI);

271 }

272

273 void visitIntrinsicInst(IntrinsicInst &II) {

274 switch (II.getIntrinsicID()) {

275 default:

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)

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{};

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

423 return;

424

425

426

428 return;

429

430

431

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

433 return;

434

435

436

437

438 bool ShouldUseLifetimeStartInfo =

442 ShouldUseLifetimeStartInfo};

443 Visitor.visitPtr(*AI);

444 if (!Visitor.getShouldLiveOnFrame())

445 return;

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

447 Visitor.getMayWriteBeforeCoroBegin());

448}

449

452

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

457}

458

465

467

468

470 continue;

471

472

474

477 continue;

478 }

479

480

481

482

483

484

486

490 }

491 continue;

492 }

493

494

496 continue;

497

500 continue;

501 }

502

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

505

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

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

510 }

511 }

512}

513

516

517

518

519

520 for (auto &Iter : Spills) {

521 auto *V = Iter.first;

524

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

528 }

529}

530

531

532

538

539

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

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

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

545 continue;

546 if (ToMove.insert(Inst))

548 }

549 };

550 for (auto &I : Spills)

551 collectUsers(I.first);

552 for (auto &I : Allocas)

553 collectUsers(I.Alloca);

554

555

556 while (!Worklist.empty()) {

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

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

561 continue;

562 if (ToMove.insert(Inst))

564 }

565 }

566

567

570

572 });

573

576 Inst->moveBefore(InsertPt->getIterator());

577}

578

584

585

587

588

589

590 Arg->getParent()->removeParamAttr(Arg->getArgNo(), Attribute::Captures);

592

593

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

595 } else {

598

599

602

603

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

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

607

611 else

613 } else {

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

615

616

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

618 }

619 }

620

621 return InsertPt;

622}

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

AMDGPU Prepare AGPR Alloc

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Expand Atomic instructions

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

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

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

uint64_t IntrinsicInst * II

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

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

static bool isSuspendReachableFrom(BasicBlock *From, VisitedBlocksSet &VisitedOrFreeBBs)

Does control flow starting at the given block ever reach a suspend instruction before reaching a bloc...

Definition SpillUtils.cpp:32

static Instruction * splitBeforeCatchSwitch(CatchSwitchInst *CatchSwitch)

Definition SpillUtils.cpp:103

static bool isLocalAlloca(CoroAllocaAllocInst *AI)

Is the given alloca "local", i.e.

Definition SpillUtils.cpp:55

static bool isNonSpilledIntrinsic(Instruction &I)

Definition SpillUtils.cpp:24

static Instruction * lowerNonLocalAlloca(CoroAllocaAllocInst *AI, const Shape &Shape, SmallVectorImpl< Instruction * > &DeadInsts)

Turn the given coro.alloca.alloc call into a dynamic allocation.

Definition SpillUtils.cpp:71

SmallPtrSet< BasicBlock *, 8 > VisitedBlocksSet

Definition SpillUtils.cpp:22

static void collectFrameAlloca(AllocaInst *AI, const coro::Shape &Shape, const SuspendCrossingInfo &Checker, SmallVectorImpl< AllocaInfo > &Allocas, const DominatorTree &DT)

Definition SpillUtils.cpp:418

an instruction to allocate memory on the stack

This class represents an incoming formal argument to a Function.

LLVM Basic Block Representation.

LLVM_ABI const_iterator getFirstInsertionPt() const

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

LLVM_ABI BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)

Split the basic block into two basic blocks at the specified instruction.

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

bool doesNotCapture(unsigned OpNo) const

Determine whether this data operand is not captured.

Value * getArgOperand(unsigned i) const

unsigned arg_size() const

Value * getParentPad() const

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 represents the llvm.coro.alloca.alloc instruction.

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

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.

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

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

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

void visit(Iterator Start, Iterator End)

bool hasMetadata() const

Return true if this instruction has any metadata attached to it.

LLVM_ABI void moveBefore(InstListType::iterator InsertPos)

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

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

LLVM_ABI const DataLayout & getDataLayout() const

Get the data layout of the module this instruction belongs to.

A base class for visitors over the uses of a pointer value.

void visitGetElementPtrInst(GetElementPtrInst &GEPI)

void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC)

void visitBitCastInst(BitCastInst &BC)

void visitIntrinsicInst(IntrinsicInst &II)

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.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

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

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

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

bool isDefinitionAcrossSuspend(BasicBlock *DefBB, User *U) const

LLVM Value Representation.

iterator_range< user_iterator > users()

const ParentTy * getParent() const

self_iterator getIterator()

NodeTy * getNextNode()

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

SmallMapVector< Value *, SmallVector< Instruction *, 2 >, 8 > SpillInfo

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

Definition SpillUtils.cpp:579

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

Definition SpillUtils.cpp:533

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

Definition SpillUtils.cpp:450

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

Definition SpillUtils.cpp:514

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)

Definition SpillUtils.cpp:459

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI void findDbgValues(Value *V, SmallVectorImpl< DbgVariableRecord * > &DbgVariableRecords)

Finds the dbg.values describing a value.

decltype(auto) dyn_cast(const From &Val)

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

auto successors(const MachineBasicBlock *BB)

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)

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

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

DWARFExpression::Operation Op

decltype(auto) cast(const From &Val)

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

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

AllocaInst * PromiseAlloca

SmallVector< AnyCoroSuspendInst *, 4 > CoroSuspends

LLVM_ABI Value * emitAlloc(IRBuilder<> &Builder, Value *Size, CallGraph *CG) const

Allocate memory according to the rules of the active lowering.

SwitchLoweringStorage SwitchLowering

CoroBeginInst * CoroBegin

BasicBlock::iterator getInsertPtAfterFramePtr() const

LLVM_ABI void emitDealloc(IRBuilder<> &Builder, Value *Ptr, CallGraph *CG) const

Deallocate memory according to the rules of the active lowering.