Changeset 2080 for src/ASM/CPP2012policy/algorithm.tex
 Timestamp:
 Jun 14, 2012, 11:57:51 AM (8 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/ASM/CPP2012policy/algorithm.tex
r2064 r2080 7 7 potentially take a great amount of time. 8 8 9 The {\tt gcc} compiler suite, for the x86 architecture, uses a greatest fix 10 point algorithm. In other words, it starts off with all jumps encoded as the 11 largest jumps possible, and then tries to reduce jumps as much as possible. 9 The SDCC compiler~\cite{SDCC2011}, which has the MCS51 among its target 10 instruction sets, simply encodes every jump as a long jump without taking the 11 distance into account. While certainly correct (the long jump can reach any 12 destination in memory) and rapid, it does result in a less than optimal 13 solution. 14 15 The {\tt gcc} compiler suite~\cite{GCC2012}, while compiling C on the x86 16 architecture, uses a greatest fix point algorithm. In other words, it starts 17 off with all jumps encoded as the largest jumps available, and then tries to 18 reduce jumps as much as possible. 12 19 13 20 Such an algorithm has the advantage that any intermediate results it returns … … 20 27 The result, however, is not necessarily optimal, even if the algorithm is run 21 28 until it terminates naturally: the fixed point reached is the {\em greatest} 22 fixed point, not the least fixed point. 29 fixed point, not the least fixed point. Furthermore, {\tt gcc} (at least for 30 the x86 architecture) only uses short and long jumps. This makes the algorithm 31 more rapid, as shown in the previous section, but also results in a less 32 optimal solution. 23 33 24 The SDCC compiler, which has the MCS51 among its target instruction sets, uses 25 a least fix point algorithm, but does not take the presence of medium jumps 26 into account. This makes the algorithm run in linear time with respect to the 27 number of jumps in the program: starting out with every jump encoded as a 28 short jump, each jump can be switched to a long jump once, but no jump ever 29 goes back from long to short. This algorithm must be run until a fixed point 30 is reached, because the intermediate solutions are not necessarily correct. 31 32 This algorithm results in a least fixed point, which means its solution is 33 potentially more optimal then the one reached by the {\tt gcc} algorithm. 34 However, the solution is still not optimal, since there might be jumps whose 35 destination is in the same segment. These jumps could be encoded as medium 36 jumps, which are smaller than long jumps. 37 38 Our first attempt at an algorithm was a least fixed point algorithm that took 39 medium jumps into account. 34 In the CerCo assembler, we opted at first for a least fixed point algorithm, 35 taking medium jumps into account. 40 36 41 37 Here, we ran into a problem with proving termination: whereas the SDCC
Note: See TracChangeset
for help on using the changeset viewer.