1//===--- VTTBuilder.cpp - C++ VTT layout builder --------------------------===//
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 contains code dealing with generation of the layout of virtual table
11// tables (VTT).
12//
13//===----------------------------------------------------------------------===//
14
15#include "clang/AST/VTTBuilder.h"
16#include "clang/AST/ASTContext.h"
17#include "clang/AST/CXXInheritance.h"
18#include "clang/AST/RecordLayout.h"
19#include "clang/Basic/TargetInfo.h"
20#include "llvm/Support/Format.h"
21#include <algorithm>
22#include <cstdio>
23
24using namespace clang;
25
26#define DUMP_OVERRIDERS 0
27
28VTTBuilder::VTTBuilder(ASTContext &Ctx,
29                       const CXXRecordDecl *MostDerivedClass,
30                       bool GenerateDefinition)
31  : Ctx(Ctx), MostDerivedClass(MostDerivedClass),
32  MostDerivedClassLayout(Ctx.getASTRecordLayout(MostDerivedClass)),
33    GenerateDefinition(GenerateDefinition) {
34  // Lay out this VTT.
35  LayoutVTT(BaseSubobject(MostDerivedClass, CharUnits::Zero()),
36            /*BaseIsVirtual=*/false);
37}
38
39void VTTBuilder::AddVTablePointer(BaseSubobject Base, uint64_t VTableIndex,
40                                  const CXXRecordDecl *VTableClass) {
41  // Store the vtable pointer index if we're generating the primary VTT.
42  if (VTableClass == MostDerivedClass) {
43    assert(!SecondaryVirtualPointerIndices.count(Base) &&
44           "A virtual pointer index already exists for this base subobject!");
45    SecondaryVirtualPointerIndices[Base] = VTTComponents.size();
46  }
47
48  if (!GenerateDefinition) {
49    VTTComponents.push_back(VTTComponent());
50    return;
51  }
52
53  VTTComponents.push_back(VTTComponent(VTableIndex, Base));
54}
55
56void VTTBuilder::LayoutSecondaryVTTs(BaseSubobject Base) {
57  const CXXRecordDecl *RD = Base.getBase();
58
59  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
60       E = RD->bases_end(); I != E; ++I) {
61
62    // Don't layout virtual bases.
63    if (I->isVirtual())
64        continue;
65
66    const CXXRecordDecl *BaseDecl =
67      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
68
69    const ASTRecordLayout &Layout = Ctx.getASTRecordLayout(RD);
70    CharUnits BaseOffset = Base.getBaseOffset() +
71      Layout.getBaseClassOffset(BaseDecl);
72
73    // Layout the VTT for this base.
74    LayoutVTT(BaseSubobject(BaseDecl, BaseOffset), /*BaseIsVirtual=*/false);
75  }
76}
77
78void
79VTTBuilder::LayoutSecondaryVirtualPointers(BaseSubobject Base,
80                                           bool BaseIsMorallyVirtual,
81                                           uint64_t VTableIndex,
82                                           const CXXRecordDecl *VTableClass,
83                                           VisitedVirtualBasesSetTy &VBases) {
84  const CXXRecordDecl *RD = Base.getBase();
85
86  // We're not interested in bases that don't have virtual bases, and not
87  // morally virtual bases.
88  if (!RD->getNumVBases() && !BaseIsMorallyVirtual)
89    return;
90
91  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
92       E = RD->bases_end(); I != E; ++I) {
93    const CXXRecordDecl *BaseDecl =
94      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
95
96    // Itanium C++ ABI 2.6.2:
97    //   Secondary virtual pointers are present for all bases with either
98    //   virtual bases or virtual function declarations overridden along a
99    //   virtual path.
100    //
101    // If the base class is not dynamic, we don't want to add it, nor any
102    // of its base classes.
103    if (!BaseDecl->isDynamicClass())
104      continue;
105
106    bool BaseDeclIsMorallyVirtual = BaseIsMorallyVirtual;
107    bool BaseDeclIsNonVirtualPrimaryBase = false;
108    CharUnits BaseOffset;
109    if (I->isVirtual()) {
110      // Ignore virtual bases that we've already visited.
111      if (!VBases.insert(BaseDecl))
112        continue;
113
114      BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
115      BaseDeclIsMorallyVirtual = true;
116    } else {
117      const ASTRecordLayout &Layout = Ctx.getASTRecordLayout(RD);
118
119      BaseOffset = Base.getBaseOffset() +
120        Layout.getBaseClassOffset(BaseDecl);
121
122      if (!Layout.isPrimaryBaseVirtual() &&
123          Layout.getPrimaryBase() == BaseDecl)
124        BaseDeclIsNonVirtualPrimaryBase = true;
125    }
126
127    // Itanium C++ ABI 2.6.2:
128    //   Secondary virtual pointers: for each base class X which (a) has virtual
129    //   bases or is reachable along a virtual path from D, and (b) is not a
130    //   non-virtual primary base, the address of the virtual table for X-in-D
131    //   or an appropriate construction virtual table.
132    if (!BaseDeclIsNonVirtualPrimaryBase &&
133        (BaseDecl->getNumVBases() || BaseDeclIsMorallyVirtual)) {
134      // Add the vtable pointer.
135      AddVTablePointer(BaseSubobject(BaseDecl, BaseOffset), VTableIndex,
136                       VTableClass);
137    }
138
139    // And lay out the secondary virtual pointers for the base class.
140    LayoutSecondaryVirtualPointers(BaseSubobject(BaseDecl, BaseOffset),
141                                   BaseDeclIsMorallyVirtual, VTableIndex,
142                                   VTableClass, VBases);
143  }
144}
145
146void
147VTTBuilder::LayoutSecondaryVirtualPointers(BaseSubobject Base,
148                                           uint64_t VTableIndex) {
149  VisitedVirtualBasesSetTy VBases;
150  LayoutSecondaryVirtualPointers(Base, /*BaseIsMorallyVirtual=*/false,
151                                 VTableIndex, Base.getBase(), VBases);
152}
153
154void VTTBuilder::LayoutVirtualVTTs(const CXXRecordDecl *RD,
155                                   VisitedVirtualBasesSetTy &VBases) {
156  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
157       E = RD->bases_end(); I != E; ++I) {
158    const CXXRecordDecl *BaseDecl =
159      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
160
161    // Check if this is a virtual base.
162    if (I->isVirtual()) {
163      // Check if we've seen this base before.
164      if (!VBases.insert(BaseDecl))
165        continue;
166
167      CharUnits BaseOffset =
168        MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
169
170      LayoutVTT(BaseSubobject(BaseDecl, BaseOffset), /*BaseIsVirtual=*/true);
171    }
172
173    // We only need to layout virtual VTTs for this base if it actually has
174    // virtual bases.
175    if (BaseDecl->getNumVBases())
176      LayoutVirtualVTTs(BaseDecl, VBases);
177  }
178}
179
180void VTTBuilder::LayoutVTT(BaseSubobject Base, bool BaseIsVirtual) {
181  const CXXRecordDecl *RD = Base.getBase();
182
183  // Itanium C++ ABI 2.6.2:
184  //   An array of virtual table addresses, called the VTT, is declared for
185  //   each class type that has indirect or direct virtual base classes.
186  if (RD->getNumVBases() == 0)
187    return;
188
189  bool IsPrimaryVTT = Base.getBase() == MostDerivedClass;
190
191  if (!IsPrimaryVTT) {
192    // Remember the sub-VTT index.
193    SubVTTIndicies[Base] = VTTComponents.size();
194  }
195
196  uint64_t VTableIndex = VTTVTables.size();
197  VTTVTables.push_back(VTTVTable(Base, BaseIsVirtual));
198
199  // Add the primary vtable pointer.
200  AddVTablePointer(Base, VTableIndex, RD);
201
202  // Add the secondary VTTs.
203  LayoutSecondaryVTTs(Base);
204
205  // Add the secondary virtual pointers.
206  LayoutSecondaryVirtualPointers(Base, VTableIndex);
207
208  // If this is the primary VTT, we want to lay out virtual VTTs as well.
209  if (IsPrimaryVTT) {
210    VisitedVirtualBasesSetTy VBases;
211    LayoutVirtualVTTs(Base.getBase(), VBases);
212  }
213}
214