r/LLVM • • Feb 02 '19

Optimizing Rust's RangeInclusive external iteration.

Hello,

For the past few week-ends I have been banging my head trying to get LLVM to optimize the external iteration of Rust RangeInclusive. The idea of RangeInclusive is simple, given two values start and end, iterate over [start, end]. The difficulty lies in the fact that unless with the semi-exclusive range [start, end) denoting the "end" of the iteration is relatively difficult.

My goal has been to:

  1. Have LLVM understand the loop structure, optimizing it out (closed form solution) when possible.

  2. When LLVM fails to do so, have a single conditional jump in the "hot" loop.

Note: the current implementation succeeds at (1), my implementation succeeds at (2), I am looking for an implementation which succeeds at both in order to be optimal whether LLVM succeeds to optimize out the loop or not.

You can follow my progress on r/Compilers; and notice that it stalled, unfortunately.

In case you prefer C++ code, it can be found on godbolt; I invite you to play with it, but reproduced it below in full for those not wishing to follow the link.

I am looking for clues:

  • in either a better implementation of RangeInclusive,

  • or a way to better understand why LLVM fails to optimize, and how to solve the issue.

I have played with -print-after-all, which is what enabled me to come this far by comparing the output at various stages for various implementations which succeeded at one or the other goal, but honestly it was not principled at all... and even sleeping on it I've run out of ideas.

I think the key to it all would be to get LLVM to realize that iterating over [start, end] is really iterating over [start, end) and then using end, which is what the internal iteration (range.for_each([&](int j) { count +=j; });) does and which produces optimal code. Unfortunately, I have not managed to replicate this with external iteration.


Full code in C++.

The "full sugar" version assumes an imaginary RangeInclusive::next method returning std::optional<T>, allowing to write:

int triangle(int n) {
    int count = 0;
    auto range = RangeInclusive<int>(0, n);
    while (auto j = range.next()) { count += j; }
    return count;
}

I have managed to find a "fully inlined" implementation which succeeds in generating optimal code:

int triangle_inlined(int n) {
    int count = 0;
    {
        int start = 0;
        bool is_done = false;

        while (true) {
            if (start < n) {
                count += start;
                start += 1;
                continue;
            }

            if (!is_done && start == n) {
                count += start;
                is_done = true;
                continue;
            }

            break;
        }
    }
    return count;
}

Generating the following assembly (beautiful, no?):

triangle_inlined(int):                  # @triangle_inlined(int)
    xor     ecx, ecx
    test    edi, edi
    cmovns  ecx, edi
    lea     eax, [rcx - 1]
    imul    rax, rcx
    shr     rax
    add     eax, ecx
    ret

Unfortunately, applying the minimum amount of "de-inlining" as possible -- computing std::optional<int> prior to using it, rather than inlining the operation -- foils LLVM:

int triangle_barely_sugared(int n) {
    int count = 0;
    {
        int start = 0;
        bool is_done = false;

        while (true) {
            bool is_set;
            int next;
            
            //  start RangeInclusive::next
            if (start < n) {
                int result = start;
                start += 1;
                //  return from RangeInclusive::next
                next = result;
                is_set = true;
            } else if (!is_done && start == n) {
                is_done = true;
                //  return from RangeInclusive::next
                next = start;
                is_set = true;
            } else {
                //  return from RangeInclusive::next
                is_set = false;
            }

            if (is_set) {
                count += next;
                continue;
            }

            break;
        }
    }
    return count;
}

And gives the following assembly:

triangle_barely_sugared(int):           # @triangle_barely_sugared(int)
    xor     edx, edx
    xor     ecx, ecx
    xor     eax, eax
    cmp     edx, edi
    jge     .LBB0_3
    jmp     .LBB0_2
.LBB0_5:
    add     eax, edx
    mov     edx, esi
    cmp     edx, edi
    jge     .LBB0_3
.LBB0_2:
    lea     esi, [rdx + 1]
    jmp     .LBB0_5
.LBB0_3:
    jne     .LBB0_6
    mov     esi, edi
    mov     edx, edi
    test    cl, cl
    mov     cl, 1
    je      .LBB0_5
.LBB0_6:
    ret

This succeeds at the second goal: the hot loop (.LBB0_3 <-> .LBB0_5) has a single conditional jump. Unfortunately, since there's a hot loop, it means LLVM failed to optimize it out.

3 Upvotes

0 comments sorted by