LoopAccessAnalysis.h Source File (original) (raw)

14#ifndef LLVM_ANALYSIS_LOOPACCESSANALYSIS_H

15#define LLVM_ANALYSIS_LOOPACCESSANALYSIS_H

20#include

21#include

23namespace llvm {

25class AAResults;

26class DataLayout;

27class Loop;

28class raw_ostream;

29class TargetTransformInfo;

54};

91public:

101

102

104

106

108 };

109

110

112

114

116

118

119

120

121

123

124

125

126

127

128

129

130

131

132

134

135

137

139

140

142

145

146

148

149

151

153

155

158

159

161

163

164

166

167

169

171

172

174

175

176

179 };

180

183 unsigned MaxTargetVectorWidthInBits)

184 : PSE(PSE), InnermostLoop(L), SymbolicStrides(SymbolicStrides),

185 MaxTargetVectorWidthInBits(MaxTargetVectorWidthInBits) {}

186

187

188

190

191

192

194

195

196

197

200

201

202

205 }

206

207

208

210 return MaxSafeVectorWidthInBits == UINT_MAX;

211 }

212

213

214

216 return MaxSafeVectorWidthInBits;

217 }

218

219

220

222 return FoundNonConstantDistanceDependence &&

224 }

225

226

227

228

230 return RecordDependences ? &Dependences : nullptr;

231 }

232

234

235

236

238 return InstMap;

239 }

240

241

242

245

246 for (unsigned I = 0; I < InstMap.size(); ++I)

248

250 }

251

252

254 bool isWrite) const;

255

256

257

259 auto I = Accesses.find({Ptr, IsWrite});

260 if (I != Accesses.end())

261 return I->second;

262 return {};

263 }

264

266

268 std::pair<const SCEV *, const SCEV *>> &

271 }

272

273private:

274

275

276

277

278

279

281 const Loop *InnermostLoop;

282

283

284

286

287

289

290

292

293

294 unsigned AccessIdx = 0;

295

296

297

298

299 uint64_t MinDepDistBytes = 0;

300

301

302

303

304

305 uint64_t MaxSafeVectorWidthInBits = -1U;

306

307

308

309 bool FoundNonConstantDistanceDependence = false;

310

311

312

313

315

316

317

318

319 bool RecordDependences = true;

320

321

322

324

325

326

327

328

329 unsigned MaxTargetVectorWidthInBits = 0;

330

331

332

334 std::pair<const SCEV *, const SCEV *>>

336

337

338 std::optionalScalarEvolution::LoopGuards LoopGuards;

339

340

341

342

343

344

345

346

347

348

349

350

351

354

355

356

357

358

359

360 bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);

361

362

363

364

366

367 struct DepDistanceStrideAndSizeInfo {

368 const SCEV *Dist;

369

370

371

372

373

375 std::optional<uint64_t> CommonStride;

376

377 bool ShouldRetryWithRuntimeCheck;

379 bool AIsWrite;

380 bool BIsWrite;

381

382 DepDistanceStrideAndSizeInfo(const SCEV *Dist, uint64_t MaxStride,

383 std::optional<uint64_t> CommonStride,

384 bool ShouldRetryWithRuntimeCheck,

385 uint64_t TypeByteSize, bool AIsWrite,

386 bool BIsWrite)

387 : Dist(Dist), MaxStride(MaxStride), CommonStride(CommonStride),

388 ShouldRetryWithRuntimeCheck(ShouldRetryWithRuntimeCheck),

389 TypeByteSize(TypeByteSize), AIsWrite(AIsWrite), BIsWrite(BIsWrite) {}

390 };

391

392

393

394

395

396

397

398

399 std::variant<Dependence::DepType, DepDistanceStrideAndSizeInfo>

400 getDependenceDistanceStrideAndSize(const MemAccessInfo &A, Instruction *AInst,

402 Instruction *BInst);

403};

404

405class RuntimePointerChecking;

406

407

409

410

413

414

415

416

417

418

422

423

424

426

427

429

431

433

434

436};

437

438

442

448

453};

454

455

456

459

460public:

462

464

465

467

468

470

472

473

475

477

479

481

488 };

489

491 : DC(DC), SE(SE) {}

492

493

495 Need = false;

496 CanUseDiffCheck = true;

499 DiffChecks.clear();

500 }

501

502

503

504

505

506

508 bool WritePtr, unsigned DepSetId, unsigned ASId,

510

511

513

514

515

517 bool UseDependencies);

518

519

520

522 return Checks;

523 }

524

525

526

527

528

529

530 std::optional<ArrayRef> getDiffChecks() const {

531 if (!CanUseDiffCheck)

532 return std::nullopt;

533 return {DiffChecks};

534 }

