From cTuning.org

Jump to: navigation, search

Google Summer of Code 2009: fine-grain optimizations.

Yuanjie Huang (ICT, China)

This project aims to provide fine-grain optimization selection and tuning abilities in GCC, and thus enable GCC to tune default optimization heuristic of the compiler or fine optimizations for a given program on a given architecture entirely automatically using statistical and machine learning techniques from the MILEPOST project.


Contents

ICI Fine-Grain Tuning Overview

Compilation recording information to XML
Compilation recording information to XML
Compilation reusing information from XML
Compilation reusing information from XML

Key Concepts

This fine grain tuning project is an extension to ICI-2.0, and follows the concepts of ICI.

Work Flow

GCC fine-grain tuning projects brings two modes to GCC: record mode and the reuse mode.

In the record mode, information on compilation is recorded. Currently XML files are generated to log passes executed on each function, and parameters for several ICI-enabled passes, which describe the characteristic of the program being compiled and the internal decision making process of GCC.

Then the recorded information could be modified by machine learning algorithms or iterative seach engine, and loaded while compiling the program again in reuse mode. Thus internal heuristics are overridden, and GCC yields differently optimized code.

The work flow of ICI fine-grain tuning project on GCC 4.4 is illustrated in the two figures on the right.

Future Work

  • Provide a flexible yet easy-to-use mechanism to represent the compilation work flow and ICI control, and remove EP_SILENT type from ICI fine-grain tuning parameter types.
  • Enable fine grain tuning in more GCC optimization passes.
  • Develop a tool to translate function specific optimization options into pass and optimizations parameters.


ICI Events

Compilation recording information to XML
Compilation recording information to XML

ICI events are used to stop normal compilation flow of GCC and execute callback function from ICI plugin. ICI Events for fine-grain tuning are shown in the figure on the right.


'New ICI Events for Fine-Grain Tuning'
Name Triggered in Description
Passes Record/Substitution Events
"all_ipa_passes_start" cgraphunit.c This event is raised before executing GCC's IPA optimization passes. Currently unused.
"all_ipa_passes_execution" cgraphunit.c This event is raised just before executing GCC's IPA optimization passes. If this event's callback is successfully executed, and ici_ipa_passes_substitution_status</t> parameter, i.e. <tt>substitute_status ICI event parameter is set to non-zero value, GCC's default IPA passes will not be executed.
"all_ipa_passes_end" cgraphunit.c This event is raised just after executing GCC's IPA optimization passes. Currently used to instruct adapt plugin to stream recorded information into XML file.
"early_gimple_passes_start" passes.c This event is raised just before execute the first early local optimization pass, i.e. GIMPLE pass, in IPA passes. Currently used to send a recording heuristic to adapt plugin.
"early_gimple_passes_end" passes.c This event is raised just after execute the last early local optimization pass, i.e. GIMPLE pass, in IPA passes. Currently used to send a recording heuristic to adapt plugin.
"all_passes_start" tree-optimize.c This event is raised before executing GCC's optimization passes on function being compiled. Currently unused.
"all_passes_execution" tree-optimize.c This event is raised just before executing GCC's optimization passes on function being compiled. If this event's callback is successfully executed, and ici_passes_substitution_status parameter, i.e. substitute_status ICI event parameter is set to non-zero value, GCC's default passes will not be executed.
"all_passes_end" tree-optimize.c This event is raised just after executing GCC's optimization passes on function being compiled. Currently used to instruct adapt plugin to stream recorded information into XML file.
"avoid_gate" passes.c This event is raised after the GCC's default gate status is set and before the execution of a pass. Thus the gate status can be overridden by the plugin when handling this event.
"pass_execution" passes.c This event is raised after the gate status is determined.
Warning: since functions generated by IPCP optimization would cause problems, pass execution event will not be raised if current_function_decl is set and DECL_ARTIFICIAL (current_function_decl) is non-zero.
Function Specific Optimizations Tuning Events
"function_spec_loader" cgraphunit.c Special Event in ici_load_function_specific_optimizations function, this event is raised for every function in call graph.
Optimization Parameter Tuning Events
"graphite_parameter_handler" graphite.c This event is raised for when some event parameter should be recorded or loaded from plugin.
"unroll_parameter_handler" loop-unroll.c This event is raised for when some event parameter should be recorded or loaded from plugin.
Extra info
"exmaple_event" source.c none

