LoopFlatten.cpp Source File (original) (raw)

76#include

78using namespace llvm;

81#define DEBUG_TYPE "loop-flatten"

83 STATISTIC(NumFlattened, "Number of loops flattened");

87 cl::desc("Limit on the cost of instructions that can be repeated due to "

88 "loop flattening"));

93 cl::desc("Assume that the product of the two iteration "

94 "trip counts will never overflow"));

98 cl::desc("Widen the loop induction variables, if possible, so "

99 "overflow checks won't reject flattening"));

100

103 cl::desc("Version loops if flattened loop could overflow"));

104

105namespace {

106

107

108

109

110

111

112

113

114struct FlattenInfo {

115 Loop *OuterLoop = nullptr;

116 Loop *InnerLoop = nullptr;

117

118 PHINode *InnerInductionPHI = nullptr;

119 PHINode *OuterInductionPHI = nullptr;

120

121

122

123 Value *InnerTripCount = nullptr;

124 Value *OuterTripCount = nullptr;

125

126

127

129

130

131

132 BinaryOperator *InnerIncrement = nullptr;

133 BinaryOperator *OuterIncrement = nullptr;

134 BranchInst *InnerBranch = nullptr;

135

136 BranchInst *OuterBranch = nullptr;

137

138

140

141 bool Widened = false;

142

143

144 PHINode *NarrowInnerInductionPHI = nullptr;

145 PHINode *NarrowOuterInductionPHI = nullptr;

146

147

148

149 Value *NewTripCount = nullptr;

150

151 FlattenInfo(Loop *OL, Loop *IL) : OuterLoop(OL), InnerLoop(IL){};

152

153 bool isNarrowInductionPhi(PHINode *Phi) {

154

155 if (!Widened)

156 return false;

157 return NarrowInnerInductionPHI == Phi || NarrowOuterInductionPHI == Phi;

158 }

159 bool isInnerLoopIncrement(User *U) {

160 return InnerIncrement == U;

161 }

162 bool isOuterLoopIncrement(User *U) {

163 return OuterIncrement == U;

164 }

165 bool isInnerLoopTest(User *U) {

166 return InnerBranch->getCondition() == U;

167 }

168

169 bool checkOuterInductionPhiUsers(SmallPtrSet<Value *, 4> &ValidOuterPHIUses) {

170 for (User *U : OuterInductionPHI->users()) {

171 if (isOuterLoopIncrement(U))

172 continue;

173

174 auto IsValidOuterPHIUses = [&] (User *U) -> bool {

175 LLVM_DEBUG(dbgs() << "Found use of outer induction variable: "; U->dump());

176 if (!ValidOuterPHIUses.count(U)) {

177 LLVM_DEBUG(dbgs() << "Did not match expected pattern, bailing\n");

178 return false;

179 }

181 return true;

182 };

183

185 for (auto *K : V->users()) {

186 if (!IsValidOuterPHIUses(K))

187 return false;

188 }

189 continue;

190 }

191

192 if (!IsValidOuterPHIUses(U))

193 return false;

194 }

195 return true;

196 }

197

198 bool matchLinearIVUser(User *U, Value *InnerTripCount,

199 SmallPtrSet<Value *, 4> &ValidOuterPHIUses) {

200 LLVM_DEBUG(dbgs() << "Checking linear i*M+j expression for: "; U->dump());

201 Value *MatchedMul = nullptr;

202 Value *MatchedItCount = nullptr;

203

207 m_Value(MatchedItCount)));

208

209

210

211 bool IsAddTrunc =

215 m_Value(MatchedItCount)));

216

217

221 m_Value(MatchedItCount)));

222

223 if (!MatchedItCount)

224 return false;

225

226 LLVM_DEBUG(dbgs() << "Matched multiplication: "; MatchedMul->dump());

227 LLVM_DEBUG(dbgs() << "Matched iteration count: "; MatchedItCount->dump());

228

229

230

232 return !isInstructionTriviallyDead(cast(U));

233 }) > 1) {

234 LLVM_DEBUG(dbgs() << "Multiply has more than one use\n");

235 return false;

236 }

