GBFC가 Brainfuck용 AOT·JIT 컴파일러를 공개했다

GBFC — General BrainFuck Compiler

GBFC는 Rust로 작성된 Brainfuck(.b) 및 Brainfuck++ 컴파일러다. LLVM이나 어셈블러, 외부 크레이트를 사용하지 않고 기계어를 직접 생성하며, 인터프리터가 아니다.

• AOT 컴파일은 약 1KB 크기의 독립형 정적 ELF 실행 파일을 생성한다. libc와 링커가 필요 없다.
• JIT 컴파일은 컴파일러 프로세스 안에서 같은 기계어를 실행한다. 익명 메모리를 사용하며 권한을 RW에서 RX로 바꾸고, W+X 권한은 사용하지 않는다.
• 대상 플랫폼은 Linux x86_64다. 다른 대상을 추가할 수 있도록 코드를 구성했다.

사용법

cargo build --release # produces target/release/gbfc gbfc prog.b # AOT: ./prog (ELF) gbfc prog.b -o out # AOT with an explicit output name gbfc -j prog.b # JIT: compile and run immediately gbfc -bfpp prog.b # same, reading the source as Brainfuck++ gbfc --emit ir prog.b # print the optimized IR gbfc --emit bin prog.b # raw machine code (objdump -D -b binary -mi386:x86-64)

• -bf / -bfpp / -bf++: 소스 언어를 선택한다. 기본값은 Brainfuck인 -bf다.
• -O0 / -O1: 최적화를 끄거나 켠다. 기본값은 -O1이다.
• --tape-size N: 테이프의 셀 수를 지정한다. 기본값은 1048576이다.
• --eof zero|unchanged|minus1: EOF에서 , 명령을 실행했을 때의 결과를 지정한다. 기본값은 zero다.
• --bounds-check: 테이프 범위를 벗어난 접근에서 트랩을 발생시킨다.
• --debug-tape: 각 연산 뒤에 단계 번호, 포인터, 셀을 표준 오류(stderr)로 출력한다.
• --fuel N: 컴파일 시간 평가의 단계 예산을 지정한다. 기본값은 100000000이며 0은 평가를 끈다.
• --target x86_64-linux: 대상을 지정한다. 기본값은 호스트 시스템이다.
• -v: 통계를 표준 오류로 출력한다.

의미와 동작 조건

셀은 8비트이며 값은 256을 법으로 순환한다. +-<>[].,에 해당하지 않는 모든 바이트는 주석이다. 짝이 맞지 않는 대괄호는 line:column 형식으로 보고한다. --bounds-check를 지정하지 않으면 테이프 범위를 검사하지 않으며, 범위를 벗어나면 SIGSEGV로 종료된다.

정상 종료 시 실행 파일은 0을 반환한다. 범위 검사가 실패하면 1, EOF가 아닌 읽기 오류나 쓰기 실패 등 I/O 오류가 발생하면 2를 반환하고 두 실패 모두 표준 오류에 메시지를 출력한다. 중단된 시스템 호출은 다시 시도하며, 부분 쓰기는 완료될 때까지 이어서 처리한다.

--debug-tape는 실행된 각 연산 뒤에 표준 오류로 한 줄을 추가한다. 형식은 step 0000000000000001 p=0000000000000000 tape=0000000000000003이며, 단계 번호와 데이터 포인터, 포인터가 가리키는 셀을 16진수로 표시한다. 이 옵션은 디버깅용이며, 사용하면 프로그램 실행이 몇 자릿수 규모로 느려진다.

지원 언어

-bf는 Brainfuck을 선택한다. -bfpp 또는 -bf++는 파일 및 소켓 명령을 추가한 Brainfuck++를 선택한다. 두 언어에서 Brainfuck 명령은 똑같이 동작하며, Brainfuck 모드에서는 추가 문자가 주석으로 처리된다.

• #: 파일이 열려 있지 않으면 현재 셀에 저장된 값만큼 떨어진 위치의 0으로 끝나는 경로를 사용해 파일을 연다. 파일이 없으면 새로 만들고 읽기·쓰기로 연다. 성공하면 셀은 0x00, 실패하면 0xFF가 된다. 파일이 이미 열려 있으면 닫는다.
• :: 파일에서 1바이트를 읽어 현재 셀에 저장한다. EOF에서는 0x00을 저장한다.
• ;: 현재 셀의 값을 파일에 쓴다.
• %: 연결이 열려 있지 않으면 현재 셀에 저장된 값만큼 떨어진 위치의 0으로 끝나는 점 표기 IPv4 주소와, 그 뒤에 오는 2바이트 빅엔디안 포트를 사용해 TCP 연결을 연다. 성공하면 셀은 0x00, 실패하면 0xFF가 된다. 연결이 이미 열려 있으면 닫는다.
• ^: 현재 셀의 값을 연결에 쓴다.
• !: 연결에서 1바이트를 읽어 현재 셀에 저장한다. 상대편이 연결을 닫았으면 0x00을 저장한다.

