Movatterモバイル変換

Go to the documentation of this file.

1//===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

8//

9// This file defines the LoopInfo class that is used to identify natural loops

10// and determine the loop depth of various nodes of the CFG. Note that the

11// loops identified may actually be several natural loops that share the same

12// header node... not just a single natural loop.

13//

14//===----------------------------------------------------------------------===//

16#include "llvm/Analysis/LoopInfo.h"

17#include "llvm/ADT/ScopeExit.h"

18#include "llvm/ADT/SmallPtrSet.h"

19#include "llvm/Analysis/IVDescriptors.h"

20#include "llvm/Analysis/LoopIterator.h"

21#include "llvm/Analysis/LoopNestAnalysis.h"

22#include "llvm/Analysis/MemorySSA.h"

23#include "llvm/Analysis/MemorySSAUpdater.h"

24#include "llvm/Analysis/ScalarEvolutionExpressions.h"

25#include "llvm/Analysis/ValueTracking.h"

26#include "llvm/Config/llvm-config.h"

27#include "llvm/IR/CFG.h"

28#include "llvm/IR/Constants.h"

29#include "llvm/IR/DebugLoc.h"

30#include "llvm/IR/Dominators.h"

31#include "llvm/IR/Instructions.h"

32#include "llvm/IR/LLVMContext.h"

33#include "llvm/IR/Metadata.h"

34#include "llvm/IR/Module.h"

35#include "llvm/IR/PassManager.h"

36#include "llvm/IR/PrintPasses.h"

37#include "llvm/InitializePasses.h"

38#include "llvm/Support/CommandLine.h"

39#include "llvm/Support/GenericLoopInfoImpl.h"

40#include "llvm/Support/raw_ostream.h"

41using namespacellvm;

43// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.

44templateclassllvm::LoopBase<BasicBlock, Loop>;

45templateclassllvm::LoopInfoBase<BasicBlock, Loop>;

47// Always verify loopinfo if expensive checking is enabled.

48#ifdef EXPENSIVE_CHECKS

49boolllvm::VerifyLoopInfo =true;

50#else

51boolllvm::VerifyLoopInfo =false;

52#endif

53staticcl::opt<bool, true>

54VerifyLoopInfoX("verify-loop-info",cl::location(VerifyLoopInfo),

55cl::Hidden,cl::desc("Verify loop info (time consuming)"));

57//===----------------------------------------------------------------------===//

58// Loop implementation

59//

61boolLoop::isLoopInvariant(constValue *V) const{

62if (constInstruction *I = dyn_cast<Instruction>(V))

63return !contains(I);

64returntrue;// All non-instructions are loop invariant

65}

67boolLoop::hasLoopInvariantOperands(constInstruction *I) const{

68returnall_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });

69}

71boolLoop::makeLoopInvariant(Value *V,bool &Changed,Instruction *InsertPt,

72MemorySSAUpdater *MSSAU,

73ScalarEvolution *SE) const{

74if (Instruction *I = dyn_cast<Instruction>(V))

75returnmakeLoopInvariant(I, Changed, InsertPt, MSSAU, SE);

76returntrue;// All non-instructions are loop-invariant.

77}

79boolLoop::makeLoopInvariant(Instruction *I,bool &Changed,

80Instruction *InsertPt,MemorySSAUpdater *MSSAU,

81ScalarEvolution *SE) const{

82// Test if the value is already loop-invariant.

83if (isLoopInvariant(I))

84returntrue;

85if (!isSafeToSpeculativelyExecute(I))

86returnfalse;

87if (I->mayReadFromMemory())

88returnfalse;

89// EH block instructions are immobile.

90if (I->isEHPad())

91returnfalse;

92// Determine the insertion point, unless one was given.

93if (!InsertPt) {

94BasicBlock *Preheader =getLoopPreheader();

95// Without a preheader, hoisting is not feasible.

96if (!Preheader)

97returnfalse;

98 InsertPt = Preheader->getTerminator();

99 }

100// Don't hoist instructions with loop-variant operands.

101for (Value *Operand :I->operands())

102if (!makeLoopInvariant(Operand, Changed, InsertPt, MSSAU, SE))

103returnfalse;

104

105// Hoist.

106I->moveBefore(InsertPt->getIterator());

107if (MSSAU)

108if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I))

109 MSSAU->moveToPlace(MUD, InsertPt->getParent(),

110MemorySSA::BeforeTerminator);

111

112// There is possibility of hoisting this instruction above some arbitrary

113// condition. Any metadata defined on it can be control dependent on this

114// condition. Conservatively strip it here so that we don't give any wrong

115// information to the optimizer.

116I->dropUnknownNonDebugMetadata();

117

118if (SE)

119 SE->forgetBlockAndLoopDispositions(I);

120

121 Changed =true;

122returntrue;

123}

124

125boolLoop::getIncomingAndBackEdge(BasicBlock *&Incoming,

126BasicBlock *&Backedge) const{

127BasicBlock *H =getHeader();

128

129Incoming =nullptr;

130 Backedge =nullptr;

131pred_iterator PI =pred_begin(H);

132assert(PI !=pred_end(H) &&"Loop must have at least one backedge!");

133 Backedge = *PI++;

134if (PI ==pred_end(H))

135returnfalse;// dead loop

136Incoming = *PI++;

137if (PI !=pred_end(H))

138returnfalse;// multiple backedges?

139

140if (contains(Incoming)) {

141if (contains(Backedge))

142returnfalse;

143std::swap(Incoming, Backedge);

144 }elseif (!contains(Backedge))

145returnfalse;

146

147assert(Incoming && Backedge &&"expected non-null incoming and backedges");

148returntrue;

149}

150

151PHINode *Loop::getCanonicalInductionVariable() const{

152BasicBlock *H =getHeader();

153

154BasicBlock *Incoming =nullptr, *Backedge =nullptr;

155if (!getIncomingAndBackEdge(Incoming, Backedge))

156returnnullptr;

157

158// Loop over all of the PHI nodes, looking for a canonical indvar.

159for (BasicBlock::iterator I =H->begin(); isa<PHINode>(I); ++I) {

160PHINode *PN = cast<PHINode>(I);

161if (ConstantInt *CI =

162 dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))

163if (CI->isZero())

164if (Instruction *Inc =

165 dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))

166if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)

167if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))

168if (CI->isOne())

169return PN;

170 }

171returnnullptr;

172}

173

174/// Get the latch condition instruction.

175ICmpInst *Loop::getLatchCmpInst() const{

176if (BasicBlock *Latch =getLoopLatch())

177if (BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator()))

178if (BI->isConditional())

179return dyn_cast<ICmpInst>(BI->getCondition());

180

181returnnullptr;

182}

183

184/// Return the final value of the loop induction variable if found.

185staticValue *findFinalIVValue(constLoop &L,constPHINode &IndVar,

186constInstruction &StepInst) {

187ICmpInst *LatchCmpInst = L.getLatchCmpInst();

188if (!LatchCmpInst)

189returnnullptr;

190

191Value *Op0 = LatchCmpInst->getOperand(0);

192Value *Op1 = LatchCmpInst->getOperand(1);

193if (Op0 == &IndVar || Op0 == &StepInst)

194return Op1;

195

196if (Op1 == &IndVar || Op1 == &StepInst)

197return Op0;

198

199returnnullptr;

200}

201

202std::optional<Loop::LoopBounds>

203Loop::LoopBounds::getBounds(constLoop &L,PHINode &IndVar,

204ScalarEvolution &SE) {

205InductionDescriptor IndDesc;

206if (!InductionDescriptor::isInductionPHI(&IndVar, &L, &SE, IndDesc))

207return std::nullopt;

208

209Value *InitialIVValue = IndDesc.getStartValue();

210Instruction *StepInst = IndDesc.getInductionBinOp();

211if (!InitialIVValue || !StepInst)

212return std::nullopt;

213

214constSCEV *Step = IndDesc.getStep();

215Value *StepInstOp1 = StepInst->getOperand(1);

216Value *StepInstOp0 = StepInst->getOperand(0);

217Value *StepValue =nullptr;

218if (SE.getSCEV(StepInstOp1) == Step)

219 StepValue = StepInstOp1;

220elseif (SE.getSCEV(StepInstOp0) == Step)

221 StepValue = StepInstOp0;

222

223Value *FinalIVValue =findFinalIVValue(L, IndVar, *StepInst);

224if (!FinalIVValue)

225return std::nullopt;

226

227returnLoopBounds(L, *InitialIVValue, *StepInst, StepValue, *FinalIVValue,

228 SE);

229}

230

231usingDirection =Loop::LoopBounds::Direction;

232

233ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate() const{

234BasicBlock *Latch = L.getLoopLatch();

235assert(Latch &&"Expecting valid latch");

236

237BranchInst *BI = dyn_cast_or_null<BranchInst>(Latch->getTerminator());

238assert(BI && BI->isConditional() &&"Expecting conditional latch branch");

239

240ICmpInst *LatchCmpInst = dyn_cast<ICmpInst>(BI->getCondition());

241assert(LatchCmpInst &&

242"Expecting the latch compare instruction to be a CmpInst");

243

244// Need to inverse the predicate when first successor is not the loop

245// header

246ICmpInst::Predicate Pred = (BI->getSuccessor(0) == L.getHeader())

247 ? LatchCmpInst->getPredicate()

248 : LatchCmpInst->getInversePredicate();

249

250if (LatchCmpInst->getOperand(0) == &getFinalIVValue())

251 Pred =ICmpInst::getSwappedPredicate(Pred);

252

253// Need to flip strictness of the predicate when the latch compare instruction

254// is not using StepInst

255if (LatchCmpInst->getOperand(0) == &getStepInst() ||

256 LatchCmpInst->getOperand(1) == &getStepInst())

257return Pred;

258

259// Cannot flip strictness of NE and EQ

260if (Pred !=ICmpInst::ICMP_NE && Pred !=ICmpInst::ICMP_EQ)

261returnICmpInst::getFlippedStrictnessPredicate(Pred);

262

263Direction D = getDirection();

264if (D == Direction::Increasing)

265returnICmpInst::ICMP_SLT;

266

267if (D == Direction::Decreasing)

268returnICmpInst::ICMP_SGT;

269

270// If cannot determine the direction, then unable to find the canonical

271// predicate

272returnICmpInst::BAD_ICMP_PREDICATE;

273}

