Missed optimization: Unreachable branch not eliminated due to circular dependency

[rluvaton]

Consider the following rust example (simplified version of pushing to vector with sufficient capacity):

// using const for simplicity, it happen as well if getting it as argument
const COUNT: usize = 10000;

#[no_mangle]
pub fn run() -> usize {
    let mut inter = 0;
    let mut my_cap = COUNT;

    for _ in 0..COUNT {
        let len = inter;

        if len == my_cap {
            something(len);
        }

        inter += 1;
    }

    return inter;
}

#[inline(never)]
fn something(len: usize) {
    std::hint::black_box(len as i128);
}

pub fn main() {
    std::hint::black_box(run());
}

Using rustc nightly with -C opt-level=3 -C target-feature=+avx2 -C codegen-units=1 -Z mir-opt-level=3 in GodBolt
you can see that

if len == my_cap {
    something(len);
}

Is optimized away.

example::main::h86544b4302037868:
        mov     qword ptr [rsp - 8], 10000
        lea     rax, [rsp - 8]
        ret

run:
        mov     eax, 10000
        ret

as the condition can never be reached.

however when changing the body inside the unreachable condition to be:

if len == my_cap {
    something(len);
    my_cap += 1;
}

code after change

const COUNT: usize = 10000;

#[no_mangle]
pub fn run() -> usize {
    let mut inter = 0;
    let mut my_cap = COUNT;

    for _ in 0..COUNT {
        let len = inter;

        if len == my_cap {
            something(len);
            my_cap += 1;
        }

        inter += 1;
    }

    return inter;
}

#[inline(never)]
fn something(len: usize) {
    std::hint::black_box(len as i128);
}

pub fn main() {
    std::hint::black_box(run());
}

You can see that the if is not optimized away

Generated assembly

example::main::h86544b4302037868:
        push    rbx
        sub     rsp, 16
        mov     eax, 10000
        xor     edi, edi
        jmp     .LBB0_1
.LBB0_3:
        mov     rdi, rbx
        cmp     rbx, 10000
        je      .LBB0_4
.LBB0_1:
        lea     rbx, [rdi + 1]
        cmp     rdi, rax
        jne     .LBB0_3
        call    example::something::h16dfb585d2622cee
        mov     rax, rbx
        jmp     .LBB0_3
.LBB0_4:
        mov     qword ptr [rsp + 8], 10000
        lea     rax, [rsp + 8]
        add     rsp, 16
        pop     rbx
        ret

example::something::h16dfb585d2622cee:
        mov     qword ptr [rsp - 24], rdi
        mov     qword ptr [rsp - 16], 0
        lea     rax, [rsp - 24]
        ret

run:
        push    rbx
        mov     eax, 10000
        xor     edi, edi
        jmp     .LBB2_1
.LBB2_3:
        mov     rdi, rbx
        cmp     rbx, 10000
        je      .LBB2_4
.LBB2_1:
        lea     rbx, [rdi + 1]
        cmp     rdi, rax
        jne     .LBB2_3
        call    example::something::h16dfb585d2622cee
        mov     rax, rbx
        jmp     .LBB2_3
.LBB2_4:
        mov     eax, 10000
        pop     rbx
        ret

---

I tried testing in C++ with x86-64 clang 21.1.0 and -O3 and same result.

