416 lines · cpp
1//===- SimplifyCFG.cpp ----------------------------------------------------===//2//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9//10// This file implements the control flow graph (CFG) simplifications11// presented as part of the 'Getting Started With LLVM: Basics' tutorial at the12// US LLVM Developers Meeting 2019. It also contains additional material.13//14// The current file contains three different CFG simplifications. There are15// multiple versions of each implementation (e.g. _v1 and _v2), which implement16// additional functionality (e.g. preserving analysis like the DominatorTree) or17// use additional utilities to simplify the code (e.g. LLVM's PatternMatch.h).18// The available simplifications are:19// 1. Trivially Dead block Removal (removeDeadBlocks_v[1,2]).20// This simplifications removes all blocks without predecessors in the CFG21// from a function.22// 2. Conditional Branch Elimination (eliminateCondBranches_v[1,2,3])23// This simplification replaces conditional branches with constant integer24// conditions with unconditional branches.25// 3. Single Predecessor Block Merging (mergeIntoSinglePredecessor_v[1,2])26// This simplification merges blocks with a single predecessor into the27// predecessor, if that block has a single successor.28//29// TODOs30// * Preserve LoopInfo.31// * Add fixed point iteration to delete all dead blocks32// * Add implementation using reachability to discover dead blocks.33//===----------------------------------------------------------------------===//34 35#include "llvm/Analysis/DomTreeUpdater.h"36#include "llvm/IR/Dominators.h"37#include "llvm/IR/Function.h"38#include "llvm/IR/PassManager.h"39#include "llvm/IR/PatternMatch.h"40#include "llvm/Passes/PassBuilder.h"41#include "llvm/Passes/PassPlugin.h"42#include "llvm/Support/CommandLine.h"43 44using namespace llvm;45using namespace PatternMatch;46 47enum TutorialVersion { V1, V2, V3 };48static cl::opt<TutorialVersion>49 Version("tut-simplifycfg-version", cl::desc("Select tutorial version"),50 cl::Hidden, cl::ValueOptional, cl::init(V1),51 cl::values(clEnumValN(V1, "v1", "version 1"),52 clEnumValN(V2, "v2", "version 2"),53 clEnumValN(V3, "v3", "version 3"),54 // Sentinel value for unspecified option.55 clEnumValN(V3, "", "")));56 57#define DEBUG_TYPE "tut-simplifycfg"58 59// Remove trivially dead blocks. First version, not preserving the60// DominatorTree.61static bool removeDeadBlocks_v1(Function &F) {62 bool Changed = false;63 64 // Remove trivially dead blocks.65 for (BasicBlock &BB : make_early_inc_range(F)) {66 // Skip blocks we know to not be trivially dead. We know a block is67 // guaranteed to be dead, iff it is neither the entry block nor68 // has any predecessors.69 if (&F.getEntryBlock() == &BB || !pred_empty(&BB))70 continue;71 72 // Notify successors of BB that BB is going to be removed. This removes73 // incoming values from BB from PHIs in the successors. Note that this will74 // not actually remove BB from the predecessor lists of its successors.75 for (BasicBlock *Succ : successors(&BB))76 Succ->removePredecessor(&BB);77 // TODO: Find a better place to put such small variations.78 // Alternatively, we can update the PHI nodes manually:79 // for (PHINode &PN : make_early_inc_range(Succ->phis()))80 // PN.removeIncomingValue(&BB);81 82 // Replace all instructions in BB with a poison constant. The block is83 // unreachable, so the results of the instructions should never get used.84 while (!BB.empty()) {85 Instruction &I = BB.back();86 I.replaceAllUsesWith(PoisonValue::get(I.getType()));87 I.eraseFromParent();88 }89 90 // Finally remove the basic block.91 BB.eraseFromParent();92 Changed = true;93 }94 95 return Changed;96}97 98// Remove trivially dead blocks. This is the second version and preserves the99// dominator tree.100static bool removeDeadBlocks_v2(Function &F, DominatorTree &DT) {101 bool Changed = false;102 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);103 SmallVector<DominatorTree::UpdateType, 8> DTUpdates;104 105 // Remove trivially dead blocks.106 for (BasicBlock &BB : make_early_inc_range(F)) {107 // Skip blocks we know to not be trivially dead. We know a block is108 // guaranteed to be dead, iff it is neither the entry block nor109 // has any predecessors.110 if (&F.getEntryBlock() == &BB || !pred_empty(&BB))111 continue;112 113 // Notify successors of BB that BB is going to be removed. This removes114 // incoming values from BB from PHIs in the successors. Note that this will115 // not actually remove BB from the predecessor lists of its successors.116 for (BasicBlock *Succ : successors(&BB)) {117 Succ->removePredecessor(&BB);118 119 // Collect updates that need to be applied to the dominator tree.120 DTUpdates.push_back({DominatorTree::Delete, &BB, Succ});121 }122 123 // Remove BB via the DomTreeUpdater. DomTreeUpdater::deleteBB conveniently124 // removes the instructions in BB as well.125 DTU.deleteBB(&BB);126 Changed = true;127 }128 129 // Apply updates permissively, to remove duplicates.130 DTU.applyUpdatesPermissive(DTUpdates);131 132 return Changed;133}134 135// Eliminate branches with constant conditionals. This is the first version,136// which *does not* preserve the dominator tree.137static bool eliminateCondBranches_v1(Function &F) {138 bool Changed = false;139 140 // Eliminate branches with constant conditionals.141 for (BasicBlock &BB : F) {142 // Skip blocks without conditional branches as terminators.143 BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator());144 if (!BI || !BI->isConditional())145 continue;146 147 // Skip blocks with conditional branches without ConstantInt conditions.148 ConstantInt *CI = dyn_cast<ConstantInt>(BI->getCondition());149 if (!CI)150 continue;151 152 // We use the branch condition (CI), to select the successor we remove:153 // if CI == 1 (true), we remove the second successor, otherwise the first.154 BasicBlock *RemovedSucc = BI->getSuccessor(CI->isOne());155 // Tell RemovedSucc we will remove BB from its predecessors.156 RemovedSucc->removePredecessor(&BB);157 158 // Replace the conditional branch with an unconditional one, by creating159 // a new unconditional branch to the selected successor and removing the160 // conditional one.161 BranchInst::Create(BI->getSuccessor(CI->isZero()), BI->getIterator());162 BI->eraseFromParent();163 Changed = true;164 }165 166 return Changed;167}168 169// Eliminate branches with constant conditionals. This is the second170// version, which *does* preserve the dominator tree.171static bool eliminateCondBranches_v2(Function &F, DominatorTree &DT) {172 bool Changed = false;173 174 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);175 SmallVector<DominatorTree::UpdateType, 8> DTUpdates;176 // Eliminate branches with constant conditionals.177 for (BasicBlock &BB : F) {178 // Skip blocks without conditional branches as terminators.179 BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator());180 if (!BI || !BI->isConditional())181 continue;182 183 // Skip blocks with conditional branches without ConstantInt conditions.184 ConstantInt *CI = dyn_cast<ConstantInt>(BI->getCondition());185 if (!CI)186 continue;187 188 // We use the branch condition (CI), to select the successor we remove:189 // if CI == 1 (true), we remove the second successor, otherwise the first.190 BasicBlock *RemovedSucc = BI->getSuccessor(CI->isOne());191 // Tell RemovedSucc we will remove BB from its predecessors.192 RemovedSucc->removePredecessor(&BB);193 194 // Replace the conditional branch with an unconditional one, by creating195 // a new unconditional branch to the selected successor and removing the196 // conditional one.197 BranchInst *NewBranch =198 BranchInst::Create(BI->getSuccessor(CI->isZero()), BI->getIterator());199 BI->eraseFromParent();200 201 // Delete the edge between BB and RemovedSucc in the DominatorTree, iff202 // the conditional branch did not use RemovedSucc as both the true and false203 // branches.204 if (NewBranch->getSuccessor(0) != RemovedSucc)205 DTUpdates.push_back({DominatorTree::Delete, &BB, RemovedSucc});206 Changed = true;207 }208 209 // Apply updates permissively, to remove duplicates.210 DTU.applyUpdatesPermissive(DTUpdates);211 212 return Changed;213}214 215// Eliminate branches with constant conditionals. This is the third216// version, which uses PatternMatch.h.217static bool eliminateCondBranches_v3(Function &F, DominatorTree &DT) {218 bool Changed = false;219 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);220 SmallVector<DominatorTree::UpdateType, 8> DTUpdates;221 222 // Eliminate branches with constant conditionals.223 for (BasicBlock &BB : F) {224 ConstantInt *CI = nullptr;225 BasicBlock *TakenSucc, *RemovedSucc;226 // Check if the terminator is a conditional branch, with constant integer227 // condition and also capture the successor blocks as TakenSucc and228 // RemovedSucc.229 if (!match(BB.getTerminator(),230 m_Br(m_ConstantInt(CI), m_BasicBlock(TakenSucc),231 m_BasicBlock(RemovedSucc))))232 continue;233 234 // If the condition is false, swap TakenSucc and RemovedSucc.235 if (CI->isZero())236 std::swap(TakenSucc, RemovedSucc);237 238 // Tell RemovedSucc we will remove BB from its predecessors.239 RemovedSucc->removePredecessor(&BB);240 241 // Replace the conditional branch with an unconditional one, by creating242 // a new unconditional branch to the selected successor and removing the243 // conditional one.244 245 BranchInst *NewBranch =246 BranchInst::Create(TakenSucc, BB.getTerminator()->getIterator());247 BB.getTerminator()->eraseFromParent();248 249 // Delete the edge between BB and RemovedSucc in the DominatorTree, iff250 // the conditional branch did not use RemovedSucc as both the true and false251 // branches.252 if (NewBranch->getSuccessor(0) != RemovedSucc)253 DTUpdates.push_back({DominatorTree::Delete, &BB, RemovedSucc});254 Changed = true;255 }256 257 // Apply updates permissively, to remove duplicates.258 DTU.applyUpdatesPermissive(DTUpdates);259 return Changed;260}261 262// Merge basic blocks into their single predecessor, if their predecessor has a263// single successor. This is the first version and does not preserve the264// DominatorTree.265static bool mergeIntoSinglePredecessor_v1(Function &F) {266 bool Changed = false;267 268 // Merge blocks with single predecessors.269 for (BasicBlock &BB : make_early_inc_range(F)) {270 BasicBlock *Pred = BB.getSinglePredecessor();271 // Make sure BB has a single predecessor Pred and BB is the single272 // successor of Pred.273 if (!Pred || Pred->getSingleSuccessor() != &BB)274 continue;275 276 // Do not try to merge self loops. That can happen in dead blocks.277 if (Pred == &BB)278 continue;279 280 // Need to replace it before nuking the branch.281 BB.replaceAllUsesWith(Pred);282 // PHI nodes in BB can only have a single incoming value. Remove them.283 for (PHINode &PN : make_early_inc_range(BB.phis())) {284 PN.replaceAllUsesWith(PN.getIncomingValue(0));285 PN.eraseFromParent();286 }287 // Move all instructions from BB to Pred.288 for (Instruction &I : make_early_inc_range(BB))289 I.moveBefore(Pred->getTerminator()->getIterator());290 291 // Remove the Pred's terminator (which jumped to BB). BB's terminator292 // will become Pred's terminator.293 Pred->getTerminator()->eraseFromParent();294 BB.eraseFromParent();295 296 Changed = true;297 }298 299 return Changed;300}301 302// Merge basic blocks into their single predecessor, if their predecessor has a303// single successor. This is the second version and does preserve the304// DominatorTree.305static bool mergeIntoSinglePredecessor_v2(Function &F, DominatorTree &DT) {306 bool Changed = false;307 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);308 SmallVector<DominatorTree::UpdateType, 8> DTUpdates;309 310 // Merge blocks with single predecessors.311 for (BasicBlock &BB : make_early_inc_range(F)) {312 BasicBlock *Pred = BB.getSinglePredecessor();313 // Make sure BB has a single predecessor Pred and BB is the single314 // successor of Pred.315 if (!Pred || Pred->getSingleSuccessor() != &BB)316 continue;317 318 // Do not try to merge self loops. That can happen in dead blocks.319 if (Pred == &BB)320 continue;321 322 // Tell DTU about the changes to the CFG: All edges from BB to its323 // successors get removed and we add edges between Pred and BB's successors.324 for (BasicBlock *Succ : successors(&BB)) {325 DTUpdates.push_back({DominatorTree::Delete, &BB, Succ});326 DTUpdates.push_back({DominatorTree::Insert, Pred, Succ});327 }328 // Also remove the edge between Pred and BB.329 DTUpdates.push_back({DominatorTree::Delete, Pred, &BB});330 331 // Need to replace it before nuking the branch.332 BB.replaceAllUsesWith(Pred);333 // PHI nodes in BB can only have a single incoming value. Remove them.334 for (PHINode &PN : make_early_inc_range(BB.phis())) {335 PN.replaceAllUsesWith(PN.getIncomingValue(0));336 PN.eraseFromParent();337 }338 // Move all instructions from BB to Pred.339 for (Instruction &I : make_early_inc_range(BB))340 I.moveBefore(Pred->getTerminator()->getIterator());341 342 // Remove the Pred's terminator (which jumped to BB). BB's terminator343 // will become Pred's terminator.344 Pred->getTerminator()->eraseFromParent();345 DTU.deleteBB(&BB);346 347 Changed = true;348 }349 350 // Apply updates permissively, to remove duplicates.351 DTU.applyUpdatesPermissive(DTUpdates);352 return Changed;353}354 355static bool doSimplify_v1(Function &F) {356 return (int)eliminateCondBranches_v1(F) | mergeIntoSinglePredecessor_v1(F) |357 removeDeadBlocks_v1(F);358}359 360static bool doSimplify_v2(Function &F, DominatorTree &DT) {361 return (int)eliminateCondBranches_v2(F, DT) |362 mergeIntoSinglePredecessor_v2(F, DT) | removeDeadBlocks_v2(F, DT);363}364 365static bool doSimplify_v3(Function &F, DominatorTree &DT) {366 return (int)eliminateCondBranches_v3(F, DT) |367 mergeIntoSinglePredecessor_v2(F, DT) | removeDeadBlocks_v2(F, DT);368}369 370namespace {371struct SimplifyCFGPass : public PassInfoMixin<SimplifyCFGPass> {372 PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM) {373 switch (Version) {374 case V1:375 doSimplify_v1(F);376 break;377 case V2: {378 DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);379 doSimplify_v2(F, DT);380 break;381 }382 case V3: {383 DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);384 doSimplify_v3(F, DT);385 break;386 }387 }388 389 return PreservedAnalyses::none();390 }391};392} // namespace393 394/* New PM Registration */395llvm::PassPluginLibraryInfo getExampleIRTransformsPluginInfo() {396 return {LLVM_PLUGIN_API_VERSION, "SimplifyCFG", LLVM_VERSION_STRING,397 [](PassBuilder &PB) {398 PB.registerPipelineParsingCallback(399 [](StringRef Name, llvm::FunctionPassManager &PM,400 ArrayRef<llvm::PassBuilder::PipelineElement>) {401 if (Name == "tut-simplifycfg") {402 PM.addPass(SimplifyCFGPass());403 return true;404 }405 return false;406 });407 }};408}409 410#ifndef LLVM_EXAMPLEIRTRANSFORMS_LINK_INTO_TOOLS411extern "C" LLVM_ATTRIBUTE_WEAK ::llvm::PassPluginLibraryInfo412llvmGetPassPluginInfo() {413 return getExampleIRTransformsPluginInfo();414}415#endif416