LoopCacheAnalysis.cpp Source File (original) (raw)

41using namespace llvm;

43#define DEBUG_TYPE "loop-cache-cost"

47 cl::desc("Use this to specify the default trip count of a loop"));

54 cl::desc("Use this to specify the max. distance between array elements "

55 "accessed in a loop so that the elements are classified to have "

56 "temporal reuse"));

63 assert( Loops .empty() && "Expecting a non-empy loop vector");

68 if (ParentLoop == nullptr) {

69 assert(Loops.size() == 1 && "Expecting a single loop");

70 return LastLoop;

71 }

74 [](const Loop *L1, const Loop *L2) {

76 }))

77 ? LastLoop

78 : nullptr;

79}

85 return false;

93 return false;

97 return false;

102

103 return StepRec == &ElemSize;

104}

105

106

107

108

115 : nullptr;

116

117 if (!TripCount) {

118 LLVM_DEBUG(dbgs() << "Trip count of loop " << L.getName()

119 << " could not be computed, using DefaultTripCount\n");

121 }

122

123 return TripCount;

124}

125

126

127

128

130 if (!R.IsValid) {

131 OS << R.StoreOrLoadInst;

132 OS << ", IsValid=false.";

133 return OS;

134 }

135

136 OS << *R.BasePointer;

137 for (const SCEV *Subscript : R.Subscripts)

138 OS << "[" << *Subscript << "]";

139

140 OS << ", Sizes: ";

141 for (const SCEV *Size : R.Sizes)

142 OS << "[" << *Size << "]";

143

144 return OS;

145}

146

149 : StoreOrLoadInst(StoreOrLoadInst), SE(SE) {

151 "Expecting a load or store instruction");

152

153 IsValid = delinearize(LI);

154 if (IsValid)

156 << "\n");

157}

158

159std::optional

162 assert(IsValid && "Expecting a valid reference");

163

164 if (BasePointer != Other.getBasePointer() && !isAliased(Other, AA)) {

166 << "No spacial reuse: different base pointers\n");

167 return false;

168 }

169

171 if (NumSubscripts != Other.getNumSubscripts()) {

173 << "No spacial reuse: different number of subscripts\n");

174 return false;

175 }

176

177

178 for (auto SubNum : seq(0, NumSubscripts - 1)) {

182 << *Other.getSubscript(SubNum) << "\n");

183 return false;

184 }

185 }

186

187

188

190 const SCEV *OtherLastSubscript = Other.getLastSubscript();

192 SE.getMinusSCEV(LastSubscript, OtherLastSubscript));

193

194 if (Diff == nullptr) {

196 << "No spacial reuse, difference between subscript:\n\t"

197 << *LastSubscript << "\n\t" << OtherLastSubscript

198 << "\nis not constant.\n");

199 return std::nullopt;

200 }

201

202 bool InSameCacheLine = (Diff->getValue()->getSExtValue() < CLS);

203

205 if (InSameCacheLine)

206 dbgs().indent(2) << "Found spacial reuse.\n";

207 else

208 dbgs().indent(2) << "No spacial reuse.\n";

209 });

210

211 return InSameCacheLine;

212}

213

214std::optional

216 unsigned MaxDistance, const Loop &L,

218 assert(IsValid && "Expecting a valid reference");

219

220 if (BasePointer != Other.getBasePointer() && !isAliased(Other, AA)) {

222 << "No temporal reuse: different base pointer\n");

223 return false;

224 }

225

226 std::unique_ptr D =

227 DI.depends(&StoreOrLoadInst, &Other.StoreOrLoadInst);

228

229 if (D == nullptr) {

231 return false;

232 }

233

234 if (D->isLoopIndependent()) {

236 return true;

237 }

238

239

240

241

242 int LoopDepth = L.getLoopDepth();

243 int Levels = D->getLevels();