274

275Direction Loop::LoopBounds::getDirection() const{

276if (constSCEVAddRecExpr *StepAddRecExpr =

277 dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&getStepInst())))

278if (constSCEV *StepRecur = StepAddRecExpr->getStepRecurrence(SE)) {

279if (SE.isKnownPositive(StepRecur))

280return Direction::Increasing;

281if (SE.isKnownNegative(StepRecur))

282return Direction::Decreasing;

283 }

284

285return Direction::Unknown;

286}

287

288std::optional<Loop::LoopBounds>Loop::getBounds(ScalarEvolution &SE) const{

289if (PHINode *IndVar =getInductionVariable(SE))

290returnLoopBounds::getBounds(*this, *IndVar, SE);

291

292return std::nullopt;

293}

294

295PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const{

296if (!isLoopSimplifyForm())

297returnnullptr;

298

299BasicBlock *Header =getHeader();

300assert(Header &&"Expected a valid loop header");

301ICmpInst *CmpInst =getLatchCmpInst();

302if (!CmpInst)

303returnnullptr;

304

305Value *LatchCmpOp0 =CmpInst->getOperand(0);

306Value *LatchCmpOp1 =CmpInst->getOperand(1);

307

308for (PHINode &IndVar : Header->phis()) {

309InductionDescriptor IndDesc;

310if (!InductionDescriptor::isInductionPHI(&IndVar,this, &SE, IndDesc))

311continue;

312

313BasicBlock *Latch =getLoopLatch();

314Value *StepInst = IndVar.getIncomingValueForBlock(Latch);

315

316// case 1:

317// IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]

318// StepInst = IndVar + step

319// cmp = StepInst < FinalValue

320if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1)

321return &IndVar;

322

323// case 2:

324// IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]

325// StepInst = IndVar + step

326// cmp = IndVar < FinalValue

327if (&IndVar == LatchCmpOp0 || &IndVar == LatchCmpOp1)

328return &IndVar;

329 }

330

331returnnullptr;

332}

333

334boolLoop::getInductionDescriptor(ScalarEvolution &SE,

335InductionDescriptor &IndDesc) const{

336if (PHINode *IndVar =getInductionVariable(SE))

337returnInductionDescriptor::isInductionPHI(IndVar,this, &SE, IndDesc);

338

339returnfalse;

340}

341

342boolLoop::isAuxiliaryInductionVariable(PHINode &AuxIndVar,

343ScalarEvolution &SE) const{

344// Located in the loop header

345BasicBlock *Header =getHeader();

346if (AuxIndVar.getParent() != Header)

347returnfalse;

348

349// No uses outside of the loop

350for (User *U : AuxIndVar.users())

351if (constInstruction *I = dyn_cast<Instruction>(U))

352if (!contains(I))

353returnfalse;

354

355InductionDescriptor IndDesc;

356if (!InductionDescriptor::isInductionPHI(&AuxIndVar,this, &SE, IndDesc))

357returnfalse;

358

359// The step instruction opcode should be add or sub.

360if (IndDesc.getInductionOpcode() != Instruction::Add &&

361 IndDesc.getInductionOpcode() != Instruction::Sub)

362returnfalse;

363

364// Incremented by a loop invariant step for each loop iteration

365return SE.isLoopInvariant(IndDesc.getStep(),this);

366}

367

368BranchInst *Loop::getLoopGuardBranch() const{

369if (!isLoopSimplifyForm())

370returnnullptr;

371

372BasicBlock *Preheader =getLoopPreheader();

373assert(Preheader &&getLoopLatch() &&

374"Expecting a loop with valid preheader and latch");

375

376// Loop should be in rotate form.

377if (!isRotatedForm())

378returnnullptr;

379

380// Disallow loops with more than one unique exit block, as we do not verify

381// that GuardOtherSucc post dominates all exit blocks.

382BasicBlock *ExitFromLatch =getUniqueExitBlock();

383if (!ExitFromLatch)

384returnnullptr;

385

386BasicBlock *GuardBB = Preheader->getUniquePredecessor();

387if (!GuardBB)

388returnnullptr;

389

390assert(GuardBB->getTerminator() &&"Expecting valid guard terminator");

391

392BranchInst *GuardBI = dyn_cast<BranchInst>(GuardBB->getTerminator());

393if (!GuardBI || GuardBI->isUnconditional())

394returnnullptr;

395

396BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(0) == Preheader)

397 ? GuardBI->getSuccessor(1)

398 : GuardBI->getSuccessor(0);

399

400// Check if ExitFromLatch (or any BasicBlock which is an empty unique

401// successor of ExitFromLatch) is equal to GuardOtherSucc. If

402// skipEmptyBlockUntil returns GuardOtherSucc, then the guard branch for the

403// loop is GuardBI (return GuardBI), otherwise return nullptr.

404if (&LoopNest::skipEmptyBlockUntil(ExitFromLatch, GuardOtherSucc,

405/*CheckUniquePred=*/true) ==

406 GuardOtherSucc)

407return GuardBI;

408else

409returnnullptr;

410}

411

412boolLoop::isCanonical(ScalarEvolution &SE) const{

413InductionDescriptor IndDesc;

414if (!getInductionDescriptor(SE, IndDesc))

415returnfalse;

416

417ConstantInt *Init = dyn_cast_or_null<ConstantInt>(IndDesc.getStartValue());

418if (!Init || !Init->isZero())

419returnfalse;

420

421if (IndDesc.getInductionOpcode() != Instruction::Add)

422returnfalse;

423

424ConstantInt *Step = IndDesc.getConstIntStepValue();

425if (!Step || !Step->isOne())

426returnfalse;

427

428returntrue;

429}

430

431// Check that 'BB' doesn't have any uses outside of the 'L'

432staticboolisBlockInLCSSAForm(constLoop &L,constBasicBlock &BB,

433constDominatorTree &DT,bool IgnoreTokens) {

434for (constInstruction &I : BB) {

435// Tokens can't be used in PHI nodes and live-out tokens prevent loop

436// optimizations, so for the purposes of considered LCSSA form, we

437// can ignore them.

438if (IgnoreTokens &&I.getType()->isTokenTy())

439continue;

440

441for (constUse &U :I.uses()) {

442constInstruction *UI = cast<Instruction>(U.getUser());

443constBasicBlock *UserBB = UI->getParent();

444

445// For practical purposes, we consider that the use in a PHI

446// occurs in the respective predecessor block. For more info,

447// see the `phi` doc in LangRef and the LCSSA doc.

448if (constPHINode *P = dyn_cast<PHINode>(UI))

449 UserBB =P->getIncomingBlock(U);

450

451// Check the current block, as a fast-path, before checking whether

452// the use is anywhere in the loop. Most values are used in the same

453// block they are defined in. Also, blocks not reachable from the

454// entry are special; uses in them don't need to go through PHIs.

455if (UserBB != &BB && !L.contains(UserBB) &&

456 DT.isReachableFromEntry(UserBB))

457returnfalse;

458 }

459 }

460returntrue;

461}

462

463boolLoop::isLCSSAForm(constDominatorTree &DT,bool IgnoreTokens) const{

464// For each block we check that it doesn't have any uses outside of this loop.

465returnall_of(this->blocks(), [&](constBasicBlock *BB) {

466returnisBlockInLCSSAForm(*this, *BB, DT, IgnoreTokens);

467 });

468}

469

470boolLoop::isRecursivelyLCSSAForm(constDominatorTree &DT,constLoopInfo &LI,

471bool IgnoreTokens) const{

472// For each block we check that it doesn't have any uses outside of its

473// innermost loop. This process will transitively guarantee that the current

474// loop and all of the nested loops are in LCSSA form.

475returnall_of(this->blocks(), [&](constBasicBlock *BB) {

476returnisBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT, IgnoreTokens);

477 });

478}

479

480boolLoop::isLoopSimplifyForm() const{

481// Normal-form loops have a preheader, a single backedge, and all of their

482// exits have all their predecessors inside the loop.

483returngetLoopPreheader() &&getLoopLatch() &&hasDedicatedExits();

484}

485

486// Routines that reform the loop CFG and split edges often fail on indirectbr.

487boolLoop::isSafeToClone() const{

488// Return false if any loop blocks contain indirectbrs, or there are any calls

489// to noduplicate functions.

490for (BasicBlock *BB : this->blocks()) {

491if (isa<IndirectBrInst>(BB->getTerminator()))

492returnfalse;

493

494for (Instruction &I : *BB)

495if (auto *CB = dyn_cast<CallBase>(&I))

496if (CB->cannotDuplicate())

497returnfalse;

498 }

499returntrue;

500}

501

502MDNode *Loop::getLoopID() const{

503MDNode *LoopID =nullptr;

504

505// Go through the latch blocks and check the terminator for the metadata.

506SmallVector<BasicBlock *, 4> LatchesBlocks;

507getLoopLatches(LatchesBlocks);

508for (BasicBlock *BB : LatchesBlocks) {

509Instruction *TI = BB->getTerminator();

510MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);

511

512if (!MD)

513returnnullptr;

514

515if (!LoopID)

516 LoopID = MD;

517elseif (MD != LoopID)

518returnnullptr;

519 }

