6502-Codegenerator übertrifft GCC und LLVM

Ein Entwickler hat einen 6502-Codegenerator gebaut, der überraschenderweise GCC, LLVM und andere Compiler übertrifft. Der Geschwindigkeitsvorteil liegt nicht an überlegenen Optimierungen auf hoher Ebene, sondern an innovativen Codegenerierungstechniken. Der Compiler nutzt „illegale“ Instruktionen, rechenintensive Instruktionsauswahl und Optimierungen, die Speicherplatz gegen Geschwindigkeit eintauschen. Der Kernalgorithmus kombiniert Instruktionsauswahl mit Registerallokation und verwendet geschickt Continuation-Passing Style. Er arbeitet mit einer DAG- und SSA-Form der Zwischenrepräsentation, erzeugt mehrere Assemblercodekombinationen, reduziert diese mit dynamischer Programmierung und Branch-and-Bound und löst schließlich ein PBQP-Problem zur optimalen Auswahl. Obwohl einige „Tricks“ verwendet werden, zeigt der Compiler bemerkenswerte Benchmark-Ergebnisse und bietet neue Perspektiven auf die Codegenerierung.