CoroElide.cpp Source File (original) (raw)

20#include

22using namespace llvm;

24#define DEBUG_TYPE "coro-elide"

26 STATISTIC(NumOfCoroElided, "The # of coroutine get elided.");

28#ifndef NDEBUG

30 "coro-elide-info-output-file", cl::value_desc("filename"),

32#endif

34namespace {

36class FunctionElideInfo {

37public:

38 FunctionElideInfo(Function *F) : ContainingFunction(F) {

39 this->collectPostSplitCoroIds();

40 }

42 bool hasCoroIds() const { return !CoroIds.empty(); }

44 const SmallVectorImpl<CoroIdInst *> &getCoroIds() const { return CoroIds; }

46private:

50 SmallPtrSet<const SwitchInst *, 4> CoroSuspendSwitches;

52 void collectPostSplitCoroIds();

53 friend class CoroIdElider;

54};

56class CoroIdElider {

57public:

58 CoroIdElider(CoroIdInst *CoroId, FunctionElideInfo &FEI, AAResults &AA,

59 DominatorTree &DT, OptimizationRemarkEmitter &ORE);

60 void elideHeapAllocations(uint64_t FrameSize, Align FrameAlign);

61 bool lifetimeEligibleForElide() const;

62 bool attemptElide();

63 bool canCoroBeginEscape(const CoroBeginInst *,

64 const SmallPtrSetImpl<BasicBlock *> &) const;

66private:

67 CoroIdInst *CoroId;

68 FunctionElideInfo &FEI;

69 AAResults &AA;

70 DominatorTree &DT;

71 OptimizationRemarkEmitter &ORE;

76 DenseMap<CoroBeginInst *, SmallVector<CoroSubFnInst *, 4>> DestroyAddr;

77};

78}

91 if (Op->getType()->isPointerTy() && .isNoAlias(Op, Frame))

92 return true;

93 return false;

94}

100

101

102

108 Call ->isMustTailCall())

109 Call->setTailCall(false);

110}

111

112

113

114static std::optional<std::pair<uint64_t, Align>>

116

119 return std::nullopt;

121}

122

123

130

131#ifndef NDEBUG

134 "coro-elide-info-output-file shouldn't be empty");

135 std::error_code EC;

138 if (!EC)

139 return Result;

140 llvm::errs() << "Error opening coro-elide-info-output-file '"

142 return std::make_unique<raw_fd_ostream>(2, false);

143}

144#endif

145

146void FunctionElideInfo::collectPostSplitCoroIds() {

147 for (auto &I : instructions(this->ContainingFunction)) {

149 if (CII->getInfo().isPostSplit())

150

151 if (CII->getCoroutine() != CII->getFunction())

152 CoroIds.push_back(CII);

153

154

155

156

157

158

160 if (CSI->hasOneUse() && isa(CSI->use_begin()->getUser())) {

161 SwitchInst *SWI = cast(CSI->use_begin()->getUser());

163 CoroSuspendSwitches.insert(SWI);

164 }

165 }

166}

167

168CoroIdElider::CoroIdElider(CoroIdInst *CoroId, FunctionElideInfo &FEI,

169 AAResults &AA, DominatorTree &DT,

170 OptimizationRemarkEmitter &ORE)

171 : CoroId(CoroId), FEI(FEI), AA(AA), DT(DT), ORE(ORE) {

172

173 for (User *U : CoroId->users()) {

174 if (auto *CB = dyn_cast(U))

175 CoroBegins.push_back(CB);

176 else if (auto *CA = dyn_cast(U))

177 CoroAllocs.push_back(CA);

178 }

179

180

181

182

183

187 switch (II->getIndex()) {

189 ResumeAddr.push_back(II);

190 break;

192 DestroyAddr[CB].push_back(II);

193 break;

194 default:

196 }

197 }

198}

199

200

201

202void CoroIdElider::elideHeapAllocations(uint64_t FrameSize, Align FrameAlign) {

203 LLVMContext &C = FEI.ContainingFunction->getContext();

206

207

208

209

210

211

212

214 for (auto *CA : CoroAllocs) {

215 CA->replaceAllUsesWith(False);

216 CA->eraseFromParent();

217 }

218

219

220

221

222

223 const DataLayout &DL = FEI.ContainingFunction->getDataLayout();

224 auto FrameTy = ArrayType::get(Type::getInt8Ty(C), FrameSize);

225 auto *Frame = new AllocaInst(FrameTy, DL.getAllocaAddrSpace(), "", InsertPt);

226 Frame->setAlignment(FrameAlign);

227 auto *FrameVoidPtr =

228 new BitCastInst(Frame, PointerType::getUnqual(C), "vFrame", InsertPt);

229

230 for (auto *CB : CoroBegins) {

231 CB->replaceAllUsesWith(FrameVoidPtr);

232 CB->eraseFromParent();

233 }

234

235

236

238}

