[cfe-dev] RFC: Name lookup overhaul

Chris Lattner clattner at apple.com
Wed Dec 10 22:23:52 PST 2008


On Dec 10, 2008, at 4:08 PM, Douglas Gregor wrote:

> This patch is a follow-on to my qualified/unqualified name lookup  
> patch. It unifies the name-lookup mechanisms used in various parts  
> of the AST and separates lexical name lookup from qualified name  
> lookup. In particular, the patch:

Yay again :)

> Comments greatly appreciated! I plan to commit this some time  
> tomorrow unless I hear howls of protest.

First howl: if you have to gzip your patch, it is too big :).  In the  
future, please try to break things up into smaller pieces.  This is  
important for review and also tracking changes over time: identifying  
which patch caused a correctness or perf regression.

Please *commit* this patch before addressing any follow up below, and  
address them with subsequent patches.


+++ include/clang/AST/DeclBase.h	(working copy)
@@ -257,10 +260,27 @@
    /// DeclKind - This indicates which class this is.
    Decl::Kind DeclKind   :  8;

-  /// DeclChain - Linked list of declarations that are defined inside  
this
-  /// declaration context.
-  ScopedDecl *DeclChain;

+  /// LookupPtr - Pointer to a data structure used to lookup
+  /// declarations within this context. If the context contains fewer
+  /// than seven declarations, the number of declarations is provided
+  /// in the 3 lowest-order bits and the upper bits are treated as a
+  /// pointer to an array of NamedDecl pointers. If the context
+  /// contains seven or more declarations, the upper bits are treated
+  /// as a pointer to a DenseMap<DeclarationName, TwoNamedDecls>.
+  llvm::PointerIntPair<void*, 3> LookupPtr;
+
+  /// Decls - Contains all of the declarations that are defined inside
+  /// this declaration context.
+  std::vector<ScopedDecl*> Decls;


This shrinks ScopedDecl by one pointer but grows DeclContext by ~3  
pointers, plus the memory that the vector keeps to hold the  
ScopedDecl's.  This is somewhat concerning because you also make every  
Record a DeclContext, and make FieldDecls into ScopedDecls.  There are  
1743 records in carbon.h and 1565 in Cocoa.h (according to "clang - 
print-stats INPUTS/Cocoa_h.m |& grep struct").  There are also  
thousands of enum decls that will get larger as well because they are  
already declcontext's (e.g. 2048 in cocoa).

Going forward, is there any way to reduce this memory hit?  Is a  
pointer chain through ScopeDecls really that bad?


  /// FieldDecl - An instance of this class is created by  
Sema::ActOnField to
  /// represent a member of a struct/union/class.
-class FieldDecl : public NamedDecl {
+class FieldDecl : public ScopedDecl {
+  bool Mutable : 1;

Do you forsee elimination of CXXFieldDecl completely forever?  If not,  
it would be nice to sink the Mutable bit down into the CXXFieldDecl  
class.  This would be a good place to put access control, mutable, and  
other C++ notions.


+  enumerator_iterator enumerator_begin() const {

Any reason to spell out "enumerator" instead of using enum_begin/ 
enum_iterator/enum_end() etc?  I like the iterator interface a lot  
better than the old getEnumConstantList stuff!

+  class field_iterator {

There is a lot of commonality between field_iterator and  
enumerator_iterator, maybe they should be genericized?

+  typedef field_iterator field_const_iterator;

Naughty naughty :)



+  /// Entity - The entity with which this scope is associated. For
+  /// example, the entity of a class scope is the class itself, the
+  /// entity of a function scope is a function, etc. This field is
+  /// maintained by the Action implementation.
+  void *Entity;

This is orthogonal to this patch, but I wonder if Scope::Entity could  
be used to simplify your recent "if(int x = ..)" patch.  If the entity  
for the if-scope was the if statement itself, you wouldn't need an "is  
defined in an if" bit on decl.


+++ lib/Analysis/RegionStore.cpp	(working copy)
@@ -433,8 +433,13 @@

    llvm::ImmutableList<SVal> StructVal =  
getBasicVals().getEmptySValList();

-  for (int i = RD->getNumMembers() - 1; i >= 0; --i) {
-    FieldRegion* FR = MRMgr.getFieldRegion(RD->getMember(i), R);
+  for (DeclContext::reverse_decl_iterator Mem = RD->decls_rbegin();
+       Mem != RD->decls_rend(); ++Mem) {
+    FieldDecl *FD = dyn_cast<FieldDecl>(*Mem);
+    if (!FD)
+      continue;
+

Please suggest to Ted that he upgrade this to use field_iterator after  
your patch goes in.


+++ lib/CodeGen/CodeGenTypes.cpp	(working copy)
@@ -392,7 +392,7 @@
    } else if (TD->isUnion()) {
      // Just use the largest element of the union, breaking ties with  
the
      // highest aligned member.
-    if (RD->getNumMembers() != 0) {
+    if (RD->field_begin() != RD->field_end()) {

Do you think a field_empty() method would be worthwhile?



+      // Remove the previous declaration from the scope.
+      if (DeclRegionScope->isDeclScope(OrigNS)) {
+       IdResolver.RemoveDecl(OrigNS);
+       DeclRegionScope->RemoveDecl(OrigNS);
+      }

Funky indentation, not tabs this time :)


+++ lib/Sema/SemaInit.cpp	(working copy)

+  int InitializableMembers
+    = std::count_if(structDecl->field_begin(), structDecl->field_end(),
+                    std::mem_fun(&FieldDecl::getDeclName));

Couldn't help yourself huh? :)  Plz make InitializableMembers while  
you're poking it.


+++ lib/Sema/SemaCXXScopeSpec.cpp	(working copy)
+    if (LookupCtx && !LookInParentCtx) {
+      IdIsUndeclared = true;
+      for (DeclContext::lookup_const_result I = LookupCtx- 
 >lookup(Context, Name);
+          I.first != I.second; ++I.first) {
+       IdIsUndeclared = false;
+       if (((*I.first)->getIdentifierNamespace() & Decl::IDNS_Tag) &&
+           !isa<EnumDecl>(*I.first))
+         return *I.first;
+      }

Personally, I find all the parens and *'s and ->'s distracting.   
Please do something like:

   whatever_t I, E;
   tie(I, E) = LookupCtx->lookup(Context, Name);
   for (; Start != End; ++Start) { ..

tie is defined in llvm/ADT/STLExtras.h.


+++ lib/Sema/SemaDecl.cpp	(working copy)

       if (!Ovl) {
          // We haven't yet overloaded this function. Take the existing
          // FunctionDecl and put it into an OverloadedFunctionDecl.
          Ovl = OverloadedFunctionDecl::Create(Context,
                                               FD->getDeclContext(),
                                               FD->getDeclName());
-        Ovl->addOverload(dyn_cast<FunctionDecl>(*I));
+        Ovl->addOverload(dyn_cast<FunctionDecl>(Prev));

Unrelated to this patch, but please use cast<> here instead of  
dyn_cast<>.

+       // If there is an name binding for the existing FunctionDecl,
+       // remove it.
+       for (IdentifierResolver::iterator I
+              = IdResolver.begin(FD->getDeclName(), FD- 
 >getDeclContext(),
+                                 false/*LookInParentCtx*/);
+            I != IdResolver.end(); ++I) {

This evaluates IdResolver.end() each time through the loop.


+  if (ScopedDecl *SD = dyn_cast<ScopedDecl>(D))
+    CurContext->addDecl(Context, SD);
+  else {
+    // Other kinds of declarations don't currently have a context
+    // where they need to be inserted.
+  }

Instead of the empty else, how about:

+  // Add scope decls to their context.  Other kinds of declarations
+  // don't have a context where they need to be inserted.
+  if (ScopedDecl *SD = dyn_cast<ScopedDecl>(D))
+    CurContext->addDecl(Context, SD);


@@ -193,22 +220,77 @@
  /// namespace.
  Decl *Sema::LookupDecl(DeclarationName Name, unsigned NSI, Scope *S,

Unrelated to this patch, but please substantially improve the doxygen  
comment for lookupdecl :)


LookupDecl now looks like this:

+  if (LookupCtx) {
       // Qualified C++
+  } else if (getLangOptions().CPlusPlus &&
+               (NS & (Decl::IDNS_Ordinary | Decl::IDNS_Tag))) {
       // Unqualified C++
+  } else {
       // C & label.
+  }

This is optimizing (both in performance and for readability) for the  
wrong case.  Please use something like:

if (LookupCtx == 0 &&
     (!getLangOptions().CPlusPlus || (NS is label)))) {
   // C & label case.
} else if (LookCtx == 0) {
   // unqualified c++
} else {
   // qualified c++
}

Alternatively, it might be better to make the qualified C++ case come  
before the unqualified c++ case since it is shorter (helps readability).

+    for (; S; S = S->getParent()) {
+      // Check whether the IdResolver has anything in this scope.
+      // FIXME: The isDeclScope check could be expensive. Can we do  
better?
+      for (; I != IEnd && S->isDeclScope(*I); ++I)

isDeclScope is a smallptrset lookup, so it isn't *that* expensive (not  
like a linear scan).  Better would be better though ;-)


+      // If there is an entity associated with this scope, it's a
+      // DeclContext. We might need to perform qualified lookup into
+      // it.
+      DeclContext *Ctx = static_cast<DeclContext *>(S->getEntity());
+      while (Ctx && Ctx->isFunctionOrMethod())
+        Ctx = Ctx->getParent();

What was the decision about this loop?  At the very least, the comment  
needs to be improved.


+        for (DeclContext::lookup_const_result I = Ctx- 
 >lookup(Context, Name);
+             I.first != I.second; ++I.first) {
+          // FIXME: Cache this result in the IdResolver
+          if ((*I.first)->getIdentifierNamespace() & NS)
+            return  *I.first;

This isn't as crazy as the loop above, but using tie might be better  
here, your call.  You have extra an space after the return.


  +++ lib/Sema/SemaOverload.cpp	(working copy)
@@ -1955,10 +1955,9 @@
    //        (13.3.1.1.1); otherwise, the set of member candidates is
    //        empty.
    if (const RecordType *T1Rec = T1->getAsRecordType()) {
-    IdentifierResolver::iterator I
-      = IdResolver.begin(OpName, cast<CXXRecordType>(T1Rec)->getDecl(),
-                         /*LookInParentCtx=*/false);
-    NamedDecl *MemberOps = (I == IdResolver.end())? 0 : *I;
+    DeclContext::lookup_const_result Lookup
+      = cast<CXXRecordType>(T1Rec)->getDecl()->lookup(Context, OpName);

Do you still need this and the other similar cast<>'s?



+  case Decl::ObjCInterface:
+    // FIXME: Can Objective-C interfaces be forward-declared?
+    return this;

Yes, but with a completely different implementation than in C.  FWIW,  
they look like this:

@class foo;

foo* P;  // ok now.

@interface foo ...
@end


+DeclContext::lookup(ASTContext &Context, DeclarationName Name) {
...
+  if (LookupPtr.getPointer() == 0) {
+    for (DeclContext *DCtx = this; DCtx; DCtx = DCtx->getNextContext())
+      for (decl_iterator D = DCtx->decls_begin(); D != DCtx- 
 >decls_end(); ++D)

This evaluates decls_end every time through the loop.

+  if (isLookupMap()) {
+    StoredDeclsMap *Map =  
static_cast<StoredDeclsMap*>(LookupPtr.getPointer());
...
+  NamedDecl **Array = static_cast<NamedDecl**>(LookupPtr.getPointer());

You do this pattern in many places.  How about something like:

   if (StoredDeclsMap *LookupMap = getLookupMap()) { // private method  
obviously.

   } else {
     NamedDecl **Array = getLookupArray();

   }

That way the cast only happens in the inline private method, instead  
of in several places.

+  for (unsigned Idx = 0; Idx < Size; ++Idx)

It doesn't really matter, but please use != for consistency.

+    // We always keep declarations of the same name next to each other
+    // in the array, so that it is easy to return multiple results
+    // from lookup(). There will be zero, one, or two declarations of
+    // the same name.
+    unsigned Match;
+    for (Match = 0; Match < Size; ++Match) {
+      if (Array[Match]->getDeclName() == D->getDeclName())
+       break;

indentation on the break and several other places in this function.

+    // Put this declaration into the appropriate slot.
+    TwoNamedDecls Val;
+    Val.Decls[0] = 0;
+    Val.Decls[1] = 0;
+    Val.Decls[IndexOfD] = D;

This is a somewhat strange idiom to me (setting then overwriting one  
element).  How about:

+    // Put this declaration into the appropriate slot.
+    TwoNamedDecls Val;
+    Val.Decls[IndexOfD] = D;
+    Val.Decls[!IndexOfD] = 0;

+    Pos = Map->insert(std::make_pair(D->getDeclName(),Val)).first;

'Pos' is dead here, no need to capture the result of the insert.


+++ lib/AST/Decl.cpp	(working copy)

+  return new (Mem) FieldDecl(Decl::Field, DC, L, Id, T, BW, Mutable,  
PrevDecl);

If CXXFieldDecl is gone for good, you can hardcode 'Decl::Field' into  
the FieldDecl ctor.


+    // FIXME: This is linear time. And the fact that we're indexing
+    // into the layout by position in the record means that we're
+    // either stuck numbering the fields in the AST or we have to keep
+    // the linear search (yuck and yuck).
+    unsigned i = 0;

I agree.  Indexes have their uses though, we should probably talk  
(with daniel) about this sometime.



+++ lib/AST/ASTContext.cpp	(working copy)
@@ -539,7 +539,7 @@
    ASTRecordLayout *NewEntry = new ASTRecordLayout();
    Entry = NewEntry;

-  NewEntry->InitializeLayout(D->getNumMembers());
+  NewEntry->InitializeLayout(std::distance(D->field_begin(), D- 
 >field_end()));

I'm not sure what InitializeLayout is doing with the size, but if it  
can be changed, it would be nice to eliminate the linear time walk  
here.  Please add a FIXME.


Overall, I'm a big fan of this change.  The biggest concern I have is  
memory use, but I think that can be "fixed" by (in a later patch!)  
threading a singly linked list through ScopeDecls.  Thanks for working  
on this Doug, this is a huge cleanup!

-Chris










More information about the cfe-dev mailing list