[TLI][X86][AArch64] Generalize isDesirableToCommuteWithShift() hook and enable for X86

[lebedev.ri]

Summary

Resolves PR38938.

[lebedev.ri]

lib/Target/X86/X86ISelDAGToDAG.cpp

2630–2633

Actually, this does not have any test coverage it seems.
So i'm not sure what extra tests this needs.

[lebedev.ri]

Comment # 4 on bug 38938 from Craig Topper

We need to get the shl created before the address mode for the inc is
selected
in Simon's test case. So we need to handle this in DAG combine or in
preprocessiseldag.

Ok, makes sense.
This turned out to be rather problematic :S

This is *very* prone to endless loops (we unfold the pattern,
and then SimplifyDemandedBits folds it back).
I suspect the change in DAGCombiner::SimplifyDemandedBits()
is too ugly, but i don't have any better ideas.
Anything else appears to deadlock.

These aren't all the test changes, but most of them.

[lebedev.ri]

Ok, so the fix for the *given* problem is so much simpler.

AArch64 already overrode isDesirableToCommuteWithShift() with this very pattern.
But we clearly want to do the same for x86.
So just generalize it.

FIXME: i'm not sure if isBitFieldExtractPattern() should be a virtual function?

[lebedev.ri]

Rebased ontop of more tests, NFC.
Will look into x86 dagcombine next..

[lebedev.ri]

In D52426#1250354, @RKSimon wrote:

@lebedev.ri Are you able to refactor this now that D52570 has landed?

Rebased now that D52570 has landed.

[lebedev.ri]

In D52426#1250878, @RKSimon wrote:

Can you remove the D52293 dependency and just move the current code to DAG so we can fix PR38938?

We don't want this hook for X86?

[lebedev.ri]

Does not appear to be worthwhile; effectively superseeded by D53126.

[RKSimon]

Abandon this?

[lebedev.ri]

In D52293#1262639, @RKSimon wrote:

In D52293#1262261, @lebedev.ri wrote:

Does not appear to be worthwhile; effectively superseeded by D53126.

Abandon this?

Oops, meant to and forgot :)

lib/Target/X86/X86ISelDAGToDAG.cpp

bool X86DAGToDAGISel::foldLoadStoreIntoMemOperand(SDNode *Node) {
   ReplaceUses(SDValue(LoadNode, 1), SDValue(Result, 1));
   ReplaceUses(SDValue(StoreNode, 0), SDValue(Result, 1));
   ReplaceUses(SDValue(StoredVal.getNode(), 1), SDValue(Result, 0));
   CurDAG->RemoveDeadNode(Node);
   return true;
 }
 
 // See if this is an (X >> C1) & C2 that we can match to BEXTR/BEXTRI.
+// We also handle  (X >> C1) & (C2 << C3)  as  ((X >> (C1 + C3)) & C2) << C3
 bool X86DAGToDAGISel::matchBEXTRFromAnd(SDNode *Node) {
   MVT NVT = Node->getSimpleValueType(0);
   SDLoc dl(Node);
 
   SDValue N0 = Node->getOperand(0);
   SDValue N1 = Node->getOperand(1);
 
   if (!Subtarget->hasBMI() && !Subtarget->hasTBM())
if (NVT != MVT::i32 && NVT != MVT::i64)
     return false;
 
   // Shift amount and RHS of and must be constant.
   ConstantSDNode *MaskCst = dyn_cast<ConstantSDNode>(N1);
   ConstantSDNode *ShiftCst = dyn_cast<ConstantSDNode>(N0->getOperand(1));
   if (!MaskCst || !ShiftCst)
     return false;
 
-  // And RHS must be a mask.
+  // And RHS must be a (potentially shifted) mask.
   uint64_t Mask = MaskCst->getZExtValue();
-  if (!isMask_64(Mask))
+  if (!isShiftedMask_64(Mask))
     return false;
 
-  uint64_t Shift = ShiftCst->getZExtValue();
   uint64_t MaskSize = countPopulation(Mask);
+  uint64_t ZeroPaddingSize = countTrailingZeros(Mask);
+
+  uint64_t Shift = ZeroPaddingSize + ShiftCst->getZExtValue();
 
   // Don't interfere with something that can be handled by extracting AH.
   // TODO: If we are able to fold a load, BEXTR might still be better than AH.
-  if (Shift == 8 && MaskSize == 8)
+  if (Shift == 8 && MaskSize == 8 && ZeroPaddingSize == 0)
     return false;
 
   // Make sure we are only using bits that were in the original value, not
   // shifted in.
   if (Shift + MaskSize > NVT.getSizeInBits())
     return false;
 
   // Create a BEXTR node and run it through selection.
   SDValue C = CurDAG->getConstant(Shift | (MaskSize << 8), dl, NVT);
   SDValue New = CurDAG->getNode(X86ISD::BEXTR, dl, NVT,
                                 N0->getOperand(0), C);
+  if (ZeroPaddingSize > 0) {
+    insertDAGNode(*CurDAG, SDValue(Node, 0), New);
+    // If the mask had some zero low bits, we need to re-introduce them.
+    SDValue Cp = CurDAG->getConstant(ZeroPaddingSize, dl, MVT::i8);
+    New = CurDAG->getNode(ISD::SHL, dl, NVT, New, Cp);
+  }
   ReplaceNode(Node, New.getNode());
   SelectCode(New.getNode());
   return true;
 }
 
 // Emit a PCMISTR(I/M) instruction.
 MachineSDNode *X86DAGToDAGISel::emitPCMPISTR(unsigned ROpc, unsigned MOpc,
                                              bool MayFoldLoad, const SDLoc &dl,

test/CodeGen/X86/bmi-x86_64.ll

entry:
   %shr = lshr i64 %a, 2
   %and = and i64 %shr, 8589934591
   ret i64 %and
 }
 
 define i64 @non_bextr64(i64 %x) {
 ; CHECK-LABEL: non_bextr64:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    shrq $2, %rdi
-; CHECK-NEXT:    movabsq $8589934590, %rax # imm = 0x1FFFFFFFE
-; CHECK-NEXT:    andq %rdi, %rax
+; CHECK-NEXT:    movl $8195, %eax # imm = 0x2003
+; CHECK-NEXT:    bextrq %rax, %rdi, %rax
+; CHECK-NEXT:    addq %rax, %rax
 ; CHECK-NEXT:    retq
 entry:
   %shr = lshr i64 %x, 2
   %and = and i64 %shr, 8589934590
   ret i64 %and
 }

