Home | History | Annotate | Download | only in Scalar 
      1 //===- ADCE.cpp - Code to perform dead code elimination -------------------===//
      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 file implements the Aggressive Dead Code Elimination pass.  This pass
     11 // optimistically assumes that all instructions are dead until proven otherwise,
     12 // allowing it to eliminate dead computations that other DCE passes do not
     13 // catch, particularly involving loop computations.
     14 //
     15 //===----------------------------------------------------------------------===//
     16 
     17 #include "llvm/Transforms/Scalar/ADCE.h"
     18 #include "llvm/ADT/DepthFirstIterator.h"
     19 #include "llvm/ADT/SmallPtrSet.h"
     20 #include "llvm/ADT/SmallVector.h"
     21 #include "llvm/ADT/Statistic.h"
     22 #include "llvm/Analysis/GlobalsModRef.h"
     23 #include "llvm/IR/BasicBlock.h"
     24 #include "llvm/IR/CFG.h"
     25 #include "llvm/IR/InstIterator.h"
     26 #include "llvm/IR/Instructions.h"
     27 #include "llvm/IR/IntrinsicInst.h"
     28 #include "llvm/Pass.h"
     29 #include "llvm/Transforms/Scalar.h"
     30 using namespace llvm;
     31 
     32 #define DEBUG_TYPE "adce"
     33 
     34 STATISTIC(NumRemoved, "Number of instructions removed");
     35 
     36 static bool aggressiveDCE(Function& F) {
     37   SmallPtrSet<Instruction*, 128> Alive;
     38   SmallVector<Instruction*, 128> Worklist;
     39 
     40   // Collect the set of "root" instructions that are known live.
     41   for (Instruction &I : instructions(F)) {
     42     if (isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) || I.isEHPad() ||
     43         I.mayHaveSideEffects()) {
     44       Alive.insert(&I);
     45       Worklist.push_back(&I);
     46     }
     47   }
     48 
     49   // Propagate liveness backwards to operands.
     50   while (!Worklist.empty()) {
     51     Instruction *Curr = Worklist.pop_back_val();
     52     for (Use &OI : Curr->operands()) {
     53       if (Instruction *Inst = dyn_cast<Instruction>(OI))
     54         if (Alive.insert(Inst).second)
     55           Worklist.push_back(Inst);
     56     }
     57   }
     58 
     59   // The inverse of the live set is the dead set.  These are those instructions
     60   // which have no side effects and do not influence the control flow or return
     61   // value of the function, and may therefore be deleted safely.
     62   // NOTE: We reuse the Worklist vector here for memory efficiency.
     63   for (Instruction &I : instructions(F)) {
     64     if (!Alive.count(&I)) {
     65       Worklist.push_back(&I);
     66       I.dropAllReferences();
     67     }
     68   }
     69 
     70   for (Instruction *&I : Worklist) {
     71     ++NumRemoved;
     72     I->eraseFromParent();
     73   }
     74 
     75   return !Worklist.empty();
     76 }
     77 
     78 PreservedAnalyses ADCEPass::run(Function &F) {
     79   if (aggressiveDCE(F))
     80     return PreservedAnalyses::none();
     81   return PreservedAnalyses::all();
     82 }
     83 
     84 namespace {
     85 struct ADCELegacyPass : public FunctionPass {
     86   static char ID; // Pass identification, replacement for typeid
     87   ADCELegacyPass() : FunctionPass(ID) {
     88     initializeADCELegacyPassPass(*PassRegistry::getPassRegistry());
     89   }
     90 
     91   bool runOnFunction(Function& F) override {
     92     if (skipOptnoneFunction(F))
     93       return false;
     94     return aggressiveDCE(F);
     95   }
     96 
     97   void getAnalysisUsage(AnalysisUsage& AU) const override {
     98     AU.setPreservesCFG();
     99     AU.addPreserved<GlobalsAAWrapperPass>();
    100   }
    101 };
    102 }
    103 
    104 char ADCELegacyPass::ID = 0;
    105 INITIALIZE_PASS(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
    106                 false, false)
    107 
    108 FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); }
    109