[llvm][Uniformity] correctly use a vector as a set by uniqifying elements

[sameerds]

Summary

The search for temporal divergence needs to determine a dominance frontier
defined for a cycle. The implementation uses a temporary vector to store a set
of newly discovered successors. Failing to uniqify the elements in this vector
causes a very large regression in compile time due to an exponential number of
redundant visits.

This fixes github issue #61123

[foad]

Works for me, thanks! I have a larger test case that goes from about 50 s to less than 1 ms with this patch.

[piotr]

Would be good to add a test case, but I do realize this can be tricky.

llvm/include/llvm/ADT/GenericUniformityImpl.h

for (auto *W : DomFrontier) {
       for (auto *Succ : successors(W)) {
         if (DomRegion.contains(Succ))
           continue;
         Temp.push_back(Succ);
       }
     }
     if (!Promoted)
       break;
+
+    // Restore the set property for the temporary vector
+    llvm::sort(Temp);
+    Temp.erase(std::unique(Temp.begin(), Temp.end()), Temp.end());
+
     DomFrontier = Temp;
   }
 
   // At DomFrontier, only the PHI nodes are affected by temporal
   // divergence.
   for (const auto *UserBlock : DomFrontier) {
     LLVM_DEBUG(dbgs() << "Analyze phis after cycle exit: "
                       << Context.print(UserBlock) << "\n");