[MC] Adding code padding for performance stability - infrastructure. NFC.

[opaparo]

Summary

Implementation of padding code with nop instructions in key places that will cause performance improvement.
The implementation is such that the adding of the nops is done in the Assembler after the layout is done and all IPs and alignments are known.
The patch is the result of this RFC: http://lists.llvm.org/pipermail/llvm-dev/2016-November/107223.html
This is the first patch of the implemented solution, and contains only the infrastructure needed for this change (this by itself is a NFC).

[opaparo]

Should we expose this to the .s?

That would make it easy to test codegen because you would just need to
check for things like .pad_bb_begin.

It would make it easier to test the layout as you could use a simple .s
file for that.

Cheers,
Rafael

Hi Rafael,

Unfortunately it cannot be exposed to the .s. I'll explain:
When generating an object file, MCObjectStreamer (or more specifically, one of its descendants) is used as the MCStreamer by MCAsmPrinter. All the decisions regarding the places to insert padding and the final size of the padding are made in the MCAsmBackend, which is a member of MCObjectStreamer (via the MCAssembler). Some of those decisions (the decisions regarding the final size of the padding) rely on the final layout of the code (as manifested by MCAsmLayout). On the other hand, when generating a .s file, MCAsmStreamer is used as the MCStreamer by MCAsmPrinter. Unlike MCObjectStreamer, this streamer does not require a MCAsmBackend. In addition, .s files don't have a layout, so there's no MCAsmLayout either, which, as I stated, is needed for the decision making. All in all, we can't mimic the padding behavior when generating a .s file.

Hope that explains it.

Thanks,
Omer

[craig.topper]

Can you please repost the diff with full context using one of the commands mentioned here. http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

That will allow phabricator to show the entire file that's being touched so we can see areas around your patch in the web interface.

include/llvm/MC/MCCodePadder.h

43

I think LLVM coding practices would prefer DenseSet here, but I'm not sure.

64

I think we would normally use DenseMap here.

[craig.topper]

include/llvm/MC/MCAsmBackend.h

22

I don't think MC layer supposed to use any of the Machine* classes.

[zvi]

Please update the patch with a context that contains the full file (svn diff -U99999 ...)

Can you add a short section to docs/CodeGenerator.rst explaining how code padding works? It will make it easier to review this patch and following patches, and would serve as a good reference.

It would be helpful if you uploaded the next patch in the queue to justify this patch.

include/llvm/MC/MCCodePadder.h

71

Where is this used?

include/llvm/MC/MCFragment.h

44

check the alignment

327

Please add a description for this class

338

Use:
struct Foo {};

instead of:
typedef struct {} Foo;

339

check alignment

407

Not sure we need this method

lib/MC/MCAsmBackend.cpp

21

Avoid the need for explicit initialization and destruction by using a unique_ptr<> or a similar object.
Or even better (if possible) avoid allocating on the heap.

25

is getOrCreateCodePadder a better name?

26

Is there a way to avoid these repeating runtime checks by requiring the user to ensure createCodePadder() happends before any getCodePadder()?
If handleCodePaddingFunctionStart() is called before other callers of getCodePadder(), maybe the allocation should happen there?

31

Is this function called anywhere other than getCodePadder? If no, i think we don't need it

lib/MC/MCCodePadder.cpp

64

if (SealedSections.count(...)) is a bit more compact

196

auto

228

Maybe "Fragment key already exists" would be more accurate?

234

auto

[opaparo]

include/llvm/MC/MCAsmBackend.h

22

Thanks for the heads up. I am now looking for ways to remove those unwanted dependencies.

[opaparo]

Removed unwanted dependencies introduces in my previous patch: MC layer no longer depends on CodeGen, Core or Target. This was achieved by introducing a new structure named MCCodePaddingContext that is being created by AsmPrinter and passed on to the MC layer (all the way to MCCodePadder). This replaces the direct use of TargetMachine, MachineBasicBlock, MachineFunction and MachineLoopInfo by the MCCodePadder.
Note: This time I used "svn diff -x -U999999" to create the patch, so comparison between this patch and the previous one may prove to be challenging (This had to be done for future work and review).

[opaparo]

Ping

[craig.topper]

I'm going to add @rafael to this since he's much more familiar with the MC layer than myself.

lib/MC/MCAssembler.cpp

938

Remove the blank lines above and below your code to match the prevailing style of this switch.

[chandlerc]

Adding folks here with a strong interest in this. =]

[davidxl]

Can you send the full patch so that we can help evaluate it?

[davidxl]

Tried the two patches with our internal benchmark -- the alignment related performance issue is still there. The problem disappears with -mllvm -x86-experimental-pref-loop-alignment=5 is used.

[opaparo]

In D34393#844569, @davidxl wrote:

Tried the two patches with our internal benchmark -- the alignment related performance issue is still there. The problem disappears with -mllvm -x86-experimental-pref-loop-alignment=5 is used.

I can think of two reasons that might have caused the patch to fail to help you:

1. This optimization is not enabled for all architectures. Use -target-cpu to specify the target (if you haven't already) to make sure you are compiling for the desired architecture, which will enable the optimization (if relevant). See the constructor of X86MCCodePadder for the list of architectures for which the optimization is enabled.
2. You might have encountered a different alignment issue than the one handled by this patch. I will send you soon another patch (which was not yet uploaded for review) that addresses another alignment issue (in addition to the first one), which will hopefully handle your case. Regardless of the results you'll get, could you send a small reproducer for this problem? I would like to investigate it and see the kind of alignment issue we are facing here.

[gadi.haber]

include/llvm/CodeGen/AsmPrinter.h

630

Consider to rename the method to: setupCodePaddingContext

include/llvm/MC/MCAsmBackend.h

153

when --> after

include/llvm/MC/MCCodePadder.h

24

MCPaddingFragment --> MCCodePaddingFragment ?

47

PaddingPolicies --> CodePaddingPolicies ?

216

basicBlockRequiresPaddingFragment --> isBasicBlockRequiresPaddingFragment ?

224

instructionRequiresPaddingFragment --> isInstructionRequiresPaddingFragment

236

computeRangePenaltyWeight --> computeScopePenaltyWeight ?

include/llvm/MC/MCFragment.h

332

MCPaddingFragment --> MCCodePaddingFragment

335

PaddingPoliciesMask --> AggregatedPaddingPoliciesMask ?

lib/CodeGen/AsmPrinter/AsmPrinter.cpp

2607

IsPaddingActive --> IsCodePaddingActive ?

[opaparo]

1. MCAsmBackend c'tor now takes a unique_ptr of MCCodePadder instead of a raw pointer
2. MCCodePaddingContext has a new field: IsBasicBlockReachableViaBranch
3. Changed names of a function and several variables

[opaparo]

include/llvm/MC/MCCodePadder.h

24

I actually don't want to limit the padding to code padding. My current implementation indeed pads with code (nops), but future implementation may pad in a different way.

216

This convention also exists in LLVM, I rather not change the name.

224

This convention also exists in LLVM, I rather not change the name.

include/llvm/CodeGen/AsmPrinter.h

 class MachineFunction;
 class MachineInstr;
 class MachineJumpTableInfo;
 class MachineLoopInfo;
 class MachineModuleInfo;
 class MachineOptimizationRemarkEmitter;
 class MCAsmInfo;
 class MCCFIInstruction;
+struct MCCodePaddingContext;
 class MCContext;
 class MCExpr;
 class MCInst;
 class MCSection;
 class MCStreamer;
 class MCSubtargetInfo;
 class MCSymbol;
 class MCTargetOptions;
public:
 
   /// Targets can override this to emit stuff at the start of a basic block.
   /// By default, this method prints the label for the specified
   /// MachineBasicBlock, an alignment (if present) and a comment describing it
   /// if appropriate.
   virtual void EmitBasicBlockStart(const MachineBasicBlock &MBB) const;
 
   /// Targets can override this to emit stuff at the end of a basic block.
-  virtual void EmitBasicBlockEnd(const MachineBasicBlock &MBB) {}
+  virtual void EmitBasicBlockEnd(const MachineBasicBlock &MBB);
 
   /// Targets should implement this to emit instructions.
   virtual void EmitInstruction(const MachineInstr *) {
     llvm_unreachable("EmitInstruction not implemented");
   }
 
   /// Return the symbol for the specified constant pool entry.
   virtual MCSymbol *GetCPISymbol(unsigned CPID) const;
private:
   /// Emit llvm.ident metadata in an '.ident' directive.
   void EmitModuleIdents(Module &M);
   void EmitXXStructorList(const DataLayout &DL, const Constant *List,
                           bool isCtor);
   GCMetadataPrinter *GetOrCreateGCPrinter(GCStrategy &C);
   /// Emit GlobalAlias or GlobalIFunc.
   void emitGlobalIndirectSymbol(Module &M,
                                 const GlobalIndirectSymbol& GIS);
+  void setupPaddingContext(const MachineBasicBlock &MBB,
+                           MCCodePaddingContext &Context) const;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_ASMPRINTER_H

include/llvm/MC/MCAsmBackend.h

 //===- llvm/MC/MCAsmBackend.h - MC Asm Backend ------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_MC_MCASMBACKEND_H
 #define LLVM_MC_MCASMBACKEND_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/MC/MCCodePadder.h"
 #include "llvm/MC/MCDirectives.h"
 #include "llvm/MC/MCFixup.h"
+#include "llvm/MC/MCFragment.h"
 #include <cstdint>
+#include <memory>
 
 namespace llvm {
 
 class MCAsmLayout;
 class MCAssembler;
 class MCCFIInstruction;
+class MCCodePadder;
 struct MCFixupKindInfo;
 class MCFragment;
 class MCInst;
+class MCObjectStreamer;
 class MCObjectWriter;
 class MCRelaxableFragment;
 class MCSubtargetInfo;
 class MCValue;
 class raw_pwrite_stream;
 
 /// Generic interface to target specific assembler backends.
 class MCAsmBackend {
+  std::unique_ptr<MCCodePadder> CodePadder;
+
 protected: // Can only create subclasses.
-  MCAsmBackend();
+  MCAsmBackend(MCCodePadder *TargetCodePadder = nullptr);
 
 public:
   MCAsmBackend(const MCAsmBackend &) = delete;
   MCAsmBackend &operator=(const MCAsmBackend &) = delete;
   virtual ~MCAsmBackend();
 
   /// lifetime management
   virtual void reset() {}
public:
   /// Handle any target-specific assembler flags. By default, do nothing.
   virtual void handleAssemblerFlag(MCAssemblerFlag Flag) {}
 
   /// \brief Generate the compact unwind encoding for the CFI instructions.
   virtual uint32_t
       generateCompactUnwindEncoding(ArrayRef<MCCFIInstruction>) const {
     return 0;
   }
+
+  /// Handles all target related code padding when starting to write a new
+  /// basic block to an object file.
+  ///
+  /// \param OS The streamer used for writing the padding data and function.
+  /// \param Context the context of the padding, Embeds the basic block's
+  /// parameters.
+  void handleCodePaddingBasicBlockStart(MCObjectStreamer *OS,
+                                        const MCCodePaddingContext &Context);
+  /// Handles all target related code padding when done writing a block to an
+  /// object file.
+  ///
+  /// \param Context the context of the padding, Embeds the basic block's
+  /// parameters.
+  void handleCodePaddingBasicBlockEnd(const MCCodePaddingContext &Context);
+  /// Handles all target related code padding before writing a new instruction
+  /// to an object file.
+  ///
+  /// \param Inst the instruction.
+  void handleCodePaddingInstructionBegin(const MCInst &Inst);
+  /// Handles all target related code padding after writing an instruction to an
+  /// object file.
+  ///
+  /// \param Inst the instruction.
+  void handleCodePaddingInstructionEnd(const MCInst &Inst);
+
+  /// Relaxes a fragment (changes the size of the padding) according to target
+  /// requirements. The new size computation is done w.r.t a layout.
+  ///
+  /// \param Fragment The fragment to relax.
+  /// \param Layout Code layout information.
+  ///
+  /// \returns true iff any relaxation occured.
+  bool relaxFragment(MCPaddingFragment *PF, MCAsmLayout &Layout);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_MC_MCASMBACKEND_H

include/llvm/MC/MCAssembler.h

private:
   bool layoutOnce(MCAsmLayout &Layout);
 
   /// \brief Perform one layout iteration of the given section and return true
   /// if any offsets were adjusted.
   bool layoutSectionOnce(MCAsmLayout &Layout, MCSection &Sec);
 
   bool relaxInstruction(MCAsmLayout &Layout, MCRelaxableFragment &IF);
 
+  bool relaxPaddingFragment(MCAsmLayout &Layout, MCPaddingFragment &PF);
+
   bool relaxLEB(MCAsmLayout &Layout, MCLEBFragment &IF);
 
   bool relaxDwarfLineAddr(MCAsmLayout &Layout, MCDwarfLineAddrFragment &DF);
   bool relaxDwarfCallFrameFragment(MCAsmLayout &Layout,
                                    MCDwarfCallFrameFragment &DF);
   bool relaxCVInlineLineTable(MCAsmLayout &Layout,
                               MCCVInlineLineTableFragment &DF);
   bool relaxCVDefRange(MCAsmLayout &Layout, MCCVDefRangeFragment &DF);

include/llvm/MC/MCCodePadder.h

+//===- llvm/MC/CodePadder.h - MC Code Padder --------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_MC_MCCODEPADDER_H
+#define LLVM_MC_MCCODEPADDER_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+
+namespace llvm {
+
+class MCAsmLayout;
+class MCCodePaddingPolicy;
+class MCFragment;
+class MCInst;
+class MCObjectStreamer;
+class MCPaddingFragment;
+class MCSection;
+
+typedef SmallVector<const MCPaddingFragment *, 8> MCPFRange;
+
+struct MCCodePaddingContext {
+  bool IsPaddingActive;
+  bool IsBasicBlockInsideInnermostLoop;
+  bool IsBasicBlockReachableViaFallthrough;
+};
+
+/// Target-independent base class incharge of all code padding decisions for a
+/// target. During encoding it determines if and where MCPaddingFragments will
+/// be located, as later on, when layout information is available, it determines
+/// their sizes.
+class MCCodePadder {
+  MCCodePadder(const MCCodePadder &) = delete;
+  void operator=(const MCCodePadder &) = delete;
+
+  /// Determines if the MCCodePaddingPolicies are active.
+  bool ArePoliciesActive;
+
+  /// All the supported MCCodePaddingPolicies.
+  SmallPtrSet<MCCodePaddingPolicy *, 4> PaddingPolicies;
+
+  /// A pointer to the fragment of the instruction whose padding is currently
+  /// done for.
+  MCPaddingFragment *CurrHandledInstFragment;
+
+  /// A map holding the jurisdiction for each padding fragment. Key: padding
+  /// fragment. Value: The fragment's jurisdiction. A jurisdiction is a vector
+  /// of padding fragments whose conditions are being controlled by another
+  /// fragment, the key fragment.
+  DenseMap<MCPaddingFragment *, MCPFRange> FragmentToJurisdiction;
+  MCPFRange &getJurisdiction(MCPaddingFragment *Fragment, MCAsmLayout &Layout);
+
+  /// A map holding the maximal instruction window size relevant for a padding
+  /// fragment.
+  DenseMap<MCPaddingFragment *, uint64_t> FragmentToMaxWindowSize;
+  uint64_t getMaxWindowSize(MCPaddingFragment *Fragment, MCAsmLayout &Layout);
+
+protected:
+  /// The current streamer, used to stream code padding.
+  MCObjectStreamer *OS;
+
+  bool addPolicy(MCCodePaddingPolicy *Policy);
+
+  virtual bool
+  basicBlockRequiresInsertionPoint(const MCCodePaddingContext &Context) {
+    return false;
+  }
+
+  virtual bool instructionRequiresInsertionPoint(const MCInst &Inst) {
+    return false;
+  }
+
+  virtual bool usePoliciesForBasicBlock(const MCCodePaddingContext &Context) {
+    return Context.IsPaddingActive;
+  }
+
+public:
+  MCCodePadder()
+      : ArePoliciesActive(false), CurrHandledInstFragment(nullptr),
+        OS(nullptr) {}
+  virtual ~MCCodePadder();
+
+  /// Handles all target related code padding when starting to write a new
+  /// basic block to an object file.
+  ///
+  /// \param OS The streamer used for writing the padding data and function.
+  /// \param Context the context of the padding, Embeds the basic block's
+  /// parameters.
+  void handleBasicBlockStart(MCObjectStreamer *OS,
+                             const MCCodePaddingContext &Context);
+  /// Handles all target related code padding when done writing a block to an
+  /// object file.
+  ///
+  /// \param Context the context of the padding, Embeds the basic block's
+  /// parameters.
+  void handleBasicBlockEnd(const MCCodePaddingContext &Context);
+  /// Handles all target related code padding before writing a new instruction
+  /// to an object file.
+  ///
+  /// \param Inst the instruction.
+  void handleInstructionBegin(const MCInst &Inst);
+  /// Handles all target related code padding after writing an instruction to an
+  /// object file.
+  ///
+  /// \param Inst the instruction.
+  void handleInstructionEnd(const MCInst &Inst);
+
+  /// Relaxes a fragment (changes the size of the padding) according to target
+  /// requirements. The new size computation is done w.r.t a layout.
+  ///
+  /// \param Fragment The fragment to relax.
+  /// \param Layout Code layout information.
+  ///
+  /// \returns true iff any relaxation occured.
+  bool relaxFragment(MCPaddingFragment *Fragment, MCAsmLayout &Layout);
+};
+
+/// The base class for all padding policies, i.e. a rule or set of rules to pad
+/// the generated code.
+class MCCodePaddingPolicy {
+  MCCodePaddingPolicy() = delete;
+  MCCodePaddingPolicy(const MCCodePaddingPolicy &) = delete;
+  void operator=(const MCCodePaddingPolicy &) = delete;
+
+protected:
+  /// A mask holding the kind of this policy, i.e. only the i'th bit will be set
+  /// where i is the kind number.
+  const uint64_t KindMask;
+  /// Instruction window size relevant to this policy.
+  const uint64_t WindowSize;
+  /// A boolean indicating which byte of the instruction determies its
+  /// instruction window. If true - the last byte of the instructions, o.w. -
+  /// the first byte of the instruction.
+  const bool InstByteIsLastByte;
+
+  MCCodePaddingPolicy(uint64_t Kind, uint64_t WindowSize,
+                      bool InstByteIsLastByte)
+      : KindMask(UINT64_C(1) << Kind), WindowSize(WindowSize),
+        InstByteIsLastByte(InstByteIsLastByte) {}
+
+  /// Computes and returns the offset of the consecutive fragment of a given
+  /// fragment.
+  ///
+  /// \param Fragment The fragment whose consecutive offset will be computed.
+  /// \param Layout Code layout information.
+  ///
+  /// \returns the offset of the consecutive fragment of \p Fragment.
+  static uint64_t getNextFragmentOffset(const MCFragment *Fragment,
+                                        const MCAsmLayout &Layout);
+  /// Returns the instruction byte of an instruction pointed by a given
+  /// MCPaddingFragment. An instruction byte is the address of the byte of an
+  /// instruction which determines its instruction window.
+  ///
+  /// \param Fragment The fragment pointing to the instruction.
+  /// \param Layout Code layout information.
+  ///
+  /// \returns the instruction byte of an instruction pointed by \p Fragment.
+  uint64_t getFragmentInstByte(const MCPaddingFragment *Fragment,
+                               MCAsmLayout &Layout) const;
+  uint64_t computeWindowEndAddress(const MCPaddingFragment *Fragment,
+                                   uint64_t Offset, MCAsmLayout &Layout) const;
+
+  /// Computes and returns the penalty weight of a first instruction window in a
+  /// range. This requires a special function since the first window does not
+  /// contain all the padding fragments in that window. It only contains all the
+  /// padding fragments starting from the relevant insertion point.
+  ///
+  /// \param Window The first window.
+  /// \param Offset The offset of the parent section relative to the beginning
+  /// of the file, mod the window size.
+  /// \param Layout Code layout information.
+  ///
+  /// \returns the penalty weight of a first instruction window in a range, \p
+  /// Window.
+  double computeFirstWindowPenaltyWeight(const MCPFRange &Window,
+                                         uint64_t Offset,
+                                         MCAsmLayout &Layout) const;
+  /// Computes and returns the penalty caused by an instruction window.
+  ///
+  /// \param Window The instruction window.
+  /// \param Offset The offset of the parent section relative to the beginning
+  /// of the file, mod the window size.
+  /// \param Layout Code layout information.
+  ///
+  /// \returns the penalty caused by \p Window.
+  virtual double computeWindowPenaltyWeight(const MCPFRange &Window,
+                                            uint64_t Offset,
+                                            MCAsmLayout &Layout) const = 0;
+
+public:
+  virtual ~MCCodePaddingPolicy() {}
+
+  /// Returns the kind mask of this policy -  A mask holding the kind of this
+  /// policy, i.e. only the i'th bit will be set where i is the kind number.
+  uint64_t getKindMask() const { return KindMask; }
+  /// Returns the instruction window size relevant to this policy.
+  uint64_t getWindowSize() const { return WindowSize; }
+  /// Returns true if the last byte of an instruction determines its instruction
+  /// window, or false if the first of an instruction determines it.
+  bool isInstByteLastByte() const { return InstByteIsLastByte; }
+
+  /// Returns true iff this policy needs padding for a given basic block.
+  ///
+  /// \param Context the context of the padding, Embeds the basic block's
+  /// parameters.
+  ///
+  /// \returns true iff this policy needs padding for the basic block.
+  virtual bool
+  basicBlockRequiresPaddingFragment(const MCCodePaddingContext &Context) const {
+    return false;
+  }
+  /// Returns true iff this policy needs padding for a given instruction.
+  ///
+  /// \param Inst The given instruction.
+  ///
+  /// \returns true iff this policy needs padding for \p Inst.
+  virtual bool instructionRequiresPaddingFragment(const MCInst &Inst) const {
+    return false;
+  }
+  /// Computes and returns the penalty caused by a range of instruction windows.
+  /// The weight is computed for each window separelty and then accumulated.
+  ///
+  /// \param Range The range.
+  /// \param Offset The offset of the parent section relative to the beginning
+  /// of the file, mod the window size.
+  /// \param Layout Code layout information.
+  ///
+  /// \returns the penalty caused by \p Range.
+  double computeRangePenaltyWeight(const MCPFRange &Range, uint64_t Offset,
+                                   MCAsmLayout &Layout) const;
+};
+
+} // namespace llvm
+
+#endif // LLVM_MC_MCCODEPADDER_H

include/llvm/MC/MCFragment.h

enum FragmentType : uint8_t {
     FT_Data,
     FT_CompactEncodedInst,
     FT_Fill,
     FT_Relaxable,
     FT_Org,
     FT_Dwarf,
     FT_DwarfFrame,
     FT_LEB,
+    FT_Padding,
     FT_SafeSEH,
     FT_CVInlineLines,
     FT_CVDefRange,
     FT_Dummy
   };
 
 private:
   FragmentType Kind;
public:
 
   /// @}
 
   static bool classof(const MCFragment *F) {
     return F->getKind() == MCFragment::FT_Align;
   }
 };
 
+/// Fragment for adding required padding.
+/// This fragment is always inserted before an instruction, and holds that
+/// instruction as context information (as well as a mask of kinds) for
+/// determining the padding size.
+///
+class MCPaddingFragment : public MCFragment {
+  /// A mask containing all the kinds relevant to this fragment. i.e. the i'th
+  /// bit will be set iff kind i is relevant to this fragment.
+  uint64_t PaddingPoliciesMask;
+  /// A boolean indicating if this fragment will actually hold padding. If its
+  /// value is false, then this fragment serves only as a placeholder,
+  /// containing data to assist other insertion point in their decision making.
+  bool IsInsertionPoint;
+
+  uint64_t Size;
+
+  struct MCInstInfo {
+    bool IsInitialized;
+    MCInst Inst;
+    /// A boolean indicating whether the instruction pointed by this fragment is
+    /// a fixed size instruction or a relaxable instruction held by a
+    /// MCRelaxableFragment.
+    bool IsImmutableSizedInst;
+    union {
+      /// If the instruction is a fixed size instruction, hold its size.
+      size_t InstSize;
+      /// Otherwise, hold a pointer to the MCRelaxableFragment holding it.
+      MCRelaxableFragment *InstFragment;
+    };
+  };
+  MCInstInfo InstInfo;
+
+public:
+  static const uint64_t PFK_None = UINT64_C(0);
+
+  enum MCPaddingFragmentKind {
+    // values 0-7 are reserved for future target independet values.
+
+    FirstTargetPerfNopFragmentKind = 8,
+
+    /// Limit range of target MCPerfNopFragment kinds to fit in uint64_t
+    MaxTargetPerfNopFragmentKind = 63
+  };
+
+  MCPaddingFragment(MCSection *Sec = nullptr)
+      : MCFragment(FT_Padding, false, 0, Sec), PaddingPoliciesMask(PFK_None),
+        IsInsertionPoint(false), Size(UINT64_C(0)),
+        InstInfo({false, MCInst(), false, {0}}) {}
+
+  bool isInsertionPoint() const { return IsInsertionPoint; }
+  void setAsInsertionPoint() { IsInsertionPoint = true; }
+  uint64_t getPaddingPoliciesMask() const { return PaddingPoliciesMask; }
+  void setPaddingPoliciesMask(uint64_t Value) { PaddingPoliciesMask = Value; }
+  bool hasPaddingPolicy(uint64_t PolicyMask) const {
+    assert(isPowerOf2_64(PolicyMask) &&
+           "Policy mask must contain exactly one policy");
+    return (getPaddingPoliciesMask() & PolicyMask) != PFK_None;
+  }
+  const MCInst &getInst() const {
+    assert(isInstructionInitialized() && "Fragment has no instruction!");
+    return InstInfo.Inst;
+  }
+  size_t getInstSize() const {
+    assert(isInstructionInitialized() && "Fragment has no instruction!");
+    if (InstInfo.IsImmutableSizedInst)
+      return InstInfo.InstSize;
+    assert(InstInfo.InstFragment != nullptr &&
+           "Must have a valid InstFragment to retrieve InstSize from");
+    return InstInfo.InstFragment->getContents().size();
+  }
+  void setInstAndInstSize(const MCInst &Inst, size_t InstSize) {
+  InstInfo.IsInitialized = true;
+    InstInfo.IsImmutableSizedInst = true;
+    InstInfo.Inst = Inst;
+    InstInfo.InstSize = InstSize;
+  }
+  void setInstAndInstFragment(const MCInst &Inst,
+                              MCRelaxableFragment *InstFragment) {
+    InstInfo.IsInitialized = true;
+    InstInfo.IsImmutableSizedInst = false;
+    InstInfo.Inst = Inst;
+    InstInfo.InstFragment = InstFragment;
+  }
+  uint64_t getSize() const { return Size; }
+  void setSize(uint64_t Value) { Size = Value; }
+  bool isInstructionInitialized() const { return InstInfo.IsInitialized; }
+
+  static bool classof(const MCFragment *F) {
+    return F->getKind() == MCFragment::FT_Padding;
+  }
+};
+
 class MCFillFragment : public MCFragment {
   /// Value to use for filling bytes.
   uint8_t Value;
 
   /// The number of bytes to insert.
   uint64_t Size;
 
 public:

include/llvm/MC/MCObjectStreamer.h

class MCObjectStreamer : public MCStreamer {
   MCSection::iterator CurInsertionPoint;
   bool EmitEHFrame;
   bool EmitDebugFrame;
   SmallVector<MCSymbol *, 2> PendingLabels;
 
   virtual void EmitInstToData(const MCInst &Inst, const MCSubtargetInfo&) = 0;
   void EmitCFIStartProcImpl(MCDwarfFrameInfo &Frame) override;
   void EmitCFIEndProcImpl(MCDwarfFrameInfo &Frame) override;
+  void EmitInstructionImpl(const MCInst &Inst, const MCSubtargetInfo &STI);
 
 protected:
   MCObjectStreamer(MCContext &Context, MCAsmBackend &TAB, raw_pwrite_stream &OS,
                    MCCodeEmitter *Emitter);
   ~MCObjectStreamer() override;
 
 public:
   /// state management
void insert(MCFragment *F) {
     MCSection *CurSection = getCurrentSectionOnly();
     CurSection->getFragmentList().insert(CurInsertionPoint, F);
     F->setParent(CurSection);
   }
 
   /// Get a data fragment to write into, creating a new one if the current
   /// fragment is not a data fragment.
   MCDataFragment *getOrCreateDataFragment();
+  MCPaddingFragment *getOrCreatePaddingFragment();
 
 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.
public:
   void EmitBytes(StringRef Data) override;
   void EmitValueToAlignment(unsigned ByteAlignment, int64_t Value = 0,
                             unsigned ValueSize = 1,
                             unsigned MaxBytesToEmit = 0) override;
   void EmitCodeAlignment(unsigned ByteAlignment,
                          unsigned MaxBytesToEmit = 0) override;
   void emitValueToOffset(const MCExpr *Offset, unsigned char Value,
                          SMLoc Loc) override;
+  void
+  EmitCodePaddingBasicBlockStart(const MCCodePaddingContext &Context) override;
+  void
+  EmitCodePaddingBasicBlockEnd(const MCCodePaddingContext &Context) override;
   void EmitDwarfLocDirective(unsigned FileNo, unsigned Line,
                              unsigned Column, unsigned Flags,
                              unsigned Isa, unsigned Discriminator,
                              StringRef FileName) override;
   void EmitDwarfAdvanceLineAddr(int64_t LineDelta, const MCSymbol *LastLabel,
                                 const MCSymbol *Label,
                                 unsigned PointerSize);
   void EmitDwarfAdvanceFrameAddr(const MCSymbol *LastLabel,

include/llvm/MC/MCStreamer.h

 #include <vector>
 
 namespace llvm {
 
 class AssemblerConstantPools;
 class formatted_raw_ostream;
 class MCAsmBackend;
 class MCCodeEmitter;
+struct MCCodePaddingContext;
 class MCContext;
 class MCExpr;
 class MCInst;
 class MCInstPrinter;
 class MCSection;
 class MCStreamer;
 class MCSymbolRefExpr;
 class MCSubtargetInfo;
public:
   /// This is used to implement assembler directives such as .org.
   ///
   /// \param Offset - The offset to reach. This may be an expression, but the
   /// expression must be associated with the current section.
   /// \param Value - The value to use when filling bytes.
   virtual void emitValueToOffset(const MCExpr *Offset, unsigned char Value,
                                  SMLoc Loc);
 
+  virtual void
+  EmitCodePaddingBasicBlockStart(const MCCodePaddingContext &Context) {}
+
+  virtual void
+  EmitCodePaddingBasicBlockEnd(const MCCodePaddingContext &Context) {}
+
   /// @}
 
   /// \brief Switch to a new logical file.  This is used to implement the '.file
   /// "foo.c"' assembler directive.
   virtual void EmitFileDirective(StringRef Filename);
 
   /// \brief Emit the "identifiers" directive.  This implements the
   /// '.ident "version foo"' assembler directive.

lib/CodeGen/AsmPrinter/AsmPrinter.cpp

 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Mangler.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/Value.h"
 #include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCCodePadder.h"
 #include "llvm/MC/MCContext.h"
 #include "llvm/MC/MCDirectives.h"
 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/MC/MCSection.h"
 #include "llvm/MC/MCSectionELF.h"
 #include "llvm/MC/MCSectionMachO.h"
 #include "llvm/MC/MCStreamer.h"

 }
 
 void AsmPrinter::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   MachineFunctionPass::getAnalysisUsage(AU);
   AU.addRequired<MachineModuleInfo>();
   AU.addRequired<MachineOptimizationRemarkEmitterPass>();
   AU.addRequired<GCModuleInfo>();
-  if (isVerbose())
-    AU.addRequired<MachineLoopInfo>();
 }
 
 bool AsmPrinter::doInitialization(Module &M) {
   MMI = getAnalysisIfAvailable<MachineModuleInfo>();
 
   // Initialize TargetLoweringObjectFile.
   const_cast<TargetLoweringObjectFile&>(getObjFileLowering())
     .Initialize(OutContext, TM);
void AsmPrinter::SetupMachineFunction(MachineFunction &MF) {
   bool NeedsLocalForSize = MAI->needsLocalForSize();
   if (needFuncLabelsForEHOrDebugInfo(MF, MMI) || NeedsLocalForSize) {
     CurrentFnBegin = createTempSymbol("func_begin");
     if (NeedsLocalForSize)
       CurrentFnSymForSize = CurrentFnBegin;
   }
 
   ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
-  if (isVerbose())
-    LI = &getAnalysis<MachineLoopInfo>();
 
   const TargetSubtargetInfo &STI = MF.getSubtarget();
   EnablePrintSchedInfo = PrintSchedule.getNumOccurrences()
                              ? PrintSchedule
                              : STI.supportPrintSchedInfo();
 }
 
 namespace {
static void emitBasicBlockLoopComments(const MachineBasicBlock &MBB,
   OS << "This ";
   if (Loop->empty())
     OS << "Inner ";
   OS << "Loop Header: Depth=" + Twine(Loop->getLoopDepth()) << '\n';
 
   PrintChildLoopComment(OS, Loop, AP.getFunctionNumber());
 }
 
+void AsmPrinter::setupPaddingContext(const MachineBasicBlock &MBB,
+                                     MCCodePaddingContext &Context) const {
+  assert(MF != nullptr && "Machine function must be valid");
+  assert(LI != nullptr && "Loop info must be valid");
+  Context.IsPaddingActive = !MF->hasInlineAsm() &&
+                            !MF->getFunction()->optForSize() &&
+                            TM.getOptLevel() != CodeGenOpt::None;
+  const MachineLoop *CurrentLoop = LI->getLoopFor(&MBB);
+  Context.IsBasicBlockInsideInnermostLoop =
+      CurrentLoop != nullptr && CurrentLoop->getSubLoops().empty();
+  Context.IsBasicBlockReachableViaFallthrough =
+      std::find(MBB.pred_begin(), MBB.pred_end(), MBB.getPrevNode()) !=
+      MBB.pred_end();
+}
+
 /// EmitBasicBlockStart - This method prints the label for the specified
 /// MachineBasicBlock, an alignment (if present) and a comment describing
 /// it if appropriate.
 void AsmPrinter::EmitBasicBlockStart(const MachineBasicBlock &MBB) const {
   // End the previous funclet and start a new one.
   if (MBB.isEHFuncletEntry()) {
     for (const HandlerInfo &HI : Handlers) {
       HI.Handler->endFunclet();
       HI.Handler->beginFunclet(MBB);
     }
   }
 
   // Emit an alignment directive for this block, if needed.
   if (unsigned Align = MBB.getAlignment())
     EmitAlignment(Align);
+  MCCodePaddingContext Context;
+  setupPaddingContext(MBB, Context);
+  OutStreamer->EmitCodePaddingBasicBlockStart(Context);
 
   // If the block has its address taken, emit any labels that were used to
   // reference the block.  It is possible that there is more than one label
   // here, because multiple LLVM BB's may have been RAUW'd to this block after
   // the references were generated.
   if (MBB.hasAddressTaken()) {
     const BasicBlock *BB = MBB.getBasicBlock();
     if (isVerbose())
if (isVerbose()) {
       // NOTE: Want this comment at start of line, don't emit with AddComment.
       OutStreamer->emitRawComment(" BB#" + Twine(MBB.getNumber()) + ":", false);
     }
   } else {
     OutStreamer->EmitLabel(MBB.getSymbol());
   }
 }
 
+void AsmPrinter::EmitBasicBlockEnd(const MachineBasicBlock &MBB) {
+  MCCodePaddingContext Context;
+  setupPaddingContext(MBB, Context);
+  OutStreamer->EmitCodePaddingBasicBlockEnd(Context);
+}
+
 void AsmPrinter::EmitVisibility(MCSymbol *Sym, unsigned Visibility,
                                 bool IsDefinition) const {
   MCSymbolAttr Attr = MCSA_Invalid;
 
   switch (Visibility) {
   default: break;
   case GlobalValue::HiddenVisibility:
     if (IsDefinition)

lib/MC/CMakeLists.txt

 add_llvm_library(LLVMMC
   ConstantPools.cpp
   ELFObjectWriter.cpp
   MCAsmBackend.cpp
   MCAsmInfo.cpp
   MCAsmInfoCOFF.cpp
   MCAsmInfoDarwin.cpp
   MCAsmInfoELF.cpp
   MCAsmInfoWasm.cpp
   MCAsmStreamer.cpp
   MCAssembler.cpp
   MCCodeEmitter.cpp
+  MCCodePadder.cpp
   MCCodeView.cpp
   MCContext.cpp
   MCDwarf.cpp
   MCELFObjectTargetWriter.cpp
   MCELFStreamer.cpp
   MCExpr.cpp
   MCFragment.cpp
   MCInst.cpp

lib/MC/MCAsmBackend.cpp

 //===- MCAsmBackend.cpp - Target MC Assembly Backend ----------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/MC/MCAsmBackend.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/MC/MCCodePadder.h"
 #include "llvm/MC/MCFixupKindInfo.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 
 using namespace llvm;
 
-MCAsmBackend::MCAsmBackend() = default;
+MCAsmBackend::MCAsmBackend(MCCodePadder *TargetCodePadder)
+    : CodePadder(TargetCodePadder != nullptr ? TargetCodePadder
+                                             : new MCCodePadder()) {}
 
 MCAsmBackend::~MCAsmBackend() = default;
 
 Optional<MCFixupKind> MCAsmBackend::getFixupKind(StringRef Name) const {
   return None;
 }
 
 const MCFixupKindInfo &MCAsmBackend::getFixupKindInfo(MCFixupKind Kind) const {
   static const MCFixupKindInfo Builtins[] = {
       {"FK_Data_1", 0, 8, 0},
       {"FK_Data_2", 0, 16, 0},
       {"FK_Data_4", 0, 32, 0},
       {"FK_Data_8", 0, 64, 0},
       {"FK_PCRel_1", 0, 8, MCFixupKindInfo::FKF_IsPCRel},
       {"FK_PCRel_2", 0, 16, MCFixupKindInfo::FKF_IsPCRel},
       {"FK_PCRel_4", 0, 32, MCFixupKindInfo::FKF_IsPCRel},

 
 bool MCAsmBackend::fixupNeedsRelaxationAdvanced(
     const MCFixup &Fixup, bool Resolved, uint64_t Value,
     const MCRelaxableFragment *DF, const MCAsmLayout &Layout) const {
   if (!Resolved)
     return true;
   return fixupNeedsRelaxation(Fixup, Value, DF, Layout);
 }
+
+void MCAsmBackend::handleCodePaddingBasicBlockStart(
+    MCObjectStreamer *OS, const MCCodePaddingContext &Context) {
+  CodePadder->handleBasicBlockStart(OS, Context);
+}
+
+void MCAsmBackend::handleCodePaddingBasicBlockEnd(
+    const MCCodePaddingContext &Context) {
+  CodePadder->handleBasicBlockEnd(Context);
+}
+
+void MCAsmBackend::handleCodePaddingInstructionBegin(const MCInst &Inst) {
+  CodePadder->handleInstructionBegin(Inst);
+}
+
+void MCAsmBackend::handleCodePaddingInstructionEnd(const MCInst &Inst) {
+  CodePadder->handleInstructionEnd(Inst);
+}
+
+bool MCAsmBackend::relaxFragment(MCPaddingFragment *PF, MCAsmLayout &Layout) {
+  return CodePadder->relaxFragment(PF, Layout);
+}
 No newline at end of file

lib/MC/MCAssembler.cpp

STATISTIC(EmittedFillFragments,
           "Number of emitted assembler fragments - fill");
 STATISTIC(EmittedOrgFragments,
           "Number of emitted assembler fragments - org");
 STATISTIC(evaluateFixup, "Number of evaluated fixups");
 STATISTIC(FragmentLayouts, "Number of fragment layouts");
 STATISTIC(ObjectBytes, "Number of emitted object file bytes");
 STATISTIC(RelaxationSteps, "Number of assembler layout and relaxation steps");
 STATISTIC(RelaxedInstructions, "Number of relaxed instructions");
+STATISTIC(PaddingFragmentsRelaxations,
+          "Number of Padding Fragments relaxations");
+STATISTIC(PaddingFragmentsBytes,
+          "Total size of all padding from adding Fragments");
 
 } // end namespace stats
 } // end anonymous namespace
 
 // FIXME FIXME FIXME: There are number of places in this file where we convert
 // what is a 64-bit assembler value used for computation into a value in the
 // object file, which may truncate it. We should detect that truncation where
 // invalid and report errors back.
uint64_t MCAssembler::computeFragmentSize(const MCAsmLayout &Layout,
   case MCFragment::FT_CompactEncodedInst:
     return cast<MCCompactEncodedInstFragment>(F).getContents().size();
   case MCFragment::FT_Fill:
     return cast<MCFillFragment>(F).getSize();
 
   case MCFragment::FT_LEB:
     return cast<MCLEBFragment>(F).getContents().size();
 
+  case MCFragment::FT_Padding:
+    return cast<MCPaddingFragment>(F).getSize();
+
   case MCFragment::FT_SafeSEH:
     return 4;
 
   case MCFragment::FT_Align: {
     const MCAlignFragment &AF = cast<MCAlignFragment>(F);
     unsigned Offset = Layout.getFragmentOffset(&AF);
     unsigned Size = OffsetToAlignment(Offset, AF.getAlignment());
     // If we are padding with nops, force the padding to be larger than the
static void writeFragment(const MCAssembler &Asm, const MCAsmLayout &Layout,
   }
 
   case MCFragment::FT_LEB: {
     const MCLEBFragment &LF = cast<MCLEBFragment>(F);
     OW->writeBytes(LF.getContents());
     break;
   }
 
+  case MCFragment::FT_Padding: {
+    if (!Asm.getBackend().writeNopData(FragmentSize, OW))
+      report_fatal_error("unable to write nop sequence of " +
+                         Twine(FragmentSize) + " bytes");
+    break;
+  }
+
   case MCFragment::FT_SafeSEH: {
     const MCSafeSEHFragment &SF = cast<MCSafeSEHFragment>(F);
     OW->write32(SF.getSymbol()->getIndex());
     break;
   }
 
   case MCFragment::FT_Org: {
     ++stats::EmittedOrgFragments;
bool MCAssembler::relaxInstruction(MCAsmLayout &Layout,
   // Update the fragment.
   F.setInst(Relaxed);
   F.getContents() = Code;
   F.getFixups() = Fixups;
 
   return true;
 }
 
+bool MCAssembler::relaxPaddingFragment(MCAsmLayout &Layout,
+                                       MCPaddingFragment &PF) {
+  uint64_t OldSize = PF.getSize();
+  if (!getBackend().relaxFragment(&PF, Layout))
+    return false;
+  uint64_t NewSize = PF.getSize();
+
+  ++stats::PaddingFragmentsRelaxations;
+  stats::PaddingFragmentsBytes += NewSize;
+  stats::PaddingFragmentsBytes -= OldSize;
+  return true;
+}
+
 bool MCAssembler::relaxLEB(MCAsmLayout &Layout, MCLEBFragment &LF) {
   uint64_t OldSize = LF.getContents().size();
   int64_t Value;
   bool Abs = LF.getValue().evaluateKnownAbsolute(Value, Layout);
   if (!Abs)
     report_fatal_error("sleb128 and uleb128 expressions must be absolute");
   SmallString<8> &Data = LF.getContents();
   Data.clear();
for (MCSection::iterator I = Sec.begin(), IE = Sec.end(); I != IE; ++I) {
     case MCFragment::FT_DwarfFrame:
       RelaxedFrag =
         relaxDwarfCallFrameFragment(Layout,
                                     *cast<MCDwarfCallFrameFragment>(I));
       break;
     case MCFragment::FT_LEB:
       RelaxedFrag = relaxLEB(Layout, *cast<MCLEBFragment>(I));
       break;
+
+    case MCFragment::FT_Padding:
+      RelaxedFrag = relaxPaddingFragment(Layout, *cast<MCPaddingFragment>(I));
+      break;
+
     case MCFragment::FT_CVInlineLines:
       RelaxedFrag =
           relaxCVInlineLineTable(Layout, *cast<MCCVInlineLineTableFragment>(I));
       break;
     case MCFragment::FT_CVDefRange:
       RelaxedFrag = relaxCVDefRange(Layout, *cast<MCCVDefRangeFragment>(I));
       break;
     }

lib/MC/MCCodePadder.cpp

+//===- MCCodePadder.cpp - Target MC Code Padder ---------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/MC/MCAsmLayout.h"
+#include "llvm/MC/MCCodePadder.h"
+#include "llvm/MC/MCObjectStreamer.h"
+#include <algorithm>
+#include <limits>
+#include <numeric>
+
+using namespace llvm;
+
+//---------------------------------------------------------------------------
+// MCCodePadder
+//
+
+MCCodePadder::~MCCodePadder() {
+  for (auto *Policy : PaddingPolicies)
+    delete Policy;
+}
+
+bool MCCodePadder::addPolicy(MCCodePaddingPolicy *Policy) {
+  assert(Policy && "Policy must be valid");
+  return PaddingPolicies.insert(Policy).second;
+}
+
+void MCCodePadder::handleBasicBlockStart(MCObjectStreamer *OS,
+                                         const MCCodePaddingContext &Context) {
+  assert(OS != nullptr && "OS must be valid");
+  assert(this->OS == nullptr && "Still handling another basic block");
+  this->OS = OS;
+
+  ArePoliciesActive = usePoliciesForBasicBlock(Context);
+
+  bool InsertionPoint = basicBlockRequiresInsertionPoint(Context);
+  assert((!InsertionPoint ||
+          OS->getCurrentFragment()->getKind() != MCFragment::FT_Align) &&
+         "Cannot insert padding nops right after an alignment fragment as it "
+         "will ruin the alignment");
+
+  uint64_t PoliciesMask = MCPaddingFragment::PFK_None;
+  if (ArePoliciesActive) {
+    PoliciesMask = std::accumulate(
+        PaddingPolicies.begin(), PaddingPolicies.end(),
+        MCPaddingFragment::PFK_None,
+        [&Context](uint64_t Mask,
+                   const MCCodePaddingPolicy *Policy) -> uint64_t {
+          return Policy->basicBlockRequiresPaddingFragment(Context)
+                     ? (Mask | Policy->getKindMask())
+                     : Mask;
+        });
+  }
+
+  if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None) {
+    MCPaddingFragment *PaddingFragment = OS->getOrCreatePaddingFragment();
+    if (InsertionPoint)
+      PaddingFragment->setAsInsertionPoint();
+    PaddingFragment->setPaddingPoliciesMask(
+        PaddingFragment->getPaddingPoliciesMask() | PoliciesMask);
+  }
+}
+
+void MCCodePadder::handleBasicBlockEnd(const MCCodePaddingContext &Context) {
+  assert(this->OS != nullptr && "Not handling a basic block");
+  OS = nullptr;
+}
+
+void MCCodePadder::handleInstructionBegin(const MCInst &Inst) {
+  if (!OS)
+    return; // instruction was emitted outside a function
+
+  assert(CurrHandledInstFragment == nullptr && "Can't start handling an "
+                                               "instruction while still "
+                                               "handling another instruction");
+
+  bool InsertionPoint = instructionRequiresInsertionPoint(Inst);
+  assert((!InsertionPoint ||
+          OS->getCurrentFragment()->getKind() != MCFragment::FT_Align) &&
+         "Cannot insert padding nops right after an alignment fragment as it "
+         "will ruin the alignment");
+
+  uint64_t PoliciesMask = MCPaddingFragment::PFK_None;
+  if (ArePoliciesActive) {
+    PoliciesMask = std::accumulate(
+        PaddingPolicies.begin(), PaddingPolicies.end(),
+        MCPaddingFragment::PFK_None,
+        [&Inst](uint64_t Mask,
+                          const MCCodePaddingPolicy *Policy) -> uint64_t {
+          return Policy->instructionRequiresPaddingFragment(Inst)
+                     ? (Mask | Policy->getKindMask())
+                     : Mask;
+        });
+  }
+  MCFragment *CurrFragment = OS->getCurrentFragment();
+  // CurrFragment can be a previously created MCPaddingFragment. If so, let's
+  // update it with the information we have, such as the instruction that it
+  // should point to.
+  bool needToUpdateCurrFragment =
+      CurrFragment != nullptr &&
+      CurrFragment->getKind() == MCFragment::FT_Padding;
+  if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None ||
+      needToUpdateCurrFragment) {
+    // temporarily holding the fragment as CurrHandledInstFragment, to be
+    // updated after the instruction will be written
+    CurrHandledInstFragment = OS->getOrCreatePaddingFragment();
+    if (InsertionPoint)
+      CurrHandledInstFragment->setAsInsertionPoint();
+    CurrHandledInstFragment->setPaddingPoliciesMask(
+        CurrHandledInstFragment->getPaddingPoliciesMask() | PoliciesMask);
+  }
+}
+
+void MCCodePadder::handleInstructionEnd(const MCInst &Inst) {
+  if (!OS)
+    return; // instruction was emitted outside a function
+  if (CurrHandledInstFragment == nullptr)
+    return;
+
+  MCFragment *InstFragment = OS->getCurrentFragment();
+  if (MCDataFragment *InstDataFragment =
+          dyn_cast_or_null<MCDataFragment>(InstFragment))
+    // Inst is a fixed size instruction and was encoded into a MCDataFragment.
+    // Let the fragment hold it and its size. Its size is the current size of
+    // the data fragment, as the padding fragment was inserted right before it
+    // and nothing was written yet except Inst
+    CurrHandledInstFragment->setInstAndInstSize(
+        Inst, InstDataFragment->getContents().size());
+  else if (MCRelaxableFragment *InstRelaxableFragment =
+               dyn_cast_or_null<MCRelaxableFragment>(InstFragment))
+    // Inst may be relaxed and its size may vary.
+    // Let the fragment hold the instruction and the MCRelaxableFragment
+    // that's holding it.
+    CurrHandledInstFragment->setInstAndInstFragment(Inst,
+                                                    InstRelaxableFragment);
+  else
+    llvm_unreachable("After encoding an instruction current fragment must be "
+                     "either a MCDataFragment or a MCRelaxableFragment");
+
+  CurrHandledInstFragment = nullptr;
+}
+
+MCPFRange &MCCodePadder::getJurisdiction(MCPaddingFragment *Fragment,
+                                         MCAsmLayout &Layout) {
+  auto JurisdictionLocation = FragmentToJurisdiction.find(Fragment);
+  if (JurisdictionLocation != FragmentToJurisdiction.end())
+    return JurisdictionLocation->second;
+
+  MCPFRange Jurisdiction;
+
+  // Forward scanning the fragments in this section, starting from the given
+  // fragments, and adding relevant MCPaddingFragments to the Jurisdiction
+  for (MCFragment *CurrFragment = Fragment; CurrFragment != nullptr;
+       CurrFragment = CurrFragment->getNextNode()) {
+
+    MCPaddingFragment *CurrPaddingFragment =
+        dyn_cast<MCPaddingFragment>(CurrFragment);
+    if (CurrPaddingFragment == nullptr)
+      continue;
+
+    if (CurrPaddingFragment != Fragment &&
+        CurrPaddingFragment->isInsertionPoint())
+      // Found next insertion point Fragment. From now on it's its jurisdiction.
+      break;
+    for (const auto *Policy : PaddingPolicies) {
+      if (CurrPaddingFragment->hasPaddingPolicy(Policy->getKindMask())) {
+        Jurisdiction.push_back(CurrPaddingFragment);
+        break;
+      }
+    }
+  }
+
+  auto InsertionResult =
+      FragmentToJurisdiction.insert(std::make_pair(Fragment, Jurisdiction));
+  assert(InsertionResult.second &&
+         "Insertion to FragmentToJurisdiction failed");
+  return InsertionResult.first->second;
+}
+
+uint64_t MCCodePadder::getMaxWindowSize(MCPaddingFragment *Fragment,
+                                        MCAsmLayout &Layout) {
+  auto MaxFragmentSizeLocation = FragmentToMaxWindowSize.find(Fragment);
+  if (MaxFragmentSizeLocation != FragmentToMaxWindowSize.end())
+    return MaxFragmentSizeLocation->second;
+
+  MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout);
+  uint64_t JurisdictionMask = MCPaddingFragment::PFK_None;
+  for (const auto *Protege : Jurisdiction)
+    JurisdictionMask |= Protege->getPaddingPoliciesMask();
+
+  uint64_t MaxFragmentSize = UINT64_C(0);
+  for (const auto *Policy : PaddingPolicies)
+    if ((JurisdictionMask & Policy->getKindMask()) !=
+        MCPaddingFragment::PFK_None)
+      MaxFragmentSize = std::max(MaxFragmentSize, Policy->getWindowSize());
+
+  auto InsertionResult =
+      FragmentToMaxWindowSize.insert(std::make_pair(Fragment, MaxFragmentSize));
+  assert(InsertionResult.second &&
+         "Insertion to FragmentToMaxWindowSize failed");
+  return InsertionResult.first->second;
+}
+
+bool MCCodePadder::relaxFragment(MCPaddingFragment *Fragment,
+                                 MCAsmLayout &Layout) {
+  if (!Fragment->isInsertionPoint())
+    return false;
+  uint64_t OldSize = Fragment->getSize();
+
+  uint64_t MaxWindowSize = getMaxWindowSize(Fragment, Layout);
+  if (MaxWindowSize == UINT64_C(0))
+    return false;
+  assert(isPowerOf2_64(MaxWindowSize) &&
+         "MaxWindowSize must be an integer power of 2");
+  uint64_t SectionAlignment = Fragment->getParent()->getAlignment();
+  assert(isPowerOf2_64(SectionAlignment) &&
+         "SectionAlignment must be an integer power of 2");
+
+  MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout);
+  uint64_t OptimalSize = UINT64_C(0);
+  double OptimalWeight = std::numeric_limits<double>::max();
+  uint64_t MaxFragmentSize = MaxWindowSize - UINT16_C(1);
+  for (uint64_t Size = UINT64_C(0); Size <= MaxFragmentSize; ++Size) {
+    Fragment->setSize(Size);
+    Layout.invalidateFragmentsFrom(Fragment);
+    double SizeWeight = 0.0;
+    // The section is guaranteed to be aligned to SectionAlignment, but that
+    // doesn't guarantee the exact section offset w.r.t. the policies window
+    // size.
+    // As a concrete example, the section could be aligned to 16B, but a
+    // policy's window size can be 32B. That means that the section actual start
+    // address can either be 0mod32 or 16mod32. The said policy will act
+    // differently for each case, so we need to take both into consideration.
+    for (uint64_t Offset = UINT64_C(0); Offset < MaxWindowSize;
+         Offset += SectionAlignment) {
+      double OffsetWeight = std::accumulate(
+          PaddingPolicies.begin(), PaddingPolicies.end(), 0.0,
+          [&Jurisdiction, &Offset, &Layout](
+              double Weight, const MCCodePaddingPolicy *Policy) -> double {
+            double PolicyWeight =
+                Policy->computeRangePenaltyWeight(Jurisdiction, Offset, Layout);
+            assert(PolicyWeight >= 0.0 && "A penalty weight must be positive");
+            return Weight + PolicyWeight;
+          });
+      SizeWeight = std::max(SizeWeight, OffsetWeight);
+    }
+    if (SizeWeight < OptimalWeight) {
+      OptimalWeight = SizeWeight;
+      OptimalSize = Size;
+    }
+    if (OptimalWeight == 0.0)
+      break;
+  }
+
+  Fragment->setSize(OptimalSize);
+  Layout.invalidateFragmentsFrom(Fragment);
+  return OldSize != OptimalSize;
+}
+
+//---------------------------------------------------------------------------
+// MCCodePaddingPolicy
+//
+
+uint64_t MCCodePaddingPolicy::getNextFragmentOffset(const MCFragment *Fragment,
+                                                    const MCAsmLayout &Layout) {
+  assert(Fragment != nullptr && "Fragment cannot be null");
+  MCFragment const *NextFragment = Fragment->getNextNode();
+  return NextFragment == nullptr
+             ? Layout.getSectionAddressSize(Fragment->getParent())
+             : Layout.getFragmentOffset(NextFragment);
+}
+
+uint64_t
+MCCodePaddingPolicy::getFragmentInstByte(const MCPaddingFragment *Fragment,
+                                         MCAsmLayout &Layout) const {
+  uint64_t InstByte = getNextFragmentOffset(Fragment, Layout);
+  if (InstByteIsLastByte)
+    InstByte += Fragment->getInstSize() - UINT64_C(1);
+  return InstByte;
+}
+
+uint64_t
+MCCodePaddingPolicy::computeWindowEndAddress(const MCPaddingFragment *Fragment,
+                                             uint64_t Offset,
+                                             MCAsmLayout &Layout) const {
+  uint64_t InstByte = getFragmentInstByte(Fragment, Layout);
+  return alignTo(InstByte + UINT64_C(1) + Offset, WindowSize) - Offset;
+}
+
+double MCCodePaddingPolicy::computeRangePenaltyWeight(
+    const MCPFRange &Range, uint64_t Offset, MCAsmLayout &Layout) const {
+
+  SmallVector<MCPFRange, 8> Windows;
+  SmallVector<MCPFRange, 8>::iterator CurrWindowLocation = Windows.end();
+  for (const MCPaddingFragment *Fragment : Range) {
+    if (!Fragment->hasPaddingPolicy(getKindMask()))
+      continue;
+    uint64_t FragmentWindowEndAddress =
+        computeWindowEndAddress(Fragment, Offset, Layout);
+    if (CurrWindowLocation == Windows.end() ||
+        FragmentWindowEndAddress !=
+            computeWindowEndAddress(*CurrWindowLocation->begin(), Offset,
+                                    Layout)) {
+      // next window is starting
+      Windows.push_back(MCPFRange());
+      CurrWindowLocation = Windows.end() - 1;
+    }
+    CurrWindowLocation->push_back(Fragment);
+  }
+
+  if (Windows.empty())
+    return 0.0;
+
+  double RangeWeight = 0.0;
+  SmallVector<MCPFRange, 8>::iterator I = Windows.begin();
+  RangeWeight += computeFirstWindowPenaltyWeight(*I, Offset, Layout);
+  ++I;
+  RangeWeight += std::accumulate(
+      I, Windows.end(), 0.0,
+      [this, &Layout, &Offset](double Weight, MCPFRange &Window) -> double {
+        return Weight += computeWindowPenaltyWeight(Window, Offset, Layout);
+      });
+  return RangeWeight;
+}
+
+double MCCodePaddingPolicy::computeFirstWindowPenaltyWeight(
+    const MCPFRange &Window, uint64_t Offset, MCAsmLayout &Layout) const {
+  if (Window.empty())
+    return 0.0;
+  uint64_t WindowEndAddress =
+      computeWindowEndAddress(*Window.begin(), Offset, Layout);
+
+  MCPFRange FullWindowFirstPart; // will hold all the fragments that are in the
+                 // same window as the fragments in the given
+                 // window but their penalty weight should not
+                 // be added
+  for (const MCFragment *Fragment = (*Window.begin())->getPrevNode();
+       Fragment != nullptr; Fragment = Fragment->getPrevNode()) {
+    const MCPaddingFragment *PaddingNopFragment =
+        dyn_cast<MCPaddingFragment>(Fragment);
+    if (PaddingNopFragment == nullptr ||
+        !PaddingNopFragment->hasPaddingPolicy(getKindMask()))
+      continue;
+    if (WindowEndAddress !=
+        computeWindowEndAddress(PaddingNopFragment, Offset, Layout))
+      break;
+
+    FullWindowFirstPart.push_back(PaddingNopFragment);
+  }
+
+  std::reverse(FullWindowFirstPart.begin(), FullWindowFirstPart.end());
+  double FullWindowFirstPartWeight =
+      computeWindowPenaltyWeight(FullWindowFirstPart, Offset, Layout);
+
+  MCPFRange FullWindow(
+      FullWindowFirstPart); // will hold all the fragments that are in the
+                            // same window as the fragments in the given
+                            // window, whether their weight should be added
+                            // or not
+  FullWindow.append(Window.begin(), Window.end());
+  double FullWindowWeight =
+      computeWindowPenaltyWeight(FullWindow, Offset, Layout);
+
+  assert(FullWindowWeight >= FullWindowFirstPartWeight &&
+         "More fragments necessarily means bigger weight");
+  return FullWindowWeight - FullWindowFirstPartWeight;
+}

lib/MC/MCFragment.cpp

case FT_Dwarf:
       delete cast<MCDwarfLineAddrFragment>(this);
       return;
     case FT_DwarfFrame:
       delete cast<MCDwarfCallFrameFragment>(this);
       return;
     case FT_LEB:
       delete cast<MCLEBFragment>(this);
       return;
+    case FT_Padding:
+      delete cast<MCPaddingFragment>(this);
+      return;
     case FT_SafeSEH:
       delete cast<MCSafeSEHFragment>(this);
       return;
     case FT_CVInlineLines:
       delete cast<MCCVInlineLineTableFragment>(this);
       return;
     case FT_CVDefRange:
       delete cast<MCCVDefRangeFragment>(this);
LLVM_DUMP_METHOD void MCFragment::dump() {
   case MCFragment::FT_CompactEncodedInst:
     OS << "MCCompactEncodedInstFragment"; break;
   case MCFragment::FT_Fill:  OS << "MCFillFragment"; break;
   case MCFragment::FT_Relaxable:  OS << "MCRelaxableFragment"; break;
   case MCFragment::FT_Org:   OS << "MCOrgFragment"; break;
   case MCFragment::FT_Dwarf: OS << "MCDwarfFragment"; break;
   case MCFragment::FT_DwarfFrame: OS << "MCDwarfCallFrameFragment"; break;
   case MCFragment::FT_LEB:   OS << "MCLEBFragment"; break;
+  case MCFragment::FT_Padding: OS << "MCPaddingFragment"; break;
   case MCFragment::FT_SafeSEH:    OS << "MCSafeSEHFragment"; break;
   case MCFragment::FT_CVInlineLines: OS << "MCCVInlineLineTableFragment"; break;
   case MCFragment::FT_CVDefRange: OS << "MCCVDefRangeTableFragment"; break;
   case MCFragment::FT_Dummy: OS << "MCDummyFragment"; break;
   }
 
   OS << "<MCFragment " << (void*) this << " LayoutOrder:" << LayoutOrder
      << " Offset:" << Offset
case MCFragment::FT_DwarfFrame:  {
     break;
   }
   case MCFragment::FT_LEB: {
     const MCLEBFragment *LF = cast<MCLEBFragment>(this);
     OS << "\n       ";
     OS << " Value:" << LF->getValue() << " Signed:" << LF->isSigned();
     break;
   }
+  case MCFragment::FT_Padding: {
+    const MCPaddingFragment *F = cast<MCPaddingFragment>(this);
+    OS << "\n       ";
+    OS << " PaddingPoliciesMask:" << F->getPaddingPoliciesMask()
+       << " IsInsertionPoint:" << F->isInsertionPoint()
+       << " Size:" << F->getSize();
+    OS << "\n       ";
+    OS << " Inst:";
+    F->getInst().dump_pretty(OS);
+    OS << " InstSize:" << F->getInstSize();
+    OS << "\n       ";
+    break;
+  }
   case MCFragment::FT_SafeSEH: {
     const MCSafeSEHFragment *F = cast<MCSafeSEHFragment>(this);
     OS << "\n       ";
     OS << " Sym:" << F->getSymbol();
     break;
   }
   case MCFragment::FT_CVInlineLines: {
     const auto *F = cast<MCCVInlineLineTableFragment>(this);

lib/MC/MCObjectStreamer.cpp

MCDataFragment *MCObjectStreamer::getOrCreateDataFragment() {
   if (!F || (Assembler->isBundlingEnabled() && !Assembler->getRelaxAll() &&
              F->hasInstructions())) {
     F = new MCDataFragment();
     insert(F);
   }
   return F;
 }
 
+MCPaddingFragment *MCObjectStreamer::getOrCreatePaddingFragment() {
+  MCPaddingFragment *F =
+      dyn_cast_or_null<MCPaddingFragment>(getCurrentFragment());
+  if (!F) {
+    F = new MCPaddingFragment();
+    insert(F);
+  }
+  return F;
+}
+
 void MCObjectStreamer::visitUsedSymbol(const MCSymbol &Sym) {
   Assembler->registerSymbol(Sym);
 }
 
 void MCObjectStreamer::EmitCFISections(bool EH, bool Debug) {
   MCStreamer::EmitCFISections(EH, Debug);
   EmitEHFrame = EH;
   EmitDebugFrame = Debug;

 }
 
 bool MCObjectStreamer::mayHaveInstructions(MCSection &Sec) const {
   return Sec.hasInstructions();
 }
 
 void MCObjectStreamer::EmitInstruction(const MCInst &Inst,
                                        const MCSubtargetInfo &STI, bool) {
+  getAssembler().getBackend().handleCodePaddingInstructionBegin(Inst);
+  EmitInstructionImpl(Inst, STI);
+  getAssembler().getBackend().handleCodePaddingInstructionEnd(Inst);
+}
+
+void MCObjectStreamer::EmitInstructionImpl(const MCInst &Inst,
+                                           const MCSubtargetInfo &STI) {
   MCStreamer::EmitInstruction(Inst, STI);
 
   MCSection *Sec = getCurrentSectionOnly();
   Sec->setHasInstructions(true);
 
   // Now that a machine instruction has been assembled into this section, make
   // a line entry for any .loc directive that has been seen.
   MCCVLineEntry::Make(this);

 }
 
 void MCObjectStreamer::emitValueToOffset(const MCExpr *Offset,
                                          unsigned char Value,
                                          SMLoc Loc) {
   insert(new MCOrgFragment(*Offset, Value, Loc));
 }
 
+void MCObjectStreamer::EmitCodePaddingBasicBlockStart(
+    const MCCodePaddingContext &Context) {
+  getAssembler().getBackend().handleCodePaddingBasicBlockStart(this, Context);
+}
+
+void MCObjectStreamer::EmitCodePaddingBasicBlockEnd(
+    const MCCodePaddingContext &Context) {
+  getAssembler().getBackend().handleCodePaddingBasicBlockEnd(Context);
+}
+
 // Associate DTPRel32 fixup with data and resize data area
 void MCObjectStreamer::EmitDTPRel32Value(const MCExpr *Value) {
   MCDataFragment *DF = getOrCreateDataFragment();
   flushPendingLabels(DF, DF->getContents().size());
 
   DF->getFixups().push_back(MCFixup::create(DF->getContents().size(),
                                             Value, FK_DTPRel_4));
   DF->getContents().resize(DF->getContents().size() + 4, 0);

lib/Target/Mips/MipsAsmPrinter.cpp

void MipsAsmPrinter::EmitFunctionBodyEnd() {
   // of the function.
   if (!InConstantPool)
     return;
   InConstantPool = false;
   OutStreamer->EmitDataRegion(MCDR_DataRegionEnd);
 }
 
 void MipsAsmPrinter::EmitBasicBlockEnd(const MachineBasicBlock &MBB) {
+  AsmPrinter::EmitBasicBlockEnd(MBB);
   MipsTargetStreamer &TS = getTargetStreamer();
   if (MBB.size() == 0)
     TS.emitDirectiveInsn();
 }
 
 /// isBlockOnlyReachableByFallthough - Return true if the basic block has
 /// exactly one predecessor and the control transfer mechanism between
 /// the predecessor and this block is a fall-through.

lib/Target/X86/X86AsmPrinter.h

public:
 
   void EmitStartOfAsmFile(Module &M) override;
 
   void EmitEndOfAsmFile(Module &M) override;
 
   void EmitInstruction(const MachineInstr *MI) override;
 
   void EmitBasicBlockEnd(const MachineBasicBlock &MBB) override {
+    AsmPrinter::EmitBasicBlockEnd(MBB);
     SMShadowTracker.emitShadowPadding(*OutStreamer, getSubtargetInfo());
   }
 
   bool PrintAsmOperand(const MachineInstr *MI, unsigned OpNo,
                        unsigned AsmVariant, const char *ExtraCode,
                        raw_ostream &OS) override;
   bool PrintAsmMemoryOperand(const MachineInstr *MI, unsigned OpNo,
                              unsigned AsmVariant, const char *ExtraCode,

test/CodeGen/AArch64/arm64-opt-remarks-lazy-bfi.ll

 ; HOTNESS-NEXT: Executing Pass 'Lazy Machine Block Frequency Analysis'
 ; HOTNESS-NEXT: Executing Pass 'Machine Optimization Remark Emitter'
 ; HOTNESS-NEXT: Building MachineBlockFrequencyInfo on the fly
 ; HOTNESS-NEXT: Building LoopInfo on the fly
 ; HOTNESS-NEXT: Building DominatorTree on the fly
 ; HOTNESS-NOT: Executing Pass
 ; HOTNESS: block-frequency: empty_func
 ; HOTNESS-NOT: Executing Pass
-; HOTNESS: Executing Pass 'AArch64 Assembly Printer'
+; HOTNESS: Executing Pass 'MachineDominator Tree Construction'
+; HOTNESS-NEXT: Executing Pass 'Machine Natural Loop Construction'
+; HOTNESS-NEXT: Executing Pass 'AArch64 Assembly Printer'
 
 ; HOTNESS: arm64-summary-remarks.ll:5:0: 1 instructions in function (hotness: 33)
 
 
 ; NO_HOTNESS:      Executing Pass 'Implement the 'patchable-function' attribute'
 ; NO_HOTNESS-NEXT:  Freeing Pass 'Implement the 'patchable-function' attribute'
 ; NO_HOTNESS-NEXT: Executing Pass 'Lazy Machine Block Frequency Analysis'
 ; NO_HOTNESS-NEXT: Executing Pass 'Machine Optimization Remark Emitter'
+; NO_HOTNESS-NEXT: Executing Pass 'MachineDominator Tree Construction'
+; NO_HOTNESS-NEXT: Executing Pass 'Machine Natural Loop Construction'
 ; NO_HOTNESS-NEXT: Executing Pass 'AArch64 Assembly Printer'
 
 ; NO_HOTNESS: arm64-summary-remarks.ll:5:0: 1 instructions in function{{$}}
 
 define void @empty_func() nounwind ssp !dbg !3 !prof !4 {
   ret void
 }
 
 !llvm.dbg.cu = !{!0}
 !llvm.module.flags = !{!2}
 
 !0 = distinct !DICompileUnit(language: DW_LANG_C, file: !1)
 !1 = !DIFile(filename: "arm64-summary-remarks.ll", directory: "")
 !2 = !{i32 2, !"Debug Info Version", i32 3}
 !3 = distinct !DISubprogram(name: "empty_func", scope: !1, file: !1, line: 5, scopeLine: 5, unit: !0)
 !4 = !{!"function_entry_count", i64 33}