Inter-procedure global register allocation method

[0001] The present invention relates to computer systems. More specifically, the present invention relates to a method and system for optimizing processor register allocation in a compiler.

[0002] A computer system generally consists of several basic components, including one or more microprocessors (processors), volatile and non-volatile memory, data transfer buses, interface devices, etc. Processors are generally classified as either RISC (reduced instruction set computer) or CISC (complex instruction set computer) and may be categorized according to internal architecture as well, such as, for example, scalar, super-scalar, pipelined, etc.

[0003] A processor includes many different internal components, such as, for example, bus interface units, instruction fetch and decode units, arithmetic logic units, floating point execution units, instruction and data caches, register files, etc. Register files typically include registers, or fixed-sized memory storage locations, that are accessed through a number of ports. These registers may contain integer or floating point numbers, and may range in size from the processor's word size (e.g., 32-bits, 64-bits, etc.), to double-word size (e.g., 64-bits, 128 bits, etc.), quadword size (e.g., 128 bits, 256 bits, etc.), floating point size (32 bits, 64 bits, etc.), etc.

[0004] Generally, the processor may execute an operating system, or task scheduler, as well as one or more application programs. The operating system, task scheduler, and/or application program are usually written in a high-level language, such as, for example, C/C++, etc., and reduced to processor-executable language through a compilation and linking process. During this process, program variables may be assigned to specific locations in memory, or to relative locations in a memory map which may be resolved dynamically during program execution. However, program execution speed suffers, sometimes considerably, when program variables are accessed from memory over a memory bus.

[0005] For example, in a typical read/modify/write program instruction sequence, a variable assigned to a specific location in memory is first transferred from memory, over the memory bus, to the processor. The variable is modified and then transferred from the processor, over the memory bus, to memory. Each of these memory bus transfers requires several bus cycles, which typically represent many processor clock cycles. Thus, memory transfers generally reduce program execution speed by introducing many processor wait states, or idle cycles, during which time the processor is inefficiently waiting for the memory transfer to complete.

[0006] A secondary cache, located between the processor and the memory bus, may improve program execution speed by temporarily storing the contents of certain memory locations (and, consequently, certain variables) in a limited-size, local memory. Similarly, a smaller, on-chip processor cache may improve program execution speed even more. However, variables stored in registers within the processor's register file may be accessed more quickly than values in memory, secondary caches, or even on-chip caches. Consequently, the compilation process may assign certain program variables to registers within a register file, rather than locations in memory, in order to improve program execution speed. The selection, or allocation, of candidate program variables depends upon several constraints, and is performed on very small sections of the entire program instruction sequence. Consequently, only a limited degree of program optimization is realized.

[0012] Embodiments of the present invention provide a method and system for optimizing processor register allocation. Variables from an acyclic call graph having a plurality of functions may be identified and a plurality of virtual registers may be created by assigning each of the identified variables to at least one virtual register. An interference graph may be constructed, based on the plurality of virtual registers, and colored with a plurality of physical registers. If the interference graph is not colorable, at least one virtual register may be spilled from the interference graph.

[0013] FIG. 1 is a computer system block diagram according to an embodiment of the present invention. Generally, target system 100 may include at least one processor 110 including at least one register file 115, memory 120, network interface 130, developer interface 140, I/O devices (not shown), etc. Additional processors 111-1, 111-2 . . . 111-n are shown in phantom outline, which may be the same type, or perform the same functionality, as processor 110. Alternatively, processors 111-1 . . . 111-n may be different than processor 110, such as, for example, in a system that includes a core processor 110 and multiple data processors 111-1 . . . 111-n.

[0014] Processor 110 may be coupled, via bus 150, to memory 120, network interface 130, developer interface 140, etc. Network 160 may include a wide variety of network protocols and may be a local area network, a wide area network, a wireless network, the Internet, etc. Network 160 may be coupled to developer system 170 and to target system 100 via network interface 130. Developer system 170 may be coupled to target system 100 via developer interface 140, which may include, for example, a wide variety of data link communications protocols, such as, for example, PPP (point-to-point protocol, e.g., Internet Standard RFC 1661), HDLC (high-level data link control protocol, e.g., ISO 6159), etc. Developer system 170 may be a personal computer such as, for example, a desktop system or portable notebook, or, alternatively, developer system 170 may be a network server. Generally, developer system 170 includes a software development kit (SDK), and appropriate device drivers, to create, compile, load, execute and debug software for target system 100. Alternatively, developer system 170 and target system 100 may be the same computer system.

