Exceptions aren't zero-cost either: they require you to be able to unwind the stack, so you have to keep the frame pointer and have one fewer general-purpose register to work with.
You actually don't need the frame pointer to unwind the stack. DWARF frame info allows the compiler to specify tables that describe the stack layout at every program point, and this can be used to perform unwinding.
Another reason why exceptions aren't zero-cost in practice is that compilers need to model the exceptional control-flow, and they usualy don't do a great job in this situation and miss a lot of potential optimizations.
