Changeset 3521
 Timestamp:
 Nov 20, 2014, 4:40:46 PM (5 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

Papers/jarassembler2014/boenderjar2014.tex
r3520 r3521 252 252 253 253 % JB and CSC 254 One of the consequences of using the MCS51 instruction set is that we have to take its specific branch instructions into account. The MCS51 has three different types of branch instructionwhich one should be used depends on the distance between the instruction and its target . This applies to unconditional branches, conditional branches and procedure calls.254 One of the consequences of using the MCS51 instruction set is that we have to take its specific branch instructions into account. The MCS51 has three different types of branch instructionwhich 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. 255 255 256 256 The three different types of branch instructions are: … … 265 265 Apart 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. 266 266 267 The {\em branch optimisation problem}, a wellknown 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. 267 The {\em branch optimisation problem}, a wellknown 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 269 The branch displacement problem has been found to be NPcomplete for several 270 similar architectures~\cite{Robertson1979,Szymanski1978}, therefore an optimal 271 solution could be timeconsuming to find. The standard 272 solution~\cite{Szymanski1978,Dickson2008} is to use a fixed point algorithm. 273 274 Two flavours of solution are possible: either a greatest fixed point algorithm 275 (encoding all branches as long and then replacing them by shorter branches 276 insofar possible), or a least fixed point algorithm (encoding all branches as 277 short and then replacing them by longer branches as necessary). The advantage 278 of a greatest fixed point algorithm is that it can be stopped after any 279 iteration, as all the intermediate solutions are safe, if not necessarily 280 optimal. This is not the case for a least fixed point algorithm, but this 281 algorithm, if it terminates, will result in a smaller solution. 282 283 In the particular case of the MCS51 instruction set, matters are complicated 284 by the existence of the absolute branch. Now, the encoding of a branch does not 285 solely depend on its span, but also on their location within the program. This 286 means that instead of being determined solely by the size of instructions 287 within its span, the encoding of a branch is determined also by all of the 288 branches that precede it. 268 289 269 290 %%%%%%%%%%%%%%%%%%%%%%
Note: See TracChangeset
for help on using the changeset viewer.