Adding assert defeats optimisation

[WeeBull]

Just a quick observation that I think might be a bug. If I have the following function:

const assert = @import("std").debug.assert;

export fn find_msb(val: usize) usize {
    // assert(val != 0);
    var v = val;
    var r:usize = 0;
    
    while (v != 0) : (v >>= 1) {
        r += 1;
    }
    return r;
}

It compiles to: ^[1]

example.find_msb:
        lzcnt   rcx, rdi
        mov     eax, 64
        sub     rax, rcx
        test    rdi, rdi
        cmove   rax, rdi
        ret

find_msb = example.find_msb

1. Count the leading zeros
2. Subtract that from 64
3. Check if the answer is zero (i.e. 64 leading zeros… function has zero as an input)
4. If so, overwrite the result with zero
5. Return the result.

(Trunk doesn’t do 3 & 4)

Seeing this, I thought I’d add an assert (commented out above) to say the input is never zero, so no need to check for it. I got this result:

example.find_msb:
        xor     eax, eax
.LBB0_1:
        inc     rax
        shr     rdi
        jne     .LBB0_1
        ret

find_msb = example.find_msb

It’s now a basic loop and doesn’t use the lzcnt instruction^[2]. Why would reducing the set of valid inputs defeat an optimisation?

Compiler Explorer - Zig

---

1. 0.17 -O fast ↩︎

2. Trunk does the same ↩︎

[matklad]

Fascinating! Worth comparing

    if (val == 0) unreachable;
    if (val == 0) return @as([]const usize, &.{val})[1];

where the former is assert, and the latter is “we have unreachable at home”.

The latter version results in

example.find_msb:
        lzcnt   rcx, rdi
        mov     eax, 64
        sub     rax, rcx
        ret

So something in unreachable is distinguishable from pure UB.

Compiler Explorer - Zig

[BruceMcRooster]

Also interesting: moving the assert after the loop can remove the check. My hunch is something along the lines of LLVM pattern recognition getting messed up by the early check, then once it makes the conversion it can drop the check given the unreachable information. But I’m not crazy up on LLVM inner workings so I don’t know.

Compiler Explorer - Zig (zig 0.17.0)

const assert = @import("std").debug.assert;

export fn find_msb(val: usize) usize {
    var v = val;
    var r:usize = 0;
    
    while (v != 0) : (v >>= 1) {
        r += 1;
    }

    assert(val != 0);
    return r;
}

example.find_msb:
        lzcnt   rcx, rdi
        mov     eax, 64
        sub     rax, rcx
        ret

[matklad]

branch hint also confuses it:

   if (val == 0) {
        @branchHint(.cold);
        return unreachable_at_home(val);
    }

[tholmes]

There’s also the superior undefined behaviour:
if(val == 0) return undefined;

[matklad]

I believe return undefined is not illegal behavior. It’s fine to have undefined data, its only becomes illegal if you branch on it .

[pzittlau]

Why not:

export fn findMsb(val: usize) usize {
    return @as(usize, @bitSizeOf(usize)) - @clz(val);
}

Which outputs(the same as @matklad )

example.findMsb:
        lzcnt   rcx, rdi
        mov     eax, 64
        sub     rax, rcx
        ret

Edit: my bad. I didn’t notice that it was more about the optimizer than on how to implement it.

[WeeBull]

@pzittlau

Edit: my bad. I didn’t notice that it was more about the optimizer than on how to implement it.

Exactly. I knew that assertions could alter optimisation, but this is the first time I’ve seen it have a negative effect. Certainly seems to have a few people thinking.

@matklad

if (val == 0) return @as([]const usize, &.{val})[1];

I don’t think I follow why this isn’t just a guard clause. Can you explain?

@BruceMcRooster

Also interesting: moving the assert after the loop can remove the check. My hunch is something along the lines of LLVM pattern recognition getting messed up by the early check, then once it makes the conversion it can drop the check given the unreachable information. But I’m not crazy up on LLVM inner workings so I don’t know.

I’m thinking along the same lines. Is there some kind of IR that might show the difference? I’d quite like to understand what’s breaking.

