Ignore:
Timestamp:
Jan 14, 2014, 3:09:15 PM (6 years ago)
Author:
boender
Message:
  • changes for proceedings of TACAS 2014
File:
1 edited

Legend:

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

    r3393 r3415  
    7171return a smaller or equal solution.
    7272
    73 Experiments on the gcc 2.3.3 test suite of C programs have shown that on
    74 average, about 25 percent of jumps are encoded as short or absolute jumps by the algorithm. As not all instructions are jumps, this does not make for a large reduction in size, but it can make for a reduction in execution time: if jumps
     73Experimenting with our algorithm on the test suite of C programs included with
     74gcc 2.3.3 has shown that on average, about 25 percent of jumps are encoded as short or absolute jumps by the algorithm. As not all instructions are jumps, this does not make for a large reduction in size, but it can make for a reduction in execution time: if jumps
    7575are executed multiple times, for example in loops, the fact that short jumps take less cycles to execute than long jumps can have great effect.
    7676
    77 As for complexity, there are at most $2n$ iterations, with $n$ the number of
     77As for complexity, there are at most $2n$ iterations, where $n$ is the number of
    7878branch instructions. Practical tests within the CerCo project on small to
    7979medium pieces of code have shown that in almost all cases, a fixed point is
     
    134134        \If {$instr$ is a backward jump to $j$}
    135135                \State $length \gets \mathrm{jump\_size}(pc,sigma_1(labels(j)))$
     136                \Comment compute jump distance
    136137        \ElsIf {$instr$ is a forward jump to $j$}
    137138                \State $length \gets \mathrm{jump\_size}(pc,old\_sigma_1(labels(j))+added)$
     
    139140        \State $old\_length \gets \mathrm{old\_sigma_1}(ppc)$
    140141        \State $new\_length \gets \mathrm{max}(old\_length, length)$
     142        \Comment length must never decrease
    141143        \State $old\_size \gets \mathrm{old\_sigma_2}(ppc)$
    142144        \State $new\_size \gets \mathrm{instruction\_size}(instr,new\_length)$
     145        \Comment compute size in bytes
    143146        \State $new\_added \gets added+(new\_size-old\_size)$
     147        \Comment keep track of total added bytes
    144148        \State $new\_sigma \gets old\_sigma$
    145149        \State $new\_sigma_1(ppc+1) \gets pc+new\_size$
    146         \State $new\_sigma_2(ppc) \gets new\_length$ \\
     150        \State $new\_sigma_2(ppc) \gets new\_length$
     151        \Comment update $\sigma$ \\
    147152        \Return $\langle new\_added, pc+new\_size, new\_sigma \rangle$
    148153\EndFunction
     
    164169        \item $instr$, the instruction currently under consideration;
    165170        \item $ppc$, the pseudo-address of $instr$;
    166         \item $acc$, the fold accumulator, which contains $pc$ (the highest memory
    167                 address reached so far), $added$ (the number of bytes added to the program
    168                 size with respect to the previous iteration), and of course $sigma$, the
     171        \item $acc$, the fold accumulator, which contains $added$ (the number of
     172        bytes added to the program size with respect to the previous iteration), $pc$
     173        (the highest memory address reached so far), and of course $sigma$, the
    169174                $\sigma$ function under construction.
    170175\end{itemize}
Note: See TracChangeset for help on using the changeset viewer.