A program trace lists the addresses of instructions executed and data referenced during a program's execution. Earlier approaches to collecting program traces, including abstract execution and optimal control tracing, are reviewed. Two tracing systems based on these techniques are presented. Results collected when using the later systems on several programs show significant reductions in the cost of collecting traces. Reduction in trace file sizes are also significant.