237

238

239

240 if (Widened && (IsAdd || IsGEP) &&

242 assert(MatchedItCount->getType() == InnerInductionPHI->getType() &&

243 "Unexpected type mismatch in types after widening");

247 }

248

249 LLVM_DEBUG(dbgs() << "Looking for inner trip count: ";

250 InnerTripCount->dump());

251

252 if ((IsAdd || IsAddTrunc || IsGEP) && MatchedItCount == InnerTripCount) {

253 LLVM_DEBUG(dbgs() << "Found. This sse is optimisable\n");

254 ValidOuterPHIUses.insert(MatchedMul);

255 LinearIVUses.insert(U);

256 return true;

257 }

258

259 LLVM_DEBUG(dbgs() << "Did not match expected pattern, bailing\n");

260 return false;

261 }

262

263 bool checkInnerInductionPhiUsers(SmallPtrSet<Value *, 4> &ValidOuterPHIUses) {

264 Value *SExtInnerTripCount = InnerTripCount;

265 if (Widened &&

267 SExtInnerTripCount = cast(InnerTripCount)->getOperand(0);

268

269 for (User *U : InnerInductionPHI->users()) {

271 if (isInnerLoopIncrement(U)) {

272 LLVM_DEBUG(dbgs() << "Use is inner loop increment, continuing\n");

273 continue;

274 }

275

276

277

279 if (->hasOneUse())

280 return false;

281 U = *U->user_begin();

282 }

283

284

285

286

287

288 if (isInnerLoopTest(U)) {

289 LLVM_DEBUG(dbgs() << "Use is the inner loop test, continuing\n");

290 continue;

291 }

292

293 if (!matchLinearIVUser(U, SExtInnerTripCount, ValidOuterPHIUses)) {

295 return false;

296 }

298 }

299 return true;

300 }

301};

302}

303

304static bool

307 TripCount = TC;

311 LLVM_DEBUG(dbgs() << "Successfully found all loop components\n");

312 return true;

313}

314

315

316

317

318

319

320

327 LLVM_DEBUG(dbgs() << "Backedge-taken count is not predictable\n");

328 return false;

329 }

330

331

332

333

334 const SCEV *SCEVTripCount =

336 BackedgeTakenCount->getType(), L);

337

339 if (SCEVRHS == SCEVTripCount)

342 if (ConstantRHS) {

343 const SCEV *BackedgeTCExt = nullptr;

344 if (IsWidened) {

345 const SCEV *SCEVTripCountExt;

346

347

350 RHS->getType(), L);

351 if (SCEVRHS != BackedgeTCExt && SCEVRHS != SCEVTripCountExt) {

352 LLVM_DEBUG(dbgs() << "Could not find valid trip count\n");

353 return false;

354 }

355 }

356

357

358 if (SCEVRHS == BackedgeTCExt || SCEVRHS == BackedgeTakenCount) {

359 Value *NewRHS = ConstantInt::get(ConstantRHS->getContext(),

360 ConstantRHS->getValue() + 1);

362 IterationInstructions);

363 }

365 }

366

367

368

369 if (!IsWidened) {

370 LLVM_DEBUG(dbgs() << "Could not find valid trip count\n");

371 return false;

372 }

374 if (!TripCountInst) {

375 LLVM_DEBUG(dbgs() << "Could not find valid trip count\n");

376 return false;

377 }

379 SE->getSCEV(TripCountInst->getOperand(0)) != SCEVTripCount) {

380 LLVM_DEBUG(dbgs() << "Could not find valid extended trip count\n");

381 return false;

382 }

384}

385

386

387

392 LLVM_DEBUG(dbgs() << "Finding components of loop: " << L->getName() << "\n");

393

394 if (!L->isLoopSimplifyForm()) {

395 LLVM_DEBUG(dbgs() << "Loop is not in normal form\n");

396 return false;

397 }

398

399

400

401 if (!L->isCanonical(*SE)) {

403 return false;

404 }

405

406

407

408 BasicBlock *Latch = L->getLoopLatch();

