[LLVMbugs] [Bug 5117] New: Simplification of multiple array initializations

[bugzilla-daemon at cs.uiuc.edu]

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

           Summary: Simplification of multiple array initializations
           Product: new-bugs
           Version: unspecified
          Platform: All
        OS/Version: All
            Status: NEW
          Keywords: code-quality, new-feature
          Severity: normal
          Priority: P2
         Component: new bugs
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: bearophile at mailas.com
                CC: llvmbugs at cs.uiuc.edu


Unlike C, the D language always initializes all variables and dynamic arrays,
so sometimes it wastes some time in useless initializations, especially for
arrays.

The back-end of the D LDC compiler is LLVM, so I'd like LLVM to recognize
*basic* cases of multiple initialization and simplify them away.

Doing it in general may be not easy, but for remove the D wasted
initializations just a basic recognition is enough (also changing LDC itself
too a little).

SO for this C code:


#include "stdlib.h"
#define N 10000
int foo(int n) {
    int i;
    int *arr = calloc(N, sizeof(int));
    for (i = 0; i < N; i++)
        arr[i] = 0;
    for (i = 0; i < N; i++)
        arr[i] = 10;
    for (i = 0; i < N; i++)
        arr[i] = i;
    return arr[n];
}


I'd like LLVM to produce something like this (note it uses a malloc and keeps
only the third loop, while the C code uses a calloc. The SimplifyLibCalls pass
may perform such simplification calloc->malloc):


define i32 @foo(i32 %n) nounwind {
bb1.thread:
    %0 = malloc [10000 x i32]       ; <[10000 x i32]*> [#uses=2]
    br label %bb1

bb1:        ; preds = %bb1, %bb1.thread
    %i.0.reg2mem.0 = phi i32 [ 0, %bb1.thread ], [ %indvar.next, %bb1 ]     ;
<i32> [#uses=3]
    %1 = getelementptr [10000 x i32]* %0, i32 0, i32 %i.0.reg2mem.0     ;
<i32*> [#uses=1]
    store i32 %i.0.reg2mem.0, i32* %1, align 4
    %indvar.next = add i32 %i.0.reg2mem.0, 1        ; <i32> [#uses=2]
    %exitcond = icmp eq i32 %indvar.next, 10000     ; <i1> [#uses=1]
    br i1 %exitcond, label %bb2, label %bb1

bb2:        ; preds = %bb1
    %2 = getelementptr [10000 x i32]* %0, i32 0, i32 %n     ; <i32*> [#uses=1]
    %3 = load i32* %2, align 4      ; <i32> [#uses=1]
    ret i32 %3
}

---------------------------------------------------------

Just for reference this is a similar example of D code:

int foo(int n) {
    auto arr = new int[10_000];
    for (int i; i < arr.length; i++)
        arr[i] = 0;
    arr[] = 10; // sets all arr to 10
    foreach (i, ref el; arr)
        el = i;
    return arr[n];
}


This is how the LDC head compiler currently compiles it:

foo:
    pushl   %ebx
    pushl   %edi
    pushl   %esi
    subl    $16, %esp
    movl    $10000, 4(%esp)
    movl    $_D11TypeInfo_Ai6__initZ, (%esp)
    xorl    %esi, %esi
    movl    %eax, %edi
    call    _d_newarrayT
    movl    %eax, %ebx
    .align  16
.LBB1_1:
    movl    $0, (%ebx,%esi,4)
    incl    %esi
    cmpl    $10000, %esi
    jne .LBB1_1
    movl    %ebx, (%esp)
    movl    $10, 8(%esp)
    movl    $10000, 4(%esp)
    call    _d_array_init_i32
    xorl    %eax, %eax
    .align  16
.LBB1_3:
    movl    %eax, (%ebx,%eax,4)
    incl    %eax
    cmpl    $10000, %eax
    jne .LBB1_3
    movl    (%ebx,%edi,4), %eax
    addl    $16, %esp
    popl    %esi
    popl    %edi
    popl    %ebx
    ret

Note the call to _d_array_init_i32 to perform:
the arr[] = 10;
This is where LDC itself may need to be improved (splitting that call in two
parts, allocation and initialization, giving LLVM a better chance to remove the
initialization where it's redundant).


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