Implement constant propagation for miniC. For constant propagation we employ a variable environment that is propagated through the control flow graph. Note that a environment can be represented as an array of structs. For each variable we have one entry in the array and the struct describes an element of the number lattice.
For example
struct constant {
enum {C_CONST, C_BOTTOM, C_TOP} type;
int num; /* value of constant if type == CONST */
};
defines the struct for an element in the number lattice. A constant
C_CONST represents a constant whereas C_BOTTOM
and C_TOP are top and bottom symbol of the number lattice.
Note that the top symbol is only used for initialization purposes --
bottom symbol represents values of variables that are not constant.
Constant propagation is a data flow problem. However, we cannot
simply map it to a gen/kill-problem. Hence we have to write our own
solver for CP.
The solver has the in- and out-values of the data-flow functions for
each basic-block. We initialize the data-flow equation system with
the top symbol for all variables and for all nodes except the start
node. For the start-node all variables are assigned the bottom-symbol,
i.e. the variables are not constants.
To represent the in- and out-values pointer-arrays are recommended. For example
struct constant **cp_in,**cp_out;
defines the in- and out-values whereby cp_in[2][3] gives
the value of the third variable in the second basic block.
The algorithm for solving CP is straight-forward. We compute the local equations until no in- and out-value changes its contents. For the data-flow equation, a meet-operator is to be programmed.
Implement common common sub-expression elimination. Use a lookup-function for identifying sub-expressions which occur more than once in a function. Each sub-expression should get a unique number that is to be used for the bit-index in the gen/kill-problem.
Back.