test/CodeGen/X86/extract-bits.ll

; X64-BMI1BMI2-NEXT:    retq
   ret i64 %masked
 }
 
 ; ---------------------------------------------------------------------------- ;
 ; Constant
 ; ---------------------------------------------------------------------------- ;
 
 define void @pr38938(i32* %a0, i64* %a1) {
-; X86-LABEL: pr38938:
-; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl (%ecx), %ecx
-; X86-NEXT:    shrl $19, %ecx
-; X86-NEXT:    andl $4092, %ecx # imm = 0xFFC
-; X86-NEXT:    incl (%eax,%ecx)
-; X86-NEXT:    retl
-;
-; X64-LABEL: pr38938:
-; X64:       # %bb.0:
-; X64-NEXT:    movq (%rsi), %rax
-; X64-NEXT:    shrq $19, %rax
-; X64-NEXT:    andl $4092, %eax # imm = 0xFFC
-; X64-NEXT:    incl (%rdi,%rax)
-; X64-NEXT:    retq
+; X86-NOBMI-LABEL: pr38938:
+; X86-NOBMI:       # %bb.0:
+; X86-NOBMI-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NOBMI-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NOBMI-NEXT:    movl (%ecx), %ecx
+; X86-NOBMI-NEXT:    shrl $19, %ecx
+; X86-NOBMI-NEXT:    andl $4092, %ecx # imm = 0xFFC
+; X86-NOBMI-NEXT:    incl (%eax,%ecx)
+; X86-NOBMI-NEXT:    retl
+;
+; X86-BMI1NOTBM-LABEL: pr38938:
+; X86-BMI1NOTBM:       # %bb.0:
+; X86-BMI1NOTBM-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-BMI1NOTBM-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-BMI1NOTBM-NEXT:    movl $2581, %edx # imm = 0xA15
+; X86-BMI1NOTBM-NEXT:    bextrl %edx, (%ecx), %ecx
+; X86-BMI1NOTBM-NEXT:    shll $2, %ecx
+; X86-BMI1NOTBM-NEXT:    incl (%eax,%ecx)
+; X86-BMI1NOTBM-NEXT:    retl
+;
+; X86-BMI1TBM-LABEL: pr38938:
+; X86-BMI1TBM:       # %bb.0:
+; X86-BMI1TBM-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-BMI1TBM-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-BMI1TBM-NEXT:    bextrl $2581, (%ecx), %ecx # imm = 0xA15
+; X86-BMI1TBM-NEXT:    shll $2, %ecx
+; X86-BMI1TBM-NEXT:    incl (%eax,%ecx)
+; X86-BMI1TBM-NEXT:    retl
+;
+; X86-BMI1NOTBMBMI2-LABEL: pr38938:
+; X86-BMI1NOTBMBMI2:       # %bb.0:
+; X86-BMI1NOTBMBMI2-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-BMI1NOTBMBMI2-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-BMI1NOTBMBMI2-NEXT:    movl $2581, %edx # imm = 0xA15
+; X86-BMI1NOTBMBMI2-NEXT:    bextrl %edx, (%ecx), %ecx
+; X86-BMI1NOTBMBMI2-NEXT:    shll $2, %ecx
+; X86-BMI1NOTBMBMI2-NEXT:    incl (%eax,%ecx)
+; X86-BMI1NOTBMBMI2-NEXT:    retl
+;
+; X64-NOBMI-LABEL: pr38938:
+; X64-NOBMI:       # %bb.0:
+; X64-NOBMI-NEXT:    movq (%rsi), %rax
+; X64-NOBMI-NEXT:    shrq $19, %rax
+; X64-NOBMI-NEXT:    andl $4092, %eax # imm = 0xFFC
+; X64-NOBMI-NEXT:    incl (%rdi,%rax)
+; X64-NOBMI-NEXT:    retq
+;
+; X64-BMI1NOTBM-LABEL: pr38938:
+; X64-BMI1NOTBM:       # %bb.0:
+; X64-BMI1NOTBM-NEXT:    movl $2581, %eax # imm = 0xA15
+; X64-BMI1NOTBM-NEXT:    bextrq %rax, (%rsi), %rax
+; X64-BMI1NOTBM-NEXT:    shlq $2, %rax
+; X64-BMI1NOTBM-NEXT:    incl (%rdi,%rax)
+; X64-BMI1NOTBM-NEXT:    retq
+;
+; X64-BMI1TBM-LABEL: pr38938:
+; X64-BMI1TBM:       # %bb.0:
+; X64-BMI1TBM-NEXT:    bextrq $2581, (%rsi), %rax # imm = 0xA15
+; X64-BMI1TBM-NEXT:    shlq $2, %rax
+; X64-BMI1TBM-NEXT:    incl (%rdi,%rax)
+; X64-BMI1TBM-NEXT:    retq
+;
+; X64-BMI1NOTBMBMI2-LABEL: pr38938:
+; X64-BMI1NOTBMBMI2:       # %bb.0:
+; X64-BMI1NOTBMBMI2-NEXT:    movl $2581, %eax # imm = 0xA15
+; X64-BMI1NOTBMBMI2-NEXT:    bextrq %rax, (%rsi), %rax
+; X64-BMI1NOTBMBMI2-NEXT:    shlq $2, %rax
+; X64-BMI1NOTBMBMI2-NEXT:    incl (%rdi,%rax)
+; X64-BMI1NOTBMBMI2-NEXT:    retq
   %tmp = load i64, i64* %a1, align 8
   %tmp1 = lshr i64 %tmp, 21
   %tmp2 = and i64 %tmp1, 1023
   %tmp3 = getelementptr inbounds i32, i32* %a0, i64 %tmp2
   %tmp4 = load i32, i32* %tmp3, align 4
   %tmp5 = add nsw i32 %tmp4, 1
   store i32 %tmp5, i32* %tmp3, align 4
   ret void
 }

