[lld-macho] Handle InputSection targets in branch range extension logic #126347

alx32 · 2025-02-08T05:00:18Z

Branch Extension Support for InputSection-type Relocations

Problem

The branch extension algorithm was originally designed to handle branch relocations that point directly to symbols. However, when linking Rust code, we encountered edge cases where branch target relocations point to InputSections instead of symbols. This caused issues because:

The branch extension algorithm couldn't process these InputSection-based relocations
No thunks were being created for these cases
This could lead to linker errors due to branches being out of range

Solution

This patch adds support for InputSection-based relocations by:

Detecting when a relocation targets an InputSection instead of a Symbol
Finding the first symbol at offset 0 in the targeted InputSection
Using this symbol as the branch target for thunk generation

Implementation Details

Added a new helper function getReferentSymbol() to get the branch target symbol, regardless of wether a relocation points to a Symbol or to an InputSection
If no symbol exists at offset 0 in the InputSection, a warning is emitted to alert about potential branch range issues
Modified the thunk generation logic to handle both Symbol and InputSection-based relocations

This change ensures proper branch extension support for edge case Rust-generated code while maintaining compatibility with existing symbol-based relocations.

Testing

This was tested to handle the known problematic scenario - but there doesn't seem to be a way for us to generate a branch relocation pointing to an InputSection as part of a test.

llvmbot · 2025-02-09T02:59:22Z

@llvm/pr-subscribers-lld

@llvm/pr-subscribers-lld-macho

Author: None (alx32)

Changes

Branch Extension Support for InputSection-type Relocations

Problem

The branch extension algorithm was originally designed to handle branch relocations that point directly to symbols. However, when linking Rust code, we encountered edge cases where branch target relocations point to InputSections instead of symbols. This caused issues because:

The branch extension algorithm couldn't process these InputSection-based relocations
No thunks were being created for these cases
This could lead to linker errors due to branches being out of range

Solution

This patch adds support for InputSection-based relocations by:

Detecting when a relocation targets an InputSection instead of a Symbol
Finding the first symbol at offset 0 in the targeted InputSection
Using this symbol as the branch target for thunk generation

Implementation Details

Added a new helper function getReferentSymbol() to get the branch target symbol, regardless of wether a relocation points to a Symbol or to an InputSection
If no symbol exists at offset 0 in the InputSection, a warning is emitted to alert about potential branch range issues
Modified the thunk generation logic to handle both Symbol and InputSection-based relocations

This change ensures proper branch extension support for edge case Rust-generated code while maintaining compatibility with existing symbol-based relocations.

Testing

This was tested to handle the known problematic scenario - but there doesn't seem to be a way for us to generate a branch relocation pointing to an InputSection as part of a test.

Full diff: https://github.com/llvm/llvm-project/pull/126347.diff

1 Files Affected:

(modified) lld/MachO/ConcatOutputSection.cpp (+32-2)

