Movatterモバイル変換

Go to the documentation of this file.

1//===- TypeBasedAliasAnalysis.cpp - Type-Based Alias Analysis -------------===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

8//

9// This file defines the TypeBasedAliasAnalysis pass, which implements

10// metadata-based TBAA.

11//

12// In LLVM IR, memory does not have types, so LLVM's own type system is not

13// suitable for doing TBAA. Instead, metadata is added to the IR to describe

14// a type system of a higher level language. This can be used to implement

15// typical C/C++ TBAA, but it can also be used to implement custom alias

16// analysis behavior for other languages.

17//

18// We now support two types of metadata format: scalar TBAA and struct-path

19// aware TBAA. After all testing cases are upgraded to use struct-path aware

20// TBAA and we can auto-upgrade existing bc files, the support for scalar TBAA

21// can be dropped.

22//

23// The scalar TBAA metadata format is very simple. TBAA MDNodes have up to

24// three fields, e.g.:

25// !0 = !{ !"an example type tree" }

26// !1 = !{ !"int", !0 }

27// !2 = !{ !"float", !0 }

28// !3 = !{ !"const float", !2, i64 1 }

29//

30// The first field is an identity field. It can be any value, usually

31// an MDString, which uniquely identifies the type. The most important

32// name in the tree is the name of the root node. Two trees with

33// different root node names are entirely disjoint, even if they

34// have leaves with common names.

35//

36// The second field identifies the type's parent node in the tree, or

37// is null or omitted for a root node. A type is considered to alias

38// all of its descendants and all of its ancestors in the tree. Also,

39// a type is considered to alias all types in other trees, so that

40// bitcode produced from multiple front-ends is handled conservatively.

41//

42// If the third field is present, it's an integer which if equal to 1

43// indicates that the type is "constant" (meaning pointsToConstantMemory

44// should return true; see

45// http://llvm.org/docs/AliasAnalysis.html#OtherItfs).

46//

47// With struct-path aware TBAA, the MDNodes attached to an instruction using

48// "!tbaa" are called path tag nodes.

49//

50// The path tag node has 4 fields with the last field being optional.

51//

52// The first field is the base type node, it can be a struct type node

53// or a scalar type node. The second field is the access type node, it

54// must be a scalar type node. The third field is the offset into the base type.

55// The last field has the same meaning as the last field of our scalar TBAA:

56// it's an integer which if equal to 1 indicates that the access is "constant".

57//

58// The struct type node has a name and a list of pairs, one pair for each member

59// of the struct. The first element of each pair is a type node (a struct type

60// node or a scalar type node), specifying the type of the member, the second

61// element of each pair is the offset of the member.

62//

63// Given an example

64// typedef struct {

65// short s;

66// } A;

67// typedef struct {

68// uint16_t s;

69// A a;

70// } B;

71//

72// For an access to B.a.s, we attach !5 (a path tag node) to the load/store

73// instruction. The base type is !4 (struct B), the access type is !2 (scalar

74// type short) and the offset is 4.

75//

76// !0 = !{!"Simple C/C++ TBAA"}

77// !1 = !{!"omnipotent char", !0} // Scalar type node

78// !2 = !{!"short", !1} // Scalar type node

79// !3 = !{!"A", !2, i64 0} // Struct type node

80// !4 = !{!"B", !2, i64 0, !3, i64 4}

81// // Struct type node

82// !5 = !{!4, !2, i64 4} // Path tag node

83//

84// The struct type nodes and the scalar type nodes form a type DAG.

85// Root (!0)

86// char (!1) -- edge to Root

87// short (!2) -- edge to char

88// A (!3) -- edge with offset 0 to short

89// B (!4) -- edge with offset 0 to short and edge with offset 4 to A

90//

91// To check if two tags (tagX and tagY) can alias, we start from the base type

92// of tagX, follow the edge with the correct offset in the type DAG and adjust

93// the offset until we reach the base type of tagY or until we reach the Root

94// node.

95// If we reach the base type of tagY, compare the adjusted offset with

96// offset of tagY, return Alias if the offsets are the same, return NoAlias

97// otherwise.

98// If we reach the Root node, perform the above starting from base type of tagY

99// to see if we reach base type of tagX.

100//

101// If they have different roots, they're part of different potentially

102// unrelated type systems, so we return Alias to be conservative.

103// If neither node is an ancestor of the other and they have the same root,

104// then we say NoAlias.

105//

106//===----------------------------------------------------------------------===//

107

108#include "llvm/Analysis/TypeBasedAliasAnalysis.h"

109#include "llvm/ADT/SetVector.h"

110#include "llvm/Analysis/AliasAnalysis.h"

111#include "llvm/Analysis/MemoryLocation.h"

112#include "llvm/IR/Constants.h"

113#include "llvm/IR/DataLayout.h"

114#include "llvm/IR/DerivedTypes.h"

