flat assembler
Message board for the users of flat assembler.

Index > Windows > Eliminating branches

Author
Thread Post new topic Reply to topic
nmake



Joined: 13 Sep 2012
Posts: 193
nmake
Hi.

I am looking after tricks to eliminate branches. Branches are expensive, do anyone know of some tricks or usage for eliminating branches in smart or non-smart ways. Can the carry flag be used for this in any way, teach me how to eliminate branches effectively. Smile
Post 15 Sep 2012, 05:20
View user's profile Send private message Reply with quote
cod3b453



Joined: 25 Aug 2004
Posts: 619
cod3b453
The simplest way is to "inline" sections of code; this may mean having local copies of code duplicated in a section to prevent branching/calling or loop unrolling so that more iterations are executed between loop branches.

As you've hinted, the carry flag (CF) can be used; usually this works well for cases where a statement such as:
Code:
A_ENABLE = 0x20          ; Must be single bit in this example

B_ENABLE = 0x01             ; Must be 1 for this example to match CF
B_COMMON = 0x10

if a and A_ENABLE then
   b := B_COMMON
else
   b := B_COMMON or B_ENABLE
end    
can be expressed as a function of CF:
Code:
CF := (a and A_ENABLE) ? 1 : 0
b := B_COMMON or (not CF)    
which would give the code:
Code:
sar eax,6               ; A_ENABLE shr 6 = 0.1 (CF=1)
cmc                    ; CF := not CF
adc ebx,B_COMMON  ; b := b + B_COMMON + not CF    
This can be extended to other values but will be more complex and at some point slower than a branched version.

Another trick is lookup tables (LUT), where an if or select statement on a value that is small (eg. 0,1,...,n-1) can be reduced to a LUT of size n and simply looking up the values has the same result as multiple branches to the right condition.

I'm sure there as more but those are all I can remember right now Cool
Post 15 Sep 2012, 07:36
View user's profile Send private message Reply with quote
JohnFound



Joined: 16 Jun 2003
Posts: 3500
Location: Bulgaria
JohnFound
The most common way is to use CMOV instruction.
There are some other tricks, but they are solutions to a particular problems.
For example function ABS:
Code:
      mov  edx, eax
      sar  edx, 31
      xor  eax, edx
      sub  eax, edx    

Min:
Code:
        sub     ebx,eax
        sbb     ecx,ecx
        and     ecx,ebx
        add     eax,ecx    

Max:
Code:
        sub     ebx,eax
        sbb     ecx,ecx
        not     ecx
        and     ecx,ebx
        add     eax,ecx    


Note however, that such tricks will make your code less readable, so such an optimizations should be kept for the later state of development, when the program works and bugs are cleared more or less.
Post 15 Sep 2012, 07:41
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
AsmGuru62



Joined: 28 Jan 2004
Posts: 1409
Location: Toronto, Canada
AsmGuru62
Also there are setCC instructions.
Here is a couple of examples.

1. During parsing of an integer value, which can be negative.
Code:
    ;
   ; ESI = text with an integer value
  ;       can be "7357632" (no negative sign)
       ;       can be "-73282" (negative sign present)
   ;
   xor     ecx, ecx
    cmp     byte [esi], '-'
   sete    cl
  add     esi, ecx
    ;
   ; ESI ^^^ will move forward 1 byte if negative sign present
 ;
    

2. Or to set up one of two cursors:
Code:
     CursorsHV       DD      0,0

     ...

     ;
   ; Load both cursors (somewhere at startup)
  ;
   mov     ebx, [hInstance]
    mov     edi, CursorsHV
      invoke  LoadCursor, ebx, IDR_CURSOR_HORZ
    stosd
       invoke  LoadCursor, ebx, IDR_CURSOR_VERT
    stosd

   ...

     ;
   ; Set up one of two cursors, depending on some flag
 ;
   xor     ecx, ecx
    cmp     [IsVerticalResize], 1
       sete    cl
  invoke  SetCursor, [CursorsHV + ecx*4]
    
Post 15 Sep 2012, 12:14
View user's profile Send private message Send e-mail Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Code:
sar eax,6               ; A_ENABLE shr 6 = 0.1 (CF=1)
cmc                     ; CF := not CF
adc ebx,B_COMMON        ; b := b + B_COMMON + not CF    
You can save the CMC instruction by using SBB instead:
Code:
sar eax,6               ; A_ENABLE shr 6 = 0.1 (CF=1)
sbb ebx,-B_COMMON - 1   ; b := b + B_COMMON + not CF    
Post 15 Sep 2012, 14:27
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.