GCC는 정적 분기 예측을 위한 차선의 코드를 생성합니까?

GCC는 정적 분기 예측을 위한 차선의 코드를 생성합니까?

제 관례상 에서 에 더 .if에서의 것보다는else, 정적 분기 예측에 도움이 될 수 있습니다.예를 들어 다음과 같습니다.

if (check_collision(player, enemy)) { // very unlikely to be true
    doA();
} else {
    doB();
}

다음과 같이 다시 쓸 수 있습니다.

if (!check_collision(player, enemy)) {
    doB();
} else {
    doA();
}

Branch Patterns, Using GCC라는 블로그 게시물을 찾았습니다. 이는 이 현상을 더 자세히 설명합니다.

if문에 대해 정방향 분기가 생성됩니다.프로세서가 분기 명령 뒤에 오는 명령이 명령어 유닛 내의 명령어 버퍼에 이미 배치되어 있을 수 있다는 점을 이용할 수 있기 때문에 이러한 명령어를 취할 가능성이 없습니다.

그 옆에 (내 emphasis)라고 쓰여 있습니다.

if-else 문을 작성할 때는 항상 "그때" 블록이 다른 블록보다 실행될 가능성이 높으므로 프로세서는 명령어 페치 버퍼에 이미 있는 명령어를 활용할 수 있습니다.

궁극적으로 Intel, Branch and Loop Reconfiguration to Preventes에 의해 작성된 기사가 있는데, 여기에는 다음 두 가지 규칙이 요약되어 있습니다.

정적 분기 예측은 마이크로프로세서가 분기를 만났을 때 수집한 데이터가 없을 때 사용되며, 일반적으로 분기를 처음 접하는 경우입니다.규칙은 간단합니다.

• 전진 분기는 기본적으로 사용되지 않습니다.
• 뒤로 가지면 기본값은 다음과 같습니다.

이러한 규칙을 활용하기 위해 코드를 효과적으로 작성하려면 if-다른 경우를 작성하거나 문장을 전환할 때 가장 일반적인 경우를 먼저 확인하고 최소 일반적인 경우까지 점진적으로 작업합니다.

파이프라인 CPU는 코드 세그먼트 내의 다른 주소로 점프하여 명령 캐시를 깨지 않고 명령 캐시의 명령을 따를 수 있는 것으로 알고 있습니다.하지만 현대적인 CPU 마이크로아키텍처의 경우 이것이 지나치게 단순화될 수 있다는 것을 알고 있습니다.

하지만 GCC는 이 규칙들을 존중하지 않는 것 같습니다.주어진 코드:

extern void foo();
extern void bar();

int some_func(int n)
{
    if (n) {
        foo();
    }
    else {
        bar();
    }
    return 0;
}

를 생성합니다 를합니다(버전 6.3.0 with).-O3 -mtune=intel):

some_func:
        lea     rsp, [rsp-8]
        xor     eax, eax
        test    edi, edi
        jne     .L6            ; here, forward branch if (n) is (conditionally) taken
        call    bar
        xor     eax, eax
        lea     rsp, [rsp+8]
        ret
.L6:
        call    foo
        xor     eax, eax
        lea     rsp, [rsp+8]
        ret

가 원하는 행동을 를 다시 입니다.if다음과 같은 조건을 사용합니다.

