[LLVMdev] Finding Things In SymbolTable

[Reid Spencer]

The SymbolTable is a map of Type* to a map of names to Value*.  This
means that in order to lookup something by name you first have to know
what type it is. For the basic types this is fine because you generally
always know which basic type you're after.  But, for derived types, this
can be quite complicated. It isn't always possible to know the exact
type.

In XPL, types are just names. That is there's no such thing as a type
expression. The name of the type _is_ the expression.  So, in XPL, we
declare something like:

<Signature name="My_Signature" result="void"></Signature>

(that's a signature type, or FunctionType in LLVM speak, that has no
arguments and returns nothing).

Now, we define a function like this:

<Function name="My_Function" signature="My_Signature">
...
</Function>

The problem is that when I hit the Function definition, all I have is
"My_Signature" to identify the function's type.  LLVM currently doesn't
let me find this signature because I'd have to know its type first. The
whole point of putting it in the symbol table is so that I can look up
its type later on with only its name.

Here's some things I'm thinking about changing in LLVM to make it easier
to support this kind of query:

(1) Make it a map of Type::PrimitiveID instead of a map of Type*. The
same interface could be retained by simply obtaining the primitive id of
of any Type* passed into the SymbolTable's interface. For the basic
types, this probably is a wash because nearly every sane complier will
use the static constants defined in Type so there won't be any bloat in
the symbol table. That is, every "int" is an instance of Type::IntTy. 
For derived types, lookups could take a little longer because the first
plane (of PrimitiveID) is now less specialized than the existing plane
(of Type*).

(2) Insert another plane, making the symbol table a map of PrimitiveId
to a map of Type* to a map of names to Value*.  That is, we categorize
the various types by their PrimitiveId as well as just their Type*
value.  This might actually speed things up a bit for derived types. It
would definitely speed things up for (3) ...

(3) Adding various methods to the interface of SymbolTable to look up
names by their PrimitiveID. This can be done regardless of implementing
(1) or (2) above. However, if neither (1) or (2) is done, the algorithm
for these methods is O(N) .. a linear search for the matching item.

Any thoughts on this?  Am I missing something?

Reid.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20040107/221922de/attachment.sig>