LoopUnrollRuntime.cpp Source File (original) (raw)

43#include

45using namespace llvm;

47#define DEBUG_TYPE "loop-unroll"

50 "Number of loops unrolled with run-time trip counts");

53 cl::desc("Allow runtime unrolling for loops with multiple exits, when "

54 "epilog is generated"));

57 cl::desc("Assume the non latch exit block to be predictable"));

88 LoopInfo *LI, bool PreserveLCSSA,

100

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

102 assert(Latch && "Loop must have a latch");

104

105

106

107

108

109

111 for (PHINode &PN : Succ->phis()) {

112

113

114

115

116

117

118

121

122

123 if (L->contains(&PN)) {

124

125 NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader),

126 PreHeader);

127 } else {

128

130 }

131

132 Value *V = PN.getIncomingValueForBlock(Latch);

134 if (L->contains(I)) {

136 }

137 }

138

139

141

142

143

144

145 if (L->contains(&PN))

146 PN.setIncomingValueForBlock(NewPreHeader, NewPN);

147 else

148 PN.addIncoming(NewPN, PrologExit);

150 }

151 }

152

153

156 if (PrologLoop) {

158 if (PrologLoop->contains(PredBB))

159 PrologExitPreds.push_back(PredBB);

160

162 nullptr, PreserveLCSSA);

163 }

164

165

166

169

170 assert(Count != 0 && "nonsensical Count!");

171

172

173

174

175

176 Value *BrLoopExit =

177 B.CreateICmpULT(BECount, ConstantInt::get(BECount->getType(), Count - 1));

178

181 nullptr, PreserveLCSSA);

182

183 MDNode *BranchWeights = nullptr;

185

188 }

189 B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader,

190 BranchWeights);

192 if (DT) {

194 PrologExit);

196 }

197}

198

199

200

201

202

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

225

226

227

231 BranchProbability ProbOneNotTooMany = ProbOne - ProbTooMany;

232 return ProbOneNotTooMany / ProbNotTooMany;

233}

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

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

264 assert(Latch && "Loop must have a latch");

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297 assert(PN.hasOneUse() && "The phi should have 1 use");

299 assert(EpilogPN->getParent() == Exit && "EpilogPN should be in Exit block");

300

301 Value *V = PN.getIncomingValueForBlock(Latch);

303 if (I && L->contains(I))

304

306

307

309

311 "EpilogPN should have EpilogPreHeader incoming block");

312

314 NewExit);

315

316

317

318

319

320

321 }

322

323

324

325

327

328 if (!L->contains(Succ))

329 continue;

330

331

332

333

334

335 assert(Succ == L->getHeader() &&

336 "Expect the only in-loop successor of latch to be the loop header");

337

338 for (PHINode &PN : Succ->phis()) {

339

341 PN.getName() + ".unr");

343

344 NewPN0->addIncoming(PN.getIncomingValueForBlock(Latch), Latch);

345

346

348 PN.getName() + ".epil.init");

350

351 NewPN1->addIncoming(PN.getIncomingValueForBlock(NewPreHeader), PreHeader);

352

354

355

356

359 }

360 }

361

362

365 Value *BrLoopExit = B.CreateIsNotNull(ModVal, "lcmp.mod");

366 assert(Exit && "Loop must have a single exit block only");

367

370 PreserveLCSSA);

371

372 MDNode *BranchWeights = nullptr;

373 if (OriginalLoopProb.isUnknown() &&

375

378 }

380 B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit, BranchWeights);

381 if (!OriginalLoopProb.isUnknown()) {

384 true);

385 }

387 if (DT) {

390 }

391

392

397}

398

399

400

401

402

403

404

406 const bool UseEpilogRemainder,

407 const bool UnrollRemainder, BasicBlock *InsertTop,

409 std::vector<BasicBlock *> &NewBlocks,

412 std::optional OriginalTripCount,

414 StringRef suffix = UseEpilogRemainder ? "epil" : "prol";

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

417 Function *F = Header->getParent();

420 Loop *ParentLoop = L->getParentLoop();

422 NewLoops[ParentLoop] = ParentLoop;

