One embodiment of the present invention provides a system that uses value speculation to break constraining dependencies in loops. The system operates by first identifying a loop within a computer program, and then identifying a dependency on a long-latency operation within the loop that is likely to constrain execution of the loop. Next, the system breaks the dependency by modifying the loop to predict a value that will break the dependency, and then using the predicted value to speculatively execute subsequent loop instructions.