Dominatorbäume

Benutzeravatar
daishan
Erstie
Erstie
Beiträge: 14
Registriert: 21. Okt 2005 12:55
Wohnort: Darmstadt / Bad Hersfeld
Kontaktdaten:

Dominatorbäume

Beitrag von daishan » 2. Jun 2010 17:33

Gibt es eigentlich einen allgemeinen Algorithmus zum Berechnen der Dominatorbäume? Die werden ja für die Rückumwandlung von SSA benötigt. Vielleicht haben wir etwas übersehen, aber wir haben weder in den Folien der Vorlesung noch in den beiden Briggs Papern etwas dazu gefunden.
Wir haben uns überlegt, mittels Datenflussanalyse die Dominatormengen zu berechnen, dann mit einer Breitensuche für jeden Knoten den IDom aus der Dominatormenge zu bestimmen und schließlich den IDom dann als Elternknoten im Dominatorbaum zu nutzen. Das ist aber recht aufwendig/kompliziert und wir sind etwas verwundert, dass dafür kein Algorithmus vorgestellt wurde.

Edoat
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 26. Feb 2007 15:10

Re: Dominatorbäume

Beitrag von Edoat » 2. Jun 2010 19:51

daishan hat geschrieben:Gibt es eigentlich einen allgemeinen Algorithmus zum Berechnen der Dominatorbäume? Die werden ja für die Rückumwandlung von SSA benötigt.
So weit ich das aus der Vorlesung in Erinnerung habe, steht da im Cytron-Paper was dazu. Ich habe das Paper allerdings nicht gelesen, deshalb kann ich das nicht mit Sicherheit sagen.
daishan hat geschrieben:Vielleicht haben wir etwas übersehen, aber wir haben weder in den Folien der Vorlesung noch in den beiden Briggs Papern etwas dazu gefunden.
Falls hier Dominator-Bäume für strukturierte Sprachen wie Triangle gemeint sein sollten, könnt ihr einen Blick in die Folien zur Wandlung in die SSA-Form (CFG2SSA-handout, ab S.64) oder das erste Briggs-Paper ("Single-Pass Generation of Static Single Assignment Form for Structured Languages", Abschnitt 3) werfen.

Benutzeravatar
daishan
Erstie
Erstie
Beiträge: 14
Registriert: 21. Okt 2005 12:55
Wohnort: Darmstadt / Bad Hersfeld
Kontaktdaten:

Re: Dominatorbäume

Beitrag von daishan » 2. Jun 2010 21:14

Edoat hat geschrieben:
daishan hat geschrieben:Gibt es eigentlich einen allgemeinen Algorithmus zum Berechnen der Dominatorbäume? Die werden ja für die Rückumwandlung von SSA benötigt.
So weit ich das aus der Vorlesung in Erinnerung habe, steht da im Cytron-Paper was dazu. Ich habe das Paper allerdings nicht gelesen, deshalb kann ich das nicht mit Sicherheit sagen.
Cytron verweist dafür auch nur auf andere Papers und die dort beschriebenen Algorithmen sind ziemlich aufwendig. Natürlich kann man die implementieren, aber das würde meiner Einschätzung nach den Rahmen des Praktikums etwas sprengen. Außerdem würde ich erwarten, dass sowas in der Aufgabenstellung zumindest mal erwähnt wäre.
Edoat hat geschrieben:
daishan hat geschrieben:Vielleicht haben wir etwas übersehen, aber wir haben weder in den Folien der Vorlesung noch in den beiden Briggs Papern etwas dazu gefunden.
Falls hier Dominator-Bäume für strukturierte Sprachen wie Triangle gemeint sein sollten, könnt ihr einen Blick in die Folien zur Wandlung in die SSA-Form (CFG2SSA-handout, ab S.64) oder das erste Briggs-Paper ("Single-Pass Generation of Static Single Assignment Form for Structured Languages", Abschnitt 3) werfen.
Ah, die genannten Folien haben wir tatsächlich übersehen. Über etwas ähnliches hatten wir auch schon nachgedacht, aber wir befürchten, dass wir in den nächsten Praktikumsaufgaben den CFG selbst optimieren sollen (ab Folie 23 in skalaropt-handout.pdf). Danach wäre ein beim Erzeugen des CFGs nebenbei erzeugter Dominatorbaum ja nicht mehr gültig. Vielleicht kann man den anfangs erzeugten Dominatorbaum dabei mit anpassen, aber zumindest bei dem Beispiel auf Folie 26 habe ich Bedenken, dass das einfach so geht ohne IDoms berechnen zu müssen.

Wenn einer der Verantwortlichen etwas dazu sagen könnte, ob das Verbiegen von Kannten im CFG noch Bestandteil des Praktikums sein wird, wäre das auch sehr hilfreich. :)

moep
Windoof-User
Windoof-User
Beiträge: 36
Registriert: 3. Nov 2005 12:32

Re: Dominatorbäume

Beitrag von moep » 3. Jun 2010 19:33

*edit*

hat sich schon erledigt

Antworten

Zurück zu „Archiv“