[ADCE][Dominators] Teach ADCE to preserve dominators

[kuhar]

Summary

This patch teaches ADCE to preserve both DominatorTrees and PostDominatorTrees.

I didn't notice any performance impact when bootstrapping clang with this patch.

[kuhar]

Don't remove the same edge multiple times.

[davide]

Can you push all these patches to a branch so that Zhendong can do a run on fuzz-testing on them?
(cc: @zhendongsu) I'll be happy if we can do at least one before all the work goes in. It shouldn't take too long and we can review in parallel.
Thanks,

Davide

[grandinj]

lib/Transforms/Scalar/ADCE.cpp

94

perverse -> preserve

[kuhar]

Here's a branch for fuzzing: https://github.com/kuhar/llvm-dominators/tree/fuzzing

[kuhar]

Fix a double edge deletion bug and add a testcase for it.

[kuhar]

Ping.

[kuhar]

Rebase to ToT.

[kuhar]

Add dependency on the DominatorTreeWrapperPass for the LegacyPassManager.

[kuhar]

Update to use the batch API.
Add a regression test for deletions in wrong order.

include/llvm/Support/GenericDomTreeConstruction.h

#ifndef NDEBUG
     assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
 #endif
 
     const TreeNodePtr FromTN = DT.getNode(From);
     // Deletion in an unreachable subtree -- nothing to do.
     if (!FromTN) return;
 
     const TreeNodePtr ToTN = DT.getNode(To);
-    assert(ToTN && "To already unreachable -- there is no edge to delete");
+    if (!ToTN) {
+      DEBUG(dbgs() << "\tTo (" << BlockNamePrinter(To)
+                   << ") already unreachable -- there is no edge to delete\n");
+      return;
+    }
+
     const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
     const TreeNodePtr NCD = DT.getNode(NCDBlock);
 
     // To dominates From -- nothing to do.
     if (ToTN == NCD) return;
 
     const TreeNodePtr ToIDom = ToTN->getIDom();
     DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "

lib/Transforms/Scalar/ADCE.cpp

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IteratedDominanceFrontier.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Pass.h"
 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/Transforms/Scalar.h"
 using namespace llvm;
struct BlockInfoType {
   TerminatorInst *Terminator = nullptr;
 
   /// Post-order numbering of reverse control flow graph.
   unsigned PostOrder;
 };
 
 class AggressiveDeadCodeElimination {
   Function &F;
+
+  // ADCE does not use DominatorTree per se, but it updates it to preserve the
+  // analysis.
+  DominatorTree &DT;
   PostDominatorTree &PDT;
 
   /// Mapping of blocks to associated information, an element in BlockInfoVec.
   DenseMap<BasicBlock *, BlockInfoType> BlockInfo;
   bool isLive(BasicBlock *BB) { return BlockInfo[BB].Live; }
 
   /// Mapping of instructions to associated information.
   DenseMap<Instruction *, InstInfoType> InstInfo;
class AggressiveDeadCodeElimination {
   /// Set the BlockInfo::PostOrder field based on a post-order
   /// numbering of the reverse control flow graph.
   void computeReversePostOrder();
 
   /// Make the terminator of this block an unconditional branch to \p Target.
   void makeUnconditional(BasicBlock *BB, BasicBlock *Target);
 
 public:
-  AggressiveDeadCodeElimination(Function &F, PostDominatorTree &PDT)
-      : F(F), PDT(PDT) {}
-  bool performDeadCodeElimination();
+ AggressiveDeadCodeElimination(Function &F, DominatorTree &DT,
+                               PostDominatorTree &PDT)
+     : F(F), DT(DT), PDT(PDT) {}
 };
 }
 
 bool AggressiveDeadCodeElimination::performDeadCodeElimination() {
   initialize();
   markLiveInstructions();
   return removeDeadInstructions();
 }
for (auto *BB : BlocksWithDeadTerminators) {
     BlockInfoType *PreferredSucc = nullptr;
     for (auto *Succ : successors(BB)) {
       auto *Info = &BlockInfo[Succ];
       if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder)
         PreferredSucc = Info;
     }
     assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&
            "Failed to find safe successor for dead branch");
+
+    // Collect removed successors to update the (Post)DominatorTrees.
+    SmallPtrSet<BasicBlock *, 4> RemovedSuccessors;
     bool First = true;
     for (auto *Succ : successors(BB)) {
-      if (!First || Succ != PreferredSucc->BB)
+      if (!First || Succ != PreferredSucc->BB) {
         Succ->removePredecessor(BB);
-      else
+        RemovedSuccessors.insert(Succ);
+      } else
         First = false;
     }
     makeUnconditional(BB, PreferredSucc->BB);
