Dataflow Analysis

Objective - This assignment will familiarize you with writing static program analyses using LLVM. LLVM is a collection of compiler and analysis tool chain utilities widely used in the software analysis community. You will use LLVM to implement two intra-procedural dataflow analyses, one forward (reaching definitions analysis) and one backward (liveness analysis).

Setup

1. Download and extract the assignment code in the file dataflow.zip.

2. Navigate to dataflow/build and run the following commands:

cmake ..

make clean

make

(You should now see libDataflowPass.so under dataflow/build/Dataflow.)

3. Go to the dataflow/example directory and compile the programs we will analyze with the following commands:

clang -emit-llvmArrayDemo.c -c -o ArrayDemo.bc

clang -emit-llvmGreatest.c -c -o Greatest.bc

4. Run the Dataflow pass using the commands below to ensure everything works as expected for the test program ArrayDemo.c. These commands print the results of reaching definition analysis and liveness analysis (they are empty sets because the analyses are only stubs) as the dataflow facts for each instruction.

opt -load ../build/Dataflow/libDataflowPass.so -ReachDef /dev/null

opt -load ../build/Dataflow/libDataflowPass.so -Liveness /dev/null

Assignment Instructions -

Complete the do Analysis method in ReachDefAnalysis.cpp and LivenessAnalysis.cpp (located in dataflow/Dataflow/ ) to implement the two analyses. Do not write your analysis code outside of these files, as these files are the only ones you will submit.

You may use the C++ Standard Template Library (STL) with LLVM.

Your code will need to iterate over the program points in the input function and store the computed dataflow facts in DataflowAnalysis::inMapand DataflowAnalysis::outMap. Both analyses inherit from the base class DataflowAnalysis, which you can find in the header file DataflowAnalysis.hlocated in the directory dataflow/Dataflow/. Besides including useful classes such as SetVectorand ValueMap, DataflowAnalysis.halso defines usefl utility functions such as getPredecessors, getSuccessors, and isDef.

The file Printer.cpp (also in the same directory) demonstrates the API by printing the definitions, uses, predecessors, and successors of each instruction. You can execute it using the command:

opt -load ../build/Dataflow/libDataflowPass.so -Printer /dev/null

After completing the two doAnalysismethods, re-build the analyses using the commands from setup Step 2, and then rerun the analyses using the commands from setup Step 4 to obtain the output of your analyses on the ArrayDemo.cprogram. If your implementation is correct, your output will match the example output in ArrayDemo_ReachDefand ArrayDemo_Liveness (both found in dataflow/example/ ). The order of elements in the in and out sets does not matter, but the number of elements and the values should match exactly.

We have also included another program, Greatest.c, and it's expected outputs for testing your implementation. You can use commands similar to those the final set-up instruction step to analyze this program.

Attachment:- Assignment Files.rar