LoopInfo.cpp Source File (original) (raw)

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

41using namespace llvm;

48#ifdef EXPENSIVE_CHECKS

50#else

52#endif

62 if (const Instruction *I = dyn_cast(V))

64 return true;

65}

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

69}

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

76 return true;

77}

84 return true;

86 return false;

87 if (I->mayReadFromMemory())

88 return false;

90 if (I->isEHPad())

91 return false;

93 if (!InsertPt) {

96 if (!Preheader)

97 return false;

99 }

100

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

103 return false;

104

105

106 I->moveBefore(InsertPt);

107 if (MSSAU)

111

112

113

114

115

116 I->dropUnknownNonDebugMetadata();

117

118 if (SE)

120

121 Changed = true;

122 return true;

123}

124

128

130 Backedge = nullptr;

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

133 Backedge = *PI++;

135 return false;

138 return false;

139

142 return false;

144 } else if ( contains (Backedge))

145 return false;

146

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

148 return true;

149}

150

153

156 return nullptr;

157

158

160 PHINode *PN = cast(I);

163 if (CI->isZero())

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

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

168 if (CI->isOne())

169 return PN;

170 }

171 return nullptr;

172}

173

174

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

178 if (BI->isConditional())

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

180

181 return nullptr;

182}

183

184

187 ICmpInst *LatchCmpInst = L.getLatchCmpInst();

188 if (!LatchCmpInst)

189 return nullptr;

190

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

194 return Op1;

195

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

197 return Op0;

198

199 return nullptr;

200}

201

202std::optionalLoop::LoopBounds

207 return std::nullopt;

208

211 if (!InitialIVValue || !StepInst)

212 return std::nullopt;

213

217 Value *StepValue = nullptr;

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

219 StepValue = StepInstOp1;

220 else if (SE.getSCEV(StepInstOp0) == Step)

221 StepValue = StepInstOp0;

222

224 if (!FinalIVValue)

225 return std::nullopt;

226

227 return LoopBounds(L, *InitialIVValue, *StepInst, StepValue, *FinalIVValue,

228 SE);

229}

230

232

234 BasicBlock *Latch = L.getLoopLatch();

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

236

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

239

241 assert(LatchCmpInst &&

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

243

244

245

249

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

252

253

254

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

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

257 return Pred;

258

259

262

264 if (D == Direction::Increasing)

266

267 if (D == Direction::Decreasing)

269

270

271

273}

274

277 dyn_cast(SE.getSCEV(&getStepInst())))

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

279 if (SE.isKnownPositive(StepRecur))

280 return Direction::Increasing;

281 if (SE.isKnownNegative(StepRecur))

282 return Direction::Decreasing;

283 }

284

285 return Direction::Unknown;

286}

287

291

292 return std::nullopt;

293}

294

297 return nullptr;

298

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

303 return nullptr;

304

307

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

311 continue;

312

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

315

316

317

318

319

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

321 return &IndVar;

322

323

324

325

326

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

328 return &IndVar;

329 }

330

331 return nullptr;

332}

333

338

339 return false;

340}

341

344

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

347 return false;

348

349

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

351 if (const Instruction *I = dyn_cast(U))

353 return false;

354

357 return false;

358

359

362 return false;

363

364

366}

367

370 return nullptr;

371

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

375

376

378 return nullptr;

379

380

381

383 if (!ExitFromLatch)

384 return nullptr;

385

387 if (!GuardBB)

388 return nullptr;

389

391

394 return nullptr;

395

399

400

401

402

403

405 true) ==

406 GuardOtherSucc)

407 return GuardBI;

408 else

409 return nullptr;

410}

411

415 return false;

416

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

419 return false;

420

422 return false;

423

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

426 return false;

427

428 return true;

429}

430

431

435

436

437

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

439 continue;

440

441 for (const Use &U : I.uses()) {

442 const Instruction *UI = cast(U.getUser());

444

445

446

447

448 if (const PHINode *P = dyn_cast(UI))

449 UserBB = P->getIncomingBlock(U);

450

451

452

453

454

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

457 return false;

458 }

459 }

460 return true;

