An approach to incremental and modular context-sensitive analysis

García Contreras, Isabel, Morales Caballero, José Francisco and Hermenegildo, Manuel V. ORCID: (2018). An approach to incremental and modular context-sensitive analysis. Monografía (Technical Report). E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.


Title: An approach to incremental and modular context-sensitive analysis
Item Type: Monograph (Technical Report)
Date: 2018
Freetext Keywords: Program analysis; Dynamic languages; Incremental analysis; Modular analysis; Constraint horn clauses; Abstract interpretation; Fixpoint algorithms; Logic and Constraint programming
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[thumbnail of HERME_TCREP_ANDMANS_2018-1.pdf]
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (2MB) | Preview


The flexibility of dynamic languages often comes at the cost
of having to perform at run time a number of additional
tasks when compared to static languages. This includes for
example detecting property violations in calls to built-ins
and libraries (as well as in user code) or performing dynamic
specialization and other optimizations. Analyzing programs
statically can help reduce the amount and cost of these dynamic tasks. However, performing global analysis can in turn
be costly at compile time for large code bases, and this can
be a special burden if it is performed at each development
iteration. On the other hand, changes between development
iterations are often isolated within a few components, and
analysis cost can be reduced by reusing the results of previous analyses. This has been achieved to date through modular analysis, which reduces memory consumption and often
localizes the computation during reanalysis mainly to the
modules affected by changes, and through global incremental
fixpoint analysis techniques, that achieve cost reductions at
finer levels of granularity, such as changes in program lines,
but which are not directly applicable to modular programs.
This paper describes, implements, and evaluates a context-
sensitive fixpoint analysis algorithm aimed at achieving both
inter-modular (coarse-grain) and intra-modular (fine-grain)
incrementality, solving the problems related to propagation
of the fine-grain change information and effects across module boundaries, for additions and deletions in multiple modules. The implementation and evaluation of our algorithm
shows encouraging results: the expected advantages of fine-
grain incremental analysis carry over to the modular analysis
context. Furthermore, the fine-grained propagation of analysis information of our algorithm improves performance with
respect to traditional modular analysis even when analyzing
from scratch.

More information

Item ID: 53067
DC Identifier:
OAI Identifier:
Official URL:
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 21 Nov 2018 11:41
Last Modified: 18 Jun 2019 06:44
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM