MemoryDependenceAnalysis.h Source File (original) (raw)

13#ifndef LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H

14#define LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H

27#include

29namespace llvm {

31class AssumptionCache;

32class DominatorTree;

33class PHITransAddr;

37 enum DepType {

48 Invalid = 0,

59 Clobber,

84 Def,

91 Other

92 };

96 enum OtherType {

100

101 NonLocal = 1,

102

103

104 NonFuncLocal,

105

106 Unknown

107 };

108

115

117

118public:

120

121

122

124 assert(Inst && "Def requires inst");

125 return MemDepResult(ValueTy::create(Inst));

126 }

128 assert(Inst && "Clobber requires inst");

129 return MemDepResult(ValueTy::create(Inst));

130 }

132 return MemDepResult(ValueTy::create(NonLocal));

133 }

135 return MemDepResult(ValueTy::create(NonFuncLocal));

136 }

138 return MemDepResult(ValueTy::create(Unknown));

139 }

140

141

142

144

145

146

148

149

151

152

153

155 return Value.is() && Value.cast() == NonLocal;

156 }

157

158

159

161 return Value.is() && Value.cast() == NonFuncLocal;

162 }

163

164

165

167 return Value.is() && Value.cast() == Unknown;

168 }

169

170

171

173 switch (Value.getTag()) {

174 case Invalid:

175 return Value.cast();

176 case Clobber:

177 return Value.cast();

178 case Def:

179 return Value.cast();

180 case Other:

181 return nullptr;

182 }

184 }

185

190

191private:

193

194

195 bool isDirty() const { return Value.is(); }

196

198 return MemDepResult(ValueTy::create(Inst));

199 }

200};

201

202

203

204

208

209public:

211 : BB(BB), Result(Result) {}

212

213

215

216

218

220

222

224};

225

226

227

228

229

233

234public:

237

238

240

242 Entry.setResult(R);

244 }

245

247

248

249

250

251

252

253

254

255

257};

258

259

260

261

262

263

264

265

266

267

268

269

270

272

275

276public:

278

279private:

280

281

283

284

285

286

287

288

290

291

292 struct NonLocalPointerInfo {

293

295

297

298

299

301

302

303

305

306 NonLocalPointerInfo() = default;

307 };

308

309

310

311

313 using ReverseNonLocalDefsCacheTy =

315 ReverseNonLocalDefsCacheTy ReverseNonLocalDefsCache;

316

317

318

319

320

321

322 using CachedNonLocalPointerInfo =

324 CachedNonLocalPointerInfo NonLocalPointerDeps;

325

326

327 using ReverseNonLocalPtrDepTy =

329 ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps;

330

331

332

333

334

335

336 using PerInstNLInfo = std::pair<NonLocalDepInfo, bool>;

337

338

340

341 NonLocalDepMapType NonLocalDepsMap;

342

343

344

345 using ReverseDepMapType =

347 ReverseDepMapType ReverseLocalDeps;

348

349

350 ReverseDepMapType ReverseNonLocalDeps;

351

352

359

360 unsigned DefaultBlockScanLimit;

361

362

364 ClobberOffsetsMapType ClobberOffsets;

365

366public:

369 unsigned DefaultBlockScanLimit)

370 : AA(AA), AC(AC), TLI(TLI), DT(DT), EEA(DT),

371 DefaultBlockScanLimit(DefaultBlockScanLimit) {}

372

373

376

377

378

379

381

382

383

384

385

387

388

389

390

391

392

393

394

395

396

397

398

399

400

402

403

404

405

406

407

408

409

410

411

412

415

416

417

419

420

421

422

423

424

425

426

428

429

430

431

432

434

435

436

437

438

439

440

441

442

443

444

445

446

447

452 unsigned *Limit = nullptr);

453

458 unsigned *Limit,

460

466

467

468

469

470

471

472

474

475

477

478

480 const auto Off = ClobberOffsets.find(DepInst);

481 if (Off != ClobberOffsets.end())

482 return Off->getSecond();

483 return std::nullopt;

484 }

485

486private:

490 bool getNonLocalPointerDepFromBB(Instruction *QueryInst,

496 bool SkipFirstBlock = false,

497 bool IsIncomplete = false);

501 unsigned NumSortedEntries,

503

504 void removeCachedNonLocalPointerDependencies(ValueIsLoadPair P);

505

506 void verifyRemoved(Instruction *Inst) const;

507};

508

509

510

511

512

516

518

519 unsigned DefaultBlockScanLimit;

520

521public:

523

525 MemoryDependenceAnalysis(unsigned DefaultBlockScanLimit) : DefaultBlockScanLimit(DefaultBlockScanLimit) { }

526

528};

529

530

531

533 std::optional MemDep;

534

535public:

537

540

541

543

544

546

547

549

551};

552

553}

554

555#endif

static bool isLoad(int Opcode)

This file defines the DenseMap class.

This header defines various interfaces for pass management in LLVM.

This file provides utility analysis objects describing memory locations.

This file defines the PointerIntPair class.

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

This file defines the SmallPtrSet class.

