The primary focus of my research is on issues in program analysis and optimizing compilers (see Parts (a)--(c)). A secondary focus is on distributed control algorithms for use in operating systems (see Part (d)).
a) Generalized theory of data flow analysis and its applications
The generalized theory for bit vector data flow analysis develops the notion of information flow and shows that it is equally applicable to classical unidirectional data flows as well as to bi-directional data flows used in some advanced optimizations. The notion of an information flow path provides deep insights into the nature of data flows and their computational complexity. Tight complexity bounds are obtained by analysing information flow paths for a data flow problem. The classical theory of data flow analysis is shown to be a special case of the generalized theory. The generalized theory has applications in designing efficient data flows. In one particular application, the solution cost of an efficient data flow designed using this theory was found to be 80 percent lower than that of a comparable data flow. The theory has also motivated interesting applications of data flow analysis (see Part (c)).
b) 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.
This work is currently being reported. It is expected to make a very significant impact on the field of PRE.
c) Applications of program analysis techniques
An execution trajectory (ET) (also called an execution history) is a record of operations performed during program execution. ETs are used for a variety of applications including dynamic slicing and debugging of programs. ETs tend to contain voluminous information, hence the overhead of producing and analysing execution histories is considerable.
My research focuses on the use of program analysis techniques to record optimized execution histories which have significantly smaller sizes and analysis costs in applications like dynamic slicing and debugging of programs, including the very challenging field of debugging and exception handling in optimized programs. These techniques make use of notions from the generalized theory of data flow analysis to avoid recording redundant information in an ET.
Performance studies show that our execution histories are at least an order of magnitude smaller than complete execution histories in most cases; for some programs they are smaller by several orders of magnitude. These reductions provide many advantages: reduced memory requirements, reduced execution-time overhead of ET recording, and reduced overhead of ET analysis.
d) Distributed control algorithms for operating systems
This is a secondary research interest for me. It deals with the concurrency and reliability of performing control operations in a distributed operating system. The issues investigated include the following:
(i) Distributed deadlock detection
(ii) Distributed termination detection
(iii) Resilient distributed mutual exclusion
(iv) Self-stabilizing algorithms.