diff options
Diffstat (limited to 'llvm/examples/IRTransforms/SimplifyCFG.cpp')
| -rw-r--r-- | llvm/examples/IRTransforms/SimplifyCFG.cpp | 413 |
1 files changed, 413 insertions, 0 deletions
diff --git a/llvm/examples/IRTransforms/SimplifyCFG.cpp b/llvm/examples/IRTransforms/SimplifyCFG.cpp new file mode 100644 index 00000000000..44bbedf4dc4 --- /dev/null +++ b/llvm/examples/IRTransforms/SimplifyCFG.cpp @@ -0,0 +1,413 @@ +//===- 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/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) |
