[eholk]

Typically the way systems do this is by translating small sections of straightline code, and patching the exits as they are translated. So you start by saying translate the block at address 0x1234. That code may go until a jump to address 0x4567. When translating that jump, they instead make a call to the runtime system which says "where is the translated code starting at address 0x4567?" If the code doesn't exist, it goes ahead and translates that block and patches the originally jump to skip the runtime system next time around.

This means early on in the program's run you spend a lot of time translating code, but it pretty quickly stabilizes and you spend most of your time in already translated code.

Of course, if your program is self modifying then the system needs to do some more work to invalidate the translation cache when the underlying code is modified.