서명된 정수 산술 오버플로를 정의되지 않은 상태로 유지하는 것을 정당화할 수 있는 의미 있는 통계 데이터가 있습니까?

서명된 정수 산술 오버플로를 정의되지 않은 상태로 유지하는 것을 정당화할 수 있는 의미 있는 통계 데이터가 있습니까?

C 표준은 서명된 정수 오버플로를 정의되지 않은 동작으로 명시적으로 지정합니다.그러나 대부분의 CPU는 오버플로에 대해 정의된 의미론으로 서명된 산술을 구현합니다(분할 오버플로는 제외).x / 0그리고.INT_MIN / -1).

컴파일러 작성자들은 이러한 오버플로의 정의되지 않은 특성을 활용하여 레거시 코드를 매우 미묘한 방식으로 파괴하는 경향이 있는 보다 공격적인 최적화를 추가해 왔습니다.예를 들어 이 코드는 이전 컴파일러에서는 작동했지만 현재 버전에서는 작동하지 않습니다.gcc그리고.clang:

/* Increment a by a value in 0..255, clamp a to positive integers.
   The code relies on 32-bit wrap-around, but the C Standard makes
   signed integer overflow undefined behavior, so sum_max can now 
   return values less than a. There are Standard compliant ways to
   implement this, but legacy code is what it is... */
int sum_max(int a, unsigned char b) {
    int res = a + b;
    return (res >= a) ? res : INT_MAX;
}

이러한 최적화가 가치가 있다는 확실한 증거가 있습니까?실제 사례 또는 고전적인 벤치마크에 대한 실제 개선 사항을 문서화하는 비교 연구가 있습니까?

저는 이것을 보면서 이 질문을 생각해냈습니다: C++Now 2018: John Regehr "마무리 키노트: 정의되지 않은 동작 및 컴파일러 최적화"

두 언어 모두 문제가 비슷하지만 답이 다를 수 있기 때문에 c와 c++에 태그를 붙입니다.

연구와 통계에 대해서는 잘 모르지만, 네, 컴파일러가 실제로 하는 것을 고려한 최적화가 분명히 있습니다.예, 매우 중요합니다(예: tldr 루프 벡터화).

컴파일러 최적화 외에도 고려해야 할 또 다른 측면이 있습니다.UB를 사용하면 C/C++ 부호 정수가 수학적으로 예상되는 대로 산술적으로 동작합니다.를 들면 예들어를.x + 10 > x(물론 유효한 코드의 경우) 지금은 유효하지만, 반환 동작에서는 그렇지 않습니다.

저는 서명된 오버플로 UB를 고려한 일부 최적화를 나열하는 Krister Walfridson의 블로그에서 어떻게 정의되지 않은 서명된 오버플로가 GCC에서 최적화를 가능하게 하는지에 대한 훌륭한 기사를 찾았습니다.다음 예는 그것에서 나온 것입니다.저는 그들에게 c++과 조립 예시를 추가하고 있습니다.

최적화가 너무 단순하거나 흥미롭지 않거나 영향이 없어 보이는 경우 이러한 최적화는 훨씬 더 큰 최적화 체인의 단계일 뿐입니다.나비 효과는 초기 단계에서 중요하지 않아 보이는 최적화가 이후 단계에서 훨씬 더 영향력 있는 최적화를 촉발할 수 있기 때문에 발생합니다.

예문이 말도 안 돼 보이는 경우(누가 쓸 것인가)x * 10 > 0와 C를 매우 수 . 상수, 매크로, 템플릿을 사용하여 C와 C++에서 이러한 종류의 예제를 매우 쉽게 얻을 수 있습니다.게다가 컴파일러는 IR에 변환과 최적화를 적용할 때 이러한 예를 얻을 수 있습니다.

부호 있는 정수 표현식 단순화

• 0과 비교하여 곱셈 제거

  (x * c) cmp 0   ->   x cmp 0 
  

  bool foo(int x) { return x * 10 > 0 }
  

  foo(int):
          test    edi, edi
          setg    al
          ret
  

• 곱셈 후 분할 제거

  (x * c1) / c2 -> x * (c1 / c2) 만약 c1이 c2로 나눈다면

  int foo(int x) { return (x * 20) / 10; }
  

  foo(int):
          lea     eax, [rdi+rdi]
          ret
  

• 부정 제거

  (-x) / (-y) -> x / y

  int foo(int x, int y) { return (-x) / (-y); }
  

  foo(int, int):
          mov     eax, edi
          cdq
          idiv    esi
          ret
  

• 항상 참 또는 거짓인 비교 간소화

  x + c < x       ->   false
  x + c <= x      ->   false
  x + c > x       ->   true
  x + c >= x      ->   true
  

  bool foo(int x) { return x + 10 >= x; }
  

  foo(int):
          mov     eax, 1
          ret
  

