LoopUnroll.cpp Source File (original) (raw)

67#include

68#include <assert.h>

69#include

70#include <type_traits>

71#include

73namespace llvm {

76}

78using namespace llvm;

80#define DEBUG_TYPE "loop-unroll"

83 STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");

84 STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)");

85 STATISTIC(NumUnrolledNotLatch, "Number of loops unrolled without a conditional "

86 "latch (completely or otherwise)");

90 cl::desc("Allow runtime unrolled loops to be unrolled "

91 "with epilog instead of prolog."));

95 cl::desc("Verify domtree after unrolling"),

96#ifdef EXPENSIVE_CHECKS

98#else

100#endif

101 );

102

105 cl::desc("Verify loopinfo after unrolling"),

106#ifdef EXPENSIVE_CHECKS

108#else

110#endif

111 );

112

113

114

115

116

117

118

119

120

121

122

124 const std::vector<BasicBlock *> &Blocks,

128 continue;

130 for (Use &U : I.operands()) {

131 if (const auto *Def = dyn_cast(U)) {

133 if (!DefLoop)

134 continue;

136 return true;

137 }

138 }

139 }

140 }

141 return false;

142}

143

144

145

146

147

151

153 assert(OldLoop && "Should (at least) be in the loop being unrolled!");

154

155 Loop *&NewLoop = NewLoops[OldLoop];

156 if (!NewLoop) {

157

159 "Header should be first in RPO");

160

163

164 if (NewLoopParent)

166 else

168

170 return OldLoop;

171 } else {

173 return nullptr;

174 }

175}

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

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

205 assert(PreHeader && Header);

206 for (const PHINode &PN : Header->phis()) {

207 if (isa(PN.getIncomingValueForBlock(PreHeader)))

208 return true;

209 }

210 return false;

211}

212

219};

220

223 unsigned CurrentGeneration;

224 unsigned ChildGeneration;

228 bool Processed = false;

229

230public:

234 : LoadScope(AvailableLoads), CurrentGeneration(cg), ChildGeneration(cg),

235 Node(N), ChildIter(Child), EndIter(End) {}

236

242

245 ++ChildIter;

246 return Child;

247 }

248

252};

253

257 if (!LV.DefI)

258 return nullptr;

260 return nullptr;

261 if (LV.Generation != CurrentGeneration) {

263 if (!MSSA)

264 return nullptr;

268 if (!MSSA->dominates(LaterDef, EarlierMA))

269 return nullptr;

270 }

271 return LV.DefI;

272}

273

280 HeaderD->begin(), HeaderD->end()));

281

282 unsigned CurrentGeneration = 0;

283 while (!NodesToProcess.empty()) {

284 StackNode *NodeToProcess = &*NodesToProcess.back();

285

287

289

290

291

292

293

294

295

296

297

299 ++CurrentGeneration;

301

302 auto *Load = dyn_cast(&I);

303 if (!Load || !Load->isSimple()) {

304 if (I.mayWriteToMemory())

305 CurrentGeneration++;

306 continue;

307 }

308

309 const SCEV *PtrSCEV = SE.getSCEV(Load->getPointerOperand());

312 getMatchingValue(LV, Load, CurrentGeneration, BAA, GetMSSA)) {

314 Load->replaceAllUsesWith(M);

315 Load->eraseFromParent();

316 }

317 } else {

318 AvailableLoads.insert(PtrSCEV, LoadValue(Load, CurrentGeneration));

319 }

320 }

322 NodeToProcess->process();

323 } else if (NodeToProcess->childIter() != NodeToProcess->end()) {

324

326 if (!L->contains(Child->getBlock()))

327 continue;

330 Child->begin(), Child->end()));

331 } else {

332

333

335 }

336 }

337}

338

339

340

341

348

349

350 if (SE && SimplifyIVs) {

353

354

355

356 while (!DeadInsts.empty()) {

358 if (Instruction *Inst = dyn_cast_or_null(V))

360 }

361

362 if (AA) {

363 std::unique_ptr MSSA = nullptr;

365 loadCSE(L, *DT, *SE, *LI, BAA, [L, AA, DT, &MSSA]() -> MemorySSA * {

366 if (!MSSA)

367 MSSA.reset(new MemorySSA(*L, AA, DT));

368 return &*MSSA;

369 });

370 }

371 }

