AliasSetTracker.cpp Source File (original) (raw)

19#include "llvm/Config/llvm-config.h"

35using namespace llvm;

39 cl::desc("The maximum total number of memory locations alias "

40 "sets may contain before degradation"));

45 assert(!AS.Forward && "Alias set is already forwarding!");

46 assert(!Forward && "This set is a forwarding set!!");

49 Access |= AS.Access;

50 Alias |= AS.Alias;

52 if (Alias == SetMustAlias) {

57 return BatchAA.isMustAlias(MemLoc, ASMemLoc);

58 });

59 }))

60 Alias = SetMayAlias;

61 }

64 if (MemoryLocs.empty()) {

65 std::swap(MemoryLocs, AS.MemoryLocs);

66 } else {

68 AS.MemoryLocs.clear();

69 }

71 bool ASHadUnknownInsts = !AS.UnknownInsts.empty();

72 if (UnknownInsts.empty()) {

73 if (ASHadUnknownInsts) {

74 std::swap(UnknownInsts, AS.UnknownInsts);

75 addRef();

76 }

77 } else if (ASHadUnknownInsts) {

79 AS.UnknownInsts.clear();

80 }

82 AS.Forward = this;

83 addRef();

85 if (ASHadUnknownInsts)

86 AS.dropRef(AST);

87}

89void AliasSetTracker::removeAliasSet(AliasSet *AS) {

90 if (AliasSet *Fwd = AS->Forward) {

91 Fwd->dropRef(*this);

92 AS->Forward = nullptr;

93 } else

94 TotalAliasSetSize -= AS->size();

96 AliasSets.erase(AS);

99 if (AS == AliasAnyAS) {

100 AliasAnyAS = nullptr;

101 assert(AliasSets.empty() && "Tracker not empty");

102 }

103}

104

106 assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");

107 AST.removeAliasSet(this);

108}

109

112 bool KnownMustAlias) {

114

115

118 }))

119 Alias = SetMayAlias;

120 }

121

122

123 MemoryLocs.push_back(MemLoc);

124

125 AST.TotalAliasSetSize++;

126}

127

129 if (UnknownInsts.empty())

130 addRef();

131 UnknownInsts.emplace_back(I);

132

133

134

135 using namespace PatternMatch;

136 bool MayWriteMemory = I->mayWriteToMemory() && isGuard (I) &&

137 !(I->use_empty() && match(I, m_IntrinsicIntrinsic::invariant\_start()));

138 if (!MayWriteMemory) {

139 Alias = SetMayAlias;

140 Access |= RefAccess;

141 return;

142 }

143

144

145 Alias = SetMayAlias;

146 Access = ModRefAccess;

147}

148

149

150

151

152

155 if (AliasAny)

157

158

159 for (const auto &ASMemLoc : MemoryLocs) {

162 return AR;

163 }

164

165

169

171}

172

175

176 if (AliasAny)

178

181

182 for (Instruction *UnknownInst : UnknownInsts) {

183 const auto *C1 = dyn_cast(UnknownInst);

184 const auto *C2 = dyn_cast(Inst);

187

189 }

190 }

191

193 for (const auto &ASMemLoc : MemoryLocs) {

196 return MR;

197 }

198

199 return MR;

200}

201

207}

208

210 PointerMap.clear();

211 AliasSets.clear();

212}

213

214

215

216

217

218

219

220AliasSet *AliasSetTracker::mergeAliasSetsForMemoryLocation(

222 AliasSet *FoundSet = nullptr;

223 MustAliasAll = true;

225 if (AS.Forward)

226 continue;

227

228

229

230

231

232

233

234 if (&AS != PtrAS) {

237 continue;

238

240 MustAliasAll = false;

241 }

242

243 if (!FoundSet) {

244

245 FoundSet = &AS;

246 } else {

247

249 }

250 }

251

252 return FoundSet;

253}

254

255AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {

256 AliasSet *FoundSet = nullptr;

259 continue;

260 if (!FoundSet) {

261

262 FoundSet = &AS;

263 } else {

264

266 }

267 }

268 return FoundSet;

269}

270

272

273

274

275 AliasSet *&MapEntry = PointerMap[MemLoc.Ptr];

276 if (MapEntry) {

277 collapseForwardingIn(MapEntry);

278 if (is_contained(MapEntry->MemoryLocs, MemLoc))

279 return *MapEntry;

280 }

281

283 bool MustAliasAll = false;

284 if (AliasAnyAS) {

285

286

287

288

289

290 AS = AliasAnyAS;

291 } else if (AliasSet *AliasAS = mergeAliasSetsForMemoryLocation(

292 MemLoc, MapEntry, MustAliasAll)) {

293

294 AS = AliasAS;

295 } else {

296

297 AliasSets.push_back(AS = new AliasSet());

298 MustAliasAll = true;

299 }

300

301

302 AS->addMemoryLocation(*this, MemLoc, MustAliasAll);

303

304

