Convert GCC Inline Assembly CMOV to Visual Studio Assembler

Question

In Linear vs. Binary Search There is a fast binary search implementation that uses the CMOV command. I would like to implement this in VC ++, because the application I'm working on relies on binary search performance.

The implementation has a built-in assembler GCC, which is declared as follows:

static int binary_cmov (const int *arr, int n, int key) {
    int min = 0, max = n;
    while (min < max) {
            int middle = (min + max) >> 1;

            asm ("cmpl %3, %2\n\tcmovg %4, %0\n\tcmovle %5, %1"
                 : "+r" (min),
                   "+r" (max)
                 : "r" (key), "g" (arr [middle]),
                   "g" (middle + 1), "g" (middle));

            // Equivalent to 
            // if (key > arr [middle])
            //    min = middle + 1;
            // else
            //    max = middle;
    }
    return min;
}

I would like to convert this GCC Assembler into a Microsoft Visual Studio compatible assembler, but as GCC noob did not know where to start.

Can someone help or at least explain the GCC Inline Assembler? TIA!

Answer 1

, :

int binary_cmov (const int *arr, int n, int key) 
{
    int min = 0, max = n;
    while (min < max) 
    {
      int middle = (min + max) >> 1;
      min = key > arr[middle] ? middle + 1 : min;
      max = key > arr[middle] ? max : middle;
    }
    return min;
}

gcc5.3 -O3 :

binary_cmov(int const*, int, int):
        xorl    %eax, %eax
        testl   %esi, %esi
        jle     .L4
.L3:
        leal    (%rax,%rsi), %ecx
        sarl    %ecx
        movslq  %ecx, %r8
        leal    1(%rcx), %r9d
        movl    (%rdi,%r8,4), %r8d
        cmpl    %edx, %r8d
        cmovl   %r9d, %eax
        cmovge  %ecx, %esi
        cmpl    %eax, %esi
        jg      .L3
        rep ret
.L4:
        rep ret

- . , , .

...

?

#include <utility>

template<class...Ts>
  auto sum(Ts...ts)
{
  std::common_type_t<Ts...> result = 0;
  using expand = int[];
  void(expand{ 0, ((result += ts), 0)... });
  return result;
}

template<class...Ts>
  auto average(Ts...ts)
{
  return sum(ts...) / sizeof...(Ts);
}

int binary_cmov (const int *arr, int n, int key) 
{
    int min = 0, max = n;
    while (min < max) 
    {
      int middle = average(min, max);
      auto greater = key > arr[middle];
      min = greater ? middle + 1 : min;
      max = greater ? max : middle;
    }
    return min;
}

:

binary_cmov(int const*, int, int):
        xorl    %eax, %eax
        testl   %esi, %esi
        jle     .L4
.L3:
        leal    (%rax,%rsi), %ecx
        movslq  %ecx, %rcx
        shrq    %rcx
        movslq  %ecx, %r8
        leal    1(%rcx), %r9d
        movl    (%rdi,%r8,4), %r8d
        cmpl    %edx, %r8d
        cmovl   %r9d, %eax
        cmovge  %ecx, %esi
        cmpl    %eax, %esi
        jg      .L3
        rep ret
.L4:
        rep ret

Answer 2

Visual Studio 2013 CMOV:

int binary_cmov (const int *arr, int n, int key) 
{
    int min = 0, max = n;
    while (min < max) 
    {
      int middle = (min + max) >> 1;
      int middle1 = middle + 1;
      min = key > arr[middle] ? middle1 : min;
      max = key > arr[middle] ? max : middle;
    }
    return min;
}

cl /Ox /Fa /c t286.c :

; Listing generated by Microsoft (R) Optimizing Compiler Version 18.00.40629.0 

binary_cmov PROC
    mov QWORD PTR [rsp+8], rbx
; Line 3
    xor eax, eax
    mov ebx, r8d
    mov r11d, edx
; Line 4
    test    edx, edx
    jle SHORT $LN9@binary_cmo
$LL2@binary_cmo:
; Line 6
    lea r10d, DWORD PTR [r11+rax]
    sar r10d, 1
; Line 8
    movsxd  r8, r10d
    lea r9d, DWORD PTR [r10+1]
    cmp ebx, DWORD PTR [rcx+r8*4]
; Line 9
    cmovg   r10d, r11d
    cmovg   eax, r9d
    mov r11d, r10d
    cmp eax, r10d
    jl  SHORT $LL2@binary_cmo
$LN9@binary_cmo:
; Line 12
    mov rbx, QWORD PTR [rsp+8]
    ret 0
binary_cmov ENDP

Visual Studio 2015 2010. Visual Studio , , . middle1 middle + 1 , Visual Studio CMOV . .

Yakk, Visual Stdio 2015 Update 3 , , CMOV, .

Answer 3

() , inline asm, . .

, " , GCC Inline Assembler". , FWIW:

:

"cmpl %3, %2\n\tcmovg %4, %0\n\tcmovle %5, %1"

, VS.

• cmpl - gcc asm . , -. , l , longs ( long 4 ). , . , intel mov eax, 1, att movl $1, %eax ( ,% ). , .
• \n\t - gcc . , '\n' '\ t' , .
• % 0-% 5 - (, ), , , printf. , (: printf("2 + 2 = %d\n", 2+2);). gcc . % 0 - , % 5 - ( ).

. , , :

             : "+r" (min),
               "+r" (max)

'+' , . , '='. , , (.. ). "R" , asm. , . ; % 0 min % 1 max, .

. , , , 'g' . , . .

             : "r" (key), "g" (arr [middle]),
               "g" (middle + 1), "g" (middle));

gcc inline asm (. https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html), . , , "r" "g" (https://gcc.gnu.org/onlinedocs/gcc/Constraints.html).

, . , , , , . , , , , - .

.

, ...

Answer 4

VS2015 3 cmova cmovbe, s > < =:

int binary_cmov(const int *arr, int n, int key) 
{
    int min = 0, max = n;
    while (min < max) 
    // cmp         r9,r8  
    // jb          binary_cmov+1B0h 
    {
        int middle = (min + max) >> 1;
        // lea         rdx,[r8+r9]  
        // shr         rdx,1  
        int middle1 = middle + 1;
        // lea         rax,[rdx+4]  
        min = key > arr[middle] ? middle1 : min;
        // cmp         r10,dword ptr [rdi+rdx*4]  
        // cmova       r9,rax  
        max = key <= arr[middle] ? middle : max;
        // cmovbe      r8,rdx  
    }
    return min;
}

i7-5600U ( ), 512 . , , > 512 , .

:

// the array must be terminated with a value that is larger than 
// any value searched for e.g. MAX_INT (the sentinel)
// the index of the equal or greater entry is returned
int find_in_terminated_array(const int *arr, int key) 
{
    int * p = arr;
    while(key > *p) +p;
    return p - arr;
 }