LIBGAV1 perf regression trunk vs. Clang 9

[adibiagio]

Bugzilla Link	44539
Resolution	FIXED
Resolved on	Feb 19, 2020 05:09
Version	trunk
OS	Windows NT
Blocks	#43756 #43900
CC	@weiguozhi,@topperc,@davidbolvansky,@efriedma-quic,@gregbedwell,@zmodem,@LebedevRI,@RKSimon,@nikic,@rotateright
Fixed by commit(s)	5eb19bf

Extended Description

This is related to bug 44411.

There is a significant perf regression in benchmark LIBGAV1.

---

-O3 -march=znver1

Numbers are FPS (frames per second); more is better.

single thread -- 2000 frames
========
                         |  GCC 7.4 |  CLANG 9.x  |  CLANG Master 
chimera_8b_1080p.ivf     |  22.77   |  21.86      |  18.71
chimera_10b_1080p.ivf    |  11.31   |  12.68      |  11.67   
summer_nature_1080p.ivf  |  21.10   |  21.02      |  18.29
summer_nature_4K.ivf     |   4.74   |   4.57      |   3.94


multi threaded (8) -- no frame limit
========
                         |  GCC 7.4 |  CLANG 9.x  |  CLANG master
chimera_8b_1080p.ivf     |  43.51   |  42.76      |  34.80
chimera_10b_1080p.ivf    |  16.18   |  18.98      |  17.12
summer_nature_1080p.ivf  |  64.22   |  63.66      |  53.89
summer_nature_4K.ivf     |  17.57   |  17.17      |  14.70


multi threaded (16) -- no frame limit
========
                         |  GCC 7.4 |  CLANG 9.x  |  CLANG master
chimera_8b_1080p.ivf     |  43.40   |  43.05      |  38.73
chimera_10b_1080p.ivf    |  16.54   |  19.68      |  18.67
summer_nature_1080p.ivf  |  62.72   |  62.20      |  54.96
summer_nature_4K.ivf     |  19.31   |  19.11      |  17.13

The single threaded execution is ~14% slower on master vs clang 9.x.

Later I will post a full description of the underlying issue that caused this perf regression.

tl;dr: performance degradation in libgav is caused by poor decisions made by pass "x86 cmov converter". In particular, a bunch of CMOVs from a hot loop are now sub-optimally expanded into if-then blocks. Those CMOVs weren't expanded by the Clang 9 compiler (that was the correct decision).

If we disable that pass then we fully get back the performance loss. For example, decoding "chimera_8b_1080p.ivf" with a single thread gives us an average of 22.14 fps.

As I wrote, I plan to post all my findings in a follow-up comment.

NOTE: this is unlikely to be AMD specific. For example, I can reproduce the poor CMOV expansions if I generate code for Skylake.

[nikic]

Not the first time this pass causes issues. See also #39374 and issues referenced there.

This pass should probably just be disabled until such a time as branch weights for selects are available in the MI backend. The idea behind the pass is reasonable, but without knowledge about whether a branch is predictable or not, it tends to have very catastrophic failure cases.

[davidbolvansky]

Were there any changes in "x86 cmov converter" between 9.0 and trunk? Looks like nothing interesting here: https://github.com/llvm-mirror/llvm/commits/master/lib/Target/X86/X86CmovConversion.cpp

We should analyze how MIR looks before this pass for Clang 9 vs Clang 10.

Anyway, this is a quite significant perf issue, so this PR should be a blocker of new release.

[adibiagio]

Were there any changes in "x86 cmov converter" between 9.0 and trunk? Looks
like nothing interesting here:
https://github.com/llvm-mirror/llvm/commits/master/lib/Target/X86/
X86CmovConversion.cpp

We should analyze how MIR looks before this pass for Clang 9 vs Clang 10.

Anyway, this is a quite significant perf issue, so this PR should be a
blocker of new release.

I am about to post my findings. Sorry it takes time to do the write up...
That pass didn't change. However, the new codegen has extra CMOVs which negatively impact the cost heuristic used by that pass.

[LebedevRI]

Were there any changes in "x86 cmov converter" between 9.0 and trunk? Looks
like nothing interesting here:
https://github.com/llvm-mirror/llvm/commits/master/lib/Target/X86/
X86CmovConversion.cpp

