1193323Sed//===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This pass is an extremely simple version of the SimplifyCFG pass. Its sole 10193323Sed// job is to delete LLVM basic blocks that are not reachable from the entry 11193323Sed// node. To do this, it performs a simple depth first traversal of the CFG, 12193323Sed// then deletes any unvisited nodes. 13193323Sed// 14193323Sed// Note that this pass is really a hack. In particular, the instruction 15193323Sed// selectors for various targets should just not generate code for unreachable 16193323Sed// blocks. Until LLVM has a more systematic way of defining instruction 17193323Sed// selectors, however, we cannot really expect them to handle additional 18193323Sed// complexity. 19193323Sed// 20193323Sed//===----------------------------------------------------------------------===// 21193323Sed 22309124Sdim#include "llvm/CodeGen/UnreachableBlockElim.h" 23249423Sdim#include "llvm/ADT/DepthFirstIterator.h" 24249423Sdim#include "llvm/ADT/SmallPtrSet.h" 25198090Srdivacky#include "llvm/CodeGen/MachineDominators.h" 26193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 27321369Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 28249423Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 29193323Sed#include "llvm/CodeGen/MachineModuleInfo.h" 30193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 31309124Sdim#include "llvm/CodeGen/Passes.h" 32327952Sdim#include "llvm/CodeGen/TargetInstrInfo.h" 33276479Sdim#include "llvm/IR/CFG.h" 34249423Sdim#include "llvm/IR/Constant.h" 35276479Sdim#include "llvm/IR/Dominators.h" 36249423Sdim#include "llvm/IR/Function.h" 37249423Sdim#include "llvm/IR/Instructions.h" 38249423Sdim#include "llvm/IR/Type.h" 39360784Sdim#include "llvm/InitializePasses.h" 40249423Sdim#include "llvm/Pass.h" 41353358Sdim#include "llvm/Transforms/Utils/BasicBlockUtils.h" 42193323Sedusing namespace llvm; 43193323Sed 44309124Sdimnamespace { 45309124Sdimclass UnreachableBlockElimLegacyPass : public FunctionPass { 46309124Sdim bool runOnFunction(Function &F) override { 47353358Sdim return llvm::EliminateUnreachableBlocks(F); 48309124Sdim } 49193323Sed 50309124Sdimpublic: 51309124Sdim static char ID; // Pass identification, replacement for typeid 52309124Sdim UnreachableBlockElimLegacyPass() : FunctionPass(ID) { 53309124Sdim initializeUnreachableBlockElimLegacyPassPass( 54309124Sdim *PassRegistry::getPassRegistry()); 55309124Sdim } 56309124Sdim 57309124Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 58309124Sdim AU.addPreserved<DominatorTreeWrapperPass>(); 59309124Sdim } 60309124Sdim}; 61309124Sdim} 62309124Sdimchar UnreachableBlockElimLegacyPass::ID = 0; 63309124SdimINITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim", 64309124Sdim "Remove unreachable blocks from the CFG", false, false) 65309124Sdim 66309124SdimFunctionPass *llvm::createUnreachableBlockEliminationPass() { 67309124Sdim return new UnreachableBlockElimLegacyPass(); 68309124Sdim} 69309124Sdim 70309124SdimPreservedAnalyses UnreachableBlockElimPass::run(Function &F, 71309124Sdim FunctionAnalysisManager &AM) { 72353358Sdim bool Changed = llvm::EliminateUnreachableBlocks(F); 73309124Sdim if (!Changed) 74309124Sdim return PreservedAnalyses::all(); 75309124Sdim PreservedAnalyses PA; 76309124Sdim PA.preserve<DominatorTreeAnalysis>(); 77309124Sdim return PA; 78309124Sdim} 79309124Sdim 80193323Sednamespace { 81198892Srdivacky class UnreachableMachineBlockElim : public MachineFunctionPass { 82276479Sdim bool runOnMachineFunction(MachineFunction &F) override; 83276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override; 84193323Sed MachineModuleInfo *MMI; 85193323Sed public: 86193323Sed static char ID; // Pass identification, replacement for typeid 87212904Sdim UnreachableMachineBlockElim() : MachineFunctionPass(ID) {} 88193323Sed }; 89193323Sed} 90193323Sedchar UnreachableMachineBlockElim::ID = 0; 91193323Sed 92212904SdimINITIALIZE_PASS(UnreachableMachineBlockElim, "unreachable-mbb-elimination", 93218893Sdim "Remove unreachable machine basic blocks", false, false) 94193323Sed 95212904Sdimchar &llvm::UnreachableMachineBlockElimID = UnreachableMachineBlockElim::ID; 96193323Sed 97198090Srdivackyvoid UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const { 98198090Srdivacky AU.addPreserved<MachineLoopInfo>(); 99198090Srdivacky AU.addPreserved<MachineDominatorTree>(); 100198090Srdivacky MachineFunctionPass::getAnalysisUsage(AU); 101198090Srdivacky} 102198090Srdivacky 103193323Sedbool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) { 104314564Sdim df_iterator_default_set<MachineBasicBlock*> Reachable; 105218893Sdim bool ModifiedPHI = false; 106193323Sed 107360784Sdim auto *MMIWP = getAnalysisIfAvailable<MachineModuleInfoWrapperPass>(); 108360784Sdim MMI = MMIWP ? &MMIWP->getMMI() : nullptr; 109198090Srdivacky MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>(); 110198090Srdivacky MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>(); 111193323Sed 112193323Sed // Mark all reachable blocks. 113280031Sdim for (MachineBasicBlock *BB : depth_first_ext(&F, Reachable)) 114280031Sdim (void)BB/* Mark all reachable blocks */; 115193323Sed 116193323Sed // Loop over all dead blocks, remembering them and deleting all instructions 117193323Sed // in them. 118193323Sed std::vector<MachineBasicBlock*> DeadBlocks; 119193323Sed for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 120296417Sdim MachineBasicBlock *BB = &*I; 121193323Sed 122193323Sed // Test for deadness. 123193323Sed if (!Reachable.count(BB)) { 124193323Sed DeadBlocks.push_back(BB); 125193323Sed 126198090Srdivacky // Update dominator and loop info. 127198090Srdivacky if (MLI) MLI->removeBlock(BB); 128198090Srdivacky if (MDT && MDT->getNode(BB)) MDT->eraseNode(BB); 129198090Srdivacky 130193323Sed while (BB->succ_begin() != BB->succ_end()) { 131193323Sed MachineBasicBlock* succ = *BB->succ_begin(); 132193323Sed 133193323Sed MachineBasicBlock::iterator start = succ->begin(); 134203954Srdivacky while (start != succ->end() && start->isPHI()) { 135193323Sed for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2) 136193323Sed if (start->getOperand(i).isMBB() && 137193323Sed start->getOperand(i).getMBB() == BB) { 138193323Sed start->RemoveOperand(i); 139193323Sed start->RemoveOperand(i-1); 140193323Sed } 141193323Sed 142193323Sed start++; 143193323Sed } 144193323Sed 145193323Sed BB->removeSuccessor(BB->succ_begin()); 146193323Sed } 147193323Sed } 148193323Sed } 149193323Sed 150193323Sed // Actually remove the blocks now. 151360784Sdim for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) { 152360784Sdim // Remove any call site information for calls in the block. 153360784Sdim for (auto &I : DeadBlocks[i]->instrs()) 154360784Sdim if (I.isCall(MachineInstr::IgnoreBundle)) 155360784Sdim DeadBlocks[i]->getParent()->eraseCallSiteInfo(&I); 156360784Sdim 157205218Srdivacky DeadBlocks[i]->eraseFromParent(); 158360784Sdim } 159193323Sed 160193323Sed // Cleanup PHI nodes. 161193323Sed for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 162296417Sdim MachineBasicBlock *BB = &*I; 163193323Sed // Prune unneeded PHI entries. 164193323Sed SmallPtrSet<MachineBasicBlock*, 8> preds(BB->pred_begin(), 165193323Sed BB->pred_end()); 166193323Sed MachineBasicBlock::iterator phi = BB->begin(); 167203954Srdivacky while (phi != BB->end() && phi->isPHI()) { 168193323Sed for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2) 169193323Sed if (!preds.count(phi->getOperand(i).getMBB())) { 170193323Sed phi->RemoveOperand(i); 171193323Sed phi->RemoveOperand(i-1); 172218893Sdim ModifiedPHI = true; 173193323Sed } 174193323Sed 175193323Sed if (phi->getNumOperands() == 3) { 176321369Sdim const MachineOperand &Input = phi->getOperand(1); 177321369Sdim const MachineOperand &Output = phi->getOperand(0); 178360784Sdim Register InputReg = Input.getReg(); 179360784Sdim Register OutputReg = Output.getReg(); 180321369Sdim assert(Output.getSubReg() == 0 && "Cannot have output subregister"); 181218893Sdim ModifiedPHI = true; 182193323Sed 183321369Sdim if (InputReg != OutputReg) { 184223017Sdim MachineRegisterInfo &MRI = F.getRegInfo(); 185321369Sdim unsigned InputSub = Input.getSubReg(); 186321369Sdim if (InputSub == 0 && 187327952Sdim MRI.constrainRegClass(InputReg, MRI.getRegClass(OutputReg)) && 188327952Sdim !Input.isUndef()) { 189321369Sdim MRI.replaceRegWith(OutputReg, InputReg); 190321369Sdim } else { 191321369Sdim // The input register to the PHI has a subregister or it can't be 192327952Sdim // constrained to the proper register class or it is undef: 193321369Sdim // insert a COPY instead of simply replacing the output 194321369Sdim // with the input. 195321369Sdim const TargetInstrInfo *TII = F.getSubtarget().getInstrInfo(); 196321369Sdim BuildMI(*BB, BB->getFirstNonPHI(), phi->getDebugLoc(), 197321369Sdim TII->get(TargetOpcode::COPY), OutputReg) 198321369Sdim .addReg(InputReg, getRegState(Input), InputSub); 199321369Sdim } 200321369Sdim phi++->eraseFromParent(); 201223017Sdim } 202193323Sed continue; 203193323Sed } 204193323Sed 205193323Sed ++phi; 206193323Sed } 207193323Sed } 208193323Sed 209193323Sed F.RenumberBlocks(); 210193323Sed 211288943Sdim return (!DeadBlocks.empty() || ModifiedPHI); 212193323Sed} 213