LoopDistribute.cpp Source File (original) (raw)

65#include

66#include

67#include

69using namespace llvm;

71#define LDIST_NAME "loop-distribute"

72#define DEBUG_TYPE LDIST_NAME

77 "llvm.loop.distribute.followup_all";

79 "llvm.loop.distribute.followup_coincident";

81 "llvm.loop.distribute.followup_sequential";

83 "llvm.loop.distribute.followup_fallback";

88 cl::desc("Turn on DominatorTree and LoopInfo verification "

89 "after Loop Distribution"),

93 "loop-distribute-non-if-convertible", cl::Hidden,

94 cl::desc("Whether to distribute into a loop that may not be "

95 "if-convertible by the loop vectorizer"),

100 cl::desc("The maximum number of SCEV checks allowed for Loop "

101 "Distribution"));

102

104 "loop-distribute-scev-check-threshold-with-pragma", cl::init(128),

106 cl::desc("The maximum number of SCEV checks allowed for Loop "

107 "Distribution for loop marked with #pragma clang loop "

108 "distribute(enable)"));

109

111 "enable-loop-distribute", cl::Hidden,

112 cl::desc("Enable the new, experimental LoopDistribution Pass"),

114

116

117 STATISTIC(NumLoopsDistributed, "Number of loops distributed");

118

119namespace {

120

121

122

123class InstPartition {

125

126public:

127 InstPartition(Instruction *I, Loop *L, bool DepCycle = false)

128 : DepCycle(DepCycle), OrigLoop(L) {

129 Set.insert(I);

130 }

131

132

133 bool hasDepCycle() const { return DepCycle; }

134

135

136 void add(Instruction *I) { Set.insert(I); }

137

138

143 bool empty() const { return Set.empty(); }

144

145

146

147 void moveTo(InstPartition &Other) {

148 Other.Set.insert_range(Set);

149 Set.clear();

150 Other.DepCycle |= DepCycle;

151 }

152

153

154

155 void populateUsedSet() {

156

157

158

159 for (auto *B : OrigLoop->getBlocks())

160 Set.insert(B->getTerminator());

161

162

163

164 SmallVector<Instruction *, 8> Worklist(Set.begin(), Set.end());

165 while (!Worklist.empty()) {

167

168 for (Value *V : I->operand_values()) {

170 if (I && OrigLoop->contains(I->getParent()) && Set.insert(I))

171 Worklist.push_back(I);

172 }

173 }

174 }

175

176

177

178

179

181 unsigned Index, LoopInfo *LI,

182 DominatorTree *DT) {

184 VMap, Twine(".ldist") + Twine(Index),

185 LI, DT, ClonedLoopBlocks);

186 return ClonedLoop;

187 }

188

189

190

191 const Loop *getClonedLoop() const { return ClonedLoop; }

192

193

194

195

196 Loop *getDistributedLoop() const {

197 return ClonedLoop ? ClonedLoop : OrigLoop;

198 }

199

200

201

203

204

205 void remapInstructions() {

207 }

208

209

210

211 void removeUnusedInsts() {

212 SmallVector<Instruction *, 8> Unused;

213

214 for (auto *Block : OrigLoop->getBlocks())

215 for (auto &Inst : *Block)

216 if (!Set.count(&Inst)) {

218 if (!VMap.empty())

220

222 "Branches are marked used early on");

223 Unused.push_back(NewInst);

224 }

225

226

227

228 for (auto *Inst : reverse(Unused)) {

230 if (!Inst->use_empty())

232 Inst->eraseFromParent();

233 }

234 }

235

236 void print(raw_ostream &OS) const {

237 OS << (DepCycle ? " (cycle)\n" : "\n");

238 for (auto *I : Set)

239

240 OS << " " << I->getParent()->getName() << ":" << *I << "\n";

241 }

242

243 void printBlocks(raw_ostream &OS) const {

244 for (auto *BB : getDistributedLoop()->getBlocks())

245 OS << *BB;

246 }

247

248private:

249

250 InstructionSet Set;

251

252

253 bool DepCycle;

254

255

256 Loop *OrigLoop;

257

258

259

260 Loop *ClonedLoop = nullptr;

261

262

263

264 SmallVector<BasicBlock *, 8> ClonedLoopBlocks;

