Problem mit Briggs nach DVNT

debach
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 18. Mai 2007 15:59
Kontaktdaten:

Problem mit Briggs nach DVNT

Beitrag von debach » 15. Jul 2010 16:47

Wir haben ein Problem mit dem Briggs-Algorithmus zum Auflösen der Phi-Funkitonen. Aus dem Triangle-Code

Code: Alles auswählen

let
	proc swaploop(var a : Integer, var b : Integer) ~ 
	let
		var tmp : Integer
	in begin
		while true do begin
			tmp := a;
			a := b;
			b := tmp;
		end
	end
in begin
end
erhalten wir nach DVNT folgenden CFG in SSA-Form

Bild

Unser Briggs macht das zu (beachtet den Unterschied zwischen 'temp' und 'tmp_')

Bild

Im Schritt schedule_copies_pass3a erkennt er im Block B2, dass a_2 eine LiveOut-Variable ist, legt eine Interblock-Sicherheitskopie temp0 = a_2 an, und merkt sich auf dem Stack für a_2, dass nun in temp2 ihr aktueller Wert steht.

Rekursiv steigt der Briggs ab und landet bei B4, im Schleifenbody. Dort muss er wieder eine Kopieranweisung a_2 = XXX einfügen, um die Phi-Funktion des Nachfolgers auszulösen. Da wieder a_2 eine LiveOut-Variable ist, legt er erneut eine Sicherheitskopie temp1 = a_2 an und legt sie über temp0 auf den Stack. Da der While-Body keine Kinder im Dominatorbaum hat, wird temp1 anschließend wieder gepoppt und für a_2 liegt nur noch temp0 darauf.

Bei der Bearbeitung von B5 wird dann jedes Vorkommen von a_2 durch temp0 ersetzt und dadurch a_2 auf seinen ursprünglichen, undefinierten Wert zurückgesetzt, was natürlich falsch ist.

Ein richtiges Ergebnis erhielte man in diesem Fall, wenn man am Ende des While-Bodies eine Anweisung temp0 = temp1 einfügen oder den Stack von a_2 poppen würde. Beides sieht der Briggs nicht vor.
Alternativ könnte man sich die Sicherheitskopien hier einfach sparen. Aber a_2 ist nun mal ein LiveOut der Blöcke B2 und B3, weil es in B5 gelesen wird.

Kann jemand helfen?

debach
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 18. Mai 2007 15:59
Kontaktdaten:

Re: Problem mit Briggs nach DVNT

Beitrag von debach » 16. Jul 2010 17:20

Ein Fehler ist, dass im Block B2 a_2 gar nicht live ist, weil es im Block B3 definiert wird, und zwar parallel zu seiner Benutzung in den anderen Phi-Funktionen.

Edit: Beachtet man die Parallelität der Phi-Funktionen bei der Datenflussanalyse, erhält man wie gewünscht

Bild

koch
Dozentin/Dozent
Beiträge: 221
Registriert: 4. Jul 2005 11:08

Re: Problem mit Briggs nach DVNT

Beitrag von koch » 27. Jul 2010 18:55

Ein Fehler ist, dass im Block B2 a_2 gar nicht live ist, weil es im Block B3 definiert wird, und zwar parallel zu seiner Benutzung in den anderen Phi-Funktionen.
Genau da liegt der Hase im Pfeffer. Allgemein: Immer die Parallelität der Phi-Funktionen beachten, die sieht man ja auf den ersten Blick nicht im Code.

Gruss & sorry für die späte Antwort,
Andreas Koch

Antworten

Zurück zu „Archiv“