MustExecute.cpp Source File (original) (raw)

25using namespace llvm;

27#define DEBUG_TYPE "must-execute"

31 return BlockColors;

32}

35 ColorVector &ColorsForNewBlock = BlockColors[New];

36 ColorVector &ColorsForOldBlock = BlockColors[Old];

37 ColorsForNewBlock = ColorsForOldBlock;

38}

41 (void)BB;

43}

46 return MayThrow;

47}

50 assert(CurLoop != nullptr && "CurLoop can't be null");

54 MayThrow = HeaderMayThrow;

59 "First block must be header");

62 if (MayThrow)

63 break;

64 }

67}

70 return ICF.hasICF(BB);

71}

74 return MayThrow;

75}

78 assert(CurLoop != nullptr && "CurLoop can't be null");

81 MayThrow = false;

83 for (const auto &BB : CurLoop->blocks())

84 if (ICF.hasICF(&*BB)) {

85 MayThrow = true;

86 break;

87 }

89}

95}

100}

101

103

104

110}

111

112

113

114

117 const Loop *CurLoop) {

119 if (!CondExitBlock)

120

121 return false;

122 assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");

123 auto *BI = dyn_cast(CondExitBlock->getTerminator());

124 if (!BI || !BI->isConditional())

125 return false;

126

127

128 if (auto *Cond = dyn_cast(BI->getCondition()))

129 return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;

130 auto *Cond = dyn_cast(BI->getCondition());

132 return false;

133

134

135

137 auto *LHS = dyn_cast(Cond->getOperand(0));

138 auto *RHS = Cond->getOperand(1);

140 Pred = Cond->getSwappedPredicate();

141 LHS = dyn_cast(Cond->getOperand(1));

142 RHS = Cond->getOperand(0);

144 return false;

145 }

146

148 auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());

150 Pred, IVStart, RHS, {DL, nullptr, DT, nullptr, BI});

151 auto *SimpleCst = dyn_cast_or_null(SimpleValOrNull);

152 if (!SimpleCst)

153 return false;

154 if (ExitBlock == BI->getSuccessor(0))

155 return SimpleCst->isZeroValue();

156 assert(ExitBlock == BI->getSuccessor(1) && "implied by above");

157 return SimpleCst->isAllOnesValue();

158}

159

160

161

162

163

164

165

169 assert(Predecessors.empty() && "Garbage in predecessors set?");

170 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");

172 return;

175 if (!CurLoop->contains(Pred))

176 continue;

177 Predecessors.insert(Pred);

179 }

180 while (!WorkList.empty()) {

182 assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");

183

184 if (Pred == CurLoop->getHeader())

185 continue;

186

187

188

189

190

191

192 for (const auto *PredPred : predecessors(Pred))

193 if (CurLoop->contains(PredPred) && Predecessors.insert(PredPred).second)

195 }

196}

197

201 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");

202

203

205 return true;

206

207

208

211

212

213

214

216

217

218 if (Predecessors.contains(Pred))

219 return false;

220

221

222

223

224

225

226

228 for (const auto *Pred : Predecessors) {

229

231 return false;

232

233

234

236 continue;

237

238 for (const auto *Succ : successors(Pred))

239 if (CheckedSuccessors.insert(Succ).second &&

240 Succ != BB && !Predecessors.count(Succ))

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255 if (CurLoop->contains(Succ) ||

257 return false;

258 }

259

260

261 return true;

262}

263

264

265

268 const Loop *CurLoop) const {

269

270

271

273

274

275

276

277 return !HeaderMayThrow ||

278 Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;

279

280

281

283}

284

287 const Loop *CurLoop) const {

290}

291

293 const Loop *CurLoop) const {

294 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");

295

296

298 return true;

299

300

301

304

305

306 for (const auto *Pred : Predecessors)

308 return false;

309 return true;

310}

311

313 const Loop *CurLoop) const {

314 auto *BB = I.getParent();

315 assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");

318}

319

321

322

323

328}

329

330namespace {

331

332

335

336public:

337 MustExecuteAnnotatedWriter(const Function &F,

341 while (L) {

343 MustExec[&I].push_back(L);

344 }

345 L = L->getParentLoop();

346 };

347 }

