Re: "I did not know that ARM actually prohibited adding instructions"
I don't think you understand what is being said. You are telling us that, if you request and parse the CPU ID before every questionable instruction, it would add a lot of overhead. When you say this, you are right. When you say this, you are missing the point. The ID is not retrieved and parsed before every possible instruction. It is retrieved and parsed (only if applicable), at the beginning of execution. Then, things are updated to use the proper instructions. The overhead is only incurred once, and that is a negligible time cost. You ask for examples of things doing this. I would direct you to nearly every program that uses one of the instruction sets that are widely supported but not universally so. Using my example of AES, look at disk encryption programs. They will do exactly this. Other extra instructions are frequently used conditionally by programs such as VM hosts or anything where the marketing includes the phrase "hardware acceleration".
As an example on how this is done, consider this pseudo-assembly, with AES acceleration as the example:
#function that does encryption in hardware:
#function that does encryption in software:
encryption_function = do_it_in_hardware
//Note: I've written this like a variable. I do know about computers, so I know this would be implemented by storing a number in a memory location or register. I wrote it like this for simplicity of reading
if (CPU can't perform hardware AES):
encryption_function = do_it_in_software
#rest of program
In this simple case, the only thing that's changed is the value of the pointer encryption_function. The rest of the code merely jumps to it. In the real world, there would be more complexity because they'd probably write the code to avoid the function-calling overhead too. But I hope you get what we're trying to explain.