[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 ↗

(On Diff #27346)

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

3

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

Same below.

7

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

13

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.

24

Nit: Can you make the alignment indentation consistent?

[mseaborn]

lib/MC/MCELFStreamer.cpp

77 ↗

(On Diff #27346)

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 ↗

(On Diff #27346)

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 ↗

(On Diff #27346)

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

3

Done.

7

It's only redundant in pnacl-llvm branch.

13

Done.

24

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.

lib/MC/MCObjectStreamer.cpp

void MCObjectStreamer::EmitCFISections(bool EH, bool Debug) {
   EmitEHFrame = EH;
   EmitDebugFrame = Debug;
 }
 
 void MCObjectStreamer::EmitValueImpl(const MCExpr *Value, unsigned Size,
                                      const SMLoc &Loc) {
   MCStreamer::EmitValueImpl(Value, Size, Loc);
   MCDataFragment *DF = getOrCreateDataFragment();
+  flushPendingLabels(DF, DF->getContents().size());
 
   MCLineEntry::Make(this, getCurrentSection().first);
 
   // Avoid fixups when possible.
   int64_t AbsValue;
   if (Value->evaluateAsAbsolute(AbsValue, getAssembler())) {
     EmitIntValue(AbsValue, Size);
     return;
if (AddrDelta->evaluateAsAbsolute(Res, getAssembler())) {
     MCDwarfFrameEmitter::EmitAdvanceLoc(*this, Res);
     return;
   }
   insert(new MCDwarfCallFrameFragment(*AddrDelta));
 }
 
 void MCObjectStreamer::EmitBytes(StringRef Data) {
   MCLineEntry::Make(this, getCurrentSection().first);
-  getOrCreateDataFragment()->getContents().append(Data.begin(), Data.end());
+  MCDataFragment *DF = getOrCreateDataFragment();
+  flushPendingLabels(DF, DF->getContents().size());
+  DF->getContents().append(Data.begin(), Data.end());
 }
 
 void MCObjectStreamer::EmitValueToAlignment(unsigned ByteAlignment,
                                             int64_t Value,
                                             unsigned ValueSize,
                                             unsigned MaxBytesToEmit) {
   if (MaxBytesToEmit == 0)
     MaxBytesToEmit = ByteAlignment;
if (!Delta->evaluateAsAbsolute(Res, getAssembler()))
     return true;
   EmitFill(Res, Value);
   return false;
 }
 
 // Associate GPRel32 fixup with data and resize data area
 void MCObjectStreamer::EmitGPRel32Value(const MCExpr *Value) {
   MCDataFragment *DF = getOrCreateDataFragment();
+  flushPendingLabels(DF, DF->getContents().size());
 
   DF->getFixups().push_back(MCFixup::create(DF->getContents().size(), 
                                             Value, FK_GPRel_4));
   DF->getContents().resize(DF->getContents().size() + 4, 0);
 }
 
 // Associate GPRel32 fixup with data and resize data area
 void MCObjectStreamer::EmitGPRel64Value(const MCExpr *Value) {
   MCDataFragment *DF = getOrCreateDataFragment();
+  flushPendingLabels(DF, DF->getContents().size());
 
   DF->getFixups().push_back(MCFixup::create(DF->getContents().size(), 
                                             Value, FK_GPRel_4));
   DF->getContents().resize(DF->getContents().size() + 8, 0);
 }
 
 void MCObjectStreamer::EmitFill(uint64_t NumBytes, uint8_t FillValue) {
   // FIXME: A MCFillFragment would be more memory efficient but MCExpr has
   //        problems evaluating expressions across multiple fragments.
-  getOrCreateDataFragment()->getContents().append(NumBytes, FillValue);
+  MCDataFragment *DF = getOrCreateDataFragment();
+  flushPendingLabels(DF, DF->getContents().size());
+  DF->getContents().append(NumBytes, FillValue);
 }
 
 void MCObjectStreamer::EmitZeros(uint64_t NumBytes) {
   const MCSection *Sec = getCurrentSection().first;
   assert(Sec && "need a section");
   unsigned ItemSize = Sec->isVirtualSection() ? 0 : 1;
   insert(new MCFillFragment(0, ItemSize, NumBytes));
 }

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
+  .align  32, 0x90
+# CHECK: 0: movl $14, 8(%esp)
+  movl  $.str2, 8(%esp)
+# CHECK: 8: movl $7, 4(%esp)
+  movl  $.str1, 4(%esp)
+# CHECK: 10: movl $0, (%esp)
+  movl  $.str, (%esp)
+
+  .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