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/Type.h"
  29 using namespace clang;
  30 using namespace CodeGen;
  31
  32 CodeGenTBAA::CodeGenTBAA(ASTContext &Ctx, llvm::LLVMContext& VMContext,
  33                          const CodeGenOptions &CGO,
  34                          const LangOptions &Features, MangleContext &MContext)
  35   : Context(Ctx), CodeGenOpts(CGO), Features(Features), MContext(MContext),
  36     MDHelper(VMContext), Root(nullptr), Char(nullptr) {
  37 }
  38
  39 CodeGenTBAA::~CodeGenTBAA() {
  40 }
  41
  42 llvm::MDNode *CodeGenTBAA::getRoot() {
  43   // Define the root of the tree. This identifies the tree, so that
  44   // if our LLVM IR is linked with LLVM IR from a different front-end
  45   // (or a different version of this front-end), their TBAA trees will
  46   // remain distinct, and the optimizer will treat them conservatively.
  47   if (!Root) {
  48     if (Features.CPlusPlus)
  49       Root = MDHelper.createTBAARoot("Simple C++ TBAA");
  50     else
  51       Root = MDHelper.createTBAARoot("Simple C/C++ TBAA");
  52   }
  53
  54   return Root;
  55 }
  56
  57 // For both scalar TBAA and struct-path aware TBAA, the scalar type has the
  58 // same format: name, parent node, and offset.
  59 llvm::MDNode *CodeGenTBAA::createTBAAScalarType(StringRef Name,
  60                                                 llvm::MDNode *Parent) {
  61   return MDHelper.createTBAAScalarTypeNode(Name, Parent);
  62 }
  63
  64 llvm::MDNode *CodeGenTBAA::getChar() {
  65   // Define the root of the tree for user-accessible memory. C and C++
  66   // give special powers to char and certain similar types. However,
  67   // these special powers only cover user-accessible memory, and doesn't
  68   // include things like vtables.
  69   if (!Char)
  70     Char = createTBAAScalarType("omnipotent char", getRoot());
  71
  72   return Char;
  73 }
  74
  75 static bool TypeHasMayAlias(QualType QTy) {
  76   // Tagged types have declarations, and therefore may have attributes.
  77   if (const TagType *TTy = dyn_cast<TagType>(QTy))
  78     return TTy->getDecl()->hasAttr<MayAliasAttr>();
  79
  80   // Typedef types have declarations, and therefore may have attributes.
  81   if (const TypedefType *TTy = dyn_cast<TypedefType>(QTy)) {
  82     if (TTy->getDecl()->hasAttr<MayAliasAttr>())
  83       return true;
  84     // Also, their underlying types may have relevant attributes.
  85     return TypeHasMayAlias(TTy->desugar());
  86   }
  87
  88   return false;
  89 }
  90
  91 llvm::MDNode *
  92 CodeGenTBAA::getTBAAInfo(QualType QTy) {
  93   // At -O0 or relaxed aliasing, TBAA is not emitted for regular types.
  94   if (CodeGenOpts.OptimizationLevel == 0 || CodeGenOpts.RelaxedAliasing)
  95     return nullptr;
  96
  97   // If the type has the may_alias attribute (even on a typedef), it is
  98   // effectively in the general char alias class.
  99   if (TypeHasMayAlias(QTy))
 100     return getChar();
 101
 102   const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
 103
 104   if (llvm::MDNode *N = MetadataCache[Ty])
 105     return N;
 106
 107   // Handle builtin types.
 108   if (const BuiltinType *BTy = dyn_cast<BuiltinType>(Ty)) {
 109     switch (BTy->getKind()) {
 110     // Character types are special and can alias anything.
 111     // In C++, this technically only includes "char" and "unsigned char",
 112     // and not "signed char". In C, it includes all three. For now,
 113     // the risk of exploiting this detail in C++ seems likely to outweigh
 114     // the benefit.
 115     case BuiltinType::Char_U:
 116     case BuiltinType::Char_S:
 117     case BuiltinType::UChar:
 118     case BuiltinType::SChar:
 119       return getChar();
 120
 121     // Unsigned types can alias their corresponding signed types.
 122     case BuiltinType::UShort:
 123       return getTBAAInfo(Context.ShortTy);
 124     case BuiltinType::UInt:
 125       return getTBAAInfo(Context.IntTy);
 126     case BuiltinType::ULong:
 127       return getTBAAInfo(Context.LongTy);
 128     case BuiltinType::ULongLong:
 129       return getTBAAInfo(Context.LongLongTy);
 130     case BuiltinType::UInt128:
 131       return getTBAAInfo(Context.Int128Ty);
 132
 133     // Treat all other builtin types as distinct types. This includes
 134     // treating wchar_t, char16_t, and char32_t as distinct from their
 135     // "underlying types".
 136     default:
 137       return MetadataCache[Ty] =
 138         createTBAAScalarType(BTy->getName(Features), getChar());
 139     }
 140   }
 141
 142   // C++1z [basic.lval]p10: "If a program attempts to access the stored value of
 143   // an object through a glvalue of other than one of the following types the
 144   // behavior is undefined: [...] a char, unsigned char, or std::byte type."
 145   if (Ty->isStdByteType())
 146     return MetadataCache[Ty] = getChar();
 147
 148   // Handle pointers.
 149   // TODO: Implement C++'s type "similarity" and consider dis-"similar"
 150   // pointers distinct.
 151   if (Ty->isPointerType())
 152     return MetadataCache[Ty] = createTBAAScalarType("any pointer",
 153                                                     getChar());
 154
 155   // Enum types are distinct types. In C++ they have "underlying types",
 156   // however they aren't related for TBAA.
 157   if (const EnumType *ETy = dyn_cast<EnumType>(Ty)) {
 158     // In C++ mode, types have linkage, so we can rely on the ODR and
 159     // on their mangled names, if they're external.
 160     // TODO: Is there a way to get a program-wide unique name for a
 161     // decl with local linkage or no linkage?
 162     if (!Features.CPlusPlus || !ETy->getDecl()->isExternallyVisible())
 163       return MetadataCache[Ty] = getChar();
 164
 165     SmallString<256> OutName;
 166     llvm::raw_svector_ostream Out(OutName);
 167     MContext.mangleTypeName(QualType(ETy, 0), Out);
 168     return MetadataCache[Ty] = createTBAAScalarType(OutName, getChar());
 169   }
 170
 171   // For now, handle any other kind of type conservatively.
 172   return MetadataCache[Ty] = getChar();
 173 }
 174
 175 llvm::MDNode *CodeGenTBAA::getTBAAInfoForVTablePtr() {
 176   return createTBAAScalarType("vtable pointer", getRoot());
 177 }
 178
 179 bool
 180 CodeGenTBAA::CollectFields(uint64_t BaseOffset,
 181                            QualType QTy,
 182                            SmallVectorImpl<llvm::MDBuilder::TBAAStructField> &
 183                              Fields,
 184                            bool MayAlias) {
 185   /* Things not handled yet include: C++ base classes, bitfields, */
 186
 187   if (const RecordType *TTy = QTy->getAs<RecordType>()) {
 188     const RecordDecl *RD = TTy->getDecl()->getDefinition();
 189     if (RD->hasFlexibleArrayMember())
 190       return false;
 191
 192     // TODO: Handle C++ base classes.
 193     if (const CXXRecordDecl *Decl = dyn_cast<CXXRecordDecl>(RD))
 194       if (Decl->bases_begin() != Decl->bases_end())
 195         return false;
 196
 197     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 198
 199     unsigned idx = 0;
 200     for (RecordDecl::field_iterator i = RD->field_begin(),
 201          e = RD->field_end(); i != e; ++i, ++idx) {
 202       uint64_t Offset = BaseOffset +
 203                         Layout.getFieldOffset(idx) / Context.getCharWidth();
 204       QualType FieldQTy = i->getType();
 205       if (!CollectFields(Offset, FieldQTy, Fields,
 206                          MayAlias || TypeHasMayAlias(FieldQTy)))
 207         return false;
 208     }
 209     return true;
 210   }
 211
 212   /* Otherwise, treat whatever it is as a field. */
 213   uint64_t Offset = BaseOffset;
 214   uint64_t Size = Context.getTypeSizeInChars(QTy).getQuantity();
 215   llvm::MDNode *TBAAInfo = MayAlias ? getChar() : getTBAAInfo(QTy);
 216   llvm::MDNode *TBAATag = getTBAAScalarTagInfo(TBAAInfo);
 217   Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size, TBAATag));
 218   return true;
 219 }
 220
 221 llvm::MDNode *
 222 CodeGenTBAA::getTBAAStructInfo(QualType QTy) {
 223   const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
 224
 225   if (llvm::MDNode *N = StructMetadataCache[Ty])
 226     return N;
 227
 228   SmallVector<llvm::MDBuilder::TBAAStructField, 4> Fields;
 229   if (CollectFields(0, QTy, Fields, TypeHasMayAlias(QTy)))
 230     return MDHelper.createTBAAStructNode(Fields);
 231
 232   // For now, handle any other kind of type conservatively.
 233   return StructMetadataCache[Ty] = nullptr;
 234 }
 235
 236 /// Check if the given type can be handled by path-aware TBAA.
 237 static bool isTBAAPathStruct(QualType QTy) {
 238   if (const RecordType *TTy = QTy->getAs<RecordType>()) {
 239     const RecordDecl *RD = TTy->getDecl()->getDefinition();
 240     if (RD->hasFlexibleArrayMember())
 241       return false;
 242     // RD can be struct, union, class, interface or enum.
 243     // For now, we only handle struct and class.
 244     if (RD->isStruct() || RD->isClass())
 245       return true;
 246   }
 247   return false;
 248 }
 249
 250 llvm::MDNode *
 251 CodeGenTBAA::getTBAAStructTypeInfo(QualType QTy) {
 252   const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
 253   assert(isTBAAPathStruct(QTy));
 254
 255   if (llvm::MDNode *N = StructTypeMetadataCache[Ty])
 256     return N;
 257
 258   if (const RecordType *TTy = QTy->getAs<RecordType>()) {
 259     const RecordDecl *RD = TTy->getDecl()->getDefinition();
 260
 261     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 262     SmallVector <std::pair<llvm::MDNode*, uint64_t>, 4> Fields;
 263     unsigned idx = 0;
 264     for (RecordDecl::field_iterator i = RD->field_begin(),
 265          e = RD->field_end(); i != e; ++i, ++idx) {
 266       QualType FieldQTy = i->getType();
 267       llvm::MDNode *FieldNode;
 268       if (isTBAAPathStruct(FieldQTy))
 269         FieldNode = getTBAAStructTypeInfo(FieldQTy);
 270       else
 271         FieldNode = getTBAAInfo(FieldQTy);
 272       if (!FieldNode)
 273         return StructTypeMetadataCache[Ty] = nullptr;
 274       Fields.push_back(std::make_pair(
 275           FieldNode, Layout.getFieldOffset(idx) / Context.getCharWidth()));
 276     }
 277
 278     SmallString<256> OutName;
 279     if (Features.CPlusPlus) {
 280       // Don't use the mangler for C code.
 281       llvm::raw_svector_ostream Out(OutName);
 282       MContext.mangleTypeName(QualType(Ty, 0), Out);
 283     } else {
 284       OutName = RD->getName();
 285     }
 286     // Create the struct type node with a vector of pairs (offset, type).
 287     return StructTypeMetadataCache[Ty] =
 288       MDHelper.createTBAAStructTypeNode(OutName, Fields);
 289   }
 290
 291   return StructMetadataCache[Ty] = nullptr;
 292 }
 293
 294 /// Return a TBAA tag node for both scalar TBAA and struct-path aware TBAA.
 295 llvm::MDNode *
 296 CodeGenTBAA::getTBAAStructTagInfo(QualType BaseQTy, llvm::MDNode *AccessNode,
 297                                   uint64_t Offset) {
 298   if (!AccessNode)
 299     return nullptr;
 300
 301   if (!CodeGenOpts.StructPathTBAA)
 302     return getTBAAScalarTagInfo(AccessNode);
 303
 304   const Type *BTy = Context.getCanonicalType(BaseQTy).getTypePtr();
 305   TBAAPathTag PathTag = TBAAPathTag(BTy, AccessNode, Offset);
 306   if (llvm::MDNode *N = StructTagMetadataCache[PathTag])
 307     return N;
 308
 309   llvm::MDNode *BNode = nullptr;
 310   if (isTBAAPathStruct(BaseQTy))
 311     BNode  = getTBAAStructTypeInfo(BaseQTy);
 312   if (!BNode)
 313     return StructTagMetadataCache[PathTag] =
 314        MDHelper.createTBAAStructTagNode(AccessNode, AccessNode, 0);
 315
 316   return StructTagMetadataCache[PathTag] =
 317     MDHelper.createTBAAStructTagNode(BNode, AccessNode, Offset);
 318 }
 319
 320 llvm::MDNode *
 321 CodeGenTBAA::getTBAAScalarTagInfo(llvm::MDNode *AccessNode) {
 322   if (!AccessNode)
 323     return nullptr;
 324   if (llvm::MDNode *N = ScalarTagMetadataCache[AccessNode])
 325     return N;
 326
 327   return ScalarTagMetadataCache[AccessNode] =
 328     MDHelper.createTBAAStructTagNode(AccessNode, AccessNode, 0);
 329 }