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

752

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

848–851

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 redundant 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 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 (!shouldAddPrefix(RF.getInst(), *MCII))
+    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;
+}
+
 static bool canBeRelaxedForPadding(const MCRelaxableFragment &RF) {
   // TODO: There are lots of other tricks we could apply for increasing
   // encoding size without impacting performance.
   auto &Inst = RF.getInst();
   auto &STI = *RF.getSubtargetInfo();
   bool Is16BitMode = STI.getFeatureBits()[X86::Mode16Bit];
   return getRelaxedOpcode(Inst, Is16BitMode) != Inst.getOpcode();
 }
 
-bool X86AsmBackend::padInstructionEncoding(MCRelaxableFragment &RF,
+bool X86AsmBackend::padInstructionViaRelaxation(MCRelaxableFragment &RF,
                                                 MCCodeEmitter &Emitter,
                                                 unsigned &RemainingSize) const {
   if (!canBeRelaxedForPadding(RF))
     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.
   if (!X86PadForAlign && !X86PadForBranchAlign)
     return;
 
   DenseSet<MCFragment *> LabeledFragments;
   for (const MCSymbol &S : Asm.symbols())
     LabeledFragments.insert(S.getFragment(false));
 
   for (MCSection &Sec : Asm) {
     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))

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 %s -x86-pad-max-prefix-size=5 | 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
+  # CHECK: 0: eb 1f                          jmp
+  # CHECK: 2: eb 1d                          jmp
+  # CHECK: 4: eb 1b                          jmp
+  # CHECK: 6: eb 19                          jmp
+  # CHECK: 8: 2e 2e eb 15                    jmp
+  # CHECK: c: 2e 2e 2e 2e 2e e9 0b 00 00 00  jmp
+  # CHECK: 16: 2e 2e 2e 2e 2e e9 01 00 00 00 jmp
+  # CHECK: 20: cc                            int3
   .p2align 4
   jmp foo
   jmp foo
   jmp foo
   jmp foo
   jmp foo
   jmp foo
   jmp foo
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: 48: 2e 2e 2e 2e 0f 8e 1e 00 00 00  jle 30 <loop_exit>
+  # CHECK: 52: 66 2e 0f 1f 84 00 00 00 00 00  nopw  %cs:(%rax,%rax)
+  # CHECK: 5c: 0f 1f 40 00                    nopl  (%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: 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