[X86] Improve instruction ordering of constant `srl/shl` with `and` to get better and-masks

[goldstein.w.n]

Summary

This moves some logic from combineShiftLeft and generalizes is to
work for shl and and. It also improves the non-mask constant
generation (reducing based on getSignificantBits instead of
countTrailingOnes) so that we can catch some cases where imm64 ->
sign-extended imm32/imm8 or imm32 -> sign-extended imm8

[pengfei]

llvm/lib/Target/X86/X86ISelLowering.cpp

47438

results

47438

One more space. You may run clang-format to help solvoing the format nits.

47533

Use curly braces for consistency.

49129

ditto.

[craig.topper]

llvm/test/CodeGen/X86/bitreverse.ll

538

Looks like the scheduler models make the distinction for AMD CPUs but not Intel

Small snippet of the predicate check:

X86SchedPredicates.td
61:def IsThreeOperandsLEAFn :

X86ScheduleBdVer2.td
560:    IsThreeOperandsLEAFn,

X86ScheduleBtVer2.td
945:    IsThreeOperandsLEAFn,

X86ScheduleZnver3.td
590:    IsThreeOperandsLEAFn,

[pengfei]

llvm/test/CodeGen/X86/bitreverse.ll

538

Thanks for the information! We may need to do the same thing for Intel. Filed #60043 for it.

[goldstein.w.n]

Fix many a nit

[goldstein.w.n]

llvm/test/CodeGen/X86/btc_bts_btr.ll

988 ↗