• 비교에서 부정적인 요소 제거

  (-x) cmp (-y)   ->   y cmp x
  

  bool foo(int x, int y) { return -x < -y; }
  

  foo(int, int):
          cmp     edi, esi
          setg    al
          ret
  

• 상수의 크기 감소

  x + c > y       ->   x + (c - 1) >= y
  x + c <= y      ->   x + (c - 1) < y
  

  bool foo(int x, int y) { return x + 10 <= y; }
  

  foo(int, int):
          add     edi, 9
          cmp     edi, esi
          setl    al
          ret
  

• 비교에서 상수 제거

  (x + c1) cmp c2         ->   x cmp (c2 - c1)
  (x + c1) cmp (y + c2)   ->   x cmp (y + (c2 - c1)) if c1 <= c2
  

  두 번째 변환은 c1 <= c2인 경우에만 유효합니다. 그렇지 않으면 y에 INT_MIN 값이 있을 때 오버플로가 발생합니다.

  bool foo(int x) { return x + 42 <= 11; }
  

  foo(int):
          cmp     edi, -30
          setl    al
          ret
  

포인터 산술 및 유형 승격

작업이 오버플로우되지 않으면 더 넓은 유형으로 작업해도 동일한 결과를 얻을 수 있습니다.이는 64비트 아키텍처에서 어레이 인덱싱과 같은 작업을 수행할 때 유용합니다. 인덱스 계산은 일반적으로 32비트 int를 사용하지만 포인터는 64비트입니다.그리고 컴파일러는 형식 확장을 생성하는 대신 32비트 정수를 64비트 연산으로 승격시킴으로써 서명된 오버플로가 정의되지 않을 때 더 효율적인 코드를 생성할 수 있습니다.

정의되지 않은 오버플로는 a[i]와 [i+1]이(가) 인접하도록 보장합니다.이것은 벡터화 등을 위한 메모리 접근의 분석을 개선합니다.

이는 루프 벡터화가 가장 효율적이고 효과적인 최적화 알고리즘 중 하나로서 매우 중요한 최적화입니다.

다음은 서명되지 않은 인덱스에서 서명된 인덱스로 인덱스를 변경하면 생성된 어셈블리가 향상되는 예입니다.

서명되지 않은 버전

#include <cstddef>

auto foo(int* v, std::size_t start)
{
    int sum = 0;

    for (std::size_t i = start; i < start + 4; ++i)
        sum += v[i];

    return sum;
}

서명되지 않은 사건과 함께.start + 4랩어라운드를 고려해야 하며 이 경우를 처리하기 위해 분기가 생성됩니다(랩어라운드는 성능에 좋지 않습니다).

; gcc on x64 with -march=skylake

foo1(int*, unsigned long):
        cmp     rsi, -5
        ja      .L3
        vmovdqu xmm0, XMMWORD PTR [rdi+rsi*4]
        vpsrldq xmm1, xmm0, 8
        vpaddd  xmm0, xmm0, xmm1
        vpsrldq xmm1, xmm0, 4
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret
.L3:
        xor     eax, eax
        ret

; clang on x64 with -march=skylake

foo1(int*, unsigned long):                             # @foo1(int*, unsigned long)
        xor     eax, eax
        cmp     rsi, -4
        jae     .LBB0_2
        vpbroadcastq    xmm0, qword ptr [rdi + 4*rsi + 8]
        vpaddd  xmm0, xmm0, xmmword ptr [rdi + 4*rsi]
        vpshufd xmm1, xmm0, 85                  # xmm1 = xmm0[1,1,1,1]
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
.LBB0_2:
        ret

참고로, 더 좁은 유형을 사용하면 SSE 벡터화된 명령어의 사용을 방해하는 최악의 어셈블리가 될 수 있습니다.

#include <cstddef>

auto foo(int* v, unsigned start)
{
    int sum = 0;

    for (unsigned i = start; i < start + 4; ++i)
        sum += v[i];

    return sum;
}

; gcc on x64 with -march=skylake

foo(int*, unsigned int):
        cmp     esi, -5
        ja      .L3
        mov     eax, esi
        mov     eax, DWORD PTR [rdi+rax*4]
        lea     edx, [rsi+1]
        add     eax, DWORD PTR [rdi+rdx*4]
        lea     edx, [rsi+2]
        add     eax, DWORD PTR [rdi+rdx*4]
        lea     edx, [rsi+3]
        add     eax, DWORD PTR [rdi+rdx*4]
        ret
.L3:
        xor     eax, eax
        ret

; clang on x64 with -march=skylake

