What Is an Index Register?

Register (Register) is one of the components in the central processing unit. Register access is the fastest, and it can fully coordinate with the CPU, but the price is very expensive, so the capacity cannot be very large. Registers are high-speed storage units with limited storage capacity. They can be used to temporarily store instructions, data, and addresses. The register allocation program refers to a program that allocates and reclaims registers and provides a management mechanism for data movement between storage levels.

In the operating system, the main task of memory management is to provide a good environment for the running of multiple programs, to facilitate users to use the memory, to improve the utilization of the memory, and to expand the memory logically. Register management is an important content of memory management. Register access is very fast, close to the speed of the CPU, but the price of registers is very expensive. In order to make full use of the register resources, the register allocation program refers to a program that manages register allocation, reclamation, and other operations. The main purpose of the register allocation program is to make the system run more jobs per unit time and improve system efficiency.

MOVE Register Allocator Generates MOVE Instruction

When the destination and source registers should be the same, a MOVE instruction is generated to satisfy the constraints of the double operand instruction.

The instruction scheduler Register allocation program instruction schedule (The instruction scheduler)

Reduce "register pressure" (ie, shortage of hard registers during allocation).

Register allocation program looks for register class

A preferred and alternative register class is found for each pseudo-register to be allocated.

Code selection is performed secretly.

Scan general information about pseudo registers (number of references, number of assignments, first and last instructions referencing pseudo registers).

Register allocation program local allocation

Hard registers are allocated to pseudo-registers active in a basic block. The result is stored in the global array reg_renumber.

Perform some register stitching work. For example, if two or more non-conflicting pseudo registers are shuffled by several MOVE instructions, they can usually be allocated to the same hard register. Perform simple copy propagation and constant propagation.

Register Allocation Program Global Allocation

Hard registers are allocated to pseudo-registers active in multiple basic blocks. When it finds hard registers that are more advantageous than local allocations, it may change the results of local allocations. Generate a bit vector for each pseudo-register that contains hard registers that conflict with the pseudo-registers, build a conflict graph for each pseudo-register, and sort all pseudo-registers according to the following priority values:
(log2 (Nrefs) * Freq / Live_Length) * Size
Here Nrefs is the number of times the pseudo register appears, Freq is the frequency it uses, Live_Length is the length of the active range of the pseudo register in the instruction, and Size is its size in the hard register. After that, the global allocator tries to assign hard registers to pseudo-registers in order of priority from high to low.
If a hard register is obtained for the current pseudo register, the hard register is added to the hard register conflict vector (of all pseudo registers that conflict with the pseudo register). By assigning a pseudo register to a hard register, an attempt is made to join the pseudo register encountered in the MOVE instruction with the hard register.

reload Register Allocator Reload Phase

If the operands in the RTL do not satisfy the constraints, then it is converted to satisfy these constraints. The pseudo-registers here may be converted to hard registers, memory, or constants.

Reload follows global and local allocations, and it may change the assignment of the former two as needed.

For example: if hard register A is assigned to pseudo register V1, but the instruction referencing V1 requires other register classes, it will generate

MOVE A to C

MOVE C to B

Among them, B is a hard register satisfying the V1 instruction register class, and C may be a memory. If B or C is already occupied by the pseudo-register V2, the retry_global function in global.c is called to allocate another hard register for V2. If the allocation fails, V2 is placed on the program's stack.

Eliminate virtual hard registers (such as actual pointers) and actual hard registers (such as frame pointers).

For those hard registers that overflow, and pseudo-registers that do not eventually get the hard registers, stack slots are assigned to them.

postreload Register allocator postreload phase

According to the basic block context, delete unnecessary move, load, store and other instructions generated during the reload phase.