Ignore:
Timestamp:
Jun 17, 2013, 1:08:27 PM (6 years ago)
Author:
boender
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
Added
Removed
  • src/ASM/CPP2012-policy/problem.tex

    r3361 r3362  
    22
    33The problem of branch displacement optimisation, also known as jump encoding, is
    4 a well-known problem in assembler design~\cite{Hyde2006}. It is caused by the
     4a well-known problem in assembler design~\cite{Hyde2006}. Its origin lies in the
    55fact that in many architecture sets, the encoding (and therefore size) of some
    66instructions depends on the distance to their operand (the instruction 'span').
     
    7878encoded using three branch instructions (for instructions whose logical
    7979negation is available, it can be done with two branch instructions, but for
    80 some instructions this is not available); the call instruction is
     80some instructions this is not the case). The call instruction is
    8181only available in absolute and long forms.
    8282
    83 Note that even though the MCS-51 architecture is much less advanced and simpler
    84 than the x86-64 architecture, the basic types of branch instruction
     83Note that even though the MCS-51 architecture is much less advanced and much
     84simpler than the x86-64 architecture, the basic types of branch instruction
    8585remain the same: a short jump with a limited range, an intra-segment jump and a
    8686jump that can reach the entire available memory.
     
    9797possible, thus minimising program length and execution time.
    9898
    99 This problem is known to be NP-complete~\cite{Robertson1979,Szymanski1978},
     99Similar problems, e.g. the branch displacement optimisation problem for other
     100architectures, are known to be NP-complete~\cite{Robertson1979,Szymanski1978},
    100101which could make finding an optimal solution very time-consuming.
    101102
     
    128129
    129130However, neither of these claims (termination nor optimality) hold when we add
    130 the absolute jump, as with absolute jumps, the encoding of a branch
     131the absolute jump. With absolute jumps, the encoding of a branch
    131132instruction no longer depends only on the distance between the branch
    132 instruction and its target: an absolute jump is possible when they
    133 are in the same segment (for the MCS-51, this means that the first 5
     133instruction and its target. An absolute jump is possible when instruction and
     134target are in the same segment (for the MCS-51, this means that the first 5
    134135bytes of their addresses have to be equal). It is therefore entirely possible
    135136for two branch instructions with the same span to be encoded in different ways
     
    203204shorter).
    204205
    205 In addition, our previous optimality argument no longer holds. Consider the program
    206 shown in Figure~\ref{f:opt_example}. Suppose that the distance between
     206In addition, our previous optimality argument no longer holds. Consider the
     207program shown in Figure~\ref{f:opt_example}. Suppose that the distance between
    207208$\mathtt{L}_{0}$ and $\mathtt{L}_{1}$ is such that if {\tt jmp X} is encoded
    208209as a short jump, there is a segment border just after $\mathtt{L}_{1}$. Let
    209 us also assume that the three branches to $\mathtt{L}_{1}$ are all in the same
     210us also assume that all three branches to $\mathtt{L}_{1}$ are in the same
    210211segment, but far enough away from $\mathtt{L}_{1}$ that they cannot be encoded
    211212as short jumps.
Note: See TracChangeset for help on using the changeset viewer.