Call-site specific selective automatic inlining

Claim 2

In a computer processor executing a computer compiler, a compiler implemented method for performing selective automatic procedure integration over a program call graph (PCG), comprising the steps of: constructing the PCG of a computer program, the PCG having a plurality of PCG nodes and PCG edges, each PCG node representing a procedure in the computer program and each PCG edge representing a call site connecting two nodes, each call site being a statement in a program that invokes a given procedure, a source node being a calling PCG node and a PCG edge having a direction from the calling node to a called node, so that an outgoing PCG edge represents a call site within said procedure and an incoming edge represents a call site invoking said procedure from within another procedure, wherein the PCG edge may further represent a back edge; eliminating from processing any back edges of the PCG; collecting a plurality of parameter values for use by a routine cost function which characterizes the suitability of each procedure for inlining, and by a call site cost function which characterizes the suitability of each PCG edge for inlining; performing the following steps for each procedure P in a reverse topological traversal of the PCG: inlining each outgoing PCG edge that has been marked to be inlined; evaluating the routine cost function which utilizes a first portion of said plurality of parameter values associated with the procedure P; evaluating the call site cost function which utilizes a second portion of said plurality of parameter values associated with each PCG edge; and marking for inlining each incoming PCG edge for which the routine cost function is evaluated less than a first threshold value and the call site cost function is evaluated less than a second threshold value.

Claim 3

The method of claim 1, further comprising the step of refining said plurality of parameter values by interprocedural constant propagation which increases the number of constant arguments within the program, responsive to said collecting step.

Claim 4

The method of claim 1, wherein said plurality of parameter values includes a size of each procedure; and wherein the routine cost function is directly proportional to said size.

Claim 5

The method of claim 1, wherein said plurality of parameter values includes a control flow complexity of each procedure; and wherein the routine cost function is directly proportional to said control flow complexity.

Claim 6

The method of claim 1, wherein said plurality of parameter values includes a call count of each procedure; and wherein the routine cost function is directly proportional to said call count.

Claim 7

The method of claim 1, wherein said routine cost threshold value is increased when the procedure is a leaf procedure.

Claim 8

The method of claim 1, wherein said plurality of parameter values includes a block size associated with each PCG edge; and wherein the call site cost function is directly proportional to said block size.

Claim 9

The method of claim 1, wherein said plurality of parameter values includes a count of execution paths which may not traverse the call site; and wherein the call site cost function is directly proportional to said count of execution paths.

Claim 10

The method of claim 1, wherein said plurality of parameter values includes a loop nesting level associated with each PCG edge; and wherein the call site cost function is inversely proportional to said loop nesting level.

Claim 11

The method of claim 1, wherein said collecting step comprises recognizing when at least one of said plurality of parameter values is used to determine a control flow within the procedure.

Claim 12

The method of claim 10, comprising the step of increasing said routine cost threshold value, responsive to said recognizing.

Claim 13

The method of claim 10, comprising the step of increasing said call site cost threshold value when the call site is associated with the parameter value used to determine the control flow, responsive to said recognizing.

Claim 14

The method of claim 9, comprising the step of increasing the call site threshold value in direct proportion to the loop nesting level, responsive to said determining a loop nesting level.

Claim 15

In a computer processor executing a computer compiler, a compiler implemented method for performing selective automatic procedure integration over a program call graph (PCG), comprising the steps of: constructing the PCG of a computer program, the PCG having a plurality of PCG nodes and PCG edges, each PCG node representing a procedure in the computer program and each PCG edge representing a call site connecting two nodes, each call site being a statement in a program that invokes a given procedure, a source node being a calling PCG node and a PCG edge having a direction from the calling node to a called node, so that an outgoing PCG edge represents a call site within said procedure and an incoming edge represents a call site invoking said procedure from within another procedure, wherein the PCG edge may further represent a back edge; eliminating from processing any back edges of the PCG; collecting a plurality of parameter values for use by a routine cost function which characterizes the suitability of each procedure for inlining, and by a call site cost function which characterizes the suitability of each PCG edge for inlining; wherein the routine cost function is directly proportional to a first portion of said plurality of parameter values including: a size of each procedure; a control flow complexity; and a call count; wherein the call site cost function is directly proportional to a second portion of said plurality of parameter values including: a block size and a loop nesting level associated with each PCG edge; and a count of execution paths which may not traverse the call site; performing the following steps for each procedure P in a reverse topological traversal of the PCG: inlining each outgoing PCG edge that has been marked to be inlined; evaluating the routine cost function for the procedure P; evaluating the call site cost function for each PCG edge; and marking for inlining each incoming PCG edge for which the routine cost function is evaluated less than a first threshold value and the call site cost function is evaluated less than a second threshold value, responsive to said evaluating.

Claim 16

