|
|
In some situations, while it is possible to optimize a statement with respect to some paths along which it lies, the same optimization opportunity does not exist along other paths through the statement. We refer to such optimizations as path sensitive optimizations. Examples of such optimizations include conditional branch elimination, partial redundancy elimination, partial dead code elimination and load removal. In this talk I will present algorithms for path sensitive optimizations that range from purely compile-time techniques to those that are implemented entirely in hardware.
Compile-time analysis required to uncover opportunities for path sensitive optimization poses a significant challenge. In order to uncover all path sensitive optimization opportunities, a straightforward approach to path sensitive analysis may attempt to collect an exceedingly large number of data flow facts. I will present an approach that addresses this problem by limiting the scope of analysis in two ways: demand driven analysis is employed to collect only the subset of data flow facts that are relevant to an optimization; and path profiles are used to limit the analysis to a subset of program paths exercised during program execution. Code motion and control flow restructuring are two transformations that can be used to enable path sensitive optimizations. I will present a conditional branch elimination algorithm that relies upon demand driven analysis and restructuring. I will also show the use of path profiles and code motion for removing redundancy and dead code from frequently executed program paths.
The challenging aspect of developing a hardware optimization algorithm is in the design of an implementation whose performance scales with the issue width of the processor. I will describe a hardware runtime memory disambiguation algorithm, that when used for load speculation, provides scalable performance up to issue widths as high as 32.