Wiedermann, P. (2008). A generalized PBQP instruction selector for the LLVM compiler framework [Master Thesis, Technische Universität Wien]. reposiTUm. http://hdl.handle.net/20.500.12708/178370
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 />
de
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 />