Inefficient code generated for "if (Operator *O = dyn_cast<Operator>(V)) { foo(O); }"

[jlebar]

Bugzilla Link	28430
Version	trunk
OS	All
CC	@zmodem,@hfinkel,@slacka,@rnk,@rotateright

Extended Description

I would expect the following two functions to compile to (roughly) the same
x86-64 machine code.

  void foo(Operator *O);

  void test1(Value *V) {
    if (Operator *O = dyn_cast<Operator>(V))
      foo(O);
  }   
  void test2(Value *V) {
    if (isa<Operator>(V))
      foo(cast<Operator>(V));
  }

But they don't:

_Z5test1PN4llvm5ValueE:
        mov     cl, byte ptr [rdi + 24]
        cmp     cl, 23
        seta    al
        cmp     cl, 10
        setne   cl
        test    rdi, rdi
        je      .LBB0_2
        xor     al, cl
        jne     .LBB0_2
        jmp     _Z3fooPN4llvm8OperatorE@PLT # TAILCALL
.LBB0_2:
        ret

_Z5test2PN4llvm5ValueE:
        mov     al, byte ptr [rdi + 24]
        cmp     al, 23
        ja      .LBB0_3
        cmp     al, 10
        je      .LBB0_3
        ret
.LBB0_3:
        jmp     _Z3fooPN4llvm8OperatorE@PLT # TAILCALL

It seems to me that there are two problems with the code generated for test1:

First, the null check on rdi shouldn't be necessary. The isa call inside
dyn_cast dereferences the pointer, so (I think?) we should be able to assume
that it's not null. (Adding an explicit __builtin_assume to the implementatin
of dyn_cast gets rid of this check.)

Second, although I'm not enough of an x86 expert to say whether the two-jump
version (as in test2) or one-jump version (as in test1) is preferable, since
they do the same thing, presumably we should prefer one over the other, if only
due to code size differences. (I also wouldn't be surprised if there were
performance differences.)

gcc 4.8.4 emits the same code for both functions, and it's basically identical
to the code clang generates for test2:

        movzx   eax, BYTE PTR 24[rdi]
        cmp     al, 23
        ja      .L9
        cmp     al, 10
        je      .L9
        rep ret
.L9:
        jmp     _Z3fooPN4llvm8OperatorE@PLT

Here are the -print-after-all -debug logs for the two functions:

test1: https://gist.github.com/fbbabc5299aca5a275b2b38a6d9d217f
test2: https://gist.github.com/24dee5133a003c12b0c127e5e5f2a3c9

Since we use this idiom everywhere in clang and llvm, it seems like a good bet
that we'd get a performance improvement from improving the codegen here.

[jlebar]

(These tests were done with clang/llvm at HEAD.)

[jlebar]

I added a __builtin_assume(Val != nullptr) to isa, dyn_cast, and cast, and the compilation time of the eigen benchmark I've been playing with went from 13s to 3s.

It's an understatement to say that beggars belief. I am running more tests.

[jlebar]

...well, the __builtin_assume's break some tests, so maybe that's responsible for the speedup somehow.

[jlebar]

The test breakage is, I am pretty sure, a miscompile with clang 3.8. All the tests pass if I boostrap clang from head (first without the assumes, then with them), but, unsurprisingly, the compiler also doesn't run 4x faster. It may be a ~1% speedup, but heck if I'm going to go anywhere near those assumes after fighting with this miscompile in our latest stable version.

Anyway, there does seem to be a missed optimization opportunity for clang here.

[rotateright]

This still looks bad with trunk r289057.

If a gep is inbounds, does that mean a subsequent load in address space 0 using that result must be nonnull?

%4 = getelementptr inbounds %"class.llvm::Value", %"class.llvm::Value"* %3, i64 0, i32 3
%5 = load i8, i8* %4, align 8, !tbaa !​6

[rotateright]

Patch that doesn't solve this, but might be step 1 of N:
https://reviews.llvm.org/D27855

[rotateright]

Another possible step towards solving this:
https://reviews.llvm.org/D28204

[rotateright]

And 2 more steps:
https://reviews.llvm.org/D28337
https://reviews.llvm.org/D28485

[rotateright]

This still looks bad with trunk r289057.

If a gep is inbounds, does that mean a subsequent load in address space 0
using that result must be nonnull?

%4 = getelementptr inbounds %"class.llvm::Value", %"class.llvm::Value"*
%3, i64 0, i32 3
%5 = load i8, i8* %4, align 8, !tbaa !​6

There's discussion about the semantics of GEP and null in bug 31439 (#30787).

[slacka]

After r298237 (https://reviews.llvm.org/D28204), LibreOffice cannot be built with the NewGVN. See Bug 32349

[slacka]

After r294897 (https://reviews.llvm.org/D28204), LibreOffice cannot be built with the NewGVN. This issue partially fixed by r295583. See Bug 32349 for details.

[aaronpuchert]

I was curious what kind of effect this might have on LLVM itself. With the above-mentioned workaround (condensed down to dyn_cast, which I think is the only interesting function here):

diff --git a/llvm/include/llvm/Support/Casting.h b/llvm/include/llvm/Support/Casting.h
index 4ff5865..19623f6 100644
--- a/llvm/include/llvm/Support/Casting.h
+++ b/llvm/include/llvm/Support/Casting.h
@@ -661,6 +661,9 @@ template <typename To, typename From>
 template <typename To, typename From>
 [[nodiscard]] inline decltype(auto) dyn_cast(From *Val) {
   assert(detail::isPresent(Val) && "dyn_cast on a non-existent value");
+#if defined(__clang__) && defined(NDEBUG)
+  __builtin_assume(Val);
+#endif
   return CastInfo<To, From *>::doCastIfPossible(Val);
 }
 

I see a reduction in the number of instructions for a typical compilation by 1% (branches by 1.5%). Doesn't sound like much, but it's not a micro-benchmark, and would probably be noticeable in the compile time tracker. The effect in time/cycles is of course harder to measure reliably, but since we're just removing redundancy it's probably not going to get slower.

The most impressive example that I came across is LLVMGetOrdering. Without workaround it has a couple of branches:

00000000033a7120 <LLVMGetOrdering@@LLVM_15>:
 33a7120:              movzbl 0x10(%rdi),%eax
 33a7124:              test   %rdi,%rdi
 33a7127:          /-- je     33a7136 <LLVMGetOrdering@@LLVM_15+0x16>
 33a7129:          |   cmp    $0x3b,%al
 33a712b:          +-- jne    33a7136 <LLVMGetOrdering@@LLVM_15+0x16>
 33a712d:          |   movzwl 0x12(%rdi),%eax
 33a7131:          |   shr    $0x7,%eax
 33a7134:       /--|-- jmp    33a7150 <LLVMGetOrdering@@LLVM_15+0x30>
 33a7136:       |  \-> movzwl 0x12(%rdi),%ecx
 33a713a:       |      test   %rdi,%rdi
 33a713d:       |  /-- je     33a714b <LLVMGetOrdering@@LLVM_15+0x2b>
 33a713f:       |  |   cmp    $0x3c,%al
 33a7141:       |  +-- jne    33a714b <LLVMGetOrdering@@LLVM_15+0x2b>
 33a7143:       |  |   movzwl %cx,%eax
 33a7146:       |  |   shr    $0x7,%eax
 33a7149:       +--|-- jmp    33a7150 <LLVMGetOrdering@@LLVM_15+0x30>
 33a714b:       |  \-> movzwl %cx,%eax
 33a714e:       |      shr    %eax
 33a7150:       \----> movzwl %ax,%eax
 33a7153:              and    $0x7,%eax
 33a7156:              ret

With workaround they're all gone:

00000000033a7060 <LLVMGetOrdering@@LLVM_15>:
 33a7060:       movzbl 0x10(%rdi),%eax
 33a7064:       add    $0xc5,%al
 33a7066:       cmp    $0x2,%al
 33a7068:       movzwl 0x12(%rdi),%eax
 33a706c:       mov    $0x7,%edx
 33a7071:       mov    $0x1,%ecx
 33a7076:       cmovb  %edx,%ecx
 33a7079:       shr    %cl,%eax
 33a707b:       and    $0x7,%eax
 33a707e:       ret

Of course that's not typical though: many polymorphic classes have the discriminator as first field, so the branches are already optimized out without hint.