265

266

267

268

270};

271

272

273

274class InstPartitionContainer {

275 using InstToPartitionIdT = DenseMap<Instruction *, int>;

276

277public:

278 InstPartitionContainer(Loop *L, LoopInfo *LI, DominatorTree *DT)

279 : L(L), LI(LI), DT(DT) {}

280

281

282 unsigned getSize() const { return PartitionContainer.size(); }

283

284

285

286 void addToCyclicPartition(Instruction *Inst) {

287

288 if (PartitionContainer.empty() || !PartitionContainer.back().hasDepCycle())

289 PartitionContainer.emplace_back(Inst, L, true);

290 else

291 PartitionContainer.back().add(Inst);

292 }

293

294

295

296

297

298

299 void addToNewNonCyclicPartition(Instruction *Inst) {

300 PartitionContainer.emplace_back(Inst, L);

301 }

302

303

304

305

306

307

308 void mergeAdjacentNonCyclic() {

309 mergeAdjacentPartitionsIf(

310 [](const InstPartition *P) { return ->hasDepCycle(); });

311 }

312

313

314

315 void mergeNonIfConvertible() {

316 mergeAdjacentPartitionsIf([&](const InstPartition *Partition) {

317 if (Partition->hasDepCycle())

318 return true;

319

320

321 bool seenStore = false;

322

323 for (auto *Inst : *Partition)

325 seenStore = true;

327 return false;

328 }

329 return seenStore;

330 });

331 }

332

333

334 void mergeBeforePopulating() {

335 mergeAdjacentNonCyclic();

337 mergeNonIfConvertible();

338 }

339

340

341

342

343

344

345

346

347 bool mergeToAvoidDuplicatedLoads() {

348 using LoadToPartitionT = DenseMap<Instruction *, InstPartition *>;

349 using ToBeMergedT = EquivalenceClasses<InstPartition *>;

350

351 LoadToPartitionT LoadToPartition;

352 ToBeMergedT ToBeMerged;

353

354

355

356

357 for (PartitionContainerT::iterator I = PartitionContainer.begin(),

358 E = PartitionContainer.end();

359 I != E; ++I) {

360 auto *PartI = &*I;

361

362

363

364 for (Instruction *Inst : *PartI)

366 bool NewElt;

367 LoadToPartitionT::iterator LoadToPart;

368

369 std::tie(LoadToPart, NewElt) =

370 LoadToPartition.insert(std::make_pair(Inst, PartI));

371 if (!NewElt) {

374 << "LDist: Merging partitions due to this load in multiple "

375 << "partitions: " << PartI << ", " << LoadToPart->second << "\n"

376 << *Inst << "\n");

377

378 auto PartJ = I;

379 do {

380 --PartJ;

381 ToBeMerged.unionSets(PartI, &*PartJ);

382 } while (&*PartJ != LoadToPart->second);

383 }

384 }

385 }

386 if (ToBeMerged.empty())

387 return false;

388

389

390

391 for (const auto &C : ToBeMerged) {

392 if (->isLeader())

393 continue;

394

395 auto PartI = C->getData();

396 for (auto *PartJ : make_range(std::next(ToBeMerged.member_begin(*C)),

397 ToBeMerged.member_end())) {

398 PartJ->moveTo(*PartI);

399 }

400 }

401

402

403 PartitionContainer.remove_if(

404 [](const InstPartition &P) { return P.empty(); });

405

406 return true;

407 }

408

409

410

411 void setupPartitionIdOnInstructions() {

412 int PartitionID = 0;

413 for (const auto &Partition : PartitionContainer) {

414 for (Instruction *Inst : Partition) {

415 bool NewElt;

417

418 std::tie(Iter, NewElt) =

419 InstToPartitionId.insert(std::make_pair(Inst, PartitionID));

420 if (!NewElt)

421 Iter->second = -1;

422 }

423 ++PartitionID;

424 }

425 }

426

427

428

429 void populateUsedSet() {

430 for (auto &P : PartitionContainer)

431 P.populateUsedSet();

432 }

433

434

435

