US 8,789,032 B1Granted

Feedback-directed inter-procedural optimization

AssigneeGoogle Inc.

InventorsXinliang David Li, Raksit Ashok, Robert Hundt

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods, systems, and apparatus, including computer program products, for inter-procedural optimization, are disclosed. In one aspect, a first executable program module is generated based on a plurality of source code modules. Profile information is collected for the plurality of source code modules by executing the first executable program module. Inter-procedural analysis for the plurality of source code modules is performed during execution of the first executable program module. The inter-procedural analysis is based on the collected profile information. IPO is performed based on the results from the inter-procedural analysis to generate a plurality of object code modules. A second executable program module is generated based on the plurality of object code modules.

Claims15

Dependent claims

A method for feedback directed inter-procedural optimization, comprising:

generating a first executable program module based on a plurality of source code modules;
collecting profile information based on feedback directed analysis for the plurality of source code modules by executing the first executable program module and wherein the profile information comprises information pertaining to invocation of procedures in the first executable program module;
determining module grouping information for the plurality of source code modules based on procedure invocation patterns in the profile information and according to one or more inter-procedural optimization heuristics, wherein determining the module grouping information comprises:
for each source code module:
creating a module group for the source code module;
designating the source code module as a primary module of the module group;
and
identifying all auxiliary modules of the module group, each of the identified auxiliary modules defining a callee procedure that is called by a caller procedure in the primary module of the module group, wherein identifying all auxiliary modules includes,
for each procedure in the primary module:
identifying all outgoing edges of the procedure that have an edge frequency count exceeding a threshold value, each of the outgoing edges representing a procedural call from the procedure to a second, different procedure;
and
for each of the identified outgoing edges:
identifying a callee procedure associated with the identified outgoing edge;
identifying a defining source code module of the identified callee procedure;
and
designating the identified defining source code module as an auxiliary module of the primary module if the identified defining source code module has not already been so designated;
performing inter-procedural optimization based on the module grouping information to generate a plurality of object code modules;
and
generating a second executable program module based on the plurality of object code modules.

16 more elements

A method for feedback directed inter-procedural optimization, comprising:

generating a first executable program module based on a plurality of source code modules;
collecting profile information based on feedback directed analysis for the plurality of source code modules by executing the first executable program module and wherein the profile information comprises information pertaining to invocation of procedures in the first executable program module;
determining module grouping information for the plurality of source code modules based on procedure invocation patterns in the profile information and according to one or more inter-procedural optimization heuristics, wherein determining the module grouping information comprises:
for each source code module:
creating a module group for the source code module;
designating the source code module as a primary module of the module group;
and
identifying all auxiliary modules of the module group, each of the identified auxiliary modules defining a callee procedure that is called by a caller procedure in the primary module of the module group, wherein identifying all auxiliary modules includes,
for each procedure in the primary module:
identifying all outgoing edges of the procedure that have an edge frequency count exceeding a threshold value, each of the outgoing edges representing a procedural call from the procedure to a second, different procedure;
and
for each of the identified outgoing edges:
identifying a callee procedure associated with the identified outgoing edge;
identifying a defining source code module of the identified callee procedure;
and
designating the identified defining source code module as an auxiliary module of the primary module if the identified defining source code module has not already been so designated;
performing inter-procedural optimization based on the module grouping information to generate a plurality of object code modules, including
performing code transformation on at least one of the identified source code modules based on the identified auxiliary source code modules to create an optimized object code module according to the one or more inter-procedural optimization heuristics, and inlining procedures from the identified auxiliary source code modules into the identified source code module in the plurality of source code modules;
and
generating a second executable program module based on the plurality of object code modules.

17 more elements

A non-transitory computer-readable medium having instructions stored thereon, which, when executed by at least one processor, cause the processor to perform operations comprising:

generating a first executable program module based on a plurality of source code modules;
collecting profile information based on feedback directed analysis for the plurality of source code modules by executing the first executable program module and wherein the profile information comprises information pertaining to invocation of procedures in the first executable program module;
determining module grouping information for the plurality of source code modules based on procedure invocation patterns in the profile information and according to one or more inter-procedural optimization heuristics, wherein determining the module grouping information comprises:
for each source code module:
creating a module group for the source code module;
designating the source code module as a primary module of the module group;
and
identifying all auxiliary modules of the module group, each of the identified auxiliary modules defining a callee procedure that is called by a caller procedure in the primary module of the module group, wherein identifying all auxiliary modules includes,
for each procedure in the primary module:
identifying all outgoing edges of the procedure that have an edge frequency count exceeding a threshold value, each of the outgoing edges representing a procedural call from the procedure to a second different procedure;
and
for each of the identified outgoing edges:
identifying a callee procedure associated with the identified outgoing edge;
identifying a defining source code module of the identified callee procedure;
and
designating the identified defining source code module as an auxiliary module of the primary module if the identified defining source code module has not already been so designated;
performing IPO based on the module grouping information to generate a plurality of object code modules;
and
generating a second executable program module based on the plurality of object code modules.