409 if (L->getExitingBlock() != Latch) {

410 LLVM_DEBUG(dbgs() << "Exiting and latch block are different\n");

411 return false;

412 }

413

414

415

416

417 InductionPHI = L->getInductionVariable(*SE);

418 if (!InductionPHI) {

419 LLVM_DEBUG(dbgs() << "Could not find induction PHI\n");

420 return false;

421 }

423

426 if (ContinueOnTrue)

428 else

430 };

431

432

433

434 ICmpInst *Compare = L->getLatchCmpInst();

435 if (!Compare || !IsValidPredicate(Compare->getUnsignedPredicate()) ||

436 Compare->hasNUsesOrMore(2)) {

437 LLVM_DEBUG(dbgs() << "Could not find valid comparison\n");

438 return false;

439 }

441 IterationInstructions.insert(BackBranch);

443 IterationInstructions.insert(Compare);

444 LLVM_DEBUG(dbgs() << "Found comparison: "; Compare->dump());

445

446

447

448

449

452 if ((Compare->getOperand(0) != Increment || ->hasNUses(2)) &&

454 LLVM_DEBUG(dbgs() << "Could not find valid increment\n");

455 return false;

456 }

457

458

459

460

461

462 Value *RHS = Compare->getOperand(1);

463

464 return verifyTripCount(RHS, L, IterationInstructions, InductionPHI, TripCount,

465 Increment, BackBranch, SE, IsWidened);

466}

467

469

470

471

472

473

474

475

476

477

478

479

480

481

482

484 SafeOuterPHIs.insert(FI.OuterInductionPHI);

485

486

487

489

490

491 if (&InnerPHI == FI.InnerInductionPHI)

492 continue;

493 if (FI.isNarrowInductionPhi(&InnerPHI))

494 continue;

495

496

497

498 assert(InnerPHI.getNumIncomingValues() == 2);

499 Value *PreHeaderValue =

500 InnerPHI.getIncomingValueForBlock(FI.InnerLoop->getLoopPreheader());

501 Value *LatchValue =

502 InnerPHI.getIncomingValueForBlock(FI.InnerLoop->getLoopLatch());

503

504

505

506

508 if (!OuterPHI || OuterPHI->getParent() != FI.OuterLoop->getHeader()) {

509 LLVM_DEBUG(dbgs() << "value modified in top of outer loop\n");

510 return false;

511 }

512

513

514

515

516

519 if (!LCSSAPHI) {

521 return false;

522 }

523

524

525

528 dbgs() << "LCSSA PHI incoming value does not match latch value\n");

529 return false;

530 }

531

535 SafeOuterPHIs.insert(OuterPHI);

536 FI.InnerPHIsToTransform.insert(&InnerPHI);

537 }

538

540 if (FI.isNarrowInductionPhi(&OuterPHI))

541 continue;

542 if (!SafeOuterPHIs.count(&OuterPHI)) {

543 LLVM_DEBUG(dbgs() << "found unsafe PHI in outer loop: "; OuterPHI.dump());

544 return false;

545 }

546 }

547

549 return true;

550}

551

552static bool

556

557

558

559

560

562 for (auto *B : FI.OuterLoop->getBlocks()) {

564 continue;

565

566 for (auto &I : *B) {

569 LLVM_DEBUG(dbgs() << "Cannot flatten because instruction may have "

570 "side effects: ";

571 I.dump());

572 return false;

573 }

574

575

576

577

578 if (IterationInstructions.count(&I))

579 continue;

580

581

585 continue;

586

587

590 continue;

594 RepeatedInstrCost += Cost;

595 }

596 }

597

598 LLVM_DEBUG(dbgs() << "Cost of instructions that will be repeated: "

599 << RepeatedInstrCost << "\n");

600

601

603 LLVM_DEBUG(dbgs() << "checkOuterLoopInsts: not profitable, bailing.\n");

604 return false;

605 }

606

608 return true;

609}

610

611

612

613

614

615

616

617

618

619

621

622

624 if (!FI.checkInnerInductionPhiUsers(ValidOuterPHIUses))

625 return false;

626

627

628