We should analyze how MIR looks before this pass for Clang 9 vs Clang 10.

Anyway, this is a quite significant perf issue, so this PR should be a
blocker of new release.

I am about to post my findings. Sorry it takes time to do the write up...
That pass didn't change. However, the new codegen has extra CMOVs which
negatively impact the cost heuristic used by that pass.

Now that sounds familiar :)
Back in https://reviews.llvm.org/D67318 it was mentioned that the new selects
should be converted back if unprofitable, but when looking at codegen,
i failed to see what is the logic/lever that is supposed to be in sync.

[adibiagio]

(apologies in advance for this long post).

As David pointed out, there weren't significant changes to the cmov conversion pass on x86.

The only significant difference w.r.t CLANG 9 is introduced by the following (perfectly valid) optimization:

%cmp3.i217 = icmp slt i32 %sub39, 0
%cond.i218 = select i1 %cmp3.i217, i32 -1, i32 1
%mul.i226 = mul nsw i32 %cond5.i.i225, %cond.i218

==>

%cmp3.inv.i217 = icmp sgt i32 %sub39, -1
%13 = sub i32 0, %cond5.i.i224
%14 = select i1 %cmp3.inv.i217, i32 %cond5.i.i224, i32 %13

(added by commit aab8b3a to fix #42842 )

In Clang 9, we didn't optimize that sequence, and we ended up with a (potentially more expensive) integer multiply.

At the end of ISel, the SELECT from the unoptimized pattern was lowered into the following sequence:

%144:gr32 = NOT32r %41:gr32(tied-def 0)
%145:gr32 = SHR32ri %144:gr32(tied-def 0), 31, implicit-def dead $eflags
%147:gr64 = IMPLICIT_DEF
%146:gr64_nosp = INSERT_SUBREG %147:gr64(tied-def 0), killed %145:gr32, %subreg.sub_32bit
%148:gr32 = LEA64_32r %146:gr64_nosp, 1, %146:gr64_nosp, -1, $noreg
...
%42:gr32 = nsw IMUL32rr %159:gr32(tied-def 0), killed %148:gr32, implicit-def dead $eflags

As you can see, no CMOV is generated. We pay the cost of a NOT+SHR+LEA sequence followed by a IMUL32rr.

--

On master, the sub+select sequence is lowered to:

%154:gr32 = NEG32r %153:gr32(tied-def 0), implicit-def dead $eflags
TEST32rr %40:gr32, %40:gr32, implicit-def $eflags
%41:gr32 = CMOV32rr %154:gr32(tied-def 0), %153:gr32, 9, implicit $eflags

This codegen is better (we avoid the NOT+SHR+LEA+IMUL sequence at the cost of a NEG+CMOV).

So, why this transformation matters?

The above mentioned combine is triggered in a hot basic block which already had 3 CMOV instructions in it.
Basically, since when the new instcombine has been added, the compiler started generating one extra CMOV in that hot basic block.

In the case of the hot loop in libgav1, the presence of an extra CMOV is surprisingly enough to skew the cost computation done by the cmov conversion pass. It is enough to trick that pass into thinking that the (very hot) do-while loop is now definitely worthy to optimize.

As a consequence, a bunch CMOVs from that loop which weren't previously expanded by the Clang 9 compiler, are now expanded. Interestingly, only CMOVs that had a zero value in input have been expanded (I'll explain why later).

So, Why the pass thinks it is profitable to expand those CMOVs?

The heuristic used by the cmov expansion pass to identify optimizable CMOVs is purely data driven.
The cost of an instruction is effectively measured in 'cycles', and it is computed as the instruction latency + max operand latency.

Each instruction is internally associated with a pair of cost values: <MIDepth, MIDepthOpt>.

MIDepth is the cost of an instruction definition in the absence of CMOV expansion (i.e. the "unoptimized" input sequence).

MIDepthOpt is the cost of the instruction in the case where CMOV are expanded (i.e. the loop is "optimized").

IMPORTANT: An "optimized" CMOV is expanded by the pass into an if-then construct. The idea is that we want to decrease the cost of a loop by sinking some of its computation into basic blocks that are not frequently executed.

