Integration of ISL code generator into Graphite Wiki

Summary

ISL is nowadays mature enough to replace CLooG with own code generation that sometimes is better. Our project aims to integrate ISL code generation into Graphite and avoid necessity of CLooG in GCC.

The project

For a long period of time Graphite was relying on CLooG [1] to produce GIMPLE code. The Integer Set Library (ISL) [2] recently became available in this project to be used as a back end of CLooG. ISL is nowadays mature enough to replace CLooG with own code generation that sometimes is better. Our proposal aims to integrate ISL code generation into Graphite and avoid necessity of CLooG in GCC.

Graphite uses the polyhedral model as a basic model for loop optimization and parallelization. Subsequently, it uses CLooG to perform code generation for loops represented in the polyhedral model. Graphite is now able to use ISL back end of CLooG for generating code out of polyhedral program representation.

The goal of our project is to totally replace CLooG with ISL to perform code generation. ISL will generate ISL AST, which is a simple abstract-syntax tree containing only loops, conditions, and statements. GIMPLE code corresponding to transformed polyhedral model will be then regenerated from this representation.

Benefits for Graphite

Details about the project

In source-to-source polyhedral compilers, the code generation pass is the last one, generating the new loop structures to scan statement instances in the order defined by the modified schedule. CLooG is used in graphite as the major component of code generation.

In Graphite it is not the syntactical source code that is the final result of the pass: graphite should be able to regenerate the GIMPLE code. Furthermore, the generated GIMPLE code has to be reinserted back into the CFG, respecting the SSA form invariants and passed to the further passes after Graphite.

Graphite uses CLooG as the major component of this code generation. CLooG generates an internal representation called CLAST which is a simple abstract-syntax tree containing only loops, conditions, and statements. In our case statements are replaced with basic blocks.

CLooG is fed by the polyhedral representation (GPOLY) and is asked to generate a CLAST through GLooG (GIMPLE Loop Generator) “scop_to_clast()”. The nodes of the abstract-syntax tree are pointers to original basic blocks. Depending on the loop transformations, the basic blocks might be rescheduled, moved to other loops, or even replicated (when performing a transformation). The final effect is represented in the CLAST. The CLAST tree is traversed through GLooG “translate_clast()” and the basic blocks are put into the their new positions in the GIMPLE CFG, loop structures are regenerated and some basic blocks are replicated.

Even in the case of the identity transformation (no schedule modification), the newly generated loops according to the CLAST tree have the new induction variables. All the basic blocks belonging to a SCoP have to be scanned, and the old induction variables have to be replaced with new induction variables.

ISL will generate ISL AST, which is a simple abstract-syntax tree containing only loops, conditions, and statements. Its statements also will be pointers to original basic blocks. After this it will be traversed and transformed into the GIMPLE CFG.

An API introduced by ISL for code generation is generally similar to the API introduced by CLooG, but has differences. In this section, we present a list of some differences between them:

In CLooG an AST can be constructed using “cloog_clast_create_from_input()”. “cloog_clast_create_from_input()” must be called with two arguments. The first of them influences on constructed AST and has type of pointer to CloogInput. A CloogInput structure represents the input to CLooG. It is essentially a CloogUnionDomain along with a context CloogDomain. CloogDomain is an type representing a polyhedral domain (a union of polyhedra). Graphite uses “cloog_clast_create_from_input()” to generate CLAST representation and “generate_cloog_input()” to create its first argument mentioned previously. “generate_cloog_input()” transforms type of scop's context to type, which is appropriate for CloogInput. “build_cloog_union_domain” is used for generation of CloogUnionDomain, which contains all CloogUnion corresponding to all basic blocks in the given scop.

In ISL an AST can be constructed using “isl_ast_build_ast_from_schedule”. “isl_ast_build_ast_from_schedule” also must be called with two arguments. The first of them must have isl_ast_build type, which specifies the context and can be created using isl_ast_build_from_context. The second argument of “isl_ast_build_ast_from_schedule” must have isl_union_map type. In particular, given a isl_union_map, an AST is generated that visits all the elements in the domain of the isl_union_map according to the lexicographic order of the corresponding image element(s).

In our case the second argument can be the union of all maps constructed by intersection of scattering functions' domains with corresponding domains of all basic blocks in the given scop.

In CLooG An AST constructed by cloog_clast_create_from_input has the type clast_stmt, which represents a linked list of “statements”, which allows to traverse an AST tree. The following statement types are defined by CLooG: clast_root, clast_assignment, clast_block, clast_user_stmt, clast_for, clast_guard. The clast_stmt returned by cloog_clast_create is a clast_root. It contains a placeholder for all the variable names that appear in the AST and a (list of) nested statement(s).

A clast_assignment assigns the value given by the clast_expr RHS to a variable named LHS. A clast_block groups a list of statements into one statement. A clast_user_stmt represents a call to a statement specified by the user. A clast_for represents a for loop.

A clast_guard represents the guarded execution of the then (list of) statement(s).

ISL has similar representation of an AST and own mechanism to traverse it. In ISL the type of an AST node is one of isl_ast_node_for, isl_ast_node_if, isl_ast_node_block or isl_ast_node_user. An isl_ast_node_for represents a for node. An isl_ast_node_if represents an if node. An isl_ast_node_block represents a compound node. An isl_ast_node_user represents an expression statement. An expression statement typically corresponds to a domain element, i.e., one of the elements that is visited by the AST. ISL uses the following functions to get child nodes of AST tree: “isl_ast_node_for_get_body()”, “isl_ast_node_if_get_then()”, “isl_ast_node_if_get_else()”, “isl_ast_node_block_get_children()”.

Timeline

Required deliverables

Nice to have

According to advancement in work on the integration and results, we want to :

Ref

[1] http://www.cloog.org/

[2] http://isl.gforge.inria.fr/

[3] http://www.marshut.com/whwvq/performance-comparison-between-cloog-and-isl-code-generation.html

[4] http://polly.llvm.org/index.html

None: ISLCodeGenerator (last edited 2014-05-16 19:42:48 by RomanGareev)