Changeset 2096 for src/ASM/CPP2012policy/algorithm.tex
 Timestamp:
 Jun 15, 2012, 3:25:21 PM (8 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/ASM/CPP2012policy/algorithm.tex
r2091 r2096 4 4 5 5 Given the NPcompleteness of the problem, to arrive at an optimal solution 6 within a short space of time (using, for example, a constraint solver) will 7 potentially take a great amountof time.6 (using, for example, a constraint solver) will potentially take a great amount 7 of time. 8 8 9 The SDCC compiler~\cite{SDCC2011}, which has the MCS51 among its target10 instruction set s, simply encodes every branch instruction as a long jump9 The SDCC compiler~\cite{SDCC2011}, which has a backend targetting the MCS51 10 instruction set, simply encodes every branch instruction as a long jump 11 11 without taking the distance into account. While certainly correct (the long 12 jump can reach any destination in memory) and rapid, it does result in a less13 than optimal solution.12 jump can reach any destination in memory) and a very fast solution to compute, 13 it results in a less than optimal solution. 14 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 branch instructions encoded as the largest jumps available, and 18 then tries to reduce branch instructions as much as possible. 15 On the other hand, the {\tt gcc} compiler suite~\cite{GCC2012}, while compiling 16 C on the x86 architecture, uses a greatest fix point algorithm. In other words, 17 it starts with all branch instructions encoded as the largest jumps 18 available, and then tries to reduce the size of branch instructions as much as 19 possible. 19 20 20 21 Such an algorithm has the advantage that any intermediate result it returns … … 22 23 jump is always possible, and the algorithm only reduces those branch 23 24 instructions whose destination address is in range for a shorter jump. 24 The algorithm can thus be stopped after a determined amountof steps without25 losing correctness.25 The algorithm can thus be stopped after a determined number of steps without 26 sacrificing correctness. 26 27 27 The result, however, is not necessarily optimal , even if the algorithm is run28 until it terminates naturally :the fixed point reached is the {\em greatest}28 The result, however, is not necessarily optimal. Even if the algorithm is run 29 until it terminates naturally, the fixed point reached is the {\em greatest} 29 30 fixed point, not the least fixed point. Furthermore, {\tt gcc} (at least for 30 31 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 less32 more efficient, as shown in the previous section, but also results in a less 32 33 optimal solution. 33 34 … … 39 40 encoding can only switch from short to long, but never in the other direction. 40 41 When we add absolute jumps, however, it is theoretically possible for a branch 41 instruction to switch from absolute to long and back, as shown in the previous 42 section. 42 instruction to switch from absolute to long and back, as previously explained. 43 43 44 44 Proving termination then becomes difficult, because there is nothing that 45 precludes a branch instruction from switching back and forth between absolute46 and long indefinitely.45 precludes a branch instruction from oscillating back and forth between absolute 46 and long jumps indefinitely. 47 47 48 48 In order to keep the algorithm in the same complexity class and more easily … … 54 54 from absolute to long. 55 55 56 There is one complicating factor : suppose that a branch instruction is encoded56 There is one complicating factor. Suppose that a branch instruction is encoded 57 57 in step $n$ as an absolute jump, but in step $n+1$ it is determined that 58 58 (because of changes elsewhere) it can now be encoded as a short jump. Due to … … 61 61 $n+1$ as well. 62 62 63 This is not necessarily correct , however: abranch instruction that can be64 encoded as a short jump cannot always also be encoded as an absolute jump 65 (a short jump can bridge segments, whereas an absolute jump cannot). Therefore,66 in this situation we decide to encode the branch instruction as a long jump,67 which is always correct.63 This is not necessarily correct. A branch instruction that can be 64 encoded as a short jump cannot always also be encoded as an absolute jump, as a 65 short jump can bridge segments, whereas an absolute jump cannot. Therefore, 66 in this situation we have decided to encode the branch instruction as a long 67 jump, which is always correct. 68 68 69 69 The resulting algorithm, while not optimal, is at least as good as the ones … … 75 75 76 76 The branch displacement algorithm forms part of the translation from 77 pseudo code to assembler. More specifically, it is used by the function that77 pseudocode to assembler. More specifically, it is used by the function that 78 78 translates pseudoaddresses (natural numbers indicating the position of the 79 79 instruction in the program) to actual addresses in memory. 80 80 81 Theoriginal intention was to have two different functions, one function81 Our original intention was to have two different functions, one function 82 82 $\mathtt{policy}: \mathbb{N} \rightarrow \{\mathtt{short\_jump}, 83 83 \mathtt{absolute\_jump}, \mathtt{long\_jump}\}$ to associate jumps to their 84 84 intended encoding, and a function $\sigma: \mathbb{N} \rightarrow 85 \mathtt{Word}$ to associate pseudoaddresses to actualaddresses. $\sigma$85 \mathtt{Word}$ to associate pseudoaddresses to machine addresses. $\sigma$ 86 86 would use $\mathtt{policy}$ to determine the size of jump instructions. 87 87 … … 91 91 From the algorithmic point of view, in order to create the $\mathtt{policy}$ 92 92 function, we must necessarily have a translation from pseudoaddresses 93 to actualaddresses (i.e. a $\sigma$ function): in order to judge the distance93 to machine addresses (i.e. a $\sigma$ function): in order to judge the distance 94 94 between a jump and its destination, we must know their memory locations. 95 95 Conversely, in order to create the $\sigma$ function, we need to have the … … 104 104 algorithms. We now have a function 105 105 $\sigma: \mathbb{N} \rightarrow \mathtt{Word} \times \mathtt{bool}$ which 106 associates a pseudoaddress to a n actualaddress. The boolean denotes a forced106 associates a pseudoaddress to a machine address. The boolean denotes a forced 107 107 long jump; as noted in the previous section, if during the fixed point 108 108 computation an absolute jump changes to be potentially reencoded as a short … … 143 143 \end{figure} 144 144 145 The algorithm, shown in figure~\ref{f:jump_expansion_step}, works by folding the145 The algorithm, shown in Figure~\ref{f:jump_expansion_step}, works by folding the 146 146 function {\sc f} over the entire program, thus gradually constructing $sigma$. 147 147 This constitutes one step in the fixed point calculation; successive steps … … 162 162 163 163 The first two are parameters that remain the same through one iteration, the 164 lastthree are standard parameters for a fold function (including $ppc$,164 final three are standard parameters for a fold function (including $ppc$, 165 165 which is simply the number of instructions of the program already processed). 166 166 … … 169 169 $\sigma: \mathbb{N} \rightarrow \mathbb{N} \times \{\mathtt{short\_jump}, 170 170 \mathtt{absolute\_jump},\mathtt{long\_jump}\}$; a function that associates a 171 pseudoaddress with a nmemory address and a jump length. We do this to be able172 to more eas ily compare thejump lengths between iterations. In the algorithm,171 pseudoaddress with a memory address and a jump length. We do this to be able 172 to more ease the comparison of jump lengths between iterations. In the algorithm, 173 173 we use the notation $sigma_1(x)$ to denote the memory address corresponding to 174 174 $x$, and $sigma_2(x)$ to denote the jump length corresponding to $x$. … … 182 182 183 183 We cannot use $old\_sigma$ without change: it might be the case that we have 184 already increased the size some branch instructions before, making the program184 already increased the size of some branch instructions before, making the program 185 185 longer and moving every instruction forward. We must compensate for this by 186 186 adding the size increase of the program to the label's memory address according … … 189 189 Note also that we add the pc to $sigma$ at location $ppc+1$, whereas we add the 190 190 jump length at location $ppc$. We do this so that $sigma(ppc)$ will always 191 return a couplewith the start address of the instruction at $ppc$ and the191 return a pair with the start address of the instruction at $ppc$ and the 192 192 length of its branch instruction (if any); the end address of the program can 193 193 be found at $sigma(n+1)$, where $n$ is the number of instructions in the
Note: See TracChangeset
for help on using the changeset viewer.