2. Partial redundancy elimination in compilers

Partial redundancy elimination (PRE) subsumes classical optimizations of common subexpression elimination, loop optimization and code movement. My contributions to this field span over two decades.

   (i) Edge placement of computations: The original PRE algorithm by Morel and Renvoise missed several opportunities of optimization due to the restrictive code placement model used by it. I formulated the technique of edge placement of computations and developed a code placement model which performed code placement in nodes as well as edges of a program. Use of this model was shown to capture all opportunities of PRE through safe placement of computations. Use of this model also simplifies the data flows involved in PRE.

The edge placement technique has been used in all PRE algorithms following my work.

  (ii) Avoiding redundant hoisting in PRE: Redundant hoisting, i.e. code movement which does not result in improvement of execution efficiency along any path in a program, needlessly increases register live ranges in a program. Its avoidance reduces register pressure.

Following my work, this feature has also been included in all PRE algorithms.

 (iii) Incorporating strength reduction in PRE frameworks: Strength reduction replaces use of expensive operations in a program by (possibly repeated) executions of less expensive operations. Its incorporation in the PRE framework results in an optimizing transformation called composite hoisting and strength reduction (CHSA) which performs comprehensive optimization of programs.

CHSA has been used in commercial compilers since the mid-80's.

  (iv) Use of PRE techniques in register assignment: This research extends use of the PRE approach to the problem of live range identification in register assignment.

   (v) Providing a conceptual basis for PRE: PRE algorithms have been hard to understand due to lack of a conceptual basis for PRE. My research has formulated the fundamental conceptual basis for PRE. Its use leads to a PRE approach which is simple to understand and efficient to implement.

Selected publications

CACM'79  IJCM'82  CACM'89  CL'88  SN'88  TOPLAS'91  PLDI'92  TOPLAS'93   JPL'95    SN'02