372

373

374

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

377 for (BasicBlock *BB : L->getBlocks()) {

378

379 if (BB->getParent()->getSubprogram())

381

385 Inst.replaceAllUsesWith(V);

388

389

390

391

392

393 {

395 const APInt *C1, *C2;

397 auto *InnerI = dyn_cast(Inst.getOperand(0));

398 auto *InnerOBO = cast(Inst.getOperand(0));

399 bool SignedOverflow;

400 APInt NewC = C1->sadd_ov(*C2, SignedOverflow);

401 Inst.setOperand(0, X);

402 Inst.setOperand(1, ConstantInt::get(Inst.getType(), NewC));

403 Inst.setHasNoUnsignedWrap(Inst.hasNoUnsignedWrap() &&

404 InnerOBO->hasNoUnsignedWrap());

405 Inst.setHasNoSignedWrap(Inst.hasNoSignedWrap() &&

406 InnerOBO->hasNoSignedWrap() &&

407 !SignedOverflow);

410 }

411 }

412 }

413

414

415

417 }

418}

419

420

421

425 return false;

426

427

428 for (auto &BB : L->blocks()) {

429 for (auto &I : *BB) {

430 if (isa(I))

431 return true;

432 if (auto *CB = dyn_cast(&I))

433 if (CB->isConvergent())

434 return CB->getConvergenceControlToken();

435 }

436 }

437 return true;

438}

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

461 bool PreserveLCSSA, Loop **RemainderLoop, AAResults *AA) {

462 assert(DT && "DomTree is required");

463

464 if (!L->getLoopPreheader()) {

465 LLVM_DEBUG(dbgs() << " Can't unroll; loop preheader-insertion failed.\n");

466 return LoopUnrollResult::Unmodified;

467 }

468

469 if (!L->getLoopLatch()) {

470 LLVM_DEBUG(dbgs() << " Can't unroll; loop exit-block-insertion failed.\n");

471 return LoopUnrollResult::Unmodified;

472 }

473

474

475 if (!L->isSafeToClone()) {

476 LLVM_DEBUG(dbgs() << " Can't unroll; Loop body cannot be cloned.\n");

477 return LoopUnrollResult::Unmodified;

478 }

479

480 if (L->getHeader()->hasAddressTaken()) {

481

483 dbgs() << " Won't unroll loop: address of header block is taken.\n");

484 return LoopUnrollResult::Unmodified;

485 }

486

488

489

490

491 BasicBlock *Preheader = L->getLoopPreheader();

493 BasicBlock *LatchBlock = L->getLoopLatch();

495 L->getExitBlocks(ExitBlocks);

496 std::vector<BasicBlock *> OriginalLoopBlocks = L->getBlocks();

497

500 unsigned EstimatedLoopInvocationWeight = 0;

501 std::optional OriginalTripCount =

503

504

505

506 if (MaxTripCount && ULO.Count > MaxTripCount)

507 ULO.Count = MaxTripCount;

508

509 struct ExitInfo {

510 unsigned TripCount;

511 unsigned TripMultiple;

512 unsigned BreakoutTrip;

513 bool ExitOnTrue;

514 BasicBlock *FirstExitingBlock = nullptr;

516 };

519 L->getExitingBlocks(ExitingBlocks);

520 for (auto *ExitingBlock : ExitingBlocks) {

521

522

523 auto *BI = dyn_cast(ExitingBlock->getTerminator());

524 if (!BI)

525 continue;

526

527 ExitInfo &Info = ExitInfos[ExitingBlock];

530 if (Info.TripCount != 0) {

532 Info.TripMultiple = 0;

533 } else {

534 Info.BreakoutTrip = Info.TripMultiple =

536 }

537 Info.ExitOnTrue = !L->contains(BI->getSuccessor(0));

538 Info.ExitingBlocks.push_back(ExitingBlock);

539 LLVM_DEBUG(dbgs() << " Exiting block %" << ExitingBlock->getName()

540 << ": TripCount=" << Info.TripCount

541 << ", TripMultiple=" << Info.TripMultiple

542 << ", BreakoutTrip=" << Info.BreakoutTrip << "\n");

543 }

