DCE.cpp revision fd93908ae8b9684fe71c239e3c6cfe13ff6a2663
1a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project//===- DCE.cpp - Code to perform dead code elimination --------------------===// 2a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// 3a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// The LLVM Compiler Infrastructure 4a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// 5a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// This file was developed by the LLVM research group and is distributed under 6a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// the University of Illinois Open Source License. See LICENSE.TXT for details. 7a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// 8a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project//===----------------------------------------------------------------------===// 9a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// 10a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// This file implements dead inst elimination and dead code elimination. 11a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// 12a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// Dead Inst Elimination performs a single pass over the function removing 13a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// instructions that are obviously dead. Dead Code Elimination is similar, but 14a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// it rechecks instructions that were used by removed instructions to see if 15a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// they are newly dead. 16a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// 17a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project//===----------------------------------------------------------------------===// 18a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 19a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project#include "llvm/Transforms/Scalar.h" 20a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project#include "llvm/Transforms/Utils/Local.h" 21a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project#include "llvm/Instruction.h" 22a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project#include "llvm/Pass.h" 23a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project#include "llvm/Support/InstIterator.h" 24a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project#include "llvm/ADT/Statistic.h" 25a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project#include <set> 26a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Projectusing namespace llvm; 27a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 28a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Projectnamespace { 29a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project Statistic<> DIEEliminated("die", "Number of insts removed"); 30a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project Statistic<> DCEEliminated("dce", "Number of insts removed"); 31a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 32a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project //===--------------------------------------------------------------------===// 33a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // DeadInstElimination pass implementation 34a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // 35a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 36a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project struct DeadInstElimination : public BasicBlockPass { 37a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project virtual bool runOnBasicBlock(BasicBlock &BB) { 38a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project bool Changed = false; 39a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) 40a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project if (dceInstruction(DI)) { 41a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project Changed = true; 42a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project ++DIEEliminated; 43a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project } else 44a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project ++DI; 45a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project return Changed; 46a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project } 47a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 48a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project virtual void getAnalysisUsage(AnalysisUsage &AU) const { 49a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project AU.setPreservesCFG(); 50a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project } 51a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project }; 52a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 53a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project RegisterOpt<DeadInstElimination> X("die", "Dead Instruction Elimination"); 54a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project} 55a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 56a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source ProjectFunctionPass *llvm::createDeadInstEliminationPass() { 57a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project return new DeadInstElimination(); 58a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project} 59a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 60a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 61a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project//===----------------------------------------------------------------------===// 62a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// DeadCodeElimination pass implementation 63a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project// 64a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 65a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Projectnamespace { 66a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project struct DCE : public FunctionPass { 67a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project virtual bool runOnFunction(Function &F); 68a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 69a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project virtual void getAnalysisUsage(AnalysisUsage &AU) const { 70a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project AU.setPreservesCFG(); 71a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project } 72a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project }; 73a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 74a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project RegisterOpt<DCE> Y("dce", "Dead Code Elimination"); 75a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project} 76a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 77a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Projectbool DCE::runOnFunction(Function &F) { 78a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // Start out with all of the instructions in the worklist... 79a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project std::vector<Instruction*> WorkList; 80a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) { 81a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project WorkList.push_back(&*i); 82a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project } 83a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project std::set<Instruction*> DeadInsts; 84a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 85a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // Loop over the worklist finding instructions that are dead. If they are 86a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // dead make them drop all of their uses, making other instructions 87a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // potentially dead, and work until the worklist is empty. 88a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // 89a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project while (!WorkList.empty()) { 90a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project Instruction *I = WorkList.back(); 91a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project WorkList.pop_back(); 92a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 93a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project if (isInstructionTriviallyDead(I)) { // If the instruction is dead... 94a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // Loop over all of the values that the instruction uses, if there are 95a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // instructions being used, add them to the worklist, because they might 96a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // go dead after this one is removed. 97a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // 98a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 99a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project if (Instruction *Used = dyn_cast<Instruction>(*OI)) 100a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project WorkList.push_back(Used); 101a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 102a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // Tell the instruction to let go of all of the values it uses... 103a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project I->dropAllReferences(); 104a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 105a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // Keep track of this instruction, because we are going to delete it later 106a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project DeadInsts.insert(I); 107a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project } 108a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project } 109a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 110a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // If we found no dead instructions, we haven't changed the function... 111a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project if (DeadInsts.empty()) return false; 112a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 113a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project // Otherwise, loop over the program, removing and deleting the instructions... 114a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 115a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project for (BasicBlock::iterator BI = I->begin(); BI != I->end(); ) 116a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project if (DeadInsts.count(BI)) { // Is this instruction dead? 117a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project BI = I->getInstList().erase(BI); // Yup, remove and delete inst 118a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project ++DCEEliminated; 119a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project } else { // This instruction is not dead 120a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project ++BI; // Continue on to the next one... 121a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project } 122a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 123a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project return true; 124a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project} 125a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 126a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source ProjectFunctionPass *llvm::createDeadCodeEliminationPass() { 127a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project return new DCE(); 128a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project} 129a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project 130a89495f48f185779ff7d9d64ce6e6b037c9ded87The Android Open Source Project