Support prefix padding for alignment purposes (Relaxable instructions only)

[reames]

Summary

Now that D75203 has landed and baked for a few days, extend the basic approach to prefix padding as well. The patch itself is fairly straight forward.

I did hit a small snag which is that we don't really have a good model for how many prefixes are safe to add with the current information. I'd planned to use the nop length information as a proxy, but it appears that this has never been updated for modern Intels. I haven't investigated to figure out why just yet.

For the moment, this patch adds the functional support and some basic testing there of, but defaults to not enabling prefix padding. I want to be able to phrase a separate patch which adds the target specific reasoning and test it cleanly. I haven't decided whether I want to common it with the nop logic or not.

[reames]

Rebase on recently landed patches, haven't yet addressed major todos.

[skan]

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

768

uint8_t TargetPrefixMax = static_cast<uint8_t>(X86PadMaxPrefixSize)

[reames]

Address review comment

[skan]

Encountered a compile error when building SPEC with option -fno-lto -mllvm --x86-align-branch-boundary=32 -mllvm -x86-align-branch=fused+jcc+jmp -mllvm -x86-pad-max-prefix-size=5.

fatal error: error in backend: value of -130 is too large for field of 1 byte.

This error is reported when applying fixups

void X86AsmBackend::applyFixup(const MCAssembler &Asm, const MCFixup &Fixup,
                               const MCValue &Target,
                               MutableArrayRef<char> Data,
                               uint64_t Value, bool IsResolved,
                               const MCSubtargetInfo *STI) const {
  unsigned Size = getFixupKindSize(Fixup.getKind());

  assert(Fixup.getOffset() + Size <= Data.size() && "Invalid fixup offset!");

  int64_t SignedValue = static_cast<int64_t>(Value);
  if ((Target.isAbsolute() || IsResolved) &&
      getFixupKindInfo(Fixup.getKind()).Flags &
      MCFixupKindInfo::FKF_IsPCRel) {
    // check that PC relative fixup fits into the fixup size.
    if (Size > 0 && !isIntN(Size * 8, SignedValue))
      Asm.getContext().reportError(
                                   Fixup.getLoc(), "value of " + Twine(SignedValue) +
                                   " is too large for field of " + Twine(Size) +
                                   ((Size == 1) ? " byte." : " bytes."));

[reames]

SKan, any chance you could bugpoint the failing IR? Having to setup a full clang and SPEC build to reproduce will be very time intensive.

[skan]

In D75300#1916196, @reames wrote:

SKan, any chance you could bugpoint the failing IR? Having to setup a full clang and SPEC build to reproduce will be very time intensive.

I have minimized the test case

  .text
.L1:
.rept 126
  int3
.endr
  jmp .L1
.rept 30
  int3
.endr
.p2align 5

Compile this with command

clang "-cc1as" "-triple" "x86_64-unknown-linux-gnu" "-filetype" "obj" "-main-file-name" "toke.s" "-target-cpu" "x86-64" "-mllvm" "-x86-pad-max-prefix-size=5" "-o" "test.o" "test.s"

and you would get the error

test.s:8:3: error: value of -130 is too large for field of 1 byte.
  jmp .L1

Reason of failure:
In this patch, we try to relax the instruction first and then try to add prefixes to it, which makes the jmp require a larger negative offset than it can encode.

[reames]

Address bug found by skan. Doing so unfortunately limits the scope quite a bit, but getting access to the value for the fixup will require a bit of redesign. I would much prefer to get the reduced scope version enabled, and then broaden the scope with testing in place.

[reames]

Use the proper diff command this time...

[skan]

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

804–807

I'm not sure only checking FKF_IsPCRel here is safe enough, since the logic in X86AsmBackend::applyFixup also checks whether the value can fit in the fixup field when kind of fixup is not FKF_IsPCRel. Can we return false directly if !isFullyRelaxed(RF)?

[reames]

Per review comment, be more conservative about non-fully relaxed instructions.

I think the previous code was in fact correct, but given it doesn't help any practical test I know of, being super conservative is reasonable for now.

Can I get an LGTM on this?

[skan]

In D75300#1921757, @reames wrote:

Per review comment, be more conservative about non-fully relaxed instructions.

I think the previous code was in fact correct, but given it doesn't help any practical test I know of, being super conservative is reasonable for now.

Can I get an LGTM on this?

I am running some tests for this patch, I will give it a LGTM once the tests are done.

[skan]

I applied this patch and found no new fail for SPEC.

[skan]

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

110

Before landing this patch, could you make this description better? I don't think the word "redundant" is appropriate here since X86PadMaxPrefixSize counts in the existing prefixes of the instructions，which may be useful, e.g. escape prefix.

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

 cl::opt<bool> X86AlignBranchWithin32BBoundaries(
     "x86-branches-within-32B-boundaries", cl::init(false),
     cl::desc(
         "Align selected instructions to mitigate negative performance impact "
         "of Intel's micro code update for errata skx102.  May break "
         "assumptions about labels corresponding to particular instructions, "
         "and should be used with caution."));
 
+cl::opt<unsigned> X86PadMaxPrefixSize(
+    "x86-pad-max-prefix-size", cl::init(0),
+    cl::desc("Maximum number of prefixes to use for padding"));
+
 cl::opt<bool> X86PadForAlign(
     "x86-pad-for-align", cl::init(true), cl::Hidden,
     cl::desc("Pad previous instructions to implement align directives"));
 
 cl::opt<bool> X86PadForBranchAlign(
     "x86-pad-for-branch-align", cl::init(true), cl::Hidden,
     cl::desc("Pad previous instructions to implement branch alignment"));
 
public:
 
   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 padInstructionViaRelaxation(MCRelaxableFragment &RF,
+                                   MCCodeEmitter &Emitter,
+                                   unsigned &RemainingSize) const;
+
+  bool padInstructionViaPrefix(MCRelaxableFragment &RF, MCCodeEmitter &Emitter,
+                               unsigned &RemainingSize) const;
+
   bool padInstructionEncoding(MCRelaxableFragment &RF, MCCodeEmitter &Emitter,
                               unsigned &RemainingSize) const;
+
   void finishLayout(MCAssembler const &Asm, MCAsmLayout &Layout) const override;
 
   bool writeNopData(raw_ostream &OS, uint64_t Count) const override;
 };
 } // end anonymous namespace
 
 static unsigned getRelaxedOpcodeBranch(const MCInst &Inst, bool Is16BitMode) {
   unsigned Op = Inst.getOpcode();
if (RelaxedOp == Inst.getOpcode()) {
     OS << "\n";
     report_fatal_error("unexpected instruction to relax: " + OS.str());
   }
 
   Res = Inst;
   Res.setOpcode(RelaxedOp);
 }
 
