Yes, the biggest problem would be that undefined behavior would have to allow the program to keep going. For example, if reading 'data[1]' may seg-fault (And there are valid situations it could), then the compiler would need to prevent that seg-fault or else "Bar" wouldn't print.
It's also worth noting that your trivial example would result in basically everything be removed, but most non-trivial examples don't do that. The most common 'optimization' from undefined-behaviour is that the compiler doesn't need to check for those conditions and can let whatever will happen happen, and that only works if it's defined in a program-wide anything-goes sense. If it's defined on a local sense, then if say 'data' was passed-in as a parameter instead of declared, the compiler would have to insert a NULL check to make sure no undefined-behaviour happens and the program doesn't crash (So that "Bar" prints). By defining undefined-behaviour like it is, there's no requirement for the compiler to do a NULL check, it can instead just assume the programmer will never let it happen and produce code with that in mind. Same thing with integer overflow and similar cases (Though things get a bit hairier there).
For the argument checking case, the compiler can turn the function into two functions, a wrapper function that checks arguments and calls the internal function, and an internal function that doesn't check its arguments, calling the two as appropriate. Then only export the wrapper function, but allow code that the compiler knows to not do things that might be undefined to call the inner function directly.
(This was actually how I'd always assumed compilers optimized publicly-accessible functions, and was quite surprised when I found out they didn't.)
If you're willing to get weird, you can even optimize it into one function with two entry points on some platforms.
Also, personally segfaults shouldn't exist, or rather not in their current uncatchable form. Everything that is potentially recoverable should be able to be caught. So the compiler would wrap the access to data[1] in a try/catch block, which doesn't hinder performance in the common case, while retaining "good" behavior in the bad one. (It can do so because it is not writing anything, just reading it.) Haven't ever used it, but look at https://code.google.com/p/segvcatch/ for something similar.
It's generally easy to catch segfaults. On UNIX-like systems, you can just set a signal handler for SIGSEGV. Other systems generally provide similar functionality.
The problem isn't that they're hard to catch, it's that it's virtually impossible to proceed in any sort of sane manner once a segfault has happened. You have no idea how much state got corrupted before the segfault actually happened. You have no idea what cleanup the functions currently on the stack expect to be able to accomplish before they return. You have no idea what kind of inconsistent state the data structures in memory are in.
If you're really lucky, everything is fine and you can keep on going. If you're not so lucky, stuff is corrupted and you just crash again the moment you try to resume, and again, and again, in an infinite segfault loop. If you're really unlucky, your program doesn't crash again, but proceeds with corrupted data, saving it out to disk and displaying it to the user and causing all sorts of havoc.
I actually helped out a little bit with a similar system:
Although instead of throwing an exception, it simply tried to proceed to the next instruction.
The whole thing was done as a joke for April Fools' Day, because it's a completely awful idea. Making it throw an exception instead of continuing immediately doesn't really make it better.
I agree in general that segfaults shouldn't exist, but your proposed solution is frightening. Segfaults shouldn't exist because the compiler enforces bounds checking, safe memory management, and other such things that ensure that your program never attempts to access memory it can't access. Once the attempt is made, it's far too late to do anything but crash.
It's also worth noting that your trivial example would result in basically everything be removed, but most non-trivial examples don't do that. The most common 'optimization' from undefined-behaviour is that the compiler doesn't need to check for those conditions and can let whatever will happen happen, and that only works if it's defined in a program-wide anything-goes sense. If it's defined on a local sense, then if say 'data' was passed-in as a parameter instead of declared, the compiler would have to insert a NULL check to make sure no undefined-behaviour happens and the program doesn't crash (So that "Bar" prints). By defining undefined-behaviour like it is, there's no requirement for the compiler to do a NULL check, it can instead just assume the programmer will never let it happen and produce code with that in mind. Same thing with integer overflow and similar cases (Though things get a bit hairier there).