LoopPeel.cpp Source File (original) (raw)

41#include

42#include

43#include

44#include

46using namespace llvm;

49#define DEBUG_TYPE "loop-peel"

51 STATISTIC(NumPeeled, "Number of loops peeled");

55 cl::desc("Set the unroll peeling count, for testing purposes"));

59 cl::desc("Allows loops to be peeled when the dynamic "

60 "trip count is known to be low."));

65 cl::desc("Allows loop nests to be peeled."));

69 cl::desc("Max average trip count which will cause loop peeling."));

73 cl::desc("Force a peel count regardless of profiling information."));

78 "Disable advance peeling. Issues for convergent targets (D134803)."));

85 if (!L->isLoopSimplifyForm())

86 return false;

88 return true;

91 L->getUniqueNonLatchExitBlocks(Exits);

101}

102

103namespace {

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157class PhiAnalyzer {

158public:

159 PhiAnalyzer(const Loop &L, unsigned MaxIterations);

160

161

162

163 std::optional calculateIterationsToPeel();

164

165protected:

166 using PeelCounter = std::optional;

167 const PeelCounter Unknown = std::nullopt;

168

169

170 PeelCounter addOne(PeelCounter PC) const {

171 if (PC == Unknown)

172 return Unknown;

173 return (*PC + 1 <= MaxIterations) ? PeelCounter{*PC + 1} : Unknown;

174 }

175

176

177

178 PeelCounter calculate(const Value &);

179

181 const unsigned MaxIterations;

182

183

185};

186

187PhiAnalyzer::PhiAnalyzer(const Loop &L, unsigned MaxIterations)

188 : L(L), MaxIterations(MaxIterations) {

189 assert(canPeel(&L) && "loop is not suitable for peeling");

190 assert(MaxIterations > 0 && "no peeling is allowed?");

191}

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207PhiAnalyzer::PeelCounter PhiAnalyzer::calculate(const Value &V) {

208

209

210

211 auto [I, Inserted] = IterationsToInvariance.try_emplace(&V, Unknown);

212 if (!Inserted)

213 return I->second;

214

215 if (L.isLoopInvariant(&V))

216

217 return (IterationsToInvariance[&V] = 0);

218 if (const PHINode *Phi = dyn_cast(&V)) {

219 if (Phi->getParent() != L.getHeader()) {

220

221 assert(IterationsToInvariance[&V] == Unknown && "unexpected value saved");

223 }

224

225 Value *Input = Phi->getIncomingValueForBlock(L.getLoopLatch());

226 PeelCounter Iterations = calculate(*Input);

227 assert(IterationsToInvariance[Input] == Iterations &&

228 "unexpected value saved");

229 return (IterationsToInvariance[Phi] = addOne(Iterations));

230 }

231 if (const Instruction *I = dyn_cast(&V)) {

232 if (isa(I) || I->isBinaryOp()) {

233

234 PeelCounter LHS = calculate(*I->getOperand(0));

237 PeelCounter RHS = calculate(*I->getOperand(1));

240 return (IterationsToInvariance[I] = {std::max(*LHS, *RHS)});

241 }

242 if (I->isCast())

243

244 return (IterationsToInvariance[I] = calculate(*I->getOperand(0)));

245 }

246

247

248

249 assert(IterationsToInvariance[&V] == Unknown && "unexpected value saved");

251}

252

253std::optional PhiAnalyzer::calculateIterationsToPeel() {

254 unsigned Iterations = 0;

255 for (auto &PHI : L.getHeader()->phis()) {

256 PeelCounter ToInvariance = calculate(PHI);

257 if (ToInvariance != Unknown) {

258 assert(*ToInvariance <= MaxIterations && "bad result in phi analysis");

259 Iterations = std::max(Iterations, *ToInvariance);

260 if (Iterations == MaxIterations)

261 break;

262 }

263 }

264 assert((Iterations <= MaxIterations) && "bad result in phi analysis");

265 return Iterations ? std::optional(Iterations) : std::nullopt;

266}

267

268}

269

270

271

272

273

277

278

279 if (L.getExitingBlock())

280 return 0;

281

282

283

285 L.getUniqueNonLatchExitBlocks(Exits);

287 return !isa(BB->getTerminator());

288 }))

289 return 0;

290

291

292

293

294

295

297 BasicBlock *Latch = L.getLoopLatch();

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

302 if (I.mayWriteToMemory())

303 return 0;

304

305 auto Iter = LoadUsers.find(&I);

306 if (Iter != LoadUsers.end()) {

307 for (Value *U : I.users())

309 }

310

311

312 if (BB == Header)

313 continue;

314 if (auto *LI = dyn_cast(&I)) {

315 Value *Ptr = LI->getPointerOperand();

316 if (DT.dominates(BB, Latch) && L.isLoopInvariant(Ptr) &&

318 for (Value *U : I.users())

320 }

321 }

322 }

324 L.getExitingBlocks(ExitingBlocks);

325 if (any_of(ExitingBlocks, [&LoadUsers](BasicBlock *Exiting) {

327 }))

328 return 1;

329 return 0;

330}

331

332

333

334

335

336

337

338

339

340

343 assert(L.isLoopSimplifyForm() && "Loop needs to be in loop simplify form");

344 unsigned DesiredPeelCount = 0;

345

346

348 if (const SCEVConstant *SC = dyn_cast(BE))

349 MaxPeelCount =

350 std::min((unsigned)SC->getAPInt().getLimitedValue() - 1, MaxPeelCount);

351

352

353

354

355 auto PeelWhilePredicateIsKnown =

356 [&](unsigned &PeelCount, const SCEV *&IterVal, const SCEV *BoundSCEV,

358 while (PeelCount < MaxPeelCount &&

360 IterVal = SE.getAddExpr(IterVal, Step);

361 ++PeelCount;

362 }

363 return SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), IterVal,

364 BoundSCEV);

365 };

366

367 const unsigned MaxDepth = 4;

368 std::function<void(Value *, unsigned)> ComputePeelCount =

369 [&](Value *Condition, unsigned Depth) -> void {

371 return;

372

373 Value *LeftVal, *RightVal;

376 ComputePeelCount(LeftVal, Depth + 1);

377 ComputePeelCount(RightVal, Depth + 1);

378 return;

379 }

380

383 return;

384

385 const SCEV *LeftSCEV = SE.getSCEV(LeftVal);

386 const SCEV *RightSCEV = SE.getSCEV(RightVal);

387

388

389

391 return;

392

393

394

395 if (!isa(LeftSCEV)) {

396 if (isa(RightSCEV)) {

398 Pred = ICmpInst::getSwappedPredicate(Pred);

399 } else

400 return;

401 }

402

403 const SCEVAddRecExpr *LeftAR = cast(LeftSCEV);

404

405

406

408 return;

411 return;

412

413

414

415 unsigned NewPeelCount = DesiredPeelCount;

416

419

420

421

422

424 Pred = ICmpInst::getInversePredicate(Pred);

425

427 if (!PeelWhilePredicateIsKnown(NewPeelCount, IterVal, RightSCEV, Step,

428 Pred))

429 return;

430

431

432

433

434 const SCEV *NextIterVal = SE.getAddExpr(IterVal, Step);

436 !SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), NextIterVal,

437 RightSCEV) &&

440 if (NewPeelCount >= MaxPeelCount)

441 return;

442 ++NewPeelCount;

443 }

444

445 DesiredPeelCount = std::max(DesiredPeelCount, NewPeelCount);

446 };

447

449 if ( MinMax ->getType()->isIntegerTy())

450 return;

452 const SCEV *BoundSCEV, *IterSCEV;

453 if (L.isLoopInvariant(LHS)) {

456 } else if (L.isLoopInvariant(RHS)) {

459 } else

460 return;

461 const auto *AddRec = dyn_cast(IterSCEV);

462

463 if (!AddRec || !AddRec->isAffine() || AddRec->getLoop() != &L)

464 return;

465 const SCEV *Step = AddRec->getStepRecurrence(SE);

466 bool IsSigned = MinMax->isSigned();

467

468

471 Pred = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;

473 Pred = IsSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;

474 else

475 return;

476

477 if (!(IsSigned ? AddRec->hasNoSignedWrap() : AddRec->hasNoUnsignedWrap()))

478 return;

479 unsigned NewPeelCount = DesiredPeelCount;

480 const SCEV *IterVal = AddRec->evaluateAtIteration(

481 SE.getConstant(AddRec->getType(), NewPeelCount), SE);

482 if (!PeelWhilePredicateIsKnown(NewPeelCount, IterVal, BoundSCEV, Step,

483 Pred))

484 return;

485 DesiredPeelCount = NewPeelCount;

486 };

487

