Movatterモバイル変換

Go to the documentation of this file.

1//===- LoopCacheAnalysis.cpp - Loop Cache Analysis -------------------------==//

2//

3// The LLVM Compiler Infrastructure

4//

5// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

6// See https://llvm.org/LICENSE.txt for license information.

7// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

8//

9//===----------------------------------------------------------------------===//

10///

11/// \file

12/// This file defines the implementation for the loop cache analysis.

13/// The implementation is largely based on the following paper:

14///

15/// Compiler Optimizations for Improving Data Locality

16/// By: Steve Carr, Katherine S. McKinley, Chau-Wen Tseng

17/// http://www.cs.utexas.edu/users/mckinley/papers/asplos-1994.pdf

18///

19/// The general approach taken to estimate the number of cache lines used by the

20/// memory references in an inner loop is:

21/// 1. Partition memory references that exhibit temporal or spacial reuse

22/// into reference groups.

23/// 2. For each loop L in the a loop nest LN:

24/// a. Compute the cost of the reference group

25/// b. Compute the loop cost by summing up the reference groups costs

26//===----------------------------------------------------------------------===//

28#include "llvm/Analysis/LoopCacheAnalysis.h"

29#include "llvm/ADT/BreadthFirstIterator.h"

30#include "llvm/ADT/Sequence.h"

31#include "llvm/ADT/SmallVector.h"

32#include "llvm/Analysis/AliasAnalysis.h"

33#include "llvm/Analysis/Delinearization.h"

34#include "llvm/Analysis/DependenceAnalysis.h"

35#include "llvm/Analysis/LoopInfo.h"

36#include "llvm/Analysis/ScalarEvolutionExpressions.h"

37#include "llvm/Analysis/TargetTransformInfo.h"

38#include "llvm/Support/CommandLine.h"

39#include "llvm/Support/Debug.h"

41using namespacellvm;

43#define DEBUG_TYPE "loop-cache-cost"

45staticcl::opt<unsigned>DefaultTripCount(

46"default-trip-count",cl::init(100),cl::Hidden,

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

49// In this analysis two array references are considered to exhibit temporal

50// reuse if they access either the same memory location, or a memory location

51// with distance smaller than a configurable threshold.

52staticcl::opt<unsigned>TemporalReuseThreshold(

53"temporal-reuse-threshold",cl::init(2),cl::Hidden,

54cl::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"));

58/// Retrieve the innermost loop in the given loop nest \p Loops. It returns a

59/// nullptr if any loops in the loop vector supplied has more than one sibling.

60/// The loop vector is expected to contain loops collected in breadth-first

61/// order.

62staticLoop *getInnerMostLoop(constLoopVectorTy &Loops) {

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

65Loop *LastLoop =Loops.back();

66Loop *ParentLoop = LastLoop->getParentLoop();

68if (ParentLoop ==nullptr) {

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

70return LastLoop;

71 }

73return (llvm::is_sorted(Loops,

74 [](constLoop *L1,constLoop *L2) {

75return L1->getLoopDepth() < L2->getLoopDepth();

76 }))

77 ? LastLoop

78 :nullptr;

79}

81staticboolisOneDimensionalArray(constSCEV &AccessFn,constSCEV &ElemSize,

82constLoop &L,ScalarEvolution &SE) {

83constSCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(&AccessFn);

84if (!AR || !AR->isAffine())

85returnfalse;

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

89// Check that start and increment are not add recurrences.

90constSCEV *Start = AR->getStart();

91constSCEV *Step = AR->getStepRecurrence(SE);

92if (isa<SCEVAddRecExpr>(Start) || isa<SCEVAddRecExpr>(Step))

93returnfalse;

95// Check that start and increment are both invariant in the loop.

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

97returnfalse;

99constSCEV *StepRec = AR->getStepRecurrence(SE);

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

101 StepRec = SE.getNegativeSCEV(StepRec);

102

103return StepRec == &ElemSize;

104}

105

106/// Compute the trip count for the given loop \p L or assume a default value if

107/// it is not a compile time constant. Return the SCEV expression for the trip

108/// count.

109staticconstSCEV *computeTripCount(constLoop &L,constSCEV &ElemSize,

110ScalarEvolution &SE) {

111constSCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(&L);

112constSCEV *TripCount = (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) &&

113 isa<SCEVConstant>(BackedgeTakenCount))

114 ? SE.getTripCountFromExitCount(BackedgeTakenCount)

115 :nullptr;

116

117if (!TripCount) {

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

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

120 TripCount = SE.getConstant(ElemSize.getType(),DefaultTripCount);

121 }

122

123return TripCount;

124}

125

126//===----------------------------------------------------------------------===//

127// IndexedReference implementation

128//

129raw_ostream &llvm::operator<<(raw_ostream &OS,constIndexedReference &R) {

130if (!R.IsValid) {

131OS << R.StoreOrLoadInst;

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

133returnOS;

134 }

135

136OS << *R.BasePointer;

137for (constSCEV *Subscript : R.Subscripts)

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

139

140OS <<", Sizes: ";

141for (constSCEV *Size : R.Sizes)

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

143

144returnOS;

145}

146

147IndexedReference::IndexedReference(Instruction &StoreOrLoadInst,

148constLoopInfo &LI,ScalarEvolution &SE)

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

150assert((isa<StoreInst>(StoreOrLoadInst) || isa<LoadInst>(StoreOrLoadInst)) &&

151"Expecting a load or store instruction");

152

153 IsValid = delinearize(LI);

154if (IsValid)

155LLVM_DEBUG(dbgs().indent(2) <<"Succesfully delinearized: " << *this

156 <<"\n");

157}

