[M68k] cmp / br pair doesn't prevent reordering in scheduling

[TechnoElf]

I have run into an issue while attempting to get some rust code compiled for the m68k target. While the code does compile, it has a completely different behaviour to that described by the source. The relevant section looks something like this:

let mut prev_state = get_input();
loop {
    let state = get_input();
    if state != prev_state {
        do_something();
    }
    prev_state = state;
}

I am pretty sure the issue lies with the backend as the generated IR looks correct. The test case can be reduced to the following IR:

define internal zeroext i1 @get1() unnamed_addr #1 {
start:
  ret i1 0
}

define internal void @main() unnamed_addr #1 {
start:
  %prev_state = alloca [1 x i8], align 1
  br label %bb5

bb5:
  %state = call zeroext i1 @get1() #11
  %8 = load i8, ptr %prev_state, align 1
  %_11 = trunc i8 %8 to i1
  %_10 = icmp ne i1 %state, %_11
  br i1 %_10, label %bb7, label %bb10

bb10:
  %9 = zext i1 %state to i8
  store i8 %9, ptr %prev_state, align 1
  br label %bb5

bb7:
  br label %bb10
}

This is compiled to the following machine code using llc -O0 -march=m68k with llvm compiled from the main branch:

        .text
        .file   "b"
        .p2align        1                               ; -- Begin function get1
        .type   get1,@function
get1:                                   ; @get1
        .cfi_startproc
; %bb.0:                                ; %start
        moveq   #0, %d0
        rts
.Lfunc_end0:
        .size   get1, .Lfunc_end0-get1
        .cfi_endproc
                                        ; -- End function
        .p2align        1                               ; -- Begin function main
        .type   main,@function
main:                                   ; @main
        .cfi_startproc
; %bb.0:                                ; %start
        suba.l  #12, %sp
        .cfi_def_cfa_offset -16
        movem.l %d2, (8,%sp)                    ; 8-byte Folded Spill
        bra     .LBB1_1
.LBB1_1:                                ; %bb5
                                        ; =>This Inner Loop Header: Depth=1
        jsr     get1
        move.b  (7,%sp), %d2
        and.b   #1, %d2
        move.b  %d0, %d1
        sub.b   %d2, %d1
        move.b  %d0, (6,%sp)                    ; 1-byte Folded Spill
        bne     .LBB1_3
        bra     .LBB1_2
.LBB1_2:                                ; %bb10
                                        ;   in Loop: Header=BB1_1 Depth=1
        move.b  (6,%sp), %d0                    ; 1-byte Folded Reload
        move.b  %d0, (7,%sp)
        bra     .LBB1_1
.LBB1_3:                                ; %bb7
                                        ;   in Loop: Header=BB1_1 Depth=1
        bra     .LBB1_2
.Lfunc_end1:
        .size   main, .Lfunc_end1-main
        .cfi_endproc
                                        ; -- End function
        .section        ".note.GNU-stack","",@progbits

The move.b %d0, (6,%sp) overwrites the value in the CC register written by the prior subtraction, preventing the subsequent branch from working correctly. Reversing the order of these two instructions makes the code function as expected.

[TechnoElf]

I have tried fixing this by adding glue in various places, but this invariably ends up breaking something else... The last attempt ended with a cycle in a SelectionDAG somewhere in the rust compiler_builtins crate (if I am interpreting the message ERROR: SmallVector unable to grow. Requested capacity (4294967296) is larger than maximum value for size type (4294967295) at the start of scheduling, just before it's supposed to print the depth of the last instruction, correctly). If anyone has any other suggestions I would be open to attempting to write a fix again. My current approach just isn't getting anywhere.

[llvmbot]

@llvm/issue-subscribers-backend-m68k

Author: Janis Heims (TechnoElf)

I have run into an issue while attempting to get some rust code compiled for the m68k target. While the code does compile, it has a completely different behaviour to that described by the source. The relevant section looks something like this:

let mut prev_state = get_input();
loop {
    let state = get_input();
    if state != prev_state {
        do_something();
    }
    prev_state = state;
}

I am pretty sure the issue lies with the backend as the generated IR looks correct. The test case can be reduced to the following IR:

define internal zeroext i1 @<!-- -->get1() unnamed_addr #<!-- -->1 {
start:
  ret i1 0
}

define internal void @<!-- -->main() unnamed_addr #<!-- -->1 {
start:
  %prev_state = alloca [1 x i8], align 1
  br label %bb5

bb5:
  %state = call zeroext i1 @<!-- -->get1() #<!-- -->11
  %8 = load i8, ptr %prev_state, align 1
  %_11 = trunc i8 %8 to i1
  %_10 = icmp ne i1 %state, %_11
  br i1 %_10, label %bb7, label %bb10

bb10:
  %9 = zext i1 %state to i8
  store i8 %9, ptr %prev_state, align 1
  br label %bb5

bb7:
  br label %bb10
}