ICI Features

New Features

ICI features added to the framework for fine-grain tuning are documented here.

Feature name Type of contents Description
"main_input_filename" array of strings, i.e., char ** Name of the file which serves as the main input file of compiler .

Known Issue of ICI 2.0 Features

  • "function_filename" can be empty for functions generated by IPCP optimization.
  • "function_name" returns NULL pointer when compiling fortran functions.

ICI Parameters

ICI Parameter with Type

ICI parameters now come with a type which should be declared when registering parameters in ICI, currently only a few basic C types are supported: void, char, unsigned char, int, unsigned int, long and unsigned long. A special type named EP_SILENT is introduced to pass parameters that is only used to pass status information to plugin; it's actually int, and is planned to be replaced by a elegant solution. The parameter type is defined in gcc/highlev-plugin-internal.h and gcc/highlev-plugin.h:

/* Datatype of event parameter pointer  */
typedef enum
{
  EP_SILENT,
  EP_VOID,
  EP_CHAR,
  EP_UNSIGNED_CHAR,
  EP_INT;
  EP_UNSIGNED_INT,
  EP_LONG,
  EP_UNSIGNED_LONG
} event_parameter_type;

The representation of parameters is defined in file gcc/events.c:

/* Parameter structure.  */
struct event_parameter
{
  const char *name;            /* Name for the parameter */
  const void *value;           /* Pointer to data */
  event_parameter_type type;   /* Type enumeration of value */
};

ICI Parameter Handling APIs

See ICI API sector below: register_event_parameter get_event_parameter_type

ICI API

Parameter Management

register_event_parameter: register a new ICI parameter

Prototype void register_event_parameter (const char *name, const void* value, event_parameter_type type)
API level FICI0
Declared in highlev-plugin.h
Implemented in events.c
Inputs name: name of the parameter
value pointer to data
type type of data
Return value none
Description

Define a new ICI parameter named name, with a pointer value to some data of type. Trigger an internal compiler error (failed assertion) if name is invalid.

Prerequisites

name can be neither NULL nor an empty string. <type> is a valid type defined in event_parameter_type.

Outputs

See also

get_event_parameter_type

get_event_parameter_type: get the type of an ICI event parameter

Prototype event_parameter_type get_event_parameter_type (const char *name)
API level FICI0
Declared in highlev-plugin.h
Implemented in events.c
Inputs name: name of the parameter
Return value EP_VOID if the parameter was found;
otherwise, the type of parameter named name
Description

Get the type of an event parameter. Trigger an internal compiler error if no parameters were registered prior to calling this function.

Prerequisites

Parameter hash table must have been initialized prior to calling this function.

Outputs

Informational message if parameters hash table does not exists.

See also

register_event_parameter

Pass Management

run_pass: run a pass

Prototype void run_pass (const char *name)
API level FICI0
Declared in pass-manager.h
Implemented in pass-manager.c
Inputs name: name of the pass
Return value none
Description

Execute the pass registered with name prior to calling this function on current function. Warning: IPA passes should not be execute with this function, use run_ipa_passinstead.

Prerequisites

A pass of the specified name has been registered prior to calling this function.

Outputs

See also

run_ipa_pass

run_ipa_pass: run an IPA pass

Prototype void run_ipa_pass (const char *name)
API level FICI0
Declared in pass-manager.h
Implemented in pass-manager.c
Inputs name: name of the pass
Return value none
Description

Execute the IPA pass registered with name prior to calling this function on current function.

Prerequisites

An IPA pass of the specified name has been registered prior to calling this function.

Outputs

See also

run_pass


initialize_ici_pass_list: initialize a list of passes for ICI batch execution

Prototype void *initialize_ici_pass_list (int num)
API level FICI0
Declared in pass-manager.h
Implemented in pass-manager.c
Inputs num: maximum number of passes.
Return value array of opt_pass pointers of size (num + 1).
Description

