Wrong code at -O1/O2 possibly due to backend bug since clang 21.1.0

[XChy]

Reproducer: https://godbolt.org/z/bGEMsr81M

I inspected the IR produced by opt, and it looks correct to me. And I can reproduce it on X86, AArch64, and RISC-V. I suspect it's the problem of the generic codegen.

Testcase:

#include <stdint.h>
#include <stdio.h>
#define BS_VEC(type, num) type __attribute__((vector_size(num * sizeof(type))))
uint64_t BS_CHECKSUM;
BS_VEC(int8_t, 32)
backsmith_snippet_1116(BS_VEC(uint8_t, 32), uint16_t, BS_VEC(int64_t, 8))
{}
static int32_t g_3, g_169;
int func_1_BS_COND_4;
int func_1_BS_COND_9;
static uint32_t func_1()
{
    uint64_t LOCAL_CHECKSUM = 0;
BS_LABEL_6:
    for (; g_3;)
    {
        int32_t l_1874[1][1][3];
        int i, j, k;
        l_1874[i][j][k] = 1;
        for (; 0; g_169)
            if (0)
            {
                for (uint32_t BS_TEMP_34; BS_TEMP_34; BS_TEMP_34++)
                {
                    LOCAL_CHECKSUM ^= 9;
                BS_LABEL_4:
                }
                __builtin_convertvector(
                    __builtin_shufflevector(
                        backsmith_snippet_1116((BS_VEC(uint8_t, 32)){}, 0,
                                               (BS_VEC(int64_t, 8)){}),
                        backsmith_snippet_1116((BS_VEC(uint8_t, 32)){}, 0,
                                               (BS_VEC(int64_t, 8)){}),
                        0, 7, 3, 3, 3, 1, 3, 6),
                    BS_VEC(uint32_t, 8));
                __asm goto("" : : : : BS_LABEL_6);
            }
            else
            BS_LABEL_7:
                if (l_1874[0][0][1]) break;
    }
    if (func_1_BS_COND_4) goto BS_LABEL_7;
    switch (func_1_BS_COND_9)
    case 2064568:
        goto BS_LABEL_4;
    BS_CHECKSUM += LOCAL_CHECKSUM;
    return 0;
}
int main()
{
    func_1();
    printf("BackSmith Checksum = 0x%016llx\n", BS_CHECKSUM);
}

Commands:

> clang -O0 a.c && a.out
BackSmith Checksum = 0x0000000000000000
> clang -O1 a.c && a.out
BackSmith Checksum = 0x00007ffe970f5af8

[XChy]

It looks like the emitted X86 asm is wrong, as rsi is not initialized to zero:

        add     rsi, qword ptr [rip + BS_CHECKSUM]
        mov     qword ptr [rip + BS_CHECKSUM], rsi

cc @RKSimon

[RKSimon]

@XChy have you run this through UBSan?

[antoniofrighetto]

I don't think there's any undefined behaviour in the code. I don't think this is as an issue in codegen either. Looking at the IR, from a quick look, I think InstructionCombine may be the culprit. I'm taking a look.

[XChy]

@XChy have you run this through UBSan?

Yes. It passes the UBsan, ASan, and Memory Sanitizer.

[antoniofrighetto]

@XChy have you run this through UBSan?

Yes. It passes the UBsan, ASan, and Memory Sanitizer.

