Four live ranges L1/L2/L3/L4. Live range L1 for variable ‘a’ spans the loop but has no references ‘a’ inside the Loop.

similarly, live range L2 for variable ‘b’ spans the loop but has no references for ‘b’ inside the loop.

Live range L3 for ‘p’ spans the loop and has references for ‘p’ inside the loop. Similarly, Live range L4 for ‘q’ spans the loop and has reference for ‘q’ inside the loops.

 All live range L1/L2/L3/L4 are interfering each other as you see from the figure.

For example, there are 2 registers for the hardware Architecture.

Since all four live ranges interferes and there are 2 registers some of the live range has to be spilled.

 L1 and L2 has no reference inside the loop but spans the loop we can assign them to memory and so that there are chances of assign 2 registers (high frequency region) for live range L3 and L4.

For the cost calculation L1 and L2 loop back edge frequency will not be considered in the cost calculation and L3 and L4 cost is taken into consideration 

the cost become less for L3 and L4  and there are chances of  copy inside the loop will be coalesced for live range L3 and L4.

For Live range splitting L1 and L2 are the low frequency range whereas L3 and L4 are high frequency range.

That’s why we split the live range L1 and L2 with the low frequency region  around the high frequency range so that the transition is from low to high frequency range or high to low frequency range so that high frequency regions like L3 and L4 gets the registers.

In the above example we split L1 into L1’ and L1’’ and L2 is split into L2’ and L2’’ and then this is colorable with 2 registers.

For re-materializations instead of re-loading at each use points both inside the loops and outside the loops we keep it in registers at the split point of L1’ and L2’. Thus, remat points is the split points L1’ and L2’.