Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp
Line
Count
Source (jump to first uncovered line)
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/DerivedTypes.h"
114
#include "llvm/IR/Instruction.h"
115
#include "llvm/IR/LLVMContext.h"
116
#include "llvm/IR/Metadata.h"
117
#include "llvm/Pass.h"
118
#include "llvm/Support/Casting.h"
119
#include "llvm/Support/CommandLine.h"
120
#include "llvm/Support/ErrorHandling.h"
121
#include <cassert>
122
#include <cstdint>
123
124
using namespace llvm;
125
126
// A handy option for disabling TBAA functionality. The same effect can also be
127
// achieved by stripping the !tbaa tags from IR, but this option is sometimes
128
// more convenient.
129
static cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(true), cl::Hidden);
130
131
namespace {
132
133
/// isNewFormatTypeNode - Return true iff the given type node is in the new
134
/// size-aware format.
135
110M
static bool isNewFormatTypeNode(const MDNode *N) {
136
110M
  if (N->getNumOperands() < 3)
137
38.4M
    return false;
138
72.4M
  // In the old format the first operand is a string.
139
72.4M
  if (!isa<MDNode>(N->getOperand(0)))
140
72.4M
    return false;
141
726
  return true;
142
726
}
143
144
/// This is a simple wrapper around an MDNode which provides a higher-level
145
/// interface by hiding the details of how alias analysis information is encoded
146
/// in its operands.
147
template<typename MDNodeTy>
148
class TBAANodeImpl {
149
  MDNodeTy *Node = nullptr;
150
151
public:
152
18.3M
  TBAANodeImpl() = default;
153
51.0M
  explicit TBAANodeImpl(MDNodeTy *N) : Node(N) {}
154
155
  /// getNode - Get the MDNode for this TBAANode.
156
171M
  MDNodeTy *getNode() const { return Node; }
157
158
  /// isNewFormat - Return true iff the wrapped type node is in the new
159
  /// size-aware format.
160
51.0M
  bool isNewFormat() const { return isNewFormatTypeNode(Node); }
161
162
  /// getParent - Get this TBAANode's Alias tree parent.
163
51.0M
  TBAANodeImpl<MDNodeTy> getParent() const {
164
51.0M
    if (isNewFormat())
165
139
      return TBAANodeImpl(cast<MDNodeTy>(Node->getOperand(0)));
166
51.0M
167
51.0M
    if (Node->getNumOperands() < 2)
168
18.3M
      return TBAANodeImpl<MDNodeTy>();
169
32.7M
    MDNodeTy *P = dyn_cast_or_null<MDNodeTy>(Node->getOperand(1));
170
32.7M
    if (!P)
171
0
      return TBAANodeImpl<MDNodeTy>();
172
32.7M
    // Ok, this node has a valid parent. Return it.
173
32.7M
    return TBAANodeImpl<MDNodeTy>(P);
174
32.7M
  }
175
176
  /// Test if this TBAANode represents a type for objects which are
177
  /// not modified (by any means) in the context where this
178
  /// AliasAnalysis is relevant.
179
0
  bool isTypeImmutable() const {
180
0
    if (Node->getNumOperands() < 3)
181
0
      return false;
182
0
    ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(2));
183
0
    if (!CI)
184
0
      return false;
185
0
    return CI->getValue()[0];
186
0
  }
187
};
188
189
/// \name Specializations of \c TBAANodeImpl for const and non const qualified
190
/// \c MDNode.
191
/// @{
192
using TBAANode = TBAANodeImpl<const MDNode>;
193
using MutableTBAANode = TBAANodeImpl<MDNode>;
194
/// @}
195
196
/// This is a simple wrapper around an MDNode which provides a
197
/// higher-level interface by hiding the details of how alias analysis
198
/// information is encoded in its operands.
199
template<typename MDNodeTy>
200
class TBAAStructTagNodeImpl {
201
  /// This node should be created with createTBAAAccessTag().
202
  MDNodeTy *Node;
203
204
public:
205
34.1M
  explicit TBAAStructTagNodeImpl(MDNodeTy *N) : Node(N) {}
206
207
  /// Get the MDNode for this TBAAStructTagNode.
208
5.14k
  MDNodeTy *getNode() const { return Node; }
209
210
  /// isNewFormat - Return true iff the wrapped access tag is in the new
211
  /// size-aware format.
212
26.9M
  bool isNewFormat() const {
213
26.9M
    if (Node->getNumOperands() < 4)
214
26.9M
      return false;
215
1.08k
    if (MDNodeTy *AccessType = getAccessType())
216
1.08k
      if (!TBAANodeImpl<MDNodeTy>(AccessType).isNewFormat())
217
913
        return false;
218
170
    return true;
219
170
  }
220
221
104M
  MDNodeTy *getBaseType() const {
222
104M
    return dyn_cast_or_null<MDNode>(Node->getOperand(0));
223
104M
  }
224
225
59.7M
  MDNodeTy *getAccessType() const {
226
59.7M
    return dyn_cast_or_null<MDNode>(Node->getOperand(1));
227
59.7M
  }
228
229
22.6M
  uint64_t getOffset() const {
230
22.6M
    return mdconst::extract<ConstantInt>(Node->getOperand(2))->getZExtValue();
231
22.6M
  }
232
233
  uint64_t getSize() const {
234
    if (!isNewFormat())
235
      return UINT64_MAX;
236
    return mdconst::extract<ConstantInt>(Node->getOperand(3))->getZExtValue();
237
  }
238
239
  /// Test if this TBAAStructTagNode represents a type for objects
240
  /// which are not modified (by any means) in the context where this
241
  /// AliasAnalysis is relevant.
242
7.25M
  bool isTypeImmutable() const {
243
7.25M
    unsigned OpNo = isNewFormat() ? 
470
:
37.25M
;
244
7.25M
    if (Node->getNumOperands() < OpNo + 1)
245
7.25M
      return false;
246
895
    ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(OpNo));
247
895
    if (!CI)
248
0
      return false;
249
895
    return CI->getValue()[0];
250
895
  }
