[X86] Enable setcc to srl(ctlz) transformation on btver2 architectures.

[pgousseau]

Summary

Following the discussion on D22038, this change enables the setcc to srl(ctlz) transformation on the btver2 architecture.
This optimisation is beneficial on Jaguar architecture only, where the lzcnt has a good reciprocal throughput.
Other architectures such as Intel's Haswell/Broadwell or AMD's Bulldozer/PileDriver do not benefit from it.
For this reason the change also add a "HasFastLZCNT" feature which gets enabled for Jaguar.

This patch requires D23445

[pgousseau]

Updating patch to reflect changes in D23445

[spatel]

lib/Target/X86/X86.td

182–184

I would move this down with the other 'fake' features (ie, the other fast/slow attributes). Someday, we may come up with a better way to distinguish performance "features" from architectural ones.

It would also be good to explain exactly what we mean by "fast" in this context.

Finally, use a hyphen to make this more readable: "fast-lzcnt".

lib/Target/X86/X86ISelLowering.cpp

30923–30939

I don't understand the need for this check, so at the least it needs a code comment to explain why it is here.
Related: if we're matching the pattern starting from a zext, doesn't that miss the icmp/icmp/or patterns that you were originally hoping to optimize in D22038?

test/CodeGen/X86/lzcnt-zext-cmp.ll

6

Instead of specifying a different CPU, this RUN would be better if it also used btver2, but explicitly disabled the 'fast-lzcnt' attribute. That way we verify the codegen with and without the attribute while simultaneously verifying that btver2 has this attribute by default.

8

Please give each test a meaningful name and/or add a comment to explain exactly what each test is checking.

82–101

There should be at least one test of the 'HasInterestingUses' logic (if that logic really belongs in this patch).

[pgousseau]

lib/Target/X86/X86.td

182–184

Sounds good will do.

lib/Target/X86/X86ISelLowering.cpp

30923–30939

Sounds good, I will think of a better comment.
I added this check to be conservative for now as I noticed several worst code gen occurences (around 50% of matches in openssl).
I hope to address this and the icmp/icmp/OR case in another patch.

test/CodeGen/X86/lzcnt-zext-cmp.ll

82–101

Yes I meant to add those, will do thanks.

[pgousseau]

Rebased changes and following Sanjay's comments:

• Move down feature declaration, add hyphen, add comment.
• Remove hasInterestingUses check.
• Use fast-lzcnt in test and add comments.

Looking again the codegen of openssl without the "hasInterestingUses" constraint the codegen does not seem worse in terms of speed, only the size is not as good as it could be but I think it is ok? Something must have gone wrong during my initial testing I suppose ...

[RKSimon]

Minor tweak request.

lib/Target/X86/X86InstrInfo.td

837

Move this down to the other fast/slow definitions.

lib/Target/X86/X86Subtarget.cpp

257

Move this down to the other fast/slow variables.

lib/Target/X86/X86Subtarget.h

428

Move this down to the other fast/slow functions.

[pgousseau]

Moving down fast-lzcnt feature changes following Simon's comments.

[spatel]

In D23446#516878, @pgousseau wrote:

Looking again the codegen of openssl without the "hasInterestingUses" constraint the codegen does not seem worse in terms of speed, only the size is not as good as it could be but I think it is ok? Something must have gone wrong during my initial testing I suppose ...

I wasn't expecting a size difference. Can you provide more details about the size and perf changes that you see with this change? We may want to gate the transform based on 'optForSize'.

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3567–3568

Remove "llvm::"

lib/Target/X86/X86.td

265–266

The description still seems too vague. The key point is that lzcnt must have the same latency and throughput as test/set, right?

How about: "If lzcnt has equivalent latency/throughput to most simple integer ops, it can be used to replace test/set sequences."

test/CodeGen/X86/lzcnt-zext-cmp.ll

86–93

lzcnt has a 16-bit variant in the ISA. Is there some reason not to use it here?

[pgousseau]

Yes sounds like I should disable this if optForSize is enabled.

For example in openssl, out of 89 srl(lzcnt) optimisations, around 30 cases cause larger code, for example I see 25 of those:

3055:	31 ed                	xor    %ebp,%ebp
3057:	ff c2                	inc    %edx
3059:	40 0f 94 c5          	sete   %bpl
305d:	01 e9                	add    %ebp,%ecx

-> 10 bytes

309d:	ff c2                	inc    %edx
309f:	f3 0f bd ea          	lzcnt  %edx,%ebp
30a3:	c1 ed 05             	shr    $0x5,%ebp
30a6:	01 e9                	add    %ebp,%ecx

-> 12 bytes

But this should not affect performances.

Luckily openssl's libcrypto total size remains smaller as the other remaining matches result in fewer and as fast instructions.

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3567–3568

Sounds good, will do.

lib/Target/X86/X86.td

265–266

Sounds good thanks, will do.

test/CodeGen/X86/lzcnt-zext-cmp.ll

86–93

I disabled the 16-bit case because this seems to lead to bigger code in general, for this test case we would get:

lzcntw  %di, %ax
andl    $16, %eax
shrl    $4, %eax
retq

instead of:

xorl    %eax, %eax
testw   %di, %di
sete    %al
retq

which seems bigger code for the same result.

[pgousseau]

Following Sanjay's comments:

• Remove llvm namespace
• Rewrite feature's comment
• Disable transform if optForSize is true

[RKSimon]

Please can you add some tests with optsize enabled?

[spatel]

In D23446#519225, @pgousseau wrote:

• Disable transform if optForSize is true

optForSize is a very gray area: we allow speed optimizations even if they increase size if the speed vs. size trade-off is "large" for some definition of "large".

Can you post the detailed perf and size differences you're seeing with this change? I don't think the size change can be that big from what you've posted: lzcnt+shr is 7 bytes; {test/inc}+set is 5/6 bytes, but if there's an xor leading into it, that's 7/8 bytes.

Are there other size-increasing changes happening as side effects that I'm not accounting for? It's also not clear why this is a perf win for Jaguar. Sorry for taking this long to ask, but why is test+set slower?

test/CodeGen/X86/lzcnt-zext-cmp.ll

86–93

Oh...yuck. So we really should've done 'xor %eax, %eax' ahead of the lzcnt in that case? Please add a note about why we don't do 16-bit in the code comments and also here in the test case.

[pgousseau]

Add tests for optForSize following Simon's comments.

[pgousseau]

In D23446#519626, @spatel wrote:

In D23446#519225, @pgousseau wrote:

• Disable transform if optForSize is true

optForSize is a very gray area: we allow speed optimizations even if they increase size if the speed vs. size trade-off is "large" for some definition of "large".

Can you post the detailed perf and size differences you're seeing with this change? I don't think the size change can be that big from what you've posted: lzcnt+shr is 7 bytes; {test/inc}+set is 5/6 bytes, but if there's an xor leading into it, that's 7/8 bytes.

Are there other size-increasing changes happening as side effects that I'm not accounting for? It's also not clear why this is a perf win for Jaguar. Sorry for taking this long to ask, but why is test+set slower?

With this change the total size of openssl is smaller by at most 0.5%.
This is because while some matches led to bigger code, the majority led to smaller code by removing 1 or 2 instructions per match. So maybe we should not protect this with optForSize because it seems the size can go both ways?

Here are the text size from openssl with and without the change.

12458547 libcrypto.lzcnt.a.txt
12460372 libcrypto.nolzcnt.a.txt
-> 0.01% size decrease with change enabled
2453571 libssl.lzcnt.a.txt
2454996 libssl.nolzcnt.a.txt
-> 0.05% size decrease with change enabled

Here is an example from libcrypto where 2 instructions is saved:

f3 45 0f bd f6       	lzcnt  %r14d,%r14d
41 c1 ee 05          	shr    $0x5,%r14d

31 c0                	xor    %eax,%eax
45 85 f6             	test   %r14d,%r14d
0f 94 c0             	sete   %al
41 89 c6             	mov    %eax,%r14d

For speed measurements I am running a microbenchmark using google's libbenchmark.
Let me know if you want me to email you the source.
Here are the results on a jaguar cpu.
"old " means without the optimisation.
"new " means with the optimisation.
f1 is for the icmp pattern
f2 is for the icmp/icmp/or pattern
The numbers 8/512/8k are the number of iterations the function is being run.
The functions contains a 100 block a inline assembly corresponding to the test cases in the patch.
My understanding is that the perf win observed in those results comes from the presence of less instruction which all have the same latency/throughput 1/0.5.

Run on (6 X 1593.74 MHz CPU s)
2016-08-18 19:00:36
Benchmark                  Time           CPU Iterations
--------------------------------------------------------
BM_f1_old/8              784 ns        784 ns     893325
BM_f1_old/512          49911 ns      49911 ns      14025
BM_f1_old/8k          798898 ns     798898 ns        876
BM_f1_new/8              585 ns        585 ns    1196970
BM_f1_new/512          37170 ns      37170 ns      18830
BM_f1_new/8k          595136 ns     595135 ns       1175
BM_f2_old/8/8          13573 ns      13574 ns      51548
BM_f2_old/512/512   55446038 ns   55446001 ns         13
BM_f2_old/8k/8k   14212025166 ns 14212028980 ns          1
BM_f2_new/8/8           9126 ns       9127 ns      76692
BM_f2_new/512/512   37212798 ns   37212874 ns         19
BM_f2_new/8k/8k   9533737898 ns 9533742905 ns          1

Let me know if more detailed are required.

test/CodeGen/X86/lzcnt-zext-cmp.ll

88–95

Sounds good, will do thanks.

[pgousseau]

Add comments for the 16-bit case following Sanjay's comment.

[spatel]

In D23446#519879, @pgousseau wrote:

With this change the total size of openssl is smaller by at most 0.5%.
This is because while some matches led to bigger code, the majority led to smaller code by removing 1 or 2 instructions per match. So maybe we should not protect this with optForSize because it seems the size can go both ways?

Here are the text size from openssl with and without the change.

12458547 libcrypto.lzcnt.a.txt
12460372 libcrypto.nolzcnt.a.txt
-> 0.01% size decrease with change enabled
2453571 libssl.lzcnt.a.txt
2454996 libssl.nolzcnt.a.txt
-> 0.05% size decrease with change enabled

Here is an example from libcrypto where 2 instructions is saved:

f3 45 0f bd f6       	lzcnt  %r14d,%r14d
41 c1 ee 05          	shr    $0x5,%r14d

31 c0                	xor    %eax,%eax
45 85 f6             	test   %r14d,%r14d
0f 94 c0             	sete   %al
41 89 c6             	mov    %eax,%r14d

This is the size savings that I was imagining based on the test cases. Given that the transform may or may not *decrease* code size, we should not guard this with optForSize. Please remove that check from the code. You can leave the additional test cases for minsize/optsize (and add a comment to explain) or remove them too.

For speed measurements I am running a microbenchmark using google's libbenchmark.
Let me know if you want me to email you the source.
Here are the results on a jaguar cpu.
"old " means without the optimisation.
"new " means with the optimisation.
f1 is for the icmp pattern
f2 is for the icmp/icmp/or pattern
The numbers 8/512/8k are the number of iterations the function is being run.
The functions contains a 100 block a inline assembly corresponding to the test cases in the patch.
My understanding is that the perf win observed in those results comes from the presence of less instruction which all have the same latency/throughput 1/0.5.

Run on (6 X 1593.74 MHz CPU s)
2016-08-18 19:00:36
Benchmark                  Time           CPU Iterations
--------------------------------------------------------
BM_f1_old/8              784 ns        784 ns     893325
BM_f1_old/512          49911 ns      49911 ns      14025
BM_f1_old/8k          798898 ns     798898 ns        876
BM_f1_new/8              585 ns        585 ns    1196970
BM_f1_new/512          37170 ns      37170 ns      18830
BM_f1_new/8k          595136 ns     595135 ns       1175
BM_f2_old/8/8          13573 ns      13574 ns      51548
BM_f2_old/512/512   55446038 ns   55446001 ns         13
BM_f2_old/8k/8k   14212025166 ns 14212028980 ns          1
BM_f2_new/8/8           9126 ns       9127 ns      76692
BM_f2_new/512/512   37212798 ns   37212874 ns         19
BM_f2_new/8k/8k   9533737898 ns 9533742905 ns          1

Please correct me if I'm not understanding: this ctlz patch gives us 34% better perf; the planned follow-on will raise that to +49%.
This is much bigger than I expected. I see that we can save a few xor and mov instructions, but my mental model was that those are nearly free. Is it possible that we've managed to shrink the decode-limited inner loop past some HW limit? Is code alignment a factor?

@andreadb / @RKSimon, do you have any insight/explanation for the perf difference?

[pgousseau]

In D23446#520684, @spatel wrote:

In D23446#519879, @pgousseau wrote:

With this change the total size of openssl is smaller by at most 0.5%.
This is because while some matches led to bigger code, the majority led to smaller code by removing 1 or 2 instructions per match. So maybe we should not protect this with optForSize because it seems the size can go both ways?

Here are the text size from openssl with and without the change.

12458547 libcrypto.lzcnt.a.txt
12460372 libcrypto.nolzcnt.a.txt
-> 0.01% size decrease with change enabled
2453571 libssl.lzcnt.a.txt
2454996 libssl.nolzcnt.a.txt
-> 0.05% size decrease with change enabled

Here is an example from libcrypto where 2 instructions is saved:

f3 45 0f bd f6       	lzcnt  %r14d,%r14d
41 c1 ee 05          	shr    $0x5,%r14d

31 c0                	xor    %eax,%eax
45 85 f6             	test   %r14d,%r14d
0f 94 c0             	sete   %al
41 89 c6             	mov    %eax,%r14d

This is the size savings that I was imagining based on the test cases. Given that the transform may or may not *decrease* code size, we should not guard this with optForSize. Please remove that check from the code. You can leave the additional test cases for minsize/optsize (and add a comment to explain) or remove them too.

Sounds good, will remove the optForSize.

For speed measurements I am running a microbenchmark using google's libbenchmark.
Let me know if you want me to email you the source.
Here are the results on a jaguar cpu.
"old " means without the optimisation.
"new " means with the optimisation.
f1 is for the icmp pattern
f2 is for the icmp/icmp/or pattern
The numbers 8/512/8k are the number of iterations the function is being run.
The functions contains a 100 block a inline assembly corresponding to the test cases in the patch.
My understanding is that the perf win observed in those results comes from the presence of less instruction which all have the same latency/throughput 1/0.5.

Run on (6 X 1593.74 MHz CPU s)
2016-08-18 19:00:36
Benchmark                  Time           CPU Iterations
--------------------------------------------------------
BM_f1_old/8              784 ns        784 ns     893325
BM_f1_old/512          49911 ns      49911 ns      14025
BM_f1_old/8k          798898 ns     798898 ns        876
BM_f1_new/8              585 ns        585 ns    1196970
BM_f1_new/512          37170 ns      37170 ns      18830
BM_f1_new/8k          595136 ns     595135 ns       1175
BM_f2_old/8/8          13573 ns      13574 ns      51548
BM_f2_old/512/512   55446038 ns   55446001 ns         13
BM_f2_old/8k/8k   14212025166 ns 14212028980 ns          1
BM_f2_new/8/8           9126 ns       9127 ns      76692
BM_f2_new/512/512   37212798 ns   37212874 ns         19
BM_f2_new/8k/8k   9533737898 ns 9533742905 ns          1

Please correct me if I'm not understanding: this ctlz patch gives us 34% better perf; the planned follow-on will raise that to +49%.
This is much bigger than I expected. I see that we can save a few xor and mov instructions, but my mental model was that those are nearly free. Is it possible that we've managed to shrink the decode-limited inner loop past some HW limit? Is code alignment a factor?

Yes this benchmark seems to show those kind of improvements, for example BM_f1_new/8 is ~25% faster than BM_f1_old/8.
Although now I reran the SPEC h264ref benchmark and unfortunately, I am seeing some small (less than 1%) but consistent performance degradation with h264ref that I wasn't seeing with the initial tablegen patch.
Why the micro-benchmark does not show this I am not sure, one hypothesis is that the micro-benchmark is only comparing the 32-bit "register, register" variant of the change, so it might be that I need to restrict the transformation to this pattern.
Or the micro-benchmark is not representative of the performance and in that case this change is probably not worth pursuing. Will come back with the findings.

@andreadb / @RKSimon, do you have any insight/explanation for the perf difference?

[RKSimon]

Any update on the performance investigations?

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3588

These can be replaced with DAG.getZExtOrTrunc(Scc, dl, ExtTy);

[pgousseau]

In D23446#542525, @RKSimon wrote:

Any update on the performance investigations?

Hi Simon/Sanjay,

Sorry for the delayed follow-up!
I have ran more tests and it seems the regressions in performances I was observing with SPEC's h264 are within the noise now so I cant tell if this patch is improving or degrading perfomances in SPEC's h264 benchmark.
I am more confident the OR case brings better performances because we will be replacing

48 85 FF                test     rdi,rdi
0F 94 C0                sete     al
48 85 F6                test     rsi,rsi
0F 94 C1                sete     cl
08 C1                   or       cl,al
0F B6 C1                movzx    eax,cl
C3                      ret

by this:

F3 0F BD CE             lzcnt    ecx,esi
F3 0F BD C7             lzcnt    eax,edi
09 C8                   or       eax,ecx
C1 E8 05                shr      eax,5
C3                      ret

My plan now is to make the patch to handle the OR case only, what do you guys think?
Would X86ISelLowering still be the best place if only supporting the OR case?

Thanks!

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3588

Will do thanks!

[spatel]

In D23446#544797, @pgousseau wrote:

I am more confident the OR case brings better performances because we will be replacing

48 85 FF                test     rdi,rdi
0F 94 C0                sete     al
48 85 F6                test     rsi,rsi
0F 94 C1                sete     cl
08 C1                   or       cl,al
0F B6 C1                movzx    eax,cl
C3                      ret

by this:

F3 0F BD CE             lzcnt    ecx,esi
F3 0F BD C7             lzcnt    eax,edi
09 C8                   or       eax,ecx
C1 E8 05                shr      eax,5
C3                      ret

My plan now is to make the patch to handle the OR case only, what do you guys think?
Would X86ISelLowering still be the best place if only supporting the OR case?

The OR case certainly looks better in isolation (less instructions, less code size). If you are measuring perf improvements from that alone, I think we can be more confident that the transform to lzcnt is the source of that improvement. It's still not clear to me how the micro-benchmark was improved so much for the simpler case.

To match the OR pattern, I think you would either add some code to visitOr() or add tablegen patterns if it is possible to match the DAG nodes that way.

[pgousseau]

Hi Simon/Sanjay,

Following up with with the previous comments, this patch contains:

• Use of DAG.getZextOrTrunc as per Simon's comment.
• Removed support for the simple case.
• Added handling of OR based patterns.
• Added a case for SRL nodes in 'isTypeDesirableForOp()' as to favor 32 bits encoding when targetting X86.
• Added support for multiple OR patterns eg: (a1||a2||a3||a4||a5)

Let me know what you think,

Thanks!

[RKSimon]

Some quick remarks - I'll do more of review later after others have had a chance to look at it.

lib/Target/X86/X86ISelLowering.cpp

28986

Should we return early if !Subtarget.isCtlzFast()?

28992

Are we letting vector types through here?

31626

Comment this. Should this be part of a separate patch with its own tests? Its fine if its only exposed by this patch to leave it here, but it should have a comment either way.

test/CodeGen/X86/lzcnt-zext-cmp.ll

8

Test single input version to make sure it isn't being used.

[pgousseau]

lib/Target/X86/X86ISelLowering.cpp

28986

Yes that makes sense.

28992

Yes it seems that way, will have to restrict to 32-bit and 64-bit integers, thanks for spotting this.

31626

Yes would make sense to have a separate patch, will try to find an associated test case.

test/CodeGen/X86/lzcnt-zext-cmp.ll

8

Makes sense.

[pgousseau]

Following Simon's comments:

• Add an early return in case isCtlzFast is false
• Add a test checking that no transformations occurs on single input cases.
• Prevent transformation on 128-bit cases: int foo(int128_t a, int128_t b) { return a || b;} as this pessimized the codegen.
  • This requires constraining the pattern to the X86 form of an equality comparison with 0.
  • This remove the need from the earlier patch to modify isTypeDesirableForOp().

[RKSimon]

Possibly better test names than barXXXX, other than that I'm happy with this - @spatel ?

[spatel]

lib/Target/X86/X86ISelLowering.cpp

29007–29012

The pattern must always begin with zext. Is there some reason not to start in combineZext() rather than combineOr()?

[pgousseau]

Following Simon and Sanjay comments:

• Renamed tests to 'test_zext_cmpXX'
• Start pattern matching from combineZext instead of combineOR.

Also added missing "hasOneUse" checks to OR nodes.
Removed one unneeded check for "isSetCCCandidate"

Let me know what you guys think,

Thanks,

Pierre

[spatel]

LGTM. See inline for nits.

lib/Target/X86/X86ISelLowering.cpp

4193

Could remove or assert hasLZCNT()?

29075–29077

No need for braces here.

test/CodeGen/X86/lzcnt-zext-cmp.ll

202

Update name: "bar6"

[pgousseau]

lib/Target/X86/X86ISelLowering.cpp

4193

Yes makes sense, will remove before commit.

29075–29077

Will remove before commit.

test/CodeGen/X86/lzcnt-zext-cmp.ll

202

Thanks for spotting this, will fix before commit.

include/llvm/Target/TargetLowering.h

public:
   /// Lower TLS global address SDNode for target independent emulated TLS model.
   virtual SDValue LowerToTLSEmulatedModel(const GlobalAddressSDNode *GA,
                                           SelectionDAG &DAG) const;
 
   // seteq(x, 0) -> truncate(srl(ctlz(zext(x)), log2(#bits)))
   // If we're comparing for equality to zero and isCtlzFast is true, expose the
   // fact that this can be implemented as a ctlz/srl pair, so that the dag
   // combiner can fold the new nodes.
-  SDValue lowerCmpEqZeroToCtlzSrl(SDValue Op, SelectionDAG &DAG) const;
+  SDValue lowerCmpEqZeroToCtlzSrl(SDValue Op, EVT ExtTy,
+                                  SelectionDAG &DAG) const;
 
 private:
   SDValue simplifySetCCWithAnd(EVT VT, SDValue N0, SDValue N1,
                                ISD::CondCode Cond, DAGCombinerInfo &DCI,
                                const SDLoc &DL) const;
 };
 
 /// Given an LLVM IR type and return type attributes, compute the return value

lib/CodeGen/SelectionDAG/TargetLowering.cpp

SDValue TargetLowering::LowerToTLSEmulatedModel(const GlobalAddressSDNode *GA,
   MFI.setAdjustsStack(true);  // Is this only for X86 target?
   MFI.setHasCalls(true);
 
   assert((GA->getOffset() == 0) &&
          "Emulated TLS must have zero offset in GlobalAddressSDNode");
   return CallResult.first;
 }
 
-SDValue TargetLowering::lowerCmpEqZeroToCtlzSrl(SDValue Op,
+SDValue TargetLowering::lowerCmpEqZeroToCtlzSrl(SDValue Op, EVT ExtTy,
                                                 SelectionDAG &DAG) const {
   assert((Op->getOpcode() == ISD::SETCC) && "Input has to be a SETCC node.");
   if (!isCtlzFast())
     return SDValue();
   ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(2))->get();
   SDLoc dl(Op);
   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
     if (C->isNullValue() && CC == ISD::SETEQ) {
       EVT VT = Op.getOperand(0).getValueType();
       SDValue Zext = Op.getOperand(0);
       if (VT.bitsLT(MVT::i32)) {
         VT = MVT::i32;
         Zext = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Op.getOperand(0));
       }
       unsigned Log2b = Log2_32(VT.getSizeInBits());
       SDValue Clz = DAG.getNode(ISD::CTLZ, dl, VT, Zext);
       SDValue Scc = DAG.getNode(ISD::SRL, dl, VT, Clz,
                                 DAG.getConstant(Log2b, dl, MVT::i32));
-      return DAG.getNode(ISD::TRUNCATE, dl, MVT::i32, Scc);
+      if (ExtTy.bitsLE(VT))
+        return DAG.getNode(ISD::TRUNCATE, dl, ExtTy, Scc);
+      else
+        return DAG.getNode(ISD::ZERO_EXTEND, dl, ExtTy, Scc);
     }
   }
   return SDValue();
 }

lib/Target/PowerPC/PPCISelLowering.cpp

if (Op.getValueType() == MVT::v2i64) {
 
     // We handle most of these in the usual way.
     return Op;
   }
 
   // If we're comparing for equality to zero, expose the fact that this is
   // implemented as a ctlz/srl pair on ppc, so that the dag combiner can
   // fold the new nodes.
-  if (SDValue V = lowerCmpEqZeroToCtlzSrl(Op, DAG))
+  if (SDValue V = lowerCmpEqZeroToCtlzSrl(Op, MVT::i32, DAG))
     return V;
 
   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
     // Leave comparisons against 0 and -1 alone for now, since they're usually
     // optimized.  FIXME: revisit this when we can custom lower all setcc
     // optimizations.
     if (C->isAllOnesValue() || C->isNullValue())
       return SDValue();

lib/Target/X86/X86.td

def FeatureRDRAND  : SubtargetFeature<"rdrnd", "HasRDRAND", "true",
                                       "Support RDRAND instruction">;
 def FeatureF16C    : SubtargetFeature<"f16c", "HasF16C", "true",
                        "Support 16-bit floating point conversion instructions",
                        [FeatureAVX]>;
 def FeatureFSGSBase : SubtargetFeature<"fsgsbase", "HasFSGSBase", "true",
                                        "Support FS/GS Base instructions">;
 def FeatureLZCNT   : SubtargetFeature<"lzcnt", "HasLZCNT", "true",
                                       "Support LZCNT instruction">;
 def FeatureBMI     : SubtargetFeature<"bmi", "HasBMI", "true",
                                       "Support BMI instructions">;
 def FeatureBMI2    : SubtargetFeature<"bmi2", "HasBMI2", "true",
                                       "Support BMI2 instructions">;
 def FeatureRTM     : SubtargetFeature<"rtm", "HasRTM", "true",
                                       "Support RTM instructions">;
 def FeatureHLE     : SubtargetFeature<"hle", "HasHLE", "true",
                                       "Support HLE">;
 def FeatureADX     : SubtargetFeature<"adx", "HasADX", "true",
                                       "Support ADX instructions">;
 def FeatureSHA     : SubtargetFeature<"sha", "HasSHA", "true",

 // But if the code is scalar that probably means that the code has some kind of
 // dependency and we should care more about reducing the latency.
 def FeatureFastScalarFSQRT
     : SubtargetFeature<"fast-scalar-fsqrt", "HasFastScalarFSQRT",
                        "true", "Scalar SQRT is fast (disable Newton-Raphson)">;
 def FeatureFastVectorFSQRT
     : SubtargetFeature<"fast-vector-fsqrt", "HasFastVectorFSQRT",
                        "true", "Vector SQRT is fast (disable Newton-Raphson)">;
+// If lzcnt has equivalent latency/throughput to most simple integer ops, it can
+// be used to replace test/set sequences.
+def FeatureFastLZCNT
+    : SubtargetFeature<
+          "fast-lzcnt", "HasFastLZCNT", "true",
+          "LZCNT instructions are as fast as most simple integer ops">;
 
 //===----------------------------------------------------------------------===//
 // X86 processors supported.
 //===----------------------------------------------------------------------===//
 
 include "X86Schedule.td"
 
 def ProcIntelAtom : SubtargetFeature<"atom", "X86ProcFamily", "IntelAtom",
def : ProcessorModel<"btver2", BtVer2Model, [
   FeatureCMPXCHG16B,
   FeaturePRFCHW,
   FeatureAES,
   FeaturePCLMUL,
   FeatureBMI,
   FeatureF16C,
   FeatureMOVBE,
   FeatureLZCNT,
+  FeatureFastLZCNT,
   FeaturePOPCNT,
   FeatureXSAVE,
   FeatureXSAVEOPT,
   FeatureSlowSHLD,
   FeatureLAHFSAHF,
   FeatureFastPartialYMMWrite
 ]>;
 

lib/Target/X86/X86ISelLowering.h

public:
 
     /// This method returns the name of a target specific DAG node.
     const char *getTargetNodeName(unsigned Opcode) const override;
 
     bool isCheapToSpeculateCttz() const override;
 
     bool isCheapToSpeculateCtlz() const override;
 
+    bool isCtlzFast() const override;
+
     bool hasBitPreservingFPLogic(EVT VT) const override {
       return VT == MVT::f32 || VT == MVT::f64 || VT.isVector();
     }
 
     bool hasAndNotCompare(SDValue Y) const override;
 
     /// Return the value type to use for ISD::SETCC.
     EVT getSetCCResultType(const DataLayout &DL, LLVMContext &Context,

lib/Target/X86/X86ISelLowering.cpp

bool X86TargetLowering::isCheapToSpeculateCttz() const {
   return Subtarget.hasBMI();
 }
 
 bool X86TargetLowering::isCheapToSpeculateCtlz() const {
   // Speculate ctlz only if we can directly use LZCNT.
   return Subtarget.hasLZCNT();
 }
 
+bool X86TargetLowering::isCtlzFast() const {
+  return Subtarget.hasLZCNT() && Subtarget.hasFastLZCNT();
+}
+
 bool X86TargetLowering::hasAndNotCompare(SDValue Y) const {
   if (!Subtarget.hasBMI())
     return false;
 
   // There are only 32-bit and 64-bit forms for 'andn'.
   EVT VT = Y.getValueType();
   if (VT != MVT::i32 && VT != MVT::i64)
     return false;
if (DCI.isBeforeLegalizeOps())
     return SDValue();
 
   if (SDValue R = combineCompareEqual(N, DAG, DCI, Subtarget))
     return R;
 
   if (SDValue FPLogic = convertIntLogicToFPLogic(N, DAG, Subtarget))
     return FPLogic;
 
   if (SDValue R = combineLogicBlendIntoPBLENDV(N, DAG, Subtarget))
     return R;
 
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N->getValueType(0);
 
   if (VT != MVT::i16 && VT != MVT::i32 && VT != MVT::i64)
     return SDValue();
 
   // fold (or (x << c) | (y >> (64 - c))) ==> (shld64 x, y, c)
   bool OptForSize = DAG.getMachineFunction().getFunction()->optForSize();
 
   // SHLD/SHRD instructions have lower register pressure, but on some
   // platforms they have higher latency than the equivalent
   // series of shifts/or that would otherwise be generated.
   // Don't fold (or (x << c) | (y >> (64 - c))) if SHLD/SHRD instructions
   // have higher latencies and we are not optimizing for size.
   if (!OptForSize && Subtarget.isSHLDSlow())
     return SDValue();
 
   if (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SHL)
     std::swap(N0, N1);
   if (N0.getOpcode() != ISD::SHL || N1.getOpcode() != ISD::SRL)
     return SDValue();
   if (!N0.hasOneUse() || !N1.hasOneUse())
     return SDValue();
 
   SDValue ShAmt0 = N0.getOperand(1);
   if (ShAmt0.getValueType() != MVT::i8)
     return SDValue();
   SDValue ShAmt1 = N1.getOperand(1);
   if (ShAmt1.getValueType() != MVT::i8)
     return SDValue();
   if (ShAmt0.getOpcode() == ISD::TRUNCATE)
if (ConstantSDNode *MaskC = dyn_cast<ConstantSDNode>(Mask)) {
       if (MaskC->getSExtValue() == (Bits - 1) && ShAmt1Op0 == ShAmt0) {
         if (Op1.getOpcode() == InnerShift &&
             isa<ConstantSDNode>(Op1.getOperand(1)) &&
             Op1.getConstantOperandVal(1) == 1) {
           return DAG.getNode(Opc, DL, VT, Op0, Op1.getOperand(0),
                              DAG.getNode(ISD::TRUNCATE, DL, MVT::i8, ShAmt0));
         }
         // Test for ADD( Y, Y ) as an equivalent to SHL( Y, 1 ).
         if (InnerShift == ISD::SHL && Op1.getOpcode() == ISD::ADD &&
             Op1.getOperand(0) == Op1.getOperand(1)) {
           return DAG.getNode(Opc, DL, VT, Op0, Op1.getOperand(0),
                      DAG.getNode(ISD::TRUNCATE, DL, MVT::i8, ShAmt0));
         }
       }
     }
   }
 
   return SDValue();
 }
static SDValue combineZext(SDNode *N, SelectionDAG &DAG,
 
   if (VT.is256BitVector())
     if (SDValue R = WidenMaskArithmetic(N, DAG, DCI, Subtarget))
       return R;
 
   if (SDValue DivRem8 = getDivRem8(N, DAG))
     return DivRem8;
 
   if (SDValue NewAdd = promoteExtBeforeAdd(N, DAG, Subtarget))
     return NewAdd;
 
+  if (N0->getOpcode() == ISD::SETCC && N0->hasOneUse() &&
+      N0->getOperand(0).getValueType().bitsGE(MVT::i32) &&
+      N->getSimpleValueType(0).bitsGE(MVT::i32) && !DCI.isBeforeLegalize() &&
+      !DAG.getMachineFunction().getFunction()->optForSize())
+    if (SDValue V = Subtarget.getTargetLowering()->lowerCmpEqZeroToCtlzSrl(
+            N0, N->getValueType(0), DAG)) {
+      return V;
+    }
+
   return SDValue();
 }
 
 /// Optimize x == -y --> x+y == 0
 ///          x != -y --> x+y != 0
 static SDValue combineSetCC(SDNode *N, SelectionDAG &DAG,
                             const X86Subtarget &Subtarget) {
   ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get();
   SDValue LHS = N->getOperand(0);
   SDValue RHS = N->getOperand(1);
   EVT VT = N->getValueType(0);
   SDLoc DL(N);
 

 /// Return true if the target has native support for the specified value type
 /// and it is 'desirable' to use the type for the given node type. e.g. On x86
 /// i16 is legal, but undesirable since i16 instruction encodings are longer and
 /// some i16 instructions are slow.
 bool X86TargetLowering::isTypeDesirableForOp(unsigned Opc, EVT VT) const {
   if (!isTypeLegal(VT))
     return false;
   if (VT != MVT::i16)
     return true;
 
   switch (Opc) {
   default:
     return true;
   case ISD::LOAD:
   case ISD::SIGN_EXTEND:
   case ISD::ZERO_EXTEND:
   case ISD::ANY_EXTEND:

lib/Target/X86/X86InstrInfo.td

 def HasFMA4      : Predicate<"Subtarget->hasFMA4()">;
 def HasXOP       : Predicate<"Subtarget->hasXOP()">;
 def HasTBM       : Predicate<"Subtarget->hasTBM()">;
 def HasMOVBE     : Predicate<"Subtarget->hasMOVBE()">;
 def HasRDRAND    : Predicate<"Subtarget->hasRDRAND()">;
 def HasF16C      : Predicate<"Subtarget->hasF16C()">;
 def HasFSGSBase  : Predicate<"Subtarget->hasFSGSBase()">;
 def HasLZCNT     : Predicate<"Subtarget->hasLZCNT()">;
 def HasBMI       : Predicate<"Subtarget->hasBMI()">;
 def HasBMI2      : Predicate<"Subtarget->hasBMI2()">;
 def HasVBMI      : Predicate<"Subtarget->hasVBMI()">,
                      AssemblerPredicate<"FeatureVBMI", "AVX-512 VBMI ISA">;
 def HasIFMA      : Predicate<"Subtarget->hasIFMA()">,
                      AssemblerPredicate<"FeatureIFMA", "AVX-512 IFMA ISA">;
 def HasRTM       : Predicate<"Subtarget->hasRTM()">;
 def HasHLE       : Predicate<"Subtarget->hasHLE()">;
 def HasTSX       : Predicate<"Subtarget->hasRTM() || Subtarget->hasHLE()">;

 def OptForSize   : Predicate<"OptForSize">;
 def OptForMinSize : Predicate<"OptForMinSize">;
 def OptForSpeed  : Predicate<"!OptForSize">;
 def FastBTMem    : Predicate<"!Subtarget->isBTMemSlow()">;
 def CallImmAddr  : Predicate<"Subtarget->isLegalToCallImmediateAddr()">;
 def FavorMemIndirectCall  : Predicate<"!Subtarget->callRegIndirect()">;
 def NotSlowIncDec : Predicate<"!Subtarget->slowIncDec()">;
 def HasFastMem32 : Predicate<"!Subtarget->isUnalignedMem32Slow()">;
+def HasFastLZCNT : Predicate<"Subtarget->hasFastLZCNT()">;
 def HasMFence    : Predicate<"Subtarget->hasMFence()">;
 
 //===----------------------------------------------------------------------===//
 // X86 Instruction Format Definitions.
 //
 
 include "X86InstrFormats.td"
 

lib/Target/X86/X86Subtarget.h

protected:
   /// True if 8-bit divisions are significantly faster than
   /// 32-bit divisions and should be used when possible.
   bool HasSlowDivide32;
 
   /// True if 16-bit divides are significantly faster than
   /// 64-bit divisions and should be used when possible.
   bool HasSlowDivide64;
 
+  /// True if LZCNT instruction is fast.
+  bool HasFastLZCNT;
+
   /// True if the short functions should be padded to prevent
   /// a stall when returning too early.
   bool PadShortFunctions;
 
   /// True if the Calls with memory reference should be converted
   /// to a register-based indirect call.
   bool CallRegIndirect;
 
public:
   bool hasAnyFMA() const { return hasFMA() || hasFMA4() || hasAVX512(); }
   bool hasXOP() const { return HasXOP; }
   bool hasTBM() const { return HasTBM; }
   bool hasMOVBE() const { return HasMOVBE; }
   bool hasRDRAND() const { return HasRDRAND; }
   bool hasF16C() const { return HasF16C; }
   bool hasFSGSBase() const { return HasFSGSBase; }
   bool hasLZCNT() const { return HasLZCNT; }
   bool hasBMI() const { return HasBMI; }
   bool hasBMI2() const { return HasBMI2; }
   bool hasVBMI() const { return HasVBMI; }
   bool hasIFMA() const { return HasIFMA; }
   bool hasRTM() const { return HasRTM; }
   bool hasHLE() const { return HasHLE; }
   bool hasADX() const { return HasADX; }
   bool hasSHA() const { return HasSHA; }
   bool hasPRFCHW() const { return HasPRFCHW; }
   bool hasRDSEED() const { return HasRDSEED; }
   bool hasLAHFSAHF() const { return HasLAHFSAHF; }
   bool hasMWAITX() const { return HasMWAITX; }
   bool isBTMemSlow() const { return IsBTMemSlow; }
   bool isSHLDSlow() const { return IsSHLDSlow; }
   bool isUnalignedMem16Slow() const { return IsUAMem16Slow; }
   bool isUnalignedMem32Slow() const { return IsUAMem32Slow; }
   bool hasSSEUnalignedMem() const { return HasSSEUnalignedMem; }
   bool hasCmpxchg16b() const { return HasCmpxchg16b; }
   bool useLeaForSP() const { return UseLeaForSP; }
   bool hasFastPartialYMMWrite() const { return HasFastPartialYMMWrite; }
   bool hasFastScalarFSQRT() const { return HasFastScalarFSQRT; }
   bool hasFastVectorFSQRT() const { return HasFastVectorFSQRT; }
+  bool hasFastLZCNT() const { return HasFastLZCNT; }
   bool hasSlowDivide32() const { return HasSlowDivide32; }
   bool hasSlowDivide64() const { return HasSlowDivide64; }
   bool padShortFunctions() const { return PadShortFunctions; }
   bool callRegIndirect() const { return CallRegIndirect; }
   bool LEAusesAG() const { return LEAUsesAG; }
   bool slowLEA() const { return SlowLEA; }
   bool slowIncDec() const { return SlowIncDec; }
   bool hasCDI() const { return HasCDI; }

lib/Target/X86/X86Subtarget.cpp

void X86Subtarget::initializeEnvironment() {
   HasFMA4 = false;
   HasXOP = false;
   HasTBM = false;
   HasMOVBE = false;
   HasRDRAND = false;
   HasF16C = false;
   HasFSGSBase = false;
   HasLZCNT = false;
   HasBMI = false;
   HasBMI2 = false;
   HasVBMI = false;
   HasIFMA = false;
   HasRTM = false;
   HasHLE = false;
   HasERI = false;
   HasCDI = false;
   HasPFI = false;
void X86Subtarget::initializeEnvironment() {
   IsUAMem16Slow = false;
   IsUAMem32Slow = false;
   HasSSEUnalignedMem = false;
   HasCmpxchg16b = false;
   UseLeaForSP = false;
   HasFastPartialYMMWrite = false;
   HasFastScalarFSQRT = false;
   HasFastVectorFSQRT = false;
+  HasFastLZCNT = false;
   HasSlowDivide32 = false;
   HasSlowDivide64 = false;
   PadShortFunctions = false;
   CallRegIndirect = false;
   LEAUsesAG = false;
   SlowLEA = false;
   SlowIncDec = false;
   stackAlignment = 4;

test/CodeGen/X86/lzcnt-zext-cmp.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; Test patterns which generates lzcnt instructions.
+; Eg: zext(setcc(cmp)) -> shr(lzcnt)
+; RUN: llc < %s -mtriple=x86_64-pc-linux -mcpu=btver2 | FileCheck %s
+; RUN: llc < %s -mtriple=x86_64-pc-linux -mcpu=btver2 -mattr=-fast-lzcnt | FileCheck --check-prefix=NOFASTLZCNT %s
+
+; Test 32-bit input, 32-bit output.
+define i32 @foo1(i32 %a) {
+; CHECK-LABEL: foo1:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    lzcntl %edi, %eax
+; CHECK-NEXT:    shrl $5, %eax
+; CHECK-NEXT:    retq
+;
+; NOFASTLZCNT-LABEL: foo1:
+; NOFASTLZCNT:       # BB#0:
+; NOFASTLZCNT-NEXT:    xorl %eax, %eax
+; NOFASTLZCNT-NEXT:    testl %edi, %edi
+; NOFASTLZCNT-NEXT:    sete %al
+; NOFASTLZCNT-NEXT:    retq
+  %cmp = icmp eq i32 %a, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+; Test 32-bit input, 64-bit output.
+define i64 @foo2(i32 %a) {
+; CHECK-LABEL: foo2:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    lzcntl %edi, %eax
+; CHECK-NEXT:    shrl $5, %eax
+; CHECK-NEXT:    retq
+;
+; NOFASTLZCNT-LABEL: foo2:
+; NOFASTLZCNT:       # BB#0:
+; NOFASTLZCNT-NEXT:    xorl %eax, %eax
+; NOFASTLZCNT-NEXT:    testl %edi, %edi
+; NOFASTLZCNT-NEXT:    sete %al
+; NOFASTLZCNT-NEXT:    retq
+  %cmp = icmp eq i32 %a, 0
+  %conv1 = zext i1 %cmp to i64
+  ret i64 %conv1
+}
+
+; Test 64-bit input, 64-bit output.
+define i64 @foo3(i64 %a) {
+; CHECK-LABEL: foo3:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    lzcntq %rdi, %rax
+; CHECK-NEXT:    shrq $6, %rax
+; CHECK-NEXT:    retq
+;
+; NOFASTLZCNT-LABEL: foo3:
+; NOFASTLZCNT:       # BB#0:
+; NOFASTLZCNT-NEXT:    xorl %eax, %eax
+; NOFASTLZCNT-NEXT:    testq %rdi, %rdi
+; NOFASTLZCNT-NEXT:    sete %al
+; NOFASTLZCNT-NEXT:    retq
+  %cmp = icmp eq i64 %a, 0
+  %conv1 = zext i1 %cmp to i64
+  ret i64 %conv1
+}
+
+; Test 64-bit input, 32-bit output.
+define i32 @foo4(i64 %a) {
+; CHECK-LABEL: foo4:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    lzcntq %rdi, %rax
+; CHECK-NEXT:    shrq $6, %rax
+; CHECK-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
+; CHECK-NEXT:    retq
+;
+; NOFASTLZCNT-LABEL: foo4:
+; NOFASTLZCNT:       # BB#0:
+; NOFASTLZCNT-NEXT:    xorl %eax, %eax
+; NOFASTLZCNT-NEXT:    testq %rdi, %rdi
+; NOFASTLZCNT-NEXT:    sete %al
+; NOFASTLZCNT-NEXT:    retq
+  %cmp = icmp eq i64 %a, 0
+  %conv1 = zext i1 %cmp to i32
+  ret i32 %conv1
+}
+
+; Test 16-bit input, 16-bit output.
+define i16 @foo5(i16 %a) {
+; CHECK-LABEL: foo5:
+; CHECK:       # BB#0:
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    testw %di, %di
+; CHECK-NEXT:    sete %al
+; CHECK-NEXT:    # kill: %AX<def> %AX<kill> %EAX<kill>
+; CHECK-NEXT:    retq
+;
+; NOFASTLZCNT-LABEL: foo5:
+; NOFASTLZCNT:       # BB#0:
+; NOFASTLZCNT-NEXT:    xorl %eax, %eax
+; NOFASTLZCNT-NEXT:    testw %di, %di
+; NOFASTLZCNT-NEXT:    sete %al
+; NOFASTLZCNT-NEXT:    # kill: %AX<def> %AX<kill> %EAX<kill>
+; NOFASTLZCNT-NEXT:    retq
+  %cmp = icmp eq i16 %a, 0
+  %conv = zext i1 %cmp to i16
+  ret i16 %conv
+}