[LLD] [COFF] Alternative ARM range thunk algorithm

[mstorsjo]

Summary

This is an alternative to D51089, implementing a simpler thunk addition algorithm with a simpler but less graceful fallback in case the first attempt at thunks didn't cut it.

[ruiu]

I think I prefer this way, as it is conceptually a bit simpler than the iterative algorithm you've implemented in another patch.

COFF/Writer.cpp

369–371 ↗

(On Diff #165697)

I'd write these three lines one line.

385 ↗

(On Diff #165697)

The relationship between section and its thunk is 1:N. I believe that's why you are using a map to manage thunk -> symbol mapping.

However, I think you visit sections in the increasing address order, so if the last thunk is not reachable, no other thunks are reachable. Can you use the fact?

[peter.smith]

My best suggestion for a test that will need exceed the margin is to use input sections with high alignment requirements. If these are on a natural boundary prior to adding thunks then adding a thunk will result in a large amount of bytes inserted to maintain section alignment. As long as these padding bytes are in between the source and destination of a branch and exceed the margin then a test case can be constructed without needing to insert hundreds of Thunks.

COFF/Writer.cpp

485 ↗

(On Diff #165697)

Given that we expect most programs not to need any thunks at all then would moving the verify part ahead of createThunks make sense? Something like

while (true) {
  if (verifyRanges)
    // were done exit
  else {
    if pass 0 initialise margin else double it.
    create thunks()
    assignAddresses()
    ++ThunkPasses;
  }
}

That would mean one more call to verifyRanges if thunks are needed, but that is expected to be the exception.

491 ↗

(On Diff #165697)

Can you move this to line 500?

[mstorsjo]

In D52156#1237627, @peter.smith wrote:

My best suggestion for a test that will need exceed the margin is to use input sections with high alignment requirements. If these are on a natural boundary prior to adding thunks then adding a thunk will result in a large amount of bytes inserted to maintain section alignment. As long as these padding bytes are in between the source and destination of a branch and exceed the margin then a test case can be constructed without needing to insert hundreds of Thunks.

The biggest section alignment that COFF supports is 8 KB. Using that probably can reduce the testcase to requiring a few dozen of thunks, and that's probably manageable to write a testcase for. Thanks for the idea! I looked into alignments before, for creating the whole gap to cause the need for thunks, but it wasn't enough as you can't do a 16 MB alignment.

COFF/Writer.cpp

369–371 ↗

(On Diff #165697)

Will do

385 ↗

(On Diff #165697)

The relationship between section and its thunk is 1:N. I believe that's why you are using a map to manage thunk -> symbol mapping.

For every target Symbol, there can be N thunks that point to it, yes.

However, I think you visit sections in the increasing address order, so if the last thunk is not reachable, no other thunks are reachable. Can you use the fact?

Yes - I'm using exactly this fact. This map allows me to look up the last thunk pointing to each specific RVA. (In the previous version, I had something similar to DenseMap<uint64_t, vector<Defined *>>, to allow finding all thunks for a specific target. But as you say, as we progress linearly we only need to keep track of the last thunk for each target.)

485 ↗

(On Diff #165697)

That sounds like a good idea. That also avoids the case of needlessly adding thunks for the case when the margin would cause them to be added, even if the total image size still is slightly below the maximum branch range.

491 ↗

(On Diff #165697)

Oh, indeed - I don't need it after the loop any longer.

[mstorsjo]

Applied the given suggestions, added test cases based on @peter.smith's idea of using large alignments for testing cases when multiple passes are needed. This should now again be in a good-to-commit state, if everybody are happy with it.

[peter.smith]

Thanks for the updates. I don't have any more comments.

[mstorsjo]

@ruiu Any more comments?

[ruiu]

COFF/Writer.cpp

385 ↗

(On Diff #165697)

I wonder if you can eliminate map lookups (which is slow). Since the relocation is 1:N, you can add a Defined * to a symbol to represent the relationship, no?

[mstorsjo]

COFF/Writer.cpp

385 ↗

(On Diff #165697)

Oh, yes, that should also work, I think. And it seems like sizeof(Defined) is significantly less than sizeof(SymbolUnion), so it shouldn't grow the total memory consumption.

But in that case, on restarts, we need to iterate over all symbols in order to reset it. That's probably fine performance-wise since that's not expected to happen in real life - but is that even possible? SymbolTable only contains global symbols right?

If that's not possible, we'd need to store Defined * and the pass number it was added in.

[ruiu]

I believe you can iterate over all input files to visit all symbols including local ones.

[mstorsjo]

In D52156#1243810, @ruiu wrote:

I believe you can iterate over all input files to visit all symbols including local ones.

Ah, yes. I have this working now - the speedup isn't significant, but it turned out I looked at the wrong numbers for the sizes. While Defined itself is significantly smaller than SymbolUnion, Defined itself has got lots of subclasses, and adding this extra field does grow SymbolUnion from 56 to 64 bytes. Do you still think it's worth it?

[ruiu]

Ah, yes. I have this working now - the speedup isn't significant, but it turned out I looked at the wrong numbers for the sizes. While Defined itself is significantly smaller than SymbolUnion, Defined itself has got lots of subclasses, and adding this extra field does grow SymbolUnion from 56 to 64 bytes. Do you still think it's worth it?

Hmm, then maybe my idea wasn't that good.

[ruiu]

This patch looks pretty good.

COFF/Writer.cpp

298–300 ↗

(On Diff #165931)

I would inline this function because it is too small, and I don't see a need to abstract this predicate this way at the moment.

333 ↗

(On Diff #165931)

Can you explain the algorithm of thunk creation, that is, we create thunks if a jump target looks too far with some margin, and then after creating all thunks, verify that all jump targets are within their ranges, and if not, redo with a wider margin.

425 ↗

(On Diff #165931)

nit: we usually define only one variable in one line.

[mstorsjo]

COFF/Writer.cpp

298–300 ↗

(On Diff #165931)

Ok - at some point I think I had more uses of it and the inline function made the check clearer, but yes, with the one current use there's little point in it - I'll inline it.

333 ↗

(On Diff #165931)

Ok, will do.

425 ↗

(On Diff #165931)

Will fix

[mstorsjo]

Did the suggested changes, added code comments to functions that were lacking comments.

[ruiu]

LGTM

Thanks!

lld/trunk/COFF/Chunks.h

public:
   virtual size_t getSize() const = 0;
 
   // Write this chunk to a mmap'ed file, assuming Buf is pointing to
   // beginning of the file. Because this function may use RVA values
   // of other chunks for relocations, you need to set them properly
   // before calling this function.
   virtual void writeTo(uint8_t *Buf) const {}
 
+  // Called by the writer once before assigning addresses and writing
+  // the output.
+  virtual void readRelocTargets() {}
+
+  // Called if restarting thunk addition.
+  virtual void resetRelocTargets() {}
+
   // Called by the writer after an RVA is assigned, but before calling
   // getSize().
   virtual void finalizeContents() {}
 
   // The writer sets and uses the addresses.
   uint64_t getRVA() const { return RVA; }
   void setRVA(uint64_t V) { RVA = V; }
 
public:
   public:
     symbol_iterator() = default;
 
     Symbol *operator*() const { return File->getSymbol(I->SymbolTableIndex); }
   };
 
   SectionChunk(ObjFile *File, const coff_section *Header);
   static bool classof(const Chunk *C) { return C->kind() == SectionKind; }
+  void readRelocTargets() override;
+  void resetRelocTargets() override;
   size_t getSize() const override { return Header->SizeOfRawData; }
   ArrayRef<uint8_t> getContents() const;
   void writeTo(uint8_t *Buf) const override;
   bool hasData() const override;
   uint32_t getOutputCharacteristics() const override;
   StringRef getSectionName() const override { return SectionName; }
   void getBaserels(std::vector<Baserel> *Res) override;
   bool isCOMDAT() const;
public:
   // The COMDAT leader symbol if this is a COMDAT chunk.
   DefinedRegular *Sym = nullptr;
 
   ArrayRef<coff_relocation> Relocs;
 
   // Used by the garbage collector.
   bool Live;
 
+  // When inserting a thunk, we need to adjust a relocation to point to
+  // the thunk instead of the actual original target Symbol.
+  std::vector<Symbol *> RelocTargets;
+
 private:
   StringRef SectionName;
   std::vector<SectionChunk *> AssocChildren;
 
   // Used for ICF (Identical COMDAT Folding)
   void replace(SectionChunk *Other);
   uint32_t Class[2] = {0, 0};
 };
public:
   size_t getSize() const override;
   void writeTo(uint8_t *Buf) const override;
 
   static std::map<uint32_t, MergeChunk *> Instances;
   std::vector<SectionChunk *> Sections;
 
 private:
   llvm::StringTableBuilder Builder;
+  bool Finalized = false;
 };
 
 // A chunk for common symbols. Common chunks don't have actual data.
 class CommonChunk : public Chunk {
 public:
   CommonChunk(const COFFSymbolRef Sym);
   size_t getSize() const override { return Sym.getValue(); }
   bool hasData() const override { return false; }
public:
   explicit ImportThunkChunkARM64(Defined *S) : ImpSymbol(S) {}
   size_t getSize() const override { return sizeof(ImportThunkARM64); }
   void writeTo(uint8_t *Buf) const override;
 
 private:
   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 *Target;
+};
+
 // Windows-specific.
 // See comments for DefinedLocalImport class.
 class LocalImportChunk : public Chunk {
 public:
   explicit LocalImportChunk(Defined *S) : Sym(S) {}
   size_t getSize() const override;
   void getBaserels(std::vector<Baserel> *Res) override;
   void writeTo(uint8_t *Buf) const override;

lld/trunk/COFF/Chunks.cpp

SectionChunk::SectionChunk(ObjFile *F, const coff_section *H)
 
   // If linker GC is disabled, every chunk starts out alive.  If linker GC is
   // enabled, treat non-comdat sections as roots. Generally optimized object
   // files will be built with -ffunction-sections or /Gy, so most things worth
   // stripping will be in a comdat.
   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::readRelocTargets() {
+  assert(RelocTargets.empty());
+  RelocTargets.reserve(Relocs.size());
+  for (const coff_relocation &Rel : Relocs)
+    RelocTargets.push_back(File->getSymbol(Rel.SymbolTableIndex));
+}
+
+// Reset RelocTargets to their original targets before thunks were added.
+void SectionChunk::resetRelocTargets() {
+  for (size_t I = 0, E = Relocs.size(); I < E; ++I)
+    RelocTargets[I] = File->getSymbol(Relocs[I].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); }
 static void or16(uint8_t *P, uint16_t V) { write16le(P, read16le(P) | V); }
 static void or32(uint8_t *P, uint32_t V) { write32le(P, read32le(P) | V); }
 
 // Verify that given sections are appropriate targets for SECREL
 // relocations. This check is relaxed because unfortunately debug
if (!hasData())
     return;
   // Copy section contents from source object file to output file.
   ArrayRef<uint8_t> A = getContents();
   if (!A.empty())
     memcpy(Buf + OutputSectionOff, A.data(), A.size());
 
   // 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
     // beginning of the following input section.
     if (Rel.VirtualAddress >= InputSize) {
       error("relocation points beyond the end of its parent section");
       continue;
     }
 
     uint8_t *Off = Buf + OutputSectionOff + Rel.VirtualAddress;
 
-    auto *Sym =
-        dyn_cast_or_null<Defined>(File->getSymbol(Rel.SymbolTableIndex));
+    // Use the potentially remapped Symbol instead of the one that the
+    // relocation points to.
+    auto *Sym = dyn_cast_or_null<Defined>(RelocTargets[I]);
     if (!Sym) {
       if (isCodeView() || isDWARF())
         continue;
       // Symbols in early discarded sections are represented using null pointers,
       // so we need to retrieve the name from the object file.
       COFFSymbolRef Sym =
           check(File->getCOFFObj()->getSymbol(Rel.SymbolTableIndex));
       StringRef Name;
static uint8_t getBaserelType(const coff_relocation &Rel) {
   }
 }
 
 // Windows-specific.
 // Collect all locations that contain absolute addresses, which need to be
 // fixed by the loader if load-time relocation is needed.
 // Only called when base relocation is enabled.
 void SectionChunk::getBaserels(std::vector<Baserel> *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<DefinedAbsolute>(Target))
       continue;
     Res->emplace_back(RVA + Rel.VirtualAddress, Ty);
   }
 }
 
 // MinGW specific.
 // Check whether a static relocation of type Type can be deferred and

 
 void ImportThunkChunkARM64::writeTo(uint8_t *Buf) const {
   int64_t Off = ImpSymbol->getRVA() & 0xfff;
   memcpy(Buf + OutputSectionOff, ImportThunkARM64, sizeof(ImportThunkARM64));
   applyArm64Addr(Buf + OutputSectionOff, ImpSymbol->getRVA(), RVA, 12);
   applyArm64Ldr(Buf + OutputSectionOff + 4, Off);
 }
 
+// A Thumb2, PIC, non-interworking range extension thunk.
+const uint8_t ArmThunk[] = {
+    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)
+    0xe7, 0x44,             // L1: add  pc, ip
+};
+
+size_t RangeExtensionThunk::getSize() const {
+  assert(Config->Machine == ARMNT);
+  return sizeof(ArmThunk);
+}
+
+void RangeExtensionThunk::writeTo(uint8_t *Buf) const {
+  assert(Config->Machine == ARMNT);
+  uint64_t Offset = Target->getRVA() - RVA - 12;
+  memcpy(Buf + OutputSectionOff, ArmThunk, sizeof(ArmThunk));
+  applyMOV32T(Buf + OutputSectionOff, uint32_t(Offset));
+}
+
 void LocalImportChunk::getBaserels(std::vector<Baserel> *Res) {
   Res->emplace_back(getRVA());
 }
 
 size_t LocalImportChunk::getSize() const {
   return Config->is64() ? 8 : 4;
 }
 

 void MergeChunk::addSection(SectionChunk *C) {
   auto *&MC = Instances[C->Alignment];
   if (!MC)
     MC = make<MergeChunk>(C->Alignment);
   MC->Sections.push_back(C);
 }
 
 void MergeChunk::finalizeContents() {
+  if (!Finalized) {
     for (SectionChunk *C : Sections)
       if (C->Live)
         Builder.add(toStringRef(C->getContents()));
     Builder.finalize();
+    Finalized = true;
+  }
 
   for (SectionChunk *C : Sections) {
     if (!C->Live)
       continue;
     size_t Off = Builder.getOffset(toStringRef(C->getContents()));
     C->setOutputSection(Out);
     C->setRVA(RVA + Off);
     C->OutputSectionOff = OutputSectionOff + Off;

lld/trunk/COFF/MapFile.cpp

void coff::writeMapFile(ArrayRef<OutputSection *> OutputSections) {
   // Print out the header line.
   OS << "Address  Size     Align Out     In      Symbol\n";
 
   // Print out file contents.
   for (OutputSection *Sec : OutputSections) {
     writeHeader(OS, Sec->getRVA(), Sec->getVirtualSize(), /*Align=*/PageSize);
     OS << Sec->Name << '\n';
 
-    for (Chunk *C : Sec->getChunks()) {
+    for (Chunk *C : Sec->Chunks) {
       auto *SC = dyn_cast<SectionChunk>(C);
       if (!SC)
         continue;
 
       writeHeader(OS, SC->getRVA(), SC->getSize(), SC->Alignment);
       OS << Indent8 << SC->File->getName() << ":(" << SC->getSectionName()
          << ")\n";
       for (DefinedRegular *Sym : SectionSyms[SC])
         OS << SymStr[Sym] << '\n';
     }
   }
 }

lld/trunk/COFF/PDB.cpp

 }
 
 // Allocate memory for a .debug$S / .debug$F section and relocate it.
 static ArrayRef<uint8_t> relocateDebugChunk(BumpPtrAllocator &Alloc,
                                             SectionChunk &DebugChunk) {
   uint8_t *Buffer = Alloc.Allocate<uint8_t>(DebugChunk.getSize());
   assert(DebugChunk.OutputSectionOff == 0 &&
          "debug sections should not be in output sections");
+  DebugChunk.readRelocTargets();
   DebugChunk.writeTo(Buffer);
   return makeArrayRef(Buffer, DebugChunk.getSize());
 }
 
 static pdb::SectionContrib createSectionContrib(const Chunk *C, uint32_t Modi) {
   OutputSection *OS = C->getOutputSection();
   pdb::SectionContrib SC;
   memset(&SC, 0, sizeof(SC));
void PDBLinker::addSections(ArrayRef<OutputSection *> OutputSections,
   uint32_t PdbFilePathNI = DbiBuilder.addECName(NativePath);
   auto &LinkerModule = ExitOnErr(DbiBuilder.addModuleInfo("* Linker *"));
   LinkerModule.setPdbFilePathNI(PdbFilePathNI);
   addCommonLinkerModuleSymbols(NativePath, LinkerModule, Alloc);
 
   // Add section contributions. They must be ordered by ascending RVA.
   for (OutputSection *OS : OutputSections) {
     addLinkerModuleSectionSymbol(LinkerModule, *OS, Alloc);
-    for (Chunk *C : OS->getChunks()) {
+    for (Chunk *C : OS->Chunks) {
       pdb::SectionContrib SC =
           createSectionContrib(C, LinkerModule.getModuleIndex());
       Builder.getDbiBuilder().addSectionContrib(SC);
     }
   }
 
   // Add Section Map stream.
   ArrayRef<object::coff_section> Sections = {

lld/trunk/COFF/Writer.h

 class OutputSection {
 public:
   OutputSection(llvm::StringRef N, uint32_t Chars) : Name(N) {
     Header.Characteristics = Chars;
   }
   void addChunk(Chunk *C);
   void insertChunkAtStart(Chunk *C);
   void merge(OutputSection *Other);
-  ArrayRef<Chunk *> getChunks() { return Chunks; }
   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);
 
   // Returns the size of this section in an executable memory image.
   // This may be smaller than the raw size (the raw size is multiple
public:
   void setStringTableOff(uint32_t V) { StringTableOff = V; }
 
   // N.B. The section index is one based.
   uint32_t SectionIndex = 0;
 
   llvm::StringRef Name;
   llvm::object::coff_section Header = {};
 
+  std::vector<Chunk *> Chunks;
+  std::vector<Chunk *> OrigChunks;
+
 private:
   uint32_t StringTableOff = 0;
-  std::vector<Chunk *> Chunks;
 };
 
 }
 }
 
 #endif

lld/trunk/COFF/Writer.cpp

private:
   void createSections();
   void createMiscChunks();
   void createImportTables();
   void appendImportThunks();
   void locateImportTables(
       std::map<std::pair<StringRef, uint32_t>, std::vector<Chunk *>> &Map);
   void createExportTable();
   void mergeSections();
+  void readRelocTargets();
   void assignAddresses();
+  void finalizeAddresses();
   void removeEmptySections();
   void createSymbolAndStringTable();
   void openFile(StringRef OutputPath);
   template <typename PEHeaderTy> void writeHeader();
   void createSEHTable();
   void createRuntimePseudoRelocs();
   void insertCtorDtorSymbols();
   void createGuardCFTables();
if (StringTableOff) {
     strncpy(Hdr->Name, Name.data(),
             std::min(Name.size(), (size_t)COFF::NameSize));
   }
 }
 
 } // namespace coff
 } // namespace lld
 
+// 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, int Margin) {
+  assert(Config->Machine == ARMNT);
+  int64_t Diff = AbsoluteDifference(S, P + 4) + Margin;
+  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 the last thunk for the given target if it is in range,
+// or create a new one.
+static std::pair<Defined *, bool>
+getThunk(DenseMap<uint64_t, Defined *> &LastThunks, Defined *Target, uint64_t P,
+         uint16_t Type, int Margin) {
+  Defined *&LastThunk = LastThunks[Target->getRVA()];
+  if (LastThunk && isInRange(Type, LastThunk->getRVA(), P, Margin))
+    return {LastThunk, false};
+  RangeExtensionThunk *C = make<RangeExtensionThunk>(Target);
+  Defined *D = make<DefinedSynthetic>("", C);
+  LastThunk = D;
+  return {D, true};
+}
+
+// This checks all relocations, and for any relocation which isn't in range
+// it adds a thunk after the section chunk that contains the relocation.
+// If the latest thunk for the specific target is in range, that is used
+// instead of creating a new thunk. All range checks are done with the
+// specified margin, to make sure that relocations that originally are in
+// range, but only barely, also get thunks - in case other added thunks makes
+// the target go out of range.
+//
+// After adding thunks, we verify that all relocations are in range (with
+// no extra margin requirements). If this failed, we restart (throwing away
+// the previously created thunks) and retry with a wider margin.
+static bool createThunks(std::vector<Chunk *> &Chunks, int Margin) {
+  bool AddressesChanged = false;
+  DenseMap<uint64_t, Defined *> LastThunks;
+  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<SectionChunk>(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;
+
+      Defined *Sym = dyn_cast_or_null<Defined>(RelocTarget);
+      if (!Sym)
+        continue;
+
+      uint64_t S = Sym->getRVA();
+
+      if (isInRange(Rel.Type, S, P, Margin))
+        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(LastThunks, Sym, P, Rel.Type, Margin);
+      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;
+}
+
+// Verify that all relocations are in range, with no extra margin requirements.
+static bool verifyRanges(const std::vector<Chunk *> Chunks) {
+  for (Chunk *C : Chunks) {
+    SectionChunk *SC = dyn_cast_or_null<SectionChunk>(C);
+    if (!SC)
+      continue;
+
+    for (size_t J = 0, E = SC->Relocs.size(); J < E; ++J) {
+      const coff_relocation &Rel = SC->Relocs[J];
+      Symbol *RelocTarget = SC->RelocTargets[J];
+
+      Defined *Sym = dyn_cast_or_null<Defined>(RelocTarget);
+      if (!Sym)
+        continue;
+
+      uint64_t P = SC->getRVA() + Rel.VirtualAddress;
+      uint64_t S = Sym->getRVA();
+
+      if (!isInRange(Rel.Type, S, P, 0))
+        return false;
+    }
+  }
+  return true;
+}
+
+// Assign addresses and add thunks if necessary.
+void Writer::finalizeAddresses() {
+  assignAddresses();
+  if (Config->Machine != ARMNT)
+    return;
+
+  size_t OrigNumChunks = 0;
+  for (OutputSection *Sec : OutputSections) {
+    Sec->OrigChunks = Sec->Chunks;
+    OrigNumChunks += Sec->Chunks.size();
+  }
+
+  int Pass = 0;
+  int Margin = 1024 * 100;
+  while (true) {
+    // First check whether we need thunks at all, or if the previous pass of
+    // adding them turned out ok.
+    bool RangesOk = true;
+    size_t NumChunks = 0;
+    for (OutputSection *Sec : OutputSections) {
+      if (!verifyRanges(Sec->Chunks)) {
+        RangesOk = false;
+        break;
+      }
+      NumChunks += Sec->Chunks.size();
+    }
+    if (RangesOk) {
+      if (Pass > 0)
+        log("Added " + Twine(NumChunks - OrigNumChunks) + " thunks with " +
+            "margin " + Twine(Margin) + " in " + Twine(Pass) + " passes");
+      return;
+    }
+
+    if (Pass >= 10)
+      fatal("adding thunks hasn't converged after " + Twine(Pass) + " passes");
+
+    if (Pass > 0) {
+      // If the previous pass didn't work out, reset everything back to the
+      // original conditions before retrying with a wider margin. This should
+      // ideally never happen under real circumstances.
+      for (OutputSection *Sec : OutputSections) {
+        Sec->Chunks = Sec->OrigChunks;
+        for (Chunk *C : Sec->Chunks)
+          C->resetRelocTargets();
+      }
+      Margin *= 2;
+    }
+
+    // Try adding thunks everywhere where it is needed, with a margin
+    // to avoid things going out of range due to the added thunks.
+    bool AddressesChanged = false;
+    for (OutputSection *Sec : OutputSections)
+      AddressesChanged |= createThunks(Sec->Chunks, Margin);
+    // If the verification above thought we needed thunks, we should have
+    // added some.
+    assert(AddressesChanged);
+
+    // Recalculate the layout for the whole image (and verify the ranges at
+    // the start of the next round).
+    assignAddresses();
+
+    Pass++;
+  }
+}
+
 // The main function of the writer.
 void Writer::run() {
   ScopedTimer T1(CodeLayoutTimer);
 
   createImportTables();
   createSections();
   createMiscChunks();
   appendImportThunks();
   createExportTable();
   mergeSections();
-  assignAddresses();
+  readRelocTargets();
+  finalizeAddresses();
   removeEmptySections();
   setSectionPermissions();
   createSymbolAndStringTable();
 
   if (FileSize > UINT32_MAX)
     fatal("image size (" + Twine(FileSize) + ") " +
         "exceeds maximum allowable size (" + Twine(UINT32_MAX) + ")");
 
void Writer::createSymbolAndStringTable() {
   uint64_t FileOff = FileSize;
   PointerToSymbolTable = FileOff;
   FileOff += OutputSymtab.size() * sizeof(coff_symbol16);
   FileOff += 4 + Strtab.size();
   FileSize = alignTo(FileOff, SectorSize);
 }
 
 void Writer::mergeSections() {
-  if (!PdataSec->getChunks().empty()) {
-    FirstPdata = PdataSec->getChunks().front();
-    LastPdata = PdataSec->getChunks().back();
+  if (!PdataSec->Chunks.empty()) {
+    FirstPdata = PdataSec->Chunks.front();
+    LastPdata = PdataSec->Chunks.back();
   }
 
   for (auto &P : Config->Merge) {
     StringRef ToName = P.second;
     if (P.first == ToName)
       continue;
     StringSet<> Names;
     while (1) {
for (auto &P : Config->Merge) {
     if (!To) {
       From->Name = ToName;
       continue;
     }
     To->merge(From);
   }
 }
 
+// Visits all sections to initialize their relocation targets.
+void Writer::readRelocTargets() {
+  for (OutputSection *Sec : OutputSections)
+    for_each(parallel::par, Sec->Chunks.begin(), Sec->Chunks.end(),
+             [&](Chunk *C) { C->readRelocTargets(); });
+}
+
 // Visits all sections to assign incremental, non-overlapping RVAs and
 // file offsets.
 void Writer::assignAddresses() {
   SizeOfHeaders = DOSStubSize + sizeof(PEMagic) + sizeof(coff_file_header) +
                   sizeof(data_directory) * NumberfOfDataDirectory +
                   sizeof(coff_section) * OutputSections.size();
   SizeOfHeaders +=
       Config->is64() ? sizeof(pe32plus_header) : sizeof(pe32_header);
   SizeOfHeaders = alignTo(SizeOfHeaders, SectorSize);
   uint64_t RVA = PageSize; // The first page is kept unmapped.
   FileSize = SizeOfHeaders;
 
   for (OutputSection *Sec : OutputSections) {
     if (Sec == RelocSec)
       addBaserels();
     uint64_t RawSize = 0, VirtualSize = 0;
     Sec->Header.VirtualAddress = RVA;
-    for (Chunk *C : Sec->getChunks()) {
+    for (Chunk *C : Sec->Chunks) {
       VirtualSize = alignTo(VirtualSize, C->Alignment);
       C->setRVA(RVA + VirtualSize);
       C->OutputSectionOff = VirtualSize;
       C->finalizeContents();
       VirtualSize += C->getSize();
       if (C->hasData())
         RawSize = alignTo(VirtualSize, SectorSize);
     }
void Writer::writeSections() {
   uint8_t *Buf = Buffer->getBufferStart();
   for (OutputSection *Sec : OutputSections) {
     uint8_t *SecBuf = Buf + Sec->getFileOff();
     // Fill gaps between functions in .text with INT3 instructions
     // instead of leaving as NUL bytes (which can be interpreted as
     // ADD instructions).
     if (Sec->Header.Characteristics & IMAGE_SCN_CNT_CODE)
       memset(SecBuf, 0xCC, Sec->getRawSize());
-    for_each(parallel::par, Sec->getChunks().begin(), Sec->getChunks().end(),
+    for_each(parallel::par, Sec->Chunks.begin(), Sec->Chunks.end(),
              [&](Chunk *C) { C->writeTo(SecBuf); });
   }
 }
 
 void Writer::writeBuildId() {
   // There are two important parts to the build ID.
   // 1) If building with debug info, the COFF debug directory contains a
   //    timestamp as well as a Guid and Age of the PDB.
if (S->Header.Characteristics & IMAGE_SCN_CNT_INITIALIZED_DATA)
       Res += S->getRawSize();
   return Res;
 }
 
 // Add base relocations to .reloc section.
 void Writer::addBaserels() {
   if (!Config->Relocatable)
     return;
+  RelocSec->Chunks.clear();
   std::vector<Baserel> V;
   for (OutputSection *Sec : OutputSections) {
     if (Sec->Header.Characteristics & IMAGE_SCN_MEM_DISCARDABLE)
       continue;
     // Collect all locations for base relocations.
-    for (Chunk *C : Sec->getChunks())
+    for (Chunk *C : Sec->Chunks)
       C->getBaserels(&V);
     // Add the addresses to .reloc section.
     if (!V.empty())
       addBaserelBlocks(V);
     V.clear();
   }
 }
 

lld/trunk/test/COFF/Inputs/far-arm-thumb-abs.s

-.global too_far1
-too_far1 = 0x1401004

lld/trunk/test/COFF/Inputs/far-arm-thumb-abs20.s

-.global too_far20
-too_far20 = 0x501004

lld/trunk/test/COFF/arm-thumb-branch-error.s

-// 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

lld/trunk/test/COFF/arm-thumb-branch20-error.s

 // 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
+// RUN: not lld-link -entry:_start -subsystem:console %t.obj -out:%t.exe 2>&1 | FileCheck %s
  .syntax unified
  .globl _start
 _start:
  bne too_far20
+ .space 0x100000
+ .section .text$a, "xr"
+too_far20:
+ bx lr
 
-// CHECK: relocation out of range
+// When trying to add a thunk at the end of the section, the thunk itself
+// will be too far away, so this won't converge.
+
+// CHECK: adding thunks hasn't converged

lld/trunk/test/COFF/arm-thumb-thunks-multipass.s

+// REQUIRES: arm
+// RUN: llvm-mc -filetype=obj -triple=thumbv7-windows %s -o %t.obj
+// RUN: lld-link -entry:main -subsystem:console %t.obj -out:%t.exe -verbose 2>&1 | FileCheck -check-prefix=VERBOSE %s
+// RUN: llvm-objdump -d %t.exe -start-address=0x403000 -stop-address=0x403008 | FileCheck -check-prefix=FUNC01 %s
+// RUN: llvm-objdump -d %t.exe -start-address=0x404ffa -stop-address=0x405012 | FileCheck -check-prefix=FUNC01-THUNKS %s
+
+// VERBOSE: Added {{.*}} thunks with margin 204800 in 2 passes
+
+    .syntax unified
+    .globl main
+    .text
+main:
+    b  func01
+    bx lr
+
+.irp i, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18
+    .section .text$\i\()a, "xr"
+    .balign 8192
+func\i:
+    bne far_func\i
+    bne func_within_margin\i
+    // Originally, the first section is less than 8192 bytes large, and the
+    // second one follows almost directly. After adding one thunk after
+    // the first section, the second one will move forward by 8192 bytes
+    // due to the alignment.
+    .space 8192 - 8 - 4
+
+    .section .text$\i\()b, "xr"
+    .balign 8192
+align\i:
+    nop
+.endr
+
+    .section .text$999, "xr"
+tail:
+    .space 0x100000 - 100*1024 - 18*8192*2
+    // Initially, these symbols are within range from all the sections above,
+    // even when taking the initial margin into account. After adding thunks
+    // to all the sections above, some of these are also out of range, forcing
+    // running a second pass.
+.irp i, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18
+func_within_margin\i:
+    nop
+.endr
+    .space 0x100000
+
+    // These are always out of range.
+.irp i, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18
+far_func\i:
+    nop
+.endr
+    bx lr
+
+// FUNC01: 403000:       41 f0 fc 87     bne.w   #8184 <.text+0x3ffc>
+// FUNC01: 403004:       41 f0 ff 87     bne.w   #8190 <.text+0x4006>
+
+// Check that we only have two thunks here, even if we created the first
+// thunk twice (once in the first pass, then thrown away and recreated
+// in the second pass).
+
+// FUNC01-THUNKS: 404ffa:       00 00           movs    r0,  r0
+// The instruction above is padding from the .space
+// FUNC01-THUNKS: 404ffc:       47 f2 1e 0c     movw    r12, #28702
+// FUNC01-THUNKS: 405000:       c0 f2 20 0c     movt    r12, #32
+// FUNC01-THUNKS: 405004:       e7 44           add     pc,  r12
+// FUNC01-THUNKS: 405006:       46 f6 f0 7c     movw    r12, #28656
+// FUNC01-THUNKS: 40500a:       c0 f2 10 0c     movt    r12, #16
+// FUNC01-THUNKS: 40500e:       e7 44           add     pc, r12
+// The instruction below is padding from the .balign
+// FUNC01-THUNKS: 405010:       cc cc           ldm     r4!, {r2, r3, r6, r7}

lld/trunk/test/COFF/arm-thumb-thunks.s

+// REQUIRES: arm
+// RUN: llvm-mc -filetype=obj -triple=thumbv7-windows %s -o %t.obj
+// RUN: lld-link -entry:main -subsystem:console %t.obj -out:%t.exe -verbose 2>&1 | FileCheck -check-prefix=VERBOSE %s
+// RUN: llvm-objdump -d %t.exe -start-address=0x401000 -stop-address=0x401022 | FileCheck -check-prefix=MAIN %s
+// RUN: llvm-objdump -d %t.exe -start-address=0x501022 -stop-address=0x501032 | FileCheck -check-prefix=FUNC1 %s
+// RUN: llvm-objdump -d %t.exe -start-address=0x601032 | FileCheck -check-prefix=FUNC2 %s
+
+// VERBOSE: Added 3 thunks with margin {{.*}} in 1 passes
+
+    .syntax unified
+    .globl main
+    .globl func1
+    .text
+main:
+    bne func1
+    bne func2
+    // This should reuse the same thunk as func1 above
+    bne func1_alias
+    bx lr
+    .section .text$a, "xr"
+    .space 0x100000
+    .section .text$b, "xr"
+func1:
+func1_alias:
+    // This shouldn't reuse the func2 thunk from above, since it is out
+    // of range.
+    bne func2
+    bx lr
+    .section .text$c, "xr"
+    .space 0x100000
+    .section .text$d, "xr"
+func2:
+// Test using string tail merging. This is irrelevant to the thunking itself,
+// but running multiple passes of assignAddresses() calls finalizeAddresses()
+// multiple times; check that MergeChunk handles this correctly.
+    movw r0, :lower16:"??_C@string1"
+    movt r0, :upper16:"??_C@string1"
+    movw r1, :lower16:"??_C@string2"
+    movt r1, :upper16:"??_C@string2"
+    bx lr
+
+    .section .rdata,"dr",discard,"??_C@string1"
+    .globl "??_C@string1"
+"??_C@string1":
+    .asciz "foobar"
+    .section .rdata,"dr",discard,"??_C@string2"
+    .globl "??_C@string2"
+"??_C@string2":
+    .asciz "bar"
+
+// MAIN:    401000:       40 f0 05 80     bne.w   #10 <.text+0xe>
+// MAIN:    401004:       40 f0 08 80     bne.w   #16 <.text+0x18>
+// MAIN:    401008:       40 f0 01 80     bne.w   #2 <.text+0xe>
+// MAIN:    40100c:       70 47           bx      lr
+// func1 thunk
+// MAIN:    40100e:       40 f2 08 0c     movw    r12, #8
+// MAIN:    401012:       c0 f2 10 0c     movt    r12, #16
+// MAIN:    401016:       e7 44           add     pc,  r12
+// func2 thunk
+// MAIN:    401018:       40 f2 0e 0c     movw    r12, #14
+// MAIN:    40101c:       c0 f2 20 0c     movt    r12, #32
+// MAIN:    401020:       e7 44           add     pc,  r12
+
+// FUNC1:   501022:       40 f0 01 80     bne.w   #2 <.text+0x100028>
+// FUNC1:   501026:       70 47           bx      lr
+// func2 thunk
+// FUNC1:   501028:       4f f6 fe 7c     movw    r12, #65534
+// FUNC1:   50102c:       c0 f2 0f 0c     movt    r12, #15
+// FUNC1:   501030:       e7 44           add     pc,  r12
+
+// FUNC2:   601032:       42 f2 00 00     movw    r0, #8192
+// FUNC2:   601036:       c0 f2 60 00     movt    r0, #96
+// FUNC2:   60103a:       42 f2 03 01     movw    r1, #8195
+// FUNC2:   60103e:       c0 f2 60 01     movt    r1, #96
+// FUNC2:   601042:       70 47   bx      lr