239

240bool CoroIdElider::canCoroBeginEscape(

241 const CoroBeginInst *CB, const SmallPtrSetImpl<BasicBlock *> &TIs) const {

242 const auto &It = DestroyAddr.find(CB);

243 assert(It != DestroyAddr.end());

244

245

246 unsigned Limit = 32 * (1 + It->second.size());

247

250

251 SmallPtrSet<const BasicBlock *, 32> Visited;

252

253

254 for (auto *DA : It->second)

255 Visited.insert(DA->getParent());

256

257 SmallPtrSet<const BasicBlock *, 32> EscapingBBs;

258 for (auto *U : CB->users()) {

259

261 continue;

262

263

264

265

266

267

268

269

270

271

272

273

275 }

276

277 bool PotentiallyEscaped = false;

278

279 do {

281 if (!Visited.insert(BB).second)

282 continue;

283

284

285

286

287 PotentiallyEscaped |= EscapingBBs.count(BB);

288

289 if (TIs.count(BB)) {

290 if (isa(BB->getTerminator()) || PotentiallyEscaped)

291 return true;

292

293

294

295

296

297

298 continue;

299 }

300

301

302 if (!--Limit)

303 return true;

304

305 auto TI = BB->getTerminator();

306

307

308

313 } else

315

316 } while (!Worklist.empty());

317

318

319

320 return false;

321}

322

323bool CoroIdElider::lifetimeEligibleForElide() const {

324

325

326 if (CoroAllocs.empty())

327 return false;

328

329

330

331

332

333

334

335

336 SmallPtrSet<BasicBlock *, 8> Terminators;

337

338

339

340 for (BasicBlock &B : *FEI.ContainingFunction) {

341 auto *TI = B.getTerminator();

342

344 continue;

345

347 }

348

349

350 for (const auto *CB : CoroBegins) {

351 auto It = DestroyAddr.find(CB);

352

353

354

355 if (It == DestroyAddr.end())

356 return false;

357

358 const auto &CorrespondingDestroyAddrs = It->second;

359

360

361

362 auto DominatesTerminator = [&](auto *TI) {

363 return llvm::any_of(CorrespondingDestroyAddrs, [&](auto *Destroy) {

364 return DT.dominates(Destroy, TI->getTerminator());

365 });

366 };

367

368 if (llvm::all_of(Terminators, DominatesTerminator))

369 continue;

370

371

372

373

374

375

376

377 if (canCoroBeginEscape(CB, Terminators))

378 return false;

379 }

380

381

382

383 return true;

384}

385

386bool CoroIdElider::attemptElide() {

387

388

390 assert(Resumers && "PostSplit coro.id Info argument must refer to an array"

391 "of coroutine subfunctions");

392 auto *ResumeAddrConstant =

394

396

397 bool EligibleForElide = lifetimeEligibleForElide();

398

402

403 for (auto &It : DestroyAddr)

405

407

408 auto CallerFunctionName = FEI.ContainingFunction->getName();

410

411 if (EligibleForElide && FrameSizeAndAlign) {

412 elideHeapAllocations(FrameSizeAndAlign->first, FrameSizeAndAlign->second);

414 NumOfCoroElided++;

415

416#ifndef NDEBUG

419 << FEI.ContainingFunction->getName() << "\n";

420#endif

421

422 ORE.emit([&]() {

423 return OptimizationRemark(DEBUG_TYPE, "CoroElide", CoroId)

424 << "'" << ore::NV("callee", CalleeCoroutineName)

425 << "' elided in '" << ore::NV("caller", CallerFunctionName)

426 << "' (frame_size="

427 << ore::NV("frame_size", FrameSizeAndAlign->first) << ", align="

428 << ore::NV("align", FrameSizeAndAlign->second.value()) << ")";

429 });

430 } else {

431 ORE.emit([&]() {

432 auto Remark = OptimizationRemarkMissed(DEBUG_TYPE, "CoroElide", CoroId)

433 << "'" << ore::NV("callee", CalleeCoroutineName)

434 << "' not elided in '"

435 << ore::NV("caller", CallerFunctionName);

436

437 if (FrameSizeAndAlign)

438 return Remark << "' (frame_size="

439 << ore::NV("frame_size", FrameSizeAndAlign->first)

440 << ", align="

441 << ore::NV("align", FrameSizeAndAlign->second.value())

442 << ")";

443 else

444 return Remark << "' (frame_size=unknown, align=unknown)";

445 });

446 }

447

448 return true;

449}

450

452 auto &M = *F.getParent();

455

456 FunctionElideInfo FEI{&F};

457

458 if (!FEI.hasCoroIds())

460

464

466 for (auto *CII : FEI.getCoroIds()) {

467 CoroIdElider CIE(CII, FEI, AA, DT, ORE);

468 Changed |= CIE.attemptElide();

469 }

470

472}

for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))

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

static bool replaceWithConstant(MachineIRBuilder &B, MachineInstr &MI, int64_t C)

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Expand Atomic instructions

static const Function * getParent(const Value *V)

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

static void replaceWithConstant(Constant *Value, SmallVectorImpl< CoroSubFnInst * > &Users)

Definition CoroElide.cpp:82

static Instruction * getFirstNonAllocaInTheEntryBlock(Function *F)

Definition CoroElide.cpp:124

static cl::opt< std::string > CoroElideInfoOutputFilename("coro-elide-info-output-file", cl::value_desc("filename"), cl::desc("File to record the coroutines got elided"), cl::Hidden)

static void removeTailCallAttribute(AllocaInst *Frame, AAResults &AA)

Definition CoroElide.cpp:103

static std::optional< std::pair< uint64_t, Align > > getFrameLayout(Function *Resume)

Definition CoroElide.cpp:115

static std::unique_ptr< raw_fd_ostream > getOrCreateLogFile()

Definition CoroElide.cpp:132

static bool operandReferences(CallInst *CI, AllocaInst *Frame, AAResults &AA)

Definition CoroElide.cpp:89

This file defines the DenseMap class.

iv Induction Variable Users

uint64_t IntrinsicInst * II

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

static Instruction * getFirstNonAllocaInTheEntryBlock(Function &F)

A manager for alias analyses.

an instruction to allocate memory on the stack

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

InstListType::iterator iterator

Instruction iterators...

This class represents a function call, abstracting a target machine's calling convention.

static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)

This is an important base class in LLVM.

LLVM_ABI Constant * getAggregateElement(unsigned Elt) const

For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...

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

Function * getCoroutine() const

This class represents the llvm.coro.subfn.addr instruction.

Analysis pass which computes a DominatorTree.

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.

const DataLayout & getDataLayout() const

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

uint64_t getParamDereferenceableBytes(unsigned ArgNo) const

Extract the number of dereferenceable bytes for a parameter.

MaybeAlign getParamAlign(unsigned ArgNo) const

LLVMContext & getContext() const

getContext - Return a reference to the LLVMContext associated with this function.

LLVM_ABI const Function * getFunction() const

Return the function this instruction belongs to.

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

static PreservedAnalyses none()

Convenience factory function for the empty preserved set.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

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

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

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

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

void push_back(const T &Elt)

unsigned getNumCases() const

Return the number of 'cases' in this switch instruction, excluding the default case.

iterator_range< value_op_iterator > operand_values()

LLVM Value Representation.

iterator_range< user_iterator > users()

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

const ParentTy * getParent() const

self_iterator getIterator()

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

Abstract Attribute helper functions.

@ C

The default llvm calling convention, compatible with C.

void replaceCoroFree(CoroIdInst *CoroId, bool Elide)

bool declaresIntrinsics(const Module &M, ArrayRef< Intrinsic::ID > List)

DiagnosticInfoOptimizationBase::Argument NV

@ OF_Append

The file should be opened in append mode.

This is an optimization pass for GlobalISel generic memory operations.

bool all_of(R &&range, UnaryPredicate P)

Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.

decltype(auto) dyn_cast(const From &Val)

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

bool any_of(R &&range, UnaryPredicate P)

Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.

LLVM_ABI bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI=nullptr, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr, SmallSetVector< Instruction *, 8 > *UnsimplifiedUsers=nullptr)

Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively.

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

LLVM_ABI raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)

RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)

DWARFExpression::Operation Op

decltype(auto) cast(const From &Val)

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

This struct is a compact representation of a valid (non-zero power of two) alignment.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition CoroElide.cpp:451

Align valueOrOne() const

For convenience, returns a valid alignment or 1 if undefined.