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");

66#ifndef NDEBUG

69#else

71#endif

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

81 FunctionAnalysisManager::Invalidator &Inv) {

87 if (!PAC.preservedWhenStateless())

88 return true;

93 if (Inv.invalidate(ID, F, PA))

94 return true;

97 return false;

98}

100

101

102

103

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

108}

109

115 "Can only call alias() on pointers");

117

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

120 dbgs() << " ";

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

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

123 }

124

126 for (const auto &AA : AAs) {

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

129 break;

130 }

132

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

135 dbgs() << " ";

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

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

138 }

139

140 if (AAQI.Depth == 0) {

142 ++NumNoAlias;

144 ++NumMustAlias;

145 else

146 ++NumMayAlias;

147 }

148 return Result;

149}

150

153

154 for (const auto &AA : AAs) {

155 Result = AA->aliasErrno(Loc, M);

157 break;

158 }

159

160 return Result;

161}

162

164 bool IgnoreLocals) {

167}

168

172

173 for (const auto &AA : AAs) {

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

175

176

179 }

180

181 return Result;

182}

183

186

187 for (const auto &AA : AAs) {

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

189

190

193 }

194

195 return Result;

196}

197

203

206

208

210 }

211

212 if (I->isFenceLike())

214

215

216

217

223}

224

229

230 for (const auto &AA : AAs) {

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

232

233

236 }

237

238

239

240

243

244 return Result;

245}

246

250

251 for (const auto &AA : AAs) {

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

253

254

257 }

258

259

260

261

262

264 if (Call1B.doesNotAccessMemory())

266

268 if (Call2B.doesNotAccessMemory())

270

271

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

274

275

276

277 if (Call1B.onlyReadsMemory())

279 else if (Call1B.onlyWritesMemory())

281

282

283

284

285 if (Call2B.onlyAccessesArgPointees()) {

286 if (!Call2B.doesAccessArgPointees())

290 const Value *Arg = *I;

292 continue;

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

294 auto Call2ArgLoc =

296

297

298

299

300

301

306 else if (isRefSet(ArgModRefC2))

308

309

310

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

312

313 R = (R | ArgMask) & Result;

314 if (R == Result)

315 break;

316 }

317

318 return R;

319 }

320

321

322

323 if (Call1B.onlyAccessesArgPointees()) {

324 if (!Call1B.doesAccessArgPointees())

328 const Value *Arg = *I;

330 continue;

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

332 auto Call1ArgLoc =

334

335

336

337

342 R = (R | ArgModRefC1) & Result;

343

344 if (R == Result)

345 break;

346 }

347

348 return R;

349 }

350

351 return Result;

352}

353

359

373

377

378 for (const auto &AA : AAs) {

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

380

381

382 if (Result.doesNotAccessMemory())

383 return Result;

384 }

385

386 return Result;

387}

388

393

396

397 for (const auto &AA : AAs) {

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

399

400

401 if (Result.doesNotAccessMemory())

402 return Result;

403 }

404

405 return Result;

406}

407

409 switch (AR) {

411 OS << "NoAlias";

412 break;

414 OS << "MustAlias";

415 break;

417 OS << "MayAlias";

418 break;

420 OS << "PartialAlias";

422 OS << " (off " << AR.getOffset() << ")";

423 break;

424 }

425 return OS;

426}

427

428

429

430

431

435

438

439

440

441 if (Loc.Ptr) {

445 }

446

448 "Stronger atomic orderings should have been handled above!");

449

452

453

455}

456

460

463

464 if (Loc.Ptr) {

466

467

470

471

472

473

474

477 }

478

480 "Stronger atomic orderings should have been handled above!");

481

484

485

487}

488

492

493

494

495 if (Loc.Ptr)

498}

499

503 if (Loc.Ptr) {

505

506

509

510

511

513 }

514

515

517}

518

522 if (Loc.Ptr) {

523

524

526 }

527

528

530}

531

535 if (Loc.Ptr) {

536

537

539 }

540

541

543}

544

548

551

552 if (Loc.Ptr) {

554

555

558 }

