Re-enable a hook in MCELFObjectTargetWriter to allow target-specific relocation table sorting and use this hook for Mips.

[vstefanovic]

Summary

Some targets (ie. Mips) have additional rules for ordering the relocation table
entries. Allow them to override generic sortRelocs(), which sorts entries by
Offset.
Then override this function for Mips, to emit HI16 and GOT16 relocations against
the local symbol in pair with the corresponding LO16 relocation.

[tomatabacu]

FYI, this is also needed for assembling Linux for MIPS with the IAS.

[• rafael]

Please check the excellent description Simon gave of what are the restrictions in the thread about r205200.

From that thread, my understanding of what is odd about mips objects in this case is that a a lo relocation (R_MIPS_LO16, R_MIPS16_LO16, R_MICROMIPS_LO16, R_MICROMIPS_HI0_LO16) matches *all* preceding hi/got relocations (R_MIPS_GOT16, R_MIPS16_GOT16, R_MICROMIPS_GOT16, R_MIPS_HI16, R_MIPS16_HI16, R_MICROMIPS_HI16).

Now, what is the semantic of the assembly file? From this code it looks like it is that a lo relocation would match *any* hi relocation with the same symbol if one is present. The search is done on an unordered relocation array, so which one it matches is undefined. This would still be an issue since the mips output will now be non-deterministic, no?

It that is really the desired behavior, you could just

• Sort by symbol.
• If same symbol, sort by type to put HI before LO
• sort by whatever else to make the output deterministic.

The current implementation is also N^2.

It should handle (and test) all relevant relocations.
It should include a large comment explaining

• What are the semantics of the .o (i.e., how will the linker handle them. Something along the lines of Simon's description)
• What are the semantics of the .s files.
• What the code is doing to match one to the other.

[vstefanovic]

Hi Rafael, thanks for the link and the review.

About the relocations that must match another:

-mips32, mips64:
R_MIPS_HI16 and local R_MIPS_GOT16 must match R_MIPS_LO16 against the same
symbol.

-micromips:
R_MICROMIPS_HI16 and local R_MICROMIPS_GOT16 must match R_MICROMIPS_LO16
against the same symbol.

-mips16:
R_MIPS16_HI16 and local R_MIPS16_GOT16 must match R_MIPS16_LO16 against the same
symbol.

Now, since mips16 and micromips are a work in progress, I would rather skip
handling them for now (ie. return generic sortRelocs() and add a TODO for the
HI16/GOT16 exceptions). E.g., instead of R_MICROMIPS_LO16, llvm currently
generates R_MIPS_LO16, so I can't even add a micromips test that will pass at
the moment.

For the deterministic output - in the examples I ran, when entering sortRelocs()
relocs were sorted by offset in the ascending order. But I will add a call to
generic sortRelocs() at the beginning of the function, to make the output
deterministic for sure.

And, apart from HI16/GOT16, I would like to sort relocs by offset - like other
architectures and mips gcc do.

A quote from binutils source (binutils/bfd/elfxx-mips.c):

The ABI requires that the *LO16 immediately follow the *HI16.
However, as a GNU extension, we permit an arbitrary number of
*HI16s to be associated with a single *LO16.

The logic I used in the code below is the simplest I came up with to obey the
rule above: for every HI16 / local GOT16 relocation at the given offset, pair it
with the first found LO16 relocation against the same symbol, starting from
offset + 4 and ending at offset -4. (Wrap around reloc table size.)

GCC does it differently; here is a comment about it from
binutils/gas/config/tc-mips.c:

When several %lo()s match a particular %got() or %hi(), we use the
following rules to distinguish them:

  (1) %lo()s with smaller offsets are a better match than %lo()s with
      higher offsets.

  (2) %lo()s with no matching %got() or %hi() are better than those
      that already have a matching %got() or %hi().

  (3) later %lo()s are better than earlier %lo()s.
These rules are applied in order.

Thus, for this example:

lui    $2, %hi(func2)
lui    $2, %hi(func2)
addiu  $2, $2, %lo(func2)
addiu  $2, $2, %lo(func2)

the code below sorts the table like this:
Offset Info Type Sym.Value Sym. Name
00000000 00000605 R_MIPS_HI16 00000000 func2
00000004 00000605 R_MIPS_HI16 00000000 func2
00000008 00000606 R_MIPS_LO16 00000000 func2
0000000c 00000606 R_MIPS_LO16 00000000 func2

and this is what gcc does:
Offset Info Type Sym.Value Sym. Name
00000004 00000605 R_MIPS_HI16 00000000 func2
00000008 00000606 R_MIPS_LO16 00000000 func2
00000000 00000605 R_MIPS_HI16 00000000 func2
0000000c 00000606 R_MIPS_LO16 00000000 func2

So, at least for consistency reasons, maybe I should change this code to behave
like gcc. What do you think?

[tomatabacu]

Ping.

[• rafael]

About the relocations that must match another:

-mips32, mips64:
R_MIPS_HI16 and local R_MIPS_GOT16 must match R_MIPS_LO16 against the same
symbol.

-micromips:
R_MICROMIPS_HI16 and local R_MICROMIPS_GOT16 must match R_MICROMIPS_LO16
against the same symbol.

-mips16:
R_MIPS16_HI16 and local R_MIPS16_GOT16 must match R_MIPS16_LO16 against the same
symbol.

And it is not possible for a file to mix relocations from these sets? I.E, no file will ever have a R_MIPS16_LO16 and a R_MIPS_HI16? If that is not the case I think there is a bug in gold :-)

