이 게시물은 Cranelift에 대한 3 부작 시리즈의 마지막입니다. 첫 번째 게시물에서는 전반적인 컨텍스트와 명령 선택 문제를 다루었습니다. 두 번째 게시물에서는 신중한 알고리즘 설계를 통해 컴파일러 성능에 대해 자세히 알아 보았습니다.
이 게시물에서는 정확성
이러한 위험을 줄이기 위해 좋은 엔지니어링 원칙을 적용 할 수있는 방법입니다. 매우 강력한 기술은 결과를 확인하는 이라는 통찰력에서 파생됩니다. 일반적으로 컴퓨팅 보다 쉬우 며 무작위로 많은 입력을 생성하면 , 이러한 입력에 대해 컴파일러 (또는 다른 프로그램)를 실행하고 출력을 확인하면 통계적 근사치 “모든 입력에 대해 컴파일러가 올바른 출력을 생성합니다”. 우리가 더 많은 무작위 입력을 시도할수록이 문장은 더 강해집니다. 이 기법을 퍼징 이라고합니다. 프로그램 특정 오라클 , 그리고 나는 그것의 기괴한 힘에 대한 긴 노래를 쓸 수 있습니다. 버그 (다른 많은 버그가 이미 있습니다).
이 게시물에서는 특정 레지스터 할당 결과에 대한 정확성을 증명하기 위해 추상 해석을 사용하는 기호 검사기를 개발하여 레지스터 할당자인 regalloc.rs의 정확성을 보장하기 위해 노력했습니다. 이 검사기를 퍼징 오라클로 사용하고 집중된 퍼징 대상으로 레지스터 할당 자만 구동함으로써 매우 흥미롭고 미묘한 버그를 발견하고 할당 자의 견고성에 대해 상당히 높은 신뢰도를 얻을 수있었습니다.
레지스터 할당이란?
들어가기 전에 몇 가지 기본 사항을 다뤄야합니다. 가장 중요한 것은 레지스터 할당 문제는 무엇이며이를 어렵게 만드는 것은 무엇입니까?
일반적인 프로그래밍 언어 인 프로그램은 범위에 임의의 수의 변수 또는 값을 가질 수 있습니다. 이것은 매우 유용한 추상화입니다. 값을 저장할 위치에 대해 걱정할 필요가 없을 때 알고리즘을 설명하는 것이 가장 쉽습니다.
예를 들어 다음과 같은 프로그램을 작성할 수 있습니다.
void f () {int x0=compute (0); int x1=계산 (1); // ... int x99=compute (99); // --- 소비 (x0); 소비 (x1); // ... consum (x99); }
프로그램 중간 지점 (- -
표시), 100 개 int 크기의 값으로 계산되어 나중에 사용됩니다. 컴파일러가이 함수에 대한 기계어 코드를 생성 할 때 해당 값은 어디에 저장됩니까?
값이 적은 작은 함수를 사용하면 모든 값을 CPU 레지스터에 쉽게 배치 할 수 있습니다. 그러나 대부분의 CPU에는 정수 저장을위한 100 개의 범용 레지스터가 없습니다 1 ; 일반적으로 대부분의 언어는 지역 변수 수에 제한을 두지 않거나 일반적인 CPU 레지스터 수보다 훨씬 더 높은 제한을 부과합니다. 따라서 한 번에 약 16 개 값 (x86-64) 또는 약 32 개 값 (aarch64) 이상으로 확장 할 수있는 접근 방식이 필요합니다.
아주 간단한 대답은 메모리 [ r0=v0 ]를 할당하는 것입니다. 각 지역 변수의 위치. 사실 이것이 바로 C 프로그래밍 모델이 제공하는 것입니다. xN 위의 변수 의미 상 메모리에 살고 있으며 주소 & xN . 이렇게하면 주소가 스택 의 일부임을 알 수 있습니다. . 함수가 호출되면 스택에 스택 프레임
하지만 우리가 할 수있는 최선은! 이것이 실제로 지역 주민들에게 어떤 작업을 수행 할 때 의미하는 바를 고려하십시오. 두 명의 로컬을 읽으면 더하기를 수행하고 결과를 다음과 같이 1/3에 저장합니다.
그런 다음 기계어 코드에서 대부분의 CPU에는 두 개의 메모리 내 값을 읽고 세 번째 메모리 내 결과를 다시 쓸 수있는 명령어가 없기 때문에 다음과 같은 내용을 내 보냅니다.
ld r0, ld r1, [address of x2] r0, r0, r1 추가 // r0 :=r0 + r1 st r0, [address of x0]
방법은 거의 결정을 내릴 필요가 없기 때문에 매우 빠릅니다 : 예를 들어 변수 참조
는 항상 메모리로드가됩니다. 이것이 “기준 JIT 컴파일러”가 일반적으로 작동하는 방식입니다. 예를 들어 SpiderMonkey JS 및 Wasm JIT 컴파일러에서 기준 JIT 계층 (매우 신속하게 통과 가능한 코드를 생성하는 것을 의미 함)은 실제로 값 스택을 JS 바이트 코드 또는 Wasm 바이트 코드의 값 스택에 일대일 대응하는 메모리. (여기에서 코드를 읽을 수 있습니다. 실제로 가장 최근 값 중 일부를 피연산자 스택 상단, 고정 레지스터에 저장하고 나머지는 메모리에 보관합니다.)
안타깝게도 모든 작업에 대해 메모리에 여러 번 액세스하는 것은 매우 느립니다. 또한 값이 생산 된 직후 재사용되는 경우가 많습니다 : 예를 들어
x0=x1 + x2; x3=x0 2;
계산하면 x3 x0 , 새로 고침합니까 x0 의 값을 저장 한 직후 메모리에서? 더 똑똑한 컴파일러는 방금 값을 계산했다는 사실을 기억할 수 있어야하며, 메모리를 통한 왕복을 완전히 피하면서 레지스터에 보관해야합니다.
이것은 등록 할당 : 프로그램의 값을 저장을 위해 레지스터에 할당합니다. 레지스터 할당을 흥미롭게 만드는 것은 (위에서 언급했듯이) 허용 가능한 프로그램 값의 수보다 CPU 레지스터가 적기 때문에 레지스터에 유지할 값의 일부를 선택해야한다는 것입니다. 이는 종종 특정 방식으로 제한됩니다. 예 : add RISC와 유사한 CPU의 명령어는 레지스터에서 읽고 쓰기 만 할 수 있으므로 값의 저장 위치는 [B]에서 사용하기 직전에 레지스터 여야합니다. + 연산자. 다행히도 위치 할당은 시간이 지남에 따라 변경 될 수 있으므로 기계 코드의 다른 지점에서 레지스터를 할당하여 다른 값을 유지할 수 있습니다. 레지스터 할당 자의 역할은 메모리와 레지스터 사이 및 레지스터 사이에서 값을 섞는 방법을 결정하여 주어진 시간에 레지스터에 있어야하는 값이 그렇게되도록하는 것입니다.
디자인에서 레지스터 할당자는 “가상 레지스터 코드”라고하는 거의 기계 코드 유형을 입력으로 받아들입니다. VCode . 일련의 기계 명령어가 있지만 명령어에 이름이 지정된 레지스터는 가상 레지스터 : 컴파일러는 필요한만큼 사용할 수 있습니다. 레지스터 할당자는 (i) 명령어의 레지스터 참조를 실제 머신 레지스터 이름으로 다시 작성하고 (ii) 필요에 따라 데이터를 섞는 명령어를 삽입합니다. 이러한 명령어는 레지스터에서 값을 이동할 때 유출 이라고합니다. 기억에; 메모리에서 레지스터로 값을 다시 이동할 때 다시로드 합니다. 레지스터간에 값을 이동할 때
이동 합니다. 레지스터에 없을 때 값이 저장되는 메모리 위치를 유출 슬롯 이라고합니다. .
레지스터 할당 문제의 예는 프로그램에서 아래와 같습니다. 네 가지 지침 :
이 할당은 두 개의 레지스터 ( r0 및 r1 ). 왼쪽에는 가상 레지스터
가있는 어셈블리와 같은 형식으로 원래 프로그램이 작성됩니다. . 오른쪽은 실제 레지스터 만 사용하도록 수정되었습니다. ).
각 명령어 사이에 가상 레지스터에서 실제 레지스터로 매핑을 작성했습니다. . 레지스터 할당 자의 작업은 이러한 매핑을 계산 한 다음 명령어를 편집하여 이러한 매핑을 통해 레지스터 참조를 가져 오는 것입니다.
프로그램은 한 지점에서 세 실시간 값 또는 나중에 사용되기 때문에 여전히 보존해야하는 값 : 첫 번째와 두 번째 명령어 사이에 v0 , v1 및 v2 가 라이브입니다. 기계에는 레지스터가 두 개뿐이므로 모든 라이브 값을 보유 할 수 없습니다. 적어도 하나를 흘려야합니다. 이것이 상점으로 작성된 유출 지시 의 이유입니다. 스택 슬롯에 [sp+0] .
레지스터 할당은 얼마나 어렵습니까?
일반적으로 레지스터 할당자는 먼저 프로그램을 분석하여 어떤 값이 어떤 프로그램 포인트에 존재하는지 알아냅니다. 이 활성 정보 및 관련 제약은 조합 최적화 문제를 지정합니다. 특정 값은 어딘가에 저장 각 지점에서 제약 조건은 선택할 수있는 선택을 제한하고 일부 선택은 다른 선택과 충돌 할 수 있습니다 (예 : 두 값이 동시에 레지스터를 차지할 수 없음). 선택 세트는 일부 비용 (데이터에서 운동). 할당자는이 최적화 문제를 해결할뿐만 아니라 레지스터 할당 자에 따라 일종의 휴리스틱을 사용할 수 있습니다.
이것은 어려운 문제입니까? 사실, 이것은 구어체적인 의미에서 어려울뿐만 아니라 NP 완전성입니다. 이것은 최악의 경우 지수 시간 무차별 대입 알고리즘 만 알고있는 다른 NP 문제만큼 어렵다는 것을 의미합니다. 2 삼 그 이유는 문제에 최적의 하부 구조가 없기 때문입니다. 개별적으로 해결할 수있는 상호 작용하지 않는 부품으로 분해 할 수 없습니다. 전체적인 솔루션으로 구성됩니다. 오히려 한 지점에서의 결정은 다른 곳, 잠재적으로 기능 본문의 다른 곳에서 결정에 영향을 미칩니다. 따라서 최악의 경우 우리가 원하는 경우 무차별 대입 검색보다 더 잘할 수 없습니다. n 최적의 솔루션.
최적의 레지스터 할당에 대한 근사치 . 일반적인 것은 선형 스캔 레지스터 할당으로, 코드 크기와 관련하여 거의 선형 시간으로 실행될 수 있습니다. 더 많은 시간을 할애 할 수있는 할당자는 더 복잡합니다. 뛰어난 동료 Julian Seward)는 레지스터에 대한 더 높은 우선 순위 사용을 발견하여 선택 사항을 편집하고 개선 할 수 있습니다.
이러한 알고리즘의 작동 방식에 대한 세부 사항은 여기에서 실제로 중요하지 않습니다. 단, 매우 복잡하고 제대로하기가 어렵습니다. 개념적 수준이나 의사 코드에서 비교적 단순 해 보이는 알고리즘은 실제 제약 조건이 들어 오면서 흥미롭고 미묘한 고려 사항에 빠르게 부딪 힙니다. regalloc.rs 코드베이스는 약 25K 줄의 깊이 알고리즘 Rust 코드입니다. 합리적인 엔지니어라면 여기에 적어도 몇 가지 버그가 포함될 것으로 예상합니다! 여기서 시급함을 더하면 레지스터 할당 버그로 인해 임의 가 발생할 수 있습니다. ) 잘못된 결과. 레지스터 할당자가 프로그램의 모든 데이터 흐름을 “연결”하는 역할을하기 때문입니다. 프로그램에서 임의의 값을 다른 임의의 값으로 교환하면 어떤 일이 일어날 수 있습니다.
정확성 확인 방법
따라서 올바른 레지스터 할당자를 작성하려고합니다. 이런 일을 어떻게 시작하나요?
“정확하다”는 의미입니다. 레지스터 할당 문제에는 좋은 속성이 있습니다. 프로그램은 이전에 및
이후 할당에는 잘 정의 된 의미가 있습니다. 특히 레지스터 할당은 무한 레지스터 머신 에서 실행중인 프로그램을 변환하는 변환으로 생각할 수 있습니다. (원하는만큼 많은 가상 레지스터를 사용할 수있는 곳) 유한 등록 머신 (CPU에 고정 된 레지스터 세트가 있음). 무한 레지스터 머신의 원래 프로그램이 유한 레지스터 머신의 변환 된 (레지스터 할당) 프로그램과 동일한 결과를 산출하면 올바른 레지스터 할당을 달성 한 것입니다.
이 동등성을 어떻게 테스트합니까?
단일 프로그램, 단일 입력 등가
두 프로그램이 있는지 테스트하는 가장 간단한 방법 동등한 것은 그들을 실행하고 결과를 비교하는 것입니다! 단일 프로그램에 대해 임의의 입력을 선택하고 적절한 인터프리터에서 레지스터 할당 버전과 함께 가상 등록 프로그램을 실행한다고 가정 해 보겠습니다. 마지막에 레지스터와 메모리 상태를 비교합니다.
주가 일치합니까? 이것은 하나의 프로그램
에 대해
레지스터 할당자가 이 하나의 프로그램 입력 에 대해 올바른 변환 된 프로그램. 여기에 두 가지 자격이 있습니다. 첫째, 다른 프로그램 입력이 주어지면 레지스터 할당이 정확하다는 것을 반드시 보여주지는 않았습니다. 다른 입력으로 인해 분기가 다른 프로그램 경로로 내려 가고 레지스터 할당자가 해당 경로에 오류가 발생했을 수 있습니다. 둘째, 다른 프로그램에 대해서는 아무것도 보여주지 않았습니다. 단일 프로그램과 레지스터 할당 출력 만 테스트했습니다.
더 많은 샘플 포인트를 취하여 첫 번째 한계 (한 번의 입력에서만 정확성)를 해결합니다. 예를 들어, 1000 개의 임의 프로그램 입력을 선택할 수 있으며 제어 흐름 범위 또는 기타 “흥미로운”동작 (퍼저처럼)을 최대화하려는 일종의 피드백을 사용하여이 임의의 선택을 유도 할 수도 있습니다. 충분한 테스트 사례가 주어지면이 단일 레지스터 할당 결과가 정확하다는 합리적인 확신을 얻을 수 있습니다.
그러나 이것은 여전히 매우 비싸다 : 우리는 N의 샘플 크기를 얻기 위해 전체 프로그램을 N 번 실행하도록 요청합니다. 한 번의 실행도 비용이 많이들 수 있습니다. 예를 들어 레지스터 할당을 수행 한 프로그램은 컴파일러 또는 비디오 게임 일 수 있습니다.
단일 프로그램, For-all-Input Equivalence
프로그램을 실행 할 필요가 전혀 없습니다 레지스터 할당 버전이 올바른지 테스트하려면?
대답은 놀랍도록 간단합니다. 예, 간단히 도메인
을 변경하면 가능합니다. 프로그램이 실행됩니다. 일반적으로 CPU 레지스터는 구체적인 숫자 (예 : 64 비트 값)를 포함하는 것으로 생각합니다. 대신 기호 가 포함 된 경우 어떻게 되나요?
프로그램 값을 기호로 일반화하면 종종 신경 쓰지 않고 입력 측면에서 시스템 상태를 나타낼 수 있습니다. 그 입력이 무엇인지. 예를 들어 다음과 같은 프로그램이 있습니다.
ld v0, [A] ld v1, [B] ld v2, [C] v3, v0, v1 추가 v4, v2, v3 v4 반환
register-allocated to :
ld r0, [A] ld r1, [B] ld r2, [C] add r0, r0, r1 add r0, r2, r0 return r0
기호 추론없이 임의의 정수를 메모리 위치에 저장할 수 있습니다 ㅏ, B 및 C 레지스터 할당 전후의 프로그램 실행을 시뮬레이션하고 불일치를 보지 못합니다. 가능한 모든 값을 반복하지 않는 한 아무것도 증명하지 마십시오. 그러나 세 번의로드 후에 r0 포함 v0 (기호 값으로 무엇이든), r1 포함 v1 및 r2 에 v2 , 그리고 그 r0 에 v3 첫 번째 추가 후 v4 두 번째 추가 후 기호를 일치시켜 대응을 볼 수 있습니다.
이것은 매우 간단한 예이며 아마도이 접근 방식의 통찰력과 힘을 과소 판매합니다. 나중에 추상 해석 에 대해 이야기 할 때 다시 돌아올 것입니다.
어쨌든 우리가 보여준 것은 단일 인스턴스에 대한 것입니다. 레지스터 할당 문제를 해결하기 위해 검증 할 수 있습니다. 올바른 방법으로 프로그램하십시오. 구체적으로 이것은 우리가 생성하는 기계어 코드가 마치 가상 등록 코드를 해석하는 것처럼 실행된다는 것을 의미합니다. 가상 레지스터 코드를 올바르게 생성 할 수 있다면 컴파일러가 올바른 것입니다. 훌륭합니다! 더 갈 수 있을까요?
모든 프로그램 동등성
레지스터 할당자가 항상 할 것임을 사전에 증명할 수 있습니다. 변환 모든 올바른 방식으로 프로그램하십시오. 즉, 프로그램에 대한 입력 값뿐만 아니라 프로그램 자체.
우리가 이것을 증명할 수 있다면, 런타임에 어떤 종류의 검사도 실행할 필요가 없습니다. 프로그램 입력을 추상화하면 프로그램을 실행할 필요가 없습니다. 레지스터 할당이 모든 입력에 대해 정확하다는 것을 알고 있습니다. 유사한 방식으로 레지스터 할당 할 프로그램을 추상화하면 레지스터 할당자를 실행할 필요가 없습니다. 레지스터 할당 자 가 모두 프로그램 및 모두 해당 프로그램에 입력 .
이것이 훨씬 더 어렵다는 것을 상상할 수 있습니다. 실제로 수행되었지만 상당한 증명 엔지니어링 노력이며 적극적인 연구 영역입니다. 기본적으로 컴파일러 알고리즘이 정확하다는 기계 검증 가능한 증명을 작성해야합니다. 이러한 검증 된 올바른 컴파일러가 존재합니다. 예를 들어 CompCert는 C를 여러 플랫폼의 기계 코드로 올바르게 컴파일하는 것으로 입증되었습니다. 안타깝게도 이러한 노력은 필요한 증명 엔지니어링 노력에 의해 크게 제한되므로 이러한 접근 방식은 기본 목표가 아닌 한 컴파일러에서 실현 가능하지 않을 것입니다.
접근 방식 : Checker가있는 할당 자
위의 모든 사항을 고려하여 가장 합리적인 트레이드 오프를 선택합니다. 기호 검사기 출력 레지스터 할당 자의. 이것은 레지스터 할당자가 정확하다는 정적 주장을 할 수는 없지만 올바른지 증명 주어진 컴파일러 실행에 대해; 그리고 이것을 퍼징 오라클로 사용하면 통계적 신뢰 를 구축 할 수 있습니다. 모든 컴파일러 실행에 대해 올바른지 확인합니다.
Register Allocator 확인
전체 흐름은 다음과 같습니다.
레지스터 할당 자 검사기를 시스템에 추가하는 방법에는 두 가지가 있습니다. 첫 번째는 왼쪽에서 “런타임 검사”라고합니다.이 모드에서는 모든 레지스터 할당 자 실행이 검사되고 할당을 사용하는 기계어 코드는 검사기가 확인할 때까지 실행이 허용되지 않습니다 (즉, 컴파일러가 결과를 반환하지 않음). 등가. 이것이 가장 안전한 모드입니다. 검증 된 올바른 할당 자와 동일한 보증을 제공합니다 (위의 “모든 프로그램 동등성”). 그러나 모든 컴파일에 약간의 오버 헤드를 부과하므로 바람직하지 않을 수 있습니다. 이러한 이유로 Cranelift에서 검사기로 레지스터 할당기를 실행하는 것은 지원되는 옵션이지만 기본값은 아닙니다.
두 번째 모드는 퍼징 [ r1=v1 ]에 체커를 적용하는 모드입니다. 워크 플로이며 일반적으로 선호하는 접근 방식입니다 (regalloc.rs에는 임의의 입력 프로그램을 생성하고 각 프로그램에서 검사기를 실행하는 fuzz 대상이 있으며이를 부분적으로 지속적으로 실행하고 있습니다) Google의 oss-fuzz 연속 퍼징 이니셔티브에있는 Wasmtime의 멤버십). 이 모드에서 우리는 검사기를 퍼징 엔진에 대한 응용 프로그램 별 오라클로 사용합니다. 퍼징 엔진이 임의의 프로그램 (테스트 케이스)을 생성 할 때 이러한 프로그램에 대해 레지스터 할당자를 실행하고 결과에 대해 검사기를 실행하고 엔진 할당자가 통과했는지 실패했는지 여부. 퍼 저는 인간 개발자가 디버그 할 수 있도록 실패한 테스트 케이스에 플래그를 지정합니다. fuzzer가 문제를 찾지 않고 오랫동안 실행되면 검사기를 실행하지 않아도 레지스터 할당자가 정확하다는 확신을 가질 수 있습니다. 퍼 저가 길어질수록 자신감이 커집니다. 응용 프로그램 별 오라클은 프로그램 충돌 또는 잘못된 출력과 같은보다 일반적인 퍼저 피드백 메커니즘에 비해 크게 향상되었습니다. 레지스터 할당 자 버그는 잘못된 실행으로 즉시 나타나지 않을 수 있거나 발생하는 경우 결과 충돌에 명백한 단점이 없을 수 있습니다. 실제 잘못 할당 된 레지스터에 연결됩니다. 검사기는 특정 명령어에서 특정 레지스터 사용을 가리키고 “이 레지스터가 잘못되었습니다”라고 말할 수 있습니다. 이러한 결과를 통해 훨씬 더 원활한 디버깅이 가능합니다!
이제 빌드 방법을 살펴 보겠습니다. 특정 레지스터 할당이 올바른지 확인하는 것을 목표로하는 “검사기”. 우리는 단계적으로 솔루션에 도달하고, 먼저 가장 쉬운 사례 인 직선 코드에 대해 추론 한 다음 제어 흐름을 도입합니다. 결국 우리는 선형 시간 (코드 크기에 비례)으로 실행되는 간단한 알고리즘을 갖게되며 그 단순함으로 인해 보증에 대해 합리적으로 확신 할 수 있습니다.
기호 동등성 및 요약 통역
위에서 실행에 대한 일종의 상징적 해석을 설명했음을 기억하십시오. 각 기호가 원래 코드의 가상 레지스터를 나타내는 “기호”값을 포함하는 CPU 레지스터에 대해 추론 할 수 있습니다. 예를 들어 코드
mov v0 , 1 mov v1, 2 add v2, v0, v1 return v2
및 해당 코드의 레지스터 할당 형식
mov r0, 1 mov r1, 2 add r0, r0, r1 return r0
그리고 어쨌든 동등하게 만드는 대체 세트 찾기 :
mov r0, 1 [ r0=v0 ] mov r1, 2 [ r1=v1 ] add r0, r0, r1 [ r0=v2 ] return r0
그러나 우리는 어떻게 해결합니까? r 이러한 대체? 위에서 우리는 값이 아닌 기호에서 작동하는 실행 형태를 암시했습니다. 원래 명령어 세트의 의미를 취하고 대신 기호 값에 대해 작동하도록 재구성 한 다음 코드를 단계별로 실행하여 의 표현을 찾을 수 있습니다. ) 모든 실행
을 한 번에. 이를 상징적 실행이라고하며 아래에 설명 된 몇 가지 개선 사항이 추상 해석의 기초가됩니다 4 . 이것은 매우 강력한 기술입니다!
명령 집합의 의미는 무엇입니까? 여기에 관련이 있습니까? 레지스터 할당자가 프로그램의 원래 명령
을 수정하지 않기 때문에 밝혀졌습니다. 5 , 우리는 각 명령어를 대부분 임의의 불투명 연산자입니다. 유일한 중요한 정보는 등록 이 읽은 작동) 및 쓰기 (작동 후). 6
유출 [C]시 레지스터 할당 기의 출력을 확인하는 것으로 밝혀졌습니다. 값 및 이동 시기 레지스터 사이의 값, 우리는 유출, 재 장전 및 이동에 대한 특별한 지식이 필요합니다. 따라서 입력 프로그램을 상징적 추론에 중요한 것만 캡처하는 일종의 최소 ISA로 줄일 수 있습니다 (실제 정의는 여기에 있습니다.이 게시물에서는 약간 단순화).
엎지르다 , : 레지스터에서 스필 슬롯으로 데이터 (가상 레지스터를 나타내는 기호)를 복사합니다.-
새로 고침 , : 스필 슬롯에서 레지스터로 데이터 복사
-
이동 , : 한 CPU 레지스터에서 다른 CPU 레지스터로 데이터 이동 (주의 : regalloc이 삽입 한 동작 만 이동 , 원래 입력 프로그램에서 이동하지 않습니다.)
-
Op read : , read_orig : 쓰기 : write_orig : : 일부 레지스터를 읽고 다른 레지스터를 쓰는 임의의 연산입니다.
마지막 지침이 가장 흥미 롭습니다. 원본 가상 레지스터와 명령어에 대한 등록 후 할당 CPU 레지스터 . 이것에 대한 필요성은 아래에서 더 명확해질 것이지만 직감은 우리가 둘 다
볼 필요가 있다는 것입니다. 사이에 대응 을 설정하기 위해
레지스터 할당자가 스캔하는 동안 위의 명령을 생성 할 수 있습니다. 코딩 및 편집; 그 부분은 간단한 번역입니다. 추상 프로그램이 있으면이를 “실행”할 수 있습니다. 상징의 영역을 넘어서. 어떻게할까요? 다음 규칙 :
- 일부를 유지합니다 state , 실제 CPU와 마찬가지로 : 각 CPU 레지스터에 대해, 스택 프레임의 각 위치에 대해 기호 (정수 값 아님). 이 기호는 저장 위치에 현재 해당 레지스터 값이 포함되어 있음을 알고있는 경우 가상 레지스터 이름이 될 수 있습니다.
알 수 없음 일 수도 있습니다. , 체커가 모르는 경우 또는 충돌 , 값이 여러 가상 레지스터 중 하나 일 수 있습니다. (후자의 두 가지의 차이점은 아래에서 제어 흐름을 논의 할 때 분명해질 것입니다. 지금은 상태를 다음과 같이 추상화하는 것으로 충분합니다. 슬롯에 프로그램 값이 기호 적으로 포함되어 있다는 것을 알고 있거나 아무것도 알지 못합니다.)
-
엎지르다, 새로 고침 또는 Move , 소스 위치 (레지스터 또는 스필 슬롯)에서 심볼 상태를 복사합니다. 목적지 위치로. 다시 말해서, 우리는 이러한 명령어가 항상 레지스터 나 메모리 워드의 정수 값을 이동한다는 것을 알고 있습니다. 따라서 가능한 모든 실행에 대해 상징적으로 소스 위치에 대한 지식이 있으면 해당 지식을 대상까지 확장 할 수 있습니다.
-
Op , 몇 가지 확인을 한 다음 몇 가지 업데이트를 수행합니다.
- 각 읽기 (입력) 레지스터에 대해 지정된 CPU 레지스터 (할당 후 위치)에 저장된 기호 값. 해당 심볼이 원래 명령어가 사용한 가상 레지스터와 일치하면 할당자가 가상 레지스터의 값을 여기에서 사용하도록 적절히 전달한 것이므로 할당은 올바른 (프로그램 데이터 흐름 유지). 그렇지 않은 경우 검사기 오류를 알리고 레지스터 할당 자에서 버그를 찾을 수 있습니다. 우리는 확실히 버그 일 것임을 압니다 (즉, (모든 실행에 대해!) 저장소에 해당 가상 레지스터가 포함되어야한다는 것을 증명 한 경우에만 저장소 위치에 대한 기호를 추적하기 때문입니다.
- 각각 쓰기 (출력) 레지스터, 주어진 CPU 레지스터에 저장된 기호 값을 주어진 (사전 할당) 가상 레지스터로 설정합니다. 즉, 각 쓰기 는 기호를 생성 합니다. 그런 다음이 기호는 소비자에게 도달 할 때까지 유출 / 재 장전 / 이동을 통해 프로그램을 통해 흐릅니다.
그리고 그게 다야! 우리는 직선 코드 (점프가없는 코드)에 대해 이것이 정확히 정확하다는 것을 매우 간단하게 증명할 수 있습니다 – 거짓 긍정이나 거짓 부정을 생성하지 않습니다. 귀납법으로이를 수행 할 수 있습니다. 기호 상태가 명령어 이전에 올 바르면 위의 규칙은 구체적인 프로그램이 수행하는 데이터 이동을 인코딩하고 기호 상태는 동일한 방식으로 업데이트되므로 기호 상태는 다음과 같습니다.
이것은 선형 도 마찬가지입니다. 따라서 직선 코드를 한 번만 스캔하면 매우 빠릅니다. 이것은 레지스터 할당 자로부터 도움 이 있기 때문에 가능합니다. 유출, 재로드 및 할당 자 삽입 이동 등록에 대해 알고 있으며 다른 모든 명령에 대한 사전 및 사후 할당 레지스터를 보유하고 있습니다. 우리가 이것들에 대해 모르고 기계 지침 만 본다면 어떻게해야하는지 생각해보십시오. 이 경우로드, 저장 또는 이동 명령은 할당 자 또는 원래 프로그램에서 올 수 있습니다. 우리는 그들 사이에 연결이있는 연산자의 그래프 만 가질 것이고, 그래프 동형 [ r0=v0 ]을 풀어야 할 것입니다. 문제. 훨씬 더 어렵고 훨씬 느립니다!
이제 끝났나요? 정답은 아닙니다. 우리는 직선 코드만을 고려했습니다. 점프하면 어떻게 되나요?
제어 흐름 조인, 격자 및 반복 데이터 흐름 분석
제어 흐름은 분석을 흥미롭게 만듭니다. 여러 가능성 을 허용하기 때문입니다. if-then-else 패턴이있는 간단한 프로그램을 생각해보십시오 (그 모양 때문에 “제어 흐름 다이아몬드”라고도 함) :
기호 분석이 왼쪽 가지에서 결정한다고 가정 해 보겠습니다. r0 에는 기호 상태가 있습니다. A 및 오른쪽 분기에는 기호 상태 B . 두 경로가 다시 결합 된 후 하위 블록에 어떤 상태가 있습니까?
“술어”를 허용하거나 다른 프로그램 상태에서 조건부로 대답 할 수있는 경우 정확한 대답을 제공 할 수 있습니다. 예를 들어 if 조건이 기호 C 부울 유형이있는 경우 추상적 인 표현 언어를 찾은 다음 if C {A} else {B} .
그러나, 이것은 빨리 견딜 수 없게됩니다. 루프가있는 프로그램은 무제한 기호 표현으로 이어집니다. (이를 보려면 기호 표현이 입력보다 더 큰 크기를 가질 수 있음을 고려하십시오. 따라서 루프 주변의 모든 순환 데이터 종속성은 무한히 큰 기호 표현을 생성 할 수 있습니다.) 비순환 제어 흐름만으로도 경로에 민감한 기호 표현이 가능합니다. 프로그램 크기에 따라 기하 급수적으로 증가 : N 기본 블록 및 루프 없음은 O (2 ^ N) 이러한 블록을 통과하는 경로와 완전히 정확한 기호 표현은 각 경로의 효과를 포착해야합니다.
따라서 대략적인 . 프로그램의 추상적 인 해석은 프로그램의 모든 동작을 손실없이 정확하게 포착 할 필요는 없습니다. 예를 들어, 정수 변수에 대해 가능한 숫자 기호 (양수, 음수, 알 수 없음) 만 추적하는 간단한 추상 해석 분석을 수행 할 수 있습니다. 따라서 다루기 쉬운 상태로 유지하려면 항상 세부 사항을 “요약”하고 삭제하는 것이 좋습니다. 따라서 여러 가능성이있을 때 상태를 “병합”할 수있는 방법을 고려해 보겠습니다.
매우 유용한 방식으로 “병합”이라는 개념을 포착하는 매우 멋진 수학적 객체 인 격자가 있습니다. 격자는 일련의 요소와 부분 순서 로 구성됩니다. 최소 요소 “bottom”및 최대 요소 “top”과 함께 두 요소 (두 피연산자보다 작은 가장 큰 요소)에 대한 “최대 하한”을 찾는 “meet”이라는 연산자 및 “최소 상한”(위의 이중)을 찾는 “join”.
(그림 출처 : Wikimedia, CC BY-SA 3.0)
격자의 매우 유용한 속성은 충족 및 결합의 병합 작업이 교환, 연관 및 재귀 . 이것은 결과가 순서와 반복에 관계없이 “혼합에 던져진”요소 세트에만 의존한다는 공식적인 방법입니다. 즉, 많은 요소들의 만남은 우리가 그것들을 처리하는 순서가 아니라 요소들의 집합 만의 기능입니다.
이것이 어떻게 유용합니까? 특정 분석 상태를 정의하고, 특정 사례에서는 CPU 레지스터와 스필 슬롯에서 기호 가상 레지스터로의 맵을 격자 요소로 정의하고 어떻게 든 상태를 병합하는 “만남 기능”을 정의하면 이 병합 동작을 사용하여 모든 프로그램 포함)에 대해 일종의 프로그램 분석을 구현할 수 있습니다. 무한한 분석 성장없이 루프가있는 사람들! 이를 “meet-over-all-paths”솔루션이라고하며 오늘날 컴파일러가 데이터 흐름 분석을 수행하는 표준 방식입니다. 7
격자는 프로그램 분석에서 “병합”을 유용한 방식으로 설명합니다. 격자 순서 관계 (위 그림의 화살표)는 한 상태가 다른 상태보다 다소 다듬어 진 (다소 많은 지식을 포함 함)을 나타내는 것으로 볼 수 있습니다. 하나는 “가장 큰”또는 “상위”요소에서 시작합니다. 모든 것이 사실 일 수 있습니다. 우리는 아무것도 모릅니다. 그런 다음 점진적으로 더 세련된 상태로 이동합니다. 한 분석 상태는 다른 상태에서 배운 모든 제약과 일부 새로운 제약 조건을 캡처하는 경우 다른 상태보다 “작게”정렬됩니다. 따라서 최대 하한을 계산하는 “meet”연산자는 두 입력 모두의 모든 지식을 캡처하는 분석 상태를 제공하며 더 이상은 없습니다. 8
임의 CFG에 대한 분석을 수행하는 일반적인 접근 방식은 다음과 같습니다.
- 분석 상태를 격자 .
- 현재 분석 상태를 추적합니다. 각 프로그램 지점 또는 명령어 사이를 가리 킵니다. 처음에 모든 프로그램 지점의 상태는 “상단”격자 요소입니다. 값이 만나면 격자에서 “아래”요소로 이동합니다.
- 각 명령의 효과를 처리하여 사전 프로그램 지점에서 사후 프로그램 지점의 상태를 계산합니다.
- 분석 상태가 제어 흐름 에지에 도달하면 에지를 통해 상태를 전파하고 다른 모든 가장자리에서 들어오는 상태와 만나 . 그러면 대상 블록의 상태를 다시 계산할 수 있습니다.
- “고정 점”루프, 더 이상 변경이 발생하지 않을 때까지 블록 항목 변경시 분석 상태로 업데이트 처리
이러한 방식으로 에 대한 모든 명령어 의미를 충족하는 데이터 흐름 문제에 대한 해결책을 찾습니다. 프로그램을 통한 모든 경로. 완전히 정확하지는 않을 수 있습니다 (즉, 모든 질문에 답하지 않을 수 있음) – 루프를 포함하는 실행에 대해 완전히 정확한 답을 포착하는 것이 종종 불가능하고 상당한 제어 흐름이있는 프로그램에서는 비실용적이기 때문입니다. 사운드 , 분석 결과에서 우리가 주장하는 모든 주장은 옳은.
데이터 흐름 분석 문제로서 레지스터 검사기
이제 모든 프로그램의 레지스터 할당 자 출력을 확인하는 데 필요한 모든 부분이 있습니다. 위에서 우리는 모든 직선 코드에 대해 기계 상태를 상징적으로 모델링 할 수 있다는 것을 보았습니다.이를 통해 제어 흐름이없는 한 레지스터 할당 자 오류를 정확하게 감지 할 수 있습니다 (위음성 및 위양성 없음). 그런 다음 제어 흐름에 대한 일반적인 정적 분석 접근 방식에 대해 논의했습니다. 두 가지를 어떻게 결합 할 수 있습니까?
대답은 우리가 격자 / 기호 레지스터 상태 , 그런 다음 고정 점 데이터 흐름 분석에서 위와 동일한 명령어 별 의미 체계를 살펴 봅니다. 간단히 말해서 각 저장 위치 (CPU 레지스터 또는 스필 슬롯)에 대해 격자가 있습니다.
“알 수 없음”상태는 “상위”격자 값입니다. 이것은 단순히 분석이 아직 수렴되지 않았거나 쓰기가 발생하지 않았기 때문에 레지스터에 무엇이 있는지 알 수 없다는 것을 의미합니다.
“충돌”상태는 “하단”격자 값입니다. 이는 둘 이상의 기호 정의가 병합되었음을 의미합니다. 일종의 예측이나 루프 요약으로 두 가지의 중첩을 나타내려고하기보다는 단순히 포기하고 “나쁜 가치”를 나타내는 상태로 이동합니다. 사용하지 않는 한 검사기 오류
가 아닙니다 . , 언제든지 좋은 값으로 덮어 쓸 수 있습니다. 그러나 값이 명령어 소스로 사용되면 오류 플래그를 지정합니다.
따라서 meet 기능은 매우 간단합니다. 동일한 레지스터가 아닌 경우 두 레지스터가 “충돌”상태가됩니다. “unknown”은 무엇이든 만나서 무엇이든 생산합니다. “충돌”은 전염성이 있습니다. “충돌”이있는 다른 주를 만나는 것은 “충돌”상태로 남아 있다는 의미입니다.
위에서 언급 한 분석 상태는 맵 레지스터 및 스필 슬롯에서 기호 상태로; 단순한 상징적 상태가 아닙니다. 따라서 우리의 격자는 실제로 각 개별 저장 위치의 상태의 산물이며 기호를 조각으로 만납니다. (결과 맵에는 모든 충족 입력에 나타나는 키에 대한 항목 만 포함됩니다. 즉, 도메인의 교차점을 사용합니다.)
분석 상태 및 충족 기능이 정의 된 상태에서 데이터 흐름 분석 루프를 실행하고 수렴하고 오류를 찾습니다. 그리고 우리는 끝났습니다!
그리고 그게 다입니다! 9
효과 : 버그를 찾을 수 있습니까?
짧은 대답은 예, 꽤 미묘한 버그를 찾을 수 있다는 것입니다!
regalloc.rs 검사기의 이점은 두 가지입니다 :
- 실제 버그를 발견했습니다. 위의 예에서 참조 유형 (정확한 GC 루팅) 지원에 개념적 오류가있었습니다. 특정 경우에 스필 슬롯이 포인터 유형 값에 할당되었지만 사용되지 않은 경우 스택 맵에 추가 될 수 있습니다 (목록 GC에 제공되는 포인터 유형 스필 슬롯). 이 버그가 발생하려면 특정 상황이 필요합니다. 가상 레지스터에 스필 슬롯을 할당하기로 결정한 레지스터 압력이 충분해야하지만 실제로 수행 할 필요가없는 (드문) 코드 경로에 도달해야합니다. 레지스터를 사용할 수 있기 때문에 유출. 적어도 SpiderMonkey의 WebAssembly 테스트 스위트에서 Cranelift 백엔드를 구동하는 꽤 광범위한 테스트에도 불구하고 GC (Wasm 참조 유형)의 다른 손으로 작성한 테스트에서는이를 달성하지 못했습니다. 퍼 저는 전체 커버리지를 향해 운전하고이 드문 코드 경로를 입력 한 다음 검사기가 오류를 발견하도록 허용했습니다.
- 신규 개발 할당자를 등록합니다. 선형 스캔 할당 자 (참조 유형 / 정확한 GC 루팅 지원이 역 추적 할당 자보다 약간 늦음)를 개발하는 동안 피드백은 검사기가 많은 실제 문제를 발견하고 더 빠르고 확실하게 진행할 수 있음을 나타냅니다.
레지스터의 개별 실행을 확인하는 체커에 대한 사전 작업을 찾는 것은 놀랍게도 어렵습니다. 할당 자. 완전히 검증 된 여러 컴파일러가 존재합니다. CompCert와 CakeML은 사실적인 언어 (각각 C와 ML)를 컴파일 할 수있는 두 가지입니다. 이러한 컴파일러는 알고리즘 자체가 올바른 것으로 입증되었다는 점에서 레지스터 할당자를 완전히 검증했습니다. 개별 컴파일 결과에 대해 검사기를 실행할 필요가 없습니다. 이를 달성하기위한 엔지니어링 노력은 체커를 작성하는 것보다 훨씬 큽니다 (후자의 경우 ~ 700 줄의 Rust).
레지스터 할당자를 올바르게 증명하는 CakeML의 접근 방식은 Tan et al. “검증 된 CakeML 컴파일러 백엔드”(J. Func Prog 29, 2019)에서. 유효한 그래프 색상 또는 “순열”(프로그램 값을 저장 슬롯에 매핑)이 제공되는 한 컴파일이 정확하도록 문제를 훌륭하게 고려한 것으로 보입니다. 이를 통해 할당 자 (그래프 채색 알고리즘)의 세부 사항과는 별도로 핵심 문제 (할당 전후의 데이터 흐름 동등성)에 대한 추론을 할 수 있습니다.
검증 생산 컴파일러도 존재합니다. e, Crellvm은 변형 된 프로그램과 함께 (기계 검사 가능) 정확성 증명을 생성하는 여러 LLVM 패스의 최근 확장입니다. 이 접근법은 개념적으로 레지스터-할당 자 검사기와 동일한 수준에 있습니다. 단일 컴파일러 실행의 유효성을 검사하지만 전체 사전 정확성 증명보다 빌드하기가 훨씬 쉽습니다. 그러나 이러한 노력은 아직 레지스터 할당을 처리하는 것으로 보이지 않습니다.
Rideau와 Leroy는 “Validating Register Allocation and Spilling”(CC 2010)은“번역 확인 검사”에서“일회성”정확성 증명을 분리하고 후자를 제공하는 유사한 분류를 설명합니다. 그러나 그들의 유효성 검사기는 해결해야하는 동등 제약 집합을 구축하는 상당히 복잡한 전달 함수를 정의합니다. 유효성 검사기는 할당 자의 힌트, 특히 원래 프로그램의 저장,로드 및 이동과 구별되는 wrt 유출, 재로드 및 삽입 된 이동을 활용하지 않는 것으로 보입니다. 이러한 힌트가 없으면 훨씬 더 일반적이고 복잡한 데이터 흐름 동등성 체계가 필요합니다.
Nandivada et al. “A Framework for End-to-End Verification and Evaluation of Register Allocators”(SAS 2007)에서는 물리적 레지스터 내용 (가상 레지스터 또는 “의사”기호)이 post-register로 인코딩되는 우리의 검사기와 매우 유사한 시스템을 설명합니다. regalloc IR을 입력합니다. 그들의 typechecker는 우리의 checker가 할 수있는 것과 동일한 종류의 regalloc 오류를 발견 할 수 있습니다. 따라서 그들의 접근 방식은 우리의 접근 방식과 거의 동일합니다. 주요 차이점은 문제를 전용 IR에서 유형 검사로 인코딩하는 것이 아니라 독립형 정적 분석으로 인코딩한다는 것입니다.
결론
지난 1 년 동안 Cranelift의 새로운 백엔드의 모든 부분을 개발하기 위해 수행 한 작업을 설명하는 3 개의 포스트 시리즈 (1, 2)! 개인적으로 매우 흥미롭고 교육적인 여행이었습니다. 더 일반적으로 가르치고 연구하는 “중간 엔드”(IR 수준 최적화)와는 별개로 컴파일러 백엔드에서 해결해야 할 완전히 새로운 흥미로운 문제의 세계를 발견했습니다. 또한 빠른 컴파일에 대한 초점은 흥미로운 반전입니다. 내가 생각하는 것은 충분히 연구되지 않았다. 점점 더 복잡한 기술을 통해 더 높은 분석 정밀도와 더 나은 생성 된 코드를 정당화하는 것은 쉽습니다. 빠른 컴파일을위한 디자인 트레이드 오프에서 찾을 수있는 이점은 더 주관적이고 작업 부하에 더 많이 의존합니다.
이 글이 우리의 디자인 결정에 들어간 생각의 일부를 밝혔기를 바랍니다. 그러나 우리의 일은 결코 끝나지 않습니다! 2021 년 Cranelift 작업 로드맵에는 더 높은 컴파일러 성능과 더 나은 코드 품질을 달성하기 위해 논의한 많은 아이디어가 나열되어 있습니다. 나는 내년에 이것들을 더 탐구하게되어 기쁩니다. 더 많은 블로그 게시물을 올릴 수도 있습니다. 그때까지 즐거운 컴파일!
이 게시물에 대한 토론을 원하시면이 스레드의 Zulip 인스턴스에 자유롭게 참여하십시오.
내가 통합 한 몇 가지 제안에 대해 Reddit의 / u / po8에게 감사드립니다. 몇 가지 제안에 대해 bjorn3에게도 감사드립니다. 마지막으로, 매우 유사한 아이디어를 제안하는 SAS 2007의 논문에 관심을 가져 주신 Fernando MQ Pereira에게 감사를 표합니다.이를 관련 작업 섹션에 추가했습니다. 모든 피드백을 환영합니다!
r0 및 r1 ). 왼쪽에는 가상 레지스터 각 명령어 사이에 가상 레지스터에서 실제 레지스터로 매핑을 작성했습니다. . 레지스터 할당 자의 작업은 이러한 매핑을 계산 한 다음 명령어를 편집하여 이러한 매핑을 통해 레지스터 참조를 가져 오는 것입니다.
프로그램은 한 지점에서 세 실시간 값 또는 나중에 사용되기 때문에 여전히 보존해야하는 값 : 첫 번째와 두 번째 명령어 사이에 v0 , v1 및 v2 가 라이브입니다. 기계에는 레지스터가 두 개뿐이므로 모든 라이브 값을 보유 할 수 없습니다. 적어도 하나를 흘려야합니다. 이것이 상점으로 작성된 유출 지시 의 이유입니다. 스택 슬롯에 [sp+0] .
레지스터 할당은 얼마나 어렵습니까?
일반적으로 레지스터 할당자는 먼저 프로그램을 분석하여 어떤 값이 어떤 프로그램 포인트에 존재하는지 알아냅니다. 이 활성 정보 및 관련 제약은 조합 최적화 문제를 지정합니다. 특정 값은 어딘가에 저장 각 지점에서 제약 조건은 선택할 수있는 선택을 제한하고 일부 선택은 다른 선택과 충돌 할 수 있습니다 (예 : 두 값이 동시에 레지스터를 차지할 수 없음). 선택 세트는 일부 비용 (데이터에서 운동). 할당자는이 최적화 문제를 해결할뿐만 아니라 레지스터 할당 자에 따라 일종의 휴리스틱을 사용할 수 있습니다.
이것은 어려운 문제입니까? 사실, 이것은 구어체적인 의미에서 어려울뿐만 아니라 NP 완전성입니다. 이것은 최악의 경우 지수 시간 무차별 대입 알고리즘 만 알고있는 다른 NP 문제만큼 어렵다는 것을 의미합니다. 2 삼 그 이유는 문제에 최적의 하부 구조가 없기 때문입니다. 개별적으로 해결할 수있는 상호 작용하지 않는 부품으로 분해 할 수 없습니다. 전체적인 솔루션으로 구성됩니다. 오히려 한 지점에서의 결정은 다른 곳, 잠재적으로 기능 본문의 다른 곳에서 결정에 영향을 미칩니다. 따라서 최악의 경우 우리가 원하는 경우 무차별 대입 검색보다 더 잘할 수 없습니다. n 최적의 솔루션.
최적의 레지스터 할당에 대한 근사치 . 일반적인 것은 선형 스캔 레지스터 할당으로, 코드 크기와 관련하여 거의 선형 시간으로 실행될 수 있습니다. 더 많은 시간을 할애 할 수있는 할당자는 더 복잡합니다. 뛰어난 동료 Julian Seward)는 레지스터에 대한 더 높은 우선 순위 사용을 발견하여 선택 사항을 편집하고 개선 할 수 있습니다.
이러한 알고리즘의 작동 방식에 대한 세부 사항은 여기에서 실제로 중요하지 않습니다. 단, 매우 복잡하고 제대로하기가 어렵습니다. 개념적 수준이나 의사 코드에서 비교적 단순 해 보이는 알고리즘은 실제 제약 조건이 들어 오면서 흥미롭고 미묘한 고려 사항에 빠르게 부딪 힙니다. regalloc.rs 코드베이스는 약 25K 줄의 깊이 알고리즘 Rust 코드입니다. 합리적인 엔지니어라면 여기에 적어도 몇 가지 버그가 포함될 것으로 예상합니다! 여기서 시급함을 더하면 레지스터 할당 버그로 인해 임의 가 발생할 수 있습니다. ) 잘못된 결과. 레지스터 할당자가 프로그램의 모든 데이터 흐름을 “연결”하는 역할을하기 때문입니다. 프로그램에서 임의의 값을 다른 임의의 값으로 교환하면 어떤 일이 일어날 수 있습니다.
정확성 확인 방법
따라서 올바른 레지스터 할당자를 작성하려고합니다. 이런 일을 어떻게 시작하나요?
“정확하다”는 의미입니다. 레지스터 할당 문제에는 좋은 속성이 있습니다. 프로그램은 이전에 및
이후 할당에는 잘 정의 된 의미가 있습니다. 특히 레지스터 할당은 무한 레지스터 머신 에서 실행중인 프로그램을 변환하는 변환으로 생각할 수 있습니다. (원하는만큼 많은 가상 레지스터를 사용할 수있는 곳) 유한 등록 머신 (CPU에 고정 된 레지스터 세트가 있음). 무한 레지스터 머신의 원래 프로그램이 유한 레지스터 머신의 변환 된 (레지스터 할당) 프로그램과 동일한 결과를 산출하면 올바른 레지스터 할당을 달성 한 것입니다.
이 동등성을 어떻게 테스트합니까?
단일 프로그램, 단일 입력 등가
두 프로그램이 있는지 테스트하는 가장 간단한 방법 동등한 것은 그들을 실행하고 결과를 비교하는 것입니다! 단일 프로그램에 대해 임의의 입력을 선택하고 적절한 인터프리터에서 레지스터 할당 버전과 함께 가상 등록 프로그램을 실행한다고 가정 해 보겠습니다. 마지막에 레지스터와 메모리 상태를 비교합니다.
주가 일치합니까? 이것은 하나의 프로그램
에 대해
레지스터 할당자가 이 하나의 프로그램 입력 에 대해 올바른 변환 된 프로그램. 여기에 두 가지 자격이 있습니다. 첫째, 다른 프로그램 입력이 주어지면 레지스터 할당이 정확하다는 것을 반드시 보여주지는 않았습니다. 다른 입력으로 인해 분기가 다른 프로그램 경로로 내려 가고 레지스터 할당자가 해당 경로에 오류가 발생했을 수 있습니다. 둘째, 다른 프로그램에 대해서는 아무것도 보여주지 않았습니다. 단일 프로그램과 레지스터 할당 출력 만 테스트했습니다.
더 많은 샘플 포인트를 취하여 첫 번째 한계 (한 번의 입력에서만 정확성)를 해결합니다. 예를 들어, 1000 개의 임의 프로그램 입력을 선택할 수 있으며 제어 흐름 범위 또는 기타 “흥미로운”동작 (퍼저처럼)을 최대화하려는 일종의 피드백을 사용하여이 임의의 선택을 유도 할 수도 있습니다. 충분한 테스트 사례가 주어지면이 단일 레지스터 할당 결과가 정확하다는 합리적인 확신을 얻을 수 있습니다.
그러나 이것은 여전히 매우 비싸다 : 우리는 N의 샘플 크기를 얻기 위해 전체 프로그램을 N 번 실행하도록 요청합니다. 한 번의 실행도 비용이 많이들 수 있습니다. 예를 들어 레지스터 할당을 수행 한 프로그램은 컴파일러 또는 비디오 게임 일 수 있습니다.
단일 프로그램, For-all-Input Equivalence
프로그램을 실행 할 필요가 전혀 없습니다 레지스터 할당 버전이 올바른지 테스트하려면?
대답은 놀랍도록 간단합니다. 예, 간단히 도메인
을 변경하면 가능합니다. 프로그램이 실행됩니다. 일반적으로 CPU 레지스터는 구체적인 숫자 (예 : 64 비트 값)를 포함하는 것으로 생각합니다. 대신 기호 가 포함 된 경우 어떻게 되나요?
프로그램 값을 기호로 일반화하면 종종 신경 쓰지 않고 입력 측면에서 시스템 상태를 나타낼 수 있습니다. 그 입력이 무엇인지. 예를 들어 다음과 같은 프로그램이 있습니다.
ld v0, [A] ld v1, [B] ld v2, [C] v3, v0, v1 추가 v4, v2, v3 v4 반환
register-allocated to :
ld r0, [A] ld r1, [B] ld r2, [C] add r0, r0, r1 add r0, r2, r0 return r0
기호 추론없이 임의의 정수를 메모리 위치에 저장할 수 있습니다 ㅏ, B 및 C 레지스터 할당 전후의 프로그램 실행을 시뮬레이션하고 불일치를 보지 못합니다. 가능한 모든 값을 반복하지 않는 한 아무것도 증명하지 마십시오. 그러나 세 번의로드 후에 r0 포함 v0 (기호 값으로 무엇이든), r1 포함 v1 및 r2 에 v2 , 그리고 그 r0 에 v3 첫 번째 추가 후 v4 두 번째 추가 후 기호를 일치시켜 대응을 볼 수 있습니다.
이것은 매우 간단한 예이며 아마도이 접근 방식의 통찰력과 힘을 과소 판매합니다. 나중에 추상 해석 에 대해 이야기 할 때 다시 돌아올 것입니다.
어쨌든 우리가 보여준 것은 단일 인스턴스에 대한 것입니다. 레지스터 할당 문제를 해결하기 위해 검증 할 수 있습니다. 올바른 방법으로 프로그램하십시오. 구체적으로 이것은 우리가 생성하는 기계어 코드가 마치 가상 등록 코드를 해석하는 것처럼 실행된다는 것을 의미합니다. 가상 레지스터 코드를 올바르게 생성 할 수 있다면 컴파일러가 올바른 것입니다. 훌륭합니다! 더 갈 수 있을까요?
모든 프로그램 동등성
레지스터 할당자가 항상 할 것임을 사전에 증명할 수 있습니다. 변환 모든 올바른 방식으로 프로그램하십시오. 즉, 프로그램에 대한 입력 값뿐만 아니라 프로그램 자체.
우리가 이것을 증명할 수 있다면, 런타임에 어떤 종류의 검사도 실행할 필요가 없습니다. 프로그램 입력을 추상화하면 프로그램을 실행할 필요가 없습니다. 레지스터 할당이 모든 입력에 대해 정확하다는 것을 알고 있습니다. 유사한 방식으로 레지스터 할당 할 프로그램을 추상화하면 레지스터 할당자를 실행할 필요가 없습니다. 레지스터 할당 자 가 모두 프로그램 및 모두 해당 프로그램에 입력 .
이것이 훨씬 더 어렵다는 것을 상상할 수 있습니다. 실제로 수행되었지만 상당한 증명 엔지니어링 노력이며 적극적인 연구 영역입니다. 기본적으로 컴파일러 알고리즘이 정확하다는 기계 검증 가능한 증명을 작성해야합니다. 이러한 검증 된 올바른 컴파일러가 존재합니다. 예를 들어 CompCert는 C를 여러 플랫폼의 기계 코드로 올바르게 컴파일하는 것으로 입증되었습니다. 안타깝게도 이러한 노력은 필요한 증명 엔지니어링 노력에 의해 크게 제한되므로 이러한 접근 방식은 기본 목표가 아닌 한 컴파일러에서 실현 가능하지 않을 것입니다.
접근 방식 : Checker가있는 할당 자
위의 모든 사항을 고려하여 가장 합리적인 트레이드 오프를 선택합니다. 기호 검사기 출력 레지스터 할당 자의. 이것은 레지스터 할당자가 정확하다는 정적 주장을 할 수는 없지만 올바른지 증명 주어진 컴파일러 실행에 대해; 그리고 이것을 퍼징 오라클로 사용하면 통계적 신뢰 를 구축 할 수 있습니다. 모든 컴파일러 실행에 대해 올바른지 확인합니다.
Register Allocator 확인
전체 흐름은 다음과 같습니다.
레지스터 할당 자 검사기를 시스템에 추가하는 방법에는 두 가지가 있습니다. 첫 번째는 왼쪽에서 “런타임 검사”라고합니다.이 모드에서는 모든 레지스터 할당 자 실행이 검사되고 할당을 사용하는 기계어 코드는 검사기가 확인할 때까지 실행이 허용되지 않습니다 (즉, 컴파일러가 결과를 반환하지 않음). 등가. 이것이 가장 안전한 모드입니다. 검증 된 올바른 할당 자와 동일한 보증을 제공합니다 (위의 “모든 프로그램 동등성”). 그러나 모든 컴파일에 약간의 오버 헤드를 부과하므로 바람직하지 않을 수 있습니다. 이러한 이유로 Cranelift에서 검사기로 레지스터 할당기를 실행하는 것은 지원되는 옵션이지만 기본값은 아닙니다.
두 번째 모드는 퍼징 [ r1=v1 ]에 체커를 적용하는 모드입니다. 워크 플로이며 일반적으로 선호하는 접근 방식입니다 (regalloc.rs에는 임의의 입력 프로그램을 생성하고 각 프로그램에서 검사기를 실행하는 fuzz 대상이 있으며이를 부분적으로 지속적으로 실행하고 있습니다) Google의 oss-fuzz 연속 퍼징 이니셔티브에있는 Wasmtime의 멤버십). 이 모드에서 우리는 검사기를 퍼징 엔진에 대한 응용 프로그램 별 오라클로 사용합니다. 퍼징 엔진이 임의의 프로그램 (테스트 케이스)을 생성 할 때 이러한 프로그램에 대해 레지스터 할당자를 실행하고 결과에 대해 검사기를 실행하고 엔진 할당자가 통과했는지 실패했는지 여부. 퍼 저는 인간 개발자가 디버그 할 수 있도록 실패한 테스트 케이스에 플래그를 지정합니다. fuzzer가 문제를 찾지 않고 오랫동안 실행되면 검사기를 실행하지 않아도 레지스터 할당자가 정확하다는 확신을 가질 수 있습니다. 퍼 저가 길어질수록 자신감이 커집니다. 응용 프로그램 별 오라클은 프로그램 충돌 또는 잘못된 출력과 같은보다 일반적인 퍼저 피드백 메커니즘에 비해 크게 향상되었습니다. 레지스터 할당 자 버그는 잘못된 실행으로 즉시 나타나지 않을 수 있거나 발생하는 경우 결과 충돌에 명백한 단점이 없을 수 있습니다. 실제 잘못 할당 된 레지스터에 연결됩니다. 검사기는 특정 명령어에서 특정 레지스터 사용을 가리키고 “이 레지스터가 잘못되었습니다”라고 말할 수 있습니다. 이러한 결과를 통해 훨씬 더 원활한 디버깅이 가능합니다!
이제 빌드 방법을 살펴 보겠습니다. 특정 레지스터 할당이 올바른지 확인하는 것을 목표로하는 “검사기”. 우리는 단계적으로 솔루션에 도달하고, 먼저 가장 쉬운 사례 인 직선 코드에 대해 추론 한 다음 제어 흐름을 도입합니다. 결국 우리는 선형 시간 (코드 크기에 비례)으로 실행되는 간단한 알고리즘을 갖게되며 그 단순함으로 인해 보증에 대해 합리적으로 확신 할 수 있습니다.
기호 동등성 및 요약 통역
위에서 실행에 대한 일종의 상징적 해석을 설명했음을 기억하십시오. 각 기호가 원래 코드의 가상 레지스터를 나타내는 “기호”값을 포함하는 CPU 레지스터에 대해 추론 할 수 있습니다. 예를 들어 코드
mov v0 , 1 mov v1, 2 add v2, v0, v1 return v2
및 해당 코드의 레지스터 할당 형식
mov r0, 1 mov r1, 2 add r0, r0, r1 return r0
그리고 어쨌든 동등하게 만드는 대체 세트 찾기 :
mov r0, 1 [ r0=v0 ] mov r1, 2 [ r1=v1 ] add r0, r0, r1 [ r0=v2 ] return r0
그러나 우리는 어떻게 해결합니까? r 이러한 대체? 위에서 우리는 값이 아닌 기호에서 작동하는 실행 형태를 암시했습니다. 원래 명령어 세트의 의미를 취하고 대신 기호 값에 대해 작동하도록 재구성 한 다음 코드를 단계별로 실행하여 의 표현을 찾을 수 있습니다. ) 모든 실행
을 한 번에. 이를 상징적 실행이라고하며 아래에 설명 된 몇 가지 개선 사항이 추상 해석의 기초가됩니다 4 . 이것은 매우 강력한 기술입니다!
프로그램 값을 기호로 일반화하면 종종 신경 쓰지 않고 입력 측면에서 시스템 상태를 나타낼 수 있습니다. 그 입력이 무엇인지. 예를 들어 다음과 같은 프로그램이 있습니다.
ld v0, [A] ld v1, [B] ld v2, [C] v3, v0, v1 추가 v4, v2, v3 v4 반환
register-allocated to :
ld r0, [A] ld r1, [B] ld r2, [C] add r0, r0, r1 add r0, r2, r0 return r0
기호 추론없이 임의의 정수를 메모리 위치에 저장할 수 있습니다 ㅏ, B 및 C 레지스터 할당 전후의 프로그램 실행을 시뮬레이션하고 불일치를 보지 못합니다. 가능한 모든 값을 반복하지 않는 한 아무것도 증명하지 마십시오. 그러나 세 번의로드 후에 r0 포함 v0 (기호 값으로 무엇이든), r1 포함 v1 및 r2 에 v2 , 그리고 그 r0 에 v3 첫 번째 추가 후 v4 두 번째 추가 후 기호를 일치시켜 대응을 볼 수 있습니다.
이것은 매우 간단한 예이며 아마도이 접근 방식의 통찰력과 힘을 과소 판매합니다. 나중에 추상 해석 에 대해 이야기 할 때 다시 돌아올 것입니다.
어쨌든 우리가 보여준 것은 단일 인스턴스에 대한 것입니다. 레지스터 할당 문제를 해결하기 위해 검증 할 수 있습니다. 올바른 방법으로 프로그램하십시오. 구체적으로 이것은 우리가 생성하는 기계어 코드가 마치 가상 등록 코드를 해석하는 것처럼 실행된다는 것을 의미합니다. 가상 레지스터 코드를 올바르게 생성 할 수 있다면 컴파일러가 올바른 것입니다. 훌륭합니다! 더 갈 수 있을까요?
모든 프로그램 동등성
레지스터 할당자가 항상 할 것임을 사전에 증명할 수 있습니다. 변환 모든 올바른 방식으로 프로그램하십시오. 즉, 프로그램에 대한 입력 값뿐만 아니라 프로그램 자체.
우리가 이것을 증명할 수 있다면, 런타임에 어떤 종류의 검사도 실행할 필요가 없습니다. 프로그램 입력을 추상화하면 프로그램을 실행할 필요가 없습니다. 레지스터 할당이 모든 입력에 대해 정확하다는 것을 알고 있습니다. 유사한 방식으로 레지스터 할당 할 프로그램을 추상화하면 레지스터 할당자를 실행할 필요가 없습니다. 레지스터 할당 자 가 모두 프로그램 및 모두 해당 프로그램에 입력 .
이것이 훨씬 더 어렵다는 것을 상상할 수 있습니다. 실제로 수행되었지만 상당한 증명 엔지니어링 노력이며 적극적인 연구 영역입니다. 기본적으로 컴파일러 알고리즘이 정확하다는 기계 검증 가능한 증명을 작성해야합니다. 이러한 검증 된 올바른 컴파일러가 존재합니다. 예를 들어 CompCert는 C를 여러 플랫폼의 기계 코드로 올바르게 컴파일하는 것으로 입증되었습니다. 안타깝게도 이러한 노력은 필요한 증명 엔지니어링 노력에 의해 크게 제한되므로 이러한 접근 방식은 기본 목표가 아닌 한 컴파일러에서 실현 가능하지 않을 것입니다.
접근 방식 : Checker가있는 할당 자
위의 모든 사항을 고려하여 가장 합리적인 트레이드 오프를 선택합니다. 기호 검사기 출력 레지스터 할당 자의. 이것은 레지스터 할당자가 정확하다는 정적 주장을 할 수는 없지만 올바른지 증명 주어진 컴파일러 실행에 대해; 그리고 이것을 퍼징 오라클로 사용하면 통계적 신뢰 를 구축 할 수 있습니다. 모든 컴파일러 실행에 대해 올바른지 확인합니다.
Register Allocator 확인
전체 흐름은 다음과 같습니다.
레지스터 할당 자 검사기를 시스템에 추가하는 방법에는 두 가지가 있습니다. 첫 번째는 왼쪽에서 “런타임 검사”라고합니다.이 모드에서는 모든 레지스터 할당 자 실행이 검사되고 할당을 사용하는 기계어 코드는 검사기가 확인할 때까지 실행이 허용되지 않습니다 (즉, 컴파일러가 결과를 반환하지 않음). 등가. 이것이 가장 안전한 모드입니다. 검증 된 올바른 할당 자와 동일한 보증을 제공합니다 (위의 “모든 프로그램 동등성”). 그러나 모든 컴파일에 약간의 오버 헤드를 부과하므로 바람직하지 않을 수 있습니다. 이러한 이유로 Cranelift에서 검사기로 레지스터 할당기를 실행하는 것은 지원되는 옵션이지만 기본값은 아닙니다.
두 번째 모드는 퍼징 [ r1=v1 ]에 체커를 적용하는 모드입니다. 워크 플로이며 일반적으로 선호하는 접근 방식입니다 (regalloc.rs에는 임의의 입력 프로그램을 생성하고 각 프로그램에서 검사기를 실행하는 fuzz 대상이 있으며이를 부분적으로 지속적으로 실행하고 있습니다) Google의 oss-fuzz 연속 퍼징 이니셔티브에있는 Wasmtime의 멤버십). 이 모드에서 우리는 검사기를 퍼징 엔진에 대한 응용 프로그램 별 오라클로 사용합니다. 퍼징 엔진이 임의의 프로그램 (테스트 케이스)을 생성 할 때 이러한 프로그램에 대해 레지스터 할당자를 실행하고 결과에 대해 검사기를 실행하고 엔진 할당자가 통과했는지 실패했는지 여부. 퍼 저는 인간 개발자가 디버그 할 수 있도록 실패한 테스트 케이스에 플래그를 지정합니다. fuzzer가 문제를 찾지 않고 오랫동안 실행되면 검사기를 실행하지 않아도 레지스터 할당자가 정확하다는 확신을 가질 수 있습니다. 퍼 저가 길어질수록 자신감이 커집니다. 응용 프로그램 별 오라클은 프로그램 충돌 또는 잘못된 출력과 같은보다 일반적인 퍼저 피드백 메커니즘에 비해 크게 향상되었습니다. 레지스터 할당 자 버그는 잘못된 실행으로 즉시 나타나지 않을 수 있거나 발생하는 경우 결과 충돌에 명백한 단점이 없을 수 있습니다. 실제 잘못 할당 된 레지스터에 연결됩니다. 검사기는 특정 명령어에서 특정 레지스터 사용을 가리키고 “이 레지스터가 잘못되었습니다”라고 말할 수 있습니다. 이러한 결과를 통해 훨씬 더 원활한 디버깅이 가능합니다!
이제 빌드 방법을 살펴 보겠습니다. 특정 레지스터 할당이 올바른지 확인하는 것을 목표로하는 “검사기”. 우리는 단계적으로 솔루션에 도달하고, 먼저 가장 쉬운 사례 인 직선 코드에 대해 추론 한 다음 제어 흐름을 도입합니다. 결국 우리는 선형 시간 (코드 크기에 비례)으로 실행되는 간단한 알고리즘을 갖게되며 그 단순함으로 인해 보증에 대해 합리적으로 확신 할 수 있습니다.
기호 동등성 및 요약 통역
위에서 실행에 대한 일종의 상징적 해석을 설명했음을 기억하십시오. 각 기호가 원래 코드의 가상 레지스터를 나타내는 “기호”값을 포함하는 CPU 레지스터에 대해 추론 할 수 있습니다. 예를 들어 코드
mov v0 , 1 mov v1, 2 add v2, v0, v1 return v2
및 해당 코드의 레지스터 할당 형식
mov r0, 1 mov r1, 2 add r0, r0, r1 return r0
그리고 어쨌든 동등하게 만드는 대체 세트 찾기 :
mov r0, 1 [ r0=v0 ] mov r1, 2 [ r1=v1 ] add r0, r0, r1 [ r0=v2 ] return r0
명령 집합의 의미는 무엇입니까? 여기에 관련이 있습니까? 레지스터 할당자가 프로그램의 원래 명령
을 수정하지 않기 때문에 밝혀졌습니다. 5 , 우리는 각 명령어를 대부분 임의의 불투명 연산자입니다. 유일한 중요한 정보는 등록 이 읽은 작동) 및 쓰기 (작동 후). 6
유출 [C]시 레지스터 할당 기의 출력을 확인하는 것으로 밝혀졌습니다. 값 및 이동 시기 레지스터 사이의 값, 우리는 유출, 재 장전 및 이동에 대한 특별한 지식이 필요합니다. 따라서 입력 프로그램을 상징적 추론에 중요한 것만 캡처하는 일종의 최소 ISA로 줄일 수 있습니다 (실제 정의는 여기에 있습니다.이 게시물에서는 약간 단순화).
엎지르다: 레지스터에서 스필 슬롯으로 데이터 (가상 레지스터를 나타내는 기호)를 복사합니다., -
새로 고침: 스필 슬롯에서 레지스터로 데이터 복사, -
이동: 한 CPU 레지스터에서 다른 CPU 레지스터로 데이터 이동 (주의 : regalloc이 삽입 한 동작 만, 이동, 원래 입력 프로그램에서 이동하지 않습니다.) -
Op read :: 일부 레지스터를 읽고 다른 레지스터를 쓰는 임의의 연산입니다., read_orig : 쓰기 : write_orig :
마지막 지침이 가장 흥미 롭습니다. 원본 가상 레지스터와 명령어에 대한 등록 후 할당 CPU 레지스터 . 이것에 대한 필요성은 아래에서 더 명확해질 것이지만 직감은 우리가 둘 다
레지스터 할당자가 스캔하는 동안 위의 명령을 생성 할 수 있습니다. 코딩 및 편집; 그 부분은 간단한 번역입니다. 추상 프로그램이 있으면이를 “실행”할 수 있습니다. 상징의 영역을 넘어서. 어떻게할까요? 다음 규칙 :
- 일부를 유지합니다 state , 실제 CPU와 마찬가지로 : 각 CPU 레지스터에 대해, 스택 프레임의 각 위치에 대해 기호 (정수 값 아님). 이 기호는 저장 위치에 현재 해당 레지스터 값이 포함되어 있음을 알고있는 경우 가상 레지스터 이름이 될 수 있습니다.
알 수 없음 일 수도 있습니다. , 체커가 모르는 경우 또는충돌, 값이 여러 가상 레지스터 중 하나 일 수 있습니다. (후자의 두 가지의 차이점은 아래에서 제어 흐름을 논의 할 때 분명해질 것입니다. 지금은 상태를 다음과 같이 추상화하는 것으로 충분합니다. 슬롯에 프로그램 값이 기호 적으로 포함되어 있다는 것을 알고 있거나 아무것도 알지 못합니다.) -
엎지르다,새로 고침또는Move, 소스 위치 (레지스터 또는 스필 슬롯)에서 심볼 상태를 복사합니다. 목적지 위치로. 다시 말해서, 우리는 이러한 명령어가 항상 레지스터 나 메모리 워드의 정수 값을 이동한다는 것을 알고 있습니다. 따라서 가능한 모든 실행에 대해 상징적으로 소스 위치에 대한 지식이 있으면 해당 지식을 대상까지 확장 할 수 있습니다. -
Op, 몇 가지 확인을 한 다음 몇 가지 업데이트를 수행합니다.- 각 읽기 (입력) 레지스터에 대해 지정된 CPU 레지스터 (할당 후 위치)에 저장된 기호 값. 해당 심볼이 원래 명령어가 사용한 가상 레지스터와 일치하면 할당자가 가상 레지스터의 값을 여기에서 사용하도록 적절히 전달한 것이므로 할당은 올바른 (프로그램 데이터 흐름 유지). 그렇지 않은 경우 검사기 오류를 알리고 레지스터 할당 자에서 버그를 찾을 수 있습니다. 우리는 확실히 버그 일 것임을 압니다 (즉, (모든 실행에 대해!) 저장소에 해당 가상 레지스터가 포함되어야한다는 것을 증명 한 경우에만 저장소 위치에 대한 기호를 추적하기 때문입니다.
- 각각 쓰기 (출력) 레지스터, 주어진 CPU 레지스터에 저장된 기호 값을 주어진 (사전 할당) 가상 레지스터로 설정합니다. 즉, 각 쓰기 는 기호를 생성 합니다. 그런 다음이 기호는 소비자에게 도달 할 때까지 유출 / 재 장전 / 이동을 통해 프로그램을 통해 흐릅니다.
그리고 그게 다야! 우리는 직선 코드 (점프가없는 코드)에 대해 이것이 정확히 정확하다는 것을 매우 간단하게 증명할 수 있습니다 – 거짓 긍정이나 거짓 부정을 생성하지 않습니다. 귀납법으로이를 수행 할 수 있습니다. 기호 상태가 명령어 이전에 올 바르면 위의 규칙은 구체적인 프로그램이 수행하는 데이터 이동을 인코딩하고 기호 상태는 동일한 방식으로 업데이트되므로 기호 상태는 다음과 같습니다.
이것은 선형 도 마찬가지입니다. 따라서 직선 코드를 한 번만 스캔하면 매우 빠릅니다. 이것은 레지스터 할당 자로부터 도움 이 있기 때문에 가능합니다. 유출, 재로드 및 할당 자 삽입 이동 등록에 대해 알고 있으며 다른 모든 명령에 대한 사전 및 사후 할당 레지스터를 보유하고 있습니다. 우리가 이것들에 대해 모르고 기계 지침 만 본다면 어떻게해야하는지 생각해보십시오. 이 경우로드, 저장 또는 이동 명령은 할당 자 또는 원래 프로그램에서 올 수 있습니다. 우리는 그들 사이에 연결이있는 연산자의 그래프 만 가질 것이고, 그래프 동형 [ r0=v0 ]을 풀어야 할 것입니다. 문제. 훨씬 더 어렵고 훨씬 느립니다!
이제 끝났나요? 정답은 아닙니다. 우리는 직선 코드만을 고려했습니다. 점프하면 어떻게 되나요?
제어 흐름 조인, 격자 및 반복 데이터 흐름 분석
제어 흐름은 분석을 흥미롭게 만듭니다. 여러 가능성 을 허용하기 때문입니다. if-then-else 패턴이있는 간단한 프로그램을 생각해보십시오 (그 모양 때문에 “제어 흐름 다이아몬드”라고도 함) :
기호 분석이 왼쪽 가지에서 결정한다고 가정 해 보겠습니다. r0 에는 기호 상태가 있습니다. A 및 오른쪽 분기에는 기호 상태 B . 두 경로가 다시 결합 된 후 하위 블록에 어떤 상태가 있습니까?
“술어”를 허용하거나 다른 프로그램 상태에서 조건부로 대답 할 수있는 경우 정확한 대답을 제공 할 수 있습니다. 예를 들어 if 조건이 기호 C 부울 유형이있는 경우 추상적 인 표현 언어를 찾은 다음 if C {A} else {B} .
그러나, 이것은 빨리 견딜 수 없게됩니다. 루프가있는 프로그램은 무제한 기호 표현으로 이어집니다. (이를 보려면 기호 표현이 입력보다 더 큰 크기를 가질 수 있음을 고려하십시오. 따라서 루프 주변의 모든 순환 데이터 종속성은 무한히 큰 기호 표현을 생성 할 수 있습니다.) 비순환 제어 흐름만으로도 경로에 민감한 기호 표현이 가능합니다. 프로그램 크기에 따라 기하 급수적으로 증가 : N 기본 블록 및 루프 없음은 O (2 ^ N) 이러한 블록을 통과하는 경로와 완전히 정확한 기호 표현은 각 경로의 효과를 포착해야합니다.
따라서 대략적인 . 프로그램의 추상적 인 해석은 프로그램의 모든 동작을 손실없이 정확하게 포착 할 필요는 없습니다. 예를 들어, 정수 변수에 대해 가능한 숫자 기호 (양수, 음수, 알 수 없음) 만 추적하는 간단한 추상 해석 분석을 수행 할 수 있습니다. 따라서 다루기 쉬운 상태로 유지하려면 항상 세부 사항을 “요약”하고 삭제하는 것이 좋습니다. 따라서 여러 가능성이있을 때 상태를 “병합”할 수있는 방법을 고려해 보겠습니다.
매우 유용한 방식으로 “병합”이라는 개념을 포착하는 매우 멋진 수학적 객체 인 격자가 있습니다. 격자는 일련의 요소와 부분 순서 로 구성됩니다. 최소 요소 “bottom”및 최대 요소 “top”과 함께 두 요소 (두 피연산자보다 작은 가장 큰 요소)에 대한 “최대 하한”을 찾는 “meet”이라는 연산자 및 “최소 상한”(위의 이중)을 찾는 “join”.
(그림 출처 : Wikimedia, CC BY-SA 3.0)
격자의 매우 유용한 속성은 충족 및 결합의 병합 작업이 교환, 연관 및 재귀 . 이것은 결과가 순서와 반복에 관계없이 “혼합에 던져진”요소 세트에만 의존한다는 공식적인 방법입니다. 즉, 많은 요소들의 만남은 우리가 그것들을 처리하는 순서가 아니라 요소들의 집합 만의 기능입니다.
이것이 어떻게 유용합니까? 특정 분석 상태를 정의하고, 특정 사례에서는 CPU 레지스터와 스필 슬롯에서 기호 가상 레지스터로의 맵을 격자 요소로 정의하고 어떻게 든 상태를 병합하는 “만남 기능”을 정의하면 이 병합 동작을 사용하여 모든 프로그램 포함)에 대해 일종의 프로그램 분석을 구현할 수 있습니다. 무한한 분석 성장없이 루프가있는 사람들! 이를 “meet-over-all-paths”솔루션이라고하며 오늘날 컴파일러가 데이터 흐름 분석을 수행하는 표준 방식입니다. 7
격자는 프로그램 분석에서 “병합”을 유용한 방식으로 설명합니다. 격자 순서 관계 (위 그림의 화살표)는 한 상태가 다른 상태보다 다소 다듬어 진 (다소 많은 지식을 포함 함)을 나타내는 것으로 볼 수 있습니다. 하나는 “가장 큰”또는 “상위”요소에서 시작합니다. 모든 것이 사실 일 수 있습니다. 우리는 아무것도 모릅니다. 그런 다음 점진적으로 더 세련된 상태로 이동합니다. 한 분석 상태는 다른 상태에서 배운 모든 제약과 일부 새로운 제약 조건을 캡처하는 경우 다른 상태보다 “작게”정렬됩니다. 따라서 최대 하한을 계산하는 “meet”연산자는 두 입력 모두의 모든 지식을 캡처하는 분석 상태를 제공하며 더 이상은 없습니다. 8
임의 CFG에 대한 분석을 수행하는 일반적인 접근 방식은 다음과 같습니다.
- 분석 상태를 격자 .
- 현재 분석 상태를 추적합니다. 각 프로그램 지점 또는 명령어 사이를 가리 킵니다. 처음에 모든 프로그램 지점의 상태는 “상단”격자 요소입니다. 값이 만나면 격자에서 “아래”요소로 이동합니다.
- 각 명령의 효과를 처리하여 사전 프로그램 지점에서 사후 프로그램 지점의 상태를 계산합니다.
- 분석 상태가 제어 흐름 에지에 도달하면 에지를 통해 상태를 전파하고 다른 모든 가장자리에서 들어오는 상태와 만나 . 그러면 대상 블록의 상태를 다시 계산할 수 있습니다.
- “고정 점”루프, 더 이상 변경이 발생하지 않을 때까지 블록 항목 변경시 분석 상태로 업데이트 처리
이러한 방식으로 에 대한 모든 명령어 의미를 충족하는 데이터 흐름 문제에 대한 해결책을 찾습니다. 프로그램을 통한 모든 경로. 완전히 정확하지는 않을 수 있습니다 (즉, 모든 질문에 답하지 않을 수 있음) – 루프를 포함하는 실행에 대해 완전히 정확한 답을 포착하는 것이 종종 불가능하고 상당한 제어 흐름이있는 프로그램에서는 비실용적이기 때문입니다. 사운드 , 분석 결과에서 우리가 주장하는 모든 주장은 옳은.
데이터 흐름 분석 문제로서 레지스터 검사기
이제 모든 프로그램의 레지스터 할당 자 출력을 확인하는 데 필요한 모든 부분이 있습니다. 위에서 우리는 모든 직선 코드에 대해 기계 상태를 상징적으로 모델링 할 수 있다는 것을 보았습니다.이를 통해 제어 흐름이없는 한 레지스터 할당 자 오류를 정확하게 감지 할 수 있습니다 (위음성 및 위양성 없음). 그런 다음 제어 흐름에 대한 일반적인 정적 분석 접근 방식에 대해 논의했습니다. 두 가지를 어떻게 결합 할 수 있습니까?
대답은 우리가 격자 / 기호 레지스터 상태 , 그런 다음 고정 점 데이터 흐름 분석에서 위와 동일한 명령어 별 의미 체계를 살펴 봅니다. 간단히 말해서 각 저장 위치 (CPU 레지스터 또는 스필 슬롯)에 대해 격자가 있습니다.
“알 수 없음”상태는 “상위”격자 값입니다. 이것은 단순히 분석이 아직 수렴되지 않았거나 쓰기가 발생하지 않았기 때문에 레지스터에 무엇이 있는지 알 수 없다는 것을 의미합니다.
“충돌”상태는 “하단”격자 값입니다. 이는 둘 이상의 기호 정의가 병합되었음을 의미합니다. 일종의 예측이나 루프 요약으로 두 가지의 중첩을 나타내려고하기보다는 단순히 포기하고 “나쁜 가치”를 나타내는 상태로 이동합니다. 사용하지 않는 한 검사기 오류
가 아닙니다 . , 언제든지 좋은 값으로 덮어 쓸 수 있습니다. 그러나 값이 명령어 소스로 사용되면 오류 플래그를 지정합니다.
따라서 meet 기능은 매우 간단합니다. 동일한 레지스터가 아닌 경우 두 레지스터가 “충돌”상태가됩니다. “unknown”은 무엇이든 만나서 무엇이든 생산합니다. “충돌”은 전염성이 있습니다. “충돌”이있는 다른 주를 만나는 것은 “충돌”상태로 남아 있다는 의미입니다.
위에서 언급 한 분석 상태는 맵 레지스터 및 스필 슬롯에서 기호 상태로; 단순한 상징적 상태가 아닙니다. 따라서 우리의 격자는 실제로 각 개별 저장 위치의 상태의 산물이며 기호를 조각으로 만납니다. (결과 맵에는 모든 충족 입력에 나타나는 키에 대한 항목 만 포함됩니다. 즉, 도메인의 교차점을 사용합니다.)
분석 상태 및 충족 기능이 정의 된 상태에서 데이터 흐름 분석 루프를 실행하고 수렴하고 오류를 찾습니다. 그리고 우리는 끝났습니다!
그리고 그게 다입니다! 9
효과 : 버그를 찾을 수 있습니까?
짧은 대답은 예, 꽤 미묘한 버그를 찾을 수 있다는 것입니다!
regalloc.rs 검사기의 이점은 두 가지입니다 :
- 실제 버그를 발견했습니다. 위의 예에서 참조 유형 (정확한 GC 루팅) 지원에 개념적 오류가있었습니다. 특정 경우에 스필 슬롯이 포인터 유형 값에 할당되었지만 사용되지 않은 경우 스택 맵에 추가 될 수 있습니다 (목록 GC에 제공되는 포인터 유형 스필 슬롯). 이 버그가 발생하려면 특정 상황이 필요합니다. 가상 레지스터에 스필 슬롯을 할당하기로 결정한 레지스터 압력이 충분해야하지만 실제로 수행 할 필요가없는 (드문) 코드 경로에 도달해야합니다. 레지스터를 사용할 수 있기 때문에 유출. 적어도 SpiderMonkey의 WebAssembly 테스트 스위트에서 Cranelift 백엔드를 구동하는 꽤 광범위한 테스트에도 불구하고 GC (Wasm 참조 유형)의 다른 손으로 작성한 테스트에서는이를 달성하지 못했습니다. 퍼 저는 전체 커버리지를 향해 운전하고이 드문 코드 경로를 입력 한 다음 검사기가 오류를 발견하도록 허용했습니다.
- 신규 개발 할당자를 등록합니다. 선형 스캔 할당 자 (참조 유형 / 정확한 GC 루팅 지원이 역 추적 할당 자보다 약간 늦음)를 개발하는 동안 피드백은 검사기가 많은 실제 문제를 발견하고 더 빠르고 확실하게 진행할 수 있음을 나타냅니다.
레지스터의 개별 실행을 확인하는 체커에 대한 사전 작업을 찾는 것은 놀랍게도 어렵습니다. 할당 자. 완전히 검증 된 여러 컴파일러가 존재합니다. CompCert와 CakeML은 사실적인 언어 (각각 C와 ML)를 컴파일 할 수있는 두 가지입니다. 이러한 컴파일러는 알고리즘 자체가 올바른 것으로 입증되었다는 점에서 레지스터 할당자를 완전히 검증했습니다. 개별 컴파일 결과에 대해 검사기를 실행할 필요가 없습니다. 이를 달성하기위한 엔지니어링 노력은 체커를 작성하는 것보다 훨씬 큽니다 (후자의 경우 ~ 700 줄의 Rust).
레지스터 할당자를 올바르게 증명하는 CakeML의 접근 방식은 Tan et al. “검증 된 CakeML 컴파일러 백엔드”(J. Func Prog 29, 2019)에서. 유효한 그래프 색상 또는 “순열”(프로그램 값을 저장 슬롯에 매핑)이 제공되는 한 컴파일이 정확하도록 문제를 훌륭하게 고려한 것으로 보입니다. 이를 통해 할당 자 (그래프 채색 알고리즘)의 세부 사항과는 별도로 핵심 문제 (할당 전후의 데이터 흐름 동등성)에 대한 추론을 할 수 있습니다.
검증 생산 컴파일러도 존재합니다. e, Crellvm은 변형 된 프로그램과 함께 (기계 검사 가능) 정확성 증명을 생성하는 여러 LLVM 패스의 최근 확장입니다. 이 접근법은 개념적으로 레지스터-할당 자 검사기와 동일한 수준에 있습니다. 단일 컴파일러 실행의 유효성을 검사하지만 전체 사전 정확성 증명보다 빌드하기가 훨씬 쉽습니다. 그러나 이러한 노력은 아직 레지스터 할당을 처리하는 것으로 보이지 않습니다.
Rideau와 Leroy는 “Validating Register Allocation and Spilling”(CC 2010)은“번역 확인 검사”에서“일회성”정확성 증명을 분리하고 후자를 제공하는 유사한 분류를 설명합니다. 그러나 그들의 유효성 검사기는 해결해야하는 동등 제약 집합을 구축하는 상당히 복잡한 전달 함수를 정의합니다. 유효성 검사기는 할당 자의 힌트, 특히 원래 프로그램의 저장,로드 및 이동과 구별되는 wrt 유출, 재로드 및 삽입 된 이동을 활용하지 않는 것으로 보입니다. 이러한 힌트가 없으면 훨씬 더 일반적이고 복잡한 데이터 흐름 동등성 체계가 필요합니다.
Nandivada et al. “A Framework for End-to-End Verification and Evaluation of Register Allocators”(SAS 2007)에서는 물리적 레지스터 내용 (가상 레지스터 또는 “의사”기호)이 post-register로 인코딩되는 우리의 검사기와 매우 유사한 시스템을 설명합니다. regalloc IR을 입력합니다. 그들의 typechecker는 우리의 checker가 할 수있는 것과 동일한 종류의 regalloc 오류를 발견 할 수 있습니다. 따라서 그들의 접근 방식은 우리의 접근 방식과 거의 동일합니다. 주요 차이점은 문제를 전용 IR에서 유형 검사로 인코딩하는 것이 아니라 독립형 정적 분석으로 인코딩한다는 것입니다.
결론
지난 1 년 동안 Cranelift의 새로운 백엔드의 모든 부분을 개발하기 위해 수행 한 작업을 설명하는 3 개의 포스트 시리즈 (1, 2)! 개인적으로 매우 흥미롭고 교육적인 여행이었습니다. 더 일반적으로 가르치고 연구하는 “중간 엔드”(IR 수준 최적화)와는 별개로 컴파일러 백엔드에서 해결해야 할 완전히 새로운 흥미로운 문제의 세계를 발견했습니다. 또한 빠른 컴파일에 대한 초점은 흥미로운 반전입니다. 내가 생각하는 것은 충분히 연구되지 않았다. 점점 더 복잡한 기술을 통해 더 높은 분석 정밀도와 더 나은 생성 된 코드를 정당화하는 것은 쉽습니다. 빠른 컴파일을위한 디자인 트레이드 오프에서 찾을 수있는 이점은 더 주관적이고 작업 부하에 더 많이 의존합니다.
이 글이 우리의 디자인 결정에 들어간 생각의 일부를 밝혔기를 바랍니다. 그러나 우리의 일은 결코 끝나지 않습니다! 2021 년 Cranelift 작업 로드맵에는 더 높은 컴파일러 성능과 더 나은 코드 품질을 달성하기 위해 논의한 많은 아이디어가 나열되어 있습니다. 나는 내년에 이것들을 더 탐구하게되어 기쁩니다. 더 많은 블로그 게시물을 올릴 수도 있습니다. 그때까지 즐거운 컴파일!
이 게시물에 대한 토론을 원하시면이 스레드의 Zulip 인스턴스에 자유롭게 참여하십시오.
내가 통합 한 몇 가지 제안에 대해 Reddit의 / u / po8에게 감사드립니다. 몇 가지 제안에 대해 bjorn3에게도 감사드립니다. 마지막으로, 매우 유사한 아이디어를 제안하는 SAS 2007의 논문에 관심을 가져 주신 Fernando MQ Pereira에게 감사를 표합니다.이를 관련 작업 섹션에 추가했습니다. 모든 피드백을 환영합니다!
RSS - Posts
