# Changeset 3362 for src/ASM/CPP2012-policy/problem.tex

Ignore:
Timestamp:
Jun 17, 2013, 1:08:27 PM (6 years ago)
Message:
• added some bits as per Claudio's mail
• rewrote some small things
• general reread, spell check, grammar check
• 16 pages again now
File:
1 edited

### Legend:

Unmodified
 r3361 The problem of branch displacement optimisation, also known as jump encoding, is a well-known problem in assembler design~\cite{Hyde2006}. It is caused by the a well-known problem in assembler design~\cite{Hyde2006}. Its origin lies in the fact that in many architecture sets, the encoding (and therefore size) of some instructions depends on the distance to their operand (the instruction 'span'). encoded using three branch instructions (for instructions whose logical negation is available, it can be done with two branch instructions, but for some instructions this is not available); the call instruction is some instructions this is not the case). The call instruction is only available in absolute and long forms. Note that even though the MCS-51 architecture is much less advanced and simpler than the x86-64 architecture, the basic types of branch instruction Note that even though the MCS-51 architecture is much less advanced and much simpler than the x86-64 architecture, the basic types of branch instruction remain the same: a short jump with a limited range, an intra-segment jump and a jump that can reach the entire available memory. possible, thus minimising program length and execution time. This problem is known to be NP-complete~\cite{Robertson1979,Szymanski1978}, Similar problems, e.g. the branch displacement optimisation problem for other architectures, are known to be NP-complete~\cite{Robertson1979,Szymanski1978}, which could make finding an optimal solution very time-consuming. However, neither of these claims (termination nor optimality) hold when we add the absolute jump, as with absolute jumps, the encoding of a branch the absolute jump. With absolute jumps, the encoding of a branch instruction no longer depends only on the distance between the branch 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 instruction and its target. An absolute jump is possible when instruction and target 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 shorter). In addition, our previous optimality argument no longer holds. Consider the program shown in Figure~\ref{f:opt_example}. Suppose that the distance between In addition, our previous optimality argument no longer holds. Consider the program shown in Figure~\ref{f:opt_example}. Suppose that the distance between $\mathtt{L}_{0}$ and $\mathtt{L}_{1}$ is such that if {\tt jmp X} is encoded as a short jump, there is a segment border just after $\mathtt{L}_{1}$. Let us also assume that the three branches to $\mathtt{L}_{1}$ are all in the same us also assume that all three branches to $\mathtt{L}_{1}$ are in the same segment, but far enough away from $\mathtt{L}_{1}$ that they cannot be encoded as short jumps.