LCOV - code coverage report
Current view: top level - lib/CodeGen - UnreachableBlockElim.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 80 82 97.6 %
Date: 2018-09-23 13:06:45 Functions: 11 11 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- UnreachableBlockElim.cpp - Remove unreachable blocks for codegen --===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This pass is an extremely simple version of the SimplifyCFG pass.  Its sole
      11             : // job is to delete LLVM basic blocks that are not reachable from the entry
      12             : // node.  To do this, it performs a simple depth first traversal of the CFG,
      13             : // then deletes any unvisited nodes.
      14             : //
      15             : // Note that this pass is really a hack.  In particular, the instruction
      16             : // selectors for various targets should just not generate code for unreachable
      17             : // blocks.  Until LLVM has a more systematic way of defining instruction
      18             : // selectors, however, we cannot really expect them to handle additional
      19             : // complexity.
      20             : //
      21             : //===----------------------------------------------------------------------===//
      22             : 
      23             : #include "llvm/CodeGen/UnreachableBlockElim.h"
      24             : #include "llvm/ADT/DepthFirstIterator.h"
      25             : #include "llvm/ADT/SmallPtrSet.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/MachineModuleInfo.h"
      31             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      32             : #include "llvm/CodeGen/Passes.h"
      33             : #include "llvm/CodeGen/TargetInstrInfo.h"
      34             : #include "llvm/IR/CFG.h"
      35             : #include "llvm/IR/Constant.h"
      36             : #include "llvm/IR/Dominators.h"
      37             : #include "llvm/IR/Function.h"
      38             : #include "llvm/IR/Instructions.h"
      39             : #include "llvm/IR/Type.h"
      40             : #include "llvm/Pass.h"
      41             : using namespace llvm;
      42             : 
      43      458401 : static bool eliminateUnreachableBlock(Function &F) {
      44             :   df_iterator_default_set<BasicBlock*> Reachable;
      45             : 
      46             :   // Mark all reachable blocks.
      47     4670666 :   for (BasicBlock *BB : depth_first_ext(&F, Reachable))
      48             :     (void)BB/* Mark all reachable blocks */;
      49             : 
      50             :   // Loop over all dead blocks, remembering them and deleting all instructions
      51             :   // in them.
      52             :   std::vector<BasicBlock*> DeadBlocks;
      53     3889412 :   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
      54     3431012 :     if (!Reachable.count(&*I)) {
      55      135548 :       BasicBlock *BB = &*I;
      56      135548 :       DeadBlocks.push_back(BB);
      57      135549 :       while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
      58           1 :         PN->replaceAllUsesWith(Constant::getNullValue(PN->getType()));
      59           1 :         BB->getInstList().pop_front();
      60           1 :       }
      61      259166 :       for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
      62      123618 :         (*SI)->removePredecessor(BB);
      63      135548 :       BB->dropAllReferences();
      64             :     }
      65             : 
      66             :   // Actually remove the blocks now.
      67     1052348 :   for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) {
      68      271096 :     DeadBlocks[i]->eraseFromParent();
      69             :   }
      70             : 
      71      458400 :   return !DeadBlocks.empty();
      72             : }
      73             : 
      74             : namespace {
      75             : class UnreachableBlockElimLegacyPass : public FunctionPass {
      76      458400 :   bool runOnFunction(Function &F) override {
      77      458400 :     return eliminateUnreachableBlock(F);
      78             :   }
      79             : 
      80             : public:
      81             :   static char ID; // Pass identification, replacement for typeid
      82       31639 :   UnreachableBlockElimLegacyPass() : FunctionPass(ID) {
      83       31639 :     initializeUnreachableBlockElimLegacyPassPass(
      84       31639 :         *PassRegistry::getPassRegistry());
      85             :   }
      86             : 
      87       31487 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      88             :     AU.addPreserved<DominatorTreeWrapperPass>();
      89       31487 :   }
      90             : };
      91             : }
      92             : char UnreachableBlockElimLegacyPass::ID = 0;
      93      157455 : INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim",
      94             :                 "Remove unreachable blocks from the CFG", false, false)
      95             : 
      96       31638 : FunctionPass *llvm::createUnreachableBlockEliminationPass() {
      97       31638 :   return new UnreachableBlockElimLegacyPass();
      98             : }
      99             : 
     100           1 : PreservedAnalyses UnreachableBlockElimPass::run(Function &F,
     101             :                                                 FunctionAnalysisManager &AM) {
     102           1 :   bool Changed = eliminateUnreachableBlock(F);
     103           1 :   if (!Changed)
     104             :     return PreservedAnalyses::all();
     105           1 :   PreservedAnalyses PA;
     106             :   PA.preserve<DominatorTreeAnalysis>();
     107           1 :   return PA;
     108             : }
     109             : 
     110             : namespace {
     111             :   class UnreachableMachineBlockElim : public MachineFunctionPass {
     112             :     bool runOnMachineFunction(MachineFunction &F) override;
     113             :     void getAnalysisUsage(AnalysisUsage &AU) const override;
     114             :     MachineModuleInfo *MMI;
     115             :   public:
     116             :     static char ID; // Pass identification, replacement for typeid
     117       21901 :     UnreachableMachineBlockElim() : MachineFunctionPass(ID) {}
     118             :   };
     119             : }
     120             : char UnreachableMachineBlockElim::ID = 0;
     121             : 
     122      119623 : INITIALIZE_PASS(UnreachableMachineBlockElim, "unreachable-mbb-elimination",
     123             :   "Remove unreachable machine basic blocks", false, false)
     124             : 
     125             : char &llvm::UnreachableMachineBlockElimID = UnreachableMachineBlockElim::ID;
     126             : 
     127       21894 : void UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const {
     128             :   AU.addPreserved<MachineLoopInfo>();
     129             :   AU.addPreserved<MachineDominatorTree>();
     130       21894 :   MachineFunctionPass::getAnalysisUsage(AU);
     131       21894 : }
     132             : 
     133      206750 : bool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) {
     134             :   df_iterator_default_set<MachineBasicBlock*> Reachable;
     135             :   bool ModifiedPHI = false;
     136             : 
     137      206750 :   MMI = getAnalysisIfAvailable<MachineModuleInfo>();
     138      206750 :   MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>();
     139      206750 :   MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
     140             : 
     141             :   // Mark all reachable blocks.
     142     1095349 :   for (MachineBasicBlock *BB : depth_first_ext(&F, Reachable))
     143             :     (void)BB/* Mark all reachable blocks */;
     144             : 
     145             :   // Loop over all dead blocks, remembering them and deleting all instructions
     146             :   // in them.
     147             :   std::vector<MachineBasicBlock*> DeadBlocks;
     148      682006 :   for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) {
     149      475256 :     MachineBasicBlock *BB = &*I;
     150             : 
     151             :     // Test for deadness.
     152      475256 :     if (!Reachable.count(BB)) {
     153         156 :       DeadBlocks.push_back(BB);
     154             : 
     155             :       // Update dominator and loop info.
     156         156 :       if (MLI) MLI->removeBlock(BB);
     157         156 :       if (MDT && MDT->getNode(BB)) MDT->eraseNode(BB);
     158             : 
     159         315 :       while (BB->succ_begin() != BB->succ_end()) {
     160           3 :         MachineBasicBlock* succ = *BB->succ_begin();
     161             : 
     162             :         MachineBasicBlock::iterator start = succ->begin();
     163           5 :         while (start != succ->end() && start->isPHI()) {
     164           6 :           for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2)
     165           8 :             if (start->getOperand(i).isMBB() &&
     166           4 :                 start->getOperand(i).getMBB() == BB) {
     167           2 :               start->RemoveOperand(i);
     168           2 :               start->RemoveOperand(i-1);
     169             :             }
     170             : 
     171             :           start++;
     172             :         }
     173             : 
     174           6 :         BB->removeSuccessor(BB->succ_begin());
     175             :       }
     176             :     }
     177             :   }
     178             : 
     179             :   // Actually remove the blocks now.
     180      413654 :   for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i)
     181         312 :     DeadBlocks[i]->eraseFromParent();
     182             : 
     183             :   // Cleanup PHI nodes.
     184      681848 :   for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) {
     185             :     MachineBasicBlock *BB = &*I;
     186             :     // Prune unneeded PHI entries.
     187             :     SmallPtrSet<MachineBasicBlock*, 8> preds(BB->pred_begin(),
     188      475099 :                                              BB->pred_end());
     189             :     MachineBasicBlock::iterator phi = BB->begin();
     190      564146 :     while (phi != BB->end() && phi->isPHI()) {
     191      290647 :       for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2)
     192      403198 :         if (!preds.count(phi->getOperand(i).getMBB())) {
     193           0 :           phi->RemoveOperand(i);
     194           0 :           phi->RemoveOperand(i-1);
     195             :           ModifiedPHI = true;
     196             :         }
     197             : 
     198       89048 :       if (phi->getNumOperands() == 3) {
     199         154 :         const MachineOperand &Input = phi->getOperand(1);
     200             :         const MachineOperand &Output = phi->getOperand(0);
     201         154 :         unsigned InputReg = Input.getReg();
     202         154 :         unsigned OutputReg = Output.getReg();
     203             :         assert(Output.getSubReg() == 0 && "Cannot have output subregister");
     204             :         ModifiedPHI = true;
     205             : 
     206         154 :         if (InputReg != OutputReg) {
     207         154 :           MachineRegisterInfo &MRI = F.getRegInfo();
     208             :           unsigned InputSub = Input.getSubReg();
     209         153 :           if (InputSub == 0 &&
     210         307 :               MRI.constrainRegClass(InputReg, MRI.getRegClass(OutputReg)) &&
     211             :               !Input.isUndef()) {
     212         152 :             MRI.replaceRegWith(OutputReg, InputReg);
     213             :           } else {
     214             :             // The input register to the PHI has a subregister or it can't be
     215             :             // constrained to the proper register class or it is undef:
     216             :             // insert a COPY instead of simply replacing the output
     217             :             // with the input.
     218           2 :             const TargetInstrInfo *TII = F.getSubtarget().getInstrInfo();
     219           2 :             BuildMI(*BB, BB->getFirstNonPHI(), phi->getDebugLoc(),
     220           4 :                     TII->get(TargetOpcode::COPY), OutputReg)
     221           2 :                 .addReg(InputReg, getRegState(Input), InputSub);
     222             :           }
     223         154 :           phi++->eraseFromParent();
     224             :         }
     225         154 :         continue;
     226             :       }
     227             : 
     228             :       ++phi;
     229             :     }
     230             :   }
     231             : 
     232      206749 :   F.RenumberBlocks();
     233             : 
     234      206749 :   return (!DeadBlocks.empty() || ModifiedPHI);
     235             : }

Generated by: LCOV version 1.13