[llvm-exegesis] Loop unrolling for loop snippet repetitor mode

[lebedev.ri]

Summary

I really needed this, like, factually, yesterday.

Consider the following example:

$ ./bin/llvm-exegesis --mode=inverse_throughput --snippets-file=/tmp/snippet.s --num-repetitions=1000000 --repetition-mode=duplicate
Check generated assembly with: /usr/bin/objdump -d /tmp/snippet-4a7e50.o
---
mode:            inverse_throughput
key:
  instructions:
    - 'VPXORYrr YMM0 YMM0 YMM0'
  config:          ''
  register_initial_values: []
cpu_name:        znver3
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 1000000
measurements:
  - { key: inverse_throughput, value: 0.31025, per_snippet_value: 0.31025 }
error:           ''
info:            ''
assembled_snippet: C5FDEFC0C5FDEFC0C5FDEFC0C5FDEFC0C5FDEFC0C5FDEFC0C5FDEFC0C5FDEFC0C5FDEFC0C5FDEFC0C5FDEFC0C5FDEFC0C5FDEFC0C5FDEFC0C5FDEFC0C5FDEFC0C3
...

What does it tell us?
So wait, it can only execute ~3 x86 AVX YMM PXOR zero-idioms per cycle?
That doesn't seem right. That's even less than there are pipes supporting this type of op.

Now, second example:

$ ./bin/llvm-exegesis --mode=inverse_throughput --snippets-file=/tmp/snippet.s --num-repetitions=1000000 --repetition-mode=loop
Check generated assembly with: /usr/bin/objdump -d /tmp/snippet-2418b5.o
---
mode:            inverse_throughput
key:
  instructions:
    - 'VPXORYrr YMM0 YMM0 YMM0'
  config:          ''
  register_initial_values: []
cpu_name:        znver3
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 1000000
measurements:
  - { key: inverse_throughput, value: 1.00011, per_snippet_value: 1.00011 }
error:           ''
info:            ''
assembled_snippet: 49B80800000000000000C5FDEFC0C5FDEFC04983C0FF75F2C3
...

Now that's just worse. Due to the looping, the throughput completely plummeted,
and now we can only do a single instruction/cycle!?

That's not great.
And final example:

$ ./bin/llvm-exegesis --mode=inverse_throughput --snippets-file=/tmp/snippet.s --num-repetitions=1000000 --repetition-mode=loop --loop-body-size=1000
Check generated assembly with: /usr/bin/objdump -d /tmp/snippet-c402e2.o
---
mode:            inverse_throughput
key:
  instructions:
    - 'VPXORYrr YMM0 YMM0 YMM0'
  config:          ''
  register_initial_values: []
cpu_name:        znver3
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 1000000
measurements:
  - { key: inverse_throughput, value: 0.167087, per_snippet_value: 0.167087 }
error:           ''
info:            ''
assembled_snippet: 49B80800000000000000C5FDEFC0C5FDEFC04983C0FF75F2C3
...

So if we merge the previous two approaches, do duplicate this single-instruction snippet 1000x
(loop-body-size/instruction count in snippet), and run a loop with 1000 iterations
over that duplicated/unrolled snippet, the measured throughput goes through the roof,
up to 5.9 instructions/cycle, which finally tells us that this idiom is zero-cycle!

[lebedev.ri]

Thinking about it more, i wonder if this really should be unroll factor,
or much like how the repetition count works, maybe this should specify
the desired loop body size?

[lebedev.ri]

Proofread the docs some more.

[courbet]

Cool, thanks for the change. I like the approach, only have minor comments.

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

171

[style] This is no longer a constant, you can remove the k.

172

ditto

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

43

Adding the LoopBodySize here sort of breaks the SnippetRepetitor abstraction. I think LoopBodySize should be a member of LoopSnippetRepetitor, initialized in the constructor.

[lebedev.ri]

@courbet thank you for taking a look!
Partially address review notes.

[lebedev.ri]

@courbet ping
Argh, i've again forgot to submit inline comment :(

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

172

So if i pass LoopBodySize into constructor of LoopSnippetRepetitor,
how can i adjust it here then?

[courbet]

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

172

Right, I don't have a good suggestion... Let's keep it like this.

[lebedev.ri]

@courbet thank you for the review!

While there, i have a question: if i wanted to make exegesis automatically search for dep-breaking idioms
(an instruction that has at least two aliasing uses), where would i best put it? llvm-exegesis/X86/target.cpp?
I guess, it would not run for all the instructions, but only a predefined set (xor, sub-like, ???)

