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

7561

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?

7732

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

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

2

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

79

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

4

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

79

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

7663

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?

79

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

79

Yes, they are not needed. I fixed them.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::mergeTruncStores(StoreSDNode *N) {
   LLVMContext &Context = *DAG.getContext();
   unsigned NumStores = Stores.size();
   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();
 
+  // Find the minimal offset
+  uint64_t OffsetMin = UINT64_MAX;
+  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)
+      return SDValue();
+    // Other than the first/last part, a shift operation is required to get the
+    // offset.
+    uint64_t Offset = 0;
+    SDValue WideVal = Trunc.getOperand(0);
+    if ((WideVal.getOpcode() == ISD::SRL || WideVal.getOpcode() == ISD::SRA) &&
+        isa<ConstantSDNode>(WideVal.getOperand(1))) {
+      // The shift amount must be a constant multiple of the narrow type.
+      // It is translated to the offset address in the wide source value "y".
+      //
+      // x = srl y, ShiftAmtC
+      // i8 z = trunc x
+      // store z, ...
+      uint64_t ShiftAmtC = WideVal.getConstantOperandVal(1);
+      if (ShiftAmtC % NarrowNumBits != 0)
+        return SDValue();
+
+      Offset = ShiftAmtC / NarrowNumBits;
+    }
+    if (Offset < OffsetMin)
+      OffsetMin = Offset;
+  }
+
   // 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);
   int64_t FirstOffset = INT64_MAX;
   StoreSDNode *FirstStore = nullptr;
   Optional<BaseIndexOffset> Base;
   for (auto Store : Stores) {
if ((WideVal.getOpcode() == ISD::SRL || WideVal.getOpcode() == ISD::SRA) &&
       //
       // x = srl y, ShiftAmtC
       // i8 z = trunc x
       // store z, ...
       uint64_t ShiftAmtC = WideVal.getConstantOperandVal(1);
       if (ShiftAmtC % NarrowNumBits != 0)
         return SDValue();
 
-      Offset = ShiftAmtC / NarrowNumBits;
+      Offset = ShiftAmtC / NarrowNumBits - OffsetMin;
       WideVal = WideVal.getOperand(0);
     }
 
     // Stores must share the same source value with different offsets.
     // Truncate and extends should be stripped to get the single source value.
     if (!SourceValue)
       SourceValue = WideVal;
     else if (stripTruncAndExt(SourceValue) != stripTruncAndExt(WideVal))
for (auto Store : Stores) {
 
     // 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 (Offset >= NumStores || OffsetMap[Offset] != INT64_MAX)
       return SDValue();
     OffsetMap[Offset] = ByteOffsetFromBase;
   }
 
   assert(FirstOffset != INT64_MAX && "First byte offset must be set");
   assert(FirstStore && "First store must be set");
 
   // 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) {
     if (MatchLittleEndian) {
       for (unsigned i = 0; i != NumStores; ++i)
         if (OffsetMap[i] != i * (NarrowNumBits / 8) + FirstOffset)
           return false;
if (NarrowNumBits == 8 && checkOffsets(Layout.isBigEndian()))
       NeedBswap = true;
     else if (NumStores == 2 && checkOffsets(Layout.isBigEndian()))
       NeedRotate = true;
     else
       return SDValue();
   }
 
   SDLoc DL(N);
+  if (OffsetMin > 0) {
+    EVT Typ = SourceValue.getValueType();
+    SDValue ShiftAmt = DAG.getConstant(OffsetMin * 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 SourceValueL;
+    SDValue SourceValueH;
+    SDValue ShiftAmt = DAG.getConstant(16, DL, MVT::i32);
+    SourceValueL = DAG.getNode(ISD::TRUNCATE, DL, MVT::i16, SourceValue);
+    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 AddrH =
+        DAG.getNode(ISD::ADD, DL, MVT::i32, FirstStore->getBasePtr(),
+                    DAG.getConstant(16, DL, MVT::i32));
+    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
+
+%struct.ab = type { i8, i8, i8, i8 }
+;
+define void @store_0(%struct.ab* nocapture noundef writeonly %_ab, i32 noundef %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
+  %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, !tbaa !4
+  %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, !tbaa !8
+  %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, !tbaa !9
+  %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, !tbaa !10
+  ret void
+}
+
+define void @store_1(%struct.ab* nocapture noundef writeonly %_ab, i32 noundef %v) {
+; RV32-LABEL: store_1:
+; RV32:       # %bb.0:
+; RV32-NEXT:    sh a1, 0(a0)
+; RV32-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, !tbaa !4
+  %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, !tbaa !8
+  ret void
+}
+
+define void @store3(%struct.ab* nocapture noundef writeonly %_ab, i32 noundef %v) {
+; RV32-LABEL: store3:
+; RV32:       # %bb.0:
+; RV32-NEXT:    srli a1, a1, 16
+; RV32-NEXT:    sh a1, 2(a0)
+; RV32-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, !tbaa !9
+  %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, !tbaa !10
+  ret void
+}
+
+define void @store4(%struct.ab* nocapture noundef writeonly %_ab, i32 noundef %v) {
+; RV32-LABEL: store4:
+; RV32:       # %bb.0:
+; RV32-NEXT:    sh a1, 2(a0)
+; RV32-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, !tbaa !9
+  %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, !tbaa !10
+  ret void
+}
+
+!4 = !{!5, !6, i64 0}
+!5 = !{!"ab", !6, i64 0, !6, i64 1, !6, i64 2, !6, i64 3}
+!6 = !{!"omnipotent char", !7, i64 0}
+!7 = !{!"Simple C/C++ TBAA"}
+!8 = !{!5, !6, i64 1}
+!9 = !{!5, !6, i64 2}
+!10 = !{!5, !6, i64 3}