[GlobalOpt] Pass DTU to removeUnreachableBlocks instead of recomputing.

[fhahn]

Summary

removeUnreachableBlocks knows how to preserve the DomTree, so make use
of it instead of re-computing the DT.

[davide]

I think I wrote some of this code and it predates Kuba's incremental dominator updater. I'm fine, but I'll wait if he has opinions cc: @kuhar

[kuhar]

Looks good to me.

[nikic]

I suspect that this change caused a major compile-time performance regression in GlobalOpt. Doesn't this essentially break the laziness of LookupDomTree() and force DT construction even if it will not be needed?

As the removeUnreachableBlocks() call is (presumably) expected to never actually do something outside of manually constructed IR examples, this seems like a bad tradeoff. Ideally we would only fetch the DT here if it exists, but threading that through is likely not worthwhile.

[fhahn]

In D68298#1804128, @nikic wrote:

I suspect that this change caused a major compile-time performance regression in GlobalOpt. Doesn't this essentially break the laziness of LookupDomTree() and force DT construction even if it will not be needed?

Do you have a test case handy? Assuming the DT for F is already computed, LookupDomTree should be free, but looking at the preceding passes, it looks like IPSCCP does not preserve the DTs with the LegacyPassManager (When I tried I could not get a module pass to preserve individual function analysis).

Unless we can get the DTs preserved until here, it is probably best to use getAnalysisIfAvailable<DominatorTreeWrapperPass>() here instead.

[nikic]

Yes, we're still on the legacy manager, so DT is not available here. I've just verified that reverting this patch does indeed reclaim a sizable part of the LLVM 10 compile-time regressions (end-to-end timings).

[xbolva00]

In D68298#1804330, @nikic wrote:

Yes, we're still on the legacy manager, so DT is not available here. I've just verified that reverting this patch does indeed reclaim a sizable part of the LLVM 10 compile-time regressions (end-to-end timings).

Maybe reason of https://bugs.llvm.org/show_bug.cgi?id=44408 too

[fhahn]

In D68298#1804330, @nikic wrote:

Yes, we're still on the legacy manager, so DT is not available here. I've just verified that reverting this patch does indeed reclaim a sizable part of the LLVM 10 compile-time regressions (end-to-end timings).

Hm it seems like the legacy module pass manager does not allow using getAnalysisIfAvailable for function analysis :( I've put up D72214 with a workaround. Does this fix the regression as well? Otherwise I guess the easiest would be to just revert this patch until the legacy pass manager is gone....

[nikic]

@fhahn I've verified that D72214 also fixes the issue (performance difference to a simple revert is in the noise).

[fhahn]

I've revert rG192cce10f67e for now.

llvm/lib/Transforms/IPO/GlobalOpt.cpp

for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
     // LLVM's definition of dominance allows instructions that are cyclic
     // in unreachable blocks, e.g.:
     // %pat = select i1 %condition, @global, i16* %pat
     // because any instruction dominates an instruction in a block that's
     // not reachable from entry.
     // So, remove unreachable blocks from the function, because a) there's
     // no point in analyzing them and b) GlobalOpt should otherwise grow
     // some more complicated logic to break these cycles.
-    // Removing unreachable blocks might invalidate the dominator so we
-    // recalculate it.
     if (!F->isDeclaration()) {
-      if (removeUnreachableBlocks(*F)) {
-        auto &DT = LookupDomTree(*F);
-        DT.recalculate(*F);
-        Changed = true;
-      }
+      DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+      Changed |= removeUnreachableBlocks(*F, &DTU);
     }
 
     Changed |= processGlobal(*F, GetTLI, LookupDomTree);
 
     if (!F->hasLocalLinkage())
       continue;
 
     // If we have an inalloca parameter that we can safely remove the