[ELF][PPC64] Suppress toc-indirect to toc-relative relaxation if R_PPC64_TOC16_LO is seen

[MaskRay]

Summary

The current implementation assumes that R_PPC64_TOC16_HA is always followed
by R_PPC64_TOC16_LO_DS. This can break with R_PPC64_TOC16_LO:

// Load the address of the TOC entry, instead of the value stored at that address
addis 3, 2, .LC0@tloc@ha  # R_PPC64_TOC16_HA
addi  3, 3, .LC0@tloc@l   # R_PPC64_TOC16_LO
blr

which is used by boringssl's util/fipstools/delocate/delocate.go
https://github.com/google/boringssl/blob/master/crypto/fipsmodule/FIPS.md has some documentation.
In short, this tool converts an assembly file to avoid any potential relocations.
The distance to an input .toc is not a constant after linking, so it cannot use an addis;ld pair.
Instead, it jumps to a stub which loads the TOC entry address with addis;addi.

This patch checks the presence of R_PPC64_TOC16_LO and suppresses
toc-indirect to toc-relative relaxation if R_PPC64_TOC16_LO is seen.
This approach is conservative and loses some relaxation opportunities but is easy to implement.

addis 3, 2, .LC0@toc@ha  # no relaxation
addi  3, 3, .LC0@toc@l   # no relaxation
li    9, 0
addis 4, 2, .LC0@toc@ha  # can relax but suppressed
ld    4, .LC0@toc@l(4)   # can relax but suppressed

Also note that interleaved R_PPC64_TOC16_HA and R_PPC64_TOC16_LO_DS is
possible and this patch accounts for that.

addis 3, 2, .LC1@toc@ha  # can relax
addis 4, 2, .LC2@toc@ha  # can relax
ld    3, .LC1@toc@l(3)   # can relax
ld    4, .LC2@toc@l(4)   # can relax

[sfertile]

Interesting. I wasn't aware that taking the address of a toc entry was allowed when I implemented the toc-optimizations 😦 . I'm not sure we can peek at just the next relocation though to see if we can optimize or not. For example consider:

  addis 4, 2, .LC1@toc@ha  # R_PPC64_TOC16_HA, should be optimized.
  addis 3, 2, .LC0@toc@ha  # R_PPC64_TOC16_HA, should *NOT* be optimized.
  ld    4,    .LC1@toc@l(4)  # R_PPC64_TOC16_LO_DS, should be optimzied
  addi  3, 3, .LC0@toc@l   # R_PPC64_TOC16_LO, should *NOT* be optimized.
  blr

AES_encrypt:
  .long 0xabcd1234

  .data
Sym: 
  .long 0

.LC0:
  .tc AES_encrypt[TC], AES_encrypt
.LC1:
  .tc Sym[TC], Sym

My initial though are we will have to scan all the .toc relocs upfront to determine which are optimizable, but I need to spend a bit more time thinking about this to make sure I fully understand the problem.

I don't really know GO, but what in the language ends up producing assembly that takes the address of the toc entry for a symbol?

[MaskRay]

In D78431#1995205, @sfertile wrote:

Interesting. I wasn't aware that taking the address of a toc entry was allowed when I implemented the toc-optimizations 😦 . I'm not sure we can peek at just the next relocation though to see if we can optimize or not. For example consider:

  addis 4, 2, .LC1@toc@ha  # R_PPC64_TOC16_HA, should be optimized.
  addis 3, 2, .LC0@toc@ha  # R_PPC64_TOC16_HA, should *NOT* be optimized.
  ld    4,    .LC1@toc@l(4)  # R_PPC64_TOC16_LO_DS, should be optimzied
  addi  3, 3, .LC0@toc@l   # R_PPC64_TOC16_LO, should *NOT* be optimized.
  blr

AES_encrypt:
  .long 0xabcd1234

  .data
Sym: 
  .long 0

