Fix a missed opportunity to optimize consecutive stores.

[nadav]

Summary

This commit fixes a missed opportunity in merging consecutive stores. The code that searches for stores skipped the case of stores that directly connect to the root. The comment above the implementation lists this case but the code did not handle it. I found this pattern when looking into the shared_ptr destructor. GCC generates the right sequence. Here is a small repo:

int foo(int* buff) {
    buff[0] = 0;
    int x = buff[1];
    buff[1] = 0;
    return x;
}

[hoy]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

17497

Does it matter if Store3 interferes with one of the loads? Wondering if it is dealt with somewhere, otherwise merging store3 with the stores following the loads might cause be a problem.

[hoy]

This is a good catch. Thanks for the fix and adding a test for it.

[nadav]

@hoy Thank you for the review. Yes, the code in TryToAddCandidate and CandidateMatch checks that all of the stores have the same base. I added a second test where the load aliases and prevents the store merging.

[nadav]

Added the test merge_store_alias that checks that aliasing loads prevent the merging of the store operations.

[hoy]

LGTM.

[uabelho]

Hi,

Anyone seen problems with this patch?
I have a case for my out-of-tree target where this patch causes two stores to be merged leading to a cycle in the DAG.
So in the initial DAG we have the following dependencies

store2 <- load1 <- load2 <- load3 <- store1

and then store2 and store1 are merged to store21 and we end up with dependencies like this:

store12 <- load1 <- load2 <- load3
                          <- store12

ie. load2 depends on both load3 and store12 so we have a broken DAG with a cycle in it.
So then we end up with

Operand not processed?0x882a240
t9: i16,ch = load<(load (s16) from %ir.next1.i)> t26, t8, undef:i16

UNREACHABLE executed at ../lib/CodeGen/SelectionDAG/LegalizeTypes.cpp:503!

I haven't been able to reproduce this for any in-tree targets yet so it might very well be something we've broken for our target but I thought I'd mention here that we see problems in case anyone else does too.

[bjope]

llvm/test/CodeGen/Hexagon/store-widen-aliased-load.ll

1

Why are you disabling the combiner-store-merging in this test case? Looks like a typo?

Reading the comment history in this ticket I got a feeling that this test case was added to verify that no store merge happened in this case. But then it seems really weird to verify that in a test case were the store merging is disabled.

Maybe there should be two RUN-lines, expecting the same result regardless if combiner-store-merging is true or false?

[bjope]

llvm/test/CodeGen/Hexagon/store-widen-aliased-load.ll

1

Aw, sorry, I now realize that the test case you added for the alias situation was in test/CodeGen/X86/MergeConsecutiveStores.ll.

[bjope]

In D116895#3269548, @uabelho wrote:

Hi,

Anyone seen problems with this patch?
I have a case for my out-of-tree target where this patch causes two stores to be merged leading to a cycle in the DAG.
So in the initial DAG we have the following dependencies

store2 <- load1 <- load2 <- load3 <- store1

and then store2 and store1 are merged to store21 and we end up with dependencies like this:

store12 <- load1 <- load2 <- load3
                          <- store12

ie. load2 depends on both load3 and store12 so we have a broken DAG with a cycle in it.
So then we end up with

Operand not processed?0x882a240
t9: i16,ch = load<(load (s16) from %ir.next1.i)> t26, t8, undef:i16

UNREACHABLE executed at ../lib/CodeGen/SelectionDAG/LegalizeTypes.cpp:503!

I haven't been able to reproduce this for any in-tree targets yet so it might very well be something we've broken for our target but I thought I'd mention here that we see problems in case anyone else does too.

Here is a reproducer using aarch64 as target:

; RUN: llc -mtriple aarch64-- -o /dev/null %s | FileCheck %s

%str0 = type { i64, i64 }
%str1 = type { i64, %str1* }

@g0 = external global %str0, align 1

