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

400 SCEVExpander Expander(SE, "loop-constrainer");

402

403 if (FixedRightSCEV)

404 RightValue =

406

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

409

411

412 Result.Tag = "main";

413 Result.Header = Header;

414 Result.Latch = Latch;

415 Result.LatchBr = LatchBr;

418 Result.IndVarStart = IndVarStartV;

419 Result.IndVarStep = StepCI;

420 Result.IndVarBase = LeftValue;

421 Result.IndVarIncreasing = IsIncreasing;

422 Result.LoopExitAt = RightValue;

425

426 FailureReason = nullptr;

427

428 return Result;

429}

430

431

432

434

435

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

437

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

444 Context,

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

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

449 Context,

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

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

453 DisableLICMVersioning, DisableDistribution});

454

456 L.setLoopID(NewLoopID);

457}

458

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

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

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

466

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

468 const char *Tag) const {

471 Result.Blocks.push_back(Clone);

472 Result.Map[BB] = Clone;

473 }

474

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

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

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

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

479 return V;

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

481 };

482

483 auto *ClonedLatch =

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

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

487

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

490

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

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

494

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

496

497 for (Instruction &I : *ClonedBB)

500

501

502

503

504

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

506 if (OriginalLoop.contains(SBB))

507 continue;

508

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

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

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

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

513 }

514 }

515 }

516}

517

518LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(

520 BasicBlock *ContinuationBlock) const {

521

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 RewrittenRangeInfo RRI;

593

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

596 &F, BBInsertLocation);

598 BBInsertLocation);

599

601 bool Increasing = LS.IndVarIncreasing;

602 bool IsSignedPredicate = LS.IsSignedPredicate;

603

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

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

607 return V;

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

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

610 };

611

612

613 Value *EnterLoopCond = nullptr;

614 auto Pred =

615 Increasing

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

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

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

620

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

623

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

625 B.SetInsertPoint(LS.LatchBr);

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

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

628

629 Value *CondForBranch = LS.LatchBrExitIdx == 1

630 ? TakeBackedgeLoopCond

631 : B.CreateNot(TakeBackedgeLoopCond);

632

633 LS.LatchBr->setCondition(CondForBranch);

634

635 B.SetInsertPoint(RRI.ExitSelector);

636

637

638

639

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

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

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

643

644 BranchInst *BranchToContinuation =

646

647

648

649

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

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

653

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

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

656 RRI.ExitSelector);

657 RRI.PHIValuesAtPseudoExit.push_back(NewPHI);

658 }

659

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

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

664

665

666

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

668

669 return RRI;

670}

671

672void LoopConstrainer::rewriteIncomingValuesForPHIs(

674 const LoopConstrainer::RewrittenRangeInfo &RRI) const {

675 unsigned PHIIndex = 0;

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

677 PN.setIncomingValueForBlock(ContinuationBlock,

678 RRI.PHIValuesAtPseudoExit[PHIIndex++]);

679

680 LS.IndVarStart = RRI.IndVarEnd;

681}

682

685 const char *Tag) const {

688

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

690

691 return Preheader;

692}

693

695 Loop *ParentLoop = OriginalLoop.getParentLoop();

696 if (!ParentLoop)

697 return;

698

699 for (BasicBlock *BB : BBs)

701}

702

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

705 bool IsSubloop) {

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

707 if (Parent)

709 else

710 LI.addTopLevelLoop(&New);

711 LPMAddNewLoop(&New, IsSubloop);

712

713

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

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

717

718

719 for (Loop *SubLoop : *Original)

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

721

722 return &New;

723}

724

726 BasicBlock *Preheader = OriginalLoop.getLoopPreheader();

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

728

729 OriginalPreheader = Preheader;

730 MainLoopPreheader = Preheader;

731 bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;

732 bool Increasing = MainLoopStructure.IndVarIncreasing;

734

735 SCEVExpander Expander(SE, "loop-constrainer");

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

737

738

739

740

741 ClonedLoop PreLoop, PostLoop;

742 bool NeedsPreLoop =

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

744 bool NeedsPostLoop =

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

746

747 Value *ExitPreLoopAt = nullptr;

748 Value *ExitMainLoopAt = nullptr;

751

752 if (NeedsPreLoop) {

753 const SCEV *ExitPreLoopAtSCEV = nullptr;

754

755 if (Increasing)

756 ExitPreLoopAtSCEV = *SR.LowLimit;

758 IsSignedPredicate))

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

760 else {

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

762 << "preloop exit limit. HighLimit = "

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

764 return false;

765 }

766

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

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

769 << " preloop exit limit " << *ExitPreLoopAtSCEV

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

771 << "\n");

772 return false;

773 }

774

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

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

777 }

778

779 if (NeedsPostLoop) {

780 const SCEV *ExitMainLoopAtSCEV = nullptr;

781

782 if (Increasing)

783 ExitMainLoopAtSCEV = *SR.HighLimit;

785 IsSignedPredicate))

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

787 else {

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

789 << "mainloop exit limit. LowLimit = "

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

791 return false;

792 }

793

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

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

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

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

798 << "\n");

799 return false;

800 }

801

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

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

804 }

805

806

807

808 if (NeedsPreLoop)

809 cloneLoop(PreLoop, "preloop");

810 if (NeedsPostLoop)

811 cloneLoop(PostLoop, "postloop");

812

813 RewrittenRangeInfo PreLoopRRI;

814

815 if (NeedsPreLoop) {

817 PreLoop.Structure.Header);

818

819 MainLoopPreheader =

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

821 PreLoopRRI = changeIterationSpaceEnd(PreLoop.Structure, Preheader,

822 ExitPreLoopAt, MainLoopPreheader);

823 rewriteIncomingValuesForPHIs(MainLoopStructure, MainLoopPreheader,

824 PreLoopRRI);

825 }

826

827 BasicBlock *PostLoopPreheader = nullptr;

828 RewrittenRangeInfo PostLoopRRI;

829

830 if (NeedsPostLoop) {

831 PostLoopPreheader =

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

833 PostLoopRRI = changeIterationSpaceEnd(MainLoopStructure, MainLoopPreheader,

834 ExitMainLoopAt, PostLoopPreheader);

835 rewriteIncomingValuesForPHIs(PostLoop.Structure, PostLoopPreheader,

836 PostLoopRRI);

837 }

838

840 MainLoopPreheader != Preheader ? MainLoopPreheader : nullptr;

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

842 PreLoopRRI.ExitSelector, PostLoopRRI.PseudoExit,

843 PostLoopRRI.ExitSelector, NewMainLoopPreheader};

844

845

846

847 auto NewBlocksEnd =

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

849

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

851

852 DT.recalculate(F);

853

854

855

856

857

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

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

860 PreL = createClonedLoopStructure(&OriginalLoop,

861 OriginalLoop.getParentLoop(), PreLoop.Map,

862 false);

863 }

864

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

866 PostL =

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

868 PostLoop.Map, false);

869 }

870

871

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

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

875

876

877 if (!IsOriginalLoop)

879 };

880 if (PreL)

881 CanonicalizeLoop(PreL, false);

882 if (PostL)

883 CanonicalizeLoop(PostL, false);

884 CanonicalizeLoop(&OriginalLoop, true);

885

886

887

888

889

890

891

892

894 if (IsSignedPredicate)

896 ->setHasNoSignedWrap(true);

897

898

899

900

901

902

903

904

905

906

907

908 return true;

909}

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

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:433

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.

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.

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:459

bool run()

Definition LoopConstrainer.cpp:725

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