Differences

This shows you the differences between two versions of the page.

--- dev:crosscompiler:backend_ppc:register_allocation [2014/07/03 15:25] – external edit 127.0.0.1
+++ dev:crosscompiler:backend_ppc:register_allocation [2018/12/20 17:14] (current) – [Register Usage] ursgraf
@@ Line 1: / Line 1: @@
 ====== Register Allocation ======
-Starting with the SSA form for each result of an SSA instruction a register has to be assigned. However, it must be decided how the registers of a processor will be used generally.
+The PowerPC architecture offers 32 GPR's and 32 FPR's.
 ===== Register Usage =====
-Registers can be classified as //dedicated//, //volatile// or //nonvolatile//. //Dedicated// are register with a special purpose, such as the stackpointer. //Volatile// means, that this register might be used any time. It does not have to be stored when another method is called. //Nonvolatile// registers must be saved in the prologue of a method before they can be used and after use they must be restored. The number of volatile and nonvolatile registers must be equal for all methods.
 | Register | State | Use |
-| R0 | volatile | method prologue, working register |
+| R0 | volatile | method prologue, scratch register |
 | R1 | dedicated | stack pointer |
 | R2 | volatile | 1. parameter, return value |
@@ Line 25: / Line 25: @@
 ==== Parameter Passing ====