490 if (SelectInst *SI = dyn_cast(&I))

491 ComputePeelCount(SI->getCondition(), 0);

493 ComputePeelCountMinMax(MinMax);

494 }

495

496 auto *BI = dyn_cast(BB->getTerminator());

497 if (!BI || BI->isUnconditional())

498 continue;

499

500

501 if (L.getLoopLatch() == BB)

502 continue;

503

504 ComputePeelCount(BI->getCondition(), 0);

505 }

506

507 return DesiredPeelCount;

508}

509

510

511

512

513

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

516 if (!Latch)

517 return true;

518

520 if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch))

521 return true;

522

524 LatchBR->getSuccessor(1) == L->getHeader()) &&

525 "At least one edge out of the latch must go to the header");

526

528 L->getUniqueNonLatchExitBlocks(ExitBlocks);

531 });

532}

533

534

535

540 unsigned Threshold) {

541 assert(LoopSize > 0 && "Zero loop size is not allowed!");

542

543

544 unsigned TargetPeelCount = PP.PeelCount;

547 return;

548

549

550

551

553 return;

554

555

557 if (UserPeelCount) {

559 << " iterations.\n");

562 return;

563 }

564

565

567 return;

568

569

570 if (2 * LoopSize > Threshold)

571 return;

572

573 unsigned AlreadyPeeled = 0;

575 AlreadyPeeled = *Peeled;

576

578 return;

579

580

582 MaxPeelCount = std::min(MaxPeelCount, Threshold / LoopSize - 1);

583

584

585

586 unsigned DesiredPeelCount = TargetPeelCount;

587

588

589

590

591

592

593 if (MaxPeelCount > DesiredPeelCount) {

594

595 auto NumPeels = PhiAnalyzer(*L, MaxPeelCount).calculateIterationsToPeel();

596 if (NumPeels)

597 DesiredPeelCount = std::max(DesiredPeelCount, *NumPeels);

598 }

599

600 DesiredPeelCount = std::max(DesiredPeelCount,

602

603 if (DesiredPeelCount == 0)

605

606 if (DesiredPeelCount > 0) {

607 DesiredPeelCount = std::min(DesiredPeelCount, MaxPeelCount);

608

609 assert(DesiredPeelCount > 0 && "Wrong loop size estimation?");

612 << " iteration(s) to turn"

613 << " some Phis into invariants.\n");

616 return;

617 }

618 }

619

620

621

622 if (TripCount)

623 return;

624

625

627 return;

628

629

630

631

632

633 if (L->getHeader()->getParent()->hasProfileData()) {

635 return;

637 if (!EstimatedTripCount)

638 return;

639

640 LLVM_DEBUG(dbgs() << "Profile-based estimated trip count is "

641 << *EstimatedTripCount << "\n");

642

643 if (*EstimatedTripCount) {

644 if (*EstimatedTripCount + AlreadyPeeled <= MaxPeelCount) {

645 unsigned PeelCount = *EstimatedTripCount;

646 LLVM_DEBUG(dbgs() << "Peeling first " << PeelCount << " iterations.\n");

648 return;

649 }

650 LLVM_DEBUG(dbgs() << "Already peel count: " << AlreadyPeeled << "\n");

652 LLVM_DEBUG(dbgs() << "Loop cost: " << LoopSize << "\n");

653 LLVM_DEBUG(dbgs() << "Max peel cost: " << Threshold << "\n");

655 << (Threshold / LoopSize - 1) << "\n");

656 }

657 }

658}

659

661

663

665};

666

667

668

669

670

671

672

673

674

675

676

677

678

679

683 if (SubWeight != 0)

684

685

686

687

689 Info.Weights[Idx] > SubWeight

690 ? std::max(Info.Weights[Idx] - SubWeight, SubWeight)

691 : SubWeight;

692}

693

694

698 L->getExitingBlocks(ExitingBlocks);

699 for (BasicBlock *ExitingBlock : ExitingBlocks) {

700 Instruction *Term = ExitingBlock->getTerminator();

703 continue;

704

705

706

707 uint32_t FallThroughWeights = 0;

709 for (auto [Succ, Weight] : zip(successors(Term), Weights)) {

710 if (L->contains(Succ))

711 FallThroughWeights += Weight;

712 else

713 ExitWeights += Weight;

714 }

715

716

717 if (FallThroughWeights == 0)

718 continue;

719

721 for (auto [Succ, Weight] : zip(successors(Term), Weights)) {

722 if (!L->contains(Succ)) {

723

725 continue;

726 }

727

728

729

730 double W = (double)Weight / (double)FallThroughWeights;

732 }

733

734 WeightInfos.insert({Term, {std::move(Weights), std::move(SubWeights)}});

735 }

736}

737

738

739

740

741

742

743

744

745

746

747

750 SmallVectorImpl<std::pair<BasicBlock *, BasicBlock *>> &ExitEdges,

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

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

758

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

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

763

764

765

769

770

771

772

773 if (ParentLoop && LI->getLoopFor(*BB) == L)

775

776 VMap[*BB] = NewBB;

777

778

779 if (DT) {

780 if (Header == *BB)

782 else {

784

786 }

787 }

788 }

789

790 {

791

792

793

794 std::string Ext = (Twine("Peel") + Twine(IterNumber)).str();

796 Header->getContext(), Ext);

797 }

798

799

800

801 for (Loop *ChildLoop : *L) {

802 cloneLoop(ChildLoop, ParentLoop, VMap, LI, nullptr);

803 }

804

805

806

807

808

810

811

812

813

814

815

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

817 auto *LatchTerm = cast(NewLatch->getTerminator());

818 for (unsigned idx = 0, e = LatchTerm->getNumSuccessors(); idx < e; ++idx)

819 if (LatchTerm->getSuccessor(idx) == Header) {

820 LatchTerm->setSuccessor(idx, InsertBot);

821 break;

822 }

823 if (DT)

825

826

827

828

829

830

831

832

833

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

836 if (IterNumber == 0) {

838 } else {

840 Instruction *LatchInst = dyn_cast(LatchVal);

841 if (LatchInst && L->contains(LatchInst))

842 VMap[&*I] = LVMap[LatchInst];

843 else

844 VMap[&*I] = LatchVal;

845 }

847 }

848

849

850

851

852

853 for (auto Edge : ExitEdges)

854 for (PHINode &PHI : Edge.second->phis()) {

855 Value *LatchVal = PHI.getIncomingValueForBlock(Edge.first);

856 Instruction *LatchInst = dyn_cast(LatchVal);

857 if (LatchInst && L->contains(LatchInst))

858 LatchVal = VMap[LatchVal];

859 PHI.addIncoming(LatchVal, cast(VMap[Edge.first]));

861 }

862

863

864

865 for (auto KV : VMap)

866 LVMap[KV.first] = KV.second;

867}

868

872 std::optional UserAllowPeeling,

873 std::optional UserAllowProfileBasedPeeling,

874 bool UnrollingSpecficValues) {

876

877

882

883

885

886

887 if (UnrollingSpecficValues) {

894 }

895

896

897 if (UserAllowPeeling)

899 if (UserAllowProfileBasedPeeling)

901

902 return PP;

903}

904

905

906

907

908

909

910

911

912

913

917 assert(PeelCount > 0 && "Attempt to peel out zero iterations?");

918 assert(canPeel(L) && "Attempt to peel a loop which is not peelable?");

919

922

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

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

927 L->getExitEdges(ExitEdges);

928

929

930

931

932

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

935 auto *BBDomNode = DT.getNode(BB);

937 for (auto *ChildDomNode : BBDomNode->children()) {

938 auto *ChildBB = ChildDomNode->getBlock();

939 if (!L->contains(ChildBB))

940 ChildrenToUpdate.push_back(ChildBB);

941 }

942

943

944

945

947 for (auto *ChildBB : ChildrenToUpdate)

948 NonLoopBlocksIDom[ChildBB] = NewIDom;

949 }

950

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

952

953

954

955

956

957

958

959

960

961

962

963

964

965

966

967

968

969

970

971

972

973

974

975

976

977

978

979

980

981

982

983

984

985

986

987

988

989

990

991

992

993

994

995

996

997

1003

1004 InsertTop->setName(Header->getName() + ".peel.begin");

1005 InsertBot->setName(Header->getName() + ".peel.next");

1006 NewPreHeader->setName(PreHeader->getName() + ".peel.newph");

1007

1009 cast(cast(Latch)->getTerminator());

1010

1011

1012

1015

1016

1017

1020

1021

