LoopUnrollAndJam.cpp Source File (original) (raw)

54#include <assert.h>

55#include

56#include

58using namespace llvm;

60#define DEBUG_TYPE "loop-unroll-and-jam"

62 STATISTIC(NumUnrolledAndJammed, "Number of loops unroll and jammed");

63 STATISTIC(NumCompletelyUnrolledAndJammed, "Number of loops unroll and jammed");

71 Loop *SubLoop = L.getSubLoops()[0];

76 if (DT.dominates(SubLoopLatch, BB))

78 else

79 ForeBlocks.insert(BB);

80 }

81 }

87 if (BB == SubLoopPreHeader)

88 continue;

91 if (!ForeBlocks.count(Succ))

92 return false;

93 }

95 return true;

96}

105

107 if (L == &JamLoop)

108 break;

109

111 return false;

112 }

113

114 return true;

115}

116

117

118

127

128

129

130

131

132

133

134

135

136template

140

142 if (!VisitedInstr.insert(I).second)

143 return true;

144

145 if (AftBlocks.count(I->getParent()))

146 for (auto &U : I->operands())

148 if (!ProcessInstr(II))

149 return false;

150

151 return Visit(I);

152 };

153

154 for (auto &Phi : Header->phis()) {

155 Value *V = Phi.getIncomingValueForBlock(Latch);

157 if (!ProcessInstr(I))

158 return false;

159 }

160

161 return true;

162}

163

164

169

170

173 if (AftBlocks.count(I->getParent()))

174 I->moveBefore(InsertLoc);

175 return true;

176 });

177}

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

215 unsigned TripMultiple, bool UnrollRemainder,

219

220

222 assert(Header && "No header.");

223 assert(L->getSubLoops().size() == 1);

224 Loop *SubLoop = *L->begin();

225

226

227 if (TripCount == 0 && Count < 2) {

228 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; almost nothing to do\n");

230 }

231

233 assert(TripMultiple > 0);

234 assert(TripCount == 0 || TripCount % TripMultiple == 0);

235

236

237 bool CompletelyUnroll = (Count == TripCount);

238

239

240 if (TripMultiple % Count != 0) {

242 true,

243 UnrollRemainder, false,

244 LI, SE, DT, AC, TTI, true,

246 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; remainder loop could not be "

247 "generated when assuming runtime trip count\n");

249 }

250 }

251

252

253

254 if (SE) {

257 }

258

259 using namespace ore;

260

261 if (CompletelyUnroll) {

262 LLVM_DEBUG(dbgs() << "COMPLETELY UNROLL AND JAMMING loop %"

263 << Header->getName() << " with trip count " << TripCount

264 << "!\n");

266 L->getHeader())

267 << "completely unroll and jammed loop with "

268 << NV("UnrollCount", TripCount) << " iterations");

269 } else {

270 auto DiagBuilder = [&]() {

272 L->getHeader());

273 return Diag << "unroll and jammed loop by a factor of "

274 << NV("UnrollCount", Count);

275 };

276

277 LLVM_DEBUG(dbgs() << "UNROLL AND JAMMING loop %" << Header->getName()

278 << " by " << Count);

279 if (TripMultiple != 1) {

280 LLVM_DEBUG(dbgs() << " with " << TripMultiple << " trips per branch");

281 ORE->emit([&]() {

282 return DiagBuilder() << " with " << NV("TripMultiple", TripMultiple)

283 << " trips per branch";

284 });

285 } else {

287 ORE->emit([&]() { return DiagBuilder() << " with run-time trip count"; });

288 }

290 }

291

292 BasicBlock *Preheader = L->getLoopPreheader();

293 BasicBlock *LatchBlock = L->getLoopLatch();

294 assert(Preheader && "No preheader");

295 assert(LatchBlock && "No latch block");

298 bool ContinueOnTrue = L->contains(BI->getSuccessor(0));

