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

Claim 2

A computer-implemented method for converting a source code computer program into a machine-readable object code, said method comprising the steps of: receiving 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, 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.

Claim 5

The method of claim 2 wherein said reducing step (c) comprises the steps of: (c.1) identifying as qualified each said node in said first CFG containing a procedure call and each said node belonging to a loop within said first CFG; (c.2) traversing said first CFG from said entry node to said exit node along every path formed by said directed arcs from said entry node without visiting any said qualified node and identifying as unqualified each said node visited; (c.3) identifying the first said qualified node that is reached on each said path from said entry node as a qualified root node; and (c.4) disconnecting from each said qualified root node the input control flow arc and reconnecting said disconnected arc into said new basic block node containing said call to said procedure body represented by a subgraph rooted in said each qualified root node.

Claim 6

The method of claim 3 wherein said disconnecting step (c.4) comprises the step of: (c.4.1) for each said qualified root node, assembling as an emitted subgraph said nodes and arcs on all paths from said each qualified root node that end at a single said unqualified node.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

The system of claim 6 further comprising: CFG annotation means in said partial expansion means for identifying as qualified each said node in said first CFG containing a procedure call and each said node belonging to a loop within said first CFG; CFG traverse means in said partial expansion means for traversing said first CFG from said entry node to said exit node along every path formed by said directed arcs from said entry node without visiting any said qualified node and identifying as unqualified each said node visited; subgraph root detection means coupled to said CFG traverse means for identifying as a qualified root node the first said qualified node that is reached on each said path from said entry node; and subgraph removal means coupled to said subgraph root detection means for disconnecting from each said qualified root node the input control flow arc and reconnecting said disconnected arc into a new basic block node containing said call to said procedure body represented by a subgraph rooted in said each qualified root node.

Claim 12

The system of claim 7 further comprising: subgraph emission means in said subgraph removal means for assembling an emitted subgraph for each said qualified root node, said emitted subgraph including said nodes and arcs on all paths from said each qualified root node that end at a single said unqualified node.

Claim 13

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.

Claim 14

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.

Claim 15

The system of claim 9 further comprising: CFG annotation means in said partial expansion means for identifying as qualified each said node in said first CFG containing a procedure call and each said node belonging to a loop within said first CFG; CFG traverse means in said partial expansion means for traversing said first CFG from said entry node to said exit node along every path formed by said directed arcs from said entry node without visiting any said qualified node and identifying as unqualified each said node visited; subgraph root detection means coupled to said CFG traverse means for identifying as a qualified root node the first said qualified node that is reached on each said path from said entry node; and subgraph removal means coupled to said subgraph root detection means for disconnecting from each said qualified root node the input control flow arc and reconnecting said disconnected are into a new basic block node containing said call to said procedure body represented by a subgraph rooted in said each qualified root node.

Claim 16

The system of claim 10 further comprising: subgraph emission means in said subgraph removal means for assembling an emitted subgraph for each said qualified root node, said emitted subgraph including said nodes and arcs on all paths from said each qualified root node that end at a single said unqualified node.

Claim 17

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.

Claim 18

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.

Claim 19

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.

Claim 20

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.

Claim 21

The computer program product of claim 13 further comprising: means recorded on said recording medium for directing said computer system to identify as qualified each said node in said first CFG containing a procedure call and each said node belonging to a loop within said first CFG; means recorded on said recording medium for directing said computer system to traverse said first CFG from said entry node to said exit node along every path formed by said directed arcs from said entry node without visiting any said qualified node and identify as unqualified each said node visited; means recorded on said recording medium for directing said computer system to identify the first said qualified node that is reached on each said path from said entry node as a qualified root node; and means recorded on said recording medium for directing said computer system to disconnect from each said qualified root node the input control flow arc and reconnect said disconnected are into said new basic block node containing said call to said procedure body represented by a subgraph rooted in said each qualified root node.

Claim 22

The computer program product of claim 14 further comprising: means recorded on said recording medium for directing said computer system to assemble an emitted subgraph for each said qualified root node, said emitted subgraph including said nodes and arcs on all paths from said each qualified root node that end at a single said unqualified node.