559

561}

562

566

569

570 if (Loc.Ptr) {

572

573

576 }

577

579}

580

582 const std::optional &OptLoc,

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

587 }

588

590

591 switch (I->getOpcode()) {

592 case Instruction::VAArg:

594 case Instruction::Load:

596 case Instruction::Store:

598 case Instruction::Fence:

600 case Instruction::AtomicCmpXchg:

602 case Instruction::AtomicRMW:

604 case Instruction::Call:

605 case Instruction::CallBr:

606 case Instruction::Invoke:

608 case Instruction::CatchPad:

610 case Instruction::CatchRet:

612 default:

613 assert(->mayReadOrWriteMemory() &&

614 "Unhandled memory access instruction!");

616 }

617}

618

619

620

621

622

623

624

625

630 if (!DT)

632

636

640

642 Object, true, I, DT,

645

646 unsigned ArgNo = 0;

648

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

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

651

652

653

654 if (!(*CI)->getType()->isPointerTy())

655 continue;

656

657

658

659

662 continue;

663

667

668

669

670

672 continue;

673 if (Call->doesNotAccessMemory(ArgNo))

674 continue;

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

677 continue;

678 }

680 }

681 return R;

682}

683

684

685

686

691

692

693

694

695

696

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

705 ++E;

706

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

709 return true;

710 return false;

711}

712

713

715

716

718

720

723

725

727 false, true)

728

732}

733

735

737

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

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

748

749

750

751

752

753

754

755

756

758

759

760

761

762

763

764 AAR.reset(

766

767

769 if (ExtWrapperPass && ExtWrapperPass->RunEarly && ExtWrapperPass->CB) {

770 LLVM_DEBUG(dbgs() << "AAResults register Early ExternalAA: "

771 << ExtWrapperPass->getPassName() << "\n");

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

773 }

774

775

776

777

778

780 LLVM_DEBUG(dbgs() << "AAResults register BasicAA\n");

782 }

783

784

785 if (auto *WrapperPass =

787 LLVM_DEBUG(dbgs() << "AAResults register ScopedNoAliasAA\n");

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

789 }

791 LLVM_DEBUG(dbgs() << "AAResults register TypeBasedAA\n");

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

793 }

795 LLVM_DEBUG(dbgs() << "AAResults register GlobalsAA\n");

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

797 }

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

801 }

802

803

804

805 if (ExtWrapperPass && !ExtWrapperPass->RunEarly && ExtWrapperPass->CB) {

806 LLVM_DEBUG(dbgs() << "AAResults register Late ExternalAA: "

807 << ExtWrapperPass->getPassName() << "\n");

808 ExtWrapperPass->CB(*this, F, *AAR);

809 }

810

811

812 return false;

813}

814

830

833 for (auto &Getter : ResultGetters)

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

835 return R;

836}

837

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

841 return false;

842}

843

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

847 return false;

848}

849

852 return true;

854 return true;

856 return true;

858 return true;

859 return false;

860}

861

865

873

877 return false;

878

879

880

881

882 return !CB->hasArgumentWithAdditionalReturnCaptureComponents();

883 }

884

885

886

887

889 return true;

890

891

892

893

894

895

897 return true;

898

899

900

901

903 return true;

904

905

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

908 return true;

909

910 return false;

911}

912

914 bool &RequiresNoCaptureBeforeUnwind) {

915 RequiresNoCaptureBeforeUnwind = false;

916

917

919 return true;

920

921

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

924

925

926

927

929 RequiresNoCaptureBeforeUnwind = true;

930 return true;

931 }

932

933 return false;

934}

935

936

937

939 bool &ExplicitlyDereferenceableOnly) {

940 ExplicitlyDereferenceableOnly = false;

941

942

943

945 return true;

946

948

949

950

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

952 ExplicitlyDereferenceableOnly = true;

953 return true;

954 }

955

956 return A->hasByValAttr();

957 }

958

959

960

962}

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

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)

Definition AliasAnalysis.cpp:844

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

Allow disabling BasicAA from the AA 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.

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

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)

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.

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

