lacc
1.0.0
이것은 내 장난감 프로젝트이며, C로 작성된 C에 대한 컴파일러를 만들기 위해 자체적으로 컴파일 할 수 있습니다.
소스에서 클론 및 빌드하면 바이너리는 bin/lacc 에 배치됩니다.
git clone https://github.com/larmel/lacc.git
cd lacc
./configure
make
make install
기본 구성에는 환경의 기본 프로브가 포함되어 있으며 컴파일하는 기계 및 LIBC를 감지합니다. 인정 된 플랫폼에는 현재 Glibc 또는 Musl과 OpenBSD가 포함 된 Linux가 포함됩니다.
stddef.h 및 stdarg.h 와 같은 특정 표준 라이브러리 헤더에는 본질적으로 컴파일러 특이 적이며 Lib/에 따라 LACC에 대해 특별히 제공되는 정의가 포함되어 있습니다. 헤더를 설치하지 않고 직접 bin/lacc 직접 사용하려면 --libdir 설정 하여이 폴더를 직접 가리키면 위치를 무시할 수 있습니다.
install 대상은 바이너리 및 헤더를 일반적인 위치로 복사하거나 --prefix 또는 --bindir 로 구성됩니다. DESTDIR 설정하는 옵션도 있습니다. 복사 된 모든 파일을 제거하려면 make uninstall .
빌드를 사용자 정의하고 매개 변수를 설치하는 옵션은 ./configure --help 참조하십시오.
명령 줄 인터페이스는 대부분 동일한 플래그 및 옵션의 하위 집합을 사용하여 GCC 및 기타 컴파일러와 유사하게 유지됩니다.
-E Output preprocessed.
-S Output GNU style textual x86_64 assembly.
-c Output x86_64 ELF object file.
-dot Output intermediate representation in dot format.
-o Specify output file name. If not speficied, default to input file
name with suffix changed to '.s', '.o' or '.dot' when compiling
with -S, -c or -dot, respectively. Otherwise use stdout.
-std= Specify C standard, valid options are c89, c99, and c11.
-I Add directory to search for included files.
-w Disable warnings.
-g Generate debug information (DWARF).
-O{0..3} Set optimization level.
-D X[=] Define macro, optionally with a value. For example -DNDEBUG, or
-D 'FOO(a)=a*2+1'.
-f[no-]PIC Generate position-independent code.
-v Print verbose diagnostic information. This will dump a lot of
internal state during compilation, and can be useful for debugging.
--help Print help text.
옵션에 맞지 않는 인수는 입력 파일로 간주됩니다. 컴파일 모드가 지정되지 않으면 LACC는 시스템 링커 /bin/ld 의 래퍼 역할을합니다. 일부 공통 링커 플래그가 지원됩니다.
-Wl, Specify linker options, separated by commas.
-L Add linker include directory.
-l Add linker library.
-shared Passed to linker as is.
-rdynamic Pass -export-dynamic to linker.
예를 들어 호출을 통해 Test/C89/Fact.c를 객체 코드로 컴파일 한 다음 시스템 링커를 사용하여 최종 실행 파일을 생성합니다.
bin/lacc -c test/c89/fact.c -o fact.o
bin/lacc fact.o -o fact
이 프로그램은 테스트 스위트의 일부이며 5를 계산합니다! 재귀 사용 및 답변으로 빠져 나옵니다. 실행 ./fact 와 echo $? 120 인쇄해야합니다.
컴파일러는 C89로 작성되었으며 총 19K 라인의 코드를 계산합니다. C 표준 Libary를 제외하고 외부 의존성은 없으며 일부 시스템 호출은 링커를 호출해야합니다.
구현은 네 가지 주요 부분으로 구성됩니다. 사전 처리기, 파서, 최적화 및 백엔드는 각각 SRC/에 따라 자체 디렉토리에 있습니다. 일반적으로, 각 모듈 (일반적으로 공개 인터페이스를 정의하는 .h 파일과 쌍을 이루는 각 모듈 (a .c 파일)은 주로 자체 하위 트리의 헤더에 따라 다릅니다. 글로벌 레벨에서 공유되는 선언은/lacc/에 있습니다. 여기에서는 핵심 데이터 구조와 전처리, 구문 분석 및 코드 생성 사이의 인터페이스를 찾을 수 있습니다.
전처리에는 파일 읽기, 토큰 화, 거시적 확장 및 지침 처리가 포함됩니다. 사전 처리기의 인터페이스 struct token peek(0) , peekn(1) , consume(1) , try_consume(1) 및 next(0) 입니다. 이들은 포함/lacc/token.h로 정의됩니다.
입력 처리는 이러한 기능을 호출하여 더 많은 입력을 소비하기 위해 구문 분석기에 의해 완전히 게으르게 수행됩니다. 전처리 토큰의 완충제는 전망대를 위해 보관되며 앞으로 엿볼 때 주문형으로 채워집니다.
코드는 기본 블록의 제어 흐름 그래프로 모델링되며 각각의 3 주소 코드 명령문을 보유합니다. 각 외부 변수 또는 기능 정의는 struct definition 객체로 표시되며 단일 struct symbol 와 코드를 고정하는 CFG를 정의합니다. 중간 표현을 뒷받침하는 데이터 구조는/lacc/ir.h 포함에서 찾을 수 있습니다.
중간 표현을 시각화하는 것은 별도의 출력 목표입니다. -DOT 옵션이 지정되면 DOT 형식의 텍스트 파일이 출력으로 생성됩니다.
bin/lacc -dot -I include src/backend/compile.c -o compile.dot
dot -Tps compile.dot -o compile.ps
아래는 SRC/Backend/Compile.c에서 발견 된 함수의 예이며 전체 그래프의 슬라이스를 보여줍니다. 전체 출력은 표시된 명령을 실행하여 Postscript 파일로 생성 될 수 있습니다.
그래프의 각 기본 블록에는 표현식 ( struct expression )을 변수 ( struct var )에 할당하는 가장 일반적으로 IR_ASSIGN 문 목록이 있습니다. 표현식에는 또한 가변적 인 피연산자가 포함되어 있으며, 이는 메모리 위치, 주소 및 불균형 포인터를 높은 수준으로 인코딩 할 수 있습니다.
DIRECT 피연산자는 *(&symbol + offset) 의 메모리를 나타냅니다. 여기서 기호는 변수이거나 메모리의 특정 위치 (예 : 스택)에서 임시입니다.ADDRESS 피연산자는 DIRECT 피연산자 (&symbol + offset) 의 주소를 정확하게 나타냅니다.DEREF Operands는 기호 (포인터 유형이어야 함)를 가리키는 메모리를 나타냅니다. 표현식은 *(symbol + offset) 이며 어셈블리에 매핑하려면 두 개의로드 작업이 필요합니다. DEREF 및 DIRECT 변수 만 할당 또는 L- 값을 대상으로 할 수 있습니다.IMMEDIATE 피연산자는 일정한 숫자 또는 문자열을 유지합니다. 즉각적인 오페라의 평가는 자동으로 일정한 접는 기능을 수행합니다.파서는 손으로 코딩 된 재귀 하강이며, 주요 부품은 SRC/Parser/Declaration.c, SRC/Parser/Initializer.c, SRC/Parser/Expression.c 및 SRC/Parser/station.c로 분할됩니다. 현재 기능 제어 흐름 그래프 및 해당 그래프의 현재 활성 기본 블록은 각 생산에 대한 인수로 전달됩니다. 그래프는 새로운 3 주소 코드 지침이 현재 블록에 추가되면서 점차 구성됩니다.
다음 예제는 비트 또는 표현식에 대한 구문 분석 규칙을 보여 주며, 이는 현재 블록에 새로운 IR_OP_OR 작업을 추가합니다. eval_expr 의 논리는 오류가 발생하는 경우 종료 된 피연산자 value 과 block->expr 유효하도록합니다.
static struct block *inclusive_or_expression(
struct definition *def,
struct block *block)
{
struct var value;
block = exclusive_or_expression(def, block);
while (try_consume('|')) {
value = eval(def, block, block->expr);
block = exclusive_or_expression(def, block);
block->expr = eval_or(def, block, value, eval(def, block, block->expr));
}
return block;
}
최신 평가 결과는 항상 block->expr 에 저장됩니다. 분기는 새로운 기본 블록을 인스턴스화하고 포인터를 유지함으로써 수행됩니다. 각 기본 블록에는 다른 블록에 대한 True 및 False Branch 포인터가 있으며, 이는 분기 및 Gotos가 모델링되는 방식입니다. 어떤 시점에서도 구문 트리 구조가 구축되지 않습니다. 그것은 재귀에 암시 적으로 만 존재합니다.
제어 흐름 그래프를 구축하기위한 주요 동기는 데이터 흐름 분석 및 최적화를 수행 할 수 있다는 것입니다. 여기의 현재 기능은 여전히 제한되어 있지만 추가 및 고급 분석 및 최적화 패스로 쉽게 확장 할 수 있습니다.
Liveitive Analysis는 모든 진술에서 나중에 읽을 수있는 모든 진술에서 파악하는 데 사용됩니다. DataFlow 알고리즘은 기호를 나타내는 비트 마스크를 사용하여 구현되어 1-63입니다. 결과적으로 최적화는 64 개 미만의 변수를 가진 함수에서만 작동합니다. 포인터 별명 분석이 없으므로 알고리즘은 매우 보수적이어야합니다 (아직).
Livendes 정보를 사용하여 Dead Store 제거를 수행하는 변환 패스는 IR_ASSIGN 노드를 제거하여 아무것도하지 않아 생성 된 코드의 크기를 줄일 수 있습니다.
텍스트 어셈블리 코드, 엘프 객체 파일 및 중간 표현의 세 가지 백엔드 대상이 있습니다. 파서에서 산출 된 각 struct definition 객체는 SRC/백엔드/compile.c 모듈로 전달됩니다. 여기서는 중간 제어 흐름 그래프 표현에서 하위 레벨 IR로 매핑하여 코드를 X86_64 명령어를 직접 나타내는 것으로 줄입니다. 이에 대한 정의는 src/backend/x86_64/encoding.h에서 찾을 수 있습니다.
프로그램 시작시 설정된 기능 포인터에 따라 지침은 ELF 백엔드 또는 텍스트 어셈블리로 전송됩니다. 따라서 텍스트 어셈블리를 출력하기위한 코드는 매우 간단하며 낮은 레벨 IR 명령과 GNU 구문 어셈블리 코드 간의 매핑 만 있으면됩니다. src/backend/x86_64/assemble.c를 참조하십시오.
DOT 출력은 생성하기 위해 낮은 레벨 IR이 필요하지 않은 별도의 파이프 라인입니다. 컴파일 모듈은 단순히 CFG를 SRC/백엔드/GraphViz/DOT.C로 전달합니다.
테스트는 LACC 및 시스템 컴파일러 (CC)로 컴파일 된 프로그램의 런타임 출력을 비교하여 수행됩니다. 검증에 사용되는 작은 독립형 프로그램 모음은 테스트/ 디렉토리에서 찾을 수 있습니다. 테스트는 Check.sh를 사용하여 실행되며, 이는 전처리, 어셈블리 및 ELF 출력의 유효성을 유효하게합니다.
$ test/check.sh bin/lacc test/c89/fact.c
[-E: Ok!] [-S: Ok!] [-c: Ok!] [-c -O1: Ok!] :: test/c89/fact.c
컴파일러의 완전한 테스트는 자체 주최 버전의 LACC에서 모든 테스트 사례를 거쳐 수행합니다.
make -C test
이것은 먼저 이미 제작 된 bin/lacc 사용하여 bin/bootstrap/lacc 생산하며, 결국 bin/selfhost/lacc 구축하는 데 사용됩니다. 부트 스트랩과 셀프 호스트 단계 사이에서 중간 객체 파일은 평등과 비교됩니다. 모든 것이 올바르게 작동하면이 단계는 동일한 바이너리를 생산해야합니다. 모든 테스트가 셀프 호스트 바이너리를 통과 할 때 컴파일러는``좋은 ''것입니다. 이것은 모든 커밋마다 항상 녹색이어야합니다.
가능한 모든 사례를 다루는 좋은 테스트 스위트를 제시하기는 어렵습니다. 버그를 제거하기 위해 CSMITH를 사용하여 검증에 적합한 임의의 프로그램을 생성 할 수 있습니다.
./csmith.sh
CSMITH.SH 스크립트는 CSMITH를 실행하여 무언가가 테스트 하네스에 실패 할 때까지 무한한 임의 프로그램 순서를 생성합니다. 일반적으로 실패없이 수천 개의 테스트를 실행합니다.
CSMITH에 의해 생성 된 프로그램에는 일련의 글로벌 변수가 포함되어 있으며, 이에 대한 돌연변이를 만드는 기능. 결국, 모든 변수의 전체 상태의 체크섬은 출력입니다. 그런 다음이 체크섬을 다른 컴파일러와 비교하여 불일치 또는 버그를 찾을 수 있습니다. CSMITH가 생성 한 예제 프로그램은 LACC에 의해 올바르게 편집 된 Doc/Random.c를 참조하십시오.
버그가 발견되면 Creduce를 사용하여 최소한의 재현을 만들 수 있습니다. 이것은 일반 테스트 스위트에서 새로운 테스트 사례로 끝납니다.
컴파일러 자체를 빠르게 만들기 위해 약간의 노력이 이루어졌습니다 (생성 된 코드는 여전히 최적화되지 않았지만). 성능 벤치 마크 및 정확성 테스트 역할을 통해 SQLITE 데이터베이스 엔진을 사용합니다. 소스 코드는 200k 이상의 라인 (주석 및 흰색 공간 포함)에 걸친 단일 ~ 7MB (7184634 바이트) 큰 C 파일로 분산되며, 이는 컴파일러를 테스트하는 응력 테스트에 적합합니다.
다음 실험은 I5-7300U CPU가있는 노트북에서 실행되었으며, SQLITE3의 버전 3.20.1을 컴파일했다. 측정은 컴파일에서 객체 코드 (-c)에서 이루어집니다.
LACC로 파일을 컴파일하는 데 200ms 미만이 걸리지 만 시간보다는 CPU 사이클 및 지침의보다 정확한 샘플링을 살펴 봅니다. 하드웨어 성능 카운터 데이터는 perf stat 및 valgrind --trace-children=yes 함께 수집됩니다. Valgrind에서는 GCC를 실행하는 동안 컴파일러 자체 ( cc1 실행 파일)의 기부금 만 계산하고 있습니다.
LACC의 숫자는 make CC='clang -O3 -DNDEBUG' bin/lacc 에 의해 생성 된 최적화 된 빌드에서 나온 것입니다. 각 컴파일러는 인수 -c sqlite/sqlite3.c -o foo.o 로 호출됩니다.
| 컴파일러 | 사이클 | 지침 | 할당 | 바이트가 할당되었습니다 | 결과 크기 |
|---|---|---|---|---|---|
| LACC | 412,334,334 | 619,466,003 | 49,020 | 24,244,107 | 1,590,482 |
| TCC (0.9.27) | 245,142,166 | 397,514,762 | 2,909 | 23,020,917 | 1,409,716 |
| GCC (9.3.0) | 9,958,514,599 | 14,524,274,665 | 1,546,790 | 1,111,331,606 | 1,098,408 |
| 클랜 (10.0.0) | 4,351,456,211 | 5,466,808,426 | 1,434,072 | 476,529,342 | 1,116,992 |
TCC에 더 가까이 다가 가기 위해 수행 할 작업이 아직 이루어 졌는데, 이는 아마도 가장 빠른 C 컴파일러 중 하나 일 것입니다. 그럼에도 불구하고 우리는 TCC 성능과 합리적인 거리에 있으며 GCC와 Clang보다 훨씬 우수합니다.
위 표에서 LACC에 의해 생성 된 SQLITE 객체 파일의 크기는 다른 컴파일러에서 생성 된 것보다 크기 때문에 덜 최적의 코드를 출력 함을 나타냅니다.
LACC 및 GCC에서 생성 된 코드의 상대적 품질을 비교하기 위해 GCC에 의해 구축 된 이진과 셀프 호스트 바이너리에 의해 실행되는 동적 지침의 수를 살펴볼 수 있습니다. 우리는 위와 동일한 테스트를 실행하여 SQLITE를 객체 코드로 컴파일합니다. 테스트 대상은 GCC에 의해 생성 된 기본 컴파일러 빌드 ( bin/lacc )와 LACC에 의해 생성 된 Selfhost Binary ( bin/selfhost/lacc )입니다. 이 두 대상은 최적화를 활성화하고 NDEBUG 정의하지 않고 생성됩니다.
| 컴파일러 | 사이클 | 지침 |
|---|---|---|
| LACC | 946,315,653 | 1,481,608,726 |
| LACC (Selfhost) | 1,417,112,690 | 2,046,996,115 |
자체 호스트 바이너리는 GCC에 의해 구축 된 컴파일러보다 SQLITE를 컴파일하는 데 느리므로 LACC가 실제로 비효율적 인 코드를 생성 함을 보여줍니다. 더 나은 교육 선택으로 백엔드를 개선하는 것이 우선 순위 이므로이 숫자는 앞으로도 더 가까워 질 것입니다.
x86_64를 타겟팅하는 C 컴파일러를 구축하는 데 유용한 리소스입니다.
