【정리】builtin_의혹 해결

최근에 GLib의 코드를 보고 이것을 만났어요. 인터넷에서 한 바퀴 검색해 보니 많은 사람들이 이걸 썼어요. 오늘에야 비로소 연구를 해서 땀을 흘리고 맹인을 퇴치하는 점을 발견했어요. 이 기록을 증거로 남겨주세요!
먼저 가장 공식적인 설명을 보십시오.
======
likely() and unlikely()
What are they ?
      In Linux kernel code, one often find calls to likely() and unlikely(), in conditions, like :

bvl = bvec_alloc(gfp_mask, nr_iovecs, &idx);
if (unlikely(!bvl)) {
  mempool_free(bio, bio_pool);
  bio = NULL;
  goto out;
}

      In fact, these functions are hints for the compiler that allows it to correctly optimize the branch, by knowing which is the likeliest one. The definitions of these macros, found in include/linux/compiler.h are the following :

#define likely(x)       __builtin_expect(!!(x), 1)
#define unlikely(x)     __builtin_expect(!!(x), 0)

The GCC documentation explains the role of __builtin_expect() :

-- Built-in Function: long __builtin_expect (long EXP, long C)
     You may use `__builtin_expect' to provide the compiler with branch
     prediction information.  In general, you should prefer to use
     actual profile feedback for this (`-fprofile-arcs'), as
     programmers are notoriously bad at predicting how their programs
     actually perform.  However, there are applications in which this
     data is hard to collect.

     The return value is the value of EXP, which should be an integral
     expression.  The value of C must be a compile-time constant.  The
     semantics of the built-in are that it is expected that EXP == C.
     For example:

          if (__builtin_expect (x, 0))
            foo ();

     would indicate that we do not expect to call `foo', since we
     expect `x' to be zero.  Since you are limited to integral
     expressions for EXP, you should use constructions such as

          if (__builtin_expect (ptr != NULL, 1))
            error ();

     when testing pointer or floating-point values.

How does it optimize things ?
      It optimizes things by ordering the generated assembly code correctly, to optimize the usage of the processor pipeline. To do so, they arrange the code so that the likeliest branch is executed without performing any jmp instruction (which has the bad effect of flushing the processor pipeline).
To see how it works, let's compile the following simple C user space program with gcc -O2 :

#define likely(x)    __builtin_expect(!!(x), 1)
#define unlikely(x)  __builtin_expect(!!(x), 0)

