Overview of Analysis

We take as input an AG description of a structure and a fragment of code as described previously. We can then create a number of FSAs that describe certain properties of the program. The definition FSA $\mathcal{F}_{def} (C,p)$, accepts the control word C and path-name pif the control word writes (or defines) that node of the structure. Similarly we can create a $\mathcal{F}_{use} (C,p)$ for describing nodes that are read by a particular statement. When we combine these FSAs to produce the conflict FSA, given by $\mathcal{F}_{use} . (\mathcal{F}_{def})^{-1}$, we have a description that links each read statement to a set of potential sources. We can simplify this further by removing potential sources that occur after the sink. For more technical details see [LA98].

Since we cannot determine which statements will actually be executed we cannot in general refine this to produce more accurate dataflow information.

We can also create FSAs for the different variants of dependency, for example read after write, write after write.