The register allocator

From Free Pascal wiki
Revision as of 18:36, 16 December 2013 by DanielS (talk | contribs)

Registry allocation in FPC

1. Introduction

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 on the place of 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.


2. 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.

2.1. 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 instances of TRgObj class. They are created when the code generation of specific routine begin. Code generator works on subroutine level. The registry allocator also allocates registers for specific method, procedure, function.

One TRgObj instance allocates registers of certain type. For example Integer registers. Thats way we have a few TRgObj instances, one for every type of register that the cpu supports.


2.2. Using registers in the code generation

Code generator uses TRgObj.getRegister to get register for some assembler instruction. This way an imaginary register is allocation and can be used after that in specific assembler instruction. There is another method if more than one imaginary register needs to be allocated - TRgObj.allocCpuRegisters

After allocation the register we can use it in some assembler instructions. For evry 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

         TRgObj.add_move_instruction(instr:Taicpu);

If an imaginary register is allocated, but later it becomes useless it can be deallocated by using the following methods

 ungetcpuregister - Free register specified.
 dealloccpuregisters - Free multiple registers specified.


2.3. Generating of real registers At the end when all the assemble instructions are generated we call

       do_register_allocation(list: TAsmList; headerTai: TAi)

It calculates real registers for the immaginary ones.


3. Tips

You can compile your project by using the -sr switch. This will leave the immaginary register names in the generated .s file

4. 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