544

545

546

547

548 const bool CompletelyUnroll = ULO.Count == MaxTripCount;

549

550 const bool PreserveOnlyFirst = CompletelyUnroll && MaxOrZero;

551

552

553

554 if (CompletelyUnroll)

556

557

558

559

560

561

562

563 bool NeedToFixLCSSA =

564 PreserveLCSSA && CompletelyUnroll &&

566 [](const BasicBlock *BB) { return isa(BB->begin()); });

567

568

569

570

571

572

573

575

576

577

578 bool LatchIsExiting = L->isLoopExiting(LatchBlock);

579 if (!LatchBI || (LatchBI->isConditional() && !LatchIsExiting)) {

581 dbgs() << "Can't unroll; a conditional latch must exit the loop");

582 return LoopUnrollResult::Unmodified;

583 }

584

586 "Can't runtime unroll if loop contains a convergent operation.");

587

588 bool EpilogProfitability =

591

599 else {

600 LLVM_DEBUG(dbgs() << "Won't unroll; remainder loop could not be "

601 "generated when assuming runtime trip count\n");

602 return LoopUnrollResult::Unmodified;

603 }

604 }

605

606 using namespace ore;

607

608 if (CompletelyUnroll) {

609 LLVM_DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName()

610 << " with trip count " << ULO.Count << "!\n");

611 if (ORE)

612 ORE->emit([&]() {

614 L->getHeader())

615 << "completely unrolled loop with "

616 << NV("UnrollCount", ULO.Count) << " iterations";

617 });

618 } else {

619 LLVM_DEBUG(dbgs() << "UNROLLING loop %" << Header->getName() << " by "

624

625 if (ORE)

626 ORE->emit([&]() {

628 L->getHeader());

629 Diag << "unrolled loop by a factor of " << NV("UnrollCount", ULO.Count);

631 Diag << " with run-time trip count";

632 return Diag;

633 });

634 }

635

636

637

638

639

640

641

642

643

644 if (SE) {

647 else {

650 }

651 }

652

653 if (!LatchIsExiting)

654 ++NumUnrolledNotLatch;

655

656

657

659 std::vector<PHINode*> OrigPHINode;

661 OrigPHINode.push_back(cast(I));

662 }

663

664 std::vector<BasicBlock *> Headers;

665 std::vector<BasicBlock *> Latches;

666 Headers.push_back(Header);

667 Latches.push_back(LatchBlock);

668

669

670

671

674

675

678

679 std::vector<BasicBlock*> UnrolledLoopBlocks = L->getBlocks();

680

681

682

683

684

686 for (Loop *SubLoop : *L)

687 LoopsToSimplify.insert(SubLoop);

688

689

690

691 if (Header->getParent()->shouldEmitDebugInfoForProfiling() &&

693 for (BasicBlock *BB : L->getBlocks())

695 if (.isDebugOrPseudoInst())

696 if (const DILocation *DIL = I.getDebugLoc()) {

697 auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(ULO.Count);

698 if (NewDIL)

699 I.setDebugLoc(*NewDIL);

700 else

702 << "Failed to create new discriminator: "

703 << DIL->getFilename() << " Line: " << DIL->getLine());

704 }

705

706

707

710

711

712

713

714 auto BlockInsertPt = std::next(LatchBlock->getIterator());

715 for (unsigned It = 1; It != ULO.Count; ++It) {

718 NewLoops[L] = L;

719

723 Header->getParent()->insert(BlockInsertPt, New);

724

726 "Header should not be in a sub-loop");

727

729 if (OldLoop)

730 LoopsToSimplify.insert(NewLoops[OldLoop]);

731

