LoopUnrollRuntime.cpp Source File (original) (raw)

44using namespace llvm;

46#define DEBUG_TYPE "loop-unroll"

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

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

53 "epilog is generated"));

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

87 LoopInfo *LI, bool PreserveLCSSA,

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

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

102 BasicBlock *PrologLatch = cast(VMap[Latch]);

103

104

105

106

107

108

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

111

112

113

114

115

116

117

120

121

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

123

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

125 PreHeader);

126 } else {

127

129 }

130

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

132 if (Instruction *I = dyn_cast(V)) {

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

135 }

136 }

137

138

140

141

142

143

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

145 PN.setIncomingValueForBlock(NewPreHeader, NewPN);

146 else

147 PN.addIncoming(NewPN, PrologExit);

149 }

150 }

151

152

155 if (PrologLoop) {

157 if (PrologLoop->contains(PredBB))

158 PrologExitPreds.push_back(PredBB);

159

161 nullptr, PreserveLCSSA);

162 }

163

164

165

168

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

170

171

172

173

174

175 Value *BrLoopExit =

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

177

180 nullptr, PreserveLCSSA);

181

182 MDNode *BranchWeights = nullptr;

184

187 }

188 B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader,

189 BranchWeights);

191 if (DT) {

193 PrologExit);

195 }

196}

197

198

199

200

201

202

203

204

205

206

207

208

209

215 unsigned Count) {

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

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

218 BasicBlock *EpilogLatch = cast(VMap[Latch]);

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

236

237

238

239

240

241

242

243

244

245

246

247

248

249

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

251 PHINode *EpilogPN = cast(PN.use_begin()->getUser());

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

253

254

257

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

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

261

263

264

266

268 "EpilogPN should have EpilogPreHeader incoming block");

269

271 NewExit);

272

273

274

275

276

277

278 }

279

280

281

283

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

285 continue;

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

287

288

291

292 NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader), PreHeader);

293

294 NewPN->addIncoming(PN.getIncomingValueForBlock(Latch), Latch);

295

296

297

298 PHINode *VPN = cast(VMap[&PN]);

300 }

301 }

302

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

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

307

310 PreserveLCSSA);

311

312 MDNode *BranchWeights = nullptr;

314

317 }

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

320 if (DT) {

323 }

324

325

328 PreserveLCSSA);

329}

330

331

332

333

334

335

336

339 const bool UnrollRemainder,

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

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

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

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

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

353 NewLoops[ParentLoop] = ParentLoop;

354

355

356

359 NewBlocks.push_back(NewBB);

360

362

363 VMap[*BB] = NewBB;

364 if (Header == *BB) {

365

366

368 }

369

370 if (DT) {

371 if (Header == *BB) {

372

374 } else {

375

377 DT->addNewBlock(NewBB, cast(VMap[IDomBB]));

378 }

379 }

380

381 if (Latch == *BB) {

382

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

384

385

386

387 BasicBlock *FirstLoopBB = cast(VMap[Header]);

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

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

398 MDNode *BranchWeights = nullptr;

402 if (Count >= 3) {

403

404

405

406 ExitWeight = 1;

407 BackEdgeWeight = (Count - 2) / 2;

408 } else {

409

410

411 ExitWeight = 1;

412 BackEdgeWeight = 0;

413 }

416 }

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

421 }

422 }

423

424

425

427 PHINode *NewPHI = cast(VMap[&*I]);

430 BasicBlock *NewLatch = cast(VMap[Latch]);

436 }

437

438 Loop *NewLoop = NewLoops[L];

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

441

442

443

444 if (UnrollRemainder)

445 return NewLoop;

446

449 if (NewLoopID) {

451

452

453

454 return NewLoop;

455 }

456

457

459 return NewLoop;

460}

461

462

463

466 bool UseEpilogRemainder) {

467

468

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

488 L->getExitingBlocks(ExitingBlocks);

489 if (ExitingBlocks.size() > 2)

490 return false;

491

492

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

494 return true;

495

496

497

498

499

500

501

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

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

505

506

507

508

509}