461}

462

464

467 });

468}

469

471 bool IgnoreTokens) const {

472

473

474

477 });

478}

479

481

482

484}

485

486

488

489

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

492 return false;

493

495 if (auto *CB = dyn_cast(&I))

496 if (CB->cannotDuplicate())

497 return false;

498 }

499 return true;

500}

501

503 MDNode *LoopID = nullptr;

504

505

508 for (BasicBlock *BB : LatchesBlocks) {

511

512 if (!MD)

513 return nullptr;

514

515 if (!LoopID)

516 LoopID = MD;

517 else if (MD != LoopID)

518 return nullptr;

519 }

522 return nullptr;

523 return LoopID;

524}

525

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

530 "Loop ID should refer to itself");

531

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

536}

537

540

541 MDNode *DisableUnrollMD =

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

547}

548

551

553

554 if (MustProgress)

555 return;

556

557 MDNode *MustProgressMD =

563}

564

567

568 if (!DesiredLoopIdMetadata)

569 return false;

570

571 MDNode *ParallelAccesses =

574 ParallelAccessGroups;

575 if (ParallelAccesses) {

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

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

580 ParallelAccessGroups.insert(AccGroup);

581 }

582 }

583

584

585

586

587

588

591 if (.mayReadOrWriteMemory())

592 continue;

593

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

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

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

598 return ParallelAccessGroups.count(AG);

599 }

600

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

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

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

605 if (ParallelAccessGroups.count(AccGroup))

606 return true;

607 }

608 return false;

609 };

610

611 if (ContainsAccessGroup(AccessGroup))

612 continue;

613 }

614

615

616

617

618

620 I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);

621

622 if (!LoopIdMD)

623 return false;

624

626 return false;

627 }

628 }

629 return true;

630}

631

633

635

638

639

640

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

643 if (!Start)

645 else

647 }

648 }

649

650 if (Start)

652 }

653

654

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

658

659

660

662 return LocRange(HeadBB->getTerminator()->getDebugLoc());

663

665}

666

668 std::string Result;

671 LoopDbgLoc.print(OS);

672 else

673

675 return Result;

676}

677

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

680

683}

684#endif

685

686

687

688

689

690namespace {

691

692

693class UnloopUpdater {

694 Loop &Unloop;

696

698

699

700

701

702

704

705

706

707 bool FoundIB = false;

708

709public:

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

711

712 void updateBlockParents();

713

714 void removeBlocksFromAncestors();

715

716 void updateSubloopParents();

717

718protected:

720};

721}

722

723

724

725void UnloopUpdater::updateBlockParents() {

726 if (Unloop.getNumBlocks()) {

727

728

731

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

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

734

735 if (NL != L) {

736

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

738 "uninitialized successor");

739 LI->changeLoopFor(POI, NL);

740 } else {

741

742

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

744 }

745 }

746 }

747

748

749 bool Changed = FoundIB;

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

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

752 (void)NIters;

753

754

755

756 Changed = false;

758 POE = DFS.endPostorder();

759 POI != POE; ++POI) {

760

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

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

763 if (NL != L) {

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

765 "uninitialized successor");

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

767 Changed = true;

768 }

769 }

770 }

771}

772

773

774void UnloopUpdater::removeBlocksFromAncestors() {

775

776

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

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

779 if (Unloop.contains(OuterParent)) {

782 OuterParent = SubloopParents[OuterParent];

783 }

784

785

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

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

789 OldParent->removeBlockFromLoop(BB);

790 }

791 }

792}

793

794

795void UnloopUpdater::updateSubloopParents() {

796 while (!Unloop.isInnermost()) {

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

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

799

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

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

802 Parent->addChildLoop(Subloop);

803 else

804 LI->addTopLevelLoop(Subloop);

805 }

806}

807

808

809

810

811

812

814

815

816

817 Loop *NearLoop = BBLoop;

818

819 Loop *Subloop = nullptr;

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

821 Subloop = NearLoop;

822

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

826 }

827

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

829 }

830

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

833 NearLoop = nullptr;

834 }

836 if (Succ == BB)

837 continue;

838

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

