[LLVMdev] Sorting relocation entries

[Akira Hatanaka]

Hi Jim,

Yes, the relocation entries have to be reordered so that the
got16/lo16 or hi16/lo16 pairs appear consecutively in the relocation
table. As a result, relocations can appear in a different order than
the instructions that they're for.

For example, in this code, the post-RA scheduler inserts an
instruction with relocation %got(body_ok) between %got(scope_top) and
%lo(scope_top).

$ cat z29.s
  lw  $3, %got(scope_top)($gp)
  lw  $2, %got(body_ok)($gp)
  lw  $3, %lo(scope_top)($3)
  addiu $2, $2, %lo(body_ok)

This is the assembled program generated by gas:
$  mips-linux-gnu-objdump -dr z29.gas.o

     748:       8f830000        lw      v1,0(gp)
                        748: R_MIPS_GOT16       .bss
     74c:       8f820000        lw      v0,0(gp)
                        74c: R_MIPS_GOT16       .bss
     750:       8c630000        lw      v1,0(v1)
                        750: R_MIPS_LO16        .bss
     754:       244245d4        addiu   v0,v0,17876
                        754: R_MIPS_LO16        .bss


gas reorders these relocations with the function in the following link:

http://repo.or.cz/w/binutils.git/blob/master:/gas/config/tc-mips.c#l15222


$ mips--linux-gnu-readelf -r z29.gas.o

Relocation section '.rel.text' at offset 0x4584 contains 705 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
...
00000748  00000409 R_MIPS_GOT16      00000000   .bss // %got(scope_top)
00000750  00000406 R_MIPS_LO16       00000000   .bss   // %lo(scope_top)
0000074c  00000409 R_MIPS_GOT16      00000000   .bss // %got(body_ok)
00000754  00000406 R_MIPS_LO16       00000000   .bss // %lo(body_ok)


The attached patch makes the following changes to make direct object
emitter write out relocations in the correct order:

1. Add a target hook MCELFObjectTargetWriter::ReorderRelocs. The
default behavior sorts the relocations by the r_offset.
2. Move struct ELFRelocationEntry from ELFObjectWriter to
MCELFObjectTargetWriter and add member fixup to it. The overridden
version of ReorderRelocs (MipsELFObjectWriter::ReorderRelocs) needs
access to ELFRelocationEntry::Type and MCFixup::Value to reorder the
relocations.

Do you think these changes are acceptable?

On Wed, Mar 21, 2012 at 3:50 PM, Jim Grosbach <grosbach at apple.com> wrote:
> Hi Akira,
>
> If I follow correctly, the relocation entries can thus be in a different order than the instructions that they're for? That seems a bit odd, but I suppose there's nothing inherently wrong with that. It's just not something, AFAIK, that llvm has had to deal with before. This should definitely be a target-specific thing, not a general ELFObjectWriter thing, as other targets may have entirely different needs. Offhand, it seems reasonable to have a post-processing pass over the relocation list before it's written out to the file. The target can manipulate the list in whatever manner it needs to. A hook on MCELFObjectTargetWriter should do the trick.
>
> -Jim
>
>
> On Mar 19, 2012, at 1:39 PM, Akira Hatanaka <ahatanak at gmail.com> wrote:
>
>> What would be the best way to sort relocation entries before they are
>> written out in ELFObjectWriter::WriteRelocationsFragment?
>>
>> According to the Mips ABI documents I have, there are certain
>> restrictions on the order relocations appear in the table (e.g.
>> R_MIPS_HI16 and R_MIPS_GOT16 must be followed immediately by a
>> R_MIPS_LO16). When I enable post RA scheduling, some of the
>> restrictions are violated in the generated object code, which results
>> in incorrect relocation values generated by the linker.
>>
>> I am considering imitating what gas does in function mips_frob_file
>> (line 15522 of tc-mips.c) to fix this problem:
>>
>> http://repo.or.cz/w/binutils.git/blob/master:/gas/config/tc-mips.c
>>
>> Are there any other targets that have similar restrictions or requirements?
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>