×

Digital computer register allocation and code spilling using interference graph coloring

  • US 5,249,295 A
  • Filed: 03/08/1993
  • Issued: 09/28/1993
  • Est. Priority Date: 06/20/1990
  • Status: Expired due to Term
First Claim
Patent Images

1. A machine-executed method for allocating a plurality R of internal registers of a computer for the storage of a plurality of values to be defined and reference during execution of a program by said computer, wherein each one of said plurality of values is "live" during a particular portion of the execution of said program, said particular portion being referred to as a "live range" of said each one value, and wherein two lives range overlapping is referred to as an "interference", the method comprising the steps of:

  • (a) constructing an interference graph having one node for each live range of said program and an edge for each interference between two live ranges;

    (b) assigning one of R distinct colors to each node in said graph such that no two of said nodes which are connected by one of said edges are assigned the same one of said R colors, leaving any given nod uncolored when said given node cannot be assigned a color different from all others of nodes which are connected to said given node;

    (c) for each node left uncolored in step (b), modifying said program such that certain ones of said live ranges corresponding to said uncolored nodes are transformed into a plurality of smaller live ranges;

    (d) repeating steps (a) through (c) above until no nodes in said interference graph are left uncolored in step (b);

    (e) assigning each one of said R colors to a unique one of said R registers, the assignment of a particular one of said R colors to a particular one of said R registers signifying that a value whose live range was represented in step (a) by node to which said particular one of said R colors was assigned in step (b) above will be stored in said particular register.

View all claims
  • 0 Assignments
Timeline View
Assignment View
    ×
    ×