Wetenschappers hebben een innovatieve methode ontwikkeld om de betrouwbaarheid van moderne compilers te verhogen. Het nieuwe framework, genaamd Trivet, integreert grote taalmodellen (LLM's) met de interactieve bewijsvoerder Lean. Hiermee kan de correctheid van transformaties binnen de LLVM-infrastructuur automatisch worden geverifieerd, wat essentieel is voor de stabiliteit van software.
LLVM vormt de basis voor veel hedendaagse toolchains en fungeert als een modulair systeem dat wordt ingezet voor het bouwen van compilers, codegeneratoren en optimalisatiepijplijnen, zoals beschreven door compilersutra.com. Binnen dit ecosysteem wordt een specifieke tussenrepresentatie (IR) gebruikt om code te optimaliseren voordat deze wordt omgezet naar machinecode voor hardware-architecturen zoals ARM of x86. Vanwege de subtiele semantiek van deze IR kunnen optimalisaties echter onbedoeld fouten introduceren, waardoor formele verificatie noodzakelijk is.
Voorheen werd voor dit proces vaak geleund op Alive2, een validator die gebruikmaakt van satisfiability modulo theories. Hoewel dit systeem effectief is, wijst een recente publicatie op arxiv.org op significante beperkingen. Zo kampt Alive2 met schaalbaarheidsproblemen, biedt het onvoldoende garanties voor lussen in de code en ondersteunt het geen symbolische bitbreedtes. Hoewel interactieve bewijsvoerders zoals Lean deze problemen kunnen oplossen, is dat proces normaal gesproken zeer arbeidsintensief omdat het handmatige bewijsvoering door experts vereist.
Trivet overbrugt dit gat door de generatieve capaciteiten van AI te koppelen aan de strikte precisie van Lean. Het proces verloopt in drie fasen: eerst wordt er via 'scaffolding' een gestructureerd bewijskader opgesteld op basis van de bron- en doel-functies. Vervolgens worden deterministische vraagstukken via vaste regels opgelost, waarna complexere transformatievraagstukken worden gedelegeerd aan een LLM. Het cruciale aspect van dit systeem is dat elk resultaat wordt gecontroleerd door de Lean-kernel, waardoor de output van de AI wiskundig wordt geverifieerd.
De effectiviteit van de methode is getest op 148 verschillende LLVM-transformaties. Trivet slaagde erin om 147 van deze gevallen te verifiëren of te weerleggen. Onder de resultaten vielen 60 lus-vrije transformaties met symbolische bitbreedtes en 27 transformaties uit een specifieke klasse van lussen. Opvallend is dat het systeem in 10 complexe gevallen met vaste bitbreedte succesvol was, terwijl de bestaande tool Alive2 in diezelfde scenario's vastliep door een timeout.
Het gebruik van het gestructureerde bewijskader bleek essentieel voor de prestaties. In vergelijking met een aanpak zonder scaffolding kon Trivet 26 extra bewijzen leveren. Daarnaast leidde deze methodiek tot een aanzienlijke efficiëntiewinst: de gemiddelde tijd om een bewijs te leveren daalde met 75,9%, terwijl de monetaire kosten met 88% werden gereduceerd.
De noodzaak voor dergelijke geautomatiseerde validatie is groot, aangezien de architectuur van LLVM zeer complex is en wordt ingezet voor diverse toepassingen, waaronder GPU-compilers en analyse-instrumenten. Zoals uiteengezet in de llvorg, biedt het systeem uitgebreide ondersteuning voor optimalisaties en JIT-compilatie (Just-In-Time). Door AI-gestuurde bewijsvoering te combineren met wiskundige controle, biedt Trivet een schaalbare oplossing voor een probleem dat voorheen ofwel te tijdrovend of technisch te beperkt was.