int main(char *argv[], int argc)
{
   int a;

   /* Get the value from somewhere GCC can't optimize */
   a = atoi (argv[1]);

   if (unlikely (a == 2))
      a++;
   else
      a--;

   printf ("%d
", a);

   return 0;
}

Now, disassemble the resulting binary using objdump -S (comments added by me) :

080483b0 <main>:
 // Prologue
 80483b0:       55                      push   %ebp
 80483b1:       89 e5                   mov    %esp,%ebp
 80483b3:       50                      push   %eax
 80483b4:       50                      push   %eax
 80483b5:       83 e4 f0                and    $0xfffffff0,%esp
 //             Call atoi()
 80483b8:       8b 45 08                mov    0x8(%ebp),%eax
 80483bb:       83 ec 1c                sub    $0x1c,%esp
 80483be:       8b 48 04                mov    0x4(%eax),%ecx
 80483c1:       51                      push   %ecx
 80483c2:       e8 1d ff ff ff          call   80482e4 <atoi@plt>
 80483c7:       83 c4 10                add    $0x10,%esp
 //             Test the value
 80483ca:       83 f8 02                cmp    $0x2,%eax
 //             --------------------------------------------------------
 //             If 'a' equal to 2 (which is unlikely), then jump,
 //             otherwise continue directly, without jump, so that it
 //             doesn't flush the pipeline.
 //             --------------------------------------------------------
 80483cd:       74 12                   je     80483e1 <main+0x31>
 80483cf:       48                      dec    %eax
 //             Call printf
 80483d0:       52                      push   %edx
 80483d1:       52                      push   %edx
 80483d2:       50                      push   %eax
 80483d3:       68 c8 84 04 08          push   $0x80484c8
 80483d8:       e8 f7 fe ff ff          call   80482d4 <printf@plt>
 //             Return 0 and go out.
 80483dd:       31 c0                   xor    %eax,%eax
 80483df:       c9                      leave
 80483e0:       c3                      ret

Now, in the previous program, replace the unlikely() by a likely(), recompile it, and disassemble it again (again, comments added by me) :

080483b0 <main>:
 //             Prologue
 80483b0:       55                      push   %ebp
 80483b1:       89 e5                   mov    %esp,%ebp
 80483b3:       50                      push   %eax
 80483b4:       50                      push   %eax
 80483b5:       83 e4 f0                and    $0xfffffff0,%esp
 //             Call atoi()
 80483b8:       8b 45 08                mov    0x8(%ebp),%eax
 80483bb:       83 ec 1c                sub    $0x1c,%esp
 80483be:       8b 48 04                mov    0x4(%eax),%ecx
 80483c1:       51                      push   %ecx
 80483c2:       e8 1d ff ff ff          call   80482e4 <atoi@plt>
 80483c7:       83 c4 10                add    $0x10,%esp
 //             --------------------------------------------------
 //             If 'a' equal 2 (which is likely), we will continue
 //             without branching, so without flusing the pipeline. The
 //             jump only occurs when a != 2, which is unlikely.
 //             ---------------------------------------------------
 80483ca:       83 f8 02                cmp    $0x2,%eax
 80483cd:       75 13                   jne    80483e2 <main+0x32>
 //             Here the a++ incrementation has been optimized by gcc
 80483cf:       b0 03                   mov    $0x3,%al
 //             Call printf()
 80483d1:       52                      push   %edx
 80483d2:       52                      push   %edx
 80483d3:       50                      push   %eax
 80483d4:       68 c8 84 04 08          push   $0x80484c8
 80483d9:       e8 f6 fe ff ff          call   80482d4 <printf@plt>
 //             Return 0 and go out.
 80483de:       31 c0                   xor    %eax,%eax
 80483e0:       c9                      leave
 80483e1:       c3                      ret

How should I use it ?
      You should use it only in cases when the likeliest branch is very very very likely, or when the unlikeliest branch is very very very unlikely.
======
가장 권위 있는 것을 보고 다음은'민간'이라는 표현을 보겠습니다.
======
likely, unlikely 매크로와 GCC 내장 함수builtin_expect()
GCC 매뉴얼의builtin_expect () 의 설명은 다음과 같습니다.
대부분의 프로그래머들이 지점 예측을 엉망으로 하기 때문에 GCC는 이 내장 함수를 제공하여 프로그래머가 지점 예측을 처리하고 프로그램을 최적화하도록 돕는다.첫 번째 인자exp는 정형 표현식이고, 이 내장 함수의 반환값도 이exp이며, c는 컴파일러 상수이다.이 함수의 의미는exp표현식의 값이 상수 c와 같기를 기대하고 GCC는 프로그램을 최적화시켜 이 조건에 부합되는 지점을 적당한 곳에 두는 것이다.일반적인 상황에서, 당신은 gcc의 매개 변수인 '- fprofile-arcs' 를 사용하여 프로그램이 실행하는 실행 절차와 지점 방향에 대한 실제 피드백 정보를 수집하는 것을 더욱 좋아할 수 있습니다.
이 프로그램은 정형 표현식만 제공하기 때문에 다른 유형의 표현식을 최적화하려면 바늘 형식을 사용할 수 있습니다.
likely와 unlikely는 gcc에서 확장된 프로세서와 관련된 매크로입니다:

#define  likely(x)        __builtin_expect(!!(x), 1) 
#define  unlikely(x)      __builtin_expect(!!(x), 0)

      
현재 프로세서는 모두 유수선이다. 어떤 안에는 여러 개의 논리 연산 단원이 있기 때문에 시스템은 여러 개의 지령을 앞당겨 병행 처리할 수 있지만 점프할 때 다시 지령을 받아야 한다. 이것은 지령을 다시 찾지 않아도 속도를 낮출 수 있다. 
그래서 likely와 unlikely를 도입했는데 그 목적은 조건 지점 예측의 정확성을 높이는 것이다. cpu는 뒤의 지령을 미리 불러오고 조건 이동 지령을 만났을 때 특정한 지점의 지령을 미리 예측하고 불러온다.likely는 이 조건이 극히 드물게 발생한다는 것을 확인할 수 있으며, 반대로 likely는 이 조건이 대부분 발생할 수 있다는 것을 의미한다.컴파일러는 cpu의 실행 효율을 최적화하기 위해 상응하는 코드를 생성할 것이다.
따라서 프로그래머는 코드를 작성할 때 판단 조건이 발생하는 확률에 따라 프로세서의 손가락질 조작을 최적화할 수 있다. 
예를 들면 다음과 같습니다.

int x, y; 
if(unlikely(x > 0)) 
    y = 1; 
else 
    y = -1;

위의 코드에서 gcc가 컴파일한 지령은 y=-1이라는 지령을 미리 읽는데 이것은 x의 값이 0보다 클 확률이 비교적 적은 상황에 적합하다. 
만약 x의 값이 대부분의 경우 0보다 크면likely(x>0)를 사용해야 한다. 이렇게 컴파일된 지령은 y=1이라는 지령을 미리 읽는 것이다.이렇게 하면 시스템이 실행될 때 재지정을 줄일 수 있다.
======
커널의 likely () 와 unlikely ()
먼저

if(likely(value))는if(value)

와 동등하다

if(unlikely(value))도if(value)

와 동등하다
      
__builtin_expect()는 GCC(version>=2.96)가 프로그래머에게 제공하는 것으로'분기 이동'의 정보를 컴파일러에 제공하기 위해 컴파일러가 코드를 최적화하여 명령 이동에 따른 성능 저하를 줄일 수 있도록 한다.
__builtin_expect((x), 1)는 x의 값이 진짜일 가능성이 더 크다는 것을 나타낸다.
__builtin_expect ((x), 0) 는 x의 값이 가짜일 가능성이 더 높다는 것을 나타낸다.
즉, likely()를 사용하면if 뒤에 있는 문장을 집행할 기회가 더 크고, unlikely()를 사용하면else 뒤에 있는 문장을 집행할 기회가 더 크다는 것이다.이런 방식을 통해 컴파일러는 컴파일링 과정에서 가능성이 더 큰 코드를 기면의 코드에 바짝 붙어 지령의 이동이 가져오는 성능의 하락을 줄일 수 있다.
======
한 바퀴 보고 가세요.
사람이 쓴 것은 자기도 좀 출력해야 한다. GLib-2.35.4를 열거하면
gmacros.h 코드는 다음과 같습니다.

/*
 * The G_LIKELY and G_UNLIKELY macros let the programmer give hints to 
 * the compiler about the expected result of an expression. Some compilers
 * can use this information for optimizations.
 *
 * The _G_BOOLEAN_EXPR macro is intended to trigger a gcc warning when
 * putting assignments in g_return_if_fail ().  
 */
#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__)
#define _G_BOOLEAN_EXPR(expr)                   \
 G_GNUC_EXTENSION ({                            \
   int _g_boolean_var_;                         \
   if (expr)                                    \
      _g_boolean_var_ = 1;                      \
   else                                         \
      _g_boolean_var_ = 0;                      \
   _g_boolean_var_;                             \
})
//                --        
#define G_LIKELY(expr) (__builtin_expect (_G_BOOLEAN_EXPR(expr), 1))
#define G_UNLIKELY(expr) (__builtin_expect (_G_BOOLEAN_EXPR(expr), 0))
#else
#define G_LIKELY(expr) (expr)
#define G_UNLIKELY(expr) (expr)
#endif

위에서 보듯이
GLib에서 사용
_G_BOOLEAN_EXPR(expr)이 대신했습니다!!(expr)
.기능적으로는 똑같아요.