define i64 @foo() {
entry:
  %sp0 = getelementptr inbounds %str0, %str0* @g0, i32 0, i32 0
  %sp1 = getelementptr inbounds %str0, %str0* @g0, i32 0, i32 1
  store i64 0, i64* %sp1, align 1, !tbaa !1
  %l0 = load %str1*, %str1** undef, align 1
  %lp0 = getelementptr inbounds %str1, %str1* %l0, i32 0, i32 1
  %l1 = load %str1*, %str1** %lp0, align 1
  %lp1 = getelementptr inbounds %str1, %str1* %l1, i32 0, i32 0
  %l2 = load i64, i64* %lp1, align 1, !tbaa !7
  store i64 0, i64* %sp0, align 1
  ret i64 %l2
}

!llvm.ident = !{!0}

!0 = !{!"clang version 14.0.0.prerel"}
!1 = !{!2, !6, i16 1}
!2 = !{!"dinges", !3, i16 0, !6, i16 1}
!3 = !{!"int", !4, i16 0}
!4 = !{!"omnipotent char", !5, i16 0}
!5 = !{!"Simple C/C++ TBAA"}
!6 = !{!"any pointer", !4, i16 0}
!7 = !{!2, !3, i16 0}

As mentioned here https://discourse.llvm.org/t/dagcombiner-chains-and-mergeconsecutivestores/59623 , maybe the fault isn't exactly related to this patch (even if it was exposed by this patch) but rather that checkMergeStoreCandidatesForDependencies need to analyse the chain operands as well.

[nadav]

Hi Björn. Thank you for looking into this bug and reproducing the problem on aarch64. It sounds like you found the underlying issue in checkMergeStoreCandidatesForDependencies. Do you need help with anything?

[bjope]

In D116895#3294189, @nadav wrote:

Hi Björn. Thank you for looking into this bug and reproducing the problem on aarch64. It sounds like you found the underlying issue in checkMergeStoreCandidatesForDependencies. Do you need help with anything?

Well, I proposed a fix here: D118943
I haven't really thought much about alternative solutions.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

void DAGCombiner::getStoreMergeCandidates(
   if (auto *Ldn = dyn_cast<LoadSDNode>(RootNode)) {
     RootNode = Ldn->getChain().getNode();
     for (auto I = RootNode->use_begin(), E = RootNode->use_end();
          I != E && NumNodesExplored < MaxSearchNodes; ++I, ++NumNodesExplored) {
       if (I.getOperandNo() == 0 && isa<LoadSDNode>(*I)) { // walk down chain
         for (auto I2 = (*I)->use_begin(), E2 = (*I)->use_end(); I2 != E2; ++I2)
           TryToAddCandidate(I2);
       }
+      // Check stores that depend on the root (e.g. Store 3 in the chart above).
+      if (I.getOperandNo() == 0 && isa<StoreSDNode>(*I)) {
+        TryToAddCandidate(I);
+      }
     }
   } else {
     for (auto I = RootNode->use_begin(), E = RootNode->use_end();
          I != E && NumNodesExplored < MaxSearchNodes; ++I, ++NumNodesExplored)
       TryToAddCandidate(I);
   }
 }
 

llvm/test/CodeGen/Hexagon/store-widen-aliased-load.ll

-; RUN: llc -march=hexagon < %s | FileCheck %s
+; RUN: llc -march=hexagon --combiner-store-merging=false < %s | FileCheck %s
 ; CHECK-NOT: memh
 ; Check that store widening does not merge the two stores.
 
 target datalayout = "e-p:32:32:32-i64:64:64-i32:32:32-i16:16:16-i1:32:32-f64:64:64-f32:32:32-v64:64:64-v32:32:32-a0:0-n16:32"
 target triple = "hexagon"
 
 %struct.type_t = type { i8, i8, [2 x i8] }
 

llvm/test/CodeGen/PowerPC/mma-acc-memops.ll

 ; BE-PAIRED-NEXT:    plxv v2, 11(r3), 0
 ; BE-PAIRED-NEXT:    pstxv v3, 35(r3), 0
 ; BE-PAIRED-NEXT:    pstxv v2, 19(r3), 0
 ; BE-PAIRED-NEXT:    blr
 ;
 ; LE-PWR9-LABEL: testUnalignedLdStPair:
 ; LE-PWR9:       # %bb.0: # %entry
 ; LE-PWR9-NEXT:    addis r3, r2, g@toc@ha
-; LE-PWR9-NEXT:    li r6, 19
 ; LE-PWR9-NEXT:    li r4, 11
-; LE-PWR9-NEXT:    li r5, 35
-; LE-PWR9-NEXT:    li r7, 27
 ; LE-PWR9-NEXT:    addi r3, r3, g@toc@l
-; LE-PWR9-NEXT:    lxvx vs0, r3, r6
-; LE-PWR9-NEXT:    ldx r4, r3, r4
-; LE-PWR9-NEXT:    ldx r5, r3, r5
-; LE-PWR9-NEXT:    stdx r4, r3, r6
-; LE-PWR9-NEXT:    stxvx vs0, r3, r7
-; LE-PWR9-NEXT:    li r7, 43
-; LE-PWR9-NEXT:    stdx r5, r3, r7
+; LE-PWR9-NEXT:    lxvx vs0, r3, r4
+; LE-PWR9-NEXT:    li r4, 27
+; LE-PWR9-NEXT:    lxvx vs1, r3, r4
+; LE-PWR9-NEXT:    li r4, 35
+; LE-PWR9-NEXT:    stxvx vs1, r3, r4
+; LE-PWR9-NEXT:    li r4, 19
+; LE-PWR9-NEXT:    stxvx vs0, r3, r4
 ; LE-PWR9-NEXT:    blr
 ;
 ; LE-PWR8-LABEL: testUnalignedLdStPair:
 ; LE-PWR8:       # %bb.0: # %entry
 ; LE-PWR8-NEXT:    addis r3, r2, g@toc@ha
-; LE-PWR8-NEXT:    li r4, 19
+; LE-PWR8-NEXT:    li r4, 27
 ; LE-PWR8-NEXT:    li r5, 11
-; LE-PWR8-NEXT:    li r6, 35
-; LE-PWR8-NEXT:    li r7, 43
-; LE-PWR8-NEXT:    li r8, 27
+; LE-PWR8-NEXT:    li r6, 19
+; LE-PWR8-NEXT:    li r8, 35
 ; LE-PWR8-NEXT:    addi r3, r3, g@toc@l
 ; LE-PWR8-NEXT:    lxvd2x vs0, r3, r4
 ; LE-PWR8-NEXT:    ldx r5, r3, r5
-; LE-PWR8-NEXT:    ldx r6, r3, r6
-; LE-PWR8-NEXT:    stdx r6, r3, r7
-; LE-PWR8-NEXT:    stdx r5, r3, r4
+; LE-PWR8-NEXT:    ldx r7, r3, r6
+; LE-PWR8-NEXT:    stdx r7, r3, r4
+; LE-PWR8-NEXT:    stdx r5, r3, r6
 ; LE-PWR8-NEXT:    stxvd2x vs0, r3, r8
 ; LE-PWR8-NEXT:    blr
 ;
 ; BE-PWR9-LABEL: testUnalignedLdStPair:
 ; BE-PWR9:       # %bb.0: # %entry
 ; BE-PWR9-NEXT:    addis r3, r2, g@toc@ha
-; BE-PWR9-NEXT:    li r6, 19
 ; BE-PWR9-NEXT:    li r4, 11
-; BE-PWR9-NEXT:    li r5, 35
-; BE-PWR9-NEXT:    li r7, 27
 ; BE-PWR9-NEXT:    addi r3, r3, g@toc@l
-; BE-PWR9-NEXT:    lxvx vs0, r3, r6
-; BE-PWR9-NEXT:    ldx r4, r3, r4
-; BE-PWR9-NEXT:    ldx r5, r3, r5
-; BE-PWR9-NEXT:    stdx r4, r3, r6
-; BE-PWR9-NEXT:    stxvx vs0, r3, r7
-; BE-PWR9-NEXT:    li r7, 43
-; BE-PWR9-NEXT:    stdx r5, r3, r7
+; BE-PWR9-NEXT:    lxvx vs0, r3, r4
+; BE-PWR9-NEXT:    li r4, 27
+; BE-PWR9-NEXT:    lxvx vs1, r3, r4
+; BE-PWR9-NEXT:    li r4, 35
+; BE-PWR9-NEXT:    stxvx vs1, r3, r4
+; BE-PWR9-NEXT:    li r4, 19
+; BE-PWR9-NEXT:    stxvx vs0, r3, r4
 ; BE-PWR9-NEXT:    blr
 ;
 ; BE-PWR8-LABEL: testUnalignedLdStPair:
 ; BE-PWR8:       # %bb.0: # %entry
 ; BE-PWR8-NEXT:    addis r3, r2, g@toc@ha
