Index: COFF/Chunks.h =================================================================== --- COFF/Chunks.h +++ COFF/Chunks.h @@ -145,6 +145,7 @@ SectionChunk(ObjFile *File, const coff_section *Header); static bool classof(const Chunk *C) { return C->kind() == SectionKind; } + void finalizeContents() override; size_t getSize() const override { return Header->SizeOfRawData; } ArrayRef getContents() const; void writeTo(uint8_t *Buf) const override; @@ -228,6 +229,10 @@ ArrayRef Relocs; + // When inserting a thunk, we need to adjust a relocation to point to + // the thunk instead of the actual original target Symbol. + std::vector RelocTargets; + private: StringRef SectionName; std::vector AssocChildren; @@ -268,6 +273,7 @@ private: llvm::StringTableBuilder Builder; + bool Finalized = false; }; // A chunk for common symbols. Common chunks don't have actual data. @@ -355,6 +361,17 @@ Defined *ImpSymbol; }; +class RangeExtensionThunk : public Chunk { +public: + explicit RangeExtensionThunk(Defined *T) : Target(T) {} + size_t getSize() const override; + void writeTo(uint8_t *Buf) const override; + Defined *getTarget() const { return Target; } + +private: + Defined *Target; +}; + // Windows-specific. // See comments for DefinedLocalImport class. class LocalImportChunk : public Chunk { Index: COFF/Chunks.cpp =================================================================== --- COFF/Chunks.cpp +++ COFF/Chunks.cpp @@ -44,6 +44,17 @@ Live = !Config->DoGC || !isCOMDAT(); } +// Initialize the RelocTargets vector, to allow redirecting certain relocations +// to a thunk instead of the actual symbol the relocation's symbol table index +// indicates. +void SectionChunk::finalizeContents() { + if (!RelocTargets.empty()) + return; + RelocTargets.reserve(Relocs.size()); + for (const coff_relocation &Rel : Relocs) + RelocTargets.push_back(File->getSymbol(Rel.SymbolTableIndex)); +} + static void add16(uint8_t *P, int16_t V) { write16le(P, read16le(P) + V); } static void add32(uint8_t *P, int32_t V) { write32le(P, read32le(P) + V); } static void add64(uint8_t *P, int64_t V) { write64le(P, read64le(P) + V); } @@ -309,7 +320,9 @@ // Apply relocations. size_t InputSize = getSize(); - for (const coff_relocation &Rel : Relocs) { + for (size_t I = 0, E = Relocs.size(); I < E; I++) { + const coff_relocation &Rel = Relocs[I]; + // Check for an invalid relocation offset. This check isn't perfect, because // we don't have the relocation size, which is only known after checking the // machine and relocation type. As a result, a relocation may overwrite the @@ -321,8 +334,9 @@ uint8_t *Off = Buf + OutputSectionOff + Rel.VirtualAddress; - auto *Sym = - dyn_cast_or_null(File->getSymbol(Rel.SymbolTableIndex)); + // Use the potentially remapped Symbol instead of the one that the + // relocation points to. + auto *Sym = dyn_cast_or_null(RelocTargets[I]); if (!Sym) { if (isCodeView() || isDWARF()) continue; @@ -414,11 +428,14 @@ // fixed by the loader if load-time relocation is needed. // Only called when base relocation is enabled. void SectionChunk::getBaserels(std::vector *Res) { - for (const coff_relocation &Rel : Relocs) { + for (size_t I = 0, E = Relocs.size(); I < E; I++) { + const coff_relocation &Rel = Relocs[I]; uint8_t Ty = getBaserelType(Rel); if (Ty == IMAGE_REL_BASED_ABSOLUTE) continue; - Symbol *Target = File->getSymbol(Rel.SymbolTableIndex); + // Use the potentially remapped Symbol instead of the one that the + // relocation points to. + Symbol *Target = RelocTargets[I]; if (!Target || isa(Target)) continue; Res->emplace_back(RVA + Rel.VirtualAddress, Ty); @@ -638,6 +655,30 @@ applyArm64Ldr(Buf + OutputSectionOff + 4, Off); } +// A Thumb2, PIC range extension thunk. A non-PIC one would be 2 bytes +// shorter but would require a base relocation instead. +const uint8_t RangeExtensionThunkARMData[] = { + 0x40, 0xf2, 0x00, 0x0c, // P: movw ip,:lower16:S - (P + (L1-P) + 4) + 0xc0, 0xf2, 0x00, 0x0c, // movt ip,:upper16:S - (P + (L1-P) + 4) + 0xfc, 0x44, // L1: add ip, pc + 0x60, 0x47, // bx ip +}; + +size_t RangeExtensionThunk::getSize() const { + assert(Config->Machine == ARMNT); + return sizeof(RangeExtensionThunkARMData); +} + +void RangeExtensionThunk::writeTo(uint8_t *Buf) const { + assert(Config->Machine == ARMNT); + uint64_t Offset = Target->getRVA() - RVA - 12; + // The target address needs to have the Thumb bit set. + Offset |= 1; + memcpy(Buf + OutputSectionOff, RangeExtensionThunkARMData, + sizeof(RangeExtensionThunkARMData)); + applyMOV32T(Buf + OutputSectionOff, uint32_t(Offset)); +} + void LocalImportChunk::getBaserels(std::vector *Res) { Res->emplace_back(getRVA()); } @@ -777,10 +818,13 @@ } void MergeChunk::finalizeContents() { - for (SectionChunk *C : Sections) - if (C->isLive()) - Builder.add(toStringRef(C->getContents())); - Builder.finalize(); + if (!Finalized) { + for (SectionChunk *C : Sections) + if (C->isLive()) + Builder.add(toStringRef(C->getContents())); + Builder.finalize(); + Finalized = true; + } for (SectionChunk *C : Sections) { if (!C->isLive()) Index: COFF/PDB.cpp =================================================================== --- COFF/PDB.cpp +++ COFF/PDB.cpp @@ -772,6 +772,7 @@ uint8_t *Buffer = Alloc.Allocate(DebugChunk->getSize()); assert(DebugChunk->OutputSectionOff == 0 && "debug sections should not be in output sections"); + DebugChunk->finalizeContents(); DebugChunk->writeTo(Buffer); return consumeDebugMagic(makeArrayRef(Buffer, DebugChunk->getSize()), ".debug$S"); Index: COFF/Writer.h =================================================================== --- COFF/Writer.h +++ COFF/Writer.h @@ -11,6 +11,7 @@ #define LLD_COFF_WRITER_H #include "Chunks.h" +#include "Symbols.h" #include "llvm/ADT/StringRef.h" #include "llvm/Object/COFF.h" #include @@ -36,11 +37,16 @@ void addChunk(Chunk *C); void merge(OutputSection *Other); ArrayRef getChunks() { return Chunks; } + void clear() { Chunks.clear(); } void addPermissions(uint32_t C); void setPermissions(uint32_t C); uint64_t getRVA() { return Header.VirtualAddress; } uint64_t getFileOff() { return Header.PointerToRawData; } void writeHeaderTo(uint8_t *Buf); + bool createThunks(int Pass, + llvm::DenseMap, + std::vector> &ThunksPerTarget, + llvm::DenseMap &Thunks); // Returns the size of this section in an executable memory image. // This may be smaller than the raw size (the raw size is multiple Index: COFF/Writer.cpp =================================================================== --- COFF/Writer.cpp +++ COFF/Writer.cpp @@ -153,6 +153,7 @@ void createExportTable(); void mergeSections(); void assignAddresses(); + void finalizeAddresses(); void removeEmptySections(); void createSymbolAndStringTable(); void openFile(StringRef OutputPath); @@ -330,6 +331,168 @@ return None; } +static bool machineRequiresThunks() { + // Only ARMNT requires range extension thunks out of the currently supported + // architectures. + return Config->Machine == ARMNT; +} + +// Check whether the target address S is in range from a relocation +// of type RelType at address P. +static bool isInRange(uint16_t RelType, uint64_t S, uint64_t P) { + assert(Config->Machine == ARMNT); + int64_t Diff = S - P - 4; + switch (RelType) { + case IMAGE_REL_ARM_BRANCH20T: + return isInt<21>(Diff); + case IMAGE_REL_ARM_BRANCH24T: + case IMAGE_REL_ARM_BLX23T: + return isInt<25>(Diff); + default: + return true; + } +} + +// Return an existing thunk which is in range, or create a new one. +static std::pair +getThunk(DenseMap, std::vector> + &ThunksPerTarget, + DenseMap &Thunks, Defined *Target, + uint64_t P, uint16_t Type) { + Chunk *TargetChunk = Target->getChunk(); + uint64_t TargetChunkRVA = TargetChunk ? TargetChunk->getRVA() : 0; + // A unique representation of the target address of a Defined symbol, + // stable across relayouts. This is represented as the base Chunk* with + // an offset, wihch should be stable across relayouts. + // Some symbols return a nullptr Chunk, which we should be ready to handle. + std::pair UniqueTarget = {TargetChunk, Target->getRVA() - + TargetChunkRVA}; + std::vector &TargetThunks = ThunksPerTarget[UniqueTarget]; + // For the first pass, any matches are most likely at the end of the vector, + // so by iterating in reverse order, we might find a match sooner. As long + // as the image size only is in the same order of magnitude as the branch + // range (16 MB for ARMNT), there will in practice only be one or a few + // thunks per target. + for (Defined *Sym : llvm::reverse(TargetThunks)) + if (isInRange(Type, Sym->getRVA(), P)) + return {Sym, false}; + RangeExtensionThunk *C = make(Target); + Defined *D = make("", C); + TargetThunks.push_back(D); + Thunks[D] = C; + return {D, true}; +} + +// Check if the symbol currently points at a thunk, and if it does, if it still +// is usable. Returns true if it is a thunk and it still is usable. +static bool +normalizeExistingThunk(DenseMap &Thunks, + Symbol *&RelocTarget, uint16_t RelType, + uint64_t RelAddr) { + Defined *Sym = dyn_cast_or_null(RelocTarget); + if (!Sym) + return false; + if (RangeExtensionThunk *RET = Thunks.lookup(Sym)) { + if (isInRange(RelType, Sym->getRVA(), RelAddr)) + return true; + // The previously used thunk is out of range; don't refer to the thunk any + // longer but directly to the original target, to avoid chaining thunks. + RelocTarget = RET->getTarget(); + } + return false; +} + +bool OutputSection::createThunks( + int Pass, DenseMap, std::vector> + &ThunksPerTarget, + DenseMap &Thunks) { + bool AddressesChanged = false; + size_t ThunksSize = 0; + // Recheck Chunks.size() each iteration, since we can insert more + // elements into it. + for (size_t I = 0; I != Chunks.size(); ++I) { + SectionChunk *SC = dyn_cast_or_null(Chunks[I]); + if (!SC) + continue; + size_t ThunkInsertionSpot = I + 1; + + // Try to get a good enough estimate of where new thunks will be placed. + // Offset this by the size of the new thunks added so far, to make the + // estimate slightly better. + size_t ThunkInsertionRVA = SC->getRVA() + SC->getSize() + ThunksSize; + for (size_t J = 0, E = SC->Relocs.size(); J < E; ++J) { + const coff_relocation &Rel = SC->Relocs[J]; + Symbol *&RelocTarget = SC->RelocTargets[J]; + + // The estimate of the source address P should be pretty accurate, + // but we don't know whether the target Symbol address should be + // offset by ThunkSize or not (or by some of ThunksSize but not all of + // it), giving us some uncertainty once we have added one thunk. + uint64_t P = SC->getRVA() + Rel.VirtualAddress + ThunksSize; + + // If this Symbol already is a thunk, and it is in range, no need to do + // anything. If it was a thunk but the thunk now also is out of range, + // this resets the Symbol to point to the original symbol, allowing the + // new thunk to point directly to the target. + if (Pass > 0 && normalizeExistingThunk(Thunks, RelocTarget, Rel.Type, P)) + continue; + + Defined *Sym = dyn_cast_or_null(RelocTarget); + if (!Sym) + continue; + + uint64_t S = Sym->getRVA(); + + if (isInRange(Rel.Type, S, P)) + continue; + + // If the target isn't in range, hook it up to an existing or new + // thunk. + Defined *Thunk; + bool WasNew; + std::tie(Thunk, WasNew) = + getThunk(ThunksPerTarget, Thunks, Sym, P, Rel.Type); + if (WasNew) { + Chunk *ThunkChunk = Thunk->getChunk(); + ThunkChunk->setRVA(ThunkInsertionRVA); // Estimate of where it will be located. + Chunks.insert(Chunks.begin() + ThunkInsertionSpot, ThunkChunk); + ThunkInsertionSpot++; + ThunksSize += ThunkChunk->getSize(); + ThunkInsertionRVA += ThunkChunk->getSize(); + AddressesChanged = true; + } + RelocTarget = Thunk; + } + } + return AddressesChanged; +} + +// Assign addresses and add thunks if necessary. +void Writer::finalizeAddresses() { + int ThunkPass = 0; + bool AddressesChanged; + DenseMap, std::vector> + ThunksPerTarget; + DenseMap Thunks; + do { + if (ThunkPass >= 10) + fatal("adding thunks hasn't converged after " + Twine(ThunkPass) + + " passes"); + assignAddresses(); + if (!machineRequiresThunks()) + return; + AddressesChanged = false; + for (OutputSection *Sec : OutputSections) + AddressesChanged |= Sec->createThunks(ThunkPass, ThunksPerTarget, Thunks); + ThunkPass++; + // Iterate until no new thunks have been added. Even if the last pass + // hooked up a relocation to a different target than before, we don't need + // to run another pass unless addresses actually have changed. + } while (AddressesChanged); + log("Added " + Twine(Thunks.size()) + " thunks in " + Twine(ThunkPass) + + " passes"); +} + // The main function of the writer. void Writer::run() { ScopedTimer T1(CodeLayoutTimer); @@ -344,7 +507,7 @@ createImportTables(); createExportTable(); mergeSections(); - assignAddresses(); + finalizeAddresses(); removeEmptySections(); setSectionPermissions(); createSymbolAndStringTable(); @@ -1317,6 +1480,7 @@ void Writer::addBaserels() { if (!Config->Relocatable) return; + RelocSec->clear(); std::vector V; for (OutputSection *Sec : OutputSections) { if (Sec->Header.Characteristics & IMAGE_SCN_MEM_DISCARDABLE) Index: test/COFF/arm-thumb-branch-error.s =================================================================== --- test/COFF/arm-thumb-branch-error.s +++ /dev/null @@ -1,10 +0,0 @@ -// RUN: llvm-mc -filetype=obj -triple=thumbv7a-windows-gnu %s -o %t -// RUN: llvm-mc -filetype=obj -triple=thumbv7a-windows-gnu %S/Inputs/far-arm-thumb-abs.s -o %tfar -// RUN: not lld-link -entry:_start -subsystem:console %t %tfar -out:%t2 2>&1 | FileCheck %s -// REQUIRES: arm - .syntax unified - .globl _start -_start: - bl too_far1 - -// CHECK: relocation out of range Index: test/COFF/arm-thumb-branch-thunk.s =================================================================== --- /dev/null +++ test/COFF/arm-thumb-branch-thunk.s @@ -0,0 +1,17 @@ +// RUN: llvm-mc -filetype=obj -triple=thumbv7a-windows-gnu %s -o %t +// RUN: llvm-mc -filetype=obj -triple=thumbv7a-windows-gnu %S/Inputs/far-arm-thumb-abs.s -o %tfar +// RUN: lld-link -entry:_start -subsystem:console %t %tfar -out:%t.exe +// RUN: llvm-objdump -d %t.exe | FileCheck %s +// REQUIRES: arm + .syntax unified + .globl _start +_start: + bl too_far1 + +// CHECK: Disassembly of section .text: +// CHECK: .text: +// CHECK: 401000: 00 f0 00 f8 bl #0 +// CHECK: 401004: 4f f6 f5 7c movw r12, #65525 +// CHECK: 401008: c0 f2 ff 0c movt r12, #255 +// CHECK: 40100c: fc 44 add r12, pc +// CHECK: 40100e: 60 47 bx r12 Index: test/COFF/arm-thumb-branch20-error.s =================================================================== --- test/COFF/arm-thumb-branch20-error.s +++ /dev/null @@ -1,10 +0,0 @@ -// REQUIRES: arm -// RUN: llvm-mc -filetype=obj -triple=thumbv7a-windows-gnu %s -o %t.obj -// RUN: llvm-mc -filetype=obj -triple=thumbv7a-windows-gnu %S/Inputs/far-arm-thumb-abs20.s -o %t.far.obj -// RUN: not lld-link -entry:_start -subsystem:console %t.obj %t.far.obj -out:%t.exe 2>&1 | FileCheck %s - .syntax unified - .globl _start -_start: - bne too_far20 - -// CHECK: relocation out of range Index: test/COFF/arm-thumb-branch20-thunk.s =================================================================== --- /dev/null +++ test/COFF/arm-thumb-branch20-thunk.s @@ -0,0 +1,17 @@ +// REQUIRES: arm +// RUN: llvm-mc -filetype=obj -triple=thumbv7a-windows-gnu %s -o %t.obj +// RUN: llvm-mc -filetype=obj -triple=thumbv7a-windows-gnu %S/Inputs/far-arm-thumb-abs20.s -o %t.far.obj +// RUN: lld-link -entry:_start -subsystem:console %t.obj %t.far.obj -out:%t.exe +// RUN: llvm-objdump -d %t.exe | FileCheck %s + .syntax unified + .globl _start +_start: + bne too_far20 + +// CHECK: Disassembly of section .text: +// CHECK: .text: +// CHECK: 401000: 40 f0 00 80 bne.w #0 <.text+0x4> +// CHECK: 401004: 4f f6 f5 7c movw r12, #65525 +// CHECK: 401008: c0 f2 0f 0c movt r12, #15 +// CHECK: 40100c: fc 44 add r12, pc +// CHECK: 40100e: 60 47 bx r12