732 if (*BB == Header) {

733

734

735 for (PHINode *OrigPHI : OrigPHINode) {

736 PHINode *NewPHI = cast(VMap[OrigPHI]);

738 if (Instruction *InValI = dyn_cast(InVal))

739 if (It > 1 && L->contains(InValI))

740 InVal = LastValueMap[InValI];

741 VMap[OrigPHI] = InVal;

743 }

744

745

749 Instruction *heartCopy = cast(it->second);

752 }

753 }

754

755

756 LastValueMap[*BB] = New;

758 VI != VE; ++VI)

759 LastValueMap[VI->first] = VI->second;

760

761

763 if (L->contains(Succ))

764 continue;

768 if (It != LastValueMap.end())

772 }

773 }

774

775

776 if (*BB == Header)

777 Headers.push_back(New);

778 if (*BB == LatchBlock)

779 Latches.push_back(New);

780

781

782

783 auto ExitInfoIt = ExitInfos.find(*BB);

784 if (ExitInfoIt != ExitInfos.end())

785 ExitInfoIt->second.ExitingBlocks.push_back(New);

786

788 UnrolledLoopBlocks.push_back(New);

789

790

791

792

793

794 if (*BB == Header)

796 else {

797 auto BBDomNode = DT->getNode(*BB);

798 auto BBIDom = BBDomNode->getIDom();

799 BasicBlock *OriginalBBIDom = BBIDom->getBlock();

801 New, cast(LastValueMap[cast(OriginalBBIDom)]));

802 }

803 }

804

805

807 for (BasicBlock *NewBlock : NewBlocks)

809 if (auto *II = dyn_cast(&I))

811

812 {

813

814

815

816 std::string ext = (Twine("It") + Twine(It)).str();

818 Header->getContext(), ext);

819 }

820 }

821

822

823 for (PHINode *PN : OrigPHINode) {

824 if (CompletelyUnroll) {

825 PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));

826 PN->eraseFromParent();

827 } else if (ULO.Count > 1) {

828 Value *InVal = PN->removeIncomingValue(LatchBlock, false);

829

830

831 if (Instruction *InValI = dyn_cast(InVal)) {

832 if (L->contains(InValI))

833 InVal = LastValueMap[InVal];

834 }

835 assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch");

836 PN->addIncoming(InVal, Latches.back());

837 }

838 }

839

840

841

842 for (unsigned i = 0, e = Latches.size(); i != e; ++i) {

843 unsigned j = (i + 1) % e;

844 Latches[i]->getTerminator()->replaceSuccessorWith(Headers[i], Headers[j]);

845 }

846

847

848

849

850

851 if (ULO.Count > 1) {

852 for (auto *BB : OriginalLoopBlocks) {

853 auto *BBDomNode = DT->getNode(BB);

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

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

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

858 ChildrenToUpdate.push_back(ChildBB);

859 }

860

861

862

863

865 for (auto *ChildBB : ChildrenToUpdate)

867 }

868 }

869

871 DT->verify(DominatorTree::VerificationLevel::Fast));

872

874 auto SetDest = [&](BasicBlock *Src, bool WillExit, bool ExitOnTrue) {

875 auto *Term = cast(Src->getTerminator());

876 const unsigned Idx = ExitOnTrue ^ WillExit;

878 BasicBlock *DeadSucc = Term->getSuccessor(1-Idx);

879

880

882

883

885 BI->setDebugLoc(Term->getDebugLoc());

886 Term->eraseFromParent();

887

888 DTUpdates.emplace_back(DominatorTree::Delete, Src, DeadSucc);

889 };

890

891 auto WillExit = [&](const ExitInfo &Info, unsigned i, unsigned j,

892 bool IsLatch) -> std::optional {

893 if (CompletelyUnroll) {

894 if (PreserveOnlyFirst) {

895 if (i == 0)

896 return std::nullopt;

897 return j == 0;

898 }

899

900 if (j == 0)

901 return true;

902 if (Info.TripCount && j != Info.TripCount)

903 return false;

904 return std::nullopt;

905 }

906

908

909

910 if (IsLatch && j != 0)

911 return false;

912 return std::nullopt;

913 }

914

