TypeBasedAliasAnalysis.cpp Source File (original) (raw)

100

101

102

103

104

105

106

107

123#include

124#include

125

126using namespace llvm;

127

128

129

130

132

133namespace {

134

135

136

137static bool isNewFormatTypeNode(const MDNode *N) {

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

139 return false;

140

141 if (!isa(N->getOperand(0)))

142 return false;

143 return true;

144}

145

146

147

148

149template

150class TBAANodeImpl {

151 MDNodeTy *Node = nullptr;

152

153public:

154 TBAANodeImpl() = default;

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

156

157

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

159

160

161

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

163

164

165 TBAANodeImpl getParent() const {

166 if (isNewFormat())

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

168

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

170 return TBAANodeImpl();

171 MDNodeTy *P = dyn_cast_or_null(Node->getOperand(1));

172 if ()

173 return TBAANodeImpl();

174

175 return TBAANodeImpl(P);

176 }

177

178

179

180

181 bool isTypeImmutable() const {

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

183 return false;

184 ConstantInt *CI = mdconst::dyn_extract(Node->getOperand(2));

185 if (!CI)

186 return false;

188 }

189};

190

191

192

193

194using TBAANode = TBAANodeImpl;

195using MutableTBAANode = TBAANodeImpl;

196

197

198

199

200

201template

202class TBAAStructTagNodeImpl {

203

204 MDNodeTy *Node;

205

206public:

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

208

209

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

211

212

213

214 bool isNewFormat() const {

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

216 return false;

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

219 return false;

220 return true;

221 }

222

224 return dyn_cast_or_null(Node->getOperand(0));

225 }

226

228 return dyn_cast_or_null(Node->getOperand(1));

229 }

230

232 return mdconst::extract(Node->getOperand(2))->getZExtValue();

233 }

234

236 if (!isNewFormat())

238 return mdconst::extract(Node->getOperand(3))->getZExtValue();

239 }

240

241

242

243

244 bool isTypeImmutable() const {

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

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

247 return false;

248 ConstantInt *CI = mdconst::dyn_extract(Node->getOperand(OpNo));

249 if (!CI)

250 return false;

252 }

253};

254

255

256

257

258using TBAAStructTagNode = TBAAStructTagNodeImpl;

259using MutableTBAAStructTagNode = TBAAStructTagNodeImpl;

260

261

262

263

264

265class TBAAStructTypeNode {

266

268

269public:

270 TBAAStructTypeNode() = default;

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

272

273

275

276

277

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

279

282 }

283

284

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

287 }

288

289 unsigned getNumFields() const {

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

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

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

293 }

294

295 TBAAStructTypeNode getFieldType(unsigned FieldIndex) const {

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

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

298 unsigned OpIndex = FirstFieldOpNo + FieldIndex * NumOpsPerField;

299 auto *TypeNode = cast(getNode()->getOperand(OpIndex));

300 return TBAAStructTypeNode(TypeNode);

301 }

302

303

304

305 TBAAStructTypeNode getField(uint64_t &Offset) const {

306 bool NewFormat = isNewFormat();

308 const unsigned NumOperands = Operands.size();

309

310 if (NewFormat) {

311

312 if (NumOperands < 6)

313 return TBAAStructTypeNode();

314 } else {

315

316 if (NumOperands < 2)

317 return TBAAStructTypeNode();

318

319

320

321 if (NumOperands <= 3) {

323 NumOperands == 2

324 ? 0

325 : mdconst::extract(Operands[2])->getZExtValue();

328 if ()

329 return TBAAStructTypeNode();

330 return TBAAStructTypeNode(P);

331 }

332 }

333

334

335

336 unsigned FirstFieldOpNo = NewFormat ? 3 : 1;

337 unsigned NumOpsPerField = NewFormat ? 3 : 2;

338 unsigned TheIdx = 0;

339

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

341 Idx += NumOpsPerField) {

343 mdconst::extract(Operands[Idx + 1])->getZExtValue();

345 assert(Idx >= FirstFieldOpNo + NumOpsPerField &&

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

347 TheIdx = Idx - NumOpsPerField;

348 break;

349 }

350 }

351

352 if (TheIdx == 0)

