Tree Borrows: Rust unsafe 코드의 별칭 규칙 모델

• Rust 컴파일러가 포인터 별칭 보장을 최적화에 활용하려면, unsafe 코드가 어디서 규칙을 어기는지 명확히 정의해야 함
• 기존 Stacked Borrows는 그 기준을 제시했지만, 실제 unsafe Rust 코드의 흔한 패턴과 최신 borrow checker 기능을 충분히 받아들이지 못함
• Tree Borrows는 Stacked Borrows의 핵심 구조를 스택에서 트리로 바꿔 더 많은 유효 패턴을 표현할 수 있게 함
• 가장 널리 쓰이는 Rust crate 30,000개 평가에서 Stacked Borrows보다 거부한 테스트 케이스가 54% 적음
• Rocq 증명으로 기존 최적화 대부분을 유지하면서 read-read 재정렬 같은 새 최적화도 가능함을 확인함

---

unsafe Rust에서 필요한 별칭 규칙

• Rust는 소유권 기반 타입 시스템으로 메모리 안전성과 데이터 레이스 방지 같은 강한 보장을 제공함
• 다만 unsafe 코드 영역에서는 안전성이 자동으로 보장되지 않으며, 프로그래머가 지켜야 할 규칙이 따로 필요함
• 컴파일러는 타입 시스템의 보장, 특히 포인터 별칭(aliasing) 관련 정보를 활용해 함수 내부 최적화를 강화하려 함
• 잘못 작성된 unsafe 코드는 이런 최적화를 깨뜨릴 수 있어, 어떤 코드를 “badly behaved”로 볼지 명확한 기준이 중요함
• 기존 연구인 Stacked Borrows는 이 기준을 정의했지만 한계가 있음
  • 실제 unsafe Rust 코드에서 흔한 여러 패턴을 거부함
  • 최근 도입된 Rust borrow checker의 고급 기능을 반영하지 못함

Tree Borrows의 접근과 평가 결과

• Tree Borrows는 Stacked Borrows의 중심 구조인 스택을 트리로 대체해 정의됨
• 이 구조 변경으로 기존 모델의 제한을 완화함
  • 가장 널리 쓰이는 Rust crate 30,000개 평가에서 Stacked Borrows보다 거부한 테스트 케이스가 54% 감소함
• Rocq 증명으로 최적화 관련 성질도 확인됨
  • Stacked Borrows가 허용하던 최적화 대부분을 유지함
  • 중요한 새 최적화인 read-read reorderings도 가능함
• Tree Borrows는 PLDI'25 Distinguished Paper Award를 받음
• 관련 자료
  • Full paper
  • Conference talk
  • Artifact
  • Source code

[GN⁺]

Hacker News 의견들

• Ralf Jung의 최근 글이 추가 맥락을 줌: https://www.ralfj.de/blog/2025/07/07/tree-borrows-paper.html
  보너스로, Rust 방언으로 Rust의 실행 의미론을 실행 가능한 형태로 정밀 명세하려는 Ralf Jung 그룹의 최근 발표도 있음: https://youtube.com/watch?v=yoeuW_dSe0o
