Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/lib/CodeGen/CodeGenTBAA.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- CodeGenTBAA.cpp - TBAA information for LLVM CodeGen ---------------===//
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 is the code that manages TBAA information and defines the TBAA policy
10
// for the optimizer to use. Relevant standards text includes:
11
//
12
//   C99 6.5p7
13
//   C++ [basic.lval] (p10 in n3126, p15 in some earlier versions)
14
//
15
//===----------------------------------------------------------------------===//
16
17
#include "CodeGenTBAA.h"
18
#include "clang/AST/ASTContext.h"
19
#include "clang/AST/Attr.h"
20
#include "clang/AST/Mangle.h"
21
#include "clang/AST/RecordLayout.h"
22
#include "clang/Basic/CodeGenOptions.h"
23
#include "llvm/ADT/SmallSet.h"
24
#include "llvm/IR/Constants.h"
25
#include "llvm/IR/LLVMContext.h"
26
#include "llvm/IR/Metadata.h"
27
#include "llvm/IR/Module.h"
28
#include "llvm/IR/Type.h"
29
using namespace clang;
30
using namespace CodeGen;
31
32
CodeGenTBAA::CodeGenTBAA(ASTContext &Ctx, llvm::Module &M,
33
                         const CodeGenOptions &CGO,
34
                         const LangOptions &Features, MangleContext &MContext)
35
  : Context(Ctx), Module(M), CodeGenOpts(CGO),
36
    Features(Features), MContext(MContext), MDHelper(M.getContext()),
37
    Root(nullptr), Char(nullptr)
