AliasAnalysis.cpp Source File (original) (raw)

49#include

50#include

51#include

53#define DEBUG_TYPE "aa"

55using namespace llvm;

57 STATISTIC(NumNoAlias, "Number of NoAlias results");

58 STATISTIC(NumMayAlias, "Number of MayAlias results");

59 STATISTIC(NumMustAlias, "Number of MustAlias results");

61namespace llvm {

65}

67#ifndef NDEBUG

70#else

72#endif

77 : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {}

88 if (!PAC.preservedWhenStateless())

89 return true;

95 return true;

98 return false;

99}

100

101

102

103

104

108 return alias(LocA, LocB, AAQIP, nullptr);

109}

110

115

117 for (unsigned I = 0; I < AAQI.Depth; ++I)

118 dbgs() << " ";

119 dbgs() << "Start " << *LocA.Ptr << " @ " << LocA.Size << ", "

120 << *LocB.Ptr << " @ " << LocB.Size << "\n";

121 }

122

124 for (const auto &AA : AAs) {

125 Result = AA->alias(LocA, LocB, AAQI, CtxI);

127 break;

128 }

130

132 for (unsigned I = 0; I < AAQI.Depth; ++I)

133 dbgs() << " ";

134 dbgs() << "End " << *LocA.Ptr << " @ " << LocA.Size << ", "

135 << *LocB.Ptr << " @ " << LocB.Size << " = " << Result << "\n";

136 }

137

138 if (AAQI.Depth == 0) {

140 ++NumNoAlias;

142 ++NumMustAlias;

143 else

144 ++NumMayAlias;

145 }

146 return Result;

147}

148

150 bool IgnoreLocals) {

153}

154

158

159 for (const auto &AA : AAs) {

160 Result &= AA->getModRefInfoMask(Loc, AAQI, IgnoreLocals);

161

162

165 }

166

167 return Result;

168}

169

172

173 for (const auto &AA : AAs) {

174 Result &= AA->getArgModRefInfo(Call, ArgIdx);

175

176

179 }

180

181 return Result;

182}

183

188}

189

192

193 if (const auto *Call1 = dyn_cast(I)) {

194

196 }

197

198 if (I->isFenceLike())

200

201

202

203

209}

210

215

216 for (const auto &AA : AAs) {

217 Result &= AA->getModRefInfo(Call, Loc, AAQI);

218

219

222 }

223

224

225

226

227

228

231 if (ME.doesNotAccessMemory())

233

236 if ((ArgMR | OtherMR) != OtherMR) {

237

238

239

242 const Value *Arg = I.value();

244 continue;

245 unsigned ArgIdx = I.index();

250 }

251 ArgMR &= AllArgsMask;

252 }

253

254 Result &= ArgMR | OtherMR;

255

256

257

258

261

262 return Result;

263}

264

268

269 for (const auto &AA : AAs) {

270 Result &= AA->getModRefInfo(Call1, Call2, AAQI);

271

272

275 }

276

277

278

279

280

282 if (Call1B.doesNotAccessMemory())

284

286 if (Call2B.doesNotAccessMemory())

288

289

290 if (Call1B.onlyReadsMemory() && Call2B.onlyReadsMemory())

292

293

294

295 if (Call1B.onlyReadsMemory())

297 else if (Call1B.onlyWritesMemory())

299

300

301

302

303 if (Call2B.onlyAccessesArgPointees()) {

304 if (!Call2B.doesAccessArgPointees())

308 const Value *Arg = *I;

310 continue;

311 unsigned Call2ArgIdx = std::distance(Call2->arg_begin(), I);

312 auto Call2ArgLoc =

314

315

316

317

318

319

324 else if (isRefSet(ArgModRefC2))

326

327

328

329 ArgMask &= getModRefInfo(Call1, Call2ArgLoc, AAQI);

330

331 R = (R | ArgMask) & Result;

332 if (R == Result)

333 break;

334 }

335

336 return R;

337 }

338

339

340

341 if (Call1B.onlyAccessesArgPointees()) {

342 if (!Call1B.doesAccessArgPointees())

346 const Value *Arg = *I;

348 continue;

349 unsigned Call1ArgIdx = std::distance(Call1->arg_begin(), I);

350 auto Call1ArgLoc =

352

353

354

355

360 R = (R | ArgModRefC1) & Result;

361

362 if (R == Result)

363 break;

364 }

365

366 return R;

367 }

368

