A Data Flow Analysis Framework for gen/kill-set problem is to be implemented. The framework should be able to compute solutions for four different types of data flow analysis problems:
For the solver we need four sets (gen, kill, in and out) for a node. The easiest way to keep the sets in memory is to store the sets in arrays and the indices corresponds to node numbers.
The gen and kill sets are constant sets and are provided from the caller. Sets in and out are computed by the solver. Only the initial value of the problem must be given in the out-set of the start node and end node respectively (dependent on the direction of the problem). We can define following interface for the solver:
enum direction {DFA_FORWARD,DFA_BACKWARD};
enum operatortype {DFA_UNION,DFA_INTERSECTION};
void dfa_solve(
struct func *f, /* function pointer */
enum direction direction, /* direction of the problem */
enum operatortype type, /* type of meet operator */
int num_set, /* number of data flow facts / size of sets */
sbitmap **gen, /* DFA sets */
sbitmap **kill,
sbitmap **in,
sbitmap **out
);
Compute gen/kill sets for liveness analysis and remove dead code, i.e. computations which are not used later in the function. Note that if an assignment of a variable is a function call and the assignment of the variable is a dead computation, the function must not be removed since there can be side-effects to memory.
Example: The liveness analysis deduces that x is not alive after assignment x=f(1,2); Function f(1,2) may contain side-effects to main-memory and it is not a valid action to remove it. Therefore, we keep the call and the assignment x=f(1,2); becomes f(1,2);.
Back.