840 if (L == &Unloop) {

841

842

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

844 FoundIB = true;

845 }

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

847

848 if (Subloop)

849 continue;

850

851

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

853

854

855 L = SubloopParents[L];

856

857 }

858 if (L == &Unloop) {

859 continue;

860 }

861

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

863 L = L->getParentLoop();

864 }

865

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

867 NearLoop = L;

868 }

869 if (Subloop) {

870 SubloopParents[Subloop] = NearLoop;

871 return BBLoop;

872 }

873 return NearLoop;

874}

875

877

880

881

885}

886

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

889

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

891

892

894

896

897 if (getLoopFor(BB) != Unloop)

898 continue;

899

900

901

902 changeLoopFor(BB, nullptr);

903 }

904

905

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

908 if (*I == Unloop) {

909 removeLoop(I);

910 break;

911 }

912 }

913

914

917

918 return;

919 }

920

921

922

923 UnloopUpdater Updater(Unloop, this);

924 Updater.updateBlockParents();

925

926

927 Updater.removeBlocksFromAncestors();

928

929

930 Updater.updateSubloopParents();

931

932

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

936 if (*I == Unloop) {

938 break;

939 }

940 }

941}

942

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

946

947

948 return false;

949

950 const Instruction *I = dyn_cast(V);

951 if ()

952 return false;

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

954 if (!L)

955 return false;

956 if (L->contains(ExitBB))

957

958 return false;

959

960

961

962

963

964 return true;

965}

966

968

970

971

972

973

974

975

978 return LI;

979}

980

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

985 LI.print(OS);

987}

988

990

992

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

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

995 OS << ")\n";

996

997

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

999 return;

1000 }

1001

1003

1004

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

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

1007 OS << ")\n";

1008

1009

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

1011 return;

1012 }

1013

1014 OS << Banner;

1015

1016 auto *PreHeader = L.getLoopPreheader();

1017 if (PreHeader) {

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

1019 PreHeader->print(OS);

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

1021 }

1022

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

1026 else

1027 OS << "Printing block";

1028

1030 L.getExitBlocks(ExitBlocks);

1031 if (!ExitBlocks.empty()) {

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

1033 for (auto *Block : ExitBlocks)

1036 else

1037 OS << "Printing block";

1038 }

1039}

1040

1042

1043 if (!LoopID)

1044 return nullptr;

1045

1046

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

1049

1050

1052 MDNode *MD = dyn_cast(MDO);

1054 continue;

1056 if (!S)

1057 continue;

1058

1060 return MD;

1061 }

1062

1063

1064 return nullptr;

1065}

1066

1069}

1070

1071

1072

1073

1074

1075

1076std::optional<const MDOperand *>

1079 if (!MD)

1080 return std::nullopt;

1082 case 1:

1083 return nullptr;

1084 case 2:

1086 default:

1088 }

1089}

1090

1094 if (!MD)

1095 return std::nullopt;

1097 case 1:

1098

1099 return true;

1100 case 2:

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

1103 return IntMD->getZExtValue();

1104 return true;

1105 }

1107}

1108

1111}

1112

1117 if (!AttrMD)

1118 return std::nullopt;

1119

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

1121 if (!IntMD)

1122 return std::nullopt;

1123

1125}

1126

1130}

1131

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

1136 if (!CB->isConvergent())

1137 continue;

1138

1139

1140

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

1142 auto *TokenDef = cast(Token);

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

1144 return CB;

1145 }

1146 return nullptr;

1147 }

1148 }

1149 return nullptr;

1150}

1151

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

1154}

1155

1157

1160}

1161

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

1164}

1165

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

1168}

1169

1174

1176

1177

1179

1180

1181

1182 if (OrigLoopID) {

1184 bool IsVectorMetadata = false;

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

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

1188 if (S)

1189 IsVectorMetadata =

1192 });

1193 }

1194 if (!IsVectorMetadata)

1196 }

1197 }

1198

1199

1200

1202

1204

1206 return NewLoopID;

1207}

1208

1209

1210

1211

1212

1215}

1216

1219 true, true)

1223

1225 releaseMemory();

