LoopConstrainer.cpp Source File (original) (raw)

11using namespace llvm;

13static const char *ClonedLoopTag = "loop_constrainer.loop.clone";

15#define DEBUG_TYPE "loop-constrainer"

21 unsigned LatchBrExitIdx, Loop *L,

23 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&

24 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)

25 return false;

28 return false;

32 LLVM_DEBUG(dbgs() << "isSafeDecreasingBound with:\n");

35 LLVM_DEBUG(dbgs() << "BoundSCEV: " << *BoundSCEV << "\n");

37 LLVM_DEBUG(dbgs() << "LatchExitBrIdx: " << LatchBrExitIdx << "\n");

39 bool IsSigned = ICmpInst::isSigned(Pred);

48 if (LatchBrExitIdx == 1)

51 assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be either 0 or 1");

54 unsigned BitWidth = cast(BoundSCEV->getType())->getBitWidth();

59 const SCEV *MinusOne =

64}

70 unsigned LatchBrExitIdx, Loop *L,

72 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&

73 Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)

74 return false;

77 return false;

79 LLVM_DEBUG(dbgs() << "isSafeIncreasingBound with:\n");

82 LLVM_DEBUG(dbgs() << "BoundSCEV: " << *BoundSCEV << "\n");

84 LLVM_DEBUG(dbgs() << "LatchExitBrIdx: " << LatchBrExitIdx << "\n");

86 bool IsSigned = ICmpInst::isSigned(Pred);

95 if (LatchBrExitIdx == 1)

98 assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be 0 or 1");

101 unsigned BitWidth = cast(BoundSCEV->getType())->getBitWidth();

105

109}

110

111

112

113

114

116 const Loop &L) {

117 const SCEV *FromBlock =

119 if (isa(FromBlock))

121 return FromBlock;

122}

123

124std::optional

126 bool AllowUnsignedLatchCond,

127 const char *&FailureReason) {

128 if (!L.isLoopSimplifyForm()) {

129 FailureReason = "loop not in LoopSimplify form";

130 return std::nullopt;

131 }

132

134 assert(Latch && "Simplified loops only have one latch!");

135

137 FailureReason = "loop has already been cloned";

138 return std::nullopt;

139 }

140

141 if (!L.isLoopExiting(Latch)) {

142 FailureReason = "no loop latch";

143 return std::nullopt;

144 }

145

147 BasicBlock *Preheader = L.getLoopPreheader();

148 if (!Preheader) {

149 FailureReason = "no preheader";

150 return std::nullopt;

151 }

152

155 FailureReason = "latch terminator not conditional branch";

156 return std::nullopt;

157 }

158

160

163 FailureReason = "latch terminator branch not conditional on integral icmp";

164 return std::nullopt;

165 }

166

168 if (isa(MaxBETakenCount)) {

169 FailureReason = "could not compute latch count";

170 return std::nullopt;

171 }

174 "loop variant exit count doesn't make sense!");

175

178 const SCEV *LeftSCEV = SE.getSCEV(LeftValue);

180

182 const SCEV *RightSCEV = SE.getSCEV(RightValue);

183

184

185 if (!isa(LeftSCEV)) {

186 if (isa(RightSCEV)) {

188 std::swap(LeftValue, RightValue);

190 } else {

191 FailureReason = "no add recurrences in the icmp";

192 return std::nullopt;

193 }

194 }

195

196 auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {

198 return true;

199

200 IntegerType *Ty = cast(AR->getType());

203

206 if (ExtendAfterOp) {

208 const SCEV *ExtendedStep =

210

211 bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&

213

214 if (NoSignedWrap)

215 return true;

216 }

217

218

220 };

221

222

223

224

227 FailureReason = "LHS in cmp is not an AddRec for this loop";

228 return std::nullopt;

229 }

231 FailureReason = "LHS in icmp not induction variable";

232 return std::nullopt;

233 }

234 const SCEV *StepRec = IndVarBase->getStepRecurrence(SE);

