데이터 흐름 분석

MIR 관련 작업을 하다 보면 다양한 종류의 데이터 흐름 분석을 자주 접하게 됩니다. rustc는 데이터 흐름을 사용하여 초기화되지 않은 변수를 찾고, 제너레이터 yield 문을 가로질러 살아 있는 변수가 무엇인지 판별하며, 제어 흐름 그래프의 특정 지점에서 어떤 Place가 빌려졌는지 계산합니다. 데이터 흐름 분석은 현대 컴파일러의 기본 개념이며, 이 주제에 대한 지식은 기여를 희망하는 분들에게 도움이 될 것입니다.

그러나 이 문서는 데이터 흐름 분석에 대한 일반적인 입문서가 아닙니다. 이 문서는 rustc에서 이러한 분석을 정의하는 데 사용되는 프레임워크를 설명할 뿐입니다. 이 문서는 독자가 핵심 개념뿐만 아니라 “전달 함수(transfer function)”, “고정점(fixpoint)”, “격자(lattice)“와 같은 기본 용어에도 익숙하다고 가정합니다. 이러한 용어가 익숙하지 않거나 빠르게 복습하고 싶다면 Static Program Analysis를 참고하십시오. 무료로 제공되는 훌륭한 교재입니다. 시청각 학습을 선호하는 분들을 위해 이전에는 YouTube에 올라온 프랑크푸르트 괴테 대학교의 짧은 강의 시리즈를 추천했으나, 현재는 삭제되었습니다. 관련 경위는 이 PR을, 대체 강의는 이 댓글을 참고하십시오.

데이터 흐름 분석 정의하기

데이터 흐름 분석은 Analysis 트레이트로 정의됩니다. 이 트레이트는 데이터 흐름 상태의 타입 외에도 각 블록 진입 시점의 상태 초기값과 분석 방향(순방향 또는 역방향)을 정의합니다. 데이터 흐름 분석의 도메인은 잘 동작하는 join 연산자를 갖춘 격자(엄밀히 말하면 결합 반격자(join-semilattice))여야 합니다. 자세한 내용은 lattice 모듈과 JoinSemiLattice 트레이트의 문서를 참고하십시오.

전달 함수와 효과

rustc의 데이터 흐름 프레임워크에서는 기본 블록 내부의 각 문(및 종결자)이 자체 전달 함수를 정의할 수 있습니다. 간결하게 부르기 위해 이러한 개별 전달 함수를 “효과(effect)“라고 합니다. 각 효과는 데이터 흐름 순서에 따라 차례로 적용되며, 이들이 모여 기본 블록 전체의 전달 함수를 정의합니다. 일부 종결자의 특정 출력 간선에 대해 효과를 정의하는 것도 가능합니다(예: Call 종결자의 success 간선에 대한 apply_call_return_effect). 이들을 통틀어 “간선별 효과(per-edge effect)“라고 부릅니다.

“이전(Before)” 효과

문서를 주의 깊게 읽은 독자라면 각 문과 종결자에 실제로 두 가지 효과, 즉 “이전(before)” 효과와 접두사가 없는(또는 “주(primary)”) 효과가 있을 수 있다는 것을 알아차렸을 것입니다. “이전” 효과는 분석 방향과 관계없이 접두사가 없는 효과 바로 직전에 적용됩니다. 다시 말해, 역방향 분석도 순방향 분석과 마찬가지로 기본 블록의 전달 함수를 계산할 때 “이전” 효과를 적용한 다음 “주” 효과를 적용합니다.

대부분의 분석은 접두사가 없는 효과만 사용해야 합니다. 각 문에 여러 효과가 있으면 사용하는 쪽에서 어디를 살펴봐야 할지 알기 어렵기 때문입니다. 그러나 대입문의 우변 효과를 좌변과 별도로 고려해야 하는 경우처럼, 일부 상황에서는 “이전” 변형이 유용할 수 있습니다.

수렴

분석은 반드시 “고정점“으로 수렴해야 하며, 그렇지 않으면 영원히 실행됩니다. 고정점으로 수렴한다는 것은 “평형에 도달한다“는 것을 달리 표현한 것일 뿐입니다. 평형에 도달하려면 분석이 몇 가지 법칙을 따라야 합니다. 따라야 하는 법칙 중 하나는 바닥 값¹을 다른 어떤 값과 결합(join)하면 그 두 번째 값과 같아야 한다는 것입니다. 이를 수식으로 나타내면 다음과 같습니다.

bottom join x = x

또 다른 법칙은 분석에 다음을 만족하는 “top 값“이 있어야 한다는 것입니다.

