23장: 최적화
새 파일
src/rep.rssrc/reach.rssrc/dump.rs변경된 파일
src/erase.rssrc/llvm/values.rssrc/llvm/primitives.rssrc/llvm/control.rssrc/llvm/mod.rssrc/anf.rssrc/anf_simplify.rssrc/anf_lint.rssrc/closure.rssrc/flat.rssrc/flat_lint.rssrc/primitives.rsrt/src/primitives.rsrt/src/abi.rssrc/main.rssrc/repl.rssrc/jit.rssrc/lib.rsrt/src/lib.rs
동기
올바른 답을 얻는 것은 최적화기에게 좋은 출발점입니다. 우리는 최적화기가 같은 계산을 두 번 하거나 산술 명령어 사이사이마다 새 박스를 할당하는 일도 피하기를 바랍니다. 더 빨라 보이는 식이 알고 보면 같은 결과를 얻는 꽤 비싼 방법일 수도 있습니다.
우리는 몇 가지 목표가 분명한 개선을 하고, 그 개선이 실제로 무엇을 바꾸는지 살펴보겠습니다. 트레이스와 머신 스텝은 중복되거나 순서가 바뀐 작업을 잡아내는 데 도움이 됩니다. 의존성 그래프는 어떤 전역 정의가 여전히 필요한지 알려 줍니다. 타입 정보는 코드 생성이 중간값을 반복해서 박싱하는 대신 네이티브 산술을 사용할 수 있는 때를 알려 줍니다.
이것들은 작은 최적화이지만, 더 큰 최적화기도 답해야 하는 질문들을 드러냅니다. 이 식에 대해 우리는 무엇을 알고 있습니까? 이 재작성은 무엇을 절약합니까? 그리고 평가 순서는 어떻게 됩니까?
현재의 언어
새로 추가된 소스 함수는 trace :: String -> a -> a 하나뿐입니다. 이 함수는 첫 번째 인자와 개행 문자를 stderr에 쓴 다음, 두 번째 인자를 그대로 반환합니다. 인자는 여전히 엄격하게 평가됩니다. 두 번째 인자를 평가하는 도중 발생한 오류는 트레이스가 출력되기 전에 일어납니다. trace는 진단 기능이며, 일반적인 프로그램 효과를 위한 IO의 대안이 아닙니다.
-- stderr: exact
f x y = x + y
main = print (f (trace "left" 20) (trace "right" 22))
이 코드는 stderr에 left와 그 뒤에 right를 출력하고, stdout에 42를 출력합니다. 이제 어떤 호출을 다른 인자 너머로 옮기면 그 변화가 눈에 보이게 됩니다. 런타임은 트레이스를 쓰기 전에 stdout을 플러시하여 앞선 출력의 순서를 보존합니다.
이론
작업 보존하기
엄격한 언어에서 let x = f y in x + x는 f y를 한 번 평가합니다. x의 두 출현 모두를 f y로 치환하면 그것을 두 번 평가하게 됩니다. 이는 비용을 바꾸고 트레이스를 반복할 수도 있습니다. 실패하는 식 역시 관찰 가능합니다. 사용되지 않는 0으로 나누기도 그냥 사라질 수는 없습니다.
우리의 단순화기는 아톰을 읽는 데 아무 작업도 들지 않으므로 아톰을 치환할 수 있습니다. 사용되지 않는 전역(total) 계산은 제거할 수 있습니다. 즉시 적용되는 람다 본문을 유일한 호출 지점으로 옮길 수 있으며, 이때 이미 평가된 인자는 보존합니다. 두 번 호출되는 람다에는 그 규칙을 사용할 수 없습니다. 이러한 제약 덕분에 전역적인 비용 분석 없이도 이 작은 변환을 이해할 수 있습니다 (Appel 1992).
ANF 머신에 단순화를 켰을 때와 껐을 때의 스텝 수를 세도록 요청할 수 있습니다. 결과, 오류, 트레이스는 일치해야 하며, 단순화된 프로그램이 더 많은 스텝을 거쳐서는 안 됩니다. 이를 통해 실수로 작업을 중복시키는 재작성을 잡아내는 유용한 방법을 얻게 됩니다. 이것이 실제 소요 시간의 단축을 증명하지는 않지만, 특정 CPU에 의존하지 않고 실제로 측정할 수 있는 주장을 검증해 줍니다.
도달 가능한 전역 정의 유지하기
전역 참조는 의존성 그래프의 간선이 됩니다. main에서 시작하여 작업 목록(worklist)이 이 간선들을 따라가며, 새로 도달한 전역 정의마다 선행자를 하나씩 기록해 둡니다. 이는 9장의 의존성 분석과 비슷하지만, 다른 질문에 답합니다. 이 실행에 필요할 수 있는 정의는 무엇입니까?
엄격한 초기화는 루트를 추가합니다. 사용되지 않는 초기화식도 main보다 먼저 트레이스를 출력하거나, 실패하거나, 발산할 수 있습니다. 우리는 지역 분류기가 무해함을 입증할 수 없는 초기화식은 모두 유지합니다. 호출과 제어 흐름 초기화식은 계속 루트로 남습니다. 클로저를 할당해도 그 본문은 실행되지 않으므로, 사용되지 않는 함수는 제거할 수 있습니다. 할당 실패는 소스 비용 모델의 범위 밖입니다.
살아남은 전역 정의들은 원래의 의존성 순서를 그대로 유지합니다. REPL에서는 이후 입력이 보이는 바인딩 중 어느 것이든 참조할 수 있으므로, 보이는 모든 바인딩이 루트가 됩니다. 증거(witness) 덤프는 유지된 각 바인딩에 대해 그것을 발견한 간선을 하나씩 보여 주므로, 가지치기 결정을 직접 들여다볼 수 있습니다.
타입 증거는 유지하고, 저장 방식은 지역적으로 선택하기
소거된 식은 더 이상 System F 타입을 지니지 않지만, 컴파일러는 그 타입이 확립한 작은 사실 하나를 유지할 수 있습니다.
#![allow(unused)]
fn main() {
impl std::fmt::Display for Rep {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(match self {
Self::Int => "Int",
Self::Double => "Double",
Self::Word => "Word",
})
}
}
use crate::{
anf::{Anf, Atom, Rhs, Var},
core,
names::Id,
};
use std::collections::BTreeMap;
pub type Table = BTreeMap<Id, Rep>;
/// Missing evidence is an internal error, never an invitation to infer a storage tag.
pub fn get(table: &Table, id: &Id) -> Result<Rep, String> {
table
.get(id)
.copied()
.ok_or_else(|| format!("missing representation evidence for {id}"))
}
pub fn atom(table: &Table, a: &Atom) -> Result<Rep, String> {
match a {
Atom::Var(v) | Atom::Global(v) => get(table, v),
Atom::Lit(l) => Ok(crate::erase::literal_rep(l)),
}
}
/// Numeric operands are checked against the primitive's declared signature.
pub fn primitive(
table: &Table,
op: crate::ast::Op,
args: &[Atom],
result: &Var,
metadata: &core::Program,
) -> Result<(), String> {
use crate::primitives::Prim;
let generic = matches!(
op,
crate::ast::Op::Runtime(Prim::Trace | Prim::Error | Prim::Exit)
);
let types = if generic {
vec![core::Type::Var(0)]
} else {
vec![]
};
let (mut ty, _) = crate::primitives::core_signature(
op,
&types,
&metadata.data_types,
)?;
for arg in args {
let core::Type::Arrow(a, b) = ty else {
return Err("primitive arity evidence".into());
};
if !matches!(a.as_ref(), core::Type::Var(_))
&& atom(table, arg)? != crate::erase::representation(&a)
{
return Err(format!(
"contradictory operand evidence for {}: {:?}",
op.text(),
arg
));
}
ty = *b;
}
let expected = if matches!(op, crate::ast::Op::Runtime(Prim::Trace)) {
atom(table, &args[1])?
} else if matches!(ty, core::Type::Var(_)) {
get(table, result)?
} else {
crate::erase::representation(&ty)
};
if get(table, result)? != expected {
return Err(format!("contradictory result evidence for {result}"));
}
Ok(())
}
/// Copy evidence to the beta continuation's fresh result. No type classification occurs here.
pub fn beta_results(program: &mut crate::anf::Program) {
let mut todo = program
.globals
.iter()
.map(|(_, b)| b.as_ref())
.collect::<Vec<_>>();
let mut joins = BTreeMap::new();
let mut pending = vec![];
while let Some(b) = todo.pop() {
match b {
Anf::Let(v, r, rest) => {
if !program.reps.contains_key(v) {
let Anf::Jump(j, _) = rest.as_ref() else {
panic!("beta result continuation")
};
pending.push((v.clone(), j.clone()));
}
if let Rhs::Lambda(l) = r {
todo.push(&l.body);
}
todo.push(rest);
}
Anf::LetRec(bs, r) => {
todo.push(r);
for (_, l) in bs {
todo.push(&l.body);
}
}
Anf::Join(j, ps, b, r) => {
if ps.len() == 1 {
joins.insert(j.clone(), program.reps[&ps[0]]);
}
todo.push(b);
todo.push(r);
}
Anf::Case(_, alts) => {
for (_, _, b) in alts {
todo.push(b);
}
}
_ => {}
}
}
for (v, j) in pending {
program.reps.insert(v, joins[&j]);
}
}
pub fn lint_anf(program: &crate::anf::Program) -> Result<(), String> {
let mut todo = vec![];
for (v, b) in &program.globals {
get(&program.reps, v)?;
todo.push(b.as_ref());
}
while let Some(b) = todo.pop() {
match b {
Anf::Let(v, r, rest) => {
get(&program.reps, v)?;
match r {
Rhs::Prim(p, args, _) => primitive(
&program.reps,
*p,
args,
v,
&program.metadata,
)?,
Rhs::Lambda(l) => todo.push(&l.body),
_ => {}
}
todo.push(rest);
}
Anf::LetRec(bs, r) => {
todo.push(r);
for (_, l) in bs {
todo.push(&l.body);
}
}
Anf::Join(_, _, b, r) => {
todo.push(b);
todo.push(r);
}
Anf::Case(_, alts) => {
for (_, _, b) in alts {
todo.push(b);
}
}
_ => {}
}
}
Ok(())
}
pub fn lint_flat(program: &crate::flat::Program) -> Result<(), String> {
use crate::flat::{Flat, Rhs};
let mut todo = program
.funcs
.iter()
.map(|f| f.body.as_ref())
.collect::<Vec<_>>();
for g in &program.globals {
get(&program.reps, &g.name)?;
todo.push(g.body.as_ref());
}
while let Some(b) = todo.pop() {
match b {
Flat::Let(v, r, rest) => {
get(&program.reps, v)?;
if let Rhs::Prim(p, args, _) = r {
primitive(
&program.reps,
*p,
args,
v,
&program.metadata,
)?;
}
todo.push(rest);
}
Flat::Join(_, _, b, r) => {
todo.push(b);
todo.push(r);
}
Flat::Case(_, alts) => {
for (_, _, b) in alts {
todo.push(b);
}
}
_ => {}
}
}
Ok(())
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Rep {
Int,
Double,
Word,
}
}Int와 Double은 수치 타입임을 확립합니다. Word는 타입 변수를 포함한 나머지 모두를 포괄합니다. 이것은 증거이지 저장 레이아웃이 아닙니다. 호출이 반환한 Int는 여전히 태그가 붙은 워드로 도착합니다. 그것을 언제 레지스터로 디코딩할지는 코드 생성이 결정합니다. 호출, 반환, 필드, 캡처, 전역 정의, 조인 매개변수는 20장의 균일한 ABI를 그대로 유지합니다 (Leroy 1990).
정수 레지스터 연산에는 한 단계가 더 필요합니다. LLVM의 i64는 64비트이지만, Fun의 부호 있는 정수는 63비트입니다. 을 자기 자신과 더하면 가 나와야 합니다. 정규화를 하지 않으면 뒤따르는 비교는 양수를 보게 되고, 2로 나누면 부호가 잘못된 결과가 나옵니다. 산술 연산 후에 우리는 왼쪽으로 한 번 시프트한 다음, 오른쪽으로 한 번 산술 시프트합니다. 이렇게 하면 62번 비트가 부호 확장되어, 이후에 사용되기 전에 Fun의 범위가 복원됩니다. 반면 를 자기 자신과 더하면 음수가 아니라 0으로 순환합니다.
Double 산술은 중간 결과를 부동소수점 레지스터에 둘 수 있습니다. 우리의 호출 규약은 워드를 전달하므로, 결과를 다른 함수에 넘길 때는 여전히 박스가 필요합니다. 그래서 기본 연산으로 된 Double 누적 루프는 꼬리 호출 지점에서 반복마다 한 번씩 누산기를 여전히 박싱합니다. 개선된 점은 그 과정에서 생기는 산술 중간값을 하나하나 박싱하지는 않는다는 것입니다.
할당 횟수를 세어 이 차이를 확인하겠습니다. 오버로드된 소스 연산자는 여전히 사전 호출을 할 수 있으므로, 이런 직접적인 원시 루프를 만들어 내지 못할 수도 있습니다. 그런 사전을 특수화하는 것은 별개의 최적화 기회입니다.
구현
트레이스 동작은 공유 런타임이 담당합니다. 두 인터프리터와 네이티브 ABI가 모두 이를 사용하므로, 임의의 클로저조차 반환값이 될 수 있습니다:
#![allow(unused)]
fn main() {
use crate::layout::normalize;
#[derive(Clone, Debug, PartialEq)]
/// Only primitive input/output types: arbitrary algebraic values stay in each engine.
pub enum Value {
Int(i64),
Double(f64),
Char(char),
String(String),
Bool(bool),
Chars(Vec<char>),
MaybeInt(Option<i64>),
Unit,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Failure {
Runtime(String),
Exit(i32),
}
impl From<String> for Failure {
fn from(s: String) -> Self {
Self::Runtime(s)
}
}
impl From<&str> for Failure {
fn from(s: &str) -> Self {
Self::Runtime(s.into())
}
}
impl std::fmt::Display for Failure {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Runtime(s) => f.write_str(s),
Self::Exit(n) => write!(f, "exit {n}"),
}
}
}
/// Optional surrounding whitespace and sign; decimal digits only, within signed 63 bits.
pub fn read_int(source: &str) -> Option<i64> {
let s = source.trim();
let digits = s.strip_prefix(['+', '-']).unwrap_or(s);
if digits.is_empty() || !digits.bytes().all(|b| b.is_ascii_digit()) {
return None;
}
s.parse().ok().filter(|n| {
(crate::layout::INT_MIN..=crate::layout::INT_MAX).contains(n)
})
}
macro_rules! primitives {($($variant:ident => $name:literal),* $(,)?)=>{
#[derive(Clone,Copy,Debug,PartialEq,Eq)] pub enum Prim {$($variant),*}
pub const ALL:&[Prim]=&[$(Prim::$variant),*];
impl Prim {pub fn name(self)->&'static str {match self {$(Self::$variant=>$name),*}}}
};}
primitives! {
IntAdd=>"prim_intAdd",IntSub=>"prim_intSub",IntMul=>"prim_intMul",IntNeg=>"prim_intNeg",IntQuot=>"prim_intQuot",IntRem=>"prim_intRem",IntDiv=>"prim_intDiv",IntMod=>"prim_intMod",IntEq=>"prim_intEq",IntLt=>"prim_intLt",IntLe=>"prim_intLe",
DblAdd=>"prim_dblAdd",DblSub=>"prim_dblSub",DblMul=>"prim_dblMul",DblDiv=>"prim_dblDiv",DblNeg=>"prim_dblNeg",DblSqrt=>"prim_dblSqrt",DblExp=>"prim_dblExp",DblLog=>"prim_dblLog",DblSin=>"prim_dblSin",DblCos=>"prim_dblCos",DblPow=>"prim_dblPow",DblEq=>"prim_dblEq",DblLt=>"prim_dblLt",DblLe=>"prim_dblLe",
IntToDbl=>"prim_intToDbl",DblFloor=>"prim_dblFloor",DblRound=>"prim_dblRound",DblTruncate=>"prim_dblTruncate",ChrOrd=>"prim_chrOrd",ChrChr=>"prim_chrChr",ChrEq=>"prim_chrEq",ChrLt=>"prim_chrLt",
StrAppend=>"prim_strAppend",StrLength=>"prim_strLength",StrEq=>"prim_strEq",StrCompare=>"prim_strCompare",StrUnpack=>"prim_strUnpack",StrPack=>"prim_strPack",
ShowInt=>"prim_showInt",ShowDouble=>"prim_showDouble",ShowChar=>"prim_showChar",ShowString=>"prim_showString",ReadInt=>"prim_readInt",Error=>"prim_error",PutStr=>"prim_putStr",GetLine=>"prim_getLine",Exit=>"prim_exit",Trace=>"prim_trace"
}
/// Formatting starts from Rust's shortest round-trip digits, then normalizes notation.
pub fn show_double(n: f64) -> String {
if n.is_nan() {
return "NaN".into();
}
if n.is_infinite() {
return if n.is_sign_negative() {
"-Infinity"
} else {
"Infinity"
}
.into();
}
if n == 0.0 {
return if n.is_sign_negative() { "-0.0" } else { "0.0" }.into();
}
let raw = format!("{:?}", n.abs());
let (mantissa, exponent) = raw
.split_once('e')
.map_or((raw.as_str(), 0), |(a, b)| (a, b.parse::<i32>().unwrap()));
let point =
mantissa.find('.').unwrap_or(mantissa.len()) as i32 + exponent;
let digits = mantissa.replace('.', "");
let leading = digits.len() - digits.trim_start_matches('0').len();
let digits = digits.trim_start_matches('0').trim_end_matches('0');
let point = point - leading as i32;
let body = if (1e-4..1e16).contains(&n.abs()) {
if point <= 0 {
format!("0.{}{digits}", "0".repeat((-point) as usize))
} else if point as usize >= digits.len() {
format!(
"{digits}{}.0",
"0".repeat(point as usize - digits.len())
)
} else {
format!(
"{}.{}",
&digits[..point as usize],
&digits[point as usize..]
)
}
} else {
format!(
"{}.{}e{:+}",
&digits[..1],
if digits.len() == 1 { "0" } else { &digits[1..] },
point - 1
)
};
if n.is_sign_negative() {
format!("-{body}")
} else {
body
}
}
/// Quote Unicode text using Fun escapes.
pub fn quote(text: &str, delimiter: char) -> String {
let mut result = String::from(delimiter);
for c in text.chars() {
match c {
'\n' => result.push_str("\\n"),
'\t' => result.push_str("\\t"),
'\0' => result.push_str("\\0"),
'\\' => result.push_str("\\\\"),
c if c == delimiter => {
result.push('\\');
result.push(c);
}
c if c.is_control() => {
result.push_str(&format!("\\u{{{:x}}}", c as u32))
}
c => result.push(c),
}
}
result.push(delimiter);
result
}
/// Execute a checked primitive, returning errors without terminating the host.
pub fn evaluate(p: Prim, args: &[Value]) -> Result<Value, Failure> {
use Prim::*;
let int = |i| match args[i] {
Value::Int(n) => n,
_ => unreachable!("typed primitive"),
};
let dbl = |i| match args[i] {
Value::Double(n) => n,
_ => unreachable!("typed primitive"),
};
let chr = |i| match args[i] {
Value::Char(c) => c,
_ => unreachable!("typed primitive"),
};
let string = |i| match &args[i] {
Value::String(s) => s.as_str(),
_ => unreachable!("typed primitive"),
};
let integer = |n| Value::Int(normalize(n));
let double = |n: f64| Value::Double(n);
let text = |s| Value::String(s);
let boolean = Value::Bool;
Ok(match p {
IntAdd => integer(int(0).wrapping_add(int(1))),
IntSub => integer(int(0).wrapping_sub(int(1))),
IntMul => integer(int(0).wrapping_mul(int(1))),
IntNeg => integer(-int(0)),
IntQuot | IntRem | IntDiv | IntMod => {
let (a, b) = (int(0), int(1));
if b == 0 {
return Err("divide by zero".into());
}
let (mut q, mut r) = (a / b, a % b);
if matches!(p, IntDiv | IntMod) && r != 0 && (r < 0) != (b < 0)
{
q -= 1;
r += b;
}
integer(if matches!(p, IntQuot | IntDiv) { q } else { r })
}
IntEq => boolean(int(0) == int(1)),
IntLt => boolean(int(0) < int(1)),
IntLe => boolean(int(0) <= int(1)),
DblAdd => double(dbl(0) + dbl(1)),
DblSub => double(dbl(0) - dbl(1)),
DblMul => double(dbl(0) * dbl(1)),
DblDiv => double(dbl(0) / dbl(1)),
DblPow => double(dbl(0).powf(dbl(1))),
DblNeg => double(-dbl(0)),
DblSqrt => double(dbl(0).sqrt()),
DblExp => double(dbl(0).exp()),
DblLog => double(dbl(0).ln()),
DblSin => double(dbl(0).sin()),
DblCos => double(dbl(0).cos()),
DblEq => boolean(dbl(0) == dbl(1)),
DblLt => boolean(dbl(0) < dbl(1)),
DblLe => boolean(dbl(0) <= dbl(1)),
IntToDbl => double(int(0) as f64),
DblFloor | DblRound | DblTruncate => {
let n = match p {
DblFloor => dbl(0).floor(),
DblRound => dbl(0).round_ties_even(),
_ => dbl(0).trunc(),
};
integer(if n.is_nan() {
0
} else {
(n as i64).clamp(-(1_i64 << 62), (1_i64 << 62) - 1)
})
}
ChrOrd => integer(chr(0) as i64),
ChrChr => {
let c = u32::try_from(int(0))
.ok()
.and_then(char::from_u32)
.ok_or("invalid character code point")?;
Value::Char(c)
}
ChrEq => boolean(chr(0) == chr(1)),
ChrLt => boolean(chr(0) < chr(1)),
StrAppend => text(format!("{}{}", string(0), string(1))),
StrLength => integer(string(0).chars().count() as i64),
StrEq => boolean(string(0) == string(1)),
StrCompare => integer(match string(0).cmp(string(1)) {
std::cmp::Ordering::Less => -1,
std::cmp::Ordering::Equal => 0,
std::cmp::Ordering::Greater => 1,
}),
StrUnpack => Value::Chars(string(0).chars().collect()),
StrPack => match &args[0] {
Value::Chars(cs) => text(cs.iter().collect()),
_ => unreachable!("typed character list"),
},
ShowInt => text(int(0).to_string()),
ShowDouble => text(show_double(dbl(0))),
ShowChar => text(quote(&chr(0).to_string(), '\'')),
ShowString => text(quote(string(0), '"')),
ReadInt => Value::MaybeInt(read_int(string(0))),
Error => return Err(string(0).into()),
PutStr => {
use std::io::Write;
std::io::stdout()
.write_all(string(0).as_bytes())
.map_err(|e| e.to_string())?;
Value::Unit
}
GetLine => {
use std::io::Write;
std::io::stdout().flush().map_err(|e| e.to_string())?;
let mut line = String::new();
if std::io::stdin()
.read_line(&mut line)
.map_err(|e| e.to_string())?
== 0
{
return Err("end of input".into());
}
if line.ends_with('\n') {
line.pop();
if line.ends_with('\r') {
line.pop();
}
}
text(line)
}
Trace => {
trace(string(0))?;
args[1].clone()
}
Exit => return Err(Failure::Exit(int(0) as i32)),
})
}
/// Match Rust main's broken-pipe policy when entered through a generated C main.
pub(crate) fn init_io() {
static INIT: std::sync::Once = std::sync::Once::new();
INIT.call_once(|| {
// SAFETY: on the supported Unix targets, SIGPIPE is 13 and SIG_IGN is
// the distinguished handler value 1. This installs no Rust callback.
unsafe {
unsafe extern "C" {
fn signal(number: i32, handler: usize) -> usize;
}
signal(13, 1);
}
});
}
/// The trace event happens after both strict operands have been evaluated.
pub fn trace(message: &str) -> Result<(), Failure> {
init_io();
use std::io::Write;
std::io::stdout().flush().map_err(|e| e.to_string())?;
writeln!(std::io::stderr().lock(), "{message}")
.map_err(|e| e.to_string())?;
Ok(())
}
}단순화기는 자신의 재작성이 무엇을 할 수 있는지를 코드 옆에 명시합니다.
#![allow(unused)]
fn main() {
//! A rewrite may delete an unused total RHS, replace an atom by an equal atom,
//! or move a lambda applied exactly once. It may never copy a call, a failing
//! primitive, or an effect, nor move one past another. Allocation failure is
//! outside the source cost model. The oracle checks transitions and trace order.
}reach::analyze는 안정적인 그래프 순회를 수행합니다. 그 루트에는 관찰 가능한 초기화식이 포함되며, 어떤 전역에 이르는 첫 번째 간선이 그 전역의 증인(witness)이 됩니다:
#![allow(unused)]
fn main() {
use crate::{
anf::{Anf, Atom, Body, Program, Rhs},
names::Id,
};
use std::collections::{BTreeMap, BTreeSet, VecDeque};
/// Source-ordered survivors and their first discovery edge. Roots have no predecessor.
pub struct Reach {
pub kept: Vec<Id>,
pub witness: BTreeMap<Id, Option<Id>>,
}
/// Visit every reference, including captures hidden in nested lambdas, without recursion.
fn references(body: &Body) -> BTreeSet<Id> {
let mut found = BTreeSet::new();
let mut todo = vec![body.as_ref()];
let mut mark = |a: &Atom| {
if let Atom::Global(v) = a {
found.insert(v.clone());
}
};
while let Some(body) = todo.pop() {
match body {
Anf::Let(_, rhs, rest) => {
todo.push(rest);
match rhs {
Rhs::Atom(a) | Rhs::Field(a, _) => mark(a),
Rhs::Call(f, args) => {
mark(f);
for a in args {
mark(a);
}
}
Rhs::Con(_, args) | Rhs::Prim(_, args, _) => {
for a in args {
mark(a);
}
}
Rhs::Lambda(l) => todo.push(&l.body),
}
}
Anf::LetRec(bs, rest) => {
todo.push(rest);
for (_, l) in bs {
todo.push(&l.body);
}
}
Anf::Join(_, _, body, rest) => {
todo.push(rest);
todo.push(body);
}
Anf::Case(a, alts) => {
mark(a);
for (_, _, body) in alts {
todo.push(body);
}
}
Anf::Ret(a) => mark(a),
Anf::TailCall(f, args) => {
mark(f);
for a in args {
mark(a);
}
}
Anf::Jump(_, args) => {
for a in args {
mark(a);
}
}
Anf::Fail(_) => {}
}
}
found
}
/// A closure's body does not run during initialization. Calls and failure stay roots.
pub fn discardable(body: &Body) -> bool {
let mut todo = vec![body.as_ref()];
while let Some(body) = todo.pop() {
match body {
Anf::Let(_, rhs, rest) => {
if !crate::anf_simplify::discardable(rhs) {
return false;
}
todo.push(rest);
}
Anf::LetRec(_, rest) => todo.push(rest),
Anf::Ret(_) => {}
// Control-flow initializers are conservatively retained. A jump may loop.
_ => return false,
}
}
true
}
/// Filtering preserves the original dependency and initialization order.
pub fn prune(program: &mut Program, reach: &Reach) {
program
.globals
.retain(|(id, _)| reach.witness.contains_key(id));
}
/// Stable diagnostic spelling keeps unique-number churn out of the witness dump.
pub fn display(reach: &Reach, original: usize) -> String {
use std::fmt::Write;
let mut text = String::new();
for id in &reach.kept {
let parent = reach.witness[id]
.as_ref()
.map_or("root", |p| p.text.as_str());
writeln!(text, "{} <- {parent}", id.text).unwrap();
}
writeln!(
text,
"kept {}, dropped {}",
reach.kept.len(),
original - reach.kept.len()
)
.unwrap();
text
}
/// Follow dependencies from explicit roots and observable initializers in stable order.
pub fn analyze(program: &Program, roots: &[Id]) -> Reach {
let bodies = program
.globals
.iter()
.map(|(id, body)| (id.clone(), body))
.collect::<BTreeMap<_, _>>();
let mut witness = BTreeMap::new();
let mut todo = VecDeque::new();
for id in roots.iter().cloned().chain(
program
.globals
.iter()
.filter(|(_, b)| !discardable(b))
.map(|(v, _)| v.clone()),
) {
if bodies.contains_key(&id) && !witness.contains_key(&id) {
witness.insert(id.clone(), None);
todo.push_back(id);
}
}
while let Some(id) = todo.pop_front() {
for next in references(bodies[&id]) {
if bodies.contains_key(&next) && !witness.contains_key(&next) {
witness.insert(next.clone(), Some(id.clone()));
todo.push_back(next);
}
}
}
Reach {
kept: program
.globals
.iter()
.filter(|(v, _)| witness.contains_key(v))
.map(|(v, _)| v.clone())
.collect(),
witness,
}
}
}소거(erasure)는 타입 정보가 아직 남아 있을 때 타입을 분류합니다:
#![allow(unused)]
fn main() {
use crate::{
ast::Op, core, data::ConId, names::Id, rep::Rep, source::Span,
};
use std::collections::BTreeMap;
#[derive(Clone, Debug)]
/// Expression-result evidence supplies the type of fresh ANF temporaries.
pub struct Expr {
pub node: Node,
pub rep: Rep,
}
#[derive(Clone, Debug)]
/// Untyped Core retains strict evaluation order and lexical join points.
pub enum Node {
Var(Id),
Global(Id),
Lit(core::Lit),
Lam(Id, Box<Expr>),
App(Box<Expr>, Box<Expr>),
Let(bool, Vec<(Id, Expr)>, Box<Expr>),
Con(ConId, Vec<Expr>),
Prim(Op, Vec<Expr>, Span),
Case(Box<Expr>, Id, Vec<(core::AltCon, Vec<Id>, Expr)>),
Join(Id, Vec<Id>, Box<Expr>, Box<Expr>),
Jump(Id, Vec<Expr>),
Fail(Span),
}
#[derive(Clone, Debug)]
pub struct Program {
pub globals: Vec<(Id, Expr)>,
pub reps: BTreeMap<Id, Rep>,
pub metadata: core::Program,
}
/// Postorder erasure uses a worklist so expression depth does not consume host stack.
fn expression(
root: &core::Expr,
program: &core::Program,
reps: &mut BTreeMap<Id, Rep>,
) -> Expr {
use core::{Expr as C, Type as T};
let mut todo = vec![(root, false)];
let mut results: Vec<(Expr, T)> = vec![];
while let Some((e, done)) = todo.pop() {
let children: Vec<&core::Expr> = match e {
C::Lam(_, e) | C::TyLam(_, e) | C::TyApp(e, _) => vec![e],
C::App(f, a) => vec![f, a],
C::Let(g, b) => g
.binds
.iter()
.map(|b| b.rhs.as_ref())
.chain(std::iter::once(b.as_ref()))
.collect(),
C::Con(_, _, es) | C::Prim(_, _, es, _) | C::Jump(_, es, _) => {
es.iter().collect()
}
C::Case(e, _, _, alts) => std::iter::once(e.as_ref())
.chain(alts.iter().map(|a| &a.rhs))
.collect(),
C::Join(_, _, b, r) => vec![b, r],
C::Match(_) => panic!("match compilation precedes erasure"),
_ => vec![],
};
if !done {
todo.push((e, true));
todo.extend(children.into_iter().rev().map(|c| (c, false)));
continue;
}
let start = results.len() - children.len();
let mut parts = results.split_off(start).into_iter();
let mut bind = |i: &core::Id| {
reps.insert(i.name.clone(), representation(&i.ty));
i.name.clone()
};
let (node, ty) = match e {
C::Var(i) => (Node::Var(i.name.clone()), i.ty.clone()),
C::Global(i) => (Node::Global(i.name.clone()), i.ty.clone()),
C::Lit(l) => (
Node::Lit(l.clone()),
match l {
core::Lit::Int(_) => T::Int,
core::Lit::Double(_) => T::Double,
core::Lit::Char(_) => T::Char,
core::Lit::String(_) => T::String,
},
),
C::Lam(i, _) => {
let (b, t) = parts.next().unwrap();
(Node::Lam(bind(i), Box::new(b)), T::arrow(i.ty.clone(), t))
}
C::App(_, _) => {
let (f, t) = parts.next().unwrap();
let (a, _) = parts.next().unwrap();
let T::Arrow(_, t) = t else {
panic!("checked Core application")
};
(Node::App(Box::new(f), Box::new(a)), *t)
}
C::TyLam(v, _) => {
let (e, t) = parts.next().unwrap();
(e.node, T::Forall(*v, Box::new(t)))
}
C::TyApp(_, a) => {
let (e, t) = parts.next().unwrap();
let T::Forall(v, t) = t else {
panic!("checked Core instantiation")
};
(e.node, t.substitute(v, a))
}
C::Let(g, _) => {
let bs = g
.binds
.iter()
.map(|b| (bind(&b.name), parts.next().unwrap().0))
.collect();
let (b, t) = parts.next().unwrap();
(Node::Let(g.recursive, bs, Box::new(b)), t)
}
C::Con(c, args, _) => {
let d = &program.constructors[c.index as usize];
let t = crate::elaborate::instantiate(
&d.result,
&d.parameters,
args,
);
(Node::Con(c.clone(), parts.map(|p| p.0).collect()), t)
}
C::Prim(op, ts, _, span) => {
let (mut t, n) = crate::primitives::core_signature(
*op,
ts,
&program.data_types,
)
.expect("checked primitive");
for _ in 0..n {
let T::Arrow(_, b) = t else { unreachable!() };
t = *b;
}
(Node::Prim(*op, parts.map(|p| p.0).collect(), *span), t)
}
C::Case(_, i, t, alts) => {
let e = parts.next().unwrap().0;
let alts = alts
.iter()
.map(|a| {
(
a.con.clone(),
a.binders.iter().map(&mut bind).collect(),
parts.next().unwrap().0,
)
})
.collect();
(Node::Case(Box::new(e), bind(i), alts), t.clone())
}
C::Join(j, ps, _, _) => {
let b = parts.next().unwrap().0;
let (r, t) = parts.next().unwrap();
(
Node::Join(
j.clone(),
ps.iter().map(&mut bind).collect(),
Box::new(b),
Box::new(r),
),
t,
)
}
C::Jump(j, _, t) => (
Node::Jump(j.clone(), parts.map(|p| p.0).collect()),
t.clone(),
),
C::PatternFail(s, t) => (Node::Fail(*s), t.clone()),
C::Match(_) => unreachable!(),
};
results.push((
Expr {
node,
rep: representation(&ty),
},
ty,
));
}
results.pop().unwrap().0
}
/// Evidence is recorded while types exist. Later passes may only copy established facts.
pub fn erase(mut program: core::Program) -> Program {
let mut reps = BTreeMap::new();
let globals = program
.groups
.iter()
.flat_map(|g| &g.binds)
.map(|b| {
reps.insert(b.name.name.clone(), representation(&b.name.ty));
(b.name.name.clone(), expression(&b.rhs, &program, &mut reps))
})
.collect();
program.global_types = program
.groups
.iter()
.flat_map(|g| &g.binds)
.map(|b| {
(
b.name.name.clone(),
crate::core_type::fingerprint(&b.name.ty),
)
})
.collect();
// Consuming Core must not recursively destroy its nested expressions.
let mut todo = program
.groups
.drain(..)
.flat_map(|g| g.binds.into_iter().map(|b| *b.rhs))
.collect::<Vec<_>>();
while let Some(e) = todo.pop() {
use core::Expr as C;
match e {
C::Lam(_, b) | C::TyLam(_, b) | C::TyApp(b, _) => todo.push(*b),
C::App(a, b) | C::Join(_, _, a, b) => {
todo.push(*a);
todo.push(*b);
}
C::Let(g, b) => {
todo.push(*b);
todo.extend(g.binds.into_iter().map(|b| *b.rhs));
}
C::Con(_, _, es) | C::Prim(_, _, es, _) | C::Jump(_, es, _) => {
todo.extend(es)
}
C::Case(e, _, _, alts) => {
todo.push(*e);
todo.extend(alts.into_iter().map(|a| a.rhs));
}
C::Match(_) => {
unreachable!("match compilation precedes erasure")
}
_ => {}
}
}
Program {
globals,
reps,
metadata: program,
}
}
pub(crate) fn literal_rep(l: &core::Lit) -> Rep {
match l {
core::Lit::Int(_) => Rep::Int,
core::Lit::Double(_) => Rep::Double,
_ => Rep::Word,
}
}
/// Compact syntax uses an explicit print stack and bounded indentation. Debug's
/// indentation grows with depth and makes even a linear tree quadratic in bytes.
impl std::fmt::Display for Expr {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
enum Work<'a> {
Expr(&'a Expr),
Text(String),
}
let mut todo = vec![Work::Expr(self)];
while let Some(work) = todo.pop() {
match work {
Work::Text(s) => write!(f, "{s}")?,
Work::Expr(e) => {
let mut parts = vec![];
match &e.node {
Node::Var(v) => write!(f, "{v}")?,
Node::Global(v) => write!(f, "@{v}")?,
Node::Lit(l) => write!(f, "{l}")?,
Node::Lam(v, b) => {
write!(f, "(lambda {v}. ")?;
parts.push(Work::Expr(b));
parts.push(Work::Text(")".into()));
}
Node::App(a, b) => {
write!(f, "(")?;
parts.extend([
Work::Expr(a),
Work::Text(" ".into()),
Work::Expr(b),
Work::Text(")".into()),
]);
}
Node::Con(c, es) => {
write!(f, "({}", c.name)?;
for e in es {
parts.push(Work::Text(" ".into()));
parts.push(Work::Expr(e));
}
parts.push(Work::Text(")".into()));
}
Node::Prim(p, es, _) => {
write!(f, "({}", p.text())?;
for e in es {
parts.push(Work::Text(" ".into()));
parts.push(Work::Expr(e));
}
parts.push(Work::Text(")".into()));
}
Node::Jump(j, es) => {
write!(f, "(jump {j}")?;
for e in es {
parts.push(Work::Text(" ".into()));
parts.push(Work::Expr(e));
}
parts.push(Work::Text(")".into()));
}
Node::Let(rec, bs, b) => {
write!(
f,
"(let{} ",
if *rec { "rec" } else { "" }
)?;
for (v, e) in bs {
parts.push(Work::Text(format!("{v} = ")));
parts.push(Work::Expr(e));
parts.push(Work::Text(";\n".into()));
}
parts.extend([
Work::Text("in ".into()),
Work::Expr(b),
Work::Text(")".into()),
]);
}
Node::Case(e, v, alts) => {
write!(f, "(case ")?;
parts.extend([
Work::Expr(e),
Work::Text(format!(" as {v} {{\n")),
]);
for (c, ps, e) in alts {
let c = match c {
core::AltCon::Con(c) => c.name.clone(),
core::AltCon::Lit(l) => l.to_string(),
core::AltCon::Default => "_".into(),
};
parts.push(Work::Text(c));
for p in ps {
parts.push(Work::Text(format!(" {p}")));
}
parts.extend([
Work::Text(" -> ".into()),
Work::Expr(e),
Work::Text(";\n".into()),
]);
}
parts.push(Work::Text("})".into()));
}
Node::Join(j, ps, b, r) => {
write!(f, "(join {j}")?;
for p in ps {
write!(f, " {p}")?;
}
write!(f, " = ")?;
parts.extend([
Work::Expr(b),
Work::Text("\nin ".into()),
Work::Expr(r),
Work::Text(")".into()),
]);
}
Node::Fail(s) => write!(f, "fail {s:?}")?,
}
todo.extend(parts.into_iter().rev());
}
}
}
Ok(())
}
}
/// Destroy an owned erased tree without recursively following Box edges.
pub fn discard(root: Expr) {
let mut todo = vec![root];
while let Some(e) = todo.pop() {
match e.node {
Node::Lam(_, b) => todo.push(*b),
Node::App(a, b) | Node::Join(_, _, a, b) => {
todo.push(*a);
todo.push(*b);
}
Node::Let(_, bs, b) => {
todo.push(*b);
todo.extend(bs.into_iter().map(|(_, e)| e));
}
Node::Con(_, es) | Node::Prim(_, es, _) | Node::Jump(_, es) => {
todo.extend(es)
}
Node::Case(e, _, alts) => {
todo.push(*e);
todo.extend(alts.into_iter().map(|(_, _, e)| e));
}
_ => {}
}
}
}
/// This is the single classification point. A type variable proves no numeric representation.
pub(crate) fn representation(ty: &core::Type) -> Rep {
match ty {
core::Type::Int => Rep::Int,
core::Type::Double => Rep::Double,
_ => Rep::Word,
}
}
}명시적인 후위 순회 작업 목록이 바인더와 표현식 결과의 증거를 기록합니다. ANF는 과포화 호출에 포함된 각 적용의 결과를 비롯해 이 증거를 새 임시 변수로 복사합니다. 클로저 변환은 이 증거를 보존합니다. 수치 증거가 없거나 서로 모순되면 내부 린트 오류입니다. 인터프리터는 이 테이블을 무시합니다. IR 덤프는 수치 표기를 보여 주므로 독자가 그 사실들을 직접 살펴볼 수 있습니다.
LLVM 방출 과정에서는 별도의 열거형이 현재 저장 방식을 기술합니다:
#![allow(unused)]
fn main() {
use super::*;
use crate::{
core::Lit,
flat::{Atom, FuncId},
runtime_layout as layout,
};
use inkwell::{
types::BasicMetadataTypeEnum,
values::{BasicMetadataValueEnum, PointerValue},
};
impl<'ctx> Backend<'ctx, '_> {
pub(super) fn n(&self, n: u64) -> IntValue<'ctx> {
self.word.const_int(n, false)
}
pub(super) fn external(
&self,
name: &str,
args: &[BasicMetadataTypeEnum<'ctx>],
result: bool,
) -> FunctionValue<'ctx> {
self.module.get_function(name).unwrap_or_else(|| {
let ty = if result {
self.word.fn_type(args, false)
} else {
self.context.void_type().fn_type(args, false)
};
self.module.add_function(name, ty, None)
})
}
pub(super) fn call(
&self,
name: &str,
args: &[BasicMetadataValueEnum<'ctx>],
) -> Result<IntValue<'ctx>> {
let types = args
.iter()
.map(|a| match a {
BasicMetadataValueEnum::IntValue(v) => v.get_type().into(),
BasicMetadataValueEnum::PointerValue(v) => {
v.get_type().into()
}
_ => unreachable!("runtime ABI operands"),
})
.collect::<Vec<_>>();
let call = self.builder.build_call(
self.external(name, &types, true),
args,
"call",
)?;
// A tailcc function must regain control to restore its callee-pop frame.
// LLVM's tail-call pass may otherwise infer a tail transfer into the C ABI.
call.set_tail_call_kind(
inkwell::values::LLVMTailCallKind::LLVMTailCallKindNoTail,
);
Ok(call.try_as_basic_value().unwrap_basic().into_int_value())
}
pub(super) fn void_call(
&self,
name: &str,
args: &[BasicMetadataValueEnum<'ctx>],
) -> Result<()> {
let types = args
.iter()
.map(|a| match a {
BasicMetadataValueEnum::IntValue(v) => v.get_type().into(),
BasicMetadataValueEnum::PointerValue(v) => {
v.get_type().into()
}
_ => unreachable!("runtime ABI operands"),
})
.collect::<Vec<_>>();
self.builder.build_call(
self.external(name, &types, false),
args,
"",
)?;
Ok(())
}
pub(super) fn pointer(
&self,
value: IntValue<'ctx>,
) -> Result<PointerValue<'ctx>> {
Ok(self.builder.build_int_to_ptr(
value,
self.context.ptr_type(AddressSpace::default()),
"ptr",
)?)
}
pub(super) fn slot(
&self,
pointer: PointerValue<'ctx>,
index: u64,
) -> Result<PointerValue<'ctx>> {
// SAFETY: GEP indexes i64 words using the checked ABI layout.
Ok(unsafe {
self.builder.build_gep(
self.word,
pointer,
&[self.n(index)],
"slot",
)?
})
}
pub(super) fn load(
&self,
value: IntValue<'ctx>,
index: u64,
) -> Result<IntValue<'ctx>> {
Ok(self
.builder
.build_load(
self.word,
self.slot(self.pointer(value)?, index)?,
"load",
)?
.into_int_value())
}
pub(super) fn store(
&self,
value: IntValue<'ctx>,
index: u64,
field: IntValue<'ctx>,
) -> Result<()> {
self.builder
.build_store(self.slot(self.pointer(value)?, index)?, field)?;
Ok(())
}
pub(super) fn allocation(
&self,
kind: u8,
tag: u32,
fields: &[IntValue<'ctx>],
) -> Result<IntValue<'ctx>> {
let name = if matches!(kind, layout::DOUBLE | layout::STRING) {
"rt_alloc_atomic"
} else {
"rt_alloc"
};
let ptr = self.context.ptr_type(AddressSpace::default());
let f = self.module.get_function(name).unwrap_or_else(|| {
self.module.add_function(
name,
ptr.fn_type(&[self.word.into()], false),
None,
)
});
let size = (fields.len() + 1) as u64
* if name == "rt_alloc" { 1 } else { 8 };
let p = self
.builder
.build_call(f, &[self.n(size).into()], "alloc")?
.try_as_basic_value()
.unwrap_basic()
.into_pointer_value();
let value = self.builder.build_ptr_to_int(p, self.word, "word")?;
self.store(
value,
0,
self.n(layout::header(kind, tag, fields.len() as u32)),
)?;
for (i, field) in fields.iter().enumerate() {
self.store(value, i as u64 + 1, *field)?;
}
Ok(value)
}
pub(super) fn closure(
&self,
f: FuncId,
captures: &[IntValue<'ctx>],
) -> Result<IntValue<'ctx>> {
let code = self.slow[f.0 as usize]
.as_global_value()
.as_pointer_value()
.const_to_int(self.word);
let mut fields = vec![
code,
self.n(self.program.funcs[f.0 as usize].params.len() as u64),
];
fields.extend_from_slice(captures);
self.allocation(layout::CLOSURE, 0, &fields)
}
fn string(&mut self, s: &str) -> IntValue<'ctx> {
if let Some(v) = self.strings.get(s) {
return *v;
}
let mut bytes = s.as_bytes().to_vec();
bytes.resize(bytes.len().div_ceil(8) * 8, 0);
let data = self.context.const_string(&bytes, false);
let object = self.context.const_struct(
&[
self.n(layout::header(
layout::STRING,
0,
1 + (bytes.len() / 8) as u32,
))
.into(),
self.n(s.len() as u64).into(),
data.into(),
],
false,
);
let g = self.module.add_global(
object.get_type(),
None,
&format!("fun.string{}", self.strings.len()),
);
g.set_linkage(Linkage::Private);
g.set_constant(true);
g.set_alignment(8);
g.set_initializer(&object);
let word = g.as_pointer_value().const_to_int(self.word);
self.strings.insert(s.into(), word);
word
}
/// Keep static string words in a retained data root table. Strings themselves are read-only.
pub(super) fn string_roots(&self) {
if self.strings.is_empty() {
return;
}
let words = self.strings.values().copied().collect::<Vec<_>>();
let array = self.word.const_array(&words);
let roots = self.module.add_global(
array.get_type(),
None,
"fun.string_roots",
);
roots.set_linkage(Linkage::Internal);
roots.set_initializer(&array);
roots.set_alignment(8);
let ptr = self.context.ptr_type(AddressSpace::default());
let used = ptr.const_array(&[roots.as_pointer_value()]);
let keep =
self.module.add_global(used.get_type(), None, "llvm.used");
keep.set_linkage(Linkage::Appending);
keep.set_section(Some("llvm.metadata"));
keep.set_initializer(&used);
}
pub(super) fn literal(&mut self, l: &Lit) -> Result<IntValue<'ctx>> {
Ok(match l {
Lit::Int(n) => self.n(layout::integer(*n)),
Lit::Char(c) => self.n(layout::integer(*c as i64)),
Lit::String(s) => self.string(s),
Lit::Double(bits) => {
self.allocation(layout::DOUBLE, 0, &[self.n(*bits)])?
}
})
}
pub(super) fn atom(
&mut self,
a: &Atom,
env: &Env<'ctx>,
) -> Result<Loc<'ctx>> {
Ok(match a {
Atom::Lit(Lit::Int(n)) => Loc::Int(self.n(*n as u64)),
Atom::Lit(Lit::Double(bits)) => Loc::Double(
self.context.f64_type().const_float(f64::from_bits(*bits)),
),
Atom::Lit(l) => Loc::Word(self.literal(l)?),
Atom::Var(v) => env[v],
Atom::Global(v) => Loc::Word(
self.builder
.build_load(
self.word,
self.globals[v].as_pointer_value(),
"global",
)?
.into_int_value(),
),
})
}
pub(super) fn loc_word(
&self,
value: Loc<'ctx>,
) -> Result<IntValue<'ctx>> {
match value {
Loc::Word(v) => Ok(v),
Loc::Int(v) => self.retag(v),
Loc::Double(v) => self.box_double(v),
}
}
pub(super) fn loc_int(
&self,
value: Loc<'ctx>,
) -> Result<IntValue<'ctx>> {
match value {
Loc::Word(v) => self.untag(v),
Loc::Int(v) => Ok(v),
Loc::Double(_) => {
unreachable!("numeric evidence checked by Flat lint")
}
}
}
pub(super) fn loc_double(
&self,
value: Loc<'ctx>,
) -> Result<inkwell::values::FloatValue<'ctx>> {
match value {
Loc::Word(v) => self.unbox_double(v),
Loc::Double(v) => Ok(v),
Loc::Int(_) => {
unreachable!("numeric evidence checked by Flat lint")
}
}
}
pub(super) fn atom_word(
&mut self,
a: &Atom,
env: &Env<'ctx>,
) -> Result<IntValue<'ctx>> {
let loc = self.atom(a, env)?;
self.loc_word(loc)
}
pub(super) fn atoms(
&mut self,
args: &[Atom],
env: &Env<'ctx>,
) -> Result<Vec<IntValue<'ctx>>> {
args.iter().map(|a| self.atom_word(a, env)).collect()
}
pub(super) fn known(
&self,
f: FuncId,
env: Option<IntValue<'ctx>>,
args: &[IntValue<'ctx>],
tail: bool,
) -> Result<IntValue<'ctx>> {
let mut actual: Vec<BasicMetadataValueEnum> =
vec![env.unwrap_or(self.n(0)).into()];
actual
.extend(args.iter().map(|v| BasicMetadataValueEnum::from(*v)));
let call = self.builder.build_call(
self.fast[f.0 as usize],
&actual,
"known",
)?;
call.set_call_convention(TAIL_CC);
call.set_tail_call(tail);
if self
.builder
.get_insert_block()
.unwrap()
.get_parent()
.unwrap()
.get_call_conventions()
!= TAIL_CC
{
call.set_tail_call_kind(
inkwell::values::LLVMTailCallKind::LLVMTailCallKindNoTail,
);
}
Ok(call.try_as_basic_value().unwrap_basic().into_int_value())
}
pub(super) fn apply(
&self,
f: IntValue<'ctx>,
args: &[IntValue<'ctx>],
) -> Result<IntValue<'ctx>> {
if (1..=4).contains(&args.len()) {
let mut actual = vec![f.into()];
actual.extend(
args.iter().map(|v| BasicMetadataValueEnum::from(*v)),
);
return self.call(&format!("rt_apply{}", args.len()), &actual);
}
// Allocate in the entry, never in a loop reached by a join back-edge.
let entry = self
.builder
.get_insert_block()
.unwrap()
.get_parent()
.unwrap()
.get_first_basic_block()
.unwrap();
let alloc = self.context.create_builder();
if let Some(first) = entry.get_first_instruction() {
alloc.position_before(&first);
} else {
alloc.position_at_end(entry);
}
let array = alloc.build_alloca(
self.word.array_type(args.len().max(1) as u32),
"arguments",
)?;
for (i, a) in args.iter().enumerate() {
self.builder.build_store(self.slot(array, i as u64)?, *a)?;
}
self.call(
"rt_apply",
&[f.into(), self.n(args.len() as u64).into(), array.into()],
)
}
pub(super) fn box_double(
&self,
v: inkwell::values::FloatValue<'ctx>,
) -> Result<IntValue<'ctx>> {
let bits = self
.builder
.build_bit_cast(v, self.word, "bits")?
.into_int_value();
self.allocation(layout::DOUBLE, 0, &[bits])
}
pub(super) fn unbox_double(
&self,
v: IntValue<'ctx>,
) -> Result<inkwell::values::FloatValue<'ctx>> {
Ok(self
.builder
.build_bit_cast(
self.load(v, 1)?,
self.context.f64_type(),
"double",
)?
.into_float_value())
}
}
/// Storage is local to codegen. All ABI boundaries still carry tagged words.
#[derive(Clone, Copy)]
pub(super) enum Loc<'ctx> {
Word(IntValue<'ctx>),
Int(IntValue<'ctx>),
Double(inkwell::values::FloatValue<'ctx>),
}
}atom_word는 ABI 용도를 처리합니다. 반면 Integer와 Double 원시 연산의 피연산자는 네이티브 저장 방식을 요청합니다. 태그가 붙은 입력은 해당 용도를 위해 한 번만 디코딩되며, 이미 네이티브 레지스터에 있는 결과는 다음 원시 연산으로 곧바로 흘러갈 수 있습니다. 정수 산술은 네이티브 결과를 저장하기 전에 정규화 헬퍼를 호출합니다:
#![allow(unused)]
fn main() {
fn normalize(&self, value: IntValue<'ctx>) -> Result<IntValue<'ctx>> {
let bits =
self.builder
.build_left_shift(value, self.n(1), "wrap.bits")?;
Ok(self.builder.build_right_shift(
bits,
self.n(1),
true,
"wrap.int",
)?)
}
}이 코드 생성 변경만 떼어 내어 보기 위해, 원시 연산을 직접 사용하는 Flat 루프를 구성하고 최적화된 LLVM에서 런타임 호출 횟수를 셉니다. 정수 루프에는 런타임 호출이 하나도 필요하지 않습니다. Double 루프에는 호출 경계를 넘는 값을 위한 원자적 할당이 한 번 필요합니다. 오버로드된 소스 프로그램은 별도로 인터프리터와 비교합니다. 그렇게 하면 우리가 실제로 어떤 개선을 구현했는지 정직하게 따질 수 있습니다.
실행해 보기
저장소 루트에서:
$ cd crates/ch23_optimize
$ cargo run -q -- run tests/programs/optimize/trace-sharing.fun --engine=anf --print-steps
once
42
steps: 92
$ cargo run -q -- run tests/programs/optimize/trace-sharing.fun --engine=anf --print-steps --no-simplify
once
42
steps: 171
$ cargo run -q -- dump --pass=reach tests/programs/optimize/trace-sharing.fun
마지막 명령은 유지된 정의와 그 증인을 나열하고, 마지막에 유지된 개수와 제거된 개수를 출력합니다. 수치 바인더 표기를 살펴보려면 dump --pass=anf나 dump --pass=flat을 사용하십시오. 실제로 최적화된 소스 루프를 살펴보려면:
$ cargo run -q -- dump --pass=llvm-opt tests/programs/optimize/double-loop.fun
지역 부동소수점 명령어뿐 아니라 사전 호출도 따라가 보십시오. 소스 함수의 명령어 개수만 비교하면 피호출자 내부의 작업이 가려질 수 있습니다. cargo test --test optimization은 작업 오라클과 트레이스 코퍼스를 실행합니다. cargo test --test native에는 할당 횟수 계약이 포함되어 있습니다.
연습 문제
- 준비 운동.
trace의 두 번째 인자가 또 다른 트레이스된 식일 때 트레이스 순서를 예측해 보십시오. 모든 엔진에서 이를 확인하십시오. - 중급. 도달 가능성 덤프를 확장하여 선행자 하나가 아니라 루트로부터의 전체 경로를 보여 주도록 하십시오.
- 중급.
Bool증거를 추가하고, 비교 결과가 워드 경계를 넘을 때까지 태그 없는 상태로 유지하십시오. - 고급. 네이티브 정수를 조인 매개변수를 통해 전달하십시오. 코드 생성을 변경하기 전에 새로운 저장 불변식을 명시하고 린트를 확장하십시오.
- 고급. 작업 오라클에 죽은 저장(dead store)을 세는 카운터를 추가하십시오. 전이 횟수는 보존하지만 불필요한 저장을 수행하는 재작성을 구성해 보십시오.
더 읽을거리
- 컴파일러에서의 변환과 비용 추론 (Appel 1992).
- 엄격한 함수형 언어 구현에서의 값 표현 (Leroy 1990).