Live range splitting optimization.

There is an important concept above the Live range splitting. If the interference graph is not colorable then the allocator goes for Live range splitting, and it splits the live ranges. This makes the graph colorable. There are different algorithm for live range splitting. They are as following.

Briggs decides on live range splitting at the points of phi nodes for ssa graph. And later they are given the priority for splitting the live range across the loop boundary. If the live range spans across the loop and there is no reference inside the loop then the live range is split across the loop boundary which reduces the spill and fetch inside the loops.

Fred Chow live range splitting is based on the concept of splitting the live ranges based on colorobility. It identifies the nodes which has def and the list grows in breadth first order and keep on adding to the list the list that corresponds to the shorter live range is colorable. If the live ranges grows and it stops the point where it is not colorable. This is the concept of live range splitting by Fred Chow.

Because of the Live range splitting the shuffle code is generated. If the live ranges after splits and the shorter live ranges become partner. And if the shorter live range L1 got the register and the partner live ranges is in memory there is a store gets generated. If the L1 is in memory and its partner is L2 is in register, then load is generated. If the L1 gets a register(r1) and L2 its partner gets a different register(r2) then there is move will be generated from register r1 to r2.

Carol Thompson does the live range splitting based on containment of the Live ranges. If the live range L2 is contained inside the live range L1 then L1 is split at the start and death of L2 and there is store at the start of L2 and load at the death of L2 for the live range L1. They split the live range based on containment graph which is compile time constraints.

There is a concept of passive splitting which reduces the spill and fetch inside the loop. If the Live ranges L1 spans across the loop and the contained live ranges L2 is inside the loop then the splitting causes a store and load inside the loop which is getting rid of by passive splitting while doing simplification pushing the nodes in the stack. The passive splitting also takes care of the live range spans the loop and there is no reference inside the loop there should be a splitting across the loop boundary which reduces the spill and fetch inside the loops.