A generalized PBQP instruction selector for the LLVM compiler framework

Abstract

In den letzten Jahren fand ein neuer Ansatz Verbreitung, der das Problem der Befehlsauswahl auf ein mathematisches Optimierungsproblem, das sogenannte Par- tioned Boolean Quadratic Problem (PBQP) abbildet. Diese neuartige Formulierung ermoeglicht neben einer funktionsglobalen Optimierung auch noch die Entwicklung ausdruckstaerkerer Befehlsgrammatiken.<br /> Fruehere Arbeiten zum Thema PBQP Befehlsauswahl stuetzen sich auf Befehls- grammatiken die aus baumfoermigen Regeln bestehen. Wir stellen eine Generalisierung vor, die GAG-foermige Regeln ermoeglicht welche mehrere Ergebnisse liefern und mehrere Operationen auf unabhaengigen Datenpfaden abdecken koennen.<br /> Wir integrieren diese generalisierte Befehlsauswahl in die LLVM Uebersetzerinfrastruktur, welche derzeit einen einfachen top-down Algorithmus zur Befehlsauswahl einsetzt. Das bringt neben einem funktionsglobalen Optimierungsraum auch noch zusatzliche Funktionalitat, wie zum Beispiel GAG-formige Regeln und ein dynamisches Kostenmodell fur die Befehlsgrammatik, mit sich.<br /> Zur Evaluierung implementieren wir Befehlsgrammatiken fur zwei unterschiedliche Architekturen und uebersetzen Programme aus verbreiteten Benchmark-Suites. Wir untersuchen dabei neben der Effizienz der ubersetzten Programme auch die algorithmische Komplexitat unserer generalisierten Befehlsauswahl.<br />

In the last few years a new approach has been discovered, which maps the in- struction selection problem onto a mathematical program, the Partitioned Boolean Quadratic Problem (PBQP). This formulation increases the scope of optimization to functions, while offering additional possibilities to develop more expressive in- struction set grammars.<br /> Previous works described PBQP instruction selectors based on instruction set grammars which consist of tree shaped rules.<br />We present a generalization that allows the formulation of DAG 1 -shaped rules with multiple results which can match multiple operations even if they are not on the same data-path.<br /> We introduce this generalized PBQP instruction selector into the LLVM com- piler framework, which is currently based on a greeedy top-down matcher.<br />This implicates several new features for the LLVM framework like function wide instruc- tion selection, DAG-shaped rules and a dynamic cost model for the instruction set grammar.<br /> We evaluated our instruction selector using two different architectures and real world benchmark suites, and examined the computational complexity of our gener- alized PBQP formulation.<br />