Symbolic evaluation and the global value graph
This paper is concerned with difficult global flew problems which require the symbolic eva la ati on of programs. life use, as is common in global flew analysis, a model in which the expressions computed are specified, but the flow of control is indicated only by a directed graph whose nodes are blocks of assignment statements. We show that if such a program model is interpreted in the domain of integer arithmetic then many natural global flow problems are unsolvable. We then develop a direct (non-iterative) method for finding general symbolic values for program expressions. Our method gives results similar to an iterative method due to Kildall and a direc t method due to Fong, Kam, and Ullman. By means of a structure called the global value graph which compactly represents both symbolic values and the flew of these values through the progran, we are able to obtain results that are as strong as either of these algorithms at a lower time cost, while retaining applicability to all flew graphs.
