1. A processor comprising: a branch information table (BIT); a speculative return address stack; and an execution return address stack; wherein the processor is configured to: in response to decoding a branch instruction and determining an entry does not exist for the branch instruction in the BIT: allocate an entry in the BIT for the branch instruction; and store an indication corresponding to the entry that indicates the branch instruction has not previously executed; in response to executing the branch instruction and determining a stored indication for the branch instruction indicates the branch instruction has not previously executed: store an address associated with an execution return stack pointer in the entry; and update said indication to indicate the branch instruction has executed; in response to executing the branch instruction and determining the indication indicates the branch instruction has previously executed, reposition the execution return address stack pointer to point to the first location by: retrieving the address associated with the execution return address stack pointer from the BIT entry; and restoring the execution return address stack pointer with the address.