Julia SSA-form IR

줄리아는 최적화를 수행하기 위해 정적 단일 할당 중간 표현(SSA IR)을 사용합니다. 이 IR은 LLVM IR과 다르며, 줄리아에 고유합니다. 이는 줄리아 특정 최적화를 가능하게 합니다.

기본 블록(제어 흐름이 없는 영역)은 명시적으로 주석이 달려 있습니다.
if/else와 루프는 goto 문으로 변환됩니다.
여러 작업이 포함된 줄은 변수를 도입하여 여러 줄로 나뉩니다.

예를 들어 다음의 Julia 코드:

function foo(x)
    y = sin(x)
    if x > 5.0
        y = y + cos(x)
    end
    return exp(2) + y
end

Float64 인수로 호출되면 다음과 같이 변환됩니다:

using InteractiveUtils
@code_typed foo(1.0)

CodeInfo(
1 ─ %1 = invoke Main.sin(x::Float64)::Float64
│   %2 = Base.lt_float(x, 5.0)::Bool
└──      goto #3 if not %2
2 ─ %4 = invoke Main.cos(x::Float64)::Float64
└── %5 = Base.add_float(%1, %4)::Float64
3 ┄ %6 = φ (#2 => %5, #1 => %1)::Float64
│   %7 = Base.add_float(7.38905609893065, %6)::Float64
└──      return %7
) => Float64

이 예제에서는 이러한 모든 변화를 볼 수 있습니다.

첫 번째 기본 블록은 모든 것입니다.

1 ─ %1 = invoke Main.sin(x::Float64)::Float64
│   %2 = Base.lt_float(x, 5.0)::Bool
└──      goto #3 if not %2

if 문은 goto #3 if not %2로 번역되며, 이는 x>5가 충족되지 않을 경우 3번째 기본 블록으로 이동하고, 그렇지 않으면 두 번째 기본 블록으로 이동합니다.
%2는 x > 5를 나타내기 위해 도입된 SSA 값입니다.

Background

줄리아 0.7부터 컴파일러의 일부는 새로운 SSA-form 중간 표현(IR)을 사용합니다. 역사적으로, 컴파일러는 줄리아 AST의 낮춘 형태에서 직접 LLVM IR을 생성했습니다. 이 형태는 대부분의 구문 추상화가 제거되었지만 여전히 추상 구문 트리와 매우 유사하게 보였습니다. 시간이 지나면서 최적화를 용이하게 하기 위해 SSA 값이 이 IR에 도입되었고 IR은 선형화되었습니다(즉, 함수 인수는 SSA 값이나 상수만 될 수 있는 형태로 변환됨). 그러나 Phi 노드가 IR에 없기 때문에 비 SSA 값(슬롯)은 IR에 남아 있었습니다(백 엣지 및 조건부 제어 흐름의 재병합에 필요). 이로 인해 중간 끝 최적화를 수행할 때 SSA 형태 표현의 유용성이 크게 감소했습니다. 이러한 최적화를 완전한 SSA 형태 표현 없이 작동하도록 만들기 위해 많은 노력이 기울여졌지만, 그러한 표현의 부족은 궁극적으로 장애가 되었습니다.

Categories of IR nodes

SSA IR 표현은 네 가지 카테고리의 IR 노드를 가지고 있습니다: Phi, Pi, PhiC, 및 Upsilon 노드(후자의 두 개는 예외 처리를 위해서만 사용됩니다).

Phi nodes and Pi nodes

Phi 노드는 일반 SSA 추상화의 일부입니다 (개념에 익숙하지 않다면 위 링크를 참조하세요). Julia IR에서 이러한 노드는 다음과 같이 표현됩니다:

struct PhiNode
    edges::Vector{Int32}
    values::Vector{Any}
end

우리는 두 벡터가 항상 동일한 길이를 가지도록 보장합니다. 표준 표현(코드 생성기와 인터프리터가 처리하는 것)에서 엣지 값은 come-from 문 번호를 나타냅니다(즉, 엣지에 15라는 항목이 있으면, 문 15에서 이 phi 노드를 대상으로 하는 goto, gotoifnot 또는 암묵적 fall through가 있어야 합니다). 값은 SSA 값이거나 상수입니다. 또한 값이 할당되지 않은 상태일 수도 있는데, 이는 변수가 이 경로에서 정의되지 않았기 때문입니다. 그러나 정의되지 않음 검사는 중간 끝 최적화 후에 명시적으로 삽입되고 부울로 표현되므로, 코드 생성기는 Phi 노드의 사용이 해당 슬롯에서 할당된 값을 가질 것이라고 가정할 수 있습니다. Phi 노드에 들어오는 엣지가 누락되는 경우, 매핑이 불완전한 것도 합법적입니다. 이 경우, 해당 값이 사용되지 않을 것임을 동적으로 보장해야 합니다.

SSA는 해당 선행자의 종료자("엣지에서") 이후에 의미적으로 발생한다고 주의하십시오. 따라서 기본 블록의 시작 부분에 여러 개의 Phi 노드가 나타나면 동시에 실행됩니다. 이는 다음 IR 스니펫에서 블록 23에서 왔다면, %46은 이 블록에 들어가기 전에 %45와 연관된 값을 가져온다는 것을 의미합니다.

%45 = φ (#18 => %23, #23 => %50)
%46 = φ (#18 => 1.0, #23 => %45)

PiNodes는 주어진 pi 노드에 의해 지배되는 기본 블록에서 암묵적으로 가정될 수 있는 정적으로 증명된 정보를 인코딩합니다. 이들은 논문 ABCD: Eliminating Array Bounds Checks on Demand에서 소개된 기법이나 LLVM의 술어 정보 노드와 개념적으로 동등합니다. 그들이 어떻게 작동하는지 보려면, 예를 들어 고려해 보십시오.

%x::Union{Int, Float64} # %x is some Union{Int, Float64} typed ssa value
if isa(x, Int)
    # use x
else
    # use x
end

우리는 술어 삽입을 수행하고 이를 다음과 같이 바꿀 수 있습니다:

%x::Union{Int, Float64} # %x is some Union{Int, Float64} typed ssa value
if isa(x, Int)
    %x_int = PiNode(x, Int)
    # use %x_int
else
    %x_float = PiNode(x, Float64)
    # use %x_float
end

Pi 노드는 일반적으로 인터프리터에서 무시되며, 값에 영향을 미치지 않지만, 때때로 컴파일러에서 코드 생성을 유도할 수 있습니다(예: 암묵적인 유니온 분할 표현에서 일반적인 언박스 표현으로 변경하기 위해). Pi 노드의 주요 유용성은 값의 경로 조건을 단순히 def-use 체인 탐색을 통해 누적할 수 있다는 사실에서 비롯됩니다. 이는 어차피 이러한 조건을 고려하는 대부분의 최적화에서 일반적으로 수행됩니다.

PhiC nodes and Upsilon nodes

예외 처리는 SSA 이야기를 다소 복잡하게 만듭니다. 왜냐하면 예외 처리는 값이 추적되어야 하는 IR에 추가적인 제어 흐름 엣지를 도입하기 때문입니다. 이를 수행하는 한 가지 방법은 LLVM이 따르는 방식으로, 예외를 발생시킬 수 있는 호출을 기본 블록 종료자로 만들고 catch 핸들러에 명시적인 제어 흐름 엣지를 추가하는 것입니다:

invoke @function_that_may_throw() to label %regular unwind to %catch

regular:
# Control flow continues here

catch:
# Exceptions go here

그러나 이는 Julia와 같은 언어에서는 문제가 됩니다. 최적화 파이프라인의 시작에서 어떤 호출이 예외를 발생시키는지 알 수 없기 때문입니다. 우리는 모든 호출(즉, Julia에서는 모든 문)이 예외를 발생시킨다고 보수적으로 가정해야 합니다. 이는 여러 가지 부정적인 영향을 미칠 것입니다. 한편으로는, 이는 사실상 모든 기본 블록의 범위를 단일 호출로 줄여 기본 블록 수준에서 작업을 수행하는 목적을 무색하게 만듭니다. 다른 한편으로는, 모든 catch 기본 블록은 n*m phi 노드 인수를 가지게 됩니다(n은 중요 구역의 문 수, m은 catch 블록을 통과하는 활성 값의 수입니다).

이 문제를 해결하기 위해 우리는 Upsilon과 PhiC 노드의 조합을 사용합니다(여기서 C는 catch를 의미하며, IR 프리티 프린터에서 φᶜ로 작성됩니다. 유니코드 아래 첨자 c는 사용할 수 없기 때문입니다). 이러한 노드를 생각하는 방법은 여러 가지가 있지만, 아마도 가장 쉬운 방법은 각 PhiC를 고유한 저장-다수, 읽기-한 번 슬롯에서의 로드로 생각하는 것입니다. 여기서 Upsilon은 해당 저장 작업에 해당합니다. PhiC는 암묵적 슬롯에 저장하는 모든 업실론 노드의 피연산자 목록을 가지고 있습니다. 그러나 Upsilon 노드는 자신이 저장하는 PhiC 노드를 기록하지 않습니다. 이는 나머지 SSA IR과의 보다 자연스러운 통합을 위해 수행됩니다. 예를 들어, PhiC 노드의 더 이상의 사용이 없다면 안전하게 삭제할 수 있으며, Upsilon 노드도 마찬가지입니다. 대부분의 IR 패스에서 PhiC 노드는 Phi 노드처럼 취급될 수 있습니다. 사용-정의 체인을 따라갈 수 있으며, 새로운 PhiC 노드와 새로운 Upsilon 노드로 올릴 수 있습니다(원래 Upsilon 노드와 같은 위치에서). 이 방식의 결과는 Upsilon 노드(및 PhiC 인수)의 수가 특정 변수에 할당된 값의 수에 비례한다는 것입니다(SSA 변환 이전), 즉 중요한 영역의 문장 수가 아닙니다.

이 스킴이 작동하는 것을 보려면, 함수를 고려하십시오.

@noinline opaque() = invokelatest(identity, nothing) # Something opaque
function foo()
    local y
    x = 1
    try
        y = 2
        opaque()
        y = 3
        error()
    catch
    end
    (x, y)
end

해당 IR(관련 없는 유형이 제거됨)은:

1 ─       nothing::Nothing
2 ─ %2  = $(Expr(:enter, #4))
3 ─ %3  = ϒ (false)
│   %4  = ϒ (#undef)
│   %5  = ϒ (1)
│   %6  = ϒ (true)
│   %7  = ϒ (2)
│         invoke Main.opaque()::Any
│   %9  = ϒ (true)
│   %10 = ϒ (3)
│         invoke Main.error()::Union{}
└──       $(Expr(:unreachable))::Union{}
4 ┄ %13 = φᶜ (%3, %6, %9)::Bool
│   %14 = φᶜ (%4, %7, %10)::Core.Compiler.MaybeUndef(Int64)
│   %15 = φᶜ (%5)::Core.Const(1)
└──       $(Expr(:leave, Core.SSAValue(2)))
5 ─       $(Expr(:pop_exception, :(%2)))::Any
│         $(Expr(:throw_undef_if_not, :y, :(%13)))::Any
│   %19 = Core.tuple(%15, %14)
└──       return %19

특히 모든 값이 중요한 영역에 들어가면 중요한 영역의 맨 위에 upsilon 노드가 생긴다는 점에 유의하십시오. 이는 catch 블록이 함수 외부에서 보이지 않는 제어 흐름 엣지를 가진 것으로 간주되기 때문입니다. 결과적으로, 어떤 SSA 값도 catch 블록을 지배하지 않으며, 모든 들어오는 값은 φᶜ 노드를 통해 와야 합니다.

Main SSA data structure

주요 SSAIR 데이터 구조는 논의할 가치가 있습니다. 이는 LLVM과 Webkit의 B3 IR에서 영감을 받았습니다. 데이터 구조의 핵심은 문장의 평면 벡터입니다. 각 문장은 벡터에서의 위치에 따라 암묵적으로 SSA 값을 할당받습니다(즉, idx 1에서의 문장의 결과는 SSAValue(1)을 사용하여 접근할 수 있습니다). 각 SSA 값에 대해 우리는 추가로 그 타입을 유지합니다. SSA 값은 정의상 한 번만 할당되므로, 이 타입은 해당 인덱스의 표현식 결과 타입이기도 합니다. 그러나 이 표현 방식은 상당히 효율적이지만(할당을 명시적으로 인코딩할 필요가 없기 때문에), 물론 순서가 의미적으로 중요하다는 단점이 있습니다. 따라서 재정렬 및 삽입은 문장 번호를 변경합니다. 또한, 우리는 사용 목록을 유지하지 않기 때문에(즉, 이 맵을 명시적으로 계산하지 않고는 정의에서 모든 사용으로 이동하는 것이 불가능합니다–그러나 정의 목록은 인덱스에서 해당 문장을 조회할 수 있으므로 사소합니다), LLVM 스타일의 RAUW(모든 사용을 교체) 작업은 사용할 수 없습니다.

대신, 우리는 다음과 같이 합니다:

우리는 삽입할 노드의 별도 버퍼를 유지합니다(삽입할 위치, 해당 값의 유형 및 노드 자체를 포함). 이러한 노드는 삽입 버퍼에서 발생한 순서에 따라 번호가 매겨져, 그 값이 IR의 다른 곳에서 즉시 사용될 수 있도록 합니다(즉, 원래 문장 목록에 12개의 문장이 있는 경우, 첫 번째 새로운 문장은 SSAValue(13)로 접근할 수 있습니다).
RAUW 스타일 작업은 해당 문장 인덱스를 대체 값으로 설정하여 수행됩니다.
진술은 해당 진술을 nothing으로 설정하여 지워집니다(이는 본질적으로 위의 특별한 경우 규칙입니다).
해당 문장이 삭제되는 경우, 모든 사용은 nothing으로 설정됩니다.

compact! 함수는 위의 데이터 구조를 압축하여 노드를 적절한 위치에 삽입하고, 사소한 복사 전파를 수행하며, 변경된 SSA 값에 대한 사용을 재명명합니다. 그러나 이 계획의 영리한 부분은 이 압축이 후속 패스의 일환으로 지연되어 수행될 수 있다는 것입니다. 대부분의 최적화 패스는 전체 문장 목록을 순회하며 분석 또는 수정을 수행해야 합니다. 우리는 문장 목록을 반복하는 데 사용할 수 있는 IncrementalCompact 반복자를 제공합니다. 이 반복자는 필요한 압축을 수행하고 노드의 새 인덱스와 노드 자체를 반환합니다. 이 시점에서 def-use 체인을 순회하고 IR에 대한 수정 또는 삭제를 수행하는 것은 합법적입니다(단, 삽입은 허용되지 않습니다).

이 배열의 아이디어는 최적화 패스가 해당 메모리를 어차피 접근해야 하고 그에 따른 메모리 접근 비용이 발생하므로, 추가적인 관리 작업을 수행하는 것이 비교적 적은 오버헤드를 가져야 한다는 것입니다 (그리고 IR 수정 중 이러한 데이터 구조를 유지하는 오버헤드를 절약할 수 있습니다).