So, if the computation of one of the CMOV operands can be "sunk" into a 'then' block, then we decrease the overall "optimized" loop cost. The cost saving is a function of the delta between MIDepth and MIDepthOpt.
However, it still depends on the actual frequencies, as well as whether branches would be predictable or not in practice (the branch misprediction penalty can be very high in practice).

In the absence of CMOVs, MIDepth and MIDepthOpt are always the same value.

The cost of a loop is simply computed as the max <MIDepth, MIDepthOpt> of all instructions in the loop. Over a certain delta between MIDepth and MIDepthOpt, the pass believes that is worthy to optimize the loop by expanding CMOVs.

Here is the problem:

The MIDepthOpt cost of a CMOVs is computed by the expression: (TrueOpDepth + FalseOpDepth + 1) / 2.

Where:

• TrueOpDepth is the "depth cost of CMOV true value operand".
• FalseOpDepth is the "depth cost of CMOV false value operand".

The MIDepthOpt cost of a CMOV is effectively the average cost of its input operands (excluding the inplicit eflags).

That cost is too optimistic:

1. It is based on the strong assumption that we can always sink the entire computation of the most_expensive operand within the expanded "then" block. This may not be true in practice (i.e. uses after the cmov; etc.) as this pass seems to also be reliant on later passes (maybe machine sink?) to do a "perfect" sinking.
   Method 'convertCmovInstsToBranches' simply creates a "then" block and populates the successor of that block with PHI nodes.

2. The cost computation surprisingly favors the expansion of CMOVs where one of the inputs is from a a dependency breaking instruction (or - more in general - instructions with no input operands). The probability of expanding a CMOV is higher if one of the operands in input is from a dependency breaking PSEUDO. This is the biggest issue in libgav1 (see below).

---

Consider the following Machine IR:

%152:gr32 = MOV32r0 implicit-def dead $eflags
TEST32rr %149:gr32, %149:gr32, implicit-def $eflags
%153:gr32 = CMOV32rr %151:gr32(tied-def 0), killed %152:gr32, 8, implicit $eflags

Assumptions:

1. %151:gr32 has a cost of <20, 20> (i.e. MIDepth is 20, MIDepthOpt is also 20).
2. The definition of 'eflags' from TEST32rr has also a cost of <20, 20>.
3. Latency of MOV32r0 is 1 cycle.
4. Latency of CMOV32rr is 1 cycle.

The cost of CMOV32rr is:
MIDepth = 1 + max(MIDepth_of(%151), MIDepth_of(%152), MIDepth_of(%eflags))
MIDepthOpt = (MIDepth_of(%151), MIDepth_of(%152) + 1) / 2

MOV32r0 is a Pseudo with no inputs.
Therefore %152 has always a cost of <1, 1> (i.e. MIDepth = MIDepthOpt = 1)

This leads to:

MIDepth_of(CMOV32rr) = 1 + max(20, 1, 20) = 21.
MIDepthOpt_of(CMOV32rr) = (20 + 1 + 1) / 2 = 11. (!!)

--

Assuming a 50% rate for both the "true" and "false" case, the overall cost (ignoring the misprediction cost for now) tends to be 11cy for the "optimized" case per loop iteration.

However, the only way to achieve that significant gain is if we fully sink the entire computation of %151 into the "then" block. This is probably still not enough, since we don't know whether the new branch would be predictable or not.

This is not what happens in practice.
We also don't sink the zero computation into the then block. So before regalloc, we are still computing both operands in the same basic block, and now we even pay the extra cost of a register copy in the new "then" block (introduced when we left the SSA form). This also sadly leads to an increase in register pressure which: (there are two extra spill slots are now present in the hottest function of libgav1; if we disable cmov conversion, we go back to the "normal" number of spills (i.e. the one from Clang 9).

In practice, a CMOV with a zero input is very rarely a good candidate for CMOV expansion. It is either used to initialize a register value to zero, or it is often used by logic which "saturates" integer values.

example:
return value < low ? low : (value > high ? high : value);

(where low is know to be zero).

In the former case, there is very little (or no) gain by expanding the CMOV. In the ideal case we save a zero move. However, the zero-move is probably required only once. So we still need to almost always evaluate the other operand.