158

159std::optional<bool>

160IndexedReference::hasSpacialReuse(constIndexedReference &Other,unsigned CLS,

161AAResults &AA) const{

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

163

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

165LLVM_DEBUG(dbgs().indent(2)

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

167returnfalse;

168 }

169

170unsigned NumSubscripts =getNumSubscripts();

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

172LLVM_DEBUG(dbgs().indent(2)

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

174returnfalse;

175 }

176

177// all subscripts must be equal, except the leftmost one (the last one).

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

179if (getSubscript(SubNum) !=Other.getSubscript(SubNum)) {

180LLVM_DEBUG(dbgs().indent(2) <<"No spacial reuse, different subscripts: "

181 <<"\n\t" << *getSubscript(SubNum) <<"\n\t"

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

183returnfalse;

184 }

185 }

186

187// the difference between the last subscripts must be less than the cache line

188// size.

189constSCEV *LastSubscript =getLastSubscript();

190constSCEV *OtherLastSubscript =Other.getLastSubscript();

191constSCEVConstant *Diff = dyn_cast<SCEVConstant>(

192 SE.getMinusSCEV(LastSubscript, OtherLastSubscript));

193

194if (Diff ==nullptr) {

195LLVM_DEBUG(dbgs().indent(2)

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

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

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

199return std::nullopt;

200 }

201

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

203

204LLVM_DEBUG({

205if (InSameCacheLine)

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

207else

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

209 });

210

211return InSameCacheLine;

212}

213

214std::optional<bool>

215IndexedReference::hasTemporalReuse(constIndexedReference &Other,

216unsigned MaxDistance,constLoop &L,

217DependenceInfo &DI,AAResults &AA) const{

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

219

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

221LLVM_DEBUG(dbgs().indent(2)

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

223returnfalse;

224 }

225

226 std::unique_ptr<Dependence>D =

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

228

229if (D ==nullptr) {

230LLVM_DEBUG(dbgs().indent(2) <<"No temporal reuse: no dependence\n");

231returnfalse;

232 }

233

234if (D->isLoopIndependent()) {

235LLVM_DEBUG(dbgs().indent(2) <<"Found temporal reuse\n");

236returntrue;

237 }

238

239// Check the dependence distance at every loop level. There is temporal reuse

240// if the distance at the given loop's depth is small (|d| <= MaxDistance) and

241// it is zero at every other loop level.

242int LoopDepth = L.getLoopDepth();

243int Levels =D->getLevels();

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

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

246constSCEVConstant *SCEVConst = dyn_cast_or_null<SCEVConstant>(Distance);

247

248if (SCEVConst ==nullptr) {

249LLVM_DEBUG(dbgs().indent(2) <<"No temporal reuse: distance unknown\n");

250return std::nullopt;

251 }

252

253constConstantInt &CI = *SCEVConst->getValue();

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

255LLVM_DEBUG(dbgs().indent(2)

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

257 <<"\n");

258returnfalse;

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

260LLVM_DEBUG(

261dbgs().indent(2)

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

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

264returnfalse;

265 }

266 }

267

268LLVM_DEBUG(dbgs().indent(2) <<"Found temporal reuse\n");

269returntrue;

270}

271