510

511

512

513

514

515

517 Value *TripCount, unsigned Count) {

518

520

521

522

523

524

525

526

527

528

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

530

531

532

533 Constant *CountC = ConstantInt::get(BECount->getType(), Count);

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

535 Value *ModValAdd = B.CreateAdd(ModValTmp,

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

537

538

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

540}

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

582 Loop *L, unsigned Count, bool AllowExpensiveTripCount,

583 bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV,

586 unsigned SCEVExpansionBudget, Loop **ResultLoop) {

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

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

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

591

592

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

595 return false;

596 }

597

598

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

601

603

605

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

609 return false;

610 }

611

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

614

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

616

617

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

621 return false;

622 }

623

624

626 L->getUniqueNonLatchExitBlocks(OtherExits);

627

628

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

630

631

632 if (!PreserveLCSSA)

633 return false;

634

636 UseEpilogRemainder)) {

639 << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "

640 "enabled!\n");

641 return false;

642 }

643 }

644

645

646 if (!SE)

647 return false;

648

649

650

651

652

653

655 if (isa(BECountSC)) {

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

657 return false;

658 }

659

660 unsigned BEWidth = cast(BECountSC->getType())->getBitWidth();

661

662

663

664 const SCEV *TripCountSC =

666 if (isa(TripCountSC)) {

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

668 return false;

669 }

670

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

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

675 if (!AllowExpensiveTripCount &&

677 PreHeaderBR)) {

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

679 return false;

680 }

681

682

683

684 if (Log2_32(Count) > BEWidth) {

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

688 return false;

689 }

690

691

692

693

694

695

696

697

698

702 BasicBlock *EpilogPreHeader = nullptr;

703 BasicBlock *PrologPreHeader = nullptr;

704

705 if (UseEpilogRemainder) {

706

707

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

710

712 nullptr, PreserveLCSSA);

713

714

715

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

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

718

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

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

721

722

723

724

725

726

727

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

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

730 LI->removeBlock(NewExit);

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

732 LI->removeBlock(EpilogPreHeader);

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

734 }

735

736 } else {

737

738

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

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

742 DT, LI);

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

744

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

747 }

748

749

750

751

752

753

754

755

756

757

758

759

760

761

762

763

764 PreHeaderBR = cast(PreHeader->getTerminator());

767 PreHeaderBR);

769

770

771

772

773

774

777 TripCount = B.CreateFreeze(TripCount);

778 BECount =

780 } else {

781

782

783 BECount =

785 }

786

788

789 Value *BranchVal =

790 UseEpilogRemainder ? B.CreateICmpULT(BECount,

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

792 Count - 1)) :

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

794 BasicBlock *RemainderLoop = UseEpilogRemainder ? NewExit : PrologPreHeader;

795 BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;

796

797 MDNode *BranchWeights = nullptr;

799

802 }

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

805 if (DT) {

806 if (UseEpilogRemainder)

808 else

810 }

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

812

813

816

817

818

819

820

821

822 std::vector<BasicBlock *> NewBlocks;

824

825

826

827

828 BasicBlock *InsertBot = UseEpilogRemainder ? LatchExit : PrologExit;

829 BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;

831 L, ModVal, UseEpilogRemainder, UnrollRemainder, InsertTop, InsertBot,

832 NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI, Count);

833

834

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

836

837

838

839

840

841 for (auto *BB : OtherExits) {

842

843

844

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

846 unsigned oldNumOperands = PN.getNumIncomingValues();

847

848

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

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

851 if (PredBB == Latch)

852

853 continue;

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

855

856

857 continue;

858

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

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

861 if (L->contains(I))

863 PN.addIncoming(V, cast(VMap[PredBB]));

864 }

865 }

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

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

870 }

871#endif

872 }

873

874

875

876

877

878

879

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

882

883

884

885

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

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

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

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

890 if (!L->contains(LI->getLoopFor(DomChildBB)))

891 ChildrenToUpdate.push_back(DomChildBB);

892 }

893 }

894 for (auto *BB : ChildrenToUpdate)

896 }

897

898

899

900

901

902

903

904

905

906

907

908

909

910

911

912

913

914

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

922 }

923 }

924

925 if (UseEpilogRemainder) {

926

927

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

929 NewPreHeader, VMap, DT, LI, PreserveLCSSA, *SE, Count);

930

931

932

933

934

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

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

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

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

944 auto Pred = LatchBR->getSuccessor(0) == Header ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ;

949 } else {

950

951

952 ConnectProlog(L, BECount, Count, PrologExit, LatchExit, PreHeader,

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

954 }

955

956

957

959

960

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

962 if (DT) {

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

965 }

966#endif

967

968

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

970

971

973 assert(RemainderLatch);

976 remainderLoop = nullptr;

977

978

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

981 for (BasicBlock *BB : RemainderBlocks) {

985 Inst.replaceAllUsesWith(V);

988 }

989

990

991

993 }

994

995

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

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

1000 }

1001

1002

1003

1004

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

1006

1007

1009

1010

1011 if (remainderLoop)

1013 }

1014

1015 auto UnrollResult = LoopUnrollResult::Unmodified;

1016 if (remainderLoop && UnrollRemainder) {

1019 ULO.Count = Count - 1;

1020 ULO.Force = false;

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

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

1028 nullptr, PreserveLCSSA);

1029 }

1030

1031 if (ResultLoop && UnrollResult != LoopUnrollResult::FullyUnrolled)

1032 *ResultLoop = remainderLoop;

1033 NumRuntimeUnrolled++;

1034 return true;

1035}

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 bool canProfitablyUnrollMultiExitLoop(Loop *L, SmallVectorImpl< BasicBlock * > &OtherExits, BasicBlock *LatchExit, bool UseEpilogRemainder)

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

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)

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

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)

Connect the unrolling epilog code to the original loop.

static const uint32_t UnrolledLoopHeaderWeights[]

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

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 const uint32_t EpilogHeaderWeights[]

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

This file contains the declarations for profiling metadata utility functions.

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

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 Basic Block Representation.

iterator_range< const_phi_iterator > phis() const

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

InstListType::const_iterator getFirstNonPHIIt() const

Iterator returning form of getFirstNonPHI.

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

This is an important base class in LLVM.

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

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

Value * CreateICmpNE(Value *LHS, Value *RHS, const Twine &Name="")

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

BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)

Create a conditional 'br Cond, TrueDest, FalseDest' instruction.

LLVMContext & getContext() const

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

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

void insertBefore(Instruction *InsertPos)

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

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.

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.

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.

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 setLoopID(MDNode *LoopID) const

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

void setLoopAlreadyUnrolled()

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

MDNode * getLoopID() const

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

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

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.

Type * getType() const

Return the LLVM type of this SCEV expression.

The main scalar evolution driver.

const SCEV * getConstant(ConstantInt *V)

bool loopHasNoAbnormalExits(const Loop *L)

Return true if the loop has no abnormal exits.

void forgetTopmostLoop(const Loop *L)

void forgetValue(Value *V)

This method should be called by the client when it has changed a value in a way that may effect its v...

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

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

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.

void setName(const Twine &Name)

Change the name of the value.

StringRef getName() const

Return a constant reference to the value's name.

int getNumOccurrences() const

const ParentTy * getParent() const

self_iterator getIterator()

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

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.

auto successors(const MachineBasicBlock *BB)

std::optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)

Create a new loop identifier for a loop created from a loop transformation.

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

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, Loop **ResultLoop=nullptr)

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

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

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

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.

constexpr bool isPowerOf2_32(uint32_t Value)

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

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

raw_ostream & dbgs()

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

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

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

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

Remove the backedge of the specified loop.

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

const char *const LLVMLoopUnrollFollowupAll

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

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

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.

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

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

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.

const char *const LLVMLoopUnrollFollowupRemainder

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

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.

bool hasBranchWeightMD(const Instruction &I)

Checks if an instructions has Branch Weight Metadata.

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

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.

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

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

bool AllowExpensiveTripCount