423

424

425

428 NewBlocks.push_back(NewBB);

429

431

432 VMap[*BB] = NewBB;

433 if (Header == *BB) {

434

435

437 }

438

439 if (DT) {

440 if (Header == *BB) {

441

443 } else {

444

447 }

448 }

449

450 if (Latch == *BB) {

451

452 VMap.erase((*BB)->getTerminator());

453

454

455

462 auto *Zero = ConstantInt::get(NewIdx->getType(), 0);

463 auto *One = ConstantInt::get(NewIdx->getType(), 1);

465 Builder.CreateAdd(NewIdx, One, NewIdx->getName() + ".next");

466 Value *IdxCmp = Builder.CreateICmpNE(IdxNext, NewIter, NewIdx->getName() + ".cmp");

467 MDNode *BranchWeights = nullptr;

468 if ((OriginalLoopProb.isUnknown() || !UseEpilogRemainder) &&

472 if (Count >= 3) {

473

474

475

476 ExitWeight = 1;

477 BackEdgeWeight = (Count - 2) / 2;

478 } else {

479

480

481 ExitWeight = 1;

482 BackEdgeWeight = 0;

483 }

484 MDBuilder MDB(Builder.getContext());

486 }

488 Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot, BranchWeights);

489 if (!OriginalLoopProb.isUnknown() && UseEpilogRemainder) {

490

491

492

493 double FreqRemIters = 1;

496 for (unsigned N = Count - 2; N >= 1; --N) {

498 FreqRemIters += ProbReaching.toDouble();

499 }

500 }

501

502

506 }

510 }

511 }

512

513

514

525 }

526

527 Loop *NewLoop = NewLoops[L];

528 assert(NewLoop && "L should have been cloned");

529

530 if (OriginalTripCount && UseEpilogRemainder)

532

533

534 if (!UnrollRemainder)

536 return NewLoop;

537}

538

539

540

543 bool UseEpilogRemainder) {

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

561 L->getExitingBlocks(ExitingBlocks);

562 if (ExitingBlocks.size() > 2)

563 return false;

564

565

566 if (OtherExits.size() == 0)

567 return true;

568

569

570

571

572

573

574

575 return (OtherExits.size() == 1 &&

577 OtherExits[0]->getPostdominatingDeoptimizeCall()));

578

579

580

581

582}

583

584

585

586

587

588

591

593

594

595

596

597

598

599

600

601

602 return B.CreateAnd(TripCount, Count - 1, "xtraiter");

603

604

605

607 Value *ModValTmp = B.CreateURem(BECount, CountC);

608 Value *ModValAdd = B.CreateAdd(ModValTmp,

609 ConstantInt::get(ModValTmp->getType(), 1));

610

611

612 return B.CreateURem(ModValAdd, CountC, "xtraiter");

613}

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

655 Loop *L, unsigned Count, bool AllowExpensiveTripCount,

656 bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV,

659 unsigned SCEVExpansionBudget, bool RuntimeUnrollMultiExit,

660 Loop **ResultLoop, std::optional OriginalTripCount,

662 LLVM_DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");

664 LLVM_DEBUG(UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n"

665 : dbgs() << "Using prolog remainder.\n");

666

667

668 if (!L->isLoopSimplifyForm()) {

670 return false;

671 }

672

673

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

676

678

680

683 << "Loop latch not terminated by a conditional branch.\n");

684 return false;

685 }

686

687 unsigned ExitIndex = LatchBR->getSuccessor(0) == Header ? 1 : 0;

689

690 if (L->contains(LatchExit)) {

691

692

695 << "One of the loop latch successors must be the exit block.\n");

696 return false;

697 }

698

699

701 L->getUniqueNonLatchExitBlocks(OtherExits);

702

703

704 if (!L->getExitingBlock() || OtherExits.size()) {

705

706

707 if (!PreserveLCSSA)

708 return false;

709

710

713 return false;

714 } else {

715

716

717 if (!RuntimeUnrollMultiExit &&

719 UseEpilogRemainder)) {

720 LLVM_DEBUG(dbgs() << "Multiple exit/exiting blocks in loop and "

721 "multi-exit unrolling not enabled!\n");

722 return false;

723 }

