[mips][mcjit] Calculate correct addend for R_MIPS_HI16 and R_MIPS_PCHI16 relocations.

[vradosavljevic]

Summary

So far, for O32 ABI we didn't calculate correct addend for R_MIPS_HI16 and R_MIPS_PCHI16 relocations. This patch fixes that.

[vradosavljevic]

Ping.

[dsanders]

lib/ExecutionEngine/RuntimeDyld/RuntimeDyldELF.cpp

1334 ↗

(On Diff #29673)

Won't this get expensive when there's lots of relocations? SmallVectors is an array internally so insert() has to move the elements after the insertion point (i.e. all elements) to make room for the new one.

Can we use push_back() here and a backwards search below?

1337–1339 ↗

(On Diff #29673)

You could use a range-based for loop here at the moment. Unfortunately, fixing the comment above will prevent this. It should still use a for-loop instead of a while though.

1342–1344 ↗

(On Diff #29673)

This is almost certainly for a later patch but I'll mention it now. Does '.' work? For example:

lui $2, $3, %hi(. + 4)
addiu $2, $3, %lo(. + 4)

I'm thinking it won't work in the current code because '.' drops unique private labels each time it's used. There's also an interesting special case with '.' and relocs like R_MIPS_(HI|LO)16. The '.' refers to the address for the %hi and the distance between the %hi and %lo is added to the addend. This is quite useful but it surprised me when I tried it. I previously thought the '.' was the current position and the programmer had to manually account for the distance.

test/ExecutionEngine/RuntimeDyld/Mips/ELF_O32_PIC_relocations.s

64 ↗

(On Diff #29673)

Nit: indentation

[mpf]

lib/ExecutionEngine/RuntimeDyld/RuntimeDyldELF.cpp

1342–1344 ↗

(On Diff #29673)

Your description is wrong here. dot (.) always means instruction of the current instruction. You are confusing how this is then processed into a relocation. For pre-mips32r6 binutils will make the reference section relative which means that in a small test case it will look like dot refers to the first instruction when it is translated into a reference to the start of the section and an addend to hit the right instruction. You do need to manually account for the distance between the two instructions. Take a look at the relocations generated for mips32r6 for a clearer understanding as the relocs will not be made section relative there.

[dsanders]

lib/ExecutionEngine/RuntimeDyld/RuntimeDyldELF.cpp

1342–1344 ↗

(On Diff #29673)

Ah, I see my mistake(s) here. At the moment, our IAS doesn't convert the relocations to be section-relative so I'm used to seeing it symbol-relative and not section-relative. We need to fix that but it doesn't seem to do any harm so it's fairly low priority compared to the other issues. My test case also happened to be badly chosen with the %hi at offset zero from the start of the section. As a result the distance happened to be the same as the section-relative offset.

It's good to know that my original understanding was correct. Thanks

[vradosavljevic]

lib/ExecutionEngine/RuntimeDyld/RuntimeDyldELF.cpp

1337–1339 ↗

(On Diff #29673)

I think that I can't use a range-based for loop, because I'm removing elements from SmallVector.

1342–1344 ↗

(On Diff #29673)

Is there anything that I need to do here?

[vradosavljevic]

Comments addressed.

[dsanders]

LGTM.

We'll have to revise this to follow the rules more closely as the corner cases start to appear but being able to correctly process the majority of HI16/LO16 pairs is a big step forwards compared to what we had before

lib/ExecutionEngine/RuntimeDyld/RuntimeDyldELF.cpp

1363–1365 ↗

(On Diff #31936)

I notice you're still iterating forwards here even though you now call push_back above. I was going to say that you need to reverse the iteration direction but having re-read the (very confusing) rules again, I think iterating forwards is the right thing to do.

The reason for this change of opinion is that the HI16's would normally be sunk down to their matching LO16 which is often the first LO16 with the same symbol after the HI16 (there's some corner cases where there are multiple candidates). By iterating forwards, this code effectively does the same thing except the LO16 searches for the matching HI16.

I think that I can't use a range-based for loop, because I'm removing elements from SmallVector.

For iterating forwards, I agree. If we iterated backwards, that would have been the reason instead.

1368–1370 ↗

(On Diff #31936)

Not for this patch.

For later patches:
I think the 'MatchingValue == Value' is stricter than it should be. The addend in the %lo is allowed to differ from one in the %hi on the condition that the user knows they didn't cause a carry from the lo16 to the hi16.

There's also the issue of '.' not working properly but that's a consequence of us not transforming relocations to be section-relative instead of symbol-relative. Once that's fixed, '.' will also work.

llvm/trunk/lib/ExecutionEngine/RuntimeDyld/RuntimeDyld.cpp

if (Flags & SymbolRef::SF_Exported)
       RTDyldSymFlags |= JITSymbolFlags::Exported;
     DEBUG(dbgs() << "Allocating common symbol " << Name << " address "
                  << format("%p", Addr) << "\n");
     GlobalSymbolTable[Name] =
       SymbolTableEntry(SectionID, Offset, RTDyldSymFlags);
     Offset += Size;
     Addr += Size;
   }
+
+  if (Checker)
+    Checker->registerSection(Obj.getFileName(), SectionID);
 }
 
 unsigned RuntimeDyldImpl::emitSection(const ObjectFile &Obj,
                                       const SectionRef &Section, bool IsCode) {
 
   StringRef data;
   uint64_t Alignment64 = Section.getAlignment();
 

llvm/trunk/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldELF.h

class RuntimeDyldELF : public RuntimeDyldImpl {
 
   // Compute the address in memory where we can find the placeholder
   void *computePlaceholderAddress(unsigned SectionID, uint64_t Offset) const;
 
   // Split out common case for createing the RelocationEntry for when the relocation requires
   // no particular advanced processing.
   void processSimpleRelocation(unsigned SectionID, uint64_t Offset, unsigned RelType, RelocationValueRef Value);
 
+  // Return matching *LO16 relocation (Mips specific)
+  uint32_t getMatchingLoRelocation(uint32_t RelType,
+                                   bool IsLocal = false) const;
+
   // The tentative ID for the GOT section
   unsigned GOTSectionID;
 
   // Records the current number of allocated slots in the GOT
   // (This would be equivalent to GOTEntries.size() were it not for relocations
   // that consume more than one slot)
   unsigned CurrentGOTIndex;
 
   // A map from section to a GOT section that has entries for section's GOT
   // relocations. (Mips64 specific)
   DenseMap<SID, SID> SectionToGOTMap;
 
   // A map to avoid duplicate got entries (Mips64 specific)
   StringMap<uint64_t> GOTSymbolOffsets;
 
+  // *HI16 relocations will be added for resolving when we find matching
+  // *LO16 part. (Mips specific)
+  SmallVector<std::pair<RelocationValueRef, RelocationEntry>, 8> PendingRelocs;
+
   // When a module is loaded we save the SectionID of the EH frame section
   // in a table until we receive a request to register all unregistered
   // EH frame sections with the memory manager.
   SmallVector<SID, 2> UnregisteredEHFrameSections;
   SmallVector<SID, 2> RegisteredEHFrameSections;
 
 public:
   RuntimeDyldELF(RuntimeDyld::MemoryManager &MemMgr,

llvm/trunk/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldELF.cpp

 void RuntimeDyldELF::processSimpleRelocation(unsigned SectionID, uint64_t Offset, unsigned RelType, RelocationValueRef Value) {
   RelocationEntry RE(SectionID, Offset, RelType, Value.Addend, Value.Offset);
   if (Value.SymbolName)
     addRelocationForSymbol(RE, Value.SymbolName);
   else
     addRelocationForSection(RE, Value.SectionID);
 }
 
+uint32_t RuntimeDyldELF::getMatchingLoRelocation(uint32_t RelType,
+                                                 bool IsLocal) const {
+  switch (RelType) {
+  case ELF::R_MICROMIPS_GOT16:
+    if (IsLocal)
+      return ELF::R_MICROMIPS_LO16;
+    break;
+  case ELF::R_MICROMIPS_HI16:
+    return ELF::R_MICROMIPS_LO16;
+  case ELF::R_MIPS_GOT16:
+    if (IsLocal)
+      return ELF::R_MIPS_LO16;
+    break;
+  case ELF::R_MIPS_HI16:
+    return ELF::R_MIPS_LO16;
+  case ELF::R_MIPS_PCHI16:
+    return ELF::R_MIPS_PCLO16;
+  default:
+    break;
+  }
+  return ELF::R_MIPS_NONE;
+}
+
 relocation_iterator RuntimeDyldELF::processRelocationRef(
     unsigned SectionID, relocation_iterator RelI, const ObjectFile &O,
     ObjSectionToIDMap &ObjSectionToID, StubMap &Stubs) {
   const auto &Obj = cast<ELFObjectFileBase>(O);
   uint64_t RelType = RelI->getType();
   ErrorOr<int64_t> AddendOrErr = ELFRelocationRef(*RelI).getAddend();
   int64_t Addend = AddendOrErr ? *AddendOrErr : 0;
   elf_symbol_iterator Symbol = RelI->getSymbol();
if (RelType == ELF::R_MIPS_26) {
           addRelocationForSection(REHi, Value.SectionID);
           addRelocationForSection(RELo, Value.SectionID);
         }
 
         RelocationEntry RE(SectionID, Offset, RelType, Section.StubOffset);
         addRelocationForSection(RE, SectionID);
         Section.StubOffset += getMaxStubSize();
       }
+    } else if (RelType == ELF::R_MIPS_HI16 || RelType == ELF::R_MIPS_PCHI16) {
+      int64_t Addend = (Opcode & 0x0000ffff) << 16;
+      RelocationEntry RE(SectionID, Offset, RelType, Addend);
+      PendingRelocs.push_back(std::make_pair(Value, RE));
+    } else if (RelType == ELF::R_MIPS_LO16 || RelType == ELF::R_MIPS_PCLO16) {
+      int64_t Addend = Value.Addend + SignExtend32<16>(Opcode & 0x0000ffff);
+      for (auto I = PendingRelocs.begin(); I != PendingRelocs.end();) {
+        const RelocationValueRef &MatchingValue = I->first;
+        RelocationEntry &Reloc = I->second;
+        if (MatchingValue == Value &&
+            RelType == getMatchingLoRelocation(Reloc.RelType) &&
+            SectionID == Reloc.SectionID) {
+          Reloc.Addend += Addend;
+          if (Value.SymbolName)
+            addRelocationForSymbol(Reloc, Value.SymbolName);
+          else
+            addRelocationForSection(Reloc, Value.SectionID);
+          I = PendingRelocs.erase(I);
+        } else
+          ++I;
+      }
+      RelocationEntry RE(SectionID, Offset, RelType, Addend);
+      if (Value.SymbolName)
+        addRelocationForSymbol(RE, Value.SymbolName);
+      else
+        addRelocationForSection(RE, Value.SectionID);
     } else {
-      // FIXME: Calculate correct addends for R_MIPS_HI16, R_MIPS_LO16,
-      // R_MIPS_PCHI16 and R_MIPS_PCLO16 relocations.
-      if (RelType == ELF::R_MIPS_HI16 || RelType == ELF::R_MIPS_PCHI16)
-        Value.Addend += (Opcode & 0x0000ffff) << 16;
-      else if (RelType == ELF::R_MIPS_LO16)
-        Value.Addend += (Opcode & 0x0000ffff);
-      else if (RelType == ELF::R_MIPS_32)
+      if (RelType == ELF::R_MIPS_32)
         Value.Addend += Opcode;
-      else if (RelType == ELF::R_MIPS_PCLO16)
-        Value.Addend += SignExtend32<16>((Opcode & 0x0000ffff));
       else if (RelType == ELF::R_MIPS_PC16)
         Value.Addend += SignExtend32<18>((Opcode & 0x0000ffff) << 2);
       else if (RelType == ELF::R_MIPS_PC19_S2)
         Value.Addend += SignExtend32<21>((Opcode & 0x0007ffff) << 2);
       else if (RelType == ELF::R_MIPS_PC21_S2)
         Value.Addend += SignExtend32<23>((Opcode & 0x001fffff) << 2);
       else if (RelType == ELF::R_MIPS_PC26_S2)
         Value.Addend += SignExtend32<28>((Opcode & 0x03ffffff) << 2);
RelocationEntry RuntimeDyldELF::computeGOTOffsetRE(unsigned SectionID, uint64_t GOTOffset, uint64_t SymbolOffset,
                                                    uint32_t Type)
 {
   (void)SectionID; // The GOT Section is the same for all section in the object file
   return RelocationEntry(GOTSectionID, GOTOffset, Type, SymbolOffset);
 }
 
 void RuntimeDyldELF::finalizeLoad(const ObjectFile &Obj,
                                   ObjSectionToIDMap &SectionMap) {
+  if (IsMipsO32ABI)
+    if (!PendingRelocs.empty())
+      report_fatal_error("Can't find matching LO16 reloc");
+
   // If necessary, allocate the global offset table
   if (GOTSectionID != 0) {
     // Allocate memory for the section
     size_t TotalSize = CurrentGOTIndex * getGOTEntrySize();
     uint8_t *Addr = MemMgr.allocateDataSection(TotalSize, getGOTEntrySize(),
                                                 GOTSectionID, ".got", false);
     if (!Addr)
       report_fatal_error("Unable to allocate memory for GOT!");

llvm/trunk/test/ExecutionEngine/RuntimeDyld/Mips/ELF_O32_PIC_relocations.s

 # RUN: llvm-mc -triple=mipsel-unknown-linux -relocation-model=pic -code-model=small -filetype=obj -o %T/test_ELF_O32.o %s
 # RUN: llc -mtriple=mipsel-unknown-linux -relocation-model=pic -filetype=obj -o %T/test_ELF_ExternalFunction_O32.o %S/Inputs/ExternalFunction.ll
-# RUN: llvm-rtdyld -triple=mipsel-unknown-linux -verify -map-section test_ELF_O32.o,.text=0x1000 -map-section test_ELF_ExternalFunction_O32.o,.text=0x10000 -check=%s %T/test_ELF_O32.o %T/test_ELF_ExternalFunction_O32.o
+# RUN: llvm-rtdyld -triple=mipsel-unknown-linux -verify -map-section test_ELF_O32.o,"<common symbols>"=0x7FF8 -map-section test_ELF_O32.o,.text=0x1000 -map-section test_ELF_ExternalFunction_O32.o,.text=0x10000 -check=%s %T/test_ELF_O32.o %T/test_ELF_ExternalFunction_O32.o
 
 # RUN: llvm-mc -triple=mips-unknown-linux -relocation-model=pic -code-model=small -filetype=obj -o %T/test_ELF_O32.o %s
 # RUN: llc -mtriple=mips-unknown-linux -relocation-model=pic -filetype=obj -o %/T/test_ELF_ExternalFunction_O32.o %S/Inputs/ExternalFunction.ll
-# RUN: llvm-rtdyld -triple=mips-unknown-linux -verify -map-section test_ELF_O32.o,.text=0x1000 -map-section test_ELF_ExternalFunction_O32.o,.text=0x10000 -check=%s %T/test_ELF_O32.o %T/test_ELF_ExternalFunction_O32.o
+# RUN: llvm-rtdyld -triple=mips-unknown-linux -verify -map-section test_ELF_O32.o,"<common symbols>"=0x7FF8 -map-section test_ELF_O32.o,.text=0x1000 -map-section test_ELF_ExternalFunction_O32.o,.text=0x10000 -check=%s %T/test_ELF_O32.o %T/test_ELF_ExternalFunction_O32.o
 
         .data
 # rtdyld-check: *{4}R_MIPS_32 = foo[31:0]
 R_MIPS_32:
         .word foo
 # rtdyld-check: *{4}(R_MIPS_32+4) = foo[31:0]
         .4byte foo
 # rtdyld-check: *{4}(R_MIPS_PC32) = (foo - R_MIPS_PC32)[31:0]

 # rtdyld-check:  decode_operand(R_MIPS_HI16, 1)[15:0] = foo[31:16]
 R_MIPS_HI16:
   lui $1, %hi(foo)
 
 # rtdyld-check:  decode_operand(R_MIPS_LO16, 1)[15:0] = foo[15:0]
 R_MIPS_LO16:
   lui $1, %lo(foo)
 
+# rtdyld-check:  decode_operand(R_MIPS_HI16_ADDEND, 1)[15:0] = (var+0x8008)[31:16]
+R_MIPS_HI16_ADDEND:
+  lui $2, %hi(var+8)
+
+# rtdyld-check:  decode_operand(R_MIPS_LO16_ADDEND, 2)[15:0] = (var+0x8)[15:0]
+R_MIPS_LO16_ADDEND:
+  lb  $2, %lo(var+8)($2)
+
   .size bar, .-bar
+  .comm var,9,1