[SDAG] Relax conditions under stores of loaded values can be merged

[niravd]

Summary

Allow consecutive stores whose values come from consecutive loads to
merged in the presense of other uses of the loads. Previously this was
disallowed as in general the merged load cannot be shared with the
other uses. Merging N stores into 1 may cause as many as N redundant
loads. However in the context of caching this should have neglible
affect on memory pressure and reduce instruction count making it
almost always a win.

Fixes PR32086.

[spatel]

The output certainly looks good - thanks!

I'm still not confident in my understanding of chains and tokenfactors, so adding some more potential reviewers. I just made some minor comments for the test file.

test/CodeGen/X86/merge_store_duplicated_loads.ll

1–4

1. Can you please commit these tests before the code change? That way we have a baseline check for today's codegen, and we'll just see the improvements from your patch.

2. If you put the triple in the RUN line, you can use utils/update_llc_test_checks.py to auto-generate the check lines. Then, when you update the tests with the code change, you just run that script again and won't have to manually write any CHECK lines.

3. Please add a comment with 'PR32086' and/or a link to bugzilla here. That makes it easier to keep track of the motivation and backstory for the tests.

[efriedma]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12565

Is this a correctness check, or a profitability check? At first glance, it isn't obvious why we're checking any of this here.

13014

Why do you need to CombineTo twice? Please explain in a comment.

[niravd]

Add comments and do minor cleanup of parameter filter.

[niravd]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12565

Folded in some pending code cleanup that makes this a bit mroe clear. This is a filter to make sure we only get mergeable candidates that would be profitable.

[efriedma]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12565

Okay, that's better.

13014

Ah, I see what you're doing. I really don't like the fact that you're creating a TokenFactor which uses itself, even temporarily... but I'm not sure what the best approach is. Could you ask on llvmdev?

[niravd]

Cleanup and rebase over D31068

[niravd]

Rebasing to head to show simplified patch.

[niravd]

Rewrite chain update to address Eli's concerns.

[efriedma]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13007

The approach makes sense... but I'm surprised a TokenFactor with zero operands doesn't cause an assertion failure somewhere. Could you use a new opcode for this?

Also, please add an assertion that TokenDummy has zero uses.

[niravd]

Address Eli's comments

[efriedma]

LGTM.

[niravd]

Temporarily reverted due to error in clang-ppc64be-linux-multistage.

[RKSimon]

llvm/trunk/test/CodeGen/X86/merge_store_duplicated_loads.ll

5 ↗

(On Diff #98511)

As mentioned on PR32086, please remove this triple and add a -mtriple=i686-unknown-linux-gnu test run to check 32-bit codegen as well.

[niravd]

Rebase past StoreMerge Cleanup.

[niravd]

PPC bug exists, but rebasing to make use of Sanjay's helper function cleanup.

[RKSimon]

Reopening this until the PPC regressions are fixed

[jyknight]

Not sure if the PPC issue was a different one, but the commit that reverted this was:

Revert "[SDAG] Relax conditions under stores of loaded values can be merged"

This reverts r302712.

The change fails with ASAN enabled:

ERROR: AddressSanitizer: use-after-poison on address ... at ...
READ of size 2 at ... thread T0
  #0 ... in llvm::SDNode::getNumValues() const <snip>/include/llvm/CodeGen/SelectionDAGNodes.h:855:42
  #1 ... in llvm::SDNode::hasAnyUseOfValue(unsigned int) const <snip>/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:7270:3
  #2 ... in llvm::SDValue::use_empty() const <snip> include/llvm/CodeGen/SelectionDAGNodes.h:1042:17
  #3 ... in (anonymous namespace)::DAGCombiner::MergeConsecutiveStores(llvm::StoreSDNode*) <snip>/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:12944:7

Reviewers: niravd

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D33081

llvm-svn: 302746

[niravd]

I can't speak to the PPC issue, but from jyknight's comment:

This is almost certainly just a matter of deleting the assert. I would land this myself, but I've yet to go through the official "you can commit" with the new companieslegal.

Is anyone willing to try removing the assert and recommiting?

[RKSimon]

@niravd What's the status of this patch?

[niravd]

I've not touched this and probably will not for the forseeable future. Is someone else willing to take the lead on this?

In D30471#1732403, @RKSimon wrote:

@niravd What's the status of this patch?

[RKSimon]

@niravd Abandon this?

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

for (auto I = RootNode->use_begin(), E = RootNode->use_end(); I != E; ++I)
               BaseIndexOffset Ptr;
               if (CandidateMatch(OtherST, Ptr))
                 StoreNodes.push_back(MemOpLink(OtherST, Ptr.Offset));
             }
   } else
     for (auto I = RootNode->use_begin(), E = RootNode->use_end(); I != E; ++I)
       if (I.getOperandNo() == 0)
         if (StoreSDNode *OtherST = dyn_cast<StoreSDNode>(*I)) {
           BaseIndexOffset Ptr;
           if (CandidateMatch(OtherST, Ptr))
             StoreNodes.push_back(MemOpLink(OtherST, Ptr.Offset));
         }
 }
 
 // We need to check that merging these stores does not cause a loop
 // in the DAG. Any store candidate may depend on another candidate
 // indirectly through its operand (we already consider dependencies