244 for (int Level = 1; Level <= Levels; ++Level) {

245 const SCEV *Distance = D->getDistance(Level);

247

248 if (SCEVConst == nullptr) {

250 return std::nullopt;

251 }

252

254 if (Level != LoopDepth && !CI.isZero()) {

256 << "No temporal reuse: distance is not zero at depth=" << Level

257 << "\n");

258 return false;

259 } else if (Level == LoopDepth && CI.getSExtValue() > MaxDistance) {

262 << "No temporal reuse: distance is greater than MaxDistance at depth="

263 << Level << "\n");

264 return false;

265 }

266 }

267

269 return true;

270}

271

273 unsigned CLS) const {

274 assert(IsValid && "Expecting a valid reference");

276 dbgs().indent(2) << "Computing cache cost for:\n";

278 });

279

280

281 if (isLoopInvariant(L)) {

283 return 1;

284 }

285

287 assert(TripCount && "Expecting valid TripCount");

288 LLVM_DEBUG(dbgs() << "TripCount=" << *TripCount << "\n");

289

290 const SCEV *RefCost = nullptr;

291 const SCEV *Stride = nullptr;

292 if (isConsecutive(L, Stride, CLS)) {

293

294

295 assert(Stride != nullptr &&

296 "Stride should not be null for consecutive access!");

297 Type *WiderType = SE.getWiderType(Stride->getType(), TripCount->getType());

299 Stride = SE.getNoopOrAnyExtend(Stride, WiderType);

300 TripCount = SE.getNoopOrZeroExtend(TripCount, WiderType);

301 const SCEV *Numerator = SE.getMulExpr(Stride, TripCount);

302

303

304

305

306

307 RefCost = SE.getUDivCeilSCEV(Numerator, CacheLineSize);

308

310 << "Access is consecutive: RefCost=(TripCount*Stride)/CLS="

311 << *RefCost << "\n");

312 } else {

313

314

315

316

317

318

319

320 RefCost = TripCount;

321

322 int Index = getSubscriptIndex(L);

323 assert(Index >= 0 && "Could not locate a valid Index");

324

327 assert(AR && AR->getLoop() && "Expecting valid loop");

328 const SCEV *TripCount =

330 Type *WiderType = SE.getWiderType(RefCost->getType(), TripCount->getType());

331

333 RefCost = SE.getMulExpr(SE.getNoopOrZeroExtend(RefCost, WiderType),

334 SE.getNoopOrZeroExtend(TripCount, WiderType));

335 }

336

338 << "Access is not consecutive: RefCost=" << *RefCost << "\n");

339 }

340 assert(RefCost && "Expecting a valid RefCost");

341

342

343

344

345

347 return ConstantCost->getValue()->getLimitedValue(

348 std::numeric_limits<int64_t>::max());

349

351 << "RefCost is not a constant! Setting to RefCost=InvalidCost "

352 "(invalid value).\n");

353

355}

356

357bool IndexedReference::tryDelinearizeFixedSize(

359 const SCEV *ElementSize) {

362 Sizes.clear();

363 return false;

364 }

365

366

367

368

369

370

371#ifndef NDEBUG

372 assert(!Sizes.empty() && Subscripts.size() == Sizes.size() &&

373 "Inconsistent length of Sizes and Subscripts");

374 Type *WideTy =

378 assert(ElemSizeExt == LastSizeExt && "Unexpected last element of Sizes");

379#endif

380

381 Sizes.pop_back();

382 return true;

383}

384

385bool IndexedReference::delinearize(const LoopInfo &LI) {

386 assert(Subscripts.empty() && "Subscripts should be empty");

387 assert(Sizes.empty() && "Sizes should be empty");

388 assert(!IsValid && "Should be called once from the constructor");

389 LLVM_DEBUG(dbgs() << "Delinearizing: " << StoreOrLoadInst << "\n");

390

391 const SCEV *ElemSize = SE.getElementSize(&StoreOrLoadInst);

392 const BasicBlock *BB = StoreOrLoadInst.getParent();

393

395 const SCEV *AccessFn =

397

399 if (BasePointer == nullptr) {

401 dbgs().indent(2)

402 << "ERROR: failed to delinearize, can't identify base pointer\n");

403 return false;

404 }

405

406 bool IsFixedSize = false;

407

408 if (tryDelinearizeFixedSize(AccessFn, Subscripts, ElemSize)) {

409 IsFixedSize = true;

410

411 Sizes.push_back(ElemSize);

412 LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()

413 << "', AccessFn: " << *AccessFn << "\n");

414 }

415

416 AccessFn = SE.getMinusSCEV(AccessFn, BasePointer);

417

418

419 if (!IsFixedSize) {

420 LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()

421 << "', AccessFn: " << *AccessFn << "\n");

423 SE.getElementSize(&StoreOrLoadInst));

424 }

425

426 if (Subscripts.empty() || Sizes.empty() ||

427 Subscripts.size() != Sizes.size()) {

428

429

432 << "ERROR: failed to delinearize reference\n");

433 Subscripts.clear();

434 Sizes.clear();

435 return false;

436 }

437

438

439

440

441

442

444 const SCEV *StepRec = AccessFnAR ? AccessFnAR->getStepRecurrence(SE) : nullptr;

445

446 if (StepRec && SE.isKnownNegative(StepRec))

447 AccessFn = SE.getAddRecExpr(

448 AccessFnAR->getStart(), SE.getNegativeSCEV(StepRec),

450 const SCEV *Div = SE.getUDivExactExpr(AccessFn, ElemSize);

451 Subscripts.push_back(Div);

452 Sizes.push_back(ElemSize);

453 }

454

455 return all_of(Subscripts, [&](const SCEV *Subscript) {

456 return isSimpleAddRecurrence(*Subscript, *L);

457 });

458 }

459

460 return false;

461}

462

463bool IndexedReference::isLoopInvariant(const Loop &L) const {

465 assert(Addr != nullptr && "Expecting either a load or a store instruction");

466 assert(SE.isSCEVable(Addr->getType()) && "Addr should be SCEVable");

467

468 if (SE.isLoopInvariant(SE.getSCEV(Addr), &L))

469 return true;

470

471

472

473 bool allCoeffForLoopAreZero = all_of(Subscripts, [&](const SCEV *Subscript) {

474 return isCoeffForLoopZeroOrInvariant(*Subscript, L);

475 });

476

477 return allCoeffForLoopAreZero;

478}

479

480bool IndexedReference::isConsecutive(const Loop &L, const SCEV *&Stride,

481 unsigned CLS) const {

482

483

484 const SCEV *LastSubscript = Subscripts.back();

485 for (const SCEV *Subscript : Subscripts) {

486 if (Subscript == LastSubscript)

487 continue;

488 if (!isCoeffForLoopZeroOrInvariant(*Subscript, L))

489 return false;

490 }

491

492

493 const SCEV *Coeff = getLastCoefficient();

494 const SCEV *ElemSize = Sizes.back();

495 Type *WiderType = SE.getWiderType(Coeff->getType(), ElemSize->getType());

496

497

498

499

500

501

502

503

504

505

506 Stride = SE.getMulExpr(SE.getNoopOrSignExtend(Coeff, WiderType),

507 SE.getNoopOrSignExtend(ElemSize, WiderType));

509

510 Stride = SE.isKnownNegative(Stride) ? SE.getNegativeSCEV(Stride) : Stride;

512}

513

514int IndexedReference::getSubscriptIndex(const Loop &L) const {

517 if (AR && AR->getLoop() == &L) {

518 return Idx;

519 }

520 }

521 return -1;

522}

523

524const SCEV *IndexedReference::getLastCoefficient() const {

528}

529

530bool IndexedReference::isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,

531 const Loop &L) const {

533 return (AR != nullptr) ? AR->getLoop() != &L

534 : SE.isLoopInvariant(&Subscript, &L);

535}

536

