Miscompilation of lbzip2 after loop-vectorize pass for avx512

[AngryLoki]

Hi, it was originally reported in https://bugs.gentoo.org/910438 that lbzip2 compiled by clang for AVX-512 platforms produces corrupted bz2 files.

I tried to check with the following results:

1. after adding -fsanitize=undefined,address issue fully disappears (i. e. produced files are correct and no complaints from sanitizers).
2. minimal flags to reproduce with clangs are -mavx512f -fvectorize -O1.
3. With OptBisect I see that the pass, which breaks code is LoopVectorizePass. If I compile all C files to LLVM bc with -O0 and apply opt -passes=loop-vectorize -mcpu=znver4 to encode.c, resulting bz2 files are corrupted:

clang -c -emit-llvm -mavx512f -O1 -DHAVE_CONFIG_H -Isrc -Ilib src/encode.c -o src/encode.o
opt -passes=loop-vectorize -mcpu=znver4 src/encode.o -o src/encode.opt.o

4. if I set __attribute__ ((optnone)) to all functions in encode.c, code is correct. To produce the issue, it is enough to apply optimizations only to assign_codes and generate_prefix_code.
5. no issues with clang/avx256 or gcc/avx512

I attach partially compiled lbzip2.bc and testing compressme file here: lbzip2.zip, which breaks after loop-vectorize with almost any file:

# with llvm release 17 or 18
opt -passes=loop-vectorize -mcpu=znver4 lbzip2.bc -o lbzip2.opt.bc  # <--
clang -O0 lbzip2.opt.bc -o lbzip2
./lbzip2 -z -k compressme
bzip2 -d -t compressme.bz2

