System for partial in-line expansion of procedure calls during program compilation

A method of operating a compiler system for translating a computer program from source code to object code, wherein said computer program may be represented by a control flow graph (CFG) having a plurality of basic block nodes each coupled by one or more directed control flow arcs to at least one other said basic block node, said compiler system including in-line expansion means for reducing computer program execution cost by replacing a higher-cost procedure call in said computer program with the lower-cost corresponding procedure body, said method comprising the steps of:

• (a) replacing in said computer program a first said procedure call with the corresponding first procedure body if the execution cost of said first procedure body is less than the execution cost of said first procedure call;
• otherwise
• (b) generating a first said CFG representing said first procedure body, said first CFG having an entry node and an exit node;
• (c) reducing said first procedure body execution cost by replacing each of one or more subgraphs in said first CFG with a new basic block node containing a call to the procedure body represented by said each subgraph;
• and
• (d) repeating said replacing step (a) for the revised said first procedure body.

A computer apparatus comprising:

• a central processing unit, said central processing unit executing an instruction stream embodying one or more procedures;
• a program compiler, said program compiler being executed by said central processing unit and including a partial in-line expander for;
• receiving a source code computer program for conversion;
• responding to a first procedure call having a corresponding first procedure body having an execution cost greater than a predetermined execution cost, replacing in said first procedure body a higher-cost portion of said first procedure body with a lower-cost second procedure call to a second procedure body containing said higher-cost first procedure body portion;
• and
• replacing said first procedure call in said source code computer program with said corresponding first procedure body.

A computer program compiler system for translating a computer program from source code to object code, said system comprising:

• in-line expansion means for replacing in said computer program a first procedure call with the corresponding first procedure body when the execution cost of said first procedure body is less than the execution cost of said first procedure call;
• CFG construction means coupled to said in-line expansion means for generating a first control flow graph (CFG) representing said first procedure body, said first CFG having a plurality of basic block nodes each coupled by one or more directed control flow arcs to at least one other said basic block node, said node plurality including an entry node and an exit node;
• and
• partial expansion means coupled to said CFG construction means and to said in-line expansion means for reducing said first procedure body execution cost by replacing in said first CFG each of one or more subgraphs with a new basic block node containing a call to the procedure body represented by said each subgraph.

A computer processing system comprising:

• central processing means for executing computer program procedures;
• memory means coupled to said central processing means for storing data and computer program procedures;
• compiler means in said memory means for translating a computer program from source code to object code;
• in-line expansion means for replacing in said computer program a first procedure call with the corresponding first procedure body when the execution cost of said first procedure body is less than the execution cost of said first procedure call;
• CFG construction means coupled to said in-line expansion means for generating a first control flow graph (CFG) representing said first procedure body, said first CFG having a plurality of basic block nodes each coupled by one or more directed control flow arcs to at least one other said basic block node, said node plurality including an entry node and an exit node;
• and
• partial expansion means coupled to said CFG construction means and to said in-line expansion means for reducing said first procedure body execution cost by replacing in said first CFG each of one or more subgraphs with a new basic block node containing a call to the procedure body represented by said each subgraph.

A computer program product for use with a computer system, said computer program product comprising:

• a recording medium;
• and
• means recorded on said recording medium for directing said computer system to;
• receive said source code computer program for conversion;
• in response to a first procedure call having a corresponding first procedure body having an execution cost greater than a predetermined execution cost, replace in said first procedure body a higher-cost portion of said first procedure body with a lower-cost second procedure call to a second procedure body containing said higher-cost first procedure body portion;
• and
• replace said first procedure call in said source code computer program with said corresponding first procedure body.

A computer program product for use with a computer system having a central processing unit (CPU) for processing data responsive to stored computer programs and having a memory for storing said computer programs, said computer program product comprising:

• a recording medium;
• means recorded on said recording medium for directing said computer system to translate a computer program from source code to object code, wherein said computer program may be represented by a control flow graph (CFG) having a plurality of basic block nodes each coupled by one or more directed control flow arcs to at least one other said basic block node;
• means recorded on said recording medium for directing said computer system to reduce computer program execution cost by replacing a higher-cost procedure call in said computer program with the lower-cost corresponding procedure body;
• means recorded on said recording medium for directing said computer system to replace in said computer program a first said procedure call with the corresponding said first procedure body when the execution cost of said first procedure body is less than the execution cost of said first procedure call;
• means recorded on said recording medium for directing said computer system to generate a first said CFG representing said first procedure body, said first CFG having an entry node and an exit node;
• and
• means recorded on said recording medium for directing said computer system to reduce said first procedure body execution cost by replacing each of one or more subgraphs in said first CFG with a new basic block node containing a call to the procedure body represented by said each subgraph.