251
};
252
253
/// \name Specializations of \c TBAAStructTagNodeImpl for const and non const
254
/// qualified \c MDNods.
255
/// @{
256
using TBAAStructTagNode = TBAAStructTagNodeImpl<const MDNode>;
257
using MutableTBAAStructTagNode = TBAAStructTagNodeImpl<MDNode>;
258
/// @}
259
260
/// This is a simple wrapper around an MDNode which provides a
261
/// higher-level interface by hiding the details of how alias analysis
262
/// information is encoded in its operands.
263
class TBAAStructTypeNode {
264
  /// This node should be created with createTBAATypeNode().
265
  const MDNode *Node = nullptr;
266
267
public:
268
16.7M
  TBAAStructTypeNode() = default;
269
62.6M
  explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {}
270
271
  /// Get the MDNode for this TBAAStructTypeNode.
272
142M
  const MDNode *getNode() const { return Node; }
273
274
  /// isNewFormat - Return true iff the wrapped type node is in the new
275
  /// size-aware format.
276
59.7M
  bool isNewFormat() const { return isNewFormatTypeNode(Node); }
277
278
55
  bool operator==(const TBAAStructTypeNode &Other) const {
279
55
    return getNode() == Other.getNode();
280
55
  }
281
282
  /// getId - Return type identifier.
283
28
  Metadata *getId() const {
284
28
    return Node->getOperand(isNewFormat() ? 
28
:
020
);
285
28
  }
286
287
110
  unsigned getNumFields() const {
288
110
    unsigned FirstFieldOpNo = isNewFormat() ? 3 : 
10
;
289
110
    unsigned NumOpsPerField = isNewFormat() ? 3 : 
20
;
290
110
    return (getNode()->getNumOperands() - FirstFieldOpNo) / NumOpsPerField;
291
110
  }
292
293
55
  TBAAStructTypeNode getFieldType(unsigned FieldIndex) const {
294
55
    unsigned FirstFieldOpNo = isNewFormat() ? 3 : 
10
;
295
55
    unsigned NumOpsPerField = isNewFormat() ? 3 : 
20
;
296
55
    unsigned OpIndex = FirstFieldOpNo + FieldIndex * NumOpsPerField;
297
55
    auto *TypeNode = cast<MDNode>(getNode()->getOperand(OpIndex));
298
55
    return TBAAStructTypeNode(TypeNode);
299
55
  }
300
301
  /// Get this TBAAStructTypeNode's field in the type DAG with
302
  /// given offset. Update the offset to be relative to the field type.
303
59.7M
  TBAAStructTypeNode getField(uint64_t &Offset) const {
304
59.7M
    bool NewFormat = isNewFormat();
305
59.7M
    if (NewFormat) {
306
79
      // New-format root and scalar type nodes have no fields.
307
79
      if (Node->getNumOperands() < 6)
308
0
        return TBAAStructTypeNode();
309
59.7M
    } else {
310
59.7M
      // Parent can be omitted for the root node.
311
59.7M
      if (Node->getNumOperands() < 2)
312
16.7M
        return TBAAStructTypeNode();
313
42.9M
314
42.9M
      // Fast path for a scalar type node and a struct type node with a single
315
42.9M
      // field.
316
42.9M
      if (Node->getNumOperands() <= 3) {
317
33.2M
        uint64_t Cur = Node->getNumOperands() == 2
318
33.2M
                           ? 
01.65M
319
33.2M
                           : mdconst::extract<ConstantInt>(Node->getOperand(2))
320
31.6M
                                 ->getZExtValue();
321
33.2M
        Offset -= Cur;
322
33.2M
        MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1));
323
33.2M
        if (!P)
324
0
          return TBAAStructTypeNode();
325
33.2M
        return TBAAStructTypeNode(P);
326
33.2M
      }
327
42.9M
    }
