Efficient Computation of Fixpoints that Arise in Complex Program Analysis

This paper presents an efficient algorithm for solving the fixpoints that arise in complex program analysis based on abstract interpretation. The algorithm behaves like those based upon interval analysis of a flow graph, but without requiring the flow graph to be given a priori. In the general case, the structure of the fixpoint computation is not known prior to analysis. In the algorithm, the entailment graph, representing the structure of the fixpoint computation, is developed during analysis; it is precise and thus results in an efficient analysis. The strategies, which underlie the algorithm, for determining the evaluation order are described. Based on these strategies, local knowledge of the entailment graph at each node is exploited to determine dynamically an effective order of evaluations. The algorithm is implemented, and experiments are conducted to compare it to other iterative algorithms for solving such problems. The results show that the algorithm is flexible, efficient, ..