[LibCallsShrinkWrap] Teach the pass how to preserve the dominator

[davide]

Summary

This has been proposed in the past, but I never got to implement it until today.

[efriedma]

lib/Transforms/Utils/LibCallsShrinkWrap.cpp

511

SplitBlockAndInsertIfThen has an optional DominatorTree argument.

[davide]

Much easier, thanks for the pointer

[efriedma]

Could you preserve the DT without requiring it? Not that it matters much for performance, but it would more clear why this pass is requesting the domtree.

[davide]

In D32552#738580, @efriedma wrote:

Could you preserve the DT without requiring it? Not that it matters much for performance, but it would more clear why this pass is requesting the domtree.

I'm not very familiar with the old pass manager infrastructure (I got involved only in new pass manager'y stuffs) and I don't want to cause troubles.
To double check, I just need to remove the addRequired() call/INITIALIZE_DEPENDENCY from the pass right? If so, I'll do another round of testing then commit.

[efriedma]

And use getAnalysisIfAvailable(). Yes, I think that's it.

lib/Transforms/Utils/LibCallsShrinkWrap.cpp

 
 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/Pass.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
public:
   bool runOnFunction(Function &F) override;
 };
 }
 
 char LibCallsShrinkWrapLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap",
                       "Conditionally eliminate dead library calls", false,
                       false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap",
                     "Conditionally eliminate dead library calls", false, false)
 
 namespace {
 class LibCallsShrinkWrap : public InstVisitor<LibCallsShrinkWrap> {
 public:
-  LibCallsShrinkWrap(const TargetLibraryInfo &TLI) : TLI(TLI), Changed(false){};
+  LibCallsShrinkWrap(const TargetLibraryInfo &TLI, DominatorTree &DT)
+      : TLI(TLI), DT(DT), Changed(false){};
   bool isChanged() const { return Changed; }
   void visitCallInst(CallInst &CI) { checkCandidate(CI); }
   void perform() {
     for (auto &CI : WorkList) {
       DEBUG(dbgs() << "CDCE calls: " << CI->getCalledFunction()->getName()
                    << "\n");
       if (perform(CI)) {
         Changed = true;
private:
   // Create a single condition.
   Value *createCond(CallInst *CI, CmpInst::Predicate Cmp, float Val) {
     IRBuilder<> BBBuilder(CI);
     Value *Arg = CI->getArgOperand(0);
     return createCond(BBBuilder, Arg, Cmp, Val);
   }
 
   const TargetLibraryInfo &TLI;
+  DominatorTree &DT;
   SmallVector<CallInst *, 16> WorkList;
   bool Changed;
 };
 } // end anonymous namespace
 
 // Perform the transformation to calls with errno set by domain error.
 bool LibCallsShrinkWrap::performCallDomainErrorOnly(CallInst *CI,
                                                     const LibFunc &Func) {
Value *LibCallsShrinkWrap::generateCondForPow(CallInst *CI,
   return nullptr;
 }
 
 // Wrap conditions that can potentially generate errno to the library call.
 void LibCallsShrinkWrap::shrinkWrapCI(CallInst *CI, Value *Cond) {
   assert(Cond != nullptr && "hrinkWrapCI is not expecting an empty call inst");
   MDNode *BranchWeights =
       MDBuilder(CI->getContext()).createBranchWeights(1, 2000);
+
   TerminatorInst *NewInst =
-      SplitBlockAndInsertIfThen(Cond, CI, false, BranchWeights);
+      SplitBlockAndInsertIfThen(Cond, CI, false, BranchWeights, &DT);
   BasicBlock *CallBB = NewInst->getParent();
   CallBB->setName("cdce.call");
-  CallBB->getSingleSuccessor()->setName("cdce.end");
+  BasicBlock *SuccBB = CallBB->getSingleSuccessor();
+  assert(SuccBB && "The split block should have a single successor");
+  SuccBB->setName("cdce.end");
   CI->removeFromParent();
   CallBB->getInstList().insert(CallBB->getFirstInsertionPt(), CI);
   DEBUG(dbgs() << "== Basic Block After ==");
   DEBUG(dbgs() << *CallBB->getSinglePredecessor() << *CallBB
                << *CallBB->getSingleSuccessor() << "\n");
 }
 
 // Perform the transformation to a single candidate.
bool LibCallsShrinkWrap::perform(CallInst *CI) {
 
   if (LibCallsShrinkWrapDoRangeError && performCallRangeErrorOnly(CI, Func))
     return true;
 
   return performCallErrors(CI, Func);
 }
 
 void LibCallsShrinkWrapLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addPreserved<DominatorTreeWrapperPass>();
   AU.addPreserved<GlobalsAAWrapperPass>();
+  AU.addRequired<DominatorTreeWrapperPass>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
 }
 
-static bool runImpl(Function &F, const TargetLibraryInfo &TLI) {
+static bool runImpl(Function &F, const TargetLibraryInfo &TLI,
+                    DominatorTree &DT) {
   if (F.hasFnAttribute(Attribute::OptimizeForSize))
     return false;
-  LibCallsShrinkWrap CCDCE(TLI);
+  LibCallsShrinkWrap CCDCE(TLI, DT);
   CCDCE.visit(F);
   CCDCE.perform();
+
+// Verify the dominator after we've updated it locally.
+#ifndef NDEBUG
+  DT.verifyDomTree();
+#endif
   return CCDCE.isChanged();
 }
 
 bool LibCallsShrinkWrapLegacyPass::runOnFunction(Function &F) {
   auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
-  return runImpl(F, TLI);
+  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  return runImpl(F, TLI, DT);
 }
 
 namespace llvm {
 char &LibCallsShrinkWrapPassID = LibCallsShrinkWrapLegacyPass::ID;
 
 // Public interface to LibCallsShrinkWrap pass.
 FunctionPass *createLibCallsShrinkWrapPass() {
   return new LibCallsShrinkWrapLegacyPass();
 }
 
 PreservedAnalyses LibCallsShrinkWrapPass::run(Function &F,
                                               FunctionAnalysisManager &FAM) {
   auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
-  bool Changed = runImpl(F, TLI);
+  auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
+  bool Changed = runImpl(F, TLI, DT);
   if (!Changed)
     return PreservedAnalyses::all();
   auto PA = PreservedAnalyses();
   PA.preserve<GlobalsAA>();
+  PA.preserve<DominatorTreeAnalysis>();
   return PA;
 }
 }