Method and apparatus for compiling computer programs with interproceduural register allocation

• US 5,428,793 A
• Filed: 11/13/1989
• Issued: 06/27/1995
• Est. Priority Date: 11/13/1989
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Santhanam, Vatsa, Odnert, Daryl
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): BUTLER, DENNIS
• Application Number:
  US07/435,914
• Time in Patent Office: 2,052 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 395/700, 395/375
• US Class Current: 717/157
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

Optimization techniques are implemented by means of a program analyzer used in connection with a program compiler to optimize usage of limited register resources in a computer processor. The first optimization technique, called interprocedural global variable promotion allows the global variables of a program to be accessed in common registers across a plurality of procedures. Moreover, a single common register can be used for different global variables in distinct regions of a program call graph. This is realized by identifying subgraphs, of the program call graph, called webs, where the variable is used. The second optimization technique, called spill code motion, involves the identification of regions of the call graph, called clusters, that facilitate the movement of spill instructions to procedures which are executed relatively less often. This decreases the overhead of register saves and restores which must be executed for procedure calls.

Claims

1. A method of operating a general purpose data processor having a plurality of machine registers, a sub-set thereof being assigned for use as interprocedural registers, so as to allow more efficient allocation of said interprocedural registers when said data processor is executing a computer program comprising a plurality of procedures, at least one of said procedures operating on a global variable, said method comprising the steps of:

building a program call graph, said program call graph comprising a set of nodes, each said node representing a procedure, interconnected by directional edges to other said nodes, each said edge representing a call from a first procedure to a second procedure, the node representing said first procedure being the ancestor of the node representing said second procedure and the node representing said second node being the descendent of the node representing said first procedure;

defining webs corresponding to global variables, each said web corresponding to a global variable, each said web comprising a collection of program call graph nodes such that said corresponding global variable is accessed in at least one node in said web and such that, for each node in said web, said corresponding global variable is not accessed in any ancestor node not in said web, and said global variable is not accessed by any descendant node not in said web;

determining an order for said webs; and

assigning said global variables to interprocedural machine registers according to the order of said webs corresponding to said global variables in said determined order.

2. The method of claim 1 wherein said priority order assigned to said webs is determined by the frequency of use of the global variable corresponding to each said web.

3. The method of claim 1 wherein said priority order assigned to said webs is determined from profile information collected by running said program with exemplary input data on a data processing system.

4. The method of claim 1 wherein said step of assigning interprocedural machine registers comprises assigning different machine registers to webs having common program call graph nodes.