Patent ID: 6925639

Claim:
A method of inserting spill code to handle a set of spilled variables, the spilled variables being identified by a register allocation procedure, into a plurality of instructions generated by a compiler, the spill code adapted for a CISC machine having registers used when executing instructions, comprising: (a) processing each instruction in reverse order in the plurality of instructions by: (i) when a variable within the instruction is dead after the instruction: (1) generating a spill code load instruction for each spilled variable included in a set of spilled variables to be loaded, the set of spilled variables to be loaded being a subset of the set of spilled variables; (2) removing all variables from the set of spilled variables to be loaded; and (3) removing all entries from a mapping from spilled variables to temporary variables; (ii) determining if the instruction includes a variable in the set of spilled variables, and if so, for each such variable: (1) adding an entry to the mapping from spilled variables to temporary variables; determining if the mapping maps the spilled variable to a temporary variable, and if it not, then adding the spilled variable to a set of variables that are to be loaded; creating the temporary variable; and updating the mapping from spilled variables to temporary variables to map the spilled variable to the temporary variable; (2) generating a store instruction to store the variable to the stack location if a store to a stack location for the variable is necessary, and (iii) generating a substitute instruction by applying the mapping from spilled variables to temporary variables; (b) generating a spill code load instruction for each variable in the set of spilled variables to be loaded; (c) counting a number of places where the temporary variable associated with the spilled variable has been substituted for the spilled variable; (d) tracking a location of each such temporary variable within the plurality of instructions; and (e) generating spill code based on the number of places where each temporary variable associated with the spilled variable has been substituted for the spilled variable and the location of each temporary variable; and (f) inserting the generated instructions.