[DAGCombine] Fix bug in MergeConsecutiveStores

[ahatanak]

Summary

This bug manifests when there are two loads and two stores that are chained as follows in a DAG,

(ld v3f32) -> (st f32) -> (ld v3f32) -> (st f32)

and the store's values are extracted from the preceding vector loads.

The current code in trunk creates a build_vector node and then inserts the new merged store node between the two load nodes. This creates a cycle between the merged store node, the build_vector node, the extract_vector_elt node, and the second vector load (set a breakpoint at DAGCombiner.cpp:10056 to visualize the transformation), which eventually results in a crash during type legalization.

This patch fixes the bug by inserting the new merged store at the position of the last store node in the chain.

[spatel]

Hi Akira,

I don't feel qualified to fully review this patch; it's not clear to me that choosing the last store is the correct solution...
so I've just pointed out some nits. :)

I'm curious if you tracked down why this fails on aarch64 but not x86-64? Something in the x86 backend prevents the stores from merging?

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10065 ↗

(On Diff #23301)

Comment does not match code now: "earliest store" should be "latest store"?

10135 ↗

(On Diff #23301)

Comment does not match code now: "first store" should be "last store"?

10523 ↗

(On Diff #23301)

Comment does not match code now: "earliest store" should be "latest store"?

10568 ↗

(On Diff #23301)

Comment does not match code now: "first store" should be "last store"?

test/CodeGen/AArch64/merge-store.ll

6 ↗

(On Diff #23301)

Can the test case be minimized? Do we need @g1?
I think it would be good to also add check lines to makes sure that the loads were merged into the register as expected ahead of the store.

[t.p.northover]

It's not clear to me that choosing the last store is the correct solution...

We already check memory aliasing before calling MergeStoresOfConstantsOrVecElts, so I think only direct data dependence matters; but stores to not produce any (non-chain) values so moving them later can't create a loop.

So I think the patch is essentially sound.

Tim.

[ahatanak]

When the target is x86-64, DAGCombiner::MergeStoresOfConstantsOrVecElts returns early because v2f32 is not a legal vector type for x86-64.

I've updated the comments and simplified the test case a little as per Sanjay's request.

[ahatanak]

Tim & Sanjay, does this look OK?

[spatel]

With Tim's explanation, I think this is fine. LGTM.

[ahatanak]

Thanks, I'll commit the patch today.

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

bool DAGCombiner::MergeStoresOfConstantsOrVecElts(
                   SmallVectorImpl<MemOpLink> &StoreNodes, EVT MemVT,
                   unsigned NumElem, bool IsConstantSrc, bool UseVector) {
   // Make sure we have something to merge.
   if (NumElem < 2)
     return false;
 
   int64_t ElementSizeBytes = MemVT.getSizeInBits() / 8;
   LSBaseSDNode *FirstInChain = StoreNodes[0].MemNode;
-  unsigned EarliestNodeUsed = 0;
+  unsigned LatestNodeUsed = 0;
 
   for (unsigned i=0; i < NumElem; ++i) {
     // Find a chain for the new wide-store operand. Notice that some
     // of the store nodes that we found may not be selected for inclusion
     // in the wide store. The chain we use needs to be the chain of the
-    // earliest store node which is *used* and replaced by the wide store.
-    if (StoreNodes[i].SequenceNum > StoreNodes[EarliestNodeUsed].SequenceNum)
-      EarliestNodeUsed = i;
+    // latest store node which is *used* and replaced by the wide store.
+    if (StoreNodes[i].SequenceNum < StoreNodes[LatestNodeUsed].SequenceNum)
+      LatestNodeUsed = i;
   }
 
-  // The earliest Node in the DAG.
-  LSBaseSDNode *EarliestOp = StoreNodes[EarliestNodeUsed].MemNode;
+  // The latest Node in the DAG.
+  LSBaseSDNode *LatestOp = StoreNodes[LatestNodeUsed].MemNode;
   SDLoc DL(StoreNodes[0].MemNode);
 
   SDValue StoredVal;
   if (UseVector) {
     // Find a legal type for the vector store.
     EVT Ty = EVT::getVectorVT(*DAG.getContext(), MemVT, NumElem);
     assert(TLI.isTypeLegal(Ty) && "Illegal vector store");
     if (IsConstantSrc) {
for (unsigned i = 0; i < NumElem ; ++i) {
       }
     }
 
     // Create the new Load and Store operations.
     EVT StoreTy = EVT::getIntegerVT(*DAG.getContext(), StoreBW);
     StoredVal = DAG.getConstant(StoreInt, StoreTy);
   }
 
-  SDValue NewStore = DAG.getStore(EarliestOp->getChain(), DL, StoredVal,
+  SDValue NewStore = DAG.getStore(LatestOp->getChain(), DL, StoredVal,
                                   FirstInChain->getBasePtr(),
                                   FirstInChain->getPointerInfo(),
                                   false, false,
                                   FirstInChain->getAlignment());
 
-  // Replace the first store with the new store
-  CombineTo(EarliestOp, NewStore);
+  // Replace the last store with the new store
+  CombineTo(LatestOp, NewStore);
   // Erase all other stores.
   for (unsigned i = 0; i < NumElem ; ++i) {
-    if (StoreNodes[i].MemNode == EarliestOp)
+    if (StoreNodes[i].MemNode == LatestOp)
       continue;
     StoreSDNode *St = cast<StoreSDNode>(StoreNodes[i].MemNode);
     // ReplaceAllUsesWith will replace all uses that existed when it was
     // called, but graph optimizations may cause new ones to appear. For
     // example, the case in pr14333 looks like
     //
     //  St's chain -> St -> another store -> X
     //
bool DAGCombiner::MergeConsecutiveStores(StoreSDNode* St) {
   // We add +1 here because the LastXXX variables refer to location while
   // the NumElem refers to array/index size.
   unsigned NumElem = std::min(LastConsecutiveStore, LastConsecutiveLoad) + 1;
   NumElem = std::min(LastLegalType, NumElem);
 
   if (NumElem < 2)
     return false;
 
-  // The earliest Node in the DAG.
-  unsigned EarliestNodeUsed = 0;
-  LSBaseSDNode *EarliestOp = StoreNodes[EarliestNodeUsed].MemNode;
+  // The latest Node in the DAG.
+  unsigned LatestNodeUsed = 0;
   for (unsigned i=1; i<NumElem; ++i) {
     // Find a chain for the new wide-store operand. Notice that some
     // of the store nodes that we found may not be selected for inclusion
     // in the wide store. The chain we use needs to be the chain of the
-    // earliest store node which is *used* and replaced by the wide store.
-    if (StoreNodes[i].SequenceNum > StoreNodes[EarliestNodeUsed].SequenceNum)
-      EarliestNodeUsed = i;
+    // latest store node which is *used* and replaced by the wide store.
+    if (StoreNodes[i].SequenceNum < StoreNodes[LatestNodeUsed].SequenceNum)
+      LatestNodeUsed = i;
   }
 
+  LSBaseSDNode *LatestOp = StoreNodes[LatestNodeUsed].MemNode;
+
   // Find if it is better to use vectors or integers to load and store
   // to memory.
   EVT JointMemOpVT;
   if (UseVectorTy) {
     JointMemOpVT = EVT::getVectorVT(*DAG.getContext(), MemVT, NumElem);
   } else {
     unsigned StoreBW = NumElem * ElementSizeBytes * 8;
     JointMemOpVT = EVT::getIntegerVT(*DAG.getContext(), StoreBW);
   }
 
   SDLoc LoadDL(LoadNodes[0].MemNode);
   SDLoc StoreDL(StoreNodes[0].MemNode);
 
   LoadSDNode *FirstLoad = cast<LoadSDNode>(LoadNodes[0].MemNode);
   SDValue NewLoad = DAG.getLoad(JointMemOpVT, LoadDL,
                                 FirstLoad->getChain(),
                                 FirstLoad->getBasePtr(),
                                 FirstLoad->getPointerInfo(),
                                 false, false, false,
                                 FirstLoad->getAlignment());
 
-  SDValue NewStore = DAG.getStore(EarliestOp->getChain(), StoreDL, NewLoad,
+  SDValue NewStore = DAG.getStore(LatestOp->getChain(), StoreDL, NewLoad,
                                   FirstInChain->getBasePtr(),
                                   FirstInChain->getPointerInfo(), false, false,
                                   FirstInChain->getAlignment());
 
   // Replace one of the loads with the new load.
   LoadSDNode *Ld = cast<LoadSDNode>(LoadNodes[0].MemNode);
   DAG.ReplaceAllUsesOfValueWith(SDValue(Ld, 1),
                                 SDValue(NewLoad.getNode(), 1));
 
   // Remove the rest of the load chains.
   for (unsigned i = 1; i < NumElem ; ++i) {
     // Replace all chain users of the old load nodes with the chain of the new
     // load node.
     LoadSDNode *Ld = cast<LoadSDNode>(LoadNodes[i].MemNode);
     DAG.ReplaceAllUsesOfValueWith(SDValue(Ld, 1), Ld->getChain());
   }
 
-  // Replace the first store with the new store.
-  CombineTo(EarliestOp, NewStore);
+  // Replace the last store with the new store.
+  CombineTo(LatestOp, NewStore);
   // Erase all other stores.
   for (unsigned i = 0; i < NumElem ; ++i) {
     // Remove all Store nodes.
-    if (StoreNodes[i].MemNode == EarliestOp)
+    if (StoreNodes[i].MemNode == LatestOp)
       continue;
     StoreSDNode *St = cast<StoreSDNode>(StoreNodes[i].MemNode);
     DAG.ReplaceAllUsesOfValueWith(SDValue(St, 0), St->getChain());
     deleteAndRecombine(St);
   }
 
   return true;
 }

llvm/trunk/test/CodeGen/AArch64/merge-store.ll

+; RUN: llc -march=aarch64 %s -o - | FileCheck %s
+
+@g0 = external global <3 x float>, align 16
+@g1 = external global <3 x float>, align 4
+
+; CHECK: ldr s[[R0:[0-9]+]], {{\[}}[[R1:x[0-9]+]]{{\]}}, #4
+; CHECK: ld1.s { v[[R0]] }[1], {{\[}}[[R1]]{{\]}}
+; CHECK: str d[[R0]]
+
+define void @blam() {
+  %tmp4 = getelementptr inbounds <3 x float>, <3 x float>* @g1, i64 0, i64 0
+  %tmp5 = load <3 x float>, <3 x float>* @g0, align 16
+  %tmp6 = extractelement <3 x float> %tmp5, i64 0
+  store float %tmp6, float* %tmp4
+  %tmp7 = getelementptr inbounds float, float* %tmp4, i64 1
+  %tmp8 = load <3 x float>, <3 x float>* @g0, align 16
+  %tmp9 = extractelement <3 x float> %tmp8, i64 1
+  store float %tmp9, float* %tmp7
+  ret void;
+}

llvm/trunk/test/CodeGen/X86/2012-11-28-merge-store-alias.ll

 ; RUN: llc < %s -march=x86-64 -mcpu=corei7 -mtriple=x86_64-pc-win64 | FileCheck %s
 
 ; CHECK: merge_stores_can
 ; CHECK: callq foo
-; CHECK-NEXT: xorps %xmm0, %xmm0
+; CHECK: xorps %xmm0, %xmm0
 ; CHECK-NEXT: movups  %xmm0
 ; CHECK: callq foo
 ; CHECK: ret
 declare i32 @foo([10 x i32]* )
 
 define i32 @merge_stores_can() nounwind ssp {
   %object1 = alloca [10 x i32]