Patent ID: 7949857

Claim:
A method for selecting a predetermined number of unused registers in a processor comprising: partitioning a plurality of registers in a processor into a first plurality of subsets, wherein the number of subsets of the first plurality of subsets is equal to the predetermined number of unused registers that is to be selected; partitioning the plurality of registers into a second plurality of subsets, wherein the number of subsets of the second plurality of subsets is equal to the predetermined number of unused registers that is to be selected and wherein each subset of the second plurality of subsets comprises a different combination of registers than each subset of the first plurality of subsets; searching each subset of the first plurality of subsets for an unused register; searching each subset of the second plurality of subsets for an unused register, wherein searching the second plurality of subsets is performed in parallel with searching the first plurality of subsets; determining whether every subset of the first plurality of subsets includes an unused register; determining whether every subset of the second plurality of subsets includes an unused register in response to determining that every subset of the first plurality of subsets includes an unused register, selecting an unused register from each subset of the first plurality of subsets; in response to determining that at least one subset of the first plurality of subsets does not include an unused register and that every subset of the second plurality of subsets includes an unused register, selecting an unused register from each subset of the second plurality of subsets; and in response to determining that at least one subset of the first plurality of subsets does not include an unused register and that at least one subset of the second plurality of subsets does not include an unused register, searching each register serially to find the predetermined number of unused registers.