tools/llvm-exegesis/lib/Uops.cpp

   1 //===-- Uops.cpp ------------------------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "Uops.h"
  10
  11 #include "Assembler.h"
  12 #include "BenchmarkRunner.h"
  13 #include "MCInstrDescView.h"
  14 #include "Target.h"
  15
  16 // FIXME: Load constants into registers (e.g. with fld1) to not break
  17 // instructions like x87.
  18
  19 // Ideally we would like the only limitation on executing uops to be the issue
  20 // ports. Maximizing port pressure increases the likelihood that the load is
  21 // distributed evenly across possible ports.
  22
  23 // To achieve that, one approach is to generate instructions that do not have
  24 // data dependencies between them.
  25 //
  26 // For some instructions, this is trivial:
  27 //    mov rax, qword ptr [rsi]
  28 //    mov rax, qword ptr [rsi]
  29 //    mov rax, qword ptr [rsi]
  30 //    mov rax, qword ptr [rsi]
  31 // For the above snippet, haswell just renames rax four times and executes the
  32 // four instructions two at a time on P23 and P0126.
  33 //
  34 // For some instructions, we just need to make sure that the source is
  35 // different from the destination. For example, IDIV8r reads from GPR and
  36 // writes to AX. We just need to ensure that the Var is assigned a
  37 // register which is different from AX:
  38 //    idiv bx
  39 //    idiv bx
  40 //    idiv bx
  41 //    idiv bx
  42 // The above snippet will be able to fully saturate the ports, while the same
  43 // with ax would issue one uop every `latency(IDIV8r)` cycles.
  44 //
  45 // Some instructions make this harder because they both read and write from
  46 // the same register:
  47 //    inc rax
  48 //    inc rax
  49 //    inc rax
  50 //    inc rax
  51 // This has a data dependency from each instruction to the next, limit the
  52 // number of instructions that can be issued in parallel.
  53 // It turns out that this is not a big issue on recent Intel CPUs because they
  54 // have heuristics to balance port pressure. In the snippet above, subsequent
  55 // instructions will end up evenly distributed on {P0,P1,P5,P6}, but some CPUs
  56 // might end up executing them all on P0 (just because they can), or try
  57 // avoiding P5 because it's usually under high pressure from vector
  58 // instructions.
  59 // This issue is even more important for high-latency instructions because
  60 // they increase the idle time of the CPU, e.g. :
  61 //    imul rax, rbx
  62 //    imul rax, rbx
  63 //    imul rax, rbx
  64 //    imul rax, rbx
  65 //
  66 // To avoid that, we do the renaming statically by generating as many
  67 // independent exclusive assignments as possible (until all possible registers
  68 // are exhausted) e.g.:
  69 //    imul rax, rbx
  70 //    imul rcx, rbx
  71 //    imul rdx, rbx
  72 //    imul r8,  rbx
  73 //
  74 // Some instruction even make the above static renaming impossible because
  75 // they implicitly read and write from the same operand, e.g. ADC16rr reads
  76 // and writes from EFLAGS.
  77 // In that case we just use a greedy register assignment and hope for the
  78 // best.
  79
  80 namespace llvm {
  81 namespace exegesis {
  82
  83 static llvm::SmallVector<const Variable *, 8>
  84 getVariablesWithTiedOperands(const Instruction &Instr) {
  85   llvm::SmallVector<const Variable *, 8> Result;
  86   for (const auto &Var : Instr.Variables)
  87     if (Var.hasTiedOperands())
  88       Result.push_back(&Var);
  89   return Result;
  90 }
  91
  92 static void remove(llvm::BitVector &a, const llvm::BitVector &b) {
  93   assert(a.size() == b.size());
  94   for (auto I : b.set_bits())
  95     a.reset(I);
  96 }
  97
  98 UopsBenchmarkRunner::~UopsBenchmarkRunner() = default;
  99
 100 UopsSnippetGenerator::~UopsSnippetGenerator() = default;
 101
 102 void UopsSnippetGenerator::instantiateMemoryOperands(
 103     const unsigned ScratchSpacePointerInReg,
 104     std::vector<InstructionTemplate> &Instructions) const {
 105   if (ScratchSpacePointerInReg == 0)
 106     return; // no memory operands.
 107   const auto &ET = State.getExegesisTarget();
 108   const unsigned MemStep = ET.getMaxMemoryAccessSize();
 109   const size_t OriginalInstructionsSize = Instructions.size();
 110   size_t I = 0;
 111   for (InstructionTemplate &IT : Instructions) {
 112     ET.fillMemoryOperands(IT, ScratchSpacePointerInReg, I * MemStep);
 113     ++I;
 114   }
 115
 116   while (Instructions.size() < kMinNumDifferentAddresses) {
 117     InstructionTemplate IT = Instructions[I % OriginalInstructionsSize];
 118     ET.fillMemoryOperands(IT, ScratchSpacePointerInReg, I * MemStep);
 119     ++I;
 120     Instructions.push_back(std::move(IT));
 121   }
 122   assert(I * MemStep < BenchmarkRunner::ScratchSpace::kSize &&
 123          "not enough scratch space");
 124 }
 125
 126 static std::vector<InstructionTemplate> generateSnippetUsingStaticRenaming(
 127     const LLVMState &State, const InstructionTemplate &IT,
 128     const ArrayRef<const Variable *> TiedVariables,
 129     const BitVector *ScratchSpaceAliasedRegs) {
 130   std::vector<InstructionTemplate> Instructions;
 131   // Assign registers to variables in a round-robin manner. This is simple but
 132   // ensures that the most register-constrained variable does not get starved.
 133   std::vector<BitVector> PossibleRegsForVar;
 134   for (const Variable *Var : TiedVariables) {
 135     assert(Var);
 136     const Operand &Op = IT.Instr.getPrimaryOperand(*Var);
 137     assert(Op.isReg());
 138     BitVector PossibleRegs = State.getRATC().emptyRegisters();
 139     if (ScratchSpaceAliasedRegs) {
 140       PossibleRegs |= *ScratchSpaceAliasedRegs;
 141     }
 142     PossibleRegs.flip();
 143     PossibleRegs &= Op.getRegisterAliasing().sourceBits();
 144     PossibleRegsForVar.push_back(std::move(PossibleRegs));
 145   }
 146   SmallVector<int, 2> Iterators(TiedVariables.size(), 0);
 147   while (true) {
 148     InstructionTemplate TmpIT = IT;
 149     // Find a possible register for each variable in turn, marking the
 150     // register as taken.
 151     for (size_t VarId = 0; VarId < TiedVariables.size(); ++VarId) {
 152       const int NextPossibleReg =
 153           PossibleRegsForVar[VarId].find_next(Iterators[VarId]);
 154       if (NextPossibleReg <= 0) {
 155         return Instructions;
 156       }
 157       TmpIT.getValueFor(*TiedVariables[VarId]) =
 158           llvm::MCOperand::createReg(NextPossibleReg);
 159       // Bump iterator.
 160       Iterators[VarId] = NextPossibleReg;
 161       // Prevent other variables from using the register.
 162       for (BitVector &OtherPossibleRegs : PossibleRegsForVar) {
 163         OtherPossibleRegs.reset(NextPossibleReg);
 164       }
 165     }
 166     Instructions.push_back(std::move(TmpIT));
 167   }
 168 }
 169
 170 llvm::Expected<std::vector<CodeTemplate>>
 171 UopsSnippetGenerator::generateCodeTemplates(const Instruction &Instr) const {
 172   CodeTemplate CT;
 173   const llvm::BitVector *ScratchSpaceAliasedRegs = nullptr;
 174   if (Instr.hasMemoryOperands()) {
 175     const auto &ET = State.getExegesisTarget();
 176     CT.ScratchSpacePointerInReg =
 177         ET.getScratchMemoryRegister(State.getTargetMachine().getTargetTriple());
 178     if (CT.ScratchSpacePointerInReg == 0)
 179       return llvm::make_error<BenchmarkFailure>(
 180           "Infeasible : target does not support memory instructions");
 181     ScratchSpaceAliasedRegs =
 182         &State.getRATC().getRegister(CT.ScratchSpacePointerInReg).aliasedBits();
 183     // If the instruction implicitly writes to ScratchSpacePointerInReg , abort.
 184     // FIXME: We could make a copy of the scratch register.
 185     for (const auto &Op : Instr.Operands) {
 186       if (Op.isDef() && Op.isImplicitReg() &&
 187           ScratchSpaceAliasedRegs->test(Op.getImplicitReg()))
 188         return llvm::make_error<BenchmarkFailure>(
 189             "Infeasible : memory instruction uses scratch memory register");
 190     }
 191   }
 192
 193   const AliasingConfigurations SelfAliasing(Instr, Instr);
 194   InstructionTemplate IT(Instr);
 195   if (SelfAliasing.empty()) {
 196     CT.Info = "instruction is parallel, repeating a random one.";
 197     CT.Instructions.push_back(std::move(IT));
 198     instantiateMemoryOperands(CT.ScratchSpacePointerInReg, CT.Instructions);
 199     return getSingleton(std::move(CT));
 200   }
 201   if (SelfAliasing.hasImplicitAliasing()) {
 202     CT.Info = "instruction is serial, repeating a random one.";
 203     CT.Instructions.push_back(std::move(IT));
 204     instantiateMemoryOperands(CT.ScratchSpacePointerInReg, CT.Instructions);
 205     return getSingleton(std::move(CT));
 206   }
 207   const auto TiedVariables = getVariablesWithTiedOperands(Instr);
 208   if (!TiedVariables.empty()) {
 209     CT.Info = "instruction has tied variables, using static renaming.";
 210     CT.Instructions = generateSnippetUsingStaticRenaming(
 211         State, IT, TiedVariables, ScratchSpaceAliasedRegs);
 212     instantiateMemoryOperands(CT.ScratchSpacePointerInReg, CT.Instructions);
 213     return getSingleton(std::move(CT));
 214   }
 215   const auto &ReservedRegisters = State.getRATC().reservedRegisters();
 216   // No tied variables, we pick random values for defs.
 217   llvm::BitVector Defs(State.getRegInfo().getNumRegs());
 218   for (const auto &Op : Instr.Operands) {
 219     if (Op.isReg() && Op.isExplicit() && Op.isDef() && !Op.isMemory()) {
 220       auto PossibleRegisters = Op.getRegisterAliasing().sourceBits();
 221       remove(PossibleRegisters, ReservedRegisters);
 222       // Do not use the scratch memory address register.
 223       if (ScratchSpaceAliasedRegs)
 224         remove(PossibleRegisters, *ScratchSpaceAliasedRegs);
 225       assert(PossibleRegisters.any() && "No register left to choose from");
 226       const auto RandomReg = randomBit(PossibleRegisters);
 227       Defs.set(RandomReg);
 228       IT.getValueFor(Op) = llvm::MCOperand::createReg(RandomReg);
 229     }
 230   }
 231   // And pick random use values that are not reserved and don't alias with defs.
 232   const auto DefAliases = getAliasedBits(State.getRegInfo(), Defs);
 233   for (const auto &Op : Instr.Operands) {
 234     if (Op.isReg() && Op.isExplicit() && Op.isUse() && !Op.isMemory()) {
 235       auto PossibleRegisters = Op.getRegisterAliasing().sourceBits();
 236       remove(PossibleRegisters, ReservedRegisters);
 237       // Do not use the scratch memory address register.
 238       if (ScratchSpaceAliasedRegs)
 239         remove(PossibleRegisters, *ScratchSpaceAliasedRegs);
 240       remove(PossibleRegisters, DefAliases);
 241       assert(PossibleRegisters.any() && "No register left to choose from");
 242       const auto RandomReg = randomBit(PossibleRegisters);
 243       IT.getValueFor(Op) = llvm::MCOperand::createReg(RandomReg);
 244     }
 245   }
 246   CT.Info =
 247       "instruction has no tied variables picking Uses different from defs";
 248   CT.Instructions.push_back(std::move(IT));
 249   instantiateMemoryOperands(CT.ScratchSpacePointerInReg, CT.Instructions);
 250   return getSingleton(std::move(CT));
 251 }
 252
 253 llvm::Expected<std::vector<BenchmarkMeasure>>
 254 UopsBenchmarkRunner::runMeasurements(const FunctionExecutor &Executor) const {
 255   std::vector<BenchmarkMeasure> Result;
 256   const PfmCountersInfo &PCI = State.getPfmCounters();
 257   // Uops per port.
 258   for (const auto *IssueCounter = PCI.IssueCounters,
 259                   *IssueCounterEnd = PCI.IssueCounters + PCI.NumIssueCounters;
 260        IssueCounter != IssueCounterEnd; ++IssueCounter) {
 261     if (!IssueCounter->Counter)
 262       continue;
 263     auto ExpectedCounterValue = Executor.runAndMeasure(IssueCounter->Counter);
 264     if (!ExpectedCounterValue)
 265       return ExpectedCounterValue.takeError();
 266     Result.push_back(BenchmarkMeasure::Create(IssueCounter->ProcResName,
 267                                               *ExpectedCounterValue));
 268   }
 269   // NumMicroOps.
 270   if (const char *const UopsCounter = PCI.UopsCounter) {
 271     auto ExpectedCounterValue = Executor.runAndMeasure(UopsCounter);
 272     if (!ExpectedCounterValue)
 273       return ExpectedCounterValue.takeError();
 274     Result.push_back(
 275         BenchmarkMeasure::Create("NumMicroOps", *ExpectedCounterValue));
 276   }
 277   return std::move(Result);
 278 }
 279
 280 constexpr const size_t UopsSnippetGenerator::kMinNumDifferentAddresses;
 281
 282 } // namespace exegesis
 283 } // namespace llvm