1 //===---- BDCE.cpp - Bit-tracking dead code elimination -------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the Bit-Tracking Dead Code Elimination pass. Some
11 // instructions (shifts, some ands, ors, etc.) kill some of their input bits.
12 // We track these dead bits and remove instructions that compute only these
15 //===----------------------------------------------------------------------===//
17 #include "llvm/Transforms/Scalar/BDCE.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/Analysis/DemandedBits.h"
22 #include "llvm/Analysis/GlobalsModRef.h"
23 #include "llvm/IR/CFG.h"
24 #include "llvm/IR/InstIterator.h"
25 #include "llvm/IR/Instructions.h"
26 #include "llvm/IR/IntrinsicInst.h"
27 #include "llvm/IR/Operator.h"
28 #include "llvm/Pass.h"
29 #include "llvm/Support/Debug.h"
30 #include "llvm/Support/raw_ostream.h"
31 #include "llvm/Transforms/Scalar.h"
34 #define DEBUG_TYPE "bdce"
36 STATISTIC(NumRemoved, "Number of instructions removed (unused)");
37 STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
39 /// If an instruction is trivialized (dead), then the chain of users of that
40 /// instruction may need to be cleared of assumptions that can no longer be
41 /// guaranteed correct.
42 static void clearAssumptionsOfUsers(Instruction *I, DemandedBits &DB) {
43 assert(I->getType()->isIntegerTy() && "Trivializing a non-integer value?");
45 // Initialize the worklist with eligible direct users.
46 SmallVector<Instruction *, 16> WorkList;
47 for (User *JU : I->users()) {
48 // If all bits of a user are demanded, then we know that nothing below that
49 // in the def-use chain needs to be changed.
50 auto *J = dyn_cast<Instruction>(JU);
51 if (J && !DB.getDemandedBits(J).isAllOnesValue())
52 WorkList.push_back(J);
55 // DFS through subsequent users while tracking visits to avoid cycles.
56 SmallPtrSet<Instruction *, 16> Visited;
57 while (!WorkList.empty()) {
58 Instruction *J = WorkList.pop_back_val();
60 // NSW, NUW, and exact are based on operands that might have changed.
61 J->dropPoisonGeneratingFlags();
63 // We do not have to worry about llvm.assume or range metadata:
64 // 1. llvm.assume demands its operand, so trivializing can't change it.
65 // 2. range metadata only applies to memory accesses which demand all bits.
69 for (User *KU : J->users()) {
70 // If all bits of a user are demanded, then we know that nothing below
71 // that in the def-use chain needs to be changed.
72 auto *K = dyn_cast<Instruction>(KU);
73 if (K && !Visited.count(K) && !DB.getDemandedBits(K).isAllOnesValue())
74 WorkList.push_back(K);
79 static bool bitTrackingDCE(Function &F, DemandedBits &DB) {
80 SmallVector<Instruction*, 128> Worklist;
82 for (Instruction &I : instructions(F)) {
83 // If the instruction has side effects and no non-dbg uses,
84 // skip it. This way we avoid computing known bits on an instruction
85 // that will not help us.
86 if (I.mayHaveSideEffects() && I.use_empty())
89 if (I.getType()->isIntegerTy() &&
90 !DB.getDemandedBits(&I).getBoolValue()) {
91 // For live instructions that have all dead bits, first make them dead by
92 // replacing all uses with something else. Then, if they don't need to
93 // remain live (because they have side effects, etc.) we can remove them.
94 DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n");
96 clearAssumptionsOfUsers(&I, DB);
98 // FIXME: In theory we could substitute undef here instead of zero.
99 // This should be reconsidered once we settle on the semantics of
100 // undef, poison, etc.
101 Value *Zero = ConstantInt::get(I.getType(), 0);
103 I.replaceNonMetadataUsesWith(Zero);
106 if (!DB.isInstructionDead(&I))
109 Worklist.push_back(&I);
110 I.dropAllReferences();
114 for (Instruction *&I : Worklist) {
116 I->eraseFromParent();
122 PreservedAnalyses BDCEPass::run(Function &F, FunctionAnalysisManager &AM) {
123 auto &DB = AM.getResult<DemandedBitsAnalysis>(F);
124 if (!bitTrackingDCE(F, DB))
125 return PreservedAnalyses::all();
127 PreservedAnalyses PA;
128 PA.preserveSet<CFGAnalyses>();
129 PA.preserve<GlobalsAA>();
134 struct BDCELegacyPass : public FunctionPass {
135 static char ID; // Pass identification, replacement for typeid
136 BDCELegacyPass() : FunctionPass(ID) {
137 initializeBDCELegacyPassPass(*PassRegistry::getPassRegistry());
140 bool runOnFunction(Function &F) override {
143 auto &DB = getAnalysis<DemandedBitsWrapperPass>().getDemandedBits();
144 return bitTrackingDCE(F, DB);
147 void getAnalysisUsage(AnalysisUsage &AU) const override {
148 AU.setPreservesCFG();
149 AU.addRequired<DemandedBitsWrapperPass>();
150 AU.addPreserved<GlobalsAAWrapperPass>();
155 char BDCELegacyPass::ID = 0;
156 INITIALIZE_PASS_BEGIN(BDCELegacyPass, "bdce",
157 "Bit-Tracking Dead Code Elimination", false, false)
158 INITIALIZE_PASS_DEPENDENCY(DemandedBitsWrapperPass)
159 INITIALIZE_PASS_END(BDCELegacyPass, "bdce",
160 "Bit-Tracking Dead Code Elimination", false, false)
162 FunctionPass *llvm::createBitTrackingDCEPass() { return new BDCELegacyPass(); }