# Changeset 3361 for src

Ignore:
Timestamp:
Jun 17, 2013, 12:11:13 PM (6 years ago)
Message:

15 pages version

Location:
src/ASM/CPP2012-policy
Files:
4 edited

Unmodified
Removed
• ## src/ASM/CPP2012-policy/algorithm.tex

 r3353 \subsection{Design decisions} Given the NP-completeness of the problem, to arrive at an optimal solution (using, for example, a constraint solver) will potentially take a great amount of time. Given the NP-completeness of the problem, finding optimal solutions (using, for example, a constraint solver) can potentially be very costly. The SDCC compiler~\cite{SDCC2011}, which has a backend targetting the MCS-51 and long jumps indefinitely. In order to keep the algorithm in the same complexity class and more easily To keep the algorithm in the same complexity class and more easily prove termination, we decided to explicitly enforce the `branch instructions must always grow longer' requirement: if a branch instruction is encoded as a long jump in one iteration, it will also be encoded as a long jump in all the following iterations. This means that the encoding of any branch instruction following iterations. Therefore the encoding of any branch instruction can change at most two times: once from short to absolute (or long), and once from absolute to long. in step $n$ as an absolute jump, but in step $n+1$ it is determined that (because of changes elsewhere) it can now be encoded as a short jump. Due to the requirement that the branch instructions must always grow longer, this means that the branch encoding will be encoded as an absolute jump in step the requirement that the branch instructions must always grow longer, the branch encoding will be encoded as an absolute jump in step $n+1$ as well. correctness, since a long jump is applicable in any situation. \begin{figure} \begin{figure}[t] \begin{algorithmic} \Function{f}{$labels$,$old\_sigma$,$instr$,$ppc$,$acc$}
• ## src/ASM/CPP2012-policy/main.tex

 r3342 \usepackage[utf8]{inputenc} \usepackage{listings} \usepackage{subcaption} \renewcommand{\verb}{\lstinline} \input{conclusion} \clearpage \bibliography{biblio} \bibliographystyle{splncs03}
• ## src/ASM/CPP2012-policy/problem.tex

 r3354 fixed point algorithm that starts with the shortest possible encoding (all branch instruction encoded as short jumps, which is likely not a correct solution) and then iterates over the program to re-encode those branch solution) and then iterates over the source to re-encode those branch instructions whose target is outside their range. the absolute jump, as with absolute jumps, the encoding of a branch instruction no longer depends only on the distance between the branch instruction and its target: in order for an absolute jump to be possible, they need to be in the same segment (for the MCS-51, this means that the first 5 instruction and its target: an absolute jump is possible when they are in the same segment (for the MCS-51, this means that the first 5 bytes of their addresses have to be equal). It is therefore entirely possible for two branch instructions with the same span to be encoded in different ways long if this is not the case). \begin{figure}[ht] \begin{figure}[t] \begin{subfigure}[b]{.45\linewidth} \begin{alltt} jmp X \vdots L$$\sb{0}$$: \vdots \ldots L$$\sb{0}$$: \ldots % Start of new segment if % jmp X is encoded as short \ldots jmp L$$\sb{0}$$ \end{alltt} \caption{Example of a program where a long jump becomes absolute} \label{f:term_example} \end{subfigure} \hfill \begin{subfigure}[b]{.45\linewidth} \begin{alltt} L$$\sb{0}$$: jmp X X:  \ldots \ldots L$$\sb{1}$$: \ldots % Start of new segment if % jmp X is encoded as short \ldots jmp L$$\sb{1}$$ \ldots jmp L$$\sb{1}$$ \ldots jmp L$$\sb{1}$$ \ldots \end{alltt} \caption{Example of a program where the fixed-point algorithm is not optimal} \label{f:opt_example} \end{subfigure} \end{figure} as short jumps. \begin{figure}[ht] \begin{alltt} L$$\sb{0}$$: jmp X X: \vdots L$$\sb{1}$$: \vdots jmp L$$\sb{1}$$ \vdots jmp L$$\sb{1}$$ \vdots jmp L$$\sb{1}$$ \vdots \end{alltt} \caption{Example of a program where the fixed-point algorithm is not optimal} \label{f:opt_example} \end{figure} Then, if {\tt jmp X} were to be encoded as a short jump, which is clearly possible, all of the branches to $\mathtt{L}_{1}$ would have to be encoded as
• ## src/ASM/CPP2012-policy/proof.tex

 r3353 In this section, we present the correctness proof for the algorithm in more detail.  The main correctness statement is as follows (slightly simplified, here): detail.  The main correctness statement is shown, slightly simplified, in~Figure~\cite{statement}. \begin{figure}[t] \begin{alignat*}{6} \mathtt{sigma}&\omit\rlap{\mathtt{\_policy\_specification} \equiv &&&&& pc + (\mathtt{instruction\_size}\ sigma\ policy\ ppc\ instruction = 2^{16})) \end{alignat*} \caption{Main correctness statement\label{statement}} \end{figure} Informally, this means that when fetching a pseudo-instruction atppc\$, the
Note: See TracChangeset for help on using the changeset viewer.