300 bool SubLoopContinueOnTrue = SubLoop->contains(

302

303

304

309 DT);

310

311

312

313

314 std::vector<BasicBlock *> ForeBlocksFirst;

315 std::vector<BasicBlock *> ForeBlocksLast;

316 std::vector<BasicBlock *> SubLoopBlocksFirst;

317 std::vector<BasicBlock *> SubLoopBlocksLast;

318 std::vector<BasicBlock *> AftBlocksFirst;

319 std::vector<BasicBlock *> AftBlocksLast;

320 ForeBlocksFirst.push_back(Header);

322 SubLoopBlocksFirst.push_back(SubLoop->getHeader());

324 AftBlocksFirst.push_back(SubLoop->getExitBlock());

325 AftBlocksLast.push_back(L->getExitingBlock());

326

328

329

331 Header, LatchBlock, ForeBlocksLast[0]->getTerminator()->getIterator(),

332 AftBlocks);

333

334

335

336

339

342

343

344

345 if (Header->getParent()->shouldEmitDebugInfoForProfiling() &&

347 for (BasicBlock *BB : L->getBlocks())

349 if (.isDebugOrPseudoInst())

350 if (const DILocation *DIL = I.getDebugLoc()) {

351 auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(Count);

352 if (NewDIL)

353 I.setDebugLoc(*NewDIL);

354 else

356 << "Failed to create new discriminator: "

357 << DIL->getFilename() << " Line: " << DIL->getLine());

358 }

359

360

361 for (unsigned It = 1; It != Count; ++It) {

363

366 NewLoops[L] = L;

367 NewLoops[SubLoop] = SubLoop;

368

372 Header->getParent()->insert(Header->getParent()->end(), New);

373

374

376

377 if (ForeBlocks.count(*BB)) {

378 if (*BB == ForeBlocksFirst[0])

379 ForeBlocksFirst.push_back(New);

380 if (*BB == ForeBlocksLast[0])

381 ForeBlocksLast.push_back(New);

382 } else if (SubLoopBlocks.count(*BB)) {

383 if (*BB == SubLoopBlocksFirst[0])

384 SubLoopBlocksFirst.push_back(New);

385 if (*BB == SubLoopBlocksLast[0])

386 SubLoopBlocksLast.push_back(New);

387 } else if (AftBlocks.count(*BB)) {

388 if (*BB == AftBlocksFirst[0])

389 AftBlocksFirst.push_back(New);

390 if (*BB == AftBlocksLast[0])

391 AftBlocksLast.push_back(New);

392 } else {

393 llvm_unreachable("BB being cloned should be in Fore/Sub/Aft");

394 }

395

396

397 auto &Last = LastValueMap[*BB];

398 PrevItValueMap[New] = (It == 1 ? *BB : Last);

401 VI != VE; ++VI) {

402 auto &LVM = LastValueMap[VI->first];

403 PrevItValueMap[VI->second] =

404 const_cast<Value *>(It == 1 ? VI->first : LVM);

405 LVM = VI->second;

406 }

407

409

410

411 if (*BB == ForeBlocksFirst[0])

412 DT->addNewBlock(New, ForeBlocksLast[It - 1]);

413 else if (*BB == SubLoopBlocksFirst[0])

414 DT->addNewBlock(New, SubLoopBlocksLast[It - 1]);

415 else if (*BB == AftBlocksFirst[0])

416 DT->addNewBlock(New, AftBlocksLast[It - 1]);

417 else {

418

419

420 auto BBDomNode = DT->getNode(*BB);

421 auto BBIDom = BBDomNode->getIDom();

422 BasicBlock *OriginalBBIDom = BBIDom->getBlock();

423 assert(OriginalBBIDom);

427 }

428 }

429

430

432 for (BasicBlock *NewBlock : NewBlocks) {

436 }

437 }

438

439

440

