[MC][X86] Automatic alignment for Macro-Op Fusion

[Amir]

Summary

Introduce an option x86-align-for-macrofusion to prevent a pair of
macro-fusion eligible instructions from being split by a given alignment
boundary by automatically padding the first instruction in a pair with
a minimal size nop.

In effect, it ensures that a pair of macro-fusible instructions is not split by
a cache line boundary, which is a precondition for macro-op fusion in
modern Intel Cores (see Intel Architecture Optimization Reference Manual,
2.3.2.1 Legacy Decode Pipeline: Macro-Fusion).

[Amir]

Addressed clang-format warnings

[skan]

llvm/lib/Target/X86/MCTargetDesc/X86BaseInfo.h

364–366

The extension is definitely wrong. BranchFused indicates fused macro fusion pairs, why do you add something like "AlignMacroFusionCmp, AlignMacroFusionBranch" .

[skan]

In D97982, NeverAlign fragment type is introduced to prevent macro fusion pairs from ending at a specified boundary. I am confused why you are trying to reuse the BoundaryAlign fragment here do the same thing. Maybe I do not see the big pitcture, so could you clarify you design?

[Amir]

@skan:
The big picture is that NeverAlign fragment insertion is controlled by a client (BOLT), while BoundaryAlign insertion is done automatically. This automatic macro-fusion alignment might be useful as a standalone performance optimization.
This diff leverages the infrastructure to detect eligible macro-fusion pairs and insert BoundaryAlign fragment. I've added logic on top of it to perform macro-fusion alignment when that is requested by an option.

[Amir]

Addressed the comment by @skan:

• removed newly added BranchKinds, reused existing ones

[Amir]

llvm/lib/Target/X86/MCTargetDesc/X86BaseInfo.h

364–366

I wanted to avoid overloading the existing types with different actions based on them: ie JCC erratum would have used existing BranchBoundaryKinds, while auto MF alignment would use new ones. But I guess it's OK to reuse and make the action depend on a cl opt.

[skan]

llvm/include/llvm/MC/MCFragment.h

563–568

The comments here is weired after you added the new usage to the fragment, you need to refine it.

llvm/lib/MC/MCAssembler.cpp

1086–1088

uint64_t NewSize = 0 is enough, we used U suffix before because of the conditional operator.

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

80–81

The words "cmp+jcc" and "falling between" seem not accurate.

166–173

In fact, X86AlignForMacroFusion is compatible with X86AlignBranchWithin32BBoundaries, you can set AlignBoundary to 64 and add AlignBranchFused to AlignBranchType if both of the options exist.

[Amir]

Addressed comments by @skan

[Amir]

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

166–173

No, they're semantically incompatible: X86AlignBranchWithin32BBoundaries would prevent macrofusion pair from crossing the 32B boundary (stronger alignment restriction), while X86AlignForMacroFusion would prevent macrofusion pair being perfectly split by 64B boundary.
So if X86AlignForMacroFusion is on, it's known not to satisfy X86AlignBranchWithin32BBoundaries restrictions.
(Conversely, if X86AlignBranchWithin32BBoundaries is on, X86AlignForMacroFusion is satisfied automatically).

They're further incompatible by the fact that X86AlignForMacroFusion flag enables the new BoundaryAlign behavior isAvoidEndAlign which performs the same alignment as NeverAlign.

[Amir]

llvm/include/llvm/MC/MCFragment.h

563–568

The comments are up-to-date. Please take a closer look at AvoidEndAlign flag usage below

[Amir]

Addressed linter warning

[skan]

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

166–173

"So if X86AlignForMacroFusion is on, it's known not to satisfy X86AlignBranchWithin32BBoundaries restrictions.
(Conversely, if X86AlignBranchWithin32BBoundaries is on, X86AlignForMacroFusion is satisfied automatically)."

The requirements of X86AlignForMacroFusion and X86AlignBranchWithin32BBoundaries can be met at the same time, so they are compatible.

isAvoidEndAlign is a detail about implementation and is not a good proof for the incompatibility.

Meanwhile, AlignBranchType, AlignBoundary can be also be set by options X86AlignBranchBoundary, X86AlignBranch. So the assert here is not correct.

[Amir]

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

166–173

I see what you mean. We can handle X86AlignForMacroFusion first and then override it if X86AlignBranchWithin32BBoundaries is set as it's a stronger alignment requirement. Let me fix that.

[Amir]

Handle X86AlignForMacroFusion option first.
Override it if X86AlignBranchWithin32BBoundaries is set.

[Amir]

Addressed linter warning

[skan]

llvm/lib/MC/MCAssembler.cpp

1098–1100

Replace tab with space here.

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

165–170

1. You need test case for this
2. I don't think it's correct to set value to an option in the constructor, maybe you need to define a class member
3. Nest the if clauses here is incorrect. As I commented before, you should care about the fields set by options rather than the options themselves because the values like AlignBranchType, AlignBoundary are not set only by X86AlignBranchWithin32BBoundaries.

Maybe a simple solution is to add the following code to the end of the constructor

// Clean the alignment request
if (AlignBoundary == Align())
          AlignBranchType.clear();
else if (AlignBranchType)
         AlignBoundary = Align();

If(X86AlignForMacroFusion) {
   if(AlignBoundary == Align())
         AlignForMacroFusionOnly = true;
   if (AlignBoundary > Align(64) || AlignBoundary == Align()) {
          AlignBoundary = assumeAligned(64);
   } 
   AlignBranchType.addKind(X86::AlignBranchFused);         
}

661–662

Name IsBranchFused is quite misleading. Inst here is not a branch and may not be fused when IsBranchFused is true.

You need a better name here, maybe IsFirstMacroFusibleInstAndMayNeedAlign?

665–666

X86AlignForMacroFusion && IsBranchFused -> AlignForMacroFusionOnly
// Add some comments ...

[Amir]

Addressed comments by @skan.

llvm/lib/MC/MCAssembler.cpp

1098–1100

Verified that these are spaces (I think Phabricator just shows with >> that the indentation changed)

[skan]

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

195

Why do you clear the branch type here?

196–197

We need test to make sure unfused jcc is not aligned.

[Amir]

Intel folks have collected perf data for this optimization on SPECint17 workload:

SPECcpu2017
 
Compiler/optimizer:  bin/clang 
 
Overall score:              228
Breakdown
500.perlbench_r        235
502.gcc_r                    238
505.mcf_r                   165  
520.omnetpp_r         132
523.xalancbmk_r       190
525.x264_r                 465
531.deepsjeng_r       228
541.leela_r                 232
548.exchange2_r      423
557.xz_r                      162
 
Compiler/optimizer:  bin/clang -mllvm -x86-align-for-macrofusion
 
Overall score:              228
Breakdown
500.perlbench_r        235
502.gcc_r                    238
505.mcf_r                   164  
520.omnetpp_r         131
523.xalancbmk_r       190
525.x264_r                 464
531.deepsjeng_r       228
541.leela_r                 234
548.exchange2_r      422
557.xz_r                      161

I'll abandon this diff based on that data. This functionality has non-trivial compile-time overhead (as it relies on relaxation for extra fragments), but it doesn't bring any perf benefit to workloads represented by SPECint17.

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

195

I think it doesn't make sense to have JCC erratum mitigation for the other branch types,

llvm/include/llvm/MC/MCFragment.h

public:
 
   StringRef getFixedSizePortion() const { return FixedSizePortion; }
 
   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.
+/// If AvoidEndAlign is set, this fragment will emit a minimum size nop to
+/// prevent the fragment following it from ending at a given \p AlignBoundary.
 class MCBoundaryAlignFragment : public MCFragment {
   /// The alignment requirement of the branch to be aligned.
   Align AlignBoundary;
   /// The last fragment in the set of fragments to be aligned.
   const 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;
+  /// Whether this fragment pads the subsequent fragment to prevent it from
+  /// ending at AlignBoundary.
+  bool IsAvoidEndAlign = false;
 
 public:
   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; }
 
   Align getAlignment() const { return AlignBoundary; }
   void setAlignment(Align Value) { AlignBoundary = Value; }
 
   const MCFragment *getLastFragment() const { return LastFragment; }
   void setLastFragment(const MCFragment *F) {
     assert(!F || getParent() == F->getParent());
     LastFragment = F;
   }
 
