V8의 설계 선택을 비판적으로 검토하며 Sea of Nodes(IR)에서의 동치 클래스 별칭, 효과/제어 체인, 가드 최적화, 스케줄링, 방문 순서, 루프 분석, DCE, 캐시/컴파일 속도 등에 대한 경험과 해법을 간결히 정리한 글.
A Simple Reply to https://www.reddit.com/r/Compilers/comments/1jjldhu/land_ahoy_leaving_the_sea_of_nodes/
Because reddit crashes when I try to post this.
이 주제에 대해 한동안 침묵했는데, 내가 하는 어떤 답변도 방어적으로 들리거나 엇나간 것처럼 보일 수 있고 어느 정도는 그게 맞기 때문이다. 또한 채팅/이메일/IRC는 심도 있는 기술 토론을 하기에 끔찍한 곳이다. 하지만 여기와 다른 포럼에서 SoN을 옹호하는 사람들이 꽤 많았기에 결국 논쟁에 뛰어들기로 했다. :-P 설계 선택들을 보면, V8은 처음부터 스스로를 족쇄 채운 게 분명해 보인다. V8은 여러 선택을 했고, 그 결과 여러 문제가 생겼는데, 내 생각에는 그에 대한 자명한 해결책들이 있었다.
_Equivalence class aliasing_은 강력한 도구이며 SoN의 핵심 부분이다. 내게는 V8이 이것을 처음부터 버렸고, 이후 몇 년에 걸쳐 그 부재로 인한 문제들을 감당해 온 것처럼 보인다.
동치 클래스 별칭(Equivalence class aliasing, ECA)은 강한 정적 타입 언어에서는 공짜, 진짜로 공짜로 얻어진다. 파서(예: JVM 바이트코드, Simple, C)에서 곧바로 나오며, 이후로 손댈 필요가 없다. 이를 통해 Java/Simple/C는 매우 희소하고 깔끔한 효과 체인을 가진다. 절대로 "너무 많다" 수준이 아니다.
JS는 _강한 정적 타입_이 아니므로, 여기에는 공학적 트레이드오프가 있다. 나는 V8(및 다른 JS 엔진들)이 _전문화(specialization)_를 공격적으로 사용해 코드 영역에서 강한 타입성을 되가져온다고 믿어왔다. 그런 영역에서는 다시 ECA가 그대로 잘 동작해야 한다.
동치 클래스 별칭은 SoN에서 직접적으로 표현된다. 그냥 보통의 노드와 에지일 뿐이다. 어디에서도 특별 취급이 없고, 일반 그래프 유지보수 함수가 다른 모든 것과 똑같이 그 노드와 에지를 조작한다. 별칭 가능성이 있는 두 노드는 직접 연결되고, 없는 노드는 연결되지 않으며, 따라서 다른 별칭 클래스에서 일어나는 일에 영향받을 수 없다. 이 두 가지 관찰(강한 타입에서 공짜로 얻어짐, 일반 노드/에지 유지보수)이 결합된 결과로, 이 형태의 효과 처리 방식은 내가 지금껏 작업한 어떤 컴파일러보다 구축과 유지가 훨씬 단순했고 사용 속도도 훨씬 빨랐다. 꽤 많은 컴파일러와 작업해 봤지만 그렇다. 자바에서 C2의 25년이 이것이 성능 면에서 매우 효과적이며 JIT에서도 충분히 빠르다는 것을 보여준다.
내 생각에 V8은 여기서 스스로에게 불리하게 작용했다.
정확성을 위한 가드 테스트: 필드의 null 체크나 배열의 범위 체크. 아마 JS(그리고 확실히 C2/Java)에서는 타입/전문화 검사도 포함된다. C2는 또한 가드 효과 노드에 제어 에지를 추가한다. 그런 다음 이들은 두 가지 일반적인 방식 중 하나로(제어 에지 제거) 최적화되어 사라진다:
(1) Lattice: null 및 타입 체크의 경우 Node Type이 null 여부나 서브클래싱 같은 것을 포함한다. Not-null 포인터는 타입에 근거해 not-null로 알려져 있고, 이에 대한 null 체크는 상수 폴딩된다. (Type들은 대칭적이고 완비적이며 경계(계급)가 있고, _meet_가 교환법칙과 결합법칙을 만족하는 _격자(lattice)_를 이룬다.)
가드 테스트 이후에는 타입을 올릴 수 있다(Cast를 사용하며, Cast는 가드 테스트에 묶이고, Cast는 격자에서 _join_을 수행한다. _meet_가 아니다). 그 가드를 필요로 하는 효과 노드는 제어 에지가 아니라 베이스 포인터에 대한 Cast를 집어든다. 나중에 Cast의 _join_이 무의미함을 증명하면, 예를 들어 _t.join(in(1)._type)==_t인 경우 Cast는 상수 폴딩되어 사라지고, 효과 노드는 보다 자유롭게 부유할 수 있다. 이 분석은(일반적인 c-prop의 일부로 제공됨) 자바의 캐스팅 필요성의 90% 초과를 제거한다.
(2) 다른 일반적인 테스트는 범위 체크로, 이는 처음에는 직접적인 제어 에지 의존성으로 시작한다. 이런 것들은 보통 사소하게 폴딩되지는 않는다. 모든 크기와 배열 인덱스가 상수인 경우라면 그럴 수 있지만, 대부분은 아니다. 그러면 C2는 _Range Check Elimination_을 실행한다. 자바의 안전한 배열을 위한 전용 패스로, 동적으로 거의 전부를 제거한다. 진지한 안전 언어 최적화에서는 똑같은 것을 기대한다.
그래프로 디버깅하지 마라. 이 글에서 보여주는 것 같은 일반 ASCII 덤프를 사용하라. 어쨌든 _내_가 그렇게 한다. C2를 시작했을 때는 빠르고 쉬운 그래프 레이아웃 같은 게 없었고, 그냥 "평범한 방법"으로 디버깅했다. 그래프는 직관을 주기에 좋지만 확장성은 떨어진다. 그렇긴 해도 디버깅용 그래프 시나리오를 더 잘 만드는 최근의 성과도 봤다(D3는 쓰지 마라. 사이클에 약하다. 파일로 덤프하고 파일 워처가 감지해 창을 새로고침하게 하라. 편집기 옆에 그래프 창을 계속 띄워 두라 등). 언젠가 다시 시도할 수도 있겠지만, 지금 내게는 ASCII 덤프가 최고다.
Click 학위 논문의 스케줄러는 반의존성(anti-dependencies)을 놓쳤다. C2, 그리고 읽기 쉬운 Simple 챕터 10에서 이를 수정했다. 알고리즘은 빠르고 충분히 단순하다. 예컨대 자연 루프 찾기 버전의 SCC보다 더 복잡하지 않다. 소스 코드는 Simple에서 구할 수 있다.
맞다. C2에서도 같은 해법을 썼다. min이나 max 같은 것을 단일한 순수 노드로 유지했다. 게임 후반의 어느 시점에 이것들을 전개(expand)했다. 내부 레지스터가 전혀 필요 없는 min 같은 사소한 것들은 RA 이후 인코딩 단계에서 전개했다. 더 복잡한 것들은 Global Code Motion이 나를 공식 CFG로 다시 데려온 직후에 전개했다.
어쨌든 이 문제(와 그 해법)는 내게… 사소하다. IR 선택 논쟁에서 큰 비중을 차지하지 않는다. 각 IR에는 고유의 문제가 있고, 모두 수십 가지의 이런 "수정"이 필요하다.
그렇다면 애쓰지 마라. 워크리스트를 써라! 완료까지 선형 시간이 보장되고, 빠르고 단순하다. 백에지는 필요하며 비용 대비 가치가 충분하다. 나는 C2를 백에지 없이 시작했는데, 몇 번의 패스로는 폐쇄(closure)를 얻지 못했다. 백에지를 추가하자 모든 것이 훨씬 빨라졌다. 에지 유지보수 코드가 그 일을 알아서 처리하므로 내가 신경 쓸 필요가 없고, 전부 캐시 상주 L1 히트다. 빠름, 빠름, 빠름.
백에지와 함께라면 공짜다. 기본적으로 백에지/참조 카운트가 0으로 떨어지면 재귀적으로 노드를 삭제한다. Simple에는 이를 위한 전용 코드가 대략 10줄 정도다.
컴파일러 작성자 여러분? 미안하지만, 이건 거의 믿기 어렵다. CFG를 편집하는 것은 도덕적으로 SoN을 편집하는 것과 같다. 뭐가 문제인가? min의 구체적 케이스에서는, CFG에서 전개할 위치를 고르는 것이 목표다… 즉, 위치를 골라야 하고, SoN에서는 보통 Global Code Motion 이후에 "위치"(고전적 CFG)가 다시 사용 가능해진다.
다시, 컴파일러 작성자 여러분? C2는 분명히 공격적인 루프 최적화를 많이 한다. 이는 표준 SCC를 돌리는 것에서 시작해 루프 헤더를 찾고, 루프에 의해 제한된 그래프 영역을 걷고, 추가 조작을 위한 루프 본문을 만들어낸다… 이런저런 과정이다. 요컨대, 나는 옛 방식(Olde Fashioned)인 SCC 실행으로 루프와 루프 트리를 구축한다.
컴파일은 빠르다. He-said-She-said. Neen-neener. 데이터는? 사실에 근거한 성능 논의는? 동등 조건 비교는? 없다고? 그렇다면 "컴파일 속도 대 코드 품질이 우리의 목표를 충족하지 못했다"는 건 어떤가?
똑같은(근거 부족한) 주장이다. 내가 C2를 만들 때는 캐시 친화성에 매우 집중했고, 모든 경쟁작(당시의 모든 AOT 컴파일러, GCC, LLVM) 대비 거대한 컴파일 속도 향상을 얻은 것을 보면 대체로 성공했다고 본다. C2의 컴파일은 "경쟁자들"보다 (캐시와 메모리 모두에서) 발자국이 훨씬 작다. 공격적인 인라이닝에도 불구하고, 대부분의 C2 컴파일은 L2에 쉽게 들어가고 거의 항상 L1에 들어간다. 이것을 제대로 하는 것이 중요하다. 따라서 V8이 빗나가게 한 다른 요인이 있었으리라 의심한다. 하지만… 내 쪽에서도 숫자는 없으니, 다시 neen-neener.
위 논의의 대부분은 V8의 삶을 더 어렵게, 그리고 더 느리게 만든 것들이며, 내가 절대 하지 않았을 일들이다. 한편으로, 나는 JS 컴파일러를 만들지는 않았으니 여기서도 사실 자료는 없다.
Cliff
