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