Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Phabricator shutdown timeline

[DAGCombiner] Transform `(icmp eq/ne (and X,C0),(shift X,C1))` to use rotate or to getter constants.
Needs ReviewPublic

Authored by goldstein.w.n on Jun 4 2023, 12:46 PM.

Details

Reviewers
pengfei
RKSimon
Summary

If C0 is a mask and C1 shifts out all the masked bits (to
essentially compare two subsets of X), we can arbitrarily re-order
shift as srl or shl.

If C1 (shift amount) is a power of 2, we can replace the and+shift
with a rotate.

Otherwise, based on target preference we can arbitrarily swap shl
and shl in/out to get better constants.

On x86 we can use this re-ordering to:

  1. get better and constants for C0 (zero extended moves or avoid imm64).
  2. covert srl to shl if shl will be implementable with lea or add (both of which can be preferable).

Proofs: https://alive2.llvm.org/ce/z/qzGM_w

Diff Detail

Event Timeline

goldstein.w.n created this revision.Jun 4 2023, 12:46 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 4 2023, 12:46 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
goldstein.w.n requested review of this revision.Jun 4 2023, 12:46 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 4 2023, 12:46 PM

This looks similar to optimizeSetCCByHoistingAndByConstFromLogicalShift/shouldProduceAndByConstByHoistingConstFromShiftsLHSOfAnd - can we extend that and perform this as a generic combine?

This looks similar to optimizeSetCCByHoistingAndByConstFromLogicalShift/shouldProduceAndByConstByHoistingConstFromShiftsLHSOfAnd - can we extend that and perform this as a generic combine?

Didn't see those earlier.
So optimizeSetCCByHoistingAndByConstFromLogicalShift seems meaningfully different. Just very different node pattern for X & (C shift Y) eq/ne 0 vs (X shift C0) eq/ne (X and C1). Then likewise shouldProduceAndByConstByHoistingConstFromShiftsLHSOfAnd seems built for optimizeSetCCByHoistingAndByConstFromLogicalShift.
I see the similarity and think could probably could implement both in `optimizeSetCCByHoistingAndByConstFromLogicalShift but think it would end up pretty awkward.
WDYT?

I suppose I'm asking was whether this patch is x86 specific or not - it's always nice not to have something in X86ISelLowering.cpp if other targets would benefit

I suppose I'm asking was whether this patch is x86 specific or not - it's always nice not to have something in X86ISelLowering.cpp if other targets would benefit

Ah I see. Happy to move to DAGCombiner and put this behind something like TargetLowing::PreferInvertShiftAndMask.

Move to DAG Combiner and make preferences target specific.
Also handle rotates

goldstein.w.n retitled this revision from [X86] Transform `(icmp eq/ne (and X, C0), (shift X, C1))` to get better constants. to [DAGCombiner] Transform `(icmp eq/ne (and X,C0),(shift X,C1))` to use rotate or to getter constants..Jun 7 2023, 12:24 AM
goldstein.w.n edited the summary of this revision. (Show Details)
RKSimon added inline comments.Jun 15 2023, 3:02 AM
llvm/include/llvm/CodeGen/TargetLowering.h
824

This function name seems very general and yet the transform seems very specific.

825

Maybe EVT /*VT*/ style would be better than all the (void) ?

goldstein.w.n added inline comments.Jun 27 2023, 10:59 AM
llvm/include/llvm/CodeGen/TargetLowering.h
824

Changed to "PiecesOfOperand" hopefully thats clearer. Otherwise, what would you suggest. "OperandPieces" is mean to refer to the fact that this for comparisons where we are comparing a part of X with another part of X (i.e (X & 255) == (X >> 8)` is comparing that the top 8bits (one piece) equals the low 8bits (another piece).

825

What is EVT /*VT*/ style?

goldstein.w.n edited the summary of this revision. (Show Details)

Rebase + rename helper

RKSimon added inline comments.Jun 28 2023, 3:11 AM
llvm/include/llvm/CodeGen/TargetLowering.h
832

Remove the (void)s

goldstein.w.n marked an inline comment as done.

Don't void variables

Removed (void)s

RKSimon added inline comments.Aug 8 2023, 2:19 AM
llvm/lib/Target/X86/X86ISelLowering.cpp
3284

AndMask.has_value() ?

3302

(style) remove the else - the if case always returns:

// If the current setup has imm64 mask, then inverse will have
// at least imm32 mask (or be zext i32 -> i64).
if (VT == MVT::i64)
  return AndMask->getSignificantBits() > 32 ? ISD::SRL : ShiftOpc;

// We can only benefit if req at least 7-bit for the mask. We
// don't want to replace shl of 1,2,3 as they can be implemented
// with lea/add.
return ShiftOrRotateAmt.uge(7) ? ISD::SRL : ShiftOpc;
3322

Please can you rephrase this? Its rather confusing.

goldstein.w.n marked 3 inline comments as done.Aug 8 2023, 11:36 PM
RKSimon added inline comments.Wed, Sep 20, 10:10 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
12413–12414

SimplifySetCC(VT, N0, N1, Cond, ....

RKSimon added inline comments.Wed, Sep 20, 10:11 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
12432–12532

Isn't this the same as Cond at line#12405?

RKSimon added inline comments.Wed, Sep 20, 10:18 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
12500

(~*AndCMask).popcount() - is this the same as !AndCMask->isAllOnes() ?

goldstein.w.n marked 2 inline comments as done.Wed, Sep 20, 11:35 AM
goldstein.w.n added inline comments.
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
12500

No, we are checking for something like:
(icmp eq (and X, 0x1f), (srl, X, 3). Not all ones.

Don't re-declare things

Remember to commit...