Konstantin Solomatov's Weblog

Data Flow Analysis In JetBrains MPS

Posted by Konstantin Solomatov on April 8, 2008

Data Flow analysis allows us to perform a lot of handy checks: we can find unused assignments, access to uninitialized variables, and it’s hardly possible to implement extract method refactoring without it. All in all, it dramatically improves experience of working with IDE. Of course we at JetBrains have implemented it in our meta-programming system and of course we created a language which can be used to describe data flow aspect of a language

In order to support data flow analysis in your language, you have to represent constructs of a language in terms of elementary instructions. Among them are:

  • read x – accesses variable x
  • write x – writes to variable x
  • jump p – unconditionally jumps to position p
  • ifjump p – conditionally jumps to position p
  • ret – return from current program

As you can see, these instructions are quite simple. It’s impossible to write a working program with them but for the kinds of data flow analysis we are interested in they are more than enough.

Let’s consider a simple example. Here is a code for do..while loop:

First we insert code for a loop’s body with “code for” statement. Then we insert code for condition. After evaluating condition, we perform conditional jump to the start of code for a while statement. Gray braces represent code which can be unreachable (we perform reachability analysis using these instructions graph). As you can see, this code is very simple and domain specific.

Let’s consider a more complex example: switch statement

First, we evaluate expression which value we switch on. Then we add conditional jumps to starts of case blocks. Finally, we add code for default case:

P.S. Almost all of this stuff is accessible in the latest build which you can download from here

P.P.S. You can read this post in Russian here

Posted in MPS | Leave a Comment »