441 for (PHINode &Phi : ForeBlocksFirst[It]->phis()) {

442 Value *OldValue = Phi.getIncomingValueForBlock(AftBlocksLast[It]);

443 assert(OldValue && "should have incoming edge from Aft[It]");

444 Value *NewValue = OldValue;

445 if (Value *PrevValue = PrevItValueMap[OldValue])

446 NewValue = PrevValue;

447

448 assert(Phi.getNumOperands() == 2);

449 Phi.setIncomingBlock(0, ForeBlocksLast[It - 1]);

450 Phi.setIncomingValue(0, NewValue);

451 Phi.removeIncomingValue(1);

452 }

453 }

454

455

456

457

458

459

460

464 for (PHINode &Phi : BB->phis()) {

465 for (unsigned b = 0; b < Phi.getNumIncomingValues(); ++b) {

466 if (Phi.getIncomingBlock(b) == OldBB) {

467 Value *OldValue = Phi.getIncomingValue(b);

468 if (Value *LastValue = LastValueMap[OldValue])

469 Phi.setIncomingValue(b, LastValue);

470 Phi.setIncomingBlock(b, NewBB);

471 break;

472 }

473 }

474 }

475 };

476

480 Phi->moveBefore(*Dest, insertPoint);

481 };

482

483

484 updatePHIBlocksAndValues(LoopExit, AftBlocksLast[0], AftBlocksLast.back(),

485 LastValueMap);

486

487

491 ForeTerm->setSuccessor(0, SubLoopBlocksFirst[0]);

492

493 if (CompletelyUnroll) {

495 Phi->replaceAllUsesWith(Phi->getIncomingValueForBlock(Preheader));

496 Phi->eraseFromParent();

497 }

498 } else {

499

500 updatePHIBlocksAndValues(ForeBlocksFirst[0], AftBlocksLast[0],

501 AftBlocksLast.back(), LastValueMap);

502 }

503

504 for (unsigned It = 1; It != Count; It++) {

505

509 ForeTerm->setSuccessor(0, ForeBlocksFirst[It]);

510 }

511

512

515 SubTerm->setSuccessor(!SubLoopContinueOnTrue, SubLoopBlocksFirst[0]);

516 SubTerm->setSuccessor(SubLoopContinueOnTrue, AftBlocksFirst[0]);

517 SubLoopBlocksFirst[0]->replacePhiUsesWith(ForeBlocksLast[0],

518 ForeBlocksLast.back());

519 SubLoopBlocksFirst[0]->replacePhiUsesWith(SubLoopBlocksLast[0],

520 SubLoopBlocksLast.back());

521

522 for (unsigned It = 1; It != Count; It++) {

523

524

526 cast(SubLoopBlocksLast[It - 1]->getTerminator());

529

530 SubLoopBlocksFirst[It]->replacePhiUsesWith(ForeBlocksLast[It],

531 ForeBlocksLast.back());

532 SubLoopBlocksFirst[It]->replacePhiUsesWith(SubLoopBlocksLast[It],

533 SubLoopBlocksLast.back());

534 movePHIs(SubLoopBlocksFirst[It], SubLoopBlocksFirst[0]);

535 }

536

537

539 if (CompletelyUnroll) {

542 } else {

543 AftTerm->setSuccessor(!ContinueOnTrue, ForeBlocksFirst[0]);

545 "Expecting the ContinueOnTrue successor of AftTerm to be LoopExit");

546 }

547 AftBlocksFirst[0]->replacePhiUsesWith(SubLoopBlocksLast[0],

548 SubLoopBlocksLast.back());

549

550 for (unsigned It = 1; It != Count; It++) {

551

552

557

558 AftBlocksFirst[It]->replacePhiUsesWith(SubLoopBlocksLast[It],

559 SubLoopBlocksLast.back());

560 movePHIs(AftBlocksFirst[It], AftBlocksFirst[0]);

561 }

562

563 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);

564

565

