[LLVMbugs] [Bug 5540] New: Partial loop unwinding with variable iteration count

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=5540

           Summary: Partial loop unwinding with variable iteration count
           Product: new-bugs
           Version: 2.6
          Platform: PC
        OS/Version: Windows NT
            Status: NEW
          Keywords: code-quality, new-feature
          Severity: enhancement
          Priority: P2
         Component: new bugs
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: bearophile at mailas.com
                CC: llvmbugs at cs.uiuc.edu


See bug 5501 to understand where this comes from:
http://llvm.org/bugs/show_bug.cgi?id=5501

After a discussion on IRC it seems LLVM is not able to perform a partial loop
unwinding when the iteration count is a run-time variable, a simple example of
C code:

#include <stdio.h>
#include <stdlib.h>

__attribute__((noinline)) int foo(int x) {
    return x * x;
}
int main() {
    int n = atoi("100"); // a run-time value
    int i, tot = 0;
    for (i = 0; i < n; i++)
        tot += foo(i);
    printf("%d\n", tot);
    return 0;
}


But the JavaVM HotSpot shows that optimization can be useful. Generally an
unrolling of 2 or 4 or 8 is enough (4 is typical. A much larger value is useful
only in special situations). Such number can be chosen heuristically according
to the amount of asm instructions inside the loop.

A little little example in C that shows how to perform first the modulus of the
loop unrolling, followed by 4X unroll (as done by HotSpot):

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n = atoi("20"); // a run-time value
    int unroll = 4; // usually 2, 4 or 8. Normally 4

    int rest = n % unroll;

    int i;
    for (i = 0; i < rest; i++)
        printf("%d\n", i);

    for (i = rest; i < n; i += 4) {
        printf("%d\n", i + 0);
        printf("%d\n", i + 1);
        printf("%d\n", i + 2);
        printf("%d\n", i + 3);
    }

    return 0;
}

A run-time profiling too can help locate what loops may enjoy such dynamic
unrolling. In the meantime annotations and compilation flags are blunt tools
that are enough to ask the backend for this optimization.


-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.