[LoopUnroll] Use Lazy strategy for DTU used for MergeBlockIntoPredecessor.

[fhahn]

Summary

We do not access the DT in the loop, so we do not have to apply updates
eagerly. We can apply them lazyly and flush them after we are done
merging blocks.

As follow-up work, we might be able to use the DTU above as well,
instead of manually updating the DT.

This brings the example from PR43134 from ~100s to ~4s for a relase +
assertions build on my machine.

[brzycki]

LGTM. I'd still like to hear if @kuhar has any objections.

[asbirlea]

Could you also make the same change in lib/Transforms/Utils/LoopUnrollAndJam.cpp:541?

[brzycki]

llvm/lib/Transforms/Utils/LoopUnroll.cpp

893 ↗

(On Diff #217734)

Nit: possibly add a comment stating this flushes/synchronizes the state of DT?

[kuhar]

Looks good. Thanks!

[fhahn]

In D66911#1649998, @asbirlea wrote:

Could you also make the same change in lib/Transforms/Utils/LoopUnrollAndJam.cpp:541?

Done, in D66918

[fhahn]

Add comment that DTU.getDomTree applies the updates to the DomTree.

llvm/trunk/lib/Transforms/Utils/LoopUnroll.cpp

for (auto *BB : OriginalLoopBlocks) {
       for (auto *ChildBB : ChildrenToUpdate)
         DT->changeImmediateDominator(ChildBB, NewIDom);
     }
   }
 
   assert(!DT || !UnrollVerifyDomtree ||
          DT->verify(DominatorTree::VerificationLevel::Fast));
 
-  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
   // Merge adjacent basic blocks, if possible.
   for (BasicBlock *Latch : Latches) {
     BranchInst *Term = dyn_cast<BranchInst>(Latch->getTerminator());
     assert((Term ||
             (CompletelyUnroll && !LatchIsExiting && Latch == Latches.back())) &&
            "Need a branch as terminator, except when fully unrolling with "
            "unconditional latch");
     if (Term && Term->isUnconditional()) {
       BasicBlock *Dest = Term->getSuccessor(0);
       BasicBlock *Fold = Dest->getUniquePredecessor();
       if (MergeBlockIntoPredecessor(Dest, &DTU, LI)) {
         // Dest has been folded into Fold. Update our worklists accordingly.
         std::replace(Latches.begin(), Latches.end(), Dest, Fold);
         UnrolledLoopBlocks.erase(std::remove(UnrolledLoopBlocks.begin(),
                                              UnrolledLoopBlocks.end(), Dest),
                                  UnrolledLoopBlocks.end());
       }
     }
   }
+  // Apply updates to the DomTree.
+  DT = &DTU.getDomTree();
 
   // At this point, the code is well formed.  We now simplify the unrolled loop,
   // doing constant propagation and dead code elimination as we go.
   simplifyLoopAfterUnroll(L, !CompletelyUnroll && (ULO.Count > 1 || Peeled), LI,
                           SE, DT, AC);
 
   NumCompletelyUnrolled += CompletelyUnroll;
   ++NumUnrolled;