915 if (j != Info.BreakoutTrip &&

916 (Info.TripMultiple == 0 || j % Info.TripMultiple != 0)) {

917

918

919 return false;

920 }

921 return std::nullopt;

922 };

923

924

925

926 for (auto &Pair : ExitInfos) {

927 ExitInfo &Info = Pair.second;

928 for (unsigned i = 0, e = Info.ExitingBlocks.size(); i != e; ++i) {

929

930 unsigned j = (i + 1) % e;

931 bool IsLatch = Pair.first == LatchBlock;

932 std::optional KnownWillExit = WillExit(Info, i, j, IsLatch);

933 if (!KnownWillExit) {

934 if ( Info .FirstExitingBlock)

935 Info.FirstExitingBlock = Info.ExitingBlocks[i];

936 continue;

937 }

938

939

940

941

942

943

944 if (*KnownWillExit && !IsLatch) {

945 if ( Info .FirstExitingBlock)

946 Info.FirstExitingBlock = Info.ExitingBlocks[i];

947 continue;

948 }

949

950 SetDest(Info.ExitingBlocks[i], *KnownWillExit, Info.ExitOnTrue);

951 }

952 }

953

954 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);

956 if (ExitingBlocks.size() == 1 && ExitInfos.size() == 1) {

957

958

959

960

961

962

963 DTUToUse = nullptr;

964 auto &[OriginalExit, Info] = *ExitInfos.begin();

965 if ( Info .FirstExitingBlock)

966 Info.FirstExitingBlock = Info.ExitingBlocks.back();

968 if (L->contains(C->getBlock()))

969 continue;

970 C->setIDom(DT->getNode(Info.FirstExitingBlock));

971 }

972 } else {

974 }

975

976

977 if (!LatchIsExiting && CompletelyUnroll) {

978

979

980

983 }

984

985

987 BranchInst *Term = dyn_cast(Latch->getTerminator());

989 (CompletelyUnroll && !LatchIsExiting && Latch == Latches.back())) &&

990 "Need a branch as terminator, except when fully unrolling with "

991 "unconditional latch");

992 if (Term && Term->isUnconditional()) {

993 BasicBlock *Dest = Term->getSuccessor(0);

996 nullptr, nullptr,

997 false,

998 DTUToUse ? nullptr : DT)) {

999

1000 std::replace(Latches.begin(), Latches.end(), Dest, Fold);

1002 }

1003 }

1004 }

1005

1006 if (DTUToUse) {

1007

1009 }

1011 DT->verify(DominatorTree::VerificationLevel::Fast));

1012

1013

1014

1016 TTI, AA);

1017

1018 NumCompletelyUnrolled += CompletelyUnroll;

1019 ++NumUnrolled;

1020

1021 Loop *OuterL = L->getParentLoop();

1022

1023 if (CompletelyUnroll) {

1025

1026 L = nullptr;

1027 } else if (OriginalTripCount) {

1028

1029

1031 EstimatedLoopInvocationWeight);

1032 }

1033

1034

1037

1038

1039

1040

1041

1042

1043

1044

1045

1046 if (PreserveLCSSA && OuterL && CompletelyUnroll && !NeedToFixLCSSA)

1048

1049

1050

1051

1052 if (OuterL) {

1053

1054

1055

1056 if (NeedToFixLCSSA) {

1057

1058

1059

1061 Loop *FixLCSSALoop = OuterL;

1062 if (!FixLCSSALoop->contains(LatchLoop))

1063 while (FixLCSSALoop->getParentLoop() != LatchLoop)

1065

1067 } else if (PreserveLCSSA) {

1069 "Loops should be in LCSSA form after loop-unroll.");

1070 }

1071

1072

1073

1074 simplifyLoop(OuterL, DT, LI, SE, AC, nullptr, PreserveLCSSA);

1075 } else {

1076

1077 for (Loop *SubLoop : LoopsToSimplify)

1078 simplifyLoop(SubLoop, DT, LI, SE, AC, nullptr, PreserveLCSSA);

1079 }

1080

1081 return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled

1082 : LoopUnrollResult::PartiallyUnrolled;