436 void cloneLoops() {

437 BasicBlock *OrigPH = L->getLoopPreheader();

438

439

441 assert(Pred && "Preheader does not have a single predecessor");

442 BasicBlock *ExitBlock = L->getExitBlock();

443 assert(ExitBlock && "No single exit block");

444 Loop *NewLoop;

445

446 assert(!PartitionContainer.empty() && "at least two partitions expected");

447

448

450 "preheader not empty");

451

452

453 MDNode *OrigLoopID = L->getLoopID();

454

455

456

457

461 NewLoop = Part.cloneLoopWithPreheader(TopPH, Pred, Index, LI, DT);

462

463 Part.getVMap()[ExitBlock] = TopPH;

464 Part.remapInstructions();

465 setNewLoopID(OrigLoopID, &Part);

468 }

470

471

472 setNewLoopID(OrigLoopID, &PartitionContainer.back());

473

474

475

476

477 for (auto Curr = PartitionContainer.cbegin(),

478 Next = std::next(PartitionContainer.cbegin()),

479 E = PartitionContainer.cend();

481 DT->changeImmediateDominator(

482 Next->getDistributedLoop()->getLoopPreheader(),

483 Curr->getDistributedLoop()->getExitingBlock());

484 }

485

486

487 void removeUnusedInsts() {

488 for (auto &Partition : PartitionContainer)

489 Partition.removeUnusedInsts();

490 }

491

492

493

494

495

496

497

498 SmallVector<int, 8>

499 computePartitionSetForPointers(const LoopAccessInfo &LAI) {

501

502 unsigned N = RtPtrCheck->Pointers.size();

503 SmallVector<int, 8> PtrToPartitions(N);

504 for (unsigned I = 0; I < N; ++I) {

507 auto ReadInstructions =

509 Instructions.append(ReadInstructions.begin(), ReadInstructions.end());

510

511 int &Partition = PtrToPartitions[I];

512

513 Partition = -2;

514 for (Instruction *Inst : Instructions) {

515

516

517 int ThisPartition = this->InstToPartitionId[Inst];

518 if (Partition == -2)

519 Partition = ThisPartition;

520

521 else if (Partition == -1)

522 break;

523 else if (Partition != ThisPartition)

524 Partition = -1;

525 }

526 assert(Partition != -2 && "Pointer not belonging to any partition");

527 }

528

529 return PtrToPartitions;

530 }

531

532 void print(raw_ostream &OS) const {

533 unsigned Index = 0;

534 for (const auto &P : PartitionContainer) {

535 OS << "LDist: Partition " << Index++ << ":";

536 P.print(OS);

537 }

538 }

539

541

542#ifndef NDEBUG

543 friend raw_ostream &operator<<(raw_ostream &OS,

544 const InstPartitionContainer &Partitions) {

545 Partitions.print(OS);

546 return OS;

547 }

548#endif

549

550 void printBlocks(raw_ostream &OS) const {

551 unsigned Index = 0;

552 for (const auto &P : PartitionContainer) {

553 OS << "LDist: Partition " << Index++ << ":";

554 P.printBlocks(OS);

555 }

556 }

557

558private:

559 using PartitionContainerT = std::list;

560

561

562 PartitionContainerT PartitionContainer;

563

564

565

566 InstToPartitionIdT InstToPartitionId;

567

568 Loop *L;

569 LoopInfo *LI;

570 DominatorTree *DT;

571

572

573

574 template

575 void mergeAdjacentPartitionsIf(UnaryPredicate Predicate) {

576 InstPartition *PrevMatch = nullptr;

577 for (auto I = PartitionContainer.begin(); I != PartitionContainer.end();) {

579 if (PrevMatch == nullptr && DoesMatch) {

580 PrevMatch = &*I;

581 ++I;

582 } else if (PrevMatch != nullptr && DoesMatch) {

583 I->moveTo(*PrevMatch);

584 I = PartitionContainer.erase(I);

585 } else {

586 PrevMatch = nullptr;

587 ++I;

588 }

589 }

590 }

591

592

593 void setNewLoopID(MDNode *OrigLoopID, InstPartition *Part) {

595 OrigLoopID,

599 if (PartitionID) {

600 Loop *NewLoop = Part->getDistributedLoop();

601 NewLoop->setLoopID(*PartitionID);

602 }

603 }

604};

605

606

607

608

609

610

611

