[Issue 10242] New: Conservative escape analysis for dynamic array allocation

[d-bugmail at puremagic.com]

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

           Summary: Conservative escape analysis for dynamic array
                    allocation
           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 2013-06-02 06:07:39 PDT ---
Time ago I have suggested to support a syntax like:


void main(string[] args) {
    scope int[] data0 = new int[5 + args.length];
}


That syntax must give a compile-time error if you escape data0 in some way.

But an alternative idea, potentially able to improve the performance of lost D
code, is to perform escape analysis on dynamic array allocations. If a dynamic
array is allocated and it doesn't get out of the scope, then if it's small it
can be allocated with an alloca by the D front-end.

In code like this data1 escapes the scope of foo through the pointer p, so it's
allocated on the heap. data2 escapes trough a global variable. But data3
doesn't escape:

int[] data;
int foo(in uint n, ref int* p) nothrow {
    int[] data1 = new int[1 + n];
    p = &data1[1]; // Local pointer escape.
    int[] data2 = new int[2 + n];
    data = data2[1 .. 2]; // Global slice escape.
    int[] data3 = new int[3 + n]; // DFoesn't escape.
    foreach (i, ref d; data3)
        d = i;
    int total = 0;
    foreach (d; data3)
        total += d;
    return total;
}
void main() {}


So this part of foo:

...
    int[] data3 = new int[3 + n];
    foreach (i, ref d; data3)
        d = i;
    int total = 0;
    foreach (d; data3)
        total += d;
    return total;
}


Can be rewritten by the D front-end with a usually run-time length test of the
amount of memory to allocate (here 3+n integers). If it's a large amount of
memory then data3 should be allocated on the heap and a call to gc.free should
be added by the front-end at the end of foo. If the amount of memory to
allocate is small, then maybe the front-end can allocate it on the stack with
an alloca().

The advantage of using "scope" is that it's a two-way contract between compiler
and programmer, and it avoids some mistakes of unwanted escaping. Another
advantage of "scope" is that it gives more control to the programmer, and this
is useful to avoid some of the stack overflows in recursive functions caused by
an unavoidable automatic usage of alloca() from the front-end.

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