To Be Written
Live Intervals are the ranges (intervals) where a variable is live. +They are used by some register allocator passes to +determine if two or more virtual registers which require the same physical +register are live at the same point in the program (i.e., they conflict). When +this situation occurs, one virtual register must be spilled.
+ +The first step in determining the live intervals of variables is to +calculate the set of registers that are immediately dead after the +instruction (i.e., the instruction calculates the value, but it is +never used) and the set of registers that are used by the instruction, +but are never used after the instruction (i.e., they are killed). Live +variable information is computed for each virtual register and +register allocatable physical register in the function. This +is done in a very efficient manner because it uses SSA to sparsely +compute lifetime information for virtual registers (which are in SSA +form) and only has to track physical registers within a block. Before +register allocation, LLVM can assume that physical registers are only +live within a single basic block. This allows it to do a single, +local analysis to resolve physical register lifetimes within each +basic block. If a physical register is not register allocatable (e.g., +a stack pointer or condition codes), it is not tracked.
+ +Physical registers may be live in to or out of a function. Live in values +are typically arguments in registers. Live out values are typically return +values in registers. Live in values are marked as such, and are given a dummy +"defining" instruction during live intervals analysis. If the last basic block +of a function is a return, then it's marked as using all live out +values in the function.
+ +PHI nodes need to be handled specially, because the calculation +of the live variable information from a depth first traversal of the CFG of +the function won't guarantee that a virtual register used by the PHI +node is defined before it's used. When a PHI node is encounted, only +the definition is handled, because the uses will be handled in other basic +blocks.
+ +For each PHI node of the current basic block, we simulate an +assignment at the end of the current basic block and traverse the successor +basic blocks. If a successor basic block has a PHI node and one of +the PHI node's operands is coming from the current basic block, +then the variable is marked as alive within the current basic block +and all of its predecessor basic blocks, until the basic block with the +defining instruction is encountered.
+ +We now have the information available to perform the live intervals analysis +and build the live intervals themselves. We start off by numbering the basic +blocks and machine instructions. We then handle the "live-in" values. These +are in physical registers, so the physical register is assumed to be killed by +the end of the basic block. Live intervals for virtual registers are computed +for some ordering of the machine instructions [1, N]. A live interval +is an interval [i, j), where 1 <= i <= j < N, for which a +variable is live.
+ +More to come...
+ +The Register Allocation problem consists in mapping a -program Pv, that can use an unbounded number of -virtual registers, to a program Pp that contains a -finite (possibly small) number of physical registers. Each target -architecture has a different number of physical registers. If the -number of physical registers is not enough to accommodate all the -virtual registers, some of them will have to be mapped into -memory. These virtuals are called spilled virtuals.
+The Register Allocation problem consists in mapping a program +Pv, that can use an unbounded number of virtual +registers, to a program Pp that contains a finite +(possibly small) number of physical registers. Each target architecture has +a different number of physical registers. If the number of physical +registers is not enough to accommodate all the virtual registers, some of +them will have to be mapped into memory. These virtuals are called +spilled virtuals.
-bool RegMapping_Fer::compatible_class(MachineFunction &mf,
+bool RegMapping_Fer::compatible_class(MachineFunction &mf,
unsigned v_reg,
unsigned p_reg) {
- assert(MRegisterInfo::isPhysicalRegister(p_reg) &&
+ assert(MRegisterInfo::isPhysicalRegister(p_reg) &&
"Target register must be physical");
const TargetRegisterClass *trc = mf.getSSARegMap()->getRegClass(v_reg);
return trc->contains(p_reg);
@@ -1558,11 +1652,31 @@ that people test.
The folowing target-specific calling conventions are known to backend:
+ +The PowerPC code generator lives in the lib/Target/PowerPC directory. The +code generation is retargetable to several variations or subtargets of +the PowerPC ISA; including ppc32, ppc64 and altivec. +
+LLVM follows the AIX PowerPC ABI, with two deviations. LLVM uses a PC +relative (PIC) or static addressing for accessing global values, so no TOC (r2) +is used. Second, r31 is used as a frame pointer to allow dynamic growth of a +stack frame. LLVM takes advantage of having no TOC to provide space to save +the frame pointer in the PowerPC linkage area of the caller frame. Other +details of PowerPC ABI can be found at PowerPC ABI. Note: This link describes the 32 bit ABI. The +64 bit ABI is similar except space for GPRs are 8 bytes wide (not 4) and r13 is +reserved for system use.
+The size of a PowerPC frame is usually fixed for the duration of a +function’s invocation. Since the frame is fixed size, all references into +the frame can be accessed via fixed offsets from the stack pointer. The +exception to this is when dynamic alloca or variable sized arrays are present, +then a base pointer (r31) is used as a proxy for the stack pointer and stack +pointer is free to grow or shrink. A base pointer is also used if llvm-gcc is +not passed the -fomit-frame-pointer flag. The stack pointer is always aligned to +16 bytes, so that space allocated for altivec vectors will be properly +aligned.
+An invocation frame is layed out as follows (low memory at top);
+| Linkage |
+
| Parameter area |
+
| Dynamic area |
+
| Locals area |
+
| Saved registers area |
+
| Previous Frame |
+
The linkage area is used by a callee to save special registers prior +to allocating its own frame. Only three entries are relevant to LLVM. The +first entry is the previous stack pointer (sp), aka link. This allows probing +tools like gdb or exception handlers to quickly scan the frames in the stack. A +function epilog can also use the link to pop the frame from the stack. The +third entry in the linkage area is used to save the return address from the lr +register. Finally, as mentioned above, the last entry is used to save the +previous frame pointer (r31.) The entries in the linkage area are the size of a +GPR, thus the linkage area is 24 bytes long in 32 bit mode and 48 bytes in 64 +bit mode.
+32 bit linkage area
+| 0 | +Saved SP (r1) | +
| 4 | +Saved CR | +
| 8 | +Saved LR | +
| 12 | +Reserved | +
| 16 | +Reserved | +
| 20 | +Saved FP (r31) | +
64 bit linkage area
+| 0 | +Saved SP (r1) | +
| 8 | +Saved CR | +
| 16 | +Saved LR | +
| 24 | +Reserved | +
| 32 | +Reserved | +
| 40 | +Saved FP (r31) | +
The parameter area is used to store arguments being passed to a callee +function. Following the PowerPC ABI, the first few arguments are actually +passed in registers, with the space in the parameter area unused. However, if +there are not enough registers or the callee is a thunk or vararg function, +these register arguments can be spilled into the parameter area. Thus, the +parameter area must be large enough to store all the parameters for the largest +call sequence made by the caller. The size must also be mimimally large enough +to spill registers r3-r10. This allows callees blind to the call signature, +such as thunks and vararg functions, enough space to cache the argument +registers. Therefore, the parameter area is minimally 32 bytes (64 bytes in 64 +bit mode.) Also note that since the parameter area is a fixed offset from the +top of the frame, that a callee can access its spilt arguments using fixed +offsets from the stack pointer (or base pointer.)
+Combining the information about the linkage, parameter areas and alignment. A +stack frame is minimally 64 bytes in 32 bit mode and 128 bytes in 64 bit +mode.
+The dynamic area starts out as size zero. If a function uses dynamic +alloca then space is added to the stack, the linkage and parameter areas are +shifted to top of stack, and the new space is available immediately below the +linkage and parameter areas. The cost of shifting the linkage and parameter +areas is minor since only the link value needs to be copied. The link value can +be easily fetched by adding the original frame size to the base pointer. Note +that allocations in the dynamic space need to observe 16 byte aligment.
+The locals area is where the llvm compiler reserves space for local +variables.
+The saved registers area is where the llvm compiler spills callee saved +registers on entry to the callee.
+The llvm prolog and epilog are the same as described in the PowerPC ABI, with +the following exceptions. Callee saved registers are spilled after the frame is +created. This allows the llvm epilog/prolog support to be common with other +targets. The base pointer callee saved register r31 is saved in the TOC slot of +linkage area. This simplifies allocation of space for the base pointer and +makes it convenient to locate programatically and during debugging.
+TODO - More to come.
+