[MC] Write padding into fragments when -mc-relax-all flag is used

[phosek]

Summary

When instruction bundling is enabled and the -mc-relax-all flag is
set, we can write bundle padding directly into fragments and avoid
creating large number of fragments significantly reducing LLVM MC
memory usage.

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

[eliben]

Could you first update http://www.chromium.org/nativeclient/pnacl/aligned-bundling-support-in-llvm to explain the proposed scheme in more general terms?

[eliben]

include/llvm/MC/MCAsmLayout.h

112 ↗

(On Diff #21251)

Is there a good reason to keep this a member and not just a standalone function?

include/llvm/MC/MCAssembler.h

1248

Here and elsewhere - please document all the new functions/methods you add - explaining their arguments, return values, etc.

include/llvm/MC/MCObjectStreamer.h

86

What is FOffset for?

lib/MC/MCAssembler.cpp

631

Does this comment need updating?

tools/pnacl-llc/pnacl-llc.cpp

706 ↗

(On Diff #21251)

This file doesn't see to belong here

[phosek]

Addressing code review comments.

[phosek]

I have added the description of the proposed scheme to http://www.chromium.org/nativeclient/pnacl/aligned-bundling-support-in-llvm as requested.

include/llvm/MC/MCAsmLayout.h

112 ↗

(On Diff #21251)

Refactored as a standalone function.

include/llvm/MC/MCAssembler.h

1248

Done for all the new functions/methods.

include/llvm/MC/MCObjectStreamer.h

86

I have update the comment to address that.

lib/MC/MCAssembler.cpp

631

I have update the comment to mention the optimization used when relax all flag is used.

tools/pnacl-llc/pnacl-llc.cpp

706 ↗

(On Diff #21251)

Right, this is a leftover testing artifact; removed.

[eliben]

include/llvm/MC/MCAssembler.h

1248

Please place all method comments consistently on the method declaration, rather than definition

1259

Describe FOffest and FSize

include/llvm/MC/MCELFStreamer.h

118

Describe this new data structure

lib/MC/MCAssembler.cpp

638–644

writing

705

So this FIXME is potentially addressed?

lib/MC/MCELFStreamer.cpp

496

Each clause here had a comment explaining what's going on - please preserve that

573

Add a comment above this block explaining what it's doing

597–614

Add a comment above this block explaining what it's doing

[phosek]

Addressing code review comments.

[eliben]

LGTM

[mseaborn]

llvm/trunk/lib/MC/MCObjectStreamer.cpp

148 ↗

(On Diff #23662)

What is the reason for checking isBundlingEnabled() and getRelaxAll() here?

Could this explain why references to data sections are coming out wrong? (See the bug described here: https://chromiumcodereview.appspot.com/1129013004/#msg5)

You are calling flushPendingLabels() from mergeFragment(), but that doesn't get called if we are processing data sections. (mergeFragment() is called from EmitInstToData().)

When we are processing data directives such as ".long" or ".asciz", what would cause labels to get their offsets set (via setOffset())?

include/llvm/MC/MCAssembler.h

public:
   }
 
   void addFileName(StringRef FileName) {
     if (std::find(file_names_begin(), file_names_end(), FileName) ==
         file_names_end())
       FileNames.push_back(FileName);
   }
 
+  /// \brief Write the necessary bundle padding to the given object writer.
+  /// Expects a fragment \p F containing instructions and its size \p FSize.
   void writeFragmentPadding(const MCFragment &F, uint64_t FSize,
                             MCObjectWriter *OW) const;
 
   /// @}
 
   void dump();
 };
 
-/// \brief Compute the amount of padding required before this fragment to
-/// obey bundling restrictions.
+/// \brief Compute the amount of padding required before the fragment \p F to
+/// obey bundling restrictions, where \p FOffset is the fragment's offset in
+/// its section and \p FSize is the fragment's size.
 uint64_t computeBundlePadding(const MCAssembler &Assembler,
                               const MCFragment *F,
                               uint64_t FOffset, uint64_t FSize);
 
 } // end namespace llvm
 
 #endif

include/llvm/MC/MCELFStreamer.h

public:
   void EmitBundleUnlock() override;
 
 private:
   void EmitInstToFragment(const MCInst &Inst, const MCSubtargetInfo &) override;
   void EmitInstToData(const MCInst &Inst, const MCSubtargetInfo &) override;
 
   void fixSymbolsInTLSFixups(const MCExpr *expr);
 
+  /// \brief Merge the content of the fragment \p EF into the fragment \p DF.
   void mergeFragment(MCDataFragment *, MCEncodedFragmentWithFixups *);
 
   bool SeenIdent;
 
   struct LocalCommon {
     MCSymbolData *SD;
     uint64_t Size;
     unsigned ByteAlignment;
   };
 
   std::vector<LocalCommon> LocalCommons;
 
   SmallPtrSet<MCSymbol *, 16> BindingExplicitlySet;
 
+  /// BundleGroups - The stack of fragments holding the bundle-locked
+  /// instructions.
   llvm::SmallVector<MCDataFragment *, 4> BundleGroups;
 };
 
 MCELFStreamer *createARMELFStreamer(MCContext &Context, MCAsmBackend &TAB,
                                     raw_ostream &OS, MCCodeEmitter *Emitter,
                                     bool RelaxAll, bool IsThumb);
 
 } // end namespace llvm
 
 #endif

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(const 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 which will be set
-  // as a symbol offset within the fragment.
+  /// 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);
 
 public:
   void visitUsedSymbol(const MCSymbol &Sym) override;
 
   MCAssembler &getAssembler() { return *Assembler; }
 
   /// @name MCStreamer Interface

lib/MC/MCAssembler.cpp

void MCAsmLayout::layoutFragment(MCFragment *F) {
   // If bundling is enabled and this fragment has instructions in it, it has to
   // obey the bundling restrictions. With padding, we'll have:
   //
   //
   //        BundlePadding
   //             |||
   // -------------------------------------
   //   Prev  |##########|       F        |
   // -------------------------------------
   //                    ^
   //                    |
   //                    F->Offset
   //
   // The fragment's offset will point to after the padding, and its computed
   // size won't include the padding.
   //
-  // When relax all flag is used, we optimize the bundling by writting the
-  // padding directly into fragments as the instructions are emitted in the
-  // streamer.
+  // When the -mc-relax-all flag is used, we optimize bundling by writting the
+  // bundle padding directly into fragments when the instructions are emitted
+  // inside the streamer.
   //
   if (Assembler.isBundlingEnabled() && !Assembler.getRelaxAll() &&
       F->hasInstructions()) {
     assert(isa<MCEncodedFragment>(F) &&
            "Only MCEncodedFragment implementations have instructions");
     uint64_t FSize = Assembler.computeFragmentSize(*this, *F);
 
     if (FSize > Assembler.getBundleAlignSize())
       report_fatal_error("Fragment can't be larger than a bundle size");
 
     uint64_t RequiredBundlePadding = computeBundlePadding(Assembler, F,
                                                           F->Offset, FSize);
     if (RequiredBundlePadding > UINT8_MAX)
       report_fatal_error("Padding cannot exceed 255 bytes");
     F->setBundlePadding(static_cast<uint8_t>(RequiredBundlePadding));
     F->Offset += RequiredBundlePadding;
   }
 }
 
 /// \brief Write the contents of a fragment to the given object writer. Expects
 ///        a MCEncodedFragment.
 static void writeFragmentContents(const MCFragment &F, MCObjectWriter *OW) {
   const MCEncodedFragment &EF = cast<MCEncodedFragment>(F);
   OW->WriteBytes(EF.getContents());
 }
 
-/// \brief Write the necessary bundle padding to the given object writer.
-//         Expects a fragment containing instructions and its size.
 void MCAssembler::writeFragmentPadding(const MCFragment &F, uint64_t FSize,
                                        MCObjectWriter *OW) const {
   // Should NOP padding be written out before this fragment?
   unsigned BundlePadding = F.getBundlePadding();
   if (BundlePadding > 0) {
     assert(isBundlingEnabled() &&
            "Writing bundle padding with disabled bundling");
     assert(F.hasInstructions() &&
void MCAssembler::writeFragmentPadding(const MCFragment &F, uint64_t FSize,
   }
 }
 
 /// \brief Write the fragment \p F to the output file.
 static void writeFragment(const MCAssembler &Asm, const MCAsmLayout &Layout,
                           const MCFragment &F) {
   MCObjectWriter *OW = &Asm.getWriter();
 
   // FIXME: Embed in fragments instead?
   uint64_t FragmentSize = Asm.computeFragmentSize(Layout, F);
 
   Asm.writeFragmentPadding(F, FragmentSize, OW);
 
   // This variable (and its dummy usage) is to participate in the assert at
   // the end of the function.
   uint64_t Start = OW->getStream().tell();
   (void) Start;

lib/MC/MCELFStreamer.cpp

 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 MCELFStreamer::~MCELFStreamer() {
 }
 
-/// \brief Merge the content of the fragment \p EF into the fragment \p DF.
 void MCELFStreamer::mergeFragment(MCDataFragment *DF,
                                   MCEncodedFragmentWithFixups *EF) {
   MCAssembler &Assembler = getAssembler();
 
   if (Assembler.isBundlingEnabled() && Assembler.getRelaxAll()) {
     uint64_t FSize = EF->getContents().size();
 
     if (FSize > Assembler.getBundleAlignSize())
void MCELFStreamer::EmitInstToData(const MCInst &Inst,
   //   data fragment because we want all the instructions in a group to get into
   //   the same fragment. Be careful not to do that for the first instruction in
   //   the group, though.
   MCDataFragment *DF;
 
   if (Assembler.isBundlingEnabled()) {
     MCSectionData *SD = getCurrentSectionData();
     if (Assembler.getRelaxAll() && SD->isBundleLocked())
+      // If the -mc-relax-all flag is used and we are bundle-locked, we re-use
+      // the current bundle group.
       DF = BundleGroups.back();
     else if (Assembler.getRelaxAll() && !SD->isBundleLocked())
+      // When not in a bundle-locked group and the -mc-relax-all flag is used,
+      // we create a new temporary fragment which will be later merged into
+      // the current fragment.
       DF = new MCDataFragment();
     else if (SD->isBundleLocked() && !SD->isBundleGroupBeforeFirstInst())
       // If we are bundle-locked, we re-use the current fragment.
       // The bundle-locking directive ensures this is a new data fragment.
       DF = cast<MCDataFragment>(getCurrentFragment());
     else if (!SD->isBundleLocked() && Fixups.size() == 0) {
       // Optimize memory usage by emitting the instruction to a
       // MCCompactEncodedInstFragment when not in a bundle-locked group and
void MCELFStreamer::EmitBundleLock(bool AlignToEnd) {
   // Sanity checks
   //
   if (!getAssembler().isBundlingEnabled())
     report_fatal_error(".bundle_lock forbidden when bundling is disabled");
 
   if (!SD->isBundleLocked())
     SD->setBundleGroupBeforeFirstInst(true);
 
   if (getAssembler().getRelaxAll() && !SD->isBundleLocked()) {
     // TODO: drop the lock state and set directly in the fragment
     MCDataFragment *DF = new MCDataFragment();
     BundleGroups.push_back(DF);
   }
 
   SD->setBundleLockState(AlignToEnd ? MCSectionData::BundleLockedAlignToEnd :
                                       MCSectionData::BundleLocked);
 }
 
 void MCELFStreamer::EmitBundleUnlock() {
   MCSectionData *SD = getCurrentSectionData();
 
   // Sanity checks
   if (!getAssembler().isBundlingEnabled())
     report_fatal_error(".bundle_unlock forbidden when bundling is disabled");
   else if (!SD->isBundleLocked())
     report_fatal_error(".bundle_unlock without matching lock");
   else if (SD->isBundleGroupBeforeFirstInst())
     report_fatal_error("Empty bundle-locked group is forbidden");
 
+  // When the -mc-relax-all flag is used, we emit instructions to fragments
+  // stored on a stack. When the bundle unlock is emited, we pop a fragment 
+  // from the stack a merge it to the one below.
   if (getAssembler().getRelaxAll()) {
     assert(!BundleGroups.empty() && "There are no bundle groups");
     MCDataFragment *DF = BundleGroups.back();
 
+    // FIXME: Use BundleGroups to track the lock state instead.
     SD->setBundleLockState(MCSectionData::NotBundleLocked);
 
+    // FIXME: Use more separate fragments for nested groups. 
     if (!SD->isBundleLocked()) {
       mergeFragment(getOrCreateDataFragment(), DF);
       BundleGroups.pop_back();
       delete DF;
     }
 
     if (SD->getBundleLockState() != MCSectionData::BundleLockedAlignToEnd)
       getOrCreateDataFragment()->setAlignToBundleEnd(false);
   } else
     SD->setBundleLockState(MCSectionData::NotBundleLocked);
 }
 
 void MCELFStreamer::Flush() {
   for (std::vector<LocalCommon>::const_iterator i = LocalCommons.begin(),
                                                 e = LocalCommons.end();
        i != e; ++i) {
     MCSymbolData *SD = i->SD;
     uint64_t Size = i->Size;