629 if (!FI.checkOuterInductionPhiUsers(ValidOuterPHIUses))

630 return false;

631

633 dbgs() << "Found " << FI.LinearIVUses.size()

634 << " value(s) that can be replaced:\n";

635 for (Value *V : FI.LinearIVUses) {

636 dbgs() << " ";

637 V->dump();

638 });

639 return true;

640}

641

642

643

648

649

652

653

654

656 FI.InnerTripCount, FI.OuterTripCount,

660 return OR;

661

663 for (Value *GEPUser : GEP->users()) {

666 !(isa(GEPUserInst) && GEP == GEPUserInst->getOperand(1)))

667 continue;

669 continue;

670

671

672

673

674 if (GEP->isInBounds() &&

675 GEPOperand->getType()->getIntegerBitWidth() >=

676 DL.getPointerTypeSizeInBits(GEP->getType())) {

678 dbgs() << "use of linear IV would be UB if overflow occurred: ";

679 GEP->dump());

680 return true;

681 }

682 }

683 return false;

684 };

685

686

687

688 for (Value *V : FI.LinearIVUses) {

690 if (GEP->getNumIndices() == 1 && CheckGEP(GEP, GEP->getOperand(1)))

694 if (CheckGEP(GEP, V))

696 }

697

699}

700

706 FI.InnerInductionPHI, FI.InnerTripCount,

707 FI.InnerIncrement, FI.InnerBranch, SE, FI.Widened))

708 return false;

710 FI.OuterInductionPHI, FI.OuterTripCount,

711 FI.OuterIncrement, FI.OuterBranch, SE, FI.Widened))

712 return false;

713

714

715

717 LLVM_DEBUG(dbgs() << "inner loop trip count not invariant\n");

718 return false;

719 }

721 LLVM_DEBUG(dbgs() << "outer loop trip count not invariant\n");

722 return false;

723 }

724

726 return false;

727

728

729 if (FI.InnerInductionPHI->getType() != FI.OuterInductionPHI->getType())

730 return false;

731

733 return false;

734

735

736

737

738

739

741 return false;

742

744 return true;

745}

746

752 LLVM_DEBUG(dbgs() << "Checks all passed, doing the transformation\n");

753 {

754 using namespace ore;

758 Remark << "Flattened into outer loop";

760 }

761

762 if (!FI.NewTripCount) {

763 FI.NewTripCount = BinaryOperator::CreateMul(

764 FI.InnerTripCount, FI.OuterTripCount, "flatten.tripcount",

766 LLVM_DEBUG(dbgs() << "Created new trip count in preheader: ";

767 FI.NewTripCount->dump());

768 }

769

770

771

773

774

775

776 for (PHINode *PHI : FI.InnerPHIsToTransform)

778

779

780

782

783

789 Term->eraseFromParent();

790

791

793 if (MSSAU)

795

796

797

799 for (Value *V : FI.LinearIVUses) {

800 Value *OuterValue = FI.OuterInductionPHI;

801 if (FI.Widened)

802 OuterValue = Builder.CreateTrunc(FI.OuterInductionPHI, V->getType(),

803 "flatten.trunciv");

804

806

808 Value *Base = InnerGEP->getOperand(0);

809

810

811 if (!DT->dominates(Base, &*Builder.GetInsertPoint()))

813 OuterValue =

814 Builder.CreateGEP(GEP->getSourceElementType(), Base, OuterValue,

815 "flatten." + V->getName(),

816 GEP->isInBounds() && InnerGEP->isInBounds());

817 }

818

820 OuterValue->dump());

822 }

823

824

825

828 if (U)

829 U->markLoopAsDeleted(*FI.InnerLoop, FI.InnerLoop->getName());

830 LI->erase(FI.InnerLoop);

831

832

833 NumFlattened++;

834

835 return true;

836}

837

841 if (!WidenIV) {

842 LLVM_DEBUG(dbgs() << "Widening the IVs is disabled\n");

843 return false;

844 }

845

848 auto &DL = M->getDataLayout();

849 auto *InnerType = FI.InnerInductionPHI->getType();

850 auto *OuterType = FI.OuterInductionPHI->getType();

