Const loop not folded

[ZuseZ4]

Originally encountered on the Julia Slack, then discussed a bit on the Rust Discord.
The following loop has no side effects and should be simple enough to fold, yet both clang and rustc end up with a phi node.
https://godbolt.org/z/16rG5bjz9

unsigned long foo() {
    unsigned long max = 1000000000;
    unsigned long total = 0;
    
    for (unsigned long i = 0; i < max; i++) {
        total = i;
    }
    return total;
}

under -O3 and -S -emit-llvm gives

define dso_local noundef i64 @foo()() local_unnamed_addr #0 !dbg !10 {
entry:
    #dbg_value(i64 1000000000, !16, !DIExpression(), !20)
    #dbg_value(i64 0, !17, !DIExpression(), !20)
    #dbg_value(i64 0, !18, !DIExpression(), !21)
  br label %vector.body, !dbg !22

vector.body:
  %index = phi i64 [ 0, %entry ], [ %index.next.9, %vector.body ], !dbg !23
  %0 = phi i64 [ 15, %entry ], [ %1, %vector.body ], !dbg !23
  %index.next.9 = add nuw nsw i64 %index, 320, !dbg !23
  %1 = add nuw nsw i64 %0, 320, !dbg !23
  %2 = icmp eq i64 %index.next.9, 1000000000, !dbg !23
  br i1 %2, label %for.cond, label %vector.body, !dbg !23

for.cond:
  %vector.recur.extract = add nuw i64 %0, 304
    #dbg_value(i64 1000000000, !18, !DIExpression(), !21)
    #dbg_value(i64 1000000000, !17, !DIExpression(), !20)
    #dbg_value(i64 1000000001, !18, !DIExpression(), !21)
  ret i64 %vector.recur.extract, !dbg !30
}

attributes #0 = { mustprogress nofree norecurse nosync nounwind willreturn memory(none) uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

The resulting asm is:

foo():
        mov     rax, -1
.LBB0_1:
        add     rax, 320
        cmp     rax, 999999999
        jne     .LBB0_1
        ret

compared to GCC, which just has a

foo():
        mov     eax, 999999999
        ret

Here the pass that looks suspicious (thanks to @scottmcm) https://rust.godbolt.org/z/dG9far1dW
Tbh. it looks like a fun issue, so if someone gives me a hint on where to fix it, I could start trying to come up with a fix next week.

[nikic]

Pretty sure we have a few duplicates of this filed already, but I can't find any of them.

The problem here is that SCEV cannot determine the exit value of total (https://llvm.godbolt.org/z/ns9hY3bdW). This specific case should be easy to fix on the SCEV side if you use the fact that we have a known non-zero backedge taken count, so you can use the backedge value of the phi only, which is an addrec.

The case where the backedge taken count can be zero would be trickier, as that would actually require determining a different exit value depending on whether it is zero or not.

[ZuseZ4]

Thanks, that sounds quite doable for this case at least, I will look into it.

[folkertdev]

I have a variation on this, it looks very similar, lmk if it deserves its own issue. The interesting thing about it is that clang 19 and rustc 1.82.0 do something different for effectively the same input LLVM IR.

• rust godbolt: https://godbolt.org/z/6K34o3daP
• c godbolt: https://godbolt.org/z/b996Trr8W
• alive2: https://alive2.llvm.org/ce/z/bropcd

The offending code is

#[no_mangle]
pub unsafe extern "C" fn b(mut c: i32, mut d: i32) {
    while c <= d {
        c += 1;
    }
}

The equivalent C code

void b(int c, int d) {
  for (int e = c; e <= d; e++);
}

optimizes to just a ret instruction, but the rust version does not:

b:
        dec     edi
.LBB0_1:
        inc     edi
        cmp     edi, esi
        jle     .LBB0_1
        ret

We can get rust to emit just a ret by using

#[no_mangle]
pub unsafe extern "C" fn b(mut c: i32, mut d: i32) {
    while c <= d {
        c = c.unchecked_add(1);
    }
}

So at first, what looks like is happening here is an optimization based on signed integer overflows being UB in C, and not in rust. And I think that is part of it, but not the whole story. In clang, the -fwrapv flag makes arithmetic wrap (i.e. it's not UB any more) and C still generates just the ret.

Based on alive2, the transformation is valid for just a standard add:

https://alive2.llvm.org/ce/z/bropcd

By looking at the llvm optimization pipelines, we can see when the two languages diverge. This turns out to be in the LoopDeletionPass which does have an effect on the C code, but not on the rust code. But I think this loop can be removed, it seems to fit the description of that llvm pass anyway

file implements the Dead Loop Deletion Pass. This pass is responsible
for eliminating loops with non-infinite computable trip counts that have no
side effects or volatile instructions, and do not contribute to the
computation of the function's return value.

https://llvm.org/doxygen/LoopDeletion_8cpp_source.html

[nikic]

@folkertdev Optimizing away this loop requires either no signed wrap or the forward progress guarantee. In Rust, the loop cannot be optimized away because it may be infinite, if d it i32::MAX.

This has no relation to this issue at all.