Partial evaluation/specialization with LLVM-gcc or gcc

Question

I am interestent in (partial) compile-time evaluation for c/c++ (not with template parameters like in c++). Lets consider the following case (taken from [1]):

double mypower(double x, int n) {
  int i;
  double ret = x;
  for (i = 1; i < n; i++) {
    ret *= x;
  }
  return ret;
}

Then you call this function somewhere in the code with:

mypower(x,3); // y varies all the time, 

Then the compiler could optimize this (e.g. loop unrolling). Some often used function I use could really benefit from that optimization (tested by the creating specialized function manually). The presentation [1] descibes a process where the function is searched and is replaced by a specialised version of the function. This seems to work. But it does not seem to be very universal, code needs to be written for the functions which should be replaced.

The presentation seems to be from 2008, i could not find anything substantial more information than in this source. So has anything improved since then? I would prefer some kind of automatism, which does the same for all function possibly controlled by attribute syntax (e.g. __attribute__(peval)...). Further I would like the same to work for object-oriented code, creating specialized classes for different objects ([2] seems to suggest that this is not possible).

Additionally, I would like this specialization not only work for constants found in code. I am thinking about a program compiled to LLVM IR (bytecode) could do the following:

1. Running the programm during an initialization phase in an interpreter, during that initialization phase the program could read some configuration from a file. After the initialization the interpreter is stopped.

2. Some variables (including member variables) are fixed from that point on. Extract these variables (e.g. marked by attribute during compilation).

3. Create specialized functions and classes. Clone these into the bytecode.

4. Run the JIT to create native machine code.

This is a lot I ask for and only few computation intensive programs would benifit from such a optimization. But some people must be working on that. I probably just don't know the right search terms to feed google.

Note: Please don't suggest template classes with non-type parameters or manual specialization, I already do that. I just would prefer the compiler doing the work for me.

Links:

[1] Presentation how to partial evaluate in LLVM

[2] Forum message about partial evaluation

Answer 1

This is largely in the arena of interprocedural optimizations. llvm has a few of them, in particular IP constant propagation which would only help if you used mypower(x, 3) at all of the call sites in a translation unit. What you describe is possible, but hasn't really been done yet. Improving the IPCP pass is what you'd want to look into doing - by having it clone and specialize a function at a particular call site. This could, if you have enough translation units, cause some pretty large code bloat though which is why people haven't really looked into doing it.

This would probably have some more use at the LTO level when you can look at all of the calls in a program.

Answer 2

You can do this using source-to-source transformations.

Our DMS Software Reengineering Toolkit could be used to implement this. DMS uses explicit language definitions to parse source code to ASTs, prettyprinting of ASTs back to source code, provides various kinds of symbol table, control/data flow capabilities, and provides transformation ability to enable one to build custom source-code transformers. DMS has many front ends for differenct languages including C and C++ with full preprocessors.

To accomplish your task with DMS, you'd use the C parser to parse all the code of your system (because you have to inspect all call sites for any partial specializations). You'd need to define a way to specify the partial evaluation you wish; one way, as you've suggested, is to write a function call with arguments bound-to constants, but you could generalize this to arguments bound-to arbitrary expressions. Such a specification can be parsed by DMS's pattern parser, which can process arbitrary lnaguage nonterminals, e.g., a function call :-} You need to park these specifications somewhere; perhaps as an additional external file, or as comments at or near the call sites in question.

With a parse of the partial-eval specification, you need to look up the function call name to determine the actual function of interest; it is somewhere in that stack of sources and the symbol table will make this easy to find. Given a call site with a specialization, the AST for the identified function can be replicated and arguments substituted; using probably only a small number of transformations but you have to watch out for capture of an argument by a lexical scope inside the function being specialized. Getting around that might require additional transformations. After gensymming a new name and shortened argument list for the specified function, you'd re-insert its AST near the original function definition site, modify the call site appropriately, and spit out the modified ASTs. Whether you wanted to add additional transforms to unroll loops for special cases, or whatever else interests you, is also practical.

DMS has been used carry out massive transformations on C and C++ code; this seems "technically" easy. There is the small matter of becoming familiar with a tool like DMS; there's a fair learning curve there.