Compilation using two-colored pebbling register allocation method such that spill code amount is invariant with basic block's textual ordering

Claim 1

A method for allocating and optimizing register assignments during the compiling of source into executable code in either a scalar or a vector processor, the source code including regions of code without branches termed "basic blocks", each basic block having statements defining computations, each processor comprising memory for storing sequences of executable code and data, and means for accessing said memory and executing any accessed code; the memory being mapped as a two-level model including a finite number p greater than 0 of registers and a comparably infinite internal memory, said registers having access times faster than that of internal memory, comprising the processor-implemented steps of: (a) ascertaining data dependency graph attributes of each basic block; (b) generating a local register allocation and assignment for q of the p registers in the range 0<q<p with reference to all computations within each basic block by performing a "two-color pebbling game" heuristic over the ascertained data dependency graph utilizing the two-level memory model; and (c) performing live variable analysis upon a flow graph-like representation of the basic blocks and responsively generating a global register allocation and assignment among (p-q) remaining registers assuming that loops expressed in the flow graph among the basic blocks are the most significant optimization entity.

Claim 2

A method for allocating and optimizing register assignments during the compiling of source into executable code in either a scalar or a vector processor, the source code including regions of code without branches termed "basic blocks", each basic block having statements defining computations, each processor comprising memory for storing sequences of executable code and data, and means for accessing said memory and executing any accessed code; the memory being mapped as a two-level model including a finite number p greater than 0 of registers and a comparably infinite internal memory, said registers having access times faster than that of internal memory, comprising the processor-implemented steps of: (a) ascertaining data dependency graph attributes of each basic block; (b) generating a local register allocation and assignment for q of the p registers in the range 0<q<p with reference to all computations within each basic block by performing a "two-color pebbling game" heuristic over the ascertained data dependency graph utilizing the two-level memory model; and (c) performing live variable analysis upon a flow graph-like representation of the basic blocks and responsively generating a global register allocation and assignment among (p-q) remaining registers assuming that loops expressed in the flow graph among the basic blocks are the most significant optimization entity.