Souffle와 Rust의 Ascent를 사용해 기본 블록의 사용/정의/후속 관계로부터 live-in/live-out 집합을 Datalog 규칙으로 정의하고 계산하는 과정을 소개합니다. 간단한 예제와 코드로 Souffle와 Ascent의 사용법을 보여줍니다.
Linear scan register allocation on SSA을 게시한 뒤, Waleed Khan과 통화할 기회가 있었고 그는 내게 Datalog를 어떻게 쓰는지 보여줬다. 그는 라이브니스 분석을 Datalog 문제로 구현해보면 유용할 것 같다고 했다.
그 포스트에 있던 Wimmer2010의 CFG 예제부터 시작해서, 각 블록에서 어떤 변수가 live-out인지 수작업으로 스케치해 봤다. 예를 들어 B1에서는 R10, B2에서는 R12 … 같은 식이다.
Wimmer2010의 그래프가 돌아왔다! 우리는 phi 대신 블록 인자(block arguments)를 쓰고 있으니, B1(R10, R11)은 B1의 첫 명령 전에 R10과 R11을 정의한다는 뜻임을 기억하자.
그다음 라이브니스를 Datalog 관계로 정식화해 보았다.
보통(적어도 내 경우엔) 라이브니스는 두 관계로 정의한다: live-in과 live-out. live-out은 어떤 블록의 모든 후속 블록들이 “필요로 하는 것”이고, live-in은 그 블록의 “필요 요약”이다. 가짜 수학 표기법으로 쓰면 다음과 같다:
live-out(b) = union(live-in(s) for each successor s of b)
live-in(b) = (live-out(b) + used(b)) - defined(b)
여기서 각 구성 요소는 변수들의 집합을 의미한다:
우리는 레지스터 할당기 포스트에서 블록의 live-in 집합을 계산한 다음 live-out 집합을 사용했다. 그러니 오늘은 Datalog로 live-in과 live-out 집합을 둘 다 계산해 보자!
Datalog는 논리 프로그래밍 언어다. 아마 당신이 써본 다른 어떤 프로그래밍 언어와도 느낌이 다를 것이다… SQL을 빼면. SQL과 비슷하다고 느낄 수도 있는데, SQL에는 Datalog에는 없는 일정한 “순서”가 있다.
여기서는 Waleed가 언급하기도 했고 데이터베이스 수업에서 조금 배웠던 Souffle를 사용하겠다.
가장 먼저 할 일은 관계를 정의하는 것이다. Datalog에서 관계는 테이블(table)을 의미한다.
이번 경우, 라이브니스 정보를 계산하려면 각 블록이 무엇을 사용하고, 무엇을 정의하며, 어떤 후속 블록을 가지는지 알아야 한다.
Datalog에서 꼭 알아야 할 점 하나. 이건 일종의 “배열(벡터화) 프로그래밍의 반대”와 같다. 우리는 집합 전체를 바로 다루지 않고, 집합의 각 원소에 대한 사실(fact)을 표현한다.
예를 들어, “이 블록 B4는 [R10, R12, R16]을 사용한다”라고 말하지 않는다. 대신 “B4는 R10을 사용한다”, “B4는 R12를 사용한다”, “B4는 R16을 사용한다”라는 세 개의 별도 사실로 말한다. 각 관계를 데이터베이스 테이블로, 각 매개변수를 열 이름으로 생각하면 된다.
다음은 블록의 사용/정의 관계와 어떤 블록이 어떤 블록을 따른(successor)다는 관계다:
// liveness.dl
.decl block_use(block:symbol, var:symbol)
.decl block_def(block:symbol, var:symbol)
.decl block_succ(succ:symbol, pred:symbol)
여기서 symbol은 문자열을 의미한다.
인라인으로 사실을 적어 넣을 수도 있다. 예를 들어 다음은 “A가 R0와 R1을 정의하고 R0을 사용한다”는 뜻이다:
block_def("A", "R0").
block_def("A", "R1").
block_use("A", "R0").
사실을 TSV로 제공할 수도 있지만, 이 포맷은 수작업으로 만들기 너무 성가시고 예전에 Souffle에서 말없이 잘못된 답을 준 적이 있어서 이번 예제에서는 사용하지 않겠다.
여러분은 학습 삼아 이전 글의 use/def/successor 정보를 모두 Souffle에 수동으로 인코딩해도 되고, 아니면 이 덩어리를 파일에 그대로 복사해도 된다:
// liveness.dl
// ...
block_def("B1", "R10").
block_def("B1", "R11").
block_use("B1", "R11").
block_def("B2", "R12").
block_def("B2", "R13").
block_use("B2", "R13").
block_def("B3", "R14").
block_def("B3", "R15").
block_use("B3", "R12").
block_use("B3", "R13").
block_use("B3", "R14").
block_use("B3", "R15").
block_def("B4", "R16").
block_use("B4", "R16").
block_use("B4", "R10").
block_use("B4", "R12").
block_succ("B2", "B1").
block_succ("B3", "B2").
block_succ("B2", "B3").
block_succ("B4", "B2").
live-in과 live-out 관계도 use/def/succ 관계처럼 선언할 수 있다. Souffle가 결과를 보여주도록 .output으로 표시한다.
// liveness.dl
// ...
.decl live_out(block:symbol, var:symbol)
.output live_out
.decl live_in(block:symbol, var:symbol)
.output live_in
이제 관계를 정의할 시간이다. Souffle의 정의가 앞에서 본 정의와 매우 비슷하다는 걸 눈치챘을 텐데, 우연이 아니다. Datalog는 데이터플로우와 그래프 문제를 위해 만들어졌다.
live-out부터 시작하자:
// liveness.dl
// ...
live_out(b, v) :- block_succ(s, b), live_in(s, v).
왼쪽에서 오른쪽으로 읽으면 “블록 b의 live-out에 변수 v가 포함되려면, b의 후속 블록 s가 존재하고 v가 그 s의 live-in이어야 한다”가 된다. :-는 왼쪽을 오른쪽으로 정의한다는 뜻이다. block_succ와 live_in 사이의 쉼표는 논리적 “그리고”—즉 합성(conjunction)—이다.
그렇다면 합집합(union)은 어디에 있을까? 아까 배열 프로그래밍 얘기를 기억하는가? 우리는 지금 집합 단위로 사고하지 않는다. 프로그램 변수 하나씩 생각한다. Souffle가 우리 관계들을 실행해 가면서 live_out 테이블은 점진적으로 쌓인다.
또 이 스타일로 프로그래밍하는 게 조금 낯설 수 있는데, s는 매개변수나 변수처럼 어디에도 “텍스트로” 정의되어 있지 않다. s는 일종의 연결자, 바인더, 외래 키 같은 것으로 생각해야 한다. 자리 표시자다. (이걸 더 잘 설명하지 못해 미안하다.)
이제 live-in을 정의하자. 표면적으로는 더 복잡해 보이지만, 그건 Souffle의 문법 선택 때문이라고 생각한다.
// liveness.dl
// ...
live_in(b, v) :- (live_out(b, v) ; block_use(b, v)), !block_def(b, v).
읽으면 “변수 v가 블록 b의 live-in이려면, v가 b의 live-out이거나 b에서 사용되어야 하고, 그리고 b에서 정의되면 안 된다”가 된다. 세미콜론은 논리적 “또는”(disjunction), 느낌표는 부정(negation)—즉 “아니다”—이다.
이 관계들은 끝없이 상호 재귀하는 것처럼 보이지만, 우리는 정확히 데이터를 대상으로 함수를 실행하는 게 아니다. 규칙—관계—의 정의를 선언적으로 표현하는 것이다. live_in의 본문에 있는 block_use(b, v)는 함수를 호출하는 게 아니라 질의하는 것이다—행 (b, v)가 block_use 테이블에 있나? Datalog는 포화(saturation)될 때까지 테이블을 구축한다.
이제 Souffle를 실행해 보자! -D-로 표준 출력으로 덤프하게 하고, 아니면 -D.를 지정해 각 출력 관계를 현재 디렉터리의 개별 파일로 덤프하게 할 수도 있다.
$ souffle -D- liveness.dl
---------------
live_in
block var
===============
B2 R10
B3 R10
B3 R12
B3 R13
B4 R10
B4 R12
===============
---------------
live_out
block var
===============
B1 R10
B2 R10
B2 R12
B2 R13
B3 R10
===============
$
멋지다. 보기 좋은 표를 두 줄의 코드로 얻었다! 요점을 강조하려고 이전 글의 Ruby 코드와 비교해 보자:
def analyze_liveness
order = post_order
gen, kill = compute_initial_liveness_sets(order)
live_in = Hash.new 0
changed = true
while changed
changed = false
for block in order
block_live = block.successors.map { |succ| live_in[succ] }.reduce(0, :|)
block_live |= gen[block]
block_live &= ~kill[block]
if live_in[block] != block_live
changed = true
live_in[block] = block_live
end
end
end
live_in
end
이는 고정점까지 반복하는 부분을 데이터플로우 분석의 핵심—식—과 분리했기 때문이다. 데이터 이동은 Datalog에게 맡기고, 우리는 규칙—오직 규칙—정의에만 집중할 수 있다.
아마 그래서 시간이 흐르면 많은 정적 분석과 컴파일러 도구들이 (부분적인) Datalog 엔진을 내장 형태로 갖추게 되는 것 같다. 이를 Scholz의 열 번째 규칙이라고 부르자.
Souffle는 C++로 컴파일하는 기능도 있는데, 이건 두 가지 장점을 준다:
이 API는 써본 적이 없다.
그때 Waleed가 문득 임베디드 Rust Datalog로 Ascent가 있다고 들었다고 언급했다.
Ascent 웹사이트 첫 페이지는 “Rust 프로그램에서 Datalog를 쓸 수 있으면 좋겠다”고 생각하고 찾아온 사람들에게 정말 매력적이다. 시작부터 proc 매크로로 그럴듯한 Datalog 문법을 제공한다.
예를 들어, Souffle의 정석적인 경로(path) 예제는 다음과 같다:
.decl edge(x:number, y:number)
.decl path(x:number, y:number)
path(x, y) :- edge(x, y).
path(x, y) :- path(x, z), edge(z, y).
Ascent에서는 이렇게 쓴다:
ascent! {
relation edge(i32, i32);
relation path(i32, i32);
path(x, y) <-- edge(x, y);
path(x, z) <-- edge(x, y), path(y, z);
}
훌륭하다.
Souffle의 라이브니스를 Rust로 그대로 옮길 수 있을지 확신은 없었는데, 해보니 정말 깨끗하게 됐다! 게다가 앞의 예제가 i32만 쓰는 것과 달리, 자체 데이터 타입도 사용할 수 있다.
use ascent::ascent;
#[derive(Clone, PartialEq, Eq, Hash, Copy)]
struct BlockId(i32);
impl std::fmt::Debug for BlockId {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "B{}", self.0)
}
}
#[derive(Clone, PartialEq, Eq, Hash, Copy)]
struct VarId(i32);
impl std::fmt::Debug for VarId {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "R{}", self.0)
}
}
ascent! {
relation block_use(BlockId, VarId);
relation block_def(BlockId, VarId);
relation block_succ(BlockId, BlockId); // (succ, pred)
relation live_out(BlockId, VarId);
relation live_in(BlockId, VarId);
live_out(b, v) <-- block_succ(s, b), live_in(s, v);
live_in(b, v) <-- (live_out(b, v) | block_use(b, v)), !block_def(b, v);
}
fn main() {
// ...
}
Datalog에서 했던 것처럼 input이나 output 애너테이션이 없는 것을 볼 수 있다. 이건 기존 프로그램에 임베드하도록 설계되었기 때문이고, 그런 프로그램은 디스크를 직접 다루고 싶지 않거나(혹은 자기 포맷으로 읽고/쓰고 싶기) 때문이다.
Ascent는 몇 개의 벡터 데이터를 넘겨받고, 실행이 끝난 뒤 몇 개의 벡터 데이터를 읽게 해준다.
// ...
fn main() {
let mut prog = AscentProgram::default();
let b1 = BlockId(1);
let b2 = BlockId(2);
let b3 = BlockId(3);
let b4 = BlockId(4);
let r10 = VarId(10);
let r11 = VarId(11);
let r12 = VarId(12);
let r13 = VarId(13);
let r14 = VarId(14);
let r15 = VarId(15);
let r16 = VarId(16);
prog.block_def = vec![
(b1, r10),
(b1, r11),
(b2, r12),
(b2, r13),
(b3, r14),
(b3, r15),
(b4, r16),
];
prog.block_succ = vec![
(b2, b1),
(b3, b2),
(b2, b3),
(b4, b2),
];
prog.block_use = vec![
(b1, r11),
(b2, r13),
(b3, r12),
(b3, r13),
(b3, r14),
(b3, r15),
(b4, r10),
(b4, r12),
(b4, r16),
];
prog.run();
println!("live out: {:?}", prog.live_out);
println!("live in: {:?}", prog.live_in);
}
그다음 cargo add ascent와 cargo run만 실행하면 된다—둘 다 문제없이 잘 동작했고, 결과는 다음과 같다.
$ cargo run
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.02s
Running `target/debug/liveness`
live out: [(B2, R12), (B2, R13), (B2, R10), (B1, R10), (B3, R10)]
live in: [(B3, R12), (B3, R13), (B4, R10), (B4, R12), (B2, R10), (B3, R10)]
$
화려한 표는 아니지만, 내 프로그램과 거의 동일한 결과가 나와서 기분이 좋다.
이건 Souffle를 C++에 임베드하고 C++을 호출하는 것과 비슷하다. 한 가지 차이는 Souffle 프로세스는 두 단계라는 점이다. 빌드 시스템이 약간 복잡해진다. 하지만 이 글은 Datalog 비교 글이 아니다!
선형 스캔 전체를 이런 식으로 모델링할 수 있을까? 아마도. 나는 이런 것들에 아직 초보다.
Ascent는 격자(lattice)도 지원하는 듯하니, 멋진 도메인에서 추상 해석을 하는 데도 쓸 수 있을 것 같다.
Maxime Chevalier-Boisvert와 나는 Rust로 loupe라는 프로시저 간 타입 분석(interprocedural type analysis)을 프로토타이핑했다. 거기서는 고정점까지 반복하는 엔진을 우리가 직접 만들어야 했는데, 만만치 않았다. Ascent 위에 비슷한 것을 만든다면 어떤 모습일지 궁금하다.
Frank McSherry의 datatoad도 한번 살펴보고 싶다.
오늘은 여기까지. Datalog 스니펫 몇 개였다. 즐거운 해킹.