Loop Derolling

Loop derolling, also known as loop rolling or loop rerolling, is a powerful technique used in source-to-source compilers to optimize and manage code efficiency and readability. This technique is particularly useful when dealing with loop unrolling, an optimization method that expands loops to decrease the iteration count and, ideally, enhance the program's execution speed. However, loop unrolling increases the code size and can sometimes adversely affect cache performance or make the code less maintainable. Here, loop derolling comes into play by transforming unrolled loops back into their more compact, rolled form.

Description

Loop derolling reverses the effects of loop unrolling. It reduces the expanded code of an unrolled loop into a loop with fewer lines of code and more iterations. This technique can improve code readability, reduce code size, and sometimes even enhance performance by improving cache utilization.

How Does It Work?

The process of loop derolling involves analyzing the structure of unrolled loops and then condensing them into a standard loop form with an appropriate iteration count. For example, consider a loop that has been unrolled to perform four iterations in a single pass. Loop derolling would transform this back into a loop that performs a single iteration per pass, across four passes.

Benefits of Loop Derolling

• Code Size Reduction: Compact code is easier to manage, understand, and debug.
• Improved Readability: Returning to a standard loop form makes the code more accessible to others, enhancing maintainability.
• Potential Performance Gains: In some cases, especially where cache utilization is concerned, derolled loops may perform better due to reduced code size and increased cache efficiency.

Interaction with Code Generators

Many code generator (e.g. dSpace TargetLink) automatically apply loop unrolling until configurable amount of loop iterations. Loop derolling can undo the effect for optimizing and fine-tuning the code for specific architectures.

Loop Derolling Transformation in emmtrix Studio

emmtrix Studio can implement loop derolling using #pragma directives or via the GUI. These directives inform the compiler of the developer's intent to deroll specific loops, guiding the transformation process.

Example

Consider the following C code snippet that manually unrolls a loop:

int a[10];
int b[10];

#pragma EMX_TRANSFORMATION Deroll
int main() {
    a[0] = 0;
    b[0] = 0;
    a[1] = 1;
    b[1] = 1;
    a[2] = 2;
    b[2] = 2;
    a[3] = 3;
    b[3] = 3;
}

Using loop derolling, the source-to-source compiler can transform this into:

int a[10];
int b[10];

int main() {
    for (int i = 0; i < 4; i = i + 1) {
        a[i] = i;
        b[i] = i;
    } 
}