| Autor |
Nachricht |
|
| Simson |
 Verfasst am: 19 Jan 2011 16:39 |
 |
|
|
Anmeldungsdatum: 23.10.2007
Beiträge: 55
|
Fürs Verständnis: Die Registerallokation vom UCLA Bsp. Factorial ist nicht ganz optimal im Sinne von "möglichst wenig Register verwenden", oder?
In der Main könnte man doch statt 4 Register auch nur 3 Verwenden?
Es werden immer folgende temps auf ein register gemapt:
21, 25, 31
22, 30
32, 24
32
Möglich wäre aber auch:
21, 22, 25, 32
23, 24
30, 21
Jedenfalls behauptet das mein interferenzgraph =) |
|
|
| Nach oben |
  
|
| konrada |
| Verfasst am: 19 Jan 2011 17:38 |
|
|
|
Anmeldungsdatum: 19.10.2009
Beiträge: 160
Wohnort: Freiburg
|
| Ich hab zwar das Beispiel nicht durchgelesen, aber halte es ungesehen fuer moeglich, dass der Registerallokator nicht auf eingesparte Register optimiert ist. Das muss noch nicht mal ineffizient sein; wenn man die Register eh hat und nicht dadurch spillen muss, kann man sie grosszuegig verteilen. |
|
|
| Nach oben |
|
| Simson |
| Verfasst am: 27 Jan 2011 12:29 |
|
|
|
Anmeldungsdatum: 23.10.2007
Beiträge: 55
|
Wenn ich nun meinen Graph gefärbt habe, ist das ja schonmal ganz toll. Aber da sind ja erstmal die callee save Register noch nicht unbedingt eingebaut. Wie ist denn da das 'übliche' Vorgehen? Was mir dazu eingefallen ist:
Man könnte die Temps, die callee-save sein sollen einfach vorfärben. Dann müsste man dabei irgendwie aber schon darauf achten, dass die nicht interferieren. Gibt es bei uns eigentlich sonst irgendwas, was vorgefärbt sein sollte?
Man könnte beim Farben zuweisen während der Graphfärbung checken, ob das Temp callee-save sein soll und dann eine dementsprechende Farbe zuweisen. Wenn dann aber die Anzahl der Farben im Algorithmus der Anzahl der Register entspricht, könnte es etwas wirr werden, wenn z.B. schon allee calle-save Farben aufgebraucht sind aber noch caller-save Farben vorhanden sind.
Man könnte nach der 'normalen' Färbung die Farben entsprechend auf die callee-save Register mappen. So ist allerdings nicht gegeben, dass auf ein callee-save Register auch nur Temps kommen, die callee-save sein müssen und die callee-save Register gehen möglichweise zu schnell aus. |
|
|
| Nach oben |
|
| konrada |
| Verfasst am: 27 Jan 2011 12:43 |
|
|
|
Anmeldungsdatum: 19.10.2009
Beiträge: 160
Wohnort: Freiburg
|
Um die Callee-save-Register und gleich noch die Arg- und Return-Register zu behandeln, hab ich gestern empfohlen, in einem zusaetzlichen Umschreibepass den Spiglet-Code zu Spiglet-Code mit vorgefaerbten Temps umzuschreiben. Der zusaetzliche Umschreibepass macht etwa aus
Code:
MOVE temp 15, CALL f (temp 22, temp 23)
den teil
Code:
MOVE temp1000, temp 22
MOVE temp1001, temp 23
MOVE temp1020, CALL f(temp1000, temp1001)
MOVE temp15, temp1020
wobei die 1000er Temps vorgefaerbt sind (1000=a0, 1001=a1, 1020=v0). Dann kann die Datenflussanalyse (die dann auch die Vorfaerbung kennen sollte) auch eintragen, dass die dritte Zeile die Temps 1000,1001, usw (also die fuer a-,v- und t-Register) ueberschreibt.
Analog: Eingehende Parameter aus den A-Registern abholen, Callee-save-Register sichern, Callee-save-Register herstellen, Rueckgabewert ablegen.[/code] |
|
|
| Nach oben |
|
| Simon2 |
| Verfasst am: 27 Jan 2011 18:02 |
|
|
|
Anmeldungsdatum: 07.01.2011
Beiträge: 11
|
Dürfen wir wieder voraussetzen, dass es im spigletcode keine temps >= 1000 gibt? Dann spart man sich den Visitor, der nen freien Bereich in den Temps findet...  |
|
|
| Nach oben |
|
| konrada |
| Verfasst am: 27 Jan 2011 18:11 |
|
|
|
Anmeldungsdatum: 19.10.2009
Beiträge: 160
Wohnort: Freiburg
|
Simon2 hat folgendes geschrieben:: Dürfen wir wieder voraussetzen, dass es im spigletcode keine temps >= 1000 gibt? Dann spart man sich den Visitor, der nen freien Bereich in den Temps findet...
Hier nimm. Ich hab den Ueberblick verloren, welche Temp-Ranges ich schon mal als unbenutzt versprochen hab.
package spiglet.tokanga.regalloc;
import spiglet.analysis.DepthFirstAdapter;
import spiglet.node.ATmp;
import spiglet.node.PLabeledStmt;
import spiglet.node.TInteger;
/**
* I find the maximum temp index.
* @author anton
*
*/
public class SpigletMaxTempVisitor extends DepthFirstAdapter {
/**
* Two states: interested and not interested.
*/
private boolean interested = false;
/**
* Running max.
*/
private int maxIndexSoFar = 0;
@Override
public void inATmp(ATmp node) {
interested = true;
}
@Override
public void outATmp(ATmp node) {
interested = false;
}
@Override
public void caseTInteger(TInteger node) {
if(!interested)
return;
int t = Integer.parseInt(node.getText());
tempIndexObserved(t);
}
/**
* Update maximum.
* @param t a temp
*/
private void tempIndexObserved(int t) {
if(maxIndexSoFar < t)
maxIndexSoFar = t;
}
/**
* Get the maximum of the temps observed so far.
* @return a temp index
*/
public int getMaxTempIndex() {
return maxIndexSoFar;
}
/**
* Compute a safe temp index, i.e. greater than the max temp index
* used in the program
* @param programFragment some part of a Spiglet program
* @return a safe temp index
*/
public static int computeSafeTempIndex(spiglet.node.Node programFragment) {
SpigletMaxTempVisitor v = new SpigletMaxTempVisitor();
programFragment.apply(v);
return 1+v.getMaxTempIndex();
}
/**
* Compute a safe temp index, i.e. greater than the max temp index
* used in the program
* @param proc a proc
* @return a safe temp index
*/
public static int computeSafeTempIndex(SpigletProcoid proc) {
SpigletMaxTempVisitor v = new SpigletMaxTempVisitor();
for(PLabeledStmt stmt : proc.getBodyStmts()){
stmt.apply(v);
}
proc.getReturnExp().apply(v);
int safeIndex = 100+v.getMaxTempIndex();
int roundSafeIndex = safeIndex - (safeIndex % 100);
return roundSafeIndex;
}
} |
|
|
| Nach oben |
|
| Simson |
| Verfasst am: 28 Jan 2011 13:48 |
|
|
|
Anmeldungsdatum: 23.10.2007
Beiträge: 55
|
konrada hat folgendes geschrieben:: [...] die 1000er Temps vorgefaerbt sind (1000=a0, 1001=a1, 1020=v0). Dann kann die Datenflussanalyse (die dann auch die Vorfaerbung kennen sollte) auch eintragen, dass die dritte Zeile die Temps 1000,1001, usw (also die fuer a-,v- und t-Register) ueberschreibt.
Analog: Eingehende Parameter aus den A-Registern abholen, Callee-save-Register sichern, Callee-save-Register herstellen, Rueckgabewert ablegen.
Alles klar wegen der Argumente. Aber wie gehe ich dann mit Temps um, die keine Parameter sind, aber dennoch callee-save sein sollten? |
|
|
| Nach oben |
|
| konrada |
| Verfasst am: 28 Jan 2011 13:54 |
|
|
|
Anmeldungsdatum: 19.10.2009
Beiträge: 160
Wohnort: Freiburg
|
Simson hat folgendes geschrieben::
Alles klar wegen der Argumente. Aber wie gehe ich dann mit Temps um, die keine Parameter sind, aber dennoch callee-save sein sollten?
Ich versteh noch nicht. Aus welchem Grund sollten die Temps callee-save sein? |
|
|
| Nach oben |
|
| konrada |
| Verfasst am: 28 Jan 2011 13:56 |
|
|
|
Anmeldungsdatum: 19.10.2009
Beiträge: 160
Wohnort: Freiburg
|
| Tip: Wie man den Registerallokator die Callee-Save-Register sichern laesst, steht in reg.pdf, Seite 14. In unserem Fall waere r3 ein mit einem s-Register vorgefaerbtes Temp. |
|
|
| Nach oben |
|
| MirkoB |
| Verfasst am: 01 Feb 2011 15:18 |
|
|
|
Anmeldungsdatum: 22.10.2010
Beiträge: 17
|
Etwas generells zur Registerallokation, ist es O.K. (im Sinne von kein Punktabzug), wenn ich folgendes mache:
- Liveness-Analyse um zu bestimmen welche Temporaries wann live sind.
- Anschließend Konstruktion des Interferenzgraphen
- Nun beliebige Färbung des Graphen, d.h. ich fange z.b. einfach mit den s_i registern an und verteile anschließend die t_j register.
(Callee- und Caller-save sicherung findet dann je nach Bedarf noch statt).
Mirko |
|
|
| Nach oben |
|
| konrada |
| Verfasst am: 01 Feb 2011 15:28 |
|
|
|
Anmeldungsdatum: 19.10.2009
Beiträge: 160
Wohnort: Freiburg
|
MirkoB hat folgendes geschrieben:: Etwas generells zur Registerallokation, ist es O.K. (im Sinne von kein Punktabzug), wenn ich folgendes mache:
- Liveness-Analyse um zu bestimmen welche Temporaries wann live sind.
- Anschließend Konstruktion des Interferenzgraphen
- Nun beliebige Färbung des Graphen, d.h. ich fange z.b. einfach mit den s_i registern an und verteile anschließend die t_j register.
(Callee- und Caller-save sicherung findet dann je nach Bedarf noch statt).
Mirko
Ich erwarte keine spezielle Klugheit in der Select-Phase bei der Wahl der Register, falls Du das meinst. |
|
|
| Nach oben |
|
|
|