> bzip2: ../environment.bz2: data integrity (CRC) error in data
> You can use the `bzip2recover' program to attempt to recover
> data from undamaged sections of corrupted files.

[dtcxzyw]

cc @fhahn

[fhahn]

@AngryLoki what version of clang are you using? Looking at the IR that gets vectorized the issue may be fixed by c2c1e6e. Could you try with a build from current main?

[AngryLoki]

@fhahn , the issue is still reproducible with a8b0ecd (2024-03-30) toolchain.

[AngryLoki]

Upd: I added #pragma clang loop vectorize(disable) to almost all loops in assign_codes and generate_prefix_code.

What remained to reproduce was:

1. assign_codes must be inlined
2. only one loop must be vectorized:

  // types: uint32_t *code; uint32_t symbol; uint32_t base_code[21]; uint8_t *length; uint32_t as;

  for (symbol = 0; symbol < as; symbol++)
    code[symbol] = base_code[length[symbol]]++;

Produced LLVM code

  %found.conflict = and i1 %bound0, %bound1
  br i1 %found.conflict, label %vec.epilog.scalar.ph, label %vector.main.loop.iter.check

vector.main.loop.iter.check:                      ; preds = %vector.memcheck
  %min.iters.check5 = icmp ult i64 %wide.trip.count525, 16
  br i1 %min.iters.check5, label %vec.epilog.ph, label %vector.ph

vector.ph:                                        ; preds = %vector.main.loop.iter.check
  %n.mod.vf = urem i64 %wide.trip.count525, 16
  %n.vec = sub i64 %wide.trip.count525, %n.mod.vf
  br label %vector.body

vector.body:                                      ; preds = %vector.body, %vector.ph
  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
  %46 = add i64 %index, 0
  %47 = getelementptr inbounds i8, ptr %arrayidx190, i64 %46
  %48 = getelementptr inbounds i8, ptr %47, i32 0
  %wide.load = load <16 x i8>, ptr %48, align 1, !tbaa !23, !alias.scope !63
  %49 = zext <16 x i8> %wide.load to <16 x i64>
  %50 = getelementptr inbounds [21 x i32], ptr %base_code.i, i64 0, <16 x i64> %49
  %wide.masked.gather = call <16 x i32> @llvm.masked.gather.v16i32.v16p0(<16 x ptr> %50, i32 4, <16 x i1> <i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true>, <16 x i32> poison), !tbaa !14
  %51 = add <16 x i32> %wide.masked.gather, <i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1>
  call void @llvm.masked.scatter.v16i32.v16p0(<16 x i32> %51, <16 x ptr> %50, i32 4, <16 x i1> <i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true>), !tbaa !14
  %52 = getelementptr inbounds i32, ptr %arrayidx185, i64 %46
  %53 = getelementptr inbounds i32, ptr %52, i32 0
  store <16 x i32> %wide.masked.gather, ptr %53, align 4, !tbaa !14, !alias.scope !66, !noalias !63
  %index.next = add nuw i64 %index, 16
  %54 = icmp eq i64 %index.next, %n.vec
  br i1 %54, label %middle.block, label %vector.body, !llvm.loop !68

middle.block:                                     ; preds = %vector.body
  %cmp.n = icmp eq i64 %wide.trip.count525, %n.vec
  br i1 %cmp.n, label %assign_codes.exit, label %vec.epilog.iter.check

vec.epilog.iter.check:                            ; preds = %middle.block
  %n.vec.remaining = sub i64 %wide.trip.count525, %n.vec
  %min.epilog.iters.check = icmp ult i64 %n.vec.remaining, 8
  br i1 %min.epilog.iters.check, label %vec.epilog.scalar.ph, label %vec.epilog.ph

vec.epilog.ph:                                    ; preds = %vector.main.loop.iter.check, %vec.epilog.iter.check
  %vec.epilog.resume.val = phi i64 [ %n.vec, %vec.epilog.iter.check ], [ 0, %vector.main.loop.iter.check ]
  %n.mod.vf6 = urem i64 %wide.trip.count525, 8
  %n.vec7 = sub i64 %wide.trip.count525, %n.mod.vf6
  br label %vec.epilog.vector.body

vec.epilog.vector.body:                           ; preds = %vec.epilog.vector.body, %vec.epilog.ph
  %index9 = phi i64 [ %vec.epilog.resume.val, %vec.epilog.ph ], [ %index.next12, %vec.epilog.vector.body ]
  %55 = add i64 %index9, 0
  %56 = getelementptr inbounds i8, ptr %arrayidx190, i64 %55
  %57 = getelementptr inbounds i8, ptr %56, i32 0
  %wide.load10 = load <8 x i8>, ptr %57, align 1, !tbaa !23, !alias.scope !71
  %58 = zext <8 x i8> %wide.load10 to <8 x i64>
  %59 = getelementptr inbounds [21 x i32], ptr %base_code.i, i64 0, <8 x i64> %58
  %wide.masked.gather11 = call <8 x i32> @llvm.masked.gather.v8i32.v8p0(<8 x ptr> %59, i32 4, <8 x i1> <i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true>, <8 x i32> poison), !tbaa !14
  %60 = add <8 x i32> %wide.masked.gather11, <i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1>
  call void @llvm.masked.scatter.v8i32.v8p0(<8 x i32> %60, <8 x ptr> %59, i32 4, <8 x i1> <i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true>), !tbaa !14
  %61 = getelementptr inbounds i32, ptr %arrayidx185, i64 %55
  %62 = getelementptr inbounds i32, ptr %61, i32 0
  store <8 x i32> %wide.masked.gather11, ptr %62, align 4, !tbaa !14, !alias.scope !74, !noalias !71
  %index.next12 = add nuw i64 %index9, 8
  %63 = icmp eq i64 %index.next12, %n.vec7
  br i1 %63, label %vec.epilog.middle.block, label %vec.epilog.vector.body, !llvm.loop !76

vec.epilog.middle.block:                          ; preds = %vec.epilog.vector.body
  %cmp.n8 = icmp eq i64 %wide.trip.count525, %n.vec7
  br i1 %cmp.n8, label %assign_codes.exit, label %vec.epilog.scalar.ph

vec.epilog.scalar.ph:                             ; preds = %vector.memcheck, %iter.check, %vec.epilog.iter.check, %vec.epilog.middle.block
  %bc.resume.val = phi i64 [ %n.vec7, %vec.epilog.middle.block ], [ %n.vec, %vec.epilog.iter.check ], [ 0, %vector.memcheck ], [ 0, %iter.check ]
  br label %for.body171.i

with gather.v16, add <16 x i32>, scatter.v16, gather.v8, add <8 x i32>, scatter.v8, then scalar, which at least on high level looks valid. Not sure if it helps, but if somebody experienced similar issues with masked gather/scatter, then they may check this issue as well.

[fhahn]

@AngryLoki thanks for checking with the latest version, could you also share the IR for the whole module before the LoopVectorize runs on the function? Then I can take a closer look

[AngryLoki]

@fhahn please check define dso_local i32 @generate_prefix_code

1. encode.noopt.ll.txt
2. encode.opt.ll.txt - same file after opt -S -passes=loop-vectorize -mcpu=znver4

I wrapped that loop with LLVM-MCA markers to make it easier to find.

[fhahn]

Ok, I think I tracked down the issue. Added a test case and hopefully a fix as well soon