1022 for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {

1025

1026 cloneLoopBlocks(L, Iter, InsertTop, InsertBot, ExitEdges, NewBlocks,

1027 LoopBlocks, VMap, LVMap, &DT, LI,

1028 LoopLocalNoAliasDeclScopes, *SE);

1029

1030

1031

1033

1034

1035 if (Iter == 0)

1036 for (auto BBIDom : NonLoopBlocksIDom)

1038 cast(LVMap[BBIDom.second]));

1039#ifdef EXPENSIVE_CHECKS

1040 assert(DT.verify(DominatorTree::VerificationLevel::Fast));

1041#endif

1042

1043 for (auto &[Term, Info] : Weights) {

1044 auto *TermCopy = cast(VMap[Term]);

1046 }

1047

1048

1049

1050 auto *LatchTermCopy = cast(VMap[LatchTerm]);

1051 LatchTermCopy->setMetadata(LLVMContext::MD_loop, nullptr);

1052

1053 InsertTop = InsertBot;

1055 InsertBot->setName(Header->getName() + ".peel.next");

1056

1057 F->splice(InsertTop->getIterator(), F, NewBlocks[0]->getIterator(),

1058 F->end());

1059 }

1060

1061

1062

1065 Value *NewVal = PHI->getIncomingValueForBlock(Latch);

1066 Instruction *LatchInst = dyn_cast(NewVal);

1067 if (LatchInst && L->contains(LatchInst))

1068 NewVal = LVMap[LatchInst];

1069

1070 PHI->setIncomingValueForBlock(NewPreHeader, NewVal);

1071 }

1072

1073 for (const auto &[Term, Info] : Weights) {

1075 }

1076

1077

1078 unsigned AlreadyPeeled = 0;

1080 AlreadyPeeled = *Peeled;

1082

1083 if (Loop *ParentLoop = L->getParentLoop())

1084 L = ParentLoop;

1085

1086

1089

1090#ifdef EXPENSIVE_CHECKS

1091

1092 assert(DT.verify(DominatorTree::VerificationLevel::Fast));

1093#endif

1094

1095

1096 simplifyLoop(L, &DT, LI, SE, AC, nullptr, PreserveLCSSA);

1097

1098 NumPeeled++;

1099

1100 return true;

1101}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Analysis containing CSE Info

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

This file defines the DenseMap class.

static void updateBranchWeights(Instruction *Term, WeightInfo &Info)

Update the branch weights of an exiting block of a peeled-off loop iteration.

static cl::opt< bool > DisableAdvancedPeeling("disable-advanced-peeling", cl::init(false), cl::Hidden, cl::desc("Disable advance peeling. Issues for convergent targets (D134803)."))

static cl::opt< unsigned > UnrollPeelMaxCount("unroll-peel-max-count", cl::init(7), cl::Hidden, cl::desc("Max average trip count which will cause loop peeling."))

static cl::opt< bool > UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden, cl::desc("Allows loops to be peeled when the dynamic " "trip count is known to be low."))

static cl::opt< unsigned > UnrollForcePeelCount("unroll-force-peel-count", cl::init(0), cl::Hidden, cl::desc("Force a peel count regardless of profiling information."))

static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount, ScalarEvolution &SE)

static bool violatesLegacyMultiExitLoopCheck(Loop *L)

This "heuristic" exactly matches implicit behavior which used to exist inside getLoopEstimatedTripCou...

static const char * PeeledCountMetaData

static void cloneLoopBlocks(Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot, SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * > > &ExitEdges, SmallVectorImpl< BasicBlock * > &NewBlocks, LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT, LoopInfo *LI, ArrayRef< MDNode * > LoopLocalNoAliasDeclScopes, ScalarEvolution &SE)

Clones the body of the loop L, putting it between InsertTop and InsertBot.

static cl::opt< bool > UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling", cl::init(false), cl::Hidden, cl::desc("Allows loop nests to be peeled."))

static cl::opt< unsigned > UnrollPeelCount("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes"))

static unsigned peelToTurnInvariantLoadsDerefencebale(Loop &L, DominatorTree &DT, AssumptionCache *AC)

static void initBranchWeights(DenseMap< Instruction *, WeightInfo > &WeightInfos, Loop *L)

Initialize the weights for all exiting blocks.

This file contains the declarations for profiling metadata utility functions.

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

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)

This pass exposes codegen information to IR-level passes.

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

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

LLVM Basic Block Representation.

const CallInst * getTerminatingDeoptimizeCall() const

Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...

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

BasicBlock * getSuccessor(unsigned i) const

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...

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

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

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

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

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

bool isEquality() const