foo(int*, unsigned int):                              # @foo(int*, unsigned int)
        xor     eax, eax
        cmp     esi, -5
        ja      .LBB0_3
        mov     ecx, esi
        add     esi, 4
        mov     eax, dword ptr [rdi + 4*rcx]
        lea     rdx, [rcx + 1]
        cmp     rdx, rsi
        jae     .LBB0_3
        add     eax, dword ptr [rdi + 4*rcx + 4]
        add     eax, dword ptr [rdi + 4*rcx + 8]
        add     eax, dword ptr [rdi + 4*rcx + 12]
.LBB0_3:
        ret

서명된 버전

그러나 서명된 인덱스를 사용하면 벡터화된 분기 없는 코드가 생성됩니다.

#include <cstddef>

auto foo(int* v, std::ptrdiff_t start)
{
    int sum = 0;

    for (std::ptrdiff_t i = start; i < start + 4; ++i)
        sum += v[i];

    return sum;
}

; gcc on x64 with -march=skylake

foo(int*, long):
        vmovdqu xmm0, XMMWORD PTR [rdi+rsi*4]
        vpsrldq xmm1, xmm0, 8
        vpaddd  xmm0, xmm0, xmm1
        vpsrldq xmm1, xmm0, 4
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret

; clang on x64 with -march=skylake

foo(int*, long):                              # @foo(int*, long)
        vpbroadcastq    xmm0, qword ptr [rdi + 4*rsi + 8]
        vpaddd  xmm0, xmm0, xmmword ptr [rdi + 4*rsi]
        vpshufd xmm1, xmm0, 85                  # xmm1 = xmm0[1,1,1,1]
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret

벡터화된 명령어는 더 좁은 부호 유형을 사용할 때에도 여전히 사용됩니다.

#include <cstddef>

auto foo(int* v, int start)
{
    int sum = 0;

    for (int i = start; i < start + 4; ++i)
        sum += v[i];

    return sum;
}

; gcc on x64 with -march=skylake

foo(int*, int):
        movsx   rsi, esi
        vmovdqu xmm0, XMMWORD PTR [rdi+rsi*4]
        vpsrldq xmm1, xmm0, 8
        vpaddd  xmm0, xmm0, xmm1
        vpsrldq xmm1, xmm0, 4
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret

; clang on x64 with -march=skylake

foo(int*, int):                              # @foo(int*, int)
        movsxd  rax, esi
        vpbroadcastq    xmm0, qword ptr [rdi + 4*rax + 8]
        vpaddd  xmm0, xmm0, xmmword ptr [rdi + 4*rax]
        vpshufd xmm1, xmm0, 85                  # xmm1 = xmm0[1,1,1,1]
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret

값 범위 계산

컴파일러는 프로그램의 각 지점에서 변수의 가능한 값 범위, 즉 다음과 같은 코드를 추적합니다.

int x = foo();
if (x > 0) {
  int y = x + 5;
  int z = y / 4;

그것은 x가 범위를 가지고 있다고 결정합니다.[1, INT_MAX]if-문 뒤에, 따라서 y가 범위를 가지고 있다고 결정할 수 있습니다.[6, INT_MAX]오버플로가 허용되지 않기 때문입니다.은 다음라최적수있다니습할화은인▁to로 최적화할 수 있습니다.int z = y >> 2;컴파일러가 y가 음이 아닌 것을 알고 있기 때문입니다.

auto foo(int x)
{
    if (x <= 0)
        __builtin_unreachable();
    
    return (x + 5) / 4;
}

foo(int):
        lea     eax, [rdi+5]
        sar     eax, 2
        ret

되지 않은 는 두이 됩니다(는 가능한 하므로).[INT_MIN, (INT_MIN+4)]또는[6, INT_MAX]와의 모든 유용한 비교를 방지합니다.<또는>), 등

• 변경하기x<y이고, true로 true이고, true로 true이고, 입니다.x그리고.y되지
• 중min(x,y)또는max(x,y)x또는y가 겹치지 ▁if우▁the않▁do는▁ranges.
• 중abs(x)x또는-x가 교차하지 0
• 중x/cx>>log2(c)한다면x>0 리고상 수그상.c는 의거곱의 입니다.2
• 중x%cx&(c-1)한다면x>0 리고상 수그상.c는 의거곱의 입니다.2

루프 분석 및 최적화

정의되지 않은 서명된 오버플로가 루프 최적화에 도움이 되는 이유에 대한 표준적인 예는 다음과 같은 루프입니다.

for (int i = 0; i <= m; i++)

정의되지 않은 오버플로에 대해 종료됩니다.이것은 특정 루프 명령어가 있는 아키텍처가 일반적으로 무한 루프를 처리하지 않도록 도와줍니다.

