CTools:ICI:Projects:GSOC09:Fine grain tuning

From cTuning.org

Current revision

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.

• GSOC'09 project description
• cTuning development mailing list
• SVN repository hosted on SourceForge.net®

  http://gcc-ici.svn.sourceforge.net/viewvc/gcc-ici/branches/

ICI Fine-Grain Tuning Overview

Compilation recording information to 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

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.

ICI Features

New Features

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

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

get_event_parameter_type: get the type of an ICI event parameter

Pass Management

run_pass: run a pass

run_ipa_pass: run an IPA pass

initialize_ici_pass_list: initialize a list of passes for ICI batch execution

insert_ici_pass_list: insert a pass into ICI pass list

run_ici_pass_list: execute an ICI pass list on current function

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

run_ici_pass_list_per_function: execute an ICI pass list on current cgraph

delete_ici_pass_list: delete an ICI pass list

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.