[castholm]

@WeeBull

Is there some kind of IR that might show the difference?

You can pass -femit-llvm-ir but I’m not sure of how much use this is because it shows the result after all LLVM optimization passes, so it’s more or less the same as machine code.

Without the assert:

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none) uwtable
define internal range(i64 0, 65) i64 @repro2.find_msb(i64 %0) unnamed_addr #0 !dbg !18 {
Entry:
    #dbg_value(i64 %0, !23, !DIExpression(), !24)
    #dbg_value(i64 %0, !25, !DIExpression(), !26)
    #dbg_value(i64 0, !27, !DIExpression(), !26)
  %1 = tail call range(i64 0, 65) i64 @llvm.ctlz.i64(i64 %0, i1 false), !dbg !28
  %2 = sub nuw nsw i64 64, %1, !dbg !28
  ret i64 %2, !dbg !32
}

With the assert:

; Function Attrs: nofree norecurse nosync nounwind memory(inaccessiblemem: write) uwtable
define internal range(i64 1, 0) i64 @repro2.find_msb(i64 %0) unnamed_addr #0 !dbg !18 {
Entry:
    #dbg_value(i64 %0, !23, !DIExpression(), !24)
  %1 = icmp ne i64 %0, 0, !dbg !25
    #dbg_value(i1 true, !26, !DIExpression(), !33)
  tail call void @llvm.assume(i1 %1), !dbg !35
    #dbg_value(i64 %0, !37, !DIExpression(), !38)
    #dbg_value(i64 0, !39, !DIExpression(), !38)
  br label %Then, !dbg !40

Then:                                             ; preds = %Entry, %Then
  %.06 = phi i64 [ %0, %Entry ], [ %3, %Then ]
  %.045 = phi i64 [ 0, %Entry ], [ %2, %Then ]
    #dbg_value(i64 %.06, !37, !DIExpression(), !38)
    #dbg_value(i64 %.045, !39, !DIExpression(), !38)
  %2 = add nuw nsw i64 %.045, 1, !dbg !44
    #dbg_value(i64 %2, !39, !DIExpression(), !38)
  %3 = lshr i64 %.06, 1, !dbg !46
    #dbg_value(i64 %3, !37, !DIExpression(), !38)
  %.not = icmp eq i64 %3, 0, !dbg !40
  br i1 %.not, label %Else, label %Then, !dbg !40

Else:                                             ; preds = %Then
  ret i64 %2, !dbg !48
}

[TibboddiT]

FYI, I think this LLVM PR (merged on Sep. 10) is related.

For convenience I’m reproducing the description here:

---

LoopIdiomRecognize converts a shift-until-zero loop to ctlz/cttz. When the loop uses the count outside the loop, it needs a zero check of the input before the loop. Without the check, the inputs 0 and 1 give the same count. The recognizer stops when the check is not present.

The check is not necessary when the input is known non-zero. InstCombine can remove the check for such inputs. Then the recognizer does not convert the loop. This happens in sbc_calc_scalefactors from ffmpeg with #222334: the input is an or reduction that starts at 32768, so it is never zero, and the loop stays a loop.

This patch makes the recognizer accept a known non-zero input in place of the zero check. The conversion is exact in this case.

ctlz-loop.ll in PhaseOrdering had a FIXME for a loop over abs(n). The recognizer now converts that loop too.

For the ffmpeg case, isKnownNonZero must also see that an or recurrence with a non-zero start is non-zero. That change goes into #222334.

---

IIUC, it seems the assert before the loop is suppressing the zero check, which then makes the pattern recognition fail. Note the irony.

[matklad]

@WeeBull

I don’t think I follow why this isn’t just a guard clause. Can you explain?

This access [1] index of array with length 1. That is, it is an out-of-bounds array access, which is illegal behavior in the release, and allows LLMV to optimize under assumption that this code path is not reachable.

In other words, it should be the same thing as assume(val != 0) or assert(val != 0) or if (val == 0) unreachable.

The reason why it’s written that way is because something simpler like val / 0 gets rejected by the zig compiler itself.