• “컴파일러가 포인터 별칭(aliasing) 관련 타입 시스템 보장을 활용해 강력한 함수 내부 최적화를 열고 싶어 한다”는 말이 실제로 얼마나 맞는지 의문임
  Torvalds는 오래전부터 C의 엄격한 별칭 규칙이 득보다 실이 많다고 주장했고, 설득력 있게 들림. 예시는 여기: https://lore.kernel.org/all/CAHk-=wgq1DvgNVoodk7JKc6BuU1m9Un... 이 주제에 관심 있으면 전체 스레드도 읽을 만함
  Rust가 근본적으로 다른지는 제한된 경험상 그렇지 않아 보임. 적어도 unsafe가 끼면 더더욱 그럼
  • C의 엄격한 별칭 규칙은 형편없다는 데 동의하지만, Rust에 제안하는 규칙은 매우 다름
    컴파일러에는 더 유용하고, 프로그래머에게는 덜 부담스럽다고 봄. 또한 언어 안에서 빠져나갈 방법도 실제로 있음: 원시 포인터를 쓰면 됨. 그리고 코드를 검사할 도구도 있음
    결국 언어 설계의 모든 것처럼 절충이고, Rust에서는 이런 최적화에 대한 새로운 sweet spot을 찾았을지도 모른다고 봄. 맞는지는 시간이 알려줄 것임
  • Rust의 별칭 규칙은 C와 상당히 다름
    C에는 restrict라는 핵폭탄 같은 장치가 있는데, 경험상 clang과 gcc에서는 함수 인자에 붙였을 때만 뭔가 효과가 있었음. 타입 기반 별칭 분석은 일반적으로 쓰기 어렵고, int64_t 타입의 사본을 무한히 만들 수도 없으며 그러고 싶지도 않을 것임. 다른 타입으로 재해석하려면 memcpy를 강제하는 점도 성가심
    반면 Rust 참조는 수명·범위·가변성이 세밀하게 경계 지어져 있고, “물리적” 타입 자체에는 크게 신경 쓰지 않음. 그래서 같은 메모리를 &mut i32/&i32와 &mut i64/&i64로 재해석하며 전환하는 것도 가능함. unsafe 추상화가 동시에 겹치는 &mut 참조를 주지 않거나, 하나의 &mut을 겹치지 않는 여러 &mut으로 나누는 한, 평범한 안전 Rust 읽기·쓰기로 절반 값이나 여러 값을 읽고 쓸 수 있음
  • Linus가 컴파일러에 대해 말하는 건 어느 정도 걸러 들어야 함. 그는 운영체제 커널을 쓰지 컴파일러를 쓰는 사람이 아니고, 둘은 꽤 다른 영역임
    별칭 분석은 요즘 좋은 성능을 얻는 데 매우 중요함. 다만 가장 큰 이득은 가장 단순한 휴리스틱에서 나온다는 점도 기억해야 함. 예컨대 같은 SSA 값을 포인터로 쓰는 두 로드는 반드시 서로 별칭이라는 식임
    LLVM 관점에서는 BasicAA가 그런 역할임. “객체의 할당 지점을 추적할 수 있으면 별칭 질의를 확정적으로 풀고, 아니면 모른다”에 가까운 단순 휴리스틱 모음임
    진짜 질문은 기본적이고 명백한 검사를 넘어서는 별칭 분석의 가치임. 별칭 질의가 더 이상 사소하게 풀리지 않는 단계가 되면, 그 결과로 할 수 있는 일도 대체로 크게 줄어들고 거의 코드 이동 위험을 찾는 정도가 됨. 그 이득은 훨씬 작음
    해보고 싶은 실험 중 하나는 이론적으로 완벽한 별칭 분석이 줄 총 속도 향상을 측정하는 것임. 추측으로는 Linux 커널 같은 비-HPC 코드에서도 20% 정도일 것 같음
    [1] 여기에는 고품질 별칭 분석 없이는 시도하지 않을 데이터 배치 변환 같은 영웅적 최적화는 포함하지 않음. 실제로 그런 별칭 분석은 없다는 걸 이미 알고 있으니 그런 최적화도 시도하지 않을 것이고, 예상 속도 향상에 넣을 가치가 없다고 봄
  • C의 엄격한 별칭과 Rust의 별칭은 둘 다 별칭을 다루지만 서로 다른 것임. Rust는 꽤 명시적으로 C 방식을 채택하지 않았음
    C의 별칭은 타입만을 기반으로 하며, 그래서 다른 이름도 타입 기반 별칭 분석 또는 TBAA임
  • 더 철저한 분석을 보고 싶지만, 간단한 가늠법은 컴파일러에서 별칭 정보를 LLVM으로 전달하는 부분을 전부 빼고 성능이 어떻게 되는지 보는 것임
    noalias가 실행 시간 기준 약 5% 성능 향상에 기여한다는 주장을 찾았지만, 자료가 아주 오래된 건 분명함
    https://github.com/rust-lang/rust/issues/54878#issuecomment-...
• 언급된 Stacked Borrows는 2020년과 2018년에도 스레드가 있었음
  https://news.ycombinator.com/item?id=22281205
  https://news.ycombinator.com/item?id=17715399
