contrib/llvm/tools/lld/include/lld/Core/SymbolTable.h

   1 //===- Core/SymbolTable.h - Main Symbol Table -----------------------------===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef LLD_CORE_SYMBOL_TABLE_H
  11 #define LLD_CORE_SYMBOL_TABLE_H
  12
  13 #include "lld/Core/LLVM.h"
  14 #include "llvm/ADT/DenseSet.h"
  15 #include "llvm/ADT/StringExtras.h"
  16 #include <cstring>
  17 #include <map>
  18 #include <vector>
  19
  20 namespace lld {
  21
  22 class AbsoluteAtom;
  23 class Atom;
  24 class DefinedAtom;
  25 class LinkingContext;
  26 class ResolverOptions;
  27 class SharedLibraryAtom;
  28 class UndefinedAtom;
  29
  30 /// \brief The SymbolTable class is responsible for coalescing atoms.
  31 ///
  32 /// All atoms coalescable by-name or by-content should be added.
  33 /// The method replacement() can be used to find the replacement atom
  34 /// if an atom has been coalesced away.
  35 class SymbolTable {
  36 public:
  37   /// @brief add atom to symbol table
  38   bool add(const DefinedAtom &);
  39
  40   /// @brief add atom to symbol table
  41   bool add(const UndefinedAtom &);
  42
  43   /// @brief add atom to symbol table
  44   bool add(const SharedLibraryAtom &);
  45
  46   /// @brief add atom to symbol table
  47   bool add(const AbsoluteAtom &);
  48
  49   /// @brief checks if name is in symbol table and if so atom is not
  50   ///        UndefinedAtom
  51   bool isDefined(StringRef sym);
  52
  53   /// @brief returns atom in symbol table for specified name (or nullptr)
  54   const Atom *findByName(StringRef sym);
  55
  56   /// @brief returns vector of remaining UndefinedAtoms
  57   std::vector<const UndefinedAtom *> undefines();
  58
  59   /// returns vector of tentative definitions
  60   std::vector<StringRef> tentativeDefinitions();
  61
  62   /// @brief add atom to replacement table
  63   void addReplacement(const Atom *replaced, const Atom *replacement);
  64
  65   /// @brief if atom has been coalesced away, return replacement, else return atom
  66   const Atom *replacement(const Atom *);
  67
  68   /// @brief if atom has been coalesced away, return true
  69   bool isCoalescedAway(const Atom *);
  70
  71 private:
  72   typedef llvm::DenseMap<const Atom *, const Atom *> AtomToAtom;
  73
  74   struct StringRefMappingInfo {
  75     static StringRef getEmptyKey() { return StringRef(); }
  76     static StringRef getTombstoneKey() { return StringRef(" ", 1); }
  77     static unsigned getHashValue(StringRef const val) {
  78       return llvm::HashString(val);
  79     }
  80     static bool isEqual(StringRef const lhs, StringRef const rhs) {
  81       return lhs.equals(rhs);
  82     }
  83   };
  84   typedef llvm::DenseMap<StringRef, const Atom *,
  85                                            StringRefMappingInfo> NameToAtom;
  86
  87   struct AtomMappingInfo {
  88     static const DefinedAtom * getEmptyKey() { return nullptr; }
  89     static const DefinedAtom * getTombstoneKey() { return (DefinedAtom*)(-1); }
  90     static unsigned getHashValue(const DefinedAtom * const Val);
  91     static bool isEqual(const DefinedAtom * const LHS,
  92                         const DefinedAtom * const RHS);
  93   };
  94   typedef llvm::DenseSet<const DefinedAtom*, AtomMappingInfo> AtomContentSet;
  95
  96   bool addByName(const Atom &);
  97   bool addByContent(const DefinedAtom &);
  98
  99   AtomToAtom _replacedAtoms;
 100   NameToAtom _nameTable;
 101   AtomContentSet _contentTable;
 102 };
 103
 104 } // namespace lld
 105
 106 #endif // LLD_CORE_SYMBOL_TABLE_H