Patent ID: 8732680

Claim:
A method for performing register allocation, comprising the steps of: representing a program in width-single static assignment (W-SSA) form, wherein said representing comprises: creating one or more sub-variables for each of a plurality of variables in the program; and maintaining a single size of each of the plurality of variables throughout a life-span of each of the plurality of variables; coalescing the plurality of variables based on a size determination for each variable to produce a plurality of coalesced variables, wherein said coalescing comprises: coalescing, for each distinct variable size among the plurality of variables, non-interfering variables having the same size so as not to increase the bit pressure at any program point; removing each pair of interfering variables from the plurality of variables; creating a new coalesced variable to replace each pair of removed interfering variables; and adding the new coalesced variable to the plurality of coalesced variables; packing the plurality of coalesced variables; and using the plurality of packed variables to perform register allocation.