272CacheCostTy IndexedReference::computeRefCost(constLoop &L,

273unsigned CLS) const{

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

275LLVM_DEBUG({

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

277dbgs().indent(4) << *this <<"\n";

278 });

279

280// If the indexed reference is loop invariant the cost is one.

281if (isLoopInvariant(L)) {

282LLVM_DEBUG(dbgs().indent(4) <<"Reference is loop invariant: RefCost=1\n");

283return 1;

284 }

285

286constSCEV *TripCount =computeTripCount(L, *Sizes.back(), SE);

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

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

289

290constSCEV *RefCost =nullptr;

291constSCEV *Stride =nullptr;

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

293// If the indexed reference is 'consecutive' the cost is

294// (TripCount*Stride)/CLS.

295assert(Stride !=nullptr &&

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

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

298constSCEV *CacheLineSize = SE.getConstant(WiderType, CLS);

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

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

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

302// Round the fractional cost up to the nearest integer number.

303// The impact is the most significant when cost is calculated

304// to be a number less than one, because it makes more sense

305// to say one cache line is used rather than zero cache line

306// is used.

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

308

309LLVM_DEBUG(dbgs().indent(4)

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

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

312 }else {

313// If the indexed reference is not 'consecutive' the cost is proportional to

314// the trip count and the depth of the dimension which the subject loop

315// subscript is accessing. We try to estimate this by multiplying the cost

316// by the trip counts of loops corresponding to the inner dimensions. For

317// example, given the indexed reference 'A[i][j][k]', and assuming the

318// i-loop is in the innermost position, the cost would be equal to the

319// iterations of the i-loop multiplied by iterations of the j-loop.

320 RefCost = TripCount;

321

322int Index = getSubscriptIndex(L);

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

324

325for (unsignedI = Index + 1;I <getNumSubscripts() - 1; ++I) {

326constSCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(getSubscript(I));

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

328constSCEV *TripCount =

329computeTripCount(*AR->getLoop(), *Sizes.back(), SE);

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

331// For the multiplication result to fit, request a type twice as wide.

332 WiderType = WiderType->getExtendedType();

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

334 SE.getNoopOrZeroExtend(TripCount, WiderType));

335 }

336

337LLVM_DEBUG(dbgs().indent(4)

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

339 }

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

341

342// Attempt to fold RefCost into a constant.

343// CacheCostTy is a signed integer, but the tripcount value can be large

344// and may not fit, so saturate/limit the value to the maximum signed

345// integer value.

346if (auto ConstantCost = dyn_cast<SCEVConstant>(RefCost))

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

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

349

350LLVM_DEBUG(dbgs().indent(4)

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

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

353

354returnCacheCostTy::getInvalid();

355}

356

357bool IndexedReference::tryDelinearizeFixedSize(

358constSCEV *AccessFn,SmallVectorImpl<const SCEV *> &Subscripts) {

359SmallVector<int, 4> ArraySizes;

360if (!tryDelinearizeFixedSizeImpl(&SE, &StoreOrLoadInst, AccessFn, Subscripts,

361 ArraySizes))

362returnfalse;

363

364// Populate Sizes with scev expressions to be used in calculations later.

365for (autoIdx : seq<unsigned>(1, Subscripts.size()))

366 Sizes.push_back(

367 SE.getConstant(Subscripts[Idx]->getType(), ArraySizes[Idx - 1]));

368

369LLVM_DEBUG({

370dbgs() <<"Delinearized subscripts of fixed-size array\n"

371 <<"GEP:" << *getLoadStorePointerOperand(&StoreOrLoadInst)

372 <<"\n";

373 });

374returntrue;

375}

376

377bool IndexedReference::delinearize(constLoopInfo &LI) {

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

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

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

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

382

383constSCEV *ElemSize = SE.getElementSize(&StoreOrLoadInst);

384constBasicBlock *BB = StoreOrLoadInst.getParent();

385

386if (Loop *L = LI.getLoopFor(BB)) {

387constSCEV *AccessFn =

388 SE.getSCEVAtScope(getPointerOperand(&StoreOrLoadInst), L);

389

390 BasePointer = dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFn));

391if (BasePointer ==nullptr) {

392LLVM_DEBUG(

393dbgs().indent(2)

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

395returnfalse;

396 }

397

398bool IsFixedSize =false;

399// Try to delinearize fixed-size arrays.

400if (tryDelinearizeFixedSize(AccessFn, Subscripts)) {

401 IsFixedSize =true;

402// The last element of Sizes is the element size.

403 Sizes.push_back(ElemSize);

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

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

406 }

407

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

409

410// Try to delinearize parametric-size arrays.

411if (!IsFixedSize) {

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

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

414llvm::delinearize(SE, AccessFn, Subscripts, Sizes,

415 SE.getElementSize(&StoreOrLoadInst));

416 }

417

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

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

420// Attempt to determine whether we have a single dimensional array access.

421// before giving up.

422if (!isOneDimensionalArray(*AccessFn, *ElemSize, *L, SE)) {

423LLVM_DEBUG(dbgs().indent(2)

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

425 Subscripts.clear();

426 Sizes.clear();

427returnfalse;

428 }

429

430// The array may be accessed in reverse, for example:

431// for (i = N; i > 0; i--)

432// A[i] = 0;

433// In this case, reconstruct the access function using the absolute value

434// of the step recurrence.

435constSCEVAddRecExpr *AccessFnAR = dyn_cast<SCEVAddRecExpr>(AccessFn);

436constSCEV *StepRec = AccessFnAR ? AccessFnAR->getStepRecurrence(SE) :nullptr;

437

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

439 AccessFn = SE.getAddRecExpr(AccessFnAR->getStart(),

440 SE.getNegativeSCEV(StepRec),

441 AccessFnAR->getLoop(),

442 AccessFnAR->getNoWrapFlags());

443constSCEV *Div = SE.getUDivExactExpr(AccessFn, ElemSize);

444 Subscripts.push_back(Div);

445 Sizes.push_back(ElemSize);

446 }

447

448returnall_of(Subscripts, [&](constSCEV *Subscript) {

449return isSimpleAddRecurrence(*Subscript, *L);

450 });

451 }

452

453returnfalse;

454}

455

456bool IndexedReference::isLoopInvariant(constLoop &L) const{

457Value *Addr =getPointerOperand(&StoreOrLoadInst);

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

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

460

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

462returntrue;

463

464// The indexed reference is loop invariant if none of the coefficients use

465// the loop induction variable.

466bool allCoeffForLoopAreZero =all_of(Subscripts, [&](constSCEV *Subscript) {

467return isCoeffForLoopZeroOrInvariant(*Subscript, L);

468 });

469

470return allCoeffForLoopAreZero;

471}

472

473bool IndexedReference::isConsecutive(constLoop &L,constSCEV *&Stride,

474unsigned CLS) const{

475// The indexed reference is 'consecutive' if the only coefficient that uses

476// the loop induction variable is the last one...

477constSCEV *LastSubscript = Subscripts.back();

478for (constSCEV *Subscript : Subscripts) {

479if (Subscript == LastSubscript)

480continue;

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

482returnfalse;

483 }

484

485// ...and the access stride is less than the cache line size.

486constSCEV *Coeff = getLastCoefficient();

487constSCEV *ElemSize = Sizes.back();

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

489// FIXME: This assumes that all values are signed integers which may

490// be incorrect in unusual codes and incorrectly use sext instead of zext.

491// for (uint32_t i = 0; i < 512; ++i) {

492// uint8_t trunc = i;

493// A[trunc] = 42;

494// }

495// This consecutively iterates twice over A. If `trunc` is sign-extended,

496// we would conclude that this may iterate backwards over the array.

497// However, LoopCacheAnalysis is heuristic anyway and transformations must

498// not result in wrong optimizations if the heuristic was incorrect.

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

500 SE.getNoopOrSignExtend(ElemSize, WiderType));

501constSCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS);