612class MemoryInstructionDependences {

613 using Dependence = MemoryDepChecker::Dependence;

614

615public:

616 struct Entry {

618 unsigned NumUnsafeDependencesStartOrEnd = 0;

619

620 Entry(Instruction *Inst) : Inst(Inst) {}

621 };

622

623 using AccessesType = SmallVector<Entry, 8>;

624

627

628 MemoryInstructionDependences(

629 const SmallVectorImpl<Instruction *> &Instructions,

630 const SmallVectorImpl &Dependences) {

632

633 LLVM_DEBUG(dbgs() << "LDist: Backward dependences:\n");

634 for (const auto &Dep : Dependences)

635 if (Dep.isPossiblyBackward()) {

636

637

638

639 ++Accesses[Dep.Source].NumUnsafeDependencesStartOrEnd;

640 --Accesses[Dep.Destination].NumUnsafeDependencesStartOrEnd;

641

643 }

644 }

645

646private:

647 AccessesType Accesses;

648};

649

650

651class LoopDistributeForLoop {

652public:

653 LoopDistributeForLoop(Loop *L, Function *F, LoopInfo *LI, DominatorTree *DT,

654 ScalarEvolution *SE, LoopAccessInfoManager &LAIs,

655 OptimizationRemarkEmitter *ORE)

656 : L(L), F(F), LI(LI), DT(DT), SE(SE), LAIs(LAIs), ORE(ORE) {

657 setForced();

658 }

659

660

661 bool processLoop() {

662 assert(L->isInnermost() && "Only process inner loops.");

663

665 << L->getHeader()->getParent()->getName() << "' from "

666 << L->getLocStr() << "\n");

667

668

669 if (!L->getExitBlock())

670 return fail("MultipleExitBlocks", "multiple exit blocks");

671 if (!L->isLoopSimplifyForm())

672 return fail("NotLoopSimplifyForm",

673 "loop is not in loop-simplify form");

674 if (!L->isRotatedForm())

675 return fail("NotBottomTested", "loop is not bottom tested");

676

677 BasicBlock *PH = L->getLoopPreheader();

678

679 LAI = &LAIs.getInfo(*L);

680

681

682

683 if (LAI->canVectorizeMemory())

684 return fail("MemOpsCanBeVectorized",

685 "memory operations are safe for vectorization");

686

687 auto *Dependences = LAI->getDepChecker().getDependences();

688 if (!Dependences || Dependences->empty())

689 return fail("NoUnsafeDeps", "no unsafe dependences to isolate");

690

691 LLVM_DEBUG(dbgs() << "LDist: Found a candidate loop: "

692 << L->getHeader()->getName() << "\n");

693

694 InstPartitionContainer Partitions(L, LI, DT);

695

696

697

698

699

700

701

702

703

704

705

706

707

708

709

710

711

712

713

714

715 const MemoryDepChecker &DepChecker = LAI->getDepChecker();

717 *Dependences);

718

719 int NumUnsafeDependencesActive = 0;

720 for (const auto &InstDep : MID) {

722

723

724 if (NumUnsafeDependencesActive ||

725 InstDep.NumUnsafeDependencesStartOrEnd > 0)

726 Partitions.addToCyclicPartition(I);

727 else

728 Partitions.addToNewNonCyclicPartition(I);

729 NumUnsafeDependencesActive += InstDep.NumUnsafeDependencesStartOrEnd;

730 assert(NumUnsafeDependencesActive >= 0 &&

731 "Negative number of dependences active");

732 }

733

734

735

736

737

738

740 for (auto *Inst : DefsUsedOutside)

741 Partitions.addToNewNonCyclicPartition(Inst);

742

743 LLVM_DEBUG(dbgs() << "LDist: Seeded partitions:\n" << Partitions);

744 if (Partitions.getSize() < 2)

745 return fail("CantIsolateUnsafeDeps",

746 "cannot isolate unsafe dependencies");

747

748

749

750 Partitions.mergeBeforePopulating();

751 LLVM_DEBUG(dbgs() << "LDist: Merged partitions:\n" << Partitions);

752 if (Partitions.getSize() < 2)

753 return fail("CantIsolateUnsafeDeps",

754 "cannot isolate unsafe dependencies");

755

756

757 Partitions.populateUsedSet();

