#28 RFE: GOTO optimization for PIC16

closed-accepted
None
5
2004-11-24
2004-11-20
Raphael Neider
No

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
not).

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:
BTFSC STATUS,0
label:
GOTO somewhere

which would otherwise be turned into

label:
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,

regards,
Raphael Neider

Discussion

  • Raphael Neider
    Raphael Neider
    2004-11-20

    Logged In: YES
    user_id=1115835

    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)

    Regards,
    Raphael Neider

     
  • Raphael Neider
    Raphael Neider
    2004-11-21

    Logged In: YES
    user_id=1115835

    Hello Vangelis,

    I just added another common special case to my optimization:
    BTFS[SC] STATUS,i
    goto label1
    goto label2
    label1:
    <something>
    is now optimized (if possible and valid) to
    Bcc label2
    label1:

    New complete patch uploaded.

    regards,
    Raphael Neider

     
  • Raphael Neider
    Raphael Neider
    2004-11-21

    GOTO optimization for PIC16 port, v3

     
  • Vangelis Rokas
    Vangelis Rokas
    2004-11-24

    Logged In: YES
    user_id=770505

    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.

    regards,
    Vangelis.

     
  • Vangelis Rokas
    Vangelis Rokas
    2004-11-24

    • assigned_to: nobody --> vrokas
    • status: open --> closed-accepted