115#include "llvm/IR/InstrTypes.h"

116#include "llvm/IR/LLVMContext.h"

117#include "llvm/IR/Metadata.h"

118#include "llvm/InitializePasses.h"

119#include "llvm/Pass.h"

120#include "llvm/Support/Casting.h"

121#include "llvm/Support/CommandLine.h"

122#include "llvm/Support/ErrorHandling.h"

123#include <cassert>

124#include <cstdint>

125

126using namespacellvm;

127

128// A handy option for disabling TBAA functionality. The same effect can also be

129// achieved by stripping the !tbaa tags from IR, but this option is sometimes

130// more convenient.

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

132

133namespace{

134

135/// isNewFormatTypeNode - Return true iff the given type node is in the new

136/// size-aware format.

137staticbool isNewFormatTypeNode(constMDNode *N) {

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

139returnfalse;

140// In the old format the first operand is a string.

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

142returnfalse;

143returntrue;

144}

145

146/// This is a simple wrapper around an MDNode which provides a higher-level

147/// interface by hiding the details of how alias analysis information is encoded

148/// in its operands.

149template<typename MDNodeTy>

150classTBAANodeImpl {

151 MDNodeTy *Node =nullptr;

152

153public:

154 TBAANodeImpl() =default;

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

156

157 /// getNode - Get the MDNode for this TBAANode.

158 MDNodeTy *getNode() const{returnNode; }

159

160 /// isNewFormat - Return true iff the wrapped type node is in the new

161 /// size-aware format.

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

163

164 /// getParent - Get this TBAANode's Alias tree parent.

165 TBAANodeImpl<MDNodeTy>getParent() const{

166if (isNewFormat())

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

168

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

170return TBAANodeImpl<MDNodeTy>();

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

172if (!P)

173return TBAANodeImpl<MDNodeTy>();

174// Ok, this node has a valid parent. Return it.

175return TBAANodeImpl<MDNodeTy>(P);

176 }

177

178 /// Test if this TBAANode represents a type for objects which are

179 /// not modified (by any means) in the context where this

180 /// AliasAnalysis is relevant.

181bool isTypeImmutable() const{

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

183returnfalse;

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

185if (!CI)

186returnfalse;

187return CI->getValue()[0];

188 }

189};

190

191/// \name Specializations of \c TBAANodeImpl for const and non const qualified

192/// \c MDNode.

193/// @{

194usingTBAANode = TBAANodeImpl<const MDNode>;

195usingMutableTBAANode = TBAANodeImpl<MDNode>;

196/// @}

197

198/// This is a simple wrapper around an MDNode which provides a

199/// higher-level interface by hiding the details of how alias analysis

200/// information is encoded in its operands.

201template<typename MDNodeTy>

202classTBAAStructTagNodeImpl {

203 /// This node should be created with createTBAAAccessTag().

204 MDNodeTy *Node;

205

206public:

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

208

209 /// Get the MDNode for this TBAAStructTagNode.

210 MDNodeTy *getNode() const{returnNode; }

211

212 /// isNewFormat - Return true iff the wrapped access tag is in the new

213 /// size-aware format.

214bool isNewFormat() const{

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

216returnfalse;

217if (MDNodeTy *AccessType =getAccessType())

218if (!TBAANodeImpl<MDNodeTy>(AccessType).isNewFormat())

219returnfalse;

220returntrue;

221 }

222

223 MDNodeTy *getBaseType() const{

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

225 }

226

227 MDNodeTy *getAccessType() const{

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

229 }

230

231uint64_t getOffset() const{

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

233 }

234

235uint64_t getSize() const{

236if (!isNewFormat())

237returnUINT64_MAX;

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

239 }

240

241 /// Test if this TBAAStructTagNode represents a type for objects

242 /// which are not modified (by any means) in the context where this

243 /// AliasAnalysis is relevant.

244bool isTypeImmutable() const{

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

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

247returnfalse;

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

249if (!CI)

250returnfalse;

251return CI->getValue()[0];

252 }

253};

254

255/// \name Specializations of \c TBAAStructTagNodeImpl for const and non const

256/// qualified \c MDNods.

257/// @{

258usingTBAAStructTagNode = TBAAStructTagNodeImpl<const MDNode>;

259usingMutableTBAAStructTagNode = TBAAStructTagNodeImpl<MDNode>;

260/// @}

261

262/// This is a simple wrapper around an MDNode which provides a

263/// higher-level interface by hiding the details of how alias analysis

264/// information is encoded in its operands.

265classTBAAStructTypeNode {

266 /// This node should be created with createTBAATypeNode().

267constMDNode *Node =nullptr;

268

269public:

270 TBAAStructTypeNode() =default;

271explicit TBAAStructTypeNode(constMDNode *N) :Node(N) {}

272

273 /// Get the MDNode for this TBAAStructTypeNode.

274constMDNode *getNode() const{returnNode; }

275

276 /// isNewFormat - Return true iff the wrapped type node is in the new

277 /// size-aware format.

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

279

280booloperator==(const TBAAStructTypeNode &Other) const{

281returngetNode() ==Other.getNode();

282 }

283

284 /// getId - Return type identifier.

285Metadata *getId() const{

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

287 }

288

289unsigned getNumFields() const{

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

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

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

293 }

294

295 TBAAStructTypeNode getFieldType(unsigned FieldIndex) const{

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

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

298unsignedOpIndex = FirstFieldOpNo + FieldIndex * NumOpsPerField;

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

300return TBAAStructTypeNode(TypeNode);

301 }

302

303 /// Get this TBAAStructTypeNode's field in the type DAG with

304 /// given offset. Update the offset to be relative to the field type.

305 TBAAStructTypeNode getField(uint64_t &Offset) const{

306bool NewFormat = isNewFormat();

307constArrayRef<MDOperand>Operands =Node->operands();

308constunsigned NumOperands =Operands.size();

309

310if (NewFormat) {

311// New-format root and scalar type nodes have no fields.

312if (NumOperands < 6)

313return TBAAStructTypeNode();

314 }else {

315// Parent can be omitted for the root node.

316if (NumOperands < 2)

317return TBAAStructTypeNode();

318

319// Fast path for a scalar type node and a struct type node with a single

320// field.

321if (NumOperands <= 3) {

322uint64_t Cur =

323 NumOperands == 2

324 ? 0

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

326Offset -= Cur;

327MDNode *P = dyn_cast_or_null<MDNode>(Operands[1]);

328if (!P)

329return TBAAStructTypeNode();

330return TBAAStructTypeNode(P);

331 }

332 }

333

334// Assume the offsets are in order. We return the previous field if

335// the current offset is bigger than the given offset.

336unsigned FirstFieldOpNo = NewFormat ? 3 : 1;

337unsigned NumOpsPerField = NewFormat ? 3 : 2;

338unsigned TheIdx = 0;

339

340for (unsignedIdx = FirstFieldOpNo;Idx < NumOperands;

341Idx += NumOpsPerField) {

342uint64_t Cur =

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

344if (Cur >Offset) {

345assert(Idx >= FirstFieldOpNo + NumOpsPerField &&

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

347 TheIdx =Idx - NumOpsPerField;

348break;

349 }

350 }

351// Move along the last field.

352if (TheIdx == 0)

353 TheIdx = NumOperands - NumOpsPerField;

354uint64_t Cur =

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

356Offset -= Cur;

357MDNode *P = dyn_cast_or_null<MDNode>(Operands[TheIdx]);

358if (!P)

359return TBAAStructTypeNode();

360return TBAAStructTypeNode(P);

361 }

362};

363

364}// end anonymous namespace

365

366/// Check the first operand of the tbaa tag node, if it is a MDNode, we treat

367/// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA

368/// format.

369staticboolisStructPathTBAA(constMDNode *MD) {

370// Anonymous TBAA root starts with a MDNode and dragonegg uses it as

371// a TBAA tag.

372return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;

373}

374

375AliasResult TypeBasedAAResult::alias(constMemoryLocation &LocA,

376constMemoryLocation &LocB,

377AAQueryInfo &AAQI,constInstruction *) {

378if (!shouldUseTBAA())

379returnAliasResult::MayAlias;

380

381if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA))