566 if (Count != 1) {

568 DTUpdates.emplace_back(DominatorTree::UpdateKind::Delete, ForeBlocksLast[0],

569 SubLoopBlocksFirst[0]);

570 DTUpdates.emplace_back(DominatorTree::UpdateKind::Delete,

571 SubLoopBlocksLast[0], AftBlocksFirst[0]);

572

573 DTUpdates.emplace_back(DominatorTree::UpdateKind::Insert,

574 ForeBlocksLast.back(), SubLoopBlocksFirst[0]);

575 DTUpdates.emplace_back(DominatorTree::UpdateKind::Insert,

576 SubLoopBlocksLast.back(), AftBlocksFirst[0]);

578 }

579

580

585

587

588

590

591

592

593

597

598 NumCompletelyUnrolledAndJammed += CompletelyUnroll;

599 ++NumUnrolledAndJammed;

600

601

602 if (CompletelyUnroll)

604

605#ifndef NDEBUG

606

611 : SubLoop;

615 if (!CompletelyUnroll)

616 assert(L->isLoopSimplifyForm());

619#endif

620

623}

624

627

628

632 if (!Ld->isSimple())

633 return false;

636 if (!St->isSimple())

637 return false;

639 } else if (I.mayReadOrWriteMemory()) {

640 return false;

641 }

642 }

643 }

644 return true;

645}

646

648 unsigned UnrollLevel, unsigned JamLevel,

650

651

652 for (unsigned CurLoopDepth = UnrollLevel + 1; CurLoopDepth <= JamLevel;

653 ++CurLoopDepth) {

654 auto JammedDir = D->getDirection(CurLoopDepth);

656 return true;

657

659 return false;

660 }

661

662 return true;

663}

664

666 unsigned UnrollLevel, unsigned JamLevel,

668

669 for (unsigned CurLoopDepth = UnrollLevel + 1; CurLoopDepth <= JamLevel;

670 ++CurLoopDepth) {

671 auto JammedDir = D->getDirection(CurLoopDepth);

673 return true;

674

676 return false;

677 }

678

679

680 return Sequentialized;

681}

682

683

684

685

686

687

688

689

690

692 unsigned UnrollLevel, unsigned JamLevel,

694 assert(UnrollLevel <= JamLevel &&

695 "Expecting JamLevel to be at least UnrollLevel");

696

697 if (Src == Dst)

698 return true;

699

701 return true;

702

703

704

705

706

707

708

709

710

711

712

713 std::unique_ptr D = DI.depends(Src, Dst);

714 if ()

715 return true;

716 assert(D->isOrdered() && "Expected an output, flow or anti dep.");

717

718 if (D->isConfused()) {

719 LLVM_DEBUG(dbgs() << " Confused dependency between:\n"

720 << " " << *Src << "\n"

721 << " " << *Dst << "\n");

722 return false;

723 }

724

725

726

727

728

729 for (unsigned CurLoopDepth = 1; CurLoopDepth < UnrollLevel; ++CurLoopDepth)

731 return true;

732

733 auto UnrollDirection = D->getDirection(UnrollLevel);

734

735

736

737

739 return true;

740

743 Sequentialized, D.get()))

744 return false;

745

748 Sequentialized, D.get()))

749 return false;

750

751 return true;

752}

753

754static bool

761 if (ForeBlocksMap.contains(L))

763 AllBlocks.push_back(SubLoopBlocks);

765 if (AftBlocksMap.contains(L))

767

772 CurrentLoadsAndStores.clear();

774 return false;

775

776 Loop *CurLoop = LI.getLoopFor((*Blocks.begin())->front().getParent());

777 unsigned CurLoopDepth = CurLoop->getLoopDepth();

778