758 LLVM_DEBUG(dbgs() << "LDist: Populated partitions:\n" << Partitions);

759

760

761

762 if (Partitions.mergeToAvoidDuplicatedLoads()) {

763 LLVM_DEBUG(dbgs() << "LDist: Partitions merged to ensure unique loads:\n"

764 << Partitions);

765 if (Partitions.getSize() < 2)

766 return fail("CantIsolateUnsafeDeps",

767 "cannot isolate unsafe dependencies");

768 }

769

770

771

772 const SCEVPredicate &Pred = LAI->getPSE().getPredicate();

773 if (LAI->hasConvergentOp() && !Pred.isAlwaysTrue()) {

774 return fail("RuntimeCheckWithConvergent",

775 "may not insert runtime check with convergent operation");

776 }

777

778 if (Pred.getComplexity() > (IsForced.value_or(false)

781 return fail("TooManySCEVRuntimeChecks",

782 "too many SCEV run-time checks needed.\n");

783

785 return fail("HeuristicDisabled", "distribution heuristic disabled");

786

788 << L->getHeader()->getName() << "\n");

789

790

791 Partitions.setupPartitionIdOnInstructions();

792

793

794 auto PtrToPartition = Partitions.computePartitionSetForPointers(*LAI);

795 const auto *RtPtrChecking = LAI->getRuntimePointerChecking();

796 const auto &AllChecks = RtPtrChecking->getChecks();

797 auto Checks = includeOnlyCrossPartitionChecks(AllChecks, PtrToPartition,

798 RtPtrChecking);

799

800 if (LAI->hasConvergentOp() && !Checks.empty()) {

801 return fail("RuntimeCheckWithConvergent",

802 "may not insert runtime check with convergent operation");

803 }

804

805

806

807

810

811 if (!Pred.isAlwaysTrue() || !Checks.empty()) {

812 assert(!LAI->hasConvergentOp() && "inserting illegal loop versioning");

813

814 MDNode *OrigLoopID = L->getLoopID();

815

817 LLVM_DEBUG(LAI->getRuntimePointerChecking()->printChecks(dbgs(), Checks));

818 LoopVersioning LVer(*LAI, Checks, L, LI, DT, SE);

819 LVer.versionLoop(DefsUsedOutside);

820 LVer.annotateLoopWithNoAlias();

821

822

823

824

826 OrigLoopID,

828 "llvm.loop.distribute.", true);

829 LVer.getNonVersionedLoop()->setLoopID(UnversionedLoopID);

831 true);

832 }

833

834

835

836 Partitions.cloneLoops();

837

838

839

840 Partitions.removeUnusedInsts();

841 LLVM_DEBUG(dbgs() << "LDist: After removing unused Instrs:\n");

843

845 LI->verify(*DT);

846 assert(DT->verify(DominatorTree::VerificationLevel::Fast));

847 }

848

849 ++NumLoopsDistributed;

850

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

852 return OptimizationRemark(LDIST_NAME, "Distribute", L->getStartLoc(),

853 L->getHeader())

854 << "distributed loop";

855 });

856 return true;

857 }

858

859

860 bool fail(StringRef RemarkName, StringRef Message) {

861 LLVMContext &Ctx = F->getContext();

862 bool Forced = isForced().value_or(false);

863

864 LLVM_DEBUG(dbgs() << "LDist: Skipping; " << Message << "\n");

865

866

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

868 return OptimizationRemarkMissed(LDIST_NAME, "NotDistributed",

869 L->getStartLoc(), L->getHeader())

870 << "loop not distributed: use -Rpass-analysis=loop-distribute for "

871 "more "

872 "info";

873 });

874

875

876

877 ORE->emit(OptimizationRemarkAnalysis(

879 RemarkName, L->getStartLoc(), L->getHeader())

880 << "loop not distributed: " << Message);

881

882

883

884 if (Forced)

885 Ctx.diagnose(DiagnosticInfoOptimizationFailure(

886 *F, L->getStartLoc(), "loop not distributed: failed "

887 "explicitly specified loop distribution"));

888

889 return false;

890 }

891

892

893

894

895

896

897 const std::optional &isForced() const { return IsForced; }

898

899private:

900

901

902

903

904

