Bound checking elimination

[soywiz]

For this kotlin code:

fun main(args: Array<String>) {
        val a = IntArray(100_000_000)
        for (n in 0 until a.size) {
                a[n] = 1
        }
        var sum = 0
        for (n in 0 until a.size) {
                sum += a[n]
        }
        println(sum)
}

kotlinc -opt demo.kt

-->

This seems to be the C decompiled code after generating an optimized binary:

So I guess something can be done here. If LLVM knows that a value is going to be constant for the whole loop, it would move it outside the loop, and would match the symbolic range check eliminating the if check completely.

Maybe the -1 there doesn't help the optimizer either to do the symbolic range checking for the dead code elimination.

---

This C code seems to do bound checking elimination because LLVM knows that n won't never be greater than array.size and knows that array.size is constant:

// clang -S -O3 -emit-llvm test.c && cat test.ll # no abort appears in the .ll file

#include <stdio.h>

typedef struct Array {
        char* ptr;
        int size;
} Array;

inline void arrayCheck(Array array, int n) {
        if (n < 0 || n >= array.size) abort();
}

int main(int argc, char **argv) {
        int size = atoi(argv[1]);
        Array array = {alloca(size), size};
        memset(array.ptr, 0, array.size);
        for (int n = 0; n < array.size; n++) {
                arrayCheck(array, n);
                array.ptr[n] = n * n;
        }
        for (int m = 0; m < array.size; m++) {
                printf("%d\n", m);
        }
        return 0;
}

---

Would put here const would help? Though I guess LLVM should be able to guess it if you are only setting it at construction. Are you setting the _count in other place than the construction?

kotlin-native/runtime/src/main/cpp/Memory.h

Line 240 in da7e31a

uint32_t count_;

Would help marking this as pure and inline?
https://github.com/JetBrains/kotlin-native/blob/master/runtime/src/main/cpp/Natives.h#L110

---

If can't instruct LLVM to do it. I guess you can store just after loading an array as local its size in other local and use it instead as intrinsics, there is a comment suggesting to do that in the future.

Would be possible to attach variable range information before lowering since in kotlin you cannot mutate the iterator variable for a plain for, and then have something like UnsafeArraySet/ArrayGet lowered IR node constructed with the information provided from the loops if it is proven that the index is always inside bounds.

---

Would be nice to also provide methods for getting setting values without boundcheckings. I have several critical paths where I totally know the index is fine where maybe LLVM cannot guess it is true. You can do it already with pointers, but pinning each time has a cost (I'm talking about billions of iterations inside methods within methods), and having to propagate the pinned object is not very nice either.
As an example I'm using a IntArray(32) to keep all the GPR registers of an emulator but when decoding the instruction I'm already masking & 0x1F, so I know the index is fine already, but in a complex program, an AOT compiler might not know this.

Not doing bound checking in hot places, can also enable vectorizing some loops to use SIMD instructions automatically when available, or even using x86 high level instructions, for repeating memory instructions.
JS and JVM can do optimistic optimizations and guesses at runtime, but AOT might require a bit of help in certain critical places.

---

Also would be nice to only be able to do pointer arithmetic and call unsafe functions within a @Unsafe annotated method, like D and C# do, to make security reviewing easier. Though this approach would require a ton of annotations if most of the codebase is somehow unsafe and not extracted the functionality to specific methods, so this might be controversial, but wanted to suggest it anyway.

[soywiz]

The other day just noticed about this:

• https://stackoverflow.com/questions/40447195/can-i-hint-the-optimizer-by-giving-the-range-of-an-integer
• https://www.quora.com/What-is-the-maximum-size-of-the-array-in-Java (But in recent HotSpot JVM it has been observed that the max size of array can be Integer.MAX_VALUE - 5.)

Maybe using both (and actually limiting allocations to Int.MAX - 5), it is possible to hint LLVM or the konan compiler, so doing things like for (n in 0 until array.size step 4) work fine (knowing for sure that it is not going to overflow). I usually only use step 1, 2 and 4 for some algorithms, so optimizing those would be nice.

[sbogolepov]

Hi. We are migrating issues to YouTrack, so I created a new one there.