The register allocator
Registry allocation in FPC
Main unit for the registry allocation is rgobj.pas
Main class for the registry allocation is TRgObj located in rgobj.pas
Registry allocator provides imaginary registers for the assembler instructions during the code generation. Then it calculates the real registers to replace the imaginary ones.
The fpc registry allocator uses the Registry coloring for determining the real registers. Also uses registry spilling technique - when there is not enough registers it uses the memory.
How to use the registry allocator
This topic describes how to use the registry allocator during the code generation.
Described like a black box with the public methods you can call to get job done.
Creating the Registry allocator
Creating registry allocator is the first step we make before we can use its functionality.
The low level code generator creates several instances of the TRgObj class. Each TRgObj instance allocates registers of a certain type. For example, one register type is Integer registers. Another one is floating point (FPU) registers. That's why we have a few TRgObj instances, one for every type of register that the cpu supports.
They are created when the code generation of specific routine begins. Code generator works on subroutine level. The registry allocator also allocates registers for specific method, procedure, function.
Using registers in the code generation
To allocate a register, the code generator uses one of the following functions:
tcg.GetIntRegister tcg.GetAddressRegister tcg.GetFPURegister tcg.GetMMRegister
which in turn call:
for the appropriate register allocator instance (depending on the register type) to get register for some assembler instruction. This way an imaginary register is allocated and can be used after that in a specific assembler instruction.
Additionally, the following methods:
getcpuregister ungetcpuregister alloccpuregisters dealloccpuregisters
allocate or free one or multiple real registers (not imaginary ones!) This is usually used for instructions that require a specific register (for example SHL/SHR/SAR on x86, which always uses ECX). This is also used when doing a function call to indicate that certain registers (which depend on the calling convention) may be destroyed by the called function.
After allocating the register we can use it in some assembler instructions. For every instruction that generates, the code generator notifies the registry allocator. It passes the instruction, also the imaginary register as parameters to the following method.
TRgObj.add_reg_instruction(instr, r, cg.executionweight);
But for MOV instruction there is specific method that is used
Generating of real registers
At the end when all the assembler instructions are generated we call
do_register_allocation(list: TAsmList; headerTai: TAi)
It calculates real registers for the imaginary ones.
You can compile your project by using the -sr switch. This will leave the immaginary register names in the generated .s file
Calls hierarchy for the public methods
Public constructor destructor do_register_allocation - level 1 is ordered by calling insert_regalloc_info_all generate_interference_graph add_edges_used(1, 2) get_alias add_edge add_edge ibitmap.s prepare_colouring make_work_list ri_coalesced sort_simplify_worklist colour_registers simplify ri_coalesced decrement_degree ri_coalesced coalesce get_alias simplifyworklist.add(v); ibitmap conservative ri_coalesced adjacent_ok ri_coalesced ibitmap add_worklist simplifyworklist.add(u); combine ibitmap, add_edge enable_moves decrement_degree ri_coalesced simplifyworklist.add(m) add_edge ibitmap.s freeze freeze_moves(, 2) get_alias(3) select_spill freeze_moves(, 2) get_alias(3) assign_colours(, 2) get_alias epilogue_colouring Destroys the objects used during the coloring - worklist_moves, active_moves, frozen_moves, coalesced_moves, constrained_moves, reginfo.movelist spill_registers clear_interferences ibitmap.s instr_spill_register get_alias getregisterinline add_edges_used(2, 2) get_alias add_edge ibitmap.s ungetregisterinline get_spill_subreg do_spill_replace do_spill_read do_spill_written translate_registers assign_colours(, 2) get_alias getregister add_move_instruction add_to_movelist combine ri_coalesced(s) enable_moves decrement_degree ri_coalesced ----------------------------------------- Properties live_range_direction set_live_range_direction live_start get_live_start set_live_start live_end get_live_end set_live_end
Main class for registry allocation in FPC
Storing imaginary registers
TRgObj stores the imaginary registers in list of TRegInfo structure.
Life of imaginary register
Life of imaginary register starts when it is first used by assembler instruction.
When it first appears in an assembler instruction in the assembler list for the specific routine.
And ends when it is last used in an assembler instruction. In the TRegInfo structure for the specific imaginary register there are 2 fields for the life of the register.
live_start: TAi; indicates which is the assembler instruction where the register is first used.
live_end: TAi; indicates which is the assembler instruction where the register is last used.