My question is, is it feasible for AMD to build an ahead of time compiler that transparently translates CUDA instructions into whatever AMD could have, so things Just Work™? They'd be heavily incentivized to do so. Or even put hardware CUDA translators directly into the cards?

Or am I misunderstanding CUDA? I think of it as something like OpenGL/DirectX.