My recollection (without references) is that they can do some amount of guess work. They might see the stack says A->C, but can see the code of A actually calls B, so logically it must have been A->B->C at some point.

Or you can use the rr-debugger, and just return back to the exact sequence of calls, and reject the need to pick between optimization and debugging :D