[fpc-devel] Experimentation: "Branch stitching"

[J. Gareth Moreton]

Hi everyone,

I don't know if this is an official term for this, but call it "branch 
stitching".  It's an idea that came to me recently and which I'm trying 
out with some success.

The principle is this... I look for blocks of code that look like the 
following (using x86) to start:

   jmp .L2
.L1:
   ...
   jmp .L3

The code between ".L1" and "jmp .L3" is essentially a self-contained 
subroutine since it can only be entered via a jump (the check for a JMP 
or RET instruction before .L1 is important to determine it can't enter 
the block via normal program flow.  After identifying these blocks, I 
see if I can 'detach' them from the assembly and reattach them 
immediately after a "jmp .L1" instruction, thereby eliminating that jump 
and potentially opening up other peephole optimisations - for example, 
in the pexpr unit - before:

     ...
     testb   %al,%al
     je     .Lj733
     subb    $1,%al
     je     .Lj734
     jmp    .Lj732
     .balign 16,0x90
.Lj733:
     ...
     jmp    .Lj718
     .balign 16,0x90
.Lj732:
     movl    $2019050530,%ecx
     call    VERBOSE_$$_INTERNALERROR$LONGINT
     jmp    .Lj718

The block with the internal error can be moved and 'stitched' to the 
"jmp .Lj732" instruction.

     ...
     testb    %al,%al
     je    .Lj733
     subb    $1,%al
     je    .Lj734
     movl    $2019050530,%ecx
     call    VERBOSE_$$_INTERNALERROR$LONGINT
     jmp    .Lj718
     .balign 16,0x90
.Lj733:
     ...

I'm still working a few things out, since it can move the function 
epilogue which makes things harder to read.  Currently I'm only moving 
blocks where the label only has a single reference, thereby causing a 
dead label when it's stitched alongside its corresponding jump.  This 
avoids problems where the label is referenced in a data block that's 
distinct from the assembly and where moving it may cause problems.

Kit