Initialize a list of NULL pointers of pass type.

Prerequisites

Outputs

See also

insert_ici_pass_list, run_ici_pass_list, run_ici_pass_list_ipa_summary, run_ici_pass_list_per_function, delete_ici_pass_list

insert_ici_pass_list: insert a pass into ICI pass list

Prototype void insert_ici_pass_list (void *list, int cursor, const char *name)
API level FICI0
Declared in pass-manager.h
Implemented in pass-manager.c
Inputs list: a pointer to ICI pass list (an array of opt_pass pointers).
cursor: an integer indicating the slot to insert pass into.
name: the name of the pass to be inserted.
Return value none
Description

Insert a pass named name into ICI pass list list at position specified by cursor.

Prerequisites

An pass named name has been registered prior to calling this function.
The cursor indicates an empty slot in list.

Outputs

Informational message if the slot specified by cursor is not empty prior to calling this function.

See also

initialize_ici_pass_list, run_ici_pass_list, run_ici_pass_list_ipa_summary, run_ici_pass_list_per_function, delete_ici_pass_list

run_ici_pass_list: execute an ICI pass list on current function

Prototype void run_ici_pass_list (void *list)
API level FICI0
Declared in pass-manager.h
Implemented in pass-manager.c
Inputs list: a pointer to ICI pass list (an array of opt_pass pointers).
Return value none
Description

Execute an ICI pass list list on function being compiled.

Prerequisites

List is not empty and current function is specified in GCC.

Outputs

See also

initialize_ici_pass_list, insert_ici_pass_list, run_ici_pass_list_ipa_summary, run_ici_pass_list_per_function, delete_ici_pass_list

run_ici_pass_list_ipa_summary: generate IPA summaries for an ICI pass list on current cgraph

Prototype void run_ici_pass_list_ipa_summary (void *list)
API level FICI0
Declared in pass-manager.h
Implemented in pass-manager.c
Inputs list: a pointer to ICI pass list (an array of opt_pass pointers) of IPA passes.
Return value none
Description

Generate summaries for all IPA passes in ICI pass list list.

Prerequisites

List is not empty and current function is specified in GCC.

Outputs

See also

initialize_ici_pass_list, insert_ici_pass_list, run_ici_pass_list, run_ici_pass_list_per_function, delete_ici_pass_list

run_ici_pass_list_per_function: execute an ICI pass list on current cgraph

Prototype void run_ici_pass_list_per_function (void *list)
API level FICI0
Declared in pass-manager.h
Implemented in pass-manager.c
Inputs list: a pointer to ICI pass list (an array of opt_pass pointers).
Return value none
Description

Execute an ICI pass list list on call graph functions one by one in 'top order'.

Prerequisites

List is not empty.

Outputs

See also

initialize_ici_pass_list, insert_ici_pass_list, run_ici_pass_list, run_ici_pass_list_ipa_summary, delete_ici_pass_list

delete_ici_pass_list: delete an ICI pass list

Prototype void insert_ici_pass_list (void *list, int *cursor, char *name)
API level FICI0
Declared in pass-manager.h
Implemented in pass-manager.c
Inputs list: a pointer to ICI pass list (an array of opt_pass pointers).
Return value none
Description

Delete an ICI pass list list.

Prerequisites

List is not empty.

Outputs

See also

initialize_ici_pass_list, insert_ici_pass_list, run_ici_pass_list, run_ici_pass_list_ipa_summary, run_ici_pass_list_per_function


Adapt Plugin

Adapt plugin provides support for GCC pass sequence record/substitution, function-specific optimization tuning, function clone and instrumentation. Plugins developed for fine-grain tuning are documented here. These plugins are developed to work with ICI-2.0 interface.

The behavior of the plugin is controled via ICI_ADAPT_CONTROL environment variable. When this variable is set to 1, information on compilation will be recorded into XML files; while this variable is set to 2, adapt plugin will reuse information from XML and tune GCC compilation workflow via ICI.


Install and Usage

Adapt plugin is depends on Mini-XML library, which provides XML reading and writing ability.