1083}

1084

1085

1086

1087

1089

1091 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");

1092

1094 MDNode *MD = dyn_cast(MDO);

1095 if (!MD)

1096 continue;

1097

1099 if (!S)

1100 continue;

1101

1103 return MD;

1104 }

1105 return nullptr;

1106}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Analysis containing CSE Info

Optimize for code generation

#define LLVM_ATTRIBUTE_USED

This file contains the declarations for the subclasses of Constant, which represent the different fla...

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.

DenseMap< Block *, BlockRelaxAux > Blocks

static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")

This file defines a set of templates that efficiently compute a dominator tree over a generic graph.

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

This defines the Use class.

static bool needToInsertPhisForLCSSA(Loop *L, const std::vector< BasicBlock * > &Blocks, LoopInfo *LI)

Check if unrolling created a situation where we need to insert phi nodes to preserve LCSSA form.

static bool isEpilogProfitable(Loop *L)

The function chooses which type of unroll (epilog or prolog) is more profitabale.

void loadCSE(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, BatchAAResults &BAA, function_ref< MemorySSA *()> GetMSSA)

Value * getMatchingValue(LoadValue LV, LoadInst *LI, unsigned CurrentGeneration, BatchAAResults &BAA, function_ref< MemorySSA *()> GetMSSA)

static cl::opt< bool > UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolled loops to be unrolled " "with epilog instead of prolog."))

static cl::opt< bool > UnrollVerifyLoopInfo("unroll-verify-loopinfo", cl::Hidden, cl::desc("Verify loopinfo after unrolling"), cl::init(false))

static cl::opt< bool > UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden, cl::desc("Verify domtree after unrolling"), cl::init(false))

static LLVM_ATTRIBUTE_USED bool canHaveUnrollRemainder(const Loop *L)

This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...

uint64_t IntrinsicInst * II

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

This file implements a set that has insertion order iteration characteristics.

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)

void childGeneration(unsigned generation)

unsigned currentGeneration() const

unsigned childGeneration() const

StackNode(ScopedHashTable< const SCEV *, LoadValue > &AvailableLoads, unsigned cg, DomTreeNode *N, DomTreeNode::const_iterator Child, DomTreeNode::const_iterator End)

DomTreeNode::const_iterator end() const

DomTreeNode * nextChild()

DomTreeNode::const_iterator childIter() const

Class for arbitrary precision integers.

APInt sadd_ov(const APInt &RHS, bool &Overflow) const

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

void registerAssumption(AssumeInst *CI)

Add an @llvm.assume intrinsic to this function's cache.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

const BasicBlock * getSinglePredecessor() const

Return the predecessor of this block if it has a single predecessor block.

const BasicBlock * getUniquePredecessor() const

Return the predecessor of this block if it has a unique predecessor block.

const BasicBlock * getSingleSuccessor() const

Return the successor of this block if it has a single successor.

InstListType::iterator iterator

Instruction iterators...

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)

Update PHI nodes in this BasicBlock before removal of predecessor Pred.

This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...

Conditional or Unconditional Branch instruction.

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

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

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

iterator find(const_arg_type_t< KeyT > Val)

iterator_range< iterator > children()

DomTreeNodeBase * getIDom() const

typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator

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

DomTreeT & getDomTree()

Flush DomTree updates and return DomTree.

void applyUpdates(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

InstListType::iterator eraseFromParent()

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

An instruction for reading from memory.

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this loop.

BlockT * getHeader() const

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

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

void addChildLoop(LoopT *NewChild)

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

LoopT * getParentLoop() const

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

Store the result of a depth first search within basic blocks contained by a single loop.

RPOIterator beginRPO() const

Reverse iterate over the cached postorder blocks.

std::vector< BasicBlock * >::const_reverse_iterator RPOIterator

void perform(const LoopInfo *LI)

Traverse the loop blocks and store the DFS result.

RPOIterator endRPO() const

void verify(const DominatorTreeBase< BlockT, false > &DomTree) const

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.

bool replacementPreservesLCSSAForm(Instruction *From, Value *To)

Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.

void erase(Loop *L)

Update LoopInfo after removing the last backedge from a loop.

Represents a single loop in the control flow graph.

bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens=true) const

