Towards a Semantics-Aware Code Transformation Toolchain
for Heterogeneous Systems∗
Salvador Tamarit

Julio Mariño

Guillermo Vigueras

Manuel Carro†

Universidad Politécnica de Madrid
IMDEA Software Institute
Campus de Montegancedo 28660
Campus de Montegancedo 28223
Boadilla del Monte, Madrid, Spain
Pozuelo de Alarcón, Madrid, Spain
{salvador.tamarit,julio.marino}@upm.es {guillermo.vigueras,manuel.carro}@imdea.org

Obtaining good performance when programming heterogeneous computing platforms poses significant challenges. We present a program transformation environment, implemented in Haskell, where
architecture-agnostic scientific C code with semantic annotations is transformed into functionally
equivalent code better suited for a given platform. The transformation steps are represented as rules
that can be fired when certain syntactic and semantic conditions are fulfilled. These rules are not
hard-wired into the rewriting engine: they are written in a C-like language and are automatically
processed and incorporated into the rewriting engine. That makes it possible for end-users to add
their own rules or to provide sets of rules that are adapted to certain specific domains or purposes.

Keywords: Rule-based program transformation, Semantics-aware program transformation, High-performance, Heterogeneous platforms, Scientific computing, Domain-specific language, Haskell, C.

1

Introduction

