Programming Techniques, Tools and Languages Group

Concept Based Optimization

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:

  1. Xiaolong 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:

Peter Gottschling and Walter E. Brown. Toward a more complete taxonomy of algebraic properties for numeric libraries. Technique Report N2650 08-0160, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, May 2008.

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.

  1. Line 1032 tells a successful match with the expression operator+(&x, &y);
  2. Line 1059 tells a rewriting operations from operator+(&x, &y) -> y;
  3. 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-
    
In the future, we will provide a convenient way to tell the effects of concept-based optimizations when compiling code with -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.

  1. custom_types.h

Upcoming Events




Share This Article




Headlines

About Us | Parasol Lab | Computer Science and Engineering | ©2010 Texas A&M University