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