Changeset 2064 for src/ASM/CPP2012policy/algorithm.tex
 Timestamp:
 Jun 13, 2012, 5:29:11 PM (8 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/ASM/CPP2012policy/algorithm.tex
r2054 r2064 124 124 \begin{figure} 125 125 \begin{algorithmic} 126 \Function{jump\_expansion\_step}{x} 126 \Function{f}{$labels$,$old\_sigma$,$instr$,$ppc$,$acc$} 127 \State $\langle added, pc, sigma \rangle \gets acc$ 128 \If {$instr$ is a backward jump to $j$} 129 \State $length \gets \mathrm{jump\_size}(pc,sigma_1(labels(j)))$ 130 \ElsIf {$instr$ is a forward jump to $j$} 131 \State $length \gets \mathrm{jump\_size}(pc,old\_sigma_1(labels(j))+added)$ 132 \Else 133 \State $length \gets \mathtt{short\_jump}$ 134 \EndIf 135 \State $old\_length \gets \mathrm{old\_sigma_1}(ppc)$ 136 \State $new\_length \gets \mathrm{max}(old\_length, length)$ 137 \State $old\_size \gets \mathrm{old\_sigma_2}(ppc)$ 138 \State $new\_size \gets \mathrm{instruction\_size}(instr,new\_length)$ 139 \State $new\_added \gets added+(new\_sizeold\_size)$ 140 \State $new\_sigma_1(ppc+1) \gets pc+new\_size$ 141 \State $new\_sigma_2(ppc) \gets new\_length$ \\ 142 \Return $\langle new\_added, pc+new\_size, new\_sigma \rangle$ 127 143 \EndFunction 128 144 \end{algorithmic} … … 130 146 \label{f:jump_expansion_step} 131 147 \end{figure} 148 149 The algorithm, shown in figure~\ref{f:jump_expansion_step}, works by folding the 150 function {\sc f} over the entire program, thus gradually constructing $sigma$. 151 This constitutes one step in the fixed point calculation; successive steps 152 repeat the fold until a fixed point is reached. 153 154 Parameters of the function {\sc f} are: 155 \begin{itemize} 156 \item a function $labels$ that associates a label to its pseudoaddress; 157 \item $old\_sigma$, the $\sigma$ function returned by the previous 158 iteration of the fixed point calculcation; 159 \item $instr$, the instruction currently under consideration; 160 \item $ppc$, the pseudoaddress of $instr$; 161 \item $acc$, the fold accumulator, which contains $pc$ (the highest memory 162 address reached so far), $added$ (the number of bytes added to the program 163 size with respect to the previous iteration), and of course $sigma$, the 164 $\sigma$ function under construction. 165 \end{itemize} 166 167 The first two are parameters that remain the same through one iteration, the 168 last three are standard parameters for a fold function (including $ppc$, 169 which is simply the number of instructions of the program already processed). 170 171 The $\sigma$ functions used by {\sc f} are not of the same type as the final 172 $\sigma$ function: they are of type 173 $\sigma: \mathbb{N} \rightarrow \mathbb{N} \times \{\mathtt{short\_jump}, 174 \mathtt{medium\_jump},\mathtt{long\_jump}\}$; a function that associates a 175 pseudoaddress with an memory address and a jump length. We do this to be able 176 to more easily compare the jump lengths between iterations. In the algorithm, 177 we use the notation $sigma_1(x)$ to denote the memory address corresponding to 178 $x$, and $sigma_2(x)$ to denote the jump length corresponding to $x$. 179 180 Note that the $\sigma$ function used for label lookup varies depending on 181 whether the label is behind our current position or ahead of it. For 182 backward jumps, where the label is behind our current position, we can use 183 $sigma$ for lookup, since its memory address is already known. However, for 184 forward jumps, the memory address of the address of the label is not yet 185 known, so we must use $old\_sigma$. 186 187 We cannot use $old\_sigma$ without change: it might be the case that we have 188 already changed some jumps before, making the program longer. We must therefore 189 compensate for this by adding the size increase of the program to the label's 190 memory address according to $old\_sigma$, so that jump distances do not get 191 compromised. 192 193 Note also that we add the pc to $sigma$ at location $ppc+1$, whereas we add the 194 jump length at location $ppc$. We do this so that $sigma(ppc)$ will always 195 return a couple with the start address of the instruction at $ppc$ and the 196 length of its jump; the end address of the program can be found at $sigma(n+1)$, 197 where $n$ is the number of instructions in the program.
Note: See TracChangeset
for help on using the changeset viewer.