537bool IndexedReference::isSimpleAddRecurrence(const SCEV &Subscript,

538 const Loop &L) const {

540 return false;

541

543 assert(AR->getLoop() && "AR should have a loop");

544

546 return false;

547

550

551 if (!SE.isLoopInvariant(Start, &L) || !SE.isLoopInvariant(Step, &L))

552 return false;

553

554 return true;

555}

556

562}

563

564

565

566

568 for (const auto &LC : CC.LoopCosts) {

569 const Loop *L = LC.first;

570 OS << "Loop '" << L->getName() << "' has cost = " << LC.second << "\n";

571 }

572 return OS;

573}

574

578 std::optional TRT)

580 TTI(TTI), AA(AA), DI(DI) {

581 assert(!Loops.empty() && "Expecting a non-empty loop vector.");

582

583 for (const Loop *L : Loops) {

584 unsigned TripCount = SE.getSmallConstantTripCount(L);

586 TripCounts.push_back({L, TripCount});

587 }

588

589 calculateCacheFootprint();

590}

591

592std::unique_ptr

596 LLVM_DEBUG(dbgs() << "Expecting the outermost loop in a loop nest\n");

597 return nullptr;

598 }

599

602

604 LLVM_DEBUG(dbgs() << "Cannot compute cache cost of loop nest with more "

605 "than one innermost loop\n");

606 return nullptr;

607 }

608

609 return std::make_unique(Loops, AR.LI, AR.SE, AR.TTI, AR.AA, DI, TRT);

610}

611

612void CacheCost::calculateCacheFootprint() {

613 LLVM_DEBUG(dbgs() << "POPULATING REFERENCE GROUPS\n");

615 if (!populateReferenceGroups(RefGroups))

616 return;

617

618 LLVM_DEBUG(dbgs() << "COMPUTING LOOP CACHE COSTS\n");

621 LoopCosts,

622 [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) &&

623 "Should not add duplicate element");

624 CacheCostTy LoopCost = computeLoopCacheCost(*L, RefGroups);

625 LoopCosts.push_back(std::make_pair(L, LoopCost));

626 }

627

628 sortLoopCosts();

629 RefGroups.clear();

630}

631

632bool CacheCost::populateReferenceGroups(ReferenceGroupsTy &RefGroups) const {

633 assert(RefGroups.empty() && "Reference groups should be empty");

634

635 unsigned CLS = TTI.getCacheLineSize();

637 assert(InnerMostLoop != nullptr && "Expecting a valid innermost loop");

638

639 for (BasicBlock *BB : InnerMostLoop->getBlocks()) {

640 for (Instruction &I : *BB) {

642 continue;

643

644 std::unique_ptr R(new IndexedReference(I, LI, SE));

645 if (->isValid())

646 continue;

647

648 bool Added = false;

650 const IndexedReference &Representative = *RefGroup.front();

652 dbgs() << "References:\n";

654 dbgs().indent(2) << Representative << "\n";

655 });

656

657

658

659

660

661

662

663

664

665

666

667

668

669 std::optional HasTemporalReuse =

670 R->hasTemporalReuse(Representative, *TRT, *InnerMostLoop, DI, AA);

671 std::optional HasSpacialReuse =

672 R->hasSpacialReuse(Representative, CLS, AA);

673

674 if ((HasTemporalReuse && *HasTemporalReuse) ||

675 (HasSpacialReuse && *HasSpacialReuse)) {

676 RefGroup.push_back(std::move(R));

678 break;

679 }

680 }

681

682 if (!Added) {

685 RefGroups.push_back(std::move(RG));

686 }

687 }

688 }

689

690 if (RefGroups.empty())

691 return false;

692

694 dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n";

695 int n = 1;

697 dbgs().indent(2) << "RefGroup " << n << ":\n";

698 for (const auto &IR : RG)

700 n++;

701 }

702 dbgs() << "\n";

703 });

704

705 return true;

706}

707

709CacheCost::computeLoopCacheCost(const Loop &L,

711 if (.isLoopSimplifyForm())

713

715 << "' as innermost loop.\n");

