[BPF] Reset machine register kill mark in BPFMISimplifyPatchable

[eddyz87]

Summary

When LLVM is build with LLVM_ENABLE_EXPENSIVE_CHECKS=ON option
the following C code snippet:

struct t {
  unsigned long a;
} __attribute__((preserve_access_index));

void foo(volatile struct t *t, volatile unsigned long *p) {
  *p = t->a;
  *p = t->a;
}

Causes an assertion:

$ clang -g -O2 -c --target=bpf -mcpu=v2 t2.c -o /dev/null

# After BPF PreEmit SimplifyPatchable
# Machine code for function foo: IsSSA, TracksLiveness
Function Live Ins: $r1 in %0, $r2 in %1

bb.0.entry:
  liveins: $r1, $r2
  DBG_VALUE $r1, $noreg, !"t", !DIExpression()
  DBG_VALUE $r2, $noreg, !"p", !DIExpression()
  %1:gpr = COPY $r2
  DBG_VALUE %1:gpr, $noreg, !"p", !DIExpression()
  %0:gpr = COPY $r1
  DBG_VALUE %0:gpr, $noreg, !"t", !DIExpression()
  %2:gpr = LD_imm64 @"llvm.t:0:0$0:0"
  %4:gpr = ADD_rr %0:gpr(tied-def 0), killed %2:gpr
  %5:gpr = CORE_LD 344, %0:gpr, @"llvm.t:0:0$0:0"
  STD killed %5:gpr, %1:gpr, 0
  %7:gpr = ADD_rr %0:gpr(tied-def 0), killed %2:gpr
  %8:gpr = CORE_LD 344, %0:gpr, @"llvm.t:0:0$0:0"
  STD killed %8:gpr, %1:gpr, 0
  RET

# End machine code for function foo.

*** Bad machine code: Using a killed virtual register ***
- function:    foo
- basic block: %bb.0 entry (0x6210000e6690)
- instruction: %7:gpr = ADD_rr %0:gpr(tied-def 0), killed %2:gpr
- operand 2:   killed %2:gpr

This happens because of the way
BPFMISimplifyPatchable::processDstReg() updates second operand of the
ADD_rr instruction. Code before BPFMISimplifyPatchable:

.-> %2:gpr = LD_imm64 @"llvm.t:0:0$0:0"
|
|`----------------.
|   %3:gpr = LDD %2:gpr, 0
|   %4:gpr = ADD_rr %0:gpr(tied-def 0), killed %3:gpr <--- (1)
|   %5:gpr = LDD killed %4:gpr, 0       ^^^^^^^^^^^^^
|   STD killed %5:gpr, %1:gpr, 0        this is updated
 `----------------.
    %6:gpr = LDD %2:gpr, 0
    %7:gpr = ADD_rr %0:gpr(tied-def 0), killed %6:gpr <--- (2)
    %8:gpr = LDD killed %7:gpr, 0       ^^^^^^^^^^^^^
    STD killed %8:gpr, %1:gpr, 0        this is updated

Instructions (1) and (2) would be updated to:

ADD_rr %0:gpr(tied-def 0), killed %2:gpr

The killed mark is inherited from machine operands killed %3:gpr
and killed %6:gpr which are updated inplace by processDstReg().

This commit updates processDstReg() reset kill marks for updated
machine operands to keep liveness information conservatively correct.

[eddyz87]

Hi Yonghong,

Could you please take a look at this revision?
All BPF Kernel selftests are passing and there are no changes on the generated object files (I checked for cpuv4).

[yonghong-song]

LGTM. Thanks for detailed comments to show why generated code is incorrect. Do you think we should backport this fix to llvm17?

[yonghong-song]

With LLVM_ENABLE_EXPENSIVE_CHECKS, even with this patch, there are still some selftest llvm crashes. I guess you are probably working on this (e.g. D157806).

[eddyz87]

In D157805#4583287, @yonghong-song wrote:

LGTM. Thanks for detailed comments to show why generated code is incorrect. Do you think we should backport this fix to llvm17?

On the one hand the code dates back to Dec 2019 and I don't see it affecting code generation in practice (at-least for our selftests). On the other hand it is really easy to backport. I'd say we should backport it.

In D157805#4583292, @yonghong-song wrote:

With LLVM_ENABLE_EXPENSIVE_CHECKS, even with this patch, there are still some selftest llvm crashes. I guess you are probably working on this (e.g. D157806).

Yes, I'm aware of two more issues, the one addressed by D157806 and the one in "BPF MachineSSA Peephole Optimization For TRUNC Eliminate":

*** Bad machine code: Illegal virtual register for instruction ***
- function:    _dissect
- basic block: %bb.9 if.end10 (0x621000e80d98)
- instruction: %24:gpr32 = MOV_rr %8:gpr32, debug-location !339; progs/bpf_flow.c:120:2 @[ progs/bpf_flow.c:161:9 ]
- operand 0:   %24:gpr32
Expected a GPR register, but got a GPR32 register

Which I suppose is caused by MOV_rr instruction generated in the end of BPFMIPeepholeTruncElim::eliminateTruncSeq(). I'll submit a fix for this issue a bit later.

[yonghong-song]

In D157805#4583326, @eddyz87 wrote:

In D157805#4583287, @yonghong-song wrote:

LGTM. Thanks for detailed comments to show why generated code is incorrect. Do you think we should backport this fix to llvm17?

On the one hand the code dates back to Dec 2019 and I don't see it affecting code generation in practice (at-least for our selftests). On the other hand it is really easy to backport. I'd say we should backport it.

Sounds good. Let us do it.

In D157805#4583292, @yonghong-song wrote:

With LLVM_ENABLE_EXPENSIVE_CHECKS, even with this patch, there are still some selftest llvm crashes. I guess you are probably working on this (e.g. D157806).

Yes, I'm aware of two more issues, the one addressed by D157806 and the one in "BPF MachineSSA Peephole Optimization For TRUNC Eliminate":

*** Bad machine code: Illegal virtual register for instruction ***
- function:    _dissect
- basic block: %bb.9 if.end10 (0x621000e80d98)
- instruction: %24:gpr32 = MOV_rr %8:gpr32, debug-location !339; progs/bpf_flow.c:120:2 @[ progs/bpf_flow.c:161:9 ]
- operand 0:   %24:gpr32
Expected a GPR register, but got a GPR32 register

Which I suppose is caused by MOV_rr instruction generated in the end of BPFMIPeepholeTruncElim::eliminateTruncSeq(). I'll submit a fix for this issue a bit later.

Sounds good. Thanks for discovering these issues and fixing them.

llvm/lib/Target/BPF/BPFMISimplifyPatchable.cpp

 
 void BPFMISimplifyPatchable::processDstReg(MachineRegisterInfo *MRI,
     Register &DstReg, Register &SrcReg, const GlobalValue *GVal,
     bool doSrcRegProp, bool IsAma) {
   auto Begin = MRI->use_begin(DstReg), End = MRI->use_end();
   decltype(End) NextI;
   for (auto I = Begin; I != End; I = NextI) {
     NextI = std::next(I);
-    if (doSrcRegProp)
+    if (doSrcRegProp) {
+      // In situations like below it is not known if usage is a kill
+      // after setReg():
+      //
+      // .-> %2:gpr = LD_imm64 @"llvm.t:0:0$0:0"
+      // |
+      // |`----------------.
+      // |   %3:gpr = LDD %2:gpr, 0
+      // |   %4:gpr = ADD_rr %0:gpr(tied-def 0), killed %3:gpr <--- (1)
+      // |   %5:gpr = LDD killed %4:gpr, 0       ^^^^^^^^^^^^^
+      // |   STD killed %5:gpr, %1:gpr, 0         this is I
+      //  `----------------.
+      //     %6:gpr = LDD %2:gpr, 0
+      //     %7:gpr = ADD_rr %0:gpr(tied-def 0), killed %6:gpr <--- (2)
+      //     %8:gpr = LDD killed %7:gpr, 0       ^^^^^^^^^^^^^
+      //     STD killed %8:gpr, %1:gpr, 0         this is I
+      //
+      // Instructions (1) and (2) would be updated by setReg() to:
+      //
+      //     ADD_rr %0:gpr(tied-def 0), %2:gpr
+      //
+      // %2:gpr is not killed at (1), so it is necessary to remove kill flag
+      // from I.
       I->setReg(SrcReg);
+      I->setIsKill(false);
+    }
 
     // The candidate needs to have a unique definition.
     if (IsAma && MRI->getUniqueVRegDef(I->getReg()))
       processInst(MRI, I->getParent(), &*I, GVal);
   }
 }
 
 // Check to see whether we could do some optimization

llvm/test/CodeGen/BPF/CORE/simplify-patchable-liveness-bug.ll

+; RUN: llc -mtriple=bpf -mcpu=v2 < %s | FileCheck -check-prefixes=CHECK %s
+
+; Test for machine register liveness update bug in
+; BPFMISimplifyPatchable::processDstReg.
+;
+; Generated from the following source code:
+;   struct t {
+;     unsigned long a;
+;   } __attribute__((preserve_access_index));
+;
+;   void foo(volatile struct t *t, volatile unsigned long *p) {
+;     *p = t->a;
+;     *p = t->a;
+;   }
+;
+; Using the following command:
+;   clang -g -O2 -S -emit-llvm --target=bpf t.c -o t.ll
+
+@"llvm.t:0:0$0:0" = external global i64, !llvm.preserve.access.index !0 #0
+
+; Function Attrs: nofree nounwind
+define dso_local void @foo(ptr noundef %t, ptr noundef %p) local_unnamed_addr #1 !dbg !12 {
+entry:
+  call void @llvm.dbg.value(metadata ptr %t, metadata !20, metadata !DIExpression()), !dbg !22
+  call void @llvm.dbg.value(metadata ptr %p, metadata !21, metadata !DIExpression()), !dbg !22
+  %0 = load i64, ptr @"llvm.t:0:0$0:0", align 8
+  %1 = getelementptr i8, ptr %t, i64 %0
+  %2 = tail call ptr @llvm.bpf.passthrough.p0.p0(i32 0, ptr %1)
+  %3 = load volatile i64, ptr %2, align 8, !dbg !23, !tbaa !24
+  store volatile i64 %3, ptr %p, align 8, !dbg !29, !tbaa !30
+  %4 = load i64, ptr @"llvm.t:0:0$0:0", align 8
+  %5 = getelementptr i8, ptr %t, i64 %4
+  %6 = tail call ptr @llvm.bpf.passthrough.p0.p0(i32 1, ptr %5)
+  %7 = load volatile i64, ptr %6, align 8, !dbg !31, !tbaa !24
+  store volatile i64 %7, ptr %p, align 8, !dbg !32, !tbaa !30
+  ret void, !dbg !33
+}
+
+; CHECK:      foo:
+; CHECK:              prologue_end
+; CHECK-NEXT: .Ltmp[[LABEL1:.*]]:
+; CHECK-NEXT: .Ltmp
+; CHECK-NEXT:         r[[#A:]] = *(u64 *)(r1 + 0)
+; CHECK-NEXT:         .loc
+; CHECK-NEXT: .Ltmp
+; CHECK-NEXT:         *(u64 *)(r2 + 0) = r[[#A]]
+; CHECK-NEXT:         .loc
+; CHECK-NEXT: .Ltmp[[LABEL2:.*]]:
+; CHECK-NEXT: .Ltmp
+; CHECK-NEXT:         r[[#B:]] = *(u64 *)(r1 + 0)
+; CHECK-NEXT: .Ltmp
+; CHECK-NEXT: .Ltmp
+; CHECK-NEXT:         .loc
+; CHECK-NEXT: .Ltmp
+; CHECK-NEXT:         *(u64 *)(r2 + 0) = r[[#B]]
+
+; CHECK: .section .BTF
+; CHECK: .long [[STR_T:.*]]  # BTF_KIND_STRUCT(id = [[ID:.*]])
+
+; CHECK: .byte   116     # string offset=[[STR_T]]
+; CHECK: .ascii  "0:0"   # string offset=[[STR_A:.*]]
+
+; CHECK:     # FieldReloc
+; CHECK:      .long .Ltmp[[LABEL1]]
+; CHECK-NEXT: .long [[ID]]
+; CHECK-NEXT: .long [[STR_A]]
+; CHECK-NEXT: .long 0
+; CHECK:      .long .Ltmp[[LABEL2]]
+; CHECK-NEXT: .long [[ID]]
+; CHECK-NEXT: .long [[STR_A]]
+; CHECK-NEXT: .long 0
+
+; Function Attrs: nofree nosync nounwind memory(none)
+declare ptr @llvm.bpf.passthrough.p0.p0(i32, ptr) #2
+
+; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
+declare void @llvm.dbg.value(metadata, metadata, metadata) #3
+
+attributes #0 = { "btf_ama" }
+attributes #1 = { nofree nounwind "frame-pointer"="all" "no-trapping-math"="true" "stack-protector-buffer-size"="8" }
+attributes #2 = { nofree nosync nounwind memory(none) }
+attributes #3 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }
+
+!llvm.dbg.cu = !{!5}
+!llvm.module.flags = !{!6, !7, !8, !9, !10}
+!llvm.ident = !{!11}
+
+!0 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "t", file: !1, line: 1, size: 64, elements: !2)
+!1 = !DIFile(filename: "some.file", directory: "/some/dir", checksumkind: CSK_MD5, checksum: "a149cfaf65a83125e7f2b2f47e5c7287")
+!2 = !{!3}
+!3 = !DIDerivedType(tag: DW_TAG_member, name: "a", scope: !0, file: !1, line: 2, baseType: !4, size: 64)
+!4 = !DIBasicType(name: "unsigned long", size: 64, encoding: DW_ATE_unsigned)
+!5 = distinct !DICompileUnit(language: DW_LANG_C11, file: !1, producer: "clang version 18.0.0 (/home/eddy/work/llvm-project/clang 3810f2eb4382d5e2090ce5cd47f45379cb453c35)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, splitDebugInlining: false, nameTableKind: None)
+!6 = !{i32 7, !"Dwarf Version", i32 5}
+!7 = !{i32 2, !"Debug Info Version", i32 3}
+!8 = !{i32 1, !"wchar_size", i32 4}
+!9 = !{i32 7, !"frame-pointer", i32 2}
+!10 = !{i32 7, !"debug-info-assignment-tracking", i1 true}
+!11 = !{!"clang version 18.0.0 (/home/eddy/work/llvm-project/clang 3810f2eb4382d5e2090ce5cd47f45379cb453c35)"}
+!12 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 4, type: !13, scopeLine: 4, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !5, retainedNodes: !19)
+!13 = !DISubroutineType(types: !14)
+!14 = !{null, !15, !17}
+!15 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !16, size: 64)
+!16 = !DIDerivedType(tag: DW_TAG_volatile_type, baseType: !0)
+!17 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !18, size: 64)
+!18 = !DIDerivedType(tag: DW_TAG_volatile_type, baseType: !4)
+!19 = !{!20, !21}
+!20 = !DILocalVariable(name: "t", arg: 1, scope: !12, file: !1, line: 4, type: !15)
+!21 = !DILocalVariable(name: "p", arg: 2, scope: !12, file: !1, line: 4, type: !17)
+!22 = !DILocation(line: 0, scope: !12)
+!23 = !DILocation(line: 5, column: 11, scope: !12)
+!24 = !{!25, !26, i64 0}
+!25 = !{!"t", !26, i64 0}
+!26 = !{!"long", !27, i64 0}
+!27 = !{!"omnipotent char", !28, i64 0}
+!28 = !{!"Simple C/C++ TBAA"}
+!29 = !DILocation(line: 5, column: 6, scope: !12)
+!30 = !{!26, !26, i64 0}
+!31 = !DILocation(line: 6, column: 11, scope: !12)
+!32 = !DILocation(line: 6, column: 6, scope: !12)
+!33 = !DILocation(line: 7, column: 1, scope: !12)