MemoryDependenceAnalysis.h Source File (original) (raw)

13#ifndef LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H

14#define LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H

27#include

29namespace llvm {

36class MemDepResult {

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

114 ValueTy Value;

115

117

118public:

120

121

122

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

126 }

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

130 }

140

141

142

143 bool isClobber() const { return Value.is(); }

144

145

146

147 bool isDef() const { return Value.is(); }

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

186 bool operator==(const MemDepResult &M) const { return Value == M.Value; }

187 bool operator!=(const MemDepResult &M) const { return Value != M.Value; }

188 bool operator<(const MemDepResult &M) const { return Value < M.Value; }

189 bool operator>(const MemDepResult &M) const { return Value > M.Value; }

190

191private:

193

194

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

196

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:

236 : Entry(BB, Result), Address(Address) {}

237

238

240

242 Entry.setResult(R);

243 Address = Addr;

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

274 LocalDepMapType LocalDeps;

275

276public:

278

279private:

280

281

283

284

285

286

287

288

290

291

292 struct NonLocalPointerInfo {

293

294 BBSkipFirstBlockPair Pair;

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

375 FunctionAnalysisManager::Invalidator &Inv);

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

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

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.

This file defines the SmallPtrSet class.

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

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.

Definition MemoryDependenceAnalysis.h:36

bool isClobber() const

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

Definition MemoryDependenceAnalysis.h:143

bool operator!=(const MemDepResult &M) const

Definition MemoryDependenceAnalysis.h:187

bool isNonLocal() const

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

Definition MemoryDependenceAnalysis.h:154

static MemDepResult getNonLocal()

Definition MemoryDependenceAnalysis.h:131

bool isNonFuncLocal() const

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

Definition MemoryDependenceAnalysis.h:160

friend class MemoryDependenceResults

Definition MemoryDependenceAnalysis.h:192

bool operator>(const MemDepResult &M) const

Definition MemoryDependenceAnalysis.h:189

static MemDepResult getClobber(Instruction *Inst)

Definition MemoryDependenceAnalysis.h:127

bool isDef() const

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

Definition MemoryDependenceAnalysis.h:147

bool operator==(const MemDepResult &M) const

Definition MemoryDependenceAnalysis.h:186

static MemDepResult getUnknown()

Definition MemoryDependenceAnalysis.h:137

bool operator<(const MemDepResult &M) const

Definition MemoryDependenceAnalysis.h:188

bool isLocal() const

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

Definition MemoryDependenceAnalysis.h:150

bool isUnknown() const

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

Definition MemoryDependenceAnalysis.h:166

static MemDepResult getNonFuncLocal()

Definition MemoryDependenceAnalysis.h:134

static MemDepResult getDef(Instruction *Inst)

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

Definition MemoryDependenceAnalysis.h:123

Instruction * getInst() const

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

Definition MemoryDependenceAnalysis.h:172

MemoryDependenceResults run(Function &F, FunctionAnalysisManager &AM)

MemoryDependenceResults Result

Definition MemoryDependenceAnalysis.h:522

MemoryDependenceAnalysis(unsigned DefaultBlockScanLimit)

Definition MemoryDependenceAnalysis.h:525

MemoryDependenceAnalysis()

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

Definition MemoryDependenceAnalysis.h:271

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

std::vector< NonLocalDepEntry > NonLocalDepInfo

Definition MemoryDependenceAnalysis.h:277

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)

Definition MemoryDependenceAnalysis.h:367

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.

Definition MemoryDependenceAnalysis.h:479

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.

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

Definition MemoryDependenceAnalysis.h:550

static char ID

Definition MemoryDependenceAnalysis.h:536

void releaseMemory() override

Clean up memory in between runs.

MemoryDependenceWrapperPass()

Representation for a specific memory location.

This is an entry in the NonLocalDepInfo cache.

Definition MemoryDependenceAnalysis.h:205

void setResult(const MemDepResult &R)

Definition MemoryDependenceAnalysis.h:219

NonLocalDepEntry(BasicBlock *BB, MemDepResult Result)

Definition MemoryDependenceAnalysis.h:210

BasicBlock * getBB() const

Definition MemoryDependenceAnalysis.h:217

bool operator<(const NonLocalDepEntry &RHS) const

Definition MemoryDependenceAnalysis.h:223

NonLocalDepEntry(BasicBlock *BB)

Definition MemoryDependenceAnalysis.h:214

const MemDepResult & getResult() const

Definition MemoryDependenceAnalysis.h:221

This is a result from a NonLocal dependence query.

Definition MemoryDependenceAnalysis.h:230

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

Definition MemoryDependenceAnalysis.h:235

BasicBlock * getBB() const

Definition MemoryDependenceAnalysis.h:239

const MemDepResult & getResult() const

Definition MemoryDependenceAnalysis.h:246

Value * getAddress() const

Returns the address of this pointer in this block.

Definition MemoryDependenceAnalysis.h:256

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

Definition MemoryDependenceAnalysis.h:241

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

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

A sum type over pointer-like types.

static PointerSumType create(typename HelperT::template Lookup< N >::PointerT Pointer)

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.

Abstract Attribute helper functions.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

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.