[0015] In an embodiment, target system 100 may be a personal computer. In this embodiment, processor 110 may be a microprocessor, such as, for example, a Pentium® IV processor manufactured by Intel Corporation of Santa Clara, Calif., etc. Alternatively, processor 110 may be a microcontroller or an Application Specific Integrated Circuit (ASIC). In another embodiment, target system 100 may be a single board computer (SBC) within a multi-slot card chassis having a backplane, such as, for example, a VMEbus chassis (VERSAmodule Eurocard Bus, IEEE-1014-1987). In a further embodiment, target system 100 may be a network processor, such as, for example, an Intel IXP1200 having a single StrongARM core processor (e.g., processor 110) and several multithreaded microengine data processors (e.g., processor 111-1 . . . 111-n).

[0016] A high-level language compiler may be used to generate machine executable code for processor 110 and processors 111-1 . . . 111-n, which may be, for example, a C-language compiler. Of course, if the architecture of processor 110 is different from processors 111-1 . . . 111-n, then different C compilers may be used. In an embodiment, developer system 170 includes a software development kit, such as, for example, the Intel IXA SDK for the IXP1200 network processor, which may include a Microengine C-language compiler for the IXP1200 network processor microengine data-plane processing elements (e.g., processors 111-1 . . . 111-n). Using the IXA SDK, IXP 1200 microengine instructions may be abstracted to permit easier coding, maintenance, and a high level of future network processor portability. Advantageously, the C-compiler may perform global, multi-level optimizations (including register allocation, etc.) for the IXP1200 network processor to produce highly efficient and compact code. The Microengine C language may be an alternative to the microcode for IXP1200 network processor development that minimizes time-to-market of intelligent applications such as VoIP (voice-over-IP) gateways, Web switches, cable head end systems, etc.

[0017] FIG. 2 illustrates simple C program, according to an embodiment of the present invention.

[0018] Program 200 may include at least three software routines, including main 210, function 220 and library 230. Main 210 may be, for example, the main calling routine for program 200. Function 220 may be a subroutine performing some predetermined functionality. Library 230 may be a library routine, such as, for example, the standard library routine abs(), or a custom library function (as shown). Several variables may be included within program 200, such as, for example, global variables A, X and Y, local variables B, C, Ptr and E, and function argument variables D and F. Of course, significantly more sophisticated programs are contemplated by the present invention.

[0019] FIG. 3 illustrates an acyclic call graph and associated sorted list, according to an embodiment of the present invention.

[0020] Call graph 300 may be derived, for example, from program 200. Alternatively, call graph 300 may be derived from an acyclic portion or branch of program 200 (not shown for clarity). For example, call graph 300 may depict main 210, calling function 220 and library 230 (variables not shown for clarity). Function 220 may be depicted as calling library 230, and library 230 may be depicted as having an empty function callee list (i.e., library 230 does not call any other function).

[0021] Sorted list 310 may represent a doubly-linked list of the functions within call graph 300 in sorted order (variables not shown for clarity). For example, call graph 300 may be sorted according to a topological algorithm. In an embodiment, call graph 300 may be traversed iteratively until all the functions within call graph 300 have been removed. For example, for each function Fi in call graph 300, if the callee list is empty, Fi may be moved to the front of the sorted list, and, for each of the remaining functions Fn in call graph 200, calls to function Fi may be removed from the callee list of Fn. Thus, for this example, sorted list 310 may include the following functions: main 210, function 220 and library 230. Each element of the list may refer to both the preceding element and the succeeding element, thereby creating a doubly-linked sorted list, with null references, or circular references, included for the boundary elements at either end of the list.

[0022] FIG. 4 illustrates a method for optimizing processor register allocation, according to an embodiment of the present invention.

[0023] A plurality of variables may be identified (400) from an acyclic call graph having a plurality of functions. In an embodiment, the compiler may identify (400) candidate variables that may be assigned to processor registers, which may include local function variables, function argument variables, function return address variables and function return value variables, as well as global variables that are referenced only by the functions in the call graph.

[0024] However, variables whose addresses are referenced, or variables exceeding a predetermined size, are excluded. For example, candidate variables identified (400) from call graph 300 may include A, B, C, D, E, F and Ptr. Variable X, however, may not be identified as a candidate variable, since the address of variable X is taken and assigned to Ptr in main 210. If the register size equals the size of an integer or integer pointer (e.g., 32 bits), then variable Y may not be a candidate variable either, since variable Y is declared as a double integer (e.g., 64 bits).

