[cfe-dev] Name lookup approach

[Zhongxing Xu]

On Fri, Jan 9, 2009 at 1:33 AM, Douglas Gregor <dgregor at apple.com> wrote:

>
> On Jan 8, 2009, at 6:17 AM, Zhongxing Xu wrote:
>
>> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20090109/9d9698fb/attachment.html>