905 SmallVector<RuntimePointerCheck, 4> includeOnlyCrossPartitionChecks(

906 const SmallVectorImpl &AllChecks,

907 const SmallVectorImpl &PtrToPartition,

908 const RuntimePointerChecking *RtPtrChecking) {

909 SmallVector<RuntimePointerCheck, 4> Checks;

910

911 copy_if(AllChecks, std::back_inserter(Checks),

913 for (unsigned PtrIdx1 : Check.first->Members)

914 for (unsigned PtrIdx2 : Check.second->Members)

915

916

917

918

919

920

921

922

923

924

925

926

927

928 if (RtPtrChecking->needsChecking(PtrIdx1, PtrIdx2) &&

930 PtrToPartition, PtrIdx1, PtrIdx2))

931 return true;

932 return false;

933 });

934

935 return Checks;

936 }

937

938

939

940 void setForced() {

941 std::optional<const MDOperand *> Value =

944 return;

945

946 const MDOperand *Op = *Value;

949 }

950

951 Loop *L;

953

954

955 LoopInfo *LI;

956 const LoopAccessInfo *LAI = nullptr;

957 DominatorTree *DT;

958 ScalarEvolution *SE;

959 LoopAccessInfoManager &LAIs;

960 OptimizationRemarkEmitter *ORE;

961

962

963

964

965

966

967

968 std::optional IsForced;

969};

970

971}

972

976

977

978

980

981 for (Loop *TopLevelLoop : *LI)

983

984 if (L->isInnermost())

986

987

989 for (Loop *L : Worklist) {

990 LoopDistributeForLoop LDL(L, &F, LI, DT, SE, LAIs, ORE);

991

992

995 dbgs() << "LDist: Distributed loop guarded for reprocessing\n");

996 continue;

997 }

998

999

1000

1002 Changed |= LDL.processLoop();

1003 }

1004

1005

1007}

1008

1015

1023 return PA;

1024}

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

static void fail(const SDLoc &DL, SelectionDAG &DAG, const Twine &Msg, SDValue Val={})

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

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

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

This file defines the DenseMap class.

This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.

Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...

static bool runImpl(Function &F, const TargetLowering &TLI, const LibcallLoweringInfo &Libcalls, AssumptionCache *AC)

This is the interface for a simple mod/ref and alias analysis over globals.

This header defines various interfaces for pass management in LLVM.

This header provides classes for managing per-loop analyses.

static const char *const LLVMLoopDistributeFollowupCoincident

Definition LoopDistribute.cpp:78

static cl::opt< bool > DistributeNonIfConvertible("loop-distribute-non-if-convertible", cl::Hidden, cl::desc("Whether to distribute into a loop that may not be " "if-convertible by the loop vectorizer"), cl::init(false))

static cl::opt< bool > EnableLoopDistribute("enable-loop-distribute", cl::Hidden, cl::desc("Enable the new, experimental LoopDistribution Pass"), cl::init(false))

static cl::opt< unsigned > DistributeSCEVCheckThreshold("loop-distribute-scev-check-threshold", cl::init(8), cl::Hidden, cl::desc("The maximum number of SCEV checks allowed for Loop " "Distribution"))

#define LDIST_NAME

Definition LoopDistribute.cpp:71

static const char *const LLVMLoopDistributeFollowupSequential

Definition LoopDistribute.cpp:80

static const char *const LLVMLoopDistributeFollowupAll

Definition LoopDistribute.cpp:76

static const char * DistributedMetaData

Definition LoopDistribute.cpp:115

static cl::opt< unsigned > PragmaDistributeSCEVCheckThreshold("loop-distribute-scev-check-threshold-with-pragma", cl::init(128), cl::Hidden, cl::desc("The maximum number of SCEV checks allowed for Loop " "Distribution for loop marked with #pragma clang loop " "distribute(enable)"))

static const char *const LLVMLoopDistributeFollowupFallback

Definition LoopDistribute.cpp:82

static bool runImpl(Function &F, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE, OptimizationRemarkEmitter *ORE, LoopAccessInfoManager &LAIs)

Definition LoopDistribute.cpp:973

static cl::opt< bool > LDistVerify("loop-distribute-verify", cl::Hidden, cl::desc("Turn on DominatorTree and LoopInfo verification " "after Loop Distribution"), cl::init(false))

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)