502

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

504return SE.isKnownPredicate(ICmpInst::ICMP_ULT, Stride,CacheLineSize);

505}

506

507int IndexedReference::getSubscriptIndex(constLoop &L) const{

508for (autoIdx : seq<int>(0,getNumSubscripts())) {

509constSCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(getSubscript(Idx));

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

511returnIdx;

512 }

513 }

514return -1;

515}

516

517constSCEV *IndexedReference::getLastCoefficient() const{

518constSCEV *LastSubscript =getLastSubscript();

519auto *AR = cast<SCEVAddRecExpr>(LastSubscript);

520return AR->getStepRecurrence(SE);

521}

522

523bool IndexedReference::isCoeffForLoopZeroOrInvariant(constSCEV &Subscript,

524constLoop &L) const{

525constSCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(&Subscript);

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

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

528}

529

530bool IndexedReference::isSimpleAddRecurrence(constSCEV &Subscript,

531constLoop &L) const{

532if (!isa<SCEVAddRecExpr>(Subscript))

533returnfalse;

534

535constSCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(&Subscript);

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

537

538if (!AR->isAffine())

539returnfalse;

540

541constSCEV *Start = AR->getStart();

542constSCEV *Step = AR->getStepRecurrence(SE);

543

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

545returnfalse;

546

547returntrue;

548}

549

550bool IndexedReference::isAliased(constIndexedReference &Other,

551AAResults &AA) const{

552constauto &Loc1 =MemoryLocation::get(&StoreOrLoadInst);

553constauto &Loc2 =MemoryLocation::get(&Other.StoreOrLoadInst);

554return AA.isMustAlias(Loc1, Loc2);

555}

556

557//===----------------------------------------------------------------------===//

558// CacheCost implementation

559//

560raw_ostream &llvm::operator<<(raw_ostream &OS,constCacheCost &CC) {

561for (constauto &LC :CC.LoopCosts) {

562constLoop *L = LC.first;

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

564 }

565returnOS;

566}

567

568CacheCost::CacheCost(constLoopVectorTy &Loops,constLoopInfo &LI,

569ScalarEvolution &SE,TargetTransformInfo &TTI,

570AAResults &AA,DependenceInfo &DI,

571 std::optional<unsigned> TRT)

