RISC-V missed optimisation: branch on equal to small constant

[Wren6991]

In this code:

void __attribute__((naked)) f() {asm ("ret");}
void __attribute__((naked)) g() {asm ("ret");}

void h(int a) {
    if (a == 15) {
        f();
    } else {
        g();
    }
}

clang trunk on godbolt produces the following at -Oz:

h(int):
        li      a1, 15
        bne     a0, a1, .LBB2_2
        tail    f()
.LBB2_2:
        tail    g()

(Godbolt link: https://godbolt.org/z/srT6MhG5Y)

However the following is two bytes smaller (because bnez compresses) and avoids a register clobber:

h(int):
        addi    a0, a0, -15
        bnez    a0, .LBB2_2
        tail    f()
.LBB2_2:
        tail    g()

This transform applies when the branch is the final use of the value, and the comparison constant is not -2048 or -32 (due to the sign change). It is useful when the branch is in compressible range, or when avoiding the clobber is profitable.

The same pattern applies to some sparse switch statements, like here in the RP2350 bootrom. That source file has several instances where this pattern saved static code size in handwritten code.

[llvmbot]

@llvm/issue-subscribers-backend-risc-v

Author: Luke Wren (Wren6991)

In this code:

void __attribute__((naked)) f() {asm ("ret");}
void __attribute__((naked)) g() {asm ("ret");}

void h(int a) {
    if (a == 15) {
        f();
    } else {
        g();
    }
}

clang trunk on godbolt produces the following at -Oz:

h(int):
        li      a1, 15
        bne     a0, a1, .LBB2_2
        tail    f()
.LBB2_2:
        tail    g()

(Godbolt link: https://godbolt.org/z/srT6MhG5Y)

However the following is two bytes smaller (because bnez compresses) and avoids a register clobber:

h(int):
        addi    a0, a0, -15
        bnez    a0, .LBB2_2
        tail    f()
.LBB2_2:
        tail    g()

This transform applies when the branch is the final use of the value, and the comparison constant is not -2048 or -32 (due to the sign change). It is useful when the branch is in compressible range, or when avoiding the clobber is profitable.

The same pattern applies to some sparse switch statements, like here in the RP2350 bootrom. That source file has several instances where this pattern saved static code size in handwritten code.

[topperc]

Looks like we try to do this with. But we explicitly ruled out 6 bit constants.

def simm12_no6 : ImmLeaf<XLenVT, [{                                              
  return isInt<12>(Imm) && !isInt<6>(Imm) && isInt<12>(-Imm);}]>;

class BrccCompressOpt<CondCode Cond, RVInstB Inst>                               
    : Pat<(riscv_brcc GPR:$lhs, simm12_no6:$Constant, Cond, bb:$place),          
          (Inst (XLenVT (ADDI GPR:$lhs, (NegImm simm12:$Constant))),             
                (XLenVT X0), bb:$place)>; 

The ADDI isn't guaranteed compressible if the branch isn't the last user of the register. And the branch distance might be too large for the branch itself to be compressible. So it's probably hard to do this from isel.

[Wren6991]

And the branch distance might be too large for the branch itself to be compressible.

When compression fails due to branch range the transformation is size-neutral. It still has potential savings due to reducing live values. Maybe this part is not a blocker?

[Wren6991]

Switch statements seem to have the same behaviour:

char __attribute__((naked)) c() {asm ("li a0, 'c'\nret");}
char __attribute__((naked)) a() {asm ("li a0, 'a'\nret");}
char __attribute__((naked)) s() {asm ("li a0, 's'\nret");}
char __attribute__((naked)) e() {asm ("li a0, 'e'\nret");}

char s(char ch) {
    switch (ch) {
    case 'c': return c();
    case 'a': return a();
    case 's': return s();
    case 'e': return e();
    default:  return 0;
    }
}

compiles to:

s(char):
        addi    a0, a0, -97
        beqz    a0, .LBB4_7
        srli    a1, a0, 1
        slli    a0, a0, 31
        or      a0, a0, a1
        li      a1, 9
        beq     a0, a1, .LBB4_5
        li      a1, 2
        beq     a0, a1, .LBB4_6
        li      a1, 1
        bne     a0, a1, .LBB4_8
        tail    c()
.LBB4_5:
        tail    s()
.LBB4_6:
        tail    e()
.LBB4_7:
        tail    a()
.LBB4_8:
        li      a0, 0
        ret

Godbolt: https://godbolt.org/z/fd5Yaxx9s

The initial compare to 'a' gets the small beqz because it doesn't fit in signed 6-bit, just like you said. The remaining comparisons get 32-bit branches.

[topperc]

Switch statements seem to have the same behaviour:

char __attribute__((naked)) c() {asm ("li a0, 'c'\nret");}
char __attribute__((naked)) a() {asm ("li a0, 'a'\nret");}
char __attribute__((naked)) s() {asm ("li a0, 's'\nret");}
char __attribute__((naked)) e() {asm ("li a0, 'e'\nret");}

char s(char ch) {
    switch (ch) {
    case 'c': return c();
    case 'a': return a();
    case 's': return s();
    case 'e': return e();
    default:  return 0;
    }
}

compiles to:

s(char):
        addi    a0, a0, -97
        beqz    a0, .LBB4_7
        srli    a1, a0, 1
        slli    a0, a0, 31
        or      a0, a0, a1
        li      a1, 9
        beq     a0, a1, .LBB4_5
        li      a1, 2
        beq     a0, a1, .LBB4_6
        li      a1, 1
        bne     a0, a1, .LBB4_8
        tail    c()
.LBB4_5:
        tail    s()
.LBB4_6:
        tail    e()
.LBB4_7:
        tail    a()
.LBB4_8:
        li      a0, 0
        ret

Godbolt: https://godbolt.org/z/fd5Yaxx9s

The initial compare to 'a' gets the small beqz because it doesn't fit in signed 6-bit, just like you said. The remaining comparisons get 32-bit branches.

For this one if we do the conversion, we'll replace the c.li instructions with addis that can't be compressed because we can't modify a0. If the branches don't end up compressing, it won't be size neutral.

In theory we could chain a series of addis by adjusting the later constants so we could clobber a0.

I'm not sure I understand why there's a rotate in that code.

[Wren6991]

In theory we could chain a series of addis by adjusting the later constants so we could clobber a0.

This is exactly what we do in handwritten code, and it can be helpful for sparse switches because the delta coding brings more constants into signed-6 range. I guess this is difficult to handle at the ISel level though.

[arichardson]

Missed this issue so filed a duplicate. Here is my observation prompted by Zibi:

Prompted by the recent change to support the proposed Zibi extension (PR #146858 and PR #127463), I looked into whether the same code size reduction could be achieved with compressed add+branches. At least for some cases we should be able to emit
c.addi a0, -CMP; c.beqz a0, ... (4 bytes) instead of the current c.li a1, CMP, beq a0, a1 (6 bytes).
Interestingly this allows representing all immeidates that Zibi will handle but of course comes with register pressure and codegen challenges that Zibi avoids.
Looking at the most common immediates in spec2017 and 2017, the distribution does seem quite random but it seems like a 6 bit immediate covers many of them (https://gist.github.com/arichardson/b88cc3d3cac1a7fec85ee1d24b463d99)

I made a draft change in https://github.com/arichardson/upstream-llvm-project/tree/2025-compressed-branch-imm, but doing this in tablegen does not seem to be particularly useful.
If I emmit the pattern unconditionally, we end up needed a c.mv $TMP, a0 in many cases since the c.addi requires same in and output registers. In that case we are better off with the c.li.

However, in cases where the register is dead after the comparison, using c.addi+c.beqz avoids the need for an extra register (same as Zibi), so it would be good to have an optimization that uses this pattern whenever possible to asses how much Zibi actually helps code size+reg pressure. Of course Zibi can still be beneficial even with identical code size for simple cores since there is no need to modify a register and/or do somewhat complex macro-op fusion.

Given the following code (https://godbolt.org/z/fn4rx1vr8):

int foo();
int bar();

int test(int num) {
    if (num == 11) {
        return foo();
    } else if (num == 16) {
        return bar();
    }
    return 1;
}

Both clang and GCC emit two li+bne/beq:

test:
        li      a1, 16
        beq     a0, a1, .LBB0_3
        li      a1, 11
        bne     a0, a1, .LBB0_4
        tail    foo
.LBB0_3:
        tail    bar
.LBB0_4:
        li      a0, 1
        ret

But since a0 is dead after the branch we should be able to save at least two bytes for the final branch quite easily:

test:
        c.li    a1,11
        beq     a0,a5,.LBB0_3
        c.addi  a0,-16
        c.beqz  a0,.LBB0_4
        c.li    a0,1
        ret
.LBB0_3:
        tail    foo
.LBB0_4:
        tail    bar

With some more effort we could track the value of a0 and save another 2 bytes to generate:

test:
        c.addi  a0,-11
        c.beqz  a0,.LBB0_3
        c.addi  a0,-5. # subtract another 5 to get to the expected -16
        c.beqz  a0,.LBB0_4
        c.li    a0,1
        ret
.LBB0_3:
        tail    foo
.LBB0_4:
        tail    bar

I imagine we would need to add a proper pass for this optimization since doing it in ISel will either generate wasteful code or not be able to optimize the branch. But maybe this becomes unnecessary once Zibi is ratified and widely available.

[preames]

@arichardson Thanks for the nice writeup. Generally agree with all your conclusions.

I'll note that I had tried a version of the simple ISEL patch a few weeks back, but with a slightly different focus. I was interested in whether the decrease in register pressure was enough to impact spill/fill behavior in the register allocator. I've copied the raw data on code size and spill/fill below, but the big picture is there wasn't an obvious benefit.

To give credit where it's due, the data was collected by @lukel97 on my behalf.

Metric: size


Program                                       size                         

                                              lhs         rhs         diff 

FP2017rate/519.lbm_r/519.lbm_r                   22576.00    22576.00  0.0%
INT2017speed/625.x264_s/625.x264_s              525328.00   525040.00 -0.1%
INT2017rate/525.x264_r/525.x264_r               525328.00   525040.00 -0.1%
INT2017rat...23.xalancbmk_r/523.xalancbmk_r    7042576.00  7038656.00 -0.1%
INT2017spe...23.xalancbmk_s/623.xalancbmk_s    7042576.00  7038656.00 -0.1%
FP2017rate/538.imagick_r/538.imagick_r         1869664.00  1868608.00 -0.1%
FP2017speed/638.imagick_s/638.imagick_s        1869664.00  1868608.00 -0.1%
FP2017rate/510.parest_r/510.parest_r          13046048.00 13037904.00 -0.1%
FP2017speed/619.lbm_s/619.lbm_s                  22512.00    22496.00 -0.1%
INT2017rate/520.omnetpp_r/520.omnetpp_r        2735400.00  2733224.00 -0.1%
INT2017spe...ed/620.omnetpp_s/620.omnetpp_s    2735400.00  2733224.00 -0.1%
FP2017rate/526.blender_r/526.blender_r        21111216.00 21094384.00 -0.1%
FP2017rate/508.namd_r/508.namd_r                543616.00   543104.00 -0.1%
FP2017rate/511.povray_r/511.povray_r           1104280.00  1103000.00 -0.1%
INT2017rate/505.mcf_r/505.mcf_r                  30632.00    30584.00 -0.2%
INT2017speed/605.mcf_s/605.mcf_s                 30632.00    30584.00 -0.2%
INT2017rate/541.leela_r/541.leela_r             192344.00   192040.00 -0.2%
INT2017speed/641.leela_s/641.leela_s            192344.00   192040.00 -0.2%
INT2017rate/557.xz_r/557.xz_r                   200192.00   199856.00 -0.2%
INT2017speed/657.xz_s/657.xz_s                  200192.00   199856.00 -0.2%
INT2017rat...31.deepsjeng_r/531.deepsjeng_r      98616.00    98440.00 -0.2%
INT2017spe...31.deepsjeng_s/631.deepsjeng_s      98616.00    98440.00 -0.2%
INT2017rat...00.perlbench_r/500.perlbench_r    2089040.00  2085120.00 -0.2%
INT2017spe...00.perlbench_s/600.perlbench_s    2089040.00  2085120.00 -0.2%
FP2017speed/644.nab_s/644.nab_s                 196648.00   196184.00 -0.2%
FP2017rate/544.nab_r/544.nab_r                  196648.00   196184.00 -0.2%
INT2017rate/502.gcc_r/502.gcc_r                9439648.00  9376464.00 -0.7%
INT2017speed/602.gcc_s/602.gcc_s               9439648.00  9376464.00 -0.7%

                           Geomean difference                         -0.2%



Metric: regalloc.NumSpills,regalloc.NumReloads


Program                                       regalloc.NumSpills                regalloc.NumReloads               

                                              lhs                rhs      diff  lhs                 rhs      diff 

FP2017rate/538.imagick_r/538.imagick_r         3830.00            4081.00  6.6% 10037.00            10665.00  6.3%
FP2017speed/638.imagick_s/638.imagick_s        3830.00            4081.00  6.6% 10037.00            10665.00  6.3%
INT2017spe...ed/620.omnetpp_s/620.omnetpp_s     702.00             736.00  4.8%  1299.00             1332.00  2.5%
INT2017rate/520.omnetpp_r/520.omnetpp_r         702.00             736.00  4.8%  1299.00             1332.00  2.5%
INT2017rate/505.mcf_r/505.mcf_r                 105.00             108.00  2.9%   278.00              262.00 -5.8%
INT2017speed/605.mcf_s/605.mcf_s                105.00             108.00  2.9%   278.00              262.00 -5.8%
INT2017speed/657.xz_s/657.xz_s                  284.00             292.00  2.8%   534.00              534.00  0.0%
INT2017rate/557.xz_r/557.xz_r                   284.00             292.00  2.8%   534.00              534.00  0.0%
FP2017rate/544.nab_r/544.nab_r                  759.00             764.00  0.7%  1107.00             1083.00 -2.2%
FP2017speed/644.nab_s/644.nab_s                 759.00             764.00  0.7%  1107.00             1083.00 -2.2%
FP2017rate/508.namd_r/508.namd_r               6627.00            6652.00  0.4% 15482.00            15457.00 -0.2%
FP2017rate/511.povray_r/511.povray_r           1903.00            1907.00  0.2%  3164.00             3149.00 -0.5%
FP2017speed/619.lbm_s/619.lbm_s                  59.00              59.00  0.0%    73.00               73.00  0.0%
FP2017rate/519.lbm_r/519.lbm_r                   64.00              64.00  0.0%    78.00               78.00  0.0%
INT2017rat...31.deepsjeng_r/531.deepsjeng_r     331.00             330.00 -0.3%   621.00              594.00 -4.3%
INT2017spe...31.deepsjeng_s/631.deepsjeng_s     331.00             330.00 -0.3%   621.00              594.00 -4.3%
INT2017rate/525.x264_r/525.x264_r              1784.00            1772.00 -0.7%  4104.00             4167.00  1.5%
INT2017speed/625.x264_s/625.x264_s             1784.00            1772.00 -0.7%  4104.00             4167.00  1.5%
FP2017rate/510.parest_r/510.parest_r          49074.00           48681.00 -0.8% 85345.00            84777.00 -0.7%
INT2017spe...00.perlbench_s/600.perlbench_s    4234.00            4167.00 -1.6% 10084.00             9821.00 -2.6%
INT2017rat...00.perlbench_r/500.perlbench_r    4234.00            4167.00 -1.6% 10084.00             9821.00 -2.6%
FP2017rate/526.blender_r/526.blender_r        13234.00           13004.00 -1.7% 26048.00            25383.00 -2.6%
INT2017spe...23.xalancbmk_s/623.xalancbmk_s    1656.00            1598.00 -3.5%  2585.00             2511.00 -2.9%
INT2017rat...23.xalancbmk_r/523.xalancbmk_r    1656.00            1598.00 -3.5%  2585.00             2511.00 -2.9%
INT2017speed/602.gcc_s/602.gcc_s              11095.00           10652.00 -4.0% 23871.00            22987.00 -3.7%
INT2017rate/502.gcc_r/502.gcc_r               11095.00           10652.00 -4.0% 23871.00            22987.00 -3.7%
INT2017rate/541.leela_r/541.leela_r             342.00             327.00 -4.4%   497.00              484.00 -2.6%
INT2017speed/641.leela_s/641.leela_s            342.00             327.00 -4.4%   497.00              484.00 -2.6%

                           Geomean difference                              0.1%                              -1.2%

Here's the dynamic results: https://lnt.lukelau.me/db_default/v4/nts/942?compare_to=938

The xalancbmk result might be worth some further investigation.