38
8.46k
{}
39
40
8.46k
CodeGenTBAA::~CodeGenTBAA() {
41
8.46k
}
42
43
24.4k
llvm::MDNode *CodeGenTBAA::getRoot() {
44
24.4k
  // Define the root of the tree. This identifies the tree, so that
45
24.4k
  // if our LLVM IR is linked with LLVM IR from a different front-end
46
24.4k
  // (or a different version of this front-end), their TBAA trees will
47
24.4k
  // remain distinct, and the optimizer will treat them conservatively.
48
24.4k
  if (!Root) {
49
7.17k
    if (Features.CPlusPlus)
50
2.19k
      Root = MDHelper.createTBAARoot("Simple C++ TBAA");
51
4.97k
    else
52
4.97k
      Root = MDHelper.createTBAARoot("Simple C/C++ TBAA");
53
7.17k
  }
54
24.4k
55
24.4k
  return Root;
56
24.4k
}
57
58
llvm::MDNode *CodeGenTBAA::createScalarTypeNode(StringRef Name,
59
                                                llvm::MDNode *Parent,
60
146k
                                                uint64_t Size) {
61
146k
  if (CodeGenOpts.NewStructPathTBAA) {
62
71
    llvm::Metadata *Id = MDHelper.createString(Name);
63
71
    return MDHelper.createTBAATypeNode(Parent, Size, Id);
64
71
  }
65
146k
  return MDHelper.createTBAAScalarTypeNode(Name, Parent);
66
146k
}
67
68
231k
llvm::MDNode *CodeGenTBAA::getChar() {
69
231k
  // Define the root of the tree for user-accessible memory. C and C++
70
231k
  // give special powers to char and certain similar types. However,
71
231k
  // these special powers only cover user-accessible memory, and doesn't
72
231k
  // include things like vtables.
73
231k
  if (!Char)
74
7.17k
    Char = createScalarTypeNode("omnipotent char", getRoot(), /* Size= */ 1);
75
231k
76
231k
  return Char;
77
231k
}
78
79
11.4M
static bool TypeHasMayAlias(QualType QTy) {
80
11.4M
  // Tagged types have declarations, and therefore may have attributes.
81
11.4M
  if (const TagType *TTy = dyn_cast<TagType>(QTy))
82
1.16M
    return TTy->getDecl()->hasAttr<MayAliasAttr>();
83
10.2M
84
10.2M
  // Typedef types have declarations, and therefore may have attributes.
85
10.2M
  if (const TypedefType *TTy = dyn_cast<TypedefType>(QTy)) {
86
2.56M
    if (TTy->getDecl()->hasAttr<MayAliasAttr>())
87
9
      return true;
88
2.56M
    // Also, their underlying types may have relevant attributes.
89
2.56M
    return TypeHasMayAlias(TTy->desugar());
90
2.56M
  }
91
7.67M
92
7.67M
  return false;
93
7.67M
}
94
95
/// Check if the given type is a valid base type to be used in access tags.
96
6.50M
static bool isValidBaseType(QualType QTy) {
97
6.50M
  if (QTy->isReferenceType())
98
207k
    return false;
99
6.30M
  if (const RecordType *TTy = QTy->getAs<RecordType>()) {
100
2.56M
    const RecordDecl *RD = TTy->getDecl()->getDefinition();
101
2.56M
    // Incomplete types are not valid base access types.
102
2.56M
    if (!RD)
103
0
      return false;
104
2.56M
    if (RD->hasFlexibleArrayMember())
105
510
      return false;
106
2.55M
    // RD can be struct, union, class, interface or enum.
107
2.55M
    // For now, we only handle struct and class.
108
2.55M
    if (RD->isStruct() || 
RD->isClass()1.34M
)
109
2.50M
      return true;
110
3.79M
  }
111
3.79M
  return false;
112
3.79M
}
113
114
199k
llvm::MDNode *CodeGenTBAA::getTypeInfoHelper(const Type *Ty) {
115
199k
  uint64_t Size = Context.getTypeSizeInChars(Ty).getQuantity();
116
199k
117
199k
  // Handle builtin types.
118
199k
  if (const BuiltinType *BTy = dyn_cast<BuiltinType>(Ty)) {
119
29.2k
    switch (BTy->getKind()) {
120
29.2k
    // Character types are special and can alias anything.
121
29.2k
    // In C++, this technically only includes "char" and "unsigned char",
122
29.2k
    // and not "signed char". In C, it includes all three. For now,
123
29.2k
    // the risk of exploiting this detail in C++ seems likely to outweigh
124
29.2k
    // the benefit.
125
29.2k
    case BuiltinType::Char_U:
126
2.92k
    case BuiltinType::Char_S:
127
2.92k
    case BuiltinType::UChar:
128
2.92k
    case BuiltinType::SChar:
129
2.92k
      return getChar();
130
2.92k
131
2.92k
    // Unsigned types can alias their corresponding signed types.
132
2.92k
    case BuiltinType::UShort:
133
1.07k
      return getTypeInfo(Context.ShortTy);
134
3.23k
    case BuiltinType::UInt:
135
3.23k
      return getTypeInfo(Context.IntTy);
136
2.92k
    case BuiltinType::ULong:
137
2.16k
      return getTypeInfo(Context.LongTy);
138
2.92k
    case BuiltinType::ULongLong:
139
2.19k
      return getTypeInfo(Context.LongLongTy);
140
2.92k
    case BuiltinType::UInt128:
141
95
      return getTypeInfo(Context.Int128Ty);
142
2.92k
143
2.92k
    // Treat all other builtin types as distinct types. This includes
144
2.92k
    // treating wchar_t, char16_t, and char32_t as distinct from their
145
2.92k
    // "underlying types".
146
17.5k
    default:
147
17.5k
      return createScalarTypeNode(BTy->getName(Features), getChar(), Size);
148
169k
    }
149
169k
  }
150
169k
151
169k
  // C++1z [basic.lval]p10: "If a program attempts to access the stored value of
152
169k
  // an object through a glvalue of other than one of the following types the
153
169k
  // behavior is undefined: [...] a char, unsigned char, or std::byte type."
154
169k
  if (Ty->isStdByteType())
155
1
    return getChar();
156
169k
157
169k
  // Handle pointers and references.
158
169k
  // TODO: Implement C++'s type "similarity" and consider dis-"similar"
159
169k
  // pointers distinct.
160
169k
  if (Ty->isPointerType() || 
Ty->isReferenceType()83.4k
)
161
101k
    return createScalarTypeNode("any pointer", getChar(), Size);
162
68.1k
163
68.1k
  // Accesses to arrays are accesses to objects of their element types.
164
68.1k
  if (CodeGenOpts.NewStructPathTBAA && 
Ty->isArrayType()7
)
165
3
    return getTypeInfo(cast<ArrayType>(Ty)->getElementType());
166
68.1k
167
68.1k
  // Enum types are distinct types. In C++ they have "underlying types",
168
68.1k
  // however they aren't related for TBAA.
169
68.1k
  if (const EnumType *ETy = dyn_cast<EnumType>(Ty)) {
170
3.84k
    // In C++ mode, types have linkage, so we can rely on the ODR and
171
3.84k
    // on their mangled names, if they're external.
172
3.84k
    // TODO: Is there a way to get a program-wide unique name for a
173
3.84k
    // decl with local linkage or no linkage?
174
3.84k
    if (!Features.CPlusPlus || 
!ETy->getDecl()->isExternallyVisible()3.08k
)
175
758
      return getChar();
176
3.08k
177
3.08k
    SmallString<256> OutName;
178
3.08k
    llvm::raw_svector_ostream Out(OutName);
179
3.08k
    MContext.mangleTypeName(QualType(ETy, 0), Out);
180
3.08k
    return createScalarTypeNode(OutName, getChar(), Size);
181
3.08k
  }
182
64.2k
183
64.2k
  // For now, handle any other kind of type conservatively.
184
64.2k
  return getChar();
185
64.2k
}
186
187
4.77M
llvm::MDNode *CodeGenTBAA::getTypeInfo(QualType QTy) {
188
4.77M
  // At -O0 or relaxed aliasing, TBAA is not emitted for regular types.
189
4.77M
  if (CodeGenOpts.OptimizationLevel == 0 || 
CodeGenOpts.RelaxedAliasing4.77M
)
190
113
    return nullptr;
191
4.77M
192
4.77M
  // If the type has the may_alias attribute (even on a typedef), it is
193
4.77M
  // effectively in the general char alias class.
194
4.77M
  if (TypeHasMayAlias(QTy))
195
0
    return getChar();
196
4.77M
197
4.77M
  // We need this function to not fall back to returning the "omnipotent char"
198
4.77M
  // type node for aggregate and union types. Otherwise, any dereference of an
199
4.77M
  // aggregate will result into the may-alias access descriptor, meaning all
200
4.77M
  // subsequent accesses to direct and indirect members of that aggregate will
201
4.77M
  // be considered may-alias too.
202
4.77M
  // TODO: Combine getTypeInfo() and getBaseTypeInfo() into a single function.
203
4.77M
  if (isValidBaseType(QTy))
204
988k
    return getBaseTypeInfo(QTy);
205
3.78M
206
3.78M
  const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
207
3.78M
  if (llvm::MDNode *N = MetadataCache[Ty])
208
3.58M
    return N;
209
199k
210
199k
  // Note that the following helper call is allowed to add new nodes to the
211
199k
  // cache, which invalidates all its previously obtained iterators. So we
212
199k
  // first generate the node for the type and then add that node to the cache.
213
199k
  llvm::MDNode *TypeNode = getTypeInfoHelper(Ty);
214
199k
  return MetadataCache[Ty] = TypeNode;
215
199k
}
216
217
4.02M
TBAAAccessInfo CodeGenTBAA::getAccessInfo(QualType AccessType) {
218
4.02M
  // Pointee values may have incomplete types, but they shall never be
219
4.02M
  // dereferenced.
220
4.02M
  if (AccessType->isIncompleteType())
221
3.88k
    return TBAAAccessInfo::getIncompleteInfo();
222
4.02M
223
4.02M
  if (TypeHasMayAlias(AccessType))
224
9
    return TBAAAccessInfo::getMayAliasInfo();
225
4.02M
226
4.02M
  uint64_t Size = Context.getTypeSizeInChars(AccessType).getQuantity();
227
4.02M
  return TBAAAccessInfo(getTypeInfo(AccessType), Size);
228
4.02M
}
229
230
17.2k
TBAAAccessInfo CodeGenTBAA::getVTablePtrAccessInfo(llvm::Type *VTablePtrType) {
231
17.2k
  llvm::DataLayout DL(&Module);
232
17.2k
  unsigned Size = DL.getPointerTypeSize(VTablePtrType);
233
17.2k
  return TBAAAccessInfo(createScalarTypeNode("vtable pointer", getRoot(), Size),
234
17.2k
                        Size);
235
17.2k
}
236
237
bool
238
CodeGenTBAA::CollectFields(uint64_t BaseOffset,
239
                           QualType QTy,
240
                           SmallVectorImpl<llvm::MDBuilder::TBAAStructField> &
241
                             Fields,
242
45.0k
                           bool MayAlias) {
243
45.0k
  /* Things not handled yet include: C++ base classes, bitfields, */
244
45.0k
245
45.0k
  if (const RecordType *TTy = QTy->getAs<RecordType>()) {
246
16.3k
    const RecordDecl *RD = TTy->getDecl()->getDefinition();
247
16.3k
    if (RD->hasFlexibleArrayMember())
248
0
      return false;
249
16.3k
250
16.3k
    // TODO: Handle C++ base classes.
251
16.3k
    if (const CXXRecordDecl *Decl = dyn_cast<CXXRecordDecl>(RD))
252
14.4k
      if (Decl->bases_begin() != Decl->bases_end())
253
2.42k
        return false;
254
13.9k
255
13.9k
    const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
256
13.9k
257
13.9k
    unsigned idx = 0;
258
13.9k
    for (RecordDecl::field_iterator i = RD->field_begin(),
259
44.8k
         e = RD->field_end(); i != e; 
++i, ++idx30.8k
) {
260
31.0k
      if ((*i)->isZeroSize(Context) || 
(*i)->isUnnamedBitfield()31.0k
)
261
5
        continue;
262
31.0k
      uint64_t Offset = BaseOffset +
263
31.0k
                        Layout.getFieldOffset(idx) / Context.getCharWidth();
264
31.0k
      QualType FieldQTy = i->getType();
265
31.0k
      if (!CollectFields(Offset, FieldQTy, Fields,
266
31.0k
                         MayAlias || TypeHasMayAlias(FieldQTy)))
267
169
        return false;
268
31.0k
    }
269
13.9k
    
return true13.7k
;
270
28.7k
  }
271
28.7k
272
28.7k
  /* Otherwise, treat whatever it is as a field. */
273
28.7k
  uint64_t Offset = BaseOffset;
274
28.7k
  uint64_t Size = Context.getTypeSizeInChars(QTy).getQuantity();
275
28.7k
  llvm::MDNode *TBAAType = MayAlias ? 
getChar()0
: getTypeInfo(QTy);
276
28.7k
  llvm::MDNode *TBAATag = getAccessTagInfo(TBAAAccessInfo(TBAAType, Size));
277
28.7k
  Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size, TBAATag));