535

536

537

540

541

542

544

545

547

548

551 unsigned Depth = 0) const;

552

553

555

556

558

559

561

562

563

564

565

566 static bool

568 unsigned PtrIdx1, unsigned PtrIdx2);

569

570

571

573

574

577 }

578

580

581private:

582

583

584

585

587 bool UseDependencies);

588

589

591

592

593

594

597

599

600

602

603

604

606

607

608 bool CanUseDiffCheck = true;

609

610

611

613};

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

637public:

641

642

643

644

645

646

647

649

650

651

652

654

656 return PtrRtChecking.get();

657 }

658

659

660

662 return PtrRtChecking->getNumberOfChecks();

663 }

664

665

666

669

670

672

675

676

677

679

680

681

683

684

685

687 bool isWrite) const {

688 return DepChecker->getInstructionsForAccess(Ptr, isWrite);

689 }

690

691

692

694 return SymbolicStrides;

695 }

696

697

699

700

701

703 return HasStoreStoreDependenceInvolvingLoopInvariantAddress;

704 }

705

706

707

709 return HasLoadStoreDependenceInvolvingLoopInvariantAddress;

710 }

711

712

714 return StoresToInvariantAddresses;

715 }

716

717

718

719

720

721

723

724private:

725

726

729

730

731

732 bool canAnalyzeLoop();

733

734

735

736

737

738

741

742

743

744

745

746 void collectStridedAccess(Value *LoadOrStoreInst);

747

748

749

750

751 void emitUnsafeDependenceRemark();

752

753 std::unique_ptr PSE;

754

755

756

757 std::unique_ptr PtrRtChecking;

758

759

760

761 std::unique_ptr DepChecker;

762

763 Loop *TheLoop;

764

765 unsigned NumLoads = 0;

766 unsigned NumStores = 0;

767

768

769 bool CanVecMem = false;

770 bool HasConvergentOp = false;

771

772

773

774 bool HasStoreStoreDependenceInvolvingLoopInvariantAddress = false;

775

776

777 bool HasLoadStoreDependenceInvolvingLoopInvariantAddress = false;

778

779

781

782

783

784 std::unique_ptr Report;

785

786

787

789};

790

791

792

793

794

795

796

797

798

799

800const SCEV *

802 const DenseMap<Value *, const SCEV *> &PtrToStride,

803 Value *Ptr);

804

805

806

807

808

809

810

811

812

813

814

815

816

817

818

819

820std::optional<int64_t>

821getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr,

822 const Loop *Lp,

823 const DenseMap<Value *, const SCEV *> &StridesMap = DenseMap<Value *, const SCEV *>(),

824 bool Assume = false, bool ShouldCheckWrap = true);

825

826

827

828

829

830

831std::optional getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB,

832 Value *PtrB, const DataLayout &DL,

833 ScalarEvolution &SE,

834 bool StrictCheck = false,

836

837

838

839

840

841

842

843

844

845

846

847bool sortPtrAccesses(ArrayRef<Value *> VL, Type *ElemTy, const DataLayout &DL,

848 ScalarEvolution &SE,

849 SmallVectorImpl &SortedIndices);

850

851

852

854 ScalarEvolution &SE, bool CheckType = true);

855

857

859

860

867

868public:

872 : SE(SE), AA(AA), DT(DT), LI(LI), TTI(TTI), TLI(TLI) {}

873

875

877

880};

881

882

883

884

885

886

887

888

893

894public:

896

898};

899

903}

904

908}

909

910}

911

912#endif

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

MapVector< const Value *, unsigned > OrderMap

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

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

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

static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckType(MVT::SimpleValueType VT, SDValue N, const TargetLowering *TLI, const DataLayout &DL)

API to communicate dependencies between analyses during invalidation.

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

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

LLVM Basic Block Representation.

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

EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...

An instruction for reading from memory.

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

LoopAccessInfoManager Result

Result run(Function &F, FunctionAnalysisManager &AM)

bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)

const LoopAccessInfo & getInfo(Loop &L)

LoopAccessInfoManager(ScalarEvolution &SE, AAResults &AA, DominatorTree &DT, LoopInfo &LI, TargetTransformInfo *TTI, const TargetLibraryInfo *TLI)

Drive the analysis of memory accesses in the loop.

const MemoryDepChecker & getDepChecker() const

the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...

ArrayRef< StoreInst * > getStoresToInvariantAddresses() const

Return the list of stores to invariant addresses.

const OptimizationRemarkAnalysis * getReport() const

The diagnostics report generated for the analysis.

const RuntimePointerChecking * getRuntimePointerChecking() const

bool canVectorizeMemory() const