572 :Loops(Loops), TRT(TRT.value_or(TemporalReuseThreshold)), LI(LI), SE(SE),

573TTI(TTI), AA(AA), DI(DI) {

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

575

576for (constLoop *L :Loops) {

577unsigned TripCount = SE.getSmallConstantTripCount(L);

578 TripCount = (TripCount == 0) ?DefaultTripCount : TripCount;

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

580 }

581

582 calculateCacheFootprint();

583}

584

585std::unique_ptr<CacheCost>

586CacheCost::getCacheCost(Loop &Root,LoopStandardAnalysisResults &AR,

587DependenceInfo &DI, std::optional<unsigned> TRT) {

588if (!Root.isOutermost()) {

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

590returnnullptr;

591 }

592

593LoopVectorTy Loops;

594append_range(Loops,breadth_first(&Root));

595

596if (!getInnerMostLoop(Loops)) {

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

598"than one innermost loop\n");

599returnnullptr;

600 }

601

602return std::make_unique<CacheCost>(Loops, AR.LI, AR.SE, AR.TTI, AR.AA, DI, TRT);

603}

604

605void CacheCost::calculateCacheFootprint() {

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

607ReferenceGroupsTy RefGroups;

608if (!populateReferenceGroups(RefGroups))

609return;

610

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

612for (constLoop *L : Loops) {

613assert(llvm::none_of(

614 LoopCosts,

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

616"Should not add duplicate element");

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

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

619 }

620

621 sortLoopCosts();

622 RefGroups.clear();

623}

624

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

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

627

628unsigned CLS =TTI.getCacheLineSize();

629Loop *InnerMostLoop =getInnerMostLoop(Loops);

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

631

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

633for (Instruction &I : *BB) {

634if (!isa<StoreInst>(I) && !isa<LoadInst>(I))

635continue;

636

637 std::unique_ptr<IndexedReference>R(newIndexedReference(I, LI, SE));

638if (!R->isValid())

639continue;

640

641boolAdded =false;

642for (ReferenceGroupTy &RefGroup : RefGroups) {

643constIndexedReference &Representative = *RefGroup.front();

644LLVM_DEBUG({

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

646dbgs().indent(2) << *R <<"\n";

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

648 });

649

650

651// FIXME: Both positive and negative access functions will be placed

652// into the same reference group, resulting in a bi-directional array

653// access such as:

654// for (i = N; i > 0; i--)

655// A[i] = A[N - i];

656// having the same cost calculation as a single dimention access pattern

657// for (i = 0; i < N; i++)

658// A[i] = A[i];

659// when in actuality, depending on the array size, the first example

660// should have a cost closer to 2x the second due to the two cache

661// access per iteration from opposite ends of the array

662 std::optional<bool> HasTemporalReuse =

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

664 std::optional<bool> HasSpacialReuse =

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

666

667if ((HasTemporalReuse && *HasTemporalReuse) ||

668 (HasSpacialReuse && *HasSpacialReuse)) {

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

670Added =true;

671break;

672 }

673 }

674

675if (!Added) {

676ReferenceGroupTy RG;

677 RG.push_back(std::move(R));

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

679 }

680 }

681 }

682

683if (RefGroups.empty())

684returnfalse;

685

686LLVM_DEBUG({

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

688int n = 1;

689for (constReferenceGroupTy &RG : RefGroups) {

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

691for (constauto &IR : RG)

692dbgs().indent(4) << *IR <<"\n";

693 n++;

694 }

695dbgs() <<"\n";

696 });

697

698returntrue;

699}

700

701CacheCostTy