278
28.7k
  return true;
279
28.7k
}
280
281
llvm::MDNode *
282
14.0k
CodeGenTBAA::getTBAAStructInfo(QualType QTy) {
283
14.0k
  const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
284
14.0k
285
14.0k
  if (llvm::MDNode *N = StructMetadataCache[Ty])
286
0
    return N;
287
14.0k
288
14.0k
  SmallVector<llvm::MDBuilder::TBAAStructField, 4> Fields;
289
14.0k
  if (CollectFields(0, QTy, Fields, TypeHasMayAlias(QTy)))
290
11.6k
    return MDHelper.createTBAAStructNode(Fields);
291
2.42k
292
2.42k
  // For now, handle any other kind of type conservatively.
293
2.42k
  return StructMetadataCache[Ty] = nullptr;
294
2.42k
}
295
296
52.8k
llvm::MDNode *CodeGenTBAA::getBaseTypeInfoHelper(const Type *Ty) {
297
52.8k
  if (auto *TTy = dyn_cast<RecordType>(Ty)) {
298
52.8k
    const RecordDecl *RD = TTy->getDecl()->getDefinition();
299
52.8k
    const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
300
52.8k
    SmallVector<llvm::MDBuilder::TBAAStructField, 4> Fields;
301
240k
    for (FieldDecl *Field : RD->fields()) {
302
240k
      if (Field->isZeroSize(Context) || 
Field->isUnnamedBitfield()240k
)
303
65
        continue;
304
240k
      QualType FieldQTy = Field->getType();
305
240k
      llvm::MDNode *TypeNode = isValidBaseType(FieldQTy) ?
306
215k
          
getBaseTypeInfo(FieldQTy)25.3k
: getTypeInfo(FieldQTy);
307
240k
      if (!TypeNode)
308
2
        return BaseTypeMetadataCache[Ty] = nullptr;
309
240k
310
240k
      uint64_t BitOffset = Layout.getFieldOffset(Field->getFieldIndex());
311
240k
      uint64_t Offset = Context.toCharUnitsFromBits(BitOffset).getQuantity();
312
240k
      uint64_t Size = Context.getTypeSizeInChars(FieldQTy).getQuantity();
313
240k
      Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size,
314
240k
                                                        TypeNode));
315
240k
    }