-; BE-PWR8-NEXT:    li r4, 19
-; BE-PWR8-NEXT:    li r5, 11
-; BE-PWR8-NEXT:    li r6, 35
-; BE-PWR8-NEXT:    li r7, 27
+; BE-PWR8-NEXT:    li r4, 11
+; BE-PWR8-NEXT:    li r5, 27
 ; BE-PWR8-NEXT:    addi r3, r3, g@toc@l
 ; BE-PWR8-NEXT:    lxvd2x vs0, r3, r4
-; BE-PWR8-NEXT:    ldx r5, r3, r5
-; BE-PWR8-NEXT:    ldx r6, r3, r6
-; BE-PWR8-NEXT:    stxvd2x vs0, r3, r7
-; BE-PWR8-NEXT:    li r7, 43
-; BE-PWR8-NEXT:    stdx r5, r3, r4
-; BE-PWR8-NEXT:    stdx r6, r3, r7
+; BE-PWR8-NEXT:    lxvd2x vs1, r3, r5
+; BE-PWR8-NEXT:    li r4, 35
+; BE-PWR8-NEXT:    li r5, 19
+; BE-PWR8-NEXT:    stxvd2x vs1, r3, r4
+; BE-PWR8-NEXT:    stxvd2x vs0, r3, r5
 ; BE-PWR8-NEXT:    blr
 entry:
   %0 = bitcast <256 x i1>* @g to i8*
   %add.ptr = getelementptr inbounds i8, i8* %0, i64 11
   %add.ptr1 = getelementptr inbounds i8, i8* %0, i64 19
   %1 = bitcast i8* %add.ptr to <256 x i1>*
   %2 = bitcast i8* %add.ptr1 to <256 x i1>*
   %3 = load <256 x i1>, <256 x i1>* %1, align 64
   store <256 x i1> %3, <256 x i1>* %2, align 64
   ret void
 }

llvm/test/CodeGen/X86/MergeConsecutiveStores.ll

; CHECK-NEXT:    retq
   store i8 %v0, i8* %d0, align 1
   store i8 %v1, i8* %d1, align 1
   store i8 %v2, i8* %d2, align 1
   store i8 %v3, i8* %d3, align 1
   store i32 %v4, i32* %d4, align 4
   ret void
 }
 
+define i32 @merge_store_load_store_seq(i32* %buff) {
+entry:
+; CHECK-LABEL: merge_store_load_store_seq:
+; CHECK:      movl 4(%rdi), %eax
+; CHECK-NEXT: movq $0, (%rdi)
+; CHECK-NEXT: retq
+
+  store i32 0, i32* %buff, align 4
+  %arrayidx1 = getelementptr inbounds i32, i32* %buff, i64 1
+  %0 = load i32, i32* %arrayidx1, align 4
+  store i32 0, i32* %arrayidx1, align 4
+  ret i32 %0
+}
+
+define i32 @merge_store_alias(i32* %buff, i32* %other) {
+entry:
+; CHECK-LABEL: merge_store_alias:
+; CHECK:  movl $0, (%rdi)
+; CHECK-NEXT:  movl (%rsi), %eax
+; CHECK-NEXT:  movl $0, 4(%rdi)
+; CHECK-NEXT:  retq
+
+  store i32 0, i32* %buff, align 4
+  %arrayidx1 = getelementptr inbounds i32, i32* %buff, i64 1
+  %0 = load i32, i32* %other, align 4
+  store i32 0, i32* %arrayidx1, align 4
+  ret i32 %0
+}