• PLDI 발표도 볼 수 있음: https://www.youtube.com/watch?v=CJi_Fcs4bak
• 논문 예제 4에서 특정 Rust 코드가 거부된다고 한 주장을 직접 시험해 봤는데, 안정 컴파일러 버전에서는 그렇지 않아 보임
  &mut에서 *mut i32를 만들고, write(x) 대신 *x = 10을 하면 암묵적 2단계 빌림을 쓰지 않으니 컴파일러가 거부해야 한다는 설명처럼 보였지만 실제로는 통과함
  • Stacked Borrows는 Miri의 런타임 모델임. Miri에서 돌리면 *x = 10; 버전에서는 오류가 보고되고 write(x); 버전에서는 그렇지 않음
    오류는 “Undefined Behavior: attempting a write access using [...] but that tag does not exist in the borrow stack for this location” 형태임
    rustc 자체가 둘 중 어느 것도 거부할 이유는 없음. y는 *mut이고, 컴파일 시점 타입 시스템 관점에서는 x인 &mut과 빌림·수명 관계가 없기 때문임
  • 논문은 현재의 빌림 검사기 구현이 아니라 제안된 Tree Borrows 모델에서의 동작을 설명함
    현재 빌림 검사기는 더 제한적인 분석을 사용해서 원시 포인터와 가변 참조 사이의 이 특정 충돌을 감지하지 못함
• 훌륭한 작업임. 몇 년 전 Nevin 웹사이트에서 Tree Borrows 명세를 읽고 꽤 까다로운 문제를 우아하게 해결하는 방식에 크게 감탄했던 기억이 있음
  실제 경험상 [1] [2]에서도 Stacked Borrows에서는 불법이지만 합리적인 코드를 허용해 줬음
  [1] https://github.com/Voultapher/sort-research-rs/blob/main/wri... Miri 열
  [2] https://github.com/rust-lang/rust/blob/6b3ae3f6e45a33c2d95fa...
• 관심 있는 사람을 위한 Miri 구현은 여기 있음: https://github.com/rust-lang/miri/tree/master/src/borrow_tra...
• Rust나 미래의 프로그래밍 언어가 컴파일 속도, 실행 속도, 알고리즘 유연성 같은 특성이 다른 여러 빌림 검사기 구현을 허용하고, 프로젝트가 선택할 수 있게 발전할지 궁금함
  • Rust는 이미 빌림 검사기 구현 전환을 지원함
    범위 기반 빌림 검사기에서 비어휘적 수명 빌림 검사기로 옮겨 왔고, 다음 실험적 Polonius 구현도 옵션으로 있음. 다만 새 구현이 프로덕션 준비가 되면 예전 구현은 버려짐. 선택할 이유가 없기 때문임
    빌림 검사는 빠르고, 새 구현은 더 많은 올바른 프로그램을 엄격하게 받아들임
    또한 Rc와 RefCell 타입이 있어서 런타임 검사 비용을 치르고 더 큰 유연성을 얻을 수 있음
  • 이미 여러 접근이 있음. Rust가 쓰는 아핀 타입, 선형 타입, 효과, 의존 타입, 형식 증명 같은 방식들임
    모두 구현, 성능, 개발자 경험 면에서 비용과 능력이 다름
    그리고 Rust 외의 대부분이 실제로 지향하는 건 자동 자원 관리의 생산성임. 방식이 무엇이든 자동 자원 관리를 쓰고, 성능이 중요한 경로에만 위 타입 시스템 중 하나를 결합하는 식임
  • 실제로 원하는 건 바탕이 되는 분리 논리일 것임. 함수 전제조건을 정밀하게 명세하고, 함수 중간 조건을 증명하며, 최적화기가 그 “보조정리”들을 받아 명시된 불변식이 허용하는 한계까지 마음껏 최적화하는 구조임
    이 맥락에서 “Rust”는 “사람들이 보통 원하는 불변식”과 “그 보통 불변식을 가정하되 그 이상도 이하도 아닌 최적화 모음”에 불과하다고 볼 수 있음
  • Rust의 빌림 검사기는 컴파일 시간 비용이 꽤 작고 코드 생성에는 전혀 영향을 주지 않음
    컴파일 시간 대부분은 트레이트 해석, 단형화, LLVM 최적화 패스, 링크에 쓰임
  • 이해하기로는 빌림 검사기는 거짓 음성만 있고 거짓 양성은 없는 것 아닌가?
    어쩌면 바보 같은 질문일 수 있지만, 여러 구현을 병렬 스레드에서 돌리고 먼저 긍정 결과를 내는 쪽이 이기게 하면 안 되는지 궁금함