In a computer processor executing a computer compiler, a compiler implemented method for performing selective automatic procedure integration over a program call graph (PCG), comprising the steps of: constructing the PCG of a computer program, the PCG having a plurality of PCG nodes and PCG edges, each PCG node representing a procedure in the computer program and each PCG edge representing a call site connecting two nodes, each call site being a statement in a program that invokes a given procedure, a source node being a calling PCG node and a PCG edge having a direction from the calling node to a called node, so that an outgoing PCG edge represents a call site within said procedure and an incoming edge represents a call site invoking said procedure from within another procedure, wherein the PCG edge may further represent a back edge; eliminating from processing any back edges of the PCG; collecting a plurality of parameter values for use by a routine cost function which characterizes the suitability of each procedure for inlining, and by a call site cost function which characterizes the suitability of each PCG edge for inlining; wherein the routine cost function is directly proportional to a first portion of said plurality of parameter values including: a size of each procedure; a control flow complexity; and a call count; wherein the call site cost function is directly proportional to a second portion of said plurality of parameter values including: a block size and a loop nesting level associated with each PCG edge; and a count of execution paths which may not traverse the call site; performing the following steps for each procedure P in a reverse topological traversal of the PCG: inlining each outgoing PCG edge that has been marked to be inlined; evaluating the routine cost function for the procedure P; evaluating the call site cost function for each PCG edge; and marking for inlining each incoming PCG edge for which the routine cost function is evaluated less than a first threshold value and the call site cost function is evaluated less than a second threshold value, responsive to said evaluating.

Claim 17

A program storage device readable by a computer processor, tangibly embodying a computer program executable by the computer processor to perform a compiler implemented method for performing automatic procedure integration over a program call graph (PCG), said method comprising the steps of: constructing the PCG of the computer program, the PCG having a plurality of PCG nodes and PCG edges, each PCG node representing a procedure in the computer program and each PCG edge representing a call site connecting two nodes, each call site being a statement in a program that invokes a given procedure, a source node being a calling PCG node and a PCG edge having a direction from the calling node to a called node, so that an outgoing PCG edge represents a call site within said procedure and an incoming edge represents a call site invoking said procedure from within another procedure, wherein the PCG edge may further represent a back edge; eliminating from processing any back edges of the PCG; collecting a plurality of parameter values for use by a routine cost function which characterizes the suitability of each procedure for inlining, and by a call site cost function which characterizes the suitability of each PCG edge for inlining; performing the following steps for each procedure in a reverse topological traversal of the PCG: inlining each outgoing PCG edge that has been marked to be inlined; evaluating the routine cost function which utilizes a first portion of said plurality of parameter values associated with the procedure P; evaluating the call site cost function which utilizes a second portion of said plurality of parameter values associated with each PCG edge; and marking for inlining each incoming PCG edge for which the routine cost function is evaluated less than a first threshold value and the call site cost function is evaluated less than a second threshold value.

Claim 18

A program storage device readable by a computer processor, tangibly embodying a computer program executable by the computer processor to perform a compiler implemented method for performing automatic procedure integration over a program call graph (PCG), said method comprising the steps of: constructing the PCG of the computer program, the PCG having a plurality of PCG nodes and PCG edges, each PCG node representing a procedure in the computer program and each PCG edge representing a call site connecting two nodes, each call site being a statement in a program that invokes a given procedure, a source node being a calling PCG node and a PCG edge having a direction from the calling node to a called node, so that an outgoing PCG edge represents a call site within said procedure and an incoming edge represents a call site invoking said procedure from within another procedure, wherein the PCG edge may further represent a back edge; eliminating from processing any back edges of the PCG; collecting a plurality of parameter values for use by a routine cost function which characterizes the suitability of each procedure for inlining, and by a call site cost function which characterizes the suitability of each PCG edge for inlining; performing the following steps for each procedure in a reverse topological traversal of the PCG: inlining each outgoing PCG edge that has been marked to be inlined; evaluating the routine cost function which utilizes a first portion of said plurality of parameter values associated with the procedure P; evaluating the call site cost function which utilizes a second portion of said plurality of parameter values associated with each PCG edge; and marking for inlining each incoming PCG edge for which the routine cost function is evaluated less than a first threshold value and the call site cost function is evaluated less than a second threshold value.

Claim 19

The program storage device of claim 15, further comprising the step of refining said plurality of parameter values by interprocedural constant propagation for increasing the number of constant arguments within the program, responsive to said collecting step.

Claim 20

The program storage device of claim 15, wherein said plurality of parameter values includes a size of each procedure; and wherein the routine cost function is directly proportional to said size.

Claim 21

The program storage device of claim 15, wherein said plurality of parameter values includes a control flow complexity of each procedure; and wherein the routine cost function is directly proportional to said control flow complexity.

Claim 22

The program storage device of claim 15, wherein said plurality of parameter values includes a call count of each procedure; and wherein the routine cost function is directly proportional to said call count.

Claim 23

The program storage device of claim 15, wherein said routine cost threshold value is increased when the procedure is a leaf procedure.

Claim 24

The program storage device of claim 15, wherein said plurality of parameter values includes a block size associated with each PCG edge; and wherein the call site cost function is directly proportional to said block size.

Claim 25

The program storage device of claim 15, wherein said plurality of parameter values includes a count of execution paths which may not traverse the call site; and wherein the call site cost function is directly proportional to said count of execution paths.

Claim 26

The program storage device of claim 15, wherein said plurality of parameter values includes a loop nesting level associated with each PCG edge; and wherein the call site cost function is inversely proportional to said loop nesting level.

Claim 27

The program storage device of claim 23, comprising the step of increasing the call site threshold value in direct proportion to the loop nesting level, responsive to said step of determining a loop nesting level.

Claim 28

The program storage device of claim 15, wherein said collecting step comprises recognizing when the parameter value is used to determine a control flow within the procedure.

Claim 29

The program storage device of claim 25, comprising the step of increasing said routine cost threshold value, responsive to said step of recognizing.

Claim 30

The program storage device of claim 25, comprising the step of increasing said call site cost threshold value when the call site is associated with the parameter value used to determine the control flow, responsive to said step of recognizing.