LoopInfo.cpp Source File (original) (raw)

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

41using namespace llvm;

48#ifdef EXPENSIVE_CHECKS

50#else

52#endif

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

69}

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

107 if (MSSAU)

111

112

113

114

115

116 I->dropUnknownNonDebugMetadata();

117

118 if (SE)

120

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

163 if (CI->isZero())

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

168 if (CI->isOne())

169 return PN;

170 }

171 return nullptr;

172}

173

174

178 if (BI->isConditional())

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

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

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

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

252

253

254

257 return Pred;

258

259

262

264 if (D == Direction::Increasing)

266

267 if (D == Direction::Decreasing)

269

270

271

273}

274

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

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()) {

444

445

446

447

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

469

471 bool IgnoreTokens) const {

472

473

474

477 });

478}

479

485

486

488

489

492 return false;

493

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

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()) {

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

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

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

729 LoopBlocksTraversal Traversal(DFS, LI);

730 for (BasicBlock *POI : Traversal) {

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

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

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

752 (void)NIters;

753

754

755

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

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;

787 OldParent = OldParent->getParentLoop()) {

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

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

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 }

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

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

879 FunctionAnalysisManager::Invalidator &) {

880

881

885}

886

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

889

891

892

894

896

898 continue;

899

900

901

903 }

904

905

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

908 if (*I == Unloop) {

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

951 if ()

952 return false;

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 const std::string &Banner) {

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

1025 Block->print(OS);

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)

1035 Block->print(OS);

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

1054 continue;

1056 if (!S)

1057 continue;

1058

1060 return MD;

1061 }

1062

1063

1064 return nullptr;

1065}

1066

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:

1103 return IntMD->getZExtValue();

1104 return true;

1105 }

1107}

1108

1112

1117 if (!AttrMD)

1118 return std::nullopt;

1119

1121 if (!IntMD)

1122 return std::nullopt;

1123

1125}

1126

1131

1136 if (!CB->isConvergent())

1137 continue;

1138

1139

1140

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

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

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;

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

1214

1217 true, true)

1221

1227

1229

1230

1231

1232

1233

1236 LI.verify(DT);

1237 }

1238}

1239

1244

1248

1256

1257

1258

1259

1260

1261

1262

1263

1267 POE = Traversal.end();

1268 POI != POE; ++POI)

1269 ;

1270}

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

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.

#define LLVM_EXPORT_TEMPLATE

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

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)

Definition LoopInfo.cpp:432

static const char * LLVMLoopMustProgress

Definition LoopInfo.cpp:1156

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

Loop::LoopBounds::Direction Direction

Definition LoopInfo.cpp:231

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)

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

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 Function * getParent() const

Return the enclosing method, or null if none.

LLVM_ABI const BasicBlock * getUniquePredecessor() const

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

InstListType::iterator iterator

Instruction iterators...

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

Analysis pass which computes a DominatorTree.

Legacy analysis pass which computes a DominatorTree.

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

print - Print out the internal state of the pass.

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

LLVM_ABI bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

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

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

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

Definition LoopInfo.cpp:969

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

bool contains(const Loop *L) const

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

bool isOutermost() const

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

BasicBlock * getLoopLatch() const

bool isInnermost() const

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

BasicBlock * getHeader() const

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

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

iterator_range< block_iterator > blocks() const

bool isInvalid() const

Return true if this loop is no longer valid.

BasicBlock * getLoopPreheader() const

LoopT * getParentLoop() const

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

bool hasDedicatedExits() const

BasicBlock * getUniqueExitBlock() const

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.

friend class LoopBlocksTraversal

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

Postorder list iterators.

void perform(const LoopInfo *LI)

Traverse the loop blocks and store the DFS result.

Definition LoopInfo.cpp:1264

po_iterator< BasicBlock *, LoopBlocksTraversal, true > POTIterator

Graph traversal iterator.

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 addTopLevelLoop(Loop *New)

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

Create the loop forest using a stable algorithm.

Loop * removeLoop(iterator I)

void changeLoopFor(BasicBlock *BB, Loop *L)

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

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

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

Definition LoopInfo.cpp:1240

LoopInfoWrapperPass()

Definition LoopInfo.cpp:1213

void releaseMemory() override

releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...

bool runOnFunction(Function &F) override

Calculate the natural loop information for a given function.

Definition LoopInfo.cpp:1222

void verifyAnalysis() const override

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

Definition LoopInfo.cpp:1228

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

print - Print out the internal state of the pass.

Definition LoopInfo.cpp:1245

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

Definition LoopInfo.cpp:943

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

Handle invalidation explicitly.

Definition LoopInfo.cpp:878

LLVM_ABI void erase(Loop *L)

Update LoopInfo after removing the last backedge from a loop.

