[llvm-exegesis] Explore LEA addressing modes.

[courbet]

Summary

This will help for PR32326.

This shows the well-known issue with RBP and R13 as base registers.

[courbet]

Example results for uops on HSW:

lea_hsw_uops.html975 KBDownload

[gchatelet]

llvm/tools/llvm-exegesis/lib/RegisterAliasing.h

106

Why not implement it this way ? Is this because of knowledge that B has few bits set?

llvm/tools/llvm-exegesis/lib/X86/Target.cpp

181

typo

217

You should provide a rationale for why only {0, 42}

[courbet]

Address comments

[courbet]

Thanks !

llvm/tools/llvm-exegesis/lib/RegisterAliasing.h

106

Right, this warrants a comment. Done.

llvm/test/tools/llvm-exegesis/X86/latency-LEA64r.s

+# RUN: llvm-exegesis -mode=latency -opcode-name=LEA64r -repetition-mode=duplicate -max-configs-per-opcode=2 | FileCheck %s
+# RUN: llvm-exegesis -mode=latency -opcode-name=LEA64r -repetition-mode=loop -max-configs-per-opcode=2 | FileCheck %s
+
+CHECK:      ---
+CHECK-NEXT: mode: latency
+CHECK-NEXT: key:
+CHECK-NEXT:   instructions:
+CHECK-NEXT:     LEA64r
+CHECK-NEXT: config: '0(%[[REG1:[A-Z0-9]+]], %[[REG1]], 1)'
+
+CHECK:      ---
+CHECK-NEXT: mode: latency
+CHECK-NEXT: key:
+CHECK-NEXT:   instructions:
+CHECK-NEXT:     LEA64r
+CHECK-NEXT: config: '42(%[[REG2:[A-Z0-9]+]], %[[REG2]], 1)'

llvm/test/tools/llvm-exegesis/X86/uops-LEA64r.s

+# RUN: llvm-exegesis -mode=uops -opcode-name=LEA64r -repetition-mode=duplicate -max-configs-per-opcode=2 | FileCheck %s
+# RUN: llvm-exegesis -mode=uops -opcode-name=LEA64r -repetition-mode=loop -max-configs-per-opcode=2 | FileCheck %s
+
+CHECK:      ---
+CHECK-NEXT: mode: uops
+CHECK-NEXT: key:
+CHECK-NEXT:   instructions:
+CHECK-NEXT:     LEA64r
+CHECK-NEXT: config: '0(%[[REG1:[A-Z0-9]+]], %[[REG2:[A-Z0-9]+]], 1)'
+
+CHECK:      ---
+CHECK-NEXT: mode: uops
+CHECK-NEXT: key:
+CHECK-NEXT:   instructions:
+CHECK-NEXT:     LEA64r
+CHECK-NEXT: config: '42(%[[REG3:[A-Z0-9]+]], %[[REG4:[A-Z0-9]+]], 1)'

llvm/tools/llvm-exegesis/lib/RegisterAliasing.h

private:
   const llvm::BitVector ReservedReg;
   const llvm::BitVector EmptyRegisters;
   mutable std::unordered_map<unsigned, std::unique_ptr<RegisterAliasingTracker>>
       Registers;
   mutable std::unordered_map<unsigned, std::unique_ptr<RegisterAliasingTracker>>
       RegisterClasses;
 };
 
+// `a = a & ~b`, optimized for few bit sets in B and no allocation.
+inline void remove(llvm::BitVector &A, const llvm::BitVector &B) {
+  assert(A.size() == B.size());
+  for (auto I : B.set_bits())
+    A.reset(I);
+}
+
 } // namespace exegesis
 } // namespace llvm
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_ALIASINGTRACKER_H

llvm/tools/llvm-exegesis/lib/Uops.cpp

 getVariablesWithTiedOperands(const Instruction &Instr) {
   llvm::SmallVector<const Variable *, 8> Result;
   for (const auto &Var : Instr.Variables)
     if (Var.hasTiedOperands())
       Result.push_back(&Var);
   return Result;
 }
 
-static void remove(llvm::BitVector &a, const llvm::BitVector &b) {
-  assert(a.size() == b.size());
-  for (auto I : b.set_bits())
-    a.reset(I);
-}
-
 UopsBenchmarkRunner::~UopsBenchmarkRunner() = default;
 
 UopsSnippetGenerator::~UopsSnippetGenerator() = default;
 
 void UopsSnippetGenerator::instantiateMemoryOperands(
     const unsigned ScratchSpacePointerInReg,
     std::vector<InstructionTemplate> &Instructions) const {
   if (ScratchSpacePointerInReg == 0)

llvm/tools/llvm-exegesis/lib/X86/Target.cpp

 #include "../SnippetGenerator.h"
 #include "../Uops.h"
 #include "MCTargetDesc/X86BaseInfo.h"
 #include "MCTargetDesc/X86MCTargetDesc.h"
 #include "X86.h"
 #include "X86RegisterInfo.h"
 #include "X86Subtarget.h"
 #include "llvm/MC/MCInstBuilder.h"
+#include "llvm/Support/FormatVariadic.h"
 
 namespace llvm {
 namespace exegesis {
 
 // Returns an error if we cannot handle the memory references in this
 // instruction.
 static Error isInvalidMemoryInstr(const Instruction &Instr) {
   switch (Instr.Description->TSFlags & X86II::FormMask) {
if (Op.isReg() && Op.isExplicit() &&
           "unsupported second-form X87 instruction");
   return llvm::Error::success();
 }
 
 static unsigned getX86FPFlags(const Instruction &Instr) {
   return Instr.Description->TSFlags & llvm::X86II::FPTypeMask;
 }
 
+// Helper to fill a memory operand with a value.
+static void setMemOp(InstructionTemplate &IT, int OpIdx,
+                     const MCOperand &OpVal) {
+  const auto Op = IT.Instr.Operands[OpIdx];
+  assert(Op.isExplicit() && "invalid memory pattern");
+  IT.getValueFor(Op) = OpVal;
+};
+
+// Common (latency, uops) code for LEA templates. `GetDestReg` takes the
+// addressing base and index registers and returns the LEA destination register.
+static llvm::Expected<std::vector<CodeTemplate>> generateLEATemplatesCommon(
+    const Instruction &Instr, const BitVector &ForbiddenRegisters,
+    const LLVMState &State, const SnippetGenerator::Options &Opts,
+    std::function<unsigned(unsigned, unsigned)> GetDestReg) {
+  assert(Instr.Operands.size() == 6 && "invalid LEA");
+  assert(X86II::getMemoryOperandNo(Instr.Description->TSFlags) == 1 &&
+         "invalid LEA");
+
+  constexpr const int kDestOp = 0;
+  constexpr const int kBaseOp = 1;
+  constexpr const int kIndexOp = 3;
+  auto PossibleDestRegs =
+      Instr.Operands[kDestOp].getRegisterAliasing().sourceBits();
+  remove(PossibleDestRegs, ForbiddenRegisters);
+  auto PossibleBaseRegs =
+      Instr.Operands[kBaseOp].getRegisterAliasing().sourceBits();
+  remove(PossibleBaseRegs, ForbiddenRegisters);
+  auto PossibleIndexRegs =
+      Instr.Operands[kIndexOp].getRegisterAliasing().sourceBits();
+  remove(PossibleIndexRegs, ForbiddenRegisters);
+
+  const auto &RegInfo = State.getRegInfo();
+  std::vector<CodeTemplate> Result;
+  for (const unsigned BaseReg : PossibleBaseRegs.set_bits()) {
+    for (const unsigned IndexReg : PossibleIndexRegs.set_bits()) {
+      for (int LogScale = 0; LogScale <= 3; ++LogScale) {
+        // FIXME: Add an option for controlling how we explore immediates.
+        for (const int Disp : {0, 42}) {
+          InstructionTemplate IT(Instr);
+          const int64_t Scale = 1ull << LogScale;
+          setMemOp(IT, 1, MCOperand::createReg(BaseReg));
+          setMemOp(IT, 2, MCOperand::createImm(Scale));
+          setMemOp(IT, 3, MCOperand::createReg(IndexReg));
+          setMemOp(IT, 4, MCOperand::createImm(Disp));
+          // SegmentReg must be 0 for LEA.
+          setMemOp(IT, 5, MCOperand::createReg(0));
+
+          // Output reg is selected by the caller.
+          setMemOp(IT, 0, MCOperand::createReg(GetDestReg(BaseReg, IndexReg)));
+
+          CodeTemplate CT;
+          CT.Instructions.push_back(std::move(IT));
+          CT.Config = formatv("{3}(%{0}, %{1}, {2})", RegInfo.getName(BaseReg),
+                              RegInfo.getName(IndexReg), Scale, Disp)
+                          .str();
+          Result.push_back(std::move(CT));
+          if (Result.size() >= Opts.MaxConfigsPerOpcode)
+            return Result;
+        }
+      }
+    }
+  }
+
+  return Result;
+}
+
 namespace {
 class X86LatencySnippetGenerator : public LatencySnippetGenerator {
 public:
   using LatencySnippetGenerator::LatencySnippetGenerator;
 
   llvm::Expected<std::vector<CodeTemplate>>
   generateCodeTemplates(const Instruction &Instr,
                         const BitVector &ForbiddenRegisters) const override;
 };
 } // namespace
 
 llvm::Expected<std::vector<CodeTemplate>>
 X86LatencySnippetGenerator::generateCodeTemplates(
     const Instruction &Instr, const BitVector &ForbiddenRegisters) const {
   if (auto E = IsInvalidOpcode(Instr))
     return std::move(E);
 
+  // LEA gets special attention.
+  const auto Opcode = Instr.Description->getOpcode();
+  if (Opcode == X86::LEA64r || Opcode == X86::LEA64_32r) {
+    return generateLEATemplatesCommon(Instr, ForbiddenRegisters, State, Opts,
+                                      [](unsigned BaseReg, unsigned IndexReg) {
+                                        // We just select the same base and
+                                        // output register.
+                                        return BaseReg;
+                                      });
+  }
+
   switch (getX86FPFlags(Instr)) {
   case llvm::X86II::NotFP:
     return LatencySnippetGenerator::generateCodeTemplates(Instr,
                                                           ForbiddenRegisters);
   case llvm::X86II::ZeroArgFP:
   case llvm::X86II::OneArgFP:
   case llvm::X86II::SpecialFP:
   case llvm::X86II::CompareFP:

 class X86UopsSnippetGenerator : public UopsSnippetGenerator {
 public:
   using UopsSnippetGenerator::UopsSnippetGenerator;
 
   llvm::Expected<std::vector<CodeTemplate>>
   generateCodeTemplates(const Instruction &Instr,
                         const BitVector &ForbiddenRegisters) const override;
 };
+
 } // namespace
 
 llvm::Expected<std::vector<CodeTemplate>>
 X86UopsSnippetGenerator::generateCodeTemplates(
     const Instruction &Instr, const BitVector &ForbiddenRegisters) const {
   if (auto E = IsInvalidOpcode(Instr))
     return std::move(E);
 
+  // LEA gets special attention.
+  const auto Opcode = Instr.Description->getOpcode();
+  if (Opcode == X86::LEA64r || Opcode == X86::LEA64_32r) {
+    // Any destination register that is not used for adddressing is fine.
+    auto PossibleDestRegs =
+        Instr.Operands[0].getRegisterAliasing().sourceBits();
+    remove(PossibleDestRegs, ForbiddenRegisters);
+    return generateLEATemplatesCommon(
+        Instr, ForbiddenRegisters, State, Opts,
+        [this, &PossibleDestRegs](unsigned BaseReg, unsigned IndexReg) {
+          auto PossibleDestRegsNow = PossibleDestRegs;
+          remove(PossibleDestRegsNow,
+                 State.getRATC().getRegister(BaseReg).aliasedBits());
+          remove(PossibleDestRegsNow,
+                 State.getRATC().getRegister(IndexReg).aliasedBits());
+          assert(PossibleDestRegsNow.set_bits().begin() !=
+                     PossibleDestRegsNow.set_bits().end() &&
+                 "no remaining registers");
+          return *PossibleDestRegsNow.set_bits().begin();
+        });
+  }
+
   switch (getX86FPFlags(Instr)) {
   case llvm::X86II::NotFP:
     return UopsSnippetGenerator::generateCodeTemplates(Instr,
                                                        ForbiddenRegisters);
   case llvm::X86II::ZeroArgFP:
   case llvm::X86II::OneArgFP:
   case llvm::X86II::SpecialFP:
     return llvm::make_error<Failure>("Unsupported x87 Instruction");
void ExegesisX86Target::fillMemoryOperands(InstructionTemplate &IT,
   assert(MemOpIdx >= 0 && "invalid memory operand index");
   // getMemoryOperandNo() ignores tied operands, so we have to add them back.
   for (unsigned I = 0; I <= static_cast<unsigned>(MemOpIdx); ++I) {
     const auto &Op = IT.Instr.Operands[I];
     if (Op.isTied() && Op.getTiedToIndex() < I) {
       ++MemOpIdx;
     }
   }
-  // Now fill in the memory operands.
-  const auto SetOp = [&IT](int OpIdx, const MCOperand &OpVal) {
-    const auto Op = IT.Instr.Operands[OpIdx];
-    assert(Op.isMemory() && Op.isExplicit() && "invalid memory pattern");
-    IT.getValueFor(Op) = OpVal;
-  };
-  SetOp(MemOpIdx + 0, MCOperand::createReg(Reg));    // BaseReg
-  SetOp(MemOpIdx + 1, MCOperand::createImm(1));      // ScaleAmt
-  SetOp(MemOpIdx + 2, MCOperand::createReg(0));      // IndexReg
-  SetOp(MemOpIdx + 3, MCOperand::createImm(Offset)); // Disp
-  SetOp(MemOpIdx + 4, MCOperand::createReg(0));      // Segment
+  setMemOp(IT, MemOpIdx + 0, MCOperand::createReg(Reg));    // BaseReg
+  setMemOp(IT, MemOpIdx + 1, MCOperand::createImm(1));      // ScaleAmt
+  setMemOp(IT, MemOpIdx + 2, MCOperand::createReg(0));      // IndexReg
+  setMemOp(IT, MemOpIdx + 3, MCOperand::createImm(Offset)); // Disp
+  setMemOp(IT, MemOpIdx + 4, MCOperand::createReg(0));      // Segment
 }
 
 void ExegesisX86Target::decrementLoopCounterAndJump(
     MachineBasicBlock &MBB, MachineBasicBlock &TargetMBB,
     const llvm::MCInstrInfo &MII) const {
   BuildMI(&MBB, DebugLoc(), MII.get(X86::ADD64ri8))
       .addDef(kLoopCounterReg)
       .addUse(kLoopCounterReg)