▲
GN⁺ 4달전 | parent | ★ favorite | on: 컴파일러가 당신을 놀라게 할 때(xania.org)
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 영상 링크