Different functionalities in adapt plugin can be enabled with in different compilation macros:

  • SUPPORT_PASSES : pass recording and substitution
  • SUPPORT_PARAMETERS : parameter tuning, need SUPPORT_PASSES
  • SUPPORT_CLONE : clone and instrumentation, need SUPPORT_PASSES
  • SUPPORT_FUNCTION_SPEC : set function specific optimizations with XML.

To compile with all these functions, set CC_SHARED parameter in Makefile like this:

CC_SHARED=gcc -ansi -fPIC -D SUPPORT_PASSES -D SUPPORT_PARAMETERS -D SUPPORT_CLONE -D SUPPORT_FUNCTION_SPEC

This plugin behaves differently depending on the ICI_ADAPT_CONTROL environmental variable, which can be either set to 1 to record information of current compilation into XML files or to 2 to reuse passes from XML files to perform passes substitution, function clone and other functionalities.

To use adapt plugin with ICI, ICI_PLUGIN environment variable should be set to the path to the plugin library (.so), and gcc should be called with with either -fici flag or ICI_USE environment parameter.


Pass Recoding and Substitution

Adapt plugin can be used to record or substite pass during compilation with information from XML files.

Description

Currently, there are two kinds of passes in GCC - IPA passes, which is executed on call graph, and GIMPLE passes. which is executed on one function. Those IPA passes are recorded per main input file, while those GIMPLE passes are recorded per pair of file in which the funtion is defined and the function name. Early local optimizations passes are special cases: they are of GIMPLE type, but since they are executed in IPA stage, they are currently stored to or read from XML file for IPA passes, included in gimple_pass_list tag inside ipa_pass_list tag.

XML file location

The name of XML file storing pass execution information is formated as:

gcc_compilation_flow@file_name@function_name@.xml

The file_name above is an escaped string of the pass to the source file (main input file for IPA passes or function define location file for GIMPLE passes). The escape rule is:

  • The escaped file name consists two parts in sequence: prefix and substituted file name
  • substituted file name is generated by substituting all directory separators with underscores.
  • If there is no directory separator in the file name, the prefix is an underscore.
  • If there is directory separator in the file name, the prefix starts with character '1' followed by three characters indicating the number of occurance in HEX, and then the offset(s) of separator(s) each represented in 3 character HEX. For example, prefix "1002011013" means there are two escaped separators in the following string, in position 17 and 19 with the first character in substituted file name referred as position 0.

An environment variable named ICI_ADAPT_XMLDIR can be used to specify a dir to save or find XML files. If this variable is not set or empty, current working directory will be used.

Adapt XML DTD

Here's XML file structure used in Adapt plugin, defined in DTD syntax (Draft):

<!ELEMENT ici (plugin, compiler, function)>

