[InstCombine] Performance degradation caused by more branch after commit b5a9361 and #66740

[cyyself]

Statement

Commit b5a9361 and PR #66740 (commit a7f962c) caused more likely branches generated. Result in 37% or more end-to-end severe performance degradation on both AMD Zen 4 and Intel Raptor Lake running Verilator generated C++ codes for XiangShan. As we can compare these two results: cyyself@a2489e3#commitcomment-144413753 cyyself@40529f8#commitcomment-144413665.

Reduced reproducer

https://godbolt.org/z/TYsnxGf5a

Look at the following code:

struct a_struct {
    bool b_1, b_2, b_3;
    unsigned int cv_1, cv_2, cv_3;
    unsigned int cav_1, cav_2, cav_3;
    unsigned int d;
};

void some_func(a_struct &a) {
    if (a.b_1 & (8U == (0x1f & a.cv_1))) [[unlikely]] {
        a.d = a.cav_1;
    }
    else if (a.b_2 & (7U == (0x1f & a.cv_2))) [[unlikely]] {
        a.d = a.cav_2;
    }
    else if (a.b_3 & (6U == (0x1f & a.cv_3))) [[unlikely]] {
        a.d = a.cav_3;
    }
}

Compile: clang++ -O3 -c test.cpp -S

We will get this code on the x86-64 target on LLVM main (at least for commit da0c8b2):

_Z9some_funcR8a_struct:                 # @_Z9some_funcR8a_struct
	.cfi_startproc
# %bb.0:
	movl	4(%rdi), %eax
	andl	$31, %eax
	cmpl	$8, %eax
	jne	.LBB0_3
# %bb.1:
	cmpb	$0, (%rdi)
	jne	.LBB0_2
.LBB0_3:
	movl	8(%rdi), %eax
	andl	$31, %eax
	cmpl	$7, %eax
	jne	.LBB0_6
...

As we can see, if the condition a.b_1 is false, LLVM will generate a conditional jump to the next if even when we have an unlikely hint. Even worse, these conditional jumps are likely to be taken, causing the CPU to flush the pipeline if the branch predictor isn't working for its small size.

But if we revert commit b5a9361 and PR #66740 (commit a7f962c) or directly use the LLVM release version < 16. We will get the code like this:

_Z9some_funcR8a_struct:                 # @_Z9some_funcR8a_struct
	.cfi_startproc
# %bb.0:
	movl	4(%rdi), %eax
	andl	$31, %eax
	cmpl	$8, %eax
	sete	%al
	testb	%al, (%rdi)
	jne	.LBB0_1
# %bb.2:
	movl	8(%rdi), %eax
	andl	$31, %eax
...

It reduced the number of branches by half and is very friendly for CPU branch predictors since there are no likely branches.

[dtcxzyw]

We will get this code on the x86-64 target on LLVM main

I cannot reproduce this with 324fea9

 .text
        .file   "test.cpp"
        .globl  _Z9some_funcR8a_struct          # -- Begin function _Z9some_funcR8a_struct
        .p2align        4, 0x90
        .type   _Z9some_funcR8a_struct,@function
_Z9some_funcR8a_struct:                 # @_Z9some_funcR8a_struct
        .cfi_startproc
# %bb.0:                                # %entry
        cmpb    $0, (%rdi)
        je      .LBB0_3
# %bb.1:                                # %entry
        movl    4(%rdi), %eax
        andl    $31, %eax
        cmpl    $8, %eax
        je      .LBB0_2
.LBB0_3:                                # %if.else
        cmpb    $0, 1(%rdi)
        je      .LBB0_6
# %bb.4:                                # %if.else
        movl    8(%rdi), %eax
        andl    $31, %eax
        cmpl    $7, %eax
        je      .LBB0_5
.LBB0_6:                                # %if.else12
        cmpb    $0, 2(%rdi)
        je      .LBB0_10
# %bb.7:                                # %if.else12
        movl    12(%rdi), %eax
        andl    $31, %eax
        cmpl    $6, %eax
        je      .LBB0_8
.LBB0_10:                               # %if.end23
        retq
.LBB0_2:
        movl    $16, %eax
        movl    (%rdi,%rax), %eax
        movl    %eax, 28(%rdi)
        retq
.LBB0_5:
        movl    $20, %eax
        movl    (%rdi,%rax), %eax
        movl    %eax, 28(%rdi)
        retq
.LBB0_8:
        movl    $24, %eax
        movl    (%rdi,%rax), %eax
        movl    %eax, 28(%rdi)
        retq
.Lfunc_end0:
        .size   _Z9some_funcR8a_struct, .Lfunc_end0-_Z9some_funcR8a_struct
        .cfi_endproc
                                        # -- End function
        .ident  "clang version 19.0.0git"
        .section        ".note.GNU-stack","",@progbits
        .addrsig

[cyyself]

We will get this code on the x86-64 target on LLVM main

I cannot reproduce this with 324fea9

Actually, you successfully reproduced. Please look carefully.

[dtcxzyw]

SDAGBuilder converts and/or into branches here:

llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

Lines 2801 to 2825 in 9d2f81e

	// If this condition is one of the special cases we handle, do special stuff
	// now.
	const Value *CondVal = I.getCondition();
	MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)];
	// If this is a series of conditions that are or'd or and'd together, emit
	// this as a sequence of branches instead of setcc's with and/or operations.
	// As long as jumps are not expensive (exceptions for multi-use logic ops,
	// unpredictable branches, and vector extracts because those jumps are likely
	// expensive for any target), this should improve performance.
	// For example, instead of something like:
	// cmp A, B
	// C = seteq
	// cmp D, E
	// F = setle
	// or C, F
	// jnz foo
	// Emit:
	// cmp A, B
	// je foo
	// cmp D, E
	// jle foo
	const Instruction *BOp = dyn_cast<Instruction>(CondVal);
	if (!DAG.getTargetLoweringInfo().isJumpExpensive() && BOp &&
	BOp->hasOneUse() && !I.hasMetadata(LLVMContext::MD_unpredictable)) {

[dtcxzyw]

As a workaround, can you try with -mllvm --jump-is-expensive?

[cyyself]

As a workaround, can you try with -mllvm --jump-is-expensive?

Confirmed. The performance of my workload is approximately to the result of reverted these two commit now.