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

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