One embodiment of the present invention provides a system that avoids read-after-write (RAW) hazards while speculatively executing instructions on a processor. The system starts in a normal execution mode, wherein the system issues instructions for execution in program order. Upon encountering a stall condition during execution of an instruction, the system generates a checkpoint, and executes the instruction and subsequent instructions in a speculative-execution mode. The system also maintains dependency information for each register indicating whether or not a value in the register depends on an unresolved data-dependency. The system uses this dependency information to avoid RAW hazards during the speculative-execution mode.