Computing system operating to assign registers to data

Claim 2

A computing system including a main storage and a plurality of unlike subsets of registers, said system operating to assign registers to quantities in response to requests for those quantities to be entered in registers, said requests occuring serially in an input instruction stream, identifying a register subset and being detected during a serial scan of the input instruction stream, said system being characterised in that upon detection of a request for a register to be assigned to a quantity, firstly determining whether or not a subset register is already assigned to the quantity and whether or not the quantity is included in a list of quantities to which subset registers are to be assigned; secondly, if a subset register is not already assigned to the quantity and the quantity is not included in the pending list, entering the quantity into the pending list together with a complete set count indicative of the total number of registers for which the quantity is not a candidate; and thirdly if a subset register is already assigned to the quantity or the quantity is included in the pending list, incrementing by an amount corresponding to the length of the quantity the complete set counts of quantities in the pending list which are candidates for the same subset of registers as the quantity, testing the incremented complete set count to detect a count value corresponding to availability of a register or registers in the subset of register identified in the register request for the quantity associated with the count value being tested, and, upon detection of such correspondence, assigning the associated quantity to the available register(s) of the identified subset of registers.

Claim 3

A computing system as claimed in claim 1 further characterised in that the quantities to which registers are assigned comprise both symbolic quantities referenced in the input stream and the addressability of such quantities, the assignments being integrated into one scan.

Claim 4

A computing system as claimed in claim 1 or 2 in which the input instruction stream comprises a plurality of blocks of instructions, each block being identified by a label, said system being further characterised by determining, during the serial scan of the input instruction stream, the presence of favourable labels (as hereinbefore defined) identifying instruction blocks, and references to labels; and, when the presence of a reference to a label is determined, saving the register state; whereas when the presence of a favourable label is determined, assigning quantities to registers from the set of pending registers quantities irrespective of their complete set count, thus defining a current register state immediately prior to the label; and assigning quantities to registers to form a new register state at the label, the new register state being selectively the saved state, if access to the label is from an unconditional branch, and otherwise, the ordered intersection of the current and saved states.

Claim 5

A computing system for compiling an input instruction stream, having a plurality of instructions including requests for quantities in a register, comprising: means for determining, during a serial scan of the instruction stream, requests for new and reuse quantities in a register; means responsive to the determination of a request for a new quantity in a register for logging the quantity to a pending set of requests for quantities in a register with a complete set count indicative of the total number of registers for which the quantity is not a candidate; means responsive to the determination of a request for a reuse quantity assigned to a register or logged to the pending set for incrementing the complete set count of quantities in the pending set, and for testing for complete sets; means for assigning to registers those quantities for which a complete set is detected.

Claim 6

A computing system for compiling an input instruction stream, having a plurality of instructions including requests for quantities in a register, comprising: means for determining, during a serial scan of the instruction stream, requests for new and reuse quantities in a register; means responsive to the determination of a request for a new quantity in a register for logging the quantity to a pending set of requests for quantities in a register with a complete set count indicative of the total number of registers for which the quantity is not a candidate; means responsive to the determination of a request for a reuse quantity assigned to a register or logged to the pending set for incrementing the complete set count of quantities in the pending set, and for testing for complete sets; means for assigning to registers those quantities for which a complete set is detected.

Claim 7

A computing system operating during compilation of an input instruction stream to assign registers to symbolic quantities referenced in the input instructions, the input stream comprising instructions arranged in a plurality of blocks of straight line code, the system generating a compiled instruction stream which optimizes register manipulation during subsequent execution of the compiled instruction stream, the operation of the system being characterised by the steps of: (1) during a serial scan of the input instruction stream, determining register usage for quantities, the presence of favorable labels identifying blocks, and references in instructions to labels; (2) upon determining during step (1) the need for a quantity in a register, enqueuing the quantity in a set of pending register requests with a complete set count representing the number of registers for which the quantity is not a candidate; (3) upon determining during step (1) the reuse of a quantity in a register or in the set of pending register requests, incrementing the complete set counts of quantities in the set of pending register requests that are candidates for the same registers as the reuse quantity and testing the complete set counts for complete set; (4) assigning to registers quantities for which a complete set is reached during step (3); (5) upon determining during step (1) the presence of a reference to a label, saving the register state; (6) upon determining during step (1) the presence of a favorable label, assigning to registers quantities in the set of pending requests irrespective of their complete set counts, thereby forming a current register state; and assigning registers to quantities to form a new state at the label, the new state being selectively the saved state, if the label is reached only from an unconditional branch or, otherwise, being the ordered intersection of the current and saved states.

Claim 8