1226 LI.analyze(getAnalysis().getDomTree());

1227 return false;

1228}

1229

1231

1232

1233

1234

1235

1237 auto &DT = getAnalysis().getDomTree();

1239 }

1240}

1241

1245}

1246

1249}

1250

1257}

1258

1259

1260

1261

1262

1263

1264

1265

1269 POE = Traversal.end();

1270 POI != POE; ++POI)

1271 ;

1272}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

#define LLVM_DUMP_METHOD

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

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

static bool runOnFunction(Function &F, bool PostInlining)

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

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

This header defines various interfaces for pass management in LLVM.

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

static const char * LLVMLoopMustProgress

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

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

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

This file defines the interface for the loop nest analysis.

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

uint64_t IntrinsicInst * II

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

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

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

This file defines the SmallPtrSet class.

This templated class represents "all analyses that operate over " (e....

API to communicate dependencies between analyses during invalidation.

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.

Represent the analysis usage information of a pass.

void setPreservesAll()

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

AnalysisUsage & addRequiredTransitive()

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

LLVM Basic Block Representation.

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.

InstListType::iterator iterator

Instruction iterators...

LLVMContext & getContext() const

Get the context in which this basic block lives.

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

Conditional or Unconditional Branch instruction.

bool isConditional() const

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

Value * getCondition() const

Represents analyses that only rely on functions' control flow.

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

This class is the base class for the comparison instructions.

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

@ ICMP_SLT

signed less than

@ ICMP_SGT

signed greater than

Predicate getSwappedPredicate() const

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

Predicate getInversePredicate() const

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

Predicate getPredicate() const

Return the predicate for this instruction.

Predicate getFlippedStrictnessPredicate() const

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

This is the shared class of boolean and integer constants.

bool isOne() const

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

int64_t getSExtValue() const

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

This class represents an Operation in the Expression.

Analysis pass which computes a DominatorTree.

Core dominator tree base class.

Legacy analysis pass which computes a DominatorTree.

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

bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

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

Module * getParent()

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

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

A struct for saving information about induction variables.

BinaryOperator * getInductionBinOp() const

const SCEV * getStep() const

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.

Instruction::BinaryOps getInductionOpcode() const

Returns binary opcode of the induction operator.

Value * getStartValue() const

ConstantInt * getConstIntStepValue() const

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

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

Analysis pass that exposes the LoopInfo for a function.

LoopInfo run(Function &F, FunctionAnalysisManager &AM)

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

bool contains(const Loop *L) const

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

bool isOutermost() const

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

BasicBlock * getLoopLatch() const

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

bool isInnermost() const

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

BasicBlock * getHeader() const

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

Return all loop latch blocks of this loop.

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

Print loop with all the BBs inside it.

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

iterator_range< block_iterator > blocks() const

bool isInvalid() const

Return true if this loop is no longer valid.

BasicBlock * getLoopPreheader() const

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

LoopT * getParentLoop() const

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

bool hasDedicatedExits() const

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

BasicBlock * getUniqueExitBlock() const

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

LoopT * removeChildLoop(iterator I)

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

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

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

Postorder list iterators.

void perform(const LoopInfo *LI)

Traverse the loop blocks and store the DFS result.

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

POTIterator begin()

Postorder traversal over the graph.

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

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

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

Create the loop forest using a stable algorithm.

void print(raw_ostream &OS) const

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

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

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

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

void getAnalysisUsage(AnalysisUsage &AU) const override

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

void verifyAnalysis() const override

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

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

print - Print out the internal state of the pass.

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

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

Handle invalidation explicitly.

void erase(Loop *L)

Update LoopInfo after removing the last backedge from a loop.

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

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

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

const DebugLoc & getStart() const

Represents a single loop in the control flow graph.

bool isCanonical(ScalarEvolution &SE) const

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

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

Return true if the Loop is in LCSSA form.

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

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

bool isSafeToClone() const

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

std::string getLocStr() const

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

bool hasLoopInvariantOperands(const Instruction *I) const

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

BranchInst * getLoopGuardBranch() const

Return the loop guard branch, if it exists.

bool isAnnotatedParallel() const

Returns true if the loop is annotated parallel.

DebugLoc getStartLoc() const

Return the debug location of the start of this loop.

LocRange getLocRange() const

Return the source code span of the loop.

bool isLoopInvariant(const Value *V) const

Return true if the specified value is loop invariant.

ICmpInst * getLatchCmpInst() const

Get the latch condition instruction.

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

Get the loop induction descriptor for the loop induction variable.

bool isRotatedForm() const

Return true if the loop is in rotated form.

void setLoopMustProgress()

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

PHINode * getInductionVariable(ScalarEvolution &SE) const

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

bool isLoopSimplifyForm() const

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

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.

void setLoopID(MDNode *LoopID) const

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

void setLoopAlreadyUnrolled()

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

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

PHINode * getCanonicalInductionVariable() const

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

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

Obtain the unique incoming and back edge.

MDNode * getLoopID() const

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

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

Return true if the given PHINode AuxIndVar is.

void replaceOperandWith(unsigned I, Metadata *New)

Replace a specific operand.

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

const MDOperand & getOperand(unsigned I) const

ArrayRef< MDOperand > operands() const

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

unsigned getNumOperands() const

Return number of MDNode operands.

Tracking metadata reference owned by Metadata.

StringRef getString() const

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

MemorySSA * getMemorySSA() const

Get handle on MemorySSA.

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

MemoryUseOrDef * getMemoryAccess(const Instruction *I) const

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

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

const std::string & getModuleIdentifier() const

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

Value * getIncomingValueForBlock(const BasicBlock *BB) const

static PassRegistry * getPassRegistry()

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

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.

PreservedAnalysisChecker getChecker() const

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

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

This class represents an analyzed expression in the program.

The main scalar evolution driver.

const SCEV * getSCEV(Value *V)

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

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

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

void forgetBlockAndLoopDispositions(Value *V=nullptr)

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

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.

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

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

void push_back(const T &Elt)

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

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

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

Value * getOperand(unsigned i) const

LLVM Value Representation.

iterator_range< user_iterator > users()

const ParentTy * getParent() const

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

A raw_ostream that writes to an std::string.

#define llvm_unreachable(msg)

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

LocationClass< Ty > location(Ty &L)

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.

bool all_of(R &&range, UnaryPredicate P)

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

bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)

