# Data flow analysis question

## saswat@cc.gatech.edu (Saswat)15 Mar 2004 09:35:23 -0500

From comp.compilers

Related articles
Data flow analysis question saswat@cc.gatech.edu (2004-03-15)
| List of all articles for this month |

 From: saswat@cc.gatech.edu (Saswat) Newsgroups: comp.compilers Date: 15 Mar 2004 09:35:23 -0500 Organization: http://groups.google.com Keywords: analysis, question Posted-Date: 15 Mar 2004 09:35:22 EST

Hello,

I am faced with this analysis problem that seems to be useful in
compilers and software engineering tools. So I am trying to find if it
has already been solved or any reference to similar problems. If the
problem sounds familiar please direct me to the reference.

Roughly, the analysis finds out all statement pairs (s1, s2) that use
the same variable (say x) such that, s2 always follows s1 and when s1
uses a particular definition of x, say p, the following s2 also use
the same definition of x (ie. p).

Formally:
For a procedure, suppose we have a trace of program statements of the
form \$s_{i_1}, s_{i_2} ... s_{i_n}\$ denoting the order in which
statements are executed. Let \$(s_{p/q})^+\$ denote a sequence of
statements in which \$s_p\$ occurs one or more number of times, but
\$s_q\$ does not occur. The goal of the analysis to find all statement
pairs \$s_p\$ and \$s_q\$ (that use the same variable) such that in the
trace:

1. every occurrence of a \$(s_{p/q})^+\$ sequence (\$S_1\$) in the trace
is followed by atleast one \$s_q\$
2. each occurrence of \$s_p\$ in \$S_1\$ and the following \$s_q\$ use the
same definition of \$x\$.

I was thinking of SSA. But does that take care all the cases?

Thanks
Saswat

Post a followup to this message