348 }

349 MustExecuteAnnotatedWriter(const Module &M,

351 for (const auto &F : M)

354 while (L) {

356 MustExec[&I].push_back(L);

357 }

358 L = L->getParentLoop();

359 };

360 }

361 }

362

363

365 if (!MustExec.count(&V))

366 return;

367

369 const auto NumLoops = Loops.size();

370 if (NumLoops > 1)

371 OS << " ; (mustexec in " << NumLoops << " loops: ";

372 else

373 OS << " ; (mustexec in: ";

374

375 ListSeparator LS;

377 OS << LS << L->getHeader()->getName();

378 OS << ")";

379 }

380};

381}

382

383

385 if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))

386 return false;

387

388

389 return true;

390}

391

393 if (!LI)

394 return false;

396 RPOTraversal FuncRPOT(&F);

398 const LoopInfo>(FuncRPOT, *LI);

399}

400

401

402

403template <typename K, typename V, typename FnTy, typename... ArgsTy>

405 FnTy &&Fn, ArgsTy &&...args) {

406 std::optional &OptVal = Map[Key];

407 if (!OptVal)

408 OptVal = Fn(std::forward(args)...);

409 return *OptVal;

410}

411

416

418 << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));

419

421 const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;

422 const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;

423 bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) ||

425 F.doesNotThrow();

427 << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")

428 << "\n");

429

430

431

434 bool IsLatch = SuccBB == HeaderBB;

435

436

437 if (!WillReturnAndNoThrow || !IsLatch)

439 }

441

442

443 if (Worklist.empty())

444 return nullptr;

445

446

447 if (Worklist.size() == 1)

448 return Worklist[0];

449

450

451

452

454 if (PDT)

455 if (const auto *InitNode = PDT->getNode(InitBB))

456 if (const auto *IDomNode = InitNode->getIDom())

457 JoinBB = IDomNode->getBlock();

458

459 if (!JoinBB && Worklist.size() == 2) {

460 const BasicBlock *Succ0 = Worklist[0];

461 const BasicBlock *Succ1 = Worklist[1];

464 if (Succ0UniqueSucc == InitBB) {

465

466

467 JoinBB = Succ1;

468 } else if (Succ1UniqueSucc == InitBB) {

469

470

471 JoinBB = Succ0;

472 } else if (Succ0 == Succ1UniqueSucc) {

473

474

475 JoinBB = Succ0;

476 } else if (Succ1 == Succ0UniqueSucc) {

477

478

479 JoinBB = Succ1;

480 } else if (Succ0UniqueSucc == Succ1UniqueSucc) {

481

482

483 JoinBB = Succ0UniqueSucc;

484 }

485 }

486

487 if (!JoinBB && L)

488 JoinBB = L->getUniqueExitBlock();

489

490 if (!JoinBB)

491 return nullptr;

492

494

495

496

497

498

499

500

501

502

503 if (.hasFnAttribute(Attribute::WillReturn) || .doesNotThrow()) {

504

505 auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {

507 };

508

510 while (!Worklist.empty()) {

512 if (ToBB == JoinBB)

513 continue;

514

515

516 if (!Visited.insert(ToBB).second) {

517 if (.hasFnAttribute(Attribute::WillReturn)) {

518 if (!LI)

519 return nullptr;

520

523 if (MayContainIrreducibleControl)

524 return nullptr;

525

528 return nullptr;

529 }

530

531 continue;

532 }

533

534

535

537 ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);

538 if (!TransfersExecution)

539 return nullptr;

540

542 }

543 }

544

546 return JoinBB;

547}

553 << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));

554

555

556

557

558 if (DT)

559 if (const auto *InitNode = DT->getNode(InitBB))

560 if (const auto *IDomNode = InitNode->getIDom())

561 return IDomNode->getBlock();

562

563 const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;

564 const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;

565

566

569 bool IsBackedge =

570 (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(PredBB));

571

572

573 if (!IsBackedge)

575 }

576

577

578 if (Worklist.empty())

579 return nullptr;

580

581

582 if (Worklist.size() == 1)

583 return Worklist[0];

584