(On Diff #488861)

Do you know if there is a later stage I can move this transform too so that it won't break any other patterns?

[pengfei]

llvm/test/CodeGen/X86/btc_bts_btr.ll

988 ↗

(On Diff #488861)

No, I don't. Maybe do it in a peephole pass after ISel?

[craig.topper]

llvm/test/CodeGen/X86/btc_bts_btr.ll

988 ↗

(On Diff #488861)

We have something similarish implemented during isel in X86DAGToDAGISel::tryShrinkShlLogicImm.

[goldstein.w.n]

llvm/test/CodeGen/X86/btc_bts_btr.ll

988 ↗

(On Diff #488861)

Do you know if there is a later stage I can move this transform too so that it won't break any other patterns?

988 ↗

(On Diff #488861)

We have something similarish implemented during isel in X86DAGToDAGISel::tryShrinkShlLogicImm.

I did in fact try moving it there and it did clean up some of the missed optimizations but added some (more severe) other missed optimizations.

988 ↗

(On Diff #488861)

No, I don't. Maybe do it in a peephole pass after ISel?

Is there an example file / pass you could point to for me to emulate?

[RKSimon]

llvm/lib/Target/X86/X86ISelLowering.cpp

47444

a lot of the if-else complexity is coming from you trying to handle and(shift(x,c1),c2) and shift(and(x,c2),c3) permutations in the same code - can you not have 2 variants in separate wrapper functions and then have a simpler core function that both call?

47454

(style) assert message

47480

(style) assert messages

[goldstein.w.n]

llvm/lib/Target/X86/X86ISelLowering.cpp

47444

a lot of the if-else complexity is coming from you trying to handle and(shift(x,c1),c2) and shift(and(x,c2),c3) permutations in the same code - can you not have 2 variants in separate wrapper functions and then have a simpler core function that both call?

It seemed to me there was enough duplication / not "too" complex to justify one function, but can ofc split.

[goldstein.w.n]

Fix regressions + more format issues

[goldstein.w.n]

@pengfei fixed the added and and shift in btc_bts_btr.ll and combine-bitreverse.ll respectively. The diffs are gone so your comments don't show up anymore.

[goldstein.w.n]

Fix andn + remove bextr + no-scrub-sp

[pengfei]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9353

So it is only profitable when MASK is a constant? Why don't use c3 in the comments?

9361

Duplicated define.

llvm/lib/Target/X86/X86ISelLowering.cpp

47459–47460

You could use ISD::isExtOpcode(Opc).

47479

I'd say the implementation is too complicated to me to understand. And the overall improvement doesn't look worth the complexity. Not to mention there's still regression in bitreverse.ll
I may not try to understand the code here, leave it for other reviewers.

[goldstein.w.n]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9353

So it is only profitable when MASK is a constant? Why don't use c3 in the comments?

llvm/lib/Target/X86/X86ISelLowering.cpp

47479

I'd say the implementation is too complicated to me to understand. And the overall improvement doesn't look worth the complexity. Not to mention there's still regression in bitreverse.ll

I think the bitreverse.ll regressions have been fixed (that was the point of the new patterns in DAGCombiner.cpp).

I may not try to understand the code here, leave it for other reviewers.

Okay, I will split into 2-functions as Simon suggested which I think will decrease the complexity.

[goldstein.w.n]

Split and/shift cases (readability). Fix some nits

[pengfei]

llvm/lib/Target/X86/X86ISelLowering.cpp

47479

I think the bitreverse.ll regressions have been fixed (that was the point of the new patterns in DAGCombiner.cpp).

I think you fixed combine-bitreverse.ll rather than bitreverse.ll
The problem in bitreverse.ll is 2 lea is replaced by 2 mov + and + shl. I think it is a minor regression due to the increased 2 mov, so I didn't insist on that.
Is the TODO in the file to address this problem?

[goldstein.w.n]

More cleanup

[goldstein.w.n]

llvm/lib/Target/X86/X86ISelLowering.cpp

47479

I'd say the implementation is too complicated to me to understand. And the overall improvement doesn't look worth the complexity. Not to mention there's still regression in bitreverse.ll
I may not try to understand the code here, leave it for other reviewers.

As simon suggested, split the two implementations. Think its a lot more readable now.

47479

I think the bitreverse.ll regressions have been fixed (that was the point of the new patterns in DAGCombiner.cpp).

I think you fixed combine-bitreverse.ll rather than bitreverse.ll
The problem in bitreverse.ll is 2 lea is replaced by 2 mov + and + shl. I think it is a minor regression due to the increased 2 mov, so I didn't insist on that.

I see. I think this is b.c of the reordering (and (shl X..)) -> (shl (and X..)) when X persists (then we need a mov).
We could prevent it with a guard in combineAndWithLogicalShift that only did the transform if this was the last use of X the shiftop was shl 1/2/3 (can become lea). Is there a way to query "isLastUse(X)" for an SDValue or do we just need to do hasOneUse?

Also note other places in the patch get the inverse behavior i.e llvm/test/CodeGen/X86/combine-rotates.ll:rotl_merge_i5.

Is the TODO in the file to address this problem?

Not directly, no. Maybe by accident.

[goldstein.w.n]

Fix regression in bitreverse

[goldstein.w.n]

llvm/lib/Target/X86/X86ISelLowering.cpp

47479

I think the bitreverse.ll regressions have been fixed (that was the point of the new patterns in DAGCombiner.cpp).

I think you fixed combine-bitreverse.ll rather than bitreverse.ll
The problem in bitreverse.ll is 2 lea is replaced by 2 mov + and + shl. I think it is a minor regression due to the increased 2 mov, so I didn't insist on that.
Is the TODO in the file to address this problem?

Fixed.

[pengfei]

The new code is a bit easier to understand now, at least to me. The idea masks sense to me though I still think the logic is a bit verbose.
I'm not going to block this patch, but please wait some days for other reviewers.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9440

Unintended change.

llvm/lib/Target/X86/X86ISelLowering.cpp

47663

I found we prefer to const APInt.

47674

countTrailingOnes?

47676

Should it just need to check MaskCnt == 8/16/32. Or even AndMask == 0xff/0xffff/0xffffffff?

47706

countTrailingOnes?

47735

Duplicated.

47735

it's

47847

is

56681

Add a comment to explain this is for combineLogicalShiftWithAnd.
Why combineAndWithLogicalShift not need this?

[goldstein.w.n]

llvm/lib/Target/X86/X86ISelLowering.cpp

56681

Add a comment to explain this is for combineLogicalShiftWithAnd.
Why combineAndWithLogicalShift not need this?

this is only called for shift ops (i.e VisitSHL and visitShiftByConstant).

[goldstein.w.n]

Fix nits + improve comments

[goldstein.w.n]

Update tests for all backends

[goldstein.w.n]

llvm/test/CodeGen/AArch64/arm64-bitfield-extract.ll

942 ↗

(On Diff #491035)

@t.p.northover the changes to the DagCombiner (allowing shl/shr to combine through an and) seems to cause regression on Aarch64. Going to update with TargetLowering flag unless this is in fact preferable.

[goldstein.w.n]

Put the DAGCombiner changes behind TLI flag as it seems to cause
minor regression on aarch64

[goldstein.w.n]

llvm/test/CodeGen/AArch64/arm64-bitfield-extract.ll

942 ↗

(On Diff #491035)

@t.p.northover the changes to the DagCombiner (allowing shl/shr to combine through an and) seems to cause regression on Aarch64. Going to update with TargetLowering flag unless this is in fact preferable.

I put it behind TLI.isDesirableToCombineShiftsAcross which is disabled by default so should be no issue.

[goldstein.w.n]

Made some changes (TLI flag) since this was accepted. Can someone do a quick pass of the most recent changes to re-verify?

[pengfei]

llvm/include/llvm/CodeGen/TargetLowering.h

4020–4022

Is Shift1 inner and Shift2 outer?

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9440

This still no changed.

llvm/lib/Target/X86/X86ISelLowering.cpp

56685–56686

The arguments are not used. Leave it void for now?

[goldstein.w.n]

llvm/include/llvm/CodeGen/TargetLowering.h

4020–4022

Is Shift1 inner and Shift2 outer?

Yes, renamed to OuterShift and InnerShift to be clearer.

[goldstein.w.n]

Fix style, issue, rename TLI helper, void variables

[pengfei]

llvm/include/llvm/CodeGen/TargetLowering.h

4020

Is the comment still incorrect?

[goldstein.w.n]

Fix comment

[goldstein.w.n]

llvm/include/llvm/CodeGen/TargetLowering.h

4020

Is the comment still incorrect?

Oof, fixed.

[RKSimon]

@goldstein.w.n What is happening with this patch? After they leave my "Ready to Review" list I tend to lose track......

[goldstein.w.n]

In D141653#4198903, @RKSimon wrote:

@goldstein.w.n What is happening with this patch? After they leave my "Ready to Review" list I tend to lose track......

When I tested on bootstrap build it caused on infinite loop. I think this approach is inherently brittle and susceptible
to that sort of bug. I haven't quite abandoned it as I think some of the shl/shr improvements can be salvaged. But
the imm improvedments I want to move to a new pass that runs at the way of end DAG lowering.