In the latter case, (unless we know a bit more about the context) the branch is likely to be unpredictable.

That second case is directly taken from libgav1. That code is inlined in two places within the hot do-while loop of libgav1.

It is hard to predict whether value will be positive or negative. It is actually hard to predict the actual range of possible values in value.
So expanding those CMOVs is probably not a good idea.

In the last example above, we were always optimistically assuming a big gain of 10cy for the CMOV of zero. That is too aggressive in practice since the risk of having to pay the misprediction cost is very high.

--

In conclusion: the presence of an extra CMOV from a perfectly valid transform surprisingly ended up confusing the cmov conversion pass. Eventually the compiler ended up suboptimally expanding ALL the CMOVs from the hottest loop of libgav that had a Zero in input.

The problematic CMOV expansions only occur when building for specific X86 subtargets. I have tested the following cpus: znver1, haswell, broadwell and skylake; only znver1 and skylake we do the needless CMOV expansion.

[adibiagio]

Not the first time this pass causes issues. See also
#39374 and issues referenced there.

This pass should probably just be disabled until such a time as branch
weights for selects are available in the MI backend. The idea behind the
pass is reasonable, but without knowledge about whether a branch is
predictable or not, it tends to have very catastrophic failure cases.

I agree. The idea is sound, but the cost heuristic is questionable in my opinion.

It would be interesting to see if by disabling this pass we also recover the performance loss from the other phoronix benchmarks. I'll keep investigating on this.

[rotateright]

Not the first time this pass causes issues. See also
#39374 and issues referenced there.

This pass should probably just be disabled until such a time as branch
weights for selects are available in the MI backend. The idea behind the
pass is reasonable, but without knowledge about whether a branch is
predictable or not, it tends to have very catastrophic failure cases.

I agree. The idea is sound, but the cost heuristic is questionable in my
opinion.

It would be interesting to see if by disabling this pass we also recover the
performance loss from the other phoronix benchmarks. I'll keep investigating
on this.

Disabling would be the ideal quick-fix, but that pass has been around long enough that I suspect we'll get alternate bug reports for causing regressions on whatever benchmarks motivated its creation in the first place. See the bottom of the original review:
https://reviews.llvm.org/D34769

Spec2006
429.mcf: +6%
456.hmmer: +12%

Telecom
fbital00: +30%

[adibiagio]

Not the first time this pass causes issues. See also
#39374 and issues referenced there.

This pass should probably just be disabled until such a time as branch
weights for selects are available in the MI backend. The idea behind the
pass is reasonable, but without knowledge about whether a branch is
predictable or not, it tends to have very catastrophic failure cases.

I agree. The idea is sound, but the cost heuristic is questionable in my
opinion.

It would be interesting to see if by disabling this pass we also recover the
performance loss from the other phoronix benchmarks. I'll keep investigating
on this.

Disabling would be the ideal quick-fix, but that pass has been around long
enough that I suspect we'll get alternate bug reports for causing
regressions on whatever benchmarks motivated its creation in the first
place. See the bottom of the original review:
https://reviews.llvm.org/D34769

Spec2006
429.mcf: +6%
456.hmmer: +12%

Telecom
fbital00: +30%

Interesting that this was on skylake. I wonder if there is something else going on in those benchmarks as a result of this pass triggering.

If disabling that pass is not an option, we can try to tweak the cost heuristic used for CMOVs with a known zero-operand in input. Maybe extend it to all definitions from dep-breaking instructions.

[nikic]

IMPORTANT: An "optimized" CMOV is expanded by the pass into an if-then construct. The idea is that we want to decrease the cost of a loop by sinking some of its computation into basic blocks that are not frequently executed.

It has been a while since I looked at this pass in detail, but I believe this is not what the cmov conversions is about. It's not about sinking instructions used by the select operands, it's about breaking the data dependency on the select condition. (Sinking instructions may be a nice side-benefit, of course.)

That is, branches have no data dependency on the condition, because they are predicted and speculated. Conditional moves to have a data dependency on the condition.

It's important to keep this in mind when looking at the cost modelling, because otherwise it really doesn't make a lot of sense. In particular, the cost with cmov (for the cmov itself) is considered

