path: root/lib/AST/RecordLayoutBuilder.cpp

//=== ASTRecordLayoutBuilder.cpp - Helper class for building record layouts ==//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#include "RecordLayoutBuilder.h"

#include "clang/AST/Attr.h"
#include "clang/AST/Decl.h"
#include "clang/AST/DeclCXX.h"
#include "clang/AST/DeclObjC.h"
#include "clang/AST/Expr.h"
#include "clang/AST/RecordLayout.h"
#include "clang/Basic/TargetInfo.h"
#include <llvm/ADT/SmallSet.h>
#include <llvm/Support/MathExtras.h>

using namespace clang;

ASTRecordLayoutBuilder::ASTRecordLayoutBuilder(ASTContext &Ctx) 
  : Ctx(Ctx), Size(0), Alignment(8), Packed(false), MaxFieldAlignment(0), 
  NextOffset(0), IsUnion(false), NonVirtualSize(0), NonVirtualAlignment(8) {}

/// LayoutVtable - Lay out the vtable and set PrimaryBase.
void ASTRecordLayoutBuilder::LayoutVtable(const CXXRecordDecl *RD) {
  // FIXME: audit indirect virtual bases
  if (!RD->isPolymorphic() && !RD->getNumVBases()) {
    // There is no primary base in this case.
    setPrimaryBase(0, false);
    return;
  }

  SelectPrimaryBase(RD);
  if (PrimaryBase == 0) {
    int AS = 0;
    UpdateAlignment(Ctx.Target.getPointerAlign(AS));
    Size += Ctx.Target.getPointerWidth(AS);
    NextOffset = Size;
  }
}

void 
ASTRecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD) {
  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
       e = RD->bases_end(); i != e; ++i) {
    if (!i->isVirtual()) {
      const CXXRecordDecl *Base = 
        cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
      // Skip the PrimaryBase here, as it is laid down first.
      if (Base != PrimaryBase)
        LayoutBaseNonVirtually(Base);
    }
  }
}

// Helper routines related to the abi definition from:
//   http://www.codesourcery.com/public/cxx-abi/abi.html
//
/// IsNearlyEmpty - Indicates when a class has a vtable pointer, but
/// no other data.
bool ASTRecordLayoutBuilder::IsNearlyEmpty(const CXXRecordDecl *RD) {
  // FIXME: Audit the corners
  if (!RD->isDynamicClass())
    return false;
  const ASTRecordLayout &BaseInfo = Ctx.getASTRecordLayout(RD);
  if (BaseInfo.getNonVirtualSize() == Ctx.Target.getPointerWidth(0))
    return true;
  return false;
}

void ASTRecordLayoutBuilder::SelectPrimaryForBase(const CXXRecordDecl *RD,
                    llvm::SmallSet<const CXXRecordDecl*, 32> &IndirectPrimary) {
  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
       e = RD->bases_end(); i != e; ++i) {
    if (!i->isVirtual()) {
      const CXXRecordDecl *Base = 
        cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
      // Only bases with virtual bases participate in computing the
      // indirect primary base classes.
      // FIXME: audit indirect virtual bases
      if (Base->getNumVBases() == 0)
        return;
      // FIXME: This information is recomputed a whole lot, cache it instead.
      SelectPrimaryBase(Base);
      IndirectPrimary.insert(PrimaryBase);
      SelectPrimaryForBase(Base, IndirectPrimary);
    }
  }
}

/// SelectPrimaryBase - Selects the primary base for the given class and
/// records that with setPrimaryBase.
void ASTRecordLayoutBuilder::SelectPrimaryBase(const CXXRecordDecl *RD) {
  // The primary base is the first non-virtual indirect or direct base class,
  // if one exists.
  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
       e = RD->bases_end(); i != e; ++i) {
    if (!i->isVirtual()) {
      const CXXRecordDecl *Base = 
        cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
      if (Base->isDynamicClass()) {
        setPrimaryBase(Base, false);
        return;
      }
    }
  }

  // Otherwise, it is the first nearly empty virtual base that is not an
  // indirect primary base class, if one exists.

  // If we have no virtual bases at this point, bail out as the searching below
  // is expensive.
  // FIXME: audit indirect virtual bases
  if (RD->getNumVBases() == 0) {
    setPrimaryBase(0, false);
    return;
  }

  // First, we compute all the primary bases for all of our direct and indirect
  // non-virtual bases, and record all their primary base classes.
  const CXXRecordDecl *FirstPrimary = 0;
  llvm::SmallSet<const CXXRecordDecl*, 32> IndirectPrimary;
  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
       e = RD->bases_end(); i != e; ++i) {
    if (!i->isVirtual()) {
      const CXXRecordDecl *Base = 
        cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
      SelectPrimaryForBase(Base, IndirectPrimary);
    }
  }

  // Then we can search for the first nearly empty virtual base itself.
  // FIXME: audit indirect virtual bases
  for (CXXRecordDecl::base_class_const_iterator i = RD->vbases_begin(),
       e = RD->vbases_end(); i != e; ++i) {
    const CXXRecordDecl *Base = 
      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
    if (IsNearlyEmpty(Base)) {
      if (FirstPrimary==0)
        FirstPrimary = Base;
      if (!IndirectPrimary.count(Base)) {
        setPrimaryBase(Base, true);
        return;
      }
    }
  }

  // Otherwise if is the first nearly empty virtual base, if one exists,
  // otherwise there is no primary base class.
  setPrimaryBase(FirstPrimary, true);
  return;
}

void ASTRecordLayoutBuilder::LayoutVirtualBase(const CXXRecordDecl *RD) {
  LayoutBaseNonVirtually(RD);
}

void ASTRecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *RD) {
  // FIXME: audit indirect virtual bases
  for (CXXRecordDecl::base_class_const_iterator i = RD->vbases_begin(),
         e = RD->vbases_end(); i != e; ++i) {
    const CXXRecordDecl *Base = 
      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
    if (Base != PrimaryBase)
      LayoutVirtualBase(Base);
  }
}

void ASTRecordLayoutBuilder::LayoutBaseNonVirtually(const CXXRecordDecl *RD) {
  const ASTRecordLayout &BaseInfo = Ctx.getASTRecordLayout(RD);
    assert(BaseInfo.getDataSize() > 0 && 
           "FIXME: Handle empty classes.");
  
  unsigned BaseAlign = BaseInfo.getNonVirtualAlign();
  uint64_t BaseSize = BaseInfo.getNonVirtualSize();
  
  // Round up the current record size to the base's alignment boundary.
  Size = (Size + (BaseAlign-1)) & ~(BaseAlign-1);

  // Add base class offsets.
  Bases.push_back(RD);
  BaseOffsets.push_back(Size);

  // Reserve space for this base.
  Size += BaseSize;
  
  // Remember the next available offset.
  NextOffset = Size;
  
  // Remember max struct/class alignment.
  UpdateAlignment(BaseAlign);
}

void ASTRecordLayoutBuilder::Layout(const RecordDecl *D) {
  IsUnion = D->isUnion();

  Packed = D->hasAttr<PackedAttr>();

  // The #pragma pack attribute specifies the maximum field alignment.
  if (const PragmaPackAttr *PPA = D->getAttr<PragmaPackAttr>())
    MaxFieldAlignment = PPA->getAlignment();
  
  if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
    UpdateAlignment(AA->getAlignment());

  // If this is a C++ class, lay out the nonvirtual bases.
  const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D);
  if (RD) {
    LayoutVtable(RD);
    // PrimaryBase goes first.
    if (PrimaryBase)
      LayoutBaseNonVirtually(PrimaryBase);
    LayoutNonVirtualBases(RD);
  }

  LayoutFields(D);
  
  NonVirtualSize = Size;
  NonVirtualAlignment = Alignment;

  if (RD)
    LayoutVirtualBases(RD);

  // Finally, round the size of the total struct up to the alignment of the
  // struct itself.
  FinishLayout();
}

void ASTRecordLayoutBuilder::Layout(const ObjCInterfaceDecl *D,
                                    const ObjCImplementationDecl *Impl) {
  if (ObjCInterfaceDecl *SD = D->getSuperClass()) {
    const ASTRecordLayout