[SelectionDAG]Reduce masked data movement chains and memory access widths

[dnsampaio]

Summary

Final goal:
detect that, in an i16 data type example:
i16 M[x] = (M[x] & 0xFF00) | (M[x] >> 8 & 0xFF)
can be reduced to an i8 data movement:
i8 M[x] = i8 M[x+1]
The existing code does not handle shifted mask, nor truncating stores and sext loads.

Step 1: Width reduction masked loads by shifted masks
the operation
and i16 (load i16, [M]), 0xFF00
can be replaced by
shl i16 (load i8, [M+1], zext i16), 8

[labrinea]

Please update your diff file in order to contain all the file content. Thanks.

[dnsampaio]

Update diff to contain all the file contents.

[samparker]

Hi Diogo,

This looks like two patches to me so please separate them. I would also expect to see more tests, this is quite a large change so try to cover some of the corner cases.

Also, one styling comment is that we use capital case for variables.

cheers,
sam

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4112

N is an AND, right? This would be easier to read if just N is passed, which you can then add an assert on the opcode, and then you can make N0 and N1 local variables.

4124

unsigned is fine, otherwise try to avoid using C-style casting. It would also be more readable if it was called something like 'ShiftOpcode'.

4125

Don't rely on the ordering of these values. How about using the switch below to default to returning instead of an unreachable?

4131

Pull the cast out of the loop, the nullptr check is also unnecessary.

4150

Is SRA really legal here?

4160

Best to just have a TODO comment and remove these opcodes from the switch.

4177

You've already created a local var for 'shiftAmount', it would be easier to follow if you continued to use it.

4178

Don't think you need to add these as they're not new.

8648–8665

AndC could be a nullptr here.

12999

This looks like two bits of new functionality, so please separate them into two patches.

test/CodeGen/ARM/stld-width-reduction1.ll

20 ↗

