In a dynamic binary translator, selecting a code segment for load-store memory disambiguation based at least in part on a measure of likelihood of frequency of execution of the code segment, heuristically identifying one or more ambiguous memory dependencies in the code segment for disambiguation by runtime checks based at least in part on inspecting instructions in the code segment, and using a pointer analysis of the code segment to identify all other ambiguous memory dependencies that can be removed by the runtime checks.