[DAGCombiner] Fix dependency analysis in checkMergeStoreCandidatesForDependencies

[bjope]

Summary

In the aftermath of D116895 a problem was found in the analysis of
dependencies between store merge candidates in
checkMergeStoreCandidatesForDependencies, that is needed to avoid
the cycles are introduced in the DAG.

In the past it has been enough (or assumed to be enough) to start
scanning from non-chain operands when analysing the store merge
candidates for dependencies, assuming that the analysis of chain
dependencies performed when finding the candidates would cover
up for potential dependencies that exist involving the chain operands.
It was however discovered that one could end up with scenarios such
as descibed in the aarch64-checkMergeStoreCandidatesForDependencies.ll
test case, when the dependency between two stores is given by a mix
of chain operand dependencies and non-chain operand dependencies.

The fix in this patch make sure that we also account for chain operand
dependencies when doing the more elaborate analysis in
checkMergeStoreCandidatesForDependencies, no longer relying on that
the earlier check involving chain operands is enough.

[niravd]

LGTM.

[RKSimon]

@bjope This has been identified as the cause of a major compile time regression - https://github.com/llvm/llvm-project/issues/59800 - please can you take a look?

[bjope]

In D118943#4023264, @RKSimon wrote:

@bjope This has been identified as the cause of a major compile time regression - https://github.com/llvm/llvm-project/issues/59800 - please can you take a look?

Thanks for the heads up @RKSimon.
IIRC this fix was done to avoid some ICE (LLVM unreachable). So the fix was just to make the analysis correct.
I can take a look to see if I can find something to improve.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (auto *Ldn = dyn_cast<LoadSDNode>(RootNode)) {
     }
   } else {
     for (auto I = RootNode->use_begin(), E = RootNode->use_end();
          I != E && NumNodesExplored < MaxSearchNodes; ++I, ++NumNodesExplored)
       TryToAddCandidate(I);
   }
 }
 
-// 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
-// through the chain). Check in parallel by searching up from
-// non-chain operands of candidates.
+// 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 operands. Check in parallel by searching up from operands of candidates.
 bool DAGCombiner::checkMergeStoreCandidatesForDependencies(
     SmallVectorImpl<MemOpLink> &StoreNodes, unsigned NumStores,
     SDNode *RootNode) {
   // FIXME: We should be able to truncate a full search of
   // predecessors by doing a BFS and keeping tabs the originating
   // stores from which worklist nodes come from in a similar way to
   // TokenFactor simplfication.
 
bool DAGCombiner::checkMergeStoreCandidatesForDependencies(
 
   // Don't count pruning nodes towards max.
   unsigned int Max = 1024 + Visited.size();
   // Search Ops of store candidates.
   for (unsigned i = 0; i < NumStores; ++i) {
     SDNode *N = StoreNodes[i].MemNode;
     // Of the 4 Store Operands:
     //   * Chain (Op 0) -> We have already considered these
-    //                    in candidate selection and can be
-    //                    safely ignored
+    //                     in candidate selection, but only by following the
+    //                     chain dependencies. We could still have a chain
+    //                     dependency to a load, that has a non-chain dep to
+    //                     another load, that depends on a store, etc. So it is
+    //                     possible to have dependencies that consist of a mix
+    //                     of chain and non-chain deps, and we need to include
+    //                     chain operands in the analysis here..
     //   * Value (Op 1) -> Cycles may happen (e.g. through load chains)
     //   * Address (Op 2) -> Merged addresses may only vary by a fixed constant,
     //                       but aren't necessarily fromt the same base node, so
     //                       cycles possible (e.g. via indexed store).
     //   * (Op 3) -> Represents the pre or post-indexing offset (or undef for
     //               non-indexed stores). Not constant on all targets (e.g. ARM)
     //               and so can participate in a cycle.
-    for (unsigned j = 1; j < N->getNumOperands(); ++j)
+    for (unsigned j = 0; j < N->getNumOperands(); ++j)
       Worklist.push_back(N->getOperand(j).getNode());
   }
   // Search through DAG. We can stop early if we find a store node.
   for (unsigned i = 0; i < NumStores; ++i)
     if (SDNode::hasPredecessorHelper(StoreNodes[i].MemNode, Visited, Worklist,
                                      Max)) {
       // If the searching bail out, record the StoreNode and RootNode in the
       // StoreRootCountMap. If we have seen the pair many times over a limit,

llvm/test/CodeGen/AArch64/aarch64-checkMergeStoreCandidatesForDependencies.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple aarch64-- -o - %s | FileCheck %s
+
+; This used to fail when legalizing types, due to not detecting that a cycle
+; in the DAG was introduced when merging consecutive stores.
+;
+; When checking for cycles the DAG looks like this:
+;
+;   SelectionDAG has 16 nodes:
+;     t0: ch = EntryToken
+;       t3: i64 = add nuw GlobalAddress:i64<%str0* @g0> 0, Constant:i64<8>
+;     t6: ch = store<(store (s64) into %ir.sp1, align 1, !tbaa !1)> t0, Constant:i64<0>, t3, undef:i64
+;     t7: i64,ch = load<(load (s64) from `%str1** undef`, align 1)> t6, undef:i64, undef:i64
+;       t8: i64 = add nuw t7, Constant:i64<8>
+;     t9: i64,ch = load<(load (s64) from %ir.lp0, align 1)> t6, t8, undef:i64
+;         t21: ch = store<(store (s64) into %ir.sp01, align 1)> t19:1, Constant:i64<0>, GlobalAddress:i64<%str0* @g0> 0, undef:i64
+;       t24: ch = TokenFactor t7:1, t9:1, t21
+;     t14: ch,glue = CopyToReg t24, Register:i64 $x0, t19
+;     t19: i64,ch = load<(load (s64) from %ir.lp12, align 1, !tbaa !7)> t0, t9, undef:i64
+;     t15: ch = AArch64ISD::RET_FLAG t14, Register:i64 $x0, t14:1
+;
+; The t21 store depends on t19 (via a chain dependency),
+; t19 load depends on t9 (via address operand),
+; t9 load depends on the t6 store (via chain).
+;
+; So there is a ordering dependency between the two stores, even if it can't
+; be found by only following chain dependencies. Neither can it be found by
+; scanning from all merge candidates when only considering the non-chain
+; operands as a starting point for the scan (as
+; checkMergeStoreCandidatesForDependencies used to do).
+;
+; This test case validates that ISel is a success, and that no store merge is
+; performed.
+
+%str0 = type { i64, i64 }
+%str1 = type { i64, %str1* }
+
+@g0 = external global %str0, align 1
+
+define i64 @foo() {
+; CHECK-LABEL: foo:
+; CHECK:       // %bb.0: // %entry
+; CHECK-NEXT:    adrp x8, :got:g0
+; CHECK-NEXT:    ldr x8, [x8, :got_lo12:g0]
+; CHECK-NEXT:    ldr x9, [x8]
+; CHECK-NEXT:    str xzr, [x8, #8]
+; CHECK-NEXT:    ldr x9, [x9, #8]
+; CHECK-NEXT:    ldr x0, [x9]
+; CHECK-NEXT:    str xzr, [x8]
+; CHECK-NEXT:    ret
+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}