contrib/llvm/tools/clang/lib/CodeGen/MicrosoftVBTables.h

   1 //===--- MicrosoftVBTables.h - Virtual Base Table Emission ----------------===//
   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 class generates data about MSVC virtual base tables.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/AST/BaseSubobject.h"
  15 #include "clang/Basic/LLVM.h"
  16 #include "llvm/ADT/SmallPtrSet.h"
  17 #include "llvm/ADT/ArrayRef.h"
  18 #include "llvm/IR/GlobalVariable.h"
  19 #include <vector>
  20
  21 namespace clang {
  22
  23 class ASTRecordLayout;
  24
  25 namespace CodeGen {
  26
  27 class CodeGenModule;
  28
  29 struct VBTableInfo {
  30   VBTableInfo(const CXXRecordDecl *ReusingBase, BaseSubobject VBPtrSubobject,
  31               llvm::GlobalVariable *GV)
  32     : ReusingBase(ReusingBase), VBPtrSubobject(VBPtrSubobject), GV(GV) { }
  33
  34   /// The vbtable will hold all of the virtual bases of ReusingBase.  This may
  35   /// or may not be the same class as VBPtrSubobject.Base.  A derived class will
  36   /// reuse the vbptr of the first non-virtual base subobject that has one.
  37   const CXXRecordDecl *ReusingBase;
  38
  39   /// The vbptr is stored inside this subobject.
  40   BaseSubobject VBPtrSubobject;
  41
  42   /// The GlobalVariable for this vbtable.
  43   llvm::GlobalVariable *GV;
  44
  45   /// \brief Emits a definition for GV by setting it's initializer.
  46   void EmitVBTableDefinition(CodeGenModule &CGM, const CXXRecordDecl *RD,
  47                              llvm::GlobalVariable::LinkageTypes Linkage) const;
  48 };
  49
  50 // These are embedded in a DenseMap and the elements are large, so we don't want
  51 // SmallVector.
  52 typedef std::vector<VBTableInfo> VBTableVector;
  53
  54 struct VBTablePath;
  55
  56 typedef llvm::SmallVector<VBTablePath *, 6> VBTablePathVector;
  57
  58 /// Produces MSVC-compatible vbtable data.  The symbols produced by this builder
  59 /// match those produced by MSVC 2012, which is different from MSVC 2010.
  60 ///
  61 /// Unlike Itanium, which uses only one vtable per class, MSVC uses a different
  62 /// symbol for every "address point" installed in base subobjects.  As a result,
  63 /// we have to compute unique symbols for every table.  Since there can be
  64 /// multiple non-virtual base subobjects of the same class, combining the most
  65 /// derived class with the base containing the vtable is insufficient.  The most
  66 /// trivial algorithm would be to mangle in the entire path from base to most
  67 /// derived, but that would be too easy and would create unnecessarily large
  68 /// symbols.  ;)
  69 ///
  70 /// MSVC 2012 appears to minimize the vbtable names using the following
  71 /// algorithm.  First, walk the class hierarchy in the usual order, depth first,
  72 /// left to right, to find all of the subobjects which contain a vbptr field.
  73 /// Visiting each class node yields a list of inheritance paths to vbptrs.  Each
  74 /// record with a vbptr creates an initially empty path.
  75 ///
  76 /// To combine paths from child nodes, the paths are compared to check for
  77 /// ambiguity.  Paths are "ambiguous" if multiple paths have the same set of
  78 /// components in the same order.  Each group of ambiguous paths is extended by
  79 /// appending the class of the base from which it came.  If the current class
  80 /// node produced an ambiguous path, its path is extended with the current class.
  81 /// After extending paths, MSVC again checks for ambiguity, and extends any
  82 /// ambiguous path which wasn't already extended.  Because each node yields an
  83 /// unambiguous set of paths, MSVC doesn't need to extend any path more than once
  84 /// to produce an unambiguous set of paths.
  85 ///
  86 /// The VBTableBuilder class attempts to implement this algorithm by repeatedly
  87 /// bucketing paths together by sorting them.
  88 ///
  89 /// TODO: Presumably vftables use the same algorithm.
  90 ///
  91 /// TODO: Implement the MSVC 2010 name mangling scheme to avoid emitting
  92 /// duplicate vbtables with different symbols.
  93 class VBTableBuilder {
  94 public:
  95   VBTableBuilder(CodeGenModule &CGM, const CXXRecordDecl *MostDerived);
  96
  97   void enumerateVBTables(VBTableVector &VBTables);
  98
  99 private:
 100   bool hasVBPtr(const CXXRecordDecl *RD);
 101
 102   llvm::GlobalVariable *getAddrOfVBTable(const CXXRecordDecl *ReusingBase,
 103                                       ArrayRef<const CXXRecordDecl *> BasePath);
 104
 105   /// Enumerates paths to bases with vbptrs.  The paths elements are compressed
 106   /// to contain only the classes necessary to form an unambiguous path.
 107   void findUnambiguousPaths(const CXXRecordDecl *ReusingBase,
 108                             BaseSubobject CurSubobject,
 109                             VBTablePathVector &Paths);
 110
 111   void extendPath(VBTablePath *Info, bool SecondPass);
 112
 113   bool rebucketPaths(VBTablePathVector &Paths, size_t PathsStart,
 114                      bool SecondPass = false);
 115
 116   CodeGenModule &CGM;
 117
 118   const CXXRecordDecl *MostDerived;
 119
 120   /// Caches the layout of the most derived class.
 121   const ASTRecordLayout &DerivedLayout;
 122
 123   /// Set of vbases to avoid re-visiting the same vbases.
 124   llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen;
 125 };
 126
 127 } // namespace CodeGen
 128
 129 } // namespace clang