Incremental and Modular Context-sensitive Analysis. Issue 2 (19th March 2021)

• Record Type: Journal Article
• Authors: GARCIA-CONTRERAS, ISABEL; MORALES, JOSÉ F.; HERMENEGILDO, MANUEL V.
• Is Part Of: Theory and practice of logic programming. Volume 21:Issue 2(2021)
• Page Start: 196
• Page End: 243
• Publication Date: 2021-03-19
• Subjects: program analysis -- incremental analysis -- modular analysis -- constrained Horn clauses -- abstract interpretation -- fixpoint algorithms -- logic and constraint programming; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068420000496
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: Context-sensitive global analysis of large code bases can be expensive, which can make its use impractical during software development. However, there are many situations in which modifications are small and isolated within a few components, and it is desirable to reuse as much as possible previous analysis results. This has been achieved to date through incremental global analysis fixpoint algorithms that achieve cost reductions at fine levels of granularity, such as changes in program lines. However, these fine-grained techniques are neither directly applicable to modular programs nor are they designed to take advantage of modular structures. This paper describes, implements, and evaluates an algorithm that performs efficient context-sensitive analysis incrementally on modular partitions of programs. The experimental results show that the proposed modular algorithm shows significant improvements, in both time and memory consumption, when compared to existing non-modular, fine-grain incremental analysis techniques. Furthermore, thanks to the proposed intermodular propagation of analysis information, our algorithm also outperforms traditional modular analysis even when analyzing from scratch.