[ADCE] Add control dependence computation

[david2050]

Summary

This is part of a serious of patches to evolve ADCE.cpp to support
removing of unnecessary control flow.

This patch adds the ability to compute control dependences using
the iterated dominance frontier. We extend the liveness propagation
to alternate between data and control dependences until convergences.

Modify the pass manager intergation to compute the post-dominator tree
needed for iterator dominance frontier.

We still force all terminators live for now until we add code to
handlinge removing control flow in a later patch.

No changes to effective behavior with this patch

Previous patches:

D23225 [ADCE] Modify data structures to support removing control flow
D23065 [ADCE] Refactor anticipating new functionality (NFC)
D23102 [ADCE] Refactoring for new functionality (NFC)

[nadav]

lib/Transforms/Scalar/ADCE.cpp

285

Comments start with a capital letter. End with a period.

[david2050]

fix comments

[david2050]

Add a missing block which logically fits with this diff (since not yet accepted)

[mehdi_amini]

lib/Transforms/Scalar/ADCE.cpp

459

How expensive is this?

[david2050]

lib/Transforms/Scalar/ADCE.cpp

459

In email, Daniel Berlin discusses this as well.

I measured ~400 cpp source files internally and impact is about ~0.6% (that is end to end starting with C++ source)

[mehdi_amini]

lib/Transforms/Scalar/ADCE.cpp

459

Thanks!

0.6% is not negligible: some LLVM users are starting from bitcode (i.e. they don't pay the frontend cost) so the % could be considerably higher, and have low-latency requirements.

It seems there is a tradeoff where the "existing" "fast" ADCE may still be desirable. Do you remember if this was addressed in a previous email thread? (I kind of remember there was a fairly extensive discussion on your first submissions)

[david2050]

lib/Transforms/Scalar/ADCE.cpp

459

The previous discussion focused on the negative maintenance costs of having two implementations. That said, it clearly could choose to not build the PDT and forego control flow removal at lower optimiation levels. Then we would pay a smaller tax (~ double the number of hash table lookups) for the reduced functionality.

[david2050]

What should we do at this point? Should I add code to restrict use of PDT to -O3 or do that in a later diff?

[mehdi_amini]

LGTM.
Let's postpone and figure later if we need an option to have a "degraded mode". Folks who really need it will have to measure the compile-time cost on their workload.

lib/Transforms/Scalar/ADCE.cpp

 
 #include "llvm/Transforms/Scalar/ADCE.h"
 
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #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/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Pass.h"
 #include "llvm/ProfileData/InstrProf.h"
struct BlockInfoType {
   BasicBlock *BB = nullptr;
 
   /// Cache of BB->getTerminator()
   TerminatorInst *Terminator = nullptr;
 };
 
 class AggressiveDeadCodeElimination {
   Function &F;
+  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;
   bool isLive(Instruction *I) { return InstInfo[I].Live; }
class AggressiveDeadCodeElimination {
   /// marked live.
   void markLiveBranchesFromControlDependences();
 
   /// Remove instructions not marked live, return if any any instruction
   /// was removed.
   bool removeDeadInstructions();
 
 public:
-  AggressiveDeadCodeElimination(Function &F) : F(F) {}
+  AggressiveDeadCodeElimination(Function &F, PostDominatorTree &PDT)
+      : F(F), PDT(PDT) {}
   bool performDeadCodeElimination();
 };
 }
 
 bool AggressiveDeadCodeElimination::performDeadCodeElimination() {
   initialize();
   markLiveInstructions();
   return removeDeadInstructions();
 }
 
 static bool isUnconditionalBranch(TerminatorInst *Term) {
   auto BR = dyn_cast<BranchInst>(Term);
   return BR && BR->isUnconditional();
 }
 
 void AggressiveDeadCodeElimination::initialize() {
 
   auto NumBlocks = F.size();
 
   // We will have an entry in the map for each block so we grow the
   // structure to twice that size to keep the load factor low in the hash table.
   BlockInfo.reserve(NumBlocks);
   size_t NumInsts = 0;
-  
   // Iterate over blocks and initialize BlockInfoVec entries, count
   // instructions to size the InstInfo hash table.
   for (auto &BB : F) {
     NumInsts += BB.size();
     auto &Info = BlockInfo[&BB];
     Info.BB = &BB;
     Info.Terminator = BB.getTerminator();
     Info.UnconditionalBranch = isUnconditionalBranch(Info.Terminator);
for (auto &BB : F) {
 
     for (auto Succ : successors(&BB))
       if (Seen.count(Succ)) {
         // back edge....
         markLive(Term);
         break;
       }
   }
-  // end temporary handling of loops
+  // End temporary handling of loops.
+
+  // Mark blocks live if there is no path from the block to the
+  // return of the function or a successor for which this is true.
+  // This protects IDFCalculator which cannot handle such blocks.
+  for (auto &BBInfoPair : BlockInfo) {
+    auto &BBInfo = BBInfoPair.second;
+    if (BBInfo.terminatorIsLive())
+      continue;
+    auto *BB = BBInfo.BB;
+    if (!PDT.getNode(BB)) {
+      DEBUG(dbgs() << "Not post-dominated by return: " << BB->getName()
+                   << '\n';);
+      markLive(BBInfo.Terminator);
+      continue;
+    }
+    for (auto Succ : successors(BB))
+      if (!PDT.getNode(Succ)) {
+        DEBUG(dbgs() << "Successor not post-dominated by return: "
+                     << BB->getName() << '\n';);
+        markLive(BBInfo.Terminator);
+        break;
+      }
+  }
 
   // Treat the entry block as always live
   auto *BB = &F.getEntryBlock();
   auto &EntryInfo = BlockInfo[BB];
   EntryInfo.Live = true;
   if (EntryInfo.UnconditionalBranch)
     markLive(EntryInfo.Terminator);
 
while (!Worklist.empty()) {
         collectLiveScopes(*DL);
 
       DEBUG(dbgs() << "work live: "; LiveInst->dump(););
       for (Use &OI : LiveInst->operands())
         if (Instruction *Inst = dyn_cast<Instruction>(OI))
           markLive(Inst);
     }
     markLiveBranchesFromControlDependences();
-    // TODO -- handle PhiNodes
+
+    if (Worklist.empty()) {
+      // Temporary until we can actually delete branches.
+      SmallVector<TerminatorInst *, 16> DeadTerminators;
+      for (auto *BB : BlocksWithDeadTerminators)
+        DeadTerminators.push_back(BB->getTerminator());
+      for (auto *I : DeadTerminators)
+        markLive(I);
+      assert(BlocksWithDeadTerminators.empty());
+      // End temporary.
+    }
   } while (!Worklist.empty());
 
-  // temporary until control dependences are implemented
   assert(BlocksWithDeadTerminators.empty());
 }
 
 void AggressiveDeadCodeElimination::markLive(Instruction *I) {
 
   auto &Info = InstInfo[I];
   if (Info.Live)
     return;
void AggressiveDeadCodeElimination::markLive(Instruction *I) {
 
   DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n');
   BBInfo.Live = true;
   NewLiveBlocks.insert(BBInfo.BB);
 
   // Mark unconditional branches at the end of live
   // blocks as live since there is no work to do for them later
   if (BBInfo.UnconditionalBranch && I != BBInfo.Terminator)
-      markLive(BBInfo.Terminator);
 }
 
 void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) {
   if (!AliveScopes.insert(&LS).second)
     return;
 
   if (isa<DISubprogram>(LS))
     return;
void AggressiveDeadCodeElimination::collectLiveScopes(const DILocation &DL) {
 
   // Tail-recurse through the inlined-at chain.
   if (const DILocation *IA = DL.getInlinedAt())
     collectLiveScopes(*IA);
 }
 
 void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
 
-  // This is  a place holder, mark all read operations live
-  // The next patch will replace this with using iterated dominance
-  // frontier to compute branches that need to be live because they
-  // control live blocks with live operations
-  SmallVector<TerminatorInst *, 16> DeadTerminators;
+  if (BlocksWithDeadTerminators.empty())
+    return;
+
+  DEBUG({
+    dbgs() << "new live blocks:\n";
+    for (auto *BB : NewLiveBlocks)
+      dbgs() << "\t" << BB->getName() << '\n';
+    dbgs() << "dead terminator blocks:\n";
     for (auto *BB : BlocksWithDeadTerminators)
-    DeadTerminators.push_back(BB->getTerminator());
-  for (auto I : DeadTerminators)
-    markLive(I);
+      dbgs() << "\t" << BB->getName() << '\n';
+  });
+
+  // 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.
+
+  SmallVector<BasicBlock *, 32> IDFBlocks;
+  ReverseIDFCalculator IDFs(PDT);
+  IDFs.setDefiningBlocks(NewLiveBlocks);
+  IDFs.setLiveInBlocks(BlocksWithDeadTerminators);
+  IDFs.calculate(IDFBlocks);
   NewLiveBlocks.clear();
+
+  // Dead terminators which control live blocks are now marked live.
+  for (auto BB : IDFBlocks) {
+    DEBUG(dbgs() << "live control in: " << BB->getName() << '\n');
+    markLive(BB->getTerminator());
+  }
 }
 
 bool AggressiveDeadCodeElimination::removeDeadInstructions() {
 
   // The inverse of the live set is the dead set.  These are those instructions
   // which have no side effects and do not influence the control flow or return
   // value of the function, and may therefore be deleted safely.
   // NOTE: We reuse the Worklist vector here for memory efficiency.
bool AggressiveDeadCodeElimination::removeDeadInstructions() {
   for (Instruction *&I : Worklist) {
     ++NumRemoved;
     I->eraseFromParent();
   }
 
   return !Worklist.empty();
 }
 
-PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &) {
-  if (!AggressiveDeadCodeElimination(F).performDeadCodeElimination())
+//===----------------------------------------------------------------------===//
+//
+// Pass Manager integration code
+//
+//===----------------------------------------------------------------------===//
+PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) {
+  auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
+  if (!AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination())
     return PreservedAnalyses::all();
 
   // FIXME: This should also 'preserve the CFG'.
   auto PA = PreservedAnalyses();
   PA.preserve<GlobalsAA>();
   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;
-    return AggressiveDeadCodeElimination(F).performDeadCodeElimination();
+    auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
+    return AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination();
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.setPreservesCFG();
+    AU.addRequired<PostDominatorTreeWrapperPass>();
+    AU.setPreservesCFG(); // TODO -- will remove when we start removing branches
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 };
 }
 
 char ADCELegacyPass::ID = 0;
-INITIALIZE_PASS(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
+INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce",
+                      "Aggressive Dead Code Elimination", false, false)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
+INITIALIZE_PASS_END(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
                     false, false)
 
 FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); }