[X86] Relax existing instructions to reduce the number of nops needed for alignment purposes

[reames]

Summary

If we have an explicit align directive, we currently default to emitting nops to fill the space. As discussed in the context of the prefix padding work for branch alignment (D72225), we're allowed to play other tricks such as extending the size of previous instructions instead.

This patch will convert near jumps to far jumps if doing so decreases the number of bytes of nops needed for a following align. It does so as a post-pass after relaxation is complete. It intentionally works without moving any labels or doing anything which might require another round of relaxation.

The point of this patch is mainly to mock out the approach. The optimization implemented is real, and possibly useful, but the main point is to demonstrate an approach for implementing such "pad previous instruction" approaches. The key notion in this patch is to treat padding previous instructions as an optional optimization, not as a core part of relaxation. The benefit to this is that we avoid the potential concern about increasing the distance between two labels and thus causing further potentially non-local code grown due to relaxation. The downside is that we may miss some opportunities to avoid nops.

For the moment, this patch only implements a small set of existing relaxations.. Assuming the approach is satisfactory, I plan to extend this to a broader set of instructions where there are obvious "relaxations" which are roughly performance equivalent.

Note that this patch *doesn't* change which instructions are relaxable. We may wish to explore that separately to increase optimization opportunity, but I figured that deserved it's own separate discussion.

There are possible downsides to this optimization (and all "pad previous instruction" variants). The major two are potentially increasing instruction fetch and perturbing uop caching. (i.e. the usual alignment risks) Specifically:

• If we pad an instruction such that it crosses a fetch window (16 bytes on modern X86), we may cause the decoder to have to trigger a fetch it wouldn't have otherwise. This can effect both decode speed, and icache pressure.
• Intel's uop caching have particular restrictions on instruction combinations which can fit in a particular way. By moving around instructions, we can both cause misses an change misses into hits. Many of the most painful cases are around branch density, so I don't expect this to be too bad on the whole.

On the whole, I expect to see small swings (i.e. the typical alignment change problem), but nothing major or systematic in either direction.

[reames]

Remove some stray debugging code, and tweak style a bit as a result of no-longer needed variables.

[reames]

Fix a minor bug in new test - intel vs att syntax bites again.

[reames]

Add support for boundary align

At first, I thought we'd be able to handle other directives as well (such as .org), but a closer read indicates I had misread the semantics of those.

[skan]

llvm/include/llvm/MC/MCFragment.h

278

For data

279

"Value is repeated ValueSize times" , I am afraid this statement is not true. ValueSize is the size of the integer (in bytes) of Value, and the Value is repeated FragmentSize / AF.getValueSize() times.

[reames]

llvm/include/llvm/MC/MCFragment.h

279

You're correct. I'm just going to remove this. The comment change isn't really related to the patch.

[reames]

Remove unrelated comment, and a couple of splittable changes.

[reames]

Restructure code triggered by discussion on D75268. If I simply admit that padding instructions is inherently target specific, we have a nice clean API for any form of target specific padding. As a separate patch, I'll add prefix padding to this API for x86. It also appears that Hexagon has a bundle nop padding (currently via finishLayout) which can be refactored into this API as well.

[reames]

On top of this, I prototyped what prefix padding for relaxable instructions might look like in D75300.

[reames]

llvm/lib/Target/X86/MCTargetDesc/X86AsmBackend.cpp

682

Note to self: Since this is increasing the size of the instruction, we need to make sure we're not creating a branch boundary crossing case. If we are, we can just skip the optional expansion here.

[skan]

llvm/lib/MC/MCAssembler.cpp

1182–1183

Capitalize the first character of the variable it

1194–1196

F.getKind() == MCFragment::FT_Data || F.getKind() == FT_CompactEncodedInst
I think we can handle MCCompactEncodedInstFragment here.

1210–1211

The return type of getFragmentOffset and computeFragmentSize is uint64_t, so I suggest use uint64_t here is better

1262–1263

uint64_t

llvm/test/MC/X86/align-via-relaxation.s

31

around

[skan]

llvm/lib/Target/X86/MCTargetDesc/X86AsmBackend.cpp

682

I think we add the code

if needAlignInst(Inst) return false;
auto *PF = cast_or_null<MCBoundaryAlignFragment>(RF.getPrevNode());
if(PF && PF.canEmitNops()) return false;

in the function canBeRelaxedForPadding to make sure we're not creating a branch boundary crossing case

[skan]

llvm/lib/MC/MCAssembler.cpp

1245–1247

We can avoid setting size for boundaryalign with D75404

[MaskRay]

llvm/lib/MC/MCAssembler.cpp

1182

for (MCSection &Sec : *this) {

1188

for (MCFragment &F : Sec) {

1194–1196

It seems we can use switch (F.getKind()) here.

1233

The comment can be moved before the if. Then the brace can be deleted.

llvm/lib/Target/X86/MCTargetDesc/X86AsmBackend.cpp

665

*RF.getSubtargetInfo() -> STI (it is a member variable)

668

SmallString<16> should be sufficient. (The SmallString used in MCAssembler::relaxInstruction should be fixed instead)

llvm/test/MC/X86/align-via-relaxation.s

2

The RUN line is unnecessarily indented. It is not common.

-pc-linux-gnu can be deleted to make the line length smaller.

7

.text and .section .text do the same thing. We can actually delete .file, .text and .section .text.

11

jmp is misaligned.

[MaskRay]

llvm/lib/MC/MCAssembler.cpp

793–799

I suspect we may have to do while (layoutOnce(Layout)) and optimizeLayout(Layout) in a lockstep.

optimizeLayout may cause some JCC_1/JMP_1 in MCRelaxableFragment to need relaxation.

794

We can dump the layout only when something has changed. This requires a change to optimizeLayout's return type.

1025

Unneeded

[reames]

llvm/lib/MC/MCAssembler.cpp

793–799

The whole point of the design is that we don't have to iterate them. If you see a case where we do, please point it out; that's a bug.

See the comments about which starting offsets are changing and why we're not skipping over any relaxable fragment.

794

I see no value in this. I can make the change if you want, but I don't think it's actually useful.

1194–1196

I'd written it with a switch originally. It was much harder to read. I could use a switch for the filtering and then fall into the complicated logic for the align cases if you want?

llvm/lib/Target/X86/MCTargetDesc/X86AsmBackend.cpp

665

I'd prefer to leave this as is. It follows the idiom of the other uses of relaxInstruction, and I haven't cross checked that the two subtarget infos are identical.

llvm/test/MC/X86/align-via-relaxation.s

7

We need to know it's a text section not a data section.

11

Er, what? Are you possibly thinking of the branch-align feature? That's not enabled in this test file.

31

No. That would change meaning of comment.

[reames]

Address most of the stylistic comments. A further update to address the one functional bug is forthcoming.

[reames]

Fix the functional bug and add tests for it.

[reames]

Remove the relaxFragment loop. Now that boundary align fragments no longer need relaxed to update size, this is now just a nop.

[reames]

Give up and just make all the code target specific. I'd originally hoped to apply this for other targets as well, but when looking at Hexagon (the only one with anything analogous), I realized that forcing a common implementation was just adding complexity for little value. Each backend has it's own set of constraints as to which padding is valuable. Instead of introducing new APIs, just follow the precedent that Hexagon already set.

Once this is in and backed a bit, we can revisit to see if any of it can be made target agnostic after all.

[craig.topper]

llvm/lib/Target/X86/MCTargetDesc/X86AsmBackend.cpp

748

it's ->its

771

The end of this line and into the next line doesn't read right. It says "a it's"

772

it's -> its

[skan]

llvm/test/MC/X86/align-via-relaxation.s

11

I think his meaning is "jmp" is misaligned in a text editor.

[skan]

In D75203#1901962, @reames wrote:

Remove the relaxFragment loop. Now that boundary align fragments no longer need relaxed to update size, this is now just a nop.

We may need add the relaxFragment loop back since the commit for D75404 was reverted.

[reames]

Rebase and address grammar comments.

[reames]

Remove tabs from test file to fix (textual) alignment.

[reames]

Add command line options to selectively disable. This is to ease performance regression triage post commit.

I think this is ready to land. I'm just waiting on an LGTM.

[skan]

llvm/lib/Target/X86/MCTargetDesc/X86AsmBackend.cpp

654

Is16BitMode

795

Capitalize i here otherwise clang tidy would report a warning

804

Capitalize i and N here otherwise clang tidy would report a warning

[reames]

llvm/lib/Target/X86/MCTargetDesc/X86AsmBackend.cpp

654

This code is copied from existing example. Will change both after commit.

795

"i" and "I" are different variables.

Also, if clang-tidy reports a warning for "i", clang-tidy has a bug.

804

No, clang-tidy is wrong.

[skan]

LGTM , I applied this patch and passed the chek-all tests and found no new fails when running SPEC.

[MaskRay]

The patch locates MCRelaxableFragment's within two MCSymbol's and relaxes some MCRelaxableFragment's to reduce the size of a MCAlignFragment. The behavior is hence dependent on additional temporary labels due to -g.

@condy reported an example where clang -O1 -g and clang -O1 have different .text content
https://bugs.llvm.org/show_bug.cgi?id=42138#c13 (a MCRelaxableFragment (jmp) has 5 bytes with -O1 and 2 bytes with -O1 -g)
(There is also a thread https://lists.llvm.org/pipermail/llvm-dev/2021-January/147568.html CC @vsk for thoughts).

.p2align 4, 0x90 is common due to loops. For a larger program, with a lot of temporary labels (-g vs non -g), the assembly output difference may be quite destined.

--- a.s 2021-01-11 13:57:25.055152745 -0800
+++ b.s 2021-01-11 13:57:20.627140370 -0800
@@ -2,2 +2,3 @@
        .file   "czw.cc"
+       .file   1 "/tmp/c" "czw.cc"
        .globl  _ZN1k1lEv                       # -- Begin function _ZN1k1lEv
@@ -7,2 +8,3 @@
 .Lfunc_begin0:
+       .loc    1 26 0                          # czw.cc:26:0
        .cfi_startproc
@@ -11,2 +13,3 @@
 # %bb.0:                                # %entry
+       #DEBUG_VALUE: l:this <- $rdi
        pushq   %r15
@@ -27,2 +30,4 @@
 .Ltmp0:
+.Ltmp3:
+       #DEBUG_VALUE: l:this <- $rbx
        .cfi_escape 0x2e, 0x00
@@ -30,9 +35,17 @@
        movq    %rsp, %rdx
+.Ltmp4:
+       .loc    1 27 15 prologue_end            # czw.cc:27:15
        movl    $.L.str, %esi
        callq   _ZN1eIciEC1EPc9allocator

I am thinking of whether we can use some properties of MCSymbol to filter out some MCSymbol's in LabeledFragments but cannot find one which works (for example, IsUsedInReloc is only used in ObjectWriter, which is after the assembler optimization).

@condy: -mllvm -x86-pad-for-align=false is a workaround.

[skan]

In D75203#2491618, @MaskRay wrote:

I am thinking of whether we can use some properties of MCSymbol to filter out some MCSymbol's in LabeledFragments but cannot find one which works (for example, IsUsedInReloc is only used in ObjectWriter, which is after the assembler optimization).

@condy: -mllvm -x86-pad-for-align=false is a workaround.

Option -x86-pad-for-align is for assembler optimization, I think we should set its default value to false and add some comments that it may interact with labels in text section. If someone turn on it explictly, the difference of machine code will be fine since it's a assembler optimization.

[reames]

This review has been closed for nearly 10 months. Please move discussion of proposed changes to the bug or another relevant location.

[jyknight]

Right, there's no fundamental reason why moving a label has to be forbidden -- but it'd be extremely complex if we allowed moving a label which could cause the re-layout of a fragment we thought we'd already finalized the offsets for. This would happen if the label offset required relaxation of some instruction/data referencing it. That, then, might require undoing the padding from an instruction we've already padded out, due to less alignment-padding being required overall.

So, maybe we can allow changing the address of labels that CAN'T cause such an issue, then? Can we identify them straightforwardly? We would need to avoid changing the offset of any label which might require further relaxation of instructions in a text segment (because that's all this pass can modify).

But that doesn't mean we can modify all labels in text which are referred to only by non-text fixups. Consider relaxable uleb128 data section containing offsets of labels in text sections -- naively it seems fine to allow further relaxation of the uleb128 data after running the padding...but unfortunately that's wrong, because if relaxable instructions in text point _back_ to labels in the uleb128 section, they may need to be relaxed when/if the address offsets in the uleb128 data grow. I think the criteria we'd need to use is something like: find all sections referenced by a relaxable fixup in the text section. Then find all sections referenced by a relaxable fixup in one of those sections, recursively. This is the set of sections that cannot point TO a label in text, if we want to be able to move it. That seems...complicated, itself.

Simpler, is it be valid to simply assume that text sections cannot ever refer, even transitively, to debug sections?

[MaskRay]

In D75203#2494775, @reames wrote:

This review has been closed for nearly 10 months. Please move discussion of proposed changes to the bug or another relevant location.

Created https://bugs.llvm.org/show_bug.cgi?id=48742

llvm/include/llvm/MC/MCAsmBackend.h

public:
   /// Check whether the given instruction may need relaxation.
   ///
   /// \param Inst - The instruction to test.
   /// \param STI - The MCSubtargetInfo in effect when the instruction was
   /// encoded.
   virtual bool mayNeedRelaxation(const MCInst &Inst,
                                  const MCSubtargetInfo &STI) const = 0;
 
+  /// Return true if the given instruction can be further relaxed.  This is
+  /// different than mayNeedFurther relaxation in that it is allowed to return
+  /// true when relaxation is possible, but not required.
+  virtual bool canBeFurtherRelaxed(const MCInst &Inst,
+                                   const MCSubtargetInfo &STI) const {
+    return mayNeedRelaxation(Inst, STI);
+  }
+
+
   /// Target specific predicate for whether a given fixup requires the
   /// associated instruction to be relaxed.
   virtual bool fixupNeedsRelaxationAdvanced(const MCFixup &Fixup, bool Resolved,
                                             uint64_t Value,
                                             const MCRelaxableFragment *DF,
                                             const MCAsmLayout &Layout,
                                             const bool WasForced) const;
 

llvm/include/llvm/MC/MCAssembler.h

private:
   bool relaxBoundaryAlign(MCAsmLayout &Layout, MCBoundaryAlignFragment &BF);
   bool relaxDwarfLineAddr(MCAsmLayout &Layout, MCDwarfLineAddrFragment &DF);
   bool relaxDwarfCallFrameFragment(MCAsmLayout &Layout,
                                    MCDwarfCallFrameFragment &DF);
   bool relaxCVInlineLineTable(MCAsmLayout &Layout,
                               MCCVInlineLineTableFragment &DF);
   bool relaxCVDefRange(MCAsmLayout &Layout, MCCVDefRangeFragment &DF);
 
+  /// Once relaxation is complete, try to reduce number of nops required
+  /// without requiring any further relaxation.
+  void optimizeLayout(MCAsmLayout &Layout);
+
   /// finishLayout - Finalize a layout, including fragment lowering.
   void finishLayout(MCAsmLayout &Layout);
 
   std::tuple<MCValue, uint64_t, bool>
   handleFixup(const MCAsmLayout &Layout, MCFragment &F, const MCFixup &Fixup);
 
 public:
   std::vector<std::pair<StringRef, const MCSymbol *>> Symvers;

llvm/include/llvm/MC/MCFragment.h

public:
   const MCInst &getInst() const { return Inst; }
   void setInst(const MCInst &Value) { Inst = Value; }
 
   static bool classof(const MCFragment *F) {
     return F->getKind() == MCFragment::FT_Relaxable;
   }
 };
 
+/// Represents alignment for either code or data.  For code, the Value and
+/// ValueSize fields are ignored; nops are always emitted.  For date, the
+/// Value is repeated ValueSize times.  Value is usually 0.
 class MCAlignFragment : public MCFragment {
   /// The alignment to ensure, in bytes.
   unsigned Alignment;
 
   /// Flag to indicate that (optimal) NOPs should be emitted instead
   /// of using the provided value. The exact interpretation of this flag is
   /// target dependent.
   bool EmitNops : 1;

llvm/lib/MC/MCAssembler.cpp

void MCAssembler::layout(MCAsmLayout &Layout) {
   // Layout until everything fits.
   while (layoutOnce(Layout))
     if (getContext().hadError())
       return;
 
   DEBUG_WITH_TYPE("mc-dump", {
       errs() << "assembler backend - post-relaxation\n--\n";
       dump(); });
 
+  optimizeLayout(Layout);
+
+  DEBUG_WITH_TYPE("mc-dump", {
+      errs() << "assembler backend - post-optimization\n--\n";
+      dump(); });
+
   // Finalize the layout, including fragment lowering.
   finishLayout(Layout);
 
   DEBUG_WITH_TYPE("mc-dump", {
       errs() << "assembler backend - final-layout\n--\n";
       dump(); });
 
   // Allow the object writer a chance to perform post-layout binding (for
for (auto i = 0, N = BF.isFused() ? 2 : 1;
     AlignedSize += computeFragmentSize(Layout, *F);
   }
   uint64_t OldSize = BF.getSize();
   AlignedOffset -= OldSize;
   Align BoundaryAlignment = BF.getAlignment();
   uint64_t NewSize = needPadding(AlignedOffset, AlignedSize, BoundaryAlignment)
                          ? offsetToAlignment(AlignedOffset, BoundaryAlignment)
                          : 0U;
-  if (NewSize == OldSize)
-    return false;
   BF.setSize(NewSize);
-  Layout.invalidateFragmentsFrom(&BF);
-  return true;
+  return (NewSize != OldSize);
 }
 
 bool MCAssembler::relaxDwarfLineAddr(MCAsmLayout &Layout,
                                      MCDwarfLineAddrFragment &DF) {
   MCContext &Context = Layout.getAssembler().getContext();
   uint64_t OldSize = DF.getContents().size();
   int64_t AddrDelta;
   bool Abs = DF.getAddrDelta().evaluateKnownAbsolute(AddrDelta, Layout);
   assert(Abs && "We created a line delta with an invalid expression");
for (iterator it = begin(), ie = end(); it != ie; ++it) {
     MCSection &Sec = *it;
     while (layoutSectionOnce(Layout, Sec))
       WasRelaxed = true;
   }
 
   return WasRelaxed;
 }
 
+void MCAssembler::optimizeLayout(MCAsmLayout &Layout) {
+  // See if we can further relax some instructions to cut down on the number of
+  // nop bytes required for code alignment.  The actual win is in reducing
+  // instruction count, not number of bytes.  Some micro-architectures (such
+  // as, say, modern X86-64) can easily end up decode limited.  It is
+  // often better to reduce the number of instructions (i.e. eliminate nops)
+  // even at the cost of increasing the size and complexity of others.
+
+  DenseSet<MCFragment *> LabeledFragments;
+  for (const MCSymbol &S : symbols())
+    LabeledFragments.insert(S.getFragment(false));
+
+  for (iterator it = begin(), ie = end(); it != ie; ++it) {
+    MCSection &Sec = *it;
+    if (!Sec.getKind().isText())
+      continue;
+
+    SmallVector<MCRelaxableFragment*, 4> Relaxable;
+    for (MCSection::iterator I = Sec.begin(), IE = Sec.end(); I != IE; ++I) {
+      MCFragment &F = *I;
+
+      if (LabeledFragments.count(&F))
+        Relaxable.clear();
+
+      if (F.getKind() ==  MCFragment::FT_Data)
+        // Skip and ignore
+        continue;
+
+      if (F.getKind() == MCFragment::FT_Relaxable) {
+        auto &RF = cast<MCRelaxableFragment>(*I);
+        if (getBackend().canBeFurtherRelaxed(RF.getInst(),
+                                             *RF.getSubtargetInfo()))
+          Relaxable.push_back(&RF);
+        // Note: It's okay to skip an instruction which can't be further
+        // relaxed as it a) will be a fixed number of bytes, and b) must be
+        // able to encode any larger offsets which result from shifting it
+        // around.
+        continue;
+      }
+
+      // For any unhandled kind, assume we can't change layout.
+      if (F.getKind() != MCFragment::FT_Align &&
+          F.getKind() != MCFragment::FT_BoundaryAlign) {
+        Relaxable.clear();
+        continue;
+      }
+      const unsigned OrigOffset = Layout.getFragmentOffset(&F);
+      const unsigned OrigSize = computeFragmentSize(Layout, F);
+      if (OrigSize == 0 || Relaxable.empty()) {
+        Relaxable.clear();
+        continue;
+      }
+
+      // To keep the effects local, prefer to relax instructions closest to
+      // the align directive.  This is purely about human understandability
+      // of the resulting code.  If we later find a reason to expand
+      // particular instructions over others, we can adjust.
+      MCFragment *FirstChangedFragment = nullptr;
+      unsigned RemainingSize = OrigSize;
+      while (!Relaxable.empty() && RemainingSize != 0) {
+        auto *RF = Relaxable.pop_back_val();
+
+        MCInst Relaxed;
+        getBackend().relaxInstruction(RF->getInst(), *RF->getSubtargetInfo(),
+                                      Relaxed);
+        SmallVector<MCFixup, 4> Fixups;
+        SmallString<256> Code;
+        raw_svector_ostream VecOS(Code);
+        getEmitter().encodeInstruction(Relaxed, VecOS, Fixups,
+                                       *RF->getSubtargetInfo());
+        const unsigned OldSize = RF->getContents().size();
+        const unsigned NewSize = Code.size();
+        assert(NewSize >= OldSize && "size decrease during relaxation?");
+        unsigned Delta = NewSize - OldSize;
+        if (Delta > RemainingSize) {
+          // Too big, can't use this relocation without requiring another
+          // round of relaxation.  Subtly, we can't skip past this one either
+          // as we *haven't* relaxed it.  Changing it's starting offset might
+          // require a larger negative offset than it can encode.  We don't
+          // need to worry about larger positive offsets as none of the
+          // possible offsets between this and our align are visible, and the
+          // ones afterwards aren't changing.
+          break;
+        }
+        RemainingSize -= Delta;
+        RF->setInst(Relaxed);
+        RF->getContents() = Code;
+        RF->getFixups() = Fixups;
+        FirstChangedFragment = RF;
+      }
+      Relaxable.clear();
+
+      // Unlike align, boundary align tracks it's own size after relaxation.
+      if (F.getKind() == MCFragment::FT_BoundaryAlign)
+        cast<MCBoundaryAlignFragment>(F).setSize(RemainingSize);
+      
+      if (FirstChangedFragment) {
+        // Redo the layout for any fragements in the effected range.  This is
+        // mostly updating start offsets, but also may need to apply other
+        // updates (such as changing offsets) to the fragments in question.
+        // Note that the relaxation itself has already been done above, and
+        // thus the total size of the range isn't changing.
+        Layout.invalidateFragmentsFrom(FirstChangedFragment);
+        while (FirstChangedFragment != &F) {
+          relaxFragment(Layout, *FirstChangedFragment);
+          FirstChangedFragment = FirstChangedFragment->getNextNode();
+        }
+      }
+
+      const unsigned FinalOffset = Layout.getFragmentOffset(&F);
+      const unsigned FinalSize = computeFragmentSize(Layout, F);
+      assert(OrigOffset + OrigSize == FinalOffset + FinalSize &&
+             "can't move start of next fragment!");
+      assert(FinalSize == RemainingSize && "inconsistent size computation?");
+    }
+  }
+}
+
+
 void MCAssembler::finishLayout(MCAsmLayout &Layout) {
   assert(getBackendPtr() && "Expected assembler backend");
   // The layout is done. Mark every fragment as valid.
   for (unsigned int i = 0, n = Layout.getSectionOrder().size(); i != n; ++i) {
     MCSection &Section = *Layout.getSectionOrder()[i];
     Layout.getFragmentOffset(&*Section.getFragmentList().rbegin());
     computeFragmentSize(Layout, *Section.getFragmentList().rbegin());
   }

llvm/lib/MC/MCFragment.cpp

OS << " Value:" << static_cast<unsigned>(FF->getValue())
        << " NumValues:" << FF->getNumValues();
     break;
   }
   case MCFragment::FT_Relaxable:  {
     const auto *F = cast<MCRelaxableFragment>(this);
     OS << "\n       ";
     OS << " Inst:";
     F->getInst().dump_pretty(OS);
+    OS << " (" << F->getContents().size() << ")";
     break;
   }
   case MCFragment::FT_Org:  {
     const auto *OF = cast<MCOrgFragment>(this);
     OS << "\n       ";
     OS << " Offset:" << OF->getOffset()
        << " Value:" << static_cast<unsigned>(OF->getValue());
     break;

llvm/lib/Target/X86/MCTargetDesc/X86AsmBackend.cpp

public:
   void applyFixup(const MCAssembler &Asm, const MCFixup &Fixup,
                   const MCValue &Target, MutableArrayRef<char> Data,
                   uint64_t Value, bool IsResolved,
                   const MCSubtargetInfo *STI) const override;
 
   bool mayNeedRelaxation(const MCInst &Inst,
                          const MCSubtargetInfo &STI) const override;
 
+  bool canBeFurtherRelaxed(const MCInst &Inst,
+                           const MCSubtargetInfo &STI) const override;
+
   bool fixupNeedsRelaxation(const MCFixup &Fixup, uint64_t Value,
                             const MCRelaxableFragment *DF,
                             const MCAsmLayout &Layout) const override;
 
   void relaxInstruction(const MCInst &Inst, const MCSubtargetInfo &STI,
                         MCInst &Res) const override;
 
   bool writeNopData(raw_ostream &OS, uint64_t Count) const override;
bool X86AsmBackend::mayNeedRelaxation(const MCInst &Inst,
   // relaxable instructions, the relaxable operand is always the last operand.
   unsigned RelaxableOp = Inst.getNumOperands() - 1;
   if (Inst.getOperand(RelaxableOp).isExpr())
     return true;
 
   return false;
 }
 
+bool X86AsmBackend::canBeFurtherRelaxed(const MCInst &Inst,
+                                        const MCSubtargetInfo &STI) const {
+  // TODO: There are lots of other tricks we could apply for increasing
+  // encoding size without impacting performance.
+  bool is16BitMode = STI.getFeatureBits()[X86::Mode16Bit];
+  return getRelaxedOpcode(Inst, is16BitMode) != Inst.getOpcode();
+}
+
+
 bool X86AsmBackend::fixupNeedsRelaxation(const MCFixup &Fixup,
                                          uint64_t Value,
                                          const MCRelaxableFragment *DF,
                                          const MCAsmLayout &Layout) const {
   // Relax if the value is too big for a (signed) i8.
   return !isInt<8>(Value);
 }
 
 // FIXME: Can tblgen help at all here to verify there aren't other instructions
 // we can relax?
 void X86AsmBackend::relaxInstruction(const MCInst &Inst,
                                      const MCSubtargetInfo &STI,
                                      MCInst &Res) const {
+  assert(canBeFurtherRelaxed(Inst, STI));
+
   // The only relaxations X86 does is from a 1byte pcrel to a 4byte pcrel.
   bool is16BitMode = STI.getFeatureBits()[X86::Mode16Bit];
   unsigned RelaxedOp = getRelaxedOpcode(Inst, is16BitMode);
 
   if (RelaxedOp == Inst.getOpcode()) {
     SmallString<256> Tmp;
     raw_svector_ostream OS(Tmp);
     Inst.dump_pretty(OS);
     OS << "\n";
     report_fatal_error("unexpected instruction to relax: " + OS.str());
   }
 
   Res = Inst;
   Res.setOpcode(RelaxedOp);
 }
 
 /// Write a sequence of optimal nops to the output, covering \p Count
 /// bytes.
 /// \return - true on success, false on failure
 bool X86AsmBackend::writeNopData(raw_ostream &OS, uint64_t Count) const {
   static const char Nops[10][11] = {
     // nop
     "\x90",
     // xchg %ax,%ax
     "\x66\x90",
     // nopl (%[re]ax)
     "\x0f\x1f\x00",
     // nopl 0(%[re]ax)
     "\x0f\x1f\x40\x00",
     // nopl 0(%[re]ax,%[re]ax,1)
     "\x0f\x1f\x44\x00\x00",
     // nopw 0(%[re]ax,%[re]ax,1)
     "\x66\x0f\x1f\x44\x00\x00",
     // nopl 0L(%[re]ax)
     "\x0f\x1f\x80\x00\x00\x00\x00",
     // nopl 0L(%[re]ax,%[re]ax,1)
     "\x0f\x1f\x84\x00\x00\x00\x00\x00",
     // nopw 0L(%[re]ax,%[re]ax,1)
     "\x66\x0f\x1f\x84\x00\x00\x00\x00\x00",
     // nopw %cs:0L(%[re]ax,%[re]ax,1)
     "\x66\x2e\x0f\x1f\x84\x00\x00\x00\x00\x00",
   };
 
   // This CPU doesn't support long nops. If needed add more.
   // FIXME: We could generated something better than plain 0x90.
   if (!STI.getFeatureBits()[X86::FeatureNOPL]) {
     for (uint64_t i = 0; i < Count; ++i)
       OS << '\x90';
     return true;
   }
 
   // 15-bytes is the longest single NOP instruction, but 10-bytes is
   // commonly the longest that can be efficiently decoded.
   uint64_t MaxNopLength = 10;
   if (STI.getFeatureBits()[X86::ProcIntelSLM])
     MaxNopLength = 7;
   else if (STI.getFeatureBits()[X86::FeatureFast15ByteNOP])
     MaxNopLength = 15;
public:
   createObjectTargetWriter() const override {
     return createX86ELFObjectWriter(/*IsELF64*/ false, OSABI,
                                     ELF::EM_X86_64);
   }
 };
 
 class ELFX86_IAMCUAsmBackend : public ELFX86AsmBackend {
 public:
   ELFX86_IAMCUAsmBackend(const Target &T, uint8_t OSABI,
                          const MCSubtargetInfo &STI)
       : ELFX86AsmBackend(T, OSABI, STI) {}
 
   std::unique_ptr<MCObjectTargetWriter>
   createObjectTargetWriter() const override {
     return createX86ELFObjectWriter(/*IsELF64*/ false, OSABI,
                                     ELF::EM_IAMCU);
   }
 };
 
 class ELFX86_64AsmBackend : public ELFX86AsmBackend {
 public:
   ELFX86_64AsmBackend(const Target &T, uint8_t OSABI,
                       const MCSubtargetInfo &STI)
     : ELFX86AsmBackend(T, OSABI, STI) {}
 
   std::unique_ptr<MCObjectTargetWriter>
   createObjectTargetWriter() const override {
     return createX86ELFObjectWriter(/*IsELF64*/ true, OSABI, ELF::EM_X86_64);
   }
 };
 
 class WindowsX86AsmBackend : public X86AsmBackend {
   bool Is64Bit;
 
 public:
   WindowsX86AsmBackend(const Target &T, bool is64Bit,
                        const MCSubtargetInfo &STI)
     : X86AsmBackend(T, STI)
     , Is64Bit(is64Bit) {
   }
 
   Optional<MCFixupKind> getFixupKind(StringRef Name) const override {
     return StringSwitch<Optional<MCFixupKind>>(Name)
         .Case("dir32", FK_Data_4)
         .Case("secrel32", FK_SecRel_4)
         .Case("secidx", FK_SecRel_2)
         .Default(MCAsmBackend::getFixupKind(Name));
   }
 
   std::unique_ptr<MCObjectTargetWriter>
   createObjectTargetWriter() const override {
     return createX86WinCOFFObjectWriter(Is64Bit);
   }
 };
 
 namespace CU {
 
   /// Compact unwind encoding values.
   enum CompactUnwindEncodings {
     /// [RE]BP based frame where [RE]BP is pused on the stack immediately after
     /// the return address, then [RE]SP is moved to [RE]BP.
     UNWIND_MODE_BP_FRAME                   = 0x01000000,
 
     /// A frameless function with a small constant stack size.
     UNWIND_MODE_STACK_IMMD                 = 0x02000000,
 
     /// A frameless function with a large constant stack size.
     UNWIND_MODE_STACK_IND                  = 0x03000000,
 
     /// No compact unwind encoding is available.
     UNWIND_MODE_DWARF                      = 0x04000000,
 
     /// Mask for encoding the frame registers.

llvm/test/MC/X86/align-branch-64.s

test_indirect:
   .endr
   jmpq *(%rax)
 
   .p2align 4
   .type   bar,@function
 bar:
   retq
 
+  # CHECK: test_pad_via_relax:
+  # CHECK: 200: testq
+  # CHECK: 203: jne
+  # CHECK: 209: int3
+  # note 6 byte jne which could be a 2 byte jne, but is instead
+  # expanded for padding purposes
+  # CHECK-NOT: nop
+  # CHECK: 220: callq
+  .global test_pad_via_relax
+  .p2align  5
+test_pad_via_relax:
+  testq %rax, %rax
+  jnz bar
+  .rept 23
+  int3
+  .endr
+  callq bar
+
   .section "unknown"
   .p2align 4
   .type   baz,@function
 baz:
   retq

llvm/test/MC/X86/align-via-relaxation.s

+  # RUN: llvm-mc -mcpu=skylake -filetype=obj -triple x86_64-pc-linux-gnu %s | llvm-objdump -d --section=.text - | FileCheck %s
+
+
+  .file "test.c"
+  .text
+  .section  .text
+  # Demonstrate that we can relax instructions to provide padding, not
+  # just insert nops.  jmps are being used for ease of demonstration.
+  # CHECK: .text
+  # CHECK: 0: eb 1f                         jmp 31 <foo>
+  # CHECK: 2: e9 1a 00 00 00                jmp 26 <foo>
+  # CHECK: 7: e9 15 00 00 00                jmp 21 <foo>
+  # CHECK: c: e9 10 00 00 00                jmp 16 <foo>
+  # CHECK: 11: e9 0b 00 00 00               jmp 11 <foo>
+  # CHECK: 16: e9 06 00 00 00               jmp 6 <foo>
+  # CHECK: 1b: e9 01 00 00 00               jmp 1 <foo>
+  # CHECK: 20: cc                           int3
+  .p2align 4
+  jmp foo
+  jmp foo
+  jmp foo
+  jmp foo
+  jmp foo
+  jmp foo
+  jmp foo
+  .p2align 5
+  int3
+foo:
+  ret
+
+  # Check that we're not shifting aroudn the offsets of labels - doing
+  # that would require a further round of relaxation
+  # CHECK: bar:
+  # CHECK: 22: eb fe                          jmp -2 <bar>
+  # CHECK: 24: 66 2e 0f 1f 84 00 00 00 00 00  nopw %cs:(%rax,%rax)
+  # CHECK: 2e: 66 90                          nop
+  # CHECK: 30: 0f 0b                          ud2
+
+bar:  
+  jmp bar
+nobypass:
+  .p2align 4
+  ud2
+
+
+  # Canonical toy loop to show benefit - we can align the loop header with
+  # fewer nops by relaxing the branch, even though we don't need to
+  # CHECK: loop_preheader:
+  # CHECK: 45: 48 85 c0                       testq %rax, %rax
+  # CHECK: 48: 0f 8e 22 00 00 00              jle 34 <loop_exit>
+  # CHECK: 4e: 66 2e 0f 1f 84 00 00 00 00 00  nopw %cs:(%rax,%rax)
+  # CHECK: 58: 0f 1f 84 00 00 00 00 00        nopl (%rax,%rax)
+  # CHECK: loop_header:
+  # CHECK: 60: 48 83 e8 01                    subq $1, %rax
+  # CHECK: 64: 48 85 c0                       testq %rax, %rax
+  # CHECK: 67: 7e 07                          jle 7 <loop_exit>
+  # CHECK: 69: e9 f2 ff ff ff                 jmp -14 <loop_header>
+  # CHECK: 6e: 66 90                          nop
+  # CHECK: loop_exit:
+  # CHECK: 70: c3                             retq
+  .p2align 5
+  .skip 5
+loop_preheader:
+  testq %rax, %rax
+  jle loop_exit
+  .p2align 5
+loop_header:
+  subq $1, %rax
+  testq %rax, %rax
+  jle loop_exit
+  jmp loop_header
+  .p2align 4
+loop_exit:
+  ret