Return true if this predicate is either EQ or NE.

InstListType::iterator eraseFromParent()

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

void setSuccessor(unsigned Idx, BasicBlock *BB)

Update the specified successor to point at the provided block.

void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)

This method is used by other analyses to update loop information.

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

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Represents a single loop in the control flow graph.

This class represents min/max intrinsics.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

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

const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const

Return the value of this chain of recurrences at the specified iteration number.

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

Constructs and returns the recurrence indicating how much this expression steps by.

bool isAffine() const

Return true if this represents an expression A + B*x where A and B are loop invariant values.

const Loop * getLoop() const

This class represents a constant integer value.

bool hasNoSelfWrap() const

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 * getConstantMaxBackedgeTakenCount(const Loop *L)

When successful, this returns a SCEVConstant that is greater than or equal to (i.e.

bool isKnownNegative(const SCEV *S)

Test if the given expression is known to be negative.

const SCEV * getConstant(ConstantInt *V)

const SCEV * getSCEV(Value *V)

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

bool isKnownPositive(const SCEV *S)

Test if the given expression is known to be positive.

void forgetTopmostLoop(const Loop *L)

void forgetBlockAndLoopDispositions(Value *V=nullptr)

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

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

std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)

If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...

std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)

Check whether the condition described by Pred, LHS, and RHS is true or false.

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.

bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)

Test if the given expression is known to satisfy the condition described by Pred, LHS,...

This class represents the LLVM 'select' instruction.

iterator find(ConstPtrType Ptr) const

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

bool contains(ConstPtrType Ptr) const

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

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

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.

void getPeelingPreferences(Loop *L, ScalarEvolution &SE, PeelingPreferences &PP) const

Get target-customized preferences for the generic loop peeling transformation.

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

bool isIntegerTy() const

True if this is an instance of IntegerType.

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

self_iterator getIterator()

BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)

bool match(Val *V, const Pattern &P)

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)

BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)

initializer< Ty > init(const Ty &Val)

NodeAddr< PhiNode * > Phi

This is an optimization pass for GlobalISel generic memory operations.

bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)

Simplify each loop in a loop nest recursively.

detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)

zip iterator for two or more iteratable types.

std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)

Returns a loop's estimated trip count based on branch weight metadata.

bool all_of(R &&range, UnaryPredicate P)

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

bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)

Check if we can prove that all paths starting from this block converge to a block that either has a @...

void computePeelCount(Loop *L, unsigned LoopSize, TargetTransformInfo::PeelingPreferences &PP, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE, AssumptionCache *AC=nullptr, unsigned Threshold=UINT_MAX)

auto enumerate(FirstRange &&First, RestRanges &&...Rest)

Given two or more input ranges, returns a new range whose values are tuples (A, B,...

auto successors(const MachineBasicBlock *BB)

bool canPeel(const Loop *L)

void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)

Set input string into loop metadata by keeping other values intact.

bool any_of(R &&range, UnaryPredicate P)

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

void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected)

Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...

TargetTransformInfo::PeelingPreferences gatherPeelingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, std::optional< bool > UserAllowPeeling, std::optional< bool > UserAllowProfileBasedPeeling, bool UnrollingSpecficValues=false)

raw_ostream & dbgs()

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

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

Find named metadata for a loop with an integer value.

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

void cloneAndAdaptNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, ArrayRef< BasicBlock * > NewBlocks, LLVMContext &Context, StringRef Ext)

Clone the specified noalias decl scopes.

void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)

Remaps instructions in Blocks using the mapping in VMap.

bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)

Return true if this is always a dereferenceable pointer.

bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)

Extract branch weights from MD_prof metadata.

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.

void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)

Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...

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

bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, DominatorTree &DT, AssumptionCache *AC, bool PreserveLCSSA, ValueToValueMapTy &VMap)

VMap is the value-map that maps instructions from the original loop to instructions in the last peele...

Loop * cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)

Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...

Implement std::hash so that hash_code can be used in STL containers.

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

Implement std::swap in terms of BitVector swap.

SmallVector< uint32_t > Weights

const SmallVector< uint32_t > SubWeights

bool AllowPeeling

Allow peeling off loop iterations.

bool AllowLoopNestsPeeling

Allow peeling off loop iterations for loop nests.

bool PeelProfiledIterations

Allow peeling basing on profile.

unsigned PeelCount

A forced peeling factor (the number of bodied of the original loop that should be peeled off before t...