851 unsigned MaxLegalSize = DL.getLargestLegalIntTypeSizeInBits();

852 auto *MaxLegalType = DL.getLargestLegalIntType(M->getContext());

853

854

855

856

857 if (InnerType != OuterType ||

858 InnerType->getScalarSizeInBits() >= MaxLegalSize ||

859 MaxLegalType->getScalarSizeInBits() <

860 InnerType->getScalarSizeInBits() * 2) {

862 return false;

863 }

864

867 unsigned ElimExt = 0;

868 unsigned Widened = 0;

869

870 auto CreateWideIV = [&](WideIVInfo WideIV, bool &Deleted) -> bool {

872 createWideIV(WideIV, LI, SE, Rewriter, DT, DeadInsts, ElimExt, Widened,

873 true , true );

874 if (!WidePhi)

875 return false;

879 return true;

880 };

881

883 if (!CreateWideIV({FI.InnerInductionPHI, MaxLegalType, false}, Deleted))

884 return false;

885

886

888 FI.InnerPHIsToTransform.insert(FI.InnerInductionPHI);

889

890 if (!CreateWideIV({FI.OuterInductionPHI, MaxLegalType, false}, Deleted))

891 return false;

892

893 assert(Widened && "Widened IV expected");

894 FI.Widened = true;

895

896

897 FI.NarrowInnerInductionPHI = FI.InnerInductionPHI;

898 FI.NarrowOuterInductionPHI = FI.OuterInductionPHI;

899

900

902}

903

910 dbgs() << "Loop flattening running on outer loop "

911 << FI.OuterLoop->getHeader()->getName() << " and inner loop "

914

916 return false;

917

918

919 bool CanFlatten = CanWidenIV(FI, DT, LI, SE, AC, TTI);

920

921

922

923

924

925

926

927

928

929

930

931

932 if (FI.Widened && !CanFlatten)

933 return true;

934

935

936 if (CanFlatten)

938

939

940

941

942

946 LLVM_DEBUG(dbgs() << "Multiply would always overflow, so not profitable\n");

947 return false;

952 LLVM_DEBUG(dbgs() << "Multiply might overflow, not flattening\n");

953 return false;

954 } else if (.isLegalInteger(

956

957

958

960 dbgs() << "Can't check overflow efficiently, not flattening\n");

961 return false;

962 }

963 LLVM_DEBUG(dbgs() << "Multiply might overflow, versioning loop\n");

964

965

966

967

970 LoopVersioning LVer(LAI, Checks, FI.OuterLoop, LI, DT, SE);

972

973

974

977 "Expected LoopVersioning to generate a conditional branch");

979 "Expected branch condition to be false");

981 Value *Call = Builder.CreateIntrinsic(

982 Intrinsic::umul_with_overflow, FI.OuterTripCount->getType(),

983 {FI.OuterTripCount, FI.InnerTripCount},

984 nullptr, "flatten.mul");

985 FI.NewTripCount = Builder.CreateExtractValue(Call, 0, "flatten.tripcount");

986 Value *Overflow = Builder.CreateExtractValue(Call, 1, "flatten.overflow");

988 } else {

989 LLVM_DEBUG(dbgs() << "Multiply cannot overflow, modifying loop in-place\n");

990 }

991

993}

994

998

1000

1001 std::optional MSSAU;

1002 if (AR.MSSA) {

1006 }

1007

1008

1009

1010

1011

1013 &AR.AC);

1016 if (!OuterLoop)

1017 continue;

1018 FlattenInfo FI(OuterLoop, InnerLoop);

1021 MSSAU ? &*MSSAU : nullptr, LAIM.getInfo(*OuterLoop));

1022 }

1023

1026

1029

1031 if (AR.MSSA)

1033 return PA;

1034}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

Module.h This file contains the declarations for the Module class.

static bool CanWidenIV(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)

Definition LoopFlatten.cpp:838

static bool verifyTripCount(Value *RHS, Loop *L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment, BranchInst *&BackBranch, ScalarEvolution *SE, bool IsWidened)

Definition LoopFlatten.cpp:321

