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/Frontend/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::getVTablePtrAccessInfo(llvm::Type *VTablePtrType) {
 219   llvm::DataLayout DL(&Module);
 220   unsigned Size = DL.getPointerTypeSize(VTablePtrType);
 221   return TBAAAccessInfo(createScalarTypeNode("vtable pointer", getRoot(), Size),
 222                         Size);
 223 }
 224
 225 bool
 226 CodeGenTBAA::CollectFields(uint64_t BaseOffset,
 227                            QualType QTy,
 228                            SmallVectorImpl<llvm::MDBuilder::TBAAStructField> &
 229                              Fields,
 230                            bool MayAlias) {
 231   /* Things not handled yet include: C++ base classes, bitfields, */
 232
 233   if (const RecordType *TTy = QTy->getAs<RecordType>()) {
 234     const RecordDecl *RD = TTy->getDecl()->getDefinition();
 235     if (RD->hasFlexibleArrayMember())
 236       return false;
 237
 238     // TODO: Handle C++ base classes.
 239     if (const CXXRecordDecl *Decl = dyn_cast<CXXRecordDecl>(RD))
 240       if (Decl->bases_begin() != Decl->bases_end())
 241         return false;
 242
 243     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 244
 245     unsigned idx = 0;
 246     for (RecordDecl::field_iterator i = RD->field_begin(),
 247          e = RD->field_end(); i != e; ++i, ++idx) {
 248       uint64_t Offset = BaseOffset +
 249                         Layout.getFieldOffset(idx) / Context.getCharWidth();
 250       QualType FieldQTy = i->getType();
 251       if (!CollectFields(Offset, FieldQTy, Fields,
 252                          MayAlias || TypeHasMayAlias(FieldQTy)))
 253         return false;
 254     }
 255     return true;
 256   }
 257
 258   /* Otherwise, treat whatever it is as a field. */
 259   uint64_t Offset = BaseOffset;
 260   uint64_t Size = Context.getTypeSizeInChars(QTy).getQuantity();
 261   llvm::MDNode *TBAAType = MayAlias ? getChar() : getTypeInfo(QTy);
 262   llvm::MDNode *TBAATag = getAccessTagInfo(TBAAAccessInfo(TBAAType, Size));
 263   Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size, TBAATag));
 264   return true;
 265 }
 266
 267 llvm::MDNode *
 268 CodeGenTBAA::getTBAAStructInfo(QualType QTy) {
 269   const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
 270
 271   if (llvm::MDNode *N = StructMetadataCache[Ty])
 272     return N;
 273
 274   SmallVector<llvm::MDBuilder::TBAAStructField, 4> Fields;
 275   if (CollectFields(0, QTy, Fields, TypeHasMayAlias(QTy)))
 276     return MDHelper.createTBAAStructNode(Fields);
 277
 278   // For now, handle any other kind of type conservatively.
 279   return StructMetadataCache[Ty] = nullptr;
 280 }
 281
 282 llvm::MDNode *CodeGenTBAA::getBaseTypeInfoHelper(const Type *Ty) {
 283   if (auto *TTy = dyn_cast<RecordType>(Ty)) {
 284     const RecordDecl *RD = TTy->getDecl()->getDefinition();
 285     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 286     SmallVector<llvm::MDBuilder::TBAAStructField, 4> Fields;
 287     for (FieldDecl *Field : RD->fields()) {
 288       QualType FieldQTy = Field->getType();
 289       llvm::MDNode *TypeNode = isValidBaseType(FieldQTy) ?
 290           getBaseTypeInfo(FieldQTy) : getTypeInfo(FieldQTy);
 291       if (!TypeNode)
 292         return BaseTypeMetadataCache[Ty] = nullptr;
 293
 294       uint64_t BitOffset = Layout.getFieldOffset(Field->getFieldIndex());
 295       uint64_t Offset = Context.toCharUnitsFromBits(BitOffset).getQuantity();
 296       uint64_t Size = Context.getTypeSizeInChars(FieldQTy).getQuantity();
 297       Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size,
 298                                                         TypeNode));
 299     }
 300
 301     SmallString<256> OutName;
 302     if (Features.CPlusPlus) {
 303       // Don't use the mangler for C code.
 304       llvm::raw_svector_ostream Out(OutName);
 305       MContext.mangleTypeName(QualType(Ty, 0), Out);
 306     } else {
 307       OutName = RD->getName();
 308     }
 309
 310     if (CodeGenOpts.NewStructPathTBAA) {
 311       llvm::MDNode *Parent = getChar();
 312       uint64_t Size = Context.getTypeSizeInChars(Ty).getQuantity();
 313       llvm::Metadata *Id = MDHelper.createString(OutName);
 314       return MDHelper.createTBAATypeNode(Parent, Size, Id, Fields);
 315     }
 316
 317     // Create the struct type node with a vector of pairs (offset, type).
 318     SmallVector<std::pair<llvm::MDNode*, uint64_t>, 4> OffsetsAndTypes;
 319     for (const auto &Field : Fields)
 320         OffsetsAndTypes.push_back(std::make_pair(Field.Type, Field.Offset));
 321     return MDHelper.createTBAAStructTypeNode(OutName, OffsetsAndTypes);
 322   }
 323
 324   return nullptr;
 325 }
 326
 327 llvm::MDNode *CodeGenTBAA::getBaseTypeInfo(QualType QTy) {
 328   if (!isValidBaseType(QTy))
 329     return nullptr;
 330
 331   const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
 332   if (llvm::MDNode *N = BaseTypeMetadataCache[Ty])
 333     return N;
 334
 335   // Note that the following helper call is allowed to add new nodes to the
 336   // cache, which invalidates all its previously obtained iterators. So we
 337   // first generate the node for the type and then add that node to the cache.
 338   llvm::MDNode *TypeNode = getBaseTypeInfoHelper(Ty);
 339   return BaseTypeMetadataCache[Ty] = TypeNode;
 340 }
 341
 342 llvm::MDNode *CodeGenTBAA::getAccessTagInfo(TBAAAccessInfo Info) {
 343   assert(!Info.isIncomplete() && "Access to an object of an incomplete type!");
 344
 345   if (Info.isMayAlias())
 346     Info = TBAAAccessInfo(getChar(), Info.Size);
 347
 348   if (!Info.AccessType)
 349     return nullptr;
 350
 351   if (!CodeGenOpts.StructPathTBAA)
 352     Info = TBAAAccessInfo(Info.AccessType, Info.Size);
 353
 354   llvm::MDNode *&N = AccessTagMetadataCache[Info];
 355   if (N)
 356     return N;
 357
 358   if (!Info.BaseType) {
 359     Info.BaseType = Info.AccessType;
 360     assert(!Info.Offset && "Nonzero offset for an access with no base type!");
 361   }
 362   if (CodeGenOpts.NewStructPathTBAA) {
 363     return N = MDHelper.createTBAAAccessTag(Info.BaseType, Info.AccessType,
 364                                             Info.Offset, Info.Size);
 365   }
 366   return N = MDHelper.createTBAAStructTagNode(Info.BaseType, Info.AccessType,
 367                                               Info.Offset);
 368 }
 369
 370 TBAAAccessInfo CodeGenTBAA::mergeTBAAInfoForCast(TBAAAccessInfo SourceInfo,
 371                                                  TBAAAccessInfo TargetInfo) {
 372   if (SourceInfo.isMayAlias() || TargetInfo.isMayAlias())
 373     return TBAAAccessInfo::getMayAliasInfo();
 374   return TargetInfo;
 375 }
 376
 377 TBAAAccessInfo
 378 CodeGenTBAA::mergeTBAAInfoForConditionalOperator(TBAAAccessInfo InfoA,
 379                                                  TBAAAccessInfo InfoB) {
 380   if (InfoA == InfoB)
 381     return InfoA;
 382
 383   if (!InfoA || !InfoB)
 384     return TBAAAccessInfo();
 385
 386   if (InfoA.isMayAlias() || InfoB.isMayAlias())
 387     return TBAAAccessInfo::getMayAliasInfo();
 388
 389   // TODO: Implement the rest of the logic here. For example, two accesses
 390   // with same final access types result in an access to an object of that final
 391   // access type regardless of their base types.
 392   return TBAAAccessInfo::getMayAliasInfo();
 393 }