Returns true if Name is applied to TheLoop and enabled.

bool succ_empty(const Instruction *I)

bool forcePrintModuleIR()

void initializeLoopInfoWrapperPassPass(PassRegistry &)

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

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

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

Find named metadata for a loop with an integer value.

auto pred_end(const MachineBasicBlock *BB)

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

Find string metadata for loop.

auto successors(const MachineBasicBlock *BB)

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

Find string metadata for a loop.

bool hasMustProgress(const Loop *L)

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

bool any_of(R &&range, UnaryPredicate P)

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

bool isMustProgress(const Loop *L)

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

CallBase * getLoopConvergenceHeart(const Loop *TheLoop)

Find the convergence heart of the loop.

bool isFinite(const Loop *L)

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

raw_ostream & dbgs()

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

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

bool VerifyLoopInfo

Enable verification of loop info.

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

Find named metadata for a loop with an integer value.

bool isValidAsAccessGroup(MDNode *AccGroup)

Return whether an MDNode might represent an access group.

auto pred_begin(const MachineBasicBlock *BB)

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.

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

Returns true if Element is found in Range.

@ Default

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

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

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

MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)

Find and return the loop attribute node for the attribute Name in LoopID.

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

Implement std::swap in terms of BitVector swap.

A special type used by analysis passes to provide an address that identifies that particular analysis...

Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Below are some utilities to get the loop guard, loop bounds and induction variable,...

static std::optional< Loop::LoopBounds > getBounds(const Loop &L, PHINode &IndVar, ScalarEvolution &SE)

Return the LoopBounds object if.

Direction

An enum for the direction of the loop.

ICmpInst::Predicate getCanonicalPredicate() const

Return the canonical predicate for the latch compare instruction, if able to be calcuated.

Direction getDirection() const

Get the direction of the loop.