static cl::opt< bool > WidenIV("loop-flatten-widen-iv", cl::Hidden, cl::init(true), cl::desc("Widen the loop induction variables, if possible, so " "overflow checks won't reject flattening"))

static bool setLoopComponents(Value *&TC, Value *&TripCount, BinaryOperator *&Increment, SmallPtrSetImpl< Instruction * > &IterationInstructions)

Definition LoopFlatten.cpp:305

static bool DoFlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI, LPMUpdater *U, MemorySSAUpdater *MSSAU)

Definition LoopFlatten.cpp:747

static bool FlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI, LPMUpdater *U, MemorySSAUpdater *MSSAU, const LoopAccessInfo &LAI)

Definition LoopFlatten.cpp:904

static bool checkIVUsers(FlattenInfo &FI)

Definition LoopFlatten.cpp:620

static bool CanFlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)

Definition LoopFlatten.cpp:701

static cl::opt< bool > VersionLoops("loop-flatten-version-loops", cl::Hidden, cl::init(true), cl::desc("Version loops if flattened loop could overflow"))

static bool findLoopComponents(Loop *L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment, BranchInst *&BackBranch, ScalarEvolution *SE, bool IsWidened)

Definition LoopFlatten.cpp:388

static OverflowResult checkOverflow(FlattenInfo &FI, DominatorTree *DT, AssumptionCache *AC)

Definition LoopFlatten.cpp:644

static bool checkPHIs(FlattenInfo &FI, const TargetTransformInfo *TTI)

Definition LoopFlatten.cpp:468

static cl::opt< unsigned > RepeatedInstructionThreshold("loop-flatten-cost-threshold", cl::Hidden, cl::init(2), cl::desc("Limit on the cost of instructions that can be repeated due to " "loop flattening"))

static cl::opt< bool > AssumeNoOverflow("loop-flatten-assume-no-overflow", cl::Hidden, cl::init(false), cl::desc("Assume that the product of the two iteration " "trip counts will never overflow"))

static bool checkOuterLoopInsts(FlattenInfo &FI, SmallPtrSetImpl< Instruction * > &IterationInstructions, const TargetTransformInfo *TTI)

Definition LoopFlatten.cpp:553

This file defines the interface for the loop nest analysis.

This header provides classes for managing a pipeline of passes over loops in LLVM IR.

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.

Virtual Register Rewriter

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

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

LLVM Basic Block Representation.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

const Function * getParent() const

Return the enclosing method, or null if none.

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.

void setCondition(Value *V)

bool isConditional() const

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

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

Value * getCondition() const

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

@ ICMP_ULT

unsigned less than

This is the shared class of boolean and integer constants.

const APInt & getValue() const

Return the constant as an APInt value reference.

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

void deleteEdge(NodeT *From, NodeT *To)

Inform the dominator tree about a CFG edge deletion and update the tree.

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

LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

an instruction for type-safe pointer arithmetic to access elements of arrays and structs

Module * getParent()

Get the module that this global value is contained inside of...

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

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

LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

Return the specified successor. This instruction must be a terminator.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

This class provides an interface for updating the loop pass manager based on mutations to the loop ne...

LLVM_ABI const LoopAccessInfo & getInfo(Loop &L, bool AllowPartial=false)

Drive the analysis of memory accesses in the loop.

bool contains(const LoopT *L) const

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

BlockT * getLoopLatch() const

If there is a single latch block for this loop, return it.

BlockT * getHeader() const

BlockT * getExitBlock() const

If getExitBlocks would return exactly one block, return that block.

BlockT * getLoopPreheader() const

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

ArrayRef< BlockT * > getBlocks() const

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

BlockT * getExitingBlock() const

If getExitingBlocks would return exactly one block, return that block.

LoopT * getParentLoop() const

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

PreservedAnalyses run(LoopNest &LN, LoopAnalysisManager &LAM, LoopStandardAnalysisResults &AR, LPMUpdater &U)

Definition LoopFlatten.cpp:995

LLVM_ABI void erase(Loop *L)

Update LoopInfo after removing the last backedge from a loop.

