▲

컴파일러가 당신을 놀라게 할 때

 (xania.org)
1P by GN⁺ 14일전 | ★ favorite | 댓글 1개
  • 간단한 정수 합산 함수를 컴파일할 때 GCC와 Clang의 최적화 차이를 관찰한 사례
  • GCC는 루프 내에서 두 수를 한 번에 더하는 x*2 + 1 형태의 루프 최적화를 수행
  • Clang은 루프를 완전히 제거하고, v(v - 1)/2라는 닫힌 형태의 수식으로 계산을 대체
  • 이 변환으로 코드가 O(n)에서 O(1) 로 바뀌며, 수학적 단순화가 자동으로 이루어짐
  • 20년 넘게 컴파일러를 다뤄온 저자도 놀랄 만큼, 컴파일러의 지능적 최적화 수준을 보여주는 사례

GCC의 루프 최적화

  • 단순한 정수 합산 함수를 작성했을 때 GCC는 루프 기반의 효율적 합산 코드를 생성
    • 루프 내부에서 lea edx, [rdx+1+rax*2] 명령을 사용해 두 수를 동시에 더함
    • 이는 x와 x+1을 더하는 연산을 x*2 + 1로 변환한 형태
  • 최적화 레벨을 -O3로 높이면 병렬 덧셈(vectorization) 을 통해 루프를 더 빠르게 처리
  • 이러한 방식은 반복문을 유지하면서도 연산 효율을 극대화하는 전통적 최적화 형태

Clang의 수학적 최적화

  • 동일한 코드를 Clang으로 컴파일하면 루프가 완전히 사라짐
    • Clang은 입력값이 양수인지 확인한 뒤, 일련의 lea, imul, shr 명령으로 계산 수행
    • 결과적으로 (v² - v)/2, 즉 정수 합의 닫힌 형태 수식으로 변환
  • 이 변환은 반복문을 제거하고 상수 시간(O(1)) 계산으로 대체
  • 저자는 이 결과를 “정수 합의 수학적 해법을 스스로 찾아낸 것”이라 표현

수식 전개 과정

  • Clang이 생성한 어셈블리 코드를 수학적으로 역추적하면 다음과 같은 변환이 이루어짐
    • v + ((v - 1)(v - 2) / 2) - 1
    • 이를 전개하고 정리하면 (v² - v)/2로 단순화
  • 최종적으로 v(v - 1)/2 형태가 되어, 1부터 v까지의 합 공식과 일치
  • 이 과정은 컴파일러가 수학적 패턴을 인식하고 최적화한 사례로 제시됨

컴파일러의 지능적 동작

  • Clang이 이 특정 명령 시퀀스를 사용하는 이유는 오버플로 방지와 유도 변수 추적 방식 때문으로 설명
  • 정확한 내부 동작 원인은 명확하지 않지만, Clang의 내부 최적화 로직이 복합적으로 작용한 결과로 언급
  • 저자는 이러한 결과를 “겸허하고 영감을 주는 경험”으로 표현

마무리 및 시리즈 맥락

  • 이 글은 ‘Advent of Compiler Optimisations 2025’ 시리즈의 24번째 글
  • 컴파일러가 코드 변환을 통해 수학적 단순화와 성능 향상을 달성하는 과정을 탐구
  • 저자는 “컴파일러는 여전히 나를 놀라게 한다”며, 오랜 경험에도 불구하고 지속되는 기술적 경이로움을 강조