llvm/docs/CommandGuide/llvm-exegesis.rst

  Either `opcode-index`, `opcode-name` or `snippets-file` must be set.
 
 .. option:: -mode=[latency|uops|inverse_throughput|analysis]
 
  Specify the run mode. Note that some modes have additional requirements and options.
 
  `latency` mode can be  make use of either RDTSC or LBR.
  `latency[LBR]` is only available on X86 (at least `Skylake`).
- To run in `latency` mode, a positive value must be specified for `x86-lbr-sample-period` and `--repetition-mode=loop`.
+ To run in `latency` mode, a positive value must be specified
+ for `x86-lbr-sample-period` and `--repetition-mode=loop`.
 
  In `analysis` mode, you also need to specify at least one of the
  `-analysis-clusters-output-file=` and `-analysis-inconsistencies-output-file=`.
 
 .. option:: -x86-lbr-sample-period=<nBranches/sample>
 
   Specify the LBR sampling period - how many branches before we take a sample.
   When a positive value is specified for this option and when the mode is `latency`,
   we will use LBRs for measuring.
   On choosing the "right" sampling period, a small value is preferred, but throttling
   could occur if the sampling is too frequent. A prime number should be used to
   avoid consistently skipping certain blocks.
-  
 .. option:: -repetition-mode=[duplicate|loop|min]
 
  Specify the repetition mode. `duplicate` will create a large, straight line
- basic block with `num-repetitions` copies of the snippet. `loop` will wrap
- the snippet in a loop which will be run `num-repetitions` times. The `loop`
- mode tends to better hide the effects of the CPU frontend on architectures
+ basic block with `num-repetitions` instructions (repeating the snippet
+ `num-repetitions`/`snippet size` times). `loop` will, optionally, duplicate the
+ snippet until the loop body contains at least `loop-body-size` instructions,
+ and then wrap the result in a loop which will execute `num-repetitions`
+ instructions (thus, again, repeating the snippet
+ `num-repetitions`/`snippet size` times). The `loop` mode, especially with loop
+ unrolling tends to better hide the effects of the CPU frontend on architectures
  that cache decoded instructions, but consumes a register for counting
- iterations. If performing an analysis over many opcodes, it may be best
- to instead use the `min` mode, which will run each other mode, and produce
- the minimal measured result.
+ iterations. If performing an analysis over many opcodes, it may be best to
+ instead use the `min` mode, which will run each other mode,
+ and produce the minimal measured result.
 
 .. option:: -num-repetitions=<Number of repetitions>
 
- Specify the number of repetitions of the asm snippet.
+ Specify the target number of executed instructions. Note that the actual
+ repetition count of the snippet will be `num-repetitions`/`snippet size`.
  Higher values lead to more accurate measurements but lengthen the benchmark.
 
+.. option:: -loop-body-size=<Preferred loop body size>
+
+ Only effective for `-repetition-mode=[loop|min]`.
+ Instead of looping over the snippet directly, first duplicate it so that the
+ loop body contains at least this many instructions. This potentially results
+ in loop body being cached in the CPU Op Cache / Loop Cache, which allows to
+ which may have higher throughput than the CPU decoders.
+
 .. option:: -max-configs-per-opcode=<value>
 
  Specify the maximum configurations that can be generated for each opcode.
  By default this is `1`, meaning that we assume that a single measurement is
  enough to characterize an opcode. This might not be true of all instructions:
  for example, the performance characteristics of the LEA instruction on X86
  depends on the value of assigned registers and immediates. Setting a value of
  `-max-configs-per-opcode` larger than `1` allows `llvm-exegesis` to explore

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

struct InstructionBenchmark {
   enum ModeE { Unknown, Latency, Uops, InverseThroughput };
   ModeE Mode;
   std::string CpuName;
   std::string LLVMTriple;
   // Which instruction is being benchmarked here?
   const MCInst &keyInstruction() const { return Key.Instructions[0]; }
   // The number of instructions inside the repeated snippet. For example, if a
   // snippet of 3 instructions is repeated 4 times, this is 12.
-  int NumRepetitions = 0;
+  unsigned NumRepetitions = 0;
   enum RepetitionModeE { Duplicate, Loop, AggregateMin };
   // Note that measurements are per instruction.
   std::vector<BenchmarkMeasure> Measurements;
   std::string Error;
   std::string Info;
   std::vector<uint8_t> AssembledSnippet;
   // How to aggregate measurements.
   enum ResultAggregationModeE { Min, Max, Mean, MinVariance };

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