IIRC MSan and UBSan used not to catch some uninitialized reads. It looks like there are some of them when compiling with -Werror=uninitialized (https://llvm.godbolt.org/z/cPeGn8dWe), would you mind taking a look at them?

[XChy]

@antoniofrighetto, I have checked the C code. The code in for (; g_3;) {xxx} is dead, as global variables like g_3 are always initialized to zero if not specified. Thus, the uninitialized reads in the loop are never run.

Without the dead loop and some dead jumps, the runtime behaviour should be like:

#include <stdint.h>
#include <stdio.h>
uint64_t BS_CHECKSUM;
static uint32_t func_1()
{
    uint64_t LOCAL_CHECKSUM = 0;
    // dead code
    BS_CHECKSUM += LOCAL_CHECKSUM;
    return 0;
}
int main()
{
    func_1();
    printf("BackSmith Checksum = 0x%016llx\n", BS_CHECKSUM);
}

[XChy]

I ran the IR at -O2 with llubi, and the result is correct. It implies that the problem is in the backend.

> llubi --verbose a.ll
Entering function main
  br label %for.cond.i jump to %for.cond.i
    phi i64 %LOCAL_CHECKSUM.1.i -> i64 0
  %0 = load i32, ptr @func_1_BS_COND_4, align 4, !tbaa !5 -> i32 0
  %tobool26.not.i = icmp eq i32 %0, 0 -> T
  br i1 %tobool26.not.i, label %if.end28.i, label %for.cond.i.backedge jump to %if.end28.i
  %1 = load i32, ptr @func_1_BS_COND_9, align 4, !tbaa !5 -> i32 0
  %cond.i = icmp eq i32 %1, 2064568 -> F
  br i1 %cond.i, label %BS_LABEL_4.i, label %func_1.exit jump to %func_1.exit
  %2 = load i64, ptr @BS_CHECKSUM, align 8, !tbaa !12 -> i64 0
  %add.i = add i64 %2, %LOCAL_CHECKSUM.1.i -> i64 0
  store i64 %add.i, ptr @BS_CHECKSUM, align 8, !tbaa !12
  %call1 = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str, i64 noundef %add.i)
    Printf: BackSmith Checksum = 0x0000000000000000
   -> i32 40
  ret i32 0

[antoniofrighetto]

Machine IR after Virtual Register Rewriter on clang-20:

0B	bb.0.entry:
	  successors: %bb.1(0x80000000); %bb.1(100.00%)

16B	  renamable $esi = MOV32r0 implicit-def dead $eflags, implicit-def $rsi

64B	bb.1.for.cond.i (machine-block-address-taken, inlineasm-br-indirect-target):
	; predecessors: %bb.0, %bb.1, %bb.3
	  successors: %bb.4(0x30000000), %bb.1(0x50000000); %bb.4(37.50%), %bb.1(62.50%)
	  liveins: $rsi
112B	  CMP32mi $rip, 1, $noreg, @func_1_BS_COND_4, $noreg, 0, implicit-def $eflags :: (dereferenceable load (s32) from @func_1_BS_COND_4)
128B	  JCC_1 %bb.4, 4, implicit killed $eflags
144B	  JMP_1 %bb.1

Machine IR after Virtual Register Rewriter on clang trunk:

0B	bb.0.entry:
	  successors: %bb.1(0x80000000); %bb.1(100.00%)

64B	bb.1.for.cond.i (inlineasm-br-indirect-target):
	; predecessors: %bb.0, %bb.1, %bb.3
	  successors: %bb.4(0x30000000), %bb.1(0x50000000); %bb.4(37.50%), %bb.1(62.50%)

80B	  renamable $rsi = IMPLICIT_DEF
112B	  CMP32mi $rip, 1, $noreg, @func_1_BS_COND_4, $noreg, 0, implicit-def $eflags :: (dereferenceable load (s32) from @func_1_BS_COND_4)
128B	  JCC_1 %bb.4, 4, implicit killed $eflags
144B	  JMP_1 %bb.1

It looks like 1) $rsi is indeed left undefined on latest Clang 2) Somehow machine-block-address-taken attribute has been lost. This has started appearing since #143958. @nikic Do you believe the following code is correct even in control-flows with asm gotos? I see a PN (which initializes local checksum on entry path) getting broken (though not sure if this is just exposing the issue).

llvm-project/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

Lines 3694 to 3702 in cbb2aa9

	case Instruction::Load: {
	LoadInst *LI = cast<LoadInst>(I);
	if (LI->isVolatile() || LI->getPointerOperand() != PI)
	return std::nullopt;
	if (isModSet(Access))
	return std::nullopt;
	Access |= ModRefInfo::Ref;
	Users.emplace_back(I);
	continue;

[nikic]

@antoniofrighetto I don't think that code has any interaction with asm goto.