(I don't really know cpp, so I tried my best to replicate the rust code)

the code:

#include <cstddef>
#include <cstdio>

const size_t COUNT = 10000;

__attribute__((noinline))
void something(size_t len) {
    printf("%d", len);
    (void)len;
}

extern "C" size_t run() {
    size_t inter = 0;
    size_t my_cap = COUNT;

    for (size_t i = 0; i < my_cap; ++i) {
        size_t len = inter;

        if (len == my_cap) {
            something(len);
            my_cap += 1;
        }

        inter += 1;
    }
    

    return inter;
}

int main() {
    volatile size_t result = run();
    (void)result;
    return 0;
}

Produce the following assembly:

something(unsigned long):
        mov     rsi, rdi
        lea     rdi, [rip + .L.str]
        xor     eax, eax
        jmp     printf@PLT

run:
        mov     rax, -25
.LBB1_1:
        add     rax, 25
        cmp     rax, 9975
        jb      .LBB1_1
        add     rax, 25
        ret

main:
        mov     qword ptr [rsp - 8], 10000
        mov     rax, qword ptr [rsp - 8]
        xor     eax, eax
        ret

.L.str:
        .asciz  "%d"

.Ldebug_list_header_start0:
        .short  5
        .byte   8
        .byte   0
        .long   3
.Ldebug_list_header_end0:

Using x86-64 gcc 15.2 with -O3 however do optimize it:

.LC0:
        .string "%d"
something(unsigned long):
        mov     rsi, rdi
        xor     eax, eax
        mov     edi, OFFSET FLAT:.LC0
        jmp     printf
run:
        mov     eax, 10000
        ret
main:
        mov     QWORD PTR [rsp-8], 10000
        mov     rax, QWORD PTR [rsp-8]
        xor     eax, eax
        ret

[tgross35]

Reduced the original input a bit https://godbolt.org/z/Pq4TGn6eb

#[unsafe(no_mangle)]
pub fn run() -> u32 {
    const COUNT: u32 = 1000;
    let mut a = 0;
    let mut b = 0;
    let mut my_cap = COUNT;

    while a < COUNT {
        if b == my_cap {
            core::intrinsics::black_box(());
            my_cap += 1;
        }

        a += 1;
        b += 1;
    }

    a // or b
}

So I think it's having difficulty figuring out that a and b are always equal.

Unoptimized ir:

define i32 @run() unnamed_addr {
start:
  %my_cap = alloca [4 x i8], align 4
  %b = alloca [4 x i8], align 4
  %a = alloca [4 x i8], align 4
  store i32 0, ptr %a, align 4
  store i32 0, ptr %b, align 4
  store i32 1000, ptr %my_cap, align 4
  br label %bb1

bb1:
  %_5 = load i32, ptr %a, align 4
  %_4 = icmp ult i32 %_5, 1000
  br i1 %_4, label %bb2, label %bb6

bb6:
  %_0 = load i32, ptr %a, align 4
  ret i32 %_0

bb2:
  %_7 = load i32, ptr %b, align 4
  %_8 = load i32, ptr %my_cap, align 4
  %_6 = icmp eq i32 %_7, %_8
  br i1 %_6, label %bb3, label %bb5

bb5:
  %0 = load i32, ptr %a, align 4
  %1 = add i32 %0, 1
  store i32 %1, ptr %a, align 4
  %2 = load i32, ptr %b, align 4
  %3 = add i32 %2, 1
  store i32 %3, ptr %b, align 4
  br label %bb1

bb3:
  call void asm sideeffect "", "~{memory}"()
  %4 = load i32, ptr %my_cap, align 4
  %5 = add i32 %4, 1
  store i32 %5, ptr %my_cap, align 4
  br label %bb5
}

[tgross35]

Reduced a bit further https://llvm.godbolt.org/z/5jKdWPf87. Without the call to opaque (or asm sideeffect via black_box in the original example), SimplifyCFG is able to inline do_side_effect to a select, which makes it easy to merge to a single bb allowing a and b to be combined in IndVarSimplify https://llvm.godbolt.org/z/o5r9YPGTc. With the call to opaque it becomes much harder to merge a and b because the needed information is spread across blocks.

define i32 @run() unnamed_addr {
start:
  %b_limit_ptr = alloca [4 x i8]
  %bptr = alloca [4 x i8]
  %aptr = alloca [4 x i8]
  store i32 0, ptr %aptr
  store i32 0, ptr %bptr
  store i32 1000, ptr %b_limit_ptr
  br label %loop_condition

; break if a >= 1000
loop_condition:
  %a = load i32, ptr %aptr
  %done = icmp uge i32 %a, 1000
  br i1 %done, label %do_ret, label %loop_body1

; if b == b_limit, do some side effect that touches b_limit
loop_body1:
  %b = load i32, ptr %bptr
  %b_limit = load i32, ptr %b_limit_ptr
  ; this is never true; `b_limit` is initialized to 1000 but incremented
  ; with `a`. If `a` is 1000, the loop breaks before this bb. `b_limit`
  ; is never modified unless this is true.
  %should_branch = icmp eq i32 %b, %b_limit
  br i1 %should_branch, label %do_side_effect, label %loop_body2

; this is unreachable
do_side_effect:
  call void @opaque() ; commenting this enables the optimization
  %b_limit2 = load i32, ptr %b_limit_ptr
  store i32 9, ptr %b_limit_ptr
  br label %loop_body2

; increment both a and b then unconditionally restart the loop
loop_body2:
  %a2 = load i32, ptr %aptr
  %b2 = load i32, ptr %bptr
  %next_a = add i32 %a2, 1
  %next_b = add i32 %b2, 1
  store i32 %next_a, ptr %aptr
  store i32 %next_b, ptr %bptr
  br label %loop_condition

do_ret:
  ret i32 1
}

declare void @opaque() unnamed_addr

[rluvaton]

I want to have black_box as it should not matter, for example if you replace black_box with println!("hello"); it will still not optimize even though the print does not touch any of the variables.

also I want to use black_box to make sure that no matter the unreachable if body it will still be eliminated

[rluvaton]

I had an idea that what if we assume that unreachable body does touch any variables, check if the if is unreachable and if so remove it.

I have an idea for a fix but there is probably a better one.

What if for every if in the loop we will ignore the body of it.
then, check which conditions can be true.
for those conditions, add the body back, and check again, which conditions are reachable.
doing this until we no longer have any reachable condition. the rest that still have their body ignored are unreachable.

Example of the flow

Example:

#[no_mangle]
pub fn run() -> usize {
    let mut inter = 0;
    let mut my_cap = COUNT;

    for _ in 0..COUNT {
        let len = inter;

        if len == my_cap {
            my_cap += 1;
            something(len);
        }

        if my_cap > COUNT {
            my_cap += 10;
            something(len);
        }

        if len < my_cap {
			inter += 1;
		} 
        
        if len == inter {
            something(len);
        }
    }

    return inter;
}

it will get all the conditions that are in that closure:

if len == my_cap {
    my_cap += 1;
    something(len);
}

if my_cap > COUNT {
    my_cap += 10;
    something(len);
}

if len < my_cap {
  inter += 1;
} 

if len == inter {
  something(len);
}

and it will change the body of all ifs to be black box that doesn't modify anything:

#[no_mangle]
pub fn run() -> usize {
    let mut inter = 0;
    let mut my_cap = COUNT;

    for _ in 0..COUNT {
        let len = inter;

        if len == my_cap {
            // black box that doesn't modify anything
        }

        if my_cap > COUNT {
            // black box that doesn't modify anything
        }

        if len < my_cap {
            // black box that doesn't modify anything
		}

        if len == inter {
            // black box that doesn't modify anything
        }
    }

    return inter;
}

and then will check what conditions can be true and for those conditions add back the body

#[no_mangle]
pub fn run() -> usize {
    let mut inter = 0;
    let mut my_cap = COUNT;

    for _ in 0..COUNT {
        let len = inter;

        if len == my_cap {
            // black box that doesn't modify anything
        }

        if my_cap > COUNT {
            // black box that doesn't modify anything
        }

        if len < my_cap {
            inter += 1;
        }

        if len == inter {
            something(len);
        }
    }

    return inter;
}

and check again what conditions can be true from the conditions that still have black box:

because no other condition that still have black box can be true anymore, they are considered unreachable.

so in this case the following 2 conditions are marked as unreachable

// unreachable
if len == my_cap {
    my_cap += 1;
    something(len);
}

// unreachable
if my_cap > COUNT {
    my_cap += 10;
    something(len);
}

(note that the last if is not marked as unreachable in this case even though it is but the current optimizations should handle that)

[tgross35]

Repro that doesn't rely on an opaque call. Possibly a slightly different cause https://gcc.godbolt.org/z/ozeTY7vG7:

#define COUNT 100

int run() {
    int a = 0;
    int b = 0;
    int limit = COUNT;

    while(a < limit) {
        if (b == limit) {
            limit += 1;
        }

        b += 1;
        a += 1;
    }
    
    return a;
}

run:
        xor     eax, eax
        mov     ecx, 100
.LBB0_1:
        xor     edx, edx
        cmp     eax, ecx
        sete    dl
        add     ecx, edx
        inc     eax
        cmp     eax, ecx
        jb      .LBB0_1
        ret

I have to imagine there is an issue open for this somewhere but I'm not having any luck searching.

[rluvaton]

I should fix my GitHub notifications, I just got that as well.

For this rust code:

#[unsafe(no_mangle)]
pub fn src() -> u32 {
    const COUNT: u32 = 50;
    let mut a = 0;
    let mut b = 0;

    while a < COUNT {
        if b == COUNT {
            a += 1;
        }

        a += 1;
        b += 1;
    }

    a
}

fn main() {
    src();
}

The unoptimized LLVM IR:

define i32 @run() unnamed_addr {
start:
  %bptr = alloca [4 x i8]
  %aptr = alloca [4 x i8]
  store i32 0, ptr %aptr
  store i32 0, ptr %bptr
  br label %loop_condition

; break if a >= 1000
loop_condition:
  %a = load i32, ptr %aptr
  %done = icmp uge i32 %a, 1000
  br i1 %done, label %do_ret, label %loop_body1

; if b == 1000, do some side effect that touches a
loop_body1:
  %b = load i32, ptr %bptr
  ; this is never true; `b` is incremeneted with `a`.
  ; If `a` is 1000, the loop breaks before this bb.
  %should_branch = icmp eq i32 %b, 1000
  br i1 %should_branch, label %do_side_effect, label %loop_body2

; this is unreachable
do_side_effect:
  ; a += 1
  %a_2 = load i32, ptr %aptr, align 4
  %a_updated = add i32 %a_2, 1
  store i32 %a_updated, ptr %aptr, align 4
  
  br label %loop_body2

; increment both a and b then unconditionally restart the loop
loop_body2:
  %a2 = load i32, ptr %aptr
  %b2 = load i32, ptr %bptr
  %next_a = add i32 %a2, 1
  %next_b = add i32 %b2, 1
  store i32 %next_a, ptr %aptr
  store i32 %next_b, ptr %bptr
  br label %loop_condition

do_ret:
  ret i32 1
}

produce this after optimization (not optimizing away the if):

define noundef i32 @run() unnamed_addr {
start:
  br label %loop_body1

loop_body1:                                       ; preds = %start, %loop_body1
  %aptr.sroa.0.05 = phi i32 [ 0, %start ], [ %next_a, %loop_body1 ]
  %bptr.sroa.0.04 = phi i32 [ 0, %start ], [ %next_b, %loop_body1 ]
  %should_branch = icmp eq i32 %bptr.sroa.0.04, 1000
  %a_updated = zext i1 %should_branch to i32
  %spec.select = add nuw nsw i32 %aptr.sroa.0.05, 1
  %next_a = add nuw nsw i32 %spec.select, %a_updated
  %next_b = add i32 %bptr.sroa.0.04, 1
  %done = icmp samesign ugt i32 %next_a, 999
  br i1 %done, label %do_ret, label %loop_body1

do_ret:                                           ; preds = %loop_body1
  ret i32 1
}

[rluvaton]

In my example the IndVarSimplify is not even used as I think a changed inside the if.

and GCC is not able to optimize it as well