226 lines · cpp
1//===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This pass is an extremely simple version of the SimplifyCFG pass. Its sole10// job is to delete LLVM basic blocks that are not reachable from the entry11// node. To do this, it performs a simple depth first traversal of the CFG,12// then deletes any unvisited nodes.13//14// Note that this pass is really a hack. In particular, the instruction15// selectors for various targets should just not generate code for unreachable16// blocks. Until LLVM has a more systematic way of defining instruction17// selectors, however, we cannot really expect them to handle additional18// complexity.19//20//===----------------------------------------------------------------------===//21 22#include "llvm/CodeGen/UnreachableBlockElim.h"23#include "llvm/ADT/DepthFirstIterator.h"24#include "llvm/ADT/SmallPtrSet.h"25#include "llvm/CodeGen/MachineBasicBlock.h"26#include "llvm/CodeGen/MachineDominators.h"27#include "llvm/CodeGen/MachineFunctionPass.h"28#include "llvm/CodeGen/MachineInstrBuilder.h"29#include "llvm/CodeGen/MachineLoopInfo.h"30#include "llvm/CodeGen/MachineRegisterInfo.h"31#include "llvm/CodeGen/Passes.h"32#include "llvm/CodeGen/TargetInstrInfo.h"33#include "llvm/IR/Dominators.h"34#include "llvm/InitializePasses.h"35#include "llvm/Pass.h"36#include "llvm/Transforms/Utils/BasicBlockUtils.h"37using namespace llvm;38 39namespace {40class UnreachableBlockElimLegacyPass : public FunctionPass {41 bool runOnFunction(Function &F) override {42 return llvm::EliminateUnreachableBlocks(F);43 }44 45public:46 static char ID; // Pass identification, replacement for typeid47 UnreachableBlockElimLegacyPass() : FunctionPass(ID) {48 initializeUnreachableBlockElimLegacyPassPass(49 *PassRegistry::getPassRegistry());50 }51 52 void getAnalysisUsage(AnalysisUsage &AU) const override {53 AU.addPreserved<DominatorTreeWrapperPass>();54 }55};56}57char UnreachableBlockElimLegacyPass::ID = 0;58INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim",59 "Remove unreachable blocks from the CFG", false, false)60 61FunctionPass *llvm::createUnreachableBlockEliminationPass() {62 return new UnreachableBlockElimLegacyPass();63}64 65PreservedAnalyses UnreachableBlockElimPass::run(Function &F,66 FunctionAnalysisManager &AM) {67 bool Changed = llvm::EliminateUnreachableBlocks(F);68 if (!Changed)69 return PreservedAnalyses::all();70 PreservedAnalyses PA;71 PA.preserve<DominatorTreeAnalysis>();72 return PA;73}74 75namespace {76class UnreachableMachineBlockElim {77 MachineDominatorTree *MDT;78 MachineLoopInfo *MLI;79 80public:81 UnreachableMachineBlockElim(MachineDominatorTree *MDT, MachineLoopInfo *MLI)82 : MDT(MDT), MLI(MLI) {}83 bool run(MachineFunction &MF);84};85 86class UnreachableMachineBlockElimLegacy : public MachineFunctionPass {87 bool runOnMachineFunction(MachineFunction &F) override;88 void getAnalysisUsage(AnalysisUsage &AU) const override;89 90public:91 static char ID; // Pass identification, replacement for typeid92 UnreachableMachineBlockElimLegacy() : MachineFunctionPass(ID) {}93};94} // namespace95 96char UnreachableMachineBlockElimLegacy::ID = 0;97 98INITIALIZE_PASS(UnreachableMachineBlockElimLegacy,99 "unreachable-mbb-elimination",100 "Remove unreachable machine basic blocks", false, false)101 102char &llvm::UnreachableMachineBlockElimID =103 UnreachableMachineBlockElimLegacy::ID;104 105void UnreachableMachineBlockElimLegacy::getAnalysisUsage(106 AnalysisUsage &AU) const {107 AU.addPreserved<MachineLoopInfoWrapperPass>();108 AU.addPreserved<MachineDominatorTreeWrapperPass>();109 MachineFunctionPass::getAnalysisUsage(AU);110}111 112PreservedAnalyses113UnreachableMachineBlockElimPass::run(MachineFunction &MF,114 MachineFunctionAnalysisManager &AM) {115 auto *MDT = AM.getCachedResult<MachineDominatorTreeAnalysis>(MF);116 auto *MLI = AM.getCachedResult<MachineLoopAnalysis>(MF);117 118 if (!UnreachableMachineBlockElim(MDT, MLI).run(MF))119 return PreservedAnalyses::all();120 121 return getMachineFunctionPassPreservedAnalyses()122 .preserve<MachineLoopAnalysis>()123 .preserve<MachineDominatorTreeAnalysis>();124}125 126bool UnreachableMachineBlockElimLegacy::runOnMachineFunction(127 MachineFunction &MF) {128 MachineDominatorTreeWrapperPass *MDTWrapper =129 getAnalysisIfAvailable<MachineDominatorTreeWrapperPass>();130 MachineDominatorTree *MDT = MDTWrapper ? &MDTWrapper->getDomTree() : nullptr;131 MachineLoopInfoWrapperPass *MLIWrapper =132 getAnalysisIfAvailable<MachineLoopInfoWrapperPass>();133 MachineLoopInfo *MLI = MLIWrapper ? &MLIWrapper->getLI() : nullptr;134 135 return UnreachableMachineBlockElim(MDT, MLI).run(MF);136}137 138bool UnreachableMachineBlockElim::run(MachineFunction &F) {139 df_iterator_default_set<MachineBasicBlock *> Reachable;140 bool ModifiedPHI = false;141 142 // Mark all reachable blocks.143 for (MachineBasicBlock *BB : depth_first_ext(&F, Reachable))144 (void)BB/* Mark all reachable blocks */;145 146 // Loop over all dead blocks, remembering them and deleting all instructions147 // in them.148 std::vector<MachineBasicBlock*> DeadBlocks;149 for (MachineBasicBlock &BB : F) {150 // Test for deadness.151 if (!Reachable.count(&BB)) {152 DeadBlocks.push_back(&BB);153 154 // Update dominator and loop info.155 if (MLI) MLI->removeBlock(&BB);156 if (MDT && MDT->getNode(&BB)) MDT->eraseNode(&BB);157 158 while (!BB.succ_empty()) {159 (*BB.succ_begin())->removePHIsIncomingValuesForPredecessor(BB);160 BB.removeSuccessor(BB.succ_begin());161 }162 }163 }164 165 // Actually remove the blocks now.166 for (MachineBasicBlock *BB : DeadBlocks) {167 // Remove any call information for calls in the block.168 for (auto &I : BB->instrs())169 if (I.shouldUpdateAdditionalCallInfo())170 BB->getParent()->eraseAdditionalCallInfo(&I);171 172 BB->eraseFromParent();173 }174 175 // Cleanup PHI nodes.176 for (MachineBasicBlock &BB : F) {177 // Prune unneeded PHI entries.178 SmallPtrSet<MachineBasicBlock *, 8> preds(llvm::from_range,179 BB.predecessors());180 for (MachineInstr &Phi : make_early_inc_range(BB.phis())) {181 for (unsigned i = Phi.getNumOperands() - 1; i >= 2; i -= 2) {182 if (!preds.count(Phi.getOperand(i).getMBB())) {183 Phi.removeOperand(i);184 Phi.removeOperand(i - 1);185 ModifiedPHI = true;186 }187 }188 189 if (Phi.getNumOperands() == 3) {190 const MachineOperand &Input = Phi.getOperand(1);191 const MachineOperand &Output = Phi.getOperand(0);192 Register InputReg = Input.getReg();193 Register OutputReg = Output.getReg();194 assert(Output.getSubReg() == 0 && "Cannot have output subregister");195 ModifiedPHI = true;196 197 if (InputReg != OutputReg) {198 MachineRegisterInfo &MRI = F.getRegInfo();199 unsigned InputSub = Input.getSubReg();200 if (InputSub == 0 &&201 MRI.constrainRegClass(InputReg, MRI.getRegClass(OutputReg)) &&202 !Input.isUndef()) {203 MRI.replaceRegWith(OutputReg, InputReg);204 } else {205 // The input register to the PHI has a subregister or it can't be206 // constrained to the proper register class or it is undef:207 // insert a COPY instead of simply replacing the output208 // with the input.209 const TargetInstrInfo *TII = F.getSubtarget().getInstrInfo();210 BuildMI(BB, BB.getFirstNonPHI(), Phi.getDebugLoc(),211 TII->get(TargetOpcode::COPY), OutputReg)212 .addReg(InputReg, getRegState(Input), InputSub);213 }214 Phi.eraseFromParent();215 }216 }217 }218 }219 220 F.RenumberBlocks();221 if (MDT)222 MDT->updateBlockNumbers();223 224 return (!DeadBlocks.empty() || ModifiedPHI);225}226