Prozedurale Abstraktion für ARM-Architekturen

Student:Alexander Dreweke
Title:Prozedurale Abstraktion für ARM-Architekturen
Type:diploma thesis
Advisors:Philippsen, M.; Schell, D.; Fischer, I.
State:submitted on March 29, 2006
Prerequisits:
Topic:

Hintergrund
Da auf eingebetteten Systemen chronischer Speicherplatzmangel herrscht, ist es wichtig, so kompakten Programmcode wie möglich zu erzeugen. Theoretisch ist es mit Assemblercode möglich, hochoptimierten und kompakten Code zu programmieren, jedoch erkauft man sich damit die bekannten Probleme in der Wartung, Pflege und Portierung des Codes. Aus diesem Grund sollen Hochsprachen wie C/C++ eingesetzt werden. Allerdings können Übersetzer durch ihre Architektur bedingt nur suboptimalen Code erzeugen. Die besonders bei OOP-Sprachen zu findende Aufteilung des Quellcodes in viele kleine Moduln und die, da meist NP-vollständig, eingeschränkten Optimierungsmöglichkeiten, sorgen dafür, dass sich oft ähnliche Code-Fragmente in dem fertigen Programm finden, die sich z.B. lediglich durch die verwendeten Register unterscheiden. Prozedurale Abstraktion [5] ist ein Ansatz zur Lösung dieses Problems: aus dem gesamten Programm werden gemeinsame Code-Sequenzen in eine eigene Funktion ausgegliedert und durch einen Aufruf dieser Funktion ersetzt. Die Ausgliederung wird nur vorgenommen, wenn sich die Kosten amortisieren, welche z.B. durch das Verschieben von Registern vor und nach dem Funktionsaufruf entstehen.

Aufgabestellung
In dieser Arbeit soll eine neue Methode zur Prozeduralen Abstraktion basierend auf "Graph Data Mining" [4] evaluiert werden. Als zugrundelegende Architektur soll ARM verwendet werden.
Folgende Meilensteine sollen erreicht werden:

  • Die Binarys sollen zuerst in einen Kontrollflussgraph und anschließend in einen Datenflussgraph umgewandelt werden. Der entstehende Graph ist Eingabe für das Data Mining auf Graphen.
  • Das Ergebnis des Data Mining sind Codestücke (Graphfragmente), die häufig im Graph vorkommen. Es ist zu testen, mit welchen Einstellungen der Miner das beste Ergebnis liefert.
  • Die gefunden Fragmente sollen analysiert werden, es müssen Heuristiken entwickelt werden, welche Fragmente entgültig ausgelagert werden sollen.
  • Die besten Fragmente sind aus dem Code auszulagern. An ihrer ursprünglichen Stelle ist ein Funktionsaufruf einzufügen, Register sind anzupassen. Das erzeugte neue Assemblerprogramm soll lauffähig sein.
  • Das entwickelte Verfahren soll z.B. anhand der MI-Bench evaluiert werden [3]. Dabei soll das entwickelte Tool mit der aipop von absint verglichen werden [2].

Literatur
[1] http://www.arm.com
[2] http://www.absint.de/aipopARM/
[3] http://www.eecs.umich.edu/mibench/
[4] Wörlein, Marc ; Meinl, Thorsten ; Fischer, Ingrid ; Philippsen, Michael: A quantitative comparison of the subgraph miners MoFa, gSpan, FFSM, and Gaston . In: Jorge, Alipio ; Torgo, Luis ; Brazdil, Pavel (Hrsg.) : Knowledge Discovery in Database: PKDD 2005 (9th European Conference on Principles and Practices of Knowledge Discovery in Databases Porto, Portugal 2005-10-03 - 2005-10-07). Berlin : Springer, 2005, S. 392-403
[5] Saumya Debray, William Evans, Robert Muth: Compiler Techniques for Code Compression, 1999, www.cs.arizona.edu/people/debray/papers/compression.ps

watermark seal