• 논문에 unsafe 코드가 같은 변수에 대한 여러 가변 참조를 포인터로 공존시킬 수 있다고 나오는데, 그건 정의되지 않은 동작 아닌가?
  포인터를 써서 같은 변수에 대한 여러 가변 참조를 동시에 존재시키는 건 정의되지 않은 동작임. 논문 의도를 오해한 게 아니라면 그렇게 보임
  • 이 작업의 핵심은 정의되지 않은 동작의 정확한 경계를 못 박는 것임
    위 코드는 Rust 컴파일러가 받아들이지만 규칙을 깨뜨림. 어떤 규칙을 깨뜨리는지가 문제임
    본질적으로 빌림 검사기가 받아들이는 것은 합법이고, unsafe는 불법이거나 정의되지 않은 동작도 표현할 수 있으며, 빌림 검사기가 확인할 수 있는 것보다 넓지만 여전히 합법이고 정의된 동작인 규칙 집합이 존재함
    이 연구의 목표는 그 규칙 집합을 정밀하게 명세하는 것임. 큰 윤곽은 “쓰기 가능한 포인터는 별칭이면 안 된다”에 가깝지만, 내부 포인터, 반복자 무효화, 나쁜 포인터를 만드는 것이 문제인지 사용하는 것이 문제인지 같은 세부사항은 매우 어려움
    이전 Stacked Borrows 논문은 더 단순했지만 더 제한적이어서, 현실의 unsafe 코드가 규칙을 자주 통과하지 못했음. Tree Borrows는 더 넓고 더 많은 코드를 허용하면서도 증명 가능하게 안전함
  • 맞지만, 정확히 어떤 규칙을 위반하는지가 문제임. 무엇이 그것을 정의되지 않은 동작이라고 말해 주는 정확한 정의인가?
    Tree Borrows는 바로 그런 정의를 제안하는 것임
    여기서 “코드가 이런 일을 할 수 있다”는 뜻은 “이 코드를 작성하고 컴파일하고 실행할 수 있으며, Tree Borrows 같은 것이 없으면 이 코드에 문제가 있다고 주장할 근거가 없다”는 의미임
    이미 이런 코드가 정의되지 않은 동작이라고 말해야 한다는 점, 즉 Tree Borrows 같은 것이 필요하다는 점은 받아들인 셈임. 논문의 이 부분은 왜 그런 것이 필요한지를 논증하는 대목임
  • 여기서 “할 수 있다”라는 말을 오해한 듯함. unsafe 코드에서는 실제로 그렇게 할 수 있음. 그리고 맞게도 그건 정의되지 않은 동작임
    https://play.rust-lang.org/?version=stable&mode=debug&editio...
  • 이어지는 문단 시작을 보면 의도가 가장 분명함
    Rust 컴파일러 개발자들이 별칭 최적화를 지원하고 싶어 하는 것이 분명하므로, 위와 같은 반례를 고려 대상에서 “배제”할 방법이 필요하다는 내용임
  • 바로 그게 핵심이라고 봄. 여러 가변 참조를 허용하지 않는 제약 같은 것을 위반하기가 너무 쉬움
    unsafe는 Rust의 수명 분석으로 코드의 유효성을 증명하기 어려운 경우를 위한 것이지만, 그보다 훨씬 더 많은 일을 하도록 남용될 수 있음
• 저자 중 한 명인 Neven Villani가 2010년 Fields Medal 수상자인 Cédric Villani의 아들이라는 걸 이제 알았음. 사과는 나무에서 멀리 떨어지지 않는다는 말이 딱 맞음