top join x = top

top 값이 있으면 반격자(semilattice)의 높이가 유한함이 보장되며, 위의 법칙은 데이터 흐름 상태가 일단 top에 도달하면 더 이상 변하지 않음을 보장합니다(고정점은 top이 됩니다).

간단한 예제

이 절에서는 간단한 데이터 흐름 분석의 예제를 개략적으로 살펴봅니다. 알아야 할 내용을 모두 설명하지는 않지만, 이 페이지의 나머지 부분을 이해하는 데 도움이 되기를 바랍니다.

프로그램의 특정 지점에 이르기까지 mem::transmute가 호출되었을 수 있는지 알아내는 간단한 분석을 만든다고 가정해 봅시다. 분석 도메인은 지금까지 transmute가 호출되었는지를 기록하는 bool 하나뿐입니다. 기본적으로 transmute는 호출되지 않은 상태이므로 bottom 값은 false입니다. transmute가 호출되었음을 확인하는 즉시 분석이 끝나므로 top 값은 true입니다. join 연산자는 단순히 불리언 OR(||) 연산자입니다. AND가 아니라 OR를 사용하는 이유는 다음과 같은 경우 때문입니다.

#![allow(unused)]
fn main() {
unsafe fn example(some_cond: bool) {
let x = if some_cond {
    std::mem::transmute::<i32, u32>(0_i32) // transmute was called!
} else {
    1_u32 // transmute was not called
};

// Has transmute been called by this point? We conservatively approximate that
// as yes, and that is why we use the OR operator.
println!("x: {}", x);
}
}

데이터 흐름 분석 결과 살펴보기

분석을 구성한 뒤에는 iterate_to_fixpoint를 호출해야 합니다. 이 함수는 각 블록에 진입할 때의 고정점 데이터 흐름 상태를 담은 Results를 반환합니다. Results가 있으면 CFG의 어느 지점에서든 고정점 데이터 흐름 상태를 살펴볼 수 있습니다. 몇몇 위치(예: 각 Drop 종결자)의 상태만 필요하다면 ResultsCursor를 사용하십시오. 모든 위치의 상태가 필요하다면 ResultsVisitor가 더 효율적입니다.

                         Analysis
                            |
                            | iterate_to_fixpoint()
                            |
                         Results
                         /     \
 into_results_cursor(…) /       \  visit_with(…)
                       /         \
               ResultsCursor  ResultsVisitor

예를 들어 다음 코드는 ResultsVisitor를 사용합니다…

// Assuming `MyVisitor` implements `ResultsVisitor<FlowState = MyAnalysis::Domain>`...
let mut my_visitor = MyVisitor::new();

// inspect the fixpoint state for every location within every block in RPO.
let results = MyAnalysis::new()
    .iterate_to_fixpoint(tcx, body, None);
results.visit_with(body, &mut my_visitor);`

반면 이 코드는 ResultsCursor를 사용합니다.

let mut results = MyAnalysis::new()
    .iterate_to_fixpoint(tcx, body, None);
    .into_results_cursor(body);

// Inspect the fixpoint state immediately before each `Drop` terminator.
for (bb, block) in body.basic_blocks().iter_enumerated() {
    if let TerminatorKind::Drop { .. } = block.terminator().kind {
        results.seek_before_primary_effect(body.terminator_loc(bb));
        let state = results.get();
        println!("state before drop: {:#?}", state);
    }
}

Graphviz 다이어그램

데이터 흐름 분석 결과가 예상과 다를 때는 결과를 시각화해 보면 도움이 되는 경우가 많습니다. 시각화는 MIR 디버깅에서 설명하는 -Z dump-mir 플래그로 할 수 있습니다. -Z dump-mir=F -Z dump-mir-dataflow로 시작하십시오. 여기서 F는 “all“이거나 살펴보려는 MIR 본문의 이름입니다.

이 .dot 파일은 mir_dump 디렉터리에 저장되며, 파일 이름에 분석의 NAME(예: maybe_inits)이 들어갑니다. 각 시각화에는 각 블록의 진입 시점과 종료 시점의 전체 데이터 흐름 상태와 함께, 각 문장과 종결자에서 일어나는 모든 변화가 표시됩니다. 아래 예제를 참고하십시오.

A graphviz diagram for a dataflow analysis

bottom 값의 주된 용도는 초기 데이터 흐름 상태입니다. 분석이 시작되기 전에 각 기본 블록의 진입 상태는 bottom으로 초기화됩니다. ↩

Keyboard shortcuts

Rust 컴파일러 개발 가이드