235 if (!isa(StepRec)) {

236 FailureReason = "LHS in icmp not induction variable";

237 return std::nullopt;

238 }

240

242 FailureReason = "LHS in icmp needs nsw for equality predicates";

243 return std::nullopt;

244 }

245

247 bool IsIncreasing = !StepCI->isNegative();

253

254 const SCEV *FixedRightSCEV = nullptr;

255

256

257

258 if (auto *I = dyn_cast(RightValue))

259 if (L.contains(I->getParent()))

260 FixedRightSCEV = RightSCEV;

261

262 if (IsIncreasing) {

263 bool DecreasedRightValueByOne = false;

264 if (StepCI->isOne()) {

265

267

268

269

270

271

272

276 else

279

280

281

282

283

287 RightSCEV =

289 DecreasedRightValueByOne = true;

290 } else if (cannotBeMinInLoop(RightSCEV, &L, SE, true)) {

292 RightSCEV =

294 DecreasedRightValueByOne = true;

295 }

296 }

297 }

298

301 bool FoundExpectedPred =

303

304 if (!FoundExpectedPred) {

305 FailureReason = "expected icmp slt semantically, found something else";

306 return std::nullopt;

307 }

308

311 FailureReason = "unsigned latch conditions are explicitly prohibited";

312 return std::nullopt;

313 }

314

317 FailureReason = "Unsafe loop bounds";

318 return std::nullopt;

319 }

321

322

323 if (!DecreasedRightValueByOne)

324 FixedRightSCEV =

326 } else {

327 assert(!DecreasedRightValueByOne &&

328 "Right value can be decreased only for LatchBrExitIdx == 0!");

329 }

330 } else {

331 bool IncreasedRightValueByOne = false;

333

335

336

337

338

339

340

343

344

345

346

347

352 IncreasedRightValueByOne = true;

353 } else if (cannotBeMaxInLoop(RightSCEV, &L, SE, true)) {

356 IncreasedRightValueByOne = true;

357 }

358 }

359 }

360

363

364 bool FoundExpectedPred =

366

367 if (!FoundExpectedPred) {

368 FailureReason = "expected icmp sgt semantically, found something else";

369 return std::nullopt;

370 }

371

374

376 FailureReason = "unsigned latch conditions are explicitly prohibited";

377 return std::nullopt;

378 }

379

382 FailureReason = "Unsafe bounds";

383 return std::nullopt;

384 }

385

387

388

389 if (!IncreasedRightValueByOne)

390 FixedRightSCEV =

392 } else {

393 assert(!IncreasedRightValueByOne &&

394 "Right value can be increased only for LatchBrExitIdx == 0!");

395 }

396 }

398

399 assert(!L.contains(LatchExit) && "expected an exit block!");

403

404 if (FixedRightSCEV)

405 RightValue =

407

409 IndVarStartV->setName("indvar.start");

410

412

413 Result.Tag = "main";

414 Result.Header = Header;

415 Result.Latch = Latch;

416 Result.LatchBr = LatchBr;

419 Result.IndVarStart = IndVarStartV;

420 Result.IndVarStep = StepCI;

421 Result.IndVarBase = LeftValue;

422 Result.IndVarIncreasing = IsIncreasing;

423 Result.LoopExitAt = RightValue;

425 Result.ExitCountTy = cast(MaxBETakenCount->getType());

426

427 FailureReason = nullptr;

428

429 return Result;

430}

431

432

433

435

436

437 LLVMContext &Context = L.getHeader()->getContext();

438

441 Context, {MDString::get(Context, "llvm.loop.unroll.disable")});

445 Context,

446 {MDString::get(Context, "llvm.loop.vectorize.enable"), FalseVal});

448 Context, {MDString::get(Context, "llvm.loop.licm_versioning.disable")});

450 Context,

451 {MDString::get(Context, "llvm.loop.distribute.enable"), FalseVal});

453 MDNode::get(Context, {Dummy, DisableUnroll, DisableVectorize,

454 DisableLICMVersioning, DisableDistribution});

455

457 L.setLoopID(NewLoopID);

458}

459

464 : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()), SE(SE),

465 DT(DT), LI(LI), LPMAddNewLoop(LPMAddNewLoop), OriginalLoop(L), RangeTy(T),

466 MainLoopStructure(LS), SR(SR) {}

467

468void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,

469 const char *Tag) const {

472 Result.Blocks.push_back(Clone);

473 Result.Map[BB] = Clone;

474 }

475

476 auto GetClonedValue = [&Result](Value *V) {

477 assert(V && "null values not in domain!");

478 auto It = Result.Map.find(V);

479 if (It == Result.Map.end())

480 return V;

481 return static_cast<Value *>(It->second);

482 };

483

484 auto *ClonedLatch =

485 cast(GetClonedValue(OriginalLoop.getLoopLatch()));

486 ClonedLatch->getTerminator()->setMetadata(ClonedLoopTag,

488

489 Result.Structure = MainLoopStructure.map(GetClonedValue);

491

492 for (unsigned i = 0, e = Result.Blocks.size(); i != e; ++i) {

495

496 assert(Result.Map[OriginalBB] == ClonedBB && "invariant!");

497

501

502

503

504

505

506 for (auto *SBB : successors(OriginalBB)) {

507 if (OriginalLoop.contains(SBB))

508 continue;

509

511 Value *OldIncoming = PN.getIncomingValueForBlock(OriginalBB);

512 PN.addIncoming(GetClonedValue(OldIncoming), ClonedBB);

514 }

515 }

516 }

517}

518

519LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(

521 BasicBlock *ContinuationBlock) const {

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

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

581

582

583

584

585

586

587

588

589

590

591

592

593 RewrittenRangeInfo RRI;

594

595 BasicBlock *BBInsertLocation = LS.Latch->getNextNode();

597 &F, BBInsertLocation);

599 BBInsertLocation);

600

602 bool Increasing = LS.IndVarIncreasing;

603 bool IsSignedPredicate = LS.IsSignedPredicate;

604

606 auto NoopOrExt = [&](Value *V) {

607 if (V->getType() == RangeTy)

608 return V;

609 return IsSignedPredicate ? B.CreateSExt(V, RangeTy, "wide." + V->getName())

610 : B.CreateZExt(V, RangeTy, "wide." + V->getName());

611 };

612

613

614 Value *EnterLoopCond = nullptr;

615 auto Pred =

616 Increasing

619 Value *IndVarStart = NoopOrExt(LS.IndVarStart);

620 EnterLoopCond = B.CreateICmp(Pred, IndVarStart, ExitSubloopAt);

621

622 B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);

624

625 LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);

626 B.SetInsertPoint(LS.LatchBr);

627 Value *IndVarBase = NoopOrExt(LS.IndVarBase);

628 Value *TakeBackedgeLoopCond = B.CreateICmp(Pred, IndVarBase, ExitSubloopAt);

629

630 Value *CondForBranch = LS.LatchBrExitIdx == 1

631 ? TakeBackedgeLoopCond

632 : B.CreateNot(TakeBackedgeLoopCond);

633

634 LS.LatchBr->setCondition(CondForBranch);

635

636 B.SetInsertPoint(RRI.ExitSelector);

637

638

639

640

641 Value *LoopExitAt = NoopOrExt(LS.LoopExitAt);

642 Value *IterationsLeft = B.CreateICmp(Pred, IndVarBase, LoopExitAt);

643 B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);

644

647

648

649

650

651 for (PHINode &PN : LS.Header->phis()) {

654

655 NewPHI->addIncoming(PN.getIncomingValueForBlock(Preheader), Preheader);

656 NewPHI->addIncoming(PN.getIncomingValueForBlock(LS.Latch),

657 RRI.ExitSelector);

658 RRI.PHIValuesAtPseudoExit.push_back(NewPHI);

659 }

660

663 RRI.IndVarEnd->addIncoming(IndVarStart, Preheader);

664 RRI.IndVarEnd->addIncoming(IndVarBase, RRI.ExitSelector);

665

666

667

668 LS.LatchExit->replacePhiUsesWith(LS.Latch, RRI.ExitSelector);

669

670 return RRI;

671}

672

673void LoopConstrainer::rewriteIncomingValuesForPHIs(

675 const LoopConstrainer::RewrittenRangeInfo &RRI) const {

676 unsigned PHIIndex = 0;

677 for (PHINode &PN : LS.Header->phis())

678 PN.setIncomingValueForBlock(ContinuationBlock,

679 RRI.PHIValuesAtPseudoExit[PHIIndex++]);

680

681 LS.IndVarStart = RRI.IndVarEnd;

682}

683

686 const char *Tag) const {

689

690 LS.Header->replacePhiUsesWith(OldPreheader, Preheader);

691

692 return Preheader;

693}

694

697 if (!ParentLoop)

698 return;

699

702}

703

704Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,

706 bool IsSubloop) {

708 if (Parent)

710 else

712 LPMAddNewLoop(&New, IsSubloop);

713

714

715 for (auto *BB : Original->blocks())

717 New.addBasicBlockToLoop(cast(VM[BB]), LI);

718

719

720 for (Loop *SubLoop : *Original)

721 createClonedLoopStructure(SubLoop, &New, VM, true);

722

723 return &New;

724}

725

728 assert(Preheader != nullptr && "precondition!");

729

730 OriginalPreheader = Preheader;

731 MainLoopPreheader = Preheader;

734 IntegerType *IVTy = cast(RangeTy);

735

738

739

740

741

742 ClonedLoop PreLoop, PostLoop;

743 bool NeedsPreLoop =

745 bool NeedsPostLoop =

747

748 Value *ExitPreLoopAt = nullptr;

749 Value *ExitMainLoopAt = nullptr;

751 cast(SE.getConstant(IVTy, -1, true ));

752

753 if (NeedsPreLoop) {

754 const SCEV *ExitPreLoopAtSCEV = nullptr;

755

756 if (Increasing)

757 ExitPreLoopAtSCEV = *SR.LowLimit;

759 IsSignedPredicate))

761 else {

762 LLVM_DEBUG(dbgs() << "could not prove no-overflow when computing "

763 << "preloop exit limit. HighLimit = "

765 return false;

766 }

767

768 if (!Expander.isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt)) {

769 LLVM_DEBUG(dbgs() << "could not prove that it is safe to expand the"

770 << " preloop exit limit " << *ExitPreLoopAtSCEV

771 << " at block " << InsertPt->getParent()->getName()

772 << "\n");

773 return false;

774 }

775

776 ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);

777 ExitPreLoopAt->setName("exit.preloop.at");

778 }

779

780 if (NeedsPostLoop) {

781 const SCEV *ExitMainLoopAtSCEV = nullptr;

782

783 if (Increasing)

784 ExitMainLoopAtSCEV = *SR.HighLimit;

786 IsSignedPredicate))

788 else {

789 LLVM_DEBUG(dbgs() << "could not prove no-overflow when computing "

790 << "mainloop exit limit. LowLimit = "

792 return false;

793 }

794

795 if (!Expander.isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt)) {

796 LLVM_DEBUG(dbgs() << "could not prove that it is safe to expand the"

797 << " main loop exit limit " << *ExitMainLoopAtSCEV

798 << " at block " << InsertPt->getParent()->getName()

799 << "\n");

800 return false;

801 }

802

803 ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);

804 ExitMainLoopAt->setName("exit.mainloop.at");

805 }

806

807

808

809 if (NeedsPreLoop)

810 cloneLoop(PreLoop, "preloop");

811 if (NeedsPostLoop)

812 cloneLoop(PostLoop, "postloop");

813

814 RewrittenRangeInfo PreLoopRRI;

815

816 if (NeedsPreLoop) {

818 PreLoop.Structure.Header);

819

820 MainLoopPreheader =

821 createPreheader(MainLoopStructure, Preheader, "mainloop");

822 PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,

823 ExitPreLoopAt, MainLoopPreheader);

824 rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,

825 PreLoopRRI);

826 }