Definition AliasAnalysis.cpp:831

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.

bool runOnFunction(Function &F) override

Run the wrapper pass to rebuild an aggregation over known AA passes.

Definition AliasAnalysis.cpp:757

void getAnalysisUsage(AnalysisUsage &AU) const override

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

Definition AliasAnalysis.cpp:815

AAResultsWrapperPass()

Definition AliasAnalysis.cpp:734

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.

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

The main low level interface to the alias analysis implementation.

Definition AliasAnalysis.cpp:104

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

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

Definition AliasAnalysis.cpp:163

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

LLVM_ABI AAResults(const TargetLibraryInfo &TLI)

Definition AliasAnalysis.cpp:73

LLVM_ABI MemoryEffects getMemoryEffects(const CallBase *Call)

Return the behavior of the given call site.

Definition AliasAnalysis.cpp:389

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

Handle invalidation events in the new pass manager.

Definition AliasAnalysis.cpp:80

LLVM_ABI ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)

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

Definition AliasAnalysis.cpp:184

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

Definition AliasAnalysis.cpp:697

LLVM_ABI AliasResult aliasErrno(const MemoryLocation &Loc, const Module *M)

Definition AliasAnalysis.cpp:151

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

Definition AliasAnalysis.cpp:687

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

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.

const Instruction & back() const

InstListType::const_iterator const_iterator

const Instruction & front() 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.

Represents which components of the pointer may be captured in which location.

CaptureComponents getOtherComponents() const

Get components potentially captured through locations other than the return value.

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

An instruction for ordering other memory operations.

Legacy wrapper pass to provide the GlobalsAAResult object.

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

bool mayReadOrWriteMemory() const

Return true if this instruction may read or write memory.

An instruction for reading from memory.

ModRefInfo getModRef(Location Loc) const

Get ModRefInfo for the given Location.

static MemoryEffectsBase unknown()

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.

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 LLVM_ABI std::optional< MemoryLocation > getOrNone(const Instruction *Inst)

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

Return a location representing a particular argument of a call.

A Module instance is used to store all the information related to an LLVM module.

AnalysisType & getAnalysis() const

getAnalysis() - This function is used by subclasses to get to the analysis information ...

AnalysisType * getAnalysisIfAvailable() const

getAnalysisIfAvailable() - Subclasses use this function to get analysis information tha...

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.

Abstract Attribute helper functions.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

decltype(auto) dyn_cast(const From &Val)

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

bool isStrongerThanMonotonic(AtomicOrdering AO)

LLVM_ABI bool isBaseOfObject(const Value *V)

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

Definition AliasAnalysis.cpp:866

bool isStrongerThanUnordered(AtomicOrdering AO)

LLVM_ABI bool isNoAliasCall(const Value *V)

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

Definition AliasAnalysis.cpp:838

MemoryEffectsBase< IRMemLocation > MemoryEffects

Summary of how a function affects memory in the program.

LLVM_ABI bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, 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...

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

LLVM_ABI raw_ostream & dbgs()

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

bool isModOrRefSet(const ModRefInfo MRI)

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

Definition AliasAnalysis.cpp:913

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

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.

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

LLVM_ABI bool isIdentifiedFunctionLocal(const Value *V)

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

Definition AliasAnalysis.cpp:862

OutputIt move(R &&Range, OutputIt Out)

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

LLVM_ABI bool isEscapeSource(const Value *V)

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

Definition AliasAnalysis.cpp:874

bool capturesAnything(CaptureComponents CC)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)

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

bool isNoModRef(const ModRefInfo MRI)

LLVM_ABI bool isIdentifiedObject(const Value *V)

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

Definition AliasAnalysis.cpp:850

bool capturesAnyProvenance(CaptureComponents CC)

bool isRefSet(const ModRefInfo MRI)

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

Definition AliasAnalysis.cpp:938

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

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

LLVM_ABI ExternalAAWrapperPass()

Definition AliasAnalysis.cpp:719

bool RunEarly

Flag indicating whether this external AA should run before Basic AA.