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

116 if ( $any\_of$ (MemoryLocs, [&](const MemoryLocation &ASMemLoc) {

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

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

185 if (!C1 || !C2 || isModOrRefSet(AA.getModRefInfo(C1, C2)) ||

187

189 }

190 }

191

193 for (const auto &ASMemLoc : MemoryLocs) {

194 MR |= AA.getModRefInfo(Inst, ASMemLoc);

196 return MR;

197 }

198

199 return MR;

200}

201

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

325

331

335

339

344

347

348

349 switch (II->getIntrinsicID()) {

350 default:

351 break;

352

353 case Intrinsic::allow_runtime_check:

354 case Intrinsic::allow_ubsan_check:

355 case Intrinsic::assume:

356 case Intrinsic::experimental_noalias_scope_decl:

357 case Intrinsic::sideeffect:

358 case Intrinsic::pseudoprobe:

359 return;

360 }

361 }

363 return;

364

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

366 AS->addUnknownInst(Inst, AA);

367 return;

368 }

369 AliasSets.push_back(new AliasSet());

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

371}

372

374

376 return add(LI);

380 return add(VAAI);

382 return add(MSI);

384 return add(MTI);

385

386

388 if (Call->onlyAccessesArgMemory()) {

391 return AliasSet::ModRefAccess;

393 return AliasSet::ModAccess;

395 return AliasSet::RefAccess;

396 else

397 return AliasSet::NoAccess;

398 };

399

400 ModRefInfo CallMask = AA.getMemoryEffects(Call).getModRef();

401

402

403

404

406 if (Call->use_empty() &&

409

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

411 int ArgIdx = IdxArgPair.index();

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

414 continue;

417 ModRefInfo ArgMask = AA.getArgModRefInfo(Call, ArgIdx);

418 ArgMask &= CallMask;

420 addMemoryLocation(ArgLoc, getAccessFromModRef(ArgMask));

421 }

422 return;

423 }

424

426}

427

429 for (auto &I : BB)

431}

432

434 assert(&AA == &AST.AA &&

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

436

437

438

439

440 for (const AliasSet &AS : AST) {

441 if (AS.Forward)

442 continue;

443

444

445 for (Instruction *Inst : AS.UnknownInsts)

446 add(Inst);

447

448

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

451 }

452}

453

454AliasSet &AliasSetTracker::mergeAllAliasSets() {

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

457 "reached");

458

459

460

461 std::vector<AliasSet *> ASVector;

464 ASVector.push_back(&AS);

465

466

467

468 AliasSets.push_back(new AliasSet());

469 AliasAnyAS = &AliasSets.back();

470 AliasAnyAS->Alias = AliasSet::SetMayAlias;

471 AliasAnyAS->Access = AliasSet::ModRefAccess;

472 AliasAnyAS->AliasAny = true;

473

474 for (auto *Cur : ASVector) {

475

476 AliasSet *FwdTo = Cur->Forward;

477 if (FwdTo) {

478 Cur->Forward = AliasAnyAS;

479 AliasAnyAS->addRef();

480 FwdTo->dropRef(*this);

481 continue;

482 }

483

484

486 }

487

488 return *AliasAnyAS;

489}

490

492 AliasSet::AccessLattice E) {

494 AS.Access |= E;

495

497

498

499 return mergeAllAliasSets();

500 }

501

502 return AS;

503}

504

505

506

507

508

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

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

512 switch (Access) {

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

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

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

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

518 }

519 if (Forward)

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

521

522 if (!MemoryLocs.empty()) {

524 OS << "Memory locations: ";

526 OS << LS;

529 OS << ", unknown after)";

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

532 else

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

534 }

535 }

536 if (!UnknownInsts.empty()) {

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

540 OS << LS;

541 if (I->hasName())

542 I->printAsOperand(OS);

543 else

544 I->print(OS);

545 }

546 }

547 OS << "\n";

548}

549

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

552 if (AliasAnyAS)

553 OS << " (Saturated)";

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

555 for (const AliasSet &AS : *this)

557 OS << "\n";

558}

559

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

563#endif

564

565

566

567

568

570

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

578 Tracker.add(&I);

579 Tracker.print(OS);

581}

unsigned const MachineRegisterInfo * MRI

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

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.

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

#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

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.

LLVM_ABI void dump() const

Definition AliasSetTracker.cpp:562

BatchAAResults & getAliasAnalysis() const

Return the underlying alias analysis object used by this tracker.

LLVM_ABI AliasSet & getAliasSetFor(const MemoryLocation &MemLoc)

Return the alias set which contains the specified memory location.

Definition AliasSetTracker.cpp:271

LLVM_ABI void addUnknown(Instruction *I)

Definition AliasSetTracker.cpp:345

AliasSetTracker(BatchAAResults &AA)

Create an empty collection of AliasSets, and use the specified alias analysis object to disambiguate ...

LLVM_ABI void print(raw_ostream &OS) const

Definition AliasSetTracker.cpp:550

LLVM_ABI void add(const MemoryLocation &Loc)

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

Definition AliasSetTracker.cpp:316

LLVM_ABI void clear()

Definition AliasSetTracker.cpp:209

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

Merge the specified alias set into this alias set.

Definition AliasSetTracker.cpp:43

LLVM_ABI void print(raw_ostream &OS) const

Definition AliasSetTracker.cpp:509

AliasSet(const AliasSet &)=delete

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

Definition AliasSetTracker.cpp:173

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

Definition AliasSetTracker.cpp:153

friend class AliasSetTracker

LLVM_ABI PointerVector getPointers() const

Definition AliasSetTracker.cpp:202

LLVM_ABI void dump() const

Definition AliasSetTracker.cpp:561

SmallVector< const Value *, 8 > PointerVector

Retrieve the pointer values for the memory locations in this alias set.

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition AliasSetTracker.cpp:571

LLVM_ABI AliasSetsPrinterPass(raw_ostream &OS)

Definition AliasSetTracker.cpp:569

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

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

bool mayReadOrWriteMemory() const

Return true if this instruction may read or write memory.

A helper class to return the specified delimiter string after the first invocation of operator String...

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

Representation for a specific memory location.

static LLVM_ABI MemoryLocation get(const LoadInst *LI)

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

static LLVM_ABI 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 LLVM_ABI MemoryLocation getForDest(const MemIntrinsic *MI)

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

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

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.

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

Abstract Attribute helper functions.

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

IntrinsicID_match m_Intrinsic()

Match intrinsic calls like this: m_IntrinsicIntrinsic::fabs(m_Value(X))

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

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

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)

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

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.