The one I've heard most about in Java is single-implementation devirtualization. Since Java loads dynamically at the class level, it knows exactly which implementations of an interface or class hierarchy are in use. It has to maintain this information in the class loaders anyway, so this is almost free. However, it allows for some pretty aggressive devirtualization by only compiling for known loaded types and trapping the rest. In my experience, especially around things like interfaces defining module contracts, there tends to only be one implementation in play during normal runtime, meaning that the interface becomes zero-cost. And it doesn't even have to track new implementations loading. It just leaves the optimization there until it has proof via the trap that it must recompile.

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.)