-static bool canBeRelaxedForPadding(const MCRelaxableFragment &RF) {
-  // TODO: There are lots of other tricks we could apply for increasing
-  // encoding size without impacting performance.
+/// Return true if this instruction has been fully relaxed into it's most
+/// general available form.
+static bool isFullyRelaxed(const MCRelaxableFragment &RF) {
   auto &Inst = RF.getInst();
   auto &STI = *RF.getSubtargetInfo();
   bool Is16BitMode = STI.getFeatureBits()[X86::Mode16Bit];
-  return getRelaxedOpcode(Inst, Is16BitMode) != Inst.getOpcode();
+  return getRelaxedOpcode(Inst, Is16BitMode) == Inst.getOpcode();
 }
 
-bool X86AsmBackend::padInstructionEncoding(MCRelaxableFragment &RF,
+
+static bool shouldAddPrefix(const MCInst &Inst, const MCInstrInfo &MCII) {
+  // Linker may rewrite the instruction with variant symbol operand.
+  return !hasVariantSymbol(Inst);
+}
+
+static unsigned getRemainingPrefixSize(const MCInst &Inst,
+                                       const MCSubtargetInfo &STI,
+                                       MCCodeEmitter &Emitter) {
+  SmallString<256> Code;
+  raw_svector_ostream VecOS(Code);
+  Emitter.emitPrefix(Inst, VecOS, STI);
+  assert(Code.size() < 15 && "The number of prefixes must be less than 15.");
+
+  // TODO: It turns out we need a decent amount of plumbing for the target
+  // specific bits to determine number of prefixes its safe to add.  Various
+  // targets (older chips mostly, but also Atom family) encounter decoder
+  // stalls with too many prefixes.  For testing purposes, we set the value
+  // externally for the moment.
+  unsigned ExistingPrefixSize = Code.size();
+  unsigned TargetPrefixMax = X86PadMaxPrefixSize;
+  if (TargetPrefixMax <= ExistingPrefixSize)
+    return 0;
+  return TargetPrefixMax - ExistingPrefixSize;
+}
+
+bool X86AsmBackend::padInstructionViaPrefix(MCRelaxableFragment &RF,
                                             MCCodeEmitter &Emitter,
                                             unsigned &RemainingSize) const {
-  if (!canBeRelaxedForPadding(RF))
+  if (!shouldAddPrefix(RF.getInst(), *MCII))
+    return false;
+  // If the instruction isn't fully relaxed, shifting it around might require a
+  // larger value for one of the fixups then can be encoded.  The outer loop
+  // will also catch this before moving to the next instruction, but we need to
+  // prevent padding this single instruction as well.
+  if (!isFullyRelaxed(RF))
+    return false;
+
+  const unsigned OldSize = RF.getContents().size();
+  if (OldSize == 15)
+    return false;
+
+  const unsigned MaxPossiblePad = std::min(15 - OldSize, RemainingSize);
+  const unsigned PrefixBytesToAdd =
+    std::min(MaxPossiblePad,
+             getRemainingPrefixSize(RF.getInst(), STI, Emitter));
+  if (PrefixBytesToAdd == 0)
+    return false;
+
+  const uint8_t Prefix = determinePaddingPrefix(RF.getInst());
+
+  SmallString<256> Code;
+  Code.append(PrefixBytesToAdd, Prefix);
+  Code.append(RF.getContents().begin(), RF.getContents().end());
+  RF.getContents() = Code;
+
+  // Adjust the fixups for the change in offsets
+  for (auto &F : RF.getFixups()) {
+    F.setOffset(F.getOffset() + PrefixBytesToAdd);
+  }
+
+  RemainingSize -= PrefixBytesToAdd;
+  return true;
+}
+
+bool X86AsmBackend::padInstructionViaRelaxation(MCRelaxableFragment &RF,
+                                                MCCodeEmitter &Emitter,
+                                                unsigned &RemainingSize) const {
+  if (isFullyRelaxed(RF))
+    // TODO: There are lots of other tricks we could apply for increasing
+    // encoding size without impacting performance.
     return false;
 
   MCInst Relaxed;
   relaxInstruction(RF.getInst(), *RF.getSubtargetInfo(), Relaxed);
 
   SmallVector<MCFixup, 4> Fixups;
   SmallString<15> Code;
   raw_svector_ostream VecOS(Code);
   Emitter.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)
     return false;
   RF.setInst(Relaxed);
   RF.getContents() = Code;
   RF.getFixups() = Fixups;
   RemainingSize -= Delta;
   return true;
 }
 
+bool X86AsmBackend::padInstructionEncoding(MCRelaxableFragment &RF,
+                                           MCCodeEmitter &Emitter,
+                                           unsigned &RemainingSize) const {
+  bool Changed = false;
+  if (RemainingSize != 0)
+    Changed |= padInstructionViaRelaxation(RF, Emitter, RemainingSize);
+  if (RemainingSize != 0)
+    Changed |= padInstructionViaPrefix(RF, Emitter, RemainingSize);
+  return Changed;
+}
+
 void X86AsmBackend::finishLayout(MCAssembler const &Asm,
                                  MCAsmLayout &Layout) const {
   // 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.  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.
#endif
           FirstChangedFragment = &RF;
 
         // If we have an instruction which hasn't been fully relaxed, we can't
         // skip past it and insert bytes before it.  Changing its 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.
-        if (mayNeedRelaxation(RF.getInst(), *RF.getSubtargetInfo()))
+        if (!isFullyRelaxed(RF))
           break;
       }
       Relaxable.clear();
 
       if (FirstChangedFragment) {
         // Make sure the offsets for any fragments in the effected range get
         // updated.  Note that this (conservatively) invalidates the offsets of
         // those following, but this is not required.

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

+# RUN: llvm-mc -mcpu=skylake -filetype=obj -triple x86_64-pc-linux-gnu %s -x86-pad-max-prefix-size=5 | llvm-objdump -d --section=.text - | FileCheck %s
+
+# This test file highlights the interactions between prefix padding and
+# relaxation padding.
+
+  .file "test.c"
+  .text
+  .section  .text
+  # We can both relax and prefix for padding purposes, but the moment, we
+  # can't prefix without first having relaxed.
+  # CHECK: .text
+  # CHECK:  0: eb 1f                         jmp
+  # CHECK:  2: eb 1d                         jmp
+  # CHECK:  4: eb 1b                         jmp
+  # CHECK:  6: eb 19                         jmp
+  # CHECK:  8: eb 17                         jmp
+  # CHECK:  a: 2e 2e 2e 2e 2e e9 0d 00 00 00 jmp
+  # CHECK: 14: 2e 2e 2e 2e 2e e9 03 00 00 00 jmp
+  # CHECK: 1e: 66 90                         nop
+  # 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
+
+  # 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: 2e 2e 2e 2e 0f 8e 1e 00 00 00  jle 30 <loop_exit>
+  # CHECK: 52: 66 66 66 66 66 2e 0f 1f 84 00 00 00 00 00      nopw  %cs:(%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: 2e 2e e9 f0 ff ff ff           jmp
+  # 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
+
+  # Correctness cornercase - can't prefix pad jmp without having relaxed it
+  # first as doing so would make the relative offset too large
+  # CHECK: fd: cc                             int3
+  # CHECK: fe: eb 80                          jmp -128 <loop_exit+0x10>
+  # CHECK: 100: cc                            int3
+.p2align 5
+.L1:
+.rept 126
+  int3
+.endr
+  jmp .L1
+.rept 30
+  int3
+.endr
+.p2align 5

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
+# RUN: llvm-mc -mcpu=skylake -filetype=obj -triple x86_64-pc-linux-gnu -x86-pad-max-prefix-size=0 %s | llvm-objdump -d --section=.text - | FileCheck %s
 
+# This test exercises only the padding via relaxation logic.  The  interaction
+# etween prefix padding and relaxation logic can be seen in align-via-padding.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>