369 return Result;

370}

371

375

376 for (const auto &AA : AAs) {

377 Result &= AA->getMemoryEffects(Call, AAQI);

378

379

380 if (Result.doesNotAccessMemory())

381 return Result;

382 }

383

384 return Result;

385}

386

390}

391

394

395 for (const auto &AA : AAs) {

396 Result &= AA->getMemoryEffects(F);

397

398

399 if (Result.doesNotAccessMemory())

400 return Result;

401 }

402

403 return Result;

404}

405

407 switch (AR) {

409 OS << "NoAlias";

410 break;

412 OS << "MustAlias";

413 break;

415 OS << "MayAlias";

416 break;

418 OS << "PartialAlias";

421 break;

422 }

423 return OS;

424}

425

426

427

428

429

433

436

437

438

439 if (Loc.Ptr) {

443 }

444

446}

447

451

454

455 if (Loc.Ptr) {

457

458

461

462

463

464

465

468 }

469

470

472}

473

477

478

479

480 if (Loc.Ptr)

483}

484

488 if (Loc.Ptr) {

490

491

494

495

496

498 }

499

500

502}

503

507 if (Loc.Ptr) {

508

509

511 }

512

513

515}

516

520 if (Loc.Ptr) {

521

522

524 }

525

526

528}

529

533

536

537 if (Loc.Ptr) {

539

540

543 }

544

546}

547

551

554

555 if (Loc.Ptr) {

557

558

561 }

562

564}

565

567 const std::optional &OptLoc,

569 if (OptLoc == std::nullopt) {

570 if (const auto *Call = dyn_cast(I))

572 }

573

575

576 switch (I->getOpcode()) {

577 case Instruction::VAArg:

579 case Instruction::Load:

581 case Instruction::Store:

583 case Instruction::Fence:

585 case Instruction::AtomicCmpXchg:

587 case Instruction::AtomicRMW:

589 case Instruction::Call:

590 case Instruction::CallBr:

591 case Instruction::Invoke:

593 case Instruction::CatchPad:

595 case Instruction::CatchRet:

597 default:

598 assert(->mayReadOrWriteMemory() &&

599 "Unhandled memory access instruction!");

601 }

602}

603

604

605

606

607

608

609

610

615 if (!DT)

617

621

622 const auto *Call = dyn_cast(I);

623 if (!Call || Call == Object)

625

627 true, I, DT,

628 true))

630

631 unsigned ArgNo = 0;

633

634 for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();

635 CI != CE; ++CI, ++ArgNo) {

636

637

638

639 if (!(*CI)->getType()->isPointerTy() || !Call->doesNotCapture(ArgNo))

640 continue;

641

645

646

647

648

650 continue;

651 if (Call->doesNotAccessMemory(ArgNo))

652 continue;

653 if (Call->onlyReadsMemory(ArgNo)) {

655 continue;

656 }

658 }

659 return R;

660}

661

662

663

664

668}

669

670

671

672

673

674

680 "Instructions not in same basic block!");

683 ++E;

684

685 for (; I != E; ++I)

687 return true;

688 return false;

689}

690

691

693

694

696

699}

700

704}

705

707

709 false, true)

710

714}

715

718}

719

721

723 "Function Alias Analysis Results", false, true)

732

733

734

735

736

737

738

739

740

742

743

744

745

746

747

748 AAR.reset(

749 new AAResults(getAnalysis().getTLI(F)));

750

751

752

753

754

756 AAR->addAAResult(getAnalysis().getResult());

757

758

759 if (auto *WrapperPass = getAnalysisIfAvailable())

760 AAR->addAAResult(WrapperPass->getResult());

761 if (auto *WrapperPass = getAnalysisIfAvailable())

762 AAR->addAAResult(WrapperPass->getResult());

763 if (auto *WrapperPass = getAnalysisIfAvailable())

764 AAR->addAAResult(WrapperPass->getResult());

765 if (auto *WrapperPass = getAnalysisIfAvailable())

766 AAR->addAAResult(WrapperPass->getResult());

767

768

769

770 if (auto *WrapperPass = getAnalysisIfAvailable())

771 if (WrapperPass->CB)

772 WrapperPass->CB(*this, F, *AAR);

773

774

775 return false;

776}

777

782

783

784

785

786

792}

793

796 for (auto &Getter : ResultGetters)

797 (*Getter)(F, AM, R);

798 return R;

799}

800

