1 | \section{The proof} |
---|
2 | |
---|
3 | In this section, we present the correctness proof for the algorithm in more |
---|
4 | detail. The main correctness statement is as follows (slightly simplified, here): |
---|
5 | |
---|
6 | \begin{alignat*}{6} |
---|
7 | \mathtt{sigma}&\omit\rlap{$\mathtt{\_policy\_specification} \equiv |
---|
8 | \lambda program.\lambda sigma.\lambda policy.$} \notag\\ |
---|
9 | & \omit\rlap{$sigma\ 0 = 0\ \wedge$} \notag\\ |
---|
10 | & \mathbf{let}\ & & \omit\rlap{$instr\_list \equiv code\ program\ \mathbf{in}$} \notag\\ |
---|
11 | &&& \omit\rlap{$\forall ppc.ppc < |instr\_list| \rightarrow$} \notag\\ |
---|
12 | &&& \mathbf{let}\ && pc \equiv sigma\ ppc\ \mathbf{in} \notag\\ |
---|
13 | &&& \mathbf{let}\ && instruction \equiv \mathtt{fetch\_pseudo\_instruction}\ instr\_list\ ppc\ \mathbf{in} \notag\\ |
---|
14 | &&& \mathbf{let}\ && next\_pc \equiv sigma\ (ppc+1)\ \mathbf{in}\notag\\ |
---|
15 | &&&&& next\_pc = pc + \mathtt{instruction\_size}\ sigma\ policy\ ppc\ instruction\ \wedge\notag\\ |
---|
16 | &&&&& (pc + \mathtt{instruction\_size}\ sigma\ policy\ ppc\ instruction < 2^{16}\ \vee\notag\\ |
---|
17 | &&&&& (\forall ppc'.ppc' < |instr\_list| \rightarrow ppc < ppc' \rightarrow \notag\\ |
---|
18 | &&&&& \mathbf{let}\ instruction' \equiv \mathtt{fetch\_pseudo\_instruction}\ instr\_list\ ppc'\ ppc\_ok'\ \mathbf{in} \notag\\ |
---|
19 | &&&&&\ \mathtt{instruction\_size}\ sigma\ policy\ ppc'\ instruction' = 0)\ \wedge \notag\\ |
---|
20 | &&&&& pc + (\mathtt{instruction\_size}\ sigma\ policy\ ppc\ instruction = 2^{16})) |
---|
21 | \end{alignat*} |
---|
22 | |
---|
23 | Informally, this means that when fetching a pseudo-instruction at $ppc$, the |
---|
24 | translation by $\sigma$ of $ppc+1$ is the same as $\sigma(ppc)$ plus the size |
---|
25 | of the instruction at $ppc$. That is, an instruction is placed consecutively |
---|
26 | after the previous one, and there are no overlaps. |
---|
27 | |
---|
28 | Instructions are also stocked in |
---|
29 | order: the memory address of the instruction at $ppc$ should be smaller than |
---|
30 | the memory address of the instruction at $ppc+1$. There is one exeception to |
---|
31 | this rule: the instruction at the very end of the program, whose successor |
---|
32 | address can be zero (this is the case where the program size is exactly equal |
---|
33 | to the amount of memory). |
---|
34 | |
---|
35 | Finally, we enforce that the program starts at address 0, i.e. $\sigma(0) = 0$. |
---|
36 | |
---|
37 | Since our computation is a least fixed point computation, we must prove |
---|
38 | termination in order to prove correctness: if the algorithm is halted after |
---|
39 | a number of steps without reaching a fixed point, the solution is not |
---|
40 | guaranteed to be correct. More specifically, branch instructions might be |
---|
41 | encoded which do not coincide with the span between their location and their |
---|
42 | destination. |
---|
43 | |
---|
44 | Proof of termination rests on the fact that the encoding of branch |
---|
45 | instructions can only grow larger, which means that we must reach a fixed point |
---|
46 | after at most $2n$ iterations, with $n$ the number of branch instructions in |
---|
47 | the program. This worst case is reached if at every iteration, we change the |
---|
48 | encoding of exactly one branch instruction; since the encoding of any branch |
---|
49 | instructions can change first from short to absolute and then from absolute to |
---|
50 | long, there can be at most $2n$ changes. |
---|
51 | |
---|
52 | The proof has been carried out using the ``Russell'' style from~\cite{Sozeau2006}. |
---|
53 | We have proven some invariants of the {\sc f} function from the previous |
---|
54 | section; these invariants are then used to prove properties that hold for every |
---|
55 | iteration of the fixed point computation; and finally, we can prove some |
---|
56 | properties of the fixed point. |
---|
57 | |
---|
58 | \subsection{Fold invariants} |
---|
59 | |
---|
60 | These are the invariants that hold during the fold of {\sc f} over the program, |
---|
61 | and that will later on be used to prove the properties of the iteration. |
---|
62 | |
---|
63 | Note that during the fixed point computation, the $\sigma$ function is |
---|
64 | implemented as a trie for ease of access; computing $\sigma(x)$ is achieved by looking |
---|
65 | up the value of $x$ in the trie. Actually, during the fold, the value we |
---|
66 | pass along is a pair $\mathbb{N} \times \mathtt{ppc\_pc\_map}$. The first component |
---|
67 | is the number of bytes added to the program so far with respect to |
---|
68 | the previous iteration, and the second component, {\tt ppc\_pc\_map}, is the |
---|
69 | acual $\sigma$ trie. |
---|
70 | |
---|
71 | \begin{alignat*}{2} |
---|
72 | \mathtt{out} & \mathtt{\_of\_program\_none} \equiv \lambda prefix.\lambda sigma. \notag\\ |
---|
73 | & \forall i.i < 2^{16} \rightarrow (i > |prefix| \leftrightarrow |
---|
74 | \mathtt{lookup\_opt}\ i\ (\mathtt{snd}\ sigma) = \mathtt{None}) |
---|
75 | \end{alignat*} |
---|
76 | |
---|
77 | This invariant states that any pseudo-address not yet examined is not |
---|
78 | present in the lookup trie. |
---|
79 | |
---|
80 | \begin{alignat*}{2} |
---|
81 | \mathtt{not} & \mathtt{\_jump\_default} \equiv \lambda prefix.\lambda sigma.\notag\\ |
---|
82 | & \forall i.i < |prefix| \rightarrow\notag\\ |
---|
83 | & \neg\mathtt{is\_jump}\ (\mathtt{nth}\ i\ prefix) \rightarrow\notag\\ |
---|
84 | & \mathtt{lookup}\ i\ (\mathtt{snd}\ sigma) = \mathtt{short\_jump} |
---|
85 | \end{alignat*} |
---|
86 | |
---|
87 | This invariant states that when we try to look up the jump length of a |
---|
88 | pseudo-address where there is no branch instruction, we will get the default |
---|
89 | value, a short jump. |
---|
90 | |
---|
91 | \begin{alignat*}{4} |
---|
92 | \mathtt{jump} & \omit\rlap{$\mathtt{\_increase} \equiv \lambda pc.\lambda op.\lambda p.$} \notag\\ |
---|
93 | & \omit\rlap{$\forall i.i < |prefix| \rightarrow$} \notag\\ |
---|
94 | & \mathbf{let}\ && oj \equiv \mathtt{lookup}\ i\ (\mathtt{snd}\ op)\ \mathbf{in} \notag\\ |
---|
95 | & \mathbf{let}\ && j \equiv \mathtt{lookup}\ i\ (\mathtt{snd}\ p)\ \mathbf{in} \notag\\ |
---|
96 | &&& \mathtt{jmpleq}\ oj\ j |
---|
97 | \end{alignat*} |
---|
98 | |
---|
99 | This invariant states that between iterations (with $op$ being the previous |
---|
100 | iteration, and $p$ the current one), jump lengths either remain equal or |
---|
101 | increase. It is needed for proving termination. |
---|
102 | |
---|
103 | \begin{alignat*}{6} |
---|
104 | \mathtt{sigma} & \omit\rlap{$\mathtt{\_compact\_unsafe} \equiv \lambda prefix.\lambda sigma.$}\notag\\ |
---|
105 | & \omit\rlap{$\forall n.n < |prefix| \rightarrow$}\notag\\ |
---|
106 | & \mathbf{match}\ && \omit\rlap{$\mathtt{lookup\_opt}\ n\ (\mathtt{snd}\ sigma)\ \mathbf{with}$}\notag\\ |
---|
107 | &&& \omit\rlap{$\mathtt{None} \Rightarrow \mathrm{False}$} \notag\\ |
---|
108 | &&& \omit\rlap{$\mathtt{Some}\ \langle pc, j \rangle \Rightarrow$} \notag\\ |
---|
109 | &&& \mathbf{match}\ && \mathtt{lookup\_opt}\ (n+1)\ (\mathtt{snd}\ sigma)\ \mathbf{with}\notag\\ |
---|
110 | &&&&& \mathtt{None} \Rightarrow \mathrm{False} \notag\\ |
---|
111 | &&&&& \mathtt{Some}\ \langle pc_1, j_1 \rangle \Rightarrow |
---|
112 | pc_1 = pc + \notag\\ |
---|
113 | &&&&& \ \ \mathtt{instruction\_size\_jmplen}\ j\ (\mathtt{nth}\ n\ prefix) |
---|
114 | \end{alignat*} |
---|
115 | |
---|
116 | This is a temporary formulation of the main property\\ |
---|
117 | ({\tt sigma\_policy\_specification}); its main difference |
---|
118 | from the final version is that it uses {\tt instruction\_size\_jmplen} to |
---|
119 | compute the instruction size. This function uses $j$ to compute the span |
---|
120 | of branch instructions (i.e. it uses the $\sigma$ function under construction), |
---|
121 | instead of looking at the distance between source and destination. This is |
---|
122 | because $\sigma$ is still under construction; later on we will prove that after |
---|
123 | the final iteration, {\tt sigma\_compact\_unsafe} is equivalent to the main |
---|
124 | property. |
---|
125 | |
---|
126 | \begin{alignat*}{6} |
---|
127 | \mathtt{sigma} & \omit\rlap{$\mathtt{\_safe} \equiv \lambda prefix.\lambda labels.\lambda old\_sigma.\lambda sigma$}\notag\\ |
---|
128 | & \omit\rlap{$\forall i.i < |prefix| \rightarrow$} \notag\\ |
---|
129 | & \omit\rlap{$\forall dest\_label.\mathtt{is\_jump\_to\ (\mathtt{nth}\ i\ prefix})\ dest\_label \rightarrow$} \notag\\ |
---|
130 | & \mathbf{let} && \omit\rlap{$\ paddr \equiv \mathtt{lookup}\ labels\ dest\_label\ \mathbf{in}$} \notag\\ |
---|
131 | & \mathbf{let} && \omit\rlap{$\ \langle j, src, dest \rangle \equiv$}\notag\\ |
---|
132 | &&& \omit\rlap{$\mathbf{if} \ paddr\ \leq\ i\ \mathbf{then}$}\notag\\ |
---|
133 | &&&&& \mathbf{let}\ \langle \_, j \rangle \equiv \mathtt{lookup}\ i\ (\mathtt{snd}\ sigma)\ \mathbf{in} \notag\\ |
---|
134 | &&&&& \mathbf{let}\ \langle pc\_plus\_jl, \_ \rangle \equiv \mathtt{lookup}\ (i+1)\ (\mathtt{snd}\ sigma)\ \mathbf{in}\notag\\ |
---|
135 | &&&&& \mathbf{let}\ \langle addr, \_ \rangle \equiv \mathtt{lookup}\ paddr\ (\mathtt{snd}\ sigma)\ \mathbf{in}\notag\\ |
---|
136 | &&&&& \langle j, pc\_plus\_jl, addr \rangle\notag\\ |
---|
137 | &&&\mathbf{else} \notag\\ |
---|
138 | &&&&&\mathbf{let}\ \langle \_, j \rangle \equiv \mathtt{lookup}\ i\ (\mathtt{snd}\ sigma)\ \mathbf{in} \notag\\ |
---|
139 | &&&&&\mathbf{let}\ \langle pc\_plus\_jl, \_ \rangle \equiv \mathtt{lookup}\ (i+1)\ (\mathtt{snd}\ old\_sigma)\ \mathbf{in}\notag\\ |
---|
140 | &&&&&\mathbf{let}\ \langle addr, \_ \rangle \equiv \mathtt{lookup}\ paddr\ (\mathtt{snd}\ old\_sigma)\ \mathbf{in}\notag\\ |
---|
141 | &&&&&\langle j, pc\_plus\_jl, addr \rangle\notag\\ |
---|
142 | &&&\omit\rlap{$\mathbf{in}$}\notag\\ |
---|
143 | &&&\mathbf{match} && \ j\ \mathbf{with} \notag\\ |
---|
144 | &&&&&\mathrm{short\_jump} \Rightarrow \mathtt{short\_jump\_valid}\ src\ dest\notag\\ |
---|
145 | &&&&&\mathrm{absolute\_jump} \Rightarrow \mathtt{absolute\_jump\_valid}\ src\ dest\notag\\ |
---|
146 | &&&&&\mathrm{long\_jump} \Rightarrow \mathrm{True} |
---|
147 | \end{alignat*} |
---|
148 | |
---|
149 | This is a more direct safety property: it states that branch instructions are |
---|
150 | encoded properly, and that no wrong branch instructions are chosen. |
---|
151 | |
---|
152 | Note that we compute the distance using the memory address of the instruction |
---|
153 | plus its size: this follows the behaviour of the MCS-51 microprocessor, which |
---|
154 | increases the program counter directly after fetching, and only then executes |
---|
155 | the branch instruction (by changing the program counter again). |
---|
156 | |
---|
157 | \begin{align*} |
---|
158 | & \mathtt{lookup}\ 0\ (\mathtt{snd}\ policy) = 0 \notag\\ |
---|
159 | & \mathtt{lookup}\ |prefix|\ (\mathtt{snd}\ policy) = \mathtt{fst}\ policy |
---|
160 | \end{align*} |
---|
161 | |
---|
162 | These two properties give the values of $\sigma$ for the start and end of the |
---|
163 | program; $\sigma(0) = 0$ and $\sigma(n)$, where $n$ is the number of |
---|
164 | instructions up until now, is equal to the maximum memory address so far. |
---|
165 | |
---|
166 | \begin{align*} |
---|
167 | & added = 0\ \rightarrow\ \mathtt{policy\_pc\_equal}\ prefix\ old\_sigma\ policy \notag\\ |
---|
168 | & \mathtt{policy\_jump\_equal}\ prefix\ old\_sigma\ policy\ \rightarrow\ added = 0 |
---|
169 | \end{align*} |
---|
170 | |
---|
171 | And finally, two properties that deal with what happens when the previous |
---|
172 | iteration does not change with respect to the current one. $added$ is a |
---|
173 | variable that keeps track of the number of bytes we have added to the program |
---|
174 | size by changing the encoding of branch instructions. If $added$ is 0, the program |
---|
175 | has not changed and vice versa. |
---|
176 | |
---|
177 | We need to use two different formulations, because the fact that $added$ is 0 |
---|
178 | does not guarantee that no branch instructions have changed. For instance, |
---|
179 | it is possible that we have replaced a short jump with an absolute jump, which |
---|
180 | does not change the size of the branch instruction. |
---|
181 | |
---|
182 | Therefore {\tt policy\_pc\_equal} states that $old\_sigma_1(x) = sigma_1(x)$, |
---|
183 | whereas {\tt policy\_jump\_equal} states that $old\_sigma_2(x) = sigma_2(x)$. |
---|
184 | This formulation is sufficient to prove termination and compactness. |
---|
185 | |
---|
186 | Proving these invariants is simple, usually by induction on the prefix length. |
---|
187 | |
---|
188 | \subsection{Iteration invariants} |
---|
189 | |
---|
190 | These are invariants that hold after the completion of an iteration. The main |
---|
191 | difference between these invariants and the fold invariants is that after the |
---|
192 | completion of the fold, we check whether the program size does not supersede |
---|
193 | 64 Kb, the maximum memory size the MCS-51 can address. |
---|
194 | |
---|
195 | The type of an iteration therefore becomes an option type: {\tt None} in case |
---|
196 | the program becomes larger than 64 Kb, or $\mathtt{Some}\ \sigma$ |
---|
197 | otherwise. We also no longer use a natural number to pass along the number of |
---|
198 | bytes added to the program size, but a boolean that indicates whether we have |
---|
199 | changed something during the iteration or not. |
---|
200 | |
---|
201 | If an iteration returns {\tt None}, we have the following invariant: |
---|
202 | |
---|
203 | \begin{alignat*}{2} |
---|
204 | \mathtt{nec} & \mathtt{\_plus\_ultra} \equiv \lambda program.\lambda p. \notag\\ |
---|
205 | &\neg(\forall i.i < |program|\ \rightarrow \notag\\ |
---|
206 | & \mathtt{is\_jump}\ (\mathtt{nth}\ i\ program)\ \rightarrow \notag\\ |
---|
207 | & \mathtt{lookup}\ i\ (\mathtt{snd}\ p) = \mathrm{long\_jump}). |
---|
208 | \end{alignat*} |
---|
209 | |
---|
210 | This invariant is applied to $old\_sigma$; if our program becomes too large |
---|
211 | for memory, the previous iteration cannot have every branch instruction encoded |
---|
212 | as a long jump. This is needed later in the proof of termination. |
---|
213 | |
---|
214 | If the iteration returns $\mathtt{Some}\ \sigma$, the invariants |
---|
215 | {\tt out\_of\_program\_none},\\ |
---|
216 | {\tt not\_jump\_default}, {\tt jump\_increase}, |
---|
217 | and the two invariants that deal with $\sigma(0)$ and $\sigma(n)$ are |
---|
218 | retained without change. |
---|
219 | |
---|
220 | Instead of using {\tt sigma\_compact\_unsafe}, we can now use the proper |
---|
221 | invariant: |
---|
222 | |
---|
223 | \begin{alignat*}{6} |
---|
224 | \mathtt{sigma} & \omit\rlap{$\mathtt{\_compact} \equiv \lambda program.\lambda sigma.$} \notag\\ |
---|
225 | & \omit\rlap{$\forall n.n < |program|\ \rightarrow$} \notag\\ |
---|
226 | & \mathbf{match}\ && \omit\rlap{$\mathtt{lookup\_opt}\ n\ (\mathtt{snd}\ sigma)\ \mathbf{with}$}\notag\\ |
---|
227 | &&& \omit\rlap{$\mathrm{None}\ \Rightarrow\ \mathrm{False}$}\notag\\ |
---|
228 | &&& \omit\rlap{$\mathrm{Some}\ \langle pc, j \rangle \Rightarrow$}\notag\\ |
---|
229 | &&& \mathbf{match}\ && \mathtt{lookup\_opt}\ (n+1)\ (\mathtt{snd}\ sigma)\ \mathbf{with}\notag\\ |
---|
230 | &&&&& \mathrm{None}\ \Rightarrow\ \mathrm{False}\notag\\ |
---|
231 | &&&&& \mathrm{Some} \langle pc1, j1 \rangle \Rightarrow\notag\\ |
---|
232 | &&&&& \ \ pc1 = pc + \mathtt{instruction\_size}\ n\ (\mathtt{nth}\ n\ program) |
---|
233 | \end{alignat*} |
---|
234 | |
---|
235 | |
---|
236 | This is almost the same invariant as ${\tt sigma\_compact\_unsafe}$, but differs in that it |
---|
237 | computes the sizes of branch instructions by looking at the distance between |
---|
238 | position and destination using $\sigma$. |
---|
239 | |
---|
240 | In actual use, the invariant is qualified: $\sigma$ is compact if there have |
---|
241 | been no changes (i.e. the boolean passed along is {\tt true}). This is to |
---|
242 | reflect the fact that we are doing a least fixed point computation: the result |
---|
243 | is only correct when we have reached the fixed point. |
---|
244 | |
---|
245 | There is another, trivial, invariant if the iteration returns |
---|
246 | $\mathtt{Some}\ \sigma$: $\mathtt{fst}\ sigma = 2^{16}$. |
---|
247 | |
---|
248 | The invariants that are taken directly from the fold invariants are trivial to |
---|
249 | prove. |
---|
250 | |
---|
251 | The proof of {\tt nec\_plus\_ultra} works as follows: if we return {\tt None}, |
---|
252 | then the program size must be greater than 64 Kb. However, since the |
---|
253 | previous iteration did not return {\tt None} (because otherwise we would |
---|
254 | terminate immediately), the program size in the previous iteration must have |
---|
255 | been smaller than 64 Kb. |
---|
256 | |
---|
257 | Suppose that all the branch instructions in the previous iteration are |
---|
258 | encoded as long jumps. This means that all branch instructions in this |
---|
259 | iteration are long jumps as well, and therefore that both iterations are equal |
---|
260 | in the encoding of their branch instructions. Per the invariant, this means that |
---|
261 | $added = 0$, and therefore that all addresses in both iterations are equal. |
---|
262 | But if all addresses are equal, the program sizes must be equal too, which |
---|
263 | means that the program size in the current iteration must be smaller than |
---|
264 | 64 Kb. This contradicts the earlier hypothesis, hence not all branch |
---|
265 | instructions in the previous iteration are encoded as long jumps. |
---|
266 | |
---|
267 | The proof of {\tt sigma\_compact} follows from {\tt sigma\_compact\_unsafe} and |
---|
268 | the fact that we have reached a fixed point, i.e. the previous iteration and |
---|
269 | the current iteration are the same. This means that the results of |
---|
270 | {\tt instruction\_size\_jmplen} and {\tt instruction\_size} are the same. |
---|
271 | |
---|
272 | \subsection{Final properties} |
---|
273 | |
---|
274 | These are the invariants that hold after $2n$ iterations, where $n$ is the |
---|
275 | program size (we use the program size for convenience; we could also use the |
---|
276 | number of branch instructions, but this is more complex). Here, we only |
---|
277 | need {\tt out\_of\_program\_none}, {\tt sigma\_compact} and the fact that |
---|
278 | $\sigma(0) = 0$. |
---|
279 | |
---|
280 | Termination can now be proved using the fact that there is a $k \leq 2n$, with |
---|
281 | $n$ the length of the program, such that iteration $k$ is equal to iteration |
---|
282 | $k+1$. There are two possibilities: either there is a $k < 2n$ such that this |
---|
283 | property holds, or every iteration up to $2n$ is different. In the latter case, |
---|
284 | since the only changes between the iterations can be from shorter jumps to |
---|
285 | longer jumps, in iteration $2n$ every branch instruction must be encoded as |
---|
286 | a long jump. In this case, iteration $2n$ is equal to iteration $2n+1$ and the |
---|
287 | fixpoint is reached. |
---|