Colloquium Speaker

Speaker:		Rajiv Gupta University of Pittsburgh
Topic:		Path Sensitive Code Optimizations
Date:		Tuesday, March 30, 1999
Time:		9:30 AM
Place:		Gould-Simpson, Room 701

ABSTRACT

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 store removal.

The 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 path profile guided code motion algorithms that use speculation to remove partial redundancy and predication to remove dead code from hot paths at the expense of impairing the performance along cold paths. I will also briefly show how the above optimizations and conditional branch elimination can be achieved through control flow restructuring.