[llvm-mca][x86] Teach how to identify optimizable register-register moves and zero-idioms.

[adibiagio]

Bugzilla Link	36671
Resolution	FIXED
Resolved on	Sep 25, 2020 11:01
Version	trunk
OS	All
Depends On	#36073
CC	@adibiagio,@legrosbuffle,@LebedevRI,@RKSimon,@rotateright

Extended Description

This is currently marked as x86. However, it may apply to other targets other than x86.

Most modern Intel/AMD processors know how to eliminate register-register moves and zero idioms at register renaming stage. The tool currently doesn't know about these patterns, and this may negatively impact the performance analysis.

We want to expose this information to llvm-mca. Ideally, the tool should have a View to generate performance counters for the:

• number of register moves eliminated
• number of zero idioms eliminated

[RKSimon]

How do you propose to flag instructions as copy/zero idioms? How much do you think will have to be done on the llvm-mca side?

The moves should be relatively easy (with some annoyances - btver2/bdver/znver don't do free moves for 256-bit registers due to double pumping etc.), but the supported zero idioms can be tricky and vary a lot between cpus (xor on most andn/psub on some...), and its not documented well ;-(

[rotateright]

This bug came up in the review for:
https://reviews.llvm.org/D44428

...before I take up the challenge of trying to fix this... :)

Let me make sure nobody else is already working on it?

And if not, then let me ask: do we start by making sure that the sched models are accurate for moves?

For example, Haswell shows:
def : WriteRes<WriteStore, [HWPort237, HWPort4]>;
def : WriteRes<WriteLoad, [HWPort23]> { let Latency = 5; }
def : WriteRes<WriteMove, [HWPort0156]>;
def : WriteRes<WriteZero, []>;

Is "WriteMove" used for anything besides reg-reg moves in the same register file? If not, then I think we want to assume that WriteMove actually has 0 latency because as shown in Agner's uarch doc:
"Most register-to-register moves are eliminated at the register allocation stage in the same way as in the Ivy Bridge, as explained on page 127."
"An eliminated move has zero latency and does not use any execution port. But is does consume bandwidth in the decoders."

[adibiagio]

The only rule with llvm-mca bugs is:
the owner of a bug is the "Assignee" according to the bugzilla.

About how to fix this: there are several ways.
One way is to use scheduling predicates. However, llvm-mca doesn't know how to process them; there is a bugzilla to track that problem (see bug 36672). I plan to tackle it on next week.

With a predicate, you can check the CPU, and dynamically solve the scheduling class. So, on BtVer2, it would return a scheduling class for a non-zero latency instruction.

Zero idioms could also be fixed using predicates. We would need to add an extra check on the MCInst operands (i.e. all register operands must be the same).
I think it should be doable.

However, if we decide to fix this issue that way, then bug 36672 becomes a dependency.

So, for now at least, I would suggest to prioritize the "making sure that the sched models are accurate for moves" part.

[rotateright]

I noticed that 'WriteZero' applies to NOOP and V_SET0, so that seemed like an easy place to start.

But this doesn't work the way I expected: no matter what I change the latency to in the Haswell sched model for WriteZero, it doesn't change what gets displayed with the asm -print-schedule comments. How does this work?

A closer look at the 'WriteMove' class shows that it applies to any reg-reg transfer and even immediates for scalar instructions, so one potential hack/change to make that better would be to give vector-vector instructions their own class. We wanted to distinguish inter-register-file moves from the others anyway?

[llvmbot]

So, for now at least, I would suggest to prioritize the "making sure that the sched models are accurate for moves" part.

Our team is working on that for Intel CPUs.

But this doesn't work the way I expected: no matter what I change the latency to in the Haswell sched model for WriteZero, it doesn't change what gets displayed with the asm -print-schedule comments. How does this work?

Intel sched models override this on a per-instruction basis, e.g. for Haswell:

def HWWriteResGroup10 : SchedWriteRes<[HWPort0156]> {
  let Latency = 1;
  let NumMicroOps = 1;
  let ResourceCycles = [1];
}
def: InstRW<[HWWriteResGroup10], (instregex "MOV(16|32|64)rr")>;

[llvmbot]

