Konstantin Solomatov's Weblog

  • Categories

  • Archives

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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: