Changeset 3362 for src/ASM/CPP2012policy/problem.tex
 Timestamp:
 Jun 17, 2013, 1:08:27 PM (6 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/ASM/CPP2012policy/problem.tex
r3361 r3362 2 2 3 3 The problem of branch displacement optimisation, also known as jump encoding, is 4 a wellknown problem in assembler design~\cite{Hyde2006}. It is caused bythe4 a wellknown problem in assembler design~\cite{Hyde2006}. Its origin lies in the 5 5 fact that in many architecture sets, the encoding (and therefore size) of some 6 6 instructions depends on the distance to their operand (the instruction 'span'). … … 78 78 encoded using three branch instructions (for instructions whose logical 79 79 negation is available, it can be done with two branch instructions, but for 80 some instructions this is not available); the call instruction is80 some instructions this is not the case). The call instruction is 81 81 only available in absolute and long forms. 82 82 83 Note that even though the MCS51 architecture is much less advanced and simpler84 than the x8664 architecture, the basic types of branch instruction83 Note that even though the MCS51 architecture is much less advanced and much 84 simpler than the x8664 architecture, the basic types of branch instruction 85 85 remain the same: a short jump with a limited range, an intrasegment jump and a 86 86 jump that can reach the entire available memory. … … 97 97 possible, thus minimising program length and execution time. 98 98 99 This problem is known to be NPcomplete~\cite{Robertson1979,Szymanski1978}, 99 Similar problems, e.g. the branch displacement optimisation problem for other 100 architectures, are known to be NPcomplete~\cite{Robertson1979,Szymanski1978}, 100 101 which could make finding an optimal solution very timeconsuming. 101 102 … … 128 129 129 130 However, neither of these claims (termination nor optimality) hold when we add 130 the absolute jump , as with absolute jumps, the encoding of a branch131 the absolute jump. With absolute jumps, the encoding of a branch 131 132 instruction no longer depends only on the distance between the branch 132 instruction and its target : an absolute jump is possible when they133 are in the same segment (for the MCS51, this means that the first 5133 instruction and its target. An absolute jump is possible when instruction and 134 target are in the same segment (for the MCS51, this means that the first 5 134 135 bytes of their addresses have to be equal). It is therefore entirely possible 135 136 for two branch instructions with the same span to be encoded in different ways … … 203 204 shorter). 204 205 205 In addition, our previous optimality argument no longer holds. Consider the program206 shown in Figure~\ref{f:opt_example}. Suppose that the distance between206 In addition, our previous optimality argument no longer holds. Consider the 207 program shown in Figure~\ref{f:opt_example}. Suppose that the distance between 207 208 $\mathtt{L}_{0}$ and $\mathtt{L}_{1}$ is such that if {\tt jmp X} is encoded 208 209 as 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 allin the same210 us also assume that all three branches to $\mathtt{L}_{1}$ are in the same 210 211 segment, but far enough away from $\mathtt{L}_{1}$ that they cannot be encoded 211 212 as short jumps.
Note: See TracChangeset
for help on using the changeset viewer.