520if (!LoopID || LoopID->getNumOperands() == 0 ||

521 LoopID->getOperand(0) != LoopID)

522returnnullptr;

523return LoopID;

524}

525

526voidLoop::setLoopID(MDNode *LoopID) const{

527assert((!LoopID || LoopID->getNumOperands() > 0) &&

528"Loop ID needs at least one operand");

529assert((!LoopID || LoopID->getOperand(0) == LoopID) &&

530"Loop ID should refer to itself");

531

532SmallVector<BasicBlock *, 4> LoopLatches;

533getLoopLatches(LoopLatches);

534for (BasicBlock *BB : LoopLatches)

535 BB->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);

536}

537

538voidLoop::setLoopAlreadyUnrolled() {

539LLVMContext &Context =getHeader()->getContext();

540

541MDNode *DisableUnrollMD =

542MDNode::get(Context,MDString::get(Context,"llvm.loop.unroll.disable"));

543MDNode *LoopID =getLoopID();

544MDNode *NewLoopID =makePostTransformationMetadata(

545 Context, LoopID, {"llvm.loop.unroll."}, {DisableUnrollMD});

546setLoopID(NewLoopID);

547}

548

549voidLoop::setLoopMustProgress() {

550LLVMContext &Context =getHeader()->getContext();

551

552MDNode *MustProgress =findOptionMDForLoop(this,"llvm.loop.mustprogress");

553

554if (MustProgress)

555return;

556

557MDNode *MustProgressMD =

558MDNode::get(Context,MDString::get(Context,"llvm.loop.mustprogress"));

559MDNode *LoopID =getLoopID();

560MDNode *NewLoopID =

561makePostTransformationMetadata(Context, LoopID, {}, {MustProgressMD});

562setLoopID(NewLoopID);

563}

564

565boolLoop::isAnnotatedParallel() const{

566MDNode *DesiredLoopIdMetadata =getLoopID();

567

568if (!DesiredLoopIdMetadata)

569returnfalse;

570

571MDNode *ParallelAccesses =

572findOptionMDForLoop(this,"llvm.loop.parallel_accesses");

573SmallPtrSet<MDNode *, 4>

574 ParallelAccessGroups;// For scalable 'contains' check.

575if (ParallelAccesses) {

576for (constMDOperand &MD :drop_begin(ParallelAccesses->operands())) {

577MDNode *AccGroup = cast<MDNode>(MD.get());

578assert(isValidAsAccessGroup(AccGroup) &&

579"List item must be an access group");

580 ParallelAccessGroups.insert(AccGroup);

581 }

582 }

583

584// The loop branch contains the parallel loop metadata. In order to ensure

585// that any parallel-loop-unaware optimization pass hasn't added loop-carried

586// dependencies (thus converted the loop back to a sequential loop), check

587// that all the memory instructions in the loop belong to an access group that

588// is parallel to this loop.

589for (BasicBlock *BB : this->blocks()) {

590for (Instruction &I : *BB) {

591if (!I.mayReadOrWriteMemory())

592continue;

593

594if (MDNode *AccessGroup =I.getMetadata(LLVMContext::MD_access_group)) {

595auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) ->bool {

596if (AG->getNumOperands() == 0) {

597assert(isValidAsAccessGroup(AG) &&"Item must be an access group");

598return ParallelAccessGroups.count(AG);

599 }

600

601for (constMDOperand &AccessListItem : AG->operands()) {

602MDNode *AccGroup = cast<MDNode>(AccessListItem.get());

603assert(isValidAsAccessGroup(AccGroup) &&

604"List item must be an access group");

605if (ParallelAccessGroups.count(AccGroup))

606returntrue;

607 }

608returnfalse;

609 };

610

611if (ContainsAccessGroup(AccessGroup))

612continue;

613 }

614

615// The memory instruction can refer to the loop identifier metadata

616// directly or indirectly through another list metadata (in case of

617// nested parallel loops). The loop identifier metadata refers to

618// itself so we can check both cases with the same routine.

619MDNode *LoopIdMD =

620I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);

621

622if (!LoopIdMD)

623returnfalse;

624

625if (!llvm::is_contained(LoopIdMD->operands(), DesiredLoopIdMetadata))

626returnfalse;

627 }

628 }

629returntrue;

630}

631

632DebugLoc Loop::getStartLoc() const{returngetLocRange().getStart(); }

633

634Loop::LocRange Loop::getLocRange() const{

635// If we have a debug location in the loop ID, then use it.

636if (MDNode *LoopID =getLoopID()) {

637DebugLoc Start;

638// We use the first DebugLoc in the header as the start location of the loop

639// and if there is a second DebugLoc in the header we use it as end location

640// of the loop.

641for (constMDOperand &MDO :llvm::drop_begin(LoopID->operands())) {

642if (DILocation *L = dyn_cast<DILocation>(MDO)) {

643if (!Start)

644 Start =DebugLoc(L);

645else

646returnLocRange(Start,DebugLoc(L));

647 }

648 }

649

650if (Start)

651returnLocRange(Start);

652 }

653

654// Try the pre-header first.

655if (BasicBlock *PHeadBB =getLoopPreheader())

656if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())

657returnLocRange(DL);

658

659// If we have no pre-header or there are no instructions with debug

660// info in it, try the header.

661if (BasicBlock *HeadBB =getHeader())

662returnLocRange(HeadBB->getTerminator()->getDebugLoc());

663

664returnLocRange();

665}

666

667std::stringLoop::getLocStr() const{

668 std::string Result;

669raw_string_ostream OS(Result);

670if (constDebugLoc LoopDbgLoc =getStartLoc())

671 LoopDbgLoc.print(OS);

672else

673// Just print the module name.

674OS <<getHeader()->getParent()->getParent()->getModuleIdentifier();

675return Result;

676}

677

678#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

679LLVM_DUMP_METHODvoidLoop::dump() const{print(dbgs()); }

680

681LLVM_DUMP_METHODvoidLoop::dumpVerbose() const{

682print(dbgs(),/*Verbose=*/true);

683}

684#endif

685

686//===----------------------------------------------------------------------===//

687// UnloopUpdater implementation

688//

689

690namespace{

691/// Find the new parent loop for all blocks within the "unloop" whose last

692/// backedges has just been removed.

693classUnloopUpdater {

694Loop &Unloop;

695LoopInfo *LI;

696

697LoopBlocksDFS DFS;

698

699// Map unloop's immediate subloops to their nearest reachable parents. Nested

700// loops within these subloops will not change parents. However, an immediate

701// subloop's new parent will be the nearest loop reachable from either its own

702// exits *or* any of its nested loop's exits.

703DenseMap<Loop *, Loop *> SubloopParents;

704

705// Flag the presence of an irreducible backedge whose destination is a block

706// directly contained by the original unloop.

707bool FoundIB =false;

708

709public:

710 UnloopUpdater(Loop *UL,LoopInfo *LInfo) : Unloop(*UL), LI(LInfo), DFS(UL) {}

711

712void updateBlockParents();

713

714void removeBlocksFromAncestors();

715

716void updateSubloopParents();

717

718protected:

719Loop *getNearestLoop(BasicBlock *BB,Loop *BBLoop);

720};

721}// end anonymous namespace

722

723/// Update the parent loop for all blocks that are directly contained within the

724/// original "unloop".

725void UnloopUpdater::updateBlockParents() {

726if (Unloop.getNumBlocks()) {

727// Perform a post order CFG traversal of all blocks within this loop,

728// propagating the nearest loop from successors to predecessors.

729LoopBlocksTraversal Traversal(DFS, LI);

730for (BasicBlock *POI : Traversal) {

731

732Loop *L = LI->getLoopFor(POI);

733Loop *NL = getNearestLoop(POI, L);

734

735if (NL != L) {

736// For reducible loops, NL is now an ancestor of Unloop.

737assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&

738"uninitialized successor");

739 LI->changeLoopFor(POI, NL);

740 }else {

741// Or the current block is part of a subloop, in which case its parent

742// is unchanged.

743assert((FoundIB || Unloop.contains(L)) &&"uninitialized successor");

744 }

745 }

746 }

747// Each irreducible loop within the unloop induces a round of iteration using

748// the DFS result cached by Traversal.

749bool Changed = FoundIB;

750for (unsigned NIters = 0; Changed; ++NIters) {

751assert(NIters < Unloop.getNumBlocks() &&"runaway iterative algorithm");

752 (void)NIters;

753

754// Iterate over the postorder list of blocks, propagating the nearest loop

755// from successors to predecessors as before.

756 Changed =false;

757for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),

758 POE = DFS.endPostorder();

759 POI != POE; ++POI) {

760

761Loop *L = LI->getLoopFor(*POI);

762Loop *NL = getNearestLoop(*POI, L);

763if (NL != L) {

764assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&

765"uninitialized successor");

766 LI->changeLoopFor(*POI, NL);

767 Changed =true;

768 }

769 }

770 }

771}

772

773/// Remove unloop's blocks from all ancestors below their new parents.

774void UnloopUpdater::removeBlocksFromAncestors() {

775// Remove all unloop's blocks (including those in nested subloops) from

776// ancestors below the new parent loop.

777for (BasicBlock *BB : Unloop.blocks()) {

778Loop *OuterParent = LI->getLoopFor(BB);

779if (Unloop.contains(OuterParent)) {

780while (OuterParent->getParentLoop() != &Unloop)

781 OuterParent = OuterParent->getParentLoop();

782 OuterParent = SubloopParents[OuterParent];

783 }

784// Remove blocks from former Ancestors except Unloop itself which will be

785// deleted.

786for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;

787 OldParent = OldParent->getParentLoop()) {

788assert(OldParent &&"new loop is not an ancestor of the original");

789 OldParent->removeBlockFromLoop(BB);

790 }

791 }

792}

793

794/// Update the parent loop for all subloops directly nested within unloop.

795void UnloopUpdater::updateSubloopParents() {

796while (!Unloop.isInnermost()) {

797Loop *Subloop = *std::prev(Unloop.end());

798 Unloop.removeChildLoop(std::prev(Unloop.end()));

799

800assert(SubloopParents.count(Subloop) &&"DFS failed to visit subloop");

801if (Loop *Parent = SubloopParents[Subloop])

802 Parent->addChildLoop(Subloop);

803else

804 LI->addTopLevelLoop(Subloop);

805 }

806}

807

808/// Return the nearest parent loop among this block's successors. If a successor

809/// is a subloop header, consider its parent to be the nearest parent of the

810/// subloop's exits.

811///

812/// For subloop blocks, simply update SubloopParents and return NULL.

813Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB,Loop *BBLoop) {

814

815// Initially for blocks directly contained by Unloop, NearLoop == Unloop and

816// is considered uninitialized.

817Loop *NearLoop = BBLoop;

818

819Loop *Subloop =nullptr;

820if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {

821 Subloop = NearLoop;

822// Find the subloop ancestor that is directly contained within Unloop.

823while (Subloop->getParentLoop() != &Unloop) {

824 Subloop = Subloop->getParentLoop();

825assert(Subloop &&"subloop is not an ancestor of the original loop");

826 }

827// Get the current nearest parent of the Subloop exits, initially Unloop.

828 NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;

829 }

830

831if (succ_empty(BB)) {

832assert(!Subloop &&"subloop blocks must have a successor");

833 NearLoop =nullptr;// unloop blocks may now exit the function.

834 }

835for (BasicBlock *Succ :successors(BB)) {

836if (Succ == BB)

837continue;// self loops are uninteresting

838

839Loop *L = LI->getLoopFor(Succ);

840if (L == &Unloop) {

841// This successor has not been processed. This path must lead to an

842// irreducible backedge.

843assert((FoundIB || !DFS.hasPostorder(Succ)) &&"should have seen IB");

844 FoundIB =true;

845 }

846if (L != &Unloop && Unloop.contains(L)) {

847// Successor is in a subloop.

848if (Subloop)

849continue;// Branching within subloops. Ignore it.

850

851// BB branches from the original into a subloop header.

852assert(L->getParentLoop() == &Unloop &&"cannot skip into nested loops");

853

854// Get the current nearest parent of the Subloop's exits.

855L = SubloopParents[L];

856// L could be Unloop if the only exit was an irreducible backedge.

857 }

858if (L == &Unloop) {

859continue;

860 }

861// Handle critical edges from Unloop into a sibling loop.

862if (L && !L->contains(&Unloop)) {

863L =L->getParentLoop();

864 }

865// Remember the nearest parent loop among successors or subloop exits.

866if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))

867 NearLoop =L;

868 }

869if (Subloop) {

870 SubloopParents[Subloop] = NearLoop;

871return BBLoop;

872 }

873return NearLoop;

874}

875

876LoopInfo::LoopInfo(constDomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }

877

878boolLoopInfo::invalidate(Function &F,constPreservedAnalyses &PA,

879FunctionAnalysisManager::Invalidator &) {

880// Check whether the analysis, all analyses on functions, or the function's

881// CFG have been preserved.

882auto PAC = PA.getChecker<LoopAnalysis>();

883return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||

884 PAC.preservedSet<CFGAnalyses>());

885}

886

887voidLoopInfo::erase(Loop *Unloop) {

888assert(!Unloop->isInvalid() &&"Loop has already been erased!");

889

890auto InvalidateOnExit =make_scope_exit([&]() { destroy(Unloop); });

891

892// First handle the special case of no parent loop to simplify the algorithm.

893if (Unloop->isOutermost()) {

894// Since BBLoop had no parent, Unloop blocks are no longer in a loop.

895for (BasicBlock *BB : Unloop->blocks()) {

896// Don't reparent blocks in subloops.

897if (getLoopFor(BB) != Unloop)

898continue;

899

900// Blocks no longer have a parent but are still referenced by Unloop until

901// the Unloop object is deleted.

902 changeLoopFor(BB,nullptr);

903 }

904

905// Remove the loop from the top-level LoopInfo object.

906for (iterator I =begin();; ++I) {

907assert(I !=end() &&"Couldn't find loop");

908if (*I == Unloop) {

909 removeLoop(I);

910break;

911 }

912 }

913

914// Move all of the subloops to the top-level.

915while (!Unloop->isInnermost())

916 addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));

917

918return;

919 }

920

921// Update the parent loop for all blocks within the loop. Blocks within

922// subloops will not change parents.

923 UnloopUpdater Updater(Unloop,this);

924 Updater.updateBlockParents();

925

926// Remove blocks from former ancestor loops.

927 Updater.removeBlocksFromAncestors();

928

929// Add direct subloops as children in their new parent loop.

930 Updater.updateSubloopParents();

931

932// Remove unloop from its parent loop.

933Loop *ParentLoop = Unloop->getParentLoop();

934for (Loop::iterator I = ParentLoop->begin();; ++I) {

935assert(I != ParentLoop->end() &&"Couldn't find loop");

936if (*I == Unloop) {

937 ParentLoop->removeChildLoop(I);

938break;

939 }

940 }

941}

942

943boolLoopInfo::wouldBeOutOfLoopUseRequiringLCSSA(

944constValue *V,constBasicBlock *ExitBB) const{

945if (V->getType()->isTokenTy())

946// We can't form PHIs of token type, so the definition of LCSSA excludes

947// values of that type.

948returnfalse;

949

950constInstruction *I = dyn_cast<Instruction>(V);

951if (!I)

952returnfalse;

953constLoop *L = getLoopFor(I->getParent());

954if (!L)

955returnfalse;

956if (L->contains(ExitBB))

957// Could be an exit bb of a subloop and contained in defining loop

958returnfalse;

959

960// We found a (new) out-of-loop use location, for a value defined in-loop.

961// (Note that because of LCSSA, we don't have to account for values defined

962// in sibling loops. Such values will have LCSSA phis of their own in the

963// common parent loop.)

964returntrue;

965}

966

967AnalysisKey LoopAnalysis::Key;

968

969LoopInfo LoopAnalysis::run(Function &F,FunctionAnalysisManager &AM) {

970// FIXME: Currently we create a LoopInfo from scratch for every function.

971// This may prove to be too wasteful due to deallocating and re-allocating

972// memory each time for the underlying map and vector datastructures. At some

973// point it may prove worthwhile to use a freelist and recycle LoopInfo

974// objects. I don't want to add that kind of complexity until the scope of

975// the problem is better understood.

976LoopInfo LI;

977 LI.analyze(AM.getResult<DominatorTreeAnalysis>(F));

978return LI;

979}

980

981PreservedAnalyses LoopPrinterPass::run(Function &F,

982FunctionAnalysisManager &AM) {

983auto &LI = AM.getResult<LoopAnalysis>(F);

984OS <<"Loop info for function '" <<F.getName() <<"':\n";

985 LI.print(OS);

986returnPreservedAnalyses::all();

987}

988

989voidllvm::printLoop(Loop &L,raw_ostream &OS,const std::string &Banner) {

990

991if (forcePrintModuleIR()) {

992// handling -print-module-scope

993OS << Banner <<" (loop: ";

994 L.getHeader()->printAsOperand(OS,false);

995OS <<")\n";

996

997// printing whole module

998OS << *L.getHeader()->getModule();

999return;

1000 }

1001

1002if (forcePrintFuncIR()) {

1003// handling -print-loop-func-scope.

1004// -print-module-scope overrides this.

1005OS << Banner <<" (loop: ";

1006 L.getHeader()->printAsOperand(OS,false);

1007OS <<")\n";

1008

1009// printing whole function.

1010OS << *L.getHeader()->getParent();

1011return;

1012 }

1013

1014OS << Banner;

1015

1016auto *PreHeader = L.getLoopPreheader();

1017if (PreHeader) {

1018OS <<"\n; Preheader:";

1019 PreHeader->print(OS);

1020OS <<"\n; Loop:";

1021 }

1022

1023for (auto *Block : L.blocks())

1024if (Block)

1025Block->print(OS);

1026else

1027OS <<"Printing <null> block";

1028

1029SmallVector<BasicBlock *, 8> ExitBlocks;

1030 L.getExitBlocks(ExitBlocks);

1031if (!ExitBlocks.empty()) {

1032OS <<"\n; Exit blocks";

1033for (auto *Block : ExitBlocks)

1034if (Block)

1035Block->print(OS);

1036else

1037OS <<"Printing <null> block";

1038 }

1039}

1040

1041MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID,StringRef Name) {

1042// No loop metadata node, no loop properties.

1043if (!LoopID)

1044returnnullptr;

1045

1046// First operand should refer to the metadata node itself, for legacy reasons.

1047assert(LoopID->getNumOperands() > 0 &&"requires at least one operand");

1048assert(LoopID->getOperand(0) == LoopID &&"invalid loop id");

1049

1050// Iterate over the metdata node operands and look for MDString metadata.

1051for (constMDOperand &MDO :llvm::drop_begin(LoopID->operands())) {

1052MDNode *MD = dyn_cast<MDNode>(MDO);

1053if (!MD || MD->getNumOperands() < 1)

1054continue;

1055MDString *S = dyn_cast<MDString>(MD->getOperand(0));

1056if (!S)

1057continue;

1058// Return the operand node if MDString holds expected metadata.

1059if (Name == S->getString())

1060return MD;

1061 }

1062

1063// Loop property not found.

1064returnnullptr;

1065}

1066

1067MDNode *llvm::findOptionMDForLoop(constLoop *TheLoop,StringRef Name) {

1068returnfindOptionMDForLoopID(TheLoop->getLoopID(),Name);

1069}

1070

1071/// Find string metadata for loop

1072///

1073/// If it has a value (e.g. {"llvm.distribute", 1} return the value as an

1074/// operand or null otherwise. If the string metadata is not found return

1075/// Optional's not-a-value.

1076std::optional<const MDOperand *>

1077llvm::findStringMetadataForLoop(constLoop *TheLoop,StringRef Name) {

1078MDNode *MD =findOptionMDForLoop(TheLoop,Name);

1079if (!MD)

1080return std::nullopt;

1081switch (MD->getNumOperands()) {

1082case 1:

1083returnnullptr;

1084case 2:

1085return &MD->getOperand(1);

1086default:

1087llvm_unreachable("loop metadata has 0 or 1 operand");

1088 }

1089}

1090

1091std::optional<bool>llvm::getOptionalBoolLoopAttribute(constLoop *TheLoop,

1092StringRef Name) {

1093MDNode *MD =findOptionMDForLoop(TheLoop,Name);

1094if (!MD)

1095return std::nullopt;

1096switch (MD->getNumOperands()) {

1097case 1:

1098// When the value is absent it is interpreted as 'attribute set'.

1099returntrue;

1100case 2:

1101if (ConstantInt *IntMD =

1102 mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))

1103return IntMD->getZExtValue();

1104returntrue;

1105 }

1106llvm_unreachable("unexpected number of options");

1107}

1108

1109boolllvm::getBooleanLoopAttribute(constLoop *TheLoop,StringRef Name) {

1110returngetOptionalBoolLoopAttribute(TheLoop,Name).value_or(false);

1111}

1112

1113std::optional<int>llvm::getOptionalIntLoopAttribute(constLoop *TheLoop,

1114StringRef Name) {

1115constMDOperand *AttrMD =

1116findStringMetadataForLoop(TheLoop,Name).value_or(nullptr);

1117if (!AttrMD)

1118return std::nullopt;

1119

1120ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());

1121if (!IntMD)

1122return std::nullopt;

1123

1124return IntMD->getSExtValue();

1125}

1126

1127intllvm::getIntLoopAttribute(constLoop *TheLoop,StringRef Name,

1128intDefault) {

1129returngetOptionalIntLoopAttribute(TheLoop,Name).value_or(Default);

1130}

1131

1132CallBase *llvm::getLoopConvergenceHeart(constLoop *TheLoop) {

1133BasicBlock *H = TheLoop->getHeader();

1134for (Instruction &II : *H) {

1135if (auto *CB = dyn_cast<CallBase>(&II)) {

1136if (!CB->isConvergent())

1137continue;

1138// This is the heart if it uses a token defined outside the loop. The

1139// verifier has already checked that only the loop intrinsic can use such

1140// a token.

1141if (auto *Token = CB->getConvergenceControlToken()) {

1142auto *TokenDef = cast<Instruction>(Token);

1143if (!TheLoop->contains(TokenDef->getParent()))

1144return CB;

1145 }

1146returnnullptr;

1147 }

1148 }

1149returnnullptr;

1150}

1151

1152boolllvm::isFinite(constLoop *L) {

1153return L->getHeader()->getParent()->willReturn();

1154}

1155

1156staticconstchar *LLVMLoopMustProgress ="llvm.loop.mustprogress";

1157

1158boolllvm::hasMustProgress(constLoop *L) {

1159returngetBooleanLoopAttribute(L,LLVMLoopMustProgress);

1160}

1161

1162boolllvm::isMustProgress(constLoop *L) {

1163return L->getHeader()->getParent()->mustProgress() ||hasMustProgress(L);

1164}

1165

1166boolllvm::isValidAsAccessGroup(MDNode *Node) {

1167return Node->getNumOperands() == 0 && Node->isDistinct();

1168}

1169

1170MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context,

1171MDNode *OrigLoopID,

1172ArrayRef<StringRef> RemovePrefixes,

1173ArrayRef<MDNode *> AddAttrs) {

1174// First remove any existing loop metadata related to this transformation.

1175SmallVector<Metadata *, 4> MDs;

1176

1177// Reserve first location for self reference to the LoopID metadata node.

1178 MDs.push_back(nullptr);

1179

1180// Remove metadata for the transformation that has been applied or that became

1181// outdated.

1182if (OrigLoopID) {

1183for (constMDOperand &MDO :llvm::drop_begin(OrigLoopID->operands())) {

1184bool IsVectorMetadata =false;

1185Metadata *Op = MDO;

1186if (MDNode *MD = dyn_cast<MDNode>(Op)) {

1187constMDString *S = dyn_cast<MDString>(MD->getOperand(0));

1188if (S)

1189 IsVectorMetadata =

1190llvm::any_of(RemovePrefixes, [S](StringRef Prefix) ->bool {

1191return S->getString().starts_with(Prefix);

1192 });

1193 }

1194if (!IsVectorMetadata)

1195 MDs.push_back(Op);

1196 }

1197 }

1198

1199// Add metadata to avoid reapplying a transformation, such as

1200// llvm.loop.unroll.disable and llvm.loop.isvectorized.

1201 MDs.append(AddAttrs.begin(), AddAttrs.end());

1202

1203MDNode *NewLoopID =MDNode::getDistinct(Context, MDs);

1204// Replace the temporary node with a self-reference.

1205 NewLoopID->replaceOperandWith(0, NewLoopID);

1206return NewLoopID;

1207}

1208

1209//===----------------------------------------------------------------------===//

1210// LoopInfo implementation

1211//

1212

1213LoopInfoWrapperPass::LoopInfoWrapperPass() :FunctionPass(ID) {

1214initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());

1215}

1216

1217charLoopInfoWrapperPass::ID = 0;

1218INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass,"loops","Natural Loop Information",

1219true,true)

1220INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)

1221INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "NaturalLoop Information",

1222true,true)

1223

1224boolLoopInfoWrapperPass::runOnFunction(Function &) {

1225 releaseMemory();

1226 LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());

1227returnfalse;

1228}

1229

1230voidLoopInfoWrapperPass::verifyAnalysis() const{

1231// LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the

1232// function each time verifyAnalysis is called is very expensive. The

1233// -verify-loop-info option can enable this. In order to perform some

1234// checking by default, LoopPass has been taught to call verifyLoop manually

1235// during loop pass sequences.

1236if (VerifyLoopInfo) {

1237auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();

1238 LI.verify(DT);

1239 }

1240}

1241

1242voidLoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const{

1243 AU.setPreservesAll();

1244 AU.addRequiredTransitive<DominatorTreeWrapperPass>();

1245}

1246

1247voidLoopInfoWrapperPass::print(raw_ostream &OS,constModule *) const{

1248 LI.print(OS);

1249}

1250

1251PreservedAnalyses LoopVerifierPass::run(Function &F,

1252FunctionAnalysisManager &AM) {

1253LoopInfo &LI = AM.getResult<LoopAnalysis>(F);

1254auto &DT = AM.getResult<DominatorTreeAnalysis>(F);

1255 LI.verify(DT);

1256returnPreservedAnalyses::all();

1257}

1258

1259//===----------------------------------------------------------------------===//

1260// LoopBlocksDFS implementation

1261//

1262

1263/// Traverse the loop blocks and store the DFS result.

1264/// Useful for clients that just want the final DFS result and don't need to

1265/// visit blocks during the initial traversal.

1266voidLoopBlocksDFS::perform(constLoopInfo *LI) {

1267LoopBlocksTraversal Traversal(*this, LI);

1268for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),

1269 POE = Traversal.end();

1270 POI != POE; ++POI)

1271 ;

1272}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Definition:ARMSLSHardening.cpp:73

true

basic Basic Alias true

Definition:BasicAliasAnalysis.cpp:1981

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

CommandLine.h

LLVM_DUMP_METHOD

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

Definition:Compiler.h:622

Constants.h

This file contains the declarations for the subclasses of Constant, which represent the different fla...

DebugLoc.h

Dominators.h

Name

std::string Name

Definition:ELFObjHandler.cpp:77

runOnFunction

static bool runOnFunction(Function &F, bool PostInlining)

Definition:EntryExitInstrumenter.cpp:98

GenericLoopInfoImpl.h

CFG.h

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

Module.h

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

PassManager.h

This header defines various interfaces for pass management in LLVM.

static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB, const DominatorTree &DT, bool IgnoreTokens)

Definition:LoopInfo.cpp:432

loops

Definition:LoopInfo.cpp:1221

LLVMLoopMustProgress

static const char * LLVMLoopMustProgress

Definition:LoopInfo.cpp:1156

findFinalIVValue

static Value * findFinalIVValue(const Loop &L, const PHINode &IndVar, const Instruction &StepInst)

Return the final value of the loop induction variable if found.

Definition:LoopInfo.cpp:185

Information

Natural Loop Information

Definition:LoopInfo.cpp:1221

VerifyLoopInfoX

static cl::opt< bool, true > VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), cl::Hidden, cl::desc("Verify loop info (time consuming)"))

LoopInfo.h

LoopIterator.h

LoopNestAnalysis.h

This file defines the interface for the loop nest analysis.

#define F(x, y, z)

Definition:MD5.cpp:55

#define I(x, y, z)

Definition:MD5.cpp:58

#define H(x, y, z)

Definition:MD5.cpp:57

MemorySSAUpdater.h

MemorySSA.h

This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...

Metadata.h

This file contains the declarations for metadata subclasses.

uint64_t IntrinsicInst * II

Definition:NVVMIntrRange.cpp:51

#define P(N)

INITIALIZE_PASS_DEPENDENCY

#define INITIALIZE_PASS_DEPENDENCY(depName)

Definition:PassSupport.h:55

INITIALIZE_PASS_END

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

Definition:PassSupport.h:57

INITIALIZE_PASS_BEGIN

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

