[ MC ] Match labels to existing fragments even when switching sections.

[mtrent]

Summary

This commit builds upon Derek Schuff's 2014 commit for attaching labels to
existing fragments ( Diff Revision: http://reviews.llvm.org/D5915 )

When temporary labels appear ahead of a fragment, MCObjectStreamer will
track the temporary label symbol in a "Pending Labels" list. Labels are
associated with fragments when a real fragment arrives; otherwise, an empty
data fragment will be created if the streamer's section changes or if the
stream finishes.

This commit moves the "Pending Labels" list into each MCStream, so that
this label-fragment matching process is resilient to section changes. If
the streamer emits a label in a new section, switches to another section to
do other work, then switches back to the first section and emits a
fragment, that initial label will be associated with this new fragment.
Labels will only receive empty data fragments in the case where no other
fragment exists for that section.

The downstream effects of this can be seen in Mach-O relocations. The
previous approach could produce local section relocations and external
symbol relocations for the same data in an object file, and this mix of
relocation types resulted in problems in the ld64 Mach-O linker. This
commit ensures relocations triggered by temporary labels are consistent.

[mtrent]

pinging reviewers.

[pete]

LGTM.

[vitalybuka]

llvm/include/llvm/MC/MCObjectStreamer.h

42

Never initialized?

[hctim]

llvm/include/llvm/MC/MCObjectStreamer.h

42

Reverted in f827aff8598873194bccdfaf469f2dde7e5620d1 due to MSan failures.

MSan bots are hard to reproduce sometimes due to the multi-stage build. The easiest way to reproduce the problem is via. these instructions: https://github.com/google/sanitizers/wiki/SanitizerBotReproduceBuild

An example failure is shown below:

==83120==WARNING: MemorySanitizer: use-of-uninitialized-value
    #0 0x3d5b7b1 in llvm::MCSection::flushPendingLabels(llvm::MCFragment*, unsigned long, unsigned int) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/MC/MCSection.cpp:102:9
    #1 0x3d4ee6e in insert /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/include/llvm/MC/MCObjectStreamer.h:77:5
    #2 0x3d4ee6e in llvm::MCObjectStreamer::getOrCreateDataFragment(llvm::MCSubtargetInfo const*) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/MC/MCObjectStreamer.cpp:210:5
    #3 0x3d29f57 in llvm::MCELFStreamer::EmitInstToData(llvm::MCInst const&, llvm::MCSubtargetInfo const&) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/MC/MCELFStreamer.cpp:584:10
    #4 0x298a7d4 in EmitAndCountInstruction /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/Target/X86/X86MCInstLower.cpp:103:16
    #5 0x298a7d4 in llvm::X86AsmPrinter::EmitInstruction(llvm::MachineInstr const*) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/Target/X86/X86MCInstLower.cpp:2552:3
    #6 0x42f02a6 in llvm::AsmPrinter::EmitFunctionBody() /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp
    #7 0x296c6b9 in llvm::X86AsmPrinter::runOnMachineFunction(llvm::MachineFunction&) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/Target/X86/X86AsmPrinter.cpp:79:3
    #8 0x5184e4e in llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:73:13
    #9 0x3aaae8a in llvm::FPPassManager::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1481:27
    #10 0x3aabcdc in llvm::FPPassManager::runOnModule(llvm::Module&) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1517:16
    #11 0x3aad010 in runOnModule /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1582:27
    #12 0x3aad010 in llvm::legacy::PassManagerImpl::run(llvm::Module&) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1694:44
    #13 0x3cb5b98 in (anonymous namespace)::codegen(llvm::lto::Config&, llvm::TargetMachine*, std::__1::function<std::__1::unique_ptr<llvm::lto::NativeObjectStream, std::__1::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)>, unsigned int, llvm::Module&) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/LTO/LTOBackend.cpp:367:17
    #14 0x3cadb15 in llvm::lto::backend(llvm::lto::Config&, std::__1::function<std::__1::unique_ptr<llvm::lto::NativeObjectStream, std::__1::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)>, unsigned int, std::__1::unique_ptr<llvm::Module, std::__1::default_delete<llvm::Module> >, llvm::ModuleSummaryIndex&) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/LTO/LTOBackend.cpp:472:5
    #15 0x3c92b2a in llvm::lto::LTO::runRegularLTO(std::__1::function<std::__1::unique_ptr<llvm::lto::NativeObjectStream, std::__1::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)>) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/LTO/LTO.cpp:1015:10
    #16 0x3c90c9a in llvm::lto::LTO::run(std::__1::function<std::__1::unique_ptr<llvm::lto::NativeObjectStream, std::__1::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)>, std::__1::function<std::__1::function<std::__1::unique_ptr<llvm::lto::NativeObjectStream, std::__1::default_delete<llvm::lto::NativeObjectStream> > (unsigned int)> (unsigned int, llvm::StringRef)>) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/LTO/LTO.cpp:945:18
    #17 0x63d1f2 in run(int, char**) /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/tools/llvm-lto2/llvm-lto2.cpp:349:13
    #18 0x631362 in main /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/tools/llvm-lto2/llvm-lto2.cpp:449:12
    #19 0x7fcd3aa132e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
    #20 0x5b4be9 in _start (/b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm_build_msan/bin/llvm-lto2+0x5b4be9)

SUMMARY: MemorySanitizer: use-of-uninitialized-value /b/sanitizer-x86_64-linux-bootstrap-msan/build/llvm-project/llvm/lib/MC/MCSection.cpp:102:9 in llvm::MCSection::flushPendingLabels(llvm::MCFragment*, unsigned long, unsigned int)

llvm/include/llvm/MC/MCObjectStreamer.h

 /// to that file format or custom semantics expected by the object writer
 /// implementation.
 class MCObjectStreamer : public MCStreamer {
   std::unique_ptr<MCAssembler> Assembler;
   MCSection::iterator CurInsertionPoint;
   bool EmitEHFrame;
   bool EmitDebugFrame;
   SmallVector<MCSymbol *, 2> PendingLabels;
+  SmallVector<MCSection*, 2> PendingLabelSections;
+  unsigned CurSubsectionIdx;
   struct PendingMCFixup {
     const MCSymbol *Sym;
     MCFixup Fixup;
     MCDataFragment *DF;
     PendingMCFixup(const MCSymbol *McSym, MCDataFragment *F, MCFixup McFixup)
         : Sym(McSym), Fixup(McFixup), DF(F) {}
   };
   SmallVector<PendingMCFixup, 2> PendingFixups;
public:
   /// fragment is not a data fragment.
   /// Optionally a \p STI can be passed in so that a new fragment is created
   /// if the Subtarget differs from the current fragment.
   MCDataFragment *getOrCreateDataFragment(const MCSubtargetInfo* STI = nullptr);
 
 protected:
   bool changeSectionImpl(MCSection *Section, const MCExpr *Subsection);
 
-  /// If any labels have been emitted but not assigned fragments, ensure that
-  /// they get assigned, either to F if possible or to a new data fragment.
-  /// Optionally, it is also possible to provide an offset \p FOffset, which
-  /// will be used as a symbol offset within the fragment.
+  /// Assign a label to the current Section and Subsection even though a
+  /// fragment is not yet present. Use flushPendingLabels(F) to associate
+  /// a fragment with this label.
+  void addPendingLabel(MCSymbol* label);
+
+  /// If any labels have been emitted but not assigned fragments in the current
+  /// Section and Subsection, ensure that they get assigned, either to fragment
+  /// F if possible or to a new data fragment. Optionally, one can provide an
+  /// offset \p FOffset as a symbol offset within the fragment.
   void flushPendingLabels(MCFragment *F, uint64_t FOffset = 0);
 
 public:
   void visitUsedSymbol(const MCSymbol &Sym) override;
 
-  /// Create a dummy fragment to assign any pending labels.
-  void flushPendingLabels() { flushPendingLabels(nullptr); }
+  /// Create a data fragment for any pending labels across all Sections
+  /// and Subsections.
+  void flushPendingLabels();
 
   MCAssembler &getAssembler() { return *Assembler; }
   MCAssembler *getAssemblerPtr() override;
   /// \name MCStreamer Interface
   /// @{
 
   void EmitLabel(MCSymbol *Symbol, SMLoc Loc = SMLoc()) override;
   virtual void EmitLabelAtPos(MCSymbol *Symbol, SMLoc Loc, MCFragment *F,

llvm/include/llvm/MC/MCSection.h

private:
   MCDummyFragment DummyFragment;
 
   FragmentListType Fragments;
 
   /// Mapping from subsection number to insertion point for subsection numbers
   /// below that number.
   SmallVector<std::pair<unsigned, MCFragment *>, 1> SubsectionFragmentMap;
 
+  /// State for tracking labels that don't yet have Fragments
+  struct PendingLabel {
+    MCSymbol* Sym;
+    unsigned Subsection;
+    PendingLabel(MCSymbol* Sym, unsigned Subsection = 0)
+      : Sym(Sym), Subsection(Subsection) {}
+  };
+  SmallVector<PendingLabel, 2> PendingLabels;
+
 protected:
   SectionVariant Variant;
   SectionKind Kind;
 
   MCSection(SectionVariant V, SectionKind K, MCSymbol *Begin);
   ~MCSection();
 
 public:
public:
 
   /// Return true if a .align directive should use "optimized nops" to fill
   /// instead of 0s.
   virtual bool UseCodeAlign() const = 0;
 
   /// Check whether this section is "virtual", that is has no actual object
   /// file contents.
   virtual bool isVirtualSection() const = 0;
+
+  /// Add a pending label for the requested subsection. This label will be
+  /// associated with a fragment in flushPendingLabels()
+  void addPendingLabel(MCSymbol* label, unsigned Subsection = 0);
+
+  /// Associate all pending labels in a subsection with a fragment.
+  void flushPendingLabels(MCFragment *F, uint64_t FOffset = 0,
+        unsigned Subsection = 0);
+
+  /// Associate all pending labels with empty data fragments. One fragment
+  /// will be created for each subsection as necessary.
+  void flushPendingLabels();
 };
 
 } // end namespace llvm
 
 #endif // LLVM_MC_MCSECTION_H

llvm/lib/MC/MCObjectStreamer.cpp

 // difference between asm and object outputs. Return nullptr to in
 // inline asm mode to limit divergence to assembly inputs.
 MCAssembler *MCObjectStreamer::getAssemblerPtr() {
   if (getUseAssemblerInfoForParsing())
     return Assembler.get();
   return nullptr;
 }
 
+void MCObjectStreamer::addPendingLabel(MCSymbol* S) {
+  MCSection *CurSection = getCurrentSectionOnly();
+  if (CurSection) {
+    // Register labels that have not yet been assigned to a Section.
+    if (!PendingLabels.empty()) {
+      for (MCSymbol* Sym : PendingLabels)
+        CurSection->addPendingLabel(Sym);
+      PendingLabels.clear();
+    }
+
+    // Add this label to the current Section / Subsection.
+    CurSection->addPendingLabel(S, CurSubsectionIdx);
+
+    // Add this Section to the list of PendingLabelSections.
+    auto SecIt = std::find(PendingLabelSections.begin(),
+                           PendingLabelSections.end(), CurSection);
+    if (SecIt == PendingLabelSections.end())
+      PendingLabelSections.push_back(CurSection);
+  }
+  else
+    // There is no Section / Subsection for this label yet.
+    PendingLabels.push_back(S);
+}
+
 void MCObjectStreamer::flushPendingLabels(MCFragment *F, uint64_t FOffset) {
-  if (PendingLabels.empty())
-    return;
-  if (!F) {
-    F = new MCDataFragment();
-    MCSection *CurSection = getCurrentSectionOnly();
-    CurSection->getFragmentList().insert(CurInsertionPoint, F);
-    F->setParent(CurSection);
+  if (!CurSection) {
+    assert(PendingLabels.empty());
+    return;
   }
-  for (MCSymbol *Sym : PendingLabels) {
-    Sym->setFragment(F);
-    Sym->setOffset(FOffset);
+  // Register labels that have not yet been assigned to a Section.
+  if (!PendingLabels.empty()) {
+    for (MCSymbol* Sym : PendingLabels)
+      CurSection->addPendingLabel(Sym, CurSubsectionIdx);
+    PendingLabels.clear();
   }
+
+  // Associate a fragment with this label, either the supplied fragment
+  // or an empty data fragment.
+  if (F)
+    CurSection->flushPendingLabels(F, FOffset, CurSubsectionIdx);
+  else
+    CurSection->flushPendingLabels(nullptr, 0, CurSubsectionIdx);
+}
+
+void MCObjectStreamer::flushPendingLabels() {
+  // Register labels that have not yet been assigned to a Section.
+  if (!PendingLabels.empty()) {
+    MCSection *CurSection = getCurrentSectionOnly();
+    assert(CurSection);
+    for (MCSymbol* Sym : PendingLabels)
+      CurSection->addPendingLabel(Sym, CurSubsectionIdx);
     PendingLabels.clear();
   }
 
+  // Assign an empty data fragment to all remaining pending labels.
+  for (MCSection* Section : PendingLabelSections)
+    Section->flushPendingLabels();
+}
+
 // When fixup's offset is a forward declared label, e.g.:
 //
 //   .reloc 1f, R_MIPS_JALR, foo
 // 1: nop
 //
 // postpone adding it to Fixups vector until the label is defined and its offset
 // is known.
 void MCObjectStreamer::resolvePendingFixups() {

 
 void MCObjectStreamer::reset() {
   if (Assembler)
     Assembler->reset();
   CurInsertionPoint = MCSection::iterator();
   EmitEHFrame = true;
   EmitDebugFrame = false;
   PendingLabels.clear();
+  PendingLabelSections.clear();
   MCStreamer::reset();
 }
 
 void MCObjectStreamer::EmitFrames(MCAsmBackend *MAB) {
   if (!getNumFrameInfos())
     return;
 
   if (EmitEHFrame)
if (F && !(getAssembler().isBundlingEnabled() &&
              getAssembler().getRelaxAll())) {
     Symbol->setFragment(F);
     Symbol->setOffset(F->getContents().size());
   } else {
     // Assign all pending labels to offset 0 within the dummy "pending"
     // fragment. (They will all be reassigned to a real fragment in
     // flushPendingLabels())
     Symbol->setOffset(0);
-    PendingLabels.push_back(Symbol);
+    addPendingLabel(Symbol);
   }
 }
 
 // Emit a label at a previously emitted fragment/offset position. This must be
 // within the currently-active section.
 void MCObjectStreamer::EmitLabelAtPos(MCSymbol *Symbol, SMLoc Loc,
                                       MCFragment *F, uint64_t Offset) {
   assert(F->getParent() == getCurrentSectionOnly());
 
   MCStreamer::EmitLabel(Symbol, Loc);
   getAssembler().registerSymbol(*Symbol);
   auto *DF = dyn_cast_or_null<MCDataFragment>(F);
   Symbol->setOffset(Offset);
   if (DF) {
     Symbol->setFragment(F);
   } else {
     assert(isa<MCDummyFragment>(F) &&
            "F must either be an MCDataFragment or the pending MCDummyFragment");
     assert(Offset == 0);
-    PendingLabels.push_back(Symbol);
+    addPendingLabel(Symbol);
   }
 }
 
 void MCObjectStreamer::EmitULEB128Value(const MCExpr *Value) {
   int64_t IntValue;
   if (Value->evaluateAsAbsolute(IntValue, getAssemblerPtr())) {
     EmitULEB128IntValue(IntValue);
     return;

 void MCObjectStreamer::ChangeSection(MCSection *Section,
                                      const MCExpr *Subsection) {
   changeSectionImpl(Section, Subsection);
 }
 
 bool MCObjectStreamer::changeSectionImpl(MCSection *Section,
                                          const MCExpr *Subsection) {
   assert(Section && "Cannot switch to a null section!");
-  flushPendingLabels(nullptr);
   getContext().clearDwarfLocSeen();
 
   bool Created = getAssembler().registerSection(*Section);
 
   int64_t IntSubsection = 0;
   if (Subsection &&
       !Subsection->evaluateAsAbsolute(IntSubsection, getAssemblerPtr()))
     report_fatal_error("Cannot evaluate subsection number");
void MCObjectStreamer::FinishImpl() {
 
   // If we are generating dwarf for assembly source files dump out the sections.
   if (getContext().getGenDwarfForAssembly())
     MCGenDwarfInfo::Emit(this);
 
   // Dump out the dwarf file & directory tables and line tables.
   MCDwarfLineTable::Emit(this, getAssembler().getDWARFLinetableParams());
 
+  // Update any remaining pending labels with empty data fragments.
   flushPendingLabels();
+
   resolvePendingFixups();
   getAssembler().Finish();
 }

llvm/lib/MC/MCSection.cpp

if (!ExactMatch && Subsection != 0) {
     SubsectionFragmentMap.insert(MI, std::make_pair(Subsection, F));
     getFragmentList().insert(IP, F);
     F->setParent(this);
   }
 
   return IP;
 }
 
+void MCSection::addPendingLabel(MCSymbol* label, unsigned Subsection) {
+  PendingLabels.push_back(PendingLabel(label, Subsection));
+}
+
+void MCSection::flushPendingLabels(MCFragment *F, uint64_t FOffset,
+           unsigned Subsection) {
+  if (PendingLabels.empty())
+    return;
+
+  // Set the fragment and fragment offset for all pending symbols in the
+  // specified Subsection, and remove those symbols from the pending list.
+  for (auto It = PendingLabels.begin(); It != PendingLabels.end(); ++It) {
+    PendingLabel& Label = *It;
+    if (Label.Subsection == Subsection) {
+      Label.Sym->setFragment(F);
+      Label.Sym->setOffset(FOffset);
+      PendingLabels.erase(It--);
+    }
+  }
+}
+
+void MCSection::flushPendingLabels() {
+  // Make sure all remaining pending labels point to data fragments, by
+  // creating new empty data fragments for each Subsection with labels pending.
+  while (!PendingLabels.empty()) {
+    PendingLabel& Label = PendingLabels[0];
+    iterator CurInsertionPoint =
+      this->getSubsectionInsertionPoint(Label.Subsection);
+    MCFragment *F = new MCDataFragment();
+    getFragmentList().insert(CurInsertionPoint, F);
+    F->setParent(this);
+    flushPendingLabels(F, 0, Label.Subsection);
+  }
+}
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void MCSection::dump() const {
   raw_ostream &OS = errs();
 
   OS << "<MCSection";
   OS << " Fragments:[\n      ";
   for (auto it = begin(), ie = end(); it != ie; ++it) {
     if (it != begin())
       OS << ",\n      ";
     it->dump();
   }
   OS << "]>";
 }
 #endif

llvm/test/MC/MachO/pending-labels.s

+// Verify relocations for temporary labels are referenced by real symbols
+// at the same address.
+//
+// RUN: llvm-mc -triple x86_64-apple-darwin -filetype=obj -o - %s | llvm-objdump -r - | FileCheck %s
+
+L1:
+  .section __TEXT,__text_cold,regular,pure_instructions
+L2:
+  .text
+L3:
+  .section __TEXT,__text_cold,regular,pure_instructions
+L4:
+_function2:
+L5:
+  nop
+L6:
+  .text
+L7:
+_function1:
+L8:
+  nop
+
+  .data
+__data:
+  .quad L1-.
+  .quad L2-.
+  .quad L3-.
+  .quad L4-.
+  .quad L5-.
+  .quad L6-.
+  .quad L7-.
+  .quad L8-.
+// CHECK: 0000000000000038 X86_64_RELOC_SUBTRACTOR _function1-__data
+// CHECK: 0000000000000038 X86_64_RELOC_UNSIGNED _function1
+// CHECK: 0000000000000030 X86_64_RELOC_SUBTRACTOR _function1-__data
+// CHECK: 0000000000000030 X86_64_RELOC_UNSIGNED _function1
+// CHECK: 0000000000000028 X86_64_RELOC_SUBTRACTOR _function2-__data
+// CHECK: 0000000000000028 X86_64_RELOC_UNSIGNED _function2
+// CHECK: 0000000000000020 X86_64_RELOC_SUBTRACTOR _function2-__data
+// CHECK: 0000000000000020 X86_64_RELOC_UNSIGNED _function2
+// CHECK: 0000000000000018 X86_64_RELOC_SUBTRACTOR _function2-__data
+// CHECK: 0000000000000018 X86_64_RELOC_UNSIGNED _function2
+// CHECK: 0000000000000010 X86_64_RELOC_SUBTRACTOR _function1-__data
+// CHECK: 0000000000000010 X86_64_RELOC_UNSIGNED _function1
+// CHECK: 0000000000000008 X86_64_RELOC_SUBTRACTOR _function2-__data
+// CHECK: 0000000000000008 X86_64_RELOC_UNSIGNED _function2
+// CHECK: 0000000000000000 X86_64_RELOC_SUBTRACTOR _function1-__data
+// CHECK: 0000000000000000 X86_64_RELOC_UNSIGNED _function1