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

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.