779 for (auto *Earlier : EarlierLoadsAndStores) {

780 Loop *EarlierLoop = LI.getLoopFor(Earlier->getParent());

781 unsigned EarlierDepth = EarlierLoop->getLoopDepth();

782 unsigned CommonLoopDepth = std::min(EarlierDepth, CurLoopDepth);

783 for (auto *Later : CurrentLoadsAndStores) {

784 if ( checkDependency (Earlier, Later, LoopDepth, CommonLoopDepth, false,

785 DI))

786 return false;

787 }

788 }

789

790 size_t NumInsts = CurrentLoadsAndStores.size();

791 for (size_t I = 0; I < NumInsts; ++I) {

792 for (size_t J = I; J < NumInsts; ++J) {

793 if ( checkDependency (CurrentLoadsAndStores[I], CurrentLoadsAndStores[J],

794 LoopDepth, CurLoopDepth, true, DI))

795 return false;

796 }

797 }

798

799 EarlierLoadsAndStores.append(CurrentLoadsAndStores.begin(),

800 CurrentLoadsAndStores.end());

801 }

802 return true;

803}

804

806

808 return false;

809

810 const Loop *L = &Root;

811 do {

812

813 if (!L->isLoopSimplifyForm())

814 return false;

815

816 if (!L->isRotatedForm())

817 return false;

818

819 if (L->getHeader()->hasAddressTaken()) {

820 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Address taken\n");

821 return false;

822 }

823

824 unsigned SubLoopsSize = L->getSubLoops().size();

825 if (SubLoopsSize == 0)

826 return true;

827

828

829 if (SubLoopsSize != 1)

830 return false;

831

832

833

834

835

836 if (!L->getExitBlock()) {

837 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; only loops with single exit "

838 "blocks can be unrolled and jammed.\n");

839 return false;

840 }

841

842

843 if (!L->getExitingBlock()) {

844 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; only loops with single "

845 "exiting blocks can be unrolled and jammed.\n");

846 return false;

847 }

848

849 L = L->getSubLoops()[0];

850 } while (L);

851

852 return true;

853}

854

856 while (!L->getSubLoops().empty())

857 L = L->getSubLoops()[0];

858 return L;

859}

860

864 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Ineligible loop form\n");

865 return false;

866 }

867

868

869

870

871

872

873

874

875

876

877

878

879

880

881

882

883

884

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899

900

901

902

903

904

905

906

907

908

909

910

911

912

913

914

915

916

917

918

919

925 AftBlocksMap, DT)) {

926 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Incompatible loop layout\n");

927 return false;

928 }

929

930

931

932

933 if (AftBlocksMap[L].size() != 1) {

934 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Can't currently handle "

935 "multiple blocks after the loop\n");

936 return false;

937 }

938

939

940

941 if (any_of(L->getLoopsInPreorder(), [&SE](Loop *SubLoop) {

942 return !hasIterationCountInvariantInParent(SubLoop, SE);

943 })) {

944 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Inner loop iteration count is "

945 "not consistent on each iteration\n");

946 return false;

947 }

948

949

953 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Something may throw\n");

954 return false;

955 }

956

957

958

959

960

961

962

963

965 BasicBlock *Latch = L->getLoopLatch();

967 Loop *SubLoop = L->getSubLoops()[0];

969 Header, Latch, AftBlocks, [&AftBlocks, &SubLoop](Instruction *I) {

970 if (SubLoop->contains(I->getParent()))

971 return false;

972 if (AftBlocks.count(I->getParent())) {

973

974

976 return false;

977

978

979 if (I->mayHaveSideEffects() || I->mayReadOrWriteMemory())

980 return false;

981 }

982

983 return true;

984 })) {

985 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; can't move required "

986 "instructions after subloop to before it\n");

987 return false;

988 }

989

990

991

992

993 if ( checkDependencies (*L, SubLoopBlocks, ForeBlocksMap, AftBlocksMap, DI,

994 LI)) {

995 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; failed dependency check\n");

996 return false;

997 }

998

999 return true;

1000}

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

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

This file defines the DenseMap class.

