148 lines · cpp
1//===- DCE.cpp - Code to perform dead code elimination --------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements dead inst elimination and dead code elimination.10//11// Dead Inst Elimination performs a single pass over the function removing12// instructions that are obviously dead. Dead Code Elimination is similar, but13// it rechecks instructions that were used by removed instructions to see if14// they are newly dead.15//16//===----------------------------------------------------------------------===//17 18#include "llvm/Transforms/Scalar/DCE.h"19#include "llvm/ADT/SetVector.h"20#include "llvm/ADT/Statistic.h"21#include "llvm/Analysis/TargetLibraryInfo.h"22#include "llvm/IR/InstIterator.h"23#include "llvm/IR/Instruction.h"24#include "llvm/InitializePasses.h"25#include "llvm/Pass.h"26#include "llvm/Support/DebugCounter.h"27#include "llvm/Transforms/Scalar.h"28#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"29#include "llvm/Transforms/Utils/BasicBlockUtils.h"30#include "llvm/Transforms/Utils/Local.h"31using namespace llvm;32 33#define DEBUG_TYPE "dce"34 35STATISTIC(DCEEliminated, "Number of insts removed");36DEBUG_COUNTER(DCECounter, "dce-transform",37 "Controls which instructions are eliminated");38 39PreservedAnalyses40RedundantDbgInstEliminationPass::run(Function &F, FunctionAnalysisManager &AM) {41 bool Changed = false;42 for (auto &BB : F)43 Changed |= RemoveRedundantDbgInstrs(&BB);44 if (!Changed)45 return PreservedAnalyses::all();46 PreservedAnalyses PA;47 PA.preserveSet<CFGAnalyses>();48 return PA;49}50 51//===--------------------------------------------------------------------===//52// DeadCodeElimination pass implementation53//54 55static bool DCEInstruction(Instruction *I,56 SmallSetVector<Instruction *, 16> &WorkList,57 const TargetLibraryInfo *TLI) {58 if (isInstructionTriviallyDead(I, TLI)) {59 if (!DebugCounter::shouldExecute(DCECounter))60 return false;61 62 salvageDebugInfo(*I);63 salvageKnowledge(I);64 65 // Null out all of the instruction's operands to see if any operand becomes66 // dead as we go.67 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {68 Value *OpV = I->getOperand(i);69 I->setOperand(i, nullptr);70 71 if (!OpV->use_empty() || I == OpV)72 continue;73 74 // If the operand is an instruction that became dead as we nulled out the75 // operand, and if it is 'trivially' dead, delete it in a future loop76 // iteration.77 if (Instruction *OpI = dyn_cast<Instruction>(OpV))78 if (isInstructionTriviallyDead(OpI, TLI))79 WorkList.insert(OpI);80 }81 82 I->eraseFromParent();83 ++DCEEliminated;84 return true;85 }86 return false;87}88 89static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI) {90 bool MadeChange = false;91 SmallSetVector<Instruction *, 16> WorkList;92 // Iterate over the original function, only adding insts to the worklist93 // if they actually need to be revisited. This avoids having to pre-init94 // the worklist with the entire function's worth of instructions.95 for (Instruction &I : llvm::make_early_inc_range(instructions(F))) {96 // We're visiting this instruction now, so make sure it's not in the97 // worklist from an earlier visit.98 if (!WorkList.count(&I))99 MadeChange |= DCEInstruction(&I, WorkList, TLI);100 }101 102 while (!WorkList.empty()) {103 Instruction *I = WorkList.pop_back_val();104 MadeChange |= DCEInstruction(I, WorkList, TLI);105 }106 return MadeChange;107}108 109PreservedAnalyses DCEPass::run(Function &F, FunctionAnalysisManager &AM) {110 if (!eliminateDeadCode(F, &AM.getResult<TargetLibraryAnalysis>(F)))111 return PreservedAnalyses::all();112 113 PreservedAnalyses PA;114 PA.preserveSet<CFGAnalyses>();115 return PA;116}117 118namespace {119struct DCELegacyPass : public FunctionPass {120 static char ID; // Pass identification, replacement for typeid121 DCELegacyPass() : FunctionPass(ID) {122 initializeDCELegacyPassPass(*PassRegistry::getPassRegistry());123 }124 125 bool runOnFunction(Function &F) override {126 if (skipFunction(F))127 return false;128 129 TargetLibraryInfo *TLI =130 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);131 132 return eliminateDeadCode(F, TLI);133 }134 135 void getAnalysisUsage(AnalysisUsage &AU) const override {136 AU.addRequired<TargetLibraryInfoWrapperPass>();137 AU.setPreservesCFG();138 }139};140}141 142char DCELegacyPass::ID = 0;143INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)144 145FunctionPass *llvm::createDeadCodeEliminationPass() {146 return new DCELegacyPass();147}148