if (__builtin_expect(n, 1)) { // force n condition to be treated as true

따라서 어셈블리 코드는 다음과 같습니다.

some_func:
        lea     rsp, [rsp-8]
        xor     eax, eax
        test    edi, edi
        je      .L2             ; here, backward branch is (conditionally) taken
        call    foo
        xor     eax, eax
        lea     rsp, [rsp+8]
        ret
.L2:
        call    bar
        xor     eax, eax
        lea     rsp, [rsp+8]
        ret

짧은 대답: 아니오, 그렇지 않습니다.

GCC는 방대한 양의 사소한 최적화를 수행하며, 그 중 하나는 제어 흐름 그래프로 판단하는 분기 확률을 추측하는 것입니다.

GCC 매뉴얼에 따라:

fno-guess-branch-확률

휴리스틱을 사용하여 분기 확률을 추측하지 마십시오.

GCC는 프로파일링 피드백을 통해 분기 확률이 제공되지 않는 경우 발견주의를 사용하여 분기 확률을 추측합니다(-fprofile-arcs). 이러한 휴리스틱은 관리 플로우 그래프를 기반으로 합니다.일부 분기 확률이 다음과 같이 지정되는 경우__builtin_expect, 그 다음 휴리스틱은 나머지 관리 흐름 그래프에 대한 분기 확률을 추측하는 데 사용됩니다.__builtin_expec장부에 기입합니다.휴리스틱과 휴리스틱 사이의 상호작용은__builtin_expect복잡할 수 있고, 어떤 경우에는 휴리스틱을 비활성화하여 효과를 낼 수 있도록 하는 것이 유용할 수 있습니다.__builtin_expect이해하기 쉽죠

-freorder-blocks가지도 바꿀 수 있습니다.

또한 OP가 언급한 것처럼 행동은 다음과 같이 무시될 수 있습니다.__builtin_expect.

증명

다음 목록을 보십시오.

void doA() { printf("A\n"); }
void doB() { printf("B\n"); }
int check_collision(void* a, void* b)
{ return a == b; }

void some_func (void* player, void* enemy) {
    if (check_collision(player, enemy)) {
        doA();
    } else {
        doB();
    }
}

int main() {
    // warming up gcc statistic
    some_func((void*)0x1, NULL);
    some_func((void*)0x2, NULL);
    some_func((void*)0x3, NULL);
    some_func((void*)0x4, NULL);
    some_func((void*)0x5, NULL);
    some_func(NULL, NULL);
    return 0;
}

는 것은 자명합니다.check_collision돌아올 것입니다0대개의 경우에그래서.doB()분기 가능성이 높고 GCC는 이를 추측할 수 있습니다.

gcc -O main.c -o opt.a
objdump -d opt.a

의 assm.some_func다음과 같습니다.

sub    $0x8,%rsp
cmp    %rsi,%rdi
je     6c6 <some_func+0x18>
mov    $0x0,%eax
callq  68f <doB>
add    $0x8,%rsp
retq   
mov    $0x0,%eax
callq  67a <doA>
jmp    6c1 <some_func+0x13>

하지만 우리는 GCC가 너무 똑똑하지 않도록 강제할 수 있습니다.

gcc -fno-guess-branch-probability main.c -o non-opt.a
objdump -d non-opt.a

그리고 우리는 다음을 얻게 될 것입니다.

push   %rbp
mov    %rsp,%rbp
sub    $0x10,%rsp
mov    %rdi,-0x8(%rbp)
mov    %rsi,-0x10(%rbp)
mov    -0x10(%rbp),%rdx
mov    -0x8(%rbp),%rax
mov    %rdx,%rsi
mov    %rax,%rdi
callq  6a0 <check_collision>
test   %eax,%eax
je     6ef <some_func+0x33>
mov    $0x0,%eax
callq  67a <doA>
jmp    6f9 <some_func+0x3d>
mov    $0x0,%eax
callq  68d <doB>
nop
leaveq 
retq  

그래서 GCC는 소스 순서대로 지점을 남길 것입니다.

저는 그 테스트를 위해 gcc 7.1.1을 사용했습니다.

'벌레'를 찾으셨다고 생각합니다

재미있는 점은 공간에 대한 최적화와 최적화가 없는 경우가 "최적" 명령 코드가 생성되는 유일한 경우라는 것입니다.gcc -S [-O0 | -Os] source.c

some_func:
FB0:
       pushl   %ebp
       movl    %esp, %ebp
       subl    $8, %esp
       cmpl    $0, 8(%ebp)
       je      L2
       call    _foo
       jmp     L3
2:
       call    _bar
3:
       movl    $0, %eax
       # Or, for -Os:
       # xorl    %eax, %eax
       leave
       ret

---

제 요점은...

---

some_func:
FB0:
       pushl   %ebp
       movl    %esp, %ebp
       subl    $8, %esp
       cmpl    $0, 8(%ebp)
       je      L2
       call    _foo

---

... 로 전화를 걸어foo출구 전략에 관계없이 전통적인 의미에서 모든 것이 "최적"입니다.

물론 최적성은 프로세서에 의해 결정됩니다.

언급URL : https://stackoverflow.com/questions/41880779/does-gcc-generate-suboptimal-code-for-static-branch-prediction