724 }

725 }

726

727

728 if (!SE)

729 return false;

730

731

732

733

734

735

738 LLVM_DEBUG(dbgs() << "Could not compute exit block SCEV\n");

739 return false;

740 }

741

743

744

745

746 const SCEV *TripCountSC =

749 LLVM_DEBUG(dbgs() << "Could not compute trip count SCEV.\n");

750 return false;

751 }

752

753 BasicBlock *PreHeader = L->getLoopPreheader();

755 const DataLayout &DL = Header->getDataLayout();

757 if (!AllowExpensiveTripCount &&

759 PreHeaderBR)) {

760 LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");

761 return false;

762 }

763

764

765

769 << "Count failed constraint on overflow trip count calculation.\n");

770 return false;

771 }

772

773

774

775

776

777

778

779

780

784 BasicBlock *EpilogPreHeader = nullptr;

785 BasicBlock *PrologPreHeader = nullptr;

786

787 if (UseEpilogRemainder) {

788

789

791 NewPreHeader->setName(PreHeader->getName() + ".new");

792

794 nullptr, PreserveLCSSA);

795

796

797

798 auto *NewExitTerminator = NewExit->getTerminator();

799 NewExitTerminator->setDebugLoc(Header->getTerminator()->getDebugLoc());

800

801 EpilogPreHeader = SplitBlock(NewExit, NewExitTerminator, DT, LI);

802 EpilogPreHeader->setName(Header->getName() + ".epil.preheader");

803

804

805

806

807

808

809

810 if (auto *ParentL = L->getParentLoop())

811 if (LI->getLoopFor(LatchExit) != ParentL) {

812 LI->removeBlock(NewExit);

813 ParentL->addBasicBlockToLoop(NewExit, *LI);

814 LI->removeBlock(EpilogPreHeader);

815 ParentL->addBasicBlockToLoop(EpilogPreHeader, *LI);

816 }

817

818 } else {

819

820

821 PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);

822 PrologPreHeader->setName(Header->getName() + ".prol.preheader");

824 DT, LI);

825 PrologExit->setName(Header->getName() + ".prol.loopexit");

826

828 NewPreHeader->setName(PreHeader->getName() + ".new");

829 }

830

831

832

833

834

835

836

837

838

839

840

841

842

843

844

845

849 PreHeaderBR);

851

852

853

854

855

856

859 TripCount = B.CreateFreeze(TripCount);

860 BECount =

862 } else {

863

864

865 BECount =

867 }

868

870

871 Value *BranchVal =

872 UseEpilogRemainder ? B.CreateICmpULT(BECount,

873 ConstantInt::get(BECount->getType(),

875 B.CreateIsNotNull(ModVal, "lcmp.mod");

877 UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;

878 BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;

879

880 MDNode *BranchWeights = nullptr;

881 if ((OriginalLoopProb.isUnknown() || !UseEpilogRemainder) &&

883

886 }

888 B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop, BranchWeights);

889 if (!OriginalLoopProb.isUnknown() && UseEpilogRemainder) {

890

891

892

896 false);

897 }

899 if (DT) {

900 if (UseEpilogRemainder)

902 else

904 }

905 Function *F = Header->getParent();

906

907

909 LoopBlocks.perform(LI);

910

911

912

913

914

915

916 std::vector<BasicBlock *> NewBlocks;

918

919

920

921

922 BasicBlock *InsertBot = UseEpilogRemainder ? LatchExit : PrologExit;

923 BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;

924 Loop *remainderLoop =

925 CloneLoopBlocks(L, ModVal, UseEpilogRemainder, UnrollRemainder, InsertTop,

926 InsertBot, NewPreHeader, NewBlocks, LoopBlocks, VMap, DT,

927 LI, Count, OriginalTripCount, OriginalLoopProb);

928

929

930 F->splice(InsertBot->getIterator(), F, NewBlocks[0]->getIterator(), F->end());

931

932

933

934

935

