TypeBasedAliasAnalysis.cpp Source File (original) (raw)

100

101

102

103

104

105

106

107

124#include

125#include

126

127using namespace llvm;

128

129

130

131

133

134namespace {

135

136

137

138static bool isNewFormatTypeNode(const MDNode *N) {

139 if (N->getNumOperands() < 3)

140 return false;

141

143 return false;

144 return true;

145}

146

147

148

149

150template

151class TBAANodeImpl {

152 MDNodeTy *Node = nullptr;

153

154public:

155 TBAANodeImpl() = default;

156 explicit TBAANodeImpl(MDNodeTy *N) : Node(N) {}

157

158

159 MDNodeTy *getNode() const { return Node; }

160

161

162

163 bool isNewFormat() const { return isNewFormatTypeNode(Node); }

164

165

166 TBAANodeImpl getParent() const {

167 if (isNewFormat())

168 return TBAANodeImpl(cast(Node->getOperand(0)));

169

170 if (Node->getNumOperands() < 2)

171 return TBAANodeImpl();

173 if ()

174 return TBAANodeImpl();

175

176 return TBAANodeImpl(P);

177 }

178

179

180

181

182 bool isTypeImmutable() const {

183 if (Node->getNumOperands() < 3)

184 return false;

186 if (!CI)

187 return false;

189 }

190};

191

192

193

194

195using TBAANode = TBAANodeImpl;

196using MutableTBAANode = TBAANodeImpl;

197

198

199

200

201

202template

203class TBAAStructTagNodeImpl {

204

205 MDNodeTy *Node;

206

207public:

208 explicit TBAAStructTagNodeImpl(MDNodeTy *N) : Node(N) {}

209

210

211 MDNodeTy *getNode() const { return Node; }

212

213

214

215 bool isNewFormat() const {

216 if (Node->getNumOperands() < 4)

217 return false;

219 if (!TBAANodeImpl(AccessType).isNewFormat())

220 return false;

221 return true;

222 }

223

226 }

227

230 }

231

234 }

235

236 uint64_t getSize() const {

237 if (!isNewFormat())

240 }

241

242

243

244

245 bool isTypeImmutable() const {

246 unsigned OpNo = isNewFormat() ? 4 : 3;

247 if (Node->getNumOperands() < OpNo + 1)

248 return false;

250 if (!CI)

251 return false;

253 }

254};

255

256

257

258

259using TBAAStructTagNode = TBAAStructTagNodeImpl;

260using MutableTBAAStructTagNode = TBAAStructTagNodeImpl;

261

262

263

264

265

266class TBAAStructTypeNode {

267

268 const MDNode *Node = nullptr;

269

270public:

271 TBAAStructTypeNode() = default;

272 explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {}

273

274

275 const MDNode *getNode() const { return Node; }

276

277

278

279 bool isNewFormat() const { return isNewFormatTypeNode(Node); }

280

283 }

284

285

287 return Node->getOperand(isNewFormat() ? 2 : 0);

288 }

289

290 unsigned getNumFields() const {

291 unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1;

292 unsigned NumOpsPerField = isNewFormat() ? 3 : 2;

293 return (getNode()->getNumOperands() - FirstFieldOpNo) / NumOpsPerField;

294 }

295

296 TBAAStructTypeNode getFieldType(unsigned FieldIndex) const {

297 unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1;

298 unsigned NumOpsPerField = isNewFormat() ? 3 : 2;

299 unsigned OpIndex = FirstFieldOpNo + FieldIndex * NumOpsPerField;

301 return TBAAStructTypeNode(TypeNode);

302 }

303

304

305