16 more elements

A non-transitory computer-readable medium having instructions stored thereon, which, when executed by at least one processor, cause the processor to perform operations comprising:

generating a first executable program module based on a plurality of source code modules;
collecting profile information based on feedback directed analysis for the plurality of source code modules by executing the first executable program module and wherein the profile information comprises information pertaining to invocation of procedures in the first executable program module;
determining module grouping information for the plurality of source code modules based on procedure invocation patterns in the profile information and according to one or more inter-procedural optimization heuristics, wherein determining the module grouping information comprises:
for each source code module:
creating a module group for the source code module;
designating the source code module as a primary module of the module group;
and
identifying all auxiliary modules of the module group, each of the identified auxiliary modules defining a callee procedure that is called by a caller procedure in the primary module of the module group, wherein identifying all auxiliary modules includes,
for each procedure in the primary module:
identifying all outgoing edges of the procedure that have an edge frequency count exceeding a threshold value, each of the outgoing edges representing a procedural call from the procedure to a second, different procedure;
and
for each of the identified outgoing edges:
identifying a callee procedure associated with the identified outgoing edge;
identifying a defining source code module of the identified callee procedure;
and
designating the identified defining source code module as an auxiliary module of the primary module if the identified defining source code module has not already been so designated;
performing inter-procedural optimization based on the module grouping information to generate a plurality of object code modules, including
performing code transformation on at least one of the identified source code modules based on the identified auxiliary source code modules to create an optimized object code module according to the one or more inter-procedural optimization heuristics, and inlining procedures from the identified auxiliary source code modules into the identified source code module in the plurality of source code modules;
and
generating a second executable program module based on the plurality of object code modules.

17 more elements

A system comprising:

one or more computers;
memory coupled to the one or more processors and storing instructions which, when executed by the one or more processors, cause the one or more computers to perform operations comprising:
generating a first executable program module based on a plurality of source code modules;
collecting profile information based on feedback directed analysis for the plurality of source code modules by executing the first executable program module and wherein the profile information comprises information pertaining to invocation of procedures in the first executable program module;
determining module grouping information for the plurality of source code modules based on procedure invocation patterns in the profile information and according to one or more inter-procedural optimization heuristics, wherein determining the module grouping information comprises:
for each source code module:
creating a module group for the source code module;
designating the source code module as a primary module of the module group;
and
identifying all auxiliary modules of the module group, each of the identified auxiliary modules defining a callee procedure that is called by a caller procedure in the primary module of the module group, wherein identifying all auxiliary modules includes,
for each procedure in the primary module:
identifying all outgoing edges of the procedure that have an edge frequency count exceeding a threshold value, each of the outgoing edges representing a procedural call from the procedure to a second different procedure;
and
for each of the identified outgoing edges:
identifying a callee procedure associated with the identified outgoing edge;
identifying a defining source code module of the identified callee procedure;
and
designating the identified defining source code module as an auxiliary module of the primary module if the identified defining source code module has not already been so designated;
performing inter-procedural optimization based on the module grouping information to generate a plurality of object code modules;
and
generating a second executable program module based on the plurality of object code modules.

18 more elements

A system comprising:

one or more computers;
memory coupled to the one or more processors and storing instructions which, when executed by the one or more processors, cause the one or more computers to perform operations comprising:
generating a first executable program module based on a plurality of source code modules;
collecting profile information based on feedback directed analysis for the plurality of source code modules by executing the first executable program module and wherein the profile information comprises information pertaining to invocation of procedures in the first executable program module;
determining module grouping information for the plurality of source code modules based on procedure invocation patterns in the profile information and according to one or more inter-procedural optimization heuristics, wherein determining the module grouping information comprises:
for each source code module:
creating a module group for the source code module;
designating the source code module as a primary module of the module group;
and
identifying all auxiliary modules of the module group, each of the identified auxiliary modules defining a callee procedure that is called by a caller procedure in the primary module of the module group, wherein identifying all auxiliary modules includes,
for each procedure in the primary module:
identifying all outgoing edges of the procedure that have an edge frequency count exceeding a threshold value, each of the outgoing edges representing a procedural call from the procedure to a second different procedure;
and
for each of the identified outgoing edges:
identifying a callee procedure associated with the identified outgoing edge;
identifying a defining source code module of the identified callee procedure;
and
designating the identified defining source code module as an auxiliary module of the primary module if the identified defining source code module has not already been so designated;
performing inter-procedural optimization based on the module grouping information to generate a plurality of object code modules, including
performing code transformation on at least one of the identified source code modules based on the identified auxiliary source code modules to create an optimized object code module according to the one or more inter-procedural optimization heuristics, and inlining procedures from the identified auxiliary source code modules into the identified source code module in the plurality of source code modules;
and
generating a second executable program module based on the plurality of object code modules.

19 more elements

Dependencies are inferred from the claim text.