This file defines a set of templates that efficiently compute a dominator tree over a generic graph.

SmallPtrSet< BasicBlock *, 4 > BasicBlockSet

Definition LoopUnrollAndJam.cpp:65

static bool partitionLoopBlocks(Loop &L, BasicBlockSet &ForeBlocks, BasicBlockSet &AftBlocks, DominatorTree &DT)

Definition LoopUnrollAndJam.cpp:69

static void moveHeaderPhiOperandsToForeBlocks(BasicBlock *Header, BasicBlock *Latch, BasicBlock::iterator InsertLoc, BasicBlockSet &AftBlocks)

Definition LoopUnrollAndJam.cpp:165

static Loop * getInnerMostLoop(Loop *L)

Definition LoopUnrollAndJam.cpp:855

static bool getLoadsAndStores(BasicBlockSet &Blocks, SmallVector< Instruction *, 4 > &MemInstr)

Definition LoopUnrollAndJam.cpp:625

static bool preservesForwardDependence(Instruction *Src, Instruction *Dst, unsigned UnrollLevel, unsigned JamLevel, bool Sequentialized, Dependence *D)

Definition LoopUnrollAndJam.cpp:647

static bool partitionOuterLoopBlocks(Loop &Root, Loop &JamLoop, BasicBlockSet &JamLoopBlocks, DenseMap< Loop *, BasicBlockSet > &ForeBlocksMap, DenseMap< Loop *, BasicBlockSet > &AftBlocksMap, DominatorTree &DT)

Partition blocks in a loop nest into blocks before and after each inner loop.

Definition LoopUnrollAndJam.cpp:100

static bool isEligibleLoopForm(const Loop &Root)

Definition LoopUnrollAndJam.cpp:805

static bool preservesBackwardDependence(Instruction *Src, Instruction *Dst, unsigned UnrollLevel, unsigned JamLevel, bool Sequentialized, Dependence *D)

Definition LoopUnrollAndJam.cpp:665

static bool checkDependencies(Loop &Root, const BasicBlockSet &SubLoopBlocks, const DenseMap< Loop *, BasicBlockSet > &ForeBlocksMap, const DenseMap< Loop *, BasicBlockSet > &AftBlocksMap, DependenceInfo &DI, LoopInfo &LI)

Definition LoopUnrollAndJam.cpp:755

static bool processHeaderPhiOperands(BasicBlock *Header, BasicBlock *Latch, BasicBlockSet &AftBlocks, T Visit)

Definition LoopUnrollAndJam.cpp:137

static bool checkDependency(Instruction *Src, Instruction *Dst, unsigned UnrollLevel, unsigned JamLevel, bool Sequentialized, DependenceInfo &DI)

Definition LoopUnrollAndJam.cpp:691

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

uint64_t IntrinsicInst * II

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

A cache of @llvm.assume calls within a function.

LLVM_ABI void registerAssumption(AssumeInst *CI)

Add an @llvm.assume intrinsic to this function's cache.

LLVM Basic Block Representation.

InstListType::iterator iterator

Instruction iterators...

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.

unsigned getNumSuccessors() const

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

void setSuccessor(unsigned idx, BasicBlock *NewSucc)

ValueT lookup(const_arg_type_t< KeyT > Val) const

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

bool contains(const_arg_type_t< KeyT > Val) const

Return true if the specified key is in the map, false otherwise.

DependenceInfo - This class is the main dependence-analysis driver.

LLVM_ABI std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool UnderRuntimeAssumptions=false)

depends - Tests for a dependence between the Src and Dst instructions.

Dependence - This class represents a dependence between two memory memory references in a function.

DomTreeNodeBase * getIDom() const

bool verify(VerificationLevel VL=VerificationLevel::Full) const

verify - checks if the tree is correct.

DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)

Add a new node to the dominator tree information.

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

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

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

LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

DomTreeT & getDomTree()

Flush DomTree updates and return DomTree.

