source: src/ASM/SEFM2012/problem.tex @ 1889

Last change on this file since 1889 was 1889, checked in by boender, 7 years ago
  • some pages of article
File size: 7.2 KB
Line 
1\section{The problem}
2
3The problem of branch displacement optimisation, also known as jump encoding, is
4a well-known problem in assembler design.
5
6In many instruction sets, amongst which the ubiquitous x86 architecture (both
7its 32-- and 64--bit incarnations), there are instructions whose addressing
8mode varies with the distance between the instruction and the object they
9address. Mostly this occurs with jump instructions; for example, in the
10x86-64 instruction set there are eleven different forms of the unconditional
11jump instruction, all with different ranges and semantics (only six are valid
12in 64-bit mode, for example). Some examples are shown in
13figure~\ref{f:x86jumps}:
14
15\begin{figure}[h]
16\begin{tabular}{|l|l|l|}
17\hline
18Instruction & Size (bytes) & Displacement range \\
19\hline
20Short jump & 2 & -128 to 127 bytes \\
21Relative near jump & 5 & $-2^{32}$ to $2^{32}-1$ bytes \\
22Absolute near jump & 6 & one segment (64-bit address) \\
23Far jump & 8 & entire memory \\
24\hline
25\end{tabular}
26\caption{List of x86 jump instructions}
27\label{f:x86jumps}
28\end{figure}
29
30The chosen target architecture of the CerCo project is the Intel MCS-51, which
31features three types of jump instructions, as shown in
32figure~\ref{f:mcs51jumps}.
33
34\begin{figure}[h]
35\begin{tabular}{|l|l|l|l|}
36\hline
37Instruction & Size    & Execution time & Displacement range \\
38            & (bytes) & (cycles) & \\
39\hline
40SJMP (`short jump') & 2 & 2 & -128 to 127 bytes \\
41AJMP (`medium jump') & 2 & 2 & one segment (11-bit address) \\
42LJMP (`long jump') & 3 & 3 & entire memory \\
43\hline
44\end{tabular}
45\caption{List of MCS-51 jump instructions}
46\label{f:mcs51jumps}
47\end{figure}
48
49The conditional jump instruction is only available in short form, which
50means that a conditional jump outside the short address range has to be
51encoded using two jumps; the call instruction is only available in
52medium and long forms.
53
54Note that even though the MCS-51 architecture is much less advanced and more
55simple than the x86-64 architecture, the basic types of jump remain the same:
56a short jump with a limited range, an intra-segment jump and a jump that can
57reach the entire available memory.
58 
59Generally, in assembly code, there is only one way to indicate a jump; the
60algorithm used by the assembler to encode these jumps into the different
61machine instructions is known as the {\tt branch displacement algorithm}. The
62optimisation problem consists in using as small an encoding as possible, thus
63minimising program length and execution time.
64
65This problem is known to be NP-complete~\cite{Robertson1979,Szymanski1978},
66which could make finding an optimal solution very time-consuming.
67
68The canonical solution, as shown in~\cite{Szymanski1978} or more recently
69in~\cite{Dickson2008} for the x86 instruction set, is to use a fixpoint
70algorithm that starts out with the shortest possible encoding (all jumps
71encoded as short jumps, which is very probably not a correct solution) and then
72iterates over the program to re-encode those jumps whose target is outside
73their range.
74
75\subsection*{Adding medium jumps}
76
77In both the canonical solutions presented, the encoding of a jump is only
78dependent on the distance between the jump and its target: below a certain
79value a short jump can be used; above this value the jump must be encoded
80as a long jump.
81
82Here, termination of the smallest fixpoint algorithm is easy to prove. All
83jumps start out encoded as short jumps, which means that the distance between
84any jump and its target is as short as possible. If we therefore need to encode
85a jump $j$ as a long jump, we can be sure that we can never reach a situation
86where the span of $j$ is so small that it can be encoded as a short jump. This
87reasoning holds throughout the subsequent iterations of the algorithms: short
88jumps can change into long jumps, but not vice versa. Hence, the algorithm
89either terminates when a fixpoint is reached or when all short jumps have been
90changed into long jumps.
91
92Also, we can be certain that we have reached an optimal solution: a short jump
93is only changed into a long jump if it is absolutely necessary.
94
95However, neither of these claims (termination nor optimality) hold when we add
96the medium jump.
97
98The reason for this is that with medium jumps, the encoding of a jump no longer
99depends only on the distance between the jump and its target: in order for a
100medium jump to be possible, they need to be in the same segment. It is therefore
101entirely possible for two jumps with the same span to be encoded in different
102ways (medium if the jump and its destination are in the same segment, long if
103this is not the case).
104
105This invalidates the termination argument: a jump, once encoded as a long jump,
106can be re-encoded during a later iteration as a medium jump. Consider the
107program shown in figure~\ref{f:term_example}. At the start of the first
108iteration, both the jump to {\tt X} and the jump to $\mathtt{L}_{0}$ are
109encoded as small jumps. Let us assume that in this case, the placement of
110$\mathtt{L}_{0}$ and the jump to it are such that $\mathtt{L}_{0}$ is just
111outside the segment that contains this jump. Let us also assume that the
112distance between $\mathtt{L}_{0}$ and the jump to it are too large for the jump
113to be encoded as a short jump.
114
115All this means that in the second iteration, the jump to $\mathtt{L}_{0}$ will
116be encoded as a long jump. If we assume that the jump to {\tt X} is encoded as
117a long jump as well, the size of the jump will increase and $\mathtt{L}_{0}$
118will be `propelled' into the same segment as its jump. Hence, in the next
119iteration, it can be encoded as a medium jump. At first glance, there is
120nothing that prevents us from making a construction where two jumps interact
121in such a way as to keep switching between long and medium indefinitely.
122
123\begin{figure}[h]
124\begin{alltt}
125    jmp X
126    \vdots
127L\(\sb{0}\):
128    \vdots
129    jmp L\(\sb{0}\)
130\end{alltt}
131\caption{Example of a program where a long jump becomes medium}
132\label{f:term_example}
133\end{figure}
134
135The optimality argument no longer holds either. Let us consider the program
136shown in figure~\ref{f:opt_example}. Suppose that the distance between
137$\mathtt{L}_{0}$ and $\mathtt{L}_{1}$ is such that if {\tt jmp X} is encoded
138as a short jump, there is a segment border just after $\mathtt{L}_{1}$. Let
139us also assume that the three jumps to $\mathtt{L}_{1}$ are all in the same
140segment, but far enough away from $\mathtt{L}_{1}$ that they cannot be encoded
141as short jumps.
142
143Then, if {\tt jmp X} were to be encoded as a short jump, which is clearly
144possible, all of the jumps to $\mathtt{L}_{1}$ would have to be encoded as
145long jumps. However, if {\tt jmp X} were to be encoded as a long jump, and
146therefore increase in size, $\mathtt{L}_{1}$ would be `propelled' across the
147segment border, so that the three jumps to $\mathtt{L}_{1}$ could be encoded
148as medium jumps. Depending on the relative sizes of long and medium jumps, this
149solution might actually be smaller than the one reached by the smallest
150fixpoint algorithm.
151
152\begin{figure}[h]
153\begin{alltt}
154L\(\sb{0}\): jmp X
155X:
156    \vdots
157L\(\sb{1}\):
158    \vdots
159    jmp L\(\sb{1}\)
160    \vdots
161    jmp L\(\sb{1}\)
162    \vdots
163    jmp L\(\sb{1}\) 
164    \vdots
165\end{alltt}
166\caption{Example of a program where the fixed-point algorithm is not optimal}
167\label{f:opt_example}
168\end{figure}
Note: See TracBrowser for help on using the repository browser.