1038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson//===- DCE.cpp - Code to perform dead code elimination --------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 902e90d59c8aa99c2c921a7f82a5fc9019efb98e6Chris Lattner// 10038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson// This file implements the Aggressive Dead Code Elimination pass. This pass 11038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson// optimistically assumes that all instructions are dead until proven otherwise, 12a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem// allowing it to eliminate dead computations that other DCE passes do not 13038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson// catch, particularly involving loop computations. 1402e90d59c8aa99c2c921a7f82a5fc9019efb98e6Chris Lattner// 1502e90d59c8aa99c2c921a7f82a5fc9019efb98e6Chris Lattner//===----------------------------------------------------------------------===// 1602e90d59c8aa99c2c921a7f82a5fc9019efb98e6Chris Lattner 17022103b3f33febb7e54b8fdf2c9bc461eea78cbaChris Lattner#include "llvm/Transforms/Scalar.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DepthFirstIterator.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallPtrSet.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallVector.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/BasicBlock.h" 2336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 2436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/InstIterator.h" 250b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 27038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson#include "llvm/Pass.h" 28bd1a90ecc77cfdf25125c96acaad1b4152fcd0deChris Lattnerusing namespace llvm; 29d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 30dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "adce" 31dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 32038a8746c96f2290c3e7127883b00fafb223b799Owen AndersonSTATISTIC(NumRemoved, "Number of instructions removed"); 33dfe81ab87aa44e51635b60c964ff6a792dcbc9d3Chris Lattner 340e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 353e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct ADCE : public FunctionPass { 36038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson static char ID; // Pass identification, replacement for typeid 37081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson ADCE() : FunctionPass(ID) { 38081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeADCEPass(*PassRegistry::getPassRegistry()); 39081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 40a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 4136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function& F) override; 42a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage& AU) const override { 44038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson AU.setPreservesCFG(); 45446698b63d574f44b730c6d6d63f9035ad701c5dChris Lattner } 46a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 47038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson }; 48837e42ccefc11be3acf163808c4e2fcb56f73717Chris Lattner} 49837e42ccefc11be3acf163808c4e2fcb56f73717Chris Lattner 50038a8746c96f2290c3e7127883b00fafb223b799Owen Andersonchar ADCE::ID = 0; 51ce665bd2e2b581ab0858d1afe359192bac96b868Owen AndersonINITIALIZE_PASS(ADCE, "adce", "Aggressive Dead Code Elimination", false, false) 52837e42ccefc11be3acf163808c4e2fcb56f73717Chris Lattner 53038a8746c96f2290c3e7127883b00fafb223b799Owen Andersonbool ADCE::runOnFunction(Function& F) { 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (skipOptnoneFunction(F)) 5536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 57ea6462bfd0ea2845338e98a1417b94bd4c575b9eOwen Anderson SmallPtrSet<Instruction*, 128> alive; 58ea6462bfd0ea2845338e98a1417b94bd4c575b9eOwen Anderson SmallVector<Instruction*, 128> worklist; 59a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 60038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson // Collect the set of "root" instructions that are known live. 61038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 62038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson if (isa<TerminatorInst>(I.getInstructionIterator()) || 636129e24e49f74f694575f9779055233fb1ab506eDale Johannesen isa<DbgInfoIntrinsic>(I.getInstructionIterator()) || 64cbe003b243c5aa0ca7ec3872164a5e53950ba44fBill Wendling isa<LandingPadInst>(I.getInstructionIterator()) || 657af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands I->mayHaveSideEffects()) { 66038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson alive.insert(I.getInstructionIterator()); 67038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson worklist.push_back(I.getInstructionIterator()); 68b8259dd93c2cab05e8381bb442f018cf52ed646dChris Lattner } 69a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 70038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson // Propagate liveness backwards to operands. 71038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson while (!worklist.empty()) { 72321a813c536e2f1f2f05bbe78a7fbf64046f0557Dan Gohman Instruction* curr = worklist.pop_back_val(); 73038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson for (Instruction::op_iterator OI = curr->op_begin(), OE = curr->op_end(); 74038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson OI != OE; ++OI) 75038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson if (Instruction* Inst = dyn_cast<Instruction>(OI)) 76038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson if (alive.insert(Inst)) 77038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson worklist.push_back(Inst); 78b8259dd93c2cab05e8381bb442f018cf52ed646dChris Lattner } 79a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 80038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson // The inverse of the live set is the dead set. These are those instructions 81038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson // which have no side effects and do not influence the control flow or return 82038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson // value of the function, and may therefore be deleted safely. 83ae18bd4246da4d2ac9494bbaeadd40abfa533c83Owen Anderson // NOTE: We reuse the worklist vector here for memory efficiency. 84038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 85038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson if (!alive.count(I.getInstructionIterator())) { 86ae18bd4246da4d2ac9494bbaeadd40abfa533c83Owen Anderson worklist.push_back(I.getInstructionIterator()); 87038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson I->dropAllReferences(); 88837e42ccefc11be3acf163808c4e2fcb56f73717Chris Lattner } 89a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 906227d5c690504c7ada5780c00a635b282c46e275Craig Topper for (SmallVectorImpl<Instruction *>::iterator I = worklist.begin(), 91ae18bd4246da4d2ac9494bbaeadd40abfa533c83Owen Anderson E = worklist.end(); I != E; ++I) { 92fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumRemoved; 93038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson (*I)->eraseFromParent(); 946b8efcd6975225c43572bf72a0507d9e4ae74025Chris Lattner } 9535275f499a95b0b7230311cee05d686310310baaDevang Patel 96b8f69c65df4e10925305e8547bc3b509f467fe15Devang Patel return !worklist.empty(); 97b8259dd93c2cab05e8381bb442f018cf52ed646dChris Lattner} 98038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson 99038a8746c96f2290c3e7127883b00fafb223b799Owen AndersonFunctionPass *llvm::createAggressiveDCEPass() { 100038a8746c96f2290c3e7127883b00fafb223b799Owen Anderson return new ADCE(); 101a806a87e29efabc1d71863c03406df39f6901e96Duncan Sands} 102