6502 코드 생성기, GCC와 LLVM 능가

한 개발자가 6502 아키텍처를 위한 코드 생성기를 만들었는데, 놀랍게도 GCC, LLVM 및 다른 컴파일러보다 성능이 뛰어났습니다. 이러한 속도 향상은 고급 최적화 때문이 아니라 혁신적인 코드 생성 기술 덕분입니다. "비합법적인" 명령어, 계산 비용이 높은 명령어 선택, 공간을 시간과 맞바꾸는 최적화 기법 등을 활용했습니다. 핵심 알고리즘은 명령어 선택과 레지스터 할당을 결합하여 지속 전달 방식을 효과적으로 사용합니다. DAG와 SSA 형태의 중간 표현을 사용하여 여러 어셈블리 코드 조합을 생성하고, 동적 계획법과 분기 한정법으로 가지치기를 수행하며, 마지막으로 PBQP 문제를 풀어 최적의 조합을 선택합니다. 몇 가지 "꼼수"를 사용했지만, 이 컴파일러는 벤치마크 테스트에서 뛰어난 결과를 보여주며 코드 생성 기술에 대한 새로운 관점을 제시합니다.