한 번에 열 수 있는 파일은 최대 하나, 연결도 최대 하나다. 새로 연 파일은 처음부터 읽는다. 파일 및 소켓 오류는 다른 I/O 오류와 마찬가지로 종료 상태를 2로 설정한다.

최적화

-O1은 다음 최적화 단계를 순서대로 수행한다. -O0은 소스 명령마다 명령어 하나를 생성하며, 이 최적화들은 적용하지 않는다.

• 컴파일 시간 실행: 프로그램의 앞부분을 컴파일러 안에서 0으로 초기화된 테이프에 실행하며, 최대 --fuel 단계까지 진행한다. 출력은 상수 Write로 바꾸고 테이프 상태는 상수 저장으로 반영하며, 나머지 프로그램은 실행 시 처리하도록 남긴다.
• 연속 명령 결합: 같은 명령이 연속된 부분(+++, >>>)을 하나의 연산으로 합친다. 포인터 이동으로 나뉜 연속 명령도 포함한다.
• 포인터 이동 지연: 포인터 이동을 즉시 생성하지 않고 셀 오프셋에 반영한다. 따라서 >+<는 덧셈 하나가 되고, 연속된 이동도 하나로 합쳐진다.
• 상수 전파와 죽은 코드 제거: 컴파일러가 값이 알려진 셀을 추적한다. 값이 0으로 알려진 셀을 검사하는 루프는 제거하고, 참으로 알려진 조건 아래의 블록은 인라인 처리하며, 불필요한 저장은 없앤다. 루프 안에서 쓰인 셀은 알려진 값 상태를 잃는다.
• 0으로 만드는 루프를 set으로 변환: [-], [+] 및 값 하나를 계수가 1인 셀로 이동하는 루프를 단순 저장으로 바꾼다.
• 복사·곱셈 루프를 muladd로 변환: [->+<], [->++>---<<] 등은 원본 셀을 한 번 불러온 뒤 배율이 적용된 덧셈을 이어서 수행하는 형태로 바꾼다. 루프의 계수는 256을 법으로 한 루프 단계에서 계산하며, 전체 연산은 하나의 If 가드로 감싼다.
• 스캔 루프를 16바이트 SSE2 탐색으로 변환: [>]와 [<]를 pcmpeqb로 반복마다 16개 셀을 비교하고 bsf 또는 bsr로 0바이트를 찾는 단일 연산으로 바꾼다.

백엔드에는 여기에 더해 몇 가지 작은 명령어 수준의 개선이 있다. 루프 조건에서 산술 플래그를 재사용하고, 곱셈 묶음마다 원본 셀을 한 번만 불러오며, 가장 짧은 점프와 주소 지정 형식을 사용한다. 또한 I/O를 버퍼링하고 포인터가 이동할 수 있는 지점에서만 범위 검사를 한다. 이 개선들은 각각 따로 나열하지 않았다.

컴파일 시간 평가

-O1에서 컴파일러는 코드를 생성하기 전에 0으로 초기화된 테이프에서 프로그램을 최대 --fuel 단계까지 실행한다. 입력을 알 수 없는 첫 번째 , 명령에 도달하거나 예산을 다 쓰거나 테이프 범위를 벗어나면 멈춘다. 그때까지 계산한 내용은 실행 파일에 반영된다. 출력은 상수 Write 연산이 되고, 테이프 내용은 상수 저장이 되며, 나머지는 실행 시간에 처리된다. 이 실행 파일은 표준 입력이 무엇이든 같은 방식으로 동작한다.

