[RISCV] Make linker-relaxable instructions terminate MCDataFragment

[MaskRay]

Summary

MCExpr::evaluateAsAbsolute has a longstanding bug. When the MCAssembler is
non-null and the MCAsmLayout is null, it may incorrectly fold A-B even if A and
B are separated by a linker-relaxable instruction. This behavior can suppress
some ADD/SUB relocations and lead to wrong results if the linker performs
relaxation.

To fix the bug, ensure that linker-relaxable instructions only appear at the end
of an MCDataFragment, thereby making them terminate the fragment. When computing
A-B, suppress folding if A and B are separated by a linker-relaxable
instruction.

• .subsection now correctly give errors for non-foldable expressions.
• gen-dwarf.s will pass even if we add back the .debug_line or .eh_frame/.debug_frame code from D150004
• This will fix suppressed relocation when we add R_RISCV_SET_ULEB128/R_RISCV_SUB_ULEB128.

In the future, we should investigate the desired behavior for
MCExpr::evaluateAsAbsolute when both MCAssembler and MCAsmLayout are non-null.

(Note: MCRelaxableFragment is only for assembler-relaxation. If we ever need
linker-relaxable MCRelaxableFragment, we would need to adjust RISCVMCExpr.cpp
(D58943/D73211).)

Depends on D153096

[barannikov88]

llvm/lib/MC/MCELFStreamer.cpp

634

• Maybe add a new fixup flag to MCFixupKindInfo.h and check if it is set?
• Can Fixups contain more than one element? If it can, why are you checking only the last one?

[MaskRay]

llvm/lib/MC/MCELFStreamer.cpp

634

Linker-relaxable instructions have two relocations and the second (last) one is R_RISCV_RELAX. There is just one relocation type, so adding a FixupKindFlags flag appears to be overkill. In addition, calling getFixupKindInfo adds some overhead to non-RISCV targets.

The current way causes the least overhead to non-RISCV targets.

[barannikov88]

MCObjectStreamer::emitInstructionImpl has some logic deciding whether the instruction can be appended to a data fragment or should go in its own fragment.
I would expect the check to be there instead of MCELFStreamer::emitInstToData.
For this to be possible encodeInstruction should be pulled out too, so that you can examine Fixups.
As I can see, all implementations of emitInstrToData call encodeInstruction. (Except MCDXContainerStreamer,
but I guess this method was overridden just for the vtable to be pinned to cpp file.)

llvm/lib/MC/MCELFStreamer.cpp

634

There is not much of overhead, but makes the solution scalable and avoids target-specific changes to common code.

[barannikov88]

llvm/lib/MC/MCELFStreamer.cpp

634

To support my point of view further, FKF_Constant is also used only by ARM backend.

[MaskRay]

In D153097#4427010, @barannikov88 wrote:

MCObjectStreamer::emitInstructionImpl has some logic deciding whether the instruction can be appended to a data fragment or should go in its own fragment.
I would expect the check to be there instead of MCELFStreamer::emitInstToData.
For this to be possible encodeInstruction should be pulled out too, so that you can examine Fixups.
As I can see, all implementations of emitInstrToData call encodeInstruction. (Except MCDXContainerStreamer,
but I guess this method was overridden just for the vtable to be pinned to cpp file.)

Actually, adding the logic to MCObjectStreamer::emitInstructionImpl was my original approach before sticking with the current version.
My previous attempt placed linker-relaxable instruction in its own fragment, instead of the end of a MCDataFragment.
However, it increased the number of fragments.

Then I realized that the preferred solution is to place the linker-relaxable instruction at the end of a MCDataFragment.
With this choice, I don't think moving DF->setLinkerRelaxable(); into MCObjectStreamer::emitInstructionImpl makes cleaner code.
I think it can be argued either way. Moving DF->setLinkerRelaxable(); closer to DF->setHasInstructions(STI); has some value as well.

llvm/lib/MC/MCELFStreamer.cpp

634

FKF_Constant (my D72892) is probably not the best reference. I suspect that we can remove it but learning AArch32 is not my priority...

makes the solution scalable and avoids target-specific changes to common code.

I am not sure I agree. Both getTargetKind and a FixupKindFlags leak into the generic code and do the same amount of "pollution" in my viewpoint. FixupKindFlags adds slightly more abstraction, so I'd avoid it.

