It's certainly not free. The execution cost is often bounded by having a multi-tier setup where only the earlier Jit tiers gather type (and perhaps value) infor

It's certainly not free. The execution cost is often bounded by having a multi-tier setup where only the earlier Jit tiers gather type (and perhaps value) information. The final tier only checks it. (Or not, in which case the updates that can invalidate the compiled code are instrumented to discard the code so that it will be recompiled with updated info.) As for space, you can use a scheme of "1, 2, many" to limit the set of types you record. That helps some. But space will also be consumed in the form of IC (inline cache) code that tests for the various possibilities. Again, those chains will probably be capped at a certain size. You're right, it's tricky and can be expensive. But the total amount of entropy in actual observed code typically isn't that large, so there are many opportunities to be clever in the encoding and thereby save a ton of space over a naive solution. (Source: I'm not really a JIT person but I've had a fair amount of exposure to the spidermonkey jit.)