One embodiment of the present invention provides a system that generates prefetches by speculatively executing code during stalls through a technique known as 'hardware scout threading.' The system starts by executing code within a processor. Upon encountering a stall, the system speculatively executes the code from the point of the stall, without committing results of the speculative execution to the architectural state of the processor. If the system encounters a memory reference during this speculative execution, the system determines if a target address for the memory reference can be resolved. If so, the system issues a prefetch for the memory reference to load a cache line for the memory reference into a cache within the processor. In a variation on this embodiment, the processor supports simultaneous multithreading (SMT), which enables multiple threads to execute concurrently through time-multiplexed interleaving in a single processor pipeline. In this variation, the non-speculative execution is carried out by a first thread and the speculative execution is carried out by a second thread, wherein the first thread and the second thread simultaneously execute on the processor.