306 TBAAStructTypeNode getField(uint64_t &Offset) const {

307 bool NewFormat = isNewFormat();

309 const unsigned NumOperands = Operands.size();

310

311 if (NewFormat) {

312

313 if (NumOperands < 6)

314 return TBAAStructTypeNode();

315 } else {

316

317 if (NumOperands < 2)

318 return TBAAStructTypeNode();

319

320

321

322 if (NumOperands <= 3) {

323 uint64_t Cur =

324 NumOperands == 2

325 ? 0

329 if ()

330 return TBAAStructTypeNode();

331 return TBAAStructTypeNode(P);

332 }

333 }

334

335

336

337 unsigned FirstFieldOpNo = NewFormat ? 3 : 1;

338 unsigned NumOpsPerField = NewFormat ? 3 : 2;

339 unsigned TheIdx = 0;

340

341 for (unsigned Idx = FirstFieldOpNo; Idx < NumOperands;

342 Idx += NumOpsPerField) {

343 uint64_t Cur =

346 assert(Idx >= FirstFieldOpNo + NumOpsPerField &&

347 "TBAAStructTypeNode::getField should have an offset match!");

348 TheIdx = Idx - NumOpsPerField;

349 break;

350 }

351 }

352

353 if (TheIdx == 0)

354 TheIdx = NumOperands - NumOpsPerField;

355 uint64_t Cur =

359 if ()

360 return TBAAStructTypeNode();

361 return TBAAStructTypeNode(P);

362 }

363};

364

365}

366

367

368

369

375

379 if (!shouldUseTBAA())

381

384

385

387}

388

391 if (!shouldUseTBAA())

393

394 const auto *N = Loc.AATags.TBAA;

395 if ()

397

398

399

400 const auto *ErrnoTBAAMD = M->getNamedMetadata("llvm.errno.tbaa");

401 if (!ErrnoTBAAMD || any_of(ErrnoTBAAMD->operands(), [&](const auto *Node) {

402 return Aliases(N, Node);

403 }))

406}

407

410 bool IgnoreLocals) {

411 if (!shouldUseTBAA())

413

414 const MDNode *M = Loc.AATags.TBAA;

415 if (!M)

417

418

419

420 if (( isStructPathTBAA (M) && TBAANode(M).isTypeImmutable()) ||

421 (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))

423

425}

426

429 if (!shouldUseTBAA())

431

432

433 if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))

434 if (( isStructPathTBAA (M) && TBAANode(M).isTypeImmutable()) ||

435 (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))

437

439}

440

445

449 if (!shouldUseTBAA())

451

452 if (const MDNode *L = Loc.AATags.TBAA)

453 if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))

454 if (!Aliases(L, M))

456

458}

459

463 if (!shouldUseTBAA())

465

468 if (!Aliases(M1, M2))

470

472}

473

477 return false;

479 if (Tag1->getString() == "vtable pointer")

480 return true;

481 }

482 return false;

483 }

484

485

486 TBAAStructTagNode Tag(this);

487 TBAAStructTypeNode AccessType(Tag.getAccessType());

489 if (Id->getString() == "vtable pointer")

490 return true;

491 return false;

492}

493

495 const MDNode **GenericTag = nullptr);

496

498 const MDNode *GenericTag;

500 return const_cast<MDNode*>(GenericTag);

501}

502

504 if ( || )

505 return nullptr;

506

507 if (A == B)

508 return A;

509

511 TBAANode TA(A);

512 while (TA.getNode()) {

513 if (!PathA.insert(TA.getNode()))

515 TA = TA.getParent();

516 }

517

519 TBAANode TB(B);

520 while (TB.getNode()) {

521 if (!PathB.insert(TB.getNode()))

523 TB = TB.getParent();

524 }

525

526 int IA = PathA.size() - 1;

527 int IB = PathB.size() - 1;

528

529 const MDNode *Ret = nullptr;

530 while (IA >= 0 && IB >= 0) {

531 if (PathA[IA] == PathB[IB])

532 Ret = PathA[IA];

533 else

534 break;

535 --IA;

536 --IB;

537 }

538

539 return Ret;

540}

541

545 Result.TBAAStruct = nullptr;

550 return Result;

551}

552

555 Result.TBAA = Result.TBAAStruct = nullptr;

560 return Result;

561}

562

564

565

567 return nullptr;

568

571

572 if (TBAAStructTypeNode(AccessType).isNewFormat()) {

573

574

576 auto *SizeNode =

579 const_cast<MDNode*>(AccessType),

580 OffsetNode, SizeNode};