353 TheIdx = NumOperands - NumOpsPerField;

355 mdconst::extract(Operands[TheIdx + 1])->getZExtValue();

358 if ()

359 return TBAAStructTypeNode();

360 return TBAAStructTypeNode(P);

361 }

362};

363

364}

365

366

367

368

370

371

373}

374

378 if (!shouldUseTBAA())

380

383

384

386}

387

390 bool IgnoreLocals) {

391 if (!shouldUseTBAA())

393

395 if (!M)

397

398

399

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

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

403

405}

406

409 if (!shouldUseTBAA())

411

412

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

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

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

417

419}

420

422

424}

425

429 if (!shouldUseTBAA())

431

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

434 if (!Aliases(L, M))

436

438}

439

443 if (!shouldUseTBAA())

445

448 if (!Aliases(M1, M2))

450

452}

453

457 return false;

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

460 return true;

461 }

462 return false;

463 }

464

465

466 TBAAStructTagNode Tag(this);

467 TBAAStructTypeNode AccessType(Tag.getAccessType());

468 if(auto *Id = dyn_cast(AccessType.getId()))

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

470 return true;

471 return false;

472}

473

475 const MDNode **GenericTag = nullptr);

476

478 const MDNode *GenericTag;

480 return const_cast<MDNode*>(GenericTag);

481}

482

484 if ( || )

485 return nullptr;

486

487 if (A == B)

488 return A;

489

491 TBAANode TA(A);

492 while (TA.getNode()) {

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

495 TA = TA.getParent();

496 }

497

499 TBAANode TB(B);

500 while (TB.getNode()) {

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

503 TB = TB.getParent();

504 }

505

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

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

508

509 const MDNode *Ret = nullptr;

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

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

512 Ret = PathA[IA];

513 else

514 break;

515 --IA;

516 --IB;

517 }

518

519 return Ret;

520}

521

525 Result.TBAAStruct = nullptr;

528 return Result;

529}

530

533 Result.TBAA = Result.TBAAStruct = nullptr;

536 return Result;

537}

538

540

541

543 return nullptr;

544

547

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

549

550

552 auto *SizeNode =

555 const_cast<MDNode*>(AccessType),

556 OffsetNode, SizeNode};

558 }

559

561 const_cast<MDNode*>(AccessType),

562 OffsetNode};

564}

565

567 TBAAStructTypeNode FieldType) {

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

569 TBAAStructTypeNode T = BaseType.getFieldType(I);

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

571 return true;

572 }

573 return false;

574}

575

576

577

578

579

580

581

582

584 TBAAStructTagNode SubobjectTag,

585 const MDNode *CommonType,

586 const MDNode **GenericTag,

587 bool &MayAlias) {

588

589

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

591 BaseTag.getAccessType() == CommonType) {

592 if (GenericTag)

594 MayAlias = true;

595 return true;

596 }

597

598

599

600

601

602

603 bool NewFormat = BaseTag.isNewFormat();

604 TBAAStructTypeNode BaseType(BaseTag.getBaseType());

605 uint64_t OffsetInBase = BaseTag.getOffset();

606

607 for (;;) {

608

609

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

612 break;

613 }

614

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

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

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

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

619 if (GenericTag) {

620 *GenericTag =

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

622 }

623 return true;

624 }

625

626

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

628 break;

629

630

631

633 }

634

635

636

637

638 if (NewFormat) {

639

640 TBAAStructTypeNode FieldType(SubobjectTag.getBaseType());

642 if (GenericTag)

644 MayAlias = true;

645 return true;

646 }

647 }

648

649 return false;

650}

651

652

653

654

656 const MDNode **GenericTag) {

657 if (A == B) {

658 if (GenericTag)

659 *GenericTag = A;

660 return true;

661 }

662

663

664 if ( || ) {

665 if (GenericTag)

666 *GenericTag = nullptr;

667 return true;

668 }

669

670

671

674

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

677 TagB.getAccessType());

678

679

680

681 if (!CommonType) {

682 if (GenericTag)

683 *GenericTag = nullptr;

684 return true;

685 }

686

687

688

689 bool MayAlias;

691 CommonType, GenericTag, MayAlias) ||

693 CommonType, GenericTag, MayAlias))

