This is an archive of the discontinued LLVM Phabricator instance.

[llvm-exegesis] 'Min' repetition mode
ClosedPublic

Authored by lebedev.ri on Mar 27 2020, 6:33 AM.

Details

Summary

As noted in documentation, different repetition modes have different trade-offs:

.. option:: -repetition-mode=[duplicate|loop]

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
that cache decoded instructions, but consumes a register for counting
iterations.

Indeed. Example:

At least for CMOV, i'm seeing wildly different results

LatencyRThroughput
duplicate10.8
loop20.6

where latency=1 seems correct, and i'd expect the througput to be close to 1/2 (since there are two execution units).

This isn't great for analysis, at least for schedule model development.

As discussed in excruciating detail in

... did that explanation of the question i'm having made any sense?

Thx for digging in the conversation !
Ok it makes more sense now.

I discussed it a bit with @courbet:

  • We want the analysis tool to stay simple so we'd rather not make it knowledgeable of the repetition mode.
  • We'd like to still be able to select either repetition mode to dig into special cases

So we could add a third min repetition mode that would run both and take the minimum. It could be the default option.
Would you have some time to look what it would take to add this third mode?

there appears to be an agreement that it is indeed sub-par,
and that we should provide an optional, measurement (not analysis!) -time
way to rectify the situation.

However, the solutions isn't entirely straight-forward.

We can just add an actual 'multiplexer' MinSnippetRepetitor, because
if we just concatenate snippets produced by DuplicateSnippetRepetitor
and LoopSnippetRepetitor and run+measure that, the measurement will
naturally be different from what we'd get by running+measuring
them separately and taking the min.
([[ https://www.wolframalpha.com/input/?i=%28x%2By%29%2F2+%21%3D+min%28x%2C+y%29 | time(D+L)/2 != min(time(D), time(L)) ]])

Also, it seems best to me to have a single snippet instead of generating
a snippet per repetition mode, since the only difference here is that the
loop repetition mode reserves one register for loop counter.

As far as i can tell, we can either teach BenchmarkRunner::runConfiguration()
to produce a single report given multiple repetitors (as in the patch),
or do that one layer higher - don't modify BenchmarkRunner::runConfiguration(),
produce multiple reports, don't actually print each one, but aggregate them somehow
and only print the final one.

Initially i've gone ahead with the latter approach, but it didn't look like a natural fit;
the former (as in the diff) does seem like a better fit to me.

There's also a question of the test coverage. It sure currently does work here:

$ ./bin/llvm-exegesis --opcode-name=CMOV64rr --mode=inverse_throughput --repetition-mode=duplicate
Check generated assembly with: /usr/bin/objdump -d /tmp/snippet-8fb949.o
---
mode:            inverse_throughput
key:
  instructions:
    - 'CMOV64rr RAX RAX R11 i_0x0'
    - 'CMOV64rr RBP RBP R15 i_0x0'
    - 'CMOV64rr RBX RBX RBX i_0x0'
    - 'CMOV64rr RCX RCX RBX i_0x0'
    - 'CMOV64rr RDI RDI R10 i_0x0'
    - 'CMOV64rr RDX RDX RAX i_0x0'
    - 'CMOV64rr RSI RSI RAX i_0x0'
    - 'CMOV64rr R8 R8 R8 i_0x0'
    - 'CMOV64rr R9 R9 RDX i_0x0'
    - 'CMOV64rr R10 R10 RBX i_0x0'
    - 'CMOV64rr R11 R11 R14 i_0x0'
    - 'CMOV64rr R12 R12 R9 i_0x0'
    - 'CMOV64rr R13 R13 R12 i_0x0'
    - 'CMOV64rr R14 R14 R15 i_0x0'
    - 'CMOV64rr R15 R15 R13 i_0x0'
  config:          ''
  register_initial_values:
    - 'RAX=0x0'
    - 'R11=0x0'
    - 'EFLAGS=0x0'
    - 'RBP=0x0'
    - 'R15=0x0'
    - 'RBX=0x0'
    - 'RCX=0x0'
    - 'RDI=0x0'
    - 'R10=0x0'
    - 'RDX=0x0'
    - 'RSI=0x0'
    - 'R8=0x0'
    - 'R9=0x0'
    - 'R14=0x0'
    - 'R12=0x0'
    - 'R13=0x0'
cpu_name:        bdver2
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 10000
measurements:
  - { key: inverse_throughput, value: 0.819, per_snippet_value: 12.285 }
error:           ''
info:            instruction has tied variables, using static renaming.
assembled_snippet: 5541574156415541545348B8000000000000000049BB00000000000000004883EC08C7042400000000C7442404000000009D48BD000000000000000049BF000000000000000048BB000000000000000048B9000000000000000048BF000000000000000049BA000000000000000048BA000000000000000048BE000000000000000049B8000000000000000049B9000000000000000049BE000000000000000049BC000000000000000049BD0000000000000000490F40C3490F40EF480F40DB480F40CB490F40FA480F40D0480F40F04D0F40C04C0F40CA4C0F40D34D0F40DE4D0F40E14D0F40EC4D0F40F74D0F40FD490F40C35B415C415D415E415F5DC3
...
$ ./bin/llvm-exegesis --opcode-name=CMOV64rr --mode=inverse_throughput --repetition-mode=loop
Check generated assembly with: /usr/bin/objdump -d /tmp/snippet-051eb3.o
---
mode:            inverse_throughput
key:
  instructions:
    - 'CMOV64rr RAX RAX R11 i_0x0'
    - 'CMOV64rr RBP RBP RSI i_0x0'
    - 'CMOV64rr RBX RBX R9 i_0x0'
    - 'CMOV64rr RCX RCX RSI i_0x0'
    - 'CMOV64rr RDI RDI RBP i_0x0'
    - 'CMOV64rr RDX RDX R9 i_0x0'
    - 'CMOV64rr RSI RSI RDI i_0x0'
    - 'CMOV64rr R9 R9 R12 i_0x0'
    - 'CMOV64rr R10 R10 R11 i_0x0'
    - 'CMOV64rr R11 R11 R9 i_0x0'
    - 'CMOV64rr R12 R12 RBP i_0x0'
    - 'CMOV64rr R13 R13 RSI i_0x0'
    - 'CMOV64rr R14 R14 R14 i_0x0'
    - 'CMOV64rr R15 R15 R10 i_0x0'
  config:          ''
  register_initial_values:
    - 'RAX=0x0'
    - 'R11=0x0'
    - 'EFLAGS=0x0'
    - 'RBP=0x0'
    - 'RSI=0x0'
    - 'RBX=0x0'
    - 'R9=0x0'
    - 'RCX=0x0'
    - 'RDI=0x0'
    - 'RDX=0x0'
    - 'R12=0x0'
    - 'R10=0x0'
    - 'R13=0x0'
    - 'R14=0x0'
    - 'R15=0x0'
cpu_name:        bdver2
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 10000
measurements:
  - { key: inverse_throughput, value: 0.6083, per_snippet_value: 8.5162 }
error:           ''
info:            instruction has tied variables, using static renaming.
assembled_snippet: 5541574156415541545348B8000000000000000049BB00000000000000004883EC08C7042400000000C7442404000000009D48BD000000000000000048BE000000000000000048BB000000000000000049B9000000000000000048B9000000000000000048BF000000000000000048BA000000000000000049BC000000000000000049BA000000000000000049BD000000000000000049BE000000000000000049BF000000000000000049B80200000000000000490F40C3480F40EE490F40D9480F40CE480F40FD490F40D1480F40F74D0F40CC4D0F40D34D0F40D94C0F40E54C0F40EE4D0F40F64D0F40FA4983C0FF75C25B415C415D415E415F5DC3
...
$ ./bin/llvm-exegesis --opcode-name=CMOV64rr --mode=inverse_throughput --repetition-mode=min
Check generated assembly with: /usr/bin/objdump -d /tmp/snippet-c7a47d.o
Check generated assembly with: /usr/bin/objdump -d /tmp/snippet-2581f1.o
---
mode:            inverse_throughput
key:
  instructions:
    - 'CMOV64rr RAX RAX R11 i_0x0'
    - 'CMOV64rr RBP RBP R10 i_0x0'
    - 'CMOV64rr RBX RBX R10 i_0x0'
    - 'CMOV64rr RCX RCX RDX i_0x0'
    - 'CMOV64rr RDI RDI RAX i_0x0'
    - 'CMOV64rr RDX RDX R9 i_0x0'
    - 'CMOV64rr RSI RSI RAX i_0x0'
    - 'CMOV64rr R9 R9 RBX i_0x0'
    - 'CMOV64rr R10 R10 R12 i_0x0'
    - 'CMOV64rr R11 R11 RDI i_0x0'
    - 'CMOV64rr R12 R12 RDI i_0x0'
    - 'CMOV64rr R13 R13 RDI i_0x0'
    - 'CMOV64rr R14 R14 R9 i_0x0'
    - 'CMOV64rr R15 R15 RBP i_0x0'
  config:          ''
  register_initial_values:
    - 'RAX=0x0'
    - 'R11=0x0'
    - 'EFLAGS=0x0'
    - 'RBP=0x0'
    - 'R10=0x0'
    - 'RBX=0x0'
    - 'RCX=0x0'
    - 'RDX=0x0'
    - 'RDI=0x0'
    - 'R9=0x0'
    - 'RSI=0x0'
    - 'R12=0x0'
    - 'R13=0x0'
    - 'R14=0x0'
    - 'R15=0x0'
cpu_name:        bdver2
llvm_triple:     x86_64-unknown-linux-gnu
num_repetitions: 10000
measurements:
  - { key: inverse_throughput, value: 0.6073, per_snippet_value: 8.5022 }
error:           ''
info:            instruction has tied variables, using static renaming.
assembled_snippet: 5541574156415541545348B8000000000000000049BB00000000000000004883EC08C7042400000000C7442404000000009D48BD000000000000000049BA000000000000000048BB000000000000000048B9000000000000000048BA000000000000000048BF000000000000000049B9000000000000000048BE000000000000000049BC000000000000000049BD000000000000000049BE000000000000000049BF0000000000000000490F40C3490F40EA490F40DA480F40CA480F40F8490F40D1480F40F04C0F40CB4D0F40D44C0F40DF4C0F40E74C0F40EF4D0F40F14C0F40FD490F40C3490F40EA5B415C415D415E415F5DC35541574156415541545348B8000000000000000049BB00000000000000004883EC08C7042400000000C7442404000000009D48BD000000000000000049BA000000000000000048BB000000000000000048B9000000000000000048BA000000000000000048BF000000000000000049B9000000000000000048BE000000000000000049BC000000000000000049BD000000000000000049BE000000000000000049BF000000000000000049B80200000000000000490F40C3490F40EA490F40DA480F40CA480F40F8490F40D1480F40F04C0F40CB4D0F40D44C0F40DF4C0F40E74C0F40EF4D0F40F14C0F40FD4983C0FF75C25B415C415D415E415F5DC3
...

but i open to suggestions as to how test that.

I also have gone with the suggestion to default to this new mode.
This was irking me for some time, so i'm happy to finally see progress here.
Looking forward to feedback.

Diff Detail

Event Timeline

lebedev.ri created this revision.Mar 27 2020, 6:33 AM
lebedev.ri edited the summary of this revision. (Show Details)Mar 27 2020, 6:34 AM
lebedev.ri edited the summary of this revision. (Show Details)Mar 27 2020, 6:36 AM

Thx for the patch !
I have a couple of suggestions but I'm onboard with the approach.

Please wait for comments from @courbet as well.

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

The scope of the for loop is pretty big. I think it would be better to create a separate function:

for (const std::unique_ptr<const SnippetRepetitor> &Repetitor : Repetitors) {
  if (auto InstrBenchmarkOrErr = runOneBenchmark(InstrBenchmark)) {
    // On success, aggregate this run
    ...
  } else {
    // On error, extract the Error value and return it.
    return InstrBenchmarkOrErr.takeError();
  }
}

This way you also don't have to have the RAII cleaner.

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

I'd rather have an empty case for InstructionBenchmark::AggregateMin and not use default.
This will help if we ever add a new mode.

lebedev.ri added inline comments.Mar 30 2020, 11:35 AM
llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp
108

Hmm. I agree that the loop is getting big, but are you very sure about the fix?

Like i said in the patch's description, i tried a variation of that approach
initially, and i'd say the result is much uglier. Instead of having one place
that fills a single InstrBenchmark and just ensuring it doesn't completely
override previous results, we will now need to keep two places in sync.

Please do note that we have two types of errors here,
a fatal one that we signal via Error, and a measurement-time error,
that we squash and stash into InstrBenchmark.Error. The latter
must not be reported as a fatal error, but it must interrupt aggregation.
So we won't avoid the RAII, just change it's form.

lebedev.ri added inline comments.Mar 30 2020, 11:48 AM
llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp
108

override previous results, we will now need to keep two places in sync.

Err, to be more specific:
We will then need to just rename the existing BenchmarkRunner::runConfiguration()
as that runOneBenchmark(), and new BenchmarkRunner::runConfiguration()
would need to know how to aggregate every field of fresh InstructionBenchmark
returned from BenchmarkRunner::runOneBenchmark() into the 'aggregate' report.
This seems more complex than teaching BenchmarkRunner::runConfiguration()
itself to do just that within the per-Repetitor loop.

courbet added inline comments.Mar 30 2020, 11:48 PM
llvm/tools/llvm-exegesis/lib/BenchmarkRunner.h
33

Let's avoid pushing tools flags down into libraries like this. This hinders testability and ties the inner classes to the tool main. What about just using repetitors.size() > 1 ?

lebedev.ri marked 2 inline comments as done.

@gchatelet @courbet
Thank you for taking a look!
Addressed review notes.

gchatelet added inline comments.Mar 31 2020, 5:54 AM
llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp
108

Acknowledge.
I'm not a huge fan of the RAII cleaner which spans the whole function and needs comments to be understood.
Maybe a custom struct would convey more semantics, it's not a lot more code.

struct ClearBenchmarkOnReturn {
  ClearBenchmarkOnReturn(InstructionBenchmark* IB) : IB(IB)
  ~ClearBenchmarkOnReturn() { if(Clear) IB->Measurements.clear(); }

  void disarm() { Clear = false; }
private:
  InstructionBenchmark* const IB;
  bool Clear = true;
};
----------------------

ClearBenchmarkOnReturn CBOR(&InstrBenchmark);

...

CBOR.disarm();
lebedev.ri marked 2 inline comments as done.

Forego of llvm::make_scope_exit in favor of more manual approach.

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

Ok, sure, that i can do.

gchatelet accepted this revision.Apr 1 2020, 7:15 AM
This revision is now accepted and ready to land.Apr 1 2020, 7:15 AM

@gchatelet thank you for the review!
@courbet any further comments?

courbet accepted this revision.Apr 1 2020, 11:23 PM

Great, thank you for the reviews!

This revision was automatically updated to reflect the committed changes.