702CacheCost::computeLoopCacheCost(constLoop &L,

703constReferenceGroupsTy &RefGroups) const{

704if (!L.isLoopSimplifyForm())

705returnCacheCostTy::getInvalid();

706

707LLVM_DEBUG(dbgs() <<"Considering loop '" <<L.getName()

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

709

710// Compute the product of the trip counts of each other loop in the nest.

711CacheCostTy TripCountsProduct = 1;

712for (constauto &TC : TripCounts) {

713if (TC.first == &L)

714continue;

715 TripCountsProduct *= TC.second;

716 }

717

718CacheCostTy LoopCost = 0;

719for (constReferenceGroupTy &RG : RefGroups) {

720CacheCostTy RefGroupCost = computeRefGroupCacheCost(RG, L);

721 LoopCost += RefGroupCost * TripCountsProduct;

722 }

723

724LLVM_DEBUG(dbgs().indent(2) <<"Loop '" <<L.getName()

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

726

727return LoopCost;

728}

729

730CacheCostTy CacheCost::computeRefGroupCacheCost(constReferenceGroupTy &RG,

731constLoop &L) const{

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

733

734constIndexedReference *Representative = RG.front().get();

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

736}

737

738//===----------------------------------------------------------------------===//

739// LoopCachePrinterPass implementation

740//

741PreservedAnalyses LoopCachePrinterPass::run(Loop &L,LoopAnalysisManager &AM,

742LoopStandardAnalysisResults &AR,

743LPMUpdater &U) {

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

745DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);

746

747if (autoCC =CacheCost::getCacheCost(L, AR, DI))

748 OS << *CC;

749

750returnPreservedAnalyses::all();

751}

AliasAnalysis.h

BreadthFirstIterator.h

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

CommandLine.h

Idx

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

Definition:DeadArgumentElimination.cpp:353

Debug.h

LLVM_DEBUG

#define LLVM_DEBUG(...)

Definition:Debug.h:106

Delinearization.h

DependenceAnalysis.h

Addr

uint64_t Addr

Definition:ELFObjHandler.cpp:79

Size

uint64_t Size

Definition:ELFObjHandler.cpp:81

Loops

Hexagon Hardware Loops

Definition:HexagonHardwareLoops.cpp:373

Legalize the Machine IR a function s Machine IR

Definition:Legalizer.cpp:80

isOneDimensionalArray

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

Definition:LoopCacheAnalysis.cpp:81

TemporalReuseThreshold

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

computeTripCount

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

getInnerMostLoop

static Loop * getInnerMostLoop(const LoopVectorTy &Loops)

Retrieve the innermost loop in the given loop nest Loops.

Definition:LoopCacheAnalysis.cpp:62

DefaultTripCount

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

LoopCacheAnalysis.h

This file defines the interface for the loop cache analysis.

LoopInfo.h

#define F(x, y, z)

Definition:MD5.cpp:55

#define I(x, y, z)

Definition:MD5.cpp:58

auto CC

Definition:RISCVRedundantCopyElimination.cpp:79

assert

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

raw_pwrite_stream & OS

Definition:SampleProfWriter.cpp:51

ScalarEvolutionExpressions.h

Sequence.h

Provides some synthesis utilities to produce sequences of values.

SmallVector.h

This file defines the SmallVector class.

CacheLineSize

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

TargetTransformInfo.h

This pass exposes codegen information to IR-level passes.

llvm::AAResults

Definition:AliasAnalysis.h:314

llvm::AAResults::isMustAlias

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

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

Definition:AliasAnalysis.h:386

llvm::AnalysisManager

A container for analyses that lazily runs them and caches their results.

Definition:PassManager.h:253

llvm::BasicBlock

LLVM Basic Block Representation.

Definition:BasicBlock.h:61

llvm::CacheCost

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

Definition:LoopCacheAnalysis.h:190

llvm::CacheCost::CacheCost

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

llvm::CacheCost::getCacheCost

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

llvm::CmpInst::ICMP_ULT

@ ICMP_ULT

unsigned less than

Definition:InstrTypes.h:698

llvm::ConstantInt

This is the shared class of boolean and integer constants.

Definition:Constants.h:83

llvm::ConstantInt::isZero

bool isZero() const

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

Definition:Constants.h:208

llvm::ConstantInt::getSExtValue

int64_t getSExtValue() const

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

Definition:Constants.h:163

llvm::DependenceInfo

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

Definition:DependenceAnalysis.h:293

llvm::DependenceInfo::depends

std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)

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

Definition:DependenceAnalysis.cpp:3589

llvm::Function

Definition:Function.h:63

llvm::IndexedReference

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

Definition:LoopCacheAnalysis.h:49

llvm::IndexedReference::computeRefCost

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

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

Definition:LoopCacheAnalysis.cpp:272

llvm::IndexedReference::getSubscript

const SCEV * getSubscript(unsigned SubNum) const

Definition:LoopCacheAnalysis.h:60

llvm::IndexedReference::hasSpacialReuse

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

llvm::IndexedReference::hasTemporalReuse

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

llvm::IndexedReference::IndexedReference

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

Construct an indexed reference given a StoreOrLoadInst instruction.

Definition:LoopCacheAnalysis.cpp:147

llvm::IndexedReference::getLastSubscript

const SCEV * getLastSubscript() const

Definition:LoopCacheAnalysis.h:68

llvm::IndexedReference::getNumSubscripts

size_t getNumSubscripts() const

Definition:LoopCacheAnalysis.h:59

llvm::InstructionCost

Definition:InstructionCost.h:29

llvm::InstructionCost::getInvalid

static InstructionCost getInvalid(CostType Val=0)

Definition:InstructionCost.h:73

llvm::Instruction

Definition:Instruction.h:68

llvm::LPMUpdater

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

Definition:LoopPassManager.h:229

llvm::LoopBase::isOutermost

