Spilling in Compiler

Introduction :

We all know that in a computer or on any other device which is used for running the binaries, all the data and instructions get stored in main memory or primary memory.?

During the execution of instructions, these instructions have to be transferred to the CPU, which is also known as the processing unit. This CPU is the place where instructions get executed or the operations are performed. Depending on the type of instruction and if there is any result, it is sent back to the memory.

Now the question arises where do the data and instruction get stored inside the CPU during execution?
The answer is Register.        

Idea About Register

A hardware unit that acts as a storage area that can be quickly accessed by the CPU or processing unit is known as a register. These registers mainly store the address of an instruction, the instruction itself, as well as the result of an operation, which can later be loaded into memory. The variables which are used in high-level programming languages are stored in the registers, or rather they are allocated to a particular register during the execution of the program.

A compiler front end gives output as an intermediate representation which may have an infinite number of the register. Even in a programming language, there might be a number of variables used, which are required to be stored in the register for faster access, making the program execute fast.

In this two scenario compiler have to take a decision on how to allocate the variable in the register. As hardware has a limited number of registers then it's a compiler's job to translate these virtual registers to real registers in the backend or synthesis phase.

What is Spilling?

The technique or methodology in which a variable is moved out from a register space to the main memory i.e. RAM to make space for other variables, which are to be used in the program currently under execution.

This technique or methodology is known as Spilling.

Why We Required Spilling?

Spilling is done in order to satisfy the below condition:-

1. Parameter Passing in Function –?

Parameters are arguments that are passed to a function. When they cannot be passed into registers, they are stored in memory locations.

2. To keep debug information –

When we have to get debug information (-g) then we have to store the line number and file name to get the dwarf to debug info. Spilling is useful here.

3. Avoid Register Allocation Failures –?

This happens, when there is a limited number of registers to hold the live variables, hence they are swapped between register and memory.

This is also when our IR has an infinite number of registers and we want to store them in the limited number of registers.

4. Dynamic Allocations –?

A programmer may need to add names, which are generated during the run-time. As registers are statically named, the compiler relies on the memory for dynamic name generation.

5. During Function Calls -

The body of the called function accesses the entire set of registers, due to which a number of saves and restore occurs. To overcome the overhead, memory references are made, which is possible using spilling.

Advantages of the Spilling

It has some advantages, which are mentioned below –

1. The biggest advantage is an increase in the performance of the hardware.
2. The access time is lower than that of a cache(for small spills).