I also think runtime information is critical. Integrated specialized JITs and hinted binary translation might be the solution. Especially considering the pace new instructions have been added lately.

Maybe superoptimization databases for some common sequences.