382returnAliasResult::MayAlias;

383

384// Otherwise return a definitive result.

385returnAliasResult::NoAlias;

386}

387

388ModRefInfo TypeBasedAAResult::getModRefInfoMask(constMemoryLocation &Loc,

389AAQueryInfo &AAQI,

390bool IgnoreLocals) {

391if (!shouldUseTBAA())

392returnModRefInfo::ModRef;

393

394constMDNode *M = Loc.AATags.TBAA;

395if (!M)

396returnModRefInfo::ModRef;

397

398// If this is an "immutable" type, we can assume the pointer is pointing

399// to constant memory.

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

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

402returnModRefInfo::NoModRef;

403

404returnModRefInfo::ModRef;

405}

406

407MemoryEffects TypeBasedAAResult::getMemoryEffects(constCallBase *Call,

408AAQueryInfo &AAQI) {

409if (!shouldUseTBAA())

410returnMemoryEffects::unknown();

411

412// If this is an "immutable" type, the access is not observable.

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

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

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

416returnMemoryEffects::none();

417

418returnMemoryEffects::unknown();

419}

420

421MemoryEffects TypeBasedAAResult::getMemoryEffects(constFunction *F) {

422// Functions don't have metadata.

423returnMemoryEffects::unknown();

424}

425

426ModRefInfo TypeBasedAAResult::getModRefInfo(constCallBase *Call,

427constMemoryLocation &Loc,

428AAQueryInfo &AAQI) {

429if (!shouldUseTBAA())

430returnModRefInfo::ModRef;

431

432if (constMDNode *L = Loc.AATags.TBAA)

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

434if (!Aliases(L, M))

435returnModRefInfo::NoModRef;

436

437returnModRefInfo::ModRef;

438}