305 if (MapEntry) {

306 collapseForwardingIn(MapEntry);

307 assert(MapEntry == AS && "Memory locations with same pointer value cannot "

308 "be in different alias sets");

309 } else {

310 AS->addRef();

311 MapEntry = AS;

312 }

313 return *AS;

314}

315

317 addMemoryLocation(Loc, AliasSet::NoAccess);

318}

319

324}

325

330}

331

334}

335

338}

339

343}

344

346 if (isa(Inst))

347 return;

348

349 if (auto *II = dyn_cast(Inst)) {

350

351

352 switch (II->getIntrinsicID()) {

353 default:

354 break;

355

356 case Intrinsic::allow_runtime_check:

357 case Intrinsic::allow_ubsan_check:

358 case Intrinsic::assume:

359 case Intrinsic::experimental_noalias_scope_decl:

360 case Intrinsic::sideeffect:

361 case Intrinsic::pseudoprobe:

362 return;

363 }

364 }

366 return;

367

368 if (AliasSet *AS = findAliasSetForUnknownInst(Inst)) {

369 AS->addUnknownInst(Inst, AA);

370 return;

371 }

372 AliasSets.push_back(new AliasSet());

373 AliasSets.back().addUnknownInst(Inst, AA);

374}

375

377

378 if (LoadInst *LI = dyn_cast(I))

379 return add(LI);

380 if (StoreInst *SI = dyn_cast(I))

381 return add(SI);

382 if (VAArgInst *VAAI = dyn_cast(I))

383 return add(VAAI);

385 return add(MSI);

387 return add(MTI);

388

389

390 if (auto *Call = dyn_cast(I))

391 if (Call->onlyAccessesArgMemory()) {

394 return AliasSet::ModRefAccess;

396 return AliasSet::ModAccess;

398 return AliasSet::RefAccess;

399 else

400 return AliasSet::NoAccess;

401 };

402

404

405

406

407

408 using namespace PatternMatch;

409 if (Call->use_empty() &&

410 match(Call, m_IntrinsicIntrinsic::invariant\_start()))

412

413 for (auto IdxArgPair : enumerate(Call->args())) {

414 int ArgIdx = IdxArgPair.index();

415 const Value *Arg = IdxArgPair.value();

417 continue;

421 ArgMask &= CallMask;

423 addMemoryLocation(ArgLoc, getAccessFromModRef(ArgMask));

424 }

425 return;

426 }

427

429}

430

432 for (auto &I : BB)

434}

435

437 assert(&AA == &AST.AA &&

438 "Merging AliasSetTracker objects with different Alias Analyses!");

439

440

441

442

443 for (const AliasSet &AS : AST) {

444 if (AS.Forward)

445 continue;

446

447

448 for (Instruction *Inst : AS.UnknownInsts)

449 add(Inst);

450

451

453 addMemoryLocation(ASMemLoc, (AliasSet::AccessLattice)AS.Access);

454 }

455}

456

457AliasSet &AliasSetTracker::mergeAllAliasSets() {

459 "Full merge should happen once, when the saturation threshold is "

460 "reached");

461

462

463

464 std::vector<AliasSet *> ASVector;

467 ASVector.push_back(&AS);

468

469

470

471 AliasSets.push_back(new AliasSet());

472 AliasAnyAS = &AliasSets.back();

473 AliasAnyAS->Alias = AliasSet::SetMayAlias;

474 AliasAnyAS->Access = AliasSet::ModRefAccess;

475 AliasAnyAS->AliasAny = true;

476

477 for (auto *Cur : ASVector) {

478

479 AliasSet *FwdTo = Cur->Forward;

480 if (FwdTo) {

481 Cur->Forward = AliasAnyAS;

482 AliasAnyAS->addRef();

483 FwdTo->dropRef(*this);

484 continue;

485 }

486

487

488 AliasAnyAS->mergeSetIn(*Cur, *this, AA);

489 }

490

491 return *AliasAnyAS;

492}

493

495 AliasSet::AccessLattice E) {

497 AS.Access |= E;

498

500

501

502 return mergeAllAliasSets();

503 }

504

505 return AS;

506}

507

508

509

510

511

513 OS << " AliasSet[" << (const void*)this << ", " << RefCount << "] ";

514 OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";

515 switch (Access) {

516 case NoAccess: OS << "No access "; break;

517 case RefAccess: OS << "Ref "; break;

518 case ModAccess: OS << "Mod "; break;

519 case ModRefAccess: OS << "Mod/Ref "; break;

521 }

522 if (Forward)

523 OS << " forwarding to " << (void*)Forward;

524

525 if (!MemoryLocs.empty()) {

526 ListSeparator LS;

527 OS << "Memory locations: ";

529 OS << LS;

532 OS << ", unknown after)";

534 OS << ", unknown before-or-after)";

535 else

536 OS << ", " << MemLoc.Size << ")";

537 }

538 }