bool isOutermost() const

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

Definition:GenericLoopInfo.h:170

llvm::LoopBase::getLoopDepth

unsigned getLoopDepth() const

Return the nesting level of this loop.

Definition:GenericLoopInfo.h:82

llvm::LoopBase::getBlocks

ArrayRef< BlockT * > getBlocks() const

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

Definition:GenericLoopInfo.h:173

llvm::LoopBase::getParentLoop

LoopT * getParentLoop() const

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

Definition:GenericLoopInfo.h:99

llvm::LoopCachePrinterPass::run

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

Definition:LoopCacheAnalysis.cpp:741

llvm::LoopInfoBase::getLoopFor

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Definition:GenericLoopInfo.h:606

llvm::LoopInfo

Definition:LoopInfo.h:407

llvm::Loop

Represents a single loop in the control flow graph.

Definition:LoopInfo.h:39

llvm::MemoryLocation::get

static MemoryLocation get(const LoadInst *LI)

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

Definition:MemoryLocation.cpp:35

llvm::PreservedAnalyses

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

Definition:Analysis.h:111

llvm::PreservedAnalyses::all

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Definition:Analysis.h:117

llvm::SCEVAddRecExpr

This node represents a polynomial recurrence on the trip count of the specified loop.

Definition:ScalarEvolutionExpressions.h:347

llvm::SCEVAddRecExpr::getStart

const SCEV * getStart() const

Definition:ScalarEvolutionExpressions.h:358

llvm::SCEVAddRecExpr::getStepRecurrence

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

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

Definition:ScalarEvolutionExpressions.h:365

llvm::SCEVAddRecExpr::isAffine

bool isAffine() const

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

Definition:ScalarEvolutionExpressions.h:375

llvm::SCEVAddRecExpr::getLoop

const Loop * getLoop() const

Definition:ScalarEvolutionExpressions.h:359

llvm::SCEVConstant

This class represents a constant integer value.

Definition:ScalarEvolutionExpressions.h:60

llvm::SCEVConstant::getValue

ConstantInt * getValue() const

Definition:ScalarEvolutionExpressions.h:69

llvm::SCEVNAryExpr::getNoWrapFlags

NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const

Definition:ScalarEvolutionExpressions.h:222

llvm::SCEV

This class represents an analyzed expression in the program.

Definition:ScalarEvolution.h:71

llvm::SCEV::getType

Type * getType() const

Return the LLVM type of this SCEV expression.

Definition:ScalarEvolution.cpp:386

llvm::ScalarEvolution

The main scalar evolution driver.

Definition:ScalarEvolution.h:447

llvm::ScalarEvolution::getNegativeSCEV

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

Return the SCEV object corresponding to -V.

Definition:ScalarEvolution.cpp:4569

llvm::ScalarEvolution::getUDivCeilSCEV

const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)

Compute ceil(N / D).

Definition:ScalarEvolution.cpp:12882

llvm::ScalarEvolution::getWiderType

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

Definition:ScalarEvolution.cpp:4469

llvm::ScalarEvolution::isKnownNegative

bool isKnownNegative(const SCEV *S)

Test if the given expression is known to be negative.

Definition:ScalarEvolution.cpp:10944

llvm::ScalarEvolution::getSCEVAtScope

const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)

Return a SCEV expression for the specified value at the specified scope in the program.

Definition:ScalarEvolution.cpp:9856

llvm::ScalarEvolution::getBackedgeTakenCount

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

Definition:ScalarEvolution.cpp:8350

llvm::ScalarEvolution::getConstant

const SCEV * getConstant(ConstantInt *V)

Definition:ScalarEvolution.cpp:473

llvm::ScalarEvolution::getSCEV

const SCEV * getSCEV(Value *V)

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

Definition:ScalarEvolution.cpp:4547

llvm::ScalarEvolution::getNoopOrSignExtend

const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)

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

Definition:ScalarEvolution.cpp:4742

llvm::ScalarEvolution::getTripCountFromExitCount

const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)

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

Definition:ScalarEvolution.cpp:8182

llvm::ScalarEvolution::isLoopInvariant

bool isLoopInvariant(const SCEV *S, const Loop *L)

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

Definition:ScalarEvolution.cpp:14100

llvm::ScalarEvolution::getAddRecExpr

const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)

Get an add recurrence expression for the specified loop.

Definition:ScalarEvolution.cpp:3641

llvm::ScalarEvolution::isSCEVable

bool isSCEVable(Type *Ty) const

Test if values of the given type are analyzable within the SCEV framework.

Definition:ScalarEvolution.cpp:4441

llvm::ScalarEvolution::getNoopOrAnyExtend

const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)

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

Definition:ScalarEvolution.cpp:4754

llvm::ScalarEvolution::getMinusSCEV

