lib/CodeGen/CodeGenTypes.cpp

   1 //===--- CodeGenTypes.cpp - Type translation 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 handles AST -> LLVM type lowering.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "CodeGenTypes.h"
  15 #include "CGCall.h"
  16 #include "CGRecordLayout.h"
  17 #include "clang/AST/ASTContext.h"
  18 #include "clang/AST/DeclObjC.h"
  19 #include "clang/AST/DeclCXX.h"
  20 #include "clang/AST/Expr.h"
  21 #include "clang/AST/RecordLayout.h"
  22 #include "llvm/DerivedTypes.h"
  23 #include "llvm/Module.h"
  24 #include "llvm/Target/TargetData.h"
  25 using namespace clang;
  26 using namespace CodeGen;
  27
  28 CodeGenTypes::CodeGenTypes(ASTContext &Ctx, llvm::Module& M,
  29                            const llvm::TargetData &TD, const ABIInfo &Info)
  30   : Context(Ctx), Target(Ctx.Target), TheModule(M), TheTargetData(TD),
  31     TheABIInfo(Info) {
  32 }
  33
  34 CodeGenTypes::~CodeGenTypes() {
  35   for (llvm::DenseMap<const Type *, CGRecordLayout *>::iterator
  36          I = CGRecordLayouts.begin(), E = CGRecordLayouts.end();
  37       I != E; ++I)
  38     delete I->second;
  39
  40   for (llvm::FoldingSet<CGFunctionInfo>::iterator
  41        I = FunctionInfos.begin(), E = FunctionInfos.end(); I != E; )
  42     delete &*I++;
  43 }
  44
  45 /// HandleLateResolvedPointers - For top-level ConvertType calls, this handles
  46 /// pointers that are referenced but have not been converted yet.  This is used
  47 /// to handle cyclic structures properly.
  48 void CodeGenTypes::HandleLateResolvedPointers() {
  49   assert(!PointersToResolve.empty() && "No pointers to resolve!");
  50
  51   // Any pointers that were converted deferred evaluation of their pointee type,
  52   // creating an opaque type instead.  This is in order to avoid problems with
  53   // circular types.  Loop through all these defered pointees, if any, and
  54   // resolve them now.
  55   while (!PointersToResolve.empty()) {
  56     std::pair<QualType, llvm::OpaqueType*> P = PointersToResolve.pop_back_val();
  57
  58     // We can handle bare pointers here because we know that the only pointers
  59     // to the Opaque type are P.second and from other types.  Refining the
  60     // opqaue type away will invalidate P.second, but we don't mind :).
  61     const llvm::Type *NT = ConvertTypeForMemRecursive(P.first);
  62     P.second->refineAbstractTypeTo(NT);
  63   }
  64 }
  65
  66
  67 /// ConvertType - Convert the specified type to its LLVM form.
  68 const llvm::Type *CodeGenTypes::ConvertType(QualType T, bool IsRecursive) {
  69   const llvm::Type *Result = ConvertTypeRecursive(T);
  70
  71   // If this is a top-level call to ConvertType and sub-conversions caused
  72   // pointers to get lazily built as opaque types, resolve the pointers, which
  73   // might cause Result to be merged away.
  74   if (!IsRecursive && !PointersToResolve.empty()) {
  75     llvm::PATypeHolder ResultHandle = Result;
  76     HandleLateResolvedPointers();
  77     Result = ResultHandle;
  78   }
  79   return Result;
  80 }
  81
  82 const llvm::Type *CodeGenTypes::ConvertTypeRecursive(QualType T) {
  83   T = Context.getCanonicalType(T);
  84
  85   // See if type is already cached.
  86   llvm::DenseMap<Type *, llvm::PATypeHolder>::iterator
  87     I = TypeCache.find(T.getTypePtr());
  88   // If type is found in map and this is not a definition for a opaque
  89   // place holder type then use it. Otherwise, convert type T.
  90   if (I != TypeCache.end())
  91     return I->second.get();
  92
  93   const llvm::Type *ResultType = ConvertNewType(T);
  94   TypeCache.insert(std::make_pair(T.getTypePtr(),
  95                                   llvm::PATypeHolder(ResultType)));
  96   return ResultType;
  97 }
  98
  99 /// ConvertTypeForMem - Convert type T into a llvm::Type.  This differs from
 100 /// ConvertType in that it is used to convert to the memory representation for
 101 /// a type.  For example, the scalar representation for _Bool is i1, but the
 102 /// memory representation is usually i8 or i32, depending on the target.
 103 const llvm::Type *CodeGenTypes::ConvertTypeForMem(QualType T, bool IsRecursive){
 104   const llvm::Type *R = ConvertType(T, IsRecursive);
 105
 106   // If this is a non-bool type, don't map it.
 107   if (!R->isIntegerTy(1))
 108     return R;
 109
 110   // Otherwise, return an integer of the target-specified size.
 111   return llvm::IntegerType::get(getLLVMContext(),
 112                                 (unsigned)Context.getTypeSize(T));
 113
 114 }
 115
 116 // Code to verify a given function type is complete, i.e. the return type
 117 // and all of the argument types are complete.
 118 const TagType *CodeGenTypes::VerifyFuncTypeComplete(const Type* T) {
 119   const FunctionType *FT = cast<FunctionType>(T);
 120   if (const TagType* TT = FT->getResultType()->getAs<TagType>())
 121     if (!TT->getDecl()->isDefinition())
 122       return TT;
 123   if (const FunctionProtoType *FPT = dyn_cast<FunctionProtoType>(T))
 124     for (unsigned i = 0; i < FPT->getNumArgs(); i++)
 125       if (const TagType* TT = FPT->getArgType(i)->getAs<TagType>())
 126         if (!TT->getDecl()->isDefinition())
 127           return TT;
 128   return 0;
 129 }
 130
 131 /// UpdateCompletedType - When we find the full definition for a TagDecl,
 132 /// replace the 'opaque' type we previously made for it if applicable.
 133 void CodeGenTypes::UpdateCompletedType(const TagDecl *TD) {
 134   const Type *Key = Context.getTagDeclType(TD).getTypePtr();
 135   llvm::DenseMap<const Type*, llvm::PATypeHolder>::iterator TDTI =
 136     TagDeclTypes.find(Key);
 137   if (TDTI == TagDeclTypes.end()) return;
 138
 139   // Remember the opaque LLVM type for this tagdecl.
 140   llvm::PATypeHolder OpaqueHolder = TDTI->second;
 141   assert(isa<llvm::OpaqueType>(OpaqueHolder.get()) &&
 142          "Updating compilation of an already non-opaque type?");
 143
 144   // Remove it from TagDeclTypes so that it will be regenerated.
 145   TagDeclTypes.erase(TDTI);
 146
 147   // Generate the new type.
 148   const llvm::Type *NT = ConvertTagDeclType(TD);
 149
 150   // Refine the old opaque type to its new definition.
 151   cast<llvm::OpaqueType>(OpaqueHolder.get())->refineAbstractTypeTo(NT);
 152
 153   // Since we just completed a tag type, check to see if any function types
 154   // were completed along with the tag type.
 155   // FIXME: This is very inefficient; if we track which function types depend
 156   // on which tag types, though, it should be reasonably efficient.
 157   llvm::DenseMap<const Type*, llvm::PATypeHolder>::iterator i;
 158   for (i = FunctionTypes.begin(); i != FunctionTypes.end(); ++i) {
 159     if (const TagType* TT = VerifyFuncTypeComplete(i->first)) {
 160       // This function type still depends on an incomplete tag type; make sure
 161       // that tag type has an associated opaque type.
 162       ConvertTagDeclType(TT->getDecl());
 163     } else {
 164       // This function no longer depends on an incomplete tag type; create the
 165       // function type, and refine the opaque type to the new function type.
 166       llvm::PATypeHolder OpaqueHolder = i->second;
 167       const llvm::Type *NFT = ConvertNewType(QualType(i->first, 0));
 168       cast<llvm::OpaqueType>(OpaqueHolder.get())->refineAbstractTypeTo(NFT);
 169       FunctionTypes.erase(i);
 170     }
 171   }
 172 }
 173
 174 static const llvm::Type* getTypeForFormat(llvm::LLVMContext &VMContext,
 175                                           const llvm::fltSemantics &format) {
 176   if (&format == &llvm::APFloat::IEEEsingle)
 177     return llvm::Type::getFloatTy(VMContext);
 178   if (&format == &llvm::APFloat::IEEEdouble)
 179     return llvm::Type::getDoubleTy(VMContext);
 180   if (&format == &llvm::APFloat::IEEEquad)
 181     return llvm::Type::getFP128Ty(VMContext);
 182   if (&format == &llvm::APFloat::PPCDoubleDouble)
 183     return llvm::Type::getPPC_FP128Ty(VMContext);
 184   if (&format == &llvm::APFloat::x87DoubleExtended)
 185     return llvm::Type::getX86_FP80Ty(VMContext);
 186   assert(0 && "Unknown float format!");
 187   return 0;
 188 }
 189
 190 const llvm::Type *CodeGenTypes::ConvertNewType(QualType T) {
 191   const clang::Type &Ty = *Context.getCanonicalType(T).getTypePtr();
 192
 193   switch (Ty.getTypeClass()) {
 194 #define TYPE(Class, Base)
 195 #define ABSTRACT_TYPE(Class, Base)
 196 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
 197 #define DEPENDENT_TYPE(Class, Base) case Type::Class:
 198 #define NON_CANONICAL_UNLESS_DEPENDENT_TYPE(Class, Base) case Type::Class:
 199 #include "clang/AST/TypeNodes.def"
 200     assert(false && "Non-canonical or dependent types aren't possible.");
 201     break;
 202
 203   case Type::Builtin: {
 204     switch (cast<BuiltinType>(Ty).getKind()) {
 205     case BuiltinType::Void:
 206     case BuiltinType::ObjCId:
 207     case BuiltinType::ObjCClass:
 208     case BuiltinType::ObjCSel:
 209       // LLVM void type can only be used as the result of a function call.  Just
 210       // map to the same as char.
 211       return llvm::Type::getInt8Ty(getLLVMContext());
 212
 213     case BuiltinType::Bool:
 214       // Note that we always return bool as i1 for use as a scalar type.
 215       return llvm::Type::getInt1Ty(getLLVMContext());
 216
 217     case BuiltinType::Char_S:
 218     case BuiltinType::Char_U:
 219     case BuiltinType::SChar:
 220     case BuiltinType::UChar:
 221     case BuiltinType::Short:
 222     case BuiltinType::UShort:
 223     case BuiltinType::Int:
 224     case BuiltinType::UInt:
 225     case BuiltinType::Long:
 226     case BuiltinType::ULong:
 227     case BuiltinType::LongLong:
 228     case BuiltinType::ULongLong:
 229     case BuiltinType::WChar:
 230     case BuiltinType::Char16:
 231     case BuiltinType::Char32:
 232       return llvm::IntegerType::get(getLLVMContext(),
 233         static_cast<unsigned>(Context.getTypeSize(T)));
 234
 235     case BuiltinType::Float:
 236     case BuiltinType::Double:
 237     case BuiltinType::LongDouble:
 238       return getTypeForFormat(getLLVMContext(),
 239                               Context.getFloatTypeSemantics(T));
 240
 241     case BuiltinType::NullPtr: {
 242       // Model std::nullptr_t as i8*
 243       const llvm::Type *Ty = llvm::Type::getInt8Ty(getLLVMContext());
 244       return llvm::PointerType::getUnqual(Ty);
 245     }
 246
 247     case BuiltinType::UInt128:
 248     case BuiltinType::Int128:
 249       return llvm::IntegerType::get(getLLVMContext(), 128);
 250
 251     case BuiltinType::Overload:
 252     case BuiltinType::Dependent:
 253     case BuiltinType::UndeducedAuto:
 254       assert(0 && "Unexpected builtin type!");
 255       break;
 256     }
 257     assert(0 && "Unknown builtin type!");
 258     break;
 259   }
 260   case Type::Complex: {
 261     const llvm::Type *EltTy =
 262       ConvertTypeRecursive(cast<ComplexType>(Ty).getElementType());
 263     return llvm::StructType::get(TheModule.getContext(), EltTy, EltTy, NULL);
 264   }
 265   case Type::LValueReference:
 266   case Type::RValueReference: {
 267     const ReferenceType &RTy = cast<ReferenceType>(Ty);
 268     QualType ETy = RTy.getPointeeType();
 269     llvm::OpaqueType *PointeeType = llvm::OpaqueType::get(getLLVMContext());
 270     PointersToResolve.push_back(std::make_pair(ETy, PointeeType));
 271     return llvm::PointerType::get(PointeeType, ETy.getAddressSpace());
 272   }
 273   case Type::Pointer: {
 274     const PointerType &PTy = cast<PointerType>(Ty);
 275     QualType ETy = PTy.getPointeeType();
 276     llvm::OpaqueType *PointeeType = llvm::OpaqueType::get(getLLVMContext());
 277     PointersToResolve.push_back(std::make_pair(ETy, PointeeType));
 278     return llvm::PointerType::get(PointeeType, ETy.getAddressSpace());
 279   }
 280
 281   case Type::VariableArray: {
 282     const VariableArrayType &A = cast<VariableArrayType>(Ty);
 283     assert(A.getIndexTypeCVRQualifiers() == 0 &&
 284            "FIXME: We only handle trivial array types so far!");
 285     // VLAs resolve to the innermost element type; this matches
 286     // the return of alloca, and there isn't any obviously better choice.
 287     return ConvertTypeForMemRecursive(A.getElementType());
 288   }
 289   case Type::IncompleteArray: {
 290     const IncompleteArrayType &A = cast<IncompleteArrayType>(Ty);
 291     assert(A.getIndexTypeCVRQualifiers() == 0 &&
 292            "FIXME: We only handle trivial array types so far!");
 293     // int X[] -> [0 x int]
 294     return llvm::ArrayType::get(ConvertTypeForMemRecursive(A.getElementType()),
 295                                 0);
 296   }
 297   case Type::ConstantArray: {
 298     const ConstantArrayType &A = cast<ConstantArrayType>(Ty);
 299     const llvm::Type *EltTy = ConvertTypeForMemRecursive(A.getElementType());
 300     return llvm::ArrayType::get(EltTy, A.getSize().getZExtValue());
 301   }
 302   case Type::ExtVector:
 303   case Type::Vector: {
 304     const VectorType &VT = cast<VectorType>(Ty);
 305     return llvm::VectorType::get(ConvertTypeRecursive(VT.getElementType()),
 306                                  VT.getNumElements());
 307   }
 308   case Type::FunctionNoProto:
 309   case Type::FunctionProto: {
 310     // First, check whether we can build the full function type.  If the
 311     // function type depends on an incomplete type (e.g. a struct or enum), we
 312     // cannot lower the function type.  Instead, turn it into an Opaque pointer
 313     // and have UpdateCompletedType revisit the function type when/if the opaque
 314     // argument type is defined.
 315     if (const TagType *TT = VerifyFuncTypeComplete(&Ty)) {
 316       // This function's type depends on an incomplete tag type; make sure
 317       // we have an opaque type corresponding to the tag type.
 318       ConvertTagDeclType(TT->getDecl());
 319       // Create an opaque type for this function type, save it, and return it.
 320       llvm::Type *ResultType = llvm::OpaqueType::get(getLLVMContext());
 321       FunctionTypes.insert(std::make_pair(&Ty, ResultType));
 322       return ResultType;
 323     }
 324
 325     // The function type can be built; call the appropriate routines to
 326     // build it.
 327     const CGFunctionInfo *FI;
 328     bool isVariadic;
 329     if (const FunctionProtoType *FPT = dyn_cast<FunctionProtoType>(&Ty)) {
 330       FI = &getFunctionInfo(
 331                    CanQual<FunctionProtoType>::CreateUnsafe(QualType(FPT, 0)),
 332                             true /*Recursive*/);
 333       isVariadic = FPT->isVariadic();
 334     } else {
 335       const FunctionNoProtoType *FNPT = cast<FunctionNoProtoType>(&Ty);
 336       FI = &getFunctionInfo(
 337                 CanQual<FunctionNoProtoType>::CreateUnsafe(QualType(FNPT, 0)),
 338                             true /*Recursive*/);
 339       isVariadic = true;
 340     }
 341
 342     return GetFunctionType(*FI, isVariadic, true);
 343   }
 344
 345   case Type::ObjCObject:
 346     return ConvertTypeRecursive(cast<ObjCObjectType>(Ty).getBaseType());
 347
 348   case Type::ObjCInterface: {
 349     // Objective-C interfaces are always opaque (outside of the
 350     // runtime, which can do whatever it likes); we never refine
 351     // these.
 352     const llvm::Type *&T = InterfaceTypes[cast<ObjCInterfaceType>(&Ty)];
 353     if (!T)
 354         T = llvm::OpaqueType::get(getLLVMContext());
 355     return T;
 356   }
 357
 358   case Type::ObjCObjectPointer: {
 359     // Protocol qualifications do not influence the LLVM type, we just return a
 360     // pointer to the underlying interface type. We don't need to worry about
 361     // recursive conversion.
 362     const llvm::Type *T =
 363       ConvertTypeRecursive(cast<ObjCObjectPointerType>(Ty).getPointeeType());
 364     return llvm::PointerType::getUnqual(T);
 365   }
 366
 367   case Type::Record:
 368   case Type::Enum: {
 369     const TagDecl *TD = cast<TagType>(Ty).getDecl();
 370     const llvm::Type *Res = ConvertTagDeclType(TD);
 371
 372     std::string TypeName(TD->getKindName());
 373     TypeName += '.';
 374
 375     // Name the codegen type after the typedef name
 376     // if there is no tag type name available
 377     if (TD->getIdentifier())
 378       // FIXME: We should not have to check for a null decl context here.
 379       // Right now we do it because the implicit Obj-C decls don't have one.
 380       TypeName += TD->getDeclContext() ? TD->getQualifiedNameAsString() :
 381         TD->getNameAsString();
 382     else if (const TypedefType *TdT = dyn_cast<TypedefType>(T))
 383       // FIXME: We should not have to check for a null decl context here.
 384       // Right now we do it because the implicit Obj-C decls don't have one.
 385       TypeName += TdT->getDecl()->getDeclContext() ?
 386         TdT->getDecl()->getQualifiedNameAsString() :
 387         TdT->getDecl()->getNameAsString();
 388     else
 389       TypeName += "anon";
 390
 391     TheModule.addTypeName(TypeName, Res);
 392     return Res;
 393   }
 394
 395   case Type::BlockPointer: {
 396     const QualType FTy = cast<BlockPointerType>(Ty).getPointeeType();
 397     llvm::OpaqueType *PointeeType = llvm::OpaqueType::get(getLLVMContext());
 398     PointersToResolve.push_back(std::make_pair(FTy, PointeeType));
 399     return llvm::PointerType::get(PointeeType, FTy.getAddressSpace());
 400   }
 401
 402   case Type::MemberPointer: {
 403     // FIXME: This is ABI dependent. We use the Itanium C++ ABI.
 404     // http://www.codesourcery.com/public/cxx-abi/abi.html#member-pointers
 405     // If we ever want to support other ABIs this needs to be abstracted.
 406
 407     QualType ETy = cast<MemberPointerType>(Ty).getPointeeType();
 408     const llvm::Type *PtrDiffTy =
 409         ConvertTypeRecursive(Context.getPointerDiffType());
 410     if (ETy->isFunctionType())
 411       return llvm::StructType::get(TheModule.getContext(), PtrDiffTy, PtrDiffTy,
 412                                    NULL);
 413     return PtrDiffTy;
 414   }
 415   }
 416
 417   // FIXME: implement.
 418   return llvm::OpaqueType::get(getLLVMContext());
 419 }
 420
 421 /// ConvertTagDeclType - Lay out a tagged decl type like struct or union or
 422 /// enum.
 423 const llvm::Type *CodeGenTypes::ConvertTagDeclType(const TagDecl *TD) {
 424   // TagDecl's are not necessarily unique, instead use the (clang)
 425   // type connected to the decl.
 426   const Type *Key =
 427     Context.getTagDeclType(TD).getTypePtr();
 428   llvm::DenseMap<const Type*, llvm::PATypeHolder>::iterator TDTI =
 429     TagDeclTypes.find(Key);
 430
 431   // If we've already compiled this tag type, use the previous definition.
 432   if (TDTI != TagDeclTypes.end())
 433     return TDTI->second;
 434
 435   // If this is still a forward declaration, just define an opaque
 436   // type to use for this tagged decl.
 437   if (!TD->isDefinition()) {
 438     llvm::Type *ResultType = llvm::OpaqueType::get(getLLVMContext());
 439     TagDeclTypes.insert(std::make_pair(Key, ResultType));
 440     return ResultType;
 441   }
 442
 443   // Okay, this is a definition of a type.  Compile the implementation now.
 444
 445   if (TD->isEnum())  // Don't bother storing enums in TagDeclTypes.
 446     return ConvertTypeRecursive(cast<EnumDecl>(TD)->getIntegerType());
 447
 448   // This decl could well be recursive.  In this case, insert an opaque
 449   // definition of this type, which the recursive uses will get.  We will then
 450   // refine this opaque version later.
 451
 452   // Create new OpaqueType now for later use in case this is a recursive
 453   // type.  This will later be refined to the actual type.
 454   llvm::PATypeHolder ResultHolder = llvm::OpaqueType::get(getLLVMContext());
 455   TagDeclTypes.insert(std::make_pair(Key, ResultHolder));
 456
 457   const RecordDecl *RD = cast<const RecordDecl>(TD);
 458
 459   // Force conversion of non-virtual base classes recursively.
 460   if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(TD)) {
 461     for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
 462          e = RD->bases_end(); i != e; ++i) {
 463       if (!i->isVirtual()) {
 464         const CXXRecordDecl *Base =
 465           cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
 466         ConvertTagDeclType(Base);
 467       }
 468     }
 469   }
 470
 471   // Layout fields.
 472   CGRecordLayout *Layout = ComputeRecordLayout(RD);
 473
 474   CGRecordLayouts[Key] = Layout;
 475   const llvm::Type *ResultType = Layout->getLLVMType();
 476
 477   // Refine our Opaque type to ResultType.  This can invalidate ResultType, so
 478   // make sure to read the result out of the holder.
 479   cast<llvm::OpaqueType>(ResultHolder.get())
 480     ->refineAbstractTypeTo(ResultType);
 481
 482   return ResultHolder.get();
 483 }
 484
 485 /// getCGRecordLayout - Return record layout info for the given llvm::Type.
 486 const CGRecordLayout &
 487 CodeGenTypes::getCGRecordLayout(const RecordDecl *TD) const {
 488   const Type *Key = Context.getTagDeclType(TD).getTypePtr();
 489   const CGRecordLayout *Layout = CGRecordLayouts.lookup(Key);
 490   assert(Layout && "Unable to find record layout information for type");
 491   return *Layout;
 492 }
 493
 494 bool CodeGenTypes::ContainsPointerToDataMember(QualType T) {
 495   // No need to check for member pointers when not compiling C++.
 496   if (!Context.getLangOptions().CPlusPlus)
 497     return false;
 498
 499   T = Context.getBaseElementType(T);
 500
 501   if (const RecordType *RT = T->getAs<RecordType>()) {
 502     const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
 503
 504     return ContainsPointerToDataMember(RD);
 505   }
 506
 507   if (const MemberPointerType *MPT = T->getAs<MemberPointerType>())
 508     return !MPT->getPointeeType()->isFunctionType();
 509
 510   return false;
 511 }
 512
 513 bool CodeGenTypes::ContainsPointerToDataMember(const CXXRecordDecl *RD) {
 514
 515   // FIXME: It would be better if there was a way to explicitly compute the
 516   // record layout instead of converting to a type.
 517   ConvertTagDeclType(RD);
 518
 519   const CGRecordLayout &Layout = getCGRecordLayout(RD);
 520   return Layout.containsPointerToDataMember();
 521 }