Definition LoopInfo.cpp:887

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

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

Definition LoopInfo.cpp:981

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

Definition LoopInfo.cpp:412

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

Return true if the Loop is in LCSSA form.

Definition LoopInfo.cpp:463

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

bool isSafeToClone() const

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

Definition LoopInfo.cpp:487

std::string getLocStr() const

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

Definition LoopInfo.cpp:667

void dumpVerbose() const

Definition LoopInfo.cpp:681

bool hasLoopInvariantOperands(const Instruction *I) const

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

Definition LoopInfo.cpp:67

BranchInst * getLoopGuardBranch() const

Return the loop guard branch, if it exists.

Definition LoopInfo.cpp:368

bool isAnnotatedParallel() const

Returns true if the loop is annotated parallel.

Definition LoopInfo.cpp:565

DebugLoc getStartLoc() const

Return the debug location of the start of this loop.

Definition LoopInfo.cpp:632

void dump() const

Definition LoopInfo.cpp:679

LocRange getLocRange() const

Return the source code span of the loop.

Definition LoopInfo.cpp:634

bool isLoopInvariant(const Value *V) const

Return true if the specified value is loop invariant.

Definition LoopInfo.cpp:61

ICmpInst * getLatchCmpInst() const

Get the latch condition instruction.

Definition LoopInfo.cpp:175

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

Get the loop induction descriptor for the loop induction variable.

Definition LoopInfo.cpp:334

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.

Definition LoopInfo.cpp:549

PHINode * getInductionVariable(ScalarEvolution &SE) const

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

Definition LoopInfo.cpp:295

bool isLoopSimplifyForm() const

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

Definition LoopInfo.cpp:480

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

void setLoopID(MDNode *LoopID) const

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

Definition LoopInfo.cpp:526

void setLoopAlreadyUnrolled()

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

Definition LoopInfo.cpp:538

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

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

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

Obtain the unique incoming and back edge.

Definition LoopInfo.cpp:125

MDNode * getLoopID() const

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

Definition LoopInfo.cpp:502

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

Return true if the given PHINode AuxIndVar is.

Definition LoopInfo.cpp:342

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

LLVM_ABI StringRef getString() const

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

MemorySSA * getMemorySSA() const

Get handle on MemorySSA.

LLVM_ABI 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

AnalysisType & getAnalysis() const

getAnalysis() - This function is used by subclasses to get to the analysis information ...

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.

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

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

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

bool starts_with(StringRef Prefix) const

Check if this string starts with the given Prefix.

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

self_iterator getIterator()

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)

std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > extract_or_null(Y &&MD)

Extract a Value from Metadata, allowing null.

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.

LLVM_ABI bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)

Returns true if Name is applied to TheLoop and enabled.

Definition LoopInfo.cpp:1109

bool succ_empty(const Instruction *I)

bool forcePrintModuleIR()

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

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

Definition LoopInfo.cpp:1091

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

Find named metadata for a loop with an integer value.

Definition LoopInfo.cpp:1127

auto pred_end(const MachineBasicBlock *BB)

decltype(auto) dyn_cast(const From &Val)

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

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

Find string metadata for loop.

Definition LoopInfo.cpp:1077

auto successors(const MachineBasicBlock *BB)

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

Find string metadata for a loop.

Definition LoopInfo.cpp:1067

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

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

LLVM_ABI bool hasMustProgress(const Loop *L)

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

Definition LoopInfo.cpp:1158

auto dyn_cast_or_null(const Y &Val)

bool any_of(R &&range, UnaryPredicate P)

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

LLVM_ABI bool isMustProgress(const Loop *L)

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

Definition LoopInfo.cpp:1162

LLVM_ABI CallBase * getLoopConvergenceHeart(const Loop *TheLoop)

Find the convergence heart of the loop.

Definition LoopInfo.cpp:1132

LLVM_ABI 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

DominatorTreeBase< T, false > DomTreeBase

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI bool VerifyLoopInfo

Enable verification of loop info.

Definition LoopInfo.cpp:51

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

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

Find named metadata for a loop with an integer value.

Definition LoopInfo.cpp:1113

LLVM_ABI bool isValidAsAccessGroup(MDNode *AccGroup)

Return whether an MDNode might represent an access group.

Definition LoopInfo.cpp:1166

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

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

Definition LoopInfo.cpp:989

DWARFExpression::Operation Op

PredIterator< BasicBlock, Value::user_iterator > pred_iterator

auto pred_begin(const MachineBasicBlock *BB)

decltype(auto) cast(const From &Val)

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

LLVM_ABI 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

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

Returns true if Element is found in Range.

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

@ Default

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

LLVM_ABI MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)

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

Definition LoopInfo.cpp:1041

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