A computing system operating during compilation of an input instruction stream to assign registers to symbolic quantities referenced in the input instructions, the input stream comprising instructions arranged in a plurality of blocks of straight line code, the system generating a compiled instruction stream which optimizes register manipulation during subsequent execution of the compiled instruction stream, the operation of the system being characterised by the steps of: (1) during a serial scan of the input instruction stream, determining register usage for quantities, the presence of favorable labels identifying blocks, and references in instructions to labels; (2) upon determining during step (1) the need for a quantity in a register, enqueuing the quantity in a set of pending register requests with a complete set count representing the number of registers for which the quantity is not a candidate; (3) upon determining during step (1) the reuse of a quantity in a register or in the set of pending register requests, incrementing the complete set counts of quantities in the set of pending register requests that are candidates for the same registers as the reuse quantity and testing the complete set counts for complete set; (4) assigning to registers quantities for which a complete set is reached during step (3); (5) upon determining during step (1) the presence of a reference to a label, saving the register state; (6) upon determining during step (1) the presence of a favorable label, assigning to registers quantities in the set of pending requests irrespective of their complete set counts, thereby forming a current register state; and assigning registers to quantities to form a new state at the label, the new state being selectively the saved state, if the label is reached only from an unconditional branch or, otherwise, being the ordered intersection of the current and saved states.

Claim 9

A computing system for compiling a machine readable input instruction stream into a machine executable instruction stream, comprising: input storage means (60) for storing a plurality of input instructions, selected instructions including symbolic designations for quantities to be assigned to registers; output storage means (70) for storing a plurality of executable instructions, including register manipulation instructions; temporary storage means (80) for storing instructions read from said input storage means (60) until the register state for the instruction is defined and the instruction written into said output storage means (70); pending queue means (92) for storing pending requests for quantities in a register; complete set pointer means (24) for identifying the last pending request added to said pending queue means for which a complete set has been determined; current load point counter means (25) for identifying the location in temporary storage (80) of a current load point instruction; pass one processor means (64) for writing instructions from input storage means (60) into temporary storage means 80, for adding to said pending queue means (92) requests to save register states at references to labels, and for generating from said instructions, requests for quantities in a register; register manager means (65) responsive to requests for quantities in a register for recursively generating requests for addressability quantities in a register; for adding to pending queue means (92) requests for new quantities with a complete set count indicative of the number of registers for which the quantity is not a candidate; for adding reuse quantities to the complete set count of pending requests in queue means (92); and, upon detecting a complete set, for updating complete set pointer means (24) to reference the quantity having the complete set; register assigner means (66) selectively responsive to the detection of a complete set and to the presence of a label for generating a write call to write all instructions prior to that referenced by said current load point counter means; pass two processor means (69) responsive to the write call for detecting requests for symbolic or addressability registers and, thereupon, for generating a resolve call; and register resolver means (68) responsive to the resolve call for resolving requests for symbolic or addressability registers by assigning the register request to a location in register list (91).

Claim 10

A computing system for compiling a machine readable input instruction stream into a machine executable instruction stream, comprising: input storage means (60) for storing a plurality of input instructions, selected instructions including symbolic designations for quantities to be assigned to registers; output storage means (70) for storing a plurality of executable instructions, including register manipulation instructions; temporary storage means (80) for storing instructions read from said input storage means (60) until the register state for the instruction is defined and the instruction written into said output storage means (70); pending queue means (92) for storing pending requests for quantities in a register; complete set pointer means (24) for identifying the last pending request added to said pending queue means for which a complete set has been determined; current load point counter means (25) for identifying the location in temporary storage (80) of a current load point instruction; pass one processor means (64) for writing instructions from input storage means (60) into temporary storage means 80, for adding to said pending queue means (92) requests to save register states at references to labels, and for generating from said instructions, requests for quantities in a register; register manager means (65) responsive to requests for quantities in a register for recursively generating requests for addressability quantities in a register; for adding to pending queue means (92) requests for new quantities with a complete set count indicative of the number of registers for which the quantity is not a candidate; for adding reuse quantities to the complete set count of pending requests in queue means (92); and, upon detecting a complete set, for updating complete set pointer means (24) to reference the quantity having the complete set; register assigner means (66) selectively responsive to the detection of a complete set and to the presence of a label for generating a write call to write all instructions prior to that referenced by said current load point counter means; pass two processor means (69) responsive to the write call for detecting requests for symbolic or addressability registers and, thereupon, for generating a resolve call; and register resolver means (68) responsive to the resolve call for resolving requests for symbolic or addressability registers by assigning the register request to a location in register list (91).