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