328
9.64M
329
9.64M
    // Assume the offsets are in order. We return the previous field if
330
9.64M
    // the current offset is bigger than the given offset.
331
9.64M
    unsigned FirstFieldOpNo = NewFormat ? 
379
:
19.64M
;
332
9.64M
    unsigned NumOpsPerField = NewFormat ? 
379
:
29.64M
;
333
9.64M
    unsigned TheIdx = 0;
334
85.2M
    for (unsigned Idx = FirstFieldOpNo; Idx < Node->getNumOperands();
335
84.2M
         
Idx += NumOpsPerField75.5M
) {
336
84.2M
      uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(Idx + 1))
337
84.2M
                         ->getZExtValue();
338
84.2M
      if (Cur > Offset) {
339
8.69M
        assert(Idx >= FirstFieldOpNo + NumOpsPerField &&
340
8.69M
               "TBAAStructTypeNode::getField should have an offset match!");
341
8.69M
        TheIdx = Idx - NumOpsPerField;
342
8.69M
        break;
343
8.69M
      }
344
84.2M
    }
345
9.64M
    // Move along the last field.
346
9.64M
    if (TheIdx == 0)
347
953k
      TheIdx = Node->getNumOperands() - NumOpsPerField;
348
9.64M
    uint64_t Cur = mdconst::extract<ConstantInt>(Node->getOperand(TheIdx + 1))
349
9.64M
                       ->getZExtValue();
350
9.64M
    Offset -= Cur;
351
9.64M
    MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(TheIdx));
352
9.64M
    if (!P)
353
0
      return TBAAStructTypeNode();
354
9.64M
    return TBAAStructTypeNode(P);
355
9.64M
  }
356
};
357
358
} // end anonymous namespace
359
360
/// Check the first operand of the tbaa tag node, if it is a MDNode, we treat
361
/// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA
362
/// format.
363
14.5M
static bool isStructPathTBAA(const MDNode *MD) {
364
14.5M
  // Anonymous TBAA root starts with a MDNode and dragonegg uses it as
365
14.5M
  // a TBAA tag.
366
14.5M
  return isa<MDNode>(MD->getOperand(0)) && MD->getNumOperands() >= 3;
367
14.5M
}
368
369
AliasResult TypeBasedAAResult::alias(const MemoryLocation &LocA,
370
                                     const MemoryLocation &LocB,
371
43.1M
                                     AAQueryInfo &AAQI) {
372
43.1M
  if (!EnableTBAA)
373
0
    return AAResultBase::alias(LocA, LocB, AAQI);
374
43.1M
375
43.1M
  // If accesses may alias, chain to the next AliasAnalysis.
376
43.1M
  if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA))
377
33.9M
    return AAResultBase::alias(LocA, LocB, AAQI);
378
9.23M
379
9.23M
  // Otherwise return a definitive result.
380
9.23M
  return NoAlias;
381
9.23M
}
382
383
bool TypeBasedAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
384
                                               AAQueryInfo &AAQI,
385
37.1M
                                               bool OrLocal) {
386
37.1M
  if (!EnableTBAA)
387
0
    return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
388
37.1M
389
37.1M
  const MDNode *M = Loc.AATags.TBAA;
390
37.1M
  if (!M)
391
29.9M
    return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
392
7.23M
393
7.23M
  // If this is an "immutable" type, we can assume the pointer is pointing
394
7.23M
  // to constant memory.
395
7.23M
  if ((!isStructPathTBAA(M) && 
TBAANode(M).isTypeImmutable()0
) ||
396
7.23M
      
(7.23M
isStructPathTBAA(M)7.23M
&&
TBAAStructTagNode(M).isTypeImmutable()7.23M
))
397
873
    return true;
398
7.23M
399
7.23M
  return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal);
400
7.23M
}
401
402
FunctionModRefBehavior
403
17.4M
TypeBasedAAResult::getModRefBehavior(const CallBase *Call) {
404
17.4M
  if (!EnableTBAA)
405
0
    return AAResultBase::getModRefBehavior(Call);
406
17.4M
407
17.4M
  FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
408
17.4M
409
17.4M
  // If this is an "immutable" type, we can assume the call doesn't write
410
17.4M
  // to memory.
411
17.4M
  if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))
412
21.7k
    if ((!isStructPathTBAA(M) && 
TBAANode(M).isTypeImmutable()0
) ||
413
21.7k
        (isStructPathTBAA(M) && TBAAStructTagNode(M).isTypeImmutable()))
414
2
      Min = FMRB_OnlyReadsMemory;
415
17.4M
416
17.4M
  return FunctionModRefBehavior(AAResultBase::getModRefBehavior(Call) & Min);
417
17.4M
}
418
419
16.9M
FunctionModRefBehavior TypeBasedAAResult::getModRefBehavior(const Function *F) {
420
16.9M
  // Functions don't have metadata. Just chain to the next implementation.
421
16.9M
  return AAResultBase::getModRefBehavior(F);
422
16.9M
}
423
424
ModRefInfo TypeBasedAAResult::getModRefInfo(const CallBase *Call,
425
                                            const MemoryLocation &Loc,
426
7.93M
                                            AAQueryInfo &AAQI) {
427
7.93M
  if (!EnableTBAA)
428
0
    return AAResultBase::getModRefInfo(Call, Loc, AAQI);
429
7.93M
430
7.93M
  if (const MDNode *L = Loc.AATags.TBAA)
431
3.95M
    if (const MDNode *M = Call->getMetadata(LLVMContext::MD_tbaa))
432
18.7k
      if (!Aliases(L, M))
433
13.1k
        return ModRefInfo::NoModRef;
434
7.92M
435
7.92M
  return AAResultBase::getModRefInfo(Call, Loc, AAQI);
436
7.92M
}
437
438
ModRefInfo TypeBasedAAResult::getModRefInfo(const CallBase *Call1,
439
                                            const CallBase *Call2,
440
817k
                                            AAQueryInfo &AAQI) {
441
817k
  if (!EnableTBAA)
442
0
    return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
443
817k
444
817k
  if (const MDNode *M1 = Call1->getMetadata(LLVMContext::MD_tbaa))
445
18
    if (const MDNode *M2 = Call2->getMetadata(LLVMContext::MD_tbaa))
446
18
      if (!Aliases(M1, M2))
447
8
        return ModRefInfo::NoModRef;
448
817k
449
817k
  return AAResultBase::getModRefInfo(Call1, Call2, AAQI);
450
817k
}
451
452
28
bool MDNode::isTBAAVtableAccess() const {
453
28
  if (!isStructPathTBAA(this)) {
454
0
    if (getNumOperands() < 1)
455
0
      return false;
456
0
    if (MDString *Tag1 = dyn_cast<MDString>(getOperand(0))) {
457
0
      if (Tag1->getString() == "vtable pointer")
458
0
        return true;
459
0
    }
460
0
    return false;
461
0
  }
462
28
463
28
  // For struct-path aware TBAA, we use the access type of the tag.
464
28
  TBAAStructTagNode Tag(this);
465
28
  TBAAStructTypeNode AccessType(Tag.getAccessType());
466
28
  if(auto *Id = dyn_cast<MDString>(AccessType.getId()))
467
28
    if (Id->getString() == "vtable pointer")
468
22
      return true;
469
6
  return false;
470
6
}
471
472
static bool matchAccessTags(const MDNode *A, const MDNode *B,
473
                            const MDNode **GenericTag = nullptr);