 public:
   explicit BenchmarkRunner(const LLVMState &State,
                            InstructionBenchmark::ModeE Mode);
 
   virtual ~BenchmarkRunner();
 
   Expected<InstructionBenchmark>
   runConfiguration(const BenchmarkCode &Configuration, unsigned NumRepetitions,
+                   unsigned LoopUnrollFactor,
                    ArrayRef<std::unique_ptr<const SnippetRepetitor>> Repetitors,
                    bool DumpObjectToDisk) const;
 
   // Scratch space to run instructions that touch memory.
   struct ScratchSpace {
     static constexpr const size_t kAlignment = 1024;
     static constexpr const size_t kSize = 1 << 20; // 1MB.
     ScratchSpace()

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

#endif
 
   const LLVMState &State;
   const ExecutableFunction Function;
   BenchmarkRunner::ScratchSpace *const Scratch;
 };
 } // namespace
 
 Expected<InstructionBenchmark> BenchmarkRunner::runConfiguration(
-    const BenchmarkCode &BC, unsigned NumRepetitions,
+    const BenchmarkCode &BC, unsigned NumRepetitions, unsigned LoopBodySize,
     ArrayRef<std::unique_ptr<const SnippetRepetitor>> Repetitors,
     bool DumpObjectToDisk) const {
   InstructionBenchmark InstrBenchmark;
   InstrBenchmark.Mode = Mode;
   InstrBenchmark.CpuName = std::string(State.getTargetMachine().getTargetCPU());
   InstrBenchmark.LLVMTriple =
       State.getTargetMachine().getTargetTriple().normalize();
   InstrBenchmark.NumRepetitions = NumRepetitions;
private:
     bool Clear = true;
   };
   ClearBenchmarkOnReturn CBOR(&InstrBenchmark);
 
   for (const std::unique_ptr<const SnippetRepetitor> &Repetitor : Repetitors) {
     // Assemble at least kMinInstructionsForSnippet instructions by repeating
     // the snippet for debug/analysis. This is so that the user clearly
     // understands that the inside instructions are repeated.
-    constexpr const int kMinInstructionsForSnippet = 16;
+    const int kMinInstructionsForSnippet = 4 * Instructions.size();
+    const int kLoopBodySizeForSnippet = 2 * Instructions.size();
     {
       SmallString<0> Buffer;
       raw_svector_ostream OS(Buffer);
       if (Error E = assembleToStream(
               State.getExegesisTarget(), State.createTargetMachine(),
               BC.LiveIns, BC.Key.RegisterInitialValues,
-              Repetitor->Repeat(Instructions, kMinInstructionsForSnippet),
+              Repetitor->Repeat(Instructions, kMinInstructionsForSnippet,
+                                kLoopBodySizeForSnippet),
               OS)) {
         return std::move(E);
       }
       const ExecutableFunction EF(State.createTargetMachine(),
                                   getObjectFromBuffer(OS.str()));
       const auto FnBytes = EF.getFunctionBytes();
       llvm::append_range(InstrBenchmark.AssembledSnippet, FnBytes);
     }
 
     // Assemble NumRepetitions instructions repetitions of the snippet for
     // measurements.
-    const auto Filler =
-        Repetitor->Repeat(Instructions, InstrBenchmark.NumRepetitions);
+    const auto Filler = Repetitor->Repeat(
+        Instructions, InstrBenchmark.NumRepetitions, LoopBodySize);
 
     object::OwningBinary<object::ObjectFile> ObjectFile;
     if (DumpObjectToDisk) {
       auto ObjectFilePath = writeObjectFile(BC, Filler);
       if (Error E = ObjectFilePath.takeError()) {
         InstrBenchmark.Error = toString(std::move(E));
         return InstrBenchmark;
       }

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

public:
   virtual ~SnippetRepetitor();
 
   // Returns the set of registers that are reserved by the repetitor.
   virtual BitVector getReservedRegs() const = 0;
 
   // Returns a functor that repeats `Instructions` so that the function executes
   // at least `MinInstructions` instructions.
   virtual FillFunction Repeat(ArrayRef<MCInst> Instructions,
-                              unsigned MinInstructions) const = 0;
+                              unsigned MinInstructions,
+                              unsigned LoopBodySize) const = 0;
 
   explicit SnippetRepetitor(const LLVMState &State) : State(State) {}
 
 protected:
   const LLVMState &State;
 };
 
 } // namespace exegesis
 } // namespace llvm
 
 #endif

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

 //===-- SnippetRepetitor.cpp ------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include <array>
 #include <string>
 
 #include "SnippetRepetitor.h"
 #include "Target.h"
