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     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   // Handle pointers.
 143   // TODO: Implement C++'s type "similarity" and consider dis-"similar"
 144   // pointers distinct.
 145   if (Ty->isPointerType())
 146     return MetadataCache[Ty] = createTBAAScalarType("any pointer",
 147                                                     getChar());
 148
 149   // Enum types are distinct types. In C++ they have "underlying types",
 150   // however they aren't related for TBAA.
 151   if (const EnumType *ETy = dyn_cast<EnumType>(Ty)) {
 152     // In C++ mode, types have linkage, so we can rely on the ODR and
 153     // on their mangled names, if they're external.
 154     // TODO: Is there a way to get a program-wide unique name for a
 155     // decl with local linkage or no linkage?
 156     if (!Features.CPlusPlus || !ETy->getDecl()->isExternallyVisible())
 157       return MetadataCache[Ty] = getChar();
 158
 159     SmallString<256> OutName;
 160     llvm::raw_svector_ostream Out(OutName);
 161     MContext.mangleTypeName(QualType(ETy, 0), Out);
 162     return MetadataCache[Ty] = createTBAAScalarType(OutName, getChar());
 163   }
 164
 165   // For now, handle any other kind of type conservatively.
 166   return MetadataCache[Ty] = getChar();
 167 }
 168
 169 llvm::MDNode *CodeGenTBAA::getTBAAInfoForVTablePtr() {
 170   return createTBAAScalarType("vtable pointer", getRoot());
 171 }
 172
 173 bool
 174 CodeGenTBAA::CollectFields(uint64_t BaseOffset,
 175                            QualType QTy,
 176                            SmallVectorImpl<llvm::MDBuilder::TBAAStructField> &
 177                              Fields,
 178                            bool MayAlias) {
 179   /* Things not handled yet include: C++ base classes, bitfields, */
 180
 181   if (const RecordType *TTy = QTy->getAs<RecordType>()) {
 182     const RecordDecl *RD = TTy->getDecl()->getDefinition();
 183     if (RD->hasFlexibleArrayMember())
 184       return false;
 185
 186     // TODO: Handle C++ base classes.
 187     if (const CXXRecordDecl *Decl = dyn_cast<CXXRecordDecl>(RD))
 188       if (Decl->bases_begin() != Decl->bases_end())
 189         return false;
 190
 191     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 192
 193     unsigned idx = 0;
 194     for (RecordDecl::field_iterator i = RD->field_begin(),
 195          e = RD->field_end(); i != e; ++i, ++idx) {
 196       uint64_t Offset = BaseOffset +
 197                         Layout.getFieldOffset(idx) / Context.getCharWidth();
 198       QualType FieldQTy = i->getType();
 199       if (!CollectFields(Offset, FieldQTy, Fields,
 200                          MayAlias || TypeHasMayAlias(FieldQTy)))
 201         return false;
 202     }
 203     return true;
 204   }
 205
 206   /* Otherwise, treat whatever it is as a field. */
 207   uint64_t Offset = BaseOffset;
 208   uint64_t Size = Context.getTypeSizeInChars(QTy).getQuantity();
 209   llvm::MDNode *TBAAInfo = MayAlias ? getChar() : getTBAAInfo(QTy);
 210   llvm::MDNode *TBAATag = getTBAAScalarTagInfo(TBAAInfo);
 211   Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size, TBAATag));
 212   return true;
 213 }
 214
 215 llvm::MDNode *
 216 CodeGenTBAA::getTBAAStructInfo(QualType QTy) {
 217   const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
 218
 219   if (llvm::MDNode *N = StructMetadataCache[Ty])
 220     return N;
 221
 222   SmallVector<llvm::MDBuilder::TBAAStructField, 4> Fields;
 223   if (CollectFields(0, QTy, Fields, TypeHasMayAlias(QTy)))
 224     return MDHelper.createTBAAStructNode(Fields);
 225
 226   // For now, handle any other kind of type conservatively.
 227   return StructMetadataCache[Ty] = nullptr;
 228 }
 229
 230 /// Check if the given type can be handled by path-aware TBAA.
 231 static bool isTBAAPathStruct(QualType QTy) {
 232   if (const RecordType *TTy = QTy->getAs<RecordType>()) {
 233     const RecordDecl *RD = TTy->getDecl()->getDefinition();
 234     if (RD->hasFlexibleArrayMember())
 235       return false;
 236     // RD can be struct, union, class, interface or enum.
 237     // For now, we only handle struct and class.
 238     if (RD->isStruct() || RD->isClass())
 239       return true;
 240   }
 241   return false;
 242 }
 243
 244 llvm::MDNode *
 245 CodeGenTBAA::getTBAAStructTypeInfo(QualType QTy) {
 246   const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
 247   assert(isTBAAPathStruct(QTy));
 248
 249   if (llvm::MDNode *N = StructTypeMetadataCache[Ty])
 250     return N;
 251
 252   if (const RecordType *TTy = QTy->getAs<RecordType>()) {
 253     const RecordDecl *RD = TTy->getDecl()->getDefinition();
 254
 255     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 256     SmallVector <std::pair<llvm::MDNode*, uint64_t>, 4> Fields;
 257     unsigned idx = 0;
 258     for (RecordDecl::field_iterator i = RD->field_begin(),
 259          e = RD->field_end(); i != e; ++i, ++idx) {
 260       QualType FieldQTy = i->getType();
 261       llvm::MDNode *FieldNode;
 262       if (isTBAAPathStruct(FieldQTy))
 263         FieldNode = getTBAAStructTypeInfo(FieldQTy);
 264       else
 265         FieldNode = getTBAAInfo(FieldQTy);
 266       if (!FieldNode)
 267         return StructTypeMetadataCache[Ty] = nullptr;
 268       Fields.push_back(std::make_pair(
 269           FieldNode, Layout.getFieldOffset(idx) / Context.getCharWidth()));
 270     }
 271
 272     SmallString<256> OutName;
 273     if (Features.CPlusPlus) {
 274       // Don't use the mangler for C code.
 275       llvm::raw_svector_ostream Out(OutName);
 276       MContext.mangleTypeName(QualType(Ty, 0), Out);
 277     } else {
 278       OutName = RD->getName();
 279     }
 280     // Create the struct type node with a vector of pairs (offset, type).
 281     return StructTypeMetadataCache[Ty] =
 282       MDHelper.createTBAAStructTypeNode(OutName, Fields);
 283   }
 284
 285   return StructMetadataCache[Ty] = nullptr;
 286 }
 287
 288 /// Return a TBAA tag node for both scalar TBAA and struct-path aware TBAA.
 289 llvm::MDNode *
 290 CodeGenTBAA::getTBAAStructTagInfo(QualType BaseQTy, llvm::MDNode *AccessNode,
 291                                   uint64_t Offset) {
 292   if (!AccessNode)
 293     return nullptr;
 294
 295   if (!CodeGenOpts.StructPathTBAA)
 296     return getTBAAScalarTagInfo(AccessNode);
 297
 298   const Type *BTy = Context.getCanonicalType(BaseQTy).getTypePtr();
 299   TBAAPathTag PathTag = TBAAPathTag(BTy, AccessNode, Offset);
 300   if (llvm::MDNode *N = StructTagMetadataCache[PathTag])
 301     return N;
 302
 303   llvm::MDNode *BNode = nullptr;
 304   if (isTBAAPathStruct(BaseQTy))
 305     BNode  = getTBAAStructTypeInfo(BaseQTy);
 306   if (!BNode)
 307     return StructTagMetadataCache[PathTag] =
 308        MDHelper.createTBAAStructTagNode(AccessNode, AccessNode, 0);
 309
 310   return StructTagMetadataCache[PathTag] =
 311     MDHelper.createTBAAStructTagNode(BNode, AccessNode, Offset);
 312 }
 313
 314 llvm::MDNode *
 315 CodeGenTBAA::getTBAAScalarTagInfo(llvm::MDNode *AccessNode) {
 316   if (!AccessNode)
 317     return nullptr;
 318   if (llvm::MDNode *N = ScalarTagMetadataCache[AccessNode])
 319     return N;
 320
 321   return ScalarTagMetadataCache[AccessNode] =
 322     MDHelper.createTBAAStructTagNode(AccessNode, AccessNode, 0);
 323 }