Return true we can analyze the memory accesses in the loop and there are no memory dependence cycles.

unsigned getNumLoads() const

unsigned getNumRuntimePointerChecks() const

Number of memchecks required to prove independence of otherwise may-alias pointers.

bool isInvariant(Value *V) const

Returns true if value V is loop invariant.

bool hasLoadStoreDependenceInvolvingLoopInvariantAddress() const

Return true if the loop has memory dependence involving a load and a store to an invariant address,...

void print(raw_ostream &OS, unsigned Depth=0) const

Print the information about the memory accesses in the loop.

const PredicatedScalarEvolution & getPSE() const

Used to add runtime SCEV checks.

unsigned getNumStores() const

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

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

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

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

const DenseMap< Value *, const SCEV * > & getSymbolicStrides() const

If an access has a symbolic strides, this maps the pointer value to the stride symbol.

bool hasStoreStoreDependenceInvolvingLoopInvariantAddress() const

Return true if the loop has memory dependence involving two stores to an invariant address,...

bool hasConvergentOp() const

Return true if there is a convergent operation in the loop.

Represents a single loop in the control flow graph.

Checks memory dependences among accesses to the same underlying object to determine whether there vec...

ArrayRef< unsigned > getOrderForAccess(Value *Ptr, bool IsWrite) const

Return the program order indices for the access location (Ptr, IsWrite).

bool isSafeForAnyVectorWidth() const

Return true if the number of elements that are safe to operate on simultaneously is not bounded.

bool areDepsSafe(const DepCandidates &AccessSets, const MemAccessInfoList &CheckDeps)

Check whether the dependencies between the accesses are safe.

EquivalenceClasses< MemAccessInfo > DepCandidates

Set of potential dependent memory accesses.

MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L, const DenseMap< Value *, const SCEV * > &SymbolicStrides, unsigned MaxTargetVectorWidthInBits)

const SmallVectorImpl< Instruction * > & getMemoryInstructions() const

The vector of memory access instructions.

const Loop * getInnermostLoop() const

uint64_t getMaxSafeVectorWidthInBits() const

Return the number of elements that are safe to operate on simultaneously, multiplied by the size of t...

bool isSafeForVectorization() const

No memory dependence was encountered that would inhibit vectorization.

const SmallVectorImpl< Dependence > * getDependences() const

Returns the memory dependences.

DenseMap< std::pair< const SCEV *, Type * >, std::pair< const SCEV *, const SCEV * > > & getPointerBounds()

SmallVector< MemAccessInfo, 8 > MemAccessInfoList

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

Find the set of instructions that read or write via Ptr.

VectorizationSafetyStatus

Type to keep track of the status of the dependence check.

@ PossiblySafeWithRtChecks

bool shouldRetryWithRuntimeCheck() const

In same cases when the dependency check fails we can still vectorize the loop with a dynamic array ac...

void addAccess(StoreInst *SI)

PointerIntPair< Value *, 1, bool > MemAccessInfo

DenseMap< Instruction *, unsigned > generateInstructionOrderMap() const

Generate a mapping between the memory instructions and their indices according to program order.

PointerIntPair - This class implements a pair of a pointer and small integer.

An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...

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

Holds information about the memory runtime legality checks to verify that a group of pointers do not ...

bool Need

This flag indicates if we need to add the runtime check.

void reset()

Reset the state of the pointer runtime information.

unsigned getNumberOfChecks() const

Returns the number of run-time checks required according to needsChecking.

RuntimePointerChecking(MemoryDepChecker &DC, ScalarEvolution *SE)

void printChecks(raw_ostream &OS, const SmallVectorImpl< RuntimePointerCheck > &Checks, unsigned Depth=0) const

Print Checks.

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

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

void print(raw_ostream &OS, unsigned Depth=0) const

Print the list run-time memory checks necessary.

std::optional< ArrayRef< PointerDiffInfo > > getDiffChecks() const

SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups

Holds a partitioning of pointers into "check groups".

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

Check if pointers are in the same partition.

bool empty() const

No run-time memory checking is necessary.

SmallVector< PointerInfo, 2 > Pointers

Information about the pointers that may require checking.

ScalarEvolution * getSE() const

void insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr, Type *AccessTy, bool WritePtr, unsigned DepSetId, unsigned ASId, PredicatedScalarEvolution &PSE, bool NeedsFreeze)

Insert a pointer and calculate the start and end SCEVs.

const SmallVectorImpl< RuntimePointerCheck > & getChecks() const

Returns the checks that generateChecks created.

const PointerInfo & getPointerInfo(unsigned PtrIdx) const

Return PointerInfo for pointer at index PtrIdx.

