Invalid optimization around loops

[Noratrieb]

come from rust-lang/rust#112061

alive2 complains about an optimization in the LLVM IR: https://alive2.llvm.org/ce/z/fyzhJ3

The code is quite big and I have made attempts to minimize it, but I didn't quite figure out the tooling, so I'm not sure whether my not very good minimizations would be useful. Everything can be found on https://github.com/Nilstrieb/rlo-issue-112061 if desired.

The program prints 11 on O0/O1 and 22 on O2.

This small helper must be linked in to run the program:

#include <stdio.h>
#include <stdint.h>

void print_var(uint8_t x) {
    printf("%d", x);
}

void fn12_rs();

int main() {
    fn12_rs();
}

I can't say for sure that the IR emitted by rustc is free of UB, but I suspect that this is the case. The code is really sensitive to small changes and rustc's constant propagation pass actually masks the miscompilation and has to be disabled.

@cbeuw suggested running LLVM built with ASan because they were facing crashes on similar input (#63013), but it did not show any issues.

[efriedma-quic]

You might want to try using opt-bisect-limit (https://llvm.org/docs/OptBisect.html) to reduce this.

[nikic]

Reduced:

; RUN: opt -S -passes=gvn < %s
define i8 @src(i64 %offset, ptr %ptr) {
start:
  %alloca = alloca [8 x i8], align 8
  store i64 u0x1122334455667788, ptr %alloca, align 8
  %gep.2 = getelementptr i8, ptr %alloca, i64 2
  %gep.unknown = getelementptr i8, ptr %alloca, i64 %offset
  br label %bb

unreachable:
  br label %bb

bb:
  %phi = phi ptr [ %gep.unknown, %start ], [ %gep.2, %unreachable ]
  store i8 0, ptr %alloca, align 8
  %load1 = load i64, ptr %alloca, align 8
  store i64 %load1, ptr %ptr, align 8
  %load2 = load i8, ptr %phi, align 1
  ret i8 %load2
}

Produces:

define i8 @src(i64 %offset, ptr %ptr) {
start:
  %alloca = alloca [8 x i8], align 8
  store i64 1234605616436508552, ptr %alloca, align 8
  %gep.2 = getelementptr i8, ptr %alloca, i64 2
  %gep.unknown = getelementptr i8, ptr %alloca, i64 %offset
  br label %bb

unreachable:                                      ; No predecessors!
  br label %bb

bb:                                               ; preds = %unreachable, %start
  %phi = phi ptr [ %gep.unknown, %start ], [ %gep.2, %unreachable ]
  store i8 0, ptr %alloca, align 8
  %load1 = load i64, ptr %alloca, align 8
  store i64 %load1, ptr %ptr, align 8
  %0 = lshr i64 %load1, 16
  %1 = trunc i64 %0 to i8
  ret i8 %1
}

Note how the extract is at offset 2 rather than offset %offset.

Edit: This also works without the unreachable predecessor. This is a slightly more natural test case:

define i8 @src(i1 %c, i64 %offset, ptr %ptr) {
start:
  %alloca = alloca [8 x i8], align 8
  store i64 u0x1122334455667788, ptr %alloca, align 8
  %gep.2 = getelementptr i8, ptr %alloca, i64 2
  %gep.unknown = getelementptr i8, ptr %alloca, i64 %offset
  br i1 %c, label %join, label %if

if:
  br label %join

join:
  %phi = phi ptr [ %gep.unknown, %start ], [ %gep.2, %if ]
  store i8 0, ptr %alloca, align 8
  %load1 = load i64, ptr %alloca, align 8
  store i64 %load1, ptr %ptr, align 8
  %load2 = load i8, ptr %phi, align 1
  ret i8 %load2
}

[nikic]

The AA trace contains this:

  End   %gep.unknown = getelementptr i8, ptr %alloca, i64 %offset @ LocationSize::precise(1),   %alloca = alloca [8 x i8], align 8 @ LocationSize::precise(8) = PartialAlias
[...]
  End   %gep.2 = getelementptr i8, ptr %alloca, i64 2 @ LocationSize::precise(1),   %alloca = alloca [8 x i8], align 8 @ LocationSize::precise(8) = PartialAlias (off -2)
End   %alloca = alloca [8 x i8], align 8 @ LocationSize::precise(8),   %phi = phi ptr [ %gep.unknown, %start ], [ %gep.2, %if ] @ LocationSize::precise(1) = PartialAlias (off 2)

So this is probably due to incorrect merging of PartialAlias with an without offsets.

[nikic]

Fixes a pretty serious miscompile, so we may consider this for backport, though the timing is a bit unfortunate.

/cherry-pick 4d64ffa 97f0e7b