Motivations for Concept-Based Optimizations
Traditional compilers typically simplify expressions via a set of built-in
optimizing rules whose correctness is generally justified by certain algebraic laws.
These optimizing rules, however, are hard-coded and only apply to expressions of
built-in types.
For example, a C++ compiler will simplify the integer addition
x + 0 via the optimizing rule i + 0 -> i
justified by the algebraic right identity law .
The same law also holds for the user-defined string operator+(x, y) in C++,
and that is, we can safely rewrite s + string() into s.
The C++ compiler, however, fails to conduct this rewriting,
because the compiler's optimizing rules are hard-coded
with specific built-in types,
neither allowing users to specify optimizing rules
nor automatically proving the validation of the right identity law for string
and applying this law to s + string().
Instead, to optimize s + string(), the compiler has to inline
the default constructor of the string class,
the string operator+(x, y), and
analyze the expanded code against the built-in optimizing rules,
which means significant amount of work.
A straightforward means to enable the compiler to apply the right identity law to
the string operator+(x, y) is supplying the compiler with this
rewrite rule s + string() -> s.
Obviously, directly encoding this rule in the compiler is not the standard course of
programming compilers.
A pre-processor or source-to-source translator may allow users to specify
rewrite rules and preprocess users' code via these customized rules.
This approach's limitations consist of:
1) users need to specify different rewrite rules
for different types, though all of these rewrite rules are instances of
one algebraic law such as the algebraic identity law;
2) this pre-processor or source-to-source translator hardly utilizes
the results of compilers' analyses and optimizations that
can reveal new facts for rewriting; for example,
in the sequence code string s; string t=string(); string l = s + t,
accessing the code's data flow graph reveals s + t == s + string(),
which in turn justifies applying the rewrite rule s + string() -> s.
A second approach is allowing users to specify generic algebraic laws, and declare the validation of applying these laws to certain expressions of specific types (both built-in and user-defined), and designating the compiler to accomplish the application. Because it is the compiler that performs the rewriting on expressions, this approach can be integrated with the compiler's analyses and optimizations.
Concept-Based Optimizations
Concept-Based Optimizations is essentially the above second approach. It exploits the principles and techniques of generic programming to build compiler optimizations generically, such that compiler optimizations apply not only to built-in types and operations, but to user-defined types and operations.
You can find more discussions on concept-based optimizations in the following paper:
- Xiaolng Tang and Jaakko Järvi. Concept-based optimization. In ACM SIGPLAN Symposium on Library-Centric Software Design (LCSD'07), October 2007.
The project group is Jaakko Järvi, Xiaolong Tang.
For further information, please contact jarvi@cs.tamu.edu.
Using Our Prototype for Concept-Based Optimizations
We already built a prototype that supports concept-based optimizations and the following describes how to use this prototype in detail. The prototype is built on Douglas Gregor's ConceptGCC (Douglas Gregor is from the Open Systems Laboratory in Indiana University) which implements the generic programming features in the forthcoming revision of C++, known as C++0X. The compiler ConceptGCC, built on GCC, implements a preliminary version of the concepts feature in C++0X. A detailed description on ConceptGCC can be found via this link: ConceptGCC. The remainder of this webpage describes how to check out the source code of this prototype, build the source code, install the just built compiler, and experience concept-based optimizations with it.
Obtaining the Source Code of the Prototype
Our prototype is available only as source code now. To retrieve the source code, you will need an installed Subversion client on your system. To checkout a latest copy of our prototype, use:
svn co https://svn.osl.iu.edu/svn/hlo/branches/optimization-with-axiom
Configure, Build, and Install the Source Code
Configuration, building and installation follow the same procedure for ConceptGCC. Please find it via this link: installing ConceptGCC.
Experiencing Algebraic Simplifications for User-defined Types
As an example, we show how to enable identity optimizations for user-defined types. Three steps are involved into this process:
Step 1: Specifying Algebraic Identity Law
Generic algebraic laws are specified via invariants defined in axioms of concepts. We use algebraic concepts to encode the generic laws. More discussions about algebraic concepts can be found in the following paper:
In our example, we encode the identity laws in the algebraic concept.
concept Monoid
: std::Semiregular, std::DefaultConstructible
{
requires std::Callable2;
requires std::SameType::result_type, T>;
T identity_element(Op, T);
axiom Identity(Op op, T x)
{
op(x, identity_element(op, x)) == x;
op(identity_element(op, x), x) == x;
}
}
Note that the two invariants in the axiom Identity are to be interpreted as generic right identity rewrite rules and left identity rule. A more complete definition for algebraic concepts can be found in this header file: algconcept.hpp.
Step 2: Declaring the identity law validation for user-defined types
The correctness of applying identity laws to specific types is established
by corresponding Monoid's concept maps
to these specific types. For example, to enable algebraic
laws for string, what users need is
defining this concept map:
concept_map Monoid< std::plus, std::string>{
std::string identity_element( std::string op, string x) {
return string("");
}
};
Step 3: Compiling with Concept-Based Optimizations
Our prototype uses the flag -fconcept-simplify
to turn on concept-based optimizations.
Note that, currently, to enable the proper running of
concept-based optimizations, these flags
-O2 and -fno-exceptions
must be specified as well.
To optimize the following code in the file string_add.cpp, use
this command:
conceptg++ -fno-exceptions -fconcept-simplify -O2 -o string_add.exe string_add.cpp
#include
#include
#include
#include "algconcept.hpp"
concept_map Monoid, std::string>{
std::string identity_element(std::plus op, std::string x) {
return std::string("");
}
};
inline std::string test1 ()
{
std::string x("");
std::string y("text");
return x + y;
}
int main(int argc, char* argv[])
{
std::string z = test1();
return 0;
}
To tell if concept-based optimizations work or not, you can supplement the compiling
command with the flag -fdump-tree-all and
check the output when issuing this command:
grep -n -A10 "Matching" *.axiommatch1
The output will be like the following snippet.
- Line 1032 tells a successful match with the expression
operator+(&x, &y); - Line 1059 tells a rewriting operations from
operator+(&x, &y) -> y; - Line 1061 tells the resulting expression after rewriting.
1032:Candidate Matching Statement:operator+ (&x, &y) [return slot optimization];
1033-
1034- Subject Pattern
1035-----------------begin----------------------
1036-The subject term is as follows:
1037-(1,1) [postion: (null) code call_expr type: 3a8dcb0 node 3c3d6f0 pck_fun_cell]
1038-(1,2) [postion: (null) code function_decl type: 3445620 node 3c38380 pck_code_cell]
1039-(1,3) [postion: (null) code array_ref type: 41c1f770 node 3c3d5d0 pck_ref_cell]
1040-(1,4) [postion: (null) code string_cst type: 3460bd0 node 2e96820 pck_const_cell]
1041-(1,5) [postion: (null) code integer_cst type: 41c16000 node 41c052d0 pck_const_cell]
1042-(1,6) [postion: (null) code integer_cst type: 41c16000 node 41c052d0 pck_const_cell]
--
1053:Checking Matching Succeed!
1054-The statement:x_2(D)
1055-
1056-The tree node: x_2(D)
1057-Founc cell: [postion: (null) code var_decl type: 3a8dd20 node 345bcb0 pck_var_cell]
1058-
1059-Changed into:y
1060-
1061-The whole statement at tage 1:*D.142756_1 = y;
1062-The statement used to bsi_replace is:__comp_ctor (D.142756_1, &y);
1063-
-fconcept-simplify .
Adobe Benchmark
We have done experiments with the Adobe Benchmark. The benchmark contains a suite of benchmark for C++ performance that are written by Chris Cox from Adobe. Amongst this suite, custom_types_algebraic_simplification.cpp aims for measuring C++ abstraction penalties regarding algebraic simplifications for user-defined types.
Please check the website C++ performance for the complete introduction on this benchmark. Here we only list some necessary files for reference.