project overview

Fork me on GitHub

IncA is a program analysis framework. It comes with a DSL for the definition of program analyses and the runtime system evaluates program analyses incrementally to achieve the performance that is needed for real-time feedback in IDEs. When code gets changed, the IncA runtime system incrementally updates the results instead of the repeated recomputation from scratch. IncA program analysis code is translated into graph patterns and we reuse existing incremental graph pattern matching solutions to evaluate the analysis code on the AST of the analyzed program.

IncA consists of a program analysis language, an optimizing compiler and an efficient runtime system. We have created a concrete implementation of the system on top of the MPS language workbench and we reuse the incremental graph pattern matching component of the IncQuery project.

Software Requirements:

1 - Highlights

2 - Getting Started

The IncA source code is available on GitHub: git clone Once cloned, you can simply open the project under the code folder in MPS. The project contains the DSL language implementation and MPS solutions for the IncA runtime system. Inside the tests folder there are examples for simple program analyses.

IncA + mbeddr for the case studies

Using IncA with the case studies requires mbeddr as well, which is set of integrated languages for embedded software development also built on top of MPS. The following steps are required to get you started:

Navigating in mbeddr

You can play around with mbeddr by navigating to the test.ts.core.dataflow module (Navigate -> Go to Module). This module contains mbeddr C code snippets which can be used to try out IncA program analyses. Whenever you need to find a file in MPS simply press CMD/CTRL + N and type in the name of the file you are looking for, then hit ENTER.

The following YouTube video also guides you through the first steps.

3 - Case Studies

IncA program analysis code can be viewed and edited in MPS. However, MPS uses projectional editing and does not store the program code in simple text format which makes it hard to read the code outside of MPS. To ease the browsing of the program analyses code of our three case studies we make them available for download as a formatted pdf file and also in simple text format. Developers of IncA code can use a JavaDoc like documentation extension and we used it document every function in the analysis code to explain how the analyses work.

Control Flow Analysis

We implemented an incremental control flow analysis that handles all of mbeddr C, including conditionals (if and switch), loops (for, while, and do while), and jumps (break and continue). The control flow analysis produces the sets of CFG edges where a CFG node represents a possible control flow point like a statement, alternative switch case branches or else if parts of if statements. The analysis code can be viewed as a declarative description of CFG source - target relationships in the context of the various control statements.

The ControlFlowAnalysis module contains the implementation in MPS (look it up with the CMD/CRTL + N keys).

Points-to Analysis

Given a variable that stores a pointer, the goal of a points to analysis is to identify the possible targets of the variable. A well-known algorithm for computing the points-to tuples is Andersen's algorithm. The algorithm considers four basic kinds of assignments and derives the points-to relation for the whole program from them.

Our points-to analysis in IncA builds on Andersen’s rules but extends them in three ways. First, by implementing the analysis in IncA we immediately improve the runtime after code changes through incrementality. Second, we add flow-sensitivity by building on top of our incremental control flow analysis. Third, we do not require the code to only use the four kinds of assignments in Andersen’s rules, rather support all of mbeddr C except pointer arithmetics.

The PointsToAnalysis module contains the implementation in MPS.

Well-formedness Checks for mbeddr C Code

We implemented four well-formedness checks for mbeddr C and its language extensions. The WellFormedness module contains the implementation in MPS.

FindBugs for Java


The FindBugs module contains the implementation in MPS.

4 - Evaluation

We evaluated the performance of IncA program analyses on three case studies with programmatically introduced program changes:

We repeated each measurement five times and discarded the results of the first and second run to account for the Java VM warm-up. The raw memory and runtime measurement results are available for all case studies: [runtime][memory].

The following YouTube video guides you through the case studies and the performance evaluation.