936 for (auto *BB : OtherExits) {

937

938

939

940 for (PHINode &PN : BB->phis()) {

941 unsigned oldNumOperands = PN.getNumIncomingValues();

942

943

944 for (unsigned i = 0; i < oldNumOperands; i++){

945 auto *PredBB =PN.getIncomingBlock(i);

946 if (PredBB == Latch)

947

948 continue;

949 if (!L->contains(PredBB))

950

951

952 continue;

953

954 auto *V = PN.getIncomingValue(i);

956 if (L->contains(I))

959 }

960 }

961#if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)

964 "Breaks the definition of dedicated exits!");

965 }

966#endif

967 }

968

969

970

971

972

973

974

975

976 if (DT && !L->getExitingBlock()) {

978

979

980

981

982 for (auto *BB : L->blocks()) {

983 auto *DomNodeBB = DT->getNode(BB);

984 for (auto *DomChild : DomNodeBB->children()) {

985 auto *DomChildBB = DomChild->getBlock();

986 if (!L->contains(LI->getLoopFor(DomChildBB)) &&

987 DomChildBB->getUniquePredecessor() != BB)

988 ChildrenToUpdate.push_back(DomChildBB);

989 }

990 }

991 for (auto *BB : ChildrenToUpdate)

993 }

994

995

996

997

998

999

1000

1001

1002

1003

1004

1005

1006

1007

1008

1009

1010

1011

1013 Module *M = BB->getModule();

1019 }

1020 }

1021

1022 if (UseEpilogRemainder) {

1023

1024

1025 ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader, EpilogPreHeader,

1026 NewPreHeader, VMap, DT, LI, PreserveLCSSA, *SE, Count, *AC,

1027 OriginalLoopProb);

1028

1029

1030

1031

1032

1034 Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");

1037 NewIdx->insertBefore(Header->getFirstNonPHIIt());

1039 auto *Zero = ConstantInt::get(NewIdx->getType(), 0);

1040 auto *One = ConstantInt::get(NewIdx->getType(), 1);

1044 NewIdx->addIncoming(Zero, NewPreHeader);

1047 } else {

1048

1049

1051 NewPreHeader, VMap, DT, LI, PreserveLCSSA, *SE);

1052 }

1053

1054

1055

1057

1058

1059#if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)

1060 if (DT) {

1061 assert(DT->verify(DominatorTree::VerificationLevel::Full));

1063 }

1064#endif

1065

1066

1067 if (Count == 2 && DT && LI && SE) {

1068

1069

1071 assert(RemainderLatch);

1074 remainderLoop = nullptr;

1075

1076

1077 const DataLayout &DL = L->getHeader()->getDataLayout();

1079 for (BasicBlock *BB : RemainderBlocks) {

1083 Inst.replaceAllUsesWith(V);

1086 }

1087

1088

1089

1091 }

1092

1093

1095 assert(ExitBB && "required after breaking cond br backedge");

1096 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);

1098 }

1099

1100

1101

1102

1103 if (OtherExits.size() > 0) {

1104

1105

1107

1108

1109 if (remainderLoop)

1111 }

1112

1114 if (remainderLoop && UnrollRemainder) {

1118 ULO.Force = false;

1124 "A loop with a convergence heart does not allow runtime unrolling.");

1125 UnrollResult = UnrollLoop(remainderLoop, ULO, LI, SE, DT, AC, TTI,

1126 nullptr, PreserveLCSSA);

1127 }

1128

1130 *ResultLoop = remainderLoop;

1131 NumRuntimeUnrolled++;

1132 return true;

1133}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

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

static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit, BasicBlock *Exit, BasicBlock *PreHeader, BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA, ScalarEvolution &SE, unsigned Count, AssumptionCache &AC, BranchProbability OriginalLoopProb)

Connect the unrolling epilog code to the original loop.

Definition LoopUnrollRuntime.cpp:256

static const uint32_t UnrolledLoopHeaderWeights[]

Definition LoopUnrollRuntime.cpp:63

static Value * CreateTripRemainder(IRBuilder<> &B, Value *BECount, Value *TripCount, unsigned Count)

Calculate ModVal = (BECount + 1) % Count on the abstract integer domain accounting for the possibilit...

Definition LoopUnrollRuntime.cpp:589

static Loop * CloneLoopBlocks(Loop *L, Value *NewIter, const bool UseEpilogRemainder, const bool UnrollRemainder, BasicBlock *InsertTop, BasicBlock *InsertBot, BasicBlock *Preheader, std::vector< BasicBlock * > &NewBlocks, LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI, unsigned Count, std::optional< unsigned > OriginalTripCount, BranchProbability OriginalLoopProb)

Create a clone of the blocks in a loop and connect them together.

Definition LoopUnrollRuntime.cpp:405

static cl::opt< bool > UnrollRuntimeOtherExitPredictable("unroll-runtime-other-exit-predictable", cl::init(false), cl::Hidden, cl::desc("Assume the non latch exit block to be predictable"))

static bool canProfitablyRuntimeUnrollMultiExitLoop(Loop *L, SmallVectorImpl< BasicBlock * > &OtherExits, BasicBlock *LatchExit, bool UseEpilogRemainder)

Returns true if we can profitably unroll the multi-exit loop L.

Definition LoopUnrollRuntime.cpp:541

static const uint32_t EpilogHeaderWeights[]

Definition LoopUnrollRuntime.cpp:68

static cl::opt< bool > UnrollRuntimeMultiExit("unroll-runtime-multi-exit", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolling for loops with multiple exits, when " "epilog is generated"))

static BranchProbability probOfNextInRemainder(BranchProbability OriginalLoopProb, unsigned N)

Assume, due to our position in the remainder loop or its guard, anywhere from 0 to N more iterations ...

Definition LoopUnrollRuntime.cpp:204

static void ConnectProlog(Loop *L, Value *BECount, unsigned Count, BasicBlock *PrologExit, BasicBlock *OriginalLoopLatchExit, BasicBlock *PreHeader, BasicBlock *NewPreHeader, ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA, ScalarEvolution &SE)

Connect the unrolling prolog code to the original loop.

Definition LoopUnrollRuntime.cpp:83

This file contains the declarations for profiling metadata utility functions.

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

#define STATISTIC(VARNAME, DESC)

This represents the llvm.assume intrinsic.

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.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const

Returns an iterator to the first instruction in this block that is not a PHINode instruction.

LLVM_ABI const BasicBlock * getSingleSuccessor() const

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

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.

void setCondition(Value *V)

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)

BranchProbability pow(unsigned N) const

Compute pow(Probability, N).

static BranchProbability getOne()

BranchProbability getCompl() const

This is an important base class in LLVM.

static LLVM_ABI Constant * getAllOnesValue(Type *Ty)

A parsed version of the target data layout string in and methods for querying it.

DomTreeNodeBase * getIDom() const

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

verify - checks if the tree is correct.

void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)

changeImmediateDominator - This method is used to update the dominator tree information when a node's...

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 Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const

Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...

LLVM_ABI CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles={})

Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...

Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)

Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)

Value * CreateIsNotNull(Value *Arg, const Twine &Name="")

Return a boolean value testing if Arg != 0.

void SetInsertPoint(BasicBlock *TheBB)

This specifies that created instructions should be appended to the end of the specified block.

Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified position.

LLVM_ABI InstListType::iterator eraseFromParent()

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

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

LLVM_ABI void setSuccessor(unsigned Idx, BasicBlock *BB)

Update the specified successor to point at the provided block.

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.

ArrayRef< BlockT * > getBlocks() const

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

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

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

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

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

bool replacementPreservesLCSSAForm(Instruction *From, Value *To)

Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.

Represents a single loop in the control flow graph.

void setLoopAlreadyUnrolled()

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

LLVM_ABI MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)

Return metadata containing two branch weights.

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

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

void setIncomingValueForBlock(const BasicBlock *BB, Value *V)

Set every incoming value(s) for block BB to V.

void setIncomingBlock(unsigned i, BasicBlock *BB)

void setIncomingValue(unsigned i, Value *V)

Value * getIncomingValue(unsigned i) const

Return incoming value number x.