439

440ModRefInfo TypeBasedAAResult::getModRefInfo(constCallBase *Call1,

441constCallBase *Call2,

442AAQueryInfo &AAQI) {

443if (!shouldUseTBAA())

444returnModRefInfo::ModRef;

445

446if (constMDNode *M1 = Call1->getMetadata(LLVMContext::MD_tbaa))

447if (constMDNode *M2 = Call2->getMetadata(LLVMContext::MD_tbaa))

448if (!Aliases(M1, M2))

449returnModRefInfo::NoModRef;

450

451returnModRefInfo::ModRef;

452}

453

454boolMDNode::isTBAAVtableAccess() const{

455if (!isStructPathTBAA(this)) {

456if (getNumOperands() < 1)

457returnfalse;

458if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) {

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

460returntrue;

461 }

462returnfalse;

463 }

464

465// For struct-path aware TBAA, we use the access type of the tag.

466 TBAAStructTagNodeTag(this);

467 TBAAStructTypeNode AccessType(Tag.getAccessType());

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

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

470returntrue;

471returnfalse;

472}

473

474staticboolmatchAccessTags(constMDNode *A,constMDNode *B,

475constMDNode **GenericTag =nullptr);

476

477MDNode *MDNode::getMostGenericTBAA(MDNode *A,MDNode *B) {

478constMDNode *GenericTag;

479matchAccessTags(A,B, &GenericTag);

480returnconst_cast<MDNode*>(GenericTag);

481}

482

483staticconstMDNode *getLeastCommonType(constMDNode *A,constMDNode *B) {

484if (!A || !B)

485returnnullptr;

486

487if (A ==B)

488returnA;

489

490SmallSetVector<const MDNode *, 4> PathA;

491 TBAANode TA(A);

492while (TA.getNode()) {

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

494report_fatal_error("Cycle found in TBAA metadata.");

495 TA = TA.getParent();

496 }

497

498SmallSetVector<const MDNode *, 4> PathB;

499 TBAANode TB(B);

500while (TB.getNode()) {

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

502report_fatal_error("Cycle found in TBAA metadata.");

503 TB = TB.getParent();

504 }

505

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

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

508

509constMDNode *Ret =nullptr;

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

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

512 Ret = PathA[IA];

513else

514break;

515 --IA;

516 --IB;

517 }

518

519return Ret;

520}

521

522AAMDNodes AAMDNodes::merge(constAAMDNodes &Other) const{

523AAMDNodes Result;

524 Result.TBAA =MDNode::getMostGenericTBAA(TBAA,Other.TBAA);

525 Result.TBAAStruct =nullptr;

526 Result.Scope =MDNode::getMostGenericAliasScope(Scope,Other.Scope);

527 Result.NoAlias =MDNode::intersect(NoAlias,Other.NoAlias);

528return Result;

529}

530

531AAMDNodes AAMDNodes::concat(constAAMDNodes &Other) const{

532AAMDNodes Result;

533 Result.TBAA = Result.TBAAStruct =nullptr;

534 Result.Scope =MDNode::getMostGenericAliasScope(Scope,Other.Scope);

535 Result.NoAlias =MDNode::intersect(NoAlias,Other.NoAlias);

536return Result;

537}

538

539staticconstMDNode *createAccessTag(constMDNode *AccessType) {

540// If there is no access type or the access type is the root node, then

541// we don't have any useful access tag to return.

542if (!AccessType || AccessType->getNumOperands() < 2)

543returnnullptr;

544

545Type *Int64 =IntegerType::get(AccessType->getContext(), 64);

546auto *OffsetNode =ConstantAsMetadata::get(ConstantInt::get(Int64, 0));

547

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

549// TODO: Take access ranges into account when matching access tags and

550// fix this code to generate actual access sizes for generic tags.

551uint64_t AccessSize =UINT64_MAX;

552auto *SizeNode =

553ConstantAsMetadata::get(ConstantInt::get(Int64, AccessSize));

554Metadata *Ops[] = {const_cast<MDNode*>(AccessType),

555const_cast<MDNode*>(AccessType),

556 OffsetNode, SizeNode};

557returnMDNode::get(AccessType->getContext(), Ops);

558 }

559

560Metadata *Ops[] = {const_cast<MDNode*>(AccessType),

561const_cast<MDNode*>(AccessType),

562 OffsetNode};

563returnMDNode::get(AccessType->getContext(), Ops);

564}

565

566staticboolhasField(TBAAStructTypeNodeBaseType,

567 TBAAStructTypeNode FieldType) {

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

569 TBAAStructTypeNodeT =BaseType.getFieldType(I);

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

571returntrue;

572 }

