Method and apparatus for determining a maximum number of live registers

The method for determining the maximum number of live registers in a computer system, said computer system having an executing computer program having at least one instruction that accesses said registers, said method comprising:

• including a read instruction in said instructions, and said live registers being associated with said read instruction;
• identifying at least two partitions in said computer program;
• associating events in said computer program with said instructions in a said, partition, and thereby associating said accessed registers with said events and said partition;
• wherein, for each said event:
• identifying when said event is associated with each said accessed register, determining when each said accessed register associated with said event is said live register, and representing said live registers associated with said event quantity by a number_of_live_registers variable associated with said event;
• identifying each said accessed register associated with said event as touched with respect to said event, and representing said touched registers associated with said event by a registers_with_known_information variable associated with said event;
• identifying said partition associated with said event and representing said partition by a partition variable associated with:
• said event;
• identifying each register pressure information variable associated with said event, said register pressure information variable including said number_of_live_registers variable associated with said event, said registers_with_known_information variable associated with said event, and said partition variable associated with said event;
• and recording said register pressure information variable associated with said event and said partition variable when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event and said partition variable represents said registers that have not been previously touched;
• combining said register pressure information variable corresponding to a previous said each event and said partition variable with said register pressure information variable corresponding to said event and said partition variable, when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event and said partition variable represents a said register that has not been previously touched;
• retaining said register pressure information variable corresponding to said previous each event and said partition variable when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event and said partition variable is equivalent to said registers with known information variable associated with said register pressure information variable corresponding to said previous each event and said partition variable;
• associating said register pressure information variable corresponding to said event and said partition variable with an uncertainty level variable that represents said registers associated with said event and said partition variable that have not been touched quantity;
• retaining said register pressure information variable with a largest value of said number_of_live_registers variable associated with said event and said partition variable when said register pressure information variable is associated with:
• different values of said number_of_live_registers variables associated with said event and said partition variable, and equivalent values of said registers_with_known_information variables associated with said event and said partition variable;
• and
• retaining one said register pressure information variable associated with said event and said partition variable when a plurality of said register pressure information variables is associated with said event and said partition variable, and said number_of_live_registers variables and said registers_with_known_information variables associated with said plurality of said register pressure information variables are equivalent;
• and
• determining a largest value of said number_of_live_registers variable associated with said events and said partition variable in said computer program and thereby identifying said maximum number of live registers associated with said partition in said computer system.

A register pressure apparatus for determining the maximum number of live registers in a computer system, said computer system having an executing computer program having at least one instruction that accesses said registers, said apparatus comprising:

• said instruction including a read instruction, and said live registers being associated with said read instruction;
• events in said computer program being associated with said instructions, and thereby said accessed registers being associated with said events;
• wherein, for each said event:
• a number_of_live_registers variable associated with said event, and when said live registers are associated with said event said number_of_live_registers variable representing said associated live registers quantity;
• a registers_with_known_information variable associated with said event and representing each said accessed register associated with said event as touched with respect to said event;
• each register pressure information variable associated with said event, said register pressure information variable including said number_of_live_registers variable associated with said event and said registers_with_known_information variable associated with said event, and said register pressure information variable associated with said event being recorded when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event represents said registers that have not been previously touched;
• said register pressure information variable corresponding to a previous said each event being combined with said register pressure information variable corresponding to said event, when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event represents a said register that has not been previously touched;
• said register pressure information variable corresponding to said previous each event being retained when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event is equivalent to said registers_with_known_information variable associated with said register pressure information variable corresponding to said previous each event;
• an uncertainty level variable that represents said registers associated with said event that have not been touched quantity, said uncertainty level variable being associated with said register pressure information variable corresponding to said event;
• said register pressure information variable with a largest value of said, number_of_live_registers variable associated with said event being retained when said register pressure information variable is associated with:
• different values of said number_of_live_registers variables associated with said event and equivalent values of said registers_with_known_information variables associated with said event;
• and
• one said register pressure information variable associated with said event being retained when a plurality of said register pressure information variables is associated with said event, and said number_of_live_registers variables and said registers_with_known_information variables associated with said plurality of said register pressure information variables are equivalent;
• and
• a largest value of said number_of_live_registers variable associated with said events in said computer program being identified and thereby said maximum number of live registers in said computer system being identified.

A register pressure apparatus for determining the maximum number of live registers in a computer system, said computer system having an executing computer program having at least one instruction that accesses said registers, said apparatus comprising:

• said instruction including a read instruction, and said live registers being associated with said read instruction;
• at least two partitions in said computer program;
• events in said computer program being associated with said instructions in a said partition, and thereby said accessed registers being associated with said events and said partition;
• wherein, for each said event:
• a number_of_live_registers variable associated with said event, and when said live registers are associated with said event said number_of_live_registers variable representing said associated live registers quantity;
• a registers_with_known_information variable associated with said event and representing each said accessed register associated with said event as touched with respect to said event;
• a partition variable associated with said event that represents said partition associated with said event;
• each register pressure information variable associated with said event, said register pressure information variable including said number_of_live_registers variable associated with said event, said registers_with_known_information variable associated with said event, and said partition variable associated with said event, and said register pressure information variable associated with said event and said partition variable being recorded when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event and said partition variable represents said registers that have not been previously touched;
• said register pressure information variable corresponding to a previous said each event and said partition variable, being combined with said register pressure information variable corresponding to said event and said partition variable, when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event and said partition variable represents a said register that has not been previously touched;
• said register pressure information variable corresponding to said previous each event and said partition variable, being retained when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event and said partition variable is equivalent to said registers_with_known_information variable associated with said register pressure information variable corresponding to said previous each event and said partition variable;
• an uncertainty level variable that represents said registers associated with said event and said partition variable that have not been touched quantity, said uncertainty level variable being associated with said register pressure information variable corresponding to said event and said partition variable;
• said register pressure information variable with a largest value of said number_of_live_registers variable associated with said event and said partition variable, being retained when said register pressure information variable is associated with:
• different values of said number_of_live_registers variables associated with said event and said partition variable, and equivalent values of said registers_with_known_information variables associated with said event and said partition variable;
• and
• one said register pressure information variable associated with said event and said partition variable, being retained when a plurality of said register pressure information variables is associated with said event and said partition variable, and said number_of_live_registers variables and said registers_with_known_information variables associated with said plurality of said register pressure information variables are equivalent;
• and
• a largest value of said number_of_live_registers variable associated with said events and said partition variable, in said computer program being identified and thereby said maximum number of live registers associated with said partition in said computer system being identified.

An article of manufacture comprising a program storage medium having computer readable program code embodied therein for determining the maximum number of live registers in a computer system, said computer system having an executing computer program having computer readable program code including at least one instruction that accesses said registers, said article of manufacture comprising:

• computer readable code for including a read instruction in said instructions, and said live registers being associated with said read instruction;
• computer readable program code for associating events in said computer program with said instructions, and thereby associating said accessed registers with said events;
• wherein, for each said event:
• computer readable program code for identifying when said event is associated with each said accessed register, determining when each said accessed register associated with said event is said live register, and representing said live registers associated with said event quantity by a number_of_live_registers variable associated with said event;
• computer readable program code for identifying each said accessed register associated with said event as touched with respect to said event, and representing said touched registers associated with said event by a registers_with_known_information variable associated with said event;
• computer readable program code for identifying each register pressure information variable associated with said event, said register pressure information variable including said number_of_live_registers variable associated with said event and said registers_with_known_information variable associated with said event, and recording said register pressure information variable associated with said event when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event represents said registers that have not been previously touched;
• computer readable program code for combining said register pressure information variable corresponding to a-previous said each event with said register pressure information variable corresponding to said event, when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event represents a said register that has not been previously touched;
• computer readable program code for retaining said register pressure information variable corresponding to said previous each event when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event is equivalent to said registers_with_known_information variable associated with said register pressure information variable corresponding to said previous each event;
• computer readable program code for associating said register pressure information variable corresponding to said event with an uncertainty level variable that represents said registers associated with said event that have not been touched quantity;
• computer readable program code for retaining said register pressure information variable with a largest value of said number_of_live_registers variable associated with said event when said register pressure information variable is associated with:
• different values of said number_of_live_registers variables associated with said event and equivalent values of said registers_with_known_information variables associated with said event;
• and
• computer readable program code for retaining one said register pressure information variable associated with said event when a plurality of said register pressure information variables is associated with said event, and said number_of_live_registers variables and said registers_with_known_information variables associated with said plurality of said register pressure information variables are equivalent;
• and
• computer readable program code for determining a largest value of said number_of_live_registers variable associated with said events in said computer program and thereby identifying said maximum number of live registers in said computer system.

An article of manufacture comprising a program storage medium having computer readable program code embodied therein for determining the maximum number of live registers in a computer system, said computer system having an executing computer program having computer readable program code including at least one instruction that accesses said registers, said article of manufacture comprising:

• computer readable program code for including a read instruction in said instructions, and said live registers being associated with said read instruction;
• computer readable program code for identifying at least two partitions in said computer program;
• computer readable program code for associating events in said computer program with said instructions in a said partition, and thereby associating said accessed registers with said events and said partition;
• wherein, for each said event:
• computer readable program code for identifying when said event is associated with each said accessed register, determining when each said accessed register associated with said event is said live register, and representing said live registers associated with said event quantity by a number_of_live_registers variable associated with said event;
• computer readable program code for identifying each said accessed register associated with said event as touched with respect to said event, and representing said touched registers associated with said event by a registers_with_known_information variable associated with said event;
• computer readable program code for identifying said partition associated with said event and representing said partition by a partition variable associated with said event;
• computer readable program code for identifying each register pressure information variable associated with said event, said register pressure information variable including said number_of_live_registers variable associated with said event, said registers_with_known_information variable associated with said event, and said partition variable associated with said event, and recording said register pressure information variable associated with said event and said partition variable when said registers with known information variable associated with said register pressure information variable corresponding to said event and said partition variable represents said registers that have not been previously touched;
• computer readable program code for combining said register pressure information variable corresponding to a previous said each event and said partition variable with said register pressure information variable corresponding to said event and said partition variable, when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event and said partition variable represents a said register that has not been previously touched;
• computer readable program code for retaining said register pressure information variable corresponding to said previous each event and said partition variable when said registers_with_known_information variable associated with said register pressure information variable corresponding to said event and said partition variable is equivalent to said registers_with_known_information variable associated with said register pressure information variable corresponding to said previous each event and said partition variable;
• computer readable program code for associating said register pressure information variable corresponding to said event and said partition variable with an uncertainty level variable that represents said registers associated with said event and said partition variable that have not been touched quantity;
• computer readable program code for retaining said register pressure information variable with a largest value of said number_of_live_registers variable associated with said event and said partition variable when said register pressure information variable is associated with:
• different values of said number_of_live_registers variables associated with said event and said partition variable, and equivalent values of said registers_with_known_information variables associated with said event and said partition variable;
• and
• computer readable program code for retaining one said register pressure information variable associated with said event and said partition variable when a plurality of said register pressure information variables is associated with said event and said partition variable, and said number_of_live_registers variables and said registers_with_known_information variables associated with said plurality of said register pressure information variables are equivalent;
• and
• computer readable program code for determining a largest value of said number_of_live_registers variable associated with said events and said partition variable in said computer program and thereby identifying said maximum number of live registers associated with said partition in said computer system.

A computer readable memory device encoded with a data structure having entries, for determining the maximum number of live registers in a computer system, said computer system having an executing computer program entry having at least one instruction entry that accesses said registers, said memory device comprising:

• said instruction entry including a read instruction entry, and said live registers being associated with said read instruction entry;
• event entries in said computer program entry being associated with said instruction entries, and thereby said accessed registers being associated with said event entries;
• wherein, for each said event entry:
• a number_of_live_registers variable entry associated with said event entry, and when said live registers are associated with said event entry said number_of_live_registers variable entry representing said associated live registers quantity;
• a registers_with_known_information variable entry associated with said event entry and representing each said accessed register associated with said event entry as touched with respect to said event entry;
• each register pressure information variable entry associated with said event entry, said register pressure information variable entry including said number_of_live_registers variable entry associated with said event entry and said registers_with_known_information variable entry associated with said event entry, and said register pressure information variable entry associated with said event entry being recorded when said registers_with_known_information variable entry associated with said register pressure information variable entry corresponding to said event entry represents said registers that have not been previously touched;
• said register pressure information variable entry corresponding to a previous said each event entry being combined with said register pressure information variable entry corresponding to said event entry, when said registers_with_known_information variable entry associated with said register pressure information variable entry corresponding to said event entry represents a said register that has not been previously touched;
• said register pressure information variable entry corresponding to said previous each event entry being retained when said registers_with_known_information variable entry associated with said register pressure information variable entry corresponding to said event entry is equivalent to said registers_with_known_information variable entry associated with said register pressure information variable entry corresponding to said previous each event entry;
• an uncertainty level variable entry that represents said registers associated with said event entry that have not been touched quantity, said uncertainty level variable entry being associated with said register pressure information variable entry corresponding to said event entry;
• said register pressure information variable entry with a largest value of said number_of_live_registers variable entry associated with said event entry being retained when said register pressure information variable entry is associated with:
• different values of said number_of_live_registers variable entries associated with said event entry and equivalent values of said registers_with_known_information variable entries associated with said event entry;
• and
• one said register pressure information variable entry associated with said event entry being retained when a plurality of said register pressure information variable entries is associated with said event entry, and said number_of_live_registers variable entries and said registers_with_known_information variable entries associated with said plurality of said register pressure information variable entries are equivalent;
• and
• a largest value of said number_of_live_registers variable entry associated with said event entries in said computer program being identified and thereby said maximum number of live registers in said computer system being identified.