Hinweise und Testprogramm zur Live-Analyse

[Julian Oppermann]

Bitte beachten Sie folgende Hinweise zur Live-Analyse, die sich aus der zweiten Runde der Kolloquien ergeben haben:

Die Semantik der Phi-Instruktionen ist bekannterweise, dass alle Phis eines Blocks parallel ausgewertet werden. Um in der Live-Analyse sinnvolle Ergebnisse zu erhalten, gehören nur Phi-Parameter in UEVar, die nicht durch eine andere Phi-Instruktion desselben Blocks definiert werden.

Return-Instruktionen machen alle im CFG verwendeten Felder live, da sie in einer der aufrufenden Methoden verwendet werden könnten (eine konservative Abschätzung).

Damit Sie ihre Implementierung noch einmal selbst testen können, finden Sie auf der Veranstaltungswebsite ein Testprogramm mit den Dataflow-Dumps unseres Referenzcompilers.

[mmi1991]

Guten Abend,
vielen Dank erstmal für die Dumps

Ich wollte mal fragen, warum bei BB16 bei

Code: Alles auswählen

A_init ENTRY 16: @t7 

nicht io@f_A drinsteht, obwohl bei einem return ja alle verwendeten Felder live sein sollten?

Viele Grüße & vielen Dank,
Marc

[Wilson]

Ich glaube einen Fall gefunden zu haben in dem die Live-Analyse, wenn sie wie beschrieben mit Phi-Funktionen umgeht, falsche Ergebnisse liefert:

live.pdf

(46.86 KiB) 56-mal heruntergeladen

Hier müssten meiner Meinung nach in bb #2 a@2 und b@2 auch live sein, sind sie aber nicht, da die beiden Variablen Phi-Parameter sind die durch andere Phi-Funktionen definiert werden und somit nie in UeVar auftauchen.

Unser Workaround war hier, wie auch schon im Kolloquium (Gruppe 1) beschrieben, dass wir UeVar nicht mehr als statisch annehmen, sondern je nachdem aus welchem Vorgänger wir grade auf den Block schauen nur die passenden Phi-Parameter in UeVar enthalten sind. Dann liefert die Analyse das Ergebnis das ich erwarten würde:

workaround.pdf

(46.86 KiB) 58-mal heruntergeladen

.

[Julian Oppermann]

Ich wollte mal fragen, warum bei BB16 bei

Code: Alles auswählen

A_init ENTRY 16: @t7 

nicht io@f_A drinsteht, obwohl bei einem return ja alle verwendeten Felder live sein sollten?

Besser formuliert: Das return wirkt wie eine Verwendung für alle im CFG vorkommenden Felder.
In A_init::BB16 wird aber direkt vor dem return io@f_A geschrieben, deswegen ist das Feld nicht in UEVar.

[Julian Oppermann]

Bezüglich der zweiten Frage: Ich habe ein paar interessante Einsichten von einem Experten erhalten, arbeite aber noch an einer zufriedenstellenden Antwort.

[Julian Oppermann]

Sie haben Recht, die Lösung in unserer Referenzimplementierung ist falsch. Danke für die Hartnäckigkeit

Ich habe bislang folgendes herausgefunden: Eine bessere Vorstellung für die Behandlung von Phis in der Live-Analyse ist, dass die Verwendung auf der Kontrollflusskante passiert. Ersatzweise nimmt man an, dass die Verwendung am Ende des Vorgängerblocks stattfindet [1].
Der Effekt dürfte ähnlich zu Ihrem Workaround sein. Die in dem verlinkten Paper vorgestellte Analyse ist aber wie auch ihre Lösung keine klassische DFA mehr. Wir werden das Thema noch weiter verfolgen.

Ein kleiner Hinweis für die Klausur am Montag: Dort wird diese konkrete Fragestellung nicht relevant sein.

[mmi1991]

Vielen Dank für die Antwort