This class represents a loop nest and can be used to query its properties.

ArrayRef< Loop * > getLoops() const

Get the loops in the nest.

This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...

void versionLoop()

Performs the CFG manipulation part of versioning the loop including the DominatorTree and LoopInfo up...

Represents a single loop in the control flow graph.

DebugLoc getStartLoc() const

Return the debug location of the start of this loop.

bool isLoopInvariant(const Value *V) const

Return true if the specified value is loop invariant.

StringRef getName() const

An analysis that produces MemorySSA for a function.

LLVM_ABI void removeEdge(BasicBlock *From, BasicBlock *To)

Update the MemoryPhi in To following an edge deletion between From and To.

LLVM_ABI void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const

Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...

A Module instance is used to store all the information related to an LLVM module.

LLVM_ABI Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)

Remove an incoming value.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

LLVM_ABI Value * hasConstantValue() const

If the specified PHI node always merges together the same value, return the value,...

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.

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

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 * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)

If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...

LLVM_ABI const SCEV * getSCEV(Value *V)

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

LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)

A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...

LLVM_ABI void forgetLoop(const Loop *L)

This method should be called by the client when it has changed a loop in a way that may effect Scalar...

LLVM_ABI const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)

LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)

Called when the client has changed the disposition of values in a loop or block.

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

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

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

@ TCK_SizeAndLatency

The weighted sum of size and latency.

LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY

If this is a vector type, return the getPrimitiveSizeInBits value for the element type.

LLVM Value Representation.

Type * getType() const

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

LLVM_ABI void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

iterator_range< user_iterator > users()

LLVM_ABI LLVMContext & getContext() const

All values hold a context through their type.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

LLVM_ABI void dump() const

Support for debugging, callable in GDB: V->dump()

const ParentTy * getParent() const

self_iterator getIterator()

CastInst_match< OpTy, TruncInst > m_Trunc(const OpTy &Op)

Matches Trunc.

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

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

auto m_GEP(const OperandTypes &...Ops)

Matches GetElementPtrInst.

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

Matches a Add with LHS and RHS in either order.

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

is_zero m_Zero()

Match any null constant or a vector with all elements equal to 0.

BinaryOp_match< LHS, RHS, Instruction::Mul, true > m_c_Mul(const LHS &L, const RHS &R)

Matches a Mul with LHS and RHS in either order.

initializer< Ty > init(const Ty &Val)

@ User

could "use" a pointer

Add a small namespace to avoid name clashes with the classes used in the streaming interface.

NodeAddr< PhiNode * > Phi

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

@ NeverOverflows

Never overflows.

@ AlwaysOverflowsHigh

Always overflows in the direction of signed/unsigned max value.

@ AlwaysOverflowsLow

Always overflows in the direction of signed/unsigned min value.

@ MayOverflow

May or may not overflow.

decltype(auto) dyn_cast(const From &Val)

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

PHINode * createWideIV(const WideIVInfo &WI, LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter, DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, unsigned &NumElimExt, unsigned &NumWidened, bool HasGuards, bool UsePostIncrementRanges)

Widen Induction Variables - Extend the width of an IV to cover its widest uses.

LLVM_ABI bool isGuaranteedToExecuteForEveryIteration(const Instruction *I, const Loop *L)

Return true if this function can prove that the instruction I is executed for every iteration of the ...

LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)

Return true if the instruction does not have any effects besides calculating the result and does not ...

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

LLVM_ABI OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ, bool IsNSW=false)

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

LLVM_ABI bool VerifyMemorySSA

Enables verification of MemorySSA.

auto count_if(R &&Range, UnaryPredicate P)

Wrapper function around std::count_if to count the number of times an element satisfying a given pred...

decltype(auto) cast(const From &Val)

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

LLVM_ABI PreservedAnalyses getLoopPassPreservedAnalyses()

Returns the minimum set of Analyses that all loop passes must preserve.

LLVM_ABI bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)

If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...

@ Increment

Incrementally increasing token ID.

The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...

TargetTransformInfo & TTI

Collect information about induction variables that are used by sign/zero extend operations.