<!ELEMENT plugin (plugin_name, plugin_version)>
<!ELEMENT plugin_name (#PCDATA)>
<!ELEMENT plugin_version (#PCDATA)>

<!ELEMENT compiler (compiler_version)>
<!ELEMENT compiler_version (#PCDATA)>

<!ELEMENT function (optimizaton_options, (ipa_pass_list|gimple_pass_list)?)>
<!ATTLIST function function_name CDATA #REQUIRED>
<!ATTLIST function function_filename CDATA #REQUIRED>
<!ATTLIST function function_start_line CDATA #IMPLIED>
<!ATTLIST function function_end_line CDATA #IMPLIED>

<!ELEMENT optimizaton_options (#PCDATA)>

<!ELEMENT ipa_pass_list (pass*, gimple_pass_list?, pass*))>
<!ELEMENT gimple_pass_list (pass*)>

<!ELEMENT pass (parameter*, loop*)>
<!ATTLIST pass pass_name CDATA #REQUIRED>
<!ATTLIST pass pass_type (GIMPLE | RTL | SIMPLE_IPA | IPA) #IMPLIED>

<!ELEMENT loop (parameter*)>
<!ATTLIST loop loop_id CDATA #REQUIRED>

<!ELEMENT parameter (#PCDATA)>
<!ATTLIST parameter param_name CDATA #REQUIRED>
<!ATTLIST parameter param_type (void | char | unsigned_char | int | unsigned_int | long | unsigned_long) #REQUIRED>

In order to support function clone and instrumentation the DTD above shoule be extended like this:

<!ELEMENT ici (plugin, compiler, function)>

<!ELEMENT plugin (plugin_name, plugin_version)>
<!ELEMENT plugin_name (#PCDATA)>
<!ELEMENT plugin_version (#PCDATA)>

<!ELEMENT compiler (compiler_version)>
<!ELEMENT compiler_version (#PCDATA)>

<!ELEMENT function (optimizaton_options?, (ipa_pass_list|gimple_pass_list)?, clones?, clone_name_extension?, adaptation_function?, add_function_call_before_func?, add_function_call_after_func?, options_clone?)>
<!ATTLIST function function_name CDATA #REQUIRED>
<!ATTLIST function function_filename CDATA #REQUIRED>
<!ATTLIST function function_start_line CDATA #IMPLIED>
<!ATTLIST function function_end_line CDATA #IMPLIED>

<!ELEMENT optimizaton_options (#PCDATA)>

<!ELEMENT ipa_pass_list (pass*, gimple_pass_list?, pass*))>
<!ELEMENT gimple_pass_list (pass*)>

<!ELEMENT pass (parameter*, loop*)>
<!ATTLIST pass pass_name CDATA #REQUIRED>
<!ATTLIST pass pass_type (GIMPLE | RTL | SIMPLE_IPA | IPA) #IMPLIED>

<!ELEMENT loop (parameter*)>
<!ATTLIST loop loop_id CDATA #REQUIRED>

<!ELEMENT parameter (#PCDATA)>
<!ATTLIST parameter param_name CDATA #REQUIRED>
<!ATTLIST parameter param_type (void | char | unsigned_char | int | unsigned_int | long | unsigned_long) #REQUIRED>

<!ELEMENT clones (#PCDATA)>
<!ELEMENT clone_name_extension (#PCDATA)>
<!ELEMENT adaptation_function (#PCDATA)>
<!ELEMENT add_function_call_before_func (#PCDATA)>
<!ELEMENT add_function_call_after_func (#PCDATA)>
<!ELEMENT options_clone (#PCDATA)>

XML TODOs:

  • Provide script to verify XML file.
  • Re-design the XML vocabulary to express clone concept more clearly.


Fine-Grain Parameter Tuning

Parameters for passes with ICI can be recorded and tuned with adapt plugin.

Description

During the first compilation, parameters are saved into correponding pass node in XML files. If it is a loop level optimization, parameters of different loops are saved in different loop nodes identified by loop id. During the second compilation, ICI event handlers will alter the parameters as specified in the XML files.

A conventon is employed to keep parameters that only provides information on currently compilation status unalterable: parameters whose name starts with an underscore ('_') will not be changed by ICI plugin.

ICI enabled passes

Currently 2 passes can tuned with ICI:

  • loop-unroll: performs loop unroll and loop peeling
  • graphite: performs loop interchange, loop strip mine and loop blocking on SCOPs

XML format

Parameters and other information for fine grain tuning is saved in the same XML files as parameter tuning, the structure of XML file is disribed with DTD in pass recording/substitution sector.

Known issues

  • During loop-unroll optimization, wrong optimization heuristics might be applied to loops as a result of different loop id (loop->num) across compilations.


Function Specific Optimization Options Tuning

Adapt plugin makes it possible to set function specific optimizations with XML files.

Description

GCC allows different command line optimization options to be set for each function, and this plugin functionnality is analog to command line settings. Through adapt plugin, optimizations options can be given in the same format as command line arguments, and is represented in a plain character string tagged optimization_options in function tag.

XML format

The XML scheme is also the same as pass management XML file.However, because this function can work without pass recording/substitution enabled, you may provide an XML file in different scheme as long as there is one optimization_options tag in the XML tree.

Known issues

none


Function Clone and Instrumentation

The function clone and instrumentation functionality is implemented in another project by Liang Peng from ICT, China.


Scripts

A set of scripts have been writen to automate the installation and compilation process. These scripts could be used with both fine-grain tuning project and function cloning and program instrumentation project, please refer to this page for usage information.

Locations of visitors to this page

Tweet