| //===- DCE.cpp - Code to perform dead code elimination --------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements dead inst elimination and dead code elimination. |
| // |
| // Dead Inst Elimination performs a single pass over the function removing |
| // instructions that are obviously dead. Dead Code Elimination is similar, but |
| // it rechecks instructions that were used by removed instructions to see if |
| // they are newly dead. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/Transforms/Scalar/DCE.h" |
| #include "llvm/ADT/SetVector.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/Analysis/TargetLibraryInfo.h" |
| #include "llvm/IR/InstIterator.h" |
| #include "llvm/IR/Instruction.h" |
| #include "llvm/InitializePasses.h" |
| #include "llvm/Pass.h" |
| #include "llvm/Support/DebugCounter.h" |
| #include "llvm/Transforms/Scalar.h" |
| #include "llvm/Transforms/Utils/AssumeBundleBuilder.h" |
| #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
| #include "llvm/Transforms/Utils/Local.h" |
| using namespace llvm; |
| |
| #define DEBUG_TYPE "dce" |
| |
| STATISTIC(DCEEliminated, "Number of insts removed"); |
| DEBUG_COUNTER(DCECounter, "dce-transform", |
| "Controls which instructions are eliminated"); |
| |
| //===--------------------------------------------------------------------===// |
| // RedundantDbgInstElimination pass implementation |
| // |
| |
| namespace { |
| struct RedundantDbgInstElimination : public FunctionPass { |
| static char ID; // Pass identification, replacement for typeid |
| RedundantDbgInstElimination() : FunctionPass(ID) { |
| initializeRedundantDbgInstEliminationPass(*PassRegistry::getPassRegistry()); |
| } |
| bool runOnFunction(Function &F) override { |
| if (skipFunction(F)) |
| return false; |
| bool Changed = false; |
| for (auto &BB : F) |
| Changed |= RemoveRedundantDbgInstrs(&BB); |
| return Changed; |
| } |
| |
| void getAnalysisUsage(AnalysisUsage &AU) const override { |
| AU.setPreservesCFG(); |
| } |
| }; |
| } |
| |
| char RedundantDbgInstElimination::ID = 0; |
| INITIALIZE_PASS(RedundantDbgInstElimination, "redundant-dbg-inst-elim", |
| "Redundant Dbg Instruction Elimination", false, false) |
| |
| Pass *llvm::createRedundantDbgInstEliminationPass() { |
| return new RedundantDbgInstElimination(); |
| } |
| |
| PreservedAnalyses |
| RedundantDbgInstEliminationPass::run(Function &F, FunctionAnalysisManager &AM) { |
| bool Changed = false; |
| for (auto &BB : F) |
| Changed |= RemoveRedundantDbgInstrs(&BB); |
| if (!Changed) |
| return PreservedAnalyses::all(); |
| PreservedAnalyses PA; |
| PA.preserveSet<CFGAnalyses>(); |
| return PA; |
| } |
| |
| //===--------------------------------------------------------------------===// |
| // DeadCodeElimination pass implementation |
| // |
| |
| static bool DCEInstruction(Instruction *I, |
| SmallSetVector<Instruction *, 16> &WorkList, |
| const TargetLibraryInfo *TLI) { |
| if (isInstructionTriviallyDead(I, TLI)) { |
| if (!DebugCounter::shouldExecute(DCECounter)) |
| return false; |
| |
| salvageDebugInfo(*I); |
| salvageKnowledge(I); |
| |
| // Null out all of the instruction's operands to see if any operand becomes |
| // dead as we go. |
| for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { |
| Value *OpV = I->getOperand(i); |
| I->setOperand(i, nullptr); |
| |
| if (!OpV->use_empty() || I == OpV) |
| continue; |
| |
| // If the operand is an instruction that became dead as we nulled out the |
| // operand, and if it is 'trivially' dead, delete it in a future loop |
| // iteration. |
| if (Instruction *OpI = dyn_cast<Instruction>(OpV)) |
| if (isInstructionTriviallyDead(OpI, TLI)) |
| WorkList.insert(OpI); |
| } |
| |
| I->eraseFromParent(); |
| ++DCEEliminated; |
| return true; |
| } |
| return false; |
| } |
| |
| static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI) { |
| bool MadeChange = false; |
| SmallSetVector<Instruction *, 16> WorkList; |
| // Iterate over the original function, only adding insts to the worklist |
| // if they actually need to be revisited. This avoids having to pre-init |
| // the worklist with the entire function's worth of instructions. |
| for (Instruction &I : llvm::make_early_inc_range(instructions(F))) { |
| // We're visiting this instruction now, so make sure it's not in the |
| // worklist from an earlier visit. |
| if (!WorkList.count(&I)) |
| MadeChange |= DCEInstruction(&I, WorkList, TLI); |
| } |
| |
| while (!WorkList.empty()) { |
| Instruction *I = WorkList.pop_back_val(); |
| MadeChange |= DCEInstruction(I, WorkList, TLI); |
| } |
| return MadeChange; |
| } |
| |
| PreservedAnalyses DCEPass::run(Function &F, FunctionAnalysisManager &AM) { |
| if (!eliminateDeadCode(F, &AM.getResult<TargetLibraryAnalysis>(F))) |
| return PreservedAnalyses::all(); |
| |
| PreservedAnalyses PA; |
| PA.preserveSet<CFGAnalyses>(); |
| return PA; |
| } |
| |
| namespace { |
| struct DCELegacyPass : public FunctionPass { |
| static char ID; // Pass identification, replacement for typeid |
| DCELegacyPass() : FunctionPass(ID) { |
| initializeDCELegacyPassPass(*PassRegistry::getPassRegistry()); |
| } |
| |
| bool runOnFunction(Function &F) override { |
| if (skipFunction(F)) |
| return false; |
| |
| TargetLibraryInfo *TLI = |
| &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); |
| |
| return eliminateDeadCode(F, TLI); |
| } |
| |
| void getAnalysisUsage(AnalysisUsage &AU) const override { |
| AU.addRequired<TargetLibraryInfoWrapperPass>(); |
| AU.setPreservesCFG(); |
| } |
| }; |
| } |
| |
| char DCELegacyPass::ID = 0; |
| INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false) |
| |
| FunctionPass *llvm::createDeadCodeEliminationPass() { |
| return new DCELegacyPass(); |
| } |