Switch lookup tables are not properly placed in program memory

[gergoerdi]

The input code here is a slight tweak of #46, but the generated code is very different because it uses a lookup instead of bit-twiddling:

Rust:

#[inline(never)]
pub fn decode(n: u8) -> Option<()> {
    match n {
        0x0 => Some(()),
        0x1 => Some(()),
        0x2 => Some(()),
        0x3 => Some(()),
        0x4 => Some(()),
        0xe => Some(()),
        _ => None
    }
}

LLVM IR:

        .text
        .file   "external-05dffe7586b7d437.ll"
        .globl  _ZN8external6decode17h0bb113af5b7a3594E
        .p2align        1
        .type   _ZN8external6decode17h0bb113af5b7a3594E,@function
_ZN8external6decode17h0bb113af5b7a3594E: ; @_ZN8external6decode17h0bb113af5b7a3594E
; BB#0:                                 ; %start
        cpi     r24, 15
        brlo    .+2
        rjmp    LBB0_1
; BB#2:                                 ; %switch.lookup
        mov     r26, r24
        mov     r27, r24
        lsl     r27
        sbc     r27, r27
        subi    r26, -lo8(switch.table)
        sbci    r27, -hi8(switch.table)
        ld      r24, X
        ret
LBB0_1:
        ldi     r24, 0
        ret
.Lfunc_end0:
        .size   _ZN8external6decode17h0bb113af5b7a3594E, .Lfunc_end0-_ZN8external6decode17h0bb113af5b7a3594E

        .type   switch.table,@object    ; @switch.table
        .section        .rodata,"a",@progbits
switch.table:
        .ascii  "\001\001\001\001\001\000\000\000\000\000\000\000\000\000\001"
        .size   switch.table, 15

AVR assembly:

Contents of section .text:
 0000 8f3008f0 00c0a82f b82fbb0f bb0ba050  .0....././.....P
 0010 b0408c91 089580e0 0895               .@........      
Contents of section .rodata:
 0000 01010101 01000000 00000000 000001    ............... 

Disassembly of section .text:

00000000 <_ZN8external6decode17h0bb113af5b7a3594E>:
   0:   8f 30           cpi     r24, 0x0F       ; 15
   2:   08 f0           brcs    .+2             ; 0x6 <_ZN8external6decode17h0bb113af5b7a3594E+0x6>
   4:   00 c0           rjmp    .+0             ; 0x6 <_ZN8external6decode17h0bb113af5b7a3594E+0x6>
                        4: R_AVR_13_PCREL       .text+0x16
   6:   a8 2f           mov     r26, r24
   8:   b8 2f           mov     r27, r24
   a:   bb 0f           add     r27, r27
   c:   bb 0b           sbc     r27, r27
   e:   a0 50           subi    r26, 0x00       ; 0
                        e: R_AVR_LO8_LDI_NEG    .rodata
  10:   b0 40           sbci    r27, 0x00       ; 0
                        10: R_AVR_HI8_LDI_NEG   .rodata
  12:   8c 91           ld      r24, X
  14:   08 95           ret

00000016 <LBB0_1>:
  16:   80 e0           ldi     r24, 0x00       ; 0
  18:   08 95           ret

[gergoerdi]

In the fully linked .elf, the table address in subi/sbci seems wrong to me:

Contents of section .data:
 800100 01010101 01000000 00000000 00000100  ................

Disassembly of section .text:
...
000000b4 <_ZN8external6decode17hbbb21fc0c1cdbaf3E>:
  b4:   8f 30           cpi     r24, 0x0F       ; 15
  b6:   08 f0           brcs    .+2             ; 0xba <_ZN8external6decode17hbbb21fc0c1cdbaf3E+0x6>
  b8:   08 c0           rjmp    .+16            ; 0xca <LBB0_1>
  ba:   a8 2f           mov     r26, r24
  bc:   b8 2f           mov     r27, r24
  be:   bb 0f           add     r27, r27
  c0:   bb 0b           sbc     r27, r27
  c2:   a0 50           subi    r26, 0x00       ; 0
  c4:   bf 4f           sbci    r27, 0xFF       ; 255
  c6:   8c 91           ld      r24, X
  c8:   08 95           ret

[gergoerdi]

Should these lookup tables even be generated?! avr-llvm/llvm#88

[gergoerdi]

Using a linker script, I moved the lookup table into .text. The linked binary now looks more promising:

Sections:
Idx Name          Size      VMA       LMA       File off  Algn
  0 .data         00000000  00800100  000000e1  00000155  2**0
                  CONTENTS, ALLOC, LOAD, DATA
  1 .text         000000e1  00000000  00000000  00000074  2**1
                  CONTENTS, ALLOC, LOAD, READONLY, CODE
  2 .stab         000006cc  00000000  00000000  00000158  2**2
                  CONTENTS, READONLY, DEBUGGING
  3 .stabstr      00000054  00000000  00000000  00000824  2**0
                  CONTENTS, READONLY, DEBUGGING

Disassembly of section .text:

000000b4 <_ZN8external6decode17hbbb21fc0c1cdbaf3E>:
  b4:   8f 30           cpi     r24, 0x0F       ; 15
  b6:   08 f0           brcs    .+2             ; 0xba <_ZN8external6decode17hbb
b21fc0c1cdbaf3E+0x6>
  b8:   08 c0           rjmp    .+16            ; 0xca <LBB0_1>
  ba:   a8 2f           mov     r26, r24
  bc:   b8 2f           mov     r27, r24
  be:   bb 0f           add     r27, r27
  c0:   bb 0b           sbc     r27, r27
  c2:   ae 52           subi    r26, 0x2E       ; 46
  c4:   bf 4f           sbci    r27, 0xFF       ; 255
  c6:   8c 91           ld      r24, X
  c8:   08 95           ret

000000d2 <_etext>:
  d2:   01 01           movw    r0, r2
  d4:   01 01           movw    r0, r2
  d6:   01 00           .word   0x0001  ; ????
        ...
  e0:   01 02           Address 0x00000000000000e0 is out of bounds.
.word   0xffff  ; ????

Where 0xff2e from 0xc2/0xc4 is exactly -0xe0, so this seems like it should work.

Unfortunately, decode(0x03) is still returning None.

[gergoerdi]

Details of decode going wrong with an input of 0x03 in r24. Note that r26 and r27 seem to point to the right .text address, but the ld still results in 0.

Breakpoint 1, 0x000000b4 in external::decode::hbbb21fc0c1cdbaf3 ()
=> 0x000000b4 <_ZN8external6decode17hbbb21fc0c1cdbaf3E+0>:	8f 30	cpi	r24, 0x0F	; 15
=> 0x000000b6 <_ZN8external6decode17hbbb21fc0c1cdbaf3E+2>:	08 f0	brcs	.+2      	;  0xba
=> 0x000000ba <_ZN8external6decode17hbbb21fc0c1cdbaf3E+6>:	a8 2f	mov	r26, r24
=> 0x000000bc <_ZN8external6decode17hbbb21fc0c1cdbaf3E+8>:	b8 2f	mov	r27, r24
=> 0x000000be <_ZN8external6decode17hbbb21fc0c1cdbaf3E+10>:	bb 0f	add	r27, r27
=> 0x000000c0 <_ZN8external6decode17hbbb21fc0c1cdbaf3E+12>:	bb 0b	sbc	r27, r27
=> 0x000000c2 <_ZN8external6decode17hbbb21fc0c1cdbaf3E+14>:	ae 52	subi	r26, 0x2E	; 46
=> 0x000000c4 <_ZN8external6decode17hbbb21fc0c1cdbaf3E+16>:	bf 4f	sbci	r27, 0xFF	; 255
=> 0x000000c6 <_ZN8external6decode17hbbb21fc0c1cdbaf3E+18>:	8c 91	ld	r24, X
r26            0xd5	213
r27            0x0	0
=> 0x000000c8 <_ZN8external6decode17hbbb21fc0c1cdbaf3E+20>:	08 95	ret
(gdb) i r r24
r24            0x0	0

[gergoerdi]

My working theory now is that the .text version is the one that should work, but we should be using LPM instead of LD.

[gergoerdi]

I've fixed this locally by matching load IR instructions with LPMRdZ and linking .rodata into .text with a linking script.

This works for the test case from this ticket, but unfortunately doesn't readily generalize to 16-bit loads, since the pseudo-instruction LPMWRdZ is not implemented. Next step: see if I can copy-paste LDWRdPtr's implementation.