Methods and apparatus to perform return-address prediction in a program are described herein. In an example method, a procedure associated with an overflow condition is detected. A branch-hint instruction corresponding to a return instruction associated with the procedure is inserted into the program.