1 //===---- BDCE.cpp - Bit-tracking dead code elimination -------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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
13 // dead bits.
14 //
15 //===----------------------------------------------------------------------===//
16
17 #include "llvm/Transforms/Scalar.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/GlobalsModRef.h"
21 #include "llvm/Analysis/DemandedBits.h"
22 #include "llvm/IR/CFG.h"
23 #include "llvm/IR/InstIterator.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/IntrinsicInst.h"
26 #include "llvm/IR/Operator.h"
27 #include "llvm/Pass.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/raw_ostream.h"
30 using namespace llvm;
31
32 #define DEBUG_TYPE "bdce"
33
34 STATISTIC(NumRemoved, "Number of instructions removed (unused)");
35 STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
36
37 namespace {
38 struct BDCE : public FunctionPass {
39 static char ID; // Pass identification, replacement for typeid
BDCE__anon6eee12af0111::BDCE40 BDCE() : FunctionPass(ID) {
41 initializeBDCEPass(*PassRegistry::getPassRegistry());
42 }
43
44 bool runOnFunction(Function& F) override;
45
getAnalysisUsage__anon6eee12af0111::BDCE46 void getAnalysisUsage(AnalysisUsage& AU) const override {
47 AU.setPreservesCFG();
48 AU.addRequired<DemandedBits>();
49 AU.addPreserved<GlobalsAAWrapperPass>();
50 }
51 };
52 }
53
54 char BDCE::ID = 0;
55 INITIALIZE_PASS_BEGIN(BDCE, "bdce", "Bit-Tracking Dead Code Elimination",
56 false, false)
INITIALIZE_PASS_DEPENDENCY(DemandedBits)57 INITIALIZE_PASS_DEPENDENCY(DemandedBits)
58 INITIALIZE_PASS_END(BDCE, "bdce", "Bit-Tracking Dead Code Elimination",
59 false, false)
60
61 bool BDCE::runOnFunction(Function& F) {
62 if (skipOptnoneFunction(F))
63 return false;
64 DemandedBits &DB = getAnalysis<DemandedBits>();
65
66 SmallVector<Instruction*, 128> Worklist;
67 bool Changed = false;
68 for (Instruction &I : instructions(F)) {
69 if (I.getType()->isIntegerTy() &&
70 !DB.getDemandedBits(&I).getBoolValue()) {
71 // For live instructions that have all dead bits, first make them dead by
72 // replacing all uses with something else. Then, if they don't need to
73 // remain live (because they have side effects, etc.) we can remove them.
74 DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n");
75 // FIXME: In theory we could substitute undef here instead of zero.
76 // This should be reconsidered once we settle on the semantics of
77 // undef, poison, etc.
78 Value *Zero = ConstantInt::get(I.getType(), 0);
79 ++NumSimplified;
80 I.replaceAllUsesWith(Zero);
81 Changed = true;
82 }
83 if (!DB.isInstructionDead(&I))
84 continue;
85
86 Worklist.push_back(&I);
87 I.dropAllReferences();
88 Changed = true;
89 }
90
91 for (Instruction *&I : Worklist) {
92 ++NumRemoved;
93 I->eraseFromParent();
94 }
95
96 return Changed;
97 }
98
createBitTrackingDCEPass()99 FunctionPass *llvm::createBitTrackingDCEPass() {
100 return new BDCE();
101 }
102
103