R_MIPS_HI16 and R_MIPS_LO16 are wrong

[DennyDai]

Description

Expected Result

0x21000:        R_MIPS_HI16     3c080000        lui     $t0, 2
0x21004:        R_MIPS_HI16     3c090000        lui     $t1, 2
0x21008:        R_MIPS_LO16     21080004        addi    $t0, $t0, 4100
0x2100c:        R_MIPS_LO16     21080008        addi    $t0, $t0, 4140
0x21010:        R_MIPS_HI16     3c080001        lui     $t0, 3
0x21014:        R_MIPS_HI16     3c090002        lui     $t1, 4
0x21018:        R_MIPS_LO16     2108fffc        addi    $t0, $t0, 4124

Result when not applying reloc at all (make relocate simply returns True)

0x21000:        R_MIPS_HI16     3c080000        lui     $t0, 0
0x21004:        R_MIPS_HI16     3c090000        lui     $t1, 0
0x21008:        R_MIPS_LO16     21080004        addi    $t0, $t0, 4
0x2100c:        R_MIPS_LO16     21080008        addi    $t0, $t0, 8
0x21010:        R_MIPS_HI16     3c080001        lui     $t0, 1
0x21014:        R_MIPS_HI16     3c090002        lui     $t1, 2
0x21018:        R_MIPS_LO16     2108fffc        addi    $t0, $t0, -4

Current impl (c8eb415)

0x21000:        R_MIPS_HI16     00020000        sll     $zero, $v0, 0
0x21004:        R_MIPS_HI16     00020000        sll     $zero, $v0, 0
0x21008:        R_MIPS_LO16     10000004        b       0x2101c
0x2100c:        R_MIPS_LO16     10240008        beq     $at, $a0, 0x21030
0x21010:        R_MIPS_HI16     00020001
0x21014:        R_MIPS_HI16     00020002        srl     $zero, $v0, 0
0x21018:        R_MIPS_LO16     1020fffc        beqz    $at, 0x2100c

Steps to reproduce the bug

Run ./test.py in attached zip.
test.zip
(test stolen from https://github.com/llvm/llvm-project/blob/main/lld/test/ELF/mips-hilo.s)

Environment

No response

Additional context

If understand this correctly, according to https://refspecs.linuxfoundation.org/elf/mipsabi.pdf Page 80, 81 (4-18, 4-19)

R_MIPS_HI16: ((AHL + S) – (short)(AHL + S)) >> 16
R_MIPS_LO16: AHL + S

If AHI and ALO are the addends from the paired R_MIPS_HI16 and R_MIPS_LO16 
entries, then the addend AHL is computed as (AHI << 16) + (short)ALO.

Each relocation type needs to access the addend value from the other to calculate the correct result

[rhelmot]

Yeah I've heard of this one before. Absolute nightmare. If you can fix it, that would be amazing, if not, a detailed report of why the current cle architecture is insufficient and what points code needs to be inserted at would be fantastic.

[DennyDai]

@rhelmot I currently don't have any idea on how to fix it, just wanna open this issue before I totally forget about this.
I will come back to this later when I have some free time.