Missed optimization: finding closed form of loop doesn't take advantage of assumption

[Quuxplusone]

Bugzilla Link	41025
Version	trunk
OS	All
CC	@hfinkel,@zygoloid,@rotateright

Extended Description

Clang trunk does a great job turning this sum-the-area-of-a-trapezoid function into its closed form. However, the closed form needs a branch to deal with the possibility that the distance from 'b' to 'e' is negative: in that case, 0 should be returned as a special case.

You can eliminate the special case by adding __builtin_assume(b < e) to the top of the function. This eliminates the branch from the codegen of f1.

However, Clang is not currently able to eliminate the branch from the codegen of f2, even though it is identical to f1 except that f2 uses i != e as the loop termination condition instead of i < e.

I don't know if this is a very deep and complicated bug that's not worth fixing, or just a simple one-line update somewhere. :)

https://godbolt.org/z/aWAahD

int f1(unsigned b, unsigned e)
{
    __builtin_assume( b < e );

    int total = 0;
    for (unsigned i = b; i < e; ++i) {
        total += i;
    }
    return total;
}

int f2(unsigned b, unsigned e)
{
    __builtin_assume( b < e );

    int total = 0;
    for (unsigned i = b; i != e; ++i) {
        total += i;
    }
    return total;
}

====

_Z2f1jj: # @​_Z2f1jj
  movl %edi, %ecx
  notl %ecx
  addl %esi, %ecx
  leal 1(%rdi), %eax
  imull %ecx, %eax
  addl $-2, %esi
  subl %edi, %esi
  imulq %rcx, %rsi
  shrq %rsi
  addl %edi, %eax
  addl %esi, %eax
  retq

_Z2f2jj: # @​_Z2f2jj
  xorl %eax, %eax
  cmpl %esi, %edi
  je .LBB1_2        // THIS BRANCH should be unnecessary AFAICT
  movl %edi, %ecx
  notl %ecx
  addl %esi, %ecx
  leal 1(%rdi), %eax
  imull %ecx, %eax
  addl $-2, %esi
  subl %edi, %esi
  imulq %rcx, %rsi
  shrq %rsi
  addl %edi, %eax
  addl %esi, %eax
.LBB1_2:
  retq

[rotateright]

In the problem case, we have:
%cmp = icmp ult i32 %b, %e
tail call void @​llvm.assume(i1 %cmp)
%cmp19 = icmp eq i32 %b, %e

We need to add a transform that simplifies a compare based on the implication of another compare.

We appear to have the necessary analysis via "CmpInst::isImpliedTrueByMatchingCmp()".

[nikic]

Looks like this has been fixed a long time ago, in Clang 10.