text: //===- SimplifyCFG.cpp ----------------------------------------------------===//
  //
  //
  // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  // See https://llvm.org/LICENSE.txt for license information.
  // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  //
  //===----------------------------------------------------------------------===//
  //
  // This file implements the control flow graph (CFG) simplifications
  // presented as part of the 'Getting Started With LLVM: Basics' tutorial at the
  // US LLVM Developers Meeting 2019. It also contains additional material.
  //
  // The current file contains three different CFG simplifications. There are
  // multiple versions of each implementation (e.g. _v1 and _v2), which implement
  // additional functionality (e.g. preserving analysis like the DominatorTree) or
  // use additional utilities to simplify the code (e.g. LLVM's PatternMatch.h).
  // The available simplifications are:
  //  1. Trivially Dead block Removal (removeDeadBlocks_v[1,2]).
  //     This simplifications removes all blocks without predecessors in the CFG
  //     from a function.
  //  2. Conditional Branch Elimination (eliminateCondBranches_v[1,2,3])
  //     This simplification replaces conditional branches with constant integer
  //     conditions with unconditional branches.
  //  3. Single Predecessor Block Merging (mergeIntoSinglePredecessor_v[1,2])
  //     This simplification merges blocks with a single predecessor into the
  //     predecessor, if that block has a single successor.
  //
  // TODOs
  //  * Hook up pass to the new pass manager.
  //  * Preserve LoopInfo.
  //  * Add fixed point iteration to delete all dead blocks
  //  * Add implementation using reachability to discover dead blocks.
  //===----------------------------------------------------------------------===//
  
  #include "SimplifyCFG.h"
  #include "InitializePasses.h"
  #include "llvm/Analysis/DomTreeUpdater.h"
  #include "llvm/IR/Dominators.h"
  #include "llvm/IR/Function.h"
  #include "llvm/IR/PassManager.h"
  #include "llvm/IR/PatternMatch.h"
  #include "llvm/InitializePasses.h"
  #include "llvm/Support/CommandLine.h"
  
  using namespace llvm;
  using namespace PatternMatch;
  
  enum TutorialVersion { V1, V2, V3 };
  static cl::opt<TutorialVersion>
      Version("tut-simplifycfg-version", cl::desc("Select tutorial version"),
              cl::Hidden, cl::ValueOptional, cl::init(V1),
              cl::values(clEnumValN(V1, "v1", "version 1"),
                         clEnumValN(V2, "v2", "version 2"),
                         clEnumValN(V3, "v3", "version 3"),
                         // Sentinel value for unspecified option.
                         clEnumValN(V3, "", "")));
  
  #define DEBUG_TYPE "tut-simplifycfg"
  
  // Remove trivially dead blocks. First version, not preserving the
  // DominatorTree.
  static bool removeDeadBlocks_v1(Function &F) {
    bool Changed = false;
  
    // Remove trivially dead blocks.
    for (BasicBlock &BB : make_early_inc_range(F)) {
      // Skip blocks we know to not be trivially dead. We know a block is
      // guaranteed to be dead, iff it is neither the entry block nor
      // has any predecessors.
      if (&F.getEntryBlock() == &BB || !pred_empty(&BB))
        continue;
  
      // Notify successors of BB that BB is going to be removed. This removes
      // incoming values from BB from PHIs in the successors. Note that this will
      // not actually remove BB from the predecessor lists of its successors.
      for (BasicBlock *Succ : successors(&BB))
        Succ->removePredecessor(&BB);
      // TODO: Find a better place to put such small variations.
      // Alternatively, we can update the PHI nodes manually:
      // for (PHINode &PN : make_early_inc_range(Succ->phis()))
      //  PN.removeIncomingValue(&BB);
  
      // Replace all instructions in BB with an undef constant. The block is
      // unreachable, so the results of the instructions should never get used.
      while (!BB.empty()) {
        Instruction &I = BB.back();
        I.replaceAllUsesWith(UndefValue::get(I.getType()));
        I.eraseFromParent();
      }
  
      // Finally remove the basic block.
      BB.eraseFromParent();
      Changed = true;
    }
  
    return Changed;
  }
  
  // Remove trivially dead blocks. This is the second version and preserves the
  // dominator tree.
  static bool removeDeadBlocks_v2(Function &F, DominatorTree &DT) {
    bool Changed = false;
    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
    SmallVector<DominatorTree::UpdateType, 8> DTUpdates;
  
    // Remove trivially dead blocks.
    for (BasicBlock &BB : make_early_inc_range(F)) {
      // Skip blocks we know to not be trivially dead. We know a block is
      // guaranteed to be dead, iff it is neither the entry block nor
      // has any predecessors.
      if (&F.getEntryBlock() == &BB || !pred_empty(&BB))
        continue;
  
      // Notify successors of BB that BB is going to be removed. This removes
      // incoming values from BB from PHIs in the successors. Note that this will
      // not actually remove BB from the predecessor lists of its successors.
      for (BasicBlock *Succ : successors(&BB)) {
        Succ->removePredecessor(&BB);
  
        // Collect updates that need to be applied to the dominator tree.
        DTUpdates.push_back({DominatorTree::Delete, &BB, Succ});
      }
  
      // Remove BB via the DomTreeUpdater. DomTreeUpdater::deleteBB conveniently
      // removes the instructions in BB as well.
      DTU.deleteBB(&BB);
      Changed = true;
    }
  
    // Apply updates permissively, to remove duplicates.
    DTU.applyUpdatesPermissive(DTUpdates);
  
    return Changed;
  }
  
  // Eliminate branches with constant conditionals. This is the first version,
  // which *does not* preserve the dominator tree.
  static bool eliminateCondBranches_v1(Function &F) {
    bool Changed = false;
  
    // Eliminate branches with constant conditionals.
    for (BasicBlock &BB : F) {
      // Skip blocks without conditional branches as terminators.
      BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator());
      if (!BI || !BI->isConditional())
        continue;
  
      // Skip blocks with conditional branches without ConstantInt conditions.
      ConstantInt *CI = dyn_cast<ConstantInt>(BI->getCondition());
      if (!CI)
        continue;
  
      // We use the branch condition (CI), to select the successor we remove:
      // if CI == 1 (true), we remove the second successor, otherwise the first.
      BasicBlock *RemovedSucc = BI->getSuccessor(CI->isOne());
      // Tell RemovedSucc we will remove BB from its predecessors.
      RemovedSucc->removePredecessor(&BB);
  
      // Replace the conditional branch with an unconditional one, by creating
      // a new unconditional branch to the selected successor and removing the
      // conditional one.
      BranchInst::Create(BI->getSuccessor(CI->isZero()), BI);
      BI->eraseFromParent();
      Changed = true;
    }
  
    return Changed;
  }
  
  // Eliminate branches with constant conditionals. This is the second
  // version, which *does* preserve the dominator tree.
  static bool eliminateCondBranches_v2(Function &F, DominatorTree &DT) {
    bool Changed = false;
  
    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
    SmallVector<DominatorTree::UpdateType, 8> DTUpdates;
    // Eliminate branches with constant conditionals.
    for (BasicBlock &BB : F) {
      // Skip blocks without conditional branches as terminators.
      BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator());
      if (!BI || !BI->isConditional())
        continue;
  
      // Skip blocks with conditional branches without ConstantInt conditions.
      ConstantInt *CI = dyn_cast<ConstantInt>(BI->getCondition());
      if (!CI)
        continue;
  
      // We use the branch condition (CI), to select the successor we remove:
      // if CI == 1 (true), we remove the second successor, otherwise the first.
      BasicBlock *RemovedSucc = BI->getSuccessor(CI->isOne());
      // Tell RemovedSucc we will remove BB from its predecessors.
      RemovedSucc->removePredecessor(&BB);
  
      // Replace the conditional branch with an unconditional one, by creating
      // a new unconditional branch to the selected successor and removing the
      // conditional one.
      BranchInst *NewBranch =
          BranchInst::Create(BI->getSuccessor(CI->isZero()), BI);
      BI->eraseFromParent();
  
      // Delete the edge between BB and RemovedSucc in the DominatorTree, iff
      // the conditional branch did not use RemovedSucc as both the true and false
      // branches.
      if (NewBranch->getSuccessor(0) != RemovedSucc)
        DTUpdates.push_back({DominatorTree::Delete, &BB, RemovedSucc});
      Changed = true;
    }
  
    // Apply updates permissively, to remove duplicates.
    DTU.applyUpdatesPermissive(DTUpdates);
  
    return Changed;
  }
  
  // Eliminate branches with constant conditionals. This is the third
  // version, which uses PatternMatch.h.
  static bool eliminateCondBranches_v3(Function &F, DominatorTree &DT) {
    bool Changed = false;
    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
    SmallVector<DominatorTree::UpdateType, 8> DTUpdates;
  
    // Eliminate branches with constant conditionals.
    for (BasicBlock &BB : F) {
      ConstantInt *CI = nullptr;
      BasicBlock *TakenSucc, *RemovedSucc;
      // Check if the terminator is a conditional branch, with constant integer
      // condition and also capture the successor blocks as TakenSucc and
      // RemovedSucc.
      if (!match(BB.getTerminator(),
                 m_Br(m_ConstantInt(CI), m_BasicBlock(TakenSucc),
                      m_BasicBlock(RemovedSucc))))
        continue;
  
      // If the condition is false, swap TakenSucc and RemovedSucc.
      if (CI->isZero())
        std::swap(TakenSucc, RemovedSucc);
  
      // Tell RemovedSucc we will remove BB from its predecessors.
      RemovedSucc->removePredecessor(&BB);
  
      // Replace the conditional branch with an unconditional one, by creating
      // a new unconditional branch to the selected successor and removing the
      // conditional one.
  
      BranchInst *NewBranch = BranchInst::Create(TakenSucc, BB.getTerminator());
      BB.getTerminator()->eraseFromParent();
  
      // Delete the edge between BB and RemovedSucc in the DominatorTree, iff
      // the conditional branch did not use RemovedSucc as both the true and false
      // branches.
      if (NewBranch->getSuccessor(0) != RemovedSucc)
        DTUpdates.push_back({DominatorTree::Delete, &BB, RemovedSucc});
      Changed = true;
    }
  
    // Apply updates permissively, to remove duplicates.
    DTU.applyUpdatesPermissive(DTUpdates);
    return Changed;
  }
  
  // Merge basic blocks into their single predecessor, if their predecessor has a
  // single successor. This is the first version and does not preserve the
  // DominatorTree.
  static bool mergeIntoSinglePredecessor_v1(Function &F) {
    bool Changed = false;
  
    // Merge blocks with single predecessors.
    for (BasicBlock &BB : make_early_inc_range(F)) {
      BasicBlock *Pred = BB.getSinglePredecessor();
      // Make sure  BB has a single predecessor Pred and BB is the single
      // successor of Pred.
      if (!Pred || Pred->getSingleSuccessor() != &BB)
        continue;
  
      // Do not try to merge self loops. That can happen in dead blocks.
      if (Pred == &BB)
        continue;
  
      // Need to replace it before nuking the branch.
      BB.replaceAllUsesWith(Pred);
      // PHI nodes in BB can only have a single incoming value. Remove them.
      for (PHINode &PN : make_early_inc_range(BB.phis())) {
        PN.replaceAllUsesWith(PN.getIncomingValue(0));
        PN.eraseFromParent();
      }
      // Move all instructions from BB to Pred.
      for (Instruction &I : make_early_inc_range(BB))
        I.moveBefore(Pred->getTerminator());
  
      // Remove the Pred's terminator (which jumped to BB). BB's terminator
      // will become Pred's terminator.
      Pred->getTerminator()->eraseFromParent();
      BB.eraseFromParent();
  
      Changed = true;
    }
  
    return Changed;
  }
  
  // Merge basic blocks into their single predecessor, if their predecessor has a
  // single successor. This is the second version and does preserve the
  // DominatorTree.
  static bool mergeIntoSinglePredecessor_v2(Function &F, DominatorTree &DT) {
    bool Changed = false;
    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
    SmallVector<DominatorTree::UpdateType, 8> DTUpdates;
  
    // Merge blocks with single predecessors.
    for (BasicBlock &BB : make_early_inc_range(F)) {
      BasicBlock *Pred = BB.getSinglePredecessor();
      // Make sure  BB has a single predecessor Pred and BB is the single
      // successor of Pred.
      if (!Pred || Pred->getSingleSuccessor() != &BB)
        continue;
  
      // Do not try to merge self loops. That can happen in dead blocks.
      if (Pred == &BB)
        continue;
  
      // Tell DTU about the changes to the CFG: All edges from BB to its
      // successors get removed and we add edges between Pred and BB's successors.
      for (BasicBlock *Succ : successors(&BB)) {
        DTUpdates.push_back({DominatorTree::Delete, &BB, Succ});
        DTUpdates.push_back({DominatorTree::Insert, Pred, Succ});
      }
      // Also remove the edge between Pred and BB.
      DTUpdates.push_back({DominatorTree::Delete, Pred, &BB});
  
      // Need to replace it before nuking the branch.
      BB.replaceAllUsesWith(Pred);
      // PHI nodes in BB can only have a single incoming value. Remove them.
      for (PHINode &PN : make_early_inc_range(BB.phis())) {
        PN.replaceAllUsesWith(PN.getIncomingValue(0));
        PN.eraseFromParent();
      }
      // Move all instructions from BB to Pred.
      for (Instruction &I : make_early_inc_range(BB))
        I.moveBefore(Pred->getTerminator());
  
      // Remove the Pred's terminator (which jumped to BB). BB's terminator
      // will become Pred's terminator.
      Pred->getTerminator()->eraseFromParent();
      DTU.deleteBB(&BB);
  
      Changed = true;
    }
  
    // Apply updates permissively, to remove duplicates.
    DTU.applyUpdatesPermissive(DTUpdates);
    return Changed;
  }
  
  static bool doSimplify_v1(Function &F) {
    return eliminateCondBranches_v1(F) | mergeIntoSinglePredecessor_v1(F) |
           removeDeadBlocks_v1(F);
  }
  
  static bool doSimplify_v2(Function &F, DominatorTree &DT) {
    return eliminateCondBranches_v2(F, DT) |
           mergeIntoSinglePredecessor_v2(F, DT) | removeDeadBlocks_v2(F, DT);
  }
  
  static bool doSimplify_v3(Function &F, DominatorTree &DT) {
    return eliminateCondBranches_v3(F, DT) |
           mergeIntoSinglePredecessor_v2(F, DT) | removeDeadBlocks_v2(F, DT);
  }
  
  namespace {
  struct SimplifyCFGLegacyPass : public FunctionPass {
    static char ID;
    SimplifyCFGLegacyPass() : FunctionPass(ID) {
      initializeSimplifyCFGLegacyPassPass(*PassRegistry::getPassRegistry());
    }
  
    void getAnalysisUsage(AnalysisUsage &AU) const override {
      AU.addRequired<DominatorTreeWrapperPass>();
      // Version 1 of the implementation does not preserve the dominator tree.
      if (Version != V1)
        AU.addPreserved<DominatorTreeWrapperPass>();
  
      FunctionPass::getAnalysisUsage(AU);
    }
  
    bool runOnFunction(Function &F) override {
      if (skipFunction(F))
        return false;
  
      switch (Version) {
      case V1:
        return doSimplify_v1(F);
      case V2: {
        auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
        return doSimplify_v2(F, DT);
      }
      case V3: {
        auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
        return doSimplify_v3(F, DT);
      }
      }
  
      llvm_unreachable("Unsupported version");
    }
  };
  } // namespace
  
  char SimplifyCFGLegacyPass::ID = 0;
  INITIALIZE_PASS_BEGIN(SimplifyCFGLegacyPass, DEBUG_TYPE,
                        "Tutorial CFG simplification", false, false)
  INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
  INITIALIZE_PASS_END(SimplifyCFGLegacyPass, DEBUG_TYPE,
                      "Tutorial CFG simplifications", false, false)
  