Automatically unrolling and outputting for C/C++ code

Question

I'm doing an experiment and the first step is to unroll a loop (from C/C++) a dozen of times (ex: 10, 50, etc) and output the C/C++ unrolled code. Is there any tool that I can use to automatize such unrolling?

In other words, what I need is:

C/C++ source/loop --->> TOOL (Unroll by X) ---->  Unrolled C/C++ source/loop

Answer 1

Our source-to-source transformation engine, the DMS Software Reengineering Toolkit, with its C++17 front end can be used to do this.

DMS can accept explicit source-to-source transformation rules.

Individual rules are written as

rule rule_name(metavariables_with_syntax_categories)
:syntax_category->syntax_category
= left_hand_side_pattern_to_match 
-> right_hand_side_replacement_after_substitution

Below I provide an (untested) set that are pretty close to the mark. These are directly inspired by the classic compiler optimization for unrolling a loop.

The ... inside "..." that you see means "(C++ syntax for) ..."; these are " here are domain text metaquotes, not C++ string quotes. \foo inside "..." means metavariable foo, which represents a chunk (tree) of C++ code. \bar(...\,...) means "metafunction bar invoked on ..." Note the "metacommas" spelled \, and metaparentheses ( ) used to distinguish metafunctions from domain ("C++") syntax. See the link for more details on the syntax of such rules.

The unquoted patterns UNROLL and ReplaceIbyEXP define "metafunctions", which can be thought of as intentions to apply more tranformations.

Here UNROLL captures our notion that we want to repeat a block of code n times. There are two (effectively recursive) rules to implement this notion, one for the base case of "repeat zero times" producing an empty statement list, and the other generating the code block followed by repeating n-1 times. ReplaceIbyEXP then adjusts the index i used in the copied code block.

external pattern ReplaceIbyEXP(s:statements,i:IDENTIFIER,r:expression):statements;

pattern UNROLL_1(s:statements,i:IDENTIFIER,k:INT_LITERAL,c:INT_LITERAL)
  :statements->statements;

rule UNROLL_1(s:statements,i:IDENTIFIER,d:INT_LITERAL,c:INT_LITERAL)
  :statements->statements
  = UNROLL(s,i,d,c) -> ";" if c=="0";

rule UNROLL_N((s:statements,i:IDENTIFIER,d:INT_LITERAL,c:INT_LITERAL)
  :statements->statements
  = UNROLL(s,i,d,c)
  -> "\ReplaceIbyEXP\(\s\,\i\,(\i+\d)\)
      \UNROLL\(\s,\i,\add\(\d\,1\),\subtract\(\c\,1\))" if c!="1";

rule UNROLL_FOR_k(i:IDENTIFIER,s:statements,limit:INT_LITERAL)
  :statements->statements
  = "for (\i=0;\i<\limit;\i++) { \s }"
  -> "for (\i=0;\i<\limit;\i+=k) { \UNROLL(\s\,\i\,0,k) }"

This code has a variety of hiccups to address:

• It doesn't express the implementation of ReplaceIbyEXP; at present, that needs to be realized by calling DMS's procedural ("PARLANSE") part ("external") to do a tree walk and replace each instance of the matching identifier with the provided subexpression. In the procedural part these are already trees and simple "AST:EqualNode" and "AST:ReplaceSubtree" can be used to realize it. This is probably another 20 lines of PARLANSE code.

• It doesn't handle the case where the loop bound is not a multiple of k. That means there needs to be variants of UNROLL_FOR_k, one where the loop bound is a multiple (that's the one provided here) and the case where it isn't a multiple. Then one needs to generate an unrolled loop of k copies, followed by cleanup code of limit modulo k copies of the code. (Alternatively, one can use something like Duff's device [mentioned in a comment on OP's question] on the first or last block of copies).

• One might want to supply k from the "outside". That is easily implemented using another external pattern to fetch it.

Now, learning to use an engine like DMS is rather involved, partly you are dealing with C++ which is already extremely complicated, and partly because DMS's machinery has to be able to handle all the peccadillos that C++ throws up. [Clang will be equally hard to apply for the same reasons, but doesn't provide the pattern-driven transformation machinery].

So using DMS just to do this once is probably not a good use of your time. If you have to automate this repeatedly, or do something much more complex reliably on a big code base, then it makes sense. My two cents.