This class represents an analyzed expression in the program.

The main scalar evolution driver.

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

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

An instruction for storing to memory.

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

Provides information about what library functions are available for the current target.

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

Value handle that tracks a Value across RAUW.

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

LLVM Value Representation.

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

This is an optimization pass for GlobalISel generic memory operations.

std::optional< int > getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB, Value *PtrB, const DataLayout &DL, ScalarEvolution &SE, bool StrictCheck=false, bool CheckType=true)

Returns the distance between the pointers PtrA and PtrB iff they are compatible and it is possible to...

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

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

std::optional< int64_t > getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, const DenseMap< Value *, const SCEV * > &StridesMap=DenseMap< Value *, const SCEV * >(), bool Assume=false, bool ShouldCheckWrap=true)

If the pointer has a constant stride return it in units of the access type size.

bool sortPtrAccesses(ArrayRef< Value * > VL, Type *ElemTy, const DataLayout &DL, ScalarEvolution &SE, SmallVectorImpl< unsigned > &SortedIndices)

Attempt to sort the pointers in VL and return the sorted indices in SortedIndices,...

const SCEV * replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE, const DenseMap< Value *, const SCEV * > &PtrToStride, Value *Ptr)

Return the SCEV corresponding to a pointer with the symbolic stride replaced with constant one,...

bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL, ScalarEvolution &SE, bool CheckType=true)

Returns true if the memory operations A and B are consecutive.

IR Values for the lower and upper bounds of a pointer evolution.

A CRTP mix-in that provides informational APIs needed for analysis passes.

A special type used by analysis passes to provide an address that identifies that particular analysis...

Dependece between memory access instructions.

Instruction * getDestination(const MemoryDepChecker &DepChecker) const

Return the destination instruction of the dependence.

DepType Type

The type of the dependence.

unsigned Destination

Index of the destination of the dependence in the InstMap vector.

Dependence(unsigned Source, unsigned Destination, DepType Type)

bool isPossiblyBackward() const

May be a lexically backward dependence type (includes Unknown).

Instruction * getSource(const MemoryDepChecker &DepChecker) const

Return the source instruction of the dependence.

bool isForward() const

Lexically forward dependence.

bool isBackward() const

Lexically backward dependence.

void print(raw_ostream &OS, unsigned Depth, const SmallVectorImpl< Instruction * > &Instrs) const

Print the dependence.

unsigned Source

Index of the source of the dependence in the InstMap vector.

DepType

The type of the dependence.

@ BackwardVectorizableButPreventsForwarding

@ ForwardButPreventsForwarding

static const char * DepName[]

String version of the types.

PointerDiffInfo(const SCEV *SrcStart, const SCEV *SinkStart, unsigned AccessSize, bool NeedsFreeze)

unsigned AddressSpace

Address space of the involved pointers.

bool addPointer(unsigned Index, const RuntimePointerChecking &RtCheck)

Tries to add the pointer recorded in RtCheck at index Index to this pointer checking group.

bool NeedsFreeze

Whether the pointer needs to be frozen after expansion, e.g.

const SCEV * High

The SCEV expression which represents the upper bound of all the pointers in this group.

SmallVector< unsigned, 2 > Members

Indices of all the pointers that constitute this grouping.

const SCEV * Low

The SCEV expression which represents the lower bound of all the pointers in this group.

PointerInfo(Value *PointerValue, const SCEV *Start, const SCEV *End, bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId, const SCEV *Expr, bool NeedsFreeze)

const SCEV * Start

Holds the smallest byte address accessed by the pointer throughout all iterations of the loop.

const SCEV * Expr

SCEV for the access.

bool NeedsFreeze

True if the pointer expressions needs to be frozen after expansion.

bool IsWritePtr

Holds the information if this pointer is used for writing to memory.

unsigned DependencySetId

Holds the id of the set of pointers that could be dependent because of a shared underlying object.

unsigned AliasSetId

Holds the id of the disjoint alias set to which this pointer belongs.

const SCEV * End

Holds the largest byte address accessed by the pointer throughout all iterations of the loop,...

TrackingVH< Value > PointerValue

Holds the pointer value that we need to check.

Collection of parameters shared beetween the Loop Vectorizer and the Loop Access Analysis.

static const unsigned MaxVectorWidth

Maximum SIMD width.

static unsigned VectorizationFactor

VF as overridden by the user.

static unsigned RuntimeMemoryCheckThreshold

\When performing memory disambiguation checks at runtime do not make more than this number of compari...

static bool isInterleaveForced()

True if force-vector-interleave was specified by the user.

static unsigned VectorizationInterleave

Interleave factor as overridden by the user.

static bool HoistRuntimeChecks