apply two more cases for store combine

[BaoshanPang]

Summary

1. handle the case with extra shift
2. use two short(16-bits) store for 4 byte store when one word store is not allowed

[BaoshanPang]

This comment was removed by BaoshanPang.

[BaoshanPang]

This comment was removed by BaoshanPang.

[BaoshanPang]

@spatel
Please help to review my code.

In the testing(https://reviews.llvm.org/harbormaster/build/217328/), there are some failures but I can't reproduce them locally. Any suggestion is welcome.

Thanks,
Baoshan

[spatel]

Adding more potential reviewers. It might help if the baseline tests are committed, so we can see the asm difference for each test. Is it the alignment or something else that prevents combining these stores currently?

[frasercrmck]

I agree that pre-committed test cases would help here.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7757

It'd be nice if we could be cleverer about this somehow as this is 90% copy/paste from below. Seems like we only use Offset as a key into a map in the following loop. Can we post-process that map instead?

7911

Don't need to pre-declare these variables uninitialized like this.

llvm/test/CodeGen/RISCV/store-combine.ll

3

We normally check RV32 and RV64 in the same test. I think this change benefits RV64 too, right?

80

Do we need all of this metadata for the test to work? I presume we don't need TBAA since the stores trivially don't alias.

[frasercrmck]

Oh and I wouldn't worry about those failing tests: those races tests are/were flaky. They may well resolve themselves then you upload the next version of this diff.

[asb]

llvm/test/CodeGen/RISCV/store-combine.ll

5

For a test like this, it's helpful to put a human-readable description of what behaviour it's trying to demonstrate.

[BaoshanPang]

In D118549#3304383, @spatel wrote:

Adding more potential reviewers. It might help if the baseline tests are committed, so we can see the asm difference for each test. Is it the alignment or something else that prevents combining these stores currently?

The .ll test case is derived from this C file:

struct ab {
    char a;
    char b;
    char c;
    char d;
} __attribute__ ((aligned (2)));

void store0(struct ab *_ab, unsigned v)
{
    _ab->a = v&0xff;
    _ab->b = (v>>8)&0xff;
    _ab->c = (v>>16)&0xff;
    _ab->d = (v>>24)&0xff;
}
void store1(struct ab *_ab, unsigned v)
{
    _ab->a = v&0xff;
    _ab->b = (v>>8)&0xff;
}
void store2(struct ab *_ab, unsigned v)
{
    _ab->c = (v>>16)&0xff;
    _ab->d = (v>>24)&0xff;
}
void store3(struct ab *_ab, unsigned v)
{
    _ab->c = (v)&0xff;
    _ab->d = (v>>8)&0xff;
}

Before my change, the generated asm code is like this:

    .text
    .attribute  4, 16
    .attribute  5, "rv32i2p0_m2p0_a2p0_c2p0"
    .file   "t.c"
    .globl  store0
    .p2align    1
    .type   store0,@function
store0:
    sb  a1, 0(a0)
    srli    a2, a1, 8
    sb  a2, 1(a0)
    srli    a2, a1, 16
    sb  a2, 2(a0)
    srli    a1, a1, 24
    sb  a1, 3(a0)
    ret
.Lfunc_end0:
    .size   store0, .Lfunc_end0-store0

    .globl  store1
    .p2align    1
    .type   store1,@function
store1:
    sh  a1, 0(a0)
    ret
.Lfunc_end1:
    .size   store1, .Lfunc_end1-store1

    .globl  store2
    .p2align    1
    .type   store2,@function
store2:
    srli    a2, a1, 16
    sb  a2, 2(a0)
    srli    a1, a1, 24
    sb  a1, 3(a0)
    ret
.Lfunc_end2:
    .size   store2, .Lfunc_end2-store2

    .globl  store3
    .p2align    1
    .type   store3,@function
store3:
    sh  a1, 2(a0)
    ret
.Lfunc_end3:
    .size   store3, .Lfunc_end3-store3

    .ident  "clang version 15.0.0 (git@172.30.80.200:/opt/repos/fortirisc_llvm.git efb383266d04c70b8adf4ffb3f4872b36bc4653f)"
    .section    ".note.GNU-stack","",@progbits
    .addrsig

With my change the genereated asm code is like this:

    .text
    .attribute  4, 16
    .attribute  5, "rv32i2p0_m2p0_a2p0_c2p0"
    .file   "t.c"
    .globl  store0
    .p2align    1
    .type   store0,@function
store0:
    srli    a2, a1, 16
    sh  a1, 0(a0)
    sh  a2, 16(a0)
    ret
.Lfunc_end0:
    .size   store0, .Lfunc_end0-store0

    .globl  store1
    .p2align    1
    .type   store1,@function
store1:
    sh  a1, 0(a0)
    ret
.Lfunc_end1:
    .size   store1, .Lfunc_end1-store1

    .globl  store2
    .p2align    1
    .type   store2,@function
store2:
    srli    a1, a1, 16
    sh  a1, 2(a0)
    ret
.Lfunc_end2:
    .size   store2, .Lfunc_end2-store2

    .globl  store3
    .p2align    1
    .type   store3,@function
store3:
    sh  a1, 2(a0)
    ret
.Lfunc_end3:
    .size   store3, .Lfunc_end3-store3

    .ident  "clang version 15.0.0 (https://github.com/llvm/llvm-project.git 59bb18ddfec5e5d91079b163a535cb3a6879093e)"
    .section    ".note.GNU-stack","",@progbits
    .addrsig

The difference are at function store0 and store2. For store0, it was failed to use instruction 'sw' as the alignment is 2, my change detect such case and use 2 'sh' for it; for store2, it was failed to use 'sh' because the extra shift(16), my change make it working for this case too.

[BaoshanPang]

Fix issues found by code review

[BaoshanPang]

llvm/test/CodeGen/RISCV/store-combine.ll

80

I am not sure how to remove TBAA(!7).
!7 is referenced by !6, i6 is referenced by all other variables. If I remove !7, it seems I will need to remove all other variables.

[BaoshanPang]

update

[BaoshanPang]

update

[xbolva00]

Tests lost?

[BaoshanPang]

update

[BaoshanPang]

In D118549#3347124, @xbolva00 wrote:

Tests lost?

Yeal, I made a mistake with last update.

[jrtc27]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7828

Run clang-format, the formatting for much of your new code is wrong

llvm/test/CodeGen/RISCV/store-combine.ll

44

Do we need any of these attributes?

80

But are any of them needed?

140

This is entirely useless

141

local_unnamed_addr #0 likely aren't needed? (and #0 doesn't exist)

[BaoshanPang]

update

[BaoshanPang]

llvm/test/CodeGen/RISCV/store-combine.ll

80

Yes, they are not needed. I fixed them.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::mergeTruncStores(StoreSDNode *N) {
   unsigned NarrowNumBits = N->getMemoryVT().getScalarSizeInBits();
   unsigned WideNumBits = NumStores * NarrowNumBits;
   EVT WideVT = EVT::getIntegerVT(Context, WideNumBits);
   if (WideVT != MVT::i16 && WideVT != MVT::i32 && WideVT != MVT::i64)
     return SDValue();
 
   // Check if all bytes of the source value that we are looking at are stored
   // to the same base address. Collect offsets from Base address into OffsetMap.
   SDValue SourceValue;
-  SmallVector<int64_t, 8> OffsetMap(NumStores, INT64_MAX);
+  std::map<unsigned, int64_t> OffsetMap;
   int64_t FirstOffset = INT64_MAX;
   StoreSDNode *FirstStore = nullptr;
   Optional<BaseIndexOffset> Base;
   for (auto Store : Stores) {
     // All the stores store different parts of the CombinedValue. A truncate is
     // required to get the partial value.
     SDValue Trunc = Store->getValue();
     if (Trunc.getOpcode() != ISD::TRUNCATE)
for (auto Store : Stores) {
     else if (!Base->equalBaseIndex(Ptr, DAG, ByteOffsetFromBase))
       return SDValue();
 
     // Remember the first store.
     if (ByteOffsetFromBase < FirstOffset) {
       FirstStore = Store;
       FirstOffset = ByteOffsetFromBase;
     }
-    // Map the offset in the store and the offset in the combined value, and
     // early return if it has been set before.
-    if (Offset < 0 || Offset >= NumStores || OffsetMap[Offset] != INT64_MAX)
+    if (OffsetMap.count(Offset) != 0)
       return SDValue();
     OffsetMap[Offset] = ByteOffsetFromBase;
   }
 
   assert(FirstOffset != INT64_MAX && "First byte offset must be set");
   assert(FirstStore && "First store must be set");
 
+  // check the shifts are consecutive
+  unsigned PreShift = INT32_MAX;
+  for (auto Iter : OffsetMap) {
+    if (PreShift != INT32_MAX) {
+      if (Iter.first - PreShift != 1)
+        return SDValue();
+    }
+    PreShift = Iter.first;
+  }
+
   // Check that a store of the wide type is both allowed and fast on the target
   const DataLayout &Layout = DAG.getDataLayout();
   bool Fast = false;
   bool Allowed = TLI.allowsMemoryAccess(Context, Layout, WideVT,
                                         *FirstStore->getMemOperand(), &Fast);
+  bool Use2St16 = false;
+  if (!Allowed || !Fast) {
+    // Is it OK to use two short store for this 4 bytes store?
+    if (NumStores == 4 && WideVT == MVT::i32) {
+      Allowed = TLI.allowsMemoryAccess(Context, Layout, MVT::i16,
+                                       *FirstStore->getMemOperand(), &Fast);
       if (!Allowed || !Fast)
         return SDValue();
+      Use2St16 = true;
+    } else {
+      return SDValue();
+    }
+  }
 
   // Check if the pieces of the value are going to the expected places in memory
   // to merge the stores.
-  auto checkOffsets = [&](bool MatchLittleEndian) {
+  auto CheckOffsets = [&](bool MatchLittleEndian) {
+    unsigned I = 0;
     if (MatchLittleEndian) {
-      for (unsigned i = 0; i != NumStores; ++i)
-        if (OffsetMap[i] != i * (NarrowNumBits / 8) + FirstOffset)
+      for (auto Iter = OffsetMap.begin(); Iter != OffsetMap.end(); Iter++) {
+        if (Iter->second != I++ * (NarrowNumBits / 8) + FirstOffset)
           return false;
-    } else { // MatchBigEndian by reversing loop counter.
-      for (unsigned i = 0, j = NumStores - 1; i != NumStores; ++i, --j)
-        if (OffsetMap[j] != i * (NarrowNumBits / 8) + FirstOffset)
+      }
+    } else {
+      for (auto Iter = OffsetMap.rbegin(); Iter != OffsetMap.rend(); Iter++) {
+        if (Iter->second != I++ * (NarrowNumBits / 8) + FirstOffset)
           return false;
       }
+    }
     return true;
   };
 
   // Check if the offsets line up for the native data layout of this target.
   bool NeedBswap = false;
   bool NeedRotate = false;
-  if (!checkOffsets(Layout.isLittleEndian())) {
+  if (!CheckOffsets(Layout.isLittleEndian())) {
     // Special-case: check if byte offsets line up for the opposite endian.
-    if (NarrowNumBits == 8 && checkOffsets(Layout.isBigEndian()))
+    if (NarrowNumBits == 8 && CheckOffsets(Layout.isBigEndian()))
       NeedBswap = true;
-    else if (NumStores == 2 && checkOffsets(Layout.isBigEndian()))
+    else if (NumStores == 2 && CheckOffsets(Layout.isBigEndian()))
       NeedRotate = true;
     else
       return SDValue();
   }
 
   SDLoc DL(N);
+  unsigned FirstShift = OffsetMap.begin()->first;
+  if (FirstShift > 0) {
+    EVT Typ = SourceValue.getValueType();
+    SDValue ShiftAmt = DAG.getConstant(FirstShift * NarrowNumBits, DL, Typ);
+    SourceValue = DAG.getNode(ISD::SRL, DL, Typ, SourceValue, ShiftAmt);
+  }
   if (WideVT != SourceValue.getValueType()) {
     assert(SourceValue.getValueType().getScalarSizeInBits() > WideNumBits &&
            "Unexpected store value to merge");
     SourceValue = DAG.getNode(ISD::TRUNCATE, DL, WideVT, SourceValue);
   }
-
-  // Before legalize we can introduce illegal bswaps/rotates which will be later
-  // converted to an explicit bswap sequence. This way we end up with a single
-  // store and byte shuffling instead of several stores and byte shuffling.
+  // Before legalize we can introduce illegal bswaps/rotates which will be
+  // later converted to an explicit bswap sequence. This way we end up with a
+  // single store and byte shuffling instead of several stores and byte
+  // shuffling.
   if (NeedBswap) {
     SourceValue = DAG.getNode(ISD::BSWAP, DL, WideVT, SourceValue);
   } else if (NeedRotate) {
     assert(WideNumBits % 2 == 0 && "Unexpected type for rotate");
     SDValue RotAmt = DAG.getConstant(WideNumBits / 2, DL, WideVT);
     SourceValue = DAG.getNode(ISD::ROTR, DL, WideVT, SourceValue, RotAmt);
   }
 
+  if (Use2St16) {
+    SDValue ShiftAmt = DAG.getConstant(16, DL, MVT::i32);
+    SDValue SourceValueL =
+        DAG.getNode(ISD::TRUNCATE, DL, MVT::i16, SourceValue);
+    SDValue SourceValueH =
+        DAG.getNode(ISD::SRL, DL, MVT::i32, SourceValue, ShiftAmt);
+    SourceValueH = DAG.getNode(ISD::TRUNCATE, DL, MVT::i16, SourceValueH);
+
+    SDValue NewSt16L =
+        DAG.getStore(Chain, DL, SourceValueL, FirstStore->getBasePtr(),
+                     FirstStore->getPointerInfo(), FirstStore->getAlign());
+    SDValue Baseptr = FirstStore->getBasePtr();
+    EVT BaseptrType = Baseptr.getValueType();
+    SDValue AddrH = DAG.getNode(ISD::ADD, DL, BaseptrType, Baseptr,
+                                DAG.getConstant(16, DL, BaseptrType));
+    SDValue NewSt16H =
+        DAG.getStore(NewSt16L, DL, SourceValueH, AddrH,
+                     FirstStore->getPointerInfo(), FirstStore->getAlign());
+    return NewSt16H;
+  }
+
   SDValue NewStore =
       DAG.getStore(Chain, DL, SourceValue, FirstStore->getBasePtr(),
                    FirstStore->getPointerInfo(), FirstStore->getAlign());
 
   // Rely on other DAG combine rules to remove the other individual stores.
   DAG.ReplaceAllUsesWith(N, NewStore.getNode());
   return NewStore;
 }

llvm/test/CodeGen/RISCV/store-combine.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s \
+; RUN:   | FileCheck %s -check-prefix=RV32
+; RUN: llc -mtriple=riscv64 -verify-machineinstrs < %s \
+; RUN:   | FileCheck %s -check-prefix=RV64
+
+; The ll test case is derived from the following C code
+;struct ab {
+;  char a;
+;  char b;
+;  char c;
+;  char d;
+;} __attribute__((aligned(2)));
+;
+;void store0(struct ab *_ab, unsigned v) {
+;  _ab->a = v & 0xff;
+;  _ab->b = (v >> 8) & 0xff;
+;  _ab->c = (v >> 16) & 0xff;
+;  _ab->d = (v >> 24) & 0xff;
+;}
+;void store1(struct ab *_ab, unsigned v) {
+;  _ab->a = v & 0xff;
+;  _ab->b = (v >> 8) & 0xff;
+;}
+;void store2(struct ab *_ab, unsigned v) {
+;  _ab->c = (v >> 16) & 0xff;
+;  _ab->d = (v >> 24) & 0xff;
+;}
+;void store3(struct ab *_ab, unsigned v) {
+;  _ab->c = (v)&0xff;
+;  _ab->d = (v >> 8) & 0xff;
+;}
+; No to combine stores for such case as
+; (char)(v >> 8) and (char)(v >> 24) can't
+; be converted to (short)(v>>8)
+;void store4(struct ab *_ab, unsigned v) {
+;  _ab->c = (v >> 8) & 0xff;
+;  _ab->d = (v >> 24) & 0xff;
+;}
+
+%struct.ab = type { i8, i8, i8, i8 }
+
+define void @store_0(%struct.ab* %_ab, i32 %v) {
+; RV32-LABEL: store_0:
+; RV32:       # %bb.0:
+; RV32-NEXT:    srli a2, a1, 16
+; RV32-NEXT:    sh a1, 0(a0)
+; RV32-NEXT:    sh a2, 16(a0)
+; RV32-NEXT:    ret
+;
+; RV64-LABEL: store_0:
+; RV64:       # %bb.0:
+; RV64-NEXT:    sh a1, 0(a0)
+; RV64-NEXT:    srli a1, a1, 16
+; RV64-NEXT:    sh a1, 16(a0)
+; RV64-NEXT:    ret
+  %conv = trunc i32 %v to i8
+  %a = getelementptr inbounds %struct.ab, %struct.ab* %_ab, i32 0, i32 0
+  store i8 %conv, i8* %a, align 2
+  %shr = lshr i32 %v, 8
+  %conv2 = trunc i32 %shr to i8
+  %b = getelementptr inbounds %struct.ab, %struct.ab* %_ab, i32 0, i32 1
+  store i8 %conv2, i8* %b, align 1
+  %shr3 = lshr i32 %v, 16
+  %conv5 = trunc i32 %shr3 to i8
+  %c = getelementptr inbounds %struct.ab, %struct.ab* %_ab, i32 0, i32 2
+  store i8 %conv5, i8* %c, align 2
+  %shr6 = lshr i32 %v, 24
+  %conv8 = trunc i32 %shr6 to i8
+  %d = getelementptr inbounds %struct.ab, %struct.ab* %_ab, i32 0, i32 3
+  store i8 %conv8, i8* %d, align 1
+  ret void
+}
+
+define void @store_1(%struct.ab* %_ab, i32 %v) {
+; RV32-LABEL: store_1:
+; RV32:       # %bb.0:
+; RV32-NEXT:    sh a1, 0(a0)
+; RV32-NEXT:    ret
+;
+; RV64-LABEL: store_1:
+; RV64:       # %bb.0:
+; RV64-NEXT:    sh a1, 0(a0)
+; RV64-NEXT:    ret
+  %conv = trunc i32 %v to i8
+  %a = getelementptr inbounds %struct.ab, %struct.ab* %_ab, i32 0, i32 0
+  store i8 %conv, i8* %a, align 2
+  %shr = lshr i32 %v, 8
+  %conv2 = trunc i32 %shr to i8
+  %b = getelementptr inbounds %struct.ab, %struct.ab* %_ab, i32 0, i32 1
+  store i8 %conv2, i8* %b, align 1
+  ret void
+}
+
+define void @store2(%struct.ab* %_ab, i32 %v) {
+; RV32-LABEL: store2:
+; RV32:       # %bb.0:
+; RV32-NEXT:    srli a1, a1, 16
+; RV32-NEXT:    sh a1, 2(a0)
+; RV32-NEXT:    ret
+;
+; RV64-LABEL: store2:
+; RV64:       # %bb.0:
+; RV64-NEXT:    srli a1, a1, 16
+; RV64-NEXT:    sh a1, 2(a0)
+; RV64-NEXT:    ret
+  %shr = lshr i32 %v, 16
+  %conv = trunc i32 %shr to i8
+  %c = getelementptr inbounds %struct.ab, %struct.ab* %_ab, i32 0, i32 2
+  store i8 %conv, i8* %c, align 2
+  %shr1 = lshr i32 %v, 24
+  %conv3 = trunc i32 %shr1 to i8
+  %d = getelementptr inbounds %struct.ab, %struct.ab* %_ab, i32 0, i32 3
+  store i8 %conv3, i8* %d, align 1
+  ret void
+}
+
+define void @store3(%struct.ab* %_ab, i32 %v) {
+; RV32-LABEL: store3:
+; RV32:       # %bb.0:
+; RV32-NEXT:    sh a1, 2(a0)
+; RV32-NEXT:    ret
+;
+; RV64-LABEL: store3:
+; RV64:       # %bb.0:
+; RV64-NEXT:    sh a1, 2(a0)
+; RV64-NEXT:    ret
+  %conv = trunc i32 %v to i8
+  %c = getelementptr inbounds %struct.ab, %struct.ab* %_ab, i32 0, i32 2
+  store i8 %conv, i8* %c, align 2
+  %shr = lshr i32 %v, 8
+  %conv2 = trunc i32 %shr to i8
+  %d = getelementptr inbounds %struct.ab, %struct.ab* %_ab, i32 0, i32 3
+  store i8 %conv2, i8* %d, align 1
+  ret void
+}
+
+; not to combine stores
+define dso_local void @store4(%struct.ab* %_ab, i32 %v){
+; RV32-LABEL: store4:
+; RV32:       # %bb.0: # %entry
+; RV32-NEXT:    srli a2, a1, 8
+; RV32-NEXT:    sb a2, 2(a0)
+; RV32-NEXT:    srli a1, a1, 24
+; RV32-NEXT:    sb a1, 3(a0)
+; RV32-NEXT:    ret
+;
+; RV64-LABEL: store4:
+; RV64:       # %bb.0: # %entry
+; RV64-NEXT:    srli a2, a1, 8
+; RV64-NEXT:    sb a2, 2(a0)
+; RV64-NEXT:    srli a1, a1, 24
+; RV64-NEXT:    sb a1, 3(a0)
+; RV64-NEXT:    ret
+entry:
+  %shr = lshr i32 %v, 8
+  %conv = trunc i32 %shr to i8
+  %c = getelementptr inbounds %struct.ab, %struct.ab* %_ab, i32 0, i32 2
+  store i8 %conv, i8* %c, align 2
+  %shr1 = lshr i32 %v, 24
+  %conv3 = trunc i32 %shr1 to i8
+  %d = getelementptr inbounds %struct.ab, %struct.ab* %_ab, i32 0, i32 3
+  store i8 %conv3, i8* %d, align 1
+  ret void
+}