The moves should be relatively easy (with some annoyances - btver2/bdver/znver don't do free moves for 256-bit registers due to double pumping etc.), but the supported zero idioms can be tricky and vary a lot between cpus (xor on most andn/psub on some...), and its not documented well ;-(

In addition move elimination on Intel CPUs depends on the context. We've experimented a bit and it seems that elimination depends at least on whether the moved from operand is ready when the move happens.

[adibiagio]

The moves should be relatively easy (with some annoyances - btver2/bdver/znver don't do free moves for 256-bit registers due to double pumping etc.), but the supported zero idioms can be tricky and vary a lot between cpus (xor on most andn/psub on some...), and its not documented well ;-(

In addition move elimination on Intel CPUs depends on the context. We've
experimented a bit and it seems that elimination depends at least on whether
the moved from operand is ready when the move happens.

A first step is to teach how to recognize optimizable register moves and zero idioms. Then, we can think about the next step; each subtargets may define its own set of constraits. The goal is not to be 100% accurate here. As long as the quality of the performance report is improved (even if for a few/limited cases), then I think it is still a win.

So, for now at least, I would suggest to prioritize the "making sure that the sched models are accurate for moves" part.

Our team is working on that for Intel CPUs.

Could you (or anybody in your team) raise a bug about it, and link the new bug to this bug (i.e. add it as a blocker)?
I'd like to avoid a situation where people start working on the same tasks in parallel without knowing.

[rotateright]

Intel sched models override this on a per-instruction basis, e.g. for
Haswell:

Ah, of course. I didn't notice that the file was now 4000+ lines long!

In addition move elimination on Intel CPUs depends on the context. We've
experimented a bit and it seems that elimination depends at least on whether
the moved from operand is ready when the move happens.

This matches what Agner says in the IvyBridge section of the uarch doc:
"Move elimination is not always successful. It fails when the necessary operands are not ready. But typically, move elimination succeeds in more than 80% of the possible cases."

I don't know how the success percentage is measured, but if that's anywhere near correct, then we should assume it works by default and assume that it gets better on newer chips.

[llvmbot]

Could you (or anybody in your team) raise a bug about it, and link the new bug to this bug (i.e. add it as a blocker)?

Done

[adibiagio]

Could you (or anybody in your team) raise a bug about it, and link the new bug to this bug (i.e. add it as a blocker)?

Done

Thanks!

[adibiagio]

So, I have just committed revision 333909:
http://llvm.org/viewvc/llvm-project?view=revision&revision=333909

We can use variant scheduling classes to describe zero-idioms on each x86 processor model.

At the moment, llvm-mca over-optimistically assumes that zero-latency instructions are all optimizable dependency-breaking instructions. That means, zero-latency instructions don't pollute the processor register file.
This is currently true on X86 for NOP instructions, and the packed XOR zero idioms.

However, that assumption is too optimistic. We may have dependency-breaking instructions that don't have zero latency. So, we need a proper framework to correctly identify dependency-breaking instructions.

So, I have come with the following idea which might work.
The new MCSchedPredicate framework could be used to define extra property checks in the form of methods that are accessible through the ExtraProcessorInfo interface.

For example, we could use a special MCSchedPredicate to check if an instruction is an "optimizable register-register move". Each processor would describe what is a optimizable register-register move using a MCSchedPredicate. That predicate would be expanded as the body of a known method in class MCExtraProcessorInfo.

Similarly, we could use a MCSchedPredicate to describe what is a dependency-breaking instruction for the processor.

Anyway.. this is just an idea (I need to check if the current framework is expressive enough for this, or if it requires a small change).
I will try to come-up with a patch/proof-of-concept for all of this.

Long story short: if possible, we should reuse the new predicate framework to describe dependency breaking instructions, optimizable register register moves (possibly adding hooks to the MCExtraProcessorInfo class).

[adibiagio]

BtVer2 now correctly marks dependency breaking zero-idioms.

It would be nice if somebody can help with adding zero-idioms definitions to the other Intel processor models. Hopefully, it would not be too complicated; I expect it would require something similar to what Simon and I have done to BtVer2.

-Andrea

[legrosbuffle]

It would be nice if somebody can help with adding zero-idioms definitions to the other Intel models

We're working on getting llvm-exegesis into a state that will flag them automatically. Then we can conmtribute them semi-automatically.

[adibiagio]

It would be nice if somebody can help with adding zero-idioms definitions to the other Intel models

We're working on getting llvm-exegesis into a state that will flag them
automatically. Then we can conmtribute them semi-automatically.

Interesting. Any idea of how long will it take to teach exegesis how to find them?

I don't have a problem with using exegesis to spot them, as long as it is not going to take a lot of effort and time. Otherwise, it may be worthy to just add them manually. After all, it should be pretty mechanic; we don't even need to "discover" them, since Intel/Agner docs already report the full list.

[legrosbuffle]

Otherwise, it may be worthy to just add them manually.

I guess we can start by adding a bunch manually.

After all, it should be pretty mechanic; we don't even need to "discover" them, since Intel/Agner docs already report the full list.

Far from from it :) Though the most important ones (xor eax, eax and co. are).