# Changeset 1001

Ignore:
Timestamp:
Jun 20, 2011, 5:26:31 PM (10 years ago)
Message:

reworded intro

File:
1 edited

### Legend:

Unmodified
 r1000 \begin{displaymath} \begin{array}{r@{\qquad}r@{\quad}l@{\;\;}l@{\qquad}l} \text{1:} & \mathtt{0x000}  & \texttt{LJMP} & \texttt{0x100}  & \text{\texttt{;; Jump forward 256.}} \\ \text{1:} & \mathtt{(0x000)}  & \texttt{LJMP} & \texttt{0x100}  & \text{\texttt{;; Jump forward 256.}} \\ \text{2:} & \mathtt{...}    & \mathtt{...}  &                 &                                               \\ \text{3:} & \mathtt{0x0FA}  & \texttt{LJMP} & \texttt{0x100}  & \text{\texttt{;; Jump forward 256.}} \\ \text{3:} & \mathtt{(0x0FA)}  & \texttt{LJMP} & \texttt{0x100}  & \text{\texttt{;; Jump forward 256.}} \\ \text{4:} & \mathtt{...}    & \mathtt{...}  &                 &                                               \\ \text{5:} & \mathtt{0x100}  & \texttt{LJMP} & \texttt{0x100}  & \text{\texttt{;; Jump forward 256.}} \\ \text{6:} & \mathtt{...}    & \mathtt{...}  &                 &                                               \\ \text{7:} & \mathtt{0x1F9}  & \texttt{LJMP} & \texttt{-0x300} & \text{\texttt{;; Arbitrary instruction.}} \\ \text{5:} & \mathtt{(0x100)}  & \texttt{LJMP} & \texttt{0x-100}  & \text{\texttt{;; Jump backward 256.}} \\ \end{array} \end{displaymath} As our example shows, given an occurence $l$ of an \texttt{LJMP} instruction, it may be possible to shrink $l$ to an occurence of an \texttt{SJMP}---consuming fewer bytes of code memory---provided we can shrink any \texttt{LJMP}s that exist between $l$ and its target location. In particular, if we can somehow shrink the \texttt{LJMP} occurring at line 5, the \texttt{LJMP}s occurring at lines 1 and 3 above may both be replaced by \texttt{SJMP}s, provided that \emph{both} jumps at 1 and 3 are replaced at the same time. In particular, if we wish to shrink the \texttt{LJMP} occurring at line 1, then we must shrink the \texttt{LJMP} occurring at line 3. However, to shrink the \texttt{LJMP} occurring at line 3 we must also shrink the \texttt{LJMP} occurring at line 5, and \emph{vice versa}. Further, consider what happens if, instead of appearing at memory address \texttt{0x100}, the instruction at line 5 instead appeared \emph{just} beyond the size of code memory, and all other memory addresses were shifted accordingly. Now, in order to be able to successfully load our program into the MCS-51's code memory, we are \emph{obliged} to shrink the \texttt{LJMP} occurring at line 5. That is, the shrinking process is not just related to optimisation, but also the completeness of the assembler. Thinking more, it is easy to imagine knotty, circular configurations of jumps developing, each jump occurrence only being shrinkable if every other is. Finding a solution to this shrinking jumps' problem then involves us finding a method to break any vicious circularities that develop. | long_jump: jump_length. \end{lstlisting} A \texttt{jump\_expansion\_policy} is a map from \texttt{Word}s to \texttt{jump\_length}s, implemented as a trie. A \texttt{jump\_expansion\_policy} is a map from pseudo program counters (implemented as \texttt{Word}s) to \texttt{jump\_length}s, implemented as a trie. Intuitively, a policy maps positions in a program (indexed using program counters implemented as \texttt{Word}s) to a particular variety of jump. \begin{lstlisting} Next, we require a series of sigma' functions. These functions map assembly program counters to their machine code counterparts, establishing the correspondence between positions' in an assembly program and positions' in a machine code program. At the heart of this process is \texttt{sigma0} which traverses an assembly program building maps from program counter to program counter. At the heart of this process is \texttt{sigma0} which traverses an assembly program building maps from pseudo program counters to program counters. This function fails if and only if an internal call to \texttt{assembly\_1\_pseudoinstruction} fails: \begin{lstlisting}