586 if (Worklist.size() == 2) {

587 const BasicBlock *Pred0 = Worklist[0];

588 const BasicBlock *Pred1 = Worklist[1];

591 if (Pred0 == Pred1UniquePred) {

592

593

594 JoinBB = Pred0;

595 } else if (Pred1 == Pred0UniquePred) {

596

597

598 JoinBB = Pred1;

599 } else if (Pred0UniquePred == Pred1UniquePred) {

600

601

602 JoinBB = Pred0UniquePred;

603 }

604 }

605

606 if (!JoinBB && L)

607 JoinBB = L->getHeader();

608

609

610

611

612 return JoinBB;

613}

614

618 if (!PP)

619 return PP;

620 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");

621

622

624 LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");

625 return nullptr;

626 }

627

628

629

630

632 if (!TransfersExecution)

633 return nullptr;

634

635

636

637

638

641 LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");

642 return NextPP;

643 }

644

645

647

648

651 return nullptr;

652 }

653

654

655

658 dbgs() << "\tUnconditional terminator, continue with successor\n");

660 }

661

662

663

664

666 return &JoinBB->front();

667

669 return nullptr;

670}

671

675 if (!PP)

676 return PP;

677

679 LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP

680 << (IsFirst ? " [IsFirst]" : "") << "\n");

681

682

683

685 LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");

686 return nullptr;

687 }

688

689

691

692

693

694 if (!IsFirst) {

697 dbgs() << "\tIntermediate instruction, continue with previous\n");

698

699 return PrevPP;

700 }

701

702

703

704

705

707 return &JoinBB->back();

708

710 return nullptr;

711}

712

715 : Explorer(Explorer), CurInst(I) {

716 reset(I);

717}

718

719void MustBeExecutedIterator::reset(const Instruction *I) {

721 resetInstruction(I);

722}

723

724void MustBeExecutedIterator::resetInstruction(const Instruction *I) {

725 CurInst = I;

726 Head = Tail = nullptr;

730 Head = I;

732 Tail = I;

733}

734

735const Instruction *MustBeExecutedIterator::advance() {

736 assert(CurInst && "Cannot advance an end iterator!");

738 if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second)

739 return Head;

740 Head = nullptr;

741

743 if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second)

744 return Tail;

745 Tail = nullptr;

746 return nullptr;

747}

748

753

754 MustExecuteAnnotatedWriter Writer(F, DT, LI);

755 F.print(OS, &Writer);

757}

758

763 GetterTy LIGetter = [&](const Function &F) {

765 };

766 GetterTy DTGetter = [&](const Function &F) {

768 };

769 GetterTy PDTGetter = [&](const Function &F) {

771 };

772

774 true,

775 true,

776 true, LIGetter, DTGetter, PDTGetter);

777

780 OS << "-- Explore context of: " << I << "\n";

782 OS << " [F: " << CI->getFunction()->getName() << "] " << *CI << "\n";

783 }

784 }

786}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Expand Atomic instructions

Module.h This file contains the declarations for the Module class.

This header defines various interfaces for pass management in LLVM.

static void collectTransitivePredecessors(const Loop *CurLoop, const BasicBlock *BB, SmallPtrSetImpl< const BasicBlock * > &Predecessors)

Collect all blocks from CurLoop which lie on all possible paths from the header of CurLoop (inclusive...

static bool maybeEndlessLoop(const Loop &L)

Return true if L might be an endless loop.

static V getOrCreateCachedOptional(K Key, DenseMap< K, std::optional< V > > &Map, FnTy &&Fn, ArgsTy &&...args)

Lookup Key in Map and return the result, potentially after initializing the optional through Fn(args)...

static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT)

static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock, const DominatorTree *DT, const Loop *CurLoop)

Return true if we can prove that the given ExitBlock is not reached on the first iteration of the giv...

Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...

FunctionAnalysisManager FAM

This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.

const SmallVectorImpl< MachineOperand > & Cond

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

A container for analyses that lazily runs them and caches their results.

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

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

LLVM Basic Block Representation.

const Instruction & front() const

const BasicBlock * getUniqueSuccessor() const

Return the successor of this block if it has a unique successor.

const BasicBlock * getSinglePredecessor() const

Return the predecessor of this block if it has a single predecessor block.

