Changeset 3521


Ignore:
Timestamp:
Nov 20, 2014, 4:40:46 PM (5 years ago)
Author:
boender
Message:
  • some more additions
File:
1 edited

Legend:

Unmodified
Added
Removed
  • Papers/jar-assembler-2014/boender-jar-2014.tex

    r3520 r3521  
    252252
    253253% JB and CSC
    254 One of the consequences of using the MCS-51 instruction set is that we have to take its specific branch instructions into account. The MCS-51 has three different types of branch instruction---which one should be used depends on the distance between the instruction and its target. This applies to unconditional branches, conditional branches and procedure calls.
     254One of the consequences of using the MCS-51 instruction set is that we have to take its specific branch instructions into account. The MCS-51 has three different types of branch instruction---which one should be used depends on the distance between the instruction and its target (the {\em span}). This applies to unconditional branches, conditional branches and procedure calls.
    255255
    256256The three different types of branch instructions are:
     
    265265Apart from their difference in size, the instructions also take different amounts of time to execute: 2 cycles for the short and absolute branch, 3 cycles for the long branch.
    266266
    267 The {\em branch optimisation problem}, a well-known problem in assembler design, is to find the smallest branch instructions for a given assembler program. This is complicated by the fact that branch instructions can influence each other: the distance between an instruction and its target depends on the size of any branch instructions in between them.
     267The {\em branch optimisation problem}, a well-known problem in assembler design, is to find the smallest branch instructions for a given assembler program. This is complicated by the fact that branch instructions can influence each other: an instruction's span depends on the size of any branch instructions in between.
     268
     269The branch displacement problem has been found to be NP-complete for several
     270similar architectures~\cite{Robertson1979,Szymanski1978}, therefore an optimal
     271solution could be time-consuming to find. The standard
     272solution~\cite{Szymanski1978,Dickson2008} is to use a fixed point algorithm.
     273
     274Two flavours of solution are possible: either a greatest fixed point algorithm
     275(encoding all branches as long and then replacing them by shorter branches
     276insofar possible), or a least fixed point algorithm (encoding all branches as
     277short and then replacing them by longer branches as necessary). The advantage
     278of a greatest fixed point algorithm is that it can be stopped after any
     279iteration, as all the intermediate solutions are safe, if not necessarily
     280optimal. This is not the case for a least fixed point algorithm, but this
     281algorithm, if it terminates, will result in a smaller solution.
     282
     283In the particular case of the MCS-51 instruction set, matters are complicated
     284by the existence of the absolute branch. Now, the encoding of a branch does not
     285solely depend on its span, but also on their location within the program. This
     286means that instead of being determined solely by the size of instructions
     287within its span, the encoding of a branch is determined also by all of the
     288branches that precede it.
    268289
    269290%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%-%
Note: See TracChangeset for help on using the changeset viewer.