316
52.8k
317
52.8k
    SmallString<256> OutName;
318
52.8k
    if (Features.CPlusPlus) {
319
47.1k
      // Don't use the mangler for C code.
320
47.1k
      llvm::raw_svector_ostream Out(OutName);
321
47.1k
      MContext.mangleTypeName(QualType(Ty, 0), Out);
322
47.1k
    } else {
323
5.65k
      OutName = RD->getName();
324
5.65k
    }
325
52.8k
326
52.8k
    if (CodeGenOpts.NewStructPathTBAA) {
327
33
      llvm::MDNode *Parent = getChar();
328
33
      uint64_t Size = Context.getTypeSizeInChars(Ty).getQuantity();
329
33
      llvm::Metadata *Id = MDHelper.createString(OutName);
330
33
      return MDHelper.createTBAATypeNode(Parent, Size, Id, Fields);
331
33
    }
332
52.8k
333
52.8k
    // Create the struct type node with a vector of pairs (offset, type).
334
52.8k
    SmallVector<std::pair<llvm::MDNode*, uint64_t>, 4> OffsetsAndTypes;
335
52.8k
    for (const auto &Field : Fields)
336
240k
        OffsetsAndTypes.push_back(std::make_pair(Field.Type, Field.Offset));
337
52.8k
    return MDHelper.createTBAAStructTypeNode(OutName, OffsetsAndTypes);
