[fpc-devel] x86-64 compilation of while loops

J. Gareth Moreton gareth at moreton-family.com
Mon May 28 01:55:11 CEST 2018

 I've come across an interesting situation with the compiler when it comes
to while loops.  It's not necessary erroneous, but I wonder if it incurs a
speed penalty.

 Using my code sample to demonstrate:


   TBinList = record
     Key: Integer;
     Data: CodePointer;
   PBinList = ^TBinList;

 function SearchBinList(List: PBinList; ListSize: Cardinal; Key: Integer;
out Data: CodePointer): Boolean;
   LoIndex, MidIndex, HiIndex: Cardinal;
   LoIndex := 0;
   HiIndex := ListSize;

   { Search binary list }
   while LoIndex + 1 < HiIndex do
       MidIndex := (LoIndex + HiIndex) shr 1;

       if List[MidIndex].Key > Key then
         HiIndex := MidIndex
         LoIndex := MidIndex;


   Data := List[LoIndex].Data;
   Result := (List[LoIndex].Key = Key);


 This is a binary search algorithm that I've streamlined as much as I can
for speed (e.g. there's no sanity check for ListSize being zero, and it
doesn't immediately exit the loop if it finds a match.

 The generated assembly (-O3) for the while loop is as follows:

     xorl    %r10d,%r10d
     jmp    .Lj6
     .balign 8,0x90
     movl    %r10d,%eax
     movl    %edx,%r11d
     addq    %r11,%rax
     shrq    $1,%rax
     movl    %eax,%ebx
     andl    $4294967295,%eax
     shlq    $4,%rax
     cmpl    (%rcx,%rax),%r8d
     cmovll    %ebx,%edx
     cmovnll    %ebx,%r10d
     movl    %r10d,%eax
     leaq    1(%rax),%r11
     movl    %edx,%eax
     cmpq    %rax,%r11
     jl    .Lj5

 In this case, the ".balign" hint adds 2 bytes to pad the loop.  However,
my question is this... why does it immediately jump to the end of the loop
to check the condition (which is very likely to be true on the first
iteration), only to jump to the beginning again? Granted, in this case the
condition is relatively simple, but why not simply check the condition
where the "jmp" instruction is, and jumping to the line after the "jl"
instruction if it's false? For example:

     xorl    %r10d,%r10d // 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20180528/0258acc1/attachment.html>

More information about the fpc-devel mailing list