Definition:PassSupport.h:52

PrintPasses.h

assert

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

raw_pwrite_stream & OS

Definition:SampleProfWriter.cpp:51

ScalarEvolutionExpressions.h

ScopeExit.h

This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...

SmallPtrSet.h

This file defines the SmallPtrSet class.

starts_with

DEMANGLE_NAMESPACE_BEGIN bool starts_with(std::string_view self, char C) noexcept

Definition:StringViewExtras.h:24

ValueTracking.h

llvm::AllAnalysesOn

This templated class represents "all analyses that operate over <a particular IR unit>" (e....

Definition:Analysis.h:49

llvm::AnalysisManager::Invalidator

API to communicate dependencies between analyses during invalidation.

Definition:PassManager.h:292

llvm::AnalysisManager

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

Definition:PassManager.h:253

llvm::AnalysisManager::getResult

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

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

Definition:PassManager.h:410

llvm::AnalysisUsage

Represent the analysis usage information of a pass.

Definition:PassAnalysisSupport.h:47

llvm::AnalysisUsage::setPreservesAll

void setPreservesAll()

Set by analyses that do not transform their input at all.

Definition:PassAnalysisSupport.h:130

llvm::AnalysisUsage::addRequiredTransitive

AnalysisUsage & addRequiredTransitive()

Definition:PassAnalysisSupport.h:81

llvm::ArrayRef

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Definition:ArrayRef.h:41

llvm::ArrayRef::end

iterator end() const

Definition:ArrayRef.h:157

llvm::ArrayRef::begin

iterator begin() const

Definition:ArrayRef.h:156

llvm::BasicBlock

LLVM Basic Block Representation.

Definition:BasicBlock.h:61

llvm::BasicBlock::getUniquePredecessor

const BasicBlock * getUniquePredecessor() const

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

Definition:BasicBlock.cpp:479

llvm::BasicBlock::getParent

const Function * getParent() const

Return the enclosing method, or null if none.

Definition:BasicBlock.h:220

llvm::BasicBlock::iterator

InstListType::iterator iterator

Instruction iterators...

Definition:BasicBlock.h:177

llvm::BasicBlock::getContext

LLVMContext & getContext() const

Get the context in which this basic block lives.

Definition:BasicBlock.cpp:168

llvm::BasicBlock::getTerminator

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

Definition:BasicBlock.h:240

llvm::BranchInst

Conditional or Unconditional Branch instruction.

Definition:Instructions.h:3016

llvm::BranchInst::isConditional

bool isConditional() const

Definition:Instructions.h:3090

llvm::BranchInst::getSuccessor

BasicBlock * getSuccessor(unsigned i) const

Definition:Instructions.h:3104

llvm::BranchInst::isUnconditional

bool isUnconditional() const

Definition:Instructions.h:3089

llvm::BranchInst::getCondition

Value * getCondition() const

Definition:Instructions.h:3092

llvm::CFGAnalyses

Represents analyses that only rely on functions' control flow.

Definition:Analysis.h:72

llvm::CallBase

Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...

Definition:InstrTypes.h:1112

llvm::CmpInst

This class is the base class for the comparison instructions.

Definition:InstrTypes.h:661

llvm::CmpInst::Predicate

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

Definition:InstrTypes.h:673

llvm::CmpInst::BAD_ICMP_PREDICATE

@ BAD_ICMP_PREDICATE

Definition:InstrTypes.h:706

llvm::CmpInst::ICMP_SLT

@ ICMP_SLT

signed less than

Definition:InstrTypes.h:702

llvm::CmpInst::ICMP_SGT

@ ICMP_SGT

signed greater than

Definition:InstrTypes.h:700

llvm::CmpInst::ICMP_EQ

@ ICMP_EQ

equal

Definition:InstrTypes.h:694

llvm::CmpInst::ICMP_NE

@ ICMP_NE

not equal

Definition:InstrTypes.h:695

llvm::CmpInst::getSwappedPredicate

Predicate getSwappedPredicate() const

For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.

Definition:InstrTypes.h:825

llvm::CmpInst::getInversePredicate

Predicate getInversePredicate() const

For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...

Definition:InstrTypes.h:787

llvm::CmpInst::getPredicate

Predicate getPredicate() const

Return the predicate for this instruction.

Definition:InstrTypes.h:763

llvm::CmpInst::getFlippedStrictnessPredicate

Predicate getFlippedStrictnessPredicate() const

For predicate of kind "is X or equal to 0" returns the predicate "is X".

Definition:InstrTypes.h:891

llvm::ConstantInt

This is the shared class of boolean and integer constants.

Definition:Constants.h:83

llvm::ConstantInt::isOne

bool isOne() const

This is just a convenience method to make client code smaller for a common case.

Definition:Constants.h:214

llvm::ConstantInt::getSExtValue

int64_t getSExtValue() const

Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...

Definition:Constants.h:163

llvm::DILocation

Debug location.

Definition:DebugInfoMetadata.h:1988

llvm::DWARFExpression::Operation

This class represents an Operation in the Expression.

Definition:DWARFExpression.h:32

llvm::DebugLoc

A debug info location.

Definition:DebugLoc.h:33

llvm::DenseMap

Definition:DenseMap.h:727

llvm::DominatorTreeAnalysis

Analysis pass which computes a DominatorTree.

Definition:Dominators.h:279

llvm::DominatorTreeBase

Core dominator tree base class.

Definition:GenericDomTree.h:237

llvm::DominatorTreeWrapperPass

Legacy analysis pass which computes a DominatorTree.

Definition:Dominators.h:317

llvm::DominatorTree

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

Definition:Dominators.h:162

llvm::DominatorTree::isReachableFromEntry

bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

Definition:Dominators.cpp:321

llvm::FunctionPass

FunctionPass class - This class is used to implement most global optimizations.

Definition:Pass.h:310

llvm::Function

Definition:Function.h:63

llvm::GlobalValue::getParent

Module * getParent()

Get the module that this global value is contained inside of...

Definition:GlobalValue.h:657

llvm::ICmpInst

This instruction compares its operands according to the predicate given to the constructor.

Definition:Instructions.h:1158

llvm::InductionDescriptor

A struct for saving information about induction variables.

Definition:IVDescriptors.h:334

llvm::InductionDescriptor::getInductionBinOp

BinaryOperator * getInductionBinOp() const

Definition:IVDescriptors.h:351

llvm::InductionDescriptor::getStep

const SCEV * getStep() const

Definition:IVDescriptors.h:350

llvm::InductionDescriptor::isInductionPHI

static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)

Returns true if Phi is an induction in the loop L.

Definition:IVDescriptors.cpp:1513

llvm::InductionDescriptor::getInductionOpcode

Instruction::BinaryOps getInductionOpcode() const

Returns binary opcode of the induction operator.

Definition:IVDescriptors.h:395

llvm::InductionDescriptor::getStartValue

Value * getStartValue() const

Definition:IVDescriptors.h:348

llvm::InductionDescriptor::getConstIntStepValue

ConstantInt * getConstIntStepValue() const

Definition:IVDescriptors.cpp:1305

llvm::Init

Definition:Record.h:285

llvm::Instruction

Definition:Instruction.h:68

llvm::Instruction::getMetadata

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

Definition:Instruction.h:407

llvm::LLVMContext

This is an important class for using LLVM in a threaded context.

Definition:LLVMContext.h:67

llvm::LoopAnalysis

Analysis pass that exposes the LoopInfo for a function.

Definition:LoopInfo.h:566

llvm::LoopAnalysis::run

LoopInfo run(Function &F, FunctionAnalysisManager &AM)

Definition:LoopInfo.cpp:969

llvm::LoopBase

Instances of this class are used to represent loops that are detected in the flow graph.

Definition:GenericLoopInfo.h:59

llvm::LoopBase< BasicBlock, Loop >::contains

bool contains(const Loop *L) const

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

Definition:GenericLoopInfo.h:124

llvm::LoopBase::isOutermost

bool isOutermost() const

Return true if the loop does not have a parent (natural) loop.

Definition:GenericLoopInfo.h:170

llvm::LoopBase< BasicBlock, Loop >::getLoopLatch

BasicBlock * getLoopLatch() const

If there is a single latch block for this loop, return it.

Definition:GenericLoopInfoImpl.h:256

llvm::LoopBase::isInnermost

bool isInnermost() const

Return true if the loop does not contain any (natural) loops.

Definition:GenericLoopInfo.h:167

llvm::LoopBase< BasicBlock, Loop >::getHeader

BasicBlock * getHeader() const

Definition:GenericLoopInfo.h:90

llvm::LoopBase< BasicBlock, Loop >::getLoopLatches

void getLoopLatches(SmallVectorImpl< BasicBlock * > &LoopLatches) const

Return all loop latch blocks of this loop.

Definition:GenericLoopInfo.h:330

llvm::LoopBase< BasicBlock, Loop >::print

void print(raw_ostream &OS, bool Verbose=false, bool PrintNested=true, unsigned Depth=0) const

Print loop with all the BBs inside it.

Definition:GenericLoopInfoImpl.h:414

llvm::LoopBase< BasicBlock, Loop >::iterator

std::vector< Loop * >::const_iterator iterator

Definition:GenericLoopInfo.h:153

llvm::LoopBase< BasicBlock, Loop >::blocks

iterator_range< block_iterator > blocks() const

Definition:GenericLoopInfo.h:180

llvm::LoopBase::isInvalid

bool isInvalid() const

Return true if this loop is no longer valid.

Definition:GenericLoopInfo.h:217

llvm::LoopBase< BasicBlock, Loop >::end

iterator end() const

Definition:GenericLoopInfo.h:157

llvm::LoopBase< BasicBlock, Loop >::getLoopPreheader

BasicBlock * getLoopPreheader() const

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

Definition:GenericLoopInfoImpl.h:210

