[GVNHoist] computeInsertionPoints() miscalculates the Iterated Dominance Frontiers

[labrinea]

Summary

Fix for https://bugs.llvm.org/show_bug.cgi?id=38912. In GVNHoist::computeInsertionPoints() we iterate over the Value Numbers and calculate the Iterated Dominance Frontiers without clearing the IDFBlocks vector first. IDFBlocks ends up accumulating an insane number of basic blocks, which bloats the compilation time of SemaChecking.cpp with ubsan enabled.

[sebpop]

Looks good to me.

lib/Transforms/Scalar/GVNHoist.cpp

struct CHIArg {
   Instruction *I;
 
   bool operator==(const CHIArg &A) { return VN == A.VN; }
   bool operator!=(const CHIArg &A) { return !(*this == A); }
 };
 
 using CHIIt = SmallVectorImpl<CHIArg>::iterator;
 using CHIArgs = iterator_range<CHIIt>;
-using CHICache = DenseMap<BasicBlock *, SmallPtrSet<Instruction *, 4>>;
 using OutValuesType = DenseMap<BasicBlock *, SmallVector<CHIArg, 2>>;
 using InValuesType =
     DenseMap<BasicBlock *, SmallVector<std::pair<VNType, Instruction *>, 2>>;
 
 // An invalid value number Used when inserting a single value number into
 // VNtoInsns.
 enum : unsigned { InvalidVN = ~2U };
 
void computeInsertionPoints(const VNtoInsns &Map, HoistingPointList &HPL,
     // - Remove the chi-nodes with missing entries
     // - Remove values from CHI-nodes which do not truly flow out, e.g.,
     //   modified along the path.
     // - Collect the remaining values that are still anticipable
     SmallVector<BasicBlock *, 2> IDFBlocks;
     ReverseIDFCalculator IDFs(*PDT);
     OutValuesType OutValue;
     InValuesType InValue;
-    CHICache CachedCHIs;
     for (const auto &R : Ranks) {
       const SmallVecInsn &V = Map.lookup(R);
       if (V.size() < 2)
         continue;
       const VNType &VN = R;
       SmallPtrSet<BasicBlock *, 2> VNBlocks;
       for (auto &I : V) {
         BasicBlock *BBI = I->getParent();
         if (!hasEH(BBI))
           VNBlocks.insert(BBI);
       }
       // Compute the Post Dominance Frontiers of each basic block
       // The dominance frontier of a live block X in the reverse
       // control graph is the set of blocks upon which X is control
       // dependent. The following sequence computes the set of blocks
       // which currently have dead terminators that are control
       // dependence sources of a block which is in NewLiveBlocks.
       IDFs.setDefiningBlocks(VNBlocks);
+      IDFBlocks.clear();
       IDFs.calculate(IDFBlocks);
 
       // Make a map of BB vs instructions to be hoisted.
       for (unsigned i = 0; i < V.size(); ++i) {
         InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));
       }
       // Insert empty CHI node for this VN. This is used to factor out
       // basic blocks where the ANTIC can potentially change.
       for (auto IDFB : IDFBlocks) {
         for (unsigned i = 0; i < V.size(); ++i) {
           CHIArg C = {VN, nullptr, nullptr};
            // Ignore spurious PDFs.
-          if (DT->properlyDominates(IDFB, V[i]->getParent()) &&
-              CachedCHIs[IDFB].insert(V[i]).second) {
+          if (DT->properlyDominates(IDFB, V[i]->getParent())) {
             OutValue[IDFB].push_back(C);
             LLVM_DEBUG(dbgs() << "\nInsertion a CHI for BB: " << IDFB->getName()
                               << ", for Insn: " << *V[i]);
           }
         }
       }
     }