Return true if the Loop is in LCSSA form.

const MDOperand & getOperand(unsigned I) const

ArrayRef< MDOperand > operands() const

unsigned getNumOperands() const

Return number of MDNode operands.

Tracking metadata reference owned by Metadata.

StringRef getString() const

MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)

Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...

Encapsulates MemorySSA, including all data associated with memory accesses.

bool dominates(const MemoryAccess *A, const MemoryAccess *B) const

Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...

MemorySSAWalker * getWalker()

MemoryUseOrDef * getMemoryAccess(const Instruction *I) const

Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

This class represents an analyzed expression in the program.

The main scalar evolution driver.

unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)

Returns the largest constant divisor of the trip count as a normal unsigned value,...

const SCEV * getSCEV(Value *V)

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

unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)

Returns the upper bound of the loop trip count as a normal unsigned value.

bool isBackedgeTakenCountMaxOrZero(const Loop *L)

Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...

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

unsigned getSmallConstantTripCount(const Loop *L)

Returns the exact trip count of the loop if we can compute it, and the result is a small constant.

void insert(const K &Key, const V &Val)

V lookup(const K &Key) const

bool insert(const value_type &X)

Insert a new element into the SetVector.

A SetVector that performs no allocations if smaller than a certain size.

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

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

A Use represents the edge between a Value definition and its users.

iterator find(const KeyT &Val)

bool erase(const KeyT &Val)

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

int getNumOccurrences() const

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

self_iterator getIterator()

@ C

The default llvm calling convention, compatible with C.

BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)

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

apint_match m_APInt(const APInt *&Res)

Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

initializer< Ty > init(const Ty &Val)

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 drop_begin(T &&RangeOrContainer, size_t N=1)

Return a range covering RangeOrContainer with the first N elements excluded.

bool RemoveRedundantDbgInstrs(BasicBlock *BB)

Try to remove redundant dbg.value instructions from given basic block.

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

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

void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, AAResults *AA=nullptr)

Perform some cleanup and simplifications on loops after unrolling.

bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())

If the specified value is a trivially dead instruction, delete it.

auto successors(const MachineBasicBlock *BB)

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

Put a loop nest into LCSSA form.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, bool PreserveLCSSA, unsigned SCEVExpansionBudget, Loop **ResultLoop=nullptr)

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

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

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

void erase(Container &C, ValueType V)

Wrapper function to remove a value from a container:

cl::opt< bool > EnableFSDiscriminator

bool any_of(R &&range, UnaryPredicate P)

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

bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)

Return true if the result produced by the instruction is not used, and the instruction will return.

CallBase * getLoopConvergenceHeart(const Loop *TheLoop)

Find the convergence heart of the loop.

raw_ostream & dbgs()

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

bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, const TargetTransformInfo *TTI, SmallVectorImpl< WeakTrackingVH > &Dead)

SimplifyLoopIVs - Simplify users of induction variables within this loop.

SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)

Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...

LoopUnrollResult

Represents the result of a UnrollLoop invocation.

unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)

Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...

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

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

bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)

Attempts to merge a block into its predecessor, if possible.

bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, unsigned EstimatedLoopInvocationWeight)

Set a loop's branch weight metadata to reflect that loop has EstimatedTripCount iterations and Estima...

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.

const Loop * addClonedBlockToLoopInfo(BasicBlock *OriginalBB, BasicBlock *ClonedBB, LoopInfo *LI, NewLoopsMap &NewLoops)

Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary and adds a mapping from the o...

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

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

MDNode * GetUnrollMetadata(MDNode *LoopID, StringRef Name)

Given an llvm.loop loop id metadata node, returns the loop hint metadata node with the given name (fo...

LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const llvm::TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr, AAResults *AA=nullptr)

Unroll the given loop by Count.

LoadValue(Instruction *Inst, unsigned Generation)

Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...

const Instruction * Heart

bool AllowExpensiveTripCount

unsigned SCEVExpansionBudget