716

717

719 for (const auto &TC : TripCounts) {

720 if (TC.first == &L)

721 continue;

722 TripCountsProduct *= TC.second;

723 }

724

727 CacheCostTy RefGroupCost = computeRefGroupCacheCost(RG, L);

728 LoopCost += RefGroupCost * TripCountsProduct;

729 }

730

732 << "' has cost=" << LoopCost << "\n");

733

734 return LoopCost;

735}

736

738 const Loop &L) const {

739 assert(!RG.empty() && "Reference group should have at least one member.");

740

741 const IndexedReference *Representative = RG.front().get();

742 return Representative->computeRefCost(L, TTI.getCacheLineSize());

743}

744

745

746

747

751 Function *F = L.getHeader()->getParent();

753

755 OS << *CC;

756

758}

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

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

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

Legalize the Machine IR a function s Machine IR

static bool isOneDimensionalArray(const SCEV &AccessFn, const SCEV &ElemSize, const Loop &L, ScalarEvolution &SE)

Definition LoopCacheAnalysis.cpp:81

static cl::opt< unsigned > TemporalReuseThreshold("temporal-reuse-threshold", cl::init(2), cl::Hidden, cl::desc("Use this to specify the max. distance between array elements " "accessed in a loop so that the elements are classified to have " "temporal reuse"))

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

Compute the trip count for the given loop L or assume a default value if it is not a compile time con...

Definition LoopCacheAnalysis.cpp:109

static Loop * getInnerMostLoop(const LoopVectorTy &Loops)

Retrieve the innermost loop in the given loop nest Loops.

Definition LoopCacheAnalysis.cpp:62

static cl::opt< unsigned > DefaultTripCount("default-trip-count", cl::init(100), cl::Hidden, cl::desc("Use this to specify the default trip count of a loop"))

This file defines the interface for the loop cache analysis.

Provides some synthesis utilities to produce sequences of values.

This file defines the SmallVector class.

static cl::opt< unsigned > CacheLineSize("cache-line-size", cl::init(0), cl::Hidden, cl::desc("Use this to override the target cache line size when " "specified by the user."))

This pass exposes codegen information to IR-level passes.

bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)

A trivial helper function to check to see if the specified pointers are must-alias.

CacheCost represents the estimated cost of a inner loop as the number of cache lines used by the memo...

CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI, ScalarEvolution &SE, TargetTransformInfo &TTI, AAResults &AA, DependenceInfo &DI, std::optional< unsigned > TRT=std::nullopt)

Construct a CacheCost object for the loop nest described by Loops.

Definition LoopCacheAnalysis.cpp:575

static std::unique_ptr< CacheCost > getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR, DependenceInfo &DI, std::optional< unsigned > TRT=std::nullopt)

Create a CacheCost for the loop nest rooted by Root.

Definition LoopCacheAnalysis.cpp:593

@ ICMP_ULT

unsigned less than

This is the shared class of boolean and integer constants.

bool isZero() const

This is just a convenience method to make client code smaller for a common code.

int64_t getSExtValue() const

Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...

DependenceInfo - This class is the main dependence-analysis driver.

LLVM_ABI std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool UnderRuntimeAssumptions=false)

depends - Tests for a dependence between the Src and Dst instructions.

Represents a memory reference as a base pointer and a set of indexing operations.

CacheCostTy computeRefCost(const Loop &L, unsigned CLS) const

Compute the cost of the reference w.r.t.

Definition LoopCacheAnalysis.cpp:272

const SCEV * getSubscript(unsigned SubNum) const

std::optional< bool > hasSpacialReuse(const IndexedReference &Other, unsigned CLS, AAResults &AA) const

Return true/false if the current object and the indexed reference Other are/aren't in the same cache ...

Definition LoopCacheAnalysis.cpp:160

std::optional< bool > hasTemporalReuse(const IndexedReference &Other, unsigned MaxDistance, const Loop &L, DependenceInfo &DI, AAResults &AA) const