694 return MayAlias;

695

696

697 if (GenericTag)

699 return false;

700}

701

702

703

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

706}

707

708bool TypeBasedAAResult::shouldUseTBAA() const {

709 return EnableTBAA && !UsingTypeSanitizer;

710}

711

713

716}

717

720 false, true)

721

724}

725

728}

729

731 Result.reset(new TypeBasedAAResult(false));

732 return false;

733}

734

736 Result.reset();

737 return false;

738}

739

742}

743

745

747 return MD;

748

750 return MD;

751

752

753

754

755

756

757

758

759

760 return MD;

761}

762

764

766 return MD;

771 mdconst::extract(MD->getOperand(i + 1));

772

774 continue;

775

779 NewOffset = 0;

781 }

782

783

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

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

789 }

791}

792

794

795 if (Len == 0)

796 return nullptr;

797

798

799

801 return MD;

802

803 TBAAStructTagNode Tag(MD);

804

805

806 if ( Tag .isNewFormat())

807 return MD;

808

809

810 if (Len == -1)

811 return nullptr;

812

813

816 ConstantInt *PreviousSize = mdconst::extract(NextNodes[3]);

817

818

819 if (PreviousSize->equalsInt(Len))

820 return MD;

821

822 NextNodes[3] =

825}

826

829 MDNode *M = New.TBAAStruct;

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

831 mdconst::hasa(M->getOperand(0)) &&

832 mdconst::extract(M->getOperand(0))->isZero() &&

833 M->getOperand(1) && mdconst::hasa(M->getOperand(1)) &&

834 mdconst::extract(M->getOperand(1))->getValue() ==

835 AccessSize &&

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

837 New.TBAA = cast(M->getOperand(2));

838

839 New.TBAAStruct = nullptr;

840 return New;

841}

842

846 if (.typeSizeEqualsStoreSize(AccessTy))

847 return New;

849 if (Size.isScalable())

850 return New;

851

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

853}

854

857 return New.adjustForAccess(AccessSize);

858}

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< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

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

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

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

std::optional< std::vector< StOtherPiece > > Other

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

Return the type of the memory being accessed.

mir Rename Register Operands

This file provides utility analysis objects describing memory locations.

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

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

static enum BaseType getBaseType(const Value *Val)

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

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.

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

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.

static bool hasField(TBAAStructTypeNode BaseType, TBAAStructTypeNode FieldType)

static const MDNode * createAccessTag(const MDNode *AccessType)

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

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.

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

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

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 IntegerType * get(LLVMContext &C, unsigned NumBits)

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

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

bool isTBAAVtableAccess() const

Check whether MDNode is a vtable access.

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

const MDOperand & getOperand(unsigned I) const

ArrayRef< MDOperand > operands() const

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

unsigned getNumOperands() const

Return number of MDNode operands.

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

LLVMContext & getContext() const

static MemoryEffectsBase none()

Create MemoryEffectsBase that cannot read or write any memory.

static MemoryEffectsBase unknown()

Create MemoryEffectsBase that can read and write any memory.

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.

static PassRegistry * getPassRegistry()

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

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.

void push_back(const T &Elt)

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.

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

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

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

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

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

bool doInitialization(Module &M) override

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

void getAnalysisUsage(AnalysisUsage &AU) const override

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

TypeBasedAAResult run(Function &F, FunctionAnalysisManager &AM)

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)

This is an optimization pass for GlobalISel generic memory operations.

void initializeTypeBasedAAWrapperPassPass(PassRegistry &)

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.

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

unsigned M1(unsigned Val)

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

void report_fatal_error(Error Err, bool gen_crash_diag=true)

Report a serious error, calling any installed error handler.

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.

ImmutablePass * createTypeBasedAAWrapperPass()

A collection of metadata nodes that might be associated with a memory access used by the alias-analys...

AAMDNodes concat(const AAMDNodes &Other) const

Determine the best AAMDNodes after concatenating two different locations together.

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

MDNode * Scope

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

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

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

AAMDNodes merge(const AAMDNodes &Other) const

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

MDNode * NoAlias

The tag specifying the noalias scope.

AAMDNodes adjustForAccess(unsigned AccessSize)

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

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

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