r/LLVM • u/matthieum • 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:
Have LLVM understand the loop structure, optimizing it out (closed form solution) when possible.
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
retUnfortunately, 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:
retThis 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.