Method and computer program product for adaptive inlining in a computer system

A computer program compiler product for implementing adaptive inlining for compiler optimization and improving program execution in a computer system comprising:

• a recording medium;
• means, recorded on the recording medium, for identifying call sites in a call multigraph for possible inlining;
• means, recorded on the recording medium, for identifying a first approximation of first priority call sites of said identified possible call sites for inlining based upon call frequency and called procedure size including means, recorded on the recording medium, for utilizing said call multigraph consisting of N nodes and E edges;
• where each node represents a procedure in the module, and each arc AB represents a call site in a procedure A that may invoke a procedure B;
• an array initialSize containing estimated instruction counts for each procedure 1−N;
• means, recorded on the recording medium, for calculating a total initial sum of the array initialSize;
• means, recorded on the recording medium, for calculating a bloat budget equal to said total initial sum multiplied by a set bloat factor;
• and
• means, recorded on the recording medium, for each arc 1 to E,
• means, recorded on the recording medium, for checking for an illegal or undesirable inlining candidate,
• means, recorded on the recording medium, responsive to identifying an illegal or undesirable inlining candidate, for setting a priority for the arc to infinity,
• means, recorded on the recording medium, responsive to not identifying an illegal or undesirable inlining candidate, for calculating a bloat estimate and a priority for the arc, and
• means, recorded on the recording medium, for placing all finite priority arcs in an initial priority queue, keyed by smallest priority;
• means, recorded on the recording medium, for calculating and for removing best priority call sites arcs from said initial priority queue;
• means, recorded on the recording medium, for marking said best priority call sites removed from said priority queue for possible inlining;
• means, recorded on the recording medium, for determining a compilation order and for processing said marked best procedure call sites using a ready priority queue and an auxiliary priority queue;
• means, recorded on the recording medium, for processing all outgoing arcs from said best procedure call sites in said ready priority queue to confirm or reject inlining;
• and
• means, recorded on the recording medium, for processing all incoming arcs for placement in either said ready priority queue or said auxiliary priority queue.

A computer program product for implementing adaptive inlining for compiler optimization and improving program execution in a computer system, said computer program product including a plurality of computer executable instructions stored on a computer readable medium, wherein said instructions, when executed by said computer, cause the computer to perform the steps of:

• identifying call sites in a call multigraph for possible inlining;
• identifying a first approximation of initial call sites of said identified possible call sites for inlining based upon call frequency and called procedure size including the steps of;
• utilizing a call multigraph consisting of N nodes and E edges;
• where each node represents a procedure in the module, and each arc AB represents a call site in a procedure A that may invoke a procedure B;
• an array initialSize containing estimated instruction counts for each procedure 1−N;
• calculating a total initial sum of the array initialSize;
• calculating a bloat budget equal to said total initial sum multiplied by a set bloat factor;
• and
• for each arc 1 to E,
• checking for an illegal or undesirable inlining candidate,
• responsive to identifying an illegal or undesirable inlining candidate, setting a priority for the arc to infinity,
• responsive to not identifying an illegal or undesirable inlining candidate, calculating a bloat estimate and a priority for the arc, and
• placing all finite priority arcs in an initial priority queue, keyed by smallest priority;
• processing procedures in said call multigraph in a determined order where a first procedure is only processed after all second procedures called by said first procedure are processed;
• said processing of said first procedure comprising the steps of:
• determining whether any call site within said first procedure has been selected for inlining, and whether the second procedure called from the call site contains confirmed inlined call sites;
• and
• if true, determining whether to confirm or reject the first approximation to inline the second procedure into said first procedure at the call site utilizing at least one predetermined criterion.