Make a major restructuring of the clang tree: introduce a top-level

lib dir and move all the libraries into it.  This follows the main
llvm tree, and allows the libraries to be built in parallel.  The
top level now enforces that all the libs are built before Driver,
but we don't care what order the libs are built in.  This speeds
up parallel builds, particularly incremental ones.


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@48402 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 551 insertions, 0 deletions

diff --git a/lib/Basic/IdentifierTable.cpp b/lib/Basic/IdentifierTable.cpp
new file mode 100644
index 0000000000..65e984a0f7
--- /dev/null
+++ b/lib/Basic/IdentifierTable.cpp
@@ -0,0 +1,551 @@
+//===--- IdentifierTable.cpp - Hash table for identifier lookup -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the IdentifierInfo, IdentifierVisitor, and
+// IdentifierTable interfaces.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Basic/IdentifierTable.h"
+#include "clang/Basic/LangOptions.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Bitcode/Serialize.h"
+#include "llvm/Bitcode/Deserialize.h"
+
+using namespace clang;
+
+//===----------------------------------------------------------------------===//
+// IdentifierInfo Implementation
+//===----------------------------------------------------------------------===//
+
+IdentifierInfo::IdentifierInfo() {
+  TokenID = tok::identifier;
+  ObjCID = tok::objc_not_keyword;
+  BuiltinID = 0;
+  HasMacro = false;
+  IsExtension = false;
+  IsPoisoned = false;
+  IsCPPOperatorKeyword = false;
+  FETokenInfo = 0;
+}
+
+//===----------------------------------------------------------------------===//
+// IdentifierTable Implementation
+//===----------------------------------------------------------------------===//
+
+IdentifierTable::IdentifierTable(const LangOptions &LangOpts)
+  // Start with space for 8K identifiers.
+  : HashTable(8192) {
+
+  // Populate the identifier table with info about keywords for the current
+  // language.
+  AddKeywords(LangOpts);
+}
+
+// This cstor is intended to be used only for serialization.
+IdentifierTable::IdentifierTable() : HashTable(8192) {}
+
+//===----------------------------------------------------------------------===//
+// Language Keyword Implementation
+//===----------------------------------------------------------------------===//
+
+/// AddKeyword - This method is used to associate a token ID with specific
+/// identifiers because they are language keywords.  This causes the lexer to
+/// automatically map matching identifiers to specialized token codes.
+///
+/// The C90/C99/CPP/CPP0x flags are set to 0 if the token should be
+/// enabled in the specified langauge, set to 1 if it is an extension
+/// in the specified language, and set to 2 if disabled in the
+/// specified language.
+static void AddKeyword(const char *Keyword, unsigned KWLen,
+                       tok::TokenKind TokenCode,
+                       int C90, int C99, int CXX, int CXX0x, int BoolSupport,
+                       const LangOptions &LangOpts, IdentifierTable &Table) {
+  int Flags = 0;
+  if (BoolSupport != 0) {
+    Flags = LangOpts.Boolean ? BoolSupport : 2;
+  } else if (LangOpts.CPlusPlus) {
+    Flags = LangOpts.CPlusPlus0x ? CXX0x : CXX;
+  } else if (LangOpts.C99) {
+    Flags = C99;
+  } else {
+    Flags = C90;
+  }
+  
+  // Don't add this keyword if disabled in this language or if an extension
+  // and extensions are disabled.
+  if (Flags + LangOpts.NoExtensions >= 2) return;
+  
+  IdentifierInfo &Info = Table.get(Keyword, Keyword+KWLen);
+  Info.setTokenID(TokenCode);
+  Info.setIsExtensionToken(Flags == 1);
+}
+
+static void AddAlias(const char *Keyword, unsigned KWLen,
+                     tok::TokenKind AliaseeID,
+                     const char *AliaseeKeyword, unsigned AliaseeKWLen,
+                     const LangOptions &LangOpts, IdentifierTable &Table) {
+  IdentifierInfo &AliasInfo = Table.get(Keyword, Keyword+KWLen);
+  IdentifierInfo &AliaseeInfo = Table.get(AliaseeKeyword,
+                                          AliaseeKeyword+AliaseeKWLen);
+  AliasInfo.setTokenID(AliaseeID);
+  AliasInfo.setIsExtensionToken(AliaseeInfo.isExtensionToken());
+}  
+
+/// AddCXXOperatorKeyword - Register a C++ operator keyword alternative
+/// representations.
+static void AddCXXOperatorKeyword(const char *Keyword, unsigned KWLen,
+                                  tok::TokenKind TokenCode,
+                                  IdentifierTable &Table) {
+  IdentifierInfo &Info = Table.get(Keyword, Keyword + KWLen);
+  Info.setTokenID(TokenCode);
+  Info.setIsCPlusPlusOperatorKeyword();
+}
+
+/// AddObjCKeyword - Register an Objective-C @keyword like "class" "selector" or 
+/// "property".
+static void AddObjCKeyword(tok::ObjCKeywordKind ObjCID, 
+                           const char *Name, unsigned NameLen,
+                           IdentifierTable &Table) {
+  Table.get(Name, Name+NameLen).setObjCKeywordID(ObjCID);
+}
+
+/// AddKeywords - Add all keywords to the symbol table.
+///
+void IdentifierTable::AddKeywords(const LangOptions &LangOpts) {
+  enum {
+    C90Shift = 0,
+    EXTC90   = 1 << C90Shift,
+    NOTC90   = 2 << C90Shift,
+    C99Shift = 2,
+    EXTC99   = 1 << C99Shift,
+    NOTC99   = 2 << C99Shift,
+    CPPShift = 4,
+    EXTCPP   = 1 << CPPShift,
+    NOTCPP   = 2 << CPPShift,
+    CPP0xShift = 6,
+    EXTCPP0x   = 1 << CPP0xShift,
+    NOTCPP0x   = 2 << CPP0xShift,
+    BoolShift = 8,
+    BOOLSUPPORT = 1 << BoolShift,
+    Mask     = 3
+  };
+  
+  // Add keywords and tokens for the current language.
+#define KEYWORD(NAME, FLAGS) \
+  AddKeyword(#NAME, strlen(#NAME), tok::kw_ ## NAME,  \
+             ((FLAGS) >> C90Shift) & Mask, \
+             ((FLAGS) >> C99Shift) & Mask, \
+             ((FLAGS) >> CPPShift) & Mask, \
+             ((FLAGS) >> CPP0xShift) & Mask, \
+             ((FLAGS) >> BoolShift) & Mask, LangOpts, *this);
+#define ALIAS(NAME, TOK) \
+  AddAlias(NAME, strlen(NAME), tok::kw_ ## TOK, #TOK, strlen(#TOK),  \
+           LangOpts, *this);
+#define CXX_KEYWORD_OPERATOR(NAME, ALIAS) \
+  if (LangOpts.CXXOperatorNames)          \
+    AddCXXOperatorKeyword(#NAME, strlen(#NAME), tok::ALIAS, *this);
+#define OBJC1_AT_KEYWORD(NAME) \
+  if (LangOpts.ObjC1)          \
+    AddObjCKeyword(tok::objc_##NAME, #NAME, strlen(#NAME), *this);
+#define OBJC2_AT_KEYWORD(NAME) \
+  if (LangOpts.ObjC2)          \
+    AddObjCKeyword(tok::objc_##NAME, #NAME, strlen(#NAME), *this);
+#include "clang/Basic/TokenKinds.def"
+}
+
+tok::PPKeywordKind IdentifierInfo::getPPKeywordID() const {
+  // We use a perfect hash function here involving the length of the keyword,
+  // the first and third character.  For preprocessor ID's there are no
+  // collisions (if there were, the switch below would complain about duplicate
+  // case values).  Note that this depends on 'if' being null terminated.
+  
+#define HASH(LEN, FIRST, THIRD) \
+  (LEN << 5) + (((FIRST-'a') + (THIRD-'a')) & 31)
+#define CASE(LEN, FIRST, THIRD, NAME) \
+  case HASH(LEN, FIRST, THIRD): \
+    return memcmp(Name, #NAME, LEN) ? tok::pp_not_keyword : tok::pp_ ## NAME
+    
+  unsigned Len = getLength();
+  if (Len < 2) return tok::pp_not_keyword;
+  const char *Name = getName();
+  switch (HASH(Len, Name[0], Name[2])) {
+  default: return tok::pp_not_keyword;
+  CASE( 2, 'i', '\0', if);
+  CASE( 4, 'e', 'i', elif);
+  CASE( 4, 'e', 's', else);
+  CASE( 4, 'l', 'n', line);
+  CASE( 4, 's', 'c', sccs);
+  CASE( 5, 'e', 'd', endif);
+  CASE( 5, 'e', 'r', error);
+  CASE( 5, 'i', 'e', ident);
+  CASE( 5, 'i', 'd', ifdef);
+  CASE( 5, 'u', 'd', undef);
+
+  CASE( 6, 'a', 's', assert);
+  CASE( 6, 'd', 'f', define);
+  CASE( 6, 'i', 'n', ifndef);
+  CASE( 6, 'i', 'p', import);
+  CASE( 6, 'p', 'a', pragma);
+
+  CASE( 7, 'd', 'f', defined);
+  CASE( 7, 'i', 'c', include);
+  CASE( 7, 'w', 'r', warning);
+
+  CASE( 8, 'u', 'a', unassert);
+  CASE(12, 'i', 'c', include_next);
+#undef CASE
+#undef HASH
+  }
+}
+
+//===----------------------------------------------------------------------===//
+// Stats Implementation
+//===----------------------------------------------------------------------===//
+
+/// PrintStats - Print statistics about how well the identifier table is doing
+/// at hashing identifiers.
+void IdentifierTable::PrintStats() const {
+  unsigned NumBuckets = HashTable.getNumBuckets();
+  unsigned NumIdentifiers = HashTable.getNumItems();
+  unsigned NumEmptyBuckets = NumBuckets-NumIdentifiers;
+  unsigned AverageIdentifierSize = 0;
+  unsigned MaxIdentifierLength = 0;
+  
+  // TODO: Figure out maximum times an identifier had to probe for -stats.
+  for (llvm::StringMap<IdentifierInfo, llvm::BumpPtrAllocator>::const_iterator
+       I = HashTable.begin(), E = HashTable.end(); I != E; ++I) {
+    unsigned IdLen = I->getKeyLength();
+    AverageIdentifierSize += IdLen;
+    if (MaxIdentifierLength < IdLen)
+      MaxIdentifierLength = IdLen;
+  }
+  
+  fprintf(stderr, "\n*** Identifier Table Stats:\n");
+  fprintf(stderr, "# Identifiers:   %d\n", NumIdentifiers);
+  fprintf(stderr, "# Empty Buckets: %d\n", NumEmptyBuckets);
+  fprintf(stderr, "Hash density (#identifiers per bucket): %f\n",
+          NumIdentifiers/(double)NumBuckets);
+  fprintf(stderr, "Ave identifier length: %f\n",
+          (AverageIdentifierSize/(double)NumIdentifiers));
+  fprintf(stderr, "Max identifier length: %d\n", MaxIdentifierLength);
+  
+  // Compute statistics about the memory allocated for identifiers.
+  HashTable.getAllocator().PrintStats();
+}
+
+//===----------------------------------------------------------------------===//
+// SelectorTable Implementation
+//===----------------------------------------------------------------------===//
+
+unsigned llvm::DenseMapInfo<clang::Selector>::getHashValue(clang::Selector S) {
+  return DenseMapInfo<void*>::getHashValue(S.getAsOpaquePtr());
+}
+
+
+/// MultiKeywordSelector - One of these variable length records is kept for each
+/// selector containing more than one keyword. We use a folding set
+/// to unique aggregate names (keyword selectors in ObjC parlance). Access to 
+/// this class is provided strictly through Selector.
+namespace clang {
+class MultiKeywordSelector : public llvm::FoldingSetNode {
+  friend SelectorTable* SelectorTable::CreateAndRegister(llvm::Deserializer&);
+  MultiKeywordSelector(unsigned nKeys) : NumArgs(nKeys) {}
+public:  
+  unsigned NumArgs;
+
+  // Constructor for keyword selectors.
+  MultiKeywordSelector(unsigned nKeys, IdentifierInfo **IIV) {
+    assert((nKeys > 1) && "not a multi-keyword selector");
+    NumArgs = nKeys;
+    
+    // Fill in the trailing keyword array.
+    IdentifierInfo **KeyInfo = reinterpret_cast<IdentifierInfo **>(this+1);
+    for (unsigned i = 0; i != nKeys; ++i)
+      KeyInfo[i] = IIV[i];
+  }  
+  
+  // getName - Derive the full selector name and return it.
+  std::string getName() const;
+    
+  unsigned getNumArgs() const { return NumArgs; }
+  
+  typedef IdentifierInfo *const *keyword_iterator;
+  keyword_iterator keyword_begin() const {
+    return reinterpret_cast<keyword_iterator>(this+1);
+  }
+  keyword_iterator keyword_end() const { 
+    return keyword_begin()+NumArgs; 
+  }
+  IdentifierInfo *getIdentifierInfoForSlot(unsigned i) const {
+    assert(i < NumArgs && "getIdentifierInfoForSlot(): illegal index");
+    return keyword_begin()[i];
+  }
+  static void Profile(llvm::FoldingSetNodeID &ID, 
+                      keyword_iterator ArgTys, unsigned NumArgs) {
+    ID.AddInteger(NumArgs);
+    for (unsigned i = 0; i != NumArgs; ++i)
+      ID.AddPointer(ArgTys[i]);
+  }
+  void Profile(llvm::FoldingSetNodeID &ID) {
+    Profile(ID, keyword_begin(), NumArgs);
+  }
+};
+} // end namespace clang.
+
+unsigned Selector::getNumArgs() const {
+  unsigned IIF = getIdentifierInfoFlag();
+  if (IIF == ZeroArg)
+    return 0;
+  if (IIF == OneArg)
+    return 1;
+  // We point to a MultiKeywordSelector (pointer doesn't contain any flags).
+  MultiKeywordSelector *SI = reinterpret_cast<MultiKeywordSelector *>(InfoPtr);
+  return SI->getNumArgs(); 
+}
+
+IdentifierInfo *Selector::getIdentifierInfoForSlot(unsigned argIndex) const {
+  if (IdentifierInfo *II = getAsIdentifierInfo()) {
+    assert(argIndex == 0 && "illegal keyword index");
+    return II;
+  }
+  // We point to a MultiKeywordSelector (pointer doesn't contain any flags).
+  MultiKeywordSelector *SI = reinterpret_cast<MultiKeywordSelector *>(InfoPtr);
+  return SI->getIdentifierInfoForSlot(argIndex);
+}
+
+std::string MultiKeywordSelector::getName() const {
+  std::string Result;
+  unsigned Length = 0;
+  for (keyword_iterator I = keyword_begin(), E = keyword_end(); I != E; ++I) {
+    if (*I)
+      Length += (*I)->getLength();
+    ++Length;  // :
+  }
+  
+  Result.reserve(Length);
+  
+  for (keyword_iterator I = keyword_begin(), E = keyword_end(); I != E; ++I) {
+    if (*I)
+      Result.insert(Result.end(), (*I)->getName(),
+                    (*I)->getName()+(*I)->getLength());
+    Result.push_back(':');
+  }
+  
+  return Result;
+}
+
+std::string Selector::getName() const {
+  if (IdentifierInfo *II = getAsIdentifierInfo()) {
+    if (getNumArgs() == 0)
+      return II->getName();
+    
+    std::string Res = II->getName();
+    Res += ":";
+    return Res;
+  }
+  
+  // We have a multiple keyword selector (no embedded flags).
+  return reinterpret_cast<MultiKeywordSelector *>(InfoPtr)->getName();
+}
+
+
+Selector SelectorTable::getSelector(unsigned nKeys, IdentifierInfo **IIV) {
+  if (nKeys < 2)
+    return Selector(IIV[0], nKeys);
+  
+  llvm::FoldingSet<MultiKeywordSelector> *SelTab;
+  
+  SelTab = static_cast<llvm::FoldingSet<MultiKeywordSelector> *>(Impl);
+    
+  // Unique selector, to guarantee there is one per name.
+  llvm::FoldingSetNodeID ID;
+  MultiKeywordSelector::Profile(ID, IIV, nKeys);
+
+  void *InsertPos = 0;
+  if (MultiKeywordSelector *SI = SelTab->FindNodeOrInsertPos(ID, InsertPos))
+    return Selector(SI);
+  
+  // MultiKeywordSelector objects are not allocated with new because they have a
+  // variable size array (for parameter types) at the end of them.
+  MultiKeywordSelector *SI = 
+    (MultiKeywordSelector*)malloc(sizeof(MultiKeywordSelector) + 
+                                  nKeys*sizeof(IdentifierInfo *));
+  new (SI) MultiKeywordSelector(nKeys, IIV);
+  SelTab->InsertNode(SI, InsertPos);
+  return Selector(SI);
+}
+
+SelectorTable::SelectorTable() {
+  Impl = new llvm::FoldingSet<MultiKeywordSelector>;
+}
+
+SelectorTable::~SelectorTable() {
+  delete static_cast<llvm::FoldingSet<MultiKeywordSelector> *>(Impl);
+}
+
+//===----------------------------------------------------------------------===//
+// Serialization for IdentifierInfo and IdentifierTable.
+//===----------------------------------------------------------------------===//
+
+void IdentifierInfo::Emit(llvm::Serializer& S) const {
+  S.EmitInt(getTokenID());
+  S.EmitInt(getBuiltinID());
+  S.EmitInt(getObjCKeywordID());  
+  S.EmitBool(hasMacroDefinition());
+  S.EmitBool(isExtensionToken());
+  S.EmitBool(isPoisoned());
+  S.EmitBool(isCPlusPlusOperatorKeyword());
+  // FIXME: FETokenInfo
+}
+
+void IdentifierInfo::Read(llvm::Deserializer& D) {
+  setTokenID((tok::TokenKind) D.ReadInt());
+  setBuiltinID(D.ReadInt());  
+  setObjCKeywordID((tok::ObjCKeywordKind) D.ReadInt());  
+  setHasMacroDefinition(D.ReadBool());
+  setIsExtensionToken(D.ReadBool());
+  setIsPoisoned(D.ReadBool());
+  setIsCPlusPlusOperatorKeyword(D.ReadBool());
+  // FIXME: FETokenInfo
+}
+
+void IdentifierTable::Emit(llvm::Serializer& S) const {
+  S.EnterBlock();
+  
+  S.EmitPtr(this);
+  
+  for (iterator I=begin(), E=end(); I != E; ++I) {
+    const char* Key = I->getKeyData();
+    const IdentifierInfo* Info = &I->getValue();
+    
+    bool KeyRegistered = S.isRegistered(Key);
+    bool InfoRegistered = S.isRegistered(Info);
+    
+    if (KeyRegistered || InfoRegistered) {
+      // These acrobatics are so that we don't incur the cost of registering
+      // a pointer with the backpatcher during deserialization if nobody
+      // references the object.
+      S.EmitPtr(InfoRegistered ? Info : NULL);
+      S.EmitPtr(KeyRegistered ? Key : NULL);
+      S.EmitCStr(Key);
+      S.Emit(*Info);
+    }
+  }
+  
+  S.ExitBlock();
+}
+
+IdentifierTable* IdentifierTable::CreateAndRegister(llvm::Deserializer& D) {
+  llvm::Deserializer::Location BLoc = D.getCurrentBlockLocation();
+
+  std::vector<char> buff;
+  buff.reserve(200);
+
+  IdentifierTable* t = new IdentifierTable();
+  D.RegisterPtr(t);  
+  
+  while (!D.FinishedBlock(BLoc)) {
+    llvm::SerializedPtrID InfoPtrID = D.ReadPtrID();
+    llvm::SerializedPtrID KeyPtrID = D.ReadPtrID();
+    
+    D.ReadCStr(buff);
+    
+    llvm::StringMapEntry<IdentifierInfo>& Entry =
+      t->HashTable.GetOrCreateValue(&buff[0],&buff[0]+buff.size());
+    
+    D.Read(Entry.getValue());
+    
+    if (InfoPtrID)
+      D.RegisterRef(InfoPtrID,Entry.getValue());
+    
+    if (KeyPtrID)
+      D.RegisterPtr(KeyPtrID,Entry.getKeyData());
+  }
+  
+  return t;
+}
+
+//===----------------------------------------------------------------------===//
+// Serialization for Selector and SelectorTable.
+//===----------------------------------------------------------------------===//
+
+void Selector::Emit(llvm::Serializer& S) const {
+  S.EmitInt(getIdentifierInfoFlag());
+  S.EmitPtr(reinterpret_cast<void*>(InfoPtr & ~ArgFlags));
+}
+
+Selector Selector::ReadVal(llvm::Deserializer& D) {
+  unsigned flag = D.ReadInt();
+  
+  uintptr_t ptr;  
+  D.ReadUIntPtr(ptr,false); // No backpatching.
+  
+  return Selector(ptr | flag);
+}
+
+void SelectorTable::Emit(llvm::Serializer& S) const {
+  typedef llvm::FoldingSet<MultiKeywordSelector>::iterator iterator;
+  llvm::FoldingSet<MultiKeywordSelector> *SelTab;
+  SelTab = static_cast<llvm::FoldingSet<MultiKeywordSelector> *>(Impl);
+  
+  S.EnterBlock();
+  
+  S.EmitPtr(this);
+  
+  for (iterator I=SelTab->begin(), E=SelTab->end(); I != E; ++I) {
+    if (!S.isRegistered(&*I))
+      continue;
+    
+    S.FlushRecord(); // Start a new record.
+
+    S.EmitPtr(&*I);
+    S.EmitInt(I->getNumArgs());
+
+    for (MultiKeywordSelector::keyword_iterator KI = I->keyword_begin(),
+         KE = I->keyword_end(); KI != KE; ++KI)
+      S.EmitPtr(*KI);
+  }
+  
+  S.ExitBlock();
+}
+
+SelectorTable* SelectorTable::CreateAndRegister(llvm::Deserializer& D) {
+  llvm::Deserializer::Location BLoc = D.getCurrentBlockLocation();
+  
+  SelectorTable* t = new SelectorTable();
+  D.RegisterPtr(t);
+  
+  llvm::FoldingSet<MultiKeywordSelector>& SelTab =
+    *static_cast<llvm::FoldingSet<MultiKeywordSelector>*>(t->Impl);
+
+  while (!D.FinishedBlock(BLoc)) {
+
+    llvm::SerializedPtrID PtrID = D.ReadPtrID();
+    unsigned nKeys = D.ReadInt();
+    
+    MultiKeywordSelector *SI = 
+      (MultiKeywordSelector*)malloc(sizeof(MultiKeywordSelector) + 
+                                    nKeys*sizeof(IdentifierInfo *));
+
+    new (SI) MultiKeywordSelector(nKeys);
+    
+    D.RegisterPtr(PtrID,SI);
+
+    IdentifierInfo **KeyInfo = reinterpret_cast<IdentifierInfo **>(SI+1);
+
+    for (unsigned i = 0; i != nKeys; ++i)
+      D.ReadPtr(KeyInfo[i],false);
+    
+    SelTab.GetOrInsertNode(SI);
+  }
+  
+  return t;
+}