474
475
114k
MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) {
476
114k
  const MDNode *GenericTag;
477
114k
  matchAccessTags(A, B, &GenericTag);
478
114k
  return const_cast<MDNode*>(GenericTag);
479
114k
}
480
481
13.4M
static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) {
482
13.4M
  if (!A || !B)
483
0
    return nullptr;
484
13.4M
485
13.4M
  if (A == B)
486
4.28M
    return A;
487
9.15M
488
9.15M
  SmallSetVector<const MDNode *, 4> PathA;
489
9.15M
  TBAANode TA(A);
490
34.7M
  while (TA.getNode()) {
491
25.5M
    if (PathA.count(TA.getNode()))
492
0
      report_fatal_error("Cycle found in TBAA metadata.");
493
25.5M
    PathA.insert(TA.getNode());
494
25.5M
    TA = TA.getParent();
495
25.5M
  }
496
9.15M
497
9.15M
  SmallSetVector<const MDNode *, 4> PathB;
498
9.15M
  TBAANode TB(B);
499
34.6M
  while (TB.getNode()) {
500
25.4M
    if (PathB.count(TB.getNode()))
501
0
      report_fatal_error("Cycle found in TBAA metadata.");
502
25.4M
    PathB.insert(TB.getNode());
503
25.4M
    TB = TB.getParent();
504
25.4M
  }
505
9.15M
506
9.15M
  int IA = PathA.size() - 1;
507
9.15M
  int IB = PathB.size() - 1;
508
9.15M
509
9.15M
  const MDNode *Ret = nullptr;
510
26.5M
  while (IA >= 0 && 
IB >= 025.4M
) {
511
24.3M
    if (PathA[IA] == PathB[IB])
512
17.4M
      Ret = PathA[IA];
513
6.90M
    else
514
6.90M
      break;
515
17.4M
    --IA;
516
17.4M
    --IB;
517
17.4M
  }
518
9.15M
519
9.15M
  return Ret;
520
9.15M
}
521
522
48.8M
void Instruction::getAAMetadata(AAMDNodes &N, bool Merge) const {
523
48.8M
  if (Merge)
524
6.19k
    N.TBAA =
525
6.19k
        MDNode::getMostGenericTBAA(N.TBAA, getMetadata(LLVMContext::MD_tbaa));
526
48.8M
  else
527
48.8M
    N.TBAA = getMetadata(LLVMContext::MD_tbaa);
528
48.8M
529
48.8M
  if (Merge)
530
6.19k
    N.Scope = MDNode::getMostGenericAliasScope(
531
6.19k
        N.Scope, getMetadata(LLVMContext::MD_alias_scope));
532
48.8M
  else
533
48.8M
    N.Scope = getMetadata(LLVMContext::MD_alias_scope);
534
48.8M
535
48.8M
  if (Merge)
536
6.19k
    N.NoAlias =
537
6.19k
        MDNode::intersect(N.NoAlias, getMetadata(LLVMContext::MD_noalias));
538
48.8M
  else
539
48.8M
    N.NoAlias = getMetadata(LLVMContext::MD_noalias);
540
48.8M
}
541
542
16.6k
static const MDNode *createAccessTag(const MDNode *AccessType) {
543
16.6k
  // If there is no access type or the access type is the root node, then
544
16.6k
  // we don't have any useful access tag to return.
545
16.6k
  if (!AccessType || AccessType->getNumOperands() < 2)
546
184
    return nullptr;
547
16.4k
548
16.4k
  Type *Int64 = IntegerType::get(AccessType->getContext(), 64);
549
16.4k
  auto *OffsetNode = ConstantAsMetadata::get(ConstantInt::get(Int64, 0));
550
16.4k
551
16.4k
  if (TBAAStructTypeNode(AccessType).isNewFormat()) {
552
0
    // TODO: Take access ranges into account when matching access tags and
553
0
    // fix this code to generate actual access sizes for generic tags.
554
0
    uint64_t AccessSize = UINT64_MAX;
555
0
    auto *SizeNode =
556
0
        ConstantAsMetadata::get(ConstantInt::get(Int64, AccessSize));
557
0
    Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
558
0
                       const_cast<MDNode*>(AccessType),
559
0
                       OffsetNode, SizeNode};
560
0
    return MDNode::get(AccessType->getContext(), Ops);
561
0
  }
562
16.4k
563
16.4k
  Metadata *Ops[] = {const_cast<MDNode*>(AccessType),
564
16.4k
                     const_cast<MDNode*>(AccessType),
565
16.4k
                     OffsetNode};
566
16.4k
  return MDNode::get(AccessType->getContext(), Ops);
