Changeset 2064 for src/ASM/CPP2012policy/problem.tex
 Timestamp:
 Jun 13, 2012, 5:29:11 PM (7 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/ASM/CPP2012policy/problem.tex
r2054 r2064 67 67 68 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 fix point69 in~\cite{Dickson2008} for the x86 instruction set, is to use a fixed point 70 70 algorithm that starts out with the shortest possible encoding (all jumps 71 71 encoded as short jumps, which is very probably not a correct solution) and then … … 79 79 can be used; above this value the jump must be encoded as a long jump. 80 80 81 Here, termination of the smallest fix point algorithm is easy to prove. All81 Here, termination of the smallest fixed point algorithm is easy to prove. All 82 82 jumps start out encoded as short jumps, which means that the distance between 83 83 any jump and its target is as short as possible. If we therefore need to encode … … 86 86 reasoning holds throughout the subsequent iterations of the algorithms: short 87 87 jumps can change into long jumps, but not vice versa. Hence, the algorithm 88 either terminates when a fix point is reached or when all short jumps have been89 changed into long jumps.88 either terminates when a fixed point is reached or when all short jumps have 89 been changed into long jumps. 90 90 91 91 Also, we can be certain that we have reached an optimal solution: a short jump … … 147 147 as medium jumps. Depending on the relative sizes of long and medium jumps, this 148 148 solution might actually be smaller than the one reached by the smallest 149 fix point algorithm.149 fixed point algorithm. 150 150 151 151 \begin{figure}[h]
Note: See TracChangeset
for help on using the changeset viewer.