[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

12513

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

12944

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

12513

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

12513

Okay, that's better.

12944

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

12939

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?

include/llvm/CodeGen/ISDOpcodes.h

namespace ISD {
   enum NodeType {
     /// DELETED_NODE - This is an illegal value that is used to catch
     /// errors.  This opcode is not a legal opcode for any node.
     DELETED_NODE,
 
     /// EntryToken - This is the marker used to indicate the start of a region.
     EntryToken,
 
+    /// DummyNode - Temporary node for node replacement. These nodes
+    /// should not persist beyond their introduction.
+    DummyNode,
+
     /// TokenFactor - This node takes multiple tokens as input and produces a
     /// single token result. This is used to represent the fact that the operand
     /// operators are independent of each other.
     TokenFactor,
 
     /// AssertSext, AssertZext - These nodes record if a register contains a
     /// value that has already been zero or sign extended from a narrower type.
     /// These nodes take two operands.  The first is the node that has already

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
bool DAGCombiner::MergeConsecutiveStores(StoreSDNode *St) {
   // Find acceptable loads. Loads need to have the same chain (token factor),
   // 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.
bool DAGCombiner::MergeConsecutiveStores(StoreSDNode *St) {
 
   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, i.e. Replace chains using Ld's chain with a
+      // TokenFactor. Create a temporary node to serve as a placer so
+      // we do not replace the reference to original Load's chain in
+      // the TokenFactor.
+      SDValue TokenDummy = DAG.getNode(ISD::DummyNode, SDLoc(Ld), MVT::Other);
+
+      // Replace all references to Load's output chain to TokenDummy
+      CombineTo(Ld, SDValue(Ld, 0), TokenDummy, false);
+      SDValue Token =
+          DAG.getNode(ISD::TokenFactor, SDLoc(Ld), MVT::Other, SDValue(Ld, 1),
+                      SDValue(NewLoad.getNode(), 1));
+      // Replace all uses of TokenDummy from itself to Ld's output chain.
+      CombineTo(TokenDummy.getNode(), Token);
+      assert(TokenDummy.use_empty() && "TokenDummy should be unused");
+      AddToWorklist(Ld);
+    }
   }
 
   // Replace the all stores with the new store.
   for (unsigned i = 0; i < NumElem; ++i)
     CombineTo(StoreNodes[i].MemNode, NewStore);
   return true;
 }
 

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