+  bool isAvoidEndAlign() const { return IsAvoidEndAlign; }
+  void setAvoidEndAlign(bool V) { IsAvoidEndAlign = V; }
+
   static bool classof(const MCFragment *F) {
     return F->getKind() == MCFragment::FT_BoundaryAlign;
   }
 };
 
 class MCPseudoProbeAddrFragment : public MCEncodedFragmentWithFixups<8, 1> {
   /// The expression for the difference of the two symbols that
   /// make up the address delta between two .pseudoprobe directives.

llvm/lib/MC/MCAssembler.cpp

bool MCAssembler::relaxBoundaryAlign(MCAsmLayout &Layout,
                                      MCBoundaryAlignFragment &BF) {
   // BoundaryAlignFragment that doesn't need to align any fragment should not be
   // relaxed.
   if (!BF.getLastFragment())
     return false;
 
   uint64_t AlignedOffset = Layout.getFragmentOffset(&BF);
   uint64_t AlignedSize = 0;
+  uint64_t NewSize = 0U;
+  Align BoundaryAlignment = BF.getAlignment();
+
+  if (BF.isAvoidEndAlign()) {
+    // Get fragment size for the fragment following this BoundaryAlign.
+    const MCFragment *NF = BF.getNextNode();
+    AlignedSize = computeFragmentSize(Layout, *NF);
+
+    // Pad with a minimum size nop.
+    if (isAgainstBoundary(AlignedOffset, AlignedSize, BoundaryAlignment))
+      NewSize = getBackend().getMinimumNopSize();
+  } else {
     for (const MCFragment *F = BF.getLastFragment(); F != &BF;
          F = F->getPrevNode())
       AlignedSize += computeFragmentSize(Layout, *F);
 
-  Align BoundaryAlignment = BF.getAlignment();
-  uint64_t NewSize = needPadding(AlignedOffset, AlignedSize, BoundaryAlignment)
-                         ? offsetToAlignment(AlignedOffset, BoundaryAlignment)
-                         : 0U;
+    if (needPadding(AlignedOffset, AlignedSize, BoundaryAlignment))
+      NewSize = offsetToAlignment(AlignedOffset, BoundaryAlignment);
+  }
+
   if (NewSize == BF.getSize())
     return false;
   BF.setSize(NewSize);
   Layout.invalidateFragmentsFrom(&BF);
   return true;
 }
 
 bool MCAssembler::relaxDwarfLineAddr(MCAsmLayout &Layout,

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

public:
   }
 
   operator uint8_t() const { return AlignBranchKind; }
   void addKind(X86::AlignBranchBoundaryKind Value) { AlignBranchKind |= Value; }
 };
 
 X86AlignBranchKind X86AlignBranchKindLoc;
 
+cl::opt<bool> X86AlignForMacroFusion(
+    "x86-align-for-macrofusion", cl::init(false),
+    cl::desc("Align cmp+jcc pairs to avoid the 64B boundary falling between "
+             "instructions, improving Macro-Op Fusion. May break assumptions "
+             "about labels corresponding to particular instructions, and "
+             "should be used with caution."));
+
 cl::opt<unsigned> X86AlignBranchBoundary(
     "x86-align-branch-boundary", cl::init(0),
     cl::desc(
         "Control how the assembler should align branches with NOP. If the "
         "boundary's size is not 0, it should be a power of 2 and no less "
         "than 32. Branches will be aligned to prevent from being across or "
         "against the boundary of specified size. The default value 0 does not "
         "align branches."));
class X86AsmBackend : public MCAsmBackend {
   MCInst PrevInst;
   MCBoundaryAlignFragment *PendingBA = nullptr;
   std::pair<MCFragment *, size_t> PrevInstPosition;
   bool CanPadInst;
 
   uint8_t determinePaddingPrefix(const MCInst &Inst) const;
   bool isMacroFused(const MCInst &Cmp, const MCInst &Jcc) const;
   bool needAlign(const MCInst &Inst) const;
+  bool needAlignEnd(const MCInst &Inst) const;
   bool canPadBranches(MCObjectStreamer &OS) const;
   bool canPadInst(const MCInst &Inst, MCObjectStreamer &OS) const;
 
