[llvm-bugs] [Bug 49336] New: Conditional branches are exchanged unoptimally

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=49336

            Bug ID: 49336
           Summary: Conditional branches are exchanged unoptimally
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Backend: X86
          Assignee: unassignedbugs at nondot.org
          Reporter: carrot at google.com
                CC: craig.topper at gmail.com, llvm-bugs at lists.llvm.org,
                    llvm-dev at redking.me.uk, pengfei.wang at intel.com,
                    spatel+llvm at rotateright.com

The following code is extracted from zippy. Compile it with -O2

#include <utility>
#define PREDICT_FALSE(x) __builtin_expect((x), 0)

volatile int g;

std::pair<char*, int>
foo(char* ip, char* ip_limit, int op) {
    do {
      char* old_ip = ip; 
      int tag_type = g;
      ip = ip + 1;
      int offset = *old_ip;
      if (offset < 8) {
          ip = ip + 2;
      }   
      int delta = op - offset;
      if (PREDICT_FALSE(delta < 0)) {     
        if (tag_type != 0) {             
            ip = old_ip;
            break;
        }
      }   
      op += 8;
    } while (ip < ip_limit);
  return {ip, op};
}

LLVM generates:

_Z3fooPcS_i:                            # @_Z3fooPcS_i
        .cfi_startproc
# %bb.0:                                # %entry
        movq    %rdi, %rax
        jmp     .LBB0_1
        .p2align        4, 0x90
.LBB0_3:                                # %cleanup
                                        #   in Loop: Header=BB0_1 Depth=1
        movb    %r8b, %cl 
        leaq    (%rax,%rcx,2), %rax
        addq    $1, %rax
        addl    $8, %edx
        cmpq    %rsi, %rax
        jae     .LBB0_4
.LBB0_1:                                # %do.body
                                        # =>This Inner Loop Header: Depth=1
        movl    g(%rip), %r9d
        movsbl  (%rax), %edi
        xorl    %ecx, %ecx
        cmpl    $8, %edi
        setl    %r8b
        testl   %r9d, %r9d              // if (tag_type != 0)
        je      .LBB0_3
# %bb.2:                                # %do.body
                                        #   in Loop: Header=BB0_1 Depth=1
        cmpl    %edi, %edx              // if (PREDICT_FALSE(delta < 0))
        jge     .LBB0_3
.LBB0_4:                                # %do.end
        retq

The condition (tag_type != 0) is unpredictable, but (delta < 0) is predicted as
false, so the unpredictable condition (tag_type != 0) is rarely executed.
But in the generated code, llvm changed the order of the two conditions, so the
unpredictable condition is always executed, causes more branch mis-prediction.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20210224/38a7bc4f/attachment.html>