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


  • src/ASM/CPP2012-policy/algorithm.tex

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