MustExecute.h Source File (original) (raw)

23#ifndef LLVM_ANALYSIS_MUSTEXECUTE_H

24#define LLVM_ANALYSIS_MUSTEXECUTE_H

33namespace llvm {

35namespace {

36template using GetterTy = std::function<T *(const Function &F)>;

37}

64protected:

68public:

100 const Loop *CurLoop) const = 0;

101

103

105};

106

107

108

109

110

112 bool MayThrow = false;

113

114 bool HeaderMayThrow = false;

115

116public:

118

120

122

125 const Loop *CurLoop) const override;

126};

127

128

129

130

131

132

134 bool MayThrow = false;

135

136

138

140

141public:

143

145

147

150 const Loop *CurLoop) const override;

151

152

153

155 const;

156

157

158

160 const;

161

162

163

164

166

167

168

169

171};

172

175

177

178

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

275

276

282

283

285

287

291

293 if (this != &Other) {

298 }

299 return *this;

300 }

301

303

304

305

307 CurInst = advance();

308 return *this;

309 }

310

316

317

318

319

321 return CurInst == Other.CurInst && Head == Other.Head && Tail == Other.Tail;

322 }

323

325 return !(*this == Other);

326 }

327

328

329

332

333

336 Visited.count({I, ExplorationDirection::BACKWARD});

337 }

338

339private:

340 using VisitedSetTy =

342

343

345

346

348

349

351

352

353

354

355

357

358

359

360 VisitedSetTy Visited;

361

362

364

365

366

367

369

370

371

372

374

376};

377

378

379

380

381

382

383

384

385

386

387

389

390

391

392

393

394

395

396

397

398

399

400

401

402

405 GetterTy LIGetter =

406 [](const Function &) { return nullptr; },

407 GetterTy DTGetter =

408 [](const Function &) { return nullptr; },

409 GetterTy PDTGetter =

410 [](const Function &) { return nullptr; })

414 DTGetter(DTGetter), PDTGetter(PDTGetter), EndIterator(*this, nullptr) {}

415

416

417

420

421

423 auto &It = InstructionIteratorMap[PP];

424 if (!It)

425 It.reset(new iterator(*this, PP));

426 return *It;

427 }

428

429

431 return *InstructionIteratorMap.find(PP)->second;

432 }

433

434

435

438

441

442

443

447

448

452

453

454

455

456

457

460 for (auto EIt = begin(PP), EEnd = end(PP); EIt != EEnd; ++EIt)

461 if (!Pred(*EIt))

462 return false;

463 return true;

464 }

465

466

467

468

469

470

471

473 auto EIt = begin(PP), EEnd = end(PP);

475 }

476

477

478

479

480

481

482

484 bool Found = EIt.count(I);

485 while (!Found && EIt != EEnd)

486 Found = (++EIt).getCurrentInst() == I;

487 return Found;

488 }

489

490

491

492

493

494

495

499

500

501

502

503

504

508

509

511

512

514

515

516

517

521

522

523private:

524

525

526

527 GetterTy LIGetter;

528 GetterTy DTGetter;

529 GetterTy PDTGetter;

530

531

532

534

535

537

538

540 InstructionIteratorMap;

541

542

544};

545

554

556 : public PassInfoMixin {

558

559public:

563};

564

565}

566

567#endif

This file defines the DenseMap class.

This file defines the DenseSet and SmallDenseSet classes.

This header defines various interfaces for pass management in LLVM.

LLVM Basic Block Representation.

Implements a dense probed hash-table based set.

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

This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...

Definition MustExecute.h:133

bool blockMayThrow(const BasicBlock *BB) const override

Returns true iff the block BB potentially may throw exception.

bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop) const

Returns true if we could not execute a memory-modifying instruction before we enter BB under assumpti...

void removeInstruction(const Instruction *Inst)

Inform safety info that we are planning to remove the instruction Inst from its block.

bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const override

Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...

bool anyBlockMayThrow() const override

Returns true iff any block of the loop for which this info is contains an instruction that may throw ...

void computeLoopSafetyInfo(const Loop *CurLoop) override

Computes safety information for a loop checks loop body & header for the possibility of may throw exc...

void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB)

Inform the safety info that we are planning to insert a new instruction Inst into the basic block BB.

This class allows to keep track on instructions with implicit control flow.

LLVM_ABI bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB, const DominatorTree *DT) const

Return true if we must reach the block BB under assumption that the loop CurLoop is entered.

LLVM_ABI void copyColors(BasicBlock *New, BasicBlock *Old)

Copy colors of block Old into the block New.

LLVM_ABI void computeBlockColors(const Loop *CurLoop)

Computes block colors.

LLVM_ABI const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const

Returns block colors map that is used to update funclet operand bundles.

virtual ~LoopSafetyInfo()=default

virtual void computeLoopSafetyInfo(const Loop *CurLoop)=0

Computes safety information for a loop checks loop body & header for the possibility of may throw exc...

virtual bool anyBlockMayThrow() const =0

Returns true iff any block of the loop for which this info is contains an instruction that may throw ...

virtual bool blockMayThrow(const BasicBlock *BB) const =0

Returns true iff the block BB potentially may throw exception.

virtual bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const =0

Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...

Represents a single loop in the control flow graph.

A Module instance is used to store all the information related to an LLVM module.

LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)

MustBeExecutedContextPrinterPass(raw_ostream &OS)

Definition MustExecute.h:560

static bool isRequired()

Definition MustExecute.h:562

static bool isRequired()

Definition MustExecute.h:552

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

MustExecutePrinterPass(raw_ostream &OS)

Definition MustExecute.h:550

PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...

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

Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...

Definition MustExecute.h:111

bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const override

Returns true if the instruction in a loop is guaranteed to execute at least once.

void computeLoopSafetyInfo(const Loop *CurLoop) override

Computes safety information for a loop checks loop body & header for the possibility of may throw exc...

bool anyBlockMayThrow() const override

Returns true iff any block of the loop for which this info is contains an instruction that may throw ...

bool blockMayThrow(const BasicBlock *BB) const override

Returns true iff the block BB potentially may throw exception.

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

A range adaptor for a pair of iterators.

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

@ Tail

Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...

This is an optimization pass for GlobalISel generic memory operations.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

OutputIt move(R &&Range, OutputIt Out)

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)

ExplorationDirection

Enum that allows us to spell out the direction.

Definition MustExecute.h:179

@ BACKWARD

Definition MustExecute.h:180

@ FORWARD

Definition MustExecute.h:181

AnalysisManager< Module > ModuleAnalysisManager

Convenience typedef for the Module analysis manager.

Implement std::hash so that hash_code can be used in STL containers.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

A "must be executed context" for a given program point PP is the set of instructions,...

Definition MustExecute.h:388

const bool ExploreInterBlock

Parameter that limit the performed exploration.

Definition MustExecute.h:518

const_iterator & begin(const Instruction *PP) const

Return an iterator to explore the cached context around PP.

Definition MustExecute.h:430

LLVM_ABI const BasicBlock * findBackwardJoinPoint(const BasicBlock *InitBB)

Find the next join point from InitBB in backward direction.

LLVM_ABI const Instruction * getMustBeExecutedNextInstruction(MustBeExecutedIterator &It, const Instruction *PP)

Return the next instruction that is guaranteed to be executed after PP.

iterator & end()

Return an universal end iterator.

Definition MustExecute.h:436

MustBeExecutedContextExplorer(bool ExploreInterBlock, bool ExploreCFGForward, bool ExploreCFGBackward, GetterTy< const LoopInfo > LIGetter=[](const Function &) { return nullptr;}, GetterTy< const DominatorTree > DTGetter=[](const Function &) { return nullptr;}, GetterTy< const PostDominatorTree > PDTGetter=[](const Function &) { return nullptr;})

In the description of the parameters we use PP to denote a program point for which the must be execut...

Definition MustExecute.h:403

const bool ExploreCFGBackward

Definition MustExecute.h:520

const bool ExploreCFGForward

Definition MustExecute.h:519

bool findInContextOf(const Instruction *I, const Instruction *PP)

Helper to look for I in the context of PP.

Definition MustExecute.h:472

const_iterator & end() const

Definition MustExecute.h:439

iterator & begin(const Instruction *PP)

Return an iterator to explore the context around PP.

Definition MustExecute.h:422

llvm::iterator_range< iterator > range(const Instruction *PP)

}

Definition MustExecute.h:444

LLVM_ABI const Instruction * getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It, const Instruction *PP)

Return the previous instr.

bool checkForAllContext(const Instruction *PP, function_ref< bool(const Instruction *)> Pred)

}

Definition MustExecute.h:458

LLVM_ABI const BasicBlock * findForwardJoinPoint(const BasicBlock *InitBB)

Find the next join point from InitBB in forward direction.

const_iterator & end(const Instruction *) const

Definition MustExecute.h:440

bool findInContextOf(const Instruction *I, iterator &EIt, iterator &EEnd)

Helper to look for I in the context defined by EIt and EEnd.

Definition MustExecute.h:483

iterator & end(const Instruction *)

Definition MustExecute.h:437

llvm::iterator_range< const_iterator > range(const Instruction *PP) const

Return an iterator range to explore the cached context around PP.

Definition MustExecute.h:449

const MustBeExecutedIterator const_iterator

Definition MustExecute.h:419

MustBeExecutedIterator iterator

Iterator-based interface.

Definition MustExecute.h:418

Must be executed iterators visit stretches of instructions that are guaranteed to be executed togethe...

Definition MustExecute.h:274

bool operator!=(const MustBeExecutedIterator &Other) const

Definition MustExecute.h:324

const Instruction * value_type

Type declarations that make his class an input iterator.

Definition MustExecute.h:277

MustBeExecutedIterator(const MustBeExecutedIterator &Other)=default

MustBeExecutedContextExplorer ExplorerTy

}

Definition MustExecute.h:284

const Instruction *& reference

Definition MustExecute.h:280

const Instruction ** pointer

Definition MustExecute.h:279

const Instruction * getCurrentInst() const

Definition MustExecute.h:331

bool operator==(const MustBeExecutedIterator &Other) const

}

Definition MustExecute.h:320

~MustBeExecutedIterator()=default

std::input_iterator_tag iterator_category

Definition MustExecute.h:281

MustBeExecutedIterator(MustBeExecutedIterator &&Other)

Definition MustExecute.h:288

std::ptrdiff_t difference_type

Definition MustExecute.h:278

MustBeExecutedIterator & operator=(MustBeExecutedIterator &&Other)

Definition MustExecute.h:292

bool count(const Instruction *I) const

Return true if I was encountered by this iterator already.

Definition MustExecute.h:334

MustBeExecutedIterator operator++(int)

Definition MustExecute.h:311

friend struct MustBeExecutedContextExplorer

Definition MustExecute.h:375

MustBeExecutedIterator & operator++()

Pre- and post-increment operators.

Definition MustExecute.h:306

const Instruction *& operator*()

}

Definition MustExecute.h:330

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