So yea, populating this at runtime depending on the CPU features supported by your CPU is possible, and the linux dynamic linker does this: http://man7.org/linux/man-pages/man8/ld.so.8.html (check out the section on hardware capabilities).
Two implementations are compiled (one is optimized using instructions only available on certain processors), and the decision of which one to use is made at program startup.
Nearly impossible to do in a high-level language, but it's the way an Asm programmer would probably think of doing it.
Linux on ARM used to have an ABI called OABI which would assume the CPU had FPU support, in case it didn't the kernel would catch the exception, perform the FPU operation in the kernel and return the result back to the program. This ended up being incredible slow however, with performance penalties for hardfpu machines as well. The new ABI (EABI) requires that the binary be built either for soft or hard float, which no longer requires the kernel to get involved.
Like the new VFMADD* instructions. So if I wanted to write a binary which supports post-2013 CPUs as well as previous ones, my way of doing this would be:
1) have a huge array of function pointers for every function that could use said instructions
2) in main() check if the CPU supports the instructions, if yes: populate array with fast functions, if not, populate with backwards-compatible functions.
Naturally this comes with a performance hit at every call as at least one (or two, if you fill the arrays at compiletime, and in main just switch the array pointer) indirections. Is this really how stuff gets done?