802 if (const auto *Call = dyn_cast(V))

803 return Call->hasRetAttr(Attribute::NoAlias);

804 return false;

805}

806

808 if (const Argument *A = dyn_cast(V))

809 return A->hasNoAliasAttr() || A->hasByValAttr();

810 return false;

811}

812

814 if (isa(V))

815 return true;

816 if (isa(V) && !isa(V))

817 return true;

819 return true;

821 return true;

822 return false;

823}

824

827}

828

830

831

832

833

834 return (isa(V) || isa(V));

835}

836

838 if (auto *CB = dyn_cast(V))

840 true);

841

842

843

844

845 if (isa(V))

846 return true;

847

848

849

850

851

852

853 if (isa(V))

854 return true;

855

856

857 if (auto *CE = dyn_cast(V))

858 if (CE->getOpcode() == Instruction::IntToPtr)

859 return true;

860

861 return false;

862}

863

865 bool &RequiresNoCaptureBeforeUnwind) {

866 RequiresNoCaptureBeforeUnwind = false;

867

868

869 if (isa(Object))

870 return true;

871

872

873 if (auto *A = dyn_cast(Object))

874 return A->hasByValAttr() || A->hasAttribute(Attribute::DeadOnUnwind);

875

876

877

878

880 RequiresNoCaptureBeforeUnwind = true;

881 return true;

882 }

883

884 return false;

885}

886

887

888

890 bool &ExplicitlyDereferenceableOnly) {

891 ExplicitlyDereferenceableOnly = false;

892

893

894

895 if (isa(Object))

896 return true;

897

898 if (auto *A = dyn_cast(Object)) {

899

900

901

902 if (A->hasAttribute(Attribute::Writable) && A->hasNoAliasAttr()) {

903 ExplicitlyDereferenceableOnly = true;

904 return true;

905 }

906

907 return A->hasByValAttr();

908 }

909

910

911

913}

static cl::opt< bool > EnableAATrace("aa-trace", cl::Hidden, cl::init(false))

Print a trace of alias analysis queries and their results.

static bool isNoAliasOrByValArgument(const Value *V)

Function Alias Analysis Results

Atomic ordering constants.

This file contains the simple types necessary to represent the attributes associated with functions a...

This is the interface for LLVM's primary stateless and local alias analysis.

block Block Frequency Analysis

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

static bool runOnFunction(Function &F, bool PostInlining)

This is the interface for a simple mod/ref and alias analysis over globals.

This file provides utility analysis objects describing memory locations.

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)

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

This is the interface for a SCEV-based alias analysis.

This is the interface for a metadata-based scoped no-alias analysis.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

This is the interface for a metadata-based TBAA.

A manager for alias analyses.

Result run(Function &F, FunctionAnalysisManager &AM)

This class stores info we want to provide to or retain within an alias query.

unsigned Depth

Query depth used to distinguish recursive queries.

A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

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

Check whether or not an instruction may read or write the optionally specified memory location.

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

The main low level interface to the alias analysis implementation.

ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, bool IgnoreLocals=false)

Returns a bitmask that should be unconditionally applied to the ModRef info of a memory location.

ModRefInfo callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT)

Return information about whether a particular call site modifies or reads the specified memory locati...

AAResults(const TargetLibraryInfo &TLI)

MemoryEffects getMemoryEffects(const CallBase *Call)

Return the behavior of the given call site.

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

Handle invalidation events in the new pass manager.

ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)

Get the ModRef info associated with a pointer argument of a call.

bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, const MemoryLocation &Loc, const ModRefInfo Mode)

Check if it is possible for the execution of the specified instructions to mod(according to the mode)...

bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc)

Check if it is possible for execution of the specified basic block to modify the location Loc.

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.

@ PartialAlias

The two locations alias, but only due to a partial overlap.

@ MustAlias

The two locations precisely alias each other.

constexpr int32_t getOffset() const

constexpr bool hasOffset() const

API to communicate dependencies between analyses during invalidation.

bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)

Trigger the invalidation of some other analysis pass if not already handled and return whether it was...

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.

Represent the analysis usage information of a pass.

AnalysisUsage & addUsedIfAvailable()

Add the specified Pass class to the set of analyses used by this pass.

void setPreservesAll()

Set by analyses that do not transform their input at all.

AnalysisUsage & addRequiredTransitive()

This class represents an incoming formal argument to a Function.

An instruction that atomically checks whether a specified value is in a memory location,...

