Ein Framework für Prozedurale Abstraktion

Student:Tobias Meyer
Title:Ein Framework für Prozedurale Abstraktion
Type:diploma thesis
Advisors:Schell, D.; Fischer, I.; Philippsen, M.
State:submitted on September 1, 2005
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 [1] 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
Es existiert bereits ein Werkzeug, welches aus Assemblercode den dazugehörigen Kontrollflussgraphen (KFG) erzeugt.

  • Auf der Basis dieses KFG ist eine Datenflussanalyse durchzuführen. Mittels dieser Analyse ist es möglich, die weitestgehend serielle Struktur des KFG in einen Graphen zu transformieren.
  • Die am Lehrstuhl vorhandenen Graph-Mining-Werkzeuge sollen eingesetzt werden, um ähnliche Code-Fragmente zu finden. Diese gefundenen Code-Fragmente stellen Kandidaten für die prozedurale Abstraktion dar.
  • Die gefundene Fragmente müssen auf Ihre Eignung zur prozeduralen Abstraktion überprüft werden. Dazu muss ein Ähnlichkeitsmaß entwickelt werden.
  • Weiterhin soll eine Transformation gefunden werden, welche mehrere ähnliche Fragmente in ein gleiches überführt.
  • Ausführliche Tests und Vergleiche mit anderen Werkzeugen, die ähnliche Ziele verfolgen, sollen die Arbeit abschließen.

Literatur
[1] Neil Johnson, Alan Mycroft: Pattern and Approximate-Pattern Matching for Program Compaction, Februar 2001, http://www.milton.arachsys.com/nj71/research/papers/patternsurvey.pdf

watermark seal