582 }

583

585 const_cast<MDNode*>(AccessType),

586 OffsetNode};

588}

589

591 TBAAStructTypeNode FieldType) {

592 for (unsigned I = 0, E = BaseType.getNumFields(); I != E; ++I) {

593 TBAAStructTypeNode T = BaseType.getFieldType(I);

594 if (T == FieldType || hasField(T, FieldType))

595 return true;

596 }

597 return false;

598}

599

600

601

602

603

604

605

606

608 TBAAStructTagNode SubobjectTag,

609 const MDNode *CommonType,

610 const MDNode **GenericTag,

611 bool &MayAlias) {

612

613

614 if (BaseTag.getAccessType() == BaseTag.getBaseType() &&

615 BaseTag.getAccessType() == CommonType) {

616 if (GenericTag)

618 MayAlias = true;

619 return true;

620 }

621

622

623

624

625

626

627 bool NewFormat = BaseTag.isNewFormat();

628 TBAAStructTypeNode BaseType(BaseTag.getBaseType());

629 uint64_t OffsetInBase = BaseTag.getOffset();

630

631 for (;;) {

632

633

635 assert(!NewFormat && "Did not see access type in access path!");

636 break;

637 }

638

639 if (BaseType.getNode() == SubobjectTag.getBaseType()) {

640 MayAlias = OffsetInBase == SubobjectTag.getOffset() ||

641 BaseType.getNode() == BaseTag.getAccessType() ||

642 SubobjectTag.getBaseType() == SubobjectTag.getAccessType();

643 if (GenericTag) {

644 *GenericTag =

645 MayAlias ? SubobjectTag.getNode() : createAccessTag(CommonType);

646 }

647 return true;

648 }

649

650

651 if (NewFormat && BaseType.getNode() == BaseTag.getAccessType())

652 break;

653

654

655

657 }

658

659

660

661

662 if (NewFormat) {

663

664 TBAAStructTypeNode FieldType(SubobjectTag.getBaseType());

666 if (GenericTag)

668 MayAlias = true;

669 return true;

670 }

671 }

672

673 return false;

674}

675

676

677

678

680 const MDNode **GenericTag) {

681 if (A == B) {

682 if (GenericTag)

683 *GenericTag = A;

684 return true;

685 }

686

687

688 if ( || ) {

689 if (GenericTag)

690 *GenericTag = nullptr;

691 return true;

692 }

693

694

695

698

699 TBAAStructTagNode TagA(A), TagB(B);

701 TagB.getAccessType());

702

703

704

705 if (!CommonType) {

706 if (GenericTag)

707 *GenericTag = nullptr;

708 return true;

709 }

710

711

712

713 bool MayAlias;

715 CommonType, GenericTag, MayAlias) ||

717 CommonType, GenericTag, MayAlias))

718 return MayAlias;

719

720

721 if (GenericTag)

723 return false;

724}

725

726

727

728bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {

730}

731

732bool TypeBasedAAResult::shouldUseTBAA() const {

733 return EnableTBAA && !UsingTypeSanitizer;

734}

735

737

741

744 false, true)

745

748}

749

751

756

758 Result.reset();

759 return false;

760}

761

765

767

769 return MD;

770

772 return MD;

773

774

775

776

777

778

779

780

781

782 return MD;

783}

784

786

788 return MD;

794

796 continue;

797

801 NewOffset = 0;

803 }

804

805

807 ConstantInt::get(InnerOffset->getType(), NewOffset)));

809 ConstantInt::get(InnerSize->getType(), NewSize)));

811 }

813}

814

816

817 if (Len == 0)

818 return nullptr;

819

820

821

823 return MD;

824

825 TBAAStructTagNode Tag(MD);

826

827

828 if ( Tag .isNewFormat())

829 return MD;

830

831

832 if (Len == -1)

833 return nullptr;

834

835

839

840

841 if (PreviousSize->equalsInt(Len))

842 return MD;

843

844 NextNodes[3] =

