Example data flow analysis

  Here we will demonstrate the analysis for a particular restricted set of programs. The restrictions will be as follows:-

• Use structures with commuting/inverse directions.
• Restrict all read/write words to single letter words (directions and inverses), plus the empty word.
• All statements occur before all recursive calls in the function body.

We analyse each pair of statements in turn. The statements have the following format, where v is the current word, and we denote the write part of S_i as W_i and the read R_i.

With reference to this pair of statements, we now want to find, for any control word of the format P.R₂, the corresponding source of the form P'.W₁, if one exists. The actual source of the read would then be found by repeating the procedure for all write statements, and taking the latest one. We need to check for the legality of the path in order to ensure that the statements are actually executed.

Since it restricts the solution the most, we only consider the situation where r_i are inverses and w_i are straightforward directions, and are all distinct. Only r₁, r₂ and w₁ affect the legality of the data word, we must have directions r₁^-1, r₂^-1 and w₁ in the current data word before the current statement and its potential source will be executed. For readability we will rename these directions a,b,c, respectively. We also label the recursive calls in the same directions as A,B,C. This gives us a correspondence between an unnormalised path name and the control words that access them; we will use the two words interchangeably, and speak of A and B commuting, when it is actually a and b which do.

Firstly, in order to cancel the b^-1 inverse, we must be able to commute an existing b within the word to the end. Having cancelled it, for the source to be of the correct form, we must be able to cancel the a^-1, and move the c to the end of the path for the write part of the statement. This gives us that $a \sim c$; if not then S₁ can be disregarded as a potential source. Let us define the set of directions that commute with A as $\textrm{Com}(A)$, P can be one of six forms, depending on the relative position of the last A,B,C in the word. Some of the forms place additional restrictions on the commuting properties of the directions in order for the paths accessed to be legal.

The X_i are composed of directions with particular commuting properties. For example, in the first, we have $X_{1} \in \textrm{Com}(A)^{*}$, $X_{2} \in (\textrm{Com}(A) \cap\textrm{Com}(B))^{*}$ and $X_{2} \in (\textrm{Com}(A) \cap\textrm{Com}(B) \cap\textrm{Com}(C))^{*}$. For a given set of commuting properties we must consider each of the possible forms and produce a source for each. Additional constraints on the order of the statements can produce a description of the potential source that relies only on the structure of the word as given above. For example, suppose out of a,b,c, only directions a and c commute. This implies that the path is of the form of (2) or (5). If it is of the form of (2) then the corresponding read and write words will be:

Now provided C > X₁ , C > X₂ and C > W, the write will be a potential source. Similarly, for the second form we have the two control words:

This gives us a potential source provided that C > X₁ and C > A. For some of the other combinations, the form of the potential source depends on the actual structure of the sections of the control word, so describing the general solution is a more complex task.