Now, since mips16 and micromips are a work in progress, I would rather skip
handling them for now (ie. return generic sortRelocs() and add a TODO for the
HI16/GOT16 exceptions). E.g., instead of R_MICROMIPS_LO16, llvm currently
generates R_MIPS_LO16, so I can't even add a micromips test that will pass at
the moment.

That is fine. An assert would be better than a comment to make sure it gets implemented :-)

For the deterministic output - in the examples I ran, when entering sortRelocs()
relocs were sorted by offset in the ascending order. But I will add a call to
generic sortRelocs() at the beginning of the function, to make the output
deterministic for sure.

Yes, I honestly cannot remember where the non determinism was coming from, but I do remember the original function sorting only by Offest and we having issues.

And, apart from HI16/GOT16, I would like to sort relocs by offset - like other
architectures and mips gcc do.

MC suffer a lot from trying to produce object files that look like what gas produces. I know this is mostly my fault, but if I can help us move to a point where every 'if' in the writer has a good justification that would be awesome.

A quote from binutils source (binutils/bfd/elfxx-mips.c):

The ABI requires that the *LO16 immediately follow the *HI16.
However, as a GNU extension, we permit an arbitrary number of
*HI16s to be associated with a single *LO16.

Check. It seems to be what gold implements.

The logic I used in the code below is the simplest I came up with to obey the
rule above: for every HI16 / local GOT16 relocation at the given offset, pair it
with the first found LO16 relocation against the same symbol, starting from
offset + 4 and ending at offset -4. (Wrap around reloc table size.)

That is something that needs to be explicitly documented, since it is the semantic of the of assembly file, which is potentially an user input.

GCC does it differently; here is a comment about it from
binutils/gas/config/tc-mips.c:

When several %lo()s match a particular %got() or %hi(), we use the
following rules to distinguish them:

  (1) %lo()s with smaller offsets are a better match than %lo()s with
      higher offsets.

  (2) %lo()s with no matching %got() or %hi() are better than those
      that already have a matching %got() or %hi().

  (3) later %lo()s are better than earlier %lo()s.
These rules are applied in order.

Thus, for this example:

lui    $2, %hi(func2)
lui    $2, %hi(func2)
addiu  $2, $2, %lo(func2)
addiu  $2, $2, %lo(func2)

the code below sorts the table like this:
Offset Info Type Sym.Value Sym. Name
00000000 00000605 R_MIPS_HI16 00000000 func2
00000004 00000605 R_MIPS_HI16 00000000 func2
00000008 00000606 R_MIPS_LO16 00000000 func2
0000000c 00000606 R_MIPS_LO16 00000000 func2

and this is what gcc does:
Offset Info Type Sym.Value Sym. Name
00000004 00000605 R_MIPS_HI16 00000000 func2
00000008 00000606 R_MIPS_LO16 00000000 func2
00000000 00000605 R_MIPS_HI16 00000000 func2
0000000c 00000606 R_MIPS_LO16 00000000 func2

So, at least for consistency reasons, maybe I should change this code to behave
like gcc. What do you think?

I agree. We should implement the same *semantics* as gas.

In the above comment, what does "match", "earlier" and "in order" mean?

[vstefanovic]

A new version of the patch is uploaded.

[vstefanovic]

(Some comments disappeared from the previous message.)

And it is not possible for a file to mix relocations from these sets? I.E, no file will ever have a R_MIPS16_LO16 and a R_MIPS_HI16? If that is not the case I think there is a bug in gold :-)

Well, you can have this in a .S file:

lui  $2,%hi(sym1)

.set mips16

li   $2,%lo(sym1)

Then relocations would be:
00000000 00000605 R_MIPS_HI16 00000000 sym1
00000004 00000669 R_MIPS16_LO16 00000000 sym1

so the first relocation wouldn't match the second.

In the above comment, what does "match", "earlier" and "in order" mean?

'match' for a *HI16 relocation is a matching LO16 relocation, ie. the one
against the same symbol and with the appropriate *LO16 relocation type.
'earlier' means smaller offset.
'in order' is similar to our cmpRel() sorting function - apply the first rule,
and if the output isn't deterministic yet, apply the second one, etc.

[• rafael]

lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp

29 ↗