[0025] A plurality of virtual registers may be created (410) by assigning each of the plurality of variables to a virtual register. In an embodiment, a virtual register VRi may be assigned to each of the identified, candidate variables Vi. For example, variables A, B, C, D, E, F and Ptr may be assigned VR₁ through VR₇, respectively. A variable may also be assigned to more than one virtual register VRi.

[0026] An interference graph may be constructed (420) based on the plurality of registers. In an embodiment, an interference graph may be populated, generally, with nodes N₁ through Nn corresponding to the live ranges of virtual registers VR₁ through VRn.

[0027] Referring to FIG. 5, for example, interference graph 500 may be populated with a plurality of nodes 510, which may consist of nodes 511 to 517 corresponding to the live ranges of virtual registers VR₁ through VR₇, respectively. In order to determine the connections among the plurality of nodes 510, sorted list 310 may be traversed in order to determine the temporal interaction among the various candidate variables V₁ through V₇, and hence between VR₁ through VR₇. If two virtual registers interfere with one another, i.e., if the two associated variables are “live” simultaneously at any point in the program, then the two nodes corresponding to the two virtual registers are connected with an “edge.” Generally, a variable may be “live” at any point in the program if there is some execution path from that point that reaches a use of the variable without passing through an assignment to the variable (e.g., use of the variable as an rvalue within an expression, as a function argument, etc.). An edge between two nodes of interference graph 500 may indicate that the two virtual registers corresponding to these nodes may not share a physical register in the processor's register file (e.g., node 511 and node 512).

[0028] For example, while traversing sorted list 310 in reverse order, two virtual register sets may be created for each function (e.g., main 210, function 220 and library 230). The first set may include, for example, the virtual registers that are used by the function itself, as well as the virtual registers that are used by any called function on any path that does not include a prior assignment to the virtual register, i.e., the set of virtual registers for which a call to the function generates liveness. The second set may include all the virtual registers unconditionally assigned on all executions of the function (e.g., virtual registers associated with global variables). And, while traversing sorted list 300 in forward order, a third set may be created for each function that may include the virtual registers that are live immediately following any call to the function, or, equivalently, the set of all virtual registers that are live at any return point of the function. The liveness of each of the virtual registers may be compared and an edge may be constructed between all of the appropriate pairs of virtual registers.

[0029] A plurality of edges 520 are generally depicted in interference graph 500 (i.e., the black lines connecting the plurality of nodes 510). However, no edge is depicted between node 513 and node 515 (i.e., VR₃ and VR₅ corresponding to variables C and E, respectively), or node 514 and node 516 (i.e., VR₄ and VR₆ corresponding to variables D and F, respectively).

[0030] The interference graph may be colored (430) with a plurality of physical registers. In an embodiment, the compiler may assign colors to the plurality of nodes 510 so that nodes sharing an edge (e.g., node 511 and node 512) always have distinct colors. The total number of colors is generally less than, or equal to, the total number of registers available within the processor's register file. For example, in an embodiment, processor 110 may contain four registers within register file 105. The compiler for processor 110 may associate each of the plurality of nodes 520 with one of four colors (e.g., red, blue, green or yellow), reusing colors between pairs of nodes that are not connected with an edge. The colors, of course, may be associated with one of the four physical registers within register file 105. In this example, four colors may be assigned: red for nodes 513 and 515, blue for nodes 514 and 516, green for node 511, and yellow for node 512. Node 517 may not be assigned a color because an edge exists between at least one node from each color assignment (e.g., nodes 511, 512, 513 and 514, respectively). Consequently, interference graph 500 may not be colorable.

[0031] If the interference graph is not colorable, at least one virtual register may be spilled (440) from the interference graph. In an embodiment, a node without an assigned color may be removed from the interference graph and the virtual register associated with this node may be assigned an address in memory 120, rather than a physical register. For example, node 517 may not be assigned a color and may be spilled (440) to memory 120 by removing node 517 from interference graph 500 and assigning the virtual register VR₇, associated with the variable Ptr, to a location in memory 120, or a memory map (not shown). Spilling one or more nodes, or live ranges, from interference graph 500 may create a new version of interference graph 500. In an embodiment, the compiler may iteratively spill different combinations of nodes, or live ranges, to optimize the resulting physical register assignment.

[0032] Several embodiments of the present invention are specifically illustrated and described herein. However, it will be appreciated that modifications and variations of the present invention are covered by the above teachings and within the purview of the appended claims without departing from the spirit and intended scope of the invention.