EFFICIENT COMPUTATION OF FIXPOINTS THAT ARISE IN COMPLEX - PROGRAM ANALYSIS

A model for studying the computation of fixpoints that arise in comple x program analysis based on abstract interpretation is proposed, and a n efficient algorithm for computing fixpoints based on the model is pr esented. Abstract interpretation provides a promising framework for ha ndling interprocedural analysis of programs in the presence of unrestr icted pointer manipulation, higher-order functions and continuations. In the general case, the structure of the fixpoint computation is not known before analysis; that is, the flow graph cannot be determined wi thout some degree of analysis. Abstract interpretation handles this si tuation easily. In the proposed algorithm, the entailment graph, repre senting the structure of the fixpoint computation, is developed during analysis. The strategies for determining the evaluation order, which underlie the algorithm, are described. Based on the strategies, local knowledge of the entailment graph at each node is exploited to determi ne dynamically an effective order of evaluation. The algorithm behaves like those based upon interval analysis of a flow graph, but without requiring the interprocedural control flow graph to be given a priori. The algorithm is implemented, and experiments are conducted to compar e it to other iterative algorithms for solving such problems. The resu lts show that the algorithm is flexible, efficient and consistently be tter than the others.