llvm::LoopBase::getParentLoop

LoopT * getParentLoop() const

Return the parent loop if it exists or nullptr for top level loops.

Definition:GenericLoopInfo.h:99

llvm::LoopBase< BasicBlock, Loop >::hasDedicatedExits

bool hasDedicatedExits() const

Return true if no exit block for the loop has a predecessor that is outside the loop.

Definition:GenericLoopInfoImpl.h:112

llvm::LoopBase< BasicBlock, Loop >::begin

iterator begin() const

Definition:GenericLoopInfo.h:156

llvm::LoopBase< BasicBlock, Loop >::getUniqueExitBlock

BasicBlock * getUniqueExitBlock() const

If getUniqueExitBlocks would return exactly one block, return that block.

Definition:GenericLoopInfoImpl.h:158

llvm::LoopBase::removeChildLoop

LoopT * removeChildLoop(iterator I)

This removes the specified child from being a subloop of this loop.

Definition:GenericLoopInfo.h:400

llvm::LoopBlocksDFS

Store the result of a depth first search within basic blocks contained by a single loop.

Definition:LoopIterator.h:97

llvm::LoopBlocksDFS::POIterator

std::vector< BasicBlock * >::const_iterator POIterator

Postorder list iterators.

Definition:LoopIterator.h:100

llvm::LoopBlocksDFS::perform

void perform(const LoopInfo *LI)

Traverse the loop blocks and store the DFS result.

Definition:LoopInfo.cpp:1266

llvm::LoopBlocksTraversal

Traverse the blocks in a loop using a depth-first search.

Definition:LoopIterator.h:200

llvm::LoopBlocksTraversal::end

POTIterator end()

Definition:LoopIterator.h:221

llvm::LoopBlocksTraversal::begin

POTIterator begin()

Postorder traversal over the graph.

Definition:LoopIterator.h:216

llvm::LoopInfoBase

This class builds and contains all of the top-level loop structures in the specified function.

Definition:GenericLoopInfo.h:526

llvm::LoopInfoBase::verify

void verify(const DominatorTreeBase< BlockT, false > &DomTree) const

Definition:GenericLoopInfoImpl.h:718

llvm::LoopInfoBase::analyze

void analyze(const DominatorTreeBase< BlockT, false > &DomTree)

Create the loop forest using a stable algorithm.

Definition:GenericLoopInfoImpl.h:577

llvm::LoopInfoBase::print

void print(raw_ostream &OS) const

Definition:GenericLoopInfoImpl.h:649

llvm::LoopInfoBase::getLoopFor

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Definition:GenericLoopInfo.h:606

llvm::LoopInfoBase< BasicBlock, Loop >::iterator

std::vector< Loop * >::const_iterator iterator

iterator/begin/end - The interface to the top-level loops in the current function.

Definition:GenericLoopInfo.h:578

llvm::LoopInfoWrapperPass

The legacy pass manager's analysis pass to compute loop information.

Definition:LoopInfo.h:593

llvm::LoopInfoWrapperPass::getAnalysisUsage

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

Definition:LoopInfo.cpp:1242

llvm::LoopInfoWrapperPass::LoopInfoWrapperPass

LoopInfoWrapperPass()

Definition:LoopInfo.cpp:1213

llvm::LoopInfoWrapperPass::ID

static char ID

Definition:LoopInfo.h:597

llvm::LoopInfoWrapperPass::verifyAnalysis

void verifyAnalysis() const override

verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...

Definition:LoopInfo.cpp:1230

llvm::LoopInfoWrapperPass::print

void print(raw_ostream &O, const Module *M=nullptr) const override

print - Print out the internal state of the pass.

Definition:LoopInfo.cpp:1247

llvm::LoopInfo

Definition:LoopInfo.h:407

llvm::LoopInfo::LoopInfo

LoopInfo()=default

llvm::LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA

bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V, const BasicBlock *ExitBB) const

Definition:LoopInfo.cpp:943

llvm::LoopInfo::invalidate

bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)

Handle invalidation explicitly.

Definition:LoopInfo.cpp:878

llvm::LoopInfo::erase

void erase(Loop *L)

Update LoopInfo after removing the last backedge from a loop.

Definition:LoopInfo.cpp:887

llvm::LoopNest::skipEmptyBlockUntil

static const BasicBlock & skipEmptyBlockUntil(const BasicBlock *From, const BasicBlock *End, bool CheckUniquePred=false)

Recursivelly traverse all empty 'single successor' basic blocks of From (if there are any).

Definition:LoopNestAnalysis.cpp:288

llvm::LoopPrinterPass::run

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition:LoopInfo.cpp:981

llvm::Loop::LocRange

A range representing the start and end location of a loop.

Definition:LoopInfo.h:42

llvm::Loop::LocRange::getStart

const DebugLoc & getStart() const

Definition:LoopInfo.h:52

llvm::Loop

Represents a single loop in the control flow graph.

Definition:LoopInfo.h:39

llvm::Loop::isCanonical

bool isCanonical(ScalarEvolution &SE) const

Return true if the loop induction variable starts at zero and increments by one each time through the...

Definition:LoopInfo.cpp:412

llvm::Loop::isLCSSAForm

bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens=true) const

Return true if the Loop is in LCSSA form.

Definition:LoopInfo.cpp:463

llvm::Loop::getBounds

std::optional< LoopBounds > getBounds(ScalarEvolution &SE) const

Return the struct LoopBounds collected if all struct members are found, else std::nullopt.

Definition:LoopInfo.cpp:288

llvm::Loop::isSafeToClone

bool isSafeToClone() const

Return true if the loop body is safe to clone in practice.

Definition:LoopInfo.cpp:487

llvm::Loop::getLocStr

std::string getLocStr() const

Return a string containing the debug location of the loop (file name + line number if present,...

Definition:LoopInfo.cpp:667

llvm::Loop::dumpVerbose

void dumpVerbose() const

Definition:LoopInfo.cpp:681

llvm::Loop::hasLoopInvariantOperands

bool hasLoopInvariantOperands(const Instruction *I) const

Return true if all the operands of the specified instruction are loop invariant.

Definition:LoopInfo.cpp:67

llvm::Loop::getLoopGuardBranch

BranchInst * getLoopGuardBranch() const

Return the loop guard branch, if it exists.

Definition:LoopInfo.cpp:368

llvm::Loop::isAnnotatedParallel

bool isAnnotatedParallel() const

Returns true if the loop is annotated parallel.

Definition:LoopInfo.cpp:565

llvm::Loop::getStartLoc

DebugLoc getStartLoc() const

Return the debug location of the start of this loop.

Definition:LoopInfo.cpp:632

llvm::Loop::dump

void dump() const

Definition:LoopInfo.cpp:679

llvm::Loop::getLocRange

LocRange getLocRange() const

Return the source code span of the loop.

Definition:LoopInfo.cpp:634

llvm::Loop::isLoopInvariant

bool isLoopInvariant(const Value *V) const

Return true if the specified value is loop invariant.

Definition:LoopInfo.cpp:61

llvm::Loop::getLatchCmpInst

ICmpInst * getLatchCmpInst() const

Get the latch condition instruction.

Definition:LoopInfo.cpp:175

llvm::Loop::getInductionDescriptor

bool getInductionDescriptor(ScalarEvolution &SE, InductionDescriptor &IndDesc) const

Get the loop induction descriptor for the loop induction variable.

Definition:LoopInfo.cpp:334

llvm::Loop::isRotatedForm

bool isRotatedForm() const

Return true if the loop is in rotated form.

Definition:LoopInfo.h:302

llvm::Loop::setLoopMustProgress

void setLoopMustProgress()

Add llvm.loop.mustprogress to this loop's loop id metadata.

Definition:LoopInfo.cpp:549

llvm::Loop::getInductionVariable

PHINode * getInductionVariable(ScalarEvolution &SE) const

Return the loop induction variable if found, else return nullptr.

Definition:LoopInfo.cpp:295

llvm::Loop::isLoopSimplifyForm

bool isLoopSimplifyForm() const

Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...

Definition:LoopInfo.cpp:480

llvm::Loop::isRecursivelyLCSSAForm

bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI, bool IgnoreTokens=true) const

Return true if this Loop and all inner subloops are in LCSSA form.

Definition:LoopInfo.cpp:470

llvm::Loop::setLoopID

void setLoopID(MDNode *LoopID) const

Set the llvm.loop loop id metadata for this loop.

Definition:LoopInfo.cpp:526

llvm::Loop::setLoopAlreadyUnrolled

void setLoopAlreadyUnrolled()

Add llvm.loop.unroll.disable to this loop's loop id metadata.

Definition:LoopInfo.cpp:538

llvm::Loop::makeLoopInvariant

bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=nullptr, MemorySSAUpdater *MSSAU=nullptr, ScalarEvolution *SE=nullptr) const

If the given value is an instruction inside of the loop and it can be hoisted, do so to make it trivi...

Definition:LoopInfo.cpp:71

llvm::Loop::getCanonicalInductionVariable

PHINode * getCanonicalInductionVariable() const

Check to see if the loop has a canonical induction variable: an integer recurrence that starts at 0 a...

Definition:LoopInfo.cpp:151

llvm::Loop::getIncomingAndBackEdge

bool getIncomingAndBackEdge(BasicBlock *&Incoming, BasicBlock *&Backedge) const

Obtain the unique incoming and back edge.

Definition:LoopInfo.cpp:125

llvm::Loop::getLoopID

MDNode * getLoopID() const

Return the llvm.loop loop id metadata node for this loop if it is present.

Definition:LoopInfo.cpp:502

llvm::Loop::isAuxiliaryInductionVariable

bool isAuxiliaryInductionVariable(PHINode &AuxIndVar, ScalarEvolution &SE) const

