[DAGCombiner] Don't add volatile or indexed stores to ChainedStores

[flyingforyou]

Summary

findBetterNeighborChains does not handle indexed stores.
However, it did not check when adding stores to ChainedStores.

[mcrosier]

It's unclear to me what problem this patch is trying to solve. Can you provide additional details?

Also, please include a test case. In many cases that makes understanding the problem much easier.

[flyingforyou]

Thanks for comment Chad.

I respect your opinion. But I couldn't add testcase for this patch.
Because it's about assert.

So, I want to explain more about this.

for (StoreSDNode *ChainedStore : ChainedStores) {
  // If ChainedStore has more than one value, we don't try replaceStoreChain.
  // replaceStoreChain uses CombineTo, which only consider Chain only.
  if (ChainedStore->getNumValues() != 1)
    continue;

  SDValue Chain = ChainedStore->getChain();
  SDValue BetterChain = FindBetterChain(ChainedStore, Chain);

  if (Chain != BetterChain) {
    MadeChange = true;
    BetterChains.push_back(std::make_pair(ChainedStore, BetterChain));
  }
}

// Do all replacements after finding the replacements to make to avoid making
// the chains more complicated by introducing new TokenFactors.
for (auto Replacement : BetterChains)
  replaceStoreChain(Replacement.first, Replacement.second);

When you see inside of for loop, ChainedStore is added to BetterChains.
After this, replaceStoreChain get ChainedStore for first parameter.

SDValue DAGCombiner::replaceStoreChain(StoreSDNode *ST, SDValue BetterChain) {
  SDLoc SL(ST);
  SDValue ReplStore;

  // Replace the chain to avoid dependency.
  if (ST->isTruncatingStore()) {
    ReplStore = DAG.getTruncStore(BetterChain, SL, ST->getValue(),
                                  ST->getBasePtr(), ST->getMemoryVT(),
                                  ST->getMemOperand());
  } else {
    ReplStore = DAG.getStore(BetterChain, SL, ST->getValue(), ST->getBasePtr(),
                             ST->getMemOperand());
  }

  // Create token to keep both nodes around.
  SDValue Token = DAG.getNode(ISD::TokenFactor, SL,
                              MVT::Other, ST->getChain(), ReplStore);

  // Make sure the new and old chains are cleaned up.
  AddToWorklist(Token.getNode());

  // Don't add users to work list.
  return CombineTo(ST, Token, false);
}

Inside of replaceStoreChain, ChainedStore will be passed to CombineTo's first parameter.
And Token which is CombineTo's second paratemter only can be combined with same type node.

SDValue DAGCombiner::CombineTo(SDNode *N, const SDValue *To, unsigned NumTo,
                               bool AddTo) {
  assert(N->getNumValues() == NumTo && "Broken CombineTo call!");
  ++NodesCombined;
  DEBUG(dbgs() << "\nReplacing.1 ";
        N->dump(&DAG);
        dbgs() << "\nWith: ";
        To[0].getNode()->dump(&DAG);
        dbgs() << " and " << NumTo-1 << " other values\n");
  for (unsigned i = 0, e = NumTo; i != e; ++i)
    assert((!To[i].getNode() ||
            N->getValueType(i) == To[i].getValueType()) &&
           "Cannot combine value to value of different type!");

  WorklistRemover DeadNodes(*this);
  DAG.ReplaceAllUsesWith(N, To);
  if (AddTo) {
    // Push the new nodes and any users onto the worklist
    for (unsigned i = 0, e = NumTo; i != e; ++i) {
      if (To[i].getNode()) {
        AddToWorklist(To[i].getNode());
        AddUsersToWorklist(To[i].getNode());
      }
    }
  }

  // Finally, if the node is now dead, remove it from the graph.  The node
  // may not be dead if the replacement process recursively simplified to
  // something else needing this node.
  if (N->use_empty())
    deleteAndRecombine(N);
  return SDValue(N, 0);
}

There is a assert check assert(N->getNumValues() == NumTo && "Broken CombineTo call!");.
When we call CombineTo(ST, Token, false), this is changed likes below.

/// Replaces all uses of the results of one DAG node with new values.
SDValue CombineTo(SDNode *N, SDValue Res, bool AddTo = true) {
  return CombineTo(N, &Res, 1, AddTo);
}

That means NumTo is always 1. This is why I added check code likes below.

if (ChainedStore->getNumValues() != 1)
  continue;

Junmo.

[arsenm]

Here is a reduced testcase. I’ll try to look at this later

• d16463-reduced.ll922 BDownload

[arsenm]

This isn't exactly the right way to fix this. The problem is this is trying to perform this for an indexed store, which was supposed to be skipped, so it should never end up in the ChainedStores list.

The loop in findBetterNeighborChains is supposed to mirror the logic in getStoreMergeAndAliasCandidates (and will hopefully eventually replace it), but it looks like it will add ChainedStores even for indexed. The first loop here is what should be fixed

[flyingforyou]

Addressed Matt's comments.

Chad, there are several examples about crash. Sorry for misunderstanding.

Junmo.

[mcrosier]

I'll defer to Matt's judgement since he has a far better understanding of the problem then I.

[zzheng]

Isn't this trying to solve the same problem as http://reviews.llvm.org/D15348?

[apazos]

Yes, it looks like the issue in http://reviews.llvm.org/D15348. Matt can you try your reduced test with that on-going review?

[flyingforyou]

Hi Ana.

I am amazed that your first approch is almost same with my first patch.
But the last patch is extending replaceStoreChain. (This is not what I am doing in this patch.)

What is the proper decision about this patch? (Transfer the test case, Abandon?)
Let me know, please.

Junmo.

[arsenm]

In D16463#335628, @apazos wrote:

Yes, it looks like the issue in http://reviews.llvm.org/D15348. Matt can you try your reduced test with that on-going review?

I don't think that patch will fix this bug. It will fix the assertion, but I think this problem uncovers one that will also effect volatiles. You can probably produce a testcase derived from this one which will break volatile handling

[arsenm]

Can you try to come up with a volatile testcase that hits this problem?

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14763–14765 ↗

(On Diff #45841)

We might as well fully break out of the loop here. This is just going to now reach the next iteration and then break the other place this was checked

[apazos]

The fix I have is to allow forming store chains that can contain stores with pre/post increment. So the check for STn->isUnindexed can be removed from Junmo's patch since his is a more restrictive solution. Let's see if Junmo can create a test for the Volatile case only.

[flyingforyou]

Addressed Matt's comments.

[apazos]

Junmo, if my patch goes in, do you still need the check STn->isIndexed()? I hope to have mine merged soon.

[flyingforyou]

Junmo, if my patch goes in, do you still need the check STn->isIndexed()? I hope to have mine merged soon.

Ana, I want to hear about opinion from Matt.
I don't want to disturb your effort in D15348. But the first test-case was made by Matt. And this commit's first reviewer is also Matt.

So, it's belong to him. Matt, could you give me a opinion about this change, please?

Junmo.

[arsenm]

LGTM

[arsenm]

Does the test need check lines? I would kind of expect an invalid merging to occur before with the volatile

[flyingforyou]

Crash occurs before merging in testcase.

Thanks for reviewing Matt.

[flyingforyou]

Ana.

Please, feel free to remove STn->isIndexed(), when your patch is ready. I still think your patch is also good.

Thanks,
Junmo.

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

while (Index) {
     // Find the next memory operand in the chain. If the next operand in the
     // chain is a store then move up and continue the scan with the next
     // memory operand. If the next operand is a load save it and use alias
     // information to check if it interferes with anything.
     SDNode *NextInChain = Index->getChain().getNode();
     while (true) {
       if (StoreSDNode *STn = dyn_cast<StoreSDNode>(NextInChain)) {
         // We found a store node. Use it for the next iteration.
+        if (STn->isVolatile() || STn->isIndexed()) {
+          Index = nullptr;
+          break;
+        }
         ChainedStores.push_back(STn);
         Index = STn;
         break;
       } else if (LoadSDNode *Ldn = dyn_cast<LoadSDNode>(NextInChain)) {
         NextInChain = Ldn->getChain().getNode();
         continue;
       } else {
         Index = nullptr;

llvm/trunk/test/CodeGen/AArch64/aarch64-DAGCombine-findBetterNeighborChains-crash.ll

+; RUN: llc < %s -march=arm64
+; Make sure we are not crashing on this test.
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-unknown-linux-gnu"
+
+declare void @extern(i8*)
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) #0
+
+; Function Attrs: nounwind
+define void @func(float* noalias %arg, i32* noalias %arg1, i8* noalias %arg2, i8* noalias %arg3) #1 {
+bb:
+  %tmp = getelementptr inbounds i8, i8* %arg2, i64 88
+  tail call void @llvm.memset.p0i8.i64(i8* noalias %arg2, i8 0, i64 40, i32 8, i1 false)
+  store i8 0, i8* %arg3
+  store i8 2, i8* %arg2
+  store float 0.000000e+00, float* %arg
+  %tmp4 = bitcast i8* %tmp to <4 x float>*
+  store volatile <4 x float> zeroinitializer, <4 x float>* %tmp4
+  store i32 5, i32* %arg1
+  tail call void @extern(i8* %tmp)
+  ret void
+}
+
+; Function Attrs: nounwind
+define void @func2(float* noalias %arg, i32* noalias %arg1, i8* noalias %arg2, i8* noalias %arg3) #1 {
+bb:
+  %tmp = getelementptr inbounds i8, i8* %arg2, i64 88
+  tail call void @llvm.memset.p0i8.i64(i8* noalias %arg2, i8 0, i64 40, i32 8, i1 false)
+  store i8 0, i8* %arg3
+  store i8 2, i8* %arg2
+  store float 0.000000e+00, float* %arg
+  %tmp4 = bitcast i8* %tmp to <4 x float>*
+  store <4 x float> zeroinitializer, <4 x float>* %tmp4
+  store i32 5, i32* %arg1
+  tail call void @extern(i8* %tmp)
+  ret void
+}
+
+attributes #0 = { argmemonly nounwind }
+attributes #1 = { nounwind "target-cpu"="cortex-a53" }