(On Diff #21582)

Please use the same names for arguments and fields so that you have
... : foo(foo), bar(bar) ... {

33 ↗

(On Diff #21582)

Can this be a

const ELFRelocationEntry &Reloc;

?

39 ↗

(On Diff #21582)

Why do you need to store this?

278 ↗

(On Diff #21582)

Why is that?

279 ↗

(On Diff #21582)

Distributing the ! is probably more readable:

Reloc.Type != ... && Reloc.Type !=

also, put a

unsigned Type = Roloc.Type;

at the start of the function so you don't have to type" Reloc." all the time.

285 ↗

(On Diff #21582)

Use an earlier return

if (MCELF::GetBinding(SD) != ELF::STB_LOCAL)

return ELF::R_MIPS_NONE;

296 ↗

(On Diff #21582)

Start variable names with an upper case letter.

309 ↗

(On Diff #21582)

Why -1?
This looks like a leftover from the sort function not considering a relocation own offset to break ties.

335 ↗

(On Diff #21582)

This wording is a bit soft.

Assembly is user input, and if gnu as matches a %lo and a %hi differently from what we do we would be producing a .o with different semantics.

344 ↗

(On Diff #21582)

This description makes it sound like that given

lui $2, %hi(func2)
lui $2, %hi(func2)
addiu $2, $2, %lo(func2)
addiu $2, $2, %lo(func2)

the second %hi would be matched with the second %lo, but in a previous comment you said that gas produces

00000004 00000605 R_MIPS_HI16 00000000 func2
00000008 00000606 R_MIPS_LO16 00000000 func2
00000000 00000605 R_MIPS_HI16 00000000 func2
0000000c 00000606 R_MIPS_LO16 00000000 func2

That is, the second %hi (offset 4) is matched with the first lo (offset 8).

353 ↗

(On Diff #21582)

Please git-clang-format the patch.

366 ↗

(On Diff #21582)

Why is this first check for I and I-1 necessary? The main loop should handle it, no?

test/MC/Mips/sort-relocation-table.s

6 ↗

(On Diff #21582)

Can you add a comment about the gnu as target and command line that can be used to compare the result of this file?

[vstefanovic]

lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp

29 ↗

(On Diff #21582)

OK.

33 ↗

(On Diff #21582)

It can be const, but '&' would bring down the last step, which copies sorted MipsRelocs back to Relocs.

39 ↗

(On Diff #21582)

It isn't necessary, I can always call getMatchingLoType() instead, which I did in the updated patch.

278 ↗

(On Diff #21582)

Just to skip calling Asm.getSymbolData() for the relocations that will return R_MIPS_NONE anyway. I removed it.

285 ↗

(On Diff #21582)

OK.

309 ↗

(On Diff #21582)

'-1' simplifies the sort function.

If omitting '-1', the rules for entries with the same SortOffset would be:
-if one is %hi, that one should be first;
-if both are %hi, sort them by Offset (in descending order).

So '-1' practically applies the first rule, and the sorting function only needs to handle the second case.

335 ↗

(On Diff #21582)

How about:

​// When there is more than one way to sort the table while respecting the ABI
​// rule, we try to implement the same semantics as gnu as, ie. we try to match
// a HI and a LO the same way gnu as does.

344 ↗

(On Diff #21582)

That's right, because the second %hi is already followed by a %lo. So the sentence about finding the matching %lo applies only to the first %hi, which gets matched with the second %lo.
I tried to be clearer in the next paragraph, with "don't look for a 'better' match for the HIs that are already followed with a matching LO".

353 ↗

(On Diff #21582)

Sure.

366 ↗

(On Diff #21582)

It finds 'non-free' %lo's, ie. the ones that are already preceded with a %hi. Then it's easier for the main loop to find a 'free' %lo for a %hi, which are preferred over the 'non-free' ones. As an addition, it remembers %hi's with a matched %lo so the main loop can early exit for them.

test/MC/Mips/sort-relocation-table.s

6 ↗

(On Diff #21582)

Added.

[• rafael]

Why -1?
This looks like a leftover from the sort function not considering a relocation own offset to break ties.

'-1' simplifies the sort function.

If omitting '-1', the rules for entries with the same SortOffset would be:
-if one is %hi, that one should be first;
-if both are %hi, sort them by Offset (in descending order).

So '-1' practically applies the first rule, and the sorting function only needs to handle the second case.

But it cant introduce a wrong result if another relocation is 1 byte
away, no? We just know that that is not possible? If so please add a
comment about that.

Assembly is user input, and if gnu as matches a %lo and a %hi differently from what we do we would be producing a .o with different semantics.

How about:

// When there is more than one way to sort the table while respecting the ABI
// rule, we try to implement the same semantics as gnu as, ie. we try to match
// a HI and a LO the same way gnu as does.

Still not there. Which relocation gets matched to another is part of
of the semantics of the assembly file. We have to match gas or
document that we are incompatible.

Comment at: lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp:366
@@ +365,3 @@
+ // Also find HIs and LOs that are already matched.
+ if (I > 0 && areMatchingHiAndLo(MipsRelocs[I], MipsRelocs[I-1]))

+ setMatch(MipsRelocs[I], MipsRelocs[I-1]);

rafael wrote:

Why is this first check for I and I-1 necessary? The main loop should handle it, no?

It finds 'non-free' %lo's, ie. the ones that are already preceded with a %hi. Then it's easier for the main loop to find a 'free' %lo for a %hi, which are preferred over the 'non-free' ones. As an addition, it remembers %hi's with a matched %lo so the main loop can early exit for them.

The rules around this area are pretty fuzzy. Lets try to make the code
as direct as possible on the first implementation at least. Could you
please remove this case and let the main loop handle it?

I will take another look in phab.

[• rafael]

LGTM in that

• It is clear from how linkers behave that something has to be done to sort the entries for Mips.
• The api change is reasonable: making sortRelocs virtual.

[vstefanovic]

But it cant introduce a wrong result if another relocation is 1 byte
away, no? We just know that that is not possible? If so please add a
comment about that.

Yes, Mips instructions length is fixed and at least 2 bytes (2 for micromips and mips16, 4 for mips32 and mips64), so there will always be 2 or 4 bytes offset between 2 instructions.

Still not there. Which relocation gets matched to another is part of
of the semantics of the assembly file. We have to match gas or
document that we are incompatible.

Copied the sentence from the generic sortRelocs().

Comment at: lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp:366
@@ +365,3 @@
+ // Also find HIs and LOs that are already matched.
+ if (I > 0 && areMatchingHiAndLo(MipsRelocs[I], MipsRelocs[I-1]))

+ setMatch(MipsRelocs[I], MipsRelocs[I-1]);

rafael wrote:

Why is this first check for I and I-1 necessary? The main loop should handle it, no?

It finds 'non-free' %lo's, ie. the ones that are already preceded with a %hi. Then it's easier for the main loop to find a 'free' %lo for a %hi, which are preferred over the 'non-free' ones. As an addition, it remembers %hi's with a matched %lo so the main loop can early exit for them.

The rules around this area are pretty fuzzy. Lets try to make the code
as direct as possible on the first implementation at least. Could you
please remove this case and let the main loop handle it?

Moved to the main loop.

[• rafael]

Still not there. Which relocation gets matched to another is part of

of the semantics of the assembly file. We have to match gas or

document that we are incompatible.

Copied the sentence from the generic sortRelocs().

That is a very different case. That is about ELF, not mips-ELF.

On ELF, the order is not important, and we just need to make sure it
is deterministic. On mips-ELF it is part of the semantics of the .o.

[vstefanovic]

In D7414#147888, @rafael wrote:

Still not there. Which relocation gets matched to another is part of

of the semantics of the assembly file. We have to match gas or

document that we are incompatible.

Copied the sentence from the generic sortRelocs().

That is a very different case. That is about ELF, not mips-ELF.

On ELF, the order is not important, and we just need to make sure it
is deterministic. On mips-ELF it is part of the semantics of the .o.

// There may be more ways to sort the table while respecting the ABI rule;
// we always sort the same way gnu as does, for compatibility.

[• rafael]

// There may be more ways to sort the table while respecting the ABI rule;
// we always sort the same way gnu as does, for compatibility.

Still not particularly clear. We *have* to sort it in a way that
causes bfd ld to match the same hi and lo relocations as would be
matched had the .s been assembled by gas.

Cheers,
Rafael

[vstefanovic]

In D7414#150147, @rafael wrote:

// There may be more ways to sort the table while respecting the ABI rule;
// we always sort the same way gnu as does, for compatibility.

Still not particularly clear. We *have* to sort it in a way that
causes bfd ld to match the same hi and lo relocations as would be
matched had the .s been assembled by gas.

Cheers,
Rafael

Ok, a new one:

We are reusing gnu as sorting algorithm so we are emitting the relocation
table sorted the same way as gnu as would sort it.

[vstefanovic]

But we are sorting the table exactly as gas only for easier comparison of the generated o files, aren't we?

The linker must not produce different results if it matches a hi with a different lo, as long as their types match (R_MIPS_HI16 with R_MIPS_LO16, etc.) and are against the same symbol.

E.g.:

0x0: lui $2,%hi(sym)
0x4: addiu $2,$2,%lo(sym)
0x8: addiu $2,$2,%lo(sym)
0xc: lui $2,%hi(sym)

The ABI and the extension allow hi at 0xc to be put before any of two lo's, and the linker must properly calculate the address in both cases. If it didn't, it would be a linker bug.

Regards,
Vladimir

[vstefanovic]

A rebase.

[• rafael]

Fine by me.

I am convinced that we need the hook and I am not the best reviewer for the mips stuff.

llvm/trunk/include/llvm/MC/MCELFObjectWriter.h

 class MCFixup;
 class MCFragment;
 class MCObjectWriter;
 class MCSectionData;
 class MCSymbol;
 class MCSymbolData;
 class MCValue;
 
+struct ELFRelocationEntry {
+  uint64_t Offset; // Where is the relocation.
+  const MCSymbol *Symbol;       // The symbol to relocate with.
+  unsigned Type;   // The type of the relocation.
+  uint64_t Addend; // The addend to use.
+
+  ELFRelocationEntry(uint64_t Offset, const MCSymbol *Symbol, unsigned Type,
+                     uint64_t Addend)
+      : Offset(Offset), Symbol(Symbol), Type(Type), Addend(Addend) {}
+};
+
 class MCELFObjectTargetWriter {
   const uint8_t OSABI;
   const uint16_t EMachine;
   const unsigned HasRelocationAddend : 1;
   const unsigned Is64Bit : 1;
   const unsigned IsN64 : 1;
 
 protected:
public:
   virtual ~MCELFObjectTargetWriter() {}
 
   virtual unsigned GetRelocType(const MCValue &Target, const MCFixup &Fixup,
                                 bool IsPCRel) const = 0;
 
   virtual bool needsRelocateWithSymbol(const MCSymbolData &SD,
                                        unsigned Type) const;
 
+  virtual void sortRelocs(const MCAssembler &Asm,
+                          std::vector<ELFRelocationEntry> &Relocs);
+
   /// @name Accessors
   /// @{
   uint8_t getOSABI() const { return OSABI; }
   uint16_t getEMachine() const { return EMachine; }
   bool hasRelocationAddend() const { return HasRelocationAddend; }
   bool is64Bit() const { return Is64Bit; }
   bool isN64() const { return IsN64; }
   /// @}

llvm/trunk/lib/MC/ELFObjectWriter.cpp

public:
   SymbolTableWriter(MCAssembler &Asm, FragmentWriter &FWriter, bool Is64Bit,
                     SectionIndexMapTy &SectionIndexMap,
                     MCDataFragment *SymtabF);
 
   void writeSymbol(uint32_t name, uint8_t info, uint64_t value, uint64_t size,
                    uint8_t other, uint32_t shndx, bool Reserved);
 };
 
-struct ELFRelocationEntry {
-  uint64_t Offset; // Where is the relocation.
-  const MCSymbol *Symbol;       // The symbol to relocate with.
-  unsigned Type;   // The type of the relocation.
-  uint64_t Addend; // The addend to use.
-
-  ELFRelocationEntry(uint64_t Offset, const MCSymbol *Symbol, unsigned Type,
-                     uint64_t Addend)
-      : Offset(Offset), Symbol(Symbol), Type(Type), Addend(Addend) {}
-};
-
 class ELFObjectWriter : public MCObjectWriter {
   FragmentWriter FWriter;
 
   protected:
 
     static bool isFixupKindPCRel(const MCAssembler &Asm, unsigned Kind);
     static bool RelocNeedsGOT(MCSymbolRefExpr::VariantKind Variant);
     static uint64_t SymbolValue(MCSymbolData &Data, const MCAsmLayout &Layout);
void ELFObjectWriter::WriteSecHdrEntry(uint32_t Name, uint32_t Type,
   WriteWord(Offset);    // sh_offset
   WriteWord(Size);      // sh_size
   Write32(Link);        // sh_link
   Write32(Info);        // sh_info
   WriteWord(Alignment); // sh_addralign
   WriteWord(EntrySize); // sh_entsize
 }
 
-// ELF doesn't require relocations to be in any order. We sort by the r_offset,
-// just to match gnu as for easier comparison. The use type is an arbitrary way
-// of making the sort deterministic.
-static int cmpRel(const ELFRelocationEntry *AP, const ELFRelocationEntry *BP) {
-  const ELFRelocationEntry &A = *AP;
-  const ELFRelocationEntry &B = *BP;
-  if (A.Offset != B.Offset)
-    return B.Offset - A.Offset;
-  if (B.Type != A.Type)
-    return A.Type - B.Type;
-  //llvm_unreachable("ELFRelocs might be unstable!");
-  return 0;
-}
-
-static void sortRelocs(const MCAssembler &Asm,
-                       std::vector<ELFRelocationEntry> &Relocs) {
-  array_pod_sort(Relocs.begin(), Relocs.end(), cmpRel);
-}
-
 void ELFObjectWriter::WriteRelocationsFragment(const MCAssembler &Asm,
                                                MCDataFragment *F,
                                                const MCSectionData *SD) {
   std::vector<ELFRelocationEntry> &Relocs = Relocations[SD];
 
-  sortRelocs(Asm, Relocs);
+  // Sort the relocation entries. Most targets just sort by Offset, but some
+  // (e.g., MIPS) have additional constraints.
+  TargetObjectWriter->sortRelocs(Asm, Relocs);
 
   for (unsigned i = 0, e = Relocs.size(); i != e; ++i) {
     const ELFRelocationEntry &Entry = Relocs[e - i - 1];
     unsigned Index =
         Entry.Symbol ? getSymbolIndexInSymbolTable(Asm, Entry.Symbol) : 0;
 
     if (is64Bit()) {
       write(*F, Entry.Offset);

llvm/trunk/lib/MC/MCELFObjectTargetWriter.cpp

: OSABI(OSABI_), EMachine(EMachine_),
     HasRelocationAddend(HasRelocationAddend_), Is64Bit(Is64Bit_),
     IsN64(IsN64_){
 }
 
 bool MCELFObjectTargetWriter::needsRelocateWithSymbol(const MCSymbolData &SD,
                                                       unsigned Type) const {
   return false;
 }
+
+// ELF doesn't require relocations to be in any order. We sort by the Offset,
+// just to match gnu as for easier comparison. The use type is an arbitrary way
+// of making the sort deterministic.
+static int cmpRel(const ELFRelocationEntry *AP, const ELFRelocationEntry *BP) {
+  const ELFRelocationEntry &A = *AP;
+  const ELFRelocationEntry &B = *BP;
+  if (A.Offset != B.Offset)
+    return B.Offset - A.Offset;
+  if (B.Type != A.Type)
+    return A.Type - B.Type;
+  //llvm_unreachable("ELFRelocs might be unstable!");
+  return 0;
+}
+
+
+void
+MCELFObjectTargetWriter::sortRelocs(const MCAssembler &Asm,
+                                    std::vector<ELFRelocationEntry> &Relocs) {
+  array_pod_sort(Relocs.begin(), Relocs.end(), cmpRel);
+}

llvm/trunk/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp

 //===-- MipsELFObjectWriter.cpp - Mips ELF Writer -------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "MCTargetDesc/MipsBaseInfo.h"
 #include "MCTargetDesc/MipsFixupKinds.h"
 #include "MCTargetDesc/MipsMCTargetDesc.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/MC/MCAssembler.h"
 #include "llvm/MC/MCELF.h"
 #include "llvm/MC/MCELFObjectWriter.h"
 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCSection.h"
 #include "llvm/MC/MCValue.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <list>
 
 using namespace llvm;
 
 namespace {
+// A helper structure based on ELFRelocationEntry, used for sorting entries in
+// the relocation table.
+struct MipsRelocationEntry {
+  MipsRelocationEntry(const ELFRelocationEntry &R)
+      : R(R), SortOffset(R.Offset), HasMatchingHi(false) {}
+  const ELFRelocationEntry R;
+  // SortOffset equals R.Offset except for the *HI16 relocations, for which it
+  // will be set based on the R.Offset of the matching *LO16 relocation.
+  int64_t SortOffset;
+  // True when this is a *LO16 relocation chosen as a match for a *HI16
+  // relocation.
+  bool HasMatchingHi;
+};
+
   class MipsELFObjectWriter : public MCELFObjectTargetWriter {
   public:
     MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI,
                         bool _isN64, bool IsLittleEndian);
 
     ~MipsELFObjectWriter() override;
 
     unsigned GetRelocType(const MCValue &Target, const MCFixup &Fixup,
                           bool IsPCRel) const override;
     bool needsRelocateWithSymbol(const MCSymbolData &SD,
                                  unsigned Type) const override;
+    virtual void sortRelocs(const MCAssembler &Asm,
+                            std::vector<ELFRelocationEntry> &Relocs) override;
   };
 }
 
 MipsELFObjectWriter::MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI,
                                          bool _isN64, bool IsLittleEndian)
     : MCELFObjectTargetWriter(_is64Bit, OSABI, ELF::EM_MIPS,
                               /*HasRelocationAddend*/ _isN64,
                               /*IsN64*/ _isN64) {}
case Mips::fixup_MIPS_PCHI16:
     break;
   case Mips::fixup_MIPS_PCLO16:
     Type = ELF::R_MIPS_PCLO16;
     break;
   }
   return Type;
 }
 
+// Sort entries by SortOffset in descending order.
+// When there are more *HI16 relocs paired with one *LO16 reloc, the 2nd rule
+// sorts them in ascending order of R.Offset.
+static int cmpRelMips(const MipsRelocationEntry *AP,
+                      const MipsRelocationEntry *BP) {
+  const MipsRelocationEntry &A = *AP;
+  const MipsRelocationEntry &B = *BP;
+  if (A.SortOffset != B.SortOffset)
+    return B.SortOffset - A.SortOffset;
+  if (A.R.Offset != B.R.Offset)
+    return A.R.Offset - B.R.Offset;
+  if (B.R.Type != A.R.Type)
+    return B.R.Type - A.R.Type;
+  //llvm_unreachable("ELFRelocs might be unstable!");
+  return 0;
+}
+
+// For the given Reloc.Type, return the matching relocation type, as in the
+// table below.
+static unsigned getMatchingLoType(const MCAssembler &Asm,
+                                  const ELFRelocationEntry &Reloc) {
+  unsigned Type = Reloc.Type;
+  if (Type == ELF::R_MIPS_HI16)
+    return ELF::R_MIPS_LO16;
+  if (Type == ELF::R_MICROMIPS_HI16)
+    return ELF::R_MICROMIPS_LO16;
+  if (Type == ELF::R_MIPS16_HI16)
+    return ELF::R_MIPS16_LO16;
+
+  const MCSymbolData &SD = Asm.getSymbolData(*Reloc.Symbol);
+
+  if (MCELF::GetBinding(SD) != ELF::STB_LOCAL)
+    return ELF::R_MIPS_NONE;
+
+  if (Type == ELF::R_MIPS_GOT16)
+    return ELF::R_MIPS_LO16;
+  if (Type == ELF::R_MICROMIPS_GOT16)
+    return ELF::R_MICROMIPS_LO16;
+  if (Type == ELF::R_MIPS16_GOT16)
+    return ELF::R_MIPS16_LO16;
+
+  return ELF::R_MIPS_NONE;
+}
+
+// Return true if First needs a matching *LO16, its matching *LO16 type equals
+// Second's type and both relocations are against the same symbol.
+static bool areMatchingHiAndLo(const MCAssembler &Asm,
+                               const ELFRelocationEntry &First,
+                               const ELFRelocationEntry &Second) {
+  return getMatchingLoType(Asm, First) != ELF::R_MIPS_NONE &&
+         getMatchingLoType(Asm, First) == Second.Type &&
+         First.Symbol && First.Symbol == Second.Symbol;
+}
+
+// Return true if MipsRelocs[Index] is a *LO16 preceded by a matching *HI16.
+static bool
+isPrecededByMatchingHi(const MCAssembler &Asm, uint32_t Index,
+                       std::vector<MipsRelocationEntry> &MipsRelocs) {
+  return Index < MipsRelocs.size() - 1 &&
+         areMatchingHiAndLo(Asm, MipsRelocs[Index + 1].R, MipsRelocs[Index].R);
+}
+
+// Return true if MipsRelocs[Index] is a *LO16 not preceded by a matching *HI16
+// and not chosen by a *HI16 as a match.
+static bool isFreeLo(const MCAssembler &Asm, uint32_t Index,
+                     std::vector<MipsRelocationEntry> &MipsRelocs) {
+  return Index < MipsRelocs.size() && !MipsRelocs[Index].HasMatchingHi &&
+         !isPrecededByMatchingHi(Asm, Index, MipsRelocs);
+}
+
+// Lo is chosen as a match for Hi, set their fields accordingly.
+// Mips instructions have fixed length of at least two bytes (two for
+// micromips/mips16, four for mips32/64), so we can set HI's SortOffset to
+// matching LO's Offset minus one to simplify the sorting function.
+static void setMatch(MipsRelocationEntry &Hi, MipsRelocationEntry &Lo) {
+  Lo.HasMatchingHi = true;
+  Hi.SortOffset = Lo.R.Offset - 1;
+}
+
+// We sort relocation table entries by offset, except for one additional rule
+// required by MIPS ABI: every *HI16 relocation must be immediately followed by
+// the corresponding *LO16 relocation. We also support a GNU extension that
+// allows more *HI16s paired with one *LO16.
+//
+// *HI16 relocations and their matching *LO16 are:
+//
+// +---------------------------------------------+-------------------+
+// |               *HI16                         |  matching *LO16   |
+// |---------------------------------------------+-------------------|
+// |  R_MIPS_HI16, local R_MIPS_GOT16            |    R_MIPS_LO16    |
+// |  R_MICROMIPS_HI16, local R_MICROMIPS_GOT16  | R_MICROMIPS_LO16  |
+// |  R_MIPS16_HI16, local R_MIPS16_GOT16        |  R_MIPS16_LO16    |
+// +---------------------------------------------+-------------------+
+//
+// (local R_*_GOT16 meaning R_*_GOT16 against the local symbol.)
+//
+// To handle *HI16 and *LO16 relocations, the linker needs a combined addend
+// ("AHL") calculated from both *HI16 ("AHI") and *LO16 ("ALO") relocations:
+// AHL = (AHI << 16) + (short)ALO;
+//
+// We are reusing gnu as sorting algorithm so we are emitting the relocation
+// table sorted the same way as gnu as would sort it, for easier comparison of
+// the generated .o files.
+//
+// The logic is:
+// search the table (starting from the highest offset and going back to zero)
+// for all *HI16 relocations that don't have a matching *LO16.
+// For every such HI, find a matching LO with highest offset that isn't already
+// matched with another HI. If there are no free LOs, match it with the first
+// found (starting from lowest offset).
+// When there are more HIs matched with one LO, sort them in descending order by
+// offset.
+//
+// In other words, when searching for a matching LO:
+// - don't look for a 'better' match for the HIs that are already followed by a
+//   matching LO;
+// - prefer LOs without a pair;
+// - prefer LOs with higher offset;
+void MipsELFObjectWriter::sortRelocs(const MCAssembler &Asm,
+                                     std::vector<ELFRelocationEntry> &Relocs) {
+  if (Relocs.size() < 2)
+    return;
+
+  // The default function sorts entries by Offset in descending order.
+  MCELFObjectTargetWriter::sortRelocs(Asm, Relocs);
+
+  // Init MipsRelocs from Relocs.
+  std::vector<MipsRelocationEntry> MipsRelocs;
+  for (unsigned I = 0, E = Relocs.size(); I != E; ++I)
+    MipsRelocs.push_back(MipsRelocationEntry(Relocs[I]));
+
+  // Find a matching LO for all HIs that need it.
+  for (int32_t I = 0, E = MipsRelocs.size(); I != E; ++I) {
+    if (getMatchingLoType(Asm, MipsRelocs[I].R) == ELF::R_MIPS_NONE ||
+        (I > 0 && isPrecededByMatchingHi(Asm, I - 1, MipsRelocs)))
+      continue;
+
+    int32_t MatchedLoIndex = -1;
+
+    // Search the list in the ascending order of Offset.
+    for (int32_t J = MipsRelocs.size() - 1, N = -1; J != N; --J) {
+      // check for a match
+      if (areMatchingHiAndLo(Asm, MipsRelocs[I].R, MipsRelocs[J].R) &&
+          (MatchedLoIndex == -1 || // first match
+           // or we already have a match,
+           // but this one is with higher offset and it's free
+           (MatchedLoIndex > J && isFreeLo(Asm, J, MipsRelocs))))
+        MatchedLoIndex = J;
+    }
+
+    if (MatchedLoIndex != -1)
+      // We have a match.
+      setMatch(MipsRelocs[I], MipsRelocs[MatchedLoIndex]);
+  }
+
+  // SortOffsets are calculated, call the sorting function.
+  array_pod_sort(MipsRelocs.begin(), MipsRelocs.end(), cmpRelMips);
+
+  // Copy sorted MipsRelocs back to Relocs.
+  for (unsigned I = 0, E = MipsRelocs.size(); I != E; ++I)
+    Relocs[I] = MipsRelocs[I].R;
+}
+
 bool
 MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbolData &SD,
                                              unsigned Type) const {
   // FIXME: This is extremely conservative. This really needs to use a
   // whitelist with a clear explanation for why each realocation needs to
   // point to the symbol, not to the section.
   switch (Type) {
   default:

llvm/trunk/test/MC/Mips/sort-relocation-table.s

+# RUN: llvm-mc -filetype=obj -arch mipsel %s | llvm-readobj -r | FileCheck %s
+
+# Test the order of records in the relocation table.
+# *HI16 and local *GOT16 relocations should be immediately followed by the
+# corresponding *LO16 relocation against the same symbol.
+#
+# We try to implement the same semantics as gas, ie. to order the relocation
+# table the same way as gas.
+#
+# gnu as command line:
+# mips-linux-gnu-as -EL sort-relocation-table.s -o sort-relocation-table.o
+#
+# TODO: Add mips16 and micromips tests.
+# Note: offsets are part of expected output, so it's simpler to add new test
+#       cases at the bottom of the file.
+
+# CHECK:       Relocations [
+# CHECK-NEXT:  {
+
+# Put HI before LO.
+addiu $2,$2,%lo(sym1)
+lui $2,%hi(sym1)
+
+# CHECK-NEXT:    0x4 R_MIPS_HI16 sym1
+# CHECK-NEXT:    0x0 R_MIPS_LO16 sym1
+
+# When searching for a matching LO, ignore LOs against a different symbol.
+addiu $2,$2,%lo(sym2)
+lui $2,%hi(sym2)
+addiu $2,$2,%lo(sym2_d)
+
+# CHECK-NEXT:    0xC R_MIPS_HI16 sym2
+# CHECK-NEXT:    0x8 R_MIPS_LO16 sym2
+# CHECK-NEXT:    0x10 R_MIPS_LO16 sym2_d
+
+# Match HI with 2nd LO because it has higher offset (than the 1st LO).
+addiu $2,$2,%lo(sym3)
+addiu $2,$2,%lo(sym3)
+lui $2,%hi(sym3)
+
+# CHECK-NEXT:    0x14 R_MIPS_LO16 sym3
+# CHECK-NEXT:    0x1C R_MIPS_HI16 sym3
+# CHECK-NEXT:    0x18 R_MIPS_LO16 sym3
+
+# HI is already followed by a matching LO, so don't look further, ie. ignore the
+# "free" LO with higher offset.
+lui $2,%hi(sym4)
+addiu $2,$2,%lo(sym4)
+addiu $2,$2,%lo(sym4)
+
+# CHECK-NEXT:    0x20 R_MIPS_HI16 sym4
+# CHECK-NEXT:    0x24 R_MIPS_LO16 sym4
+# CHECK-NEXT:    0x28 R_MIPS_LO16 sym4
+
+# Match 2nd HI with 2nd LO, since it's the one with highest offset among the
+# "free" ones.
+addiu $2,$2,%lo(sym5)
+addiu $2,$2,%lo(sym5)
+lui $2,%hi(sym5)
+addiu $2,$2,%lo(sym5)
+lui $2,%hi(sym5)
+
+# CHECK-NEXT:    0x2C R_MIPS_LO16 sym5
+# CHECK-NEXT:    0x3C R_MIPS_HI16 sym5
+# CHECK-NEXT:    0x30 R_MIPS_LO16 sym5
+# CHECK-NEXT:    0x34 R_MIPS_HI16 sym5
+# CHECK-NEXT:    0x38 R_MIPS_LO16 sym5
+
+# When more HIs are matched with one LO, sort them in descending order of
+# offset.
+addiu $2,$2,%lo(sym6)
+lui $2,%hi(sym6)
+lui $2,%hi(sym6)
+
+# CHECK-NEXT:    0x48 R_MIPS_HI16 sym6
+# CHECK-NEXT:    0x44 R_MIPS_HI16 sym6
+# CHECK-NEXT:    0x40 R_MIPS_LO16 sym6
+
+#  sym7 is a local symbol, so GOT relocation against it needs a matching LO.
+sym7:
+addiu $2,$2,%lo(sym7)
+lui $2,%got(sym7)
+
+# CHECK-NEXT:    0x50 R_MIPS_GOT16 sym7
+# CHECK-NEXT:    0x4C R_MIPS_LO16 sym7
+
+# sym8 is not a local symbol, don't look for a matching LO for GOT.
+.global sym8
+addiu $2,$2,%lo(sym8)
+lui $2,%got(sym8)
+
+# CHECK-NEXT:    0x54 R_MIPS_LO16 sym8
+# CHECK-NEXT:    0x58 R_MIPS_GOT16 sym8
+
+# A small combination of previous checks.
+symc1:
+addiu $2,$2,%lo(symc1)
+addiu $2,$2,%lo(symc1)
+addiu $2,$2,%lo(symc1)
+lui $2,%hi(symc1)
+lui $2,%got(symc1)
+addiu $2,$2,%lo(symc2)
+lui $2,%hi(symc1)
+lui $2,%hi(symc1)
+lui $2,%got(symc2)
+lui $2,%hi(symc1)
+addiu $2,$2,%lo(symc1)
+addiu $2,$2,%lo(symc2)
+lui $2,%hi(symc1)
+lui $2,%hi(symc1)
+
+# CHECK-NEXT:    0x78 R_MIPS_HI16 symc1
+# CHECK-NEXT:    0x74 R_MIPS_HI16 symc1
+# CHECK-NEXT:    0x6C R_MIPS_GOT16 symc1
+# CHECK-NEXT:    0x68 R_MIPS_HI16 symc1
+# CHECK-NEXT:    0x5C R_MIPS_LO16 symc1
+# CHECK-NEXT:    0x8C R_MIPS_HI16 symc1
+# CHECK-NEXT:    0x60 R_MIPS_LO16 symc1
+# CHECK-NEXT:    0x90 R_MIPS_HI16 symc1
+# CHECK-NEXT:    0x64 R_MIPS_LO16 symc1
+# CHECK-NEXT:    0x70 R_MIPS_LO16 symc2
+# CHECK-NEXT:    0x7C R_MIPS_GOT16 symc2
+# CHECK-NEXT:    0x80 R_MIPS_HI16 symc1
+# CHECK-NEXT:    0x84 R_MIPS_LO16 symc1
+# CHECK-NEXT:    0x88 R_MIPS_LO16 symc2

llvm/trunk/test/MC/Mips/xgot.s

 // RUN: llvm-mc -filetype=obj -triple mipsel-unknown-linux  %s -o - | llvm-readobj -r | FileCheck %s
 
 // Check that the appropriate relocations were created.
 // For the xgot case we want to see R_MIPS_[GOT|CALL]_[HI|LO]16.
 
 // CHECK: Relocations [
 // CHECK:   0x0 R_MIPS_HI16 _gp_disp
 // CHECK:   0x4 R_MIPS_LO16 _gp_disp
 // CHECK:   0x14 R_MIPS_GOT_HI16 ext_1
 // CHECK:   0x1C R_MIPS_GOT_LO16 ext_1
 // CHECK:   0x24 R_MIPS_CALL_HI16 printf
-// CHECK:   0x2C R_MIPS_GOT16 $.str
 // CHECK:   0x30 R_MIPS_CALL_LO16 printf
+// CHECK:   0x2C R_MIPS_GOT16 $.str
 // CHECK:   0x38 R_MIPS_LO16 $.str
 // CHECK: ]
 
   .text
   .abicalls
   .section  .mdebug.abi32,"",@progbits
   .file "/home/espindola/llvm/llvm/test/MC/Mips/xgot.ll"
   .text