[cfe-dev] Name lookup approach
Douglas Gregor
dgregor at apple.com
Thu Jan 8 09:33:35 PST 2009
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
More information about the cfe-dev
mailing list