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/09/30 15:00] – [Register Assignment] 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 | + | |
- | 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 // | + | |
- | + | ||
- | ===== 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 | + | |
- | 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. | ||
- | ===== Releasing of Registers of phi-Functions ===== | ||
- | As described above, phi-functions have a field //last// which is used to make sure that a registers of a phi-function lives to the very end of its loop. At the this end the register of the phi-function (which is actually given in its join value) could be released. However, at this stage we already passed the phi-function. For this purpose all phi-functions are referenced in a linked list (with the field //next//) in the first SSA instruction of the node following the node with the phi-function. | ||
- | ==== 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 Result Register ==== | ||
- | The register pool will be searched for a free register for the result. The result type determines if 1 or 2 GPR's or a FPR must be reserved. The following two cases must be considered. | ||
- | === 1. join != null === | ||
- | The same register must be assigned as the result of the phi function. If not handled yet the phi function has to be dealt with first. It can happen that several phi funtions occupy the same index in the state array: | ||
- | <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; | ||
- | </ | ||
- | In those cases all phi functions with the same index get the same register assigned. | ||
- | === 2. Loading of a Constant === | ||
- | If a constant can be used as immediate operand by the machine instruction no register has to be reserved. However, if the value shows up in the state array (index >= 0), it must be loaded into a register anyway. This is the case with the conditional operator. A register must be assigned also in case of //join != null//. | ||
- | ==== Releasing of Result Registers ==== | ||
- | The result register can be released immediately if the live range already expires. |