test/CodeGen/X86/selectcc-to-shiftand.ll

 ; CHECK-NOBMI:       # %bb.0:
 ; CHECK-NOBMI-NEXT:    movl %edi, %eax
 ; CHECK-NOBMI-NEXT:    shrl $22, %eax
 ; CHECK-NOBMI-NEXT:    andl $512, %eax # imm = 0x200
 ; CHECK-NOBMI-NEXT:    retq
 ;
 ; CHECK-BMI-LABEL: neg_sel_special_constant:
 ; CHECK-BMI:       # %bb.0:
-; CHECK-BMI-NEXT:    movl %edi, %eax
-; CHECK-BMI-NEXT:    shrl $22, %eax
-; CHECK-BMI-NEXT:    andl $512, %eax # imm = 0x200
+; CHECK-BMI-NEXT:    movl $287, %eax # imm = 0x11F
+; CHECK-BMI-NEXT:    bextrl %eax, %edi, %eax
+; CHECK-BMI-NEXT:    shll $9, %eax
 ; CHECK-BMI-NEXT:    retq
   %tmp.1 = icmp slt i32 %a, 0
   %retval = select i1 %tmp.1, i32 512, i32 0
   ret i32 %retval
 }
 
 ; Compare if negative and select variable or zero.
 

 ; CHECK-NOBMI-NEXT:    movl %edi, %eax
 ; CHECK-NOBMI-NEXT:    notl %eax
 ; CHECK-NOBMI-NEXT:    shrl $22, %eax
 ; CHECK-NOBMI-NEXT:    andl $512, %eax # imm = 0x200
 ; CHECK-NOBMI-NEXT:    retq
 ;
 ; CHECK-BMI-LABEL: pos_sel_special_constant:
 ; CHECK-BMI:       # %bb.0:
-; CHECK-BMI-NEXT:    movl %edi, %eax
-; CHECK-BMI-NEXT:    notl %eax
-; CHECK-BMI-NEXT:    shrl $22, %eax
-; CHECK-BMI-NEXT:    andl $512, %eax # imm = 0x200
+; CHECK-BMI-NEXT:    notl %edi
+; CHECK-BMI-NEXT:    movl $287, %eax # imm = 0x11F
+; CHECK-BMI-NEXT:    bextrl %eax, %edi, %eax
+; CHECK-BMI-NEXT:    shll $9, %eax
 ; CHECK-BMI-NEXT:    retq
   %tmp.1 = icmp sgt i32 %a, -1
   %retval = select i1 %tmp.1, i32 512, i32 0
   ret i32 %retval
 }
 
 ; Compare if positive and select variable or zero.