[barannikov88]

In D153097#4427091, @MaskRay wrote:

In D153097#4427010, @barannikov88 wrote:

MCObjectStreamer::emitInstructionImpl has some logic deciding whether the instruction can be appended to a data fragment or should go in its own fragment.
I would expect the check to be there instead of MCELFStreamer::emitInstToData.
For this to be possible encodeInstruction should be pulled out too, so that you can examine Fixups.
As I can see, all implementations of emitInstrToData call encodeInstruction. (Except MCDXContainerStreamer,
but I guess this method was overridden just for the vtable to be pinned to cpp file.)

Actually, adding the logic to MCObjectStreamer::emitInstructionImpl was my original approach before sticking with the current version.
My previous attempt placed linker-relaxable instruction in its own fragment, instead of the end of a MCDataFragment.
However, it increased the number of fragments.

Sadly you reconsidered, because I thought the same way.

Then I realized that the preferred solution is to place the linker-relaxable instruction at the end of a MCDataFragment.
With this choice, I don't think moving DF->setLinkerRelaxable(); into MCObjectStreamer::emitInstructionImpl makes cleaner code.
I think it can be argued either way. Moving DF->setLinkerRelaxable(); closer to DF->setHasInstructions(STI); has some value as well.

Moving it into emitInstructionImpl would generalize the changes to non-ELF targets.

llvm/include/llvm/MC/MCFragment.h

251

A brief comment would be nice.

llvm/lib/MC/MCELFStreamer.cpp

634

FKF_Constant (my D72892) is probably not the best reference. I suspect that we can remove it but learning AArch32 is not my priority...

FixupKindFlags adds slightly more abstraction, so I'd avoid it.

Not sure I get it. Abstraction is almost always a win. Well, can't force you.

[MaskRay]

In D153097#4427239, @barannikov88 wrote:

In D153097#4427091, @MaskRay wrote:

In D153097#4427010, @barannikov88 wrote:

MCObjectStreamer::emitInstructionImpl has some logic deciding whether the instruction can be appended to a data fragment or should go in its own fragment.
I would expect the check to be there instead of MCELFStreamer::emitInstToData.
For this to be possible encodeInstruction should be pulled out too, so that you can examine Fixups.
As I can see, all implementations of emitInstrToData call encodeInstruction. (Except MCDXContainerStreamer,
but I guess this method was overridden just for the vtable to be pinned to cpp file.)

Actually, adding the logic to MCObjectStreamer::emitInstructionImpl was my original approach before sticking with the current version.
My previous attempt placed linker-relaxable instruction in its own fragment, instead of the end of a MCDataFragment.
However, it increased the number of fragments.

Sadly you reconsidered, because I thought the same way.

Then I realized that the preferred solution is to place the linker-relaxable instruction at the end of a MCDataFragment.
With this choice, I don't think moving DF->setLinkerRelaxable(); into MCObjectStreamer::emitInstructionImpl makes cleaner code.
I think it can be argued either way. Moving DF->setLinkerRelaxable(); closer to DF->setHasInstructions(STI); has some value as well.

Moving it into emitInstructionImpl would generalize the changes to non-ELF targets.

Unfortunately, RISC-V linker relaxation is very ELF-specific and I don't think other object file formats can benefit from a generalized interface.
LoongArch folks may copy the design (I am a bit concerned of this as the assembler infrastructure for linker relaxation needs significant re-architecture. If they try upstreaming such stuff at this point, it would make fixing linker relaxation more difficult), otherwise no other ELF target will use the relaxation feature.
I think adding a FKF_ flag is over-engineering without a clear benefit.

Moving the setLinkerRelaxable call into MCObjectStreamer::emitInstructionImpl, as you mentioned previously, would require significant refactoring to pull out encodeInstruction out of all derived emitInstToData.
(MCDXContainerStreamer::emitInstToData doesn't call encodeInstruction. The function is unfortunately not tested by check-llvm.)
Yet I don't see a value in terms of various aspects I can think of.

llvm/lib/MC/MCELFStreamer.cpp

634

Well, can't force you.

Thank you:) I think the abstraction will just add a bit more cognitive load to readers. They will need to figure out that this is just about a specific fixup kind.

[MaskRay]

