This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
dev:crosscompiler:backend_ppc:register_allocation [2015/04/18 08:16] – [Zuweisung der Register] ursgraf | dev:crosscompiler:backend_ppc:register_allocation [2018/12/20 17:14] (current) – [Register Usage] ursgraf | ||
---|---|---|---|
Line 1: | Line 1: | ||
====== Register Allocation ====== | ====== 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 ===== | ===== Register Usage ===== | ||
- | Registers can be classified as // | + | |
| Register | State | Use | | | Register | State | Use | | ||
- | | R0 | volatile | method prologue, | + | | R0 | volatile | method prologue, |
| R1 | dedicated | stack pointer | | | R1 | dedicated | stack pointer | | ||
| R2 | volatile | 1. parameter, return value | | | R2 | volatile | 1. parameter, return value | | ||
Line 25: | Line 25: | ||
==== Parameter Passing ==== | ==== Parameter Passing ==== | ||
- | Parameters are passes | + | Parameters are passed |
- | In the interface // | + | In the interface // |
- | + | ||
- | ===== 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: | + | |
- | [{{ .: | + | |
- | + | ||
- | 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 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 = ...; | + | |
- | } | + | |
- | </ | + | |
- | //a// and //f// occupy the same slot (or index). Nevertheless, | + | |
- | [{{ .: | + | |
- | + | ||
- | + | ||
- | ===== 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 // | ||
- | ===== Determine Used Parameters ===== | ||
- | Parameters are passed in volatile registers. Some of them have to be copied to nonvolatile registers. Some parameters might not be used at all in a method. This can be determined in the exit set of the last node. If a value is null in that set the parameter with this index was never loaded and hence no register must be reserved. The following example demonstrates parameter usage. | ||
- | <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; | ||
- | } | ||
- | </ | ||
- | |**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| | ||
- | |**not used**|x| | | | | |x| | | ||
- | |**Register**| |R3, | ||
- | ===== Register Assignment ===== | ||
- | Finally the results of all SSA instructions will be assigned a register. | ||
- | ==== Loading of Parameters ==== | ||
- | All // | ||
- | ==== Reservation of Auxiliary Registers ==== | ||
- | Some instruction need 1 or 2 additional (auxiliary) registers. These will be reserved and stored in //regAux1// and // | ||
- | ==== Releasing of Operand Registers ==== | ||
- | Registers of operands, whose live range expires, must be released. If they are of type //Long//, this step must happen at the very end. | ||
- | ==== Reservation of a Register for the Resueines 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; | ||
- | </ | ||
- | 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, | ||
- | ==== 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 |