HOME | ENGLISH | IMPRESSUM | KIT

Bachelor-/Masterarbeit (offen): Load-Store-Optimierung mit Speicherpartitionierung

Das Ziel der Load-Store-Optimierung ist es unnötige Speicherzugriffe zu vermeiden, da diese sehr viele Prozessortakte in Anspruch nehmen können. Folgt einem Load-Befehl beispielsweise ein Store-Befehl auf dieselbe Adresse, so kann der zuvor gespeicherte Wert direkt wiederbenutzt werden. Falls zwischen dem Load- und dem Store-Befehl noch weitere Speicherzugriffe erfolgen, kann die Optimierung nur durchgeführt werden, wenn diese garantiert auf eine andere Adresse zugreifen. Die Analyse, die herausfindet, ob zwei Adressen garantiert verschieden sind, heißt Alias-Analyse. Beispielsweise kann im folgenden C-Programm


int a;
int b;

int main(void)
{
	a = -1;
	b = 1;
	int la = a;
	int lb = b;

	return la + lb;
}

der geladene Wert von a nur dann durch den Wert -1 ersetzt werden, wenn der zweite Store-Befehl auf b garantiert nicht den Wert von a überschreibt.

Ziel dieser Arbeit ist es, die Load-Store-Optimierung des am Lehrstuhl entwickelten Compilers libFirm zu verbessern. In libFirm werden Funktionen als Abhängigkeitsgraphen modelliert. Die obige Funktion sieht in libFirm wie folgt aus:

Damit Load- und Store-Befehle in der spezifizierten Reihenfolge ausgeführt werden, werden alle Speicherbefehle durch die blauen Speicherabhängigkeiten total geordnet. Um dieses Totalordnung in eine gültige partielle Ordnung zu überführen, kann der Speicher mit Hilfe der Alias-Analyse in Partitionen unterteilt werden. Der Sync-Knoten dient hierbei dazu, die Partition wieder zu vereinigen. Dadurch wird die Alias-Information in der Struktur des Graphen codiert, was die Load-Store-Optimierung vereinfacht:

Im Rahmen der Masterarbeit soll die in libFirm vorhandene Load-Store-Optimierung auf die angesprochenen Partitionen erweitert werden. Anschließend soll die Qualität der Load-Store-Optimierung weiter verbessert werden. Mögliche Ansätze dazu wären:

  • Eine verbesserte Alias-Analyse
  • Das Verschieben von Speicheroperation auf seltener ausgeführte Pfade
  • Das Verschmelzen mehrerer gleichartiger Speicheroperationen mit geringer Bitbreite zu einer Speicheroperation mit höherer Bitbreite

Aufgabe:

  • Umstellung der Load-Store-Optimierung auf Partitionen
  • Qualitätsverbesserung der Load-Store-Optimierung

Voraussetzungen

  • Programmierkenntnisse in C
  • Interesse am Compilerbau und Optimierungen
  • Erfahrung in libFirm vorteilhaft

Schlüsselworte

Compiler, libFirm, Optimierung 

Betreuer

Wissenschaftliche Mitarbeiter
Sebastian Buchwald