This pass exposes codegen information to IR-level passes.

static unsigned getSize(unsigned Kind)

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

iterator begin()

Instruction iterator methods.

LLVM_ABI const BasicBlock * getSinglePredecessor() const

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

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

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator

Analysis pass which computes a DominatorTree.

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

LLVM_ABI void diagnose(const DiagnosticInfo &DI)

Report a message to the currently installed diagnostic handler.

This analysis provides dependence information for the memory accesses of a loop.

const RuntimePointerChecking * getRuntimePointerChecking() const

static LLVM_ABI bool blockNeedsPredication(const BasicBlock *BB, const Loop *TheLoop, const DominatorTree *DT)

Return true if the block BB needs to be predicated in order for the loop to be vectorized.

SmallVector< Instruction *, 4 > getInstructionsForAccess(Value *Ptr, bool isWrite) const

Return the list of instructions that use Ptr to read or write memory.

Analysis pass that exposes the LoopInfo for a function.

BlockT * getLoopPreheader() const

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

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition LoopDistribute.cpp:1009

Represents a single loop in the control flow graph.

void setLoopID(MDNode *LoopID) const

Set the llvm.loop loop id metadata for this loop.

const SmallVectorImpl< Instruction * > & getMemoryInstructions() const

The vector of memory access instructions.

static LLVM_ABI PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

LLVM_ABI bool needsChecking(const RuntimeCheckingPtrGroup &M, const RuntimeCheckingPtrGroup &N) const

Decide if we need to add a check between two groups of pointers, according to needsChecking.

static LLVM_ABI bool arePointersInSamePartition(const SmallVectorImpl< int > &PtrToPartition, unsigned PtrIdx1, unsigned PtrIdx2)

Check if pointers are in the same partition.

SmallVector< PointerInfo, 2 > Pointers

Information about the pointers that may require checking.

virtual unsigned getComplexity() const

Returns the estimated complexity of this predicate.

virtual bool isAlwaysTrue() const =0

Returns true if the predicate is always true.

Analysis pass that exposes the ScalarEvolution for a function.

The main scalar evolution driver.

typename vector_type::const_iterator iterator

typename vector_type::const_iterator const_iterator

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

void push_back(const T &Elt)

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

LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)

Replace uses of one Value with another.

const ParentTy * getParent() const

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

Predicate

Predicate - These are "(BI << 5) | BO" for various predicates.

initializer< Ty > init(const Ty &Val)

std::enable_if_t< detail::IsValidPointer< X, Y >::value, bool > hasa(Y &&MD)

Check whether Metadata has a Value.

std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > extract(Y &&MD)

Extract a Value from Metadata.

friend class Instruction

Iterator for Instructions in a `BasicBlock.

LLVM_ABI iterator begin() const

This is an optimization pass for GlobalISel generic memory operations.

auto drop_begin(T &&RangeOrContainer, size_t N=1)

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

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

FunctionAddr VTableAddr Value

Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)

std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck

A memcheck which made up of a pair of grouped pointers.

LLVM_ABI std::optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)

decltype(auto) dyn_cast(const From &Val)

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

LLVM_ABI std::optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)

Find string metadata for loop.

LLVM_ABI void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)

Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

LLVM_ABI std::optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)

Create a new loop identifier for a loop created from a loop transformation.

OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)

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

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

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

LLVM_ABI SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)

Returns the instructions that use values defined in the loop.

auto reverse(ContainerTy &&C)

LLVM_ABI Loop * cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, Loop *OrigLoop, ValueToValueMapTy &VMap, const Twine &NameSuffix, LoopInfo *LI, DominatorTree *DT, SmallVectorImpl< BasicBlock * > &Blocks)

Clones a loop OrigLoop.

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI bool hasDisableAllTransformsHint(const Loop *L)

Look for the loop attribute that disables all transformation heuristic.

bool isa(const From &Val)

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

FunctionAddr VTableAddr Next

DWARFExpression::Operation Op

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

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

Remaps instructions in Blocks using the mapping in VMap.

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

decltype(auto) cast(const From &Val)

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

LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)

Split the specified block at the specified instruction.

iterator_range< df_iterator< T > > depth_first(const T &G)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.