• 컴파일 시간은 예산에 따라 늘어나며 단계당 약 2ns다. 기본값인 100,000,000단계는 최대 약 0.2초, --fuel 4000000000은 최대 약 8초가 걸린다.
• 끝나지 않거나 예산보다 오래 실행되는 프로그램은 컴파일할 때마다 예산 전체를 소모한다.
• 상수 출력은 최대 1MiB까지 바이너리에 포함한다. 이를 넘는 출력은 실행 시간에 생성한다.
• 입력을 읽는 프로그램은 첫 번째 , 이후부터는 이득을 얻지 못한다.
• 중첩 루프 내부에서 멈추는 바람에 프로그램 크기가 두 배를 넘게 커질 경우 이 최적화 단계를 건너뛴다.
• --fuel 0 또는 -O0을 지정하면 이 단계를 끈다.

설계

.b -> parser -> IR -> opt -> IR -> backend/<arch> -> CodeImage -+-> format/<os> -> ELF (AOT) +-> jit (JIT)

• ir.rs: Add/Set/MulAdd/Move/In/Out/Write/Loop/If/Scan과 Brainfuck++의 FOpen/FClose/FIn/FOut/NetOpen/NetClose/NetIn/NetOut을 포함하는 IR이다. 각 셀 연산은 데이터 포인터 기준 오프셋을 가진다. Write는 컴파일 시간 평가에서 나온 상수 출력이며, Scan은 0인 셀을 한 칸씩 찾아가는 검색([>], [<])이다.
• parser.rs: 바이트 단위로 IR을 파싱한다. Lang::{Bf, Bfpp}가 명령어 집합을 선택한다.
• opt.rs: 연속 명령 결합, 루프와 if를 넘나드는 포인터 이동 지연, 죽은 코드 제거를 포함한 상수 전파, [-]를 set으로 변환, 복사·곱셈 루프를 muladd로 변환, 스캔 루프를 scan으로 변환한다.
• peval.rs: 프로그램 앞부분을 컴파일 시간에 평가한다.
• target.rs: Arch와 Os, 시스템 호출 번호(Syscalls)를 다룬다.
• backend/mod.rs: CodeGen 트레이트, CodegenOptions, EntryKind::{Function, Process}를 정의한다.
• backend/x86_64.rs: x86-64 기계어를 직접 인코딩한다. 데이터 포인터는 rbx에 두고 I/O에는 원시 시스템 호출을 사용한다. 루프 조건에서 산술 플래그를 재사용하고, 곱셈 묶음은 원본 셀을 한 번만 읽는다. scan은 SSE2로 한 번에 16바이트를 검색하며, 파일 및 소켓 명령은 스택 프레임에 파일 디스크립터를 둔다.
• format/: 운영체제별 실행 파일을 기록한다. 현재는 elf.rs가 있다.
• jit.rs: extern "C" fn(*mut u8, usize) -> u32를 불러오며, 테이프 끝 뒤에 16바이트 여유 공간을 두고 메모리를 할당한다.

예를 들어 aarch64-linux 대상을 추가하려면 Arch 변형과 Target::syscalls의 시스템 호출 번호, CodeGen을 구현하는 backend/aarch64.rs, format/elf.rs의 e_machine 값을 추가한다. 새 운영체제를 지원하려면 format/에 실행 파일 기록기(Mach-O, PE)를 추가해야 한다. IR과 최적화 코드는 그대로 유지된다.

벤치마크

저장소 루트에서 bash bench/run.sh를 실행한다. 필요한 외부 프로그램은 bench/fetch.sh가 내려받고, 나머지는 임시 디렉터리에 생성한다. RUNS, FUEL, TIMEOUT 환경 변수로 설정할 수 있으며, BASELINE=/path/to/gbfc를 지정하면 기준 컴파일러와 비교할 수 있다.

아래 표는 이 컴파일러를 개발한 컴퓨터에서 스크립트를 실행한 결과다. 3회 실행 가운데 가장 좋은 결과를 기록했으며, 다른 하드웨어에서는 정확한 수치가 달라진다.

-O1 --fuel 4000000000은 계산 전체를 컴파일러에서 수행한다. mandelbrot은 약 13.6초, 두 mandelbrot 변형은 각각 약 13초가 걸리고 실행 시간은 수 밀리초로 줄어든다. 첫 번째 ,에서 멈추는 프로그램이나 시스템 호출에 묶인 프로그램(factor, cat)에는 이 방식이 도움이 되지 않는다.

테스트

cargo test --release

• 모든 examples/*.b를 각 최적화 모드에서 AOT와 JIT로 실행한다. 표준 입력은 .in, 기대 표준 출력은 .out 파일에 둔다.
• Brainfuck++의 파일 및 소켓 명령은 실제 파일과 TCP 루프백 연결을 통해 시험한다.