This is compiled to the following machine code using llc -O0 -march=m68k with llvm compiled from the main branch:

        .text
        .file   "b"
        .p2align        1                               ; -- Begin function get1
        .type   get1,@<!-- -->function
get1:                                   ; @<!-- -->get1
        .cfi_startproc
; %bb.0:                                ; %start
        moveq   #<!-- -->0, %d0
        rts
.Lfunc_end0:
        .size   get1, .Lfunc_end0-get1
        .cfi_endproc
                                        ; -- End function
        .p2align        1                               ; -- Begin function main
        .type   main,@<!-- -->function
main:                                   ; @<!-- -->main
        .cfi_startproc
; %bb.0:                                ; %start
        suba.l  #<!-- -->12, %sp
        .cfi_def_cfa_offset -16
        movem.l %d2, (8,%sp)                    ; 8-byte Folded Spill
        bra     .LBB1_1
.LBB1_1:                                ; %bb5
                                        ; =&gt;This Inner Loop Header: Depth=1
        jsr     get1
        move.b  (7,%sp), %d2
        and.b   #<!-- -->1, %d2
        move.b  %d0, %d1
        sub.b   %d2, %d1
        move.b  %d0, (6,%sp)                    ; 1-byte Folded Spill
        bne     .LBB1_3
        bra     .LBB1_2
.LBB1_2:                                ; %bb10
                                        ;   in Loop: Header=BB1_1 Depth=1
        move.b  (6,%sp), %d0                    ; 1-byte Folded Reload
        move.b  %d0, (7,%sp)
        bra     .LBB1_1
.LBB1_3:                                ; %bb7
                                        ;   in Loop: Header=BB1_1 Depth=1
        bra     .LBB1_2
.Lfunc_end1:
        .size   main, .Lfunc_end1-main
        .cfi_endproc
                                        ; -- End function
        .section        ".note.GNU-stack","",@<!-- -->progbits

The move.b %d0, (6,%sp) overwrites the value in the CC register written by the prior subtraction, preventing the subsequent branch from working correctly. Reversing the order of these two instructions makes the code function as expected.

[s-barannikov]

The instruction is inserted by the register allocator, which can insert spills / restores anywhere.
The issue could probably be solved by using MOVEM instruction instead of MOVE in M68kInstrInfo::storeRegToStackSlot / M68kInstrInfo::loadRegFromStackSlot.

[TechnoElf]

Interesting! When I glued together the BRCOND and SUB nodes it also prevented the insertion of the spill between them, but I guess I only got lucky in that case then.

Anyway, your suggestion seems to work! I'm not sure how to make sure the size of the stack slot is increased to 2 bytes for 1 byte registers though.

        .text
        .file   "b"
        .p2align        1                               ; -- Begin function get1
        .type   get1,@function
get1:                                   ; @get1
        .cfi_startproc
; %bb.0:                                ; %start
        moveq   #0, %d0
        rts
.Lfunc_end0:
        .size   get1, .Lfunc_end0-get1
        .cfi_endproc
                                        ; -- End function
        .p2align        1                               ; -- Begin function main
        .type   main,@function
main:                                   ; @main
        .cfi_startproc
; %bb.0:                                ; %start
        suba.l  #12, %sp
        .cfi_def_cfa_offset -16
        movem.l %d2, (8,%sp)                    ; 8-byte Folded Spill
        bra     .LBB1_1
.LBB1_1:                                ; %bb5
                                        ; =>This Inner Loop Header: Depth=1
        jsr     get1
        move.b  (7,%sp), %d2
        and.b   #1, %d2
        move.b  %d0, %d1
        sub.b   %d2, %d1
        movem.w %d0, (6,%sp)
        bne     .LBB1_3
        bra     .LBB1_2
.LBB1_2:                                ; %bb10
                                        ;   in Loop: Header=BB1_1 Depth=1
        movem.w (6,%sp), %d0
        move.b  %d0, (7,%sp)
        bra     .LBB1_1
.LBB1_3:                                ; %bb7
                                        ;   in Loop: Header=BB1_1 Depth=1
        bra     .LBB1_2
.Lfunc_end1:
        .size   main, .Lfunc_end1-main
        .cfi_endproc
                                        ; -- End function

In this code it seems like the spill would overwrite another stack slot?

[TechnoElf]

Oh, also, would you mind me creating a PR with your fix (assuming I can get it working correctly ^^)?

[s-barannikov]

I'm not sure how to make sure the size of the stack slot is increased to 2 bytes for 1 byte registers though.

Probably like this:

  // Data Registers
+ let Size = 16 in
  def DR8  : MxRegClass<[i8],  16, (sequence "BD%u", 0, 7)>;

in M68kRegisterInfo.td

Oh, also, would you mind me creating a PR with your fix (assuming I can get it working correctly ^^)?

I don't mind and I have no relation to M68k backend, I just remember a few things about the architecture.

[s-barannikov]

cc @mshockwave