diff --git a/lld/MachO/ConcatOutputSection.cpp b/lld/MachO/ConcatOutputSection.cpp
index d64816ec695ad52..375f81d632f2389 100644
--- a/lld/MachO/ConcatOutputSection.cpp
+++ b/lld/MachO/ConcatOutputSection.cpp
@@ -116,6 +116,30 @@ void ConcatOutputSection::addInput(ConcatInputSection *input) {
 
 DenseMap<Symbol *, ThunkInfo> lld::macho::thunkMap;
 
+// Returns the target Symbol that a relocation refers to.
+// A Reloc can refer to either a Symbol directly, or to an InputSection.
+// For InputSection referents, we return the first Symbol at offset 0.
+// This conversion is necessary because the thunk generation algorithm
+// can only handle Symbols as branch targets, not InputSections.
+static Symbol *getReferentSymbol(const Reloc &r) {
+  if (auto *sym = r.referent.dyn_cast<Symbol *>()) {
+    return sym;
+  } else if (auto *isec = r.referent.dyn_cast<InputSection *>()) {
+    // Use the first symbol at offset 0 in the InputSection
+    for (Defined *sym : isec->symbols) {
+      if (sym->value == 0) {
+        return sym;
+      }
+    }
+    // Handle absence of suitable symbol
+    warn("Branch-range extension: No symbol at offset 0 in InputSection '" +
+         toString(isec) + "', possible branch out of range errors may occur.");
+    return nullptr;
+  } else {
+    llvm_unreachable("Unexpected referent type");
+  }
+}
+
 // Determine whether we need thunks, which depends on the target arch -- RISC
 // (i.e., ARM) generally does because it has limited-range branch/call
 // instructions, whereas CISC (i.e., x86) generally doesn't. RISC only needs
@@ -145,7 +169,10 @@ bool TextOutputSection::needsThunks() const {
     for (Reloc &r : isec->relocs) {
       if (!target->hasAttr(r.type, RelocAttrBits::BRANCH))
         continue;
-      auto *sym = cast<Symbol *>(r.referent);
+      // Get the Symbol that the relocation targets.
+      Symbol *sym = getReferentSymbol(r);
+      if (!sym)
+        continue;
       // Pre-populate the thunkMap and memoize call site counts for every
       // InputSection and ThunkInfo. We do this for the benefit of
       // estimateStubsInRangeVA().
@@ -325,7 +352,10 @@ void TextOutputSection::finalize() {
           backwardBranchRange < callVA ? callVA - backwardBranchRange : 0;
       uint64_t highVA = callVA + forwardBranchRange;
       // Calculate our call referent address
-      auto *funcSym = cast<Symbol *>(r.referent);
+      Symbol *funcSym = getReferentSymbol(r);
+      if (!funcSym)
+        continue;
+
       ThunkInfo &thunkInfo = thunkMap[funcSym];
       // The referent is not reachable, so we need to use a thunk ...
       if (funcSym->isInStubs() && callVA >= stubsInRangeVA) {

kazutakahirata · 2025-02-09T03:06:31Z

lld/MachO/ConcatOutputSection.cpp

+// This conversion is necessary because the thunk generation algorithm
+// can only handle Symbols as branch targets, not InputSections.
+static Symbol *getReferentSymbol(const Reloc &r) {
+  if (auto *sym = r.referent.dyn_cast<Symbol *>()) {


We are migrating away from PointerUnion::dyn_cast:

llvm-project/llvm/include/llvm/ADT/PointerUnion.h

Lines 146 to 147 in c89735d

// FIXME: Replace the uses of is(), get() and dyn_cast() with

// isa<T>, cast<T> and the llvm::dyn_cast<T>

AFAICT from llvm_unrechable below, you expect r.referent.isNull() to be false, so may I suggest the following?

Suggested change

if (auto *sym = r.referent.dyn_cast<Symbol *>()) {

if (auto *sym = llvm::dyn_cast<Symbol *>(r.referent)) {

kazutakahirata · 2025-02-09T03:07:04Z

lld/MachO/ConcatOutputSection.cpp

+static Symbol *getReferentSymbol(const Reloc &r) {
+  if (auto *sym = r.referent.dyn_cast<Symbol *>()) {
+    return sym;
+  } else if (auto *isec = r.referent.dyn_cast<InputSection *>()) {


Likewise, may I suggest the following?

Suggested change

} else if (auto *isec = r.referent.dyn_cast<InputSection *>()) {

} else if (auto *isec = llvm::dyn_cast<InputSection *>(r.referent)) {

Also, don't use else after a return
https://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

kyulee-com · 2025-02-09T13:11:35Z

Overall, it looks good to me.
A typo in the summary: wether -> whether

yozhu · 2025-02-09T19:53:52Z

LGTM

yozhu · 2025-02-09T19:57:50Z

lld/MachO/ConcatOutputSection.cpp

+      }
+    }
+    // Handle absence of suitable symbol
+    warn("Branch-range extension: No symbol at offset 0 in InputSection '" +


If no symbol at offset 0, could we create a local fake symbol at offset 0, and later after relocation is done skip emitting this created symbol into symbol table?

We could but I haven't encountered this scenario yet so we might not want to add the extra complexity without a way of testing it.

thevinster · 2025-02-09T22:06:16Z

but there doesn't seem to be a way for us to generate a branch relocation pointing to an InputSection as part of a test.

Is there any way to generate a reduced Rust assembly or LLVM IR from the problematic scenario as a test?

smeenai · 2025-02-10T04:19:48Z

If you're not able to generate the test case though assembly, can you use yaml2obj?

ellishg · 2025-02-10T17:24:58Z

lld/MachO/ConcatOutputSection.cpp

+static Symbol *getReferentSymbol(const Reloc &r) {
+  if (auto *sym = r.referent.dyn_cast<Symbol *>()) {
+    return sym;
+  } else if (auto *isec = r.referent.dyn_cast<InputSection *>()) {


Also, don't use else after a return
https://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

ellishg · 2025-02-10T17:25:23Z

lld/MachO/ConcatOutputSection.cpp

+    for (Defined *sym : isec->symbols) {
+      if (sym->value == 0) {
+        return sym;
+      }
+    }


Suggested change

for (Defined *sym : isec->symbols) {

if (sym->value == 0) {

return sym;

}

}

for (Defined *sym : isec->symbols)

if (sym->value == 0)

return sym;

ellishg · 2025-02-10T17:25:56Z

lld/MachO/ConcatOutputSection.cpp

+  } else {
+    llvm_unreachable("Unexpected referent type");
+  }


Suggested change

} else {

llvm_unreachable("Unexpected referent type");

}

}

llvm_unreachable("Unexpected referent type");

DataCorrupted · 2025-02-10T18:44:05Z

lld/MachO/ConcatOutputSection.cpp

+    }
+    // Handle absence of suitable symbol
+    warn("Branch-range extension: No symbol at offset 0 in InputSection '" +
+         toString(isec) + "', possible branch out of range errors may occur.");


Suggested change

toString(isec) + "', possible branch out of range errors may occur.");

toString(isec) + "', branch out of range errors may occur.");

"possible" and "may" are redundant.

alx32 · 2025-02-12T02:01:43Z

While trying to get a Rust repro for this - it turns out that I was misdiagnosing the root issue.

The issue comes from --icf=safe_thunks creating branches with InputSection targets, the input files don't actually have branches with InputSection targets natively.

While this PR still fixes the issue - it seems like fixing the root cause would be better: #126835

I'll close this PR after landing the alternate one above.

alx32 · 2025-02-13T19:08:17Z

Another approach to fixing the issue (#126835) was merged - closing this PR. Thank you everyone for your feedback !

[lld-macho] Handle InputSection targets in branch range extension logic

ac309bc

alx32 requested review from DataCorrupted, ellishg, kazutakahirata, kyulee-com and yozhu February 9, 2025 02:58

alx32 marked this pull request as ready for review February 9, 2025 02:58

llvmbot added lld lld:MachO labels Feb 9, 2025

kazutakahirata reviewed Feb 9, 2025

View reviewed changes

yozhu reviewed Feb 9, 2025

View reviewed changes

ellishg reviewed Feb 10, 2025

View reviewed changes

DataCorrupted reviewed Feb 10, 2025

View reviewed changes

alx32 closed this Feb 13, 2025

	// FIXME: Replace the uses of is(), get() and dyn_cast() with
	// isa<T>, cast<T> and the llvm::dyn_cast<T>

	if (auto sym = r.referent.dyn_cast<Symbol >()) {
	if (auto sym = llvm::dyn_cast<Symbol >(r.referent)) {

	} else if (auto isec = r.referent.dyn_cast<InputSection >()) {
	} else if (auto isec = llvm::dyn_cast<InputSection >(r.referent)) {

	toString(isec) + "', possible branch out of range errors may occur.");
	toString(isec) + "', branch out of range errors may occur.");

[lld-macho] Handle InputSection targets in branch range extension logic #126347

[lld-macho] Handle InputSection targets in branch range extension logic #126347

Uh oh!

Conversation

alx32 commented Feb 8, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Branch Extension Support for InputSection-type Relocations

Problem

Solution

Implementation Details

Testing

Uh oh!

llvmbot commented Feb 9, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Branch Extension Support for InputSection-type Relocations

Problem

Solution

Implementation Details

Testing

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kyulee-com commented Feb 9, 2025

Uh oh!

yozhu commented Feb 9, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

thevinster commented Feb 9, 2025

Uh oh!

smeenai commented Feb 10, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

alx32 commented Feb 12, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

alx32 commented Feb 13, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

9 participants

alx32 commented Feb 8, 2025 •

edited

Loading

llvmbot commented Feb 9, 2025 •

edited

Loading

alx32 commented Feb 12, 2025 •

edited

Loading

alx32 commented Feb 13, 2025 •

edited

Loading