int getBasicBlockIndex(const BasicBlock *BB) const

Return the first index of the specified basic block in the value list for this PHI.

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

static LLVM_ABI PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

This class uses information about analyze scalars to rewrite expressions in canonical form.

bool isHighCostExpansion(ArrayRef< const SCEV * > Exprs, Loop *L, unsigned Budget, const TargetTransformInfo *TTI, const Instruction *At)

Return true for expressions that can't be evaluated at runtime within given Budget.

LLVM_ABI Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)

Insert code to directly compute the specified SCEV expression into the program.

This class represents an analyzed expression in the program.

LLVM_ABI Type * getType() const

Return the LLVM type of this SCEV expression.

The main scalar evolution driver.

LLVM_ABI const SCEV * getConstant(ConstantInt *V)

bool loopHasNoAbnormalExits(const Loop *L)

Return true if the loop has no abnormal exits.

LLVM_ABI void forgetTopmostLoop(const Loop *L)

LLVM_ABI void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)

Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...

LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)

Return the number of times the backedge executes before the given exit would be taken; if not exactly...

LLVM_ABI const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Get a canonical add expression, or something simpler if possible.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

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.

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

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

ValueT lookup(const KeyT &Val) const

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

bool erase(const KeyT &Val)

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

LLVM_ABI void setName(const Twine &Name)

Change the name of the value.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

const ParentTy * getParent() const

self_iterator getIterator()

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())

If the specified value is a trivially dead instruction, delete it.

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)

SmallDenseMap< const Loop *, Loop *, 4 > NewLoopsMap

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)

See if we can compute a simplified version of this instruction.

bool setBranchProbability(BranchInst *B, BranchProbability P, bool ForFirstTarget)

Set branch weight metadata for B to indicate that P and 1 - P are the probabilities of control flowin...

LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)

Return true if the result produced by the instruction is not used, and the instruction will return.

unsigned Log2_32(uint32_t Value)

Return the floor log base 2 of the specified value, -1 if the value is zero.

void RemapDbgRecordRange(Module *M, iterator_range< DbgRecordIterator > Range, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)

Remap the Values used in the DbgRecords Range using the value map VM.

constexpr bool isPowerOf2_32(uint32_t Value)

Return true if the argument is a power of two > 0.

LLVM_ABI CallBase * getLoopConvergenceHeart(const Loop *TheLoop)

Find the convergence heart of the loop.

@ RF_IgnoreMissingLocals

If this flag is set, the remapper ignores missing function-local entries (Argument,...

@ RF_NoModuleLevelChanges

If this flag is set, the remapper knows that only local values within a function (such as an instruct...

LLVM_ABI raw_ostream & dbgs()

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

FunctionAddr VTableAddr Count

@ Unmodified

The loop was not modified.

@ FullyUnrolled

The loop was fully unrolled into straight-line code.

LLVM_ABI void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)

Remove the backedge of the specified loop.

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 BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)

This method introduces at least one new basic block into the function and moves some of the predecess...

LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)

Attempts to merge a block into its predecessor, if possible.

LLVM_ABI bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)

Ensure that all exit blocks of the loop are dedicated exits.

void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)

Convert the instruction operands from referencing the current values into those specified by VM.

LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)

Return true if this function can prove that V does not have undef bits and is never poison.

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

LLVM_ABI bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, std::optional< unsigned > EstimatedLoopInvocationWeight=std::nullopt)

Set llvm.loop.estimated_trip_count with the value EstimatedTripCount in the loop metadata of L.

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 BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)

Split the specified block at the specified instruction.

auto predecessors(const MachineBasicBlock *BB)

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

Returns true if Element is found in Range.

LLVM_ABI bool hasBranchWeightMD(const Instruction &I)

Checks if an instructions has Branch Weight Metadata.

LLVM_ABI BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")

Split the edge connecting the specified blocks, and return the newly created basic block between From...

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.

Definition LoopUnrollRuntime.cpp:654

LLVM_ABI LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const llvm::TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr, AAResults *AA=nullptr)

Unroll the given loop by Count.

bool AllowExpensiveTripCount