Rebase.
Rename to isLinkerRelaxable.
Improve comment.

[nickdesaulniers]

Is the presubmit failure related?

llvm/lib/MC/MCExpr.cpp

663

could use your new variables here.

686

once set, we probably don't need to check these other conditions? maybe check !BBeforeRelax first, and !AAfterRelax below (L690)?

if (!BBeforeRelax && (&*FI != FB || ...))
  ...

[MaskRay]

rebase

[nickdesaulniers]

Is it possible to tell which instructions are linker-relaxable? If so, perhaps fixing MCExpr::evaluateAsAbsolute to scan fragments for those is a better fix?

[MaskRay]

In D153097#4442561, @nickdesaulniers wrote:

Is it possible to tell which instructions are linker-relaxable? If so, perhaps fixing MCExpr::evaluateAsAbsolute to scan fragments for those is a better fix?

Thanks for taking a look.
https://github.com/riscv-non-isa/riscv-elf-psabi-doc/blob/master/riscv-elf.adoc#linker-relaxation has listed some instructions that are linker-relaxable (they generate a R_RISCV_RELAX relocation with the default -mrelax).

AttemptToFoldSymbolOffsetDifference is eventually called by MCExpr::evaluateAsAbsolute.
Fragment scanning should generally be avoided. Adding another fragment scan to MCExpr::evaluateAsAbsolute would increase complexity.
After intensive investigation, I conclude that AttemptToFoldSymbolOffsetDifference is the place to fix...

llvm/lib/MC/MCExpr.cpp

686

We could add !BBeforeRelax && but I feel that this just makes the code slightly more complex without providing a performance improvement, so I think we may just afford redundant BBeforeRelax assignment...

[nickdesaulniers]

llvm/test/MC/ELF/RISCV/subsection.s

1–38

riscv64-linux-gnu-as seems able to assemble this test case just fine. That's curious.

[MaskRay]

llvm/test/MC/ELF/RISCV/subsection.s

1–38

Yes, GNU assembler allows negative .subsection numbers but that we don't.
The negative subsection numbers may be error-prone, so seems fine to reject.
Here I just use .subsection as a convenient feature to test the behavior of evaluateAsAbsolute...

[MaskRay]

Ping:)

[asb]

I've stepped through the patch description and the code - both of which make sense to me. I'm not familiar enough with the code to be certain there's not an alternative way of achieving the same thing that would be better....but then I'd normally looking to @MaskRay for such suggestions :) LGTM, just left a minor query regarding tweaking a doc comment.

llvm/include/llvm/MC/MCAsmBackend.h

54

I assume the point of labelling this as RISC-V thing is to note that it hasn't been put to use across multiple targets. So perhaps "Fixup kind used for linker relaxation. Currently only used by RISC-V" might be a better description? (i.e. in theory general code, but hasn't been used in practice outside of one target).

[barannikov88]

In D153097#4459780, @asb wrote:

I've stepped through the patch description and the code - both of which make sense to me. I'm not familiar enough with the code to be certain there's not an alternative way of achieving the same thing that would be better....but then I'd normally looking to @MaskRay for such suggestions :) LGTM, just left a minor query regarding tweaking a doc comment.

This was my main concern. The patch assumes there is only one possible fixup that may need linker relaxation, and only supported on ELF targets.
I can imagine that RISC-V could be supported by non-unix OS, or that more fixups needing linker relaxation can be added, possibly by other targets.
I hoped my concern could be addressed, but I might as well be nitpicking, as it can easily be addressed in the future.

llvm/lib/MC/MCExpr.cpp

663

(nit) It could be slightly easier to follow if the Displacement was calculated after the fragments are sorted.

[MaskRay]

In D153097#4460146, @barannikov88 wrote:

In D153097#4459780, @asb wrote:

I've stepped through the patch description and the code - both of which make sense to me. I'm not familiar enough with the code to be certain there's not an alternative way of achieving the same thing that would be better....but then I'd normally looking to @MaskRay for such suggestions :) LGTM, just left a minor query regarding tweaking a doc comment.

This was my main concern. The patch assumes there is only one possible fixup that may need linker relaxation, and only supported on ELF targets.
I can imagine that RISC-V could be supported by non-unix OS, or that more fixups needing linker relaxation can be added, possibly by other targets.
I hoped my concern could be addressed, but I might as well be nitpicking, as it can easily be addressed in the future.

