This technique is used by some existing VMs. .NET does this with a background thread and calls it 'tiered compilation', where methods are queued for recompilation at a higher (more expensive/thorough) optimization level in the background. It's pretty helpful.

I believe most browser JS runtimes do it too.