+
+    // Inform the dominators about the deleted CFG edges.
+    for (auto *Succ : RemovedSuccessors) {
+      // It might have happened that the same successor appeared multiple times
+      // and the CFG edge wasn't really removed.
+      if (Succ != PreferredSucc->BB) {
+        DEBUG(dbgs() << "ADCE: Removing (Post)DomTree edge " << BB->getName()
+                     << " -> " << Succ->getName() << "\n");
+        DT.deleteEdge(BB, Succ);
+        PDT.deleteEdge(BB, Succ);
+      }
+    }
+
     NumBranchesRemoved += 1;
   }
 }
 
 // reverse top-sort order
 void AggressiveDeadCodeElimination::computeReversePostOrder() {
 
   // This provides a post-order numbering of the reverse control flow graph
void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,
   }
   DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n');
   NumBranchesRemoved += 1;
   IRBuilder<> Builder(PredTerm);
   auto *NewTerm = Builder.CreateBr(Target);
   InstInfo[NewTerm].Live = true;
   if (const DILocation *DL = PredTerm->getDebugLoc())
     NewTerm->setDebugLoc(DL);
+
+  InstInfo.erase(PredTerm);
+  PredTerm->eraseFromParent();
 }
 
 //===----------------------------------------------------------------------===//
 //
 // Pass Manager integration code
 //
 //===----------------------------------------------------------------------===//
 PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) {
+  auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
   auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
-  if (!AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination())
+  if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination())
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   PA.preserve<GlobalsAA>();
+  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserve<PostDominatorTreeAnalysis>();
   return PA;
 }
 
 namespace {
 struct ADCELegacyPass : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   ADCELegacyPass() : FunctionPass(ID) {
     initializeADCELegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
+
+    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
-    return AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination();
+    return AggressiveDeadCodeElimination(F, DT, PDT)
+        .performDeadCodeElimination();
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
+    // We require DominatorTree here only to update and thus preserve it.
+    AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<PostDominatorTreeWrapperPass>();
     if (!RemoveControlFlowFlag)
       AU.setPreservesCFG();
+    else {
+      AU.addPreserved<DominatorTreeWrapperPass>();
+      AU.addPreserved<PostDominatorTreeWrapperPass>();
+    }
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 };
 }
 
 char ADCELegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce",
                       "Aggressive Dead Code Elimination", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 INITIALIZE_PASS_END(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
                     false, false)
 
 FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); }

test/Transforms/ADCE/domtree-DoubleDeletion.ll

+; RUN: opt < %s -gvn -simplifycfg -adce | llvm-dis
+; RUN: opt < %s -gvn -simplifycfg -adce -verify-dom-info | llvm-dis
+
+; This test makes sure that the DominatorTree properly handles
+; deletion of edges that go to forward-unreachable regions.
+; In this case, %land.end is already forward unreachable when
+; the DT gets informed about the deletion of %entry -> %land.end.
+
+@a = common global i32 0, align 4
+
+define i32 @main() {
+entry:
+  %retval = alloca i32, align 4
+  store i32 0, i32* %retval, align 4
+  %0 = load i32, i32* @a, align 4
+  %cmp = icmp ne i32 %0, 1
+  br i1 %cmp, label %land.rhs, label %land.end4
+
+land.rhs:                                         ; preds = %entry
+  %1 = load i32, i32* @a, align 4
+  %tobool = icmp ne i32 %1, 0
+  br i1 %tobool, label %land.rhs1, label %land.end
+
+land.rhs1:                                        ; preds = %land.rhs
+  br label %land.end
+
+land.end:                                         ; preds = %land.rhs1, %land.rhs
+  %2 = phi i1 [ false, %land.rhs ], [ true, %land.rhs1 ]
+  %land.ext = zext i1 %2 to i32
+  %conv = trunc i32 %land.ext to i16
+  %conv2 = sext i16 %conv to i32
+  %tobool3 = icmp ne i32 %conv2, 0
+  br label %land.end4
+
+land.end4:                                        ; preds = %land.end, %entry
+  %3 = phi i1 [ false, %entry ], [ %tobool3, %land.end ]
+  %land.ext5 = zext i1 %3 to i32
+  ret i32 0
+}

test/Transforms/ADCE/unreachable.ll

+; RUN: opt < %s -adce -simplifycfg | llvm-dis
+; RUN: opt < %s -passes=adce | llvm-dis
+
+define i32 @Test(i32 %A, i32 %B) {
+BB1:
+        br label %BB4
+
+BB2:            ; No predecessors!
+        br label %BB3
+
+BB3:            ; preds = %BB4, %BB2
+        %ret = phi i32 [ %X, %BB4 ], [ %B, %BB2 ]               ; <i32> [#uses=1]
+        ret i32 %ret
+
+BB4:            ; preds = %BB1
+        %X = phi i32 [ %A, %BB1 ]               ; <i32> [#uses=1]
+        br label %BB3
+}