Correctly Slicing Extended Finite State Machines

We consider slicing extended finite state machines. Extended finite state machines (EFSMs) combine a finite state machine with a store and can model a range of computational phenomena, from high-level software to cyber-physical systems. EFSMs are essentially interactive, possibly non-terminating or with multiple exit states and may be nondeterministic, so standard techniques for slicing, developed for control flow graphs of programs with a functional semantics, are not immediately applicable.

This paper addresses the various aspects of correctness for slicing of EFSMs, and provides syntactic criteria that we prove are sufficient for our proposed notions of semantic correctness. The syntactic criteria are based on the “weak commitment” and “strong commitment” properties highlighted by Danicic et alia. We provide polynomial-time algorithms to compute the least sets satisfying each of these two properties. We have conducted experiments using widely-studied benchmark and industrial EFSMs that compare our slicing algorithms with those using existing definitions of control dependence. We found that our algorithms produce the smallest average slices sizes, 21% of the original EFSMs when “weak commitment” is sufficient and 58% when “strong commitment” is needed (to preserve termination properties).

1. 1.

   Published as Research Note RN/13/22 from University College London.

Authors and Affiliations

1. Kansas State University, Manhattan, KS, 66506, USA

   Torben Amtoft

2. Middlesex University, London, NW4 4BT, UK

   Kelly Androutsopoulos

3. University College London, London, WC1E 6BT, UK

   David Clark

Corresponding author

Correspondence to Torben Amtoft .

Editors and Affiliations

1. University of Verona, Verona, Italy

   Alessandra Di Pierro

2. School of Electronic Engineering and Computer Science, Queen Mary University of London, London, UK

   Pasquale Malacaria

3. Department of Computer Science, Middlesex University, London, UK

   Rajagopal Nagarajan

A Proofs of Completeness and (Weak/Strong) Soundness

We shall now prove the correctness theorems from Sect. 4, but shall first establish some generally applicable results.

1.1 A.1 General Results

Lemma 31

Assume that \(\mathcal {L}\) is closed under \(\rightarrow _{\mathrm {dd}}\), and that \(t \notin \mathcal {L}\). With \(n = \mathsf {S}(t)\) and \(n' = \mathsf {T}(t)\) we then have \({ Rv}_{{\mathcal {L}}}({n'}) \subseteq { Rv}_{{\mathcal {L}}}({n})\), and if \({i}\,\vdash \,{t}:\, {(n,s)}\,\overset{{E}}{\rightarrow }\,{(n',s')}\) for some \(i \in \{{1,2}\}\) then \(s(v) = s'(v)\) for all \(v \in { Rv}({n'})\).

Proof

