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,

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");

48 if (LatchBrExitIdx == 1)

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

59 const SCEV *MinusOne =

64}

70 unsigned LatchBrExitIdx, Loop *L,

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");

95 if (LatchBrExitIdx == 1)

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

105

109}

110

111

112

113

114

116 const Loop &L) {

117 const SCEV *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

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

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

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);

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

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;

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) {

494 BasicBlock *OriginalBB = OriginalLoop.getBlocks()[i];

495

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

497

498 for (Instruction &I : *ClonedBB)

501

502

503

504

505

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

507 if (OriginalLoop.contains(SBB))

508 continue;

509

510 for (PHINode &PN : SBB->phis()) {

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

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

513 SE.forgetLcssaPhiWithNewPredecessor(&OriginalLoop, &PN);

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

618 : (IsSignedPredicate ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT);

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

645 BranchInst *BranchToContinuation =

647

648

649

650

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

652 PHINode *NewPHI = PHINode::Create(PN.getType(), 2, PN.getName() + ".copy",

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

696 Loop *ParentLoop = OriginalLoop.getParentLoop();

697 if (!ParentLoop)

698 return;

699

700 for (BasicBlock *BB : BBs)

702}

703

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

706 bool IsSubloop) {

707 Loop &New = *LI.AllocateLoop();

708 if (Parent)

710 else

711 LI.addTopLevelLoop(&New);

712 LPMAddNewLoop(&New, IsSubloop);

713

714

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

716 if (LI.getLoopFor(BB) == Original)

718

719

720 for (Loop *SubLoop : *Original)

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

722

723 return &New;

724}

725

727 BasicBlock *Preheader = OriginalLoop.getLoopPreheader();

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

729

730 OriginalPreheader = Preheader;

731 MainLoopPreheader = Preheader;

732 bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;

733 bool Increasing = MainLoopStructure.IndVarIncreasing;

735

736 SCEVExpander Expander(SE, F.getDataLayout(), "loop-constrainer");

737 Instruction *InsertPt = OriginalPreheader->getTerminator();

738

739

740

741

742 ClonedLoop PreLoop, PostLoop;

743 bool NeedsPreLoop =

744 Increasing ? SR.LowLimit.has_value() : SR.HighLimit.has_value();

745 bool NeedsPostLoop =

746 Increasing ? SR.HighLimit.has_value() : SR.LowLimit.has_value();

747

748 Value *ExitPreLoopAt = nullptr;

749 Value *ExitMainLoopAt = nullptr;

752

753 if (NeedsPreLoop) {

754 const SCEV *ExitPreLoopAtSCEV = nullptr;

755

756 if (Increasing)

757 ExitPreLoopAtSCEV = *SR.LowLimit;

759 IsSignedPredicate))

760 ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);

761 else {

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

763 << "preloop exit limit. HighLimit = "

764 << *(*SR.HighLimit) << "\n");

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

787 ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);

788 else {

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

790 << "mainloop exit limit. LowLimit = "

791 << *(*SR.LowLimit) << "\n");

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

853 DT.recalculate(F);

854

855

856

857

858

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

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

861 PreL = createClonedLoopStructure(&OriginalLoop,

862 OriginalLoop.getParentLoop(), PreLoop.Map,

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

895 if (IsSignedPredicate)

897 ->setHasNoSignedWrap(true);

898

899

900

901

902

903

904

905

906

907

908

909 return true;

910}

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

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

Definition LoopConstrainer.cpp:13

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

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

Definition LoopConstrainer.cpp:115

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

Definition LoopConstrainer.cpp:19

static void DisableAllLoopOptsOnLoop(Loop &L)

Definition LoopConstrainer.cpp:434

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

Definition LoopConstrainer.cpp:68

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.

LLVM_ABI 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)

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.

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

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.

LLVM_ABI InstListType::iterator eraseFromParent()

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

Class to represent integer types.

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

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

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

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.

ArrayRef< BlockT * > getBlocks() const

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

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

Definition LoopConstrainer.cpp:460

bool run()

Definition LoopConstrainer.cpp:726

Represents a single loop in the control flow graph.

LLVM_ABI void replaceOperandWith(unsigned I, Metadata *New)

Replace a specific operand.

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

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

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

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

Return the SCEV object corresponding to -V.

LLVM_ABI bool isKnownNegative(const SCEV *S)

Test if the given expression is known to be negative.

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

LLVM_ABI const SCEV * getConstant(ConstantInt *V)

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

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

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

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

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

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

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

@ SymbolicMaximum

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

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

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

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.

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 LLVM_ABI IntegerType * getInt1Ty(LLVMContext &C)

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

LLVM_ABI 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()

@ BasicBlock

Various leaf nodes.

This is an optimization pass for GlobalISel generic memory operations.

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

Simplify each loop in a loop nest recursively.

FunctionAddr VTableAddr Value

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

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

decltype(auto) dyn_cast(const From &Val)

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

auto successors(const MachineBasicBlock *BB)

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

Put a loop nest into LCSSA form.

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

LLVM_ABI raw_ostream & dbgs()

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

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >

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.

ArrayRef(const T &OneElt) -> ArrayRef< T >

constexpr unsigned BitWidth

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

decltype(auto) cast(const From &Val)

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

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

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

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

Definition LoopConstrainer.cpp:125