Method and apparatus for compiling computer programs with interprocedural register allocation

A method for optimizing register usage in an executable computer program on a computer processor having a limited plurality of machine registers, said computer program being compiled from a plurality of individual source code files, said method comprising the steps of:

• reading said individual source code files having high-level program language text reciting a plurality of procedures, said source code files being read one at a time;
• determining syntactic and semantic correctness of each said source code file;
• translating each said source code file into an intermediate representation;
• collecting local information about usage of global variables from each said source code file, wherein a global variable is a named storage location the contents of which can be stored in a single machine register and is accessible from a plurality of procedures;
• estimating need of registers for each procedure from each said intermediate representation;
• and
• constructing a record of said register need and said global variable usage and calls to procedures for each procedure in a summary file for each said source code file.

An apparatus for optimizing register usage in an executable computer program on a computer processor having a limited plurality of machine registers, said computer program being compiled from a plurality of individual source code files, said apparatus comprising:

• means for reading said individual source code files having high-level program language text reciting a plurality of procedures, said source code files being read one at a time;
• means coupled to said reading means for determining syntactic and semantic correctness of each said source code file;
• means coupled to said determining means for translating each said source code file into an intermediate representation and generating therefrom an intermediate representation file;
• means coupled to said translating means for collecting local information about usage of global variables from each said source code file, wherein a global variable is a named storage location the contents of which can be stored in a single machine register and is accessible from a plurality of procedures;
• means coupled to said collecting means for estimating need of registers for each procedure from each said intermediate representation;
• and
• means coupled to said estimating means, to said collecting means, and to said translating means for constructing a record of said register need and said global variable usage and calls to procedures for each procedure in a summary file for each said source code file.

An apparatus for optimizing register usage in an executable computer program on a computer processor having a limited plurality of machine registers, said computer program being compiled from a plurality of individual source code files, said apparatus comprising:

• means for reading said individual source code files having high-level program language text reciting a plurality of procedures, said source code files being read one at a time;
• means coupled to said reading means for determining syntactic and semantic correctness of each said source code file;
• means coupled to said determining means for translating each said source code file into an intermediate representation;
• means coupled to said translating means for collecting local information about usage of global variables from each said source code file, wherein a global variable is a named storage location the contents of which can be stored in a single machine register and is accessible from a plurality of procedures;
• means coupled to said collecting means for estimating need of registers for each procedure from each said intermediate representation;
• and
• means coupled to said estimating means, to said collecting means, and to said translating means for constructing a record of said register need and said global variable usage and calls to procedures for each procedure in a summary file for each said source code file.

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 procedural 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 an descendant node not in said web;
• determining the 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, wherein said selected global variables comprise said global variables are eligible for assignment to an interprocedural machine register.

A method of operating a general purpose data processor having a plurality of machine register, 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 an descendant node not in said web;
• determining the 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, wherein said order determined for said webs is determined by the frequency of use of the global variable corresponding to each said web.

A method of operating a general purpose data processor having a plurality of machine register, 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 an descendant node not in said web;
• determining the 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, wherein said order determined for said webs is determined from profile information collected by executing said program with exemplary input data on a data processing system capable of running said program.

A method of operating a general purpose data processor having a plurality of machine register, 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 collections 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 an descendant node not in said web;
• determining the 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,
• said method further comprising the step of identifying a procedure into which code is to be inserted, said code causing the contents of one of said interprocedural register to be stored in a location in said data processing system different from said interprocedural register upon entry into said procedure thereby freeing said interprocedural register for use in storing a different said global variable.