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

> Clean Markdown view of GeekNews topic #25334. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=25334](https://news.hada.io/topic?id=25334)
- GeekNews Markdown: [https://news.hada.io/topic/25334.md](https://news.hada.io/topic/25334.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2025-12-26T04:37:45+09:00
- Updated: 2025-12-26T04:37:45+09:00
- Original source: [xania.org](https://xania.org/202512/24-cunning-clang)
- Points: 1
- Comments: 1

## Topic Body

- 간단한 정수 합산 함수를 컴파일할 때 **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번째 글  
- 컴파일러가 코드 변환을 통해 **수학적 단순화와 성능 향상**을 달성하는 과정을 탐구  
- 저자는 “컴파일러는 여전히 나를 놀라게 한다”며, **오랜 경험에도 불구하고 지속되는 기술적 경이로움**을 강조

## Comments



### Comment 48252

- Author: neo
- Created: 2025-12-26T04:37:45+09:00
- Points: 1

###### [Hacker News 의견들](https://news.ycombinator.com/item?id=46375384) 
- 이 기능을 구현한 코드는 [ScalarEvolution.cpp](https://github.com/llvm/llvm-project/blob/release/21.x/llvm/lib/Analysis/ScalarEvolution.cpp)와 [IndVarSimplify.cpp](https://github.com/llvm/llvm-project/blob/release/21.x/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp)에 있음  
  - 한 파일에 거의 **16,000줄**의 코드가 들어있다는 게 놀랍고 동시에 약간 불안한 느낌임  

- 이런 종류의 최적화는 정말 흥미로움  
  컴파일러 최적화는 크게 두 가지로 나뉨 — **데이터 흐름 분석**과 **패턴 인식 및 대체**  
  첫 번째는 대부분의 프로그램에 효과적이고, 두 번째는 점점 수익이 줄어드는 패턴 누적 작업임  
  링크된 예시는 똑똑하고 재밌지만 실제로는 큰 가치가 없음. 45년 동안 그런 루프를 작성한 적이 없었음  
  물론 이런 패턴 치환은 고수준 코드에서 자동으로 생성되기 때문에 여전히 중요함  
  솔직히 말하면, 내 **optimizer**가 이런 최적화를 못 해서 약간 투덜거리는 걸 수도 있음  
  - 실제로는 생각보다 더 가치가 있을 수도 있음. LLVM의 **SCEV(Scalar Evolution)** 는 주로 분석용으로 쓰이고, 수학 루프 외의 다른 최적화도 가능하게 함  
  - 어떤 최적화를 수행했는지 명확하지 않음. 예전에 틈새용 컴파일러를 만들 때, 내가 직접 작성한 최적화보다 컴파일러가 더 똑똑하게 처리하는 걸 보고 놀랐던 기억이 있음  

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

- 비슷한 최적화 사례로 [“Do not optimize away” 글](https://matklad.github.io/2025/12/09/do-not-optimize-away.html)이 있음  
  - 그 글의 초반 설명은 약간 틀림. 코드가 0부터 N까지 더하지만 N은 제외하므로, 실제로는 **N(N-1)/2**가 맞음. 수학적으로 1부터 N까지의 합은 N(N+1)/2이므로, 상한을 제외하려면 N을 (N-1)로 바꿔야 함  
  - 컴파일러가 여전히 이걸 최적화할 수 있지 않을까 생각함. 상수 폴딩 버전과 비상수 버전을 각각 만들어 런타임에 분기하면 가능할 듯함  

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

- 컴파일러가 더 많은 **closed form**을 추가할 수도 있을 것 같음. 그럴 가치가 있을까 궁금함  
  관련 개념으로 [Wilf–Zeilberger pair](https://en.wikipedia.org/wiki/Wilf%E2%80%93Zeilberger_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 영상 링크](https://www.youtube.com/watch?v=bSkpMdDe4g4&t=2640)