| Current compiler optimizers are conservative and inflexible. As a result, even "highly optimized" programs execute half of their instructions redundantly, only to recompute previously computed values. Ideally, these values should be remembered and later reused, removing recomputations.;Unfortunately, this reuse strategy fails often. The culprit is intermittent reuse---one that exists only along some execution paths leading to the redundant instruction. This path-specific reuse is frequent, but to remove it, the optimizer may need to pay the exponential price of optimizing each path separately.;This thesis describes how to defeat this exponential path explosion, in its various forms: how to analyze paths separately only when it matters, via demand analysis; how to generate less path-specific code, via optimal profiling feedback; and how to avoid profiling individual paths, via adding confidence to imprecise profiles. The result is a path-sensitive optimization framework that is powerful enough to remove nearly all redundancies, yet practical enough to permit an industrial-strength implementation. |