const BasicBlock * getUniquePredecessor() const

Return the predecessor of this block if it has a unique predecessor block.

const Function * getParent() const

Return the enclosing method, or null if none.

const Module * getModule() const

Return the module owning the function this basic block belongs to, or nullptr if the function does no...

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

This is an important base class in LLVM.

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

Analysis pass which computes a DominatorTree.

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

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.

bool hasPersonalityFn() const

Check whether this function has a personality function.

Constant * getPersonalityFn() const

Get the personality function associated with this function.

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.

bool isDominatedByICFIFromSameBlock(const Instruction *Insn)

Returns true if the first ICFI of Insn's block exists and dominates Insn.

bool hasICF(const BasicBlock *BB)

Returns true if at least one instruction from the given basic block has implicit control flow.

An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...

void clear()

Invalidates all information from this tracking.

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

Notifies this tracking that we are going to insert a new instruction Inst to the basic block BB.

void removeInstruction(const Instruction *Inst)

Notifies this tracking that we are going to remove the instruction Inst It makes all necessary update...

unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

Return the specified successor. This instruction must be a terminator.

bool isTerminator() const

Analysis pass that exposes the LoopInfo for a function.

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this loop.

BlockT * getHeader() const

iterator_range< block_iterator > blocks() const

BlockT * getLoopPreheader() const

If there is a preheader for this loop, return it.

ArrayRef< BlockT * > getBlocks() const

Get a list of the basic blocks which make up this loop.

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

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.

void copyColors(BasicBlock *New, BasicBlock *Old)

Copy colors of block Old into the block New.

void computeBlockColors(const Loop *CurLoop)

Computes block colors.

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

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

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

Returns true iff the block BB potentially may throw exception.

Represents a single loop in the control flow graph.

bool mayWriteToMemory(const BasicBlock *BB)

Returns true if at least one instruction from the given basic block may write memory.

bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn)

Returns true if the first memory writing instruction of Insn's block exists and dominates Insn.

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

const DataLayout & getDataLayout() const

Get the data layout for the module's target platform.

PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Analysis pass which computes a PostDominatorTree.

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.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

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

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.

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

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.

bool contains(ConstPtrType Ptr) const

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

void push_back(const T &Elt)

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

TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...

LLVM Value Representation.

StringRef getName() const

Return a constant reference to the value's name.

std::pair< iterator, bool > insert(const ValueT &V)

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

const ParentTy * getParent() const

NodeTy * getNextNode()

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

This is an optimization pass for GlobalISel generic memory operations.

auto drop_begin(T &&RangeOrContainer, size_t N=1)

Return a range covering RangeOrContainer with the first N elements excluded.

auto successors(const MachineBasicBlock *BB)

bool isGuaranteedToExecuteForEveryIteration(const Instruction *I, const Loop *L)

Return true if this function can prove that the instruction I is executed for every iteration of the ...

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

DenseMap< BasicBlock *, ColorVector > colorEHFunclets(Function &F)

If an EH funclet personality is in use (see isFuncletEHPersonality), this will recompute which blocks...

bool isScopedEHPersonality(EHPersonality Pers)

Returns true if this personality uses scope-style EH IR instructions: catchswitch,...

bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)

Return true if the control flow in RPOTraversal is irreducible.

raw_ostream & dbgs()

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

EHPersonality classifyEHPersonality(const Value *Pers)

See if the given exception handling personality function is one that we understand.

bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)

Return true if this function can prove that the instruction I will always transfer execution to one o...

auto predecessors(const MachineBasicBlock *BB)

Value * simplifyCmpInst(CmpPredicate Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)

Given operands for a CmpInst, fold the result or return null.

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

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

const bool ExploreInterBlock

Parameter that limit the performed exploration.

const BasicBlock * findBackwardJoinPoint(const BasicBlock *InitBB)

Find the next join point from InitBB in backward direction.

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

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

const bool ExploreCFGBackward

const bool ExploreCFGForward

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

}

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

Return the previous instr.

const BasicBlock * findForwardJoinPoint(const BasicBlock *InitBB)

Find the next join point from InitBB in forward direction.

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

MustBeExecutedIterator(const MustBeExecutedIterator &Other)=default