+#include "llvm/ADT/Sequence.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 
 namespace llvm {
 namespace exegesis {
 namespace {
 
 class DuplicateSnippetRepetitor : public SnippetRepetitor {
 public:
   using SnippetRepetitor::SnippetRepetitor;
 
   // Repeats the snippet until there are at least MinInstructions in the
   // resulting code.
-  FillFunction Repeat(ArrayRef<MCInst> Instructions,
-                      unsigned MinInstructions) const override {
+  FillFunction Repeat(ArrayRef<MCInst> Instructions, unsigned MinInstructions,
+                      unsigned LoopBodySize) const override {
     return [Instructions, MinInstructions](FunctionFiller &Filler) {
       auto Entry = Filler.getEntry();
       if (!Instructions.empty()) {
         // Add the whole snippet at least once.
         Entry.addInstructions(Instructions);
         for (unsigned I = Instructions.size(); I < MinInstructions; ++I) {
           Entry.addInstruction(Instructions[I % Instructions.size()]);
         }

 class LoopSnippetRepetitor : public SnippetRepetitor {
 public:
   explicit LoopSnippetRepetitor(const LLVMState &State)
       : SnippetRepetitor(State),
         LoopCounter(State.getExegesisTarget().getLoopCounterRegister(
             State.getTargetMachine().getTargetTriple())) {}
 
   // Loop over the snippet ceil(MinInstructions / Instructions.Size()) times.
-  FillFunction Repeat(ArrayRef<MCInst> Instructions,
-                      unsigned MinInstructions) const override {
-    return [this, Instructions, MinInstructions](FunctionFiller &Filler) {
+  FillFunction Repeat(ArrayRef<MCInst> Instructions, unsigned MinInstructions,
+                      unsigned LoopBodySize) const override {
+    return [this, Instructions, MinInstructions,
+            LoopBodySize](FunctionFiller &Filler) {
       const auto &ET = State.getExegesisTarget();
       auto Entry = Filler.getEntry();
       auto Loop = Filler.addBasicBlock();
       auto Exit = Filler.addBasicBlock();
 
+      const unsigned LoopUnrollFactor =
+          LoopBodySize <= Instructions.size()
+              ? 1
+              : divideCeil(LoopBodySize, Instructions.size());
+      assert(LoopUnrollFactor >= 1 && "Should end up with at least 1 snippet.");
+
       // Set loop counter to the right value:
-      const APInt LoopCount(32, (MinInstructions + Instructions.size() - 1) /
-                                    Instructions.size());
+      const APInt LoopCount(
+          32,
+          divideCeil(MinInstructions, LoopUnrollFactor * Instructions.size()));
+      assert(LoopCount.uge(1) && "Trip count should be at least 1.");
       for (const MCInst &Inst :
            ET.setRegTo(State.getSubtargetInfo(), LoopCounter, LoopCount))
         Entry.addInstruction(Inst);
 
       // Set up the loop basic block.
       Entry.MBB->addSuccessor(Loop.MBB, BranchProbability::getOne());
       Loop.MBB->addSuccessor(Loop.MBB, BranchProbability::getOne());
       // The live ins are: the loop counter, the registers that were setup by
       // the entry block, and entry block live ins.
       Loop.MBB->addLiveIn(LoopCounter);
       for (unsigned Reg : Filler.getRegistersSetUp())
         Loop.MBB->addLiveIn(Reg);
       for (const auto &LiveIn : Entry.MBB->liveins())
         Loop.MBB->addLiveIn(LiveIn);
+      for (auto _ : seq(0U, LoopUnrollFactor)) {
+        (void)_;
         Loop.addInstructions(Instructions);
+      }
       ET.decrementLoopCounterAndJump(*Loop.MBB, *Loop.MBB,
                                      State.getInstrInfo());
 
       // Set up the exit basic block.
       Loop.MBB->addSuccessor(Exit.MBB, BranchProbability::getZero());
       Exit.addReturn();
     };
   }

llvm/tools/llvm-exegesis/llvm-exegesis.cpp

cl::values(
                    "All of the above and take the minimum of measurements")),
     cl::init(exegesis::InstructionBenchmark::Duplicate));
 
 static cl::opt<unsigned>
     NumRepetitions("num-repetitions",
                    cl::desc("number of time to repeat the asm snippet"),
                    cl::cat(BenchmarkOptions), cl::init(10000));
 
+static cl::opt<unsigned>
+    LoopBodySize("loop-body-size",
+                 cl::desc("when repeating the instruction snippet by looping "
+                          "over it, duplicate the snippet until the loop body "
+                          "contains at least this many instruction"),
+                 cl::cat(BenchmarkOptions), cl::init(0));
+
 static cl::opt<unsigned> MaxConfigsPerOpcode(
     "max-configs-per-opcode",
     cl::desc(
         "allow to snippet generator to generate at most that many configs"),
     cl::cat(BenchmarkOptions), cl::init(1));
 
 static cl::opt<bool> IgnoreInvalidSchedClass(
     "ignore-invalid-sched-class",
#endif
   }
 
   // Write to standard output if file is not set.
   if (BenchmarkFile.empty())
     BenchmarkFile = "-";
 
   for (const BenchmarkCode &Conf : Configurations) {
     InstructionBenchmark Result = ExitOnErr(Runner->runConfiguration(
-        Conf, NumRepetitions, Repetitors, DumpObjectToDisk));
+        Conf, NumRepetitions, LoopBodySize, Repetitors, DumpObjectToDisk));
     ExitOnFileError(BenchmarkFile, Result.writeYaml(State, BenchmarkFile));
   }
   exegesis::pfm::pfmTerminate();
 }
 
 // Prints the results of running analysis pass `Pass` to file `OutputFilename`
 // if OutputFilename is non-empty.
 template <typename Pass>

llvm/unittests/tools/llvm-exegesis/X86/SnippetRepetitorTest.cpp

void SetUp() override {
     MMI = std::make_unique<MachineModuleInfo>(TM.get());
     MF = &createVoidVoidPtrMachineFunction("TestFn", Mod.get(), MMI.get());
   }
 
   void TestCommon(InstructionBenchmark::RepetitionModeE RepetitionMode) {
     const auto Repetitor = SnippetRepetitor::Create(RepetitionMode, State);
     const std::vector<MCInst> Instructions = {MCInstBuilder(X86::NOOP)};
     FunctionFiller Sink(*MF, {X86::EAX});
-    const auto Fill = Repetitor->Repeat(Instructions, kMinInstructions);
+    const auto Fill =
+        Repetitor->Repeat(Instructions, kMinInstructions, kLoopBodySize);
     Fill(Sink);
   }
 
   static constexpr const unsigned kMinInstructions = 3;
+  static constexpr const unsigned kLoopBodySize = 5;
 
   std::unique_ptr<LLVMTargetMachine> TM;
   std::unique_ptr<LLVMContext> Context;
   std::unique_ptr<Module> Mod;
   std::unique_ptr<MachineModuleInfo> MMI;
   MachineFunction *MF = nullptr;
 };
 

 }
 
 TEST_F(X86SnippetRepetitorTest, Loop) {
   TestCommon(InstructionBenchmark::Loop);
   // Duplicating creates an entry block, a loop body and a ret block.
   ASSERT_EQ(MF->getNumBlockIDs(), 3u);
   const auto &LoopBlock = *MF->getBlockNumbered(1);
   EXPECT_THAT(LoopBlock.instrs(),
-              ElementsAre(HasOpcode(X86::NOOP), HasOpcode(X86::ADD64ri8),
+              ElementsAre(HasOpcode(X86::NOOP), HasOpcode(X86::NOOP),
+                          HasOpcode(X86::NOOP), HasOpcode(X86::NOOP),
+                          HasOpcode(X86::NOOP), HasOpcode(X86::ADD64ri8),
                           HasOpcode(X86::JCC_1)));
   EXPECT_THAT(LoopBlock.liveins(),
               UnorderedElementsAre(
                   LiveReg(X86::EAX),
                   LiveReg(State.getExegesisTarget().getLoopCounterRegister(
                       State.getTargetMachine().getTargetTriple()))));
   EXPECT_THAT(MF->getBlockNumbered(2)->instrs(),
               ElementsAre(HasOpcode(X86::RETQ)));
 }
 
 } // namespace
 } // namespace exegesis
 } // namespace llvm