#28 RFE: GOTO optimization for PIC16


Dear Vangelis,

I worked out an optimization that turns GOTOs
(2 words in program memory) into BRAs (using
only 1 word) by modifying the pCode.
(This cannot be done using the normal peephole
optimizer because of problems mentioned below).

The optimization actually has two aims:
(1) program memory is being reduced
(2) execution of "BTFSx; GOTO" pairs will be
sped up (saving one cycle if skipping,
as the GOTO leaves a NOP to execute).

Additionally the procedure turns
"BTFSx STATUS,i; GOTO" pairs into equivalent
"Bcc" instructions (with BTFSx being either BTFSS
or BTFSC and Bcc being one of BC, BZ, BOV, BN
or their negated variant).
This again speeds things up and reduces
program memory usage even further.

My code checks whether the destination labels
of the GOTO instructions are within +-1023 bytes
from the statement (the largest offset permitted
by BRA) or even within +-127 bytes (the largest
offset permitted by Bcc instructions) by summing
up the (estimated) sizes of all instructions in
between the GOTO and its destination; inline
assembly instructions (PS_ASMDIR) are assumed
to be 4 bytes (to be on the safe side).

Furthermore the procedure takes care NOT to destroy
jumptables (by conservatively estimating whether
the GOTo in question can be part of a jumptable or

Last but not least I make sure that no label(s)
attached to modified instructions get lost or
moved to wrong places (especially important
in cases like:
GOTO somewhere

which would otherwise be turned into

BC somewhere

turning the unconditional GOTO into a
conditional branch...).

Taking all this into consideration should result
in valid code in all cases.

To be on the safe side, I added a compiler switch
"--optimize-goto" to enable the feature and a
(conditional) call to the optimization
(pic16_optimizeJumps) to pic16glue().

I also modified the bankswitch-insertion procedure
from inserting GOTOs to using BRAs instead.

A patch to include this into the current CVS sources
has been uploaded (apply in src/pic16/ with -p0).

I am looking forward to getting comments/questions
about the patch,

Raphael Neider


  • Raphael Neider

    Raphael Neider - 2004-11-20

    Logged In: YES

    Hello again,

    I made two corrections to my patch:
    (1) glue.c: I moved the call to pic16_optimizeJumps() after
    pic16_analyzeBanking() as that function can insert
    instructions into the code that might lead to BRAs being
    unable to address their target label.

    (2) pcode.c: "BTFSS STATUS,x"-instructions are now properly
    replaced by "BNx" instructions (they were replaced by their
    non-negated counterparts due to a superfluos "& 0x0F" in
    "switch (condBraType & 0x0F)".

    Now it produces correct code...

    BTW: runtime improvements have been measured to be around
    >10% (using a loop-intensive division-benchmark)

    Raphael Neider

  • Raphael Neider

    Raphael Neider - 2004-11-21

    Logged In: YES

    Hello Vangelis,

    I just added another common special case to my optimization:
    goto label1
    goto label2
    is now optimized (if possible and valid) to
    Bcc label2

    New complete patch uploaded.

    Raphael Neider

  • Vangelis Rokas

    Vangelis Rokas - 2004-11-24

    Logged In: YES

    Patch accepted and succesfully applied.
    SDCC v. 2.4.7 #888

    This is a big advance for pic16 port, but we have to
    take care of the following points:
    1. accurately count inline assembly code, or don't optimize
    when a goto goes through such a block, (perhaps have a function
    to count how many instruction mnemonics are inside the inline
    block and return their respective size sum)
    2. accurately detect jumptables by adding of INFO pcodes
    before and after jumptables.

    I run a test on your changes but no faults were detected.
    Well done.


  • Vangelis Rokas

    Vangelis Rokas - 2004-11-24
    • assigned_to: nobody --> vrokas
    • status: open --> closed-accepted

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

No, thanks