827

828 BasicBlock *PostLoopPreheader = nullptr;

829 RewrittenRangeInfo PostLoopRRI;

830

831 if (NeedsPostLoop) {

832 PostLoopPreheader =

833 createPreheader(PostLoop.Structure, Preheader, "postloop");

834 PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,

835 ExitMainLoopAt, PostLoopPreheader);

836 rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,

837 PostLoopRRI);

838 }

839

841 MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;

842 BasicBlock *NewBlocks[] = {PostLoopPreheader, PreLoopRRI.PseudoExit,

843 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,

844 PostLoopRRI.ExitSelector, NewMainLoopPreheader};

845

846

847

848 auto NewBlocksEnd =

849 std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr);

850

851 addToParentLoopIfNeeded(ArrayRef(std::begin(NewBlocks), NewBlocksEnd));

852

854

855

856

857

858

859 Loop *PreL = nullptr, *PostL = nullptr;

860 if (!PreLoop.Blocks.empty()) {

861 PreL = createClonedLoopStructure(&OriginalLoop,

863 false);

864 }

865

866 if (!PostLoop.Blocks.empty()) {

867 PostL =

868 createClonedLoopStructure(&OriginalLoop, OriginalLoop.getParentLoop(),

869 PostLoop.Map, false);

870 }

871

872

873 auto CanonicalizeLoop = [&](Loop *L, bool IsOriginalLoop) {

875 simplifyLoop(L, &DT, &LI, &SE, nullptr, nullptr, true);

876

877

878 if (!IsOriginalLoop)

880 };

881 if (PreL)

882 CanonicalizeLoop(PreL, false);

883 if (PostL)

884 CanonicalizeLoop(PostL, false);

885 CanonicalizeLoop(&OriginalLoop, true);

886

887

888

889

890

891

892

893

894 if (isa(MainLoopStructure.IndVarBase))

895 if (IsSignedPredicate)

896 cast(MainLoopStructure.IndVarBase)

897 ->setHasNoSignedWrap(true);

898

899

900

901

902

903

904

905

906

907

908

909 return true;

910}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static const Function * getParent(const Value *V)

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

static const char * ClonedLoopTag

static const SCEV * getNarrowestLatchMaxTakenCountEstimate(ScalarEvolution &SE, const Loop &L)

Returns estimate for max latch taken count of the loop of the narrowest available type.

static bool isSafeDecreasingBound(const SCEV *Start, const SCEV *BoundSCEV, const SCEV *Step, ICmpInst::Predicate Pred, unsigned LatchBrExitIdx, Loop *L, ScalarEvolution &SE)

Given a loop with an deccreasing induction variable, is it possible to safely calculate the bounds of...

static void DisableAllLoopOptsOnLoop(Loop &L)

static bool isSafeIncreasingBound(const SCEV *Start, const SCEV *BoundSCEV, const SCEV *Step, ICmpInst::Predicate Pred, unsigned LatchBrExitIdx, Loop *L, ScalarEvolution &SE)

Given a loop with an increasing induction variable, is it possible to safely calculate the bounds of ...

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

Class for arbitrary precision integers.

static APInt getMaxValue(unsigned numBits)

Gets maximum unsigned value of APInt for specific bit width.

static APInt getSignedMaxValue(unsigned numBits)

Gets maximum signed value of APInt for a specific bit width.

static APInt getMinValue(unsigned numBits)

Gets minimum unsigned value of APInt for a specific bit width.

static APInt getSignedMinValue(unsigned numBits)

Gets minimum signed value of APInt for a specific bit width.

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

LLVM Basic Block Representation.

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

const DataLayout & getDataLayout() const

Get the data layout of the module this basic block belongs to.

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.

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

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

Value * getCondition() const

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

@ ICMP_SLT

signed less than

@ ICMP_UGT

unsigned greater than

@ ICMP_SGT

signed greater than

@ ICMP_ULT

unsigned less than

Predicate getSwappedPredicate() const

For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.

Predicate getPredicate() const

Return the predicate for this instruction.

This is the shared class of boolean and integer constants.

bool isMinusOne() const

This function will return true iff every bit in this constant is set to true.

bool isOne() const

This is just a convenience method to make client code smaller for a common case.

bool isZero() const

This is just a convenience method to make client code smaller for a common code.

const APInt & getValue() const

Return the constant as an APInt value reference.

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

void recalculate(ParentType &Func)

recalculate - compute a dominator tree for the given function

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

const DataLayout & getDataLayout() const

Get the data layout of the module this function belongs to.

This instruction compares its operands according to the predicate given to the constructor.

static bool isEquality(Predicate P)

Return true if this predicate is either EQ or NE.

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

InstListType::iterator eraseFromParent()

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

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

Class to represent integer types.

static IntegerType * get(LLVMContext &C, unsigned NumBits)

This static method is the primary way of constructing an IntegerType.

unsigned getBitWidth() const

Get the number of bits in this IntegerType.

This is an important class for using LLVM in a threaded context.

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.

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

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

iterator_range< block_iterator > blocks() const

void addChildLoop(LoopT *NewChild)

Add the specified loop to be a child of this loop.

BlockT * getLoopPreheader() const

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

ArrayRef< BlockT * > getBlocks() const

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

LoopT * getParentLoop() const

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

LoopConstrainer(Loop &L, LoopInfo &LI, function_ref< void(Loop *, bool)> LPMAddNewLoop, const LoopStructure &LS, ScalarEvolution &SE, DominatorTree &DT, Type *T, SubRanges SR)

void addTopLevelLoop(LoopT *New)

This adds the specified loop to the collection of top-level loops.

LoopT * AllocateLoop(ArgsTy &&...Args)

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Represents a single loop in the control flow graph.

void replaceOperandWith(unsigned I, Metadata *New)

Replace a specific operand.

static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)

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

void addIncoming(Value *V, BasicBlock *BB)

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

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

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

const SCEV * getStart() const

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

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

This class represents a constant integer value.

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

bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const

Return true if the given expression is safe to expand in the sense that all materialized values are d...

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 * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)

Return the SCEV object corresponding to -V.

bool isKnownNegative(const SCEV *S)

Test if the given expression is known to be negative.

bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)

Test whether entry to the loop is protected by a conditional between LHS and RHS.

const SCEV * getConstant(ConstantInt *V)

const SCEV * getSCEV(Value *V)

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

const SCEV * getOne(Type *Ty)

Return a SCEV for the constant 1 of a specific type.

LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)

Return the "disposition" of the given SCEV with respect to the given loop.

const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Return LHS-RHS.

@ LoopInvariant

The SCEV is loop-invariant.

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

bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)

Determine if the SCEV can be evaluated at loop's entry.

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 * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)

@ SymbolicMaximum

An expression which provides an upper bound on the exact trip count.

const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)

Try to apply information from loop guards for L to Expr.

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.

const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)

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

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

The instances of the Type class are immutable: once they are created, they are never changed.

static IntegerType * getInt1Ty(LLVMContext &C)

LLVMContext & getContext() const

Return the LLVMContext in which this type was uniqued.

bool replaceUsesOfWith(Value *From, Value *To)

Replace uses of one Value with another.

Value * getOperand(unsigned i) const

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.

An efficient, type-erasing, non-owning reference to a callable.

const ParentTy * getParent() const

self_iterator getIterator()

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.

auto successors(const MachineBasicBlock *BB)

bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)

Put a loop nest into LCSSA form.

bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)

Returns true if S is defined and never is equal to signed/unsigned max.

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

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

constexpr unsigned BitWidth

bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)

Returns true if S is defined and never is equal to signed/unsigned min.

bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)

Returns true if we can prove that S is defined and always non-negative in loop L.

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

Implement std::swap in terms of BitVector swap.

std::optional< const SCEV * > LowLimit

std::optional< const SCEV * > HighLimit

LoopStructure map(M Map) const

static std::optional< LoopStructure > parseLoopStructure(ScalarEvolution &, Loop &, bool, const char *&)