Incremental Flow Analysis through Computational Dependency Reification

Onderzoeksoutput: Conference paper

Samenvatting

Static analyses are used to gain more confidence in changes made by developers. To be of most use, such analyses must deliver feedback fast. Therefore, incremental static analyses update previous results rather than entirely recompute them. This reduces the analysis time upon a program change, and makes the analysis well-suited for environments where the codebase is frequently updated, such as in IDEs and CI pipelines.

In this work, we present a general approach to render a modular static analysis for highly dynamic programs incremental, by exploiting dependencies between intermediate analysis results. Modular analyses divide a program in interdependent parts that are analysed in isolation. The dependencies between these parts stem, for example, from the use of shared variables within the program. Our incrementalisation approach leverages the modularity of the analysis together with the dependencies that it reifies to compute and bound the impact of changes. This way, only the affected parts of the result need to be reanalysed, and unnecessary recomputations are avoided.

We apply our approach to both a function-modular and thread-modular analysis and evaluate it by comparing an incremental update of an existing result to a full reanalysis. We find reductions of the analysis time from 6% to 99% on 14 out of 16 benchmark programs, and on most programs the impact on precision is limited. On 7 of the programs, reanalysis time is reduced by more than 75%, showing that our approach results in fast incremental updates.
Originele taal-2English
TitelProceedings of the 20th IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2020)
UitgeverijIEEE
Pagina's25-36
Aantal pagina's12
ISBN van elektronische versie9781728192482
ISBN van geprinte versie978-1-7281-9248-2
DOI's
StatusPublished - 27 sep 2020
Evenement20th IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM2020) - Adelaide, Australia
Duur: 27 sep 202028 sep 2020

Publicatie series

NaamProceedings - 20th IEEE International Working Conference on Source Code Analysis and Manipulation, SCAM 2020

Conference

Conference20th IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM2020)
LandAustralia
StadAdelaide
Periode27/09/2028/09/20

Vingerafdruk Duik in de onderzoeksthema's van 'Incremental Flow Analysis through Computational Dependency Reification'. Samen vormen ze een unieke vingerafdruk.

Citeer dit