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

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/ASM/CPP2012policy/algorithm.tex
r3361 r3362 6 6 (using, for example, a constraint solver) can potentially be very costly. 7 7 8 The SDCC compiler~\cite{SDCC2011}, which has a backend target ting the MCS518 The SDCC compiler~\cite{SDCC2011}, which has a backend targeting the MCS51 9 9 instruction set, simply encodes every branch instruction as a long jump 10 10 without taking the distance into account. While certainly correct (the long 11 11 jump can reach any destination in memory) and a very fast solution to compute, 12 it results in a less than optimal solution. 12 it results in a less than optimal solution in terms of output size and 13 execution time. 13 14 14 15 On the other hand, the {\tt gcc} compiler suite~\cite{GCC2012}, while compiling … … 66 67 jump, which is always correct. 67 68 68 The resulting algorithm, while not optimal, is at least as good as the ones 69 from SDCC and {\tt gcc}, and potentially better. Its complexity remains 70 the same (there are at most $2n$ iterations, where $n$ is the number of branch 71 instructions in the program). 69 The resulting algorithm, therefore, will not return the least fixed point, as 70 it might have too many long jumps. However, it is still better than the 71 algorithms from SDCC and {\tt gcc}, since even in the worst case, it will still 72 return a smaller or equal solution. 73 74 As for complexity, there are at most $2n$ iterations, with $n$ the number of 75 branch instructions. Practical tests within the CerCo project on small to 76 medium pieces of code have shown that in almost all cases, a fixed point is 77 reached in 3 passes. Only in one case did the algorithm need 4. 78 79 This is not surprising: after all, the difference between short/absolute and 80 long jumps is only one byte (three for conditional jumps). For a change from 81 short/absolute to long to have an effect on other jumps is therefore relatively 82 uncommon, which explains why a fixed point is reached so quickly. 72 83 73 84 \subsection{The algorithm in detail}
Note: See TracChangeset
for help on using the changeset viewer.