Homework 5: Live Variable Analysis (II)

Problem

A variable is live at a program point if there exists an execution where its value is read later in the execution without it is being written to in between.

For example, in example.c, b is a live variable at line 5, for the value of b before the execution of line 5 will be used later(include line 5 itself). At lines 6 and 8, the value of b is not used further, thus b is not a live variable anymore.

• example.c

1  int foo(){
2    int a;        // a is uninitialized
3    int b = 0;
4    int c = 1;
5    a = b + 1;    // b is a live variable
6    a = a * c;    // b is not a live variable
7  
8    return 0;
9  }

In this homework, you are expected to implement a pass to perform an intraprocedural path-insensitive live variable analysis for a C program. The liveness information is a mapping from the line number of the source file to the name set of local variables in the source file. You should output the liveness information to an output file after the analysis.

We assume that

• There is loop now in the function, while the branch should still be considered. This assignment requires you to implement fixed-point algorithm (Worklist) to simulate the analysis process. (To reduce workload, we still choose live variable analysis.)
• There is no pointer and function parameter in the source code.

You can generate the bc code by the following command or use the bc code provided in the benchmark section.

• Command: clang -O0 -g -emit-llvm example.c -c -o example.bc (This command applies the existing optimization in LLVM on the final IR so that it may look slightly different from the original program.)

There are some concrete points:

• In terms of the Worklist algorithms, you should implement a transfer function as well as the filtration using the control dependence. For the dependence relations, you can leverage the control dependence as the dependence defined in the algorithm.
• You should iterate the loop at least twice for the Worklist algorithm.
• If all the variables have an uninitialized value at a specific line, it should not be displayed in the output file.
• Please pay attention to the definition of join operation for liveness state coming from different branches. It should be consistent with the definition of live variables.

Sample Output