API to communicate dependencies between analyses during invalidation.

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

Represent the analysis usage information of a pass.

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

LLVM Basic Block Representation.

InstListType::iterator iterator

Instruction iterators...

This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...

Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...

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

Context-sensitive CaptureAnalysis provider, which computes and caches the earliest common dominator c...

FunctionPass class - This class is used to implement most global optimizations.

An instruction for reading from memory.

static constexpr LocationSize afterPointer()

Any location after the base pointer (but still within the underlying object).

A memory dependence query can return one of three different answers.

bool isClobber() const

Tests if this MemDepResult represents a query that is an instruction clobber dependency.

bool operator!=(const MemDepResult &M) const

bool isNonLocal() const

Tests if this MemDepResult represents a query that is transparent to the start of the block,...

static MemDepResult getNonLocal()

bool isNonFuncLocal() const

Tests if this MemDepResult represents a query that is transparent to the start of the function.

bool operator>(const MemDepResult &M) const

static MemDepResult getClobber(Instruction *Inst)

bool isDef() const

Tests if this MemDepResult represents a query that is an instruction definition dependency.

bool operator==(const MemDepResult &M) const

static MemDepResult getUnknown()

bool operator<(const MemDepResult &M) const

bool isLocal() const

Tests if this MemDepResult represents a valid local query (Clobber/Def).

bool isUnknown() const

Tests if this MemDepResult represents a query which cannot and/or will not be computed.

static MemDepResult getNonFuncLocal()

static MemDepResult getDef(Instruction *Inst)

get methods: These are static ctor methods for creating various MemDepResult kinds.

Instruction * getInst() const

If this is a normal dependency, returns the instruction that is depended on.

An analysis that produces MemoryDependenceResults for a function.

MemoryDependenceResults run(Function &F, FunctionAnalysisManager &AM)

MemoryDependenceAnalysis(unsigned DefaultBlockScanLimit)

MemoryDependenceAnalysis()

Provides a lazy, caching interface for making common memory aliasing information queries,...

MemDepResult getSimplePointerDependencyFrom(const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst, unsigned *Limit, BatchAAResults &BatchAA)

std::vector< NonLocalDepEntry > NonLocalDepInfo

void invalidateCachedPredecessors()

Clears the PredIteratorCache info.

void invalidateCachedPointerInfo(Value *Ptr)

Invalidates cached information about the specified pointer, because it may be too conservative in mem...

MemoryDependenceResults(AAResults &AA, AssumptionCache &AC, const TargetLibraryInfo &TLI, DominatorTree &DT, unsigned DefaultBlockScanLimit)

MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst=nullptr, unsigned *Limit=nullptr)

Returns the instruction on which a memory location depends.

std::optional< int32_t > getClobberOffset(LoadInst *DepInst) const

Return the clobber offset to dependent instruction.

void removeInstruction(Instruction *InstToRemove)

Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...

MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB)

This analysis looks for other loads and stores with invariant.group metadata and the same pointer ope...

unsigned getDefaultBlockScanLimit() const

Some methods limit the number of instructions they will examine.

MemDepResult getDependency(Instruction *QueryInst)

Returns the instruction on which a memory operation depends.

const NonLocalDepInfo & getNonLocalCallDependency(CallBase *QueryCall)

Perform a full dependency query for the specified call, returning the set of blocks that the value is...

void getNonLocalPointerDependency(Instruction *QueryInst, SmallVectorImpl< NonLocalDepResult > &Result)

Perform a full dependency query for an access to the QueryInst's specified memory location,...

void releaseMemory()

Release memory in caches.

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

Handle invalidation in the new PM.

A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance.

bool runOnFunction(Function &) override

Pass Implementation stuff. This doesn't do any analysis eagerly.

~MemoryDependenceWrapperPass() override

void getAnalysisUsage(AnalysisUsage &AU) const override

Does not modify anything. It uses Value Numbering and Alias Analysis.

MemoryDependenceResults & getMemDep()

void releaseMemory() override

Clean up memory in between runs.

MemoryDependenceWrapperPass()

Representation for a specific memory location.

This is an entry in the NonLocalDepInfo cache.

void setResult(const MemDepResult &R)

NonLocalDepEntry(BasicBlock *BB, MemDepResult Result)

BasicBlock * getBB() const

bool operator<(const NonLocalDepEntry &RHS) const

NonLocalDepEntry(BasicBlock *BB)

const MemDepResult & getResult() const

This is a result from a NonLocal dependence query.

NonLocalDepResult(BasicBlock *BB, MemDepResult Result, Value *Address)

BasicBlock * getBB() const

const MemDepResult & getResult() const

Value * getAddress() const

Returns the address of this pointer in this block.

void setResult(const MemDepResult &R, Value *Addr)

PHITransAddr - An address value which tracks and handles phi translation.

PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.

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

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

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

LLVM Value Representation.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

This is an optimization pass for GlobalISel generic memory operations.

A collection of metadata nodes that might be associated with a memory access used by the alias-analys...

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

A compile time pair of an integer tag and the pointer-like type which it indexes within a sum type.