-Parameters are passes in R2..R10 and F1..F8.\\
+Parameters are passed in R2..R10 and F1..F8.\\
-In the interface //cgPPC/Registers// you can find the definitions about which registers are used for volatiles and nonvolatiles and which are used for parameter passing. Important: the number of parameter registers must be <= number of volatiles.
+In the interface //cgPPC/Registers// you can find the definitions about which registers are used for volatiles and nonvolatiles and which are used for parameter passing. Important: the number of parameter registers must be smaller or equal than the number of volatiles.
-===== Resolving of Phi-Functions =====
-The operands of a phi-function must all get the same register as the result of the phi-function. For this purpose all these operands have a field //join//. \\
-Before the phi-functions can be resolved, loops need special treatment. Let's consider the folowing case:
-[{{ .:phifunctionloop1.png?110 |//Phi-Function in a loop//}}]
-The SSAValue of //a// is used in the loop. The live range of //a// extends to the instruction for //b = 2 * a//. However, this would be wrong, because the register for //a// would be released at this point and might be used otherwise. It must stay reserved until the end of the loop. At the beginning of node 2 a phi-function is created for //a//. This function will be deleted because //a// is set in node 1 and only read in node 2. For all phi-functions in loops (whether deleted or not) the field //last// is set to the last instruction of this loop.\\
-Subsequently, all instructions of all SSA nodes are copied into an array, since the control flow is no longer important for the further processing and the access is faster.\\
-All used phi-functions are marked (field //used//). //used// indicates if a deleted phi-Funktion is used further downstream. If not, the register can be released immediately. The reason for doing this is the fact, that phi-functions were inserted for every local variable if loops are present. Most of this phi-functions are deleted and should not occupy a register unnecessarily. \\
-Phi-functions will be resolved as follows: A new state array //join// is created. The field //join// of the result of the phi-function and of its operands refer to the value in this state array with the same index as the phi-function. Several phi-functions might refer to the same //join// value. \\
-There are cases where two different phi-functions with the same index refer to two different variables, as in:
-<code java>
-  if() {
-    int a = ...;
-    while() a = ...;
-  } else {
-    float f = ...;
-    while() f = ...;
-  }
-</code>
-//a// and //f// occupy the same slot (or index). Nevertheless, the two ranges must not be integrated into one. If the two variables have the same type it wouldn't really matter, though it wouldn't be efficient. However, in this case the type is different and later, we have to assign different registers. Therefore, we check if the range of a new phi-function overlaps with the range of a phi-function further upstream at the same index. If this is not the case, we create another //join// value in the state array and link it to the previous one.
-[{{ .:phifunctionjoin1.png?200 |//Phi-functions for same slots but different types//}}]
-===== Determination of Live Range =====
-We determine for the results of all SSA instructions up to which instruction they are used (field //end//).
-Results of phi-functions must be handled separately. Such results might be used as operands of instructions which are placed further upstream. For this reason the live range of a phi-function does not start with its instruction but with its first use of an operand or the phi-function itself. Hence, phi-function need a field //start//.
-===== Determine the Register Type =====
-Before beeing able to assign registers we have to decide whether to use a volatile or nonvolatile register. As soon there is a call to a method within the live range of a value (holds also for phi-functions) then this value must be assigned a nonvolatile Register. Other values are assigned a volatile register. The same is true for exceptions. If the live range of a variable extends into (or over) a catch block we must assign a nonvolatile register, as the handling of the exception destroys volatiles.\\
-A special case is the SSA instruction //sCloadLocal//. With this we must ckeck if a method call occurs between the start of the method to the end of the live range. If this is not the case we can leave the parameter in the the register where it was passed, which is a volatile register already.
-===== Determine Used Parameters =====
-Zu Beginn einer Methode werden alle Parameter in den volatile Registern übergeben. Zum Teil müssen sie in nonvolatile Register umkopiert werden. Es gibt auch den Fall, dass Parameter in der Methode gar nicht verwendet werden. Dies ist aus dem exit set des letzten Knotens ersichtlich. Wenn dort ein Wert null ist, wurde der Parameter mit diesem Index nie geladen und sein Register muss nicht reserviert werden. Das folgende Beispiel verdeutlicht das Vorgehen.
-<code java>
-  float m2(long a, float b, double c, byte[] d, short e, int f, int g) {
-    a = 0x7545 & a;
-    e += 100;
-    T08Calls.classMethod(d[2]);
-    e = (short)(20 + e);
-    g |= 0x223344;
-    c = 3.2;
-    int h = g - e;
-    T08Calls.classMethod(h);
-    short i = (short)h;
-    return b;
-  }
-</code>
-|**Variable**|this|a|b|c|d|e|f|g|
-|**Typ**|ref|Long|Float|Double|ByteArray|Short|Integer|Integer|
-|**Register Typ**| |vol|nonVol|vol|vol|vol| |nonVol|
-|**nicht verwendet**|x| | | | | |x| |
-|**Register**| |R3,R4|FR31|FR2|R5|R6| |R31|
-===== Zuweisung der Register =====
-Zuletzt erhält jedes Resultat einer SSA Instruktion ein Register zugewiesen.
-==== Laden der Parameter ====
-Alle sCloadLocal Instruktionen benutzen das gleiche Register, wie bereits der Parameter erhalten hat. Falls //join != null// erhält auch die referenzierte phi-Funktion das gleiche Register.
-==== Reservation von Hilfsregistern ====
-Einige Instruktionen benötigen 1 oder 2 zusätzliche Hilfsregister. Diese werden reserviert und in den Feldern //regAux1// und //regAux2// abgelegt. Anschliessend können sie gleich wieder freigegeben werden. Somit kann das Resultat der SSA Instruktion das gleiche sein, wie eines dieser Hilfsregister.
-==== Freigabe der Operandenregister ====
-Die Register aller Operanden, die das Ende ihrer live range erreicht haben, können freigegeben werden. Falls diese vom Typ Long sind, darf dieser Schritt erst am Schluss erfolgen.
-==== Reservation eines Registers für das Resultat ====
-Jetzt kann im Registerpool ein Register reserviert werden. Der Typ des Resultates bestimmt dabei, ob 1 oder 2 GPR's oder 1 FPR. Dabei müssen die 2 folgenden Fälle unterschieden werden.
-=== 1. join != null ===
-Hier muss das gleiche Register wie dem Resultat der phi-Funktion zugewiesen werden. Falls noch nicht behandelt, muss die phi-Funktion zuerst behandelt werden.
-Es kann der Fall auftreten, dass mehrere phi-Funktionen den gleichen Index im Statearray belegen, siehe folgendes Beispiel:
-<code java>
-  switch(i) {
-  case 0: return 0;
-  case 1: i++; break;
-  case 2: return 2;
-  case 3: i += 3;
-  case 4: i += 4; break;
-  default: return -1;
-  ..
-  return i + 3;
-</code>
-Alle phi-Funktionen mit dem gleichen Index erhalten das gleiche Register zugewiesen.
-=== 2. Laden einer Konstanten ===
-Falls die Konstante 16 Bit nicht überschreitet und die Instruktion, wo sie als Operand verwendet wird, übersetzt werden kann in eine Maschineninstruktion mit immediate Operand, muss kein Register zugewiesen werden. Falls der Wert aber im Statearray auftaucht (index >= 0) muss der Wert immer in ein Register geladen werden. Das ist z.B. beim Bedingungsoperator der Fall. Das gleiche gilt auch, wenn //join != null//.
-==== Freigabe des Resultatregisters ====
-Das Resultatregister darf gleich wieder freigegeben werden, wenn das Ende der live range bereits erreicht wurde (der erzeugte Wert wird gar nie verwendet).
-Jetzt

deep

User Tools

Site Tools

Differences

Page Tools