LCOV - code coverage report
Current view: top level - lib/CodeGen - UnreachableBlockElim.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 98 101 97.0 %
Date: 2017-09-14 15:23:50 Functions: 13 15 86.7 %
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/IR/CFG.h"
      34             : #include "llvm/IR/Constant.h"
      35             : #include "llvm/IR/Dominators.h"
      36             : #include "llvm/IR/Function.h"
      37             : #include "llvm/IR/Instructions.h"
      38             : #include "llvm/IR/Type.h"
      39             : #include "llvm/Pass.h"
      40             : #include "llvm/Target/TargetInstrInfo.h"
      41             : using namespace llvm;
      42             : 
      43      161809 : static bool eliminateUnreachableBlock(Function &F) {
      44      323618 :   df_iterator_default_set<BasicBlock*> Reachable;
      45             : 
      46             :   // Mark all reachable blocks.
      47     1421021 :   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      323618 :   std::vector<BasicBlock*> DeadBlocks;
      53      323618 :   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
      54      306102 :     if (!Reachable.count(&*I)) {
      55         114 :       BasicBlock *BB = &*I;
      56         114 :       DeadBlocks.push_back(BB);
      57         231 :       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         391 :       for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
      62          98 :         (*SI)->removePredecessor(BB);
      63         114 :       BB->dropAllReferences();
      64             :     }
      65             : 
      66             :   // Actually remove the blocks now.
      67      323732 :   for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i) {
      68         228 :     DeadBlocks[i]->eraseFromParent();
      69             :   }
      70             : 
      71      323618 :   return !DeadBlocks.empty();
      72             : }
      73             : 
      74             : namespace {
      75       37735 : class UnreachableBlockElimLegacyPass : public FunctionPass {
      76      161808 :   bool runOnFunction(Function &F) override {
      77      161808 :     return eliminateUnreachableBlock(F);
      78             :   }
      79             : 
      80             : public:
      81             :   static char ID; // Pass identification, replacement for typeid
      82       37974 :   UnreachableBlockElimLegacyPass() : FunctionPass(ID) {
      83       18987 :     initializeUnreachableBlockElimLegacyPassPass(
      84       18987 :         *PassRegistry::getPassRegistry());
      85             :   }
      86             : 
      87       18941 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      88       18941 :     AU.addPreserved<DominatorTreeWrapperPass>();
      89       18941 :   }
      90             : };
      91             : }
      92             : char UnreachableBlockElimLegacyPass::ID = 0;
      93      298041 : INITIALIZE_PASS(UnreachableBlockElimLegacyPass, "unreachableblockelim",
      94             :                 "Remove unreachable blocks from the CFG", false, false)
      95             : 
      96       18986 : FunctionPass *llvm::createUnreachableBlockEliminationPass() {
      97       37972 :   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           2 :   PreservedAnalyses PA;
     106           1 :   PA.preserve<DominatorTreeAnalysis>();
     107           1 :   return PA;
     108             : }
     109             : 
     110             : namespace {
     111       16742 :   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       16845 :     UnreachableMachineBlockElim() : MachineFunctionPass(ID) {}
     118             :   };
     119             : }
     120             : char UnreachableMachineBlockElim::ID = 0;
     121             : 
     122      211835 : INITIALIZE_PASS(UnreachableMachineBlockElim, "unreachable-mbb-elimination",
     123             :   "Remove unreachable machine basic blocks", false, false)
     124             : 
     125             : char &llvm::UnreachableMachineBlockElimID = UnreachableMachineBlockElim::ID;
     126             : 
     127       16841 : void UnreachableMachineBlockElim::getAnalysisUsage(AnalysisUsage &AU) const {
     128       16841 :   AU.addPreserved<MachineLoopInfo>();
     129       16841 :   AU.addPreserved<MachineDominatorTree>();
     130       16841 :   MachineFunctionPass::getAnalysisUsage(AU);
     131       16841 : }
     132             : 
     133      142488 : bool UnreachableMachineBlockElim::runOnMachineFunction(MachineFunction &F) {
     134      284976 :   df_iterator_default_set<MachineBasicBlock*> Reachable;
     135      142488 :   bool ModifiedPHI = false;
     136             : 
     137      142488 :   MMI = getAnalysisIfAvailable<MachineModuleInfo>();
     138      142487 :   MachineDominatorTree *MDT = getAnalysisIfAvailable<MachineDominatorTree>();
     139      142488 :   MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
     140             : 
     141             :   // Mark all reachable blocks.
     142     1300984 :   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      284975 :   std::vector<MachineBasicBlock*> DeadBlocks;
     148      284974 :   for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) {
     149      294399 :     MachineBasicBlock *BB = &*I;
     150             : 
     151             :     // Test for deadness.
     152      294399 :     if (!Reachable.count(BB)) {
     153         126 :       DeadBlocks.push_back(BB);
     154             : 
     155             :       // Update dominator and loop info.
     156         126 :       if (MLI) MLI->removeBlock(BB);
     157         126 :       if (MDT && MDT->getNode(BB)) MDT->eraseNode(BB);
     158             : 
     159         539 :       while (BB->succ_begin() != BB->succ_end()) {
     160          14 :         MachineBasicBlock* succ = *BB->succ_begin();
     161             : 
     162           7 :         MachineBasicBlock::iterator start = succ->begin();
     163          29 :         while (start != succ->end() && start->isPHI()) {
     164           8 :           for (unsigned i = start->getNumOperands() - 1; i >= 2; i-=2)
     165          20 :             if (start->getOperand(i).isMBB() &&
     166           5 :                 start->getOperand(i).getMBB() == BB) {
     167           3 :               start->RemoveOperand(i);
     168           3 :               start->RemoveOperand(i-1);
     169             :             }
     170             : 
     171           3 :           start++;
     172             :         }
     173             : 
     174          14 :         BB->removeSuccessor(BB->succ_begin());
     175             :       }
     176             :     }
     177             :   }
     178             : 
     179             :   // Actually remove the blocks now.
     180      285102 :   for (unsigned i = 0, e = DeadBlocks.size(); i != e; ++i)
     181         252 :     DeadBlocks[i]->eraseFromParent();
     182             : 
     183             :   // Cleanup PHI nodes.
     184      284976 :   for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) {
     185      294274 :     MachineBasicBlock *BB = &*I;
     186             :     // Prune unneeded PHI entries.
     187             :     SmallPtrSet<MachineBasicBlock*, 8> preds(BB->pred_begin(),
     188      882822 :                                              BB->pred_end());
     189      294274 :     MachineBasicBlock::iterator phi = BB->begin();
     190      983082 :     while (phi != BB->end() && phi->isPHI()) {
     191      109240 :       for (unsigned i = phi->getNumOperands() - 1; i >= 2; i-=2)
     192      149312 :         if (!preds.count(phi->getOperand(i).getMBB())) {
     193           0 :           phi->RemoveOperand(i);
     194           0 :           phi->RemoveOperand(i-1);
     195           0 :           ModifiedPHI = true;
     196             :         }
     197             : 
     198       34584 :       if (phi->getNumOperands() == 3) {
     199          76 :         const MachineOperand &Input = phi->getOperand(1);
     200          38 :         const MachineOperand &Output = phi->getOperand(0);
     201          38 :         unsigned InputReg = Input.getReg();
     202          38 :         unsigned OutputReg = Output.getReg();
     203             :         assert(Output.getSubReg() == 0 && "Cannot have output subregister");
     204          38 :         ModifiedPHI = true;
     205             : 
     206          38 :         if (InputReg != OutputReg) {
     207          38 :           MachineRegisterInfo &MRI = F.getRegInfo();
     208          38 :           unsigned InputSub = Input.getSubReg();
     209          75 :           if (InputSub == 0 &&
     210          37 :               MRI.constrainRegClass(InputReg, MRI.getRegClass(OutputReg))) {
     211          37 :             MRI.replaceRegWith(OutputReg, InputReg);
     212             :           } else {
     213             :             // The input register to the PHI has a subregister or it can't be
     214             :             // constrained to the proper register class:
     215             :             // insert a COPY instead of simply replacing the output
     216             :             // with the input.
     217           1 :             const TargetInstrInfo *TII = F.getSubtarget().getInstrInfo();
     218           2 :             BuildMI(*BB, BB->getFirstNonPHI(), phi->getDebugLoc(),
     219           4 :                     TII->get(TargetOpcode::COPY), OutputReg)
     220           1 :                 .addReg(InputReg, getRegState(Input), InputSub);
     221             :           }
     222         114 :           phi++->eraseFromParent();
     223             :         }
     224          38 :         continue;
     225             :       }
     226             : 
     227             :       ++phi;
     228             :     }
     229             :   }
     230             : 
     231      142488 :   F.RenumberBlocks();
     232             : 
     233      284976 :   return (!DeadBlocks.empty() || ModifiedPHI);
     234             : }

Generated by: LCOV version 1.13