A KNOWLEDGE-BASED APPROACH TO THE ANALYSIS OF LOOPS

This paper presents a knowledge-based analysis approach that generates first order predicate logic annotations of loops. A classification of loops according to their complexity levels is presented. Based on thi s taxonomy, variations on the basic analysis approach that best fit ea ch of the different classes are described. In general, mechanical anno tation of loops is performed by first decomposing them using data flow analysis. This decomposition encapsulates closely related statements in events, that can be analyzed individually. Specifications of the re sulting loop events are then obtained by utilizing patterns, called pl ans, stored in a knowledge base. Finally, a consistent and rigorous fu nctional abstraction of the whole loop is synthesized from the specifi cations of its individual events. To test the analysis techniques and to assess their effectiveness, a case study was performed on an existi ng program of reasonable size. Results concerning the analyzed loops a nd the plans designed for them are given.