Thank you for your thoughts. I think our bikeshedding on this point is a fairly minor thing... The two object file formats LLVM supports that will mostly likely add RISC-V support (even when we say "most likely", it can be multiple years) are Mach-O and PE/COFF.

Mach-O has 16 available r_type values, which are very limited, (along with other assembler issues and subsections semantics) make it fairly difficult to add relaxation based on a relocation type.
If they do enable relaxation, they'll likely use .loh directive, with is entirely independent of this relocation based mechanism.

PE/COFF has an uint16_t relocation type field. If it does add RISC-V relaxation, it can reuse a relocation type for this purpose.
However, it does not provide an addend field. I haven't thought much about what this will entail, but I think adding relaxation could be quite challenging as well.

Anyhow, even if Mach-O and PE/COFF add RISC-V support and enable relaxation, the mechanism will be quite unclear.
The MC code may require larger changes. At that point, we can rethink how to re-architecture our code to make the most sense.
For now, I am not comfortable adding some abstraction to make reasoning about the code slightly more difficult.

[MaskRay]

Move SAOffset and Displacement
Improve a comment

llvm/include/llvm/MC/MCAsmBackend.h

 class MCValue;
 class raw_pwrite_stream;
 class StringRef;
 class raw_ostream;
 
 /// Generic interface to target specific assembler backends.
 class MCAsmBackend {
 protected: // Can only create subclasses.
-  MCAsmBackend(support::endianness Endian);
+  MCAsmBackend(support::endianness Endian,
+               unsigned RelaxFixupKind = MaxFixupKind);
 
 public:
   MCAsmBackend(const MCAsmBackend &) = delete;
   MCAsmBackend &operator=(const MCAsmBackend &) = delete;
   virtual ~MCAsmBackend();
 
   const support::endianness Endian;
 
+  /// Fixup kind for RISC-V linker relaxation.
+  const unsigned RelaxFixupKind;
+
   /// Return true if this target might automatically pad instructions and thus
   /// need to emit padding enable/disable directives around sensative code.
   virtual bool allowAutoPadding() const { return false; }
   /// Return true if this target allows an unrelaxable instruction to be
   /// emitted into RelaxableFragment and then we can increase its size in a
   /// tricky way for optimization.
   virtual bool allowEnhancedRelaxation() const { return false; }
 

llvm/include/llvm/MC/MCFragment.h

private:
 
   FragmentType Kind;
 
   /// Whether fragment is being laid out.
   bool IsBeingLaidOut;
 
 protected:
   bool HasInstructions;
+  bool LinkerRelaxable = false;
 
   MCFragment(FragmentType Kind, bool HasInstructions,
              MCSection *Parent = nullptr);
 
 public:
   MCFragment() = delete;
   MCFragment(const MCFragment &) = delete;
   MCFragment &operator=(const MCFragment &) = delete;

 class MCDataFragment : public MCEncodedFragmentWithFixups<32, 4> {
 public:
   MCDataFragment(MCSection *Sec = nullptr)
       : MCEncodedFragmentWithFixups<32, 4>(FT_Data, false, Sec) {}
 
   static bool classof(const MCFragment *F) {
     return F->getKind() == MCFragment::FT_Data;
   }
+
+  bool isLinkerRelaxable() const { return LinkerRelaxable; }
+  void setLinkerRelaxable() { LinkerRelaxable = true; }
 };
 
 /// This is a compact (memory-size-wise) fragment for holding an encoded
 /// instruction (non-relaxable) that has no fixups registered. When applicable,
 /// it can be used instead of MCDataFragment and lead to lower memory
 /// consumption.
 ///
 class MCCompactEncodedInstFragment : public MCEncodedFragmentWithContents<4> {

llvm/lib/MC/MCAsmBackend.cpp

 #include "llvm/MC/MCWinCOFFObjectWriter.h"
 #include "llvm/MC/MCXCOFFObjectWriter.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 
 using namespace llvm;
 
-MCAsmBackend::MCAsmBackend(support::endianness Endian) : Endian(Endian) {}
+MCAsmBackend::MCAsmBackend(support::endianness Endian, unsigned RelaxFixupKind)
+    : Endian(Endian), RelaxFixupKind(RelaxFixupKind) {}
 
 MCAsmBackend::~MCAsmBackend() = default;
 
 std::unique_ptr<MCObjectWriter>
 MCAsmBackend::createObjectWriter(raw_pwrite_stream &OS) const {
   auto TW = createObjectTargetWriter();
   switch (TW->getFormat()) {
   case Triple::ELF:

llvm/lib/MC/MCELFStreamer.cpp

void MCELFStreamer::emitInstToData(const MCInst &Inst,
 
   // Add the fixups and data.
   for (auto &Fixup : Fixups) {
     Fixup.setOffset(Fixup.getOffset() + DF->getContents().size());
     DF->getFixups().push_back(Fixup);
   }
 
   DF->setHasInstructions(STI);
+  if (!Fixups.empty() && Fixups.back().getTargetKind() ==
+                             getAssembler().getBackend().RelaxFixupKind)
+    DF->setLinkerRelaxable();
   DF->getContents().append(Code.begin(), Code.end());
 
   if (Assembler.isBundlingEnabled() && Assembler.getRelaxAll()) {
     if (!isBundleLocked()) {
       mergeFragment(getOrCreateDataFragment(&STI), DF);
       delete DF;
     }
   }
 }

llvm/lib/MC/MCExpr.cpp

if (Layout) {
     // is created in the case of foo: instr; .arch_extension ext; instr .if . -
     // foo.
     if (SA.isVariable() || SB.isVariable() ||
         FA->getSubsectionNumber() != FB->getSubsectionNumber())
       return;
 
     // Try to find a constant displacement from FA to FB, add the displacement
     // between the offset in FA of SA and the offset in FB of SB.
+    uint64_t SAOffset = SA.getOffset(), SBOffset = SB.getOffset();
     int64_t Displacement = SA.getOffset() - SB.getOffset();
     bool Reverse = false;
     if (FA == FB) {
       Reverse = SA.getOffset() < SB.getOffset();
     } else if (!isa<MCDummyFragment>(FA)) {
       Reverse = std::find_if(std::next(FA->getIterator()), SecA.end(),
                              [&](auto &I) { return &I == FB; }) != SecA.end();
     }
     if (Reverse) {
       std::swap(FA, FB);
+      std::swap(SAOffset, SBOffset);
       Displacement *= -1;
     }
 
     bool Found = false;
+    // Track whether B is before a relaxable instruction and whether A is after
+    // a relaxable instruction. If SA and SB are separated by a linker-relaxable
+    // instruction, the difference cannot be resolved as it may be changed by
+    // the linker.
+    bool BBeforeRelax = false, AAfterRelax = false;
     for (auto FI = FB->getIterator(), FE = SecA.end(); FI != FE; ++FI) {
       auto DF = dyn_cast<MCDataFragment>(FI);
+      if (DF && DF->isLinkerRelaxable()) {
+        if (&*FI != FB || SBOffset != DF->getContents().size())
+          BBeforeRelax = true;
+        if (&*FI != FA || SAOffset == DF->getContents().size())
+          AAfterRelax = true;
+        if (BBeforeRelax && AAfterRelax)
+          return;
+      }
       if (&*FI == FA) {
         Found = true;
         break;
       }
 
       int64_t Num;
       if (DF) {
         Displacement += DF->getContents().size();

llvm/lib/MC/MCObjectStreamer.cpp

MCFragment *MCObjectStreamer::getCurrentFragment() const {
   return nullptr;
 }
 
 static bool canReuseDataFragment(const MCDataFragment &F,
                                  const MCAssembler &Assembler,
                                  const MCSubtargetInfo *STI) {
   if (!F.hasInstructions())
     return true;
+  // Do not add data after a linker-relaxable instruction. The difference
+  // between a new label and a label at or before the linker-relaxable
+  // instruction cannot be resolved at assemble-time.
+  if (F.isLinkerRelaxable())
+    return false;
   // When bundling is enabled, we don't want to add data to a fragment that
   // already has instructions (see MCELFStreamer::emitInstToData for details)
   if (Assembler.isBundlingEnabled())
     return Assembler.getRelaxAll();
   // If the subtarget is changed mid fragment we start a new fragment to record
   // the new STI.
   return !STI || F.getSubtargetInfo() == STI;
 }

llvm/lib/Target/RISCV/MCTargetDesc/RISCVAsmBackend.h

class RISCVAsmBackend : public MCAsmBackend {
   uint8_t OSABI;
   bool Is64Bit;
   bool ForceRelocs = false;
   const MCTargetOptions &TargetOptions;
 
 public:
   RISCVAsmBackend(const MCSubtargetInfo &STI, uint8_t OSABI, bool Is64Bit,
                   const MCTargetOptions &Options)
-      : MCAsmBackend(support::little), STI(STI), OSABI(OSABI), Is64Bit(Is64Bit),
-        TargetOptions(Options) {
+      : MCAsmBackend(support::little, RISCV::fixup_riscv_relax), STI(STI),
+        OSABI(OSABI), Is64Bit(Is64Bit), TargetOptions(Options) {
     RISCVFeatures::validate(STI.getTargetTriple(), STI.getFeatureBits());
   }
   ~RISCVAsmBackend() override = default;
 
   void setForceRelocs() { ForceRelocs = true; }
 
   // Return Size with extra Nop Bytes for alignment directive in code section.
   bool shouldInsertExtraNopBytesForCodeAlign(const MCAlignFragment &AF,

llvm/test/MC/ELF/RISCV/subsection.s

-# RUN: not llvm-mc -filetype=obj -triple=riscv64 -mattr=-relax %s -o /dev/null 2>&1 | FileCheck %s --check-prefix=ERR --implicit-check-not=error:
-# RUN: not llvm-mc -filetype=obj -triple=riscv64 -mattr=+relax %s -o /dev/null 2>&1 | FileCheck %s --check-prefix=ERR --implicit-check-not=error:
+# RUN: not llvm-mc -filetype=obj -triple=riscv64 -mattr=-relax %s -o /dev/null 2>&1 | FileCheck %s --check-prefixes=ERR,NORELAX --implicit-check-not=error:
+# RUN: not llvm-mc -filetype=obj -triple=riscv64 -mattr=+relax %s -o /dev/null 2>&1 | FileCheck %s --check-prefixes=ERR,RELAX --implicit-check-not=error:
 
 a:
   nop
 b:
   call foo@plt
 c:
   nop
 d:
 
 .data
 ## Positive subsection numbers
+## With relaxation, report an error as c-b is not an assemble-time constant.
+# RELAX: :[[#@LINE+1]]:14: error: cannot evaluate subsection number
 .subsection c-b
+# RELAX: :[[#@LINE+1]]:14: error: cannot evaluate subsection number
 .subsection d-b
+# RELAX: :[[#@LINE+1]]:14: error: cannot evaluate subsection number
 .subsection c-a
 
 .subsection b-a
 .subsection d-c
 
 ## Negative subsection numbers
-# ERR: :[[#@LINE+1]]:14: error: subsection number -8 is not within [0,2147483647]
+# NORELAX: :[[#@LINE+2]]:14: error: subsection number -8 is not within [0,2147483647]
+# RELAX:   :[[#@LINE+1]]:14: error: cannot evaluate subsection number
 .subsection b-c
-# ERR: :[[#@LINE+1]]:14: error: subsection number -12 is not within [0,2147483647]
+# NORELAX: :[[#@LINE+2]]:14: error: subsection number -12 is not within [0,2147483647]
+# RELAX:   :[[#@LINE+1]]:14: error: cannot evaluate subsection number
 .subsection b-d
-# ERR: :[[#@LINE+1]]:14: error: subsection number -12 is not within [0,2147483647]
+# NORELAX: :[[#@LINE+2]]:14: error: subsection number -12 is not within [0,2147483647]
+# RELAX:   :[[#@LINE+1]]:14: error: cannot evaluate subsection number
 .subsection a-c
-# ERR: :[[#@LINE+1]]:14: error: subsection number -4 is not within [0,2147483647]
+# ERR:     :[[#@LINE+1]]:14: error: subsection number -4 is not within [0,2147483647]
 .subsection a-b
-# ERR: :[[#@LINE+1]]:14: error: subsection number -4 is not within [0,2147483647]
+# ERR:     :[[#@LINE+1]]:14: error: subsection number -4 is not within [0,2147483647]
 .subsection c-d