Consider \(v \in { Rv}({n'})\). There exists a path \([t_1..t_k]\) with \(k \ge 1\) from \(n'\) such that \(t_k \in \mathcal {L}\) with \(v \in \mathsf {U}(t_k)\) and such that \(v \notin \mathsf {D}(t_j)\) for all \(j \in {1}\ldots {k-1}\).

Assume, to get a contradiction, that \(v \in \mathsf {D}(t)\). Then \({t} \rightarrow _{\mathrm {dd}}{t_k}\), which together with \(t_k \in \mathcal {L}\) and \(t \notin \mathcal {L}\) contradicts \(\mathcal {L}\) being closed under \(\rightarrow _{\mathrm {dd}}\).

Hence \(v \notin \mathsf {D}(t)\). Thus the path \([t,t_1..t_k]\) will establish \(v \in { Rv}({n})\), and if \({i}\,\vdash \,{t}:\, {(n,s)}\,\overset{{E}}{\rightarrow }\,{(n',s')}\) then \(s'(v) = s(v)\) (no matter whether \(i = 1\) or \(i = 2\)).

Lemma 32

Assume that for \(t \in \mathcal {L}\) we have

\({1}\,\vdash \,{t}:\, {(n,s_1)}\,\overset{{E}}{\rightarrow }\,{(n',s'_1)}\) and

\({2}\,\vdash \,{t}:\, {(n,s_2)}\,\overset{{E}}{\rightarrow }\,{(n',s'_2)}\)

where \(s_1(v) = s_2(v)\) for all \(v \in { Rv}({n})\). Then \(s'_1(v) = s'_2(v)\) for all \(v \in { Rv}({n'})\).

Proof

Let \(v \in { Rv}({n'})\) be given, so as to show \(s'_1(v) = s'_2(v)\). We split into two cases.

The first case is when \(v \notin \mathsf {D}(t)\). Then \(v \in { Rv}({n})\), implying the desired equality \(s'_1(v) = s_1(v) = s_2(v) = s'_2(v)\).

The second case is when \(v \in \mathsf {D}(t)\), where we must prove that \([\![{A}]\!]{s_1} = [\![{A}]\!]{s_2}\) where \(A = {\mathsf {A}(t)}[{c}/{v_b}]\) if E is of the form e(c), and \(A = \mathsf {A}(t)\) otherwise. But this follows from the fact that for all \(w \in { fv}({A}) = { fv}({\mathsf {A}(t)}) \setminus \{{v_b}\}\) we have \(s_1(w) = s_2(w)\), since \(w \in \mathsf {U}(t)\) and thus (as \(t \in \mathcal {L}\)) also \(w \in { Rv}({t}) \subseteq { Rv}({n})\).

1.2 A.2 Proving Completeness

We shall first establish some intermediate results:

Lemma 33

Assume that \(\mathcal {L}\) is closed under \(\rightarrow _{\mathrm {dd}}\). If with \(t \notin \mathcal {L}\) we have

• \({1}\,\vdash \,{t}:\, {(n,s_1)}\,\overset{{E_1}}{\rightarrow }\,{(n',s'_1)}\) and

• \(s_1(v) = s_2(v)\) for all \(v \in { Rv}({n})\)

then

• \({2}\,\vdash \,{t}:\, {(n,s_2)}\,\overset{{\varepsilon }}{\rightarrow }\,{(n',s_2)}\) and

• \(s'_1(v) = s_2(v)\) for all \(v \in { Rv}({n'})\).

where \(\mathsf {filter}({E_1}) = \varepsilon \) if \(\mathcal {L}\) is uniform.

Proof

Since \(t \notin \mathcal {L}\), we see that \(\mathsf {G}_{{2}}(t) = \textit{true}\) and \(\mathsf {E}_{{2}}(t) = \varepsilon \) and \(\mathsf {D}_{{2}}(t) = \emptyset \) which yields the first claim. For the second claim, consider \(v \in { Rv}({n'})\): since \(t \notin \mathcal {L}\), we infer by Lemma 31 that \(s_1(v) = s'_1(v)\), and that \(v \in { Rv}({n})\) which by assumption implies \(s_1(v) = s_2(v)\); hence we can conclude that \(s'_1(v) = s_2(v)\). The last claim follows from Fact 11.

Lemma 34

If with \(t \in \mathcal {L}\) we have

• \({1}\,\vdash \,{t}:\, {(n,s_1)}\,\overset{{E}}{\rightarrow }\,{(n',s'_1)}\) and

• \(s_1(v) = s_2(v)\) for all \(v \in { Rv}({n})\)

then there exists \(s'_2\) such that

• \({2}\,\vdash \,{t}:\, {(n,s_2)}\,\overset{{E}}{\rightarrow }\,{(n',s'_2)}\) and

• \(s'_1(v) = s'_2(v)\) for all \(v \in { Rv}({n'})\).

Proof

Our assumptions entail \(n = \mathsf {S}(t)\), \(n' = \mathsf {T}(t)\), \(\mathsf {G}_{{1}}(t) = \mathsf {G}_{{2}}(t) = \mathsf {G}(t)\), and \([\![{g}]\!]{s_1} = \textit{true}\) where \(g = {\mathsf {G}(t)}[{c}/{v_b}]\) if E is of the form e(c), and \(g = \mathsf {G}(t)\) otherwise. For an arbitrary \(w \in { fv}({\mathsf {G}(t)}) \setminus \{v_b\}\) we infer by Fact 13 that \(w \in { Rv}({t}) \subseteq { Rv}({n})\), implying \(s_1(w) = s_2(w)\). Hence also \([\![{g}]\!]{s_2} = \textit{true}\), implying that there exists \(s'_2\) such that \({2}\,\vdash \,{t}:\, {(n,s_2)}\,\overset{{E}}{\rightarrow }\,{(n',s'_2)}\). That \(s'_1(v) = s'_2(v)\) for all \(v \in { Rv}({n'})\) now follows from Lemma 32.

Theorem 1 (Completeness): Assume that \(\mathcal {L}\) is closed under \(\rightarrow _{\mathrm {dd}}\). If

• \({1}\,\vdash _{\text{ ni }}\,{\pi }:\ {C_1}\,\overset{{E}}{\longrightarrow }\,{C'_1}\) and

• \(C_1 \;Q\;C_2\)

then there exists \(C'_2\) such that

• \({2}\,\vdash \,{\pi }:\ {C_2}\,\overset{{E}}{\longrightarrow }\,{C'_2}\) and

• \(C'_1 \;Q\;C'_2\).

Moreover, if \(\mathcal {L}\) is uniform then \({2}\,\vdash _{\text{ ni }}\,{\pi }:\ {C_2}\,\overset{{\mathsf {filter}({E})}}{\longrightarrow }\,{C'_2}\).

Proof

We do induction in the length of \(\pi \). If \(\pi \) is empty, then \(C'_1 = C_1\) and \(E_1 = \varepsilon \), and the claim is trivial with \(C'_2 = C_2\).

If \(\pi \) is a singleton t, we split into two cases: if \(t \in \mathcal {L}\) then the claim follows from Lemma 34; if \(t \notin \mathcal {L}\) then the claim follows from Lemma 33.

Now assume that \(\pi \) can be written \(\pi = \pi '' \pi '\) with \(\pi '\) and \(\pi ''\) not empty. It is easy to see that there exists \(E''\) and \(E'\) with \(E = E'' E'\) such that \({1}\,\vdash _{\text{ ni }}\,{\pi ''}:\ {C_1}\,\overset{{E''}}{\longrightarrow }\,{C''_1}\) and \({1}\,\vdash _{\text{ ni }}\,{\pi '}:\ {C''_1}\,\overset{{E'}}{\longrightarrow }\,{C'_1}\). Inductively on \(\pi ''\), there exists \(C''_2\) with \(C''_1 \;Q\;C''_2\) such that \({2}\,\vdash \,{\pi ''}:\ {C_2}\,\overset{{E''}}{\longrightarrow }\,{C''_2}\); inductively on \(\pi '\), there then exists \(C'_2\) with \(C'_1 \;Q\;C'_2\) such that \({2}\,\vdash \,{\pi '}:\ {C''_2}\,\overset{{E'}}{\longrightarrow }\,{C'_2}\). But then it is easy to see that we have the desired \({2}\,\vdash \,{\pi }:\ {C_2}\,\overset{{E}}{\longrightarrow }\,{C'_2}\). Finally, if \(\mathcal {L}\) is uniform, we inductively get \({2}\,\vdash _{\text{ ni }}\,{\pi ''}:\ {C_2}\,\overset{{\mathsf {filter}({E''})}}{\longrightarrow }\,{C''_2}\) and \({2}\,\vdash _{\text{ ni }}\,{\pi '}:\ {C''_2}\,\overset{{\mathsf {filter}({E'})}}{\longrightarrow }\,{C'_2}\) and thus clearly also \({2}\,\vdash _{\text{ ni }}\,{\pi }:\ {C_2}\,\overset{{\mathsf {filter}({E''})\mathsf {filter}({E'})}}{\longrightarrow }\,{C'_2}\) which yields the claim since \(\mathsf {filter}({E}) = \mathsf {filter}({E''}) \mathsf {filter}({E'})\).

1.3 A.3 Proving Soundness

As discussed in Sect. 3.4, we cannot quite hope for the converse of Theorem 1 in that the original EFSM may get stuck, or loop, rather than reach the next observable state. This is formalized by the following result:

Lemma 35

Let \( obs ({n}) = \{{m}\}\). Given s, one of the 3 cases below applies:

1. 1.

   there exists E and \(s'\) such that \({1}\,\vdash _{\text{ ni }}\,{(n,s)}\,\overset{{E}}{\Longrightarrow }\,{(m,s')}\)

2. 2.

   the original EFSM gets stuck from (n, s) avoiding \(\mathcal {L}\)

3. 3.

   the original EFMS loops from (n, s) avoiding \(\mathcal {L}\).

Proof

Consider the following iterative algorithm, incrementally constructing \(n_j\), \(s_j\), \(E_j\) for \(j \ge 0\). With \(n_0 = n\), \(s_0 = s\) and \(E_0 = \varepsilon \), the invariant is that

This trivially holds for \(j = 0\). For each iteration (with \(j \ge 0\)), there are 3 possible actions: if \(n_j = m\) we exit the loop, and we have established case 1 with \(E = E_j\) and \(s' = s_j\).

Otherwise, if \(n_j \ne m\), we can infer that \(n_j\) is not the source of a transition in \(\mathcal {L}\), since if \(n_j = \mathsf {S}(t)\) with \(t \in \mathcal {L}\) then \(n_j \in obs ({n}) = \{{m}\}\). There are now two possibilities:

• if there exists t with \(\mathsf {S}(t) = n_j\) such that \([\![{\mathsf {G}(t)}]\!]{s_j} = \textit{true}\), or such that \([\![{{\mathsf {G}_{{i}}(t)}[{c}/{v_b}]}]\!]{s} = \textit{true}\) for some c if \(\mathsf {E}_{{i}}(t)\) is of the form \(e(v_b)\), we define \(t_{j+1}\) as one such t (say the “smallest”). Then there exists \(n_{j+1}\) and \(s_{j+1}\) and \(E'_j\) such that

  $$ {1}\,\vdash \,{t_j}:\, {(n_j,s_j)}\,\overset{{E'_j}}{\rightarrow }\,{(n_{j+1},s_{j+1})} $$

  Let \(E_{j+1} = E_j E'_j\). We then increment j by one and repeat the loop; the invariant will be maintained since \(t \notin \mathcal {L}\) and \(n_j\) is not the source of a transition in \(\mathcal {L}\).

• otherwise, we exit the loop, concluding that \((n_j,s_j)\) is 1-stuck which establishes case 2.

If we never exit the loop, this will establish case 3.

Theorem 2 (Weak Soundness): Assume that \(\mathcal {L}\) is closed under \(\rightarrow _{\mathrm {dd}}\) and satisfies \(\mathcal {WCC}\). If \({2}\,\vdash _{\text{ ni }}^{{t}}\,{C_2}\,\overset{{E_2}}{\Rightarrow \rightarrow }\,{C'_2}\) and \(C_1 \;Q\;C_2\) then there are 3 possibilities:

1. 1.

   \({1}\,\vdash _{\text{ ni }}^{{t}}\,{C_1}\,\overset{{E_1 E_2}}{\Rightarrow \rightarrow }\,{C'_1}\) for some \(C'_1, E_1\) with \(C'_1 \;Q\;C'_2\) (and if \(\mathcal {L}\) is uniform then \(\mathsf {filter}({E_1}) = \varepsilon \)), or

2. 2.

   the original EFSM gets stuck from \(C_1\) avoiding \(\mathcal {L}\) (cf. Definition 15), or

3. 3.

   the original EFSM loops from \(C_1\) avoiding \(\mathcal {L}\) (cf. Definition 16).

Proof

Let \(C_2 = (n,s_2)\) and \(C'_2 = (n',s'_2)\) and \(C_1 = (n,s_1)\). From Definition 9 and Fact 8 we see that \(t \in \mathcal {L}\) and that for some m: \({2}\,\vdash _{\text{ ni }}\,{(n,s_2)}\,\overset{{\varepsilon }}{\Longrightarrow }\,{(m,s_2)}\) and \({2}\,\vdash \,{t}:\, {(m,s_2)}\,\overset{{E_2}}{\rightarrow }\,{(n',s'_2)}\). Thus \(m \in obs ({n})\), and from the \(\mathcal {WCC}\) property we infer \( obs ({n}) = \{{m}\}\). Lemma 35 now tells us that either

1. 1.

   there exists \(E_1\) and \(s''_1\) such that \({1}\,\vdash _{\text{ ni }}\,{(n,s_1)}\,\overset{{E_1}}{\Longrightarrow }\,{(m,s''_1)}\), or

2. 2.

   the original EFSM gets stuck from \((n,s_1)\) avoiding \(\mathcal {L}\), or

3. 3.

   the original EFSM loops from \((n,s_1)\) avoiding \(\mathcal {L}\).

If case 2 or case 3 holds, we are done. We thus assume that case 1 holds (and from Fact 11 we see that if \(\mathcal {L}\) is uniform then \(\mathsf {filter}({E_1}) = \varepsilon \)).

By assumption, we have \(s_1(v) = s_2(v)\) for all \(v \in { Rv}({n})\). By repeated application of Lemma 31, we infer that \({ Rv}({m}) \subseteq { Rv}({n})\) and that \(s''_1(v) = s_1(v)\) for all \(v \in { Rv}({m})\). Thus \(s''_1(v) = s_2(v)\) for all \(v \in { Rv}({m})\), which establishes

From \(t \in \mathcal {L}\) we have \(\mathsf {G}_{{1}}(t) = \mathsf {G}_{{2}}(t) = \mathsf {G}(t)\), and from \({2}\,\vdash \,{t}:\, {(m,s_2)}\,\overset{{E_2}}{\rightarrow }\,{(n',s'_2)}\) we know that \([\![{g}]\!]{s_2} = \textit{true}\) where \(g = {\mathsf {G}(t)}[{c}/{v_b}]\) if \(E_2\) is of the form e(c), and \(g = \mathsf {G}(t)\) otherwise. For an arbitrary \(w \in { fv}({\mathsf {G}_{{1}}(t)}) \setminus \{{v_b}\}\) we infer by Fact 13 that \(w \in { Rv}({t}) \subseteq { Rv}({m})\), implying \(s''_1(w) = s_2(w)\). Hence also \([\![{g}]\!]{s''_1} = \textit{true}\), implying that there exists \(s'_1\) such that \({1}\,\vdash \,{t}:\, {(m,s''_1)}\,\overset{{E_2}}{\rightarrow }\,{(n',s'_1)}\), and thus with \(C'_1 = (n',s'_1)\) we have \({1}\,\vdash _{\text{ ni }}^{{t}}\,{C_1}\,\overset{{E_1 E_2}}{\Rightarrow \rightarrow }\,{C'_1}\). That \(C'_1 \;Q\;C'_2\), that is \(s'_1(v) = s'_2(v)\) for all \(v \in { Rv}({n'})\), now follows from Lemma 32.

If \(\mathcal {L}\) satisfies not just \(\mathcal {WCC}\) but also \(\mathcal {SCC}\), we can rule out case 3, which establishes

Theorem 3 (Strong Soundness): Assume \(\mathcal {L}\) is closed under \(\rightarrow _{\mathrm {dd}}\) and satisfies \(\mathcal {SCC}\).

If \({2}\,\vdash _{\text{ ni }}^{{t}}\,{C_2}\,\overset{{E_2}}{\Rightarrow \rightarrow }\,{C'_2}\) and \(C_1 \;Q\;C_2\) then there are 2 possibilities:

1. 1.

   \({1}\,\vdash _{\text{ ni }}^{{t}}\,{C_1}\,\overset{{E_1 E_2}}{\Rightarrow \rightarrow }\,{C'_1}\) for some \(C'_1, E_1\) with \(C'_1 \;Q\;C'_2\) (and if \(\mathcal {L}\) is uniform then \(\mathsf {filter}({E_1}) = \varepsilon \)), or

2. 2.

   the original EFSM gets stuck from \(C_1\) avoiding \(\mathcal {L}\).

B Proofs of Correctness for Algorithms Computing Least Slices

Theorem 5 (WCC Algorithm Correctness): Assuming that the table DD correctly computes data dependence, Algorithm 1 returns in L the least superset of \(\mathcal {L}\) that is closed under data dependence and satisfies \(\mathcal {WCC}\).

Proof

We shall first state a number of loop invariants for the inner loop; they are expressed in terms of k, the number of iterations so far. We shall use \(C^k\) to denote the value of C after k iterations; similarly we shall write \(V^k\) and \(X^k\) (it is convenient to let \(V^{-1} = \emptyset \)). For \(k \ge 0\) and each state n we define \( obs _{{L}}^{{k}}({n})\) as the set of states \(n'\) such that there exists t in L with \(\mathsf {S}(t) = n'\), and there exists a cycle-free path of length \(\le k\) outside L from n to \(n'\). We observe that \(n' \in obs _{{L}}^{{0}}({n})\) iff \(n' = n\) and n in B, that \( obs _{{L}}^{{k}}({n}) \subseteq obs _{{L}}^{{k'}}({n})\) if \(k \le k'\), and that \(n' \in obs _{{L}}({n})\) iff there exists \(k \ge 0\) such that \(n' \in obs _{{L}}^{{k}}({n})\).

The while loop invariants are, with \(k \ge 0\):

1. 1.

   \(V^k = \{n \mid X^k[n]\) is defined \(\}\)

2. 2.

   \(V^k\) is the disjoint union of \(V^{k-1}\) and \(C^k\)

3. 3.

   for all \(n \in V^k\), \(X^k[n] \in obs _{{L}}^{{k}}({n})\)

4. 4.

   for all n, if \( obs _{{L}}^{{k}}({n}) \ne \emptyset \) then \(n \in V^k\)

5. 5.

   if Lnew\(^{k}\) \(= \emptyset \) then \( obs _{{L}}^{{k}}({n}) = \{X^k[n]\}\) for all \(n \in V^k\)

6. 6.

   if \(L'\) satisfies \(\mathcal {WCC}\) with L \(\subseteq L'\) then Lnew \(\subseteq L'\)

It is easy to see that all invariants hold at loop entry, with \(k = 0\). We shall now argue that the invariants are maintained by the body of the while loop; in particular, that they hold for \(k+1\) where we can assume that they hold for k.

1. 1.

   This follows easily from inspecting the code.

2. 2.

   This follows easily from inspecting the code.

3. 3.

   The claim is obvious if \(X^{k+1}[n] = X^k[n]\) as then \(X^k[n] \in obs _{{L}}^{{k}}({n})\) (as invariant 3 holds before the iteration) and thus \(X^{k+1}[n] \in obs _{{L}}^{{k+1}}({n})\). Next consider the situation where \(X^{k+1}[n]\) assumes the value of \(X^k[m]\) because there exists \(t \notin \) L with \(\mathsf {T}(t) = m\) and \(\mathsf {S}(t) = n\) where \(m \in C^k\). Since invariant 3 holds before the iteration, we know that \(X^k[m] \in obs _{{L}}^{{k}}({m})\). As it is easy to see (as \(t \notin \) L) that \( obs _{{L}}^{{k}}({m}) \subseteq obs _{{L}}^{{k+1}}({n})\), this yields the desired \(X^{k+1}[n] \in obs _{{L}}^{{k+1}}({n})\).

4. 4.

   We assume that \( obs _{{L}}^{{k+1}}({n}) \ne \emptyset \). If also \( obs _{{L}}^{{k}}({n}) \ne \emptyset \), we know (since invariant 4 holds) that \(n \in V^k\) and thus \(n \in V^{k+1}\). We can thus assume that \( obs _{{L}}^{{k}}({n}) = \emptyset \), and infer that there exists \(t \notin \) L with \(\mathsf {S}(t) = n\) such that with \(m = \mathsf {T}(t)\) it holds that \( obs _{{L}}^{{k}}({m})\) is non-empty, but \( obs _{{L}}^{{k-1}}({m}) = \emptyset \). From invariants 4, 1, 3 and 2 we infer \(m \in V^k\) and even \(m \in C^k\). But then the iteration will add n to V so that \(n \in V^{k+1}\).

5. 5.

   We assume that Lnew remains empty; since we have already established invariant 3, our task is to prove that if \(n' \in obs _{{L}}^{{k+1}}({n})\) then \(n' = X^{k+1}[n]\). If \(n' \in obs _{{L}}^{{k}}({n})\), we know (from invariants 4 and 5) that \(n' = X^k[n]\) and thus also \(n' = X^{k+1}(n)\). So assume that \(n' \notin obs _{{L}}^{{k}}({n})\). The situation is that there exists \(t \notin \) L with \(n = \mathsf {S}(t)\) such that with \(m = \mathsf {T}(t)\) we have \(n' \in obs _{{L}}^{{k}}({m})\) but \(n' \notin obs _{{L}}^{{k-1}}({m})\). From \(n' \in obs _{{L}}^{{k}}({m})\), and Lnew being empty before the iteration (as otherwise the loop would exit), we see (as invariants 4 and  5 hold) that \(m \in V^k\) and \(X^k[m] = n'\) and \( obs _{{L}}^{{k}}({m}) = \{n'\}\). From \(n' \notin obs _{{L}}^{{k-1}}({m})\) we infer that \( obs _{{L}}^{{k-1}}({m}) = \emptyset \), and thus (from invariants 3 and 2) we have \(m \in C^k\). Thus t is considered during the iteration, and since Lnew remains empty, we infer that \(X^{k+1}[n] = n'\) (as X[n] will be assigned either due to t, or some other transition being considered before t).

6. 6.

   Let t be a member of Lnew\(^{k+1}\). With \(n = \mathsf {S}(t)\) and \(m = \mathsf {T}(t)\), we have \(n \in V^{k+1}\) and \(m \in C^{k}\), and there exists \(n'\) and \(m'\) with \(n' \ne m'\) such that \(n' = X^{k+1}[n]\) and \(m' = X^{k}[m]\). From invariant 3 we see that \(n' \in obs _{{L}}^{{k+1}}({n})\) and that \(m' \in obs _{{L}}^{{k}}({m})\) which implies \(m' \in obs _{{L}}^{{k+1}}({n})\). There thus exists a cycle-free path \(\pi _1\) from n to \(n'\), and a cycle-free path \(\pi _2\) from n to \(m'\). These paths can have nothing in common. For assume, to get a contradiction, that some node \(n''\) occurs on both paths. Then there exists j with \(j \le k\) such that \( obs _{{L}}^{{j}}({n''})\) is not a singleton. From invariant 5 we infer that Lnew\(^j\) is non-empty, but then the loop would exit after j iterations, which is a contradiction. Now assume that \(L'\) contains L and satisfies \(\mathcal {WCC}\). In particular, \( obs _{{L'}}({n})\) has to be at most a singleton. But since \( obs _{{L'}}({n})\) has to contain a node from \(\pi _1\), and also a node from \(\pi _2\), this is only possible if \( obs _{{L'}}({n}) = \{{n}\}\). But this can only happen if \(t \in L'\).

After having stated and proved the invariants for the while loop, let us now address the invariant for the repeat loop. It obviously holds initially. We shall now argue it is maintained by an iteration, which is obvious for the part about being closed under data dependence (due to the call of DDclose at the end of the body).

Now let \(L'\) be a superset of \(\mathcal {L}\) that is closed under data dependence and satisfies \(\mathcal {WCC}\). Our goal is to show that after an iteration, L \(\subseteq L'\). From the invariant, we know that L \(\subseteq L'\) holds before the iteration. From invariant 6 for the while loop, we see that Lnew \(\subseteq L'\). By the specification of DDclose, we infer that DDclose(L,Lnew) \(\subseteq L'\). But this is what we aimed to prove.

We are left with proving that L does indeed satisfy \(\mathcal {WCC}\) when the repeat loop exits, with Lnew \(= \emptyset \). Let the last iteration have k iterations of the while loop; thus \(C^k = \emptyset \) but \(C^{j} \ne \emptyset \) for \(j < k\).

Now assume, to get a contradiction, that L does not satisfy \(\mathcal {WCC}\).

There thus exists i and m such that \( obs _{{L}}^{{i}}({m})\) has at least two elements. We can assume that i is the least such number, that is: for \(j < i\) and all n, \( obs _{{L}}^{{j}}({n})\) is at most a singleton. We infer that there exists \(n'\) such that \(n' \in obs _{{L}}^{{i}}({m})\), and that there exists \(m'\) with \(m' \ne n'\) such that \(m' \in obs _{{L}}^{{i}}({m})\) but \(m' \notin obs _{{L}}^{{i-1}}({m})\). There thus exists \(m_0..m_i\) with \(m_i = m\) and \(m_0 = m'\), and a cycle-free path through \(m_i...m_0\) from m to \(m'\), such that for all \(j \in {0}\ldots {i}\) it holds that \(m' \in obs _{{L}}^{{j}}({m_j})\) but \(m' \notin obs _{{L}}^{{j-1}}({m_j})\). For \(j < i\) we know, as \( obs _{{L}}^{{j}}({m_j})\) is at most a singleton, that \( obs _{{L}}^{{j}}({m_j}) = \{{m'}\}\), and thus \( obs _{{L}}^{{j-1}}({m_j}) = \emptyset \) from which we infer that \(m_j \in V^j \setminus V^{j-1} = C^j\). Since \(C^j \ne \emptyset \) for \(j < i\), and \(C^k = \emptyset \), we infer that \(i \le k\). Thus \( obs _{{L}}^{{k}}({m})\) has at least two elements. But this conflicts with invariant 5 for the while loop, giving the desired contradiction.

Theorem 7 (SCC Algorithm Correctness): Assuming that the table DD correctly computes data dependence, Algorithm 2 (using Algorithm 3) returns in L the least superset of \(\mathcal {L}\) that is closed under data dependence and satisfies \(\mathcal {SCC}\).

Proof

The proof is quite similar to the proof of Theorem 5; we shall only list the features to be added.

First, we need to add the following invariant for the while loop:

To prove this, first observe that if \(n = n'\), and hence when \(k = 0\), the claim is trivial. We may thus assume that \(k > 0\) and \(n' \ne n\). By invariant 3 we have \(n' \in obs _{{L}}^{{k}}({n})\). Thus there exists \(t \notin \) L with \(n = \mathsf {S}(t)\) such that with \(m = \mathsf {T}(t)\) we have \(n' \in obs _{{L}}^{{k-1}}({m})\) and by invariant 4 thus \(m \in V^{k-1}\). We infer that \(m \in C^j\) for some \(j \le k-1\) and hence the \((j+1)\)th iteration will examine t. Since Lnew\(^{j+1} = \emptyset \), we infer that LoopAvoids(n, \(n'\)) does not hold, and hence (by Fact 24) there is no infinite path from n that avoids \(n'\).

Also, we need to modify Invariant 6 for the while loop into:

To see that this invariant is maintained, assume that \(L'\) contains L and satisfies \(\mathcal {SCC}\) (and thus also \(\mathcal {WCC}\)), and that t is a member of Lnew\(^{k+1}\); we must show that \(t \in L'\).

If t was added by line 17 of Algorithm 2, we can reason as in the proof of Theorem 7 to show that \(t \in L'\).

We can therefore assume that t was added by Line 14. With \(n = \mathsf {S}(t)\) and \(m = \mathsf {T}(t)\) and \(m' = X^k[m]\), so that there is a cycle-free path \(\pi \) outside L from n to \(m'\) that starts with t, there thus is a infinite path from n that avoids \(m'\).

Assume, to get a contradiction, that \(t \notin L'\). Then \( obs _{{L'}}({n})\) (which obviously cannot be empty) would consist of a node in \(\pi \) different from n, say \(n'\). There exists \(i \le k\) such that \(m' = X^i[n']\), and as Lnew\(^i = \emptyset \) we see by (1) that no infinite path from \(n'\) avoids \(m'\). But then there is an infinite path from n that avoids \(n'\), as otherwise no infinite path from n would avoid \(m'\). Since \( obs _{{L'}}({n}) = \{n'\}\), this contradicts \(L'\) satisfying \(\mathcal {SCC}\). We conclude that \(t \in L'\), as desired.

Having proved that (2) and (1) are indeed extra invariants for the while loop, we can now proceed as in the proof of Theorem 5 to show the correctness of the invariant listed in Algorithm 2 for the repeat loop.

We are left with proving that L does indeed satisfy \(\mathcal {SCC}\) when the repeat loop exits, with Lnew \(= \emptyset \). Let the last iteration have k iterations of the while loop; thus \(C^k = \emptyset \) but \(C^{j} \ne \emptyset \) for \(j < k\).

Now assume, to get a contradiction, that L does not satisfy \(\mathcal {SCC}\). There can be two reasons for this: if L does not satisfy \(\mathcal {WCC}\), we can show as in the proof of Theorem 5 that this conflicts with invariant 5 for the while loop.

We can thus assume that L satisfies \(\mathcal {WCC}\) but not \(\mathcal {SCC}\). Then there exists n and \(n'\) such that \(n' \in obs _{{L}}({n})\), and yet there is an infinite path from n that avoids \(n'\). Let i be the smallest number such that \(n' \in obs _{{L}}^{{i}}({n})\). There thus exists \(n_0..n_i\) with \(n_i = n\) and \(n_0 = n'\), and a cycle-free path through \(n_i...n_0\) from n to \(n'\), such that for all \(j \in {0}\ldots {i}\) it holds that \(n' \in obs _{{L}}^{{j}}({n_j})\) but \(n' \notin obs _{{L}}^{{j-1}}({n_j})\). For \(j \le i\) we know, as \( obs _{{L}}^{{j}}({n_j})\) is at most a singleton, that \( obs _{{L}}^{{j}}({n_j}) = \{{n'}\}\), and thus \( obs _{{L}}^{{j-1}}({n_j}) = \emptyset \) from which we infer that \(n_j \in V^j \setminus V^{j-1} = C^j\). Since \(C^j \ne \emptyset \) for \(j \le i\), and \(C^k = \emptyset \), we infer that \(i < k\). Thus \(n' \in obs _{{L}}^{{k}}({n})\), and hence (by invariant 5 for the while loop) \(n' = X^k[n]\). But then an infinite path from n that avoids \(n'\) conflicts with (1), giving the desired contradiction.

Reprints and permissions

© 2020 Springer Nature Switzerland AG

Policies and ethics