847}

848

851 MDNode *M = New.TBAAStruct;

852 if (!New.TBAA && M && M->getNumOperands() >= 3 && M->getOperand(0) &&

857 AccessSize &&

858 M->getOperand(2) && isa(M->getOperand(2)))

860

861 New.TBAAStruct = nullptr;

862 return New;

863}

864

868 if (.typeSizeEqualsStoreSize(AccessTy))

869 return New;

871 if (Size.isScalable())

872 return New;

873

874 return New.adjustForAccess(Size.getKnownMinValue());

875}

876

879 return New.adjustForAccess(AccessSize);

880}

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

static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static const Function * getParent(const Value *V)

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

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

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

This file contains the declarations for the subclasses of Constant, which represent the different fla...

Module.h This file contains the declarations for the Module class.

const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]

static MemAccessTy getAccessType(const TargetTransformInfo &TTI, Instruction *Inst, Value *OperandVal)

Return the type of the memory being accessed.

This file provides utility analysis objects describing memory locations.

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

static enum BaseType getBaseType(const Value *Val)

Return the baseType for Val which states whether Val is exclusively derived from constant/null,...

BaseType

A given derived pointer can have multiple base pointers through phi/selects.

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

static bool matchAccessTags(const MDNode *A, const MDNode *B, const MDNode **GenericTag=nullptr)

matchTags - Return true if the given couple of accesses are allowed to overlap.

Definition TypeBasedAliasAnalysis.cpp:679

static cl::opt< bool > EnableTBAA("enable-tbaa", cl::init(true), cl::Hidden)

static bool isStructPathTBAA(const MDNode *MD)

Check the first operand of the tbaa tag node, if it is a MDNode, we treat it as struct-path aware TBA...

Definition TypeBasedAliasAnalysis.cpp:370

static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag, TBAAStructTagNode SubobjectTag, const MDNode *CommonType, const MDNode **GenericTag, bool &MayAlias)

Return true if for two given accesses, one of the accessed objects may be a subobject of the other.

Definition TypeBasedAliasAnalysis.cpp:607

static bool hasField(TBAAStructTypeNode BaseType, TBAAStructTypeNode FieldType)

Definition TypeBasedAliasAnalysis.cpp:590

static const MDNode * createAccessTag(const MDNode *AccessType)

Definition TypeBasedAliasAnalysis.cpp:563

static const MDNode * getLeastCommonType(const MDNode *A, const MDNode *B)

Definition TypeBasedAliasAnalysis.cpp:503

This is the interface for a metadata-based TBAA.

static unsigned getSize(unsigned Kind)

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

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.

Represent the analysis usage information of a pass.

void setPreservesAll()

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

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

size_t size() const

size - Get the array size.

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

This is the shared class of boolean and integer constants.

uint64_t getZExtValue() const

Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...

bool equalsInt(uint64_t V) const

A helper method that can be used to determine if the constant contained within is equal to a constant...

const APInt & getValue() const

Return the constant as an APInt value reference.

A parsed version of the target data layout string in and methods for querying it.

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

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)

This static method is the primary way of constructing an IntegerType.

static LLVM_ABI MDNode * getMostGenericAliasScope(MDNode *A, MDNode *B)

LLVM_ABI bool isTBAAVtableAccess() const

Check whether MDNode is a vtable access.

Definition TypeBasedAliasAnalysis.cpp:474

static LLVM_ABI MDNode * getMostGenericTBAA(MDNode *A, MDNode *B)

Definition TypeBasedAliasAnalysis.cpp:497

const MDOperand & getOperand(unsigned I) const

static LLVM_ABI MDNode * getMostGenericNoaliasAddrspace(MDNode *A, MDNode *B)

ArrayRef< MDOperand > operands() const

static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)

unsigned getNumOperands() const

Return number of MDNode operands.

LLVM_ABI MDNode(LLVMContext &Context, unsigned ID, StorageType Storage, ArrayRef< Metadata * > Ops1, ArrayRef< Metadata * > Ops2={})

static LLVM_ABI MDNode * intersect(MDNode *A, MDNode *B)

LLVMContext & getContext() const

static MemoryEffectsBase none()

static MemoryEffectsBase unknown()

Representation for a specific memory location.

AAMDNodes AATags

The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...

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

size_type size() const

Determine the number of elements in the SetVector.

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.

A simple AA result that uses TBAA metadata to answer queries.

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

Definition TypeBasedAliasAnalysis.cpp:389

LLVM_ABI AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI, const Instruction *CtxI)

Definition TypeBasedAliasAnalysis.cpp:376

LLVM_ABI ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool IgnoreLocals)

Definition TypeBasedAliasAnalysis.cpp:408

LLVM_ABI ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)

Definition TypeBasedAliasAnalysis.cpp:446

LLVM_ABI MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI)

Definition TypeBasedAliasAnalysis.cpp:427

Legacy wrapper pass to provide the TypeBasedAAResult object.

bool doFinalization(Module &M) override

doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...

Definition TypeBasedAliasAnalysis.cpp:757

TypeBasedAAWrapperPass()

Definition TypeBasedAliasAnalysis.cpp:750

bool doInitialization(Module &M) override

doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...

Definition TypeBasedAliasAnalysis.cpp:752

void getAnalysisUsage(AnalysisUsage &AU) const override

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

Definition TypeBasedAliasAnalysis.cpp:762

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

Definition TypeBasedAliasAnalysis.cpp:738

The instances of the Type class are immutable: once they are created, they are never changed.

Type * getType() const

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

initializer< Ty > init(const Ty &Val)

std::enable_if_t< detail::IsValidPointer< X, Y >::value, bool > hasa(Y &&MD)

Check whether Metadata has a Value.

std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > dyn_extract(Y &&MD)

Extract a Value from Metadata, if any.

std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > extract(Y &&MD)

Extract a Value from Metadata.

This is an optimization pass for GlobalISel generic memory operations.

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

decltype(auto) dyn_cast(const From &Val)

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

MemoryEffectsBase< IRMemLocation > MemoryEffects

Summary of how a function affects memory in the program.

bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)

unsigned M1(unsigned Val)

auto dyn_cast_or_null(const Y &Val)

static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)

bool any_of(R &&range, UnaryPredicate P)

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

LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)

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.

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

@ Sub

Subtraction of integers.

LLVM_ABI ImmutablePass * createTypeBasedAAWrapperPass()

ArrayRef(const T &OneElt) -> ArrayRef< T >

decltype(auto) cast(const From &Val)

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI AAMDNodes concat(const AAMDNodes &Other) const

Determine the best AAMDNodes after concatenating two different locations together.

Definition TypeBasedAliasAnalysis.cpp:553

static LLVM_ABI MDNode * shiftTBAAStruct(MDNode *M, size_t off)

Definition TypeBasedAliasAnalysis.cpp:785

MDNode * NoAliasAddrSpace

The tag specifying the noalias address spaces.

MDNode * Scope

The tag for alias scope specification (used with noalias).

static LLVM_ABI MDNode * extendToTBAA(MDNode *TBAA, ssize_t len)

Definition TypeBasedAliasAnalysis.cpp:815

MDNode * TBAA

The tag for type-based alias analysis.

AAMDNodes shift(size_t Offset) const

Create a new AAMDNode that describes this AAMDNode after applying a constant offset to the start of t...

LLVM_ABI AAMDNodes merge(const AAMDNodes &Other) const

Given two sets of AAMDNodes applying to potentially different locations, determine the best AAMDNodes...

Definition TypeBasedAliasAnalysis.cpp:542

MDNode * NoAlias

The tag specifying the noalias scope.

LLVM_ABI AAMDNodes adjustForAccess(unsigned AccessSize)

Create a new AAMDNode for accessing AccessSize bytes of this AAMDNode.

Definition TypeBasedAliasAnalysis.cpp:849

static LLVM_ABI MDNode * shiftTBAA(MDNode *M, size_t off)

Definition TypeBasedAliasAnalysis.cpp:766

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