567
16.4k
}
568
569
static bool hasField(TBAAStructTypeNode BaseType,
570
110
                     TBAAStructTypeNode FieldType) {
571
133
  for (unsigned I = 0, E = BaseType.getNumFields(); I != E; 
++I23
) {
572
55
    TBAAStructTypeNode T = BaseType.getFieldType(I);
573
55
    if (T == FieldType || 
hasField(T, FieldType)31
)
574
32
      return true;
575
55
  }
576
110
  
return false78
;
577
110
}
578
579
/// Return true if for two given accesses, one of the accessed objects may be a
580
/// subobject of the other. The \p BaseTag and \p SubobjectTag parameters
581
/// describe the accesses to the base object and the subobject respectively.
582
/// \p CommonType must be the metadata node describing the common type of the
583
/// accessed objects. On return, \p MayAlias is set to true iff these accesses
584
/// may alias and \p Generic, if not null, points to the most generic access
585
/// tag for the given two.
586
static bool mayBeAccessToSubobjectOf(TBAAStructTagNode BaseTag,
587
                                     TBAAStructTagNode SubobjectTag,
588
                                     const MDNode *CommonType,
589
                                     const MDNode **GenericTag,
590
21.8M
                                     bool &MayAlias) {
591
21.8M
  // If the base object is of the least common type, then this may be an access
592
21.8M
  // to its subobject.
593
21.8M
  if (BaseTag.getAccessType() == BaseTag.getBaseType() &&
594
21.8M
      
BaseTag.getAccessType() == CommonType11.0M
) {
595
2.09M
    if (GenericTag)
596
1.57k
      *GenericTag = createAccessTag(CommonType);
597
2.09M
    MayAlias = true;
598
2.09M
    return true;
599
2.09M
  }
600
19.7M
601
19.7M
  // If the access to the base object is through a field of the subobject's
602
19.7M
  // type, then this may be an access to that field. To check for that we start
603
19.7M
  // from the base type, follow the edge with the correct offset in the type DAG
604
19.7M
  // and adjust the offset until we reach the field type or until we reach the
605
19.7M
  // access type.
606
19.7M
  bool NewFormat = BaseTag.isNewFormat();
607
19.7M
  TBAAStructTypeNode BaseType(BaseTag.getBaseType());
608
19.7M
  uint64_t OffsetInBase = BaseTag.getOffset();
609
19.7M
610
79.4M
  for (;;) {
611
79.4M
    // In the old format there is no distinction between fields and parent
612
79.4M
    // types, so in this case we consider all nodes up to the root.
613
79.4M
    if (!BaseType.getNode()) {
614
16.7M
      assert(!NewFormat && "Did not see access type in access path!");
615
16.7M
      break;
616
16.7M
    }
617
62.6M
618
62.6M
    if (BaseType.getNode() == SubobjectTag.getBaseType()) {
619
2.96M
      bool SameMemberAccess = OffsetInBase == SubobjectTag.getOffset();
620
2.96M
      if (GenericTag) {
621
18.2k
        *GenericTag = SameMemberAccess ? 
SubobjectTag.getNode()5.14k
:
622
18.2k
                                         
createAccessTag(CommonType)13.0k
;
623
18.2k
      }
624
2.96M
      MayAlias = SameMemberAccess;
625
2.96M
      return true;
626
2.96M
    }
627
59.7M
628
59.7M
    // With new-format nodes we stop at the access type.
629
59.7M
    if (NewFormat && 
BaseType.getNode() == BaseTag.getAccessType()158
)
630
79
      break;
631
59.7M
632
59.7M
    // Follow the edge with the correct offset. Offset will be adjusted to
633
59.7M
    // be relative to the field type.
634
59.7M
    BaseType = BaseType.getField(OffsetInBase);
635
59.7M
  }
636
19.7M
637
19.7M
  // If the base object has a direct or indirect field of the subobject's type,
638
19.7M
  // then this may be an access to that field. We need this to check now that
639
19.7M
  // we support aggregates as access types.
640
19.7M
  
if (16.7M
NewFormat16.7M
) {
641
79
    // TBAAStructTypeNode BaseAccessType(BaseTag.getAccessType());
642
79
    TBAAStructTypeNode FieldType(SubobjectTag.getBaseType());
643
79
    if (hasField(BaseType, FieldType)) {
644
24
      if (GenericTag)
645
0
        *GenericTag = createAccessTag(CommonType);
646
24
      MayAlias = true;
647
24
      return true;
648
24
    }
649
16.7M
  }
650
16.7M
651
16.7M
  return false;
652
16.7M
}
653
654
/// matchTags - Return true if the given couple of accesses are allowed to
655
/// overlap. If \arg GenericTag is not null, then on return it points to the
656
/// most generic access descriptor for the given two.
657
static bool matchAccessTags(const MDNode *A, const MDNode *B,
658
43.2M
                            const MDNode **GenericTag) {
659
43.2M
  if (A == B) {
660
20.1M
    if (GenericTag)
661
92.3k
      *GenericTag = A;
662
20.1M
    return true;
663
20.1M
  }
664
23.1M
665
23.1M
  // Accesses with no TBAA information may alias with any other accesses.
666
23.1M
  if (!A || 
!B18.7M
) {
667
9.72M
    if (GenericTag)
668
331
      *GenericTag = nullptr;
669
9.72M
    return true;
670
9.72M
  }
671
13.4M
672
13.4M
  // Verify that both input nodes are struct-path aware.  Auto-upgrade should
673
13.4M
  // have taken care of this.
674
13.4M
  assert(isStructPathTBAA(A) && "Access A is not struct-path aware!");
675
13.4M
  assert(isStructPathTBAA(B) && "Access B is not struct-path aware!");
676
13.4M
677
13.4M
  TBAAStructTagNode TagA(A), TagB(B);
678
13.4M
  const MDNode *CommonType = getLeastCommonType(TagA.getAccessType(),
679
13.4M
                                                TagB.getAccessType());
680
13.4M
681
13.4M
  // If the final access types have different roots, they're part of different
682
13.4M
  // potentially unrelated type systems, so we must be conservative.
683
13.4M
  if (!CommonType) {
684
13
    if (GenericTag)
685
2
      *GenericTag = nullptr;
686
13
    return true;
687
13
  }
688
13.4M
689
13.4M
  // If one of the accessed objects may be a subobject of the other, then such
690
13.4M
  // accesses may alias.
691
13.4M
  bool MayAlias;
692
13.4M
  if (mayBeAccessToSubobjectOf(/* BaseTag= */ TagA, /* SubobjectTag= */ TagB,
693
13.4M
                               CommonType, GenericTag, MayAlias) ||
694
13.4M
      mayBeAccessToSubobjectOf(/* BaseTag= */ TagB, /* SubobjectTag= */ TagA,
695
8.38M
                               CommonType, GenericTag, MayAlias))
696
5.06M
    return MayAlias;
697
8.38M
698
8.38M
  // Otherwise, we've proved there's no alias.
699
8.38M
  if (GenericTag)
700
1.99k
    *GenericTag = createAccessTag(CommonType);
701
8.38M
  return false;
702
8.38M
}
703
704
/// Aliases - Test whether the access represented by tag A may alias the
705
/// access represented by tag B.
706
43.1M
bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {
707
43.1M
  return matchAccessTags(A, B);
708
43.1M
}
709
710
AnalysisKey TypeBasedAA::Key;
711
712
2.59k
TypeBasedAAResult TypeBasedAA::run(Function &F, FunctionAnalysisManager &AM) {
713
2.59k
  return TypeBasedAAResult();
714
2.59k
}
715
716
char TypeBasedAAWrapperPass::ID = 0;
717
INITIALIZE_PASS(TypeBasedAAWrapperPass, "tbaa", "Type-Based Alias Analysis",
718
                false, true)
719
720
62.3k
ImmutablePass *llvm::createTypeBasedAAWrapperPass() {
721
62.3k
  return new TypeBasedAAWrapperPass();
722
62.3k
}
723
724
62.4k
TypeBasedAAWrapperPass::TypeBasedAAWrapperPass() : ImmutablePass(ID) {
725
62.4k
  initializeTypeBasedAAWrapperPassPass(*PassRegistry::getPassRegistry());
726
62.4k
}
727
728
62.2k
bool TypeBasedAAWrapperPass::doInitialization(Module &M) {
729
62.2k
  Result.reset(new TypeBasedAAResult());
730
62.2k
  return false;
731
62.2k
}
732
733
62.0k
bool TypeBasedAAWrapperPass::doFinalization(Module &M) {
734
62.0k
  Result.reset();
735
62.0k
  return false;
736
62.0k
}
737
738
62.2k
void TypeBasedAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
739
62.2k
  AU.setPreservesAll();
740
62.2k
}