Optimizing for space and time usage with speculative partial redundancy elimination

摘要

Speculative partial redundancy elimination (SPRE) uses execution profiles to improve the expected performance of programs. We show how the problem of placing expressions to achieve the optimal expected performance can be mapped to a particular kind of network flow problem and hence solved by well known techniques. Our solution is sufficiently efficient to be used in practice. Furthermore, the objective function may be chosen so that reduction in space requirements is the primary goal and execution time is secondary. One surprising result that an explosion in size may occur if speed is the sole goal, and consideration of space usage is therefore important.