IBB: The XFOR compiler

http://xfor.gforge.inria.fr

What is the XFOR structure?

The xfor is a new programming control structure of the C language. A xfor-loop defines several loops whose bodies run in interleaved mode. Respective iteration domains are mapped onto each other according to a running frequency, the grain, and a relative position, the offset. A source-to-source compiler, IBB for Iterate-But-Better!, enabling xfor programming has been developed.

We give a brief description of the current syntax and semantics which can be extended in many ways in the future.

XFOR Syntax and Semantics

The syntax of a xfor is defined as follows:

where […] denotes optional arguments, index denotes the indices of the loops composing the xfor, expr denotes affine arithmetic expressions on englobing loop indices, or constants, increment denotes an integer constant, grain is an integer ≥ 1, offset is either an integer verifying offset ≥ 0 or an invariant affine arithmetic expression, and prefix is a positive integer associating each statement to a given for-loop composing the xfor-loop, according to the order in which they are defined ( 0 for the first loop, 1 for the second loop, etc.).

Each for-loop composing the xfor behaves as a traditional for-loop, but all are mapped on a same global “virtual referential” domain, which can also be seen as a template. The way the iteration domains of the for-loops are mapped relatively to each other is defined by their respective offset and grain, and not at all by the values of their respective indices. The grain defines the frequency in which the associated loop has to run, relatively to the referential. The offset defines the gap between the first iteration of the referential and the first iteration of the associated loop.

The bodies of each for-loop composing the xfor-loop can be any C/C++ code. However, they only have access to their respective indices which cannot be modified elsewhere than in the loop header by the increment.

Examples

Here are examples of xfor-loop, the corresponding referential domain representation, and the resulting code generated by IBB:

Nested XFOR-Loops

Nested xfor-loops are behaving like several nested for-loops which are synchronized according the common referential domain. Nested for-loops are defined according the order in which they appear in the xfor structures. For instance, in a 2-depth xfor nest, the first index of the outermost loop is related to the first index of the inner loop, the second to the second, and so on. Hence the same number of indices have to be defined at each level of any xfor nest, which is not a strong restriction since indices of one unique value can be defined.

Example

This is an example of a xfor-loop nest, the corresponding referential domain representation and the resulting code generated by IBB:

More examples are detailed in our papers.

Iterate, But Better !… with the IBB compiler

We developed a xfor-compiler called IBB. IBB translates any C program containing xfor-loops into an equivalent C program in which all xfor-loops are replaced with equivalent for-loops. The resulting source code can then be compiled using any C compiler to produce executable code.