(On Diff #146310)

Please remove the attributes and metadata.

[dnsampaio]

Attended all review requests, including spitting into 2 patches.
Fixed the cases where the SRA can be accepted.
Added more unit-tests.

[rogfer01]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

450

Typo here in Redudant?

[dnsampaio]

Fixed typo.

[samparker]

Hi Diogo,

You seem to have forgot to re-add your tests now that you've split the patch.

[dnsampaio]

Re-inserted tests.

[samparker]

Hi Diogo,

Thanks for adding the tests again, but they're still not exercising your change properly - I don't see how your testing the SHL, ROTL or ROTR paths. Also by not checking the input and output registers, using regex or otherwise, you're not testing that the data flow is correct.
This patch should also be split again: into the shift folding and the load reduction, dag combining can be a pain so its best to break into down as much as possible.

cheers,
sam

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4191

remove

6396

Is this needed for the rest of the patch to work? I would have expected that once the above transformation has been performed, that the transform you've added below would later be performed by the existing code in ReduceLoadWidth.

[dnsampaio]

Spitted the patch into 3 parts, and added further tests.

[samparker]

Hi Diogo,

This is looking good, I have just a couple of inline queries. Also, please add a couple of negative tests that use a mask that isn't a multiple of 8 bits.

cheers,
sam

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

8661

OR instead of AND?

8665

Could you explain what you're checking here?

8668

remove or uncomment.

8707

Could you comment on why both of these are being set please?

test/CodeGen/ARM/2018-ShiftedAndMask.ll

54

Is it now possible to do a ldrh with an offset of 1 by using a mask of 0xff0?

[samparker]

test/CodeGen/ARM/2018-ShiftedAndMask.ll

54

i meant a mask of 0xffff00...

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

private:
     SDValue MatchBSwapHWord(SDNode *N, SDValue N0, SDValue N1);
     SDNode *MatchRotatePosNeg(SDValue Shifted, SDValue Pos, SDValue Neg,
                               SDValue InnerPos, SDValue InnerNeg,
                               unsigned PosOpcode, unsigned NegOpcode,
                               const SDLoc &DL);
     SDNode *MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL);
     SDValue MatchLoadCombine(SDNode *N);
     SDValue ReduceLoadWidth(SDNode *N);
     SDValue ReduceLoadOpStoreWidth(SDNode *N);
     SDValue splitMergedValStore(StoreSDNode *ST);
     SDValue TransformFPLoadStorePair(SDNode *N);
     SDValue convertBuildVecZextToZext(SDNode *N);
     SDValue reduceBuildVecExtToExtBuildVec(SDNode *N);
     SDValue reduceBuildVecConvertToConvertBuildVec(SDNode *N);
     SDValue reduceBuildVecToShuffle(SDNode *N);
     SDValue createBuildVecShuffle(const SDLoc &DL, SDNode *N,
                                   ArrayRef<int> VectorMask, SDValue VecIn1,
bool DAGCombiner::BackwardsPropagateMask(SDNode *N, SelectionDAG &DAG) {
   return false;
 }
 
 SDValue DAGCombiner::visitAND(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N1.getValueType();
 
   // x & x --> x
   if (N0 == N1)
     return N0;
 
   // fold vector ops
   if (VT.isVector()) {
     if (SDValue FoldedVOp = SimplifyVBinOp(N))
       return FoldedVOp;
 
     // fold (and x, 0) -> 0, vector edition
     if (ISD::isBuildVectorAllZeros(N0.getNode()))
       // do not return N0, because undef node may exist in N0
       return DAG.getConstant(APInt::getNullValue(N0.getScalarValueSizeInBits()),
                              SDLoc(N), N0.getValueType());
     if (ISD::isBuildVectorAllZeros(N1.getNode()))
       // do not return N1, because undef node may exist in N1
       return DAG.getConstant(APInt::getNullValue(N1.getScalarValueSizeInBits()),
                              SDLoc(N), N1.getValueType());
 
     // fold (and x, -1) -> x, vector edition
     if (ISD::isBuildVectorAllOnes(N0.getNode()))
       return N1;
     if (ISD::isBuildVectorAllOnes(N1.getNode()))
       return N0;
   }
 
   // fold (and c1, c2) -> c1&c2
   ConstantSDNode *N0C = getAsNonOpaqueConstant(N0);
   ConstantSDNode *N1C = isConstOrConstSplat(N1);
   if (N0C && N1C && !N1C->isOpaque())
     return DAG.FoldConstantArithmetic(ISD::AND, SDLoc(N), VT, N0C, N1C);
   // canonicalize constant to RHS
   if (DAG.isConstantIntBuildVectorOrConstantInt(N0) &&
      !DAG.isConstantIntBuildVectorOrConstantInt(N1))
     return DAG.getNode(ISD::AND, SDLoc(N), VT, N1, N0);
   // fold (and x, -1) -> x
   if (isAllOnesConstant(N1))
     return N0;
   // if (and x, c) is known to be zero, return 0
   unsigned BitWidth = VT.getScalarSizeInBits();
   if (N1C && DAG.MaskedValueIsZero(SDValue(N, 0),
                                    APInt::getAllOnesValue(BitWidth)))
     return DAG.getConstant(0, SDLoc(N), VT);
 
   if (SDValue NewSel = foldBinOpIntoSelect(N))
     return NewSel;
 
   // reassociate and
   if (SDValue RAND = ReassociateOps(ISD::AND, SDLoc(N), N0, N1))
     return RAND;
 
   // Try to convert a constant mask AND into a shuffle clear mask.
   if (VT.isVector())
     if (SDValue Shuffle = XformToShuffleWithZero(N))
       return Shuffle;
 
   // fold (and (or x, C), D) -> D if (C & D) == D
   auto MatchSubset = [](ConstantSDNode *LHS, ConstantSDNode *RHS) {
     return RHS->getAPIntValue().isSubsetOf(LHS->getAPIntValue());
   };
   if (N0.getOpcode() == ISD::OR &&
       ISD::matchBinaryPredicate(N0.getOperand(1), N1, MatchSubset))
     return N1;
   // fold (and (any_ext V), c) -> (zero_ext V) if 'and' only clears top bits.
   if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) {
     SDValue N0Op0 = N0.getOperand(0);
     APInt Mask = ~N1C->getAPIntValue();
     Mask = Mask.trunc(N0Op0.getScalarValueSizeInBits());
     if (DAG.MaskedValueIsZero(N0Op0, Mask)) {
       SDValue Zext = DAG.getNode(ISD::ZERO_EXTEND, SDLoc(N),
                                  N0.getValueType(), N0Op0);
 
       // Replace uses of the AND with uses of the Zero extend node.
       CombineTo(N, Zext);
 
       // We actually want to replace all uses of the any_extend with the
       // zero_extend, to avoid duplicating things.  This will later cause this
       // AND to be folded.
       CombineTo(N0.getNode(), Zext);
       return SDValue(N, 0);   // Return N so it doesn't get rechecked!
     }
   }
   // similarly fold (and (X (load ([non_ext|any_ext|zero_ext] V))), c) ->
   // (X (load ([non_ext|zero_ext] V))) if 'and' only clears top bits which must
   // already be zero by virtue of the width of the base type of the load.
   //
   // the 'X' node here can either be nothing or an extract_vector_elt to catch
   // more cases.
SDValue DAGCombiner::visitAND(SDNode *N) {
 
   // fold (and (load x), 255) -> (zextload x, i8)
   // fold (and (extload x, i16), 255) -> (zextload x, i8)
   // fold (and (any_ext (extload x, i16)), 255) -> (zextload x, i8)
   if (!VT.isVector() && N1C && (N0.getOpcode() == ISD::LOAD ||
                                 (N0.getOpcode() == ISD::ANY_EXTEND &&
                                  N0.getOperand(0).getOpcode() == ISD::LOAD))) {
     if (SDValue Res = ReduceLoadWidth(N)) {
+      if (Res.getOpcode() == ISD::SHL)
+        return Res;
+
       LoadSDNode *LN0 = N0->getOpcode() == ISD::ANY_EXTEND
         ? cast<LoadSDNode>(N0.getOperand(0)) : cast<LoadSDNode>(N0);
 
       AddToWorklist(N);
       CombineTo(LN0, Res, Res.getValue(1));
       return SDValue(N, 0);
     }
   }
SDValue DAGCombiner::visitSRL(SDNode *N) {
 
   // fold (srl (anyextend x), c) -> (and (anyextend (srl x, c)), mask)
   if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) {
     // Shifting in all undef bits?
     EVT SmallVT = N0.getOperand(0).getValueType();
     unsigned BitSize = SmallVT.getScalarSizeInBits();
     if (N1C->getZExtValue() >= BitSize)
       return DAG.getUNDEF(VT);
 
     if (!LegalTypes || TLI.isTypeDesirableForOp(ISD::SRL, SmallVT)) {
       uint64_t ShiftAmt = N1C->getZExtValue();
       SDLoc DL0(N0);
       SDValue SmallShift = DAG.getNode(ISD::SRL, DL0, SmallVT,
                                        N0.getOperand(0),
                           DAG.getConstant(ShiftAmt, DL0,
                                           getShiftAmountTy(SmallVT)));
       AddToWorklist(SmallShift.getNode());
SDValue DAGCombiner::ReduceLoadWidth(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   EVT VT = N->getValueType(0);
   EVT ExtVT = VT;
 
   // This transformation isn't valid for vector loads.
   if (VT.isVector())
     return SDValue();
 
+  unsigned ShAmt = 0;
+  unsigned ShLeftAmt = 0;
+
   // Special case: SIGN_EXTEND_INREG is basically truncating to ExtVT then
   // extended to VT.
   if (Opc == ISD::SIGN_EXTEND_INREG) {
     ExtType = ISD::SEXTLOAD;
     ExtVT = cast<VTSDNode>(N->getOperand(1))->getVT();
   } else if (Opc == ISD::SRL) {
     // Another special-case: SRL is basically zero-extending a narrower value,
     // or it maybe shifting a higher subword, half or byte into the lowest
if (Opc == ISD::SIGN_EXTEND_INREG) {
     if (LN0->getExtensionType() != ISD::SEXTLOAD && MemoryWidth > ShiftAmt)
       ExtVT = EVT::getIntegerVT(*DAG.getContext(), MemoryWidth - ShiftAmt);
     else
       ExtVT = EVT::getIntegerVT(*DAG.getContext(),
                                 VT.getSizeInBits() - ShiftAmt);
   } else if (Opc == ISD::AND) {
     // An AND with a constant mask is the same as a truncate + zero-extend.
     auto AndC = dyn_cast<ConstantSDNode>(N->getOperand(1));
-    if (!AndC || !AndC->getAPIntValue().isMask())
+    if (!AndC)
       return SDValue();
 
-    unsigned ActiveBits = AndC->getAPIntValue().countTrailingOnes();
+    // TODO: Not only [shifted] masks should be accepted.
+    // For example:       AND (LD i16, [M]), 0x00AB)
+    // can be replaced by AND (ZEXT(LD i8, [M]) to i16), 0x00AB).
+    const APInt &MaskAPInt = AndC->getAPIntValue();
+    if (!MaskAPInt.isShiftedMask())
+      return SDValue();
+
+    unsigned MaxBit = MaskAPInt.getBitWidth() - MaskAPInt.countLeadingZeros();
+    const unsigned MinBit = MaskAPInt.countTrailingZeros();
+    // Only accepts multiples of 8 bits, and power of 2 sizes
+    if (!MaxBit && (0 != (MaxBit | MinBit) % 8))
+      return SDValue();
+
+    unsigned ActiveBits = MaxBit - MinBit;
+    if (ActiveBits & (ActiveBits - 1))
+      return SDValue();
+
+    //    LLVM_DEBUG(dbgs() << "\tMask: 0x" << MaskAPInt.toString(16, false) <<
+    //    " : ";
+    //               AndC->dump();
+    //               dbgs() << "\t\tmaxActiveBit: " << MaxBit - 1
+    //                      << "\n\t\tminActiveBit: " << MinBit << '\n');
+
+    LoadSDNode *LN0 = dyn_cast<LoadSDNode>(N0);
     ExtType = ISD::ZEXTLOAD;
+    if (MinBit != 0) {
+      // How to treat if it was not a load?
+      if (LN0 == nullptr)
+        return SDValue();
+
+      const auto &mvt = LN0->getMemoryVT();
+      if (MinBit >= mvt.getSizeInBits()) {
+        // The (and) is filtering what was extended, not the actual data
+        // value...
+        if (ISD::LoadExtType::ZEXTLOAD == LN0->getExtensionType()) {
+          // We only read the zero values
+          return DAG.getConstant(0, SDLoc(N), AndC->getValueType(0));
+        }
+        // We access the sign extension, not known here
+        return SDValue();
+      }
+      if (MaxBit > mvt.getSizeInBits())
+        ExtType = LN0->getExtensionType();
+      //    LLVM_DEBUG(dbgs() << "\tCan replace load: "; LN0->dump();
+      //               dbgs() << "\tBy a load of width " << ActiveBits / 8
+      //                      << " bytes, and with offset of " << MinBit / 8 <<
+      //                      " bytes\n");
+    }
+    // TODO: Accept SEXT if the architecture accepts doing a LD?SH (load + shl)
+    // An (and (ld.32bit.sext.from16 [M]), 0x00FFFF00) can be replaced by
+    //   (and (shl (ld.32bit.sext.from8 [M+1]), 8), 0x00FFFF00)
+    if (ExtType != ISD::ZEXTLOAD)
+      return SDValue();
+
     ExtVT = EVT::getIntegerVT(*DAG.getContext(), ActiveBits);
+    ShAmt = MinBit;
+    ShLeftAmt = MinBit;
   }
 
-  unsigned ShAmt = 0;
   if (N0.getOpcode() == ISD::SRL && N0.hasOneUse()) {
     SDValue SRL = N0;
     if (auto *ConstShift = dyn_cast<ConstantSDNode>(SRL.getOperand(1))) {
       ShAmt = ConstShift->getZExtValue();
       unsigned EVTBits = ExtVT.getSizeInBits();
       // Is the shift amount a multiple of size of VT?
       if ((ShAmt & (EVTBits-1)) == 0) {
         N0 = N0.getOperand(0);
if (auto *ConstShift = dyn_cast<ConstantSDNode>(SRL.getOperand(1))) {
             ExtVT = MaskedVT;
         }
       }
     }
   }
 
   // If the load is shifted left (and the result isn't shifted back right),
   // we can fold the truncate through the shift.
-  unsigned ShLeftAmt = 0;
   if (ShAmt == 0 && N0.getOpcode() == ISD::SHL && N0.hasOneUse() &&
       ExtVT == VT && TLI.isNarrowingProfitable(N0.getValueType(), VT)) {
     if (ConstantSDNode *N01 = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
       ShLeftAmt = N01->getZExtValue();
       N0 = N0.getOperand(0);
     }
   }
 
ShrinkLoadReplaceStoreWithStore(const std::pair<unsigned, unsigned> &MaskInfo,
   IVal = DAG.getNode(ISD::TRUNCATE, SDLoc(IVal), VT, IVal);
 
   ++OpsNarrowed;
   return DAG
       .getStore(St->getChain(), SDLoc(St), IVal, Ptr,
                 St->getPointerInfo().getWithOffset(StOffset), NewAlign)
       .getNode();
 }
 
 /// Look for sequence of load / op / store where op is one of 'or', 'xor', and
 /// 'and' of immediates. If 'op' is only touching some of the loaded bits, try
 /// narrowing the load and store if it would end up being a win for performance
 /// or code size.
 SDValue DAGCombiner::ReduceLoadOpStoreWidth(SDNode *N) {
   StoreSDNode *ST  = cast<StoreSDNode>(N);
   if (ST->isVolatile())
     return SDValue();

test/CodeGen/ARM/2018-ShiftedAndMask.ll

+; RUN: llc -O3 -march=arm -o - %s | FileCheck %s -check-prefix=ARM
+; RUN: llc -O3 -march=armeb -o - %s | FileCheck %s -check-prefix=ARMEB
+define void @ldb1(i32* %A) {
+entry:
+  %0 = load i32, i32* %A, align 4
+  %1 = and i32 %0, 65280
+  store i32 %1, i32* %A, align 4
+  ret void
+}
+; ARM-LABEL: ldb1
+; ARM: ldrb [[R0:r[0-9]+]], {{\[}}[[R1:r[0-9]+]], #1{{\]}}
+; ARM: lsl  [[R2:r[0-9]+]], [[R0]], #8
+; ARM: str  [[R2]], {{\[}}[[R1]]{{\]}}
+
+; ARMEB-LABEL: ldb1
+; ARMEB: ldrb [[R0:r[0-9]+]], {{\[}}[[R1:r[0-9]+]], #2{{\]}}
+; ARMEB: lsl  [[R2:r[0-9]+]], [[R0]], #8
+; ARMEB: str  [[R2]], {{\[}}[[R1]]{{\]}}
+
+define void @ldb2(i32* %A) {
+entry:
+  %0 = load i32, i32* %A, align 4
+  %1 = and i32 %0, 16711680
+  store i32 %1, i32* %A, align 4
+  ret void
+}
+; ARM-LABEL: ldb2
+; ARM: ldrb [[R0:r[0-9]+]], {{\[}}[[R1:r[0-9]+]], #2{{\]}}
+; ARM: lsl  [[R2:r[0-9]+]], [[R0]], #16
+; ARM: str  [[R2]], {{\[}}[[R1]]{{\]}}
+
+; ARMEB-LABEL: ldb2
+; ARMEB: ldrb [[R0:r[0-9]+]], {{\[}}[[R1:r[0-9]+]], #1{{\]}}
+; ARMEB: lsl  [[R2:r[0-9]+]], [[R0]], #16
+; ARMEB: str  [[R2]], {{\[}}[[R1]]{{\]}}
+
+define void @ldb3(i32* %A) {
+entry:
+  %0 = load i32, i32* %A, align 4
+  %1 = and i32 %0, 4278190080
+  store i32 %1, i32* %A, align 4
+  ret void
+}
+; ARM-LABEL: ldb3
+; ARM: ldrb [[R0:r[0-9]+]], {{\[}}[[R1:r[0-9]+]], #3{{\]}}
+; ARM: lsl  [[R2:r[0-9]+]], [[R0]], #24
+; ARM: str  [[R2]], {{\[}}[[R1]]{{\]}}
+
+; ARMEB-LABEL: ldb3
+; ARMEB: ldrb [[R0:r[0-9]+]], {{\[}}[[R1:r[0-9]+]]{{\]}}
+; ARMEB: lsl  [[R2:r[0-9]+]], [[R0]], #24
+; ARMEB: str  [[R2]], {{\[}}[[R1]]{{\]}}
+
+define void @ldh(i32* %A) {
+entry:
+  %0 = load i32, i32* %A, align 4
+  %1 = and i32 %0, 4294901760
+  store i32 %1, i32* %A, align 4
+  ret void
+}
+; ARM-LABEL: ldh
+; ARM: ldrh [[R0:r[0-9]+]], {{\[}}[[R1:r[0-9]+]], #2{{\]}}
+; ARM: lsl  [[R2:r[0-9]+]], [[R0]], #16
+; ARM: str  [[R2]], {{\[}}[[R1]]{{\]}}
+
+; ARMEB-LABEL: ldh
+; ARMEB: ldrh [[R0:r[0-9]+]], {{\[}}[[R1:r[0-9]+]]{{\]}}
+; ARMEB: lsl  [[R2:r[0-9]+]], [[R0]], #16
+; ARMEB: str  [[R2]], {{\[}}[[R1]]{{\]}}

test/CodeGen/X86/fp128-i128.ll

 ;      __float128 w;
 ;      u.e = s;
 ;      u.bits.manh = n;
 ;      w = u.e;
 ;      foo(w);
 ; }
 define void @TestUnionLD1(fp128 %s, i64 %n) #0 {
 ; CHECK-LABEL: TestUnionLD1:
-; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    movaps %xmm0, -{{[0-9]+}}(%rsp)
-; CHECK-NEXT:    movq -{{[0-9]+}}(%rsp), %rax
-; CHECK-NEXT:    movabsq $281474976710655, %rcx # imm = 0xFFFFFFFFFFFF
-; CHECK-NEXT:    andq %rdi, %rcx
-; CHECK-NEXT:    movabsq $-281474976710656, %rdx # imm = 0xFFFF000000000000
-; CHECK-NEXT:    andq -{{[0-9]+}}(%rsp), %rdx
-; CHECK-NEXT:    orq %rcx, %rdx
-; CHECK-NEXT:    movq %rax, -{{[0-9]+}}(%rsp)
-; CHECK-NEXT:    movq %rdx, -{{[0-9]+}}(%rsp)
-; CHECK-NEXT:    movaps -{{[0-9]+}}(%rsp), %xmm0
-; CHECK-NEXT:    jmp foo # TAILCALL
+; CHECK:       # %bb.0:                                # %entry
+; CHECK-NEXT:   movaps  %xmm0, -24(%rsp)
+; CHECK-NEXT:   movzwl  -10(%rsp), %eax
+; CHECK-NEXT:   shlq  $48, %rax
+; CHECK-NEXT:   movq  -24(%rsp), %rcx
+; CHECK-NEXT:   movabsq $281474976710655, %rdx  # imm = 0xFFFFFFFFFFFF
+; CHECK-NEXT:   andq  %rdi, %rdx
+; CHECK-NEXT:   orq %rax, %rdx
+; CHECK-NEXT:   movq  %rcx, -40(%rsp)
+; CHECK-NEXT:   movq  %rdx, -32(%rsp)
+; CHECK-NEXT:   movaps  -40(%rsp), %xmm0
+; CHECK-NEXT:   jmp foo                     # TAILCALL
 entry:
   %0 = bitcast fp128 %s to i128
   %1 = zext i64 %n to i128
   %bf.value = shl nuw i128 %1, 64
   %bf.shl = and i128 %bf.value, 5192296858534809181786422619668480
   %bf.clear = and i128 %0, -5192296858534809181786422619668481
   %bf.set = or i128 %bf.shl, %bf.clear
   %2 = bitcast i128 %bf.set to fp128