There is a strong trend in high-performance computing towards the integration of heterogeneous computing elements: vector processors, GPUs, FPGAs, etc. Each of these components is specially suited
for some class of computations, which makes the resulting platform able to excel in performance by
mapping computations to the unit best suited to execute them. Such platforms are proving to be a costeffective alternative to more traditional supercomputing architectures [8, 17] in terms of performance
and energy consumption. However, this specialization comes at the price of additional hardware and,
notably, software complexity. Developers must take care of very different features to make the most of
the underlying computing infrastructure. Thus, programming these systems is restricted to a few experts,
which hinders its widespread adoption, increases the likelihood of bugs, and greatly limits portability.
For these reasons, defining programming models that ease the task of efficiently programming heterogeneous systems has become a topic of great relevance and is the objective of many ongoing efforts (for
example, the POLCA project http://polca-project.eu, which focuses on scientific applications).
Scientific applications sit at the core of many research projects of industrial relevance that require, for
example, simulating physical systems or numerically solving differential equations. One distinguishing
characteristic of many scientific applications is that they rely on a large base of existing algorithms.
These algorithms often need to be ported to new architectures and exploit their computational strengths
to the limit, while avoiding pitfalls and bottlenecks. Of course, these new versions have to preserve
∗ Work

partially funded by EU FP7-ICT-2013.3.4 project 610686 POLCA, Comunidad de Madrid project S2013/ICE-2731
N-Greens Software, and MINECO Projects TIN2012-39391-C04-03 / TIN2012-39391-C04-04 (StrongSoft), TIN2013-44742C4-1-R (CAVI-ROSE), and TIN2015-67522-C3-1-R (TRACES).
† Manuel Carro is also affiliated with the Universidad Politécnica de Madrid

A. Villanueva (Ed.): PROLE 2016
EPTCS 237, 2017, pp. 34–51, doi:10.4204/EPTCS.237.3

c S. Tamarit, J. Mariño, G. Vigueras & M. Carro
This work is licensed under the
Creative Commons Attribution License.

S. Tamarit, J. Mariño, G. Vigueras & M. Carro
0 - original code

1 - F OR -L OOP F USION

float c[N], v[N], a, b;
for(int i=0;i<N;i++)
c[i] = a*v[i];

for(int i=0;i<N;i++) {
c[i] = a*v[i];
c[i] += b*v[i];
}

for(int i=0;i<N;i++)
c[i] += b*v[i];

3 - J OINA SSIGNMENTS

4 - U NDO D ISTRIBUTE

for(int i=0;i<N;i++)
c[i] = a*v[i]+b*v[i];

for(int i=0;i<N;i++)
c[i] = (a+b) * v[i];

35
2 - AUG A DDITIONA SSIGN
for(int i=0;i<N;i++) {
c[i] = a*v[i];
c[i] = c[i] +
b*v[i];
}

5 -L OOP I NV C ODE M OTION
float k = a + b;
for(int i=0;i<N;i++)
c[i] = k * v[i];

Figure 1: A sequence of transformations of a piece of C code to compute c = av + bv.
the functional properties of the original code. Porting is often carried out by transforming or replacing
certain fragments of code to improve their performance in a given architecture while preserving their
semantics. Unfortunately, (legacy) code often does not clearly spell its meaning or the programmer’s
intentions, although scientific code usually follows patterns rooted in its mathematical origin.
Our goal is to obtain a framework for the transformation of (scientific), architecture-agnostic C code.
The framework should be able to transform existing code into a functionally equivalent program, only
better suited for a given platform. Despite the broad range of compilation and refactoring tools available [2, 25, 21], no existing tool fits our needs by being adaptable enough to flexibly recognize specific
source patterns and generate code better adapted to different architectures (Section 2), so we decided to
implement our own transformation framework. Its core is a code rewriting engine, written in Haskell,
that works at the abstract syntax tree (AST) level. The engine executes transformation rules written in
a C-like, domain-specific language (STML, inspired by CTT [4] and CML [6]). This makes understanding the meaning of the rules and defining additional rulesets for specific domains or targets easy for C
programmers.
The tool does not have hard-wired strategies to select which rules are the most appropriate for each
case. Instead, it is modularly designed to use external oracles that help in selecting which rules have to
be applied. In this respect, we are developing human interfaces and machine learning-based tools that
advice on the selection of the most promising transformation chain(s) [24]. The tool also includes an
interactive mode to allow for more steering by expert users. When code deemed adequate for the target
architecture is reached, it is handed out to a translator in charge of adapting it to the programming model
of the target platform.
Fig. 1 shows a sample code transformation sequence, containing an original fragment of C code along
with the result of stepwise applying a number of transformations. Although the examples presented in
this paper are simple, the tool is able to transform much more complex, real-life code, including code
with arbitrarily nested loops (both for collapsing them in a single loop and creating them from non-nested
loops), code that needs inlining, and others. Some of these transformations are currently done by existing
optimizing compilers. However, they are usually performed internally, at the intermediate representation
(IR) level, and with few, if any, opportunities for user intervention or tailoring, which falls short to cater
for many relevant situations that we want to address:
• Most compilers are designed to work with minimal (if any) interaction with the environment.
While this situation is optimal when it can be applied, in many cases static analysis cannot discover
the underlying properties that a programmer knows. For example, in Fig. 1, a compiler would rely

36

Towards a Semantics-Aware Code Transformation Toolchain for Heterogeneous Systems
Rule execution(s)
Ready code
Rule
library
(STML)

Translated code
GPGPU (OpenCL)

Initial
code

OpenMP
MPI
FPGA (MaxJ, POROTO)
DSP (FlexaWare)
Transformation

Translation

Engine written in Haskell
Rule library
(Haskell)

.hs

.hs

.hs

Figure 2: Architecture of the transformation tool.
on native knowledge of the properties of multiplication and addition. If these operations were
substituted by calls to functions implementing operations with the same properties (distributivity,
associativity, commutativity), such as operations on matrices, the transformation presented would
be feasible but unlikely to be performed by a compiler relying solely on static analysis.
• Most compilers have a set of standard transformations that are useful for usual architectures —
commonly Von Neumann-based CPU architectures. However, when CPU-generic code is to be
adapted for a specific architecture (e.g., FPGA, GPGPU) the transformations to be made are not
trivial and fall outside those usually implemented in standard compilers. Even more, compilers
(such as ROCCC [14]) that accept a subset of the C language and generate executables or lowerlevel code for a specific architecture, need the input code to follow specific coding patterns, which
our tool can help generate.
• Transformations to generate code amenable to be compiled down to some hybrid architecture can
be sometimes complex and are better expressed at a higher level rather than inside a compiler’s
architecture. That could require users to come up with transformations that are better suited for
a given coding style or application domain. Therefore, giving programmers the possibility of
defining transformations at a higher level as plugins for a compiler greatly enlarges the set of
scenarios where automatic program manipulation can be applied.
Fig. 2 shows an overview of the tool, designed to work in two stages: a transformation phase (Section 3) and a translation phase (Section 4). The transformation phase rewrites the original input code into
a form that follows coding patterns closer to what is appropriate for the destination architecture. That
code can be given to compilers that accept C code adapted to the targeted architecture [14]. Additionally,
this transformation phase can be used to other purposes, such as sophisticated code refactoring. The
translation phase converts transformed code into code that can be compiled for the appropriate architec-

S. Tamarit, J. Mariño, G. Vigueras & M. Carro

37

ture by tools that do not accept (sequential) C code. For example, in our case MaxJ [18] code can be
generated, as well as C code with OpenMP annotations or with MPI calls.
Our efforts have focused so far on the transformation phase [22]. Our initial work on the translation
phase shows encouraging results and points to next steps which we present in more detail in Section 6.

2

Related Work

Some related approaches generate code from a mathematical model (automatic code synthesis), while
others use (mathematical) properties to transform existing code. The former can in many cases generate
underperforming code because of its generality. The latter usually requires that the initial code is in some
“canonical” form.
An example of code generation based on mathematical specifications is [11], which focuses on synthesizing code for matrix operations. The starting point is a mathematical formula that is transformed
(not automatically) using rewriting rules to generate another formula that can be implemented in a hopefully more efficient way. This kind of approaches are often very domain-dependent and restricted to
a certain kind of formulas or mathematical objects, which makes their application to general domains
not straightforward, if possible at all. Given that the starting point is a mathematical formula, applying
them to legacy code is not easy. Also, their code generation is usually based on composing blocks that
correspond to patterns for the basic formulas, where inter-optimization is often not exercised.
There are some language-independent transformation tools that share some similarities with our approach. The most relevant ones are Stratego-XT [25], TXL [7], DMS [3] and Rascal [15]. Stratego-XT
is more oriented to strategies than to rewriting rules, and its rule language is too limited for our needs
(e.g., rule firing does not depend on semantic conditions that express when applying a rule is sound).
This may be adequate for a functional language featuring referential transparency, but not for a procedural language. Besides, it is not designed to add analyzers as plugins, it does not support pragmas or
keeps a symbol table. This means that, for some cases, it is not possible to decide whether a given rule
can be soundly applied. The last two disadvantages are shared with TXL. DMS is a powerful, industrial
transformation tool that is not free and there is not too much information of how it works internally; its
overall open documentation is scarce. Since it transforms programs by applying rules until a fix point is
reached, the rules should be carefully defined to ensure that they do not produce loops in the rewriting
stage. Finally, Rascal is still in alpha state and only available as binary, and the source code is not freely
and immediately accessible.
CodeBoost [2], built on top of Stratego-XT, performs domain-specific optimizations to C++ code
following an approach similar in spirit to our proposal. User-defined rules specify domain-specific optimizations; code annotations are used as preconditions and inserted as postconditions during the rewriting
process. However, it is a mostly abandoned project that, additionally, mixes C++, the Stratego-XT language, and their rule language. All together, this makes it to have a steep learning curve. Concept-based
frameworks such as Simplicissimus [21] transform C++ based on user-provided algebraic properties.
The rule application strategy can be guided by the cost of the resulting operation. This cost is defined
at the expression level (and not at the statement level), which makes its applicability limited. Besides,
their cost is defined using “arbiters” that do not have a global view of the transformation process, which
makes it possible to become trapped in local minima (Sec. 3.4.2).
Handel-C [6] performs program transformations to optimize parallelism in its compilation into a
FPGA. It is however focused on a subset of C enriched with extensions to express synchronicity, and
therefore some of its assumptions are not valid in more general settings.

38

Towards a Semantics-Aware Code Transformation Toolchain for Heterogeneous Systems

Other systems lay between both approaches. They use a high-level (declarative) language with some
syntactical / semantic restrictions that is compiled down to a lower level formalism [1, 10]. While
successful for their goals, they cannot directly tackle the problem of adapting existing code.
Most compilers have an internal phase to perform code transformation, commonly at the IR level.
Among the well-known open-source compilers, CLang / LLVM probably has the better designed libraries
/ APIs to perform program manipulation. However, they were designed for compilation instead of for
source-to-source program transformation. We tried using them but found that they are neither easy to
use nor effective in many situations. Moreover, the design documents warn that the interface can not
be assumed to be stable. Additionally, code transformation routines had to be coded in C++, which
made these routines verbose and full of low-level details, and writing them error-prone. Compiling
rules to C++ is of course an option, but the conceptual distance between the rules and the (unstable)
code manipulation API was quite large. That pointed to a difficult compilation stage that would need
considerable maintenance. Even in that case, the whole CLang project would have to be recompiled
after introducing new rules, which would make project development and testing cumbersome, and would
make adding user-defined rules complicated.

3

Source-to-Source Transformations

The code transformation tool has two main components: a parser that reads the input program and the
transformation rules and builds an AST using Haskell data types and translates the rules into Haskell for
faster execution, and an engine that performs source-to-source C code transformation using these rules.
The transformation rules contain patterns that have to syntactically match input code and describe
the skeleton of the code to generate. They can specify, if necessary, conditions to ensure that their application is sound. These conditions are checked using a combination of static analysis and user-provided
annotations (pragmas) in the source code with which the programmer provides additional information.
The annotations can capture properties at two different levels: high-level properties that describe algorithmic structures and low-level properties that describe details of the procedural code. The decision of
whether to apply a given rule depends on two main factors:
• Its application must be sound. This can be checked with the AST in simple cases. Otherwise,
whether a rule is applicable or not can be decided based on information inferred from annotations
in the source code. These annotations may come from external tools, such as static analyzers, or
be provided by a programmer.
• The transformation should (eventually) improve some efficiency metric, which is far from trivial.
An interactive mode that leaves this decision to a final user is available. While this is useful in many
cases, including debugging, it is clearly not scalable and deciding the best rule is often difficult.
As a solution, we are working on a machine learning-based oracle [24] that decides which rule to
apply based on estimations of the expected performance of rule application chains.
We present now the code annotations and the rule language. We will close this section with a description of the interaction between the transformation tool and external oracles.

3.1 High-Level Annotations
Annotations describing semantic features of the code make it possible to capture algorithmic skeletons
at a higher level of abstraction and, at the same time, to express properties of the underlying code.

S. Tamarit, J. Mariño, G. Vigueras & M. Carro

39

#pragma polca scanl F INI v w
#pragma
#pragma
#pragma
#pragma
#pragma
#pragma

stml
stml
stml
stml
stml
stml

reads output(INI)
reads v in {0}
reads w in {0}
writes w in {1}
pure F
iteration_space 0 length(v)

#pragma polca zipWith F v w z
#pragma
#pragma
#pragma
#pragma
#pragma
#pragma
#pragma
#pragma

stml
stml
stml
stml
stml
stml
stml
stml

reads v in {0}
reads w in {0}
writes z in {0}
same_length v w
same_length v z
pure F
iteration_space 0 length(v)
iteration_independent

#pragma polca map F v w
#pragma
#pragma
#pragma
#pragma
#pragma
#pragma

stml
stml
stml
stml
stml
stml

reads v in {0}
writes w in {0}
same_length v w
pure F
iteration_space 0 length(v)
iteration_independent

#pragma polca fold F INI v a
#pragma
#pragma
#pragma
#pragma
#pragma

stml
stml
stml
stml
stml

reads v in {0}
reads output(INI)
writes a
pure F
iteration_space 0 length(v)

Table 1: Annotations used in the POLCA project and their translation into STML annotations.
Our annotations follow a functional programming style. For instance, for loops expressing a mapping
between an input and an output array are annotated with a map pragma such as #pragma polca map
F v w. This annotation would indicate that the loop traverses the input array v and applies function F to
each element in v giving as result the array w. For the annotation to be correct, we assume that F is pure,
that v and w have the same length, and that every element in w is computed only from the corresponding
element in v. As a design decision, we do not check for these properties, but we expect them to hold.1
The top boxes of the frames in Table 1 list some high-level annotations. For illustrative purposes,
Fig. 3 shows an annotated version of the code in Fig. 1. The listing shows how the algorithmic skeletons
are parametric and their functional parameters are obtained from blocks of C code by specifying their
formal inputs and outputs.
1 However,

if some available analysis infers information contradicting any of these assumptions, we warn the user.

Towards a Semantics-Aware Code Transformation Toolchain for Heterogeneous Systems

40

float c[N], v[N], a, b;
#pragma polca map BODY1 v c
for(int i=0;i<N;i++)
#pragma polca def BODY1
#pragma polca input v[i]
#pragma polca output c[i]
c[i] = a*v[i];

#pragma polca zipWith BODY2 v c c
for(int i=0;i<N;i++)
#pragma polca def BODY2
#pragma polca input v[i]
#pragma polca input c[i]
#pragma polca output c[i]
c[i] += b*v[i];

Figure 3: Annotations for the code in Fig. 1.
Listing 1: BNF grammar for STML.
<code_prop_list> ::= "#pragma stml" <code_prop> |
"#pragma stml" <code_prop> <code_prop_list>
<code_prop> ::= <loop_prop> | <exp_prop> <exp> | [<op>] <op_prop> <op> |
"write("<exp>") =" <location_list> |
"same_length" <exp> <exp> | "output("<exp>")" |
<mem_access> <exp> ["in" <offset_list>]
<loop_prop> ::= "iteration_independent" |
"iteration_space" <parameter> <parameter>
<exp_prop>
::= "appears" | "pure" | "is_identity"
<op_prop>
::= "commutative" | "associative" | "distributes_over"
<mem_access> ::= "writes" | "reads" | "rw"
<location_list> ::= "{" <c_location> {"," <c_location>} "}"
<offset_list> ::= "{" <INT> {"," <INT>} "}"
<exp>
::= <C_EXP> | <C_VAR> | <polca_var_id>
<op>
::= <C_OP> | <C_VAR> | <polca_var_id>
<c_location> ::= <C_VAR> | <C_VAR>("["<C_EXP>"]")+
<parameter> ::= <c_location> | <polca_var_id> | <INT>

3.2 STML Properties
The transformation tool requires that some low-level, language-dependent properties hold to ensure that
transformations are sound. While some of these properties can be inferred from a high-level annotation,
some of them can go beyond what can be expressed in the high-level functional specifications. For
example, a purely functional semantics featuring referential transparency cannot capture some aspects of
imperative languages such as destructive assignment or aliasing. In our framework, these properties can
be expressed in a language we have termed STML (from Semantic Transformation Meta-Language) that
can be used both in the code annotations and in the conditions of the transformation rules.
3.2.1

Syntax and Semantics of STML Annotations

Listing 1 shows the grammar for STML annotations. An intuitive explanation of its semantics follows.
• <code_prop> refers to code properties expressed through STML annotations.

S. Tamarit, J. Mariño, G. Vigueras & M. Carro

41

• [<exp>] <exp_prop> <exp>: <exp_prop> denotes properties about code expressions of the
statement immediately below the annotation. Some examples are:
– appears <exp>: there is at least one occurrence of <exp> in the statement below.
– pure <exp>: expression <exp> is pure, i.e. it has neither side effects nor writes on any
memory location.
– is_identity <exp>: <exp> is an identity element. High-level annotations that define the
group or field in which <exp> is the identity element must have appeared before.
• [<op>] <op_prop> <op>: <op_prop> is an operator property (maybe binary). Some examples are:
– commutative <op>: <op> has the commutative property: if <op> = f , then ∀x, y. f (x, y) =
f (y, x).
– associative <op>: <op> has the associative property: if <op> = f , then ∀x, y, z.
f ( f (x, y), z) = f (x, f (y, z)).
– <op> distributes_over <op>: The first operator distributes over the second operator:
if the operators are f and g, then ∀x, y, z. g( f (x, y), z) = f (g(x, z), g(y, z)).
• "write("<exp>")="<location_list>: the list of memory locations written on by expression
<exp> is <location_list>, a list of variables (scalar or array type) in the C code. For example,
write(c = a + 3)= {c} and write(c[i++] = a + 3)= {c[i], i}
• <mem_access> <exp> ["in"<offset_list>]: <mem_access> states properties about the
memory accesses made by the statement(s) that immediately follow the expression <exp>. When
<exp> is an array, "in"<offset_list> can state the list of positions accessed for reading from
or writing to (depending on <mem_access>) the array. Some examples are:
– writes <exp>: the set of statements associated to the annotation writing into a location
identified by <exp>.
– writes <exp> "in"<offset_list>: this annotation is similar to the previous one, but
for non-scalar variables within loops. It specifies that for each i-th iteration of the loop, an
array identified by <exp> is written to in the locations whose offset with respect to the index
of the loop is contained in <offset_list>. For example,
#pragma stml writes c in {0}
for (i = 0; i < N; i++)
c[i] = i*2;

#pragma stml writes c in {-1,0}
for (i = 1; i < N; i++){
c[i-1] = i;
c[i] = c[i-1] * 2;}

– reads <exp>: the set of statements associated with the annotation read from location
<exp>.
– reads <exp> "in"<offset_list>t: similar to writes <exp> "in"<offset_list>
but for reading instead of writing. An example follows:
#pragma stml reads c in {0}
for (i = 0; i < N; i++)
a += c[i];

#pragma stml reads c in {-1,0,+1}
for (i = 1; i < N - 1; i++)
a += c[i-1]+c[i+1]-2*c[i];

Towards a Semantics-Aware Code Transformation Toolchain for Heterogeneous Systems

42

– rw <exp>: the set of statements associated to the STML annotation reads and writes from /
to location <exp>.
– rw <exp> "in"<offset_list>: similar to writes <exp> "in"<offset_list> but
for reading or writing.
• <loop_prop>: this term represents annotations related with loop properties:
– "iteration_space"<parameter> <parameter>: this annotation states the iteration
space limits of the for loop associated with the annotation. An example would be:
#pragma stml iteration_space 0 N-1
for (i = 0; i < N; i++)
c[i] = i*2;

– "iteration_independent": this annotation is used to state that there is no loop-carried
dependencies in the body of the loop associated to this annotation.
• "same_length"<exp> <exp>: the two C arrays given as parameters have the same length.
• "output("<exp>")": <exp> is the output of a block of code.
3.2.2

Translation from High-Level to STML Annotations

As mentioned before, annotated code is assumed to follow the semantics given by the annotations. Using
this interpretation, lower-level STML properties can be inferred for annotated code and used to decide
which transformations are applicable. For example, let us consider the loop annotated with map BODY1
v c in Fig. 3. In this context the assumption is that:
• BODY1 behaves as if it had no side effects. It may read and write from/to a global variable, but it
should behave as if this variable did not implement a state for BODY1. For example, it may always
write to a global variable and then read from it, and the behavior of other code should not depend
on the contents of this variable.
• v and c are arrays of the same size.
• For every element of c, the element in the i-th position is computed by applying BODY1 to the
element in the i-th position of v.
• The applications of BODY1 are not assumed to be done in any particular order: they can go from
v[0] upwards to v[length(v)-1] or in the opposite direction. Therefore, all applications of
BODY1 should be independent from each other.
The STML properties inferred from some high-level annotations are shown in Table 1. Focusing on
the translation of map, the STML annotations mean that:
• Iteration i-th reads from v in the position i-th (it actually reads from the set of positions {i + 0-th},
since the set of offsets it reads from is {0}).
• Iteration i-th writes on w in the position i-th.
• v and w have the same length.
• F behaves as if it did not have side effects.
• F is applied to v and w in the indexes ranging from 0 to length(v).
Table 1 shows the STML properties inferred from other high-level annotations (explained more in
depth in [20]). Fig. 5 shows the translation of the code in Fig. 3 into STML. All rules used in the
transformation in Fig. 1 are shown in Table 2, and the conditions they need are described in Table 3.

S. Tamarit, J. Mariño, G. Vigueras & M. Carro

43

join_assignments {
pattern: {
cstmts(s1);
cexpr(v) = cexpr(e1);
cstmts(s2);
cexpr(v) = cexpr(e2);
cstmts(s3);
}
condition: {
no_write(cstmts(s2), {cexpr(v),cexpr(e1)});
no_read(cstmts(s2),{cexpr(v)});
pure(cexpr(e1));
pure(cexpr(v));
}
generate: {
cstmts(s1);
cstmts(s2);
cexpr(v) = subs(cexpr(e2),cexpr(v), cexpr(e1));
cstmts(s3);
}
}

Figure 4: The STML rule J OINA SSIGNMENTS in C-like syntax.

float c[N], v[N], a, b;
#pragma polca map BODY1 v c
#pragma stml reads v in {0}
#pragma stml writes c in {0}
#pragma stml same_length v c
#pragma stml pure BODY1
#pragma stml iteration_space 0
length(v)
#pragma stml iteration_independent
for(int i = 0; i < N; i++)
#pragma polca def BODY1
#pragma polca input v[i]
#pragma polca output c[i]
c[i] = a*v[i];

#pragma polca zipWith BODY2 v c c
#pragma stml reads v in {0}
#pragma stml reads c in {0}
#pragma stml writes c in {0}
#pragma stml same_length v c
#pragma stml pure BODY2
#pragma stml iteration_space 0
length(v)
#pragma stml iteration_independent
for(int i = 0; i < N; i++)
#pragma polca def BODY2
#pragma polca input v[i]
#pragma polca input c[i]
#pragma polca output c[i]
c[i] += b*v[i];

Figure 5: Translation of high-level annotations in Fig. 3 into STML.

44

Towards a Semantics-Aware Code Transformation Toolchain for Heterogeneous Systems

for(l=eini ;rel(l, eend );mod(l)) {s1 }
⇒
for(l=eini ;rel(l, eend );mod(l)) {s2 }

for(l=eini ;rel(l, eend );mod(l)) {s1 ;s2 }
<

67 s1
when rel pure, (s1 ;s2 ) →
67 {l, eini , eend }, writes(mod(l)) ⊆ {l}, s1 →
67
s2 , s2 →
67
s1 , s2 →
−a[l]

−a[l]

a[l]

(F OR -L OOP F USION )
l += e; ⇒ l = l + e;
when l pure
s1 ; l = e1 ; s2 ; l = e2 ; s3 ; ⇒ s1 ; s2 ; l = e2 [e1 /l]; s3 ;
when l, e1 pure, s2 →
67 {l, e1 }, s2 6←[ l, s2 →
67 e1

f (g(e1 , e3 ), g(e2 , e3 )) ⇒ g( f (e1 , e2 ), e3 )
when e1 , e2 , e3 pure, g distributes over f

(AUG A DDITIONA SSIGN )
(J OINA SSIGNMENTS )
(U NDO D ISTRIBUTE )

for (e1 ;e2 ;e3 ){sb } ⇒ l = einv ; for (e1 ;e2 ;e3 ){sb [l/einv ])}
when l fresh, einv occurs in sb , einv pure, {sb , e3 , e2 } →
67 einv
(L OOP I NV C ODE M OTION )

Table 2: Source code transformations used in the example of Fig. 1.
3.2.3

External Tools

Besides the properties provided by the user, external tools can automatically infer additional properties,
thereby relieving users from writing many annotations to capture low-level details. These properties can
be made available to the transformation tool by writing them as STML annotations. We are currently
using Cetus [9] to automatically produce STML annotations. Cetus is a compiler framework, written in
Java, to implement source-to-source transformations. We have modified it to add some new analyses
and to output the properties it infers as STML pragmas annotating the input code. If the annotations
automatically inferred by external tools contradict those provided by the user, the properties provided by
the user are preferred to those deduced from external tools, but a warning is issued nonetheless.

3.3 Rules in STML
Let us see one example: Fig. 4 shows the STML version of rule J OINA SSIGNMENTS. Rules can be applied
when the code being transformed matches the pattern section and fulfills the condition section.
When the rule is activated, code is generated according to the template in the generate section, where
expressions matched in the pattern are replaced in the generated code. In this case one assignment
is removed by propagating the expression in its right hand side (RHS).
STML uses tagged meta-variables to match components of the initial code and specify which kind of
component is matched. For example, a meta-variable v can be tagged as cexpr(v) to denote that it can
only match an expression, cstmt(v) for a statement, or cstmts(v) for a sequence of statements. In
Fig. 4, s1, s2 and s3 should be (sequences of) statements, and e1, e2 and v are expressions.
Additional conditions and primitives (Tables 4 and 5) help write descriptive rules that can at the same
time be sound. In these tables, E represents an expression, S represents a statement and [S] represents a
sequence of statements. The function bin oper(Eop,El ,Er ) matches or generates a binary operation
(El Eop Er ) and can be used in the sections pattern and generate. The section generate can
also state, using #pragmas, new properties that hold in the resulting code.

S. Tamarit, J. Mariño, G. Vigueras & M. Carro
s→
67 l
s 6←[ l
s1 →
67 s2
s1 6←[ s2
s1 →
67
s2
−a[l]

45

statements s do not write into location l: l ∈
/ writes(s)
statements s do not read the value in location l
statements s1 do not write into any location read by s2
statements s1 do not read from any location written by s2
same predicate as the previous one but not taking into account locations referred through arrays

<

s1 →
67 s2

statements s1 do not write into any previous location corresponding to an index
array read by s2
e pure
expression e is pure, i.e. does not have side effects nor writes any memory
locations
writes(s)
set of locations written by statements s.
g distributes over f ∀x, y, z. g( f (x, y), z) ≈ f (g(x, z), g(y, z))
l fresh
l is the location of a fresh identifier, i.e. does not clash with existing identifiers
if introduced in a given program state
a[l]

Table 3: Predicates used to express conditions for the application transformation rules in Table 2.

3.4 Rule Selection
In most cases, several (often many) rules can be safely applied at multiple code points in every step of
the rewriting process. Deciding which rule has to be fired should be ultimately decided based on whether
that rule contributes to an eventual increase in performance. As mentioned before, we currently provide
two ways to perform rule selection: a human-driven one and an interface to communicate with external
tools.
3.4.1

Interactive Rule Selection

An interface to make interactive transformations possible is available: the user is presented with the
rules that can be applied at some point together with the piece of code before and after applying some
selected rule (using auxiliary programs, such as [26], to clearly show the differences). This is useful to
refine/debug rules or to perform general-purpose refactoring, which may or not be related to improving
performance or adapting code to a given platform.
3.4.2

Oracle-Based Rule Selection

In our experience, manual rule selection is very fine-grained and in general not scalable, and using it is
not realistic even for medium-sized programs. Therefore, mechanizing as much as possible this process
is a must, keeping in mind that our goal is that the final code has to improve the original code. A
straightforward possibility is to select at each step the rule that improves more some metric. However,
this may make the search to be trapped in local minima. In our experience, it is often necessary to apply
transformations that temporarily reduce the quality of the code because they enable the application of
further transformations.
A possibility to work around this problem is to explore a bounded neighborhood. The size of the
bounded region needs to be decided, since taking too few steps would not make it possible to leave a
local minimum. Given that in our experience the number of rules that can be applied in most states is
high (typically in the order of the tens), increasing the diameter of the boundary to be explored can cause

46

Towards a Semantics-Aware Code Transformation Toolchain for Heterogeneous Systems

Function
no write((S|[S]|E)1, (S|[S]|E)2)
no write except arrays
((S|[S]|E)1,(S|[S]|E)2,E)
no write prev arrays
((S|[S]|E)1 (S|[S]|E)2, E)
no read((S|[S]|E)1, (S|[S]|E)2)
pure((S|[S]|E))
writes((S|[S]|E))
distributes over(E1,E2 )
occurs in(E,(S|[S]|E))
fresh var(E)
is identity(E)
is assignment(E)
is subseteq(E1,E2 )

Description
True if (S|[S]|E)1 does not write in any location
read by (S|[S]|E)2.
As the previous condition, but not taking arrays accessed using E into account.
True if no array writes indexed using E in
(S|[S]|E)1 access previous locations to array
reads indexed using E in (S|[S]|E)2.
True if (S|[S]|E)1 does not read in any location
written by (S|[S]|E)2.
True if (S|[S]|E) does not write in any location.
Locations written by (S|[S]|E).
True if operation E1 distributes over operation E2 .
True if expression E occurs in (S|[S]|E).
Indicates that E should be a new variable.
True if E is the identity.
True if E is an assignment.
True if E1 ⊆ E2

Table 4: Rule language functions for the condition section of a rule.
Function/Construction
subs((S|[S]|E),Ef,Et )
if then:{Econd ; (S|[S]|E);}
if then else:{Econd ;
(S|[S]|E)t;(S|[S]|E)e;}
gen list: {[(S|[S]|E)];}

Description
Replace each occurrence of Ef in (S|[S]|E) for Et .
If Econd is true, then generate (S|[S]|E).
If Econd is true, then generate (S|[S]|E)t
else generate (S|[S]|E)e.
Each element in [(S|[S]|E)] produces a different rule
consequent.

Table 5: Rule language constructions and functions for generate rule section.
an exponential explosion in the number of states to be evaluated. This would happen even considering
some improvements such as partial order reduction for pairs of commutative rules.
Therefore, we need a mechanism that can make local decisions taking into account global strategies
— i.e., a procedure able to select a rule under the knowledge that it is part of a sequence of rule applications that improves code performance for a given platform. We are exploring the use of machine learning
techniques based on reinforcement learning [24]. From the point of view of the transformation engine,
the selection tool works as an oracle that, given a code configuration and a set of applicable rules, returns
which rule should be applied. We will describe now an abstract interface to an external rule selector,
which can be applied not only to the current oracle, but to other similar external oracles.
The interface of the transformation tool (Fig. 6) is composed by functions AppRules and Trans.
Function AppRules determines the possible transformations applicable to a given code and returns, for
a given input Code, a set of tuples containing each a rule name Rule and the code position Pos where it
can be applied (e.g., the identifier of a node in the AST). Function Trans applies rule Rule to code Codei

S. Tamarit, J. Mariño, G. Vigueras & M. Carro
AppRules(Code) → {(Rule, Pos)}
Trans(Codei , Rule, Pos) → Codeo
Figure 6: Functions provided by the transformation tool.

47
SelectRule({(Codei , {Rulei })}) → (Codeo , Ruleo )
IsFinal(Code) → Boolean
Figure 7: Functions provided by the oracle.

Header
NewCode(Codei , {Rulei }) → (Codeo , Ruleo )
Definition
NewCode(c, rls) = SelectRule({(c′ , {r′ | (r′ , ) ∈ AppRules(c′ )})
| c′ ∈ {Trans(c, r, p) | (r, p) ∈ AppRules(c), r ∈ rls} })

Complete derivation
NewCode(c0 , AllRules) →∗ (cn , rn )
when IsFinal(cn ) and ∀i, 0 < i < n.
(ci , ri ) = NewCode(ci−1 , {ri−1 })
when ¬IsFinal(ci )

Figure 8: Interaction between the transformation and the oracle interface.
at position Pos and returns the resulting code Codeo after applying the transformation.
The API from the external tool (Fig. 7) includes operations to decide which rule has to be applied
and whether the search should stop. Function SelectRule receives a set of safe possibilities, each of them
composed of a code fragment and a set of rules that can be applied to it, and returns one of the input code
fragments and the rule that should be applied to it. Function IsFinal is used to know whether a given
code Code is considered ready for translation or not.
The function that defines the interaction between the transformation engine and the external oracle is
NewCode (Fig. 8), which receives an initial Codei and a set of rules and returns (a) Codeo which results
from applying one of the rules from {Rulei } to Codei , and (b) Ruleo that should be applied in the next
transformation step, i.e., the next time NewCode is invoked with Codeo . The rationale is that the first
time NewCode is called, it receives all the applicable rules as candidates to be applied, but after this
first application {Rulei } is always a singleton. NewCode is called repeatedly until the transformation
generates a code for which IsFinal returns true.
This approach makes it unnecessary for the external oracle to consider code positions where a transformation can be applied, since that choice is implicit in the selection of a candidate code between all
possible code versions obtained using a single input rule. Furthermore, by selecting the next rule to be
applied, it takes the control of the next step of the transformation. The key here is the function SelectRule:
given inputs Codei and Rulei , SelectRule selects a resulting code between all the codes that can be generated from Codei using Rulei . The size of the set received by function SelectRule corresponds to the
total number of positions where Rulei can be applied. In this way, SelectRule is implicitly selecting a
position.

4

Producing Code for Heterogeneous Systems

In the second phase of the tool (Fig. 2), code for a given platform is produced starting from the result
of the transformation process. The destination platform of a fragment of code can be specified using
annotations that make this explicit. This information helps the tool decide what transformations should
be applied and when the code is ready for translation.
The translation to code for a given architecture is in most cases straightforward as it needs only
to introduce the “idioms” necessary for the architecture or to perform a syntactical translation. As a
consequence, there is no search or decision process: for each input code given to the translation, there is
only one output code that is obtained via predefined transformations or glue code injection.

48

Towards a Semantics-Aware Code Transformation Toolchain for Heterogeneous Systems

Some translations need specific information: for instance, knowing if a statement is performing I/O
is necessary when translating to MPI, because executing this operation might need to be done in a single
thread. It is often the case that this can be deduced by syntactical inspection, but in other cases (e.g., if
the operation is part of a library function) it may need explicit annotations.

5

Implementation Notes

The transformation phase, which obtains C code that could be easily translated into the source language
for the destination platform, is a key part of the tool. As a large part of the system was experimental
(including the definition of the language, the properties, the generation of the final code, and the search /
rule selection procedures), we needed a flexible and expressive implementation platform. We decided to
use a declarative language and implement the tool in Haskell. Parsing the input code is done by means
of the Language.C [12] library which returns the AST as a data structure that is easy to manipulate.
In particular, we used the Haskell facilities to deal with generic data structures through the Scrap Your
Boilerplate (SYB) library [16]. This allows us to easily extract information from the AST or modify it
with a generic traversal of the whole structure.
The rules themselves are written in a subset of C and are parsed using Language.C. After reading
these rules in, they are automatically compiled into Haskell code (contained in the file Rules.hs —see
Fig. 2) that performs the traversal and (when applicable) the transformation of the AST. This module is
loaded with the rest of the tool, therefore avoiding the extra overhead of interpreting the rules.
When it comes to rule compilation, STML rules can be divided into two classes: those that operate at
the expression level and those that can manipulate both expressions and sequences of statements. In the
latter case, sequences of statements (cstmts) of an unknown size have to be considered: for example,
in Fig. 4, s1, s2, and s3 can be sequences of any number of statements (including the empty sequence),
and the rule has to try all the possibilities to determine if there is a match that meets the rule conditions.
For this, Haskell code that explicitly performs an AST traversal needs to be generated. Expressions, on
the other hand, are syntactically bound and the translation of the rule is much easier.
When generating Haskell code, the rule sections (pattern, condition, generate, assert)
generate the corresponding LHS’s, guards, and RHS’s of a Haskell function. If the conditions to apply
a rule are met, the result is returned in a triplet (rule_name, old_code, new_code) where the two
last components are, respectively, the matched and transformed sections of the AST. Note that new_code
may contain new properties if the generate section of the rule defines them.
The tool is divided into four main modules:
• Main.hs implements the main workflow of the tool: it calls the parser on the input C code to
build the AST, links the pragmas to the AST, executes the transformation sequence (interactively
or automatically) and outputs the transformed code.
• PragmaLib.hs reads pragmas and links them to their corresponding node in the AST. It also
restores or injects pragmas in the transformed code.
• Rul2Has.hs translates STML rules (stored in an external file) into Haskell functions that actually
perform the AST manipulation. It also reads and loads STML rules as an AST and generates the
corresponding Haskell code in the Rules.hs file.
• RulesLib.hs contains supporting code used by Rules.hs to identify whether some STML
rule is or not applicable (e.g., there is matching code, the preconditions hold, etc.) and to execute
the implementation of the rule (including AST traversal, transformation, . . . ).

S. Tamarit, J. Mariño, G. Vigueras & M. Carro

6

49

Conclusion

We have presented a transformation toolchain that uses semantic information, in the form of user- or
machine-provided annotations, to produce code for different platforms. It has two clearly separated
phases: a source-to-source transformation that generates code with the style appropriate for the destination architecture and a translation from that code to the one used in the specific platform.
We have focused until now in the initial phase, which included the specification of a DSL (STML) to
define rules and code properties, a translator from this language into Haskell, a complete engine to work
with these rules, and an interface to interact with external oracles (such as a reinforcement learning tool
that we are developing) to guide the transformation.
The translation phase is still in a preliminary stage. However, and while it is able to translate some
input code, it needs to be improved in order to support a wider range of programs. We have compared,
using several metrics, the code obtained using our tool and the corresponding initial code and the results
are encouraging.
As said before, we have started the development of external (automated) oracles to guide the transformation process. Initial results using an oracle based on reinforcement (machine) learning [24] are
very encouraging. The possibility of using other techniques such as partial order reduction to prune the
search space is still open to investigation.
We plan to improve the usability of the STML language and continue modifying Cetus to automatically obtain more advanced / specific properties, and we are integrating profiling techniques in the process
to make evaluating the whole transformation system and giving feedback on it easier. Simultaneously,
we are investigating other analysis tools that can be used to derive more precise properties. Many of these
properties are related to data dependencies and pointer behavior. We are considering, on one hand, tools
like PLuTo [5] and PET [23] (two polytope model-based analysis tools) or the dependency analyzers for
the Clang / LLVM compiler. However, since they fall short to derive dependencies (e.g., alias analysis)
in code with pointers, we are also considering tools based on separation logic [19] such as VeriFast [13]
that can reason on dynamically-allocated mutable structures.

References
[1] Christiaan Baaij, Matthijs Kooijman, Jan Kuper, Arjan Boeijink & Marco Gerards (2010): Cλ aSH: Structural
Descriptions of Synchronous Hardware Using Haskell. In Sebastián López, editor: DSD, IEEE, pp. 714–721,
doi:10.1109/DSD.2010.21.
[2] Otto Skrove Bagge, Karl Trygve Kalleberg, Eelco Visser & Magne Haveraaen (2003): Design of the
CodeBoost Transformation System for Domain-Specific Optimisation of C++ Programs. In: Third International Workshop on Source Code Analysis and Manipulation (SCAM 2003), IEEE, pp. 65–75,
doi:10.1109/SCAM.2003.1238032.
[3] Ira D Baxter, Christopher Pidgeon & Michael Mehlich (2004): DMS R : Program transformations for practical scalable software evolution. In: Proceedings of the 26th International Conference on Software Engineering, IEEE Computer Society, pp. 625–634, doi:10.1109/ICSE.2004.1317484.
[4] Maarten Boekhold, Ireneusz Karkowski & Henk Corporaal (1999): Transforming and parallelizing ANSI
C programs using pattern recognition. In: High-Performance Computing and Networking, Springer, pp.
673–682, doi:10.1007/BFb0100628.
[5] Uday Bondhugula, Albert Hartono, J. Ramanujam & P. Sadayappan (2008): A Practical Automatic Polyhedral Parallelizer and Locality Optimizer. SIGPLAN Not. 43(6), pp. 101–113, doi:10.1145/1379022.1375595.

50

Towards a Semantics-Aware Code Transformation Toolchain for Heterogeneous Systems

[6] Ashley Brown, Wayne Luk & Paul Kelly (2005):
Optimising Transformations for
Hardware Compilation.
Technical Report, Imperial College London.
Available at
http://www3.ic.ac.uk/pls/portallive/docs/1/18619721.PDF.
[7] James R Cordy (2006): The TXL source transformation language. Science of Computer Programming 61(3),
pp. 190–210, doi:10.1016/j.scico.2006.04.002.
[8] Anthony Danalis, Gabriel Marin, Collin McCurdy, Jeremy S Meredith, Philip C Roth, Kyle Spafford, Vinod
Tipparaju & Jeffrey S Vetter (2010): The Scalable Heterogeneous Computing (SHOC) Benchmark Suite. In:
Proceedings of the 3rd Workshop on General-Purpose Computation on Graphics Processing Units, ACM, pp.
63–74, doi:10.1145/1735688.1735702.
[9] Chirag Dave, Hansang Bae, Seung-Jai Min, Seyong Lee, Rudolf Eigenmann & Samuel P. Midkiff (2009):
Cetus: A Source-to-Source Compiler Infrastructure for Multicores. IEEE Computer 42(11), pp. 36–42,
doi:10.1109/MC.2009.385.
[10] Christophe Dubach, Perry Cheng, Rodric Rabbah, David F Bacon & Stephen J Fink (2012): Compiling a
high-level language for GPUs:(via language support for architectures and compilers). In: Proceedings of
the 33rd ACM SIGPLAN conference on Programming Language Design and Implementation, ACM, pp.
1–12, doi:10.1145/2345156.2254066.
[11] Franz Franchetti, Yevgen Voronenko & Markus Püschel (2006): FFT program generation for shared memory:
SMP and multicore. In: Proceedings of the ACM/IEEE SC2006 Conference on High Performance Networking and Computing, November 11-17, 2006, Tampa, FL, USA, p. 115, doi:10.1145/1188455.1188575.
[12] Benedikt Huber (2014): The Language.C Package.
https://hackage.haskell.org/package/language-c.
[13] Bart Jacobs, Jan Smans, Pieter Philippaerts, Frédéric Vogels, Willem Penninckx & Frank Piessens (2011):
VeriFast: A Powerful, Sound, Predictable, Fast Verifier for C and Java. In: Proceedings of the Third International Symposium on NASA Formal Methods, NFM 2011, Pasadena, CA, USA, April 18-20, 2011., pp.
41–55, doi:10.1007/978-3-642-20398-5 4.
[14] Jacquard Computing Inc. (2012): ROCCC 2.0 User’s Manual, revision 0.74 edition.
http://roccc.cs.ucr.edu/UserManual.pdf.

Available at

[15] Paul Klint, Tijs Van Der Storm & Jurgen Vinju (2009): Rascal: A domain specific language for source
code analysis and manipulation. In: Source Code Analysis and Manipulation, 2009. SCAM’09. Ninth IEEE
International Working Conference on, IEEE, pp. 168–177, doi:10.1109/SCAM.2009.28.
[16] Ralf Lammel, Simon Peyton Jones & Jose Pedro Magalhaes (2009):
https://hackage.haskell.org/package/syb.

The SYB Package.

[17] Olav Lindtjorn, Robert G Clapp, Oliver Pell, Haohuan Fu, Michael J Flynn & Oskar Mencer (2011): Beyond
Traditional Microprocessors for Geoscience High-Performance Computing Applications. IEEE Micro 31(2),
pp. 41–49, doi:10.1109/MM.2011.17.
[18] Maxeler Technologies (2016):
latency/maxcompilermpt/.

Max Compiler MPT.

https://www.maxeler.com/solutions/low-

[19] John C. Reynolds (2002): Separation Logic: A Logic for Shared Mutable Data Structures. In: LICS, IEEE
Computer Society, pp. 55–74, doi:10.1109/LICS.2002.1029817.
[20] Daniel Rubio, Colin W Glass, Jan Kuper & Robert de Groote (2015): Introducing and Exploiting Hierarchical Structural Information. In: IEEE International Conference on Cluster Computing (CLUSTER), 2015,
IEEE, pp. 777–784, doi:10.1109/CLUSTER.2015.133.
[21] Sibylle Schupp, Douglas Gregor, David Musser & Shin-Ming Liu (2002): Semantic and beInformation and Software Technology 44(13), pp. 797–810,
havioral library transformations.
doi:10.1016/S0950-5849(02)00122-2.
[22] Salvador Tamarit, Guillermo Vigueras, Manuel Carro & Julio Mariño (2015): A Haskell Implementation
of a Rule-Based Program Transformation for C Programs. In Enrico Pontelli & Tran Cao Son, editors:

S. Tamarit, J. Mariño, G. Vigueras & M. Carro

[23]

[24]

[25]

[26]

51

International Symposium on Practical Aspects of Declarative Languages, LNCS 9131, Springer-Verlag, pp.
105–114, doi:10.1007/978-3-319-19686-2 8.
Sven Verdoolaege & Tobias Grosser (2012): Polyhedral extraction tool. In: Second International
Workshop on Polyhedral Compilation Techniques (IMPACT’12), Paris, France, pp. –. Available at
http://impact.gforge.inria.fr/impact2012/workshop_IMPACT/verdoolaege.pdf.
Guillermo Vigueras, Manuel Carro, Salvador Tamarit & Julio Mariño (2016): Towards Automatic Learning of Heuristics for Mechanical Transformations of Procedural Code. In Alicia Villanueva, editor:
Proceedings of XIV Jornadas sobre Programación y Lenguajes (PROLE 2016), pp. 2–16. Available at
http://hdl.handle.net/11705/PROLE/2016/015.
Eelco Visser (2004): Program Transformation with Stratego/XT: Rules, Strategies, Tools, and Systems in
StrategoXT-0.9. In Christian Lengauer, Don Batory, Charles Consel & Martin Odersk, editors: DomainSpecific Program Generation, Lecture Notes in Computer Science 3016, Springer-Verlag, pp. 216–238,
doi:10.1007/978-3-540-25935-0 13.
Kai Willadsen (2016): Meld. http://meldmerge.org/. Retrieved on December 2016.