539 if (!UnknownInsts.empty()) {

540 ListSeparator LS;

541 OS << "\n " << UnknownInsts.size() << " Unknown instructions: ";

543 OS << LS;

544 if (I->hasName())

545 I->printAsOperand(OS);

546 else

547 I->print(OS);

548 }

549 }

550 OS << "\n";

551}

552

554 OS << "Alias Set Tracker: " << AliasSets.size();

555 if (AliasAnyAS)

556 OS << " (Saturated)";

557 OS << " alias sets for " << PointerMap.size() << " pointer values.\n";

558 for (const AliasSet &AS : *this)

560 OS << "\n";

561}

562

563#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

566#endif

567

568

569

570

571

573

579 OS << "Alias sets for function '" << F.getName() << "':\n";

581 Tracker.add(&I);

582 Tracker.print(OS);

584}

unsigned const MachineRegisterInfo * MRI

static cl::opt< unsigned > SaturationThreshold("alias-set-saturation-threshold", cl::Hidden, cl::init(250), cl::desc("The maximum total number of memory locations alias " "sets may contain before degradation"))

Expand Atomic instructions

Atomic ordering constants.

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

This header defines various interfaces for pass management in LLVM.

This file provides utility analysis objects describing memory locations.

uint64_t IntrinsicInst * II

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

This file implements a set that has insertion order iteration characteristics.

A manager for alias analyses.

The possible results of an alias query.

@ MayAlias

The two locations may or may not alias.

@ NoAlias

The two locations do not alias at all.

@ MustAlias

The two locations precisely alias each other.

BatchAAResults & getAliasAnalysis() const

Return the underlying alias analysis object used by this tracker.

AliasSet & getAliasSetFor(const MemoryLocation &MemLoc)

Return the alias set which contains the specified memory location.

void addUnknown(Instruction *I)

void print(raw_ostream &OS) const

void add(const MemoryLocation &Loc)

These methods are used to add different types of instructions to the alias sets.

void mergeSetIn(AliasSet &AS, AliasSetTracker &AST, BatchAAResults &BatchAA)

Merge the specified alias set into this alias set.

void print(raw_ostream &OS) const

ModRefInfo aliasesUnknownInst(const Instruction *Inst, BatchAAResults &AA) const

AliasResult aliasesMemoryLocation(const MemoryLocation &MemLoc, BatchAAResults &AA) const

If the specified memory location "may" (or must) alias one of the members in the set return the appro...

PointerVector getPointers() const

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

AliasSetsPrinterPass(raw_ostream &OS)

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

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

This class represents any memset intrinsic.

LLVM Basic Block Representation.

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

AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)

ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)

MemoryEffects getMemoryEffects(const CallBase *Call)

ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)

bool mayReadOrWriteMemory() const

Return true if this instruction may read or write memory.

An instruction for reading from memory.

AtomicOrdering getOrdering() const

Returns the ordering constraint of this load instruction.

static constexpr LocationSize beforeOrAfterPointer()

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

static constexpr LocationSize afterPointer()

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

ModRefInfo getModRef(Location Loc) const

Get ModRefInfo for the given Location.

Representation for a specific memory location.

static MemoryLocation get(const LoadInst *LI)

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

static MemoryLocation getForSource(const MemTransferInst *MTI)

Return a location representing the source of a memory transfer.

LocationSize Size

The maximum size of the location, in address-units, or UnknownSize if the size is not known.

const Value * Ptr

The address of the start of the location.

static MemoryLocation getForDest(const MemIntrinsic *MI)

Return a location representing the destination of a memory set or transfer.

static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)

Return a location representing a particular argument of a call.

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

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Vector takeVector()

Clear the SetVector and return the underlying vector.

bool insert(const value_type &X)

Insert a new element into the SetVector.

A SetVector that performs no allocations if smaller than a certain size.

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

An instruction for storing to memory.

bool isPointerTy() const

True if this is an instance of PointerType.

This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...

LLVM Value Representation.

Type * getType() const

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

void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const

Print the name of this Value out to the specified raw_ostream.

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

#define llvm_unreachable(msg)

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

bool match(Val *V, const Pattern &P)

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

auto enumerate(FirstRange &&First, RestRanges &&...Rest)

Given two or more input ranges, returns a new range whose values are tuples (A, B,...

bool isStrongerThanMonotonic(AtomicOrdering AO)

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

Wrapper function to append range R to container C.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

bool any_of(R &&range, UnaryPredicate P)

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

bool isGuard(const User *U)

Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....

bool isModSet(const ModRefInfo MRI)

raw_ostream & dbgs()

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

bool isModOrRefSet(const ModRefInfo MRI)

ModRefInfo

Flags indicating whether a memory access modifies or references memory.

@ Ref

The access may reference the value stored in memory.

@ ModRef

The access may reference and may modify the value stored in memory.

@ NoModRef

The access neither references nor modifies the value stored in memory.

bool isModAndRefSet(const ModRefInfo MRI)

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

bool isNoModRef(const ModRefInfo MRI)

bool isRefSet(const ModRefInfo MRI)

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.