while (StoreNodes.size() > 1) {
     // must not be zext, volatile, indexed, and they must be consecutive.
     BaseIndexOffset LdBasePtr;
     for (unsigned i = 0; i < NumConsecutiveStores; ++i) {
       StoreSDNode *St = cast<StoreSDNode>(StoreNodes[i].MemNode);
       LoadSDNode *Ld = dyn_cast<LoadSDNode>(St->getValue());
       if (!Ld)
         break;
 
-      // Loads must only have one use.
-      if (!Ld->hasNUsesOfValue(1, 0))
-        break;
-
       // The memory operands must not be volatile.
       if (Ld->isVolatile() || Ld->isIndexed())
         break;
 
       // We do not accept ext loads.
       if (Ld->getExtensionType() != ISD::NON_EXTLOAD)
         break;
 
-      // The stored memory type must be the same.
-      if (Ld->getMemoryVT() != MemVT)
-        break;
-
       BaseIndexOffset LdPtr = BaseIndexOffset::match(Ld->getBasePtr(), DAG);
       // If this is not the first ptr that we check.
       if (LdBasePtr.Base.getNode()) {
         // The base ptr must be the same.
         if (!LdPtr.equalBaseIndex(LdBasePtr))
           break;
       } else {
         // Check that all other base pointers are the same as this one.
while (StoreNodes.size() > 1) {
 
     SDValue NewStore = DAG.getStore(
         NewStoreChain, StoreDL, NewLoad, FirstInChain->getBasePtr(),
         FirstInChain->getPointerInfo(), FirstStoreAlign);
 
     // Transfer chain users from old loads to the new load.
     for (unsigned i = 0; i < NumElem; ++i) {
       LoadSDNode *Ld = cast<LoadSDNode>(LoadNodes[i].MemNode);
+      if (SDValue(Ld, 0).hasOneUse()) {
+        // Only the original store used value so just replace chain.
         DAG.ReplaceAllUsesOfValueWith(SDValue(Ld, 1),
                                       SDValue(NewLoad.getNode(), 1));
+      } else {
+        // Multiple uses exist. Keep the old load in line with the new
+        // load.
+        DAG.makeEquivalentMemoryOrdering(Ld, NewLoad);
+        AddToWorklist(Ld);
+      }
     }
 
     // Replace the all stores with the new store.
     for (unsigned i = 0; i < NumElem; ++i)
       CombineTo(StoreNodes[i].MemNode, NewStore);
     RV = true;
     StoreNodes.erase(StoreNodes.begin(), StoreNodes.begin() + NumElem);
     continue;

test/CodeGen/X86/merge_store_duplicated_loads.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc %s -mtriple=x86_64-unknown-linux-gnu -mcpu=corei7 -o - | FileCheck %s
 
-
+; PR32086
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @merge_double(double* noalias nocapture %st, double* noalias nocapture readonly %ld) #0 {
 ; CHECK-LABEL: merge_double:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    movsd {{.*#+}} xmm0 = mem[0],zero
-; CHECK-NEXT:    movsd {{.*#+}} xmm1 = mem[0],zero
-; CHECK-NEXT:    movsd %xmm0, (%rdi)
-; CHECK-NEXT:    movsd %xmm1, 8(%rdi)
-; CHECK-NEXT:    movsd %xmm0, 16(%rdi)
-; CHECK-NEXT:    movsd %xmm1, 24(%rdi)
+; CHECK-NEXT:    movups (%rsi), %xmm0
+; CHECK-NEXT:    movups %xmm0, (%rdi)
+; CHECK-NEXT:    movups %xmm0, 16(%rdi)
 ; CHECK-NEXT:    retq
   %ld_idx1 = getelementptr inbounds double, double* %ld, i64 1
   %ld0 = load double, double* %ld, align 8, !tbaa !2
   %ld1 = load double, double* %ld_idx1, align 8, !tbaa !2
 
   %st_idx1 = getelementptr inbounds double, double* %st, i64 1
   %st_idx2 = getelementptr inbounds double, double* %st, i64 2
   %st_idx3 = getelementptr inbounds double, double* %st, i64 3
 
   store double %ld0, double* %st, align 8, !tbaa !2
   store double %ld1, double* %st_idx1, align 8, !tbaa !2
   store double %ld0, double* %st_idx2, align 8, !tbaa !2
   store double %ld1, double* %st_idx3, align 8, !tbaa !2
   ret void
 }
 
 define void @merge_loadstore_int(i64* noalias nocapture readonly %p, i64* noalias nocapture %q) local_unnamed_addr #0 {
 ; CHECK-LABEL: merge_loadstore_int:
 ; CHECK:       # BB#0: # %entry
-; CHECK-NEXT:    movq (%rdi), %rax
-; CHECK-NEXT:    movq 8(%rdi), %rcx
-; CHECK-NEXT:    movq %rax, (%rsi)
-; CHECK-NEXT:    movq %rcx, 8(%rsi)
-; CHECK-NEXT:    movq %rax, 16(%rsi)
-; CHECK-NEXT:    movq %rcx, 24(%rsi)
+; CHECK-NEXT:    movups (%rdi), %xmm0
+; CHECK-NEXT:    movups %xmm0, (%rsi)
+; CHECK-NEXT:    movups %xmm0, 16(%rsi)
 ; CHECK-NEXT:    retq
 entry:
   %0 = load i64, i64* %p, align 8, !tbaa !1
   %arrayidx1 = getelementptr inbounds i64, i64* %p, i64 1
   %1 = load i64, i64* %arrayidx1, align 8, !tbaa !1
   store i64 %0, i64* %q, align 8, !tbaa !1
   %arrayidx3 = getelementptr inbounds i64, i64* %q, i64 1
   store i64 %1, i64* %arrayidx3, align 8, !tbaa !1
   %arrayidx4 = getelementptr inbounds i64, i64* %q, i64 2
   store i64 %0, i64* %arrayidx4, align 8, !tbaa !1
   %arrayidx5 = getelementptr inbounds i64, i64* %q, i64 3
   store i64 %1, i64* %arrayidx5, align 8, !tbaa !1
   ret void
 }
 
 define i64 @merge_loadstore_int_with_extra_use(i64* noalias nocapture readonly %p, i64* noalias nocapture %q) local_unnamed_addr #0 {
 ; CHECK-LABEL: merge_loadstore_int_with_extra_use:
 ; CHECK:       # BB#0: # %entry
 ; CHECK-NEXT:    movq (%rdi), %rax
-; CHECK-NEXT:    movq 8(%rdi), %rcx
-; CHECK-NEXT:    movq %rax, (%rsi)
-; CHECK-NEXT:    movq %rcx, 8(%rsi)
-; CHECK-NEXT:    movq %rax, 16(%rsi)
-; CHECK-NEXT:    movq %rcx, 24(%rsi)
+; CHECK-NEXT:    movups (%rdi), %xmm0
+; CHECK-NEXT:    movups %xmm0, (%rsi)
+; CHECK-NEXT:    movups %xmm0, 16(%rsi)
 ; CHECK-NEXT:    retq
 entry:
   %0 = load i64, i64* %p, align 8, !tbaa !1
   %arrayidx1 = getelementptr inbounds i64, i64* %p, i64 1
   %1 = load i64, i64* %arrayidx1, align 8, !tbaa !1
   store i64 %0, i64* %q, align 8, !tbaa !1
   %arrayidx3 = getelementptr inbounds i64, i64* %q, i64 1
   store i64 %1, i64* %arrayidx3, align 8, !tbaa !1