void applyUpdatesPermissive(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

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

bool contains(const LoopT *L) const

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

BlockT * getLoopLatch() const

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

SmallVector< const LoopT *, 4 > getLoopsInPreorder() const

Return all loops in the loop nest rooted by the loop in preorder, with siblings in forward program or...

const std::vector< LoopT * > & getSubLoops() const

Return the loops contained entirely within this loop.

BlockT * getHeader() const

unsigned getLoopDepth() const

Return the nesting level of this loop.

iterator_range< block_iterator > blocks() const

BlockT * getExitBlock() const

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

BlockT * getLoopPreheader() const

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

BlockT * getExitingBlock() const

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

LoopT * getParentLoop() const

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

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

RPOIterator beginRPO() const

Reverse iterate over the cached postorder blocks.

std::vector< BasicBlock * >::const_reverse_iterator RPOIterator

void perform(const LoopInfo *LI)

Traverse the loop blocks and store the DFS result.

RPOIterator endRPO() const

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

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

LLVM_ABI void erase(Loop *L)

Update LoopInfo after removing the last backedge from a loop.

Represents a single loop in the control flow graph.

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.

The main scalar evolution driver.

LLVM_ABI void forgetLoop(const Loop *L)

This method should be called by the client when it has changed a loop in a way that may effect Scalar...

LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)

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

LLVM_ABI void verify() const

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

void computeLoopSafetyInfo(const Loop *CurLoop) override

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

bool anyBlockMayThrow() const override

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

size_type count(ConstPtrType Ptr) const

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

void insert_range(Range &&R)

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.

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

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

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

ValueMapIteratorImpl< MapT, const Value *, false > iterator

LLVM Value Representation.

self_iterator getIterator()

#define llvm_unreachable(msg)

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

Add a small namespace to avoid name clashes with the classes used in the streaming interface.

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, DependenceInfo &DI, LoopInfo &LI)

Definition LoopUnrollAndJam.cpp:861

LLVM_ABI void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, AAResults *AA=nullptr)

Perform some cleanup and simplifications on loops after unrolling.

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

LLVM_ABI BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, bool MapAtoms=true)

Return a copy of the specified basic block, but without embedding the block into a particular functio...

decltype(auto) dyn_cast(const From &Val)

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

auto successors(const MachineBasicBlock *BB)

LLVM_ABI cl::opt< bool > EnableFSDiscriminator

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 MergeBlockSuccessorsIntoGivenBlocks(SmallPtrSetImpl< BasicBlock * > &MergeBlocks, Loop *L=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)

Merge block(s) sucessors, if possible.

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI cl::opt< unsigned > SCEVCheapExpansionBudget

FunctionAddr VTableAddr Count

LoopUnrollResult

Represents the result of a UnrollLoop invocation.

@ PartiallyUnrolled

The loop was partially unrolled – we still have a loop, but with a smaller trip count.

@ Unmodified

The loop was not modified.

@ FullyUnrolled

The loop was fully unrolled into straight-line code.

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 void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)

Remaps instructions in Blocks using the mapping in VMap.

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

LLVM_ABI const Loop * addClonedBlockToLoopInfo(BasicBlock *OriginalBB, BasicBlock *ClonedBB, LoopInfo *LI, NewLoopsMap &NewLoops)

Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary and adds a mapping from the o...

decltype(auto) cast(const From &Val)

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

LLVM_ABI bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, bool PreserveLCSSA, unsigned SCEVExpansionBudget, bool RuntimeUnrollMultiExit, Loop **ResultLoop=nullptr, std::optional< unsigned > OriginalTripCount=std::nullopt, BranchProbability OriginalLoopProb=BranchProbability::getUnknown())

Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.

LLVM_ABI LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, unsigned TripMultiple, bool UnrollRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, Loop **EpilogueLoop=nullptr)

Definition LoopUnrollAndJam.cpp:214