그러나 정의되지 않은 서명된 오버플로는 더 많은 루프 최적화에 도움이 됩니다.반복 횟수 결정, 유도 변수 변환 및 메모리 액세스 추적과 같은 모든 분석은 작업을 수행하기 위해 이전 섹션의 모든 것을 사용합니다.특히 서명된 오버플로가 허용되면 벡터화할 수 있는 루프 집합이 크게 줄어듭니다.

최적화의 좋은 예는 아니지만 정의되지 않은 행동의 유용한 결과는 다음과 같습니다.-ftrapvGCC/clang의 명령줄 스위치입니다.정수 오버플로 시 프로그램을 충돌시키는 코드를 삽입합니다.

부호 없는 오버플로는 의도적이라는 개념에 따라 부호 없는 정수에서는 작동하지 않습니다.

서명된 정수 오버플로에 대한 표준의 문구는 사람들이 오버플로 코드를 의도적으로 작성하지 않도록 보장합니다.ftrapv는 의도하지 않은 오버플로를 발견하는 데 유용한 도구입니다.

여기 실제 작은 벤치마크인 버블 정렬이 있습니다.시간을 비교해 봤습니다.-fwrapv(Overflow 가 UB/not UB가 아님).다음은 결과(초)입니다.

                   -O3     -O3 -fwrapv    -O1     -O1 -fwrapv
Machine1, clang    5.2     6.3            6.8     7.7
Machine2, clang-8  4.2     7.8            6.4     6.7
Machine2, gcc-8    6.6     7.4            6.5     6.5

와 같이 not-UB, 비-UB()는-fwrapv느리고, 큰입니다.) 버은거의항느며리상전차, 가큰는이 1.85배다니입.

여기 코드가 있습니다.이 테스트에서 더 큰 차이가 발생할 수 있는 구현을 의도적으로 선택했습니다.

#include <stdio.h>
#include <stdlib.h>

void bubbleSort(int *a, long n) {
        bool swapped;
        for (int i = 0; i < n-1; i++) {
                swapped = false;
                for (int j = 0; j < n-i-1; j++) {
                        if (a[j] > a[j+1]) {
                                int t = a[j];
                                a[j] = a[j+1];
                                a[j+1] = t;
                                swapped = true;
                        }
                }

                if (!swapped) break;
        }
}

int main() {
        int a[8192];

        for (int j=0; j<100; j++) {
                for (int i=0; i<8192; i++) {
                        a[i] = rand();
                }

                bubbleSort(a, 8192);
        }
}

답은 실제로 당신의 질문에 있습니다.

그러나 대부분의 CPU는 정의된 의미론으로 서명된 산술을 구현합니다.

오늘날 당신이 살 수 있는 CPU는 부호 있는 정수에 대해 두 개의 상보적인 산술을 사용하지 않지만 항상 그런 것은 아니었습니다.

C 언어는 1972년에 발명되었습니다.그 당시에도 IBM 7090 메인프레임은 여전히 존재했습니다.모든 컴퓨터가 두 개의 칭찬을 받은 것은 아닙니다.

2s 전후로 언어(및 오버플로 동작)를 정의했다면 그렇지 않은 기계에서 코드 생성에 악영향을 미쳤을 것입니다.

또한 이미 말했듯이 서명된 오버플로를 UB로 지정하면 컴파일러가 더 나은 코드를 생성할 수 있습니다. 서명된 오버플로로 인해 발생하는 코드 경로를 할인할 수 있기 때문입니다.

만약 내가 그것이 a와 b의 합을 0으로 고정시키기 위한 것이라는 것을 정확히 이해한다면...INT_MAX는 랩어라운드 없이 두 가지 방법으로 이 함수를 작성할 수 있습니다.

첫째, 모든 CPU에서 작동하는 비효율적인 일반 사례:

int sum_max(int a, unsigned char b) {
    if (a > std::numeric_limits<int>::max() - b)
        return std::numeric_limits<int>::max();
    else
        return a + b;
}

둘째, 놀라울 정도로 효율적인 2s-compreement 구체적인 방법:

int sum_max2(int a, unsigned char b) {
    unsigned int buffer;
    std::memcpy(&buffer, &a, sizeof(a));
    buffer += b;
    if (buffer > std::numeric_limits<int>::max())
        buffer = std::numeric_limits<int>::max();
    std::memcpy(&a, &buffer, sizeof(a));
    return a;
}

결과 어셈블러는 https://godbolt.org/z/F42IXV 에서 확인할 수 있습니다.

언급URL : https://stackoverflow.com/questions/56047702/is-there-some-meaningful-statistical-data-to-justify-keeping-signed-integer-arit