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"
30using namespace llvm;
31
32#define DEBUG_TYPE "bdce"
33
34STATISTIC(NumRemoved, "Number of instructions removed (unused)");
35STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
36
37namespace {
38struct BDCE : public FunctionPass {
39  static char ID; // Pass identification, replacement for typeid
40  BDCE() : FunctionPass(ID) {
41    initializeBDCEPass(*PassRegistry::getPassRegistry());
42  }
43
44  bool runOnFunction(Function& F) override;
45
46  void getAnalysisUsage(AnalysisUsage& AU) const override {
47    AU.setPreservesCFG();
48    AU.addRequired<DemandedBits>();
49    AU.addPreserved<GlobalsAAWrapperPass>();
50  }
51};
52}
53
54char BDCE::ID = 0;
55INITIALIZE_PASS_BEGIN(BDCE, "bdce", "Bit-Tracking Dead Code Elimination",
56                      false, false)
57INITIALIZE_PASS_DEPENDENCY(DemandedBits)
58INITIALIZE_PASS_END(BDCE, "bdce", "Bit-Tracking Dead Code Elimination",
59                    false, false)
60
61bool 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
99FunctionPass *llvm::createBitTrackingDCEPass() {
100  return new BDCE();
101}
102
103