Reimplement BoundaryAlign mechanism (mostly, but not quite NFC)

[reames]

Summary

This patch is an implementation of a review suggestion I had made on the original review. Essentially, rather than using up to two boundary align fragments to refine the region of interest, instead use a single one at the beginning of the region with an explicit end pointer. I happen to think this is a simpler and more clear implementation, but it may be a matter of opinion. I'm curious what others think.

This turned out to quite be NFC for an unexpected reason; we hadn't be flushing pending labels when starting a boundary align region. As such labels between a pair of instructions would sometimes have nops inserted before the previous instruction and the resulting label placement. As noted in the other negative tests, binding the label to the preceding instruction isn't *always* what you want, but it seems like a pretty reasonable default.

Since the patch was already NFC, I went ahead and reduced the maximum padding amount so that I could keep the size of a boundary align fragment the same on 64 bit platforms.

[skan]

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

513–514

If
a) the next instruction is a relaxable instruction (e.g. jump) and is emitted into a RelaxableFragment, or

b) the next instruction has no fixup and is emitted into a CompactEncodedInstFragment, or

c) the next fragment is a AlignFragment,

the data fragment will be unused. From my perspective, an unused BoundaryAlignFragment is normal when it doesn't have a 'LastFragment' by design. However a unused data fragment is kind of strange.

[skan]

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

481–484

Case

cmp %rax %rcx
.align 16
je .Label0

isn't correctly handled here. We should not emit NOP before cmp %rax %rcx, it may cause infinite loop.

[skan]

llvm/include/llvm/MC/MCFragment.h

541–542

I think using uint64_t as the type of Size is good enough here. And the maximum size of the BoundaryAlignFragment is 30 (15+15, 15 is the maximum of an instruction) indeed. So if you really want Size is more space-saving, I suggest uint8_t.

[skan]

Some meta comments:

Currently, the NOP padding version doesn't check the hardcode so that it has some common issues( not introduced by the reimplementation):

1. Some unfused pair is padded as if it is fused

cmp %rax %rcx
.byte 0x90
je .Label0

.byte 0x90 is not emitted by the function MCObjectStreamer::EmitInstruction, so current code can't see .byte 0x90 and thinks the CMP is fused with JE, however, they are not fused apparently.

2. Some expected check will fail
MCBoudaryAlignFragment is used to align one instruction or a fused pair, so it's size is expected to be no more than 30(the maximun size of two instructions).
When we encounter the case

cmp %rax %rcx
.rept 30
.byte 0x90
.endr
je .Label0

current code will emit NOP before the CMP and think the size of the instructions to be aligned is sizeof(CMP) + 30 + sizeof(JE) incorrectly, then the size of padding may be greater than 30.

3. NOP may be inserted after hardcode
As @jyknight says,

 p4_general_done:
	.byte 0xf3
	ret

Inserting anything between the tacked-on-prefix with .byte, and the rest of the instruction written mnemonically, would be bad.

Although all these case can be correctly addressed by adding assembler directive (your proposal D72303) manually, they can also be dealt with correctly and naturally
by not appending hardcode to fragment that has an instruction.

Prefix padding patch
To support for aligning branch with prefix padding, I have uploaded a new patch D72225. All three issues above have been resolved and my design for MCBoundaryAlignFragment is really similar to your reimplementation, do you mind if we directly focus on the prefix padding patch?

[MaskRay]

llvm/include/llvm/MC/MCFragment.h

541–542

uint8_t Size = 0;
Align AlignBoundary;
MCFragment *LastFragment = nullptr;

can make sizeof(MCBoundaryAlignFragment) 8 bytes smaller.

This patch does not apply on master. It needs a rebase.

[reames]

Getting this off review queues for the moment. Will return to this once other more urgent items in this area settle out.

llvm/include/llvm/MC/MCFragment.h

public:
 
   static bool classof(const MCFragment *F) {
     return F->getKind() == MCFragment::FT_CVDefRange;
   }
 };
 
 /// Represents required padding such that a particular other set of fragments
 /// does not cross a particular power-of-two boundary. The other fragments must
-/// follow this one within the same section.
+/// follow this one within the same section.  The set of aligned fragments is
+/// (ThisFragment, LastFragment].  That is, the range starting at the fragment
+/// following this one and stopping at LastFragment (inclusive).
 class MCBoundaryAlignFragment : public MCFragment {
-  /// The alignment requirement of the branch to be aligned.
-  Align AlignBoundary;
-  /// Flag to indicate whether the branch is fused.  Use in determining the
-  /// region of fragments being aligned.
-  bool Fused : 1;
-  /// Flag to indicate whether NOPs should be emitted.
-  bool EmitNops : 1;
+  /// The last fragment in the range of fragments being aligned.  The range of
+  /// instructions being aligned is defined as (this, LastFragment].
+  MCFragment *LastFragment = nullptr;
   /// The size of the fragment.  The size is lazily set during relaxation, and
   /// is not meaningful before that.
-  uint64_t Size = 0;
+  uint16_t Size = 0;
+  /// The alignment requirement of the branch to be aligned.
+  Align AlignBoundary;
 
 public:
-  MCBoundaryAlignFragment(Align AlignBoundary, bool Fused = false,
-                          bool EmitNops = false, MCSection *Sec = nullptr)
-      : MCFragment(FT_BoundaryAlign, false, Sec), AlignBoundary(AlignBoundary),
-        Fused(Fused), EmitNops(EmitNops) {}
+  MCBoundaryAlignFragment(Align AlignBoundary, MCSection *Sec = nullptr)
+    : MCFragment(FT_BoundaryAlign, false, Sec), AlignBoundary(AlignBoundary)
+  {}
 
   uint64_t getSize() const { return Size; }
-  void setSize(uint64_t Value) { Size = Value; }
+  void setSize(uint64_t Value) {
+    assert(Value == (uint64_t)((uint16_t)Value));
+    Size = Value;
+  }
 
   Align getAlignment() const { return AlignBoundary; }
 
-  bool isFused() const { return Fused; }
-  void setFused(bool Value) { Fused = Value; }
-
-  bool canEmitNops() const { return EmitNops; }
-  void setEmitNops(bool Value) { EmitNops = Value; }
+  MCFragment *getLastFragment() const { return LastFragment; }
+  void setLastFragment(MCFragment *F) { LastFragment = F; }
 
   static bool classof(const MCFragment *F) {
     return F->getKind() == MCFragment::FT_BoundaryAlign;
   }
 };
 } // end namespace llvm
 
 #endif // LLVM_MC_MCFRAGMENT_H

llvm/lib/MC/MCAssembler.cpp

 static bool needPadding(uint64_t StartAddr, uint64_t Size,
                         Align BoundaryAlignment) {
   return mayCrossBoundary(StartAddr, Size, BoundaryAlignment) ||
          isAgainstBoundary(StartAddr, Size, BoundaryAlignment);
 }
 
 bool MCAssembler::relaxBoundaryAlign(MCAsmLayout &Layout,
                                      MCBoundaryAlignFragment &BF) {
-  // The MCBoundaryAlignFragment that doesn't emit NOP should not be relaxed.
-  if (!BF.canEmitNops())
+  // If the last fragment was never set, then there's nothing to align.
+  if (!BF.getLastFragment())
     return false;
 
   uint64_t AlignedOffset = Layout.getFragmentOffset(BF.getNextNode());
+  // Compute the size of all the instructions in the range we're trying to
+  // align.  The range is [BF.getNextNode, LastNode].  
   uint64_t AlignedSize = 0;
-  const MCFragment *F = BF.getNextNode();
-  // If the branch is unfused, it is emitted into one fragment, otherwise it is
-  // emitted into two fragments at most, the next MCBoundaryAlignFragment(if
-  // exists) also marks the end of the branch.
-  for (auto i = 0, N = BF.isFused() ? 2 : 1;
-       i != N && !isa<MCBoundaryAlignFragment>(F); ++i, F = F->getNextNode()) {
+  for (const MCFragment *F = BF.getNextNode(), *Last = BF.getLastFragment(); ;
+       F = F->getNextNode()) {
     AlignedSize += computeFragmentSize(Layout, *F);
+    if (F == Last)
+      break;
   }
+  assert(AlignedSize <= BF.getAlignment().value() &&
+         "can't align a region larger than the alignment");
   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;

llvm/lib/MC/MCFragment.cpp

LLVM_DUMP_METHOD void MCFragment::dump() const {
   case MCFragment::FT_LEB: {
     const auto *LF = cast<MCLEBFragment>(this);
     OS << "\n       ";
     OS << " Value:" << LF->getValue() << " Signed:" << LF->isSigned();
     break;
   }
   case MCFragment::FT_BoundaryAlign: {
     const auto *BF = cast<MCBoundaryAlignFragment>(this);
-    if (BF->canEmitNops())
-      OS << " (can emit nops to align";
-    if (BF->isFused())
-      OS << " fused branch)";
-    else
-      OS << " unfused branch)";
-    OS << "\n       ";
     OS << " BoundarySize:" << BF->getAlignment().value()
-       << " Size:" << BF->getSize();
+       << " Size:" << BF->getSize()
+       << " LastFragment:" << BF->getLastFragment();
     break;
   }
   case MCFragment::FT_SymbolId: {
     const auto *F = cast<MCSymbolIdFragment>(this);
     OS << "\n       ";
     OS << " Sym:" << F->getSymbol();
     break;
   }

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

class X86AsmBackend : public MCAsmBackend {
   std::unique_ptr<const MCInstrInfo> MCII;
   X86AlignBranchKind AlignBranchType;
   Align AlignBoundary;
 
   bool isMacroFused(const MCInst &Cmp, const MCInst &Jcc) const;
 
   bool needAlign(MCObjectStreamer &OS) const;
   bool needAlignInst(const MCInst &Inst) const;
-  MCBoundaryAlignFragment *
-  getOrCreateBoundaryAlignFragment(MCObjectStreamer &OS) const;
+
   MCInst PrevInst;
+  MCBoundaryAlignFragment *PendingBA = nullptr;
 
 public:
   X86AsmBackend(const Target &T, const MCSubtargetInfo &STI)
       : MCAsmBackend(support::little), STI(STI),
         MCII(T.createMCInstrInfo()) {
     AlignBoundary = assumeAligned(X86AlignBranchBoundary);
     AlignBranchType = X86AlignBranchKindLoc;
   }
return (InstDesc.isConditionalBranch() &&
          (InstDesc.isCall() &&
           (AlignBranchType & X86AlignBranchKind::AlignBranchCall)) ||
          (InstDesc.isReturn() &&
           (AlignBranchType & X86AlignBranchKind::AlignBranchRet)) ||
          (InstDesc.isIndirectBranch() &&
           (AlignBranchType & X86AlignBranchKind::AlignBranchIndirect));
 }
 
-static bool canReuseBoundaryAlignFragment(const MCBoundaryAlignFragment &F) {
-  // If a MCBoundaryAlignFragment has not been used to emit NOP,we can reuse it.
-  return !F.canEmitNops();
-}
-
-MCBoundaryAlignFragment *
-X86AsmBackend::getOrCreateBoundaryAlignFragment(MCObjectStreamer &OS) const {
-  auto *F = dyn_cast_or_null<MCBoundaryAlignFragment>(OS.getCurrentFragment());
-  if (!F || !canReuseBoundaryAlignFragment(*F)) {
-    F = new MCBoundaryAlignFragment(AlignBoundary);
-    OS.insert(F);
-  }
-  return F;
-}
-
 /// Insert MCBoundaryAlignFragment before instructions to align branches.
 void X86AsmBackend::alignBranchesBegin(MCObjectStreamer &OS,
                                        const MCInst &Inst) {
   if (!needAlign(OS))
     return;
 
-  MCFragment *CF = OS.getCurrentFragment();
+  // Summary of pending BA scheme
+  // - If we encounter the first instruction in a fusible pair, insert a BA
+  //   fragment.
+  // - If we emit anything which isn't part of a fusible pair, clear pending.
+  // - If we ecounter an jmp/branch/etc, insert a BA fragment if there isn't
+  //   already one pending for a valid fusible sequence.
+  // - Close the pending sequence after any alignable instruction (since they
+  //   also terminate fusible sequences.)
+  // Note that the BoundaryAlign fragment only has semantic meaning once a
+  // valid LastFragment is set.  Otherwise, it remains a nop.
+
   bool NeedAlignFused = AlignBranchType & X86AlignBranchKind::AlignBranchFused;
-  if (NeedAlignFused && isMacroFused(PrevInst, Inst) && CF) {
-    // Macro fusion actually happens and there is no other fragment inserted
-    // after the previous instruction. NOP can be emitted in PF to align fused
-    // jcc.
-    if (auto *PF =
-            dyn_cast_or_null<MCBoundaryAlignFragment>(CF->getPrevNode())) {
-      const_cast<MCBoundaryAlignFragment *>(PF)->setEmitNops(true);
-      const_cast<MCBoundaryAlignFragment *>(PF)->setFused(true);
-    }
-  } else if (needAlignInst(Inst)) {
-    // Note: When there is at least one fragment, such as MCAlignFragment,
-    // inserted after the previous instruction, e.g.
-    //
-    // \code
-    //   cmp %rax %rcx
-    //   .align 16
-    //   je .Label0
-    // \ endcode
-    //
-    // We will treat the JCC as a unfused branch although it may be fused
-    // with the CMP.
-    auto *F = getOrCreateBoundaryAlignFragment(OS);
-    F->setEmitNops(true);
-    F->setFused(false);
-  } else if (NeedAlignFused && isFirstMacroFusibleInst(Inst, *MCII)) {
-    // We don't know if macro fusion happens until the reaching the next
-    // instruction, so a place holder is put here if necessary.
-    getOrCreateBoundaryAlignFragment(OS);
+  if (!needAlignInst(Inst) && PendingBA)
+    PendingBA = nullptr;
+  if ((needAlignInst(Inst) && (!PendingBA ||
+                               !isMacroFused(PrevInst, Inst))) ||
+      (NeedAlignFused && isFirstMacroFusibleInst(Inst, *MCII))) {
+    PendingBA = new MCBoundaryAlignFragment(AlignBoundary);
+    OS.insert(PendingBA);
   }
 
   PrevInst = Inst;
 }
 
 /// Insert a MCBoundaryAlignFragment to mark the end of the branch to be aligned
 /// if necessary.
 void X86AsmBackend::alignBranchesEnd(MCObjectStreamer &OS, const MCInst &Inst) {
-  if (!needAlign(OS))
+  if (!needAlign(OS) || !needAlignInst(Inst))
+    return;
+
+  auto *BA = PendingBA;
+  if (!BA)
     return;
-  // If the branch is emitted into a MCRelaxableFragment, we can determine the
-  // size of the branch easily in MCAssembler::relaxBoundaryAlign. When the
-  // branch is fused, the fused branch(macro fusion pair) must be emitted into
-  // two fragments. Or when the branch is unfused, the branch must be emitted
-  // into one fragment. The MCRelaxableFragment naturally marks the end of the
-  // fused or unfused branch.
-  // Otherwise, we need to insert a MCBoundaryAlignFragment to mark the end of
-  // the branch. This MCBoundaryAlignFragment may be reused to emit NOP to align
-  // other branch.
-  if (needAlignInst(Inst) && !isa<MCRelaxableFragment>(OS.getCurrentFragment()))
-    OS.insert(new MCBoundaryAlignFragment(AlignBoundary));
+  PendingBA = nullptr;
+
+  auto *CF = OS.getCurrentFragment();
+  if (!CF)
+    return;
+
+  // Define the range of fragments being aligned.
+  BA->setLastFragment(CF);
+  
+  // We need to ensure that further instructions aren't added to the current
+  // fragment.  The easiest way is to insert a new empty DataFragment.
+  // RelaxableFragments are always single instructions, and are common for
+  // jumps, so avoid inserting a potentially unused fragment in that case.
+  if (!isa<MCRelaxableFragment>(CF))
+    OS.insert(new MCDataFragment());
   
   // Update the maximum alignment on the current section if necessary.
   MCSection *Sec = OS.getCurrentSectionOnly();
   if (AlignBoundary.value() > Sec->getAlignment())
     Sec->setAlignment(AlignBoundary);
 }
 
 Optional<MCFixupKind> X86AsmBackend::getFixupKind(StringRef Name) const {
   if (STI.getTargetTriple().isOSBinFormatELF()) {

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

   # RUN: llvm-mc -filetype=obj -triple x86_64-pc-linux-gnu --x86-align-branch-boundary=32 --x86-align-branch=call+jmp+indirect+ret+jcc+fused %s | llvm-objdump -d --no-show-raw-insn - | FileCheck %s
 
   # This file includes cases which are problematic to apply automatic padding
   # in the assembler.  These are the examples brought up in review and
   # discussion which motivate the need for a assembler directive to
   # selectively enable/disable.
-  # FIXME: the checks are checking current *incorrect* behavior
+  # FIXME: (some of) the checks are checking current *incorrect* behavior
 
   .text
 
   # In the first test, we have a label which is expected to be bound to the
   # start of the call.  For instance, we want to associate a fault on the call
-  # target with some bit of higher level sementic.
+  # target with some bit of higher level sementic. (FIXME)
   # CHECK: labeled_call_test1:
   # CHECK: 1f label_before
   # CHECK: 1f: nop
   # CHECK: 20: callq
   .globl  labeled_call_test1
   .p2align  5
 labeled_call_test1:
   .rept 31
   int3
   .endr
 label_before:
   callq bar
 
   # In the second test, we have a label which is expected to be bound to the
   # end of the call.  For instance, we want the to associate some data with
   # the return address of the call.
   # CHECK: labeled_call_test2:
   # CHECK: 5a: callq
+  # CHECK: 5f label_after
   # CHECK: 5f: nop
-  # CHECK: 60 label_after
   # CHECK: 60: jmp
   .globl  labeled_call_test2
   .p2align  5
 labeled_call_test2:
   .rept 26
   int3
   .endr
   callq bar
 label_after:
   jmp bar
 
   # Our third test is like the first w/a labeled fault, but specifically to
   # a fused memory comparison.  This is the form produced by implicit null
-  # checks for instance.
+  # checks for instance. (FIXME)
   # CHECK: implicit_null_check:
   # CHECK: 9f fault_addr
   # CHECK: 9f: nop
   # CHECK: a0: cmpq
   .globl  implicit_null_check
   .p2align  5
 implicit_null_check:
   .rept 31