## Loop unrolling

Today something a bit technical once again. Only suitable for people knowing something of ML etc.

In compilers, semantics and program analysis it’s sometimes handy or needed to transform loops into nested if’s. Perhaps for efficiency reasons, for precision of some invariant detection, or perhaps to know the meaning of a loop up to some defined iteration.

Unrolling a loop twice consists of the transformation from

`while(B) { C; }`

to the following nested if statements:

`if(B) { C; if (B) { C; while(B) { C; } } }`

Recently, I thought about how to do that (more or less) elegantly given an abstract syntax tree of the loop. Here my approach in Ocaml. First, we start with a simple language of only boolean expressions and some commands.

type bexp = Random and cmd = Skip |Assign |Seq of cmd list |If of bexp * cmd * cmd |While of bexp * cmd

We have a boolean expression Random and the usual commands cmd: Skip, Assignments, Sequences, If, and While constructs. Let’s define a simple loop:

`let loop1 = While(Random, Assign)`

Which corresponds to something like `while(Random) { Assign; }`. Obviously, the commands and boolean expressions are not really useful, but that’s just for demonstration purposes — it could easily be replaced with real AST constructs.

Next, let’s write out how we would like to have the first unrolling look like:

`let unrolled1 = If(Random, Seq [Assign; loop1], Skip)`

Which corresponds to something like `if(Random) { Assign; While(Random) { Assign; } else { Skip; }`. All we did is taking the body of the loop, wrapping it in an if, given the guard of the body, and concatenating the whole loop to the then-branch.

How do the second and third unrolling look like?

let unrolled2 = If(Random, Seq [Assign;

If(Random, Seq [Assign; loop1], Skip)], Skip)

`let unrolled3 = If(Random, Seq [Assign;
If(Random, Seq [Assign;
If(Random, Seq [Assign; loop1], Skip)], Skip)], Skip)
`

Ok, we see a very repetitive structure (obviously!). Let’s try to write some functions which solve our problem.

The first pattern we see is the following: If(*GUARD*, Seq[ *BODY*; *REMAINING*] , Skip). Basically, we can generalise the stuff written in capitals with arguments of a function:

`let buildIfSkip guard body remain = If(guard, Seq[body; remain], Skip)`

Given the body and guard of loop1 we could now curry `buildIfSkip` as follows:

`let doRemain = buildIfSkip Random Assign`

The function doRemain has only one argument which defines what gets put in *REMAINING*.

That’s already it, almost! The first unrolling we get by:

`doRemain (doRemain loop1)`

which produces

`If (True, Seq [Assign; If (True, Seq [Assign; While (True, Assign)], Skip)], Skip)`

All which is needed now is a function which parametrises all of this. It needs to do the following:

- Take a loop, get the guard and the body of it
- Produce the function doRemain as shown above
- recursively apply doRemain to itself

Here’s the complete function:

let unroll loop n = let guard,body = match loop with |While(guard,body) -> guard,body |_ -> raise Not_found in let buildIfSkip guard body remain = If(guard, Seq[body; remain], Skip) in let doRemain = buildIfSkip guard body in let iterate n f v = let rec iter v = function 0 -> v |n -> iter (f v) (n-1) in iter v n in iterate n doRemain loop

To check we can do the following:

`# unroll loop1 3 = unrolled3;;
- : bool = true
#`

Feel free to use the code 🙂

Hey, applause! So this is what you tried to show me and wrodpress didn’t want to co-operate…

While we’re on the subject, I had an idea of getting rid of branching in certain functions. It might be beneficial for cases where some functions get called a lot and have branches inside – e.g. a state machine which is run all the time.

The idea is something like this; each branch would be something like a function pointer, and could point to an empty function or a real function. Then, condition-evaluation would just set the function pointers appropriately. The condition evaluation would have to be done anyway, but would be done “on demand”, not all the time.

Then the worker function would always look like the same with “hardcoded” stuff i.e. calls to the function ptrs.

In dodgy pseudocode, something like:

void allTheTime() { if (a) { doA(); } if (b) { doB(); } else { doC(); } }

would become:

void allTheTime() { doAPtr(); doBPtr(); doCPtr(); }

And the contents of each ptr would be set appropriately. When e.g. b is false, then doBPtr would be set to point to an empty function – or No-Operations, or such. No branching needed in the new allTheTime function.

Maybe I should write a blog entry about this… and analyze it a bit further. It’s pretty raw from my head, didn’t roll any numbers to see if it would actually help much.

SlinkyDecember 12, 2008 at 9:15 pm

Nice.. Here is another article about loop unrolling and compilers but this time in C:

http://www.safercode.com/blog/2009/01/27/tweak-your-code-for-speed-unroll-those-loops-part-1.html

shantanu goelFebruary 14, 2009 at 12:11 am