Marc,

You suggested I look at the Static Analysis Symposium for ways to implement abstract value representations efficiently. I'm not sure exactly what to look at. I looked at old proceedings of SAS, but unfortunately, much of the papers seem not to be online. Are there any specific papers you think I should look at?

Even though I couldn't find what I was looking for, I did spend some time thinking of possible type representations on my own. I believe it's possible to have a fairly accurate representation of JavaScript types that fits in as little as 16 bits per type, using some bitwise logic tricks. Such as setting bit 0 to 1 to indicate an object, in which case we can use the remaining 15 bits to specify some kind of class/constructor identifier (32768 possibilities). It may also be possible to store some (compressed) range information for integers, and even small constant values if the value is known. We might also want special bitwise patterns for the unknown type (top) and the uninferred type (bottom).

The types we probably want to account for: - Undefined - Boolean - Number - Integer or not - Range information [min, max] - Small constant int value if known - String - Array - Object - Constructor/class identifier

If each potential type can fit in 16 bits, the set of types a variable can take can be stored efficiently using a 64 bit word followed by a pointer to a linked list. In this way, the first 4 potential types are readily available, if the type set contains 4 or less types. If we are in a situation where a variable can take more types, we can still store all of these potential types in the hash table, thereby not sacrificing accuracy. This can possibly be made even more memory efficient by storing only the first 3 types and the linked list pointer in a union value, and doing some bitwise checks to see if it's a pointer or not (eg: is last bit 0?).

The type analysis itself involves having a type set for each local/global/parameter/return value/object field. The analysis can be made rather fast since we can also use a simple check (eg: is all zeros) to check if the set is currently bottom or top. We can avoid any pointer indirection most of the time. Type objects themselves can also be compared and operated on pretty fast.

- Maxime