jonny goes to england

London & co

Loop unrolling

with 2 comments

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 🙂

Advertisements

Written by jk

December 11, 2008 at 10:57 pm

Posted in english, technical

2 Responses

Subscribe to comments with RSS.

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

    Slinky

    December 12, 2008 at 9:15 pm

  2. 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 goel

    February 14, 2009 at 12:11 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: