How backtrace when an instruction related exception is caught

The easiest method is that used by the linux kernel:

Just scan through the stack and report every value that is inside the code area.

Stale values (caused by unwritten locations in the current call sequence) are a slight problem.

If the code is compiled to use a frame pointer, then it should be possible to follow the fp chain (fp should point to the previous value and the return address should be in the adjacent location). But IIRC someone has reported that gcc doesn't always get this right.

Or you can use the debug info generated by the compiler that contains the stack offset at every instruction offset - not for the faint hearted.

Or you can follow the instruction stream forwards while monitoring the value of sp (and fp) until you hit a return instruction. You need to remember the instructions processed and be willing to restart assuming that a branch is taken. Works quite well provided you are in a function that can return.

Probably not to bad to implement for nios either (a pain for x86).