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

[dnsampaio]

Summary

Detects patterns that copies the higher half of an element to its lower half.
Example, it replaces the pattern:
x= (zext i8 ( load 1 [M+1] ) to i16)
x2= i16 or(x, shl(x, 8))
store 1 (truncate i16 x2 to i8) [M]

by:
x = i8 load 1 [M+1]
store 1 i8 x [M]

[javed.absar]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13109

I think the comment here can be improved. e.g. 'load 1 from M' is confusing. You probably mean load i8 from memory?

Also, it looks like you are combing two points into one statement which may confuse readers. Better to simplify it.

13115

Would be better to return nullptr instead of 'llvm_unreachable' in case its not ISD::OR

[rogfer01]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13114–13115

If you choose to leave the assertion, consider simplifying it into something like

assert(OR.getOpcode() == ISD::OR && "Expecting ISD::OR");

See the recommendation described in http://llvm.org/docs/ProgrammersManual.html#programmatic-errors

13176–13181

Was this left accidentally? If not, perhaps a single TODO comment describing what can be done next will be clearer.

[dnsampaio]

Implemented one TODO left on the code, and added check to verify if the load is sign extend, when the load width is smaller than the store width. Else the result of the OR operation would not be known.

[samparker]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13112

Can this not be implemented in, or as a helper function for, ReduceLoadOpStoreWidth? That function is already performing safety checks and handling the load and store creation correctly. It looks like it needs help understanding a shifted operand to the OR, instead of just a constant.

lib/Transforms/Utils/SimplifyIndVar.cpp

787 ↗

(On Diff #150281)

Why these changes?

[dnsampaio]

Added further tests.

[samparker]

Hi Diogo,

I will look at this again once the two parent changes have been committed, as I'm not familiar with these functions. I'm confused as to why there isn't a ReduceStoreWidth to pair with ReduceLoadWidth. These LoadOpStore functions have a lot of overlap and related functionality that I suspect can be refactored nicely.

cheers,
sam

[samparker]

I am not suggesting that I will ask you to refactor by the way! I just want to spend some more time looking at these functions and having a play with your other two patches.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

private:
     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 foldRedundantShiftedMasks(SDNode *N);
+    SDValue checkOverwritenLoadReduceStoreWidth(StoreSDNode *Store);
     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,
bool DAGCombiner::SliceUpLoad(SDNode *N) {
   DAG.ReplaceAllUsesOfValueWith(SDValue(N, 1), Chain);
   AddToWorklist(Chain.getNode());
   return true;
 }
 
 /// Check to see if V is (and load (ptr), imm), where the load is having
 /// specific bytes cleared out.  If so, return the byte size being masked out
 /// and the shift amount.
-static std::pair<unsigned, unsigned>
+typedef struct {
+  unsigned Bytes = 0, Offset = 0, Shl = 0;
+} MaskedLoadValue;
+static MaskedLoadValue
 CheckForMaskedLoad(SDValue V, SDValue Ptr, SDValue Chain) {
-  std::pair<unsigned, unsigned> Result(0, 0);
+  MaskedLoadValue Result;
 
   // Check for the structure we're looking for.
   if (V->getOpcode() != ISD::AND ||
       !isa<ConstantSDNode>(V->getOperand(1)) ||
       !ISD::isNormalLoad(V->getOperand(0).getNode()))
     return Result;
 
   // Check the chain and pointer.
CheckForMaskedLoad(SDValue V, SDValue Ptr, SDValue Chain) {
   case 4: break;
   default: return Result; // All one mask, or 5-byte mask.
   }
 
   // Verify that the first bit starts at a multiple of mask so that the access
   // is aligned the same as the access width.
   if (NotMaskTZ && NotMaskTZ/8 % MaskedBytes) return Result;
 
-  Result.first = MaskedBytes;
-  Result.second = NotMaskTZ/8;
+  Result.Bytes = MaskedBytes;
+  Result.Offset = NotMaskTZ/8;
+  Result.Shl = Result.Offset;
   return Result;
 }
 
 /// Check to see if IVal is something that provides a value as specified by
 /// MaskInfo. If so, replace the specified store with a narrower store of
 /// truncated IVal.
 static SDNode *
-ShrinkLoadReplaceStoreWithStore(const std::pair<unsigned, unsigned> &MaskInfo,
+ShrinkLoadReplaceStoreWithStore(MaskedLoadValue &MaskInfo,
                                 SDValue IVal, StoreSDNode *St,
                                 DAGCombiner *DC) {
-  unsigned NumBytes = MaskInfo.first;
-  unsigned ByteShift = MaskInfo.second;
   SelectionDAG &DAG = DC->getDAG();
 
   // Check to see if IVal is all zeros in the part being masked in by the 'or'
   // that uses this.  If not, this is not a replacement.
   APInt Mask = ~APInt::getBitsSet(IVal.getValueSizeInBits(),
-                                  ByteShift*8, (ByteShift+NumBytes)*8);
+                                  MaskInfo.Shl*8, (MaskInfo.Shl+MaskInfo.Bytes)*8);
   if (!DAG.MaskedValueIsZero(IVal, Mask)) return nullptr;
 
   // Check that it is legal on the target to do this.  It is legal if the new
   // VT we're shrinking to (i8/i16/i32) is legal or we're still before type
   // legalization.
-  MVT VT = MVT::getIntegerVT(NumBytes*8);
+  MVT VT = MVT::getIntegerVT(MaskInfo.Bytes*8);
   if (!DC->isTypeLegal(VT))
     return nullptr;
 
   // Okay, we can do this!  Replace the 'St' store with a store of IVal that is
-  // shifted by ByteShift and truncated down to NumBytes.
-  if (ByteShift) {
+  // shifted by MaskInfo.Shl and truncated down to MaskInfo.Bytes.
+  if (MaskInfo.Shl) {
     SDLoc DL(IVal);
     IVal = DAG.getNode(ISD::SRL, DL, IVal.getValueType(), IVal,
-                       DAG.getConstant(ByteShift*8, DL,
+                       DAG.getConstant(MaskInfo.Shl*8, DL,
                                     DC->getShiftAmountTy(IVal.getValueType())));
   }
 
   // Figure out the offset for the store and the alignment of the access.
   unsigned StOffset;
   unsigned NewAlign = St->getAlignment();
 
   if (DAG.getDataLayout().isLittleEndian())
-    StOffset = ByteShift;
+    StOffset = MaskInfo.Offset;
   else
-    StOffset = IVal.getValueType().getStoreSize() - ByteShift - NumBytes;
+    StOffset = IVal.getValueType().getStoreSize() - MaskInfo.Offset - MaskInfo.Bytes;
 
   SDValue Ptr = St->getBasePtr();
   if (StOffset) {
     SDLoc DL(IVal);
     Ptr = DAG.getNode(ISD::ADD, DL, Ptr.getValueType(),
                       Ptr, DAG.getConstant(StOffset, DL, Ptr.getValueType()));
     NewAlign = MinAlign(NewAlign, StOffset);
   }
 
   // Truncate down to the new size.
   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();
 }
 
+/// Detects that half of a Store operation is just overwriting a previous
+/// Load operation, using OR and SHIFT operations. Such as:
+/// st i16 ((zext(ld i8, [M]) to i16) or (shl(zext(ld i8, [M])to i16), 8)), [M]
+SDValue
+DAGCombiner::checkOverwritenLoadReduceStoreWidth(StoreSDNode *ST){
+  // It is safe to reduce the ST operation even after LegalizeTypes
+  // as we only create a ST of the same width of the LD
+  assert(ST && "Expecting non-null");
+  if(!ST)
+    return SDValue();
+
+  if (ST->isVolatile())
+    return SDValue();
+
+  SDValue OR = ST->getValue();
+  if (!OR.hasOneUse())
+    return SDValue();
+
+  if (OR.getOpcode() != ISD::OR)
+    return SDValue();
+
+  EVT VT = OR.getValueType();
+
+  if (VT.isVector())
+    return SDValue();
+
+  SDValue LDVal = OR.getOperand(0);
+  LoadSDNode *LD = dyn_cast<LoadSDNode>(LDVal);
+  SDNode *SHL;
+  if(!LD){
+    SHL = LDVal.getNode();
+    LDVal = OR.getOperand(1);
+    LD = dyn_cast<LoadSDNode>(LDVal);
+    if(!LD)
+      return SDValue();
+  } else
+    SHL = OR.getOperand(1).getNode();
+
+  if ((SHL->getOpcode() != ISD::SHL) ||
+      (SHL->getOperand(0).getNode() != LD) ||
+      !isa<ConstantSDNode>(SHL->getOperand(1)))
+    return SDValue();
+
+  SDValue Chain = ST->getChain();
+
+  if(Chain != SDValue(LD, 1))
+    return SDValue();
+
+  unsigned BytesShift = cast<ConstantSDNode>(SHL->getOperand(1).getNode())
+                     ->getAPIntValue().getSExtValue() / 8;
+
+  unsigned StoreMemSz = ST->getMemoryVT().getStoreSize();
+
+  if (2 * BytesShift != StoreMemSz)
+    return SDValue();
+
+  const SDValue LoadPtr = LD->getBasePtr();
+  SDValue Ptr = ST->getBasePtr();
+  unsigned LoadMemSz = LD->getMemoryVT().getStoreSize();
+  if (BytesShift)
+  // TODO: Detect when both LOAD and STORE memory addresses are both ADD
+  // instructions to a common base address, with a known constant difference
+  // Ex: load i8 [M+3] and store i16 [M+2]
+  if (LoadPtr == Ptr) {
+    if ((LoadMemSz < StoreMemSz) && LD->getExtensionType() != ISD::ZEXTLOAD)
+      return SDValue();
+
+    if (LoadMemSz == BytesShift) {
+      // replace something like
+      //  store i16( or(ld i8 [M] zext i16), (shl ( ld i8 [M] ), 8) ),[M]
+      // by
+      //  store i8( ld i8 [M]) [M+1]
+//      LLVM_DEBUG(dbgs() << "\tGot load: "; LD->dump());
+//      LLVM_DEBUG(dbgs() << "\tThat is shifted by: "; SHL->dump());
+//      LLVM_DEBUG(dbgs() << "\tOR combined by: "; OR->dump());
+//      LLVM_DEBUG(dbgs() << "\tAnd stored by: "; ST->dump());
+//      LLVM_DEBUG(dbgs() << "\tNot writing the lower half of the value\n");
+      // For big endian targets, we need to adjust the offset to the pointer to
+      // load the correct bytes.
+      MaskedLoadValue MLV = {LoadMemSz, LoadMemSz, 0};
+      return SDValue(ShrinkLoadReplaceStoreWithStore(MLV, LDVal, ST, this), 0);
+    }
+    return SDValue();
+  }
+
+  SDValue OffsetPtr = LoadPtr;
+  SDValue NonOffsetPtr = Ptr;
+
+  if(DAG.getDataLayout().isBigEndian())
+    std::swap(OffsetPtr, NonOffsetPtr);
+
+  if ((OffsetPtr.getOpcode() != ISD::ADD)||
+     (!((OffsetPtr.getOperand(0) == NonOffsetPtr) ||
+             (OffsetPtr.getOperand(1) == NonOffsetPtr))))
+    return SDValue();
+
+  ConstantSDNode *Offset = dyn_cast<ConstantSDNode>(OffsetPtr.getOperand(1));
+  if (!Offset)
+    Offset = dyn_cast<ConstantSDNode>(OffsetPtr.getOperand(0));
+
+  if (!Offset)
+    return SDValue();
+
+  unsigned LoadByteOffset = Offset->getAPIntValue().getZExtValue();
+  if (!((LoadByteOffset == LoadMemSz) && (2 * LoadMemSz == StoreMemSz) &&
+      LD->getExtensionType() == ISD::ZEXTLOAD))
+    return SDValue();
+
+  // Replace something like
+  // store i16( or(ld i8 [M+1]), (shl ( ld i8 [M+1]), 8) ),[M]
+  // by
+  //  store i8( ld i8 [M+1]) [M]. The ld must be zext.
+//  LLVM_DEBUG(dbgs() << "\tGot load: "; LD->dump());
+//  LLVM_DEBUG(dbgs() << "\tThat is shifted by: "; SHL->dump());
+//  LLVM_DEBUG(dbgs() << "\tOR combined by: "; OR->dump());
+//  LLVM_DEBUG(dbgs() << "\tAnd stored by: "; ST->dump());
+//  LLVM_DEBUG(dbgs() << "\tNot writing the upper half of the value\n");
+  MaskedLoadValue MLV = {LoadMemSz, 0, 0};
+  return SDValue(ShrinkLoadReplaceStoreWithStore(MLV, LDVal, ST, this), 0);
+}
 /// 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();
SDValue DAGCombiner::ReduceLoadOpStoreWidth(SDNode *N) {
   unsigned Opc = Value.getOpcode();
 
   // If this is "store (or X, Y), P" and X is "(and (load P), cst)", where cst
   // is a byte mask indicating a consecutive number of bytes, check to see if
   // Y is known to provide just those bytes.  If so, we try to replace the
   // load + replace + store sequence with a single (narrower) store, which makes
   // the load dead.
   if (Opc == ISD::OR) {
-    std::pair<unsigned, unsigned> MaskedLoad;
+    MaskedLoadValue MaskedLoad;
     MaskedLoad = CheckForMaskedLoad(Value.getOperand(0), Ptr, Chain);
-    if (MaskedLoad.first)
+    if (MaskedLoad.Bytes)
       if (SDNode *NewST = ShrinkLoadReplaceStoreWithStore(MaskedLoad,
                                                   Value.getOperand(1), ST,this))
         return SDValue(NewST, 0);
 
     // Or is commutative, so try swapping X and Y.
     MaskedLoad = CheckForMaskedLoad(Value.getOperand(1), Ptr, Chain);
-    if (MaskedLoad.first)
+    if (MaskedLoad.Bytes)
       if (SDNode *NewST = ShrinkLoadReplaceStoreWithStore(MaskedLoad,
                                                   Value.getOperand(0), ST,this))
         return SDValue(NewST, 0);
   }
 
   if ((Opc != ISD::OR && Opc != ISD::XOR && Opc != ISD::AND) ||
       Value.getOperand(1).getOpcode() != ISD::Constant)
     return SDValue();
SDValue DAGCombiner::visitSTORE(SDNode *N) {
   if (isa<ConstantFPSDNode>(ST->getValue())) {
     if (SDValue NewSt = replaceStoreOfFPConstant(ST))
       return NewSt;
   }
 
   if (SDValue NewSt = splitMergedValStore(ST))
     return NewSt;
 
+  if (SDValue NewSt = checkOverwritenLoadReduceStoreWidth(ST))
+    return NewSt;
+
   return ReduceLoadOpStoreWidth(N);
 }
 
 /// For the instruction sequence of store below, F and I values
 /// are bundled together as an i64 value before being stored into memory.
 /// Sometimes it is more efficent to generate separate stores for F and I,
 /// which can remove the bitwise instructions or sink them to colder places.
 ///

test/CodeGen/ARM/2018_05_30_FoldMakedMoves.ll

+; RUN: llc -O3 -march=arm %s -o - | FileCheck %s -check-prefix=ARM
+; RUN: llc -O3 -march=armeb %s -o - | FileCheck %s -check-prefix=ARMEB
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "armv4t-arm-none-eabi"
+define void @foo1(i16* %b){
+entry:
+  %0 = load i16, i16* %b, align 2
+  %conv = sext i16 %0 to i32
+  %and = and i32 %conv, 65280
+  %1 = lshr i32 %conv, 8
+  %and3 = and i32 %1, 255
+  %or = or i32 %and3, %and
+  %conv4 = trunc i32 %or to i16
+  store i16 %conv4, i16* %b, align 2
+  ret void
+}
+
+define void @foo2(i32* %b){
+entry:
+  %0 = load i32, i32* %b, align 4
+  %1 = lshr i32 %0, 16
+  %and2 = and i32 %1, 65535
+  %and = and i32 %0, 4294901760
+  %or = or i32 %and2, %and
+  store i32 %or, i32* %b, align 4
+  ret void
+}
+
+define void @test_1x4p1(i32* %M, i32 %I) {
+entry:
+  %0 = getelementptr inbounds i32, i32* %M, i32 %I
+  %1 = load i32, i32* %0, align 4
+  %2 = and i32 %1, 65280
+  %3 = lshr i32 %1, 8
+  %4 = and i32 %3, 255
+  %5 = or i32 %2, %4
+  store i32 %5, i32* %0, align 4
+  ret void
+}
+
+define void @test_1x4p1_shl(i32* %M, i32 %I) {
+entry:
+  %0 = getelementptr inbounds i32, i32* %M, i32 %I
+  %1 = load i32, i32* %0, align 4
+  %2 = and i32 %1, 65280
+  %3 = shl i32 %1, 8
+  %4 = and i32 %3, 16711680
+  %5 = or i32 %2, %4
+  store i32 %5, i32* %0, align 4
+  ret void
+}
+; ARMEB-LABEL:foo1:
+; ARMEB: ldrb  [[R1:r[0-9]+]], {{\[}}[[R0:r[0-9]+]]{{\]}}
+; ARMEB: strb  [[R1:r[0-9]+]], {{\[}}[[R0:r[0-9]+]], #2] 
+; ARMEB-LABEL:foo2:
+; ARMEB: ldrh  [[R1:r[0-9]+]], {{\[}}[[R0:r[0-9]+]]{{\]}}
+; ARMEB: strh  [[R1:r[0-9]+]], {{\[}}[[R0:r[0-9]+]], #2] 
+; ARMEB-LABEL:test_1x4p1:
+; ARMEB: add [[R2:r[0-9]+]], [[R0:r[0-9]+]], [[R1:r[0-9]+]], lsl #2
+; ARMEB: ldrb  [[R2:r[0-9]+]], {{\[}}[[R2:r[0-9]+]], #2] 
+; ARMEB: orr [[R2:r[0-9]+]], [[R2:r[0-9]+]], [[R2:r[0-9]+]], lsl #8
+; ARMEB: str [[R2:r[0-9]+]], {{\[}}[[R0:r[0-9]+]], [[R1:r[0-9]+]], lsl #2] 
+; ARMEB-LABEL:test_1x4p1_shl:
+; ARMEB: add [[R2:r[0-9]+]], [[R0:r[0-9]+]], [[R1:r[0-9]+]], lsl #2
+; ARMEB: ldrb  [[R2:r[0-9]+]], {{\[}}[[R2:r[0-9]+]], #2] 
+; ARMEB: lsl [[R3:r[0-9]+]], [[R2:r[0-9]+]], #8
+; ARMEB: orr [[R2:r[0-9]+]], [[R3:r[0-9]+]], [[R2:r[0-9]+]], lsl #16 
+; ARMEB: str [[R2:r[0-9]+]], {{\[}}[[R0:r[0-9]+]], [[R1:r[0-9]+]], lsl #2]
+; ARM-LABEL: foo1:
+; ARM: ldrb  [[R1:r[0-9]+]], {{\[}}[[R0:r[0-9]+]], #1] 
+; ARM: strb  [[R1:r[0-9]+]], {{\[}}[[R0:r[0-9]+]]{{\]}}
+; ARM-LABEL: foo2:
+; ARM: ldrh  [[R1:r[0-9]+]], {{\[}}[[R0:r[0-9]+]], #2] 
+; ARM: strh  [[R1:r[0-9]+]], {{\[}}[[R0:r[0-9]+]]{{\]}}
+; ARM-LABEL: test_1x4p1:
+; ARM: add [[R2:r[0-9]+]], [[R0:r[0-9]+]], [[R1:r[0-9]+]], lsl #2
+; ARM: ldrb  [[R2:r[0-9]+]], {{\[}}[[R2:r[0-9]+]], #1] 
+; ARM: orr [[R2:r[0-9]+]], [[R2:r[0-9]+]], [[R2:r[0-9]+]], lsl #8
+; ARM: str [[R2:r[0-9]+]], {{\[}}[[R0:r[0-9]+]], [[R1:r[0-9]+]], lsl #2] 
+; ARM-LABEL: test_1x4p1_shl:
+; ARM: add [[R2:r[0-9]+]], [[R0:r[0-9]+]], [[R1:r[0-9]+]], lsl #2
+; ARM: ldrb  [[R2:r[0-9]+]], {{\[}}[[R2:r[0-9]+]], #1] 
+; ARM: lsl [[R3:r[0-9]+]], [[R2:r[0-9]+]], #8
+; ARM: orr [[R2:r[0-9]+]], [[R3:r[0-9]+]], [[R2:r[0-9]+]], lsl #16 
+; ARM: str [[R2:r[0-9]+]], {{\[}}[[R0:r[0-9]+]], [[R1:r[0-9]+]], lsl #2]
+; armeb
+;foo1:
+; ldrb  r1, [r0]
+; strb  r1, [r0, #2]
+;foo2:
+; ldrh  r1, [r0]
+; strh  r1, [r0, #2]
+;test_1x4p1:
+; add r2, r0, r1, lsl #2
+; ldrb  r2, [r2, #2]
+; orr r2, r2, r2, lsl #8
+; str r2, [r0, r1, lsl #2]
+;test_1x4p1_shl:
+; add r2, r0, r1, lsl #2
+; ldrb  r2, [r2, #2]
+; lsl r3, r2, #8
+; orr r2, r3, r2, lsl #16
+; str r2, [r0, r1, lsl #2]
+; arm
+;foo1:
+; ldrb  r1, [r0, #1]
+; strb  r1, [r0]
+;foo2:
+; ldrh  r1, [r0, #2]
+; strh  r1, [r0]
+;test_1x4p1:
+; add r2, r0, r1, lsl #2
+; ldrb  r2, [r2, #1]
+; orr r2, r2, r2, lsl #8
+; str r2, [r0, r1, lsl #2]
+;test_1x4p1_shl:
+; add r2, r0, r1, lsl #2
+; ldrb  r2, [r2, #1]
+; lsl r3, r2, #8
+; orr r2, r3, r2, lsl #16
+; str r2, [r0, r1, lsl #2]