▲
GN⁺ 14일전  [-]
Hacker News 의견들

  • 이 기능을 구현한 코드는 ScalarEvolution.cpp와 IndVarSimplify.cpp에 있음

    • 한 파일에 거의 16,000줄의 코드가 들어있다는 게 놀랍고 동시에 약간 불안한 느낌임

  • 이런 종류의 최적화는 정말 흥미로움
    컴파일러 최적화는 크게 두 가지로 나뉨 — 데이터 흐름 분석과 패턴 인식 및 대체
    첫 번째는 대부분의 프로그램에 효과적이고, 두 번째는 점점 수익이 줄어드는 패턴 누적 작업임
    링크된 예시는 똑똑하고 재밌지만 실제로는 큰 가치가 없음. 45년 동안 그런 루프를 작성한 적이 없었음
    물론 이런 패턴 치환은 고수준 코드에서 자동으로 생성되기 때문에 여전히 중요함
    솔직히 말하면, 내 optimizer가 이런 최적화를 못 해서 약간 투덜거리는 걸 수도 있음

    • 실제로는 생각보다 더 가치가 있을 수도 있음. LLVM의 SCEV(Scalar Evolution) 는 주로 분석용으로 쓰이고, 수학 루프 외의 다른 최적화도 가능하게 함
    • 어떤 최적화를 수행했는지 명확하지 않음. 예전에 틈새용 컴파일러를 만들 때, 내가 직접 작성한 최적화보다 컴파일러가 더 똑똑하게 처리하는 걸 보고 놀랐던 기억이 있음

  • 이건 Scalar Evolution(SCEV) 이라 불리는 기능이며, LLVM에서는 꽤 복잡하게 구현되어 있음

  • 비슷한 최적화 사례로 “Do not optimize away” 글이 있음

    • 그 글의 초반 설명은 약간 틀림. 코드가 0부터 N까지 더하지만 N은 제외하므로, 실제로는 N(N-1)/2가 맞음. 수학적으로 1부터 N까지의 합은 N(N+1)/2이므로, 상한을 제외하려면 N을 (N-1)로 바꿔야 함
    • 컴파일러가 여전히 이걸 최적화할 수 있지 않을까 생각함. 상수 폴딩 버전과 비상수 버전을 각각 만들어 런타임에 분기하면 가능할 듯함

  • 이 최적화의 진짜 멋진 점은 일반화(generic) 되어 있다는 것임
    단순히 “유한 정수열의 합” 패턴을 인식하는 게 아니라, 범용적으로 적용된다는 게 인상적임

  • 컴파일러가 더 많은 closed form을 추가할 수도 있을 것 같음. 그럴 가치가 있을까 궁금함
    관련 개념으로 Wilf–Zeilberger pair가 있음

  • 또 한 번 GCC가 Clang보다 느린 결과에 놀랐음
    GCC가 20년이나 앞서 있었는데도 여전히 Clang이 더 빠른 코드를 내는 경우가 있음
    예전에 비트 추출을 할 때 Clang은 두 번의 시프트로 끝냈는데, GCC는 세 번이나 했음

    • GCC와 LLVM/Clang 사이에는 컴파일러 기술의 세대 차이가 큼. GCC는 여전히 대단한 프로젝트지만, 현대적 최적화 기법을 적용하기엔 구조적으로 어렵다고 들음
    • 실제 성능은 두 컴파일러가 비슷함. 서로 다른 최적화 패스를 갖고 있어서 상황에 따라 결과가 달라짐
    • GCC는 초기엔 라이선스 중심의 이상주의적 설계로 확장성이 떨어졌음. 지금은 많이 완화됐지만 코드 생성기가 여전히 복잡함. 반면 Clang은 구조가 단순해 최적화 구현이 쉬움. 개인적으로는 MSVC나 ICC의 출력도 꽤 괜찮다고 느낌
    • 혹시 bitfield 관련 코드였는지? GCC는 그 부분 최적화가 특히 약함

  • 누군가 그래프 색칠 문제(graph coloring) 를 상수로 대체하는 최적화를 시도했을까 궁금함

    • 그래프 색칠은 NP-hard 문제라 O(1)로 바꾸기 어려움. 평면 그래프라면 4색 정리가 적용되지만, 항상 같은 답이 나오진 않음. 그냥 그래프 이론 얘기를 하고 싶었음

  • 이건 구현과 명세의 경계를 흐리게 만드는 예시임
    우리가 구현을 작성한다고 생각하지만, 사실상 명세의 프록시를 작성하는 셈임
    즉, 컴파일러가 명령형 기계의 환상을 만들어내는 것임

  • 처음엔 Matt이 이런 동작을 모른다는 게 놀라웠음
    나도 대학 시절 LLVM IR을 가지고 놀다 재귀가 곱셈으로 단순화되는 걸 보고 충격받았음
    Matt이 몰랐다는 건, 이 최적화가 그가 다루지 않는 단순한 케이스에만 적용된다는 뜻일 수도 있음

    • 사실 그는 이미 알고 있었음. 2017년 발표에서 같은 예시를 직접 언급했음
      YouTube 영상 링크
답변달기