338
52.8k
  }
339
0
340
0
  return nullptr;
341
0
}
342
343
1.49M
llvm::MDNode *CodeGenTBAA::getBaseTypeInfo(QualType QTy) {
344
1.49M
  if (!isValidBaseType(QTy))
345
244
    return nullptr;
346
1.49M
347
1.49M
  const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
348
1.49M
  if (llvm::MDNode *N = BaseTypeMetadataCache[Ty])
349
1.44M
    return N;
350
52.8k
351
52.8k
  // Note that the following helper call is allowed to add new nodes to the
352
52.8k
  // cache, which invalidates all its previously obtained iterators. So we
353
52.8k
  // first generate the node for the type and then add that node to the cache.
354
52.8k
  llvm::MDNode *TypeNode = getBaseTypeInfoHelper(Ty);
355
52.8k
  return BaseTypeMetadataCache[Ty] = TypeNode;
356
52.8k
}
357
358
3.21M
llvm::MDNode *CodeGenTBAA::getAccessTagInfo(TBAAAccessInfo Info) {
359
3.21M
  assert(!Info.isIncomplete() && "Access to an object of an incomplete type!");
360
3.21M
361
3.21M
  if (Info.isMayAlias())
362
40.7k
    Info = TBAAAccessInfo(getChar(), Info.Size);
363
3.21M
364
3.21M
  if (!Info.AccessType)
365
97
    return nullptr;
366
3.21M
367
3.21M
  if (!CodeGenOpts.StructPathTBAA)
368
265
    Info = TBAAAccessInfo(Info.AccessType, Info.Size);
369
3.21M
370
3.21M
  llvm::MDNode *&N = AccessTagMetadataCache[Info];
371
3.21M
  if (N)
372
3.11M
    return N;
373
98.4k
374
98.4k
  if (!Info.BaseType) {
375
27.8k
    Info.BaseType = Info.AccessType;
376
27.8k
    assert(!Info.Offset && "Nonzero offset for an access with no base type!");
377
27.8k
  }
378
98.4k
  if (CodeGenOpts.NewStructPathTBAA) {
379
66
    return N = MDHelper.createTBAAAccessTag(Info.BaseType, Info.AccessType,
380
66
                                            Info.Offset, Info.Size);
381
66
  }
382
98.3k
  return N = MDHelper.createTBAAStructTagNode(Info.BaseType, Info.AccessType,
383
98.3k
                                              Info.Offset);
384
98.3k
}
385
386
TBAAAccessInfo CodeGenTBAA::mergeTBAAInfoForCast(TBAAAccessInfo SourceInfo,
387
3.00k
                                                 TBAAAccessInfo TargetInfo) {
388
3.00k
  if (SourceInfo.isMayAlias() || 
TargetInfo.isMayAlias()2.98k
)
389
17
    return TBAAAccessInfo::getMayAliasInfo();
390
2.98k
  return TargetInfo;
391
2.98k
}
392
393
TBAAAccessInfo
394
CodeGenTBAA::mergeTBAAInfoForConditionalOperator(TBAAAccessInfo InfoA,
395
629
                                                 TBAAAccessInfo InfoB) {
396
629
  if (InfoA == InfoB)
397
617
    return InfoA;
398
12
399
12
  if (!InfoA || !InfoB)
400
0
    return TBAAAccessInfo();
401
12
402
12
  if (InfoA.isMayAlias() || 
InfoB.isMayAlias()11
)
403
2
    return TBAAAccessInfo::getMayAliasInfo();
404
10
405
10
  // TODO: Implement the rest of the logic here. For example, two accesses
406
10
  // with same final access types result in an access to an object of that final
407
10
  // access type regardless of their base types.
408
10
  return TBAAAccessInfo::getMayAliasInfo();
409
10
}
410
411
TBAAAccessInfo
412
CodeGenTBAA::mergeTBAAInfoForMemoryTransfer(TBAAAccessInfo DestInfo,
413
0
                                            TBAAAccessInfo SrcInfo) {
414
0
  if (DestInfo == SrcInfo)
415
0
    return DestInfo;
416
0
417
0
  if (!DestInfo || !SrcInfo)
418
0
    return TBAAAccessInfo();
419
0
420
0
  if (DestInfo.isMayAlias() || SrcInfo.isMayAlias())
421
0
    return TBAAAccessInfo::getMayAliasInfo();
422
0
423
0
  // TODO: Implement the rest of the logic here. For example, two accesses
424
0
  // with same final access types result in an access to an object of that final
425
0
  // access type regardless of their base types.
426
0
  return TBAAAccessInfo::getMayAliasInfo();
427
0
}