The trends toward diverse computer configurations, modular software, and high performance have driven increased interest in and prevalence of dynamic optimization systems that can tailor software to a computer system, to a software set, or for a user need. Optimization of software after the completion of the compilation and linking process, termed postlink optimization, promises great benefits but also imposes strict standards on the optimization system itself. Since optimization is performed late once the user's environment is known, software can be adapted to the class of computer on which it will be run or is currently running, such as a server, desktop, or handheld device. Even beyond the class of computer, a dynamic optimizationsystem can adapt the code to the specific model's configuration, be it memory, latency, or processor resources. While there are many avenues for dynamic optimization to yield benefits, the fact remains that the correctness of the running application cannot be sacrificed. Namely, the dynamically modified software must behave identically (except for speed) to the original untouched program on the user's system. Anything short of this would make software vendors uneasy and thereby limit the acceptance of large-scale dynamic optimization systems. In order to behave identically, the explicit meaning of instructions must be preserved as well as more implicit characteristics such as synchronization events and exception handling. All of the semantics must be preserved by the optimization system without inflating the system's overhead and thereby grossly diminishing any benefits. This thesis looks at a technique called Precise Speculation that provides a flexible, low-overhead mechanism through which instructions can be persistently reordered at runtime while not violating any of the code's semantics.