AtomicOrdering getSuccessOrdering() const

Returns the success ordering constraint of this cmpxchg instruction.

an instruction that atomically reads a memory location, combines it with another value,...

AtomicOrdering getOrdering() const

Returns the ordering constraint of this rmw instruction.

Legacy wrapper pass to provide the BasicAAResult object.

LLVM Basic Block Representation.

InstListType::const_iterator const_iterator

const Instruction & front() const

const Instruction & back() const

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

User::op_iterator arg_begin()

Return the iterator pointing to the beginning of the argument list.

User::op_iterator arg_end()

Return the iterator pointing to the end of the argument list.

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

An instruction for ordering other memory operations.

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

Legacy wrapper pass to provide the GlobalsAAResult object.

ImmutablePass class - This class is used to provide information that does not need to be run.

An instruction for reading from memory.

MemoryEffectsBase getWithoutLoc(Location Loc) const

Get new MemoryEffectsBase with NoModRef on the given Loc.

ModRefInfo getModRef(Location Loc) const

Get ModRefInfo for the given Location.

static MemoryEffectsBase unknown()

Create MemoryEffectsBase that can read and write any memory.

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.

LocationSize Size

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

static MemoryLocation getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())

Return a location that may access any location before or after Ptr, while remaining within the underl...

const Value * Ptr

The address of the start of the location.

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

Return a location representing a particular argument of a call.

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

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

PreservedAnalysisChecker getChecker() const

Build a checker for this PreservedAnalyses and the specified analysis type.

Legacy wrapper pass to provide the SCEVAAResult object.

Legacy wrapper pass to provide the ScopedNoAliasAAResult object.

AAQueryInfo that uses SimpleCaptureAnalysis.

An instruction for storing to memory.

AtomicOrdering getOrdering() const

Returns the ordering constraint of this store instruction.

Analysis pass providing the TargetLibraryInfo.

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

Legacy wrapper pass to provide the TypeBasedAAResult object.

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.

const ParentTy * getParent() const

self_iterator getIterator()

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

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

cl::opt< bool > DisableBasicAA("disable-basic-aa", cl::Hidden, cl::init(false))

Allow disabling BasicAA from the AA results.

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)

bool isBaseOfObject(const Value *V)

Return true if we know V to the base address of the corresponding memory object.

bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, const DominatorTree *DT, bool IncludeI=false, unsigned MaxUsesToExplore=0, const LoopInfo *LI=nullptr)

PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...

const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)

This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....

bool isNoAliasCall(const Value *V)

Return true if this pointer is returned by a noalias function.

void initializeAAResultsWrapperPassPass(PassRegistry &)

bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(const CallBase *Call, bool MustPreserveNullness)

{launder,strip}.invariant.group returns pointer that aliases its argument, and it only captures point...

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)

bool isNotVisibleOnUnwind(const Value *Object, bool &RequiresNoCaptureBeforeUnwind)

Return true if Object memory is not visible after an unwind, in the sense that program semantics cann...

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.

@ Mod

The access may modify the value stored in memory.

@ NoModRef

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

@ ArgMem

Access to memory via argument pointers.

@ InaccessibleMem

Memory that is inaccessible via LLVM IR.

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

bool isIdentifiedFunctionLocal(const Value *V)

Return true if V is umabigously identified at the function-level.

OutputIt move(R &&Range, OutputIt Out)

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

bool isEscapeSource(const Value *V)

Returns true if the pointer is one which would have been considered an escape by isNonEscapingLocalOb...

ImmutablePass * createExternalAAWrapperPass(std::function< void(Pass &, Function &, AAResults &)> Callback)

A wrapper pass around a callback which can be used to populate the AAResults in the AAResultsWrapperP...

void initializeExternalAAWrapperPassPass(PassRegistry &)

bool isNoModRef(const ModRefInfo MRI)

bool isIdentifiedObject(const Value *V)

Return true if this pointer refers to a distinct and identifiable object.

bool isStrongerThan(AtomicOrdering AO, AtomicOrdering Other)

Returns true if ao is stronger than other as defined by the AtomicOrdering lattice,...

bool isRefSet(const ModRefInfo MRI)

bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)

Return true if the Object is writable, in the sense that any location based on this pointer that can ...

Implement std::hash so that hash_code can be used in STL containers.

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

A wrapper pass for external alias analyses.

std::function< void(Pass &, Function &, AAResults &)> CallbackT