[SCEV][NFC] Factor out common API for getting unique operands of a SCEV

[mkazantsev]

Summary

This function is used at least in 2 places, to it makes sense to make it separate.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

6627

We loose the exit-early with huge operand behavior here.

6642

Please back out the pushOp inlining and just call it here.

[reames]

LGTM

[nikic]

I'm concerned that as-implemented this is could cause non-determinism in edge cases. SmallPtrSet has non-deterministic order, and I think the code in getDefiningScopeBound can be order dependent for cases where scopes with no dominance relation are involved (i.e. neither dominates the other). Do we need the "unique" aspect here? Ideally I'd just return an ArrayRef.

[mkazantsev]

Well, uniqueness is to reduce overhead for the users. If that concerns you, I'll rewrite it into returning vector of unique elements in deterministic order.

[mkazantsev]

Addressed Nikita's non-determinism concern.

[reames]

To be explicit, still LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::getNonTrivialDefiningScopeBound(const SCEV *S) {
   if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(S))
     return &*AddRec->getLoop()->getHeader()->begin();
   if (auto *U = dyn_cast<SCEVUnknown>(S))
     if (auto *I = dyn_cast<Instruction>(U->getValue()))
       return I;
   return nullptr;
 }
 
+/// Fills \p Ops with unique operands of \p S, if it has operands. If not,
+/// \p Ops remains unmodified.
+static void collectUniqueOps(const SCEV *S,
+                             SmallVectorImpl<const SCEV *> &Ops) {
+  SmallPtrSet<const SCEV *, 4> Unique;
+  auto InsertUnique = [&](const SCEV *S) {
+    if (Unique.insert(S).second)
+      Ops.push_back(S);
+  };
+  if (auto *S2 = dyn_cast<SCEVCastExpr>(S))
+    for (auto *Op : S2->operands())
+      InsertUnique(Op);
+  else if (auto *S2 = dyn_cast<SCEVNAryExpr>(S))
+    for (auto *Op : S2->operands())
+      InsertUnique(Op);
+  else if (auto *S2 = dyn_cast<SCEVUDivExpr>(S))
+    for (auto *Op : S2->operands())
+      InsertUnique(Op);
+}
+
 const Instruction *
 ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops) {
   // Do a bounded search of the def relation of the requested SCEVs.
   SmallSet<const SCEV *, 16> Visited;
   SmallVector<const SCEV *> Worklist;
   auto pushOp = [&](const SCEV *S) {
     if (!Visited.insert(S).second)
       return;
     // Threshold of 30 here is arbitrary.
     if (Visited.size() > 30)
       return;
     Worklist.push_back(S);
   };
 
   for (auto *S : Ops)
     pushOp(S);
 
   const Instruction *Bound = nullptr;
   while (!Worklist.empty()) {
     auto *S = Worklist.pop_back_val();
     if (auto *DefI = getNonTrivialDefiningScopeBound(S)) {
       if (!Bound || DT.dominates(Bound, DefI))
         Bound = DefI;
-    } else if (auto *S2 = dyn_cast<SCEVCastExpr>(S))
-      for (auto *Op : S2->operands())
-        pushOp(Op);
-    else if (auto *S2 = dyn_cast<SCEVNAryExpr>(S))
-      for (auto *Op : S2->operands())
-        pushOp(Op);
-    else if (auto *S2 = dyn_cast<SCEVUDivExpr>(S))
-      for (auto *Op : S2->operands())
+    } else {
+      SmallVector<const SCEV *, 4> Ops;
+      collectUniqueOps(S, Ops);
+      for (auto *Op : Ops)
         pushOp(Op);
     }
+  }
   return Bound ? Bound : &*F.getEntryBlock().begin();
 }
 
 bool ScalarEvolution::isGuaranteedToTransferExecutionTo(const Instruction *A,
                                                         const Instruction *B) {
   if (A->getParent() == B->getParent() &&
       isGuaranteedToTransferExecutionToSuccessor(A->getIterator(),
                                                  B->getIterator()))
     return true;
for (auto &KV : ValueExprMap) {
     if (!AR)
       continue;
     assert(ValidLoops.contains(AR->getLoop()) &&
            "AddRec references invalid loop");
   }
 
   // Verify intergity of SCEV users.
   for (const auto &S : UniqueSCEVs) {
-    SmallPtrSet<const SCEV *, 4> Ops;
-    if (const auto *NS = dyn_cast<SCEVNAryExpr>(&S))
-      Ops.insert(NS->op_begin(), NS->op_end());
-    else if (const auto *CS = dyn_cast<SCEVCastExpr>(&S))
-      Ops.insert(CS->getOperand());
-    else if (const auto *DS = dyn_cast<SCEVUDivExpr>(&S)) {
-      Ops.insert(DS->getLHS());
-      Ops.insert(DS->getRHS());
-    }
+    SmallVector<const SCEV *, 4> Ops;
+    collectUniqueOps(&S, Ops);
     for (const auto *Op : Ops) {
       // We do not store dependencies of constants.
       if (isa<SCEVConstant>(Op))
         continue;
       auto It = SCEVUsers.find(Op);
       if (It != SCEVUsers.end() && It->second.count(&S))
         continue;
       dbgs() << "Use of operand  " << *Op << " by user " << S