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