const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Return LHS-RHS.

Definition:ScalarEvolution.cpp:4655

llvm::ScalarEvolution::getNoopOrZeroExtend

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

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

Definition:ScalarEvolution.cpp:4730

llvm::ScalarEvolution::getSmallConstantTripCount

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.

Definition:ScalarEvolution.cpp:8237

llvm::ScalarEvolution::getPointerBase

const SCEV * getPointerBase(const SCEV *V)

Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...

Definition:ScalarEvolution.cpp:4823

llvm::ScalarEvolution::getMulExpr

const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Get a canonical multiply expression, or something simpler if possible.

Definition:ScalarEvolution.cpp:3106

llvm::ScalarEvolution::getElementSize

const SCEV * getElementSize(Instruction *Inst)

Return the size of an element read or written by Inst.

Definition:ScalarEvolution.cpp:13595

llvm::ScalarEvolution::getUDivExactExpr

const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)

Get a canonical unsigned division expression, or something simpler if possible.

Definition:ScalarEvolution.cpp:3587

llvm::ScalarEvolution::isKnownPredicate

bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)

Test if the given expression is known to satisfy the condition described by Pred, LHS,...

Definition:ScalarEvolution.cpp:11050

llvm::SmallVectorBase::empty

bool empty() const

Definition:SmallVector.h:81

llvm::SmallVectorBase::size

size_t size() const

Definition:SmallVector.h:78

llvm::SmallVectorImpl

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

Definition:SmallVector.h:573

llvm::SmallVectorImpl::clear

void clear()

Definition:SmallVector.h:610

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition:SmallVector.h:413

llvm::SmallVectorTemplateCommon::front

reference front()

Definition:SmallVector.h:299

llvm::SmallVectorTemplateCommon::back

reference back()

Definition:SmallVector.h:308

llvm::SmallVector< Loop *, 8 >

llvm::TargetTransformInfo

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

Definition:TargetTransformInfo.h:212

llvm::TargetTransformInfo::getCacheLineSize

unsigned getCacheLineSize() const

Definition:TargetTransformInfo.cpp:823

llvm::Type

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

Definition:Type.h:45

llvm::Type::getExtendedType

Type * getExtendedType() const

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

llvm::Value

LLVM Value Representation.

Definition:Value.h:74

llvm::cl::opt

Definition:CommandLine.h:1423

llvm::ilist_detail::node_parent_access::getParent

const ParentTy * getParent() const

Definition:ilist_node.h:32

llvm::raw_ostream

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

Definition:raw_ostream.h:52

llvm::raw_ostream::indent

raw_ostream & indent(unsigned NumSpaces)

indent - Insert 'NumSpaces' spaces.

Definition:raw_ostream.cpp:495

llvm::M68k::MemAddrModeKind::L

@ L

llvm::RISCVFenceField::R

@ R

Definition:RISCVBaseInfo.h:373

llvm::cl::Hidden

@ Hidden

Definition:CommandLine.h:137

llvm::cl::init

initializer< Ty > init(const Ty &Val)

Definition:CommandLine.h:443

llvm::logicalview::LVComparePass::Added

@ Added

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::all_of

bool all_of(R &&range, UnaryPredicate P)

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

Definition:STLExtras.h:1739

llvm::getLoadStorePointerOperand

const Value * getLoadStorePointerOperand(const Value *V)

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

Definition:Instructions.h:4984

llvm::append_range

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

Wrapper function to append range R to container C.

Definition:STLExtras.h:2115

llvm::getPointerOperand

const Value * getPointerOperand(const Value *V)

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

Definition:Instructions.h:4998

llvm::dbgs

raw_ostream & dbgs()

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

Definition:Debug.cpp:163

llvm::none_of

bool none_of(R &&Range, UnaryPredicate P)

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

Definition:STLExtras.h:1753

llvm::is_sorted

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

Definition:STLExtras.h:1926

llvm::breadth_first

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

Definition:BreadthFirstIterator.h:157

llvm::IRMemLocation::Other

@ Other

Any other memory.

llvm::tryDelinearizeFixedSizeImpl

bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst, const SCEV *AccessFn, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)

Implementation of fixed size array delinearization.

Definition:Delinearization.cpp:521

llvm::operator<<

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

Definition:APFixedPoint.h:303

llvm::delinearize

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

Definition:Delinearization.cpp:447

llvm::LoopStandardAnalysisResults

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

Definition:LoopAnalysisManager.h:53

llvm::LoopStandardAnalysisResults::SE

ScalarEvolution & SE

Definition:LoopAnalysisManager.h:58

llvm::LoopStandardAnalysisResults::TTI

TargetTransformInfo & TTI

Definition:LoopAnalysisManager.h:60

llvm::LoopStandardAnalysisResults::LI