Ignore:
Timestamp:
Jun 15, 2012, 11:36:47 AM (8 years ago)
Author:
boender
Message:
  • rewrote introduction
  • changed 'medium' to 'absolute'
  • added a bit to conclusion (CompCert?, Piton, ...)
File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/ASM/CPP2012-policy/problem.tex

    r2064 r2085  
    22
    33The problem of branch displacement optimisation, also known as jump encoding, is
    4 a well-known problem in assembler design.
    5 
    6 In many instruction sets, amongst which the ubiquitous x86 architecture (both
    7 its 32-- and 64--bit incarnations), there are instructions whose addressing
    8 mode varies with the distance between the instruction and the object they
    9 address. Mostly this occurs with jump instructions; for example, in the
    10 x86-64 instruction set there are eleven different forms of the unconditional
    11 jump instruction, all with different ranges, instruction sizes and semantics
    12 (only six are valid in 64-bit mode, for example). Some examples are shown in
    13 figure~\ref{f:x86jumps}:
    14 
    15 \begin{figure}[h]
     4a well-known problem in assembler design. It is caused by the fact that in
     5many architecture sets, the encoding (and therefore size) of some instructions
     6depends on the distance to their operand (the instruction 'span'). The branch
     7displacement optimisation problem consists in encoding these span-dependent
     8instructions in such a way that the resulting program is as small as possible.
     9
     10This problem is the subject of the present paper. After introducing the problem
     11in more detail, we will discuss the solutions used by other compilers, present
     12the algorithm used by us in the CerCo assembler, and discuss its verification,
     13that is the proofs of termination and correctness.
     14 
     15The research presented in this paper has been executed within the CerCo project
     16which aims at formally verifying a C compiler with cost annotations. The
     17target architecture for this project is the MCS-51, whose instruction set
     18contains span-dependent instructions. Furthermore, its maximum addressable
     19memory size is very small (65 Kbytes), which makes it important to generate
     20programs that are as small as possible.
     21
     22With this optimisation, however, comes increased complexity and hence
     23increased possibility for error. We must make sure that the jumps are encoded
     24correctly, otherwise the assembled program will behave impredictably.
     25
     26\section{The branch displacement optimisation problem}
     27
     28In most modern instruction sets, the only span-dependent instructions are
     29branch instructions. Taking the ubiquitous x86-64 instruction set as an
     30example, we find that it contains are eleven different forms of the
     31unconditional jump instruction, all with different ranges, instruction sizes
     32and semantics (only six are valid in 64-bit mode, for example). Some examples
     33are shown in figure~\ref{f:x86jumps}.
     34
     35\begin{figure}[h]
     36\begin{center}
    1637\begin{tabular}{|l|l|l|}
    1738\hline
     
    2445\hline
    2546\end{tabular}
     47\end{center}
    2648\caption{List of x86 jump instructions}
    2749\label{f:x86jumps}
     
    2951
    3052The chosen target architecture of the CerCo project is the Intel MCS-51, which
    31 features three types of jump instructions, as shown in
    32 figure~\ref{f:mcs51jumps}.
    33 
    34 \begin{figure}[h]
     53features three types of branch instructions (or jump instructions; the two terms
     54are used interchangeably), as shown in figure~\ref{f:mcs51jumps}.
     55
     56\begin{figure}[h]
     57\begin{center}
    3558\begin{tabular}{|l|l|l|l|}
    3659\hline
     
    3962\hline
    4063SJMP (`short jump') & 2 & 2 & -128 to 127 bytes \\
    41 AJMP (`medium jump') & 2 & 2 & one segment (11-bit address) \\
     64AJMP (`absolute jump') & 2 & 2 & one segment (11-bit address) \\
    4265LJMP (`long jump') & 3 & 3 & entire memory \\
    4366\hline
    4467\end{tabular}
     68\end{center}
    4569\caption{List of MCS-51 jump instructions}
    4670\label{f:mcs51jumps}
     
    5074means that a conditional jump outside the short address range has to be
    5175encoded using two jumps; the call instruction is only available in
    52 medium and long forms.
     76absolute and long forms.
    5377
    5478Note that even though the MCS-51 architecture is much less advanced and more
     
    5781reach the entire available memory.
    5882 
    59 Generally, in assembly code, there is only one way to indicate a jump; the
    60 algorithm used by the assembler to encode these jumps into the different
     83Generally, in the code that is sent to the assembler as input, the only
     84difference made between jump instructions is by semantics, not by span. This
     85means that a distinction is made between the inconditional jump and the several
     86kinds of conditional jump, but not between their short, absolute or long
     87variants.
     88
     89The algorithm used by the assembler to encode these jumps into the different
    6190machine instructions is known as the {\tt branch displacement algorithm}. The
    6291optimisation problem consists in using as small an encoding as possible, thus
     
    6695which could make finding an optimal solution very time-consuming.
    6796
    68 The canonical solution, as shown in~\cite{Szymanski1978} or more recently
    69 in~\cite{Dickson2008} for the x86 instruction set, is to use a fixed point
    70 algorithm that starts out with the shortest possible encoding (all jumps
    71 encoded as short jumps, which is very probably not a correct solution) and then
    72 iterates over the program to re-encode those jumps whose target is outside
    73 their range.
    74 
    75 \subsection*{Adding medium jumps}
     97The canonical solution, as shown by Szymanski~\cite{Szymanski1978} or more
     98recently by Dickson~\cite{Dickson2008} for the x86 instruction set, is to use a
     99fixed point algorithm that starts out with the shortest possible encoding (all
     100jumps encoded as short jumps, which is very probably not a correct solution)
     101and then iterates over the program to re-encode those jumps whose target is
     102outside their range.
     103
     104\subsection*{Adding absolute jumps}
    76105
    77106In both papers mentioned above, the encoding of a jump is only dependent on the
     
    81110Here, termination of the smallest fixed point algorithm is easy to prove. All
    82111jumps start out encoded as short jumps, which means that the distance between
    83 any jump and its target is as short as possible. If we therefore need to encode
    84 a jump $j$ as a long jump, we can be sure that we can never reach a situation
    85 where the span of $j$ is so small that it can be encoded as a short jump. This
    86 reasoning holds throughout the subsequent iterations of the algorithms: short
    87 jumps can change into long jumps, but not vice versa. Hence, the algorithm
    88 either terminates when a fixed point is reached or when all short jumps have
    89 been changed into long jumps.
     112any jump and its target is as short as possible. If, in this situation, there
     113is a jump $j$ whose span is not within the range for a short jump, we can be
     114sure that we can never reach a situation where the span of $j$ is so small that
     115it can be encoded as a short jump. This reasoning holds throughout the
     116subsequent iterations of the algorithm: short jumps can change into long jumps,
     117but not vice versa (spans only increase). Hence, the algorithm either
     118terminates when a fixed point is reached or when all short jumps have been
     119changed into long jumps.
    90120
    91121Also, we can be certain that we have reached an optimal solution: a short jump
     
    93123
    94124However, neither of these claims (termination nor optimality) hold when we add
    95 the medium jump.
    96 
    97 The reason for this is that with medium jumps, the encoding of a jump no longer
    98 depends only on the distance between the jump and its target: in order for a
    99 medium jump to be possible, they need to be in the same segment. It is therefore
    100 entirely possible for two jumps with the same span to be encoded in different
    101 ways (medium if the jump and its destination are in the same segment, long if
    102 this is not the case).
     125the absolute jump.
     126
     127The reason for this is that with absolute jumps, the encoding of a jump no
     128longer depends only on the distance between the jump and its target: in order
     129for an absolute jump to be possible, they need to be in the same segment (for
     130the MCS-51, this means that the first 5 bytes of their addesses have to be
     131equal). It is therefore entirely possible for two jumps with the same span to
     132be encoded in different ways (absolute if the jump and its target are in the
     133same segment, long if this is not the case).
    103134
    104135This invalidates the termination argument: a jump, once encoded as a long jump,
    105 can be re-encoded during a later iteration as a medium jump. Consider the
     136can be re-encoded during a later iteration as an absolute jump. Consider the
    106137program shown in figure~\ref{f:term_example}. At the start of the first
    107138iteration, both the jump to {\tt X} and the jump to $\mathtt{L}_{0}$ are
     
    115146be encoded as a long jump. If we assume that the jump to {\tt X} is encoded as
    116147a long jump as well, the size of the jump will increase and $\mathtt{L}_{0}$
    117 will be `propelled' into the same segment as its jump. Hence, in the next
    118 iteration, it can be encoded as a medium jump. At first glance, there is
     148will be `propelled' into the same segment as its jump. Hence, in the third
     149iteration, it can be encoded as an absolute jump. At first glance, there is
    119150nothing that prevents us from making a construction where two jumps interact
    120 in such a way as to keep switching between long and medium indefinitely.
     151in such a way as to keep switching between long and absolute encodings for
     152an indefinite amount of iterations.
    121153
    122154\begin{figure}[h]
     
    128160    jmp L\(\sb{0}\)
    129161\end{alltt}
    130 \caption{Example of a program where a long jump becomes medium}
     162\caption{Example of a program where a long jump becomes absolute}
    131163\label{f:term_example}
    132164\end{figure}
     165
     166In fact, this situation mirrors the explanation by
     167Szymanski~\cite{Szymanski1978} of why the branch displacement optimisation
     168problem is NP-complete. In this explanation, a condition for NP-completeness
     169is the fact that programs be allowed to contain {\em pathological} jumps.
     170These are jumps that can normally not be encoded as a short(er) jump, but gain
     171this property when some other jumps are encoded as a long(er) jump. This is
     172exactly what happens in figure~\ref{f:term_example}: by encoding the first
     173jump as a long jump, another jump switches from long to absolute
     174(which is shorter).
    133175
    134176The optimality argument no longer holds either. Let us consider the program
     
    145187therefore increase in size, $\mathtt{L}_{1}$ would be `propelled' across the
    146188segment border, so that the three jumps to $\mathtt{L}_{1}$ could be encoded
    147 as medium jumps. Depending on the relative sizes of long and medium jumps, this
    148 solution might actually be smaller than the one reached by the smallest
     189as absolute jumps. Depending on the relative sizes of long and absolute jumps,
     190this solution might actually be smaller than the one reached by the smallest
    149191fixed point algorithm.
    150192
Note: See TracChangeset for help on using the changeset viewer.