.LC0:
  .tc AES_encrypt[TC], AES_encrypt
.LC1:
  .tc Sym[TC], Sym

My initial though are we will have to scan all the .toc relocs upfront to determine which are optimizable, but I need to spend a bit more time thinking about this to make sure I fully understand the problem.

I don't really know GO, but what in the language ends up producing assembly that takes the address of the toc entry for a symbol?

boringssl delocate (there is some documentation on https://github.com/google/boringssl/blob/master/crypto/fipsmodule/FIPS.md ; my understanding is very limited, too) is the only tool that takes the address of a TOC entry. In short, this tool converts an assembly file to avoid any potential relocations. The distance to an input .toc is not a constant, so it cannot use an addis;ld pair. It calls a stub function (where relocations can be freely used) and the stub loads the address of the TOC entry in r3. The stub function has the TOC16_HA/TOC16_LO code sequence.

I believe all of our internal ppc targets can be built if we use --no-toc-optimize. After this bug fixed, there may be another bug related to delocate generated assembly, but no other tool generates such strange TOC16_HA/TOC16_LO pairs.

For interleaved R_PPC64_TOC16_* symbols, I agree that it is indeed a problem. I think we have to count on compilers/users not writing such assembly. GNU ld appears to use some heuristics. This patch brings us on par to some extent.

[sfertile]

Thanks. I'm reading through the docs you linked and will have a look at the delocate tool.

[agl]

Sorry about delocate. It is profoundly weird, motivated purely by compliance with FIPS regulations, and we don't want it to cause any problems.

It has been a couple of years since I last had all the POWER stuff in my head but, if delocate can change to make things easier for you, please let us(*) know. The POWER ABI is also non-trivial and it's possible that we're doing invalid things that have only worked because of luck.

(*) agl at google dot com.

[sfertile]

In D78431#2000967, @agl wrote:

Sorry about delocate. It is profoundly weird, motivated purely by compliance with FIPS regulations, and we don't want it to cause any problems.

No need to apologize, the linked documentation does a good job explaining why delocate does what it does, and the tests make it really easy to see what the transformations for Power are in practice. When I saw that the tests have input assembly that take the address of a toc-entry it got me thinking about if the gcc section-anchor option could produce code from source that takes the address of a toc-entry.

The POWER ABI is also non-trivial and it's possible that we're doing invalid things that have only worked because of luck.

All the transformations I looked at were ABI compliant, and I don't think there is anything in the ABI disallowing taking the address of a toc-entry. Both BFD and Gold disable toc-optimizations for these instructions so I would say that is pretty solid evidence showing it is a supported construct.

FWIW, I think I am OK with us landing a patch like this that will selectively unbreak the code that delocate emits. I'm going to poke around a bit more today though to see how hard a more general solution might be before approving this patch.

[sfertile]

LGTM. Unfortunately a more general solution looks to be quite difficult/intrusive and I'm not sure if it is worth it.

[MaskRay]

Update description

[sfertile]

I had to pull this as it breaks the PPC mutlistage LLD bot. Consider the following input:

addis r3, r2, .LC0@toc@ha  # No longer gets optimized
addis r4, r2, .LC1@toc@ha
ld  r3, .LC0@toc@l(r3)
ld r4, .LC1@toc@l(r4)

I should have caught this in the initial review, so I am sorry for the churn.

I think I have an alternative 'big-hammer' approach that will work and not be too intrusive to the rest of LLD.

There is a bit free in the Symbol class. We can use that to indicate if we have to disable toc optimizations through this symbol. In ScanRelocs if we find a R_PPC64_TOC16_LO relocation to a toc-entry, we set the bit on the referenced sym. That will disable toc-optimizations to any symbol referenced through that objects toc-section.

[MaskRay]

In D78431#2010238, @sfertile wrote:

I had to pull this as it breaks the PPC mutlistage LLD bot. Consider the following input:

addis r3, r2, .LC0@toc@ha  # No longer gets optimized
addis r4, r2, .LC1@toc@ha
ld  r3, .LC0@toc@l(r3)
ld r4, .LC1@toc@l(r4)

I should have caught this in the initial review, so I am sorry for the churn.

Oh, I did not know this can be interleaved. Can you point me to an example?

I think I have an alternative 'big-hammer' approach that will work and not be too intrusive to the rest of LLD.

There is a bit free in the Symbol class. We can use that to indicate if we have to disable toc optimizations through this symbol. In ScanRelocs if we find a R_PPC64_TOC16_LO relocation to a toc-entry, we set the bit on the referenced sym. That will disable toc-optimizations to any symbol referenced through that objects toc-section.

We have a spare bit after Symbol::scriptDefined. Indeed it seems that a stateless transformation is problematic. Adding logic to scanRelocs is probably the best approach.

@sfertile Your revert does not include Differential Revision: . I guess if it included, the revision would be automatically re-opened, and Commits: would list the associated revert commits.

[sfertile]

In D78431#2010446, @MaskRay wrote:

@sfertile Your revert does not include Differential Revision: . I guess if it included, the revision would be automatically re-opened, and Commits: would list the associated revert commits.

Cool, I didn't realize we had that functionality. I'll make sure to include it from now on.

[MaskRay]

New approach

[MaskRay]

Improve comments

[sfertile]

One minor comment but otherwise LGTM. Thanks for fixing this.

lld/ELF/Relocations.cpp

1325

We should check that the symbol is a section, and that the sections name is ".toc" before adding it to the map as well.

[MaskRay]

Check the section name is .toc

[MaskRay]

Improve description

lld/ELF/InputSection.h

 
 inline bool isDebugSection(const InputSectionBase &sec) {
   return sec.name.startswith(".debug") || sec.name.startswith(".zdebug");
 }
 
 // The list of all input sections.
 extern std::vector<InputSectionBase *> inputSections;
 
+// The set of TOC entries (.toc + addend) for which we should not apply
+// toc-indirect to toc-relative relaxation. const Symbol * refers to the
+// STT_SECTION symbol associated to the .toc input section.
+extern llvm::DenseSet<std::pair<const Symbol *, uint64_t>> ppc64noTocRelax;
+
 } // namespace elf
 
 std::string toString(const elf::InputSectionBase *);
 } // namespace lld
 
 #endif

lld/ELF/InputSection.cpp

 namespace lld {
 // Returns a string to construct an error message.
 std::string toString(const elf::InputSectionBase *sec) {
   return (toString(sec->file) + ":(" + sec->name + ")").str();
 }
 
 namespace elf {
 std::vector<InputSectionBase *> inputSections;
+DenseSet<std::pair<const Symbol *, uint64_t>> ppc64noTocRelax;
 
 template <class ELFT>
 static ArrayRef<uint8_t> getSectionContents(ObjFile<ELFT> &file,
                                             const typename ELFT::Shdr &hdr) {
   if (hdr.sh_type == SHT_NOBITS)
     return makeArrayRef<uint8_t>(nullptr, hdr.sh_size);
   return check(file.getObj().getSectionContents(&hdr));
 }
uint64_t targetVA = SignExtend64(
         bits);
 
     switch (expr) {
     case R_RELAX_GOT_PC:
     case R_RELAX_GOT_PC_NOPIC:
       target->relaxGot(bufLoc, rel, targetVA);
       break;
     case R_PPC64_RELAX_TOC:
-      if (!tryRelaxPPC64TocIndirection(rel, bufLoc))
+      // rel.sym refers to the STT_SECTION symbol associated to the .toc input
+      // section. If an R_PPC64_TOC16_LO (.toc + addend) references the TOC
+      // entry, there may be R_PPC64_TOC16_HA not paired with
+      // R_PPC64_TOC16_LO_DS. Don't relax. This loses some relaxation
+      // opportunities but is safe.
+      if (ppc64noTocRelax.count({rel.sym, rel.addend}) ||
+          !tryRelaxPPC64TocIndirection(rel, bufLoc))
         target->relocate(bufLoc, rel, targetVA);
       break;
     case R_RELAX_TLS_IE_TO_LE:
       target->relaxTlsIeToLe(bufLoc, rel, targetVA);
       break;
     case R_RELAX_TLS_LD_TO_LE:
     case R_RELAX_TLS_LD_TO_LE_ABS:
       target->relaxTlsLdToLe(bufLoc, rel, targetVA);

lld/ELF/Relocations.cpp

static void scanReloc(InputSectionBase &sec, OffsetGetter &getOffset, RelTy *&i,
 
   const uint8_t *relocatedAddr = sec.data().begin() + rel.r_offset;
   RelExpr expr = target->getRelExpr(type, sym, relocatedAddr);
 
   // Ignore R_*_NONE and other marker relocations.
   if (expr == R_NONE)
     return;
 
-  // We can separate the small code model relocations into 2 categories:
-  // 1) Those that access the compiler generated .toc sections.
-  // 2) Those that access the linker allocated got entries.
-  // lld allocates got entries to symbols on demand. Since we don't try to sort
-  // the got entries in any way, we don't have to track which objects have
-  // got-based small code model relocs. The .toc sections get placed after the
-  // end of the linker allocated .got section and we do sort those so sections
-  // addressed with small code model relocations come first.
-  if (config->emachine == EM_PPC64 && isPPC64SmallCodeModelTocReloc(type))
-    sec.file->ppc64SmallCodeModelTocRelocs = true;
-
   if (sym.isGnuIFunc() && !config->zText && config->warnIfuncTextrel) {
     warn("using ifunc symbols when text relocations are allowed may produce "
          "a binary that will segfault, if the object file is linked with "
          "old version of glibc (glibc 2.28 and earlier). If this applies to "
          "you, consider recompiling the object files without -fPIC and "
          "without -Wl,-z,notext option. Use -no-warn-ifunc-textrel to "
          "turn off this warning." +
          getLocation(sec, sym, offset));
   }
 
   // Read an addend.
   int64_t addend = computeAddend<ELFT>(rel, end, sec, expr, sym.isLocal());
 
+  if (config->emachine == EM_PPC64) {
+    // We can separate the small code model relocations into 2 categories:
+    // 1) Those that access the compiler generated .toc sections.
+    // 2) Those that access the linker allocated got entries.
+    // lld allocates got entries to symbols on demand. Since we don't try to
+    // sort the got entries in any way, we don't have to track which objects
+    // have got-based small code model relocs. The .toc sections get placed
+    // after the end of the linker allocated .got section and we do sort those
+    // so sections addressed with small code model relocations come first.
+    if (isPPC64SmallCodeModelTocReloc(type))
+      sec.file->ppc64SmallCodeModelTocRelocs = true;
+
+    // Record the TOC entry (.toc + addend) as not relaxable. See the comment in
+    // InputSectionBase::relocateAlloc().
+    if (type == R_PPC64_TOC16_LO && sym.isSection() && isa<Defined>(sym) &&
+        cast<Defined>(sym).section->name == ".toc")
+      ppc64noTocRelax.insert({&sym, addend});
+  }
+
   // Relax relocations.
   //
   // If we know that a PLT entry will be resolved within the same ELF module, we
   // can skip PLT access and directly jump to the destination function. For
   // example, if we are linking a main executable, all dynamic symbols that can
   // be resolved within the executable will actually be resolved that way at
   // runtime, because the main executable is always at the beginning of a search
   // list. We can leverage that fact.

lld/ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::finalizeSections() {
   // Change values of linker-script-defined symbols from placeholders (assigned
   // by declareSymbols) to actual definitions.
   script->processSymbolAssignments();
 
   // Scan relocations. This must be done after every symbol is declared so that
   // we can correctly decide if a dynamic relocation is needed. This is called
   // after processSymbolAssignments() because it needs to know whether a
   // linker-script-defined symbol is absolute.
+  ppc64noTocRelax.clear();
   if (!config->relocatable) {
     forEachRelSec(scanRelocations<ELFT>);
     reportUndefinedSymbols<ELFT>();
   }
 
   if (in.plt && in.plt->isNeeded())
     in.plt->addSymbols();
   if (in.iplt && in.iplt->isNeeded())

lld/test/ELF/ppc64-toc-relax2.s

+# REQUIRES: ppc
+# RUN: llvm-mc -filetype=obj -triple=powerpc64le %s -o %t.o
+# RUN: echo 'addis 5, 2, .LC0@toc@ha; ld 5, .LC0@toc@l(5); foo: \
+# RUN:   .section .toc,"aw",@progbits; .LC0: .tc foo[TC], foo' \
+# RUN:   | llvm-mc -filetype=obj -triple=powerpc64le - -o %t1.o
+# RUN: ld.lld %t.o %t1.o -o %t
+# RUN: llvm-objdump -d %t | FileCheck %s
+
+# CHECK-LABEL: <_start>:
+.globl _start
+_start:
+## Perform toc-indirect to toc-relative relaxation even if there are unrelated instructions in between.
+# CHECK-NEXT:   addis 3, 2, -2
+# CHECK-NEXT:   li 9, 0
+# CHECK-NEXT:   addi 3, 3, 32752
+# CHECK-NEXT:   lwa 3, 0(3)
+  addis 3, 2, .LC1@toc@ha  # R_PPC64_TOC16_HA
+  li    9, 0
+  ld    3, .LC1@toc@l(3)   # R_PPC64_TOC16_LO_DS
+  lwa   3, 0(3)
+
+## R_PPC64_TOC16_HA and R_PPC64_TOC16_LO_DS can interleave.
+# CHECK-NEXT:   addis 3, 2, -2
+# CHECK-NEXT:   addis 4, 2, -2
+# CHECK-NEXT:   addi 3, 3, 32752
+# CHECK-NEXT:   addi 4, 4, 32756
+  addis 3, 2, .LC1@toc@ha
+  addis 4, 2, .LC2@toc@ha
+  ld    3, .LC1@toc@l(3)
+  ld    4, .LC2@toc@l(4)
+
+## We choose to be conservative: the presence of R_PPC64_TOC16_LO
+## suppresses relaxation for the symbol.
+## R_PPC64_TOC16_HA and R_PPC64_TOC16_LO_DS pairs are not relaxed as well.
+# CHECK-NEXT:   nop
+# CHECK-NEXT:   addi 3, 2, -32768
+# CHECK-NEXT:   li 9, 0
+# CHECK-NEXT:   nop
+# CHECK-NEXT:   ld 4, -32768(2)
+  addis 3, 2, .LC0@toc@ha  # R_PPC64_TOC16_HA
+  addi  3, 3, .LC0@toc@l   # R_PPC64_TOC16_LO
+  li    9, 0
+  addis 4, 2, .LC0@toc@ha
+  ld    4, .LC0@toc@l(4)
+
+# CHECK-COUNT-3:   blr
+AES_encrypt:
+  blr
+AES_decrypt:
+  blr
+BN_free:
+  blr
+
+## %t1.o has relaxable relocation pairs referencing its .toc which is different
+## from %t.o(.toc). The suppression in %t.o does not affect %t1.o even if
+## the relocation addends are the same.
+# CHECK-NEXT:   addis 5, 2, -1
+# CHECK-NEXT:   addi 5, 5, -32768
+
+.section .toc,"aw",@progbits
+.LC0:
+  .tc AES_encrypt[TC], AES_encrypt
+.LC1:
+  .tc AES_decrypt[TC], AES_decrypt
+.LC2:
+  .tc BN_free[TC], BN_free