APT - A DATA STRUCTURE FOR OPTIMAL-CONTROL DEPENDENCE COMPUTATION

The control dependence relation is used extensively in restructuring c ompilers. This relation is usually represented using the control depen dence graph; unfortunately, the size of this data structure can be qua dratic in the size of the program, even for some structured programs. In this paper, we introduce a data structure called the augmented post -dominator tree (APT) which is constructed in space and time proportio nal to the size of the program, and which can answer control dependenc e queries in time proportional to the size of the output. Therefore, A PI is an optimal representation of control dependence. We also show th at using Apl, we can compute SSA graphs, as well as sparse dataflow ev aluator graphs, in time proportional to the size of the program. Final ly, we put APT in perspective by showing that it can be viewed as a fa ctored representation of the control dependence graph in which filtere d search is used to answer queries.