[TargetLowering] Optimize expanded SRL/SHL fed into SETCC ne/eq 0

[fzhinkin]

Summary

During legalization SHL/SRL nodes could be expanded into expression
that rotates low/high part of original input and then apply OR to
rotated part and other part. If the result of this operation is
compared for equality/not-equality with zero then rotation could
be removed as it does not affect comparision result.

Bug report: https://llvm.org/PR50197

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3411

Please use SDValue. LLVM is pretty conservative about the use of auto. https://llvm.org/docs/CodingStandards.html#use-auto-type-deduction-to-make-code-more-readable

llvm/test/CodeGen/ARM/arm-icmp-shift-opt.ll

118 ↗

(On Diff #378602)

"does not match" -> "do not match" since constants is plural.

[fzhinkin]

Fixed typos, cleaned up the code.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3411

Thanks for pointing to it, fixed.

[fzhinkin]

Ping

[RKSimon]

please can you pre-commit these new tests to trunk with current codegen and then rebase to show the diff?

llvm/test/CodeGen/AArch64/arm64-icmp-shift-opt.ll

1 ↗

(On Diff #378795)

rename icmp-shift-opt.ll?

llvm/test/CodeGen/ARM/arm-icmp-shift-opt.ll

1 ↗

(On Diff #378795)

rename icmp-shift-opt.ll?

llvm/test/CodeGen/X86/icmp-shift-opt.ll

8

add nounwind to reduce cfi noise

[fzhinkin]

Renamed test files, added nounwind attribute.

[fzhinkin]

Fixed typos in ARM tests.

[fzhinkin]

In D111530#3074772, @RKSimon wrote:

please can you pre-commit these new tests to trunk with current codegen and then rebase to show the diff?

I don't have a permission to commit changes, so I'll appreciate if you can help me with it. Here's the patch adding new tests with checks generated for current trunk:

50197_precommit_tests.patch13 KBDownload

[RKSimon]

In D111530#3076353, @fzhinkin wrote:

In D111530#3074772, @RKSimon wrote:

please can you pre-commit these new tests to trunk with current codegen and then rebase to show the diff?

I don't have a permission to commit changes, so I'll appreciate if you can help me with it. Here's the patch adding new tests with checks generated for current trunk:

50197_precommit_tests.patch13 KBDownload

Done (sorry for the delay) - please can you rebase?

[fzhinkin]

Rebased to current trunk

[fzhinkin]

In D111530#3080538, @RKSimon wrote:

In D111530#3076353, @fzhinkin wrote:

In D111530#3074772, @RKSimon wrote:

please can you pre-commit these new tests to trunk with current codegen and then rebase to show the diff?

I don't have a permission to commit changes, so I'll appreciate if you can help me with it. Here's the patch adding new tests with checks generated for current trunk:

50197_precommit_tests.patch13 KBDownload

Done (sorry for the delay) - please can you rebase?

Thank you! Rebase done.

Also, thanks for adding i686 to X86's test, it revealed that my optimization does not work when we're legalizing i128 to i32. I'll check if that case could be easily supported.

[fzhinkin]

In D111530#3080743, @fzhinkin wrote:

In D111530#3080538, @RKSimon wrote:

In D111530#3076353, @fzhinkin wrote:

In D111530#3074772, @RKSimon wrote:

please can you pre-commit these new tests to trunk with current codegen and then rebase to show the diff?

I don't have a permission to commit changes, so I'll appreciate if you can help me with it. Here's the patch adding new tests with checks generated for current trunk:

50197_precommit_tests.patch13 KBDownload

Done (sorry for the delay) - please can you rebase?

Thank you! Rebase done.

Also, thanks for adding i686 to X86's test, it revealed that my optimization does not work when we're legalizing i128 to i32. I'll check if that case could be easily supported.

Handling of trees generated during legalization of i128/i256/etc to i32 is relatively simple, but in case of i686 some of these expressions are folded into funnel shifts before SimplifySetCC is applied to setcc.
I see two options here (but I'm far from being an expert, so correct me if I'm wrong and there are simpler alternatives):

1. support various instructions (funnel shifts, rotations, bit/byte swaps) in TargetLowering::optimizeSetCCOfExpandedShift in addition to SHL/SRL;
2. support only SHL/SRL in TargetLowering::optimizeSetCCOfExpandedShift and apply it in DAGTypeLegalizer::IntegerExpandSetCCOperands right after setcc's operands expansion.

Personally I'm leaning towards second option as it should be less fragile and easier to maintain.

[RKSimon]

In D111530#3083495, @fzhinkin wrote:

Handling of trees generated during legalization of i128/i256/etc to i32 is relatively simple, but in case of i686 some of these expressions are folded into funnel shifts before SimplifySetCC is applied to setcc.
I see two options here (but I'm far from being an expert, so correct me if I'm wrong and there are simpler alternatives):

1. support various instructions (funnel shifts, rotations, bit/byte swaps) in TargetLowering::optimizeSetCCOfExpandedShift in addition to SHL/SRL;
2. support only SHL/SRL in TargetLowering::optimizeSetCCOfExpandedShift and apply it in DAGTypeLegalizer::IntegerExpandSetCCOperands right after setcc's operands expansion.

Personally I'm leaning towards second option as it should be less fragile and easier to maintain.

Makes sense to try (2) first - although I expect at least partial support for (1) might end up being required - you are handling a pattern that is almost a funnel shift much of the time.

[fzhinkin]

Reimplemented expanded shift matching to handle funnel shifts.

[fzhinkin]

In D111530#3083530, @RKSimon wrote:

In D111530#3083495, @fzhinkin wrote:

Handling of trees generated during legalization of i128/i256/etc to i32 is relatively simple, but in case of i686 some of these expressions are folded into funnel shifts before SimplifySetCC is applied to setcc.
I see two options here (but I'm far from being an expert, so correct me if I'm wrong and there are simpler alternatives):

1. support various instructions (funnel shifts, rotations, bit/byte swaps) in TargetLowering::optimizeSetCCOfExpandedShift in addition to SHL/SRL;
2. support only SHL/SRL in TargetLowering::optimizeSetCCOfExpandedShift and apply it in DAGTypeLegalizer::IntegerExpandSetCCOperands right after setcc's operands expansion.

Personally I'm leaning towards second option as it should be less fragile and easier to maintain.

Makes sense to try (2) first - although I expect at least partial support for (1) might end up being required - you are handling a pattern that is almost a funnel shift much of the time.

Unfortunately (2) doesn't work well, because nodes created during shift expansion may have several uses until type legalization finished, so I gave it up.

Instead I supported funnel shifts TargetLowering::optimizeSetCCOfExpandedShift (did not support rotations and bit/byte swaps because such nodes should not be created during expanded shift's combining).

While optimization works fine for i686 now there is an issue with AArch64: shifts expanded from types wider than i128 won't be optimized (see @opt_setcc_shl_ne_zero_i256) because for AArch64 funnel shift alike patterns combined into AArch64ISD::EXTR instead of FSHL/FSHR. I attempted to fix it by implementing (2), but the solution was fragile and didn't work in some cases.

[RKSimon]

In D111530#3100864, @fzhinkin wrote:

Instead I supported funnel shifts TargetLowering::optimizeSetCCOfExpandedShift (did not support rotations and bit/byte swaps because such nodes should not be created during expanded shift's combining).

While optimization works fine for i686 now there is an issue with AArch64: shifts expanded from types wider than i128 won't be optimized (see @opt_setcc_shl_ne_zero_i256) because for AArch64 funnel shift alike patterns combined into AArch64ISD::EXTR instead of FSHL/FSHR. I attempted to fix it by implementing (2), but the solution was fragile and didn't work in some cases.

I'm hoping D112443 will help with this

[RKSimon]

In D111530#3101173, @RKSimon wrote:

In D111530#3100864, @fzhinkin wrote:

Instead I supported funnel shifts TargetLowering::optimizeSetCCOfExpandedShift (did not support rotations and bit/byte swaps because such nodes should not be created during expanded shift's combining).

While optimization works fine for i686 now there is an issue with AArch64: shifts expanded from types wider than i128 won't be optimized (see @opt_setcc_shl_ne_zero_i256) because for AArch64 funnel shift alike patterns combined into AArch64ISD::EXTR instead of FSHL/FSHR. I attempted to fix it by implementing (2), but the solution was fragile and didn't work in some cases.

I'm hoping D112443 will help with this

D112443 has been committed - please can you see if it helps?

[fzhinkin]

Rebase

[fzhinkin]

In D111530#3102654, @RKSimon wrote:

In D111530#3101173, @RKSimon wrote:

In D111530#3100864, @fzhinkin wrote:

Instead I supported funnel shifts TargetLowering::optimizeSetCCOfExpandedShift (did not support rotations and bit/byte swaps because such nodes should not be created during expanded shift's combining).

While optimization works fine for i686 now there is an issue with AArch64: shifts expanded from types wider than i128 won't be optimized (see @opt_setcc_shl_ne_zero_i256) because for AArch64 funnel shift alike patterns combined into AArch64ISD::EXTR instead of FSHL/FSHR. I attempted to fix it by implementing (2), but the solution was fragile and didn't work in some cases.

I'm hoping D112443 will help with this

D112443 has been committed - please can you see if it helps?

Unfortunately it didn't affect AArch64ISD::EXTR combining.

[lebedev.ri]

X86 changes look good. Are AArch64 changes actually a regressions, or are they just changes?

[fzhinkin]

In D111530#3104045, @lebedev.ri wrote:

X86 changes look good. Are AArch64 changes actually a regressions, or are they just changes?

Thanks!
There is no regression for AArch64: better code sequence is generated for legalized i128 shifts, but there is no improvement for wider types (like i256).

[lebedev.ri]

In D111530#3104196, @fzhinkin wrote:

In D111530#3104045, @lebedev.ri wrote:

X86 changes look good. Are AArch64 changes actually a regressions, or are they just changes?

Thanks!
There is no regression for AArch64: better code sequence is generated for legalized i128 shifts, but there is no improvement for wider types (like i256).

A change that only triggers for some (common?) cases and causes no regressions is a better step forward
than a change that indiscriminately triggers on everything and causes widespread regressions i would think :)

[fzhinkin]

In D111530#3104217, @lebedev.ri wrote:

In D111530#3104196, @fzhinkin wrote:

In D111530#3104045, @lebedev.ri wrote:

X86 changes look good. Are AArch64 changes actually a regressions, or are they just changes?

Thanks!
There is no regression for AArch64: better code sequence is generated for legalized i128 shifts, but there is no improvement for wider types (like i256).

A change that only triggers for some (common?) cases and causes no regressions is a better step forward
than a change that indiscriminately triggers on everything and causes widespread regressions i would think :)

I agree. I don't think that i256 and wider types are something frequently you can see in real code.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3399

Lots of comment duplication - description to header, and keep the code snippet here?

3440

const APInt &C

3476

(style) Break apart if-else chains when they return.

3486

const APInt &CVal =

3497

Why was i4096 of particular interest?

We have a default depth limit we use for this kind of thing: SelectionDAG::MaxRecursionDepth = 6, also, normally we increment a depth to that value instead of decrementing a height.

3508

(style) Don't use auto

3517

Can't you avoid pushing results by just OR'ing the results once?

SDValue Reduction = Result[0];
for (size_t I = 1, E = Results.size(); I < E; ++I)
  Reduction = DAG.getNode(ISD::OR, DL, N0.getValueType(), Reduction, Result[I]);

[fzhinkin]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3497

Nothing really interesting about i4096, just mentioned it to depict that max height of 8 is large enough for any type someone will use in actual code.

I'll change 8 to SelectionDAG::MaxRecursionDepth and decrement to increment. Thanks!

3517

I'm pushing ORs back to the results list to generate balanced tree (and shorten critical path's length). And it pays off at least for ARM:

; llc -O3 -mtriple=armv7 test.ll
define i1 @opt_setcc_shl_ne_zero_i128(i128 %a) nounwind {
   %shl = shl i128 %a, 17
   %cmp = icmp ne i128 %shl, 0
   ret i1 %cmp
}

Code generated using current implementation:

opt_setcc_shl_ne_zero_i128:
@ %bb.0:
	orr	r2, r2, r3, lsl #17
	orr	r0, r1, r0
	orrs	r0, r0, r2
	movwne	r0, #1
	bx	lr

Code generated using implementation OR'ing in place:

opt_setcc_shl_ne_zero_i128:
@ %bb.0:
	orr	r0, r1, r0
	orr	r0, r0, r2
	orr	r0, r0, r3, lsl #17
	cmp	r0, #0
	movwne	r0, #1
	bx	lr

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3517

OK - maybe mention that in the comment?

[fzhinkin]

Cleanup

[fzhinkin]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3517

Updated the comment and fixed all other issues you've mentioned earlier.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3410

Use isNullOrNullSplat?

[fzhinkin]

Simplified expression in assertion.

[RKSimon]

llvm/test/CodeGen/AArch64/icmp-shift-opt.ll

151

pre-commit?

[fzhinkin]

llvm/test/CodeGen/AArch64/icmp-shift-opt.ll

151

Will appreciate if you can help me with committing it:

50197_precommit_tests.patch.11 KBDownload

[fzhinkin]

llvm/test/CodeGen/AArch64/icmp-shift-opt.ll

151

thanks!

[fzhinkin]

Rebase

[RKSimon]

llvm/test/CodeGen/ARM/icmp-shift-opt.ll

150

sorry - I didn't add this one - I'll commit this shortly.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

4155

This is doing something pretty similar, its more limited to the 'concat' pattern but handles the -1 'allbits' case as well.

[fzhinkin]

Rebase

[fzhinkin]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

4155

Are you suggesting to extract and reuse code common to both optimizations or to support -1 in optimizeSetCCOfExpandedShift?

llvm/test/CodeGen/ARM/icmp-shift-opt.ll

150

Thank you.

[fzhinkin]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

4155

It does not make sense to support -1 in optimizeSetCCOfExpandedShift because a shifted value (the method support only logical shifts) is never equal to -1.

For me it seems like "concat" optimization and optimizeSetCCOfExpandedShift are not so similar. "concat" opt merges OR arms in place, but optimizeSetCCOfExpandedShift eliminate shift pairs that are scattered among the tree and the whole tree should be scanned before final OR reduction is applied.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

4155

OK - what about the CmpZero case - is that redundant dead code now?

[fzhinkin]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

4155

CmpZero case is redundant only if Y's type was lowered to a pair of values having narrower type (X and Y are i64 and comp. target is armv7).

However, concat optimization still works for following cases not supported in optimizeSetCCOfExpandedShift:

• X and Y whose type was legal (X and Y are i64, x86_64 is the target);
• X and Y are vectors.

I did not support vector types in optimizeSetCCOfExpandedShift because it seems impossible to get a DAG with appropriate shape during vectors legalization.

[fzhinkin]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

4155

MergeConcat's CmpZero case will continue to work and there is no easy way to exclude cases that could be handled by both optimizeSetCCOfExpandedShift and MergeConcat. So I think it does make sense to apply optimizeSetCCOfExpandedShift after MergeConcat and only when types legalization is complete.

[fzhinkin]

Reordered MergeConcat and optimizeSetCCOfExpandedShift optimizations.

[fzhinkin]

Cleanup

[fzhinkin]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

4155

So I think it does make sense to apply optimizeSetCCOfExpandedShift after MergeConcat and only when types legalization is complete.

optimizeSetCCOfExpandedShift could not be disabled during type legalization phase, because some cases won't be handled then.

[fzhinkin]

Rebase

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3456

You might be better off pulling this lambda out as static helper function instead of relying on recursive lambda calls?

[fzhinkin]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3456

Yes, thanks for suggestion. I think it'll be better to move both lambdas as well result reduction to a helper class.

[fzhinkin]

Move most of optimization's code into helper class.

[RKSimon]

Any more comments? @lebedev.ri @spatel @pengfei

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3413

don't pass SDValue by reference - its just a pointer + int - it should pass by value very cheaply

3469

don't pass SDValue by reference

[fzhinkin]

Pass SDValue by value.

[spatel]

I didn't step through everything here, so I may not be seeing the entire problem.

There are 2 or more relatively simple folds that are missing both in IR and DAG, and adding those might solve this more generally and more easily than the proposed patch.

Here are examples in Alive2:
https://alive2.llvm.org/ce/z/KNQuYm
https://alive2.llvm.org/ce/z/LKLpo3

So it might be possible to solve the motivating bug without starting from icmp/setcc -- it's really a problem of combining shifts and funnel shifts in a way that is better for analysis/codegen.

We can show a potential codegen improvement for x86 with a minimal example:

% cat fsh.ll          
declare i32 @llvm.fshl.i32 (i32, i32, i32)
declare i32 @llvm.fshr.i32 (i32, i32, i32)

define i32 @src(i32 %x, i32 %y) {
  %y5 = shl i32 %y, 5
  %fun3 = call i32 @llvm.fshr.i32(i32 %x, i32 %y, i32 27)
  %or2 = or i32 %fun3, %y5
  ret i32 %or2
}


define i32 @tgt(i32 %x, i32 %y) {
  %x5 = shl i32 %x, 5
  %rot3 = call i32 @llvm.fshl.i32(i32 %y, i32 %y, i32 5)
  %or2 = or i32 %rot3, %x5
  ret i32 %or2
}

% llc -o - fsh.ll
_src:
	shldl	$5, %esi, %edi  ; avoid shld if possible because it is slow on some targets
	movl	%esi, %eax
	shll	$5, %eax
	orl	%edi, %eax
	ret

_tgt:
	movl	%esi, %eax
	shll	$5, %edi
	roll	$5, %eax
	orl	%edi, %eax
	retq

[spatel]

If I'm seeing the patterns correctly, there's at least one more possibility.
If a target has a legal+fast funnel shift, we could eliminate the shift completely from this sequence instead of forming a rotate:
https://alive2.llvm.org/ce/z/PpGpy3

[fzhinkin]

In D111530#3329473, @spatel wrote:

I didn't step through everything here, so I may not be seeing the entire problem.

There are 2 or more relatively simple folds that are missing both in IR and DAG, and adding those might solve this more generally and more easily than the proposed patch.

Here are examples in Alive2:
https://alive2.llvm.org/ce/z/KNQuYm
https://alive2.llvm.org/ce/z/LKLpo3

So it might be possible to solve the motivating bug without starting from icmp/setcc -- it's really a problem of combining shifts and funnel shifts in a way that is better for analysis/codegen.

Transformation from this change is not only about shifts recombination but (and mostly) about removal of shifts that will rotate bits of a value compared with zero. In that particular case such shifts could be safely eliminated, but in any other case it's not possible as it will change the result.

By combining shifts differently (by replacing shift + funnel shift with rotate + shift, for example) we can improve performance on some platforms, but the case with icmp eq/ne 0 would still have to be handled separately as it allow transformation that is illegal otherwise.

[fzhinkin]

In D111530#3332382, @fzhinkin wrote:

In D111530#3329473, @spatel wrote:

I didn't step through everything here, so I may not be seeing the entire problem.

There are 2 or more relatively simple folds that are missing both in IR and DAG, and adding those might solve this more generally and more easily than the proposed patch.

Here are examples in Alive2:
https://alive2.llvm.org/ce/z/KNQuYm
https://alive2.llvm.org/ce/z/LKLpo3

So it might be possible to solve the motivating bug without starting from icmp/setcc -- it's really a problem of combining shifts and funnel shifts in a way that is better for analysis/codegen.

Transformation from this change is not only about shifts recombination but (and mostly) about removal of shifts that will rotate bits of a value compared with zero. In that particular case such shifts could be safely eliminated, but in any other case it's not possible as it will change the result.

By combining shifts differently (by replacing shift + funnel shift with rotate + shift, for example) we can improve performance on some platforms, but the case with icmp eq/ne 0 would still have to be handled separately as it allow transformation that is illegal otherwise.

On the other hand it's just a special case where we're using "identify" instead of rotation.

I agree that a general solution for shifts combining could be developed and used instead of the transformation from this change.

[fzhinkin]

@spatel I remembered why I didn't add a transformation into DAGCombiner and decided to perform specific transformation in TargetLowering::SimplifySetCC:

• to remove unnecessary shifts we have to know that legalized shift was an input of setcc eq/ne 0 and expanded shifts are not yet combined when DAGCombiner is visiting setcc;
• and it's actually better to apply the optimization before shifts combining because for some targets shifts could be combined to some target-specific node instead of a funnel shift (for example, for AArch64 shifts implemening funnel shift will be combined into EXTR node instead of FSHL/FSHR).

As a generalization I was thinking to extract rotation-matching part of this optimization to a separate method that will actually combine shifts into rotations, call if from both TargetLowering::SimplifySetCC and DAGCombiner::MatchRotate and then eliminate rotations in TargetLowering::SimplifySetCC.
But it seems like or-shift expression trees that deep enough to apply such optimization should be quite rare. In fact, I'm hardly imagining cases other than setcc eq/ne 0.

[spatel]

In D111530#3340750, @fzhinkin wrote:

@spatel I remembered why I didn't add a transformation into DAGCombiner and decided to perform specific transformation in TargetLowering::SimplifySetCC:

• to remove unnecessary shifts we have to know that legalized shift was an input of setcc eq/ne 0 and expanded shifts are not yet combined when DAGCombiner is visiting setcc;
• and it's actually better to apply the optimization before shifts combining because for some targets shifts could be combined to some target-specific node instead of a funnel shift (for example, for AArch64 shifts implemening funnel shift will be combined into EXTR node instead of FSHL/FSHR).

As a generalization I was thinking to extract rotation-matching part of this optimization to a separate method that will actually combine shifts into rotations, call if from both TargetLowering::SimplifySetCC and DAGCombiner::MatchRotate and then eliminate rotations in TargetLowering::SimplifySetCC.
But it seems like or-shift expression trees that deep enough to apply such optimization should be quite rare. In fact, I'm hardly imagining cases other than setcc eq/ne 0.

I'm not convinced yet that we need to include the setcc to handle the motivating bug.

I noticed that we're missing an even more basic logic+shift transform (we miss this in IR too):
https://alive2.llvm.org/ce/z/RZjxTE

I think that transform should work with any shift opcode and any bitwise logic opcode (as long as they are matching opcodes within any one transform).

Would this patch still get the optimal result for the transformed code?

[spatel]

In D111530#3332382, @fzhinkin wrote:

Transformation from this change is not only about shifts recombination but (and mostly) about removal of shifts that will rotate bits of a value compared with zero. In that particular case such shifts could be safely eliminated, but in any other case it's not possible as it will change the result.

Now that we're reducing the pattern more with:
acb96ffd149db447
...I see what you mean. We were missing a transform that already exists in IR:
69684b84c61c

We still need 1-2 other patches to fix the motivating example, but I think we can get there with some small peepholes.

[RKSimon]

@fzhinkin @spatel Is this patch still relevant?

[fzhinkin]

In D111530#3484697, @RKSimon wrote:

@fzhinkin @spatel Is this patch still relevant?

@spatel fixed almost all cases (huge thanks for that), so this patch is no longer relevant.

llvm/include/llvm/CodeGen/TargetLowering.h

SDValue optimizeSetCCOfSignedTruncationCheck(EVT SCCVT, SDValue N0,
                                                DAGCombinerInfo &DCI,
                                                const SDLoc &DL) const;
 
   // (X & (C l>>/<< Y)) ==/!= 0  -->  ((X <</l>> Y) & C) ==/!= 0
   SDValue optimizeSetCCByHoistingAndByConstFromLogicalShift(
       EVT SCCVT, SDValue N0, SDValue N1C, ISD::CondCode Cond,
       DAGCombinerInfo &DCI, const SDLoc &DL) const;
 
+  // Simplify SETCC testing shifted value for equality/non-equality to zero by
+  // removing redundant operations generated during shift's expansion.
+  // Shift's expansion (when its result fed into SETCC eq/ne 0) generates tree
+  // consisting of OR and multiple SRL/SHL (that may be combined into
+  // FSHL/FSHR). When such pair of shifts applied to the same operand it
+  // performs rotation and it could be eliminated as far as the overall result
+  // is compared with zero.
+  SDValue optimizeSetCCOfExpandedShift(EVT SCCVT, SDValue N0, SDValue N1C,
+                                       ISD::CondCode Cond, DAGCombinerInfo &DCI,
+                                       const SDLoc &DL) const;
+
   SDValue prepareUREMEqFold(EVT SETCCVT, SDValue REMNode,
                             SDValue CompTargetNode, ISD::CondCode Cond,
                             DAGCombinerInfo &DCI, const SDLoc &DL,
                             SmallVectorImpl<SDNode *> &Created) const;
   SDValue buildUREMEqFold(EVT SETCCVT, SDValue REMNode, SDValue CompTargetNode,
                           ISD::CondCode Cond, DAGCombinerInfo &DCI,
                           const SDLoc &DL) const;
 

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

SDValue TargetLowering::optimizeSetCCByHoistingAndByConstFromLogicalShift(
   // Produce:
   // ((X 'OppositeShiftOpcode' Y) & C) Cond 0
   SDValue T0 = DAG.getNode(NewShiftOpcode, DL, VT, X, Y);
   SDValue T1 = DAG.getNode(ISD::AND, DL, VT, T0, C);
   SDValue T2 = DAG.getSetCC(DL, SCCVT, T1, N1C, Cond);
   return T2;
 }
 
+// Example of redundant shifts elimination:
+// (or (or (srl X, C0), (shl Y, C1)), (srl Y, C0)) ==/!= 0
+//    -->  (or (srl X, C0), Y) ==/!= 0
+//
+// (or (or (srl Y, C0), (shl X, C1)), (shl Y, C1)) ==/!= 0
+//    -->  (or (shl X, C1), Y) ==/!= 0
+//
+// (or (srl X, C), (fshr X, Y, C)) ==/!= 0  -->  (or (srl Y, C), X)
+//
+// (or (or (fshl W, X, C), (fshl X, Y, C)),
+//     (or (fshl Y, Z, C), (shl Z, C)))) ==/!= 0
+//    -->  (or (or (shl W, C), X), (or Y, Z))
+SDValue TargetLowering::optimizeSetCCOfExpandedShift(EVT SCCVT, SDValue N0,
+                                                     SDValue N1C,
+                                                     ISD::CondCode Cond,
+                                                     DAGCombinerInfo &DCI,
+                                                     const SDLoc &DL) const {
+  assert(isConstOrConstSplat(N1C) &&
+         isConstOrConstSplat(N1C)->getAPIntValue().isZero() &&
+         "Should be a comparison with 0.");
+  assert((Cond == ISD::SETEQ || Cond == ISD::SETNE) && "Unexpected condcode");
+
+  struct ShiftInfo {
+    APInt Bits;
+    bool IsLeft;
+  };
+  SmallDenseMap<SDValue, ShiftInfo, 16> UnmatchedShifts;
+  SmallVector<SDValue, 16> Result;
+
+  // Match pairs of shifts applied to the same operand that effectively
+  // perform its rotation:
+  // 1) create a new entry in UnmatchedShifts map if Op was observed
+  //    for the first time;
+  // 2) if UnmatchedShifts map contains an entry for the Op check that
+  //    it was created for a shift in opposite direction and that
+  //    amount of bits in these two shifts is summed up to OpSizeInBits.
+  unsigned MatchedShiftsCount = 0;
+  unsigned OpSizeInBits = N0.getValueType().getScalarSizeInBits();
+  auto MatchShifts = [&UnmatchedShifts, &Result, &MatchedShiftsCount,
+                      OpSizeInBits](SDValue &Op, const APInt &C, bool IsLeft) {
+    ShiftInfo &Info = UnmatchedShifts[Op];
+    if (Info.Bits.isZero()) {
+      Info.Bits = C;
+      Info.IsLeft = IsLeft;
+      return true;
+    }
+    if (Info.IsLeft == IsLeft)
+      return false;
+    if (Info.Bits + C != OpSizeInBits)
+      return false;
+    Result.push_back(Op);
+    UnmatchedShifts.erase(Op);
+    ++MatchedShiftsCount;
+    return true;
+  };
+
+  // Recursively scan DAG to match all shifts while following conditions are
+  // met:
+  // 1) every node should has only one use;
+  // 2) every shift should be either first shift found for its operand
+  //    or there shoud be previously found matching shift in opposite
+  //    direction;
+  // 3) Depth should be lower than SelectionDAG::MaxRecursionDepth
+  std::function<bool(const SDValue &, unsigned)> Scan;
+  Scan = [&Scan, &MatchShifts, &Result, OpSizeInBits](const SDValue &Value,
+                                                      unsigned Depth) {
+    if (Depth >= SelectionDAG::MaxRecursionDepth || !Value->hasOneUse())
+      return false;
+    unsigned Opcode = Value->getOpcode();
+    bool IsShiftLeft = Opcode == ISD::SHL || Opcode == ISD::FSHL;
+    ConstantSDNode *C;
+
+    if (Opcode == ISD::OR) {
+      return Scan(Value->getOperand(0), Depth + 1) &&
+             Scan(Value->getOperand(1), Depth + 1);
+    }
+    if (Opcode == ISD::SRL || Opcode == ISD::SHL) {
+      if (!(C = dyn_cast<ConstantSDNode>(Value->getOperand(1))))
+        return false;
+      SDValue Op = Value->getOperand(0);
+      return MatchShifts(Op, C->getAPIntValue(), IsShiftLeft);
+    }
+    if (Opcode == ISD::FSHL || Opcode == ISD::FSHR) {
+      if (!(C = dyn_cast<ConstantSDNode>(Value->getOperand(2))))
+        return false;
+      SDValue Op1 = Value->getOperand(0);
+      SDValue Op2 = Value->getOperand(1);
+      const APInt &CVal = C->getAPIntValue();
+      // For funnel shifts second operand is effectively shifted
+      // in opposite direction.
+      return MatchShifts(Op1, CVal, IsShiftLeft) &&
+             MatchShifts(Op2, OpSizeInBits - CVal, !IsShiftLeft);
+    }
+    Result.push_back(Value);
+    return true;
+  };
+  if (!Scan(N0, 0))
+    return SDValue();
+  // There should be at most one unmatched shift and at least one pair
+  // of matched shifts.
+  if (MatchedShiftsCount == 0 || UnmatchedShifts.size() > 1 || Result.empty())
+    return SDValue();
+
+  SelectionDAG &DAG = DCI.DAG;
+  // Recreate value for unmatched shift.
+  if (!UnmatchedShifts.empty()) {
+    DenseMap<SDValue, ShiftInfo>::iterator UnmatchedShift =
+        UnmatchedShifts.begin();
+    SDValue Op = UnmatchedShift->first;
+    ShiftInfo &Info = UnmatchedShift->second;
+    EVT ShiftTy = EVT::getIntegerVT(*DAG.getContext(), Info.Bits.getBitWidth());
+    SDValue Con = DAG.getConstant(Info.Bits, DL, ShiftTy);
+    unsigned ShiftOpcode = Info.IsLeft ? ISD::SHL : ISD::SRL;
+    Result.push_back(DAG.getNode(ShiftOpcode, DL, N0.getValueType(), Op, Con));
+  }
+  // Reduce all values using OR.
+  // Push new OR back to the Result list and combine pairs of values from it
+  // to generate balanced tree and shorten the critical path.
+  for (size_t Index = 0; Index + 1 < Result.size(); Index += 2) {
+    SDValue NewOr = DAG.getNode(ISD::OR, DL, N0.getValueType(), Result[Index],
+                                Result[Index + 1]);
+    Result.push_back(NewOr);
+  }
+  return DAG.getSetCC(DL, SCCVT, Result.back(), N1C, Cond);
+}
+
 /// Try to fold an equality comparison with a {add/sub/xor} binary operation as
 /// the 1st operand (N0). Callers are expected to swap the N0/N1 parameters to
 /// handle the commuted versions of these patterns.
 SDValue TargetLowering::foldSetCCWithBinOp(EVT VT, SDValue N0, SDValue N1,
                                            ISD::CondCode Cond, const SDLoc &DL,
                                            DAGCombinerInfo &DCI) const {
   unsigned BOpcode = N0.getOpcode();
   assert((BOpcode == ISD::ADD || BOpcode == ISD::SUB || BOpcode == ISD::XOR) &&
if (Cond == ISD::SETGT || Cond == ISD::SETUGT) {
         if (C1 == MaxVal-1)
           return DAG.getSetCC(dl, VT, N0,
                               DAG.getConstant(MaxVal, dl, N0.getValueType()),
                               ISD::SETEQ);
       }
     }
 
     if (Cond == ISD::SETEQ || Cond == ISD::SETNE) {
+      if (C1.isZero()) {
         // (X & (C l>>/<< Y)) ==/!= 0  -->  ((X <</l>> Y) & C) ==/!= 0
-      if (C1.isZero())
         if (SDValue CC = optimizeSetCCByHoistingAndByConstFromLogicalShift(
                 VT, N0, N1, Cond, DCI, dl))
           return CC;
 
+        // Try to simplify expanded shift by removing shift operations
+        // that effectively perform rotation.
+        if (SDValue CC =
+                optimizeSetCCOfExpandedShift(VT, N0, N1, Cond, DCI, dl))
+          return CC;
+      }
+
       // For all/any comparisons, replace or(x,shl(y,bw/2)) with and/or(x,y).
       // For example, when high 32-bits of i64 X are known clear:
       // all bits clear: (X | (Y<<32)) ==  0 --> (X | Y) ==  0
       // all bits set:   (X | (Y<<32)) == -1 --> (X & Y) == -1
       bool CmpZero = N1C->getAPIntValue().isZero();
       bool CmpNegOne = N1C->getAPIntValue().isAllOnes();
       if ((CmpZero || CmpNegOne) && N0.hasOneUse()) {
         // Match or(lo,shl(hi,bw/2)) pattern.
         auto IsConcat = [&](SDValue V, SDValue &Lo, SDValue &Hi) {
           unsigned EltBits = V.getScalarValueSizeInBits();
           if (V.getOpcode() != ISD::OR || (EltBits % 2) != 0)
             return false;

llvm/test/CodeGen/AArch64/icmp-shift-opt.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=arm64-eabi | FileCheck %s
 
 ; Optimize expanded SRL/SHL used as an input of
 ; SETCC comparing it with zero by removing rotation.
 ;
 ; See https://bugs.llvm.org/show_bug.cgi?id=50197
 define i128 @opt_setcc_lt_power_of_2(i128 %a) nounwind {
 ; CHECK-LABEL: opt_setcc_lt_power_of_2:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:  .LBB0_1: // %loop
 ; CHECK-NEXT:    // =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    adds x0, x0, #1
 ; CHECK-NEXT:    adcs x1, x1, xzr
-; CHECK-NEXT:    extr x8, x1, x0, #60
-; CHECK-NEXT:    orr x8, x8, x1, lsr #60
+; CHECK-NEXT:    orr x8, x1, x0, lsr #60
 ; CHECK-NEXT:    cbnz x8, .LBB0_1
 ; CHECK-NEXT:  // %bb.2: // %exit
 ; CHECK-NEXT:    ret
   br label %loop
 
 loop:
   %phi.a = phi i128 [ %a, %0 ], [ %inc, %loop ]
   %inc = add i128 %phi.a, 1
   %cmp = icmp ult i128 %inc, 1152921504606846976
   br i1 %cmp, label %exit, label %loop
 
 exit:
   ret i128 %inc
 }
 
 define i1 @opt_setcc_srl_eq_zero(i128 %a) nounwind {
 ; CHECK-LABEL: opt_setcc_srl_eq_zero:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    extr x8, x1, x0, #17
-; CHECK-NEXT:    orr x8, x8, x1, lsr #17
+; CHECK-NEXT:    orr x8, x1, x0, lsr #17
 ; CHECK-NEXT:    cmp x8, #0
 ; CHECK-NEXT:    cset w0, eq
 ; CHECK-NEXT:    ret
    %srl = lshr i128 %a, 17
    %cmp = icmp eq i128 %srl, 0
    ret i1 %cmp
 }
 
 define i1 @opt_setcc_srl_ne_zero(i128 %a) nounwind {
 ; CHECK-LABEL: opt_setcc_srl_ne_zero:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    extr x8, x1, x0, #17
-; CHECK-NEXT:    orr x8, x8, x1, lsr #17
+; CHECK-NEXT:    orr x8, x1, x0, lsr #17
 ; CHECK-NEXT:    cmp x8, #0
 ; CHECK-NEXT:    cset w0, ne
 ; CHECK-NEXT:    ret
    %srl = lshr i128 %a, 17
    %cmp = icmp ne i128 %srl, 0
    ret i1 %cmp
 }
 
 define i1 @opt_setcc_shl_eq_zero(i128 %a) nounwind {
 ; CHECK-LABEL: opt_setcc_shl_eq_zero:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    extr x8, x1, x0, #47
-; CHECK-NEXT:    orr x8, x8, x0, lsl #17
+; CHECK-NEXT:    orr x8, x0, x1, lsl #17
 ; CHECK-NEXT:    cmp x8, #0
 ; CHECK-NEXT:    cset w0, eq
 ; CHECK-NEXT:    ret
    %shl = shl i128 %a, 17
    %cmp = icmp eq i128 %shl, 0
    ret i1 %cmp
 }
 
 define i1 @opt_setcc_shl_ne_zero(i128 %a) nounwind {
 ; CHECK-LABEL: opt_setcc_shl_ne_zero:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    extr x8, x1, x0, #47
-; CHECK-NEXT:    orr x8, x8, x0, lsl #17
+; CHECK-NEXT:    orr x8, x0, x1, lsl #17
 ; CHECK-NEXT:    cmp x8, #0
 ; CHECK-NEXT:    cset w0, ne
 ; CHECK-NEXT:    ret
    %shl = shl i128 %a, 17
    %cmp = icmp ne i128 %shl, 0
    ret i1 %cmp
 }
 
; CHECK-NEXT:    ret
    ret i1 %cmp
 }
 
 ; Check that optimization is applied to DAG having appropriate shape
 ; even if there were no actual shift's expansion.
 define i1 @opt_setcc_expanded_shl_correct_shifts(i64 %a, i64 %b) nounwind {
 ; CHECK-LABEL: opt_setcc_expanded_shl_correct_shifts:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    extr x8, x0, x1, #47
-; CHECK-NEXT:    orr x8, x8, x1, lsl #17
+; CHECK-NEXT:    orr x8, x1, x0, lsl #17
 ; CHECK-NEXT:    cmp x8, #0
 ; CHECK-NEXT:    cset w0, eq
 ; CHECK-NEXT:    ret
   %shl.a = shl i64 %a, 17
   %srl.b = lshr i64 %b, 47
   %or.0 = or i64 %shl.a, %srl.b
   %shl.b = shl i64 %b, 17
   %or.1 = or i64 %or.0, %shl.b
; CHECK-NEXT:    ret
   %srl.b = lshr i64 %b, 47
   %or.0 = or i64 %shl.a, %srl.b
   %shl.b = shl i64 %b, 18
   %or.1 = or i64 %or.0, %shl.b
   %cmp = icmp eq i64 %or.1, 0
   ret i1 %cmp
 }
 
+define i1 @opt_setcc_shl_ne_zero_i256(i256 %a) nounwind {
+; CHECK-LABEL: opt_setcc_shl_ne_zero_i256:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    extr x8, x3, x2, #47
+; CHECK-NEXT:    extr x9, x2, x1, #47
+; CHECK-NEXT:    extr x10, x1, x0, #47
+; CHECK-NEXT:    orr x9, x9, x0, lsl #17
+; CHECK-NEXT:    orr x8, x10, x8
+; CHECK-NEXT:    orr x8, x9, x8
+; CHECK-NEXT:    cmp x8, #0
+; CHECK-NEXT:    cset w0, ne
+; CHECK-NEXT:    ret
+   %shl = shl i256 %a, 17
+   %cmp = icmp ne i256 %shl, 0
+   ret i1 %cmp
+}
+
 declare void @use(i128 %a)

llvm/test/CodeGen/ARM/consthoist-icmpimm.ll

 ; CHECKV7M-NEXT:    .save {r7, lr}
 ; CHECKV7M-NEXT:    push {r7, lr}
 ; CHECKV7M-NEXT:    mov r12, r0
 ; CHECKV7M-NEXT:    ldr r0, [sp, #16]
 ; CHECKV7M-NEXT:    lsls r0, r0, #31
 ; CHECKV7M-NEXT:    ldrd lr, r0, [sp, #8]
 ; CHECKV7M-NEXT:    beq .LBB6_2
 ; CHECKV7M-NEXT:  @ %bb.1: @ %then
-; CHECKV7M-NEXT:    lsrs r2, r2, #17
-; CHECKV7M-NEXT:    orr.w r2, r2, r3, lsl #15
-; CHECKV7M-NEXT:    orr.w r2, r2, r3, lsr #17
-; CHECKV7M-NEXT:    lsr.w r3, r12, #17
-; CHECKV7M-NEXT:    orr.w r3, r3, r1, lsl #15
+; CHECKV7M-NEXT:    orr.w r2, r3, r2, lsr #17
+; CHECKV7M-NEXT:    orr.w r1, r1, r12, lsr #17
 ; CHECKV7M-NEXT:    cmp r2, #0
 ; CHECKV7M-NEXT:    mov r2, r0
-; CHECKV7M-NEXT:    orr.w r1, r3, r1, lsr #17
 ; CHECKV7M-NEXT:    it ne
 ; CHECKV7M-NEXT:    movne r2, lr
 ; CHECKV7M-NEXT:    cmp r1, #0
 ; CHECKV7M-NEXT:    it ne
 ; CHECKV7M-NEXT:    movne r0, lr
 ; CHECKV7M-NEXT:    add r0, r2
 ; CHECKV7M-NEXT:    pop {r7, pc}
 ; CHECKV7M-NEXT:  .LBB6_2: @ %else
-; CHECKV7M-NEXT:    lsrs r1, r2, #17
-; CHECKV7M-NEXT:    orr.w r1, r1, r3, lsl #15
-; CHECKV7M-NEXT:    orr.w r1, r1, r3, lsr #17
+; CHECKV7M-NEXT:    orr.w r1, r3, r2, lsr #17
 ; CHECKV7M-NEXT:    cmp r1, #0
 ; CHECKV7M-NEXT:    it ne
 ; CHECKV7M-NEXT:    movne r0, lr
 ; CHECKV7M-NEXT:    pop {r7, pc}
 ;
 ; CHECKV7A-LABEL: icmp64_uge_m2:
 ; CHECKV7A:       @ %bb.0:
 ; CHECKV7A-NEXT:    .save {r4, lr}
 ; CHECKV7A-NEXT:    push {r4, lr}
 ; CHECKV7A-NEXT:    ldr r4, [sp, #16]
 ; CHECKV7A-NEXT:    mov r12, r0
 ; CHECKV7A-NEXT:    ldrd lr, r0, [sp, #8]
 ; CHECKV7A-NEXT:    lsls r4, r4, #31
 ; CHECKV7A-NEXT:    beq .LBB6_2
 ; CHECKV7A-NEXT:  @ %bb.1: @ %then
-; CHECKV7A-NEXT:    lsrs r2, r2, #17
-; CHECKV7A-NEXT:    orr.w r2, r2, r3, lsl #15
-; CHECKV7A-NEXT:    orr.w r2, r2, r3, lsr #17
-; CHECKV7A-NEXT:    lsr.w r3, r12, #17
-; CHECKV7A-NEXT:    orr.w r3, r3, r1, lsl #15
+; CHECKV7A-NEXT:    orr.w r2, r3, r2, lsr #17
+; CHECKV7A-NEXT:    orr.w r1, r1, r12, lsr #17
 ; CHECKV7A-NEXT:    cmp r2, #0
 ; CHECKV7A-NEXT:    mov r2, r0
-; CHECKV7A-NEXT:    orr.w r1, r3, r1, lsr #17
 ; CHECKV7A-NEXT:    it ne
 ; CHECKV7A-NEXT:    movne r2, lr
 ; CHECKV7A-NEXT:    cmp r1, #0
 ; CHECKV7A-NEXT:    it ne
 ; CHECKV7A-NEXT:    movne r0, lr
 ; CHECKV7A-NEXT:    add r0, r2
 ; CHECKV7A-NEXT:    pop {r4, pc}
 ; CHECKV7A-NEXT:  .LBB6_2: @ %else
-; CHECKV7A-NEXT:    lsrs r1, r2, #17
-; CHECKV7A-NEXT:    orr.w r1, r1, r3, lsl #15
-; CHECKV7A-NEXT:    orr.w r1, r1, r3, lsr #17
+; CHECKV7A-NEXT:    orr.w r1, r3, r2, lsr #17
 ; CHECKV7A-NEXT:    cmp r1, #0
 ; CHECKV7A-NEXT:    it ne
 ; CHECKV7A-NEXT:    movne r0, lr
 ; CHECKV7A-NEXT:    pop {r4, pc}
   br i1 %c, label %then, label %else
 then:
   %c1 = icmp uge i64 %x, 131072
   %c2 = icmp uge i64 %y, 131072

llvm/test/CodeGen/ARM/icmp-shift-opt.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=armv7 %s -o - | FileCheck %s
 
 ; Optimize expanded SRL/SHL used as an input of
 ; SETCC comparing it with zero by removing rotation.
 ;
 ; See https://bugs.llvm.org/show_bug.cgi?id=50197
 define i64 @opt_setcc_lt_power_of_2(i64 %a) nounwind {
 ; CHECK-LABEL: opt_setcc_lt_power_of_2:
 ; CHECK:       @ %bb.0:
 ; CHECK-NEXT:  .LBB0_1: @ %loop
 ; CHECK-NEXT:    @ =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    adds r0, r0, #1
 ; CHECK-NEXT:    adc r1, r1, #0
-; CHECK-NEXT:    lsr r2, r0, #16
-; CHECK-NEXT:    orr r2, r2, r1, lsl #16
-; CHECK-NEXT:    orr r2, r2, r1, lsr #16
+; CHECK-NEXT:    orr r2, r1, r0, lsr #16
 ; CHECK-NEXT:    cmp r2, #0
 ; CHECK-NEXT:    bne .LBB0_1
 ; CHECK-NEXT:  @ %bb.2: @ %exit
 ; CHECK-NEXT:    bx lr
   br label %loop
 
 loop:
   %phi.a = phi i64 [ %a, %0 ], [ %inc, %loop ]
   %inc = add i64 %phi.a, 1
   %cmp = icmp ult i64 %inc, 65536
   br i1 %cmp, label %exit, label %loop
 
 exit:
   ret i64 %inc
 }
 
 define i1 @opt_setcc_srl_eq_zero(i64 %a) nounwind {
 ; CHECK-LABEL: opt_setcc_srl_eq_zero:
 ; CHECK:       @ %bb.0:
-; CHECK-NEXT:    lsr r0, r0, #17
-; CHECK-NEXT:    orr r0, r0, r1, lsl #15
-; CHECK-NEXT:    orr r0, r0, r1, lsr #17
+; CHECK-NEXT:    orr r0, r1, r0, lsr #17
 ; CHECK-NEXT:    clz r0, r0
 ; CHECK-NEXT:    lsr r0, r0, #5
 ; CHECK-NEXT:    bx lr
    %srl = lshr i64 %a, 17
    %cmp = icmp eq i64 %srl, 0
    ret i1 %cmp
 }
 
 define i1 @opt_setcc_srl_ne_zero(i64 %a) nounwind {
 ; CHECK-LABEL: opt_setcc_srl_ne_zero:
 ; CHECK:       @ %bb.0:
-; CHECK-NEXT:    lsr r0, r0, #17
-; CHECK-NEXT:    orr r0, r0, r1, lsl #15
-; CHECK-NEXT:    orr r0, r0, r1, lsr #17
+; CHECK-NEXT:    orr r0, r1, r0, lsr #17
 ; CHECK-NEXT:    cmp r0, #0
 ; CHECK-NEXT:    movwne r0, #1
 ; CHECK-NEXT:    bx lr
    %srl = lshr i64 %a, 17
    %cmp = icmp ne i64 %srl, 0
    ret i1 %cmp
 }
 
 define i1 @opt_setcc_shl_eq_zero(i64 %a) nounwind {
 ; CHECK-LABEL: opt_setcc_shl_eq_zero:
 ; CHECK:       @ %bb.0:
-; CHECK-NEXT:    lsl r1, r1, #17
-; CHECK-NEXT:    orr r1, r1, r0, lsr #15
-; CHECK-NEXT:    orr r0, r1, r0, lsl #17
+; CHECK-NEXT:    orr r0, r0, r1, lsl #17
 ; CHECK-NEXT:    clz r0, r0
 ; CHECK-NEXT:    lsr r0, r0, #5
 ; CHECK-NEXT:    bx lr
    %shl = shl i64 %a, 17
    %cmp = icmp eq i64 %shl, 0
    ret i1 %cmp
 }
 
 define i1 @opt_setcc_shl_ne_zero(i64 %a) nounwind {
 ; CHECK-LABEL: opt_setcc_shl_ne_zero:
 ; CHECK:       @ %bb.0:
-; CHECK-NEXT:    lsl r1, r1, #17
-; CHECK-NEXT:    orr r1, r1, r0, lsr #15
-; CHECK-NEXT:    orr r0, r1, r0, lsl #17
+; CHECK-NEXT:    orr r0, r0, r1, lsl #17
 ; CHECK-NEXT:    cmp r0, #0
 ; CHECK-NEXT:    movwne r0, #1
 ; CHECK-NEXT:    bx lr
    %shl = shl i64 %a, 17
    %cmp = icmp ne i64 %shl, 0
    ret i1 %cmp
 }
 
; CHECK-NEXT:    pop {r4, r5, r11, pc}
    ret i1 %cmp
 }
 
 ; Check that optimization is applied to DAG having appropriate shape
 ; even if there were no actual shift's expansion.
 define i1 @opt_setcc_expanded_shl_correct_shifts(i32 %a, i32 %b) nounwind {
 ; CHECK-LABEL: opt_setcc_expanded_shl_correct_shifts:
 ; CHECK:       @ %bb.0:
-; CHECK-NEXT:    lsl r0, r0, #17
-; CHECK-NEXT:    orr r0, r0, r1, lsr #15
-; CHECK-NEXT:    orr r0, r0, r1, lsl #17
+; CHECK-NEXT:    orr r0, r1, r0, lsl #17
 ; CHECK-NEXT:    clz r0, r0
 ; CHECK-NEXT:    lsr r0, r0, #5
 ; CHECK-NEXT:    bx lr
   %shl.a = shl i32 %a, 17
   %srl.b = lshr i32 %b, 15
   %or.0 = or i32 %shl.a, %srl.b
   %shl.b = shl i32 %b, 17
   %or.1 = or i32 %or.0, %shl.b
; CHECK-NEXT:    bx lr
   %srl.b = lshr i32 %b, 15
   %or.0 = or i32 %shl.a, %srl.b
   %shl.b = shl i32 %b, 18
   %or.1 = or i32 %or.0, %shl.b
   %cmp = icmp eq i32 %or.1, 0
   ret i1 %cmp
 }
 
+define i1 @opt_setcc_shl_ne_zero_i128(i128 %a) nounwind {
+; CHECK-LABEL: opt_setcc_shl_ne_zero_i128:
+; CHECK:       @ %bb.0:
+; CHECK-NEXT:    orr r2, r2, r3, lsl #17
+; CHECK-NEXT:    orr r0, r1, r0
+; CHECK-NEXT:    orrs r0, r0, r2
+; CHECK-NEXT:    movwne r0, #1
+; CHECK-NEXT:    bx lr
+   %shl = shl i128 %a, 17
+   %cmp = icmp ne i128 %shl, 0
+   ret i1 %cmp
+}
+
 declare void @use(i64 %a)

llvm/test/CodeGen/X86/icmp-shift-opt.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=i686-- < %s | FileCheck %s --check-prefix=X86
 ; RUN: llc -mtriple=x86_64-- < %s | FileCheck %s --check-prefix=X64
 
 ; Optimize expanded SRL/SHL used as an input of
 ; SETCC comparing it with zero by removing rotation.
 ;
 ; See https://bugs.llvm.org/show_bug.cgi?id=50197
 define i128 @opt_setcc_lt_power_of_2(i128 %a) nounwind {
 ; X86-LABEL: opt_setcc_lt_power_of_2:
 ; X86:       # %bb.0:
 ; X86-NEXT:    pushl %ebp
 ; X86-NEXT:    pushl %ebx
 ; X86-NEXT:    pushl %edi
 ; X86-NEXT:    pushl %esi
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ebx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %edi
 ; X86-NEXT:    .p2align 4, 0x90
 ; X86-NEXT:  .LBB0_1: # %loop
 ; X86-NEXT:    # =>This Inner Loop Header: Depth=1
-; X86-NEXT:    addl $1, %ecx
+; X86-NEXT:    addl $1, %edi
 ; X86-NEXT:    adcl $0, %esi
 ; X86-NEXT:    adcl $0, %edx
-; X86-NEXT:    adcl $0, %ebx
-; X86-NEXT:    movl %ebx, %edi
-; X86-NEXT:    shldl $4, %edx, %edi
-; X86-NEXT:    movl %edx, %ebp
-; X86-NEXT:    shldl $4, %esi, %ebp
-; X86-NEXT:    movl %ecx, %eax
-; X86-NEXT:    movl %ebx, %ecx
-; X86-NEXT:    shrl $28, %ecx
-; X86-NEXT:    orl %ebp, %ecx
-; X86-NEXT:    orl %edi, %ecx
-; X86-NEXT:    movl %eax, %ecx
+; X86-NEXT:    adcl $0, %ecx
+; X86-NEXT:    movl %ecx, %ebx
+; X86-NEXT:    orl %edx, %ebx
+; X86-NEXT:    movl %esi, %ebp
+; X86-NEXT:    shrl $28, %ebp
+; X86-NEXT:    orl %ebx, %ebp
 ; X86-NEXT:    jne .LBB0_1
 ; X86-NEXT:  # %bb.2: # %exit
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl %ecx, (%eax)
+; X86-NEXT:    movl %edi, (%eax)
 ; X86-NEXT:    movl %esi, 4(%eax)
 ; X86-NEXT:    movl %edx, 8(%eax)
-; X86-NEXT:    movl %ebx, 12(%eax)
+; X86-NEXT:    movl %ecx, 12(%eax)
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    popl %edi
 ; X86-NEXT:    popl %ebx
 ; X86-NEXT:    popl %ebp
 ; X86-NEXT:    retl $4
 ;
 ; X64-LABEL: opt_setcc_lt_power_of_2:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movq %rsi, %rdx
 ; X64-NEXT:    movq %rdi, %rax
 ; X64-NEXT:    .p2align 4, 0x90
 ; X64-NEXT:  .LBB0_1: # %loop
 ; X64-NEXT:    # =>This Inner Loop Header: Depth=1
 ; X64-NEXT:    addq $1, %rax
 ; X64-NEXT:    adcq $0, %rdx
-; X64-NEXT:    movq %rdx, %rcx
-; X64-NEXT:    shldq $4, %rax, %rcx
-; X64-NEXT:    movq %rdx, %rsi
-; X64-NEXT:    shrq $60, %rsi
-; X64-NEXT:    orq %rcx, %rsi
+; X64-NEXT:    movq %rax, %rcx
+; X64-NEXT:    shrq $60, %rcx
+; X64-NEXT:    orq %rdx, %rcx
 ; X64-NEXT:    jne .LBB0_1
 ; X64-NEXT:  # %bb.2: # %exit
 ; X64-NEXT:    retq
   br label %loop
 
 loop:
   %phi.a = phi i128 [ %a, %0 ], [ %inc, %loop ]
   %inc = add i128 %phi.a, 1
   %cmp = icmp ult i128 %inc, 1152921504606846976
   br i1 %cmp, label %exit, label %loop
 
 exit:
   ret i128 %inc
 }
 
 define i1 @opt_setcc_srl_eq_zero(i128 %a) nounwind {
 ; X86-LABEL: opt_setcc_srl_eq_zero:
 ; X86:       # %bb.0:
-; X86-NEXT:    pushl %edi
-; X86-NEXT:    pushl %esi
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    movl %esi, %edi
-; X86-NEXT:    shldl $15, %edx, %edi
-; X86-NEXT:    shldl $15, %ecx, %edx
-; X86-NEXT:    shrdl $17, %ecx, %eax
-; X86-NEXT:    orl %edi, %eax
-; X86-NEXT:    shrl $17, %esi
-; X86-NEXT:    orl %edx, %esi
-; X86-NEXT:    orl %eax, %esi
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    shrl $17, %eax
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    orl %ecx, %eax
 ; X86-NEXT:    sete %al
-; X86-NEXT:    popl %esi
-; X86-NEXT:    popl %edi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: opt_setcc_srl_eq_zero:
 ; X64:       # %bb.0:
-; X64-NEXT:    shrdq $17, %rsi, %rdi
-; X64-NEXT:    shrq $17, %rsi
-; X64-NEXT:    orq %rdi, %rsi
+; X64-NEXT:    shrq $17, %rdi
+; X64-NEXT:    orq %rsi, %rdi
 ; X64-NEXT:    sete %al
 ; X64-NEXT:    retq
    %srl = lshr i128 %a, 17
    %cmp = icmp eq i128 %srl, 0
    ret i1 %cmp
 }
 
 define i1 @opt_setcc_srl_ne_zero(i128 %a) nounwind {
 ; X86-LABEL: opt_setcc_srl_ne_zero:
 ; X86:       # %bb.0:
-; X86-NEXT:    pushl %edi
-; X86-NEXT:    pushl %esi
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    movl %esi, %edi
-; X86-NEXT:    shldl $15, %edx, %edi
-; X86-NEXT:    shldl $15, %ecx, %edx
-; X86-NEXT:    shrdl $17, %ecx, %eax
-; X86-NEXT:    orl %edi, %eax
-; X86-NEXT:    shrl $17, %esi
-; X86-NEXT:    orl %edx, %esi
-; X86-NEXT:    orl %eax, %esi
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    shrl $17, %eax
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    orl %ecx, %eax
 ; X86-NEXT:    setne %al
-; X86-NEXT:    popl %esi
-; X86-NEXT:    popl %edi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: opt_setcc_srl_ne_zero:
 ; X64:       # %bb.0:
-; X64-NEXT:    shrdq $17, %rsi, %rdi
-; X64-NEXT:    shrq $17, %rsi
-; X64-NEXT:    orq %rdi, %rsi
+; X64-NEXT:    shrq $17, %rdi
+; X64-NEXT:    orq %rsi, %rdi
 ; X64-NEXT:    setne %al
 ; X64-NEXT:    retq
    %srl = lshr i128 %a, 17
    %cmp = icmp ne i128 %srl, 0
    ret i1 %cmp
 }
 
 define i1 @opt_setcc_shl_eq_zero(i128 %a) nounwind {
 ; X86-LABEL: opt_setcc_shl_eq_zero:
 ; X86:       # %bb.0:
-; X86-NEXT:    pushl %esi
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    shldl $17, %esi, %edx
-; X86-NEXT:    shldl $17, %ecx, %esi
-; X86-NEXT:    shldl $17, %eax, %ecx
-; X86-NEXT:    shll $17, %eax
-; X86-NEXT:    orl %esi, %eax
-; X86-NEXT:    orl %edx, %ecx
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    shll $17, %ecx
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    orl %eax, %ecx
 ; X86-NEXT:    sete %al
-; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: opt_setcc_shl_eq_zero:
 ; X64:       # %bb.0:
-; X64-NEXT:    shldq $17, %rdi, %rsi
-; X64-NEXT:    shlq $17, %rdi
-; X64-NEXT:    orq %rsi, %rdi
+; X64-NEXT:    shlq $17, %rsi
+; X64-NEXT:    orq %rdi, %rsi
 ; X64-NEXT:    sete %al
 ; X64-NEXT:    retq
    %shl = shl i128 %a, 17
    %cmp = icmp eq i128 %shl, 0
    ret i1 %cmp
 }
 
 define i1 @opt_setcc_shl_ne_zero(i128 %a) nounwind {
 ; X86-LABEL: opt_setcc_shl_ne_zero:
 ; X86:       # %bb.0:
-; X86-NEXT:    pushl %esi
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    shldl $17, %esi, %edx
-; X86-NEXT:    shldl $17, %ecx, %esi
-; X86-NEXT:    shldl $17, %eax, %ecx
-; X86-NEXT:    shll $17, %eax
-; X86-NEXT:    orl %esi, %eax
-; X86-NEXT:    orl %edx, %ecx
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    shll $17, %ecx
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    orl %eax, %ecx
 ; X86-NEXT:    setne %al
-; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: opt_setcc_shl_ne_zero:
 ; X64:       # %bb.0:
-; X64-NEXT:    shldq $17, %rdi, %rsi
-; X64-NEXT:    shlq $17, %rdi
-; X64-NEXT:    orq %rsi, %rdi
+; X64-NEXT:    shlq $17, %rsi
+; X64-NEXT:    orq %rdi, %rsi
 ; X64-NEXT:    setne %al
 ; X64-NEXT:    retq
    %shl = shl i128 %a, 17
    %cmp = icmp ne i128 %shl, 0
    ret i1 %cmp
 }
 
 ; Negative test: optimization should not be applied if shift has multiple users.
; X64-NEXT:    retq
    ret i1 %cmp
 }
 
 ; Check that optimization is applied to DAG having appropriate shape
 ; even if there were no actual shift's expansion.
 define i1 @opt_setcc_expanded_shl_correct_shifts(i64 %a, i64 %b) nounwind {
 ; X86-LABEL: opt_setcc_expanded_shl_correct_shifts:
 ; X86:       # %bb.0:
-; X86-NEXT:    pushl %esi
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    shldl $17, %edx, %esi
-; X86-NEXT:    shldl $17, %ecx, %edx
-; X86-NEXT:    shldl $17, %eax, %ecx
-; X86-NEXT:    shll $17, %eax
-; X86-NEXT:    orl %edx, %eax
-; X86-NEXT:    orl %esi, %ecx
+; X86-NEXT:    shll $17, %ecx
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    orl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    orl %eax, %ecx
 ; X86-NEXT:    sete %al
-; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: opt_setcc_expanded_shl_correct_shifts:
 ; X64:       # %bb.0:
-; X64-NEXT:    shldq $17, %rsi, %rdi
-; X64-NEXT:    shlq $17, %rsi
-; X64-NEXT:    orq %rdi, %rsi
+; X64-NEXT:    shlq $17, %rdi
+; X64-NEXT:    orq %rsi, %rdi
 ; X64-NEXT:    sete %al
 ; X64-NEXT:    retq
   %shl.a = shl i64 %a, 17
   %srl.b = lshr i64 %b, 47
   %or.0 = or i64 %shl.a, %srl.b
   %shl.b = shl i64 %b, 17
   %or.1 = or i64 %or.0, %shl.b
   %cmp = icmp eq i64 %or.1, 0