[LoopInfo] Remove duplicates in ExitBlocks to reduce the compile time of hasDedicatedExits

[wmi]

Summary

For the problem described in https://reviews.llvm.org/D67359, turns out the root cause is there are many duplicates in ExitBlocks so the algorithm complexity of hasDedicatedExits gets very high. If we remove the duplicates, the compile time issue is gone.

Thanks to Philip Reames for raising a good question and lead me to find the root cause.

But how to properly add a compile time test is still a question for me.

[reames]

include/llvm/Analysis/LoopInfoImpl.h

89

Please see: getUniqueExitBlocks on Loop.

[wmi]

Address Philip's comment.

[reames]

LGTM

include/llvm/Analysis/LoopInfoImpl.h

BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
   return nullptr;
 }
 
 template <class BlockT, class LoopT>
 bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const {
   // Each predecessor of each exit block of a normal loop is contained
   // within the loop.
   SmallVector<BlockT *, 4> ExitBlocks;
   getExitBlocks(ExitBlocks);
-  for (BlockT *EB : ExitBlocks)
+  SmallPtrSet<BlockT *, 4> UniqExitBlocks;
+  UniqExitBlocks.insert(ExitBlocks.begin(), ExitBlocks.end());
+  for (BlockT *EB : UniqExitBlocks)
     for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB))
       if (!contains(Predecessor))
         return false;
   // All the requirements are met.
   return true;
 }
 
 // Helper function to get unique loop exits. Pred is a predicate pointing to