[Issue 4453] New: Loop-invariant code motion for pure functions

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=4453

           Summary: Loop-invariant code motion for pure functions
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: DMD
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2010-07-13 09:42:55 PDT ---
D pure functions return the same result (or they throw an error/exception), so
their call can be pulled out of loops if their input is loop-invariant. It's a
compiler optimization:
http://en.wikipedia.org/wiki/Loop-invariant_code_motion

This example of D2 code shows two examples of this possible optimization:


import core.stdc.stdio: printf;
pure int foo(int n) {
    auto array = new int[n];
    foreach (i, ref x; array)
        x = i;
    int total = 0;
    foreach (x; array)
        total += x;
    return total;
}
void main() {
    int[int] aa = [1:10];
    int total = 0;
    foreach (i; 0 .. 5) {
        int n = aa[1];
        total += foo(n);
    }
    printf("%d\n", total);
}


The fetching of a value from an associative array (__aaGetRvalue) is a pure
function, and there is no other change done on the associative array, so it can
be moved outside the foreach(i) loop of main(). Then the call to foo(n) too
becomes loop-invariant. (Later further optimizations can replace the constant
sums inside a loop by a multiplication, but this is a different kind of
optimization).

Currently dmd v2.047 doesn't move the calls to not-inlined pure functions out
of the loop:


L1D:        push    1
        mov    EDX,offset FLAT:_D10TypeInfo_i6__initZ
        push    4
        push    EDX
        push    EDI
        call    near ptr __aaGetRvalue
        add    ESP,010h
        mov    EAX,[EAX]
        call    near ptr _D5test23fooFNaiZi
        add    ESI,EAX
        inc    EBX
        cmp    EBX,5
        jb    L1D

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------