Ignore:
Timestamp:
Jun 15, 2012, 3:25:21 PM (7 years ago)
Author:
mulligan
Message:

Changes to the English for Jaap, and some tidying up and making consistent with the other CPP submission.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/ASM/CPP2012-policy/algorithm.tex

    r2091 r2096  
    44
    55Given the NP-completeness 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 amount of time.
     6(using, for example, a constraint solver) will potentially take a great amount
     7of time.
    88
    9 The SDCC compiler~\cite{SDCC2011}, which has the MCS-51 among its target
    10 instruction sets, simply encodes every branch instruction as a long jump
     9The SDCC compiler~\cite{SDCC2011}, which has a backend targetting the MCS-51
     10instruction set, simply encodes every branch instruction as a long jump
    1111without 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 less
    13 than optimal solution.
     12jump can reach any destination in memory) and a very fast solution to compute,
     13it results in a less than optimal solution.
    1414
    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.
     15On the other hand, the {\tt gcc} compiler suite~\cite{GCC2012}, while compiling
     16C on the x86 architecture, uses a greatest fix point algorithm. In other words,
     17it starts with all branch instructions encoded as the largest jumps
     18available, and then tries to reduce the size of branch instructions as much as
     19possible.
    1920
    2021Such an algorithm has the advantage that any intermediate result it returns
     
    2223jump is always possible, and the algorithm only reduces those branch
    2324instructions whose destination address is in range for a shorter jump.
    24 The algorithm can thus be stopped after a determined amount of steps without
    25 losing correctness.
     25The algorithm can thus be stopped after a determined number of steps without
     26sacrificing correctness.
    2627
    27 The result, however, is not necessarily optimal, even if the algorithm is run
    28 until it terminates naturally: the fixed point reached is the {\em greatest}
     28The result, however, is not necessarily optimal. Even if the algorithm is run
     29until it terminates naturally, the fixed point reached is the {\em greatest}
    2930fixed point, not the least fixed point. Furthermore, {\tt gcc} (at least for
    3031the 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
     32more efficient, as shown in the previous section, but also results in a less
    3233optimal solution.
    3334
     
    3940encoding can only switch from short to long, but never in the other direction.
    4041When 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.
     42instruction to switch from absolute to long and back, as previously explained.
    4343
    4444Proving termination then becomes difficult, because there is nothing that
    45 precludes a branch instruction from switching back and forth between absolute
    46 and long indefinitely.
     45precludes a branch instruction from oscillating back and forth between absolute
     46and long jumps indefinitely.
    4747
    4848In order to keep the algorithm in the same complexity class and more easily
     
    5454from absolute to long.
    5555
    56 There is one complicating factor: suppose that a branch instruction is encoded
     56There is one complicating factor. Suppose that a branch instruction is encoded
    5757in step $n$ as an absolute jump, but in step $n+1$ it is determined that
    5858(because of changes elsewhere) it can now be encoded as a short jump. Due to
     
    6161$n+1$ as well.
    6262
    63 This is not necessarily correct, however: a branch instruction that can be
    64 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.
     63This is not necessarily correct. A branch instruction that can be
     64encoded as a short jump cannot always also be encoded as an absolute jump, as a
     65short jump can bridge segments, whereas an absolute jump cannot. Therefore,
     66in this situation we have decided to encode the branch instruction as a long
     67jump, which is always correct.
    6868
    6969The resulting algorithm, while not optimal, is at least as good as the ones
     
    7575
    7676The branch displacement algorithm forms part of the translation from
    77 pseudo-code to assembler. More specifically, it is used by the function that
     77pseudocode to assembler. More specifically, it is used by the function that
    7878translates pseudo-addresses (natural numbers indicating the position of the
    7979instruction in the program) to actual addresses in memory.
    8080
    81 The original intention was to have two different functions, one function
     81Our original intention was to have two different functions, one function
    8282$\mathtt{policy}: \mathbb{N} \rightarrow \{\mathtt{short\_jump},
    8383\mathtt{absolute\_jump}, \mathtt{long\_jump}\}$ to associate jumps to their
    8484intended encoding, and a function $\sigma: \mathbb{N} \rightarrow
    85 \mathtt{Word}$ to associate pseudo-addresses to actual addresses. $\sigma$
     85\mathtt{Word}$ to associate pseudo-addresses to machine addresses. $\sigma$
    8686would use $\mathtt{policy}$ to determine the size of jump instructions.
    8787
     
    9191From the algorithmic point of view, in order to create the $\mathtt{policy}$
    9292function, we must necessarily have a translation from pseudo-addresses
    93 to actual addresses (i.e. a $\sigma$ function): in order to judge the distance
     93to machine addresses (i.e. a $\sigma$ function): in order to judge the distance
    9494between a jump and its destination, we must know their memory locations.
    9595Conversely, in order to create the $\sigma$ function, we need to have the
     
    104104algorithms. We now have a function
    105105$\sigma: \mathbb{N} \rightarrow \mathtt{Word} \times \mathtt{bool}$ which
    106 associates a pseudo-address to an actual address. The boolean denotes a forced
     106associates a pseudo-address to a machine address. The boolean denotes a forced
    107107long jump; as noted in the previous section, if during the fixed point
    108108computation an absolute jump changes to be potentially re-encoded as a short
     
    143143\end{figure}
    144144
    145 The algorithm, shown in figure~\ref{f:jump_expansion_step}, works by folding the
     145The algorithm, shown in Figure~\ref{f:jump_expansion_step}, works by folding the
    146146function {\sc f} over the entire program, thus gradually constructing $sigma$.
    147147This constitutes one step in the fixed point calculation; successive steps
     
    162162
    163163The first two are parameters that remain the same through one iteration, the
    164 last three are standard parameters for a fold function (including $ppc$,
     164final three are standard parameters for a fold function (including $ppc$,
    165165which is simply the number of instructions of the program already processed).
    166166
     
    169169$\sigma: \mathbb{N} \rightarrow \mathbb{N} \times \{\mathtt{short\_jump},
    170170\mathtt{absolute\_jump},\mathtt{long\_jump}\}$; a function that associates a
    171 pseudo-address with an memory address and a jump length. We do this to be able
    172 to more easily compare the jump lengths between iterations. In the algorithm,
     171pseudo-address with a memory address and a jump length. We do this to be able
     172to more ease the comparison of jump lengths between iterations. In the algorithm,
    173173we use the notation $sigma_1(x)$ to denote the memory address corresponding to
    174174$x$, and $sigma_2(x)$ to denote the jump length corresponding to $x$.
     
    182182
    183183We 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 program
     184already increased the size of some branch instructions before, making the program
    185185longer and moving every instruction forward. We must compensate for this by
    186186adding the size increase of the program to the label's memory address according
     
    189189Note also that we add the pc to $sigma$ at location $ppc+1$, whereas we add the
    190190jump length at location $ppc$. We do this so that $sigma(ppc)$ will always
    191 return a couple with the start address of the instruction at $ppc$ and the
     191return a pair with the start address of the instruction at $ppc$ and the
    192192length of its branch instruction (if any); the end address of the program can
    193193be found at $sigma(n+1)$, where $n$ is the number of instructions in the
Note: See TracChangeset for help on using the changeset viewer.