contrib/llvm/tools/clang/lib/CodeGen/CodeGenTBAA.cpp

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