• Live variables analysis finds out, for each program point in a given program, a set of variables that are read in further execution of the program in some instance of program execution. It is used for eliminating dead assignments (assignments that store value in a variable that is guaranteed to be not used in the program after the assignment), or for performing register allocation (deciding which variables should have their values in registers). Both these applications fall in the category of code optimization.
• Constant propagation finds out, for each program point in a given program, a set of variables whose value is a compile time constant (and hence is same in all possible executions of the program). Replacement of variables by constant allows using immediate mode addressing in the generated code. This eliminates the need of loading values in a register and hence leads to a possibly faster execution of programs. Further, it may enable other optimizations such as loop optimizations (if loop bounds are discovered to be compile time constants) or procedure specialization (if actual parameters are known to be compile time constants).
• Pointer analysis provides information to disambiguate indirect reads and writes of data through pointers and indirect control flow through function pointers or virtual functions. Its precision influences the precision and scalability of client program analyses significantly. Computationally intensive analyses such as model checking are noted as being ineffective on programs containing pointers, partly because of imprecision of points-to analyses. Thus pointer analysis is a key enabler of precision and efficiency in any analysis.

Live variables analysis and constant propagation have been around for a long while and are mature analyses that every compiler employs. Pointer analysis has also been around for a long while but it has not reached the same degree of exploitation because for it needs to performed across procedures for finding out practically meaningful information. This hampers its scalability and leading to a precision-scalability tradeoff. Thus it is a ripe area of research. This tutorial provides a glimpse of some of the recent research efforts in pointer analysis.

Although the tutorial primarily focuses on the C/C++ language model, the concepts are generic and are applicable to Java too. More details of these analyses can be found in the text Data Flow Analysis: Theory and Practice.

We will perform these analyses using SPAN (Synergistic Program Analyzer), a tool developed by Anshuman Dhuliya as a part of his research in our group at IIT Bombay. Please use this link to set it up on your laptops. The link also gives instructions for setting up its front end based on CLANG so that the analysis can be performed on any C program by generating spanir files corresponding to them. This step of setting up CLANG is a bit time consuming. If you have difficulties in setting up the front end, you can try to modify the spanir representation of a program which is a textual representation describing it in python data structures. A set of C programs and their spanir versions can be found here along with a README file containing useful information.

The tutorial will be based on the following set of slides. They contain several animations so viewing them in presentation mode would be more effective.

• Introduction to data flow analysis
• Live variables analysis
• Constant propagation
• Pointer analysis
• Some example of program analysis research at IIT Bombay