max(CondOpDepth, TrueOpDepth, FalseOpDepth)

while after conversion to a branch it is

(TrueOpDepth + FalseOpDepth + 1) / 2

Under the premise that we have no a-priori knowledge of which branch will be taken, and under the (very questionable) premise that we can ignore branch mispredict penality, this modelling is correct: From a data-dependency point of view, we have removed the latency of the condition, and we will need the latency of the true / false operand in 50% of the cases.

Note that none of this assumes any of the instructions being sunk, as long as we only look at latency and assume (this is again a problematic assumption) that we have unlimited resources where instruction issue and execution units are concerned.

I think your particular case (with one of the cmov operands having very high latency and the other very low) clashes primarily with that last assumption. That is, we are unable to capitalize on the improved theoretical latency of the happy path, because we're saturated by executing unsinkable instructions from the other path anyway.

Using max(TrueOpDepth, FalseOpDepth) (and only dropping the condition operand) would be a conservative correction in the other direction, but I suspect that's going to prevent the cmov conversion for most of the "desired" cases as well.

[rotateright]

If disabling that pass is not an option, we can try to tweak the cost
heuristic used for CMOVs with a known zero-operand in input. Maybe extend it
to all definitions from dep-breaking instructions.

Disabling is still an option IMO as long as we can show that the wins from disabling are in the ballpark of any losses. This will of course be subjective since everyone has their favorite benchmarks.

So a possible first step in making (hopefully quick!) progress would be to disable the pass and re-run SPEC2006 to see if those initial claims still hold on Skylake or similar.

[davidbolvansky]

Even if SPEC is OK, it is just a set of benchmarks. Other benchmarks or real programs would suffer a lot since they rely on current codegen decisions. New tuning/heuristic could work too.

I like this idea:
"...branch weights for selects are available in the MI backend"

[adibiagio]

Thanks Nikita.
Your explanation makes a lot of sense.

I didn't know much about that pass and its cost model until I started triaging this issue. The code comment for function getDepthOfOptCmov could definitely be improved by describing those assumptions.

If we make the assumption of 'unlimited execution units' and we ignore for a moment that branches may be unpredictable then yes, the cost computation definitely makes more sense. And I can see now how it is not about what could be sunk.

The assumption that branches are always predictable is concerning though. I still think that it may be an option to limit CMOV expansions in cases where one of the operands is Zero (I need to run more experiments on this, but I believe that those might not be good CMOV candidates in practice).

Out of curiosity I have run some experiments on my host PC (a znver1) by capturing PMCs for branches retired with perf.

perf stat -e r0c2:u,r0c3:u,r0c4:u,r0c5:u --all-cpu -i -d --no-inherit --repeat 5 ./gav1_decode ~/libgav1/chimera_10b_1080p.ivf --limit 1000

(a description of the monitored counters is available from the official AMD document "Processor Programming Reference (PPR) for AMD Family 17h Models 00h-0Fh Processors (PUB)").

libgav1 built with clang 9:

Performance counter stats for 'system wide' (5 runs):

67,173,370,695      r0c2:u     ( +-  0.16% )  (83.33%)
   491,957,599      r0c3:u     ( +-  0.12% )  (83.33%)
32,226,438,161      r0c4:u     ( +-  0.06% )  (83.34%)
   281,124,841      r0c5:u     ( +-  0.21% )  (83.33%)

  69.143514319 seconds time elapsed           ( +-  0.19% )

--
libgav1 built with clang master:

Performance counter stats for 'system wide' (5 runs):

73,288,084,819      r0c2:u     ( +-  0.19% )  (83.33%)
 1,102,000,294      r0c3:u     ( +-  0.09% )  (83.33%)
35,457,785,949      r0c4:u     ( +-  0.07% )  (83.33%)
   597,985,407      r0c5:u     ( +-  0.04% )  (83.33%)

  73.891046577 seconds time elapsed           ( +-  0.40% )

--

r0c2 - Retired Branch Instructions
r0c3 - Retired Branch Instructions Mispredicted
r0c4 - Retired Taken Branch Instructions
r0c5 - Retired Taken Branch Instructions Mispredicted

As expected, the number of branches dynamically executed went up (roughly 8% more branches). However, the number of mispredicted branches went up by more than double.

[nikic]

Possibly this tweak would work?

diff --git a/llvm/lib/Target/X86/X86CmovConversion.cpp b/llvm/lib/Target/X86/X86CmovConversion.cpp
index fe43bf4cbbc..e842993644f 100644
--- a/llvm/lib/Target/X86/X86CmovConversion.cpp
+++ b/llvm/lib/Target/X86/X86CmovConversion.cpp
@@ -364,12 +364,11 @@ bool X86CmovConverterPass::collectCmovCandidates(
/// \param TrueOpDepth depth cost of CMOV true value operand.
/// \param FalseOpDepth depth cost of CMOV false value operand.
static unsigned getDepthOfOptCmov(unsigned TrueOpDepth, unsigned FalseOpDepth) {

• //===--------------------------------------------------------------------===//
• // With no info about branch weight, we assume 50% for each value operand.
• // Thus, depth of optimized CMOV instruction is the rounded up average of
• // its True-Operand-Value-Depth and False-Operand-Value-Depth.
• //===--------------------------------------------------------------------===//
• return (TrueOpDepth + FalseOpDepth + 1) / 2;

• // With no info about branch weight, we assume 75% for one and 25% for the
• // other, and pick the larger resulting depth.
• return std::max(

•  (TrueOpDepth * 3 + FalseOpDepth + 3) / 4,
  

•  (FalseOpDepth * 3 + TrueOpDepth + 3) / 4);
  

}

bool X86CmovConverterPass::checkForProfitableCmovCandidates(

I tried to make it just std::max(TrueOpDepth, FalseOpDepth) first, but that failed some existing tests. One of them has

%add = add nsw i32 %0, 1
%mul = mul nsw i32 %0, %a
%cmp3 = icmp sgt i32 %mul, %b
%. = select i1 %cmp3, i32 10, i32 %add

in it, which presumably falls into the "one zero-depth operand" case you mention, so that may not be a good special-case if we want to retain codegen on existing tests.

[adibiagio]

I tried to make it just std::max(TrueOpDepth, FalseOpDepth) first, but that
failed some existing tests. One of them has

%add = add nsw i32 %0, 1
%mul = mul nsw i32 %0, %a
%cmp3 = icmp sgt i32 %mul, %b
%. = select i1 %cmp3, i32 10, i32 %add

in it, which presumably falls into the "one zero-depth operand" case you
mention, so that may not be a good special-case if we want to retain codegen
on existing tests.

My suggestion was related only to dependency-breaking instructions. In particular zero idioms. Basically I suggested that the pass should only treat those specially.

Out of curiosity: do we know if those tests are from benchmarks that benefitted from the x86 cmov conversion pass?

In the meantime, I'll see if by hacking the cost heuristic as you have have suggested fixes the issue with libgav1. I expect it to improve the situation. However, there will always be issues with unpredictable branches.

So a possible first step in making (hopefully quick!) progress would be to
disable the pass and re-run SPEC2006 to see if those initial claims still
hold on Skylake or similar.

I don't have access to a Skylake machine. I can try to run some experiments on other machines though.

[adibiagio]

The idea of propagating frequencies to machine instructions makes a lot of sense.

However, branch weigths are normally available with PGO. Also, assuming that brach weights are available, only select instructions obtained from folding branches would have branch weights.
For example: SimplifyCFG propagates branch weights from a folded branch to the resulting select (in the form of 'prof' metadata).

The most common way to get frequencies is basically with PGO and only if a select is originally from a branch with known weights. The latter is not the case in libgav1. In libgav1 the CMOV is from an expression like this a < 0 ? (a > n ? n : a). Even in the presence of prof metadata, we would not be able to know the relative frequency of a < 0 (unless we do value profiling on the select condition).

If in future we start propagating branch weights to machine instructions, then we can change/tweak how the x86 CMOV conversion identifies CMOV candidates. For example, we could restrict the transform to only those CMOVs that have known frequencies and ignore others. That way we could have a better guess on the predictability of branches. Not sure if this makes sense. In case, this is just an idea for the long term.