Name lookup approach

Hi,

Currently we have two mechanisms to do name lookup: IdentifierResolver and DeclContext. In Sema::LookupDecl(), we combine the two approaches to fulfil the name lookup task. I really feel that the code in Sema::LookupDecl() logically uninituitive and error prone. Could we use DeclContext exclusively to do name lookup and eliminate the IdentifierResolver use? I think that way could make name lookup logically more clear. My only concern is if that could cause performance lost?

-Zhongxing

Currently we have two mechanisms to do name lookup: IdentifierResolver and DeclContext. In Sema::LookupDecl(), we combine the two approaches to fulfil the name lookup task. I really feel that the code in Sema::LookupDecl() logically uninituitive and error prone. Could we use DeclContext exclusively to do name lookup and eliminate the IdentifierResolver use?

Currently, no; the chains of declarations held in the IdentifierResolver contain information local declarations that are all in the same DeclContext. For example:

void f(int x) { // #1
   {
     int x; // #2
       {
         int x; // #3

        printf("%i", x); // this 'x' refers to #3
       }
   }
}

Here, the IdentifierResolver has a chain of declarations #3 -> #2 -> #1 for the name 'x'. However, all three 'x's live in the DeclContext associated with f's FunctionDecl.

Now, it is possible that we want compound statements to be DeclContexts, so that the 'x's would be be in different DeclContexts. That might be a good generalization (regardless of whether we use it for name lookup), because it would mean that more of the scope structure of the program is present in the ASTs after parsing. But, that gets to your comment below...

I think that way could make name lookup logically more clear. My only concern is if that could cause performance lost?

Yes, it would most certainly cause performance degradation if we used DeclContext for all name lookup. The beauty of IdentifierResolver is that the chain of declarations in scope for a particular name is attached to the IdentifierInfo for the name, so it's O(1) to find the first declaration with that name that's in scope. If we're using just DeclContexts, we'd have to walk the scope chain upward, checking DeclContext along the way (each check is either a search through a small array or a hash table lookup).

In fact, some of the optimization comments in LookupDecl (and other optimization ideas that have yet to be written down) involve trying to skip calls to DeclContext::lookup when we know that we would have found the answer on the IdentifierResolver chain if there were an answer.

So, I think the complexity of LookupDecl is inherent to solving the problem efficiently. It's also extremely important to performance: when compiling a C++ program that includes <iostream>, GCC spends 26% of its time in name lookup.

  - Doug

Thanks for the explanation, Doug.