Generic Matrix

Today I started coding my liveness analysis. I start preparing a pass that collects the liveness information of the control flow graph. For each pair of basic blocks u and v, it records the set of variables alive between u and v. The requirements in terms of space is O(N*N*T), where N is the number of basic blocks, and T is the total number of temporaries in the control flow graph. Notice that this program only records information about virtual registers. Physical registers are not supposed to be alive between basic blocks. The time complexity of the analysis will be O(T*N). Basically, each block is traversed once, and, for each temporary used, some blocks may have to be traversed in a backward fashion. The pass uses a matrix data structure. Each cell of the matrix is a vector. I coded a generic implementation of the matrix here.