Return true if the current object and the indexed reference Other have distance smaller than MaxDista...

Definition LoopCacheAnalysis.cpp:215

IndexedReference(Instruction &StoreOrLoadInst, const LoopInfo &LI, ScalarEvolution &SE)

Construct an indexed reference given a StoreOrLoadInst instruction.

Definition LoopCacheAnalysis.cpp:147

const SCEV * getLastSubscript() const

size_t getNumSubscripts() const

static InstructionCost getInvalid(CostType Val=0)

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

bool isOutermost() const

Return true if the loop does not have a parent (natural) loop.

unsigned getLoopDepth() const

Return the nesting level of this loop.

ArrayRef< BlockT * > getBlocks() const

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

LoopT * getParentLoop() const

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

PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)

Definition LoopCacheAnalysis.cpp:748

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Represents a single loop in the control flow graph.

static LLVM_ABI MemoryLocation get(const LoadInst *LI)

Return a location with information about the memory reference by the given instruction.

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 node represents a polynomial recurrence on the trip count of the specified loop.

const SCEV * getStart() const

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

Constructs and returns the recurrence indicating how much this expression steps by.

bool isAffine() const

Return true if this represents an expression A + B*x where A and B are loop invariant values.

const Loop * getLoop() const

This class represents a constant integer value.

ConstantInt * getValue() const

This class represents an analyzed expression in the program.

LLVM_ABI Type * getType() const

Return the LLVM type of this SCEV expression.

The main scalar evolution driver.

LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)

Return the SCEV object corresponding to -V.

LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const

LLVM_ABI bool isKnownNegative(const SCEV *S)

Test if the given expression is known to be negative.

LLVM_ABI const SCEV * removePointerBase(const SCEV *S)

Compute an expression equivalent to S - getPointerBase(S).

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 * getConstant(ConstantInt *V)

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 bool isLoopInvariant(const SCEV *S, const Loop *L)

Return true if the value of the given SCEV is unchanging in the specified loop.

LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)

Return a SCEV corresponding to a conversion of the input value to the specified type.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void push_back(const T &Elt)

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

The instances of the Type class are immutable: once they are created, they are never changed.

LLVM_ABI Type * getExtendedType() const

Given scalar/vector integer type, returns a type with elements twice as wide as in the original type.

Type * getType() const

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

This class implements an extremely fast bulk output stream that can only output to a stream.

raw_ostream & indent(unsigned NumSpaces)

indent - Insert 'NumSpaces' spaces.

Abstract Attribute helper functions.

@ BasicBlock

Various leaf nodes.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

bool all_of(R &&range, UnaryPredicate P)

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

InstructionCost CacheCostTy

decltype(auto) dyn_cast(const From &Val)

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

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

SmallVector< std::unique_ptr< IndexedReference >, 8 > ReferenceGroupTy

A reference group represents a set of memory references that exhibit temporal or spacial reuse.

const Value * getPointerOperand(const Value *V)

A helper function that returns the pointer operand of a load, store or GEP instruction.

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

auto dyn_cast_or_null(const Y &Val)

bool delinearizeFixedSizeArray(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)

Split this SCEVAddRecExpr into two vectors of SCEVs representing the subscripts and sizes of an acces...

SmallVector< Loop *, 8 > LoopVectorTy

LLVM_ABI raw_ostream & dbgs()

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

bool none_of(R &&Range, UnaryPredicate P)

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

bool is_sorted(R &&Range, Compare C)

Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...

bool isa(const From &Val)

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

iterator_range< bf_iterator< T > > breadth_first(const T &G)

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

void delinearize(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)

Split this SCEVAddRecExpr into two vectors of SCEVs representing the subscripts and sizes of an array...

decltype(auto) cast(const From &Val)

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

auto seq(T Begin, T End)

Iterate over an integral type from Begin up to - but not including - End.

SmallVector< ReferenceGroupTy, 8 > ReferenceGroupsTy

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

TargetTransformInfo & TTI