Return true if the given PHINode AuxIndVar is.

Definition:LoopInfo.cpp:342

llvm::MDNode

Metadata node.

Definition:Metadata.h:1073

llvm::MDNode::replaceOperandWith

void replaceOperandWith(unsigned I, Metadata *New)

Replace a specific operand.

Definition:Metadata.cpp:1077

llvm::MDNode::getDistinct

static MDTuple * getDistinct(LLVMContext &Context, ArrayRef< Metadata * > MDs)

Definition:Metadata.h:1557

llvm::MDNode::getOperand

const MDOperand & getOperand(unsigned I) const

Definition:Metadata.h:1434

llvm::MDNode::operands

ArrayRef< MDOperand > operands() const

Definition:Metadata.h:1432

llvm::MDNode::get

static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)

Definition:Metadata.h:1549

llvm::MDNode::getNumOperands

unsigned getNumOperands() const

Return number of MDNode operands.

Definition:Metadata.h:1440

llvm::MDOperand

Tracking metadata reference owned by Metadata.

Definition:Metadata.h:895

llvm::MDOperand::get

Metadata * get() const

Definition:Metadata.h:924

llvm::MDString

A single uniqued string.

Definition:Metadata.h:724

llvm::MDString::getString

StringRef getString() const

Definition:Metadata.cpp:616

llvm::MDString::get

static MDString * get(LLVMContext &Context, StringRef Str)

Definition:Metadata.cpp:606

llvm::MemorySSAUpdater

Definition:MemorySSAUpdater.h:54

llvm::MemorySSAUpdater::getMemorySSA

MemorySSA * getMemorySSA() const

Get handle on MemorySSA.

Definition:MemorySSAUpdater.h:240

llvm::MemorySSAUpdater::moveToPlace

void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)

Definition:MemorySSAUpdater.cpp:1185

llvm::MemorySSA::BeforeTerminator

@ BeforeTerminator

Definition:MemorySSA.h:790

llvm::MemorySSA::getMemoryAccess

MemoryUseOrDef * getMemoryAccess(const Instruction *I) const

Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.

Definition:MemorySSA.h:719

llvm::Metadata

Root of the metadata hierarchy.

Definition:Metadata.h:62

llvm::Module

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

Definition:Module.h:65

llvm::Module::getModuleIdentifier

const std::string & getModuleIdentifier() const

Get the module identifier which is, essentially, the name of the module.

Definition:Module.h:268

llvm::PHINode

Definition:Instructions.h:2600

llvm::PHINode::getIncomingValueForBlock

Value * getIncomingValueForBlock(const BasicBlock *BB) const

Definition:Instructions.h:2775

llvm::PassRegistry::getPassRegistry

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

Definition:PassRegistry.cpp:24

llvm::PredIterator

Definition:CFG.h:42

llvm::PreservedAnalyses

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

Definition:Analysis.h:111

llvm::PreservedAnalyses::all

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Definition:Analysis.h:117

llvm::PreservedAnalyses::getChecker

PreservedAnalysisChecker getChecker() const

Build a checker for this PreservedAnalyses and the specified analysis type.

Definition:Analysis.h:264

llvm::SCEVAddRecExpr

This node represents a polynomial recurrence on the trip count of the specified loop.

Definition:ScalarEvolutionExpressions.h:347

llvm::SCEV

This class represents an analyzed expression in the program.

Definition:ScalarEvolution.h:71

llvm::ScalarEvolution

The main scalar evolution driver.

Definition:ScalarEvolution.h:447

llvm::ScalarEvolution::getSCEV

const SCEV * getSCEV(Value *V)

Return a SCEV expression for the full generality of the specified expression.

Definition:ScalarEvolution.cpp:4547

llvm::ScalarEvolution::isLoopInvariant

bool isLoopInvariant(const SCEV *S, const Loop *L)

Return true if the value of the given SCEV is unchanging in the specified loop.

Definition:ScalarEvolution.cpp:14100

llvm::ScalarEvolution::forgetBlockAndLoopDispositions

void forgetBlockAndLoopDispositions(Value *V=nullptr)

Called when the client has changed the disposition of values in a loop or block.

Definition:ScalarEvolution.cpp:8597

llvm::SmallPtrSetImpl::count

size_type count(ConstPtrType Ptr) const

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

Definition:SmallPtrSet.h:452

llvm::SmallPtrSetImpl::insert

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

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

Definition:SmallPtrSet.h:384

llvm::SmallPtrSet

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

Definition:SmallPtrSet.h:519

llvm::SmallVectorBase::empty

bool empty() const

Definition:SmallVector.h:81

llvm::SmallVectorImpl::append

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

Definition:SmallVector.h:683

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition:SmallVector.h:413

llvm::SmallVector

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

Definition:SmallVector.h:1196

llvm::StringRef

StringRef - Represent a constant reference to a string, i.e.

Definition:StringRef.h:51

llvm::Use

A Use represents the edge between a Value definition and its users.

Definition:Use.h:43

llvm::User

Definition:User.h:44

llvm::User::getOperand

Value * getOperand(unsigned i) const

Definition:User.h:228

llvm::Value

LLVM Value Representation.

Definition:Value.h:74

llvm::Value::users

iterator_range< user_iterator > users()

Definition:Value.h:421

llvm::cl::opt

Definition:CommandLine.h:1423

llvm::ilist_detail::node_parent_access::getParent

const ParentTy * getParent() const

Definition:ilist_node.h:32

llvm::ilist_node_impl::getIterator

self_iterator getIterator()

Definition:ilist_node.h:132

llvm::po_iterator

Definition:PostOrderIterator.h:97

llvm::raw_ostream

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

Definition:raw_ostream.h:52

llvm::raw_string_ostream

A raw_ostream that writes to an std::string.

Definition:raw_ostream.h:661

unsigned

llvm_unreachable

#define llvm_unreachable(msg)

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

Definition:ErrorHandling.h:143

llvm::M68k::MemAddrModeKind::L

@ L

llvm::cl::Hidden

@ Hidden

Definition:CommandLine.h:137

llvm::cl::location

LocationClass< Ty > location(Ty &L)

Definition:CommandLine.h:463

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::drop_begin

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

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

Definition:STLExtras.h:329

llvm::all_of

bool all_of(R &&range, UnaryPredicate P)

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

Definition:STLExtras.h:1739

llvm::PseudoProbeType::Block

@ Block

llvm::getBooleanLoopAttribute

bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)

Returns true if Name is applied to TheLoop and enabled.

Definition:LoopInfo.cpp:1109

llvm::succ_empty

bool succ_empty(const Instruction *I)

Definition:CFG.h:255

llvm::forcePrintModuleIR

bool forcePrintModuleIR()

Definition:PrintPasses.cpp:148

llvm::initializeLoopInfoWrapperPassPass

void initializeLoopInfoWrapperPassPass(PassRegistry &)

llvm::make_scope_exit

detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)

Definition:ScopeExit.h:59

llvm::getOptionalBoolLoopAttribute

std::optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)

Definition:LoopInfo.cpp:1091

llvm::getIntLoopAttribute

int getIntLoopAttribute(const Loop *TheLoop, StringRef Name, int Default=0)

Find named metadata for a loop with an integer value.

Definition:LoopInfo.cpp:1127

llvm::pred_end

auto pred_end(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1385

llvm::findStringMetadataForLoop

std::optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)

Find string metadata for loop.

Definition:LoopInfo.cpp:1077

llvm::successors

auto successors(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1376

llvm::findOptionMDForLoop

MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)

Find string metadata for a loop.

Definition:LoopInfo.cpp:1067

llvm::hasMustProgress

bool hasMustProgress(const Loop *L)

Look for the loop attribute that requires progress within the loop.

Definition:LoopInfo.cpp:1158

llvm::any_of

bool any_of(R &&range, UnaryPredicate P)

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

Definition:STLExtras.h:1746

llvm::isMustProgress

bool isMustProgress(const Loop *L)

Return true if this loop can be assumed to make progress.

Definition:LoopInfo.cpp:1162

llvm::getLoopConvergenceHeart

CallBase * getLoopConvergenceHeart(const Loop *TheLoop)

Find the convergence heart of the loop.

Definition:LoopInfo.cpp:1132

llvm::isFinite

bool isFinite(const Loop *L)

Return true if this loop can be assumed to run for a finite number of iterations.

Definition:LoopInfo.cpp:1152

llvm::dbgs

raw_ostream & dbgs()

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

Definition:Debug.cpp:163

llvm::isSafeToSpeculativelyExecute

bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true)

Return true if the instruction does not have any effects besides calculating the result and does not ...

Definition:ValueTracking.cpp:7043

llvm::VerifyLoopInfo

bool VerifyLoopInfo

Enable verification of loop info.

Definition:LoopInfo.cpp:51

llvm::getOptionalIntLoopAttribute

std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)

Find named metadata for a loop with an integer value.

Definition:LoopInfo.cpp:1113

llvm::isValidAsAccessGroup

bool isValidAsAccessGroup(MDNode *AccGroup)

Return whether an MDNode might represent an access group.

Definition:LoopInfo.cpp:1166

llvm::pred_begin

auto pred_begin(const MachineBasicBlock *BB)

Definition:MachineBasicBlock.h:1383

llvm::makePostTransformationMetadata

llvm::MDNode * makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID, llvm::ArrayRef< llvm::StringRef > RemovePrefixes, llvm::ArrayRef< llvm::MDNode * > AddAttrs)

Create a new LoopID after the loop has been transformed.

Definition:LoopInfo.cpp:1170

llvm::is_contained

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

Definition:STLExtras.h:1903

llvm::InstructionUniformity::Default

@ Default

The result values are uniform if and only if all operands are uniform.

llvm::printLoop

void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner="")

Function to print a loop's contents as LLVM's text IR assembly.