[MC] Ensure that pending labels are flushed when -mc-relax-all flag is used

[phosek]

Summary

The current implementation doesn't always flush all pending labels before emitting
data which can result in an incorrectly placed labels in case when when instruction
bundling is enabled and -mc-relax-all flag is being used. To address this issue,
we always flush pending labels before emitting data.

The change was tested by running PNaCl toolchain trybots with
-mc-relax-all flag set.

Fixes https://code.google.com/p/nativeclient/issues/detail?id=4063

[mseaborn]

Can you add a test for this, please?

[phosek]

• Test added

[mseaborn]

lib/MC/MCELFStreamer.cpp

77

This logic looks OK. However, doesn't this take O(n) time in the number of symbols that have been created so far? I'm concerned that this could lead to compilation taking O(n^2) time in the size of the module. (Quadratic time per function would be bad, but quadratic time per module would be even worse. :-( )

test/MC/X86/AlignedBundling/rodata-section.s

2

Nit: Indent "llvm-objdump", because this is a continuation line (it follows a "\").

Same below.

6

Nit: Is this redundant if you're also using "-triple=i686-nacl"? (Or maybe it's only redundant in the pnacl-llvm branch?)

12

Nit: It would make the test clearer if you omitted parts that aren't necessary for reproducing the bug, i.e.

• "foo" label
• prologue and epilogue
• call to "bar"

etc.

23

Nit: Can you make the alignment indentation consistent?

[mseaborn]

lib/MC/MCELFStreamer.cpp

77

Here's a suggestion to avoid the O(n) time problem.

Background:

• When PendingLabels was introduced by Derek (in http://llvm.org/viewvc/llvm-project?view=revision&revision=220439), it had the following invariant: If the current fragment is an MCDataFragment, PendingLabels should be empty.
• Functions such as EmitBytes() assumed they can add to the current data fragment, if there is one, without calling flushPendingLabels() first.
• Your change (r234714) created cases where the invariant didn't apply, which broke EmitBytes(). (If there had been an assertion to check the invariant, we would have noticed the problem more readily.)

How about we fix this assumption by EmitBytes() etc., by making sure they trigger a call to flushPendingLabels()? Maybe we could have getOrCreateDataFragment() call flushPendingLabels(). We would then allow PendingLabels to be non-empty when the current fragment is an MCDataFragment.

That way, we don't have to adjust any labels after they've already been assigned to an offset within a fragment.

[phosek]

lib/MC/MCELFStreamer.cpp

77

I agree, that's the solution I'm currently considering i.e. calling flushPendingLabels() from getOrCreateDataFragment(). I still need to run the change through bots to make sure that everything it doesn't break any other invariants.

[phosek]

• Test added
• Ensure that pending labels are always flushed

lib/MC/MCELFStreamer.cpp

77

I have updated the implementation which now ensures that pending labels are always properly flushed before emitting any instructions.

test/MC/X86/AlignedBundling/rodata-section.s

2

Done.

6

It's only redundant in pnacl-llvm branch.

12

Done.

23

It should be consistent with other tests.

[mseaborn]

In the commit message, can you add "when instruction bundling is enabled and..." before "when -mc-relax-all flag is being used", to clarify, please? (And to match your other change, http://reviews.llvm.org/D10044.)

LGTM, thanks.

include/llvm/MC/MCObjectStreamer.h

protected:
   /// Get a data fragment to write into, creating a new one if the current
   /// fragment is not a data fragment.
   MCDataFragment *getOrCreateDataFragment();
 
   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.
-  void flushPendingLabels(MCFragment *F, uint64_t FOffset = 0);
+  void flushPendingLabels(MCFragment *F);
 
 public:
   void visitUsedSymbol(const MCSymbol &Sym) override;
 
   MCAssembler &getAssembler() { return *Assembler; }
 
   /// \name MCStreamer Interface
   /// @{

lib/MC/MCELFStreamer.cpp

if (RequiredBundlePadding > 0) {
       MCObjectWriter *OW = Assembler.getBackend().createObjectWriter(VecOS);
 
       EF->setBundlePadding(static_cast<uint8_t>(RequiredBundlePadding));
 
       Assembler.writeFragmentPadding(*EF, FSize, OW);
       VecOS.flush();
       delete OW;
 
+      // Push any symbols which are on the fragment boundary below the padding.
+      size_t Offset = DF->getContents().size();
+      for (const MCSymbol &Symbol : Assembler.symbols()) {
+        MCSymbolData &SD = Symbol.getData();
+        if (SD.getFragment() == DF && SD.getOffset() == Offset) {
+          SD.setOffset(SD.getOffset() + Code.size());
+        }
+      }
       DF->getContents().append(Code.begin(), Code.end());
     }
   }
 
-  flushPendingLabels(DF, DF->getContents().size());
-
   for (unsigned i = 0, e = EF->getFixups().size(); i != e; ++i) {
     EF->getFixups()[i].setOffset(EF->getFixups()[i].getOffset() +
                                  DF->getContents().size());
     DF->getFixups().push_back(EF->getFixups()[i]);
   }
   DF->setHasInstructions(true);
   DF->getContents().append(EF->getContents().begin(), EF->getContents().end());
 }

lib/MC/MCObjectStreamer.cpp

 
 MCObjectStreamer::~MCObjectStreamer() {
   delete &Assembler->getBackend();
   delete &Assembler->getEmitter();
   delete &Assembler->getWriter();
   delete Assembler;
 }
 
-void MCObjectStreamer::flushPendingLabels(MCFragment *F, uint64_t FOffset) {
+void MCObjectStreamer::flushPendingLabels(MCFragment *F) {
   if (PendingLabels.size()) {
     if (!F) {
       F = new MCDataFragment();
       CurSectionData->getFragmentList().insert(CurInsertionPoint, F);
       F->setParent(CurSectionData);
     }
     for (MCSymbolData *SD : PendingLabels) {
       SD->setFragment(F);
-      SD->setOffset(FOffset);
     }
     PendingLabels.clear();
   }
 }
 
 bool MCObjectStreamer::emitAbsoluteSymbolDiff(const MCSymbol *Hi,
                                               const MCSymbol *Lo,
                                               unsigned Size) {
void MCObjectStreamer::EmitLabel(MCSymbol *Symbol) {
   MCStreamer::EmitLabel(Symbol);
 
   MCSymbolData &SD = getAssembler().getOrCreateSymbolData(*Symbol);
   assert(!SD.getFragment() && "Unexpected fragment on symbol data!");
 
   // If there is a current fragment, mark the symbol as pointing into it.
   // Otherwise queue the label and set its fragment pointer when we emit the
   // next fragment.
-  auto *F = dyn_cast_or_null<MCDataFragment>(getCurrentFragment());
-  if (F && !(getAssembler().isBundlingEnabled() &&
-             getAssembler().getRelaxAll())) {
+  if (auto *F = dyn_cast_or_null<MCDataFragment>(getCurrentFragment())) {
     SD.setFragment(F);
     SD.setOffset(F->getContents().size());
   } else {
     PendingLabels.push_back(&SD);
   }
 }
 
 void MCObjectStreamer::EmitULEB128Value(const MCExpr *Value) {

test/MC/X86/AlignedBundling/rodata-section.s

+# RUN: llvm-mc -triple=i686-nacl -filetype=obj %s -o - | \
+# RUN: llvm-objdump -disassemble -no-show-raw-insn - | FileCheck %s
+# RUN: llvm-mc -triple=i686-nacl -filetype=obj -mc-relax-all %s -o - | \
+# RUN: llvm-objdump -disassemble -no-show-raw-insn - | FileCheck %s
+
+        .bundle_align_mode 5
+        .text
+        .globl  foo
+        .align  32, 0x90
+        .type   foo,@function
+foo:
+        subl  $12, %esp
+# CHECK: 3: movl $14, 8(%esp)
+        movl  $.str2, 8(%esp)
+# CHECK: b: movl $7, 4(%esp)
+        movl  $.str1, 4(%esp)
+# CHECK: 13: movl $0, (%esp)
+        movl  $.str, (%esp)
+        calll bar
+# CHECK: 1f: nop
+        addl  $12, %esp
+        popl  %ecx
+        jmp   *%ecx
+
+
+        .type .str,@object
+        .section  .rodata,"a",@progbits
+.str:
+        .asciz  "hello1"
+        .size .str, 7
+
+        .type .str1,@object
+.str1:
+        .asciz  "hello2"
+        .size .str1, 7
+
+        .type .str2,@object
+.str2:
+        .asciz  "hello3"
+        .size .str2, 7