Constant Propagation

Introduction

This code repository implements constant propagation using the WALA framework for program analysis. Here are some reference for constant propagation:

This project has been coded entirely on Intellij IDEA 16. Therefore to setup the development environment, import this project directly onto Intellij IDEA 16.

This project uses Maven. Dependencies can be found here pom.xml

Building and Execution

The following files are important for the functioning of the WALA framework:

J2SEClassHierarchyExclusions.txt
primordial.txt
primordial.jar.model
A jar file for analysis (As an example - SampleProgram.jar can be found in the repo)

The project can be built using mvn clean install

Once the project is built compile the java classes (ConstantPropagation, Main and MyCallGraph)

Program can be executed by:

java Main "jarfilename" "methodsignature" "graphviz"

where the arguments are:

jarfilename name of the jar file to analyze
methodsignature name of the method to analyze. Example: Program.fun(I)V, represents the method void fun(int) in class Program.
grahviz either true of false. True for generating a pdf file("out.pdf") consisting of the Control Flow Graph. False otherwise.

Algorithm for Constant propagation

Brief overview of the algorithm:

Using the WALA framework a Shrike Control Flow Graph is generated consisting of Blocks. Each block represents part of the program to be analysed
The algorithm then iterates over the blocks(Graph traversal) and evaluates them.
Evaluation rules can be found out from the references.

Simple Demonstration:

The SampleProgram.jar contains the following classes:

SampleProgramDriver - simple driver program to invoke a method in a different class

   public class SampleProgramDriver {
   
       public static void main(String[] arg){
           Program program = new Program();
           program.fun(3);
       }
   }

Program - class where the function fun resides. The program without any user input analyzes method fun by default.

   public class Program {
       public Program(){
   
       }
   
       public void fun(int x){ // keep z as an argument
           int a=5,b=10,z=7; // keep z as a constant
           if(a==5){
               a=10;
               z=1;
               if(a==10){
                   a=15;
                   z=3;
               }else{
                   a=12;
                   z=4;
               }
           }else{
               a=x+3;
           }
       }
   }

Sample run the program gives the following output:

{\[BB 0 ---> BB 1\]={}, \[BB 1 ---> BB 2\]={b=10, a=5, z=7}, \[BB 6 ---> BB 7\]={b=10, a=15, z=3}, \[BB 3 ---> BB 6\]={b=10, a=15, z=3}, \[BB 2 ---> BB 3\]={b=10, a=10, z=1}}

The output represent a edge variable map. Each edge in the control flow graph is mapped to a variable set which signifies the propagated constant after the source block in [Source ---> Destination].

Related Projects:

Constant Propagation - implemented in Java and Scala using WALA

TO:DO:

Program only works for fairly simple conditional constructs (simple if statements).
Loops work with limited flexibility
Conditional statements with complicated expressions have not been handled.
Instruction evaluation is not exhaustive.

Athithyaa/WalaTest