573returnfalse;

574}

575

576/// Return true if for two given accesses, one of the accessed objects may be a

577/// subobject of the other. The \p BaseTag and \p SubobjectTag parameters

578/// describe the accesses to the base object and the subobject respectively.

579/// \p CommonType must be the metadata node describing the common type of the

580/// accessed objects. On return, \p MayAlias is set to true iff these accesses

581/// may alias and \p Generic, if not null, points to the most generic access

582/// tag for the given two.

583staticboolmayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag,

584 TBAAStructTagNode SubobjectTag,

585constMDNode *CommonType,

586constMDNode **GenericTag,

587bool &MayAlias) {

588// If the base object is of the least common type, then this may be an access

589// to its subobject.

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

591 BaseTag.getAccessType() == CommonType) {

592if (GenericTag)

593 *GenericTag =createAccessTag(CommonType);

594 MayAlias =true;

595returntrue;

596 }

597

598// If the access to the base object is through a field of the subobject's

599// type, then this may be an access to that field. To check for that we start

600// from the base type, follow the edge with the correct offset in the type DAG

601// and adjust the offset until we reach the field type or until we reach the

602// access type.

603bool NewFormat = BaseTag.isNewFormat();

604 TBAAStructTypeNodeBaseType(BaseTag.getBaseType());

605uint64_t OffsetInBase = BaseTag.getOffset();

606

607for (;;) {

608// In the old format there is no distinction between fields and parent

609// types, so in this case we consider all nodes up to the root.

610if (!BaseType.getNode()) {

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

612break;

613 }

614

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

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

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

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

619if (GenericTag) {

620 *GenericTag =

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

622 }

623returntrue;

624 }

625

626// With new-format nodes we stop at the access type.

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

628break;

629

630// Follow the edge with the correct offset. Offset will be adjusted to

631// be relative to the field type.

632BaseType =BaseType.getField(OffsetInBase);

633 }

634

635// If the base object has a direct or indirect field of the subobject's type,

636// then this may be an access to that field. We need this to check now that

637// we support aggregates as access types.

638if (NewFormat) {

639// TBAAStructTypeNode BaseAccessType(BaseTag.getAccessType());

640 TBAAStructTypeNode FieldType(SubobjectTag.getBaseType());

641if (hasField(BaseType, FieldType)) {

642if (GenericTag)

643 *GenericTag =createAccessTag(CommonType);

644 MayAlias =true;

645returntrue;

646 }

647 }

648

649returnfalse;

650}

651

652/// matchTags - Return true if the given couple of accesses are allowed to

653/// overlap. If \arg GenericTag is not null, then on return it points to the

654/// most generic access descriptor for the given two.

655staticboolmatchAccessTags(constMDNode *A,constMDNode *B,

656constMDNode **GenericTag) {

657if (A ==B) {

658if (GenericTag)

659 *GenericTag =A;

660returntrue;

661 }

662

663// Accesses with no TBAA information may alias with any other accesses.

664if (!A || !B) {

665if (GenericTag)

666 *GenericTag =nullptr;

667returntrue;

668 }

669

670// Verify that both input nodes are struct-path aware. Auto-upgrade should

671// have taken care of this.

672assert(isStructPathTBAA(A) &&"Access A is not struct-path aware!");

673assert(isStructPathTBAA(B) &&"Access B is not struct-path aware!");

674

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

676constMDNode *CommonType =getLeastCommonType(TagA.getAccessType(),

677 TagB.getAccessType());

678

679// If the final access types have different roots, they're part of different

680// potentially unrelated type systems, so we must be conservative.

681if (!CommonType) {

682if (GenericTag)

683 *GenericTag =nullptr;

684returntrue;

685 }

686

687// If one of the accessed objects may be a subobject of the other, then such

688// accesses may alias.

689bool MayAlias;

690if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA,/* SubobjectTag= */ TagB,

691 CommonType, GenericTag, MayAlias) ||

692mayBeAccessToSubobjectOf(/* BaseTag= */ TagB,/* SubobjectTag= */ TagA,

693 CommonType, GenericTag, MayAlias))

694return MayAlias;

695

696// Otherwise, we've proved there's no alias.

697if (GenericTag)

698 *GenericTag =createAccessTag(CommonType);

699returnfalse;

700}

701

702/// Aliases - Test whether the access represented by tag A may alias the

703/// access represented by tag B.

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

705returnmatchAccessTags(A,B);

706}

707

708bool TypeBasedAAResult::shouldUseTBAA() const{

709returnEnableTBAA && !UsingTypeSanitizer;

710}

711

712AnalysisKey TypeBasedAA::Key;

713

714TypeBasedAAResult TypeBasedAA::run(Function &F,FunctionAnalysisManager &AM) {

715returnTypeBasedAAResult(F.hasFnAttribute(Attribute::SanitizeType));

716}

717

718charTypeBasedAAWrapperPass::ID = 0;

719INITIALIZE_PASS(TypeBasedAAWrapperPass,"tbaa","Type-Based Alias Analysis",

720false,true)

721

722ImmutablePass *llvm::createTypeBasedAAWrapperPass() {

723returnnewTypeBasedAAWrapperPass();

724}

725

726TypeBasedAAWrapperPass::TypeBasedAAWrapperPass() :ImmutablePass(ID) {

727initializeTypeBasedAAWrapperPassPass(*PassRegistry::getPassRegistry());

728}

729

730boolTypeBasedAAWrapperPass::doInitialization(Module &M) {

731 Result.reset(newTypeBasedAAResult(/*UsingTypeSanitizer=*/false));

732returnfalse;

733}

734

735boolTypeBasedAAWrapperPass::doFinalization(Module &M) {

736 Result.reset();

737returnfalse;

738}

739

740voidTypeBasedAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const{

741 AU.setPreservesAll();

742}

743

744MDNode *AAMDNodes::shiftTBAA(MDNode *MD,size_tOffset) {

745// Fast path if there's no offset

746if (Offset == 0)

747return MD;

748// Fast path if there's no path tbaa node (and thus scalar)

749if (!isStructPathTBAA(MD))

750return MD;

751

752// The correct behavior here is to add the offset into the TBAA

753// struct node offset. The base type, however may not have defined

754// a type at this additional offset, resulting in errors. Since

755// this method is only used within a given load/store access

756// the offset provided is only used to subdivide the previous load

757// maintaining the validity of the previous TBAA.

758//

759// This, however, should be revisited in the future.

760return MD;

761}

762

763MDNode *AAMDNodes::shiftTBAAStruct(MDNode *MD,size_tOffset) {

764// Fast path if there's no offset

765if (Offset == 0)

766return MD;

767SmallVector<Metadata *, 3> Sub;

768for (size_t i = 0,size = MD->getNumOperands(); i <size; i += 3) {

769ConstantInt *InnerOffset = mdconst::extract<ConstantInt>(MD->getOperand(i));

770ConstantInt *InnerSize =

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

772// Don't include any triples that aren't in bounds

773if (InnerOffset->getZExtValue() + InnerSize->getZExtValue() <=Offset)

774continue;

775

776uint64_t NewSize = InnerSize->getZExtValue();

777uint64_t NewOffset = InnerOffset->getZExtValue() -Offset;

778if (InnerOffset->getZExtValue() <Offset) {

779 NewOffset = 0;

780 NewSize -=Offset - InnerOffset->getZExtValue();

781 }

782

783// Shift the offset of the triple

784 Sub.push_back(ConstantAsMetadata::get(

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

786 Sub.push_back(ConstantAsMetadata::get(

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

788 Sub.push_back(MD->getOperand(i + 2));

789 }

790returnMDNode::get(MD->getContext(), Sub);

791}

792

793MDNode *AAMDNodes::extendToTBAA(MDNode *MD, ssize_t Len) {

794// Fast path if 0-length

795if (Len == 0)

796returnnullptr;

797

798// Regular TBAA is invariant of length, so we only need to consider

799// struct-path TBAA.

800if (!isStructPathTBAA(MD))

801return MD;

802

803 TBAAStructTagNodeTag(MD);

804

805// Only new format TBAA has a size

806if (!Tag.isNewFormat())

807return MD;

808

809// If unknown size, drop the TBAA.

810if (Len == -1)

811returnnullptr;

812

813// Otherwise, create TBAA with the new Len

814ArrayRef<MDOperand> MDOperands = MD->operands();

815SmallVector<Metadata *, 4> NextNodes(MDOperands);

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

817

818// Don't create a new MDNode if it is the same length.

819if (PreviousSize->equalsInt(Len))

820return MD;

821

822 NextNodes[3] =

823ConstantAsMetadata::get(ConstantInt::get(PreviousSize->getType(), Len));

824returnMDNode::get(MD->getContext(), NextNodes);

825}

826

827AAMDNodes AAMDNodes::adjustForAccess(unsigned AccessSize) {

828AAMDNodes New = *this;

829MDNode *M = New.TBAAStruct;

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

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

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

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

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

835 AccessSize &&

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

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

838

839 New.TBAAStruct =nullptr;

840return New;

841}

842

843AAMDNodes AAMDNodes::adjustForAccess(size_tOffset,Type *AccessTy,

844constDataLayout &DL) {

845AAMDNodes New =shift(Offset);

846if (!DL.typeSizeEqualsStoreSize(AccessTy))

847return New;

848TypeSize Size =DL.getTypeStoreSize(AccessTy);

849if (Size.isScalable())

850return New;

851

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

853}

854

855AAMDNodes AAMDNodes::adjustForAccess(size_tOffset,unsigned AccessSize) {

856AAMDNodes New =shift(Offset);

857return New.adjustForAccess(AccessSize);

858}

getNode

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

Definition:AMDGPUDelayedMCExpr.cpp:15

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Definition:ARMSLSHardening.cpp:73

AliasAnalysis.h

getParent

static const Function * getParent(const Value *V)

Definition:BasicAliasAnalysis.cpp:863

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

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

Casting.h

CommandLine.h

Constants.h

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

DataLayout.h

Idx

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

Definition:DeadArgumentElimination.cpp:353

DerivedTypes.h

Size

uint64_t Size

Definition:ELFObjHandler.cpp:81

Other

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

Definition:ELFYAML.cpp:1315

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

Return the type of the memory being accessed.

Definition:LoopStrengthReduce.cpp:1029

#define F(x, y, z)

Definition:MD5.cpp:55

#define I(x, y, z)

Definition:MD5.cpp:58

Operands

mir Rename Register Operands

Definition:MIRNamerPass.cpp:74

MemoryLocation.h

This file provides utility analysis objects describing memory locations.

Metadata.h

This file contains the declarations for metadata subclasses.

#define P(N)

INITIALIZE_PASS

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

Definition:PassSupport.h:38

Pass.h

assert

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

OpIndex

unsigned OpIndex

Definition:SPIRVModuleAnalysis.cpp:63

getBaseType

static enum BaseType getBaseType(const Value *Val)

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

Definition:SafepointIRVerifier.cpp:328

SetVector.h

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

Int64

@ Int64

Definition:TargetLibraryInfo.cpp:69

matchAccessTags

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:655

EnableTBAA

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

isStructPathTBAA

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:369

mayBeAccessToSubobjectOf

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:583

hasField

static bool hasField(TBAAStructTypeNode BaseType, TBAAStructTypeNode FieldType)

Definition:TypeBasedAliasAnalysis.cpp:566

createAccessTag

static const MDNode * createAccessTag(const MDNode *AccessType)

Definition:TypeBasedAliasAnalysis.cpp:539

getLeastCommonType

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

Definition:TypeBasedAliasAnalysis.cpp:483

TypeBasedAliasAnalysis.h

This is the interface for a metadata-based TBAA.

getSize

static unsigned getSize(unsigned Kind)

Definition:XtensaAsmBackend.cpp:134

BaseType

Node

Definition:ItaniumDemangle.h:163

llvm::AAQueryInfo

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

Definition:AliasAnalysis.h:238

llvm::AliasResult

The possible results of an alias query.

Definition:AliasAnalysis.h:77

llvm::AliasResult::MayAlias

@ MayAlias

The two locations may or may not alias.

Definition:AliasAnalysis.h:98

llvm::AliasResult::NoAlias

@ NoAlias

The two locations do not alias at all.

Definition:AliasAnalysis.h:95

llvm::AnalysisManager

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

Definition:PassManager.h:253

llvm::AnalysisUsage

Represent the analysis usage information of a pass.

Definition:PassAnalysisSupport.h:47

llvm::AnalysisUsage::setPreservesAll

void setPreservesAll()

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

Definition:PassAnalysisSupport.h:130

llvm::ArrayRef

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

Definition:ArrayRef.h:41

llvm::CallBase

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

Definition:InstrTypes.h:1112

llvm::ConstantAsMetadata::get

static ConstantAsMetadata * get(Constant *C)

Definition:Metadata.h:532

llvm::ConstantInt

This is the shared class of boolean and integer constants.

Definition:Constants.h:83

llvm::ConstantInt::getZExtValue

uint64_t getZExtValue() const

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

Definition:Constants.h:157

llvm::ConstantInt::equalsInt

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

Definition:Constants.h:183

llvm::ConstantInt::getValue

const APInt & getValue() const

Return the constant as an APInt value reference.

Definition:Constants.h:148

llvm::DataLayout

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

Definition:DataLayout.h:63

llvm::Function

Definition:Function.h:63

llvm::ImmutablePass

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

Definition:Pass.h:281

llvm::Instruction

Definition:Instruction.h:68

llvm::Instruction::getMetadata

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

Definition:Instruction.h:426

llvm::IntegerType::get

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

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

Definition:Type.cpp:311

llvm::MDNode

Metadata node.

Definition:Metadata.h:1073

llvm::MDNode::getMostGenericAliasScope

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

Definition:Metadata.cpp:1141

llvm::MDNode::isTBAAVtableAccess

bool isTBAAVtableAccess() const

Check whether MDNode is a vtable access.

Definition:TypeBasedAliasAnalysis.cpp:454

llvm::MDNode::getMostGenericTBAA

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

Definition:TypeBasedAliasAnalysis.cpp:477

llvm::MDNode::getOperand

const MDOperand & getOperand(unsigned I) const

Definition:Metadata.h:1434

llvm::MDNode::operands

ArrayRef< MDOperand > operands() const

Definition:Metadata.h:1432

llvm::MDNode::get

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

Definition:Metadata.h:1549

llvm::MDNode::getNumOperands

unsigned getNumOperands() const

Return number of MDNode operands.

Definition:Metadata.h:1440

llvm::MDNode::intersect

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

Definition:Metadata.cpp:1128

llvm::MDNode::getContext

LLVMContext & getContext() const

Definition:Metadata.h:1237

llvm::MDString

A single uniqued string.

Definition:Metadata.h:724

llvm::MemoryEffectsBase

Definition:ModRef.h:72

llvm::MemoryEffectsBase::none

static MemoryEffectsBase none()

Create MemoryEffectsBase that cannot read or write any memory.

Definition:ModRef.h:117

llvm::MemoryEffectsBase::unknown

static MemoryEffectsBase unknown()

Create MemoryEffectsBase that can read and write any memory.

Definition:ModRef.h:112

llvm::MemoryLocation

Representation for a specific memory location.

Definition:MemoryLocation.h:227

llvm::MemoryLocation::AATags

AAMDNodes AATags

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

Definition:MemoryLocation.h:248

llvm::Metadata

Root of the metadata hierarchy.

Definition:Metadata.h:62

llvm::Module

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

Definition:Module.h:65

llvm::PassRegistry::getPassRegistry

static PassRegistry * getPassRegistry()

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

Definition:PassRegistry.cpp:24

llvm::SetVector::size

size_type size() const

Determine the number of elements in the SetVector.

Definition:SetVector.h:98

llvm::SetVector::insert

bool insert(const value_type &X)

Insert a new element into the SetVector.

Definition:SetVector.h:162

llvm::SmallSetVector

A SetVector that performs no allocations if smaller than a certain size.

Definition:SetVector.h:370

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition:SmallVector.h:413

llvm::SmallVector

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Definition:SmallVector.h:1196

llvm::TypeBasedAAResult

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

Definition:TypeBasedAliasAnalysis.h:31

llvm::TypeBasedAAResult::alias

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

Definition:TypeBasedAliasAnalysis.cpp:375

llvm::TypeBasedAAResult::getModRefInfoMask

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

Definition:TypeBasedAliasAnalysis.cpp:388

llvm::TypeBasedAAResult::getModRefInfo

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

Definition:TypeBasedAliasAnalysis.cpp:426

llvm::TypeBasedAAResult::getMemoryEffects

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

Definition:TypeBasedAliasAnalysis.cpp:407

llvm::TypeBasedAAWrapperPass

Legacy wrapper pass to provide the TypeBasedAAResult object.

Definition:TypeBasedAliasAnalysis.h:82

llvm::TypeBasedAAWrapperPass::doFinalization

bool doFinalization(Module &M) override

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

Definition:TypeBasedAliasAnalysis.cpp:735

llvm::TypeBasedAAWrapperPass::ID

static char ID

Definition:TypeBasedAliasAnalysis.h:86

llvm::TypeBasedAAWrapperPass::TypeBasedAAWrapperPass

TypeBasedAAWrapperPass()

Definition:TypeBasedAliasAnalysis.cpp:726

llvm::TypeBasedAAWrapperPass::doInitialization

bool doInitialization(Module &M) override

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

Definition:TypeBasedAliasAnalysis.cpp:730

llvm::TypeBasedAAWrapperPass::getAnalysisUsage

void getAnalysisUsage(AnalysisUsage &AU) const override

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

Definition:TypeBasedAliasAnalysis.cpp:740

llvm::TypeBasedAA::run

TypeBasedAAResult run(Function &F, FunctionAnalysisManager &AM)

Definition:TypeBasedAliasAnalysis.cpp:714

llvm::TypeSize

Definition:TypeSize.h:334

llvm::Type

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

Definition:Type.h:45

llvm::Value::getType

Type * getType() const

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

Definition:Value.h:255

llvm::cl::opt

Definition:CommandLine.h:1423

uint64_t

unsigned

UINT64_MAX

#define UINT64_MAX

Definition:DataTypes.h:77

ErrorHandling.h

llvm::cl::Hidden

@ Hidden

Definition:CommandLine.h:137

llvm::cl::init

initializer< Ty > init(const Ty &Val)

Definition:CommandLine.h:443

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::Offset

@ Offset

Definition:DWP.cpp:480

llvm::initializeTypeBasedAAWrapperPassPass

void initializeTypeBasedAAWrapperPassPass(PassRegistry &)

llvm::size

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.

Definition:STLExtras.h:1697

llvm::operator==

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

Definition:AddressRanges.h:153

llvm::M1

unsigned M1(unsigned Val)

Definition:VE.h:376

llvm::getOffset

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

Definition:RuntimeDyld.cpp:172

llvm::report_fatal_error