 public:
   X86AsmBackend(const Target &T, const MCSubtargetInfo &STI)
       : MCAsmBackend(support::little), STI(STI),
         MCII(T.createMCInstrInfo()) {
     if (X86AlignBranchWithin32BBoundaries) {
       // At the moment, this defaults to aligning fused branches, unconditional
       // jumps, and (unfused) conditional jumps with nops.  Both the
       // instructions aligned and the alignment method (nop vs prefix) may
       // change in the future.
       AlignBoundary = assumeAligned(32);;
       AlignBranchType.addKind(X86::AlignBranchFused);
       AlignBranchType.addKind(X86::AlignBranchJcc);
       AlignBranchType.addKind(X86::AlignBranchJmp);
     }
+    if (X86AlignForMacroFusion) {
+      assert(!X86AlignBranchWithin32BBoundaries &&
+             "X86AlignForMacroFusion is incompatible with "
+             "X86AlignBranchWithin32BBoundaries");
+      AlignBoundary = assumeAligned(64);
+      AlignBranchType.addKind(X86::AlignMacroFusionCmp);
+      AlignBranchType.addKind(X86::AlignMacroFusionBranch);
+    }
     // Allow overriding defaults set by master flag
     if (X86AlignBranchBoundary.getNumOccurrences())
       AlignBoundary = assumeAligned(X86AlignBranchBoundary);
     if (X86AlignBranch.getNumOccurrences())
       AlignBranchType = X86AlignBranchKindLoc;
     if (X86PadMaxPrefixSize.getNumOccurrences())
       TargetPrefixMax = X86PadMaxPrefixSize;
   }
 
   bool allowAutoPadding() const override;
   bool allowEnhancedRelaxation() const override;
   void emitInstructionBegin(MCObjectStreamer &OS, const MCInst &Inst) override;
   void emitInstructionEnd(MCObjectStreamer &OS, const MCInst &Inst) override;
 
   unsigned getNumFixupKinds() const override {
     return X86::NumTargetFixupKinds;
   }
 
   Optional<MCFixupKind> getFixupKind(StringRef Name) const override;
 
   const MCFixupKindInfo &getFixupKindInfo(MCFixupKind Kind) const override;
 
   bool shouldForceRelocation(const MCAssembler &Asm, const MCFixup &Fixup,
                              const MCValue &Target) override;
 
   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 X86AsmBackend::canPadBranches(MCObjectStreamer &OS) const {
 
   // Branches only need to be aligned in 32-bit or 64-bit mode.
   if (!(STI.hasFeature(X86::Mode64Bit) || STI.hasFeature(X86::Mode32Bit)))
     return false;
 
   return true;
 }
 
+/// Check if the instruction is an eligible ending in an alignment pair.
+bool X86AsmBackend::needAlignEnd(const MCInst &Inst) const {
+  const MCInstrDesc &Desc = MCII->get(Inst.getOpcode());
+  return Desc.isConditionalBranch() &&
+         (AlignBranchType & X86::AlignMacroFusionBranch);
+}
+
 /// Check if the instruction operand needs to be aligned.
 bool X86AsmBackend::needAlign(const MCInst &Inst) const {
   const MCInstrDesc &Desc = MCII->get(Inst.getOpcode());
   return (Desc.isConditionalBranch() &&
           (AlignBranchType & X86::AlignBranchJcc)) ||
          (Desc.isUnconditionalBranch() &&
           (AlignBranchType & X86::AlignBranchJmp)) ||
          (Desc.isCall() && (AlignBranchType & X86::AlignBranchCall)) ||
void X86AsmBackend::emitInstructionBegin(MCObjectStreamer &OS,
 
   if (!CanPadInst)
     return;
 
   if (PendingBA && OS.getCurrentFragment()->getPrevNode() == PendingBA) {
     // Macro fusion actually happens and there is no other fragment inserted
     // after the previous instruction.
     //
-    // Do nothing here since we already inserted a BoudaryAlign fragment when
+    // Do nothing here since we already inserted a BoundaryAlign fragment when
     // we met the first instruction in the fused pair and we'll tie them
     // together in emitInstructionEnd.
     //
     // 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.
     return;
   }
 
-  if (needAlign(Inst) || ((AlignBranchType & X86::AlignBranchFused) &&
+  if (needAlign(Inst) || ((AlignBranchType & X86::AlignBranchFused ||
+                           AlignBranchType & X86::AlignMacroFusionCmp) &&
                           isFirstMacroFusibleInst(Inst, *MCII))) {
     // If we meet a unfused branch or the first instuction in a fusiable pair,
     // insert a BoundaryAlign fragment.
     OS.insert(PendingBA = new MCBoundaryAlignFragment(AlignBoundary));
+    if ((AlignBranchType & X86::AlignMacroFusionCmp) &&
+        isFirstMacroFusibleInst(Inst, *MCII))
+      PendingBA->setAvoidEndAlign(true);
   }
 }
 
 /// Set the last fragment to be aligned for the BoundaryAlignFragment.
 void X86AsmBackend::emitInstructionEnd(MCObjectStreamer &OS, const MCInst &Inst) {
   PrevInst = Inst;
   MCFragment *CF = OS.getCurrentFragment();
   PrevInstPosition = std::make_pair(CF, getSizeForInstFragment(CF));
   if (auto *F = dyn_cast_or_null<MCRelaxableFragment>(CF))
     F->setAllowAutoPadding(CanPadInst);
 
   if (!canPadBranches(OS))
     return;
 
-  if (!needAlign(Inst) || !PendingBA)
+  if (!(needAlign(Inst) || needAlignEnd(Inst)) || !PendingBA)
     return;
 
-  // Tie the aligned instructions into a a pending BoundaryAlign.
+  // Tie the aligned instructions into a pending BoundaryAlign.
   PendingBA->setLastFragment(CF);
   PendingBA = nullptr;
 
   // We need to ensure that further data isn't added to the current
   // DataFragment, so that we can get the size of instructions later in
   // MCAssembler::relaxBoundaryAlign. The easiest way is to insert a new empty
   // DataFragment.
   if (isa_and_nonnull<MCDataFragment>(CF))

llvm/lib/Target/X86/MCTargetDesc/X86BaseInfo.h

namespace X86 {
   /// Defines the possible values of the branch boundary alignment mask.
   enum AlignBranchBoundaryKind : uint8_t {
     AlignBranchNone = 0,
     AlignBranchFused = 1U << 0,
     AlignBranchJcc = 1U << 1,
     AlignBranchJmp = 1U << 2,
     AlignBranchCall = 1U << 3,
     AlignBranchRet = 1U << 4,
-    AlignBranchIndirect = 1U << 5
+    AlignBranchIndirect = 1U << 5,
+    AlignMacroFusionCmp = 1U << 6,
+    AlignMacroFusionBranch = 1U << 7
   };
 
   /// Defines the encoding values for segment override prefix.
   enum EncodingOfSegmentOverridePrefix : uint8_t {
     CS_Encoding = 0x2E,
     DS_Encoding = 0x3E,
     ES_Encoding = 0x26,
     FS_Encoding = 0x64,
namespace X86II {
   inline uint8_t getBaseOpcodeFor(uint64_t TSFlags) {
     return TSFlags >> X86II::OpcodeShift;
   }
 
   inline bool hasImm(uint64_t TSFlags) {
     return (TSFlags & X86II::ImmMask) != 0;
   }
 
-  /// Decode the "size of immediate" field from the TSFlags field of the 
+  /// Decode the "size of immediate" field from the TSFlags field of the
   /// specified instruction.
   inline unsigned getSizeOfImm(uint64_t TSFlags) {
     switch (TSFlags & X86II::ImmMask) {
     default: llvm_unreachable("Unknown immediate size");
     case X86II::Imm8:
     case X86II::Imm8PCRel:
     case X86II::Imm8Reg:    return 1;
     case X86II::Imm16:

llvm/test/MC/X86/x86_64-auto-mf-align.s

+# RUN: llvm-mc -triple=x86_64 -x86-align-for-macrofusion %s -filetype=obj | llvm-objdump --no-show-raw-insn -d - | FileCheck %s
+
+# no padding is expected since test doesn't end at alignment boundary:
+# CHECK-NOT: nop
+  testl %eax, %eax
+# CHECK: testl %eax, %eax
+  je  .LBB0
+
+.nops 57
+  int3
+# BoundaryAlign followed by MCDataFragment:
+# inserts nop because `test` would end at alignment boundary:
+# CHECK:      3e: nop
+  testl %eax, %eax
+# CHECK-NEXT: 3f: testl %eax, %eax
+  je  .LBB0
+# CHECK-NEXT: 41: je
+.LBB0:
+  retq
+
+.p2align 6
+.L0:
+.nops 57
+  int3
+# BoundaryAlign followed by RelaxableFragment:
+# CHECK:      ba: nop
+  cmpl $(.L1-.L0), %eax
+# CHECK-NEXT: bb: cmpl
+  je  .L0
+# CHECK-NEXT: c1: je
+.nops 65
+.L1: