1//===---- BDCE.cpp - Bit-tracking 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-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the Bit-Tracking Dead Code Elimination pass. Some
10// instructions (shifts, some ands, ors, etc.) kill some of their input bits.
11// We track these dead bits and remove instructions that compute only these
12// dead bits. We also simplify sext that generates unused extension bits,
13// converting it to a zext.
14//
15//===----------------------------------------------------------------------===//
16
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/IRBuilder.h"
24#include "llvm/IR/InstIterator.h"
25#include "llvm/IR/Instructions.h"
26#include "llvm/InitializePasses.h"
27#include "llvm/Pass.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/raw_ostream.h"
30#include "llvm/Transforms/Scalar.h"
31#include "llvm/Transforms/Utils/Local.h"
32using namespace llvm;
33
34#define DEBUG_TYPE "bdce"
35
36STATISTIC(NumRemoved, "Number of instructions removed (unused)");
37STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
38STATISTIC(NumSExt2ZExt,
39          "Number of sign extension instructions converted to zero extension");
40
41/// If an instruction is trivialized (dead), then the chain of users of that
42/// instruction may need to be cleared of assumptions that can no longer be
43/// guaranteed correct.
44static void clearAssumptionsOfUsers(Instruction *I, DemandedBits &DB) {
45  assert(I->getType()->isIntOrIntVectorTy() &&
46         "Trivializing a non-integer value?");
47
48  // Initialize the worklist with eligible direct users.
49  SmallPtrSet<Instruction *, 16> Visited;
50  SmallVector<Instruction *, 16> WorkList;
51  for (User *JU : I->users()) {
52    // If all bits of a user are demanded, then we know that nothing below that
53    // in the def-use chain needs to be changed.
54    auto *J = dyn_cast<Instruction>(JU);
55    if (J && J->getType()->isIntOrIntVectorTy() &&
56        !DB.getDemandedBits(J).isAllOnesValue()) {
57      Visited.insert(J);
58      WorkList.push_back(J);
59    }
60
61    // Note that we need to check for non-int types above before asking for
62    // demanded bits. Normally, the only way to reach an instruction with an
63    // non-int type is via an instruction that has side effects (or otherwise
64    // will demand its input bits). However, if we have a readnone function
65    // that returns an unsized type (e.g., void), we must avoid asking for the
66    // demanded bits of the function call's return value. A void-returning
67    // readnone function is always dead (and so we can stop walking the use/def
68    // chain here), but the check is necessary to avoid asserting.
69  }
70
71  // DFS through subsequent users while tracking visits to avoid cycles.
72  while (!WorkList.empty()) {
73    Instruction *J = WorkList.pop_back_val();
74
75    // NSW, NUW, and exact are based on operands that might have changed.
76    J->dropPoisonGeneratingFlags();
77
78    // We do not have to worry about llvm.assume or range metadata:
79    // 1. llvm.assume demands its operand, so trivializing can't change it.
80    // 2. range metadata only applies to memory accesses which demand all bits.
81
82    for (User *KU : J->users()) {
83      // If all bits of a user are demanded, then we know that nothing below
84      // that in the def-use chain needs to be changed.
85      auto *K = dyn_cast<Instruction>(KU);
86      if (K && Visited.insert(K).second && K->getType()->isIntOrIntVectorTy() &&
87          !DB.getDemandedBits(K).isAllOnesValue())
88        WorkList.push_back(K);
89    }
90  }
91}
92
93static bool bitTrackingDCE(Function &F, DemandedBits &DB) {
94  SmallVector<Instruction*, 128> Worklist;
95  bool Changed = false;
96  for (Instruction &I : instructions(F)) {
97    // If the instruction has side effects and no non-dbg uses,
98    // skip it. This way we avoid computing known bits on an instruction
99    // that will not help us.
100    if (I.mayHaveSideEffects() && I.use_empty())
101      continue;
102
103    // Remove instructions that are dead, either because they were not reached
104    // during analysis or have no demanded bits.
105    if (DB.isInstructionDead(&I) ||
106        (I.getType()->isIntOrIntVectorTy() &&
107         DB.getDemandedBits(&I).isNullValue() &&
108         wouldInstructionBeTriviallyDead(&I))) {
109      salvageDebugInfo(I);
110      Worklist.push_back(&I);
111      I.dropAllReferences();
112      Changed = true;
113      continue;
114    }
115
116    // Convert SExt into ZExt if none of the extension bits is required
117    if (SExtInst *SE = dyn_cast<SExtInst>(&I)) {
118      APInt Demanded = DB.getDemandedBits(SE);
119      const uint32_t SrcBitSize = SE->getSrcTy()->getScalarSizeInBits();
120      auto *const DstTy = SE->getDestTy();
121      const uint32_t DestBitSize = DstTy->getScalarSizeInBits();
122      if (Demanded.countLeadingZeros() >= (DestBitSize - SrcBitSize)) {
123        clearAssumptionsOfUsers(SE, DB);
124        IRBuilder<> Builder(SE);
125        I.replaceAllUsesWith(
126            Builder.CreateZExt(SE->getOperand(0), DstTy, SE->getName()));
127        Worklist.push_back(SE);
128        Changed = true;
129        NumSExt2ZExt++;
130        continue;
131      }
132    }
133
134    for (Use &U : I.operands()) {
135      // DemandedBits only detects dead integer uses.
136      if (!U->getType()->isIntOrIntVectorTy())
137        continue;
138
139      if (!isa<Instruction>(U) && !isa<Argument>(U))
140        continue;
141
142      if (!DB.isUseDead(&U))
143        continue;
144
145      LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << U << " (all bits dead)\n");
146
147      clearAssumptionsOfUsers(&I, DB);
148
149      // FIXME: In theory we could substitute undef here instead of zero.
150      // This should be reconsidered once we settle on the semantics of
151      // undef, poison, etc.
152      U.set(ConstantInt::get(U->getType(), 0));
153      ++NumSimplified;
154      Changed = true;
155    }
156  }
157
158  for (Instruction *&I : Worklist) {
159    ++NumRemoved;
160    I->eraseFromParent();
161  }
162
163  return Changed;
164}
165
166PreservedAnalyses BDCEPass::run(Function &F, FunctionAnalysisManager &AM) {
167  auto &DB = AM.getResult<DemandedBitsAnalysis>(F);
168  if (!bitTrackingDCE(F, DB))
169    return PreservedAnalyses::all();
170
171  PreservedAnalyses PA;
172  PA.preserveSet<CFGAnalyses>();
173  PA.preserve<GlobalsAA>();
174  return PA;
175}
176
177namespace {
178struct BDCELegacyPass : public FunctionPass {
179  static char ID; // Pass identification, replacement for typeid
180  BDCELegacyPass() : FunctionPass(ID) {
181    initializeBDCELegacyPassPass(*PassRegistry::getPassRegistry());
182  }
183
184  bool runOnFunction(Function &F) override {
185    if (skipFunction(F))
186      return false;
187    auto &DB = getAnalysis<DemandedBitsWrapperPass>().getDemandedBits();
188    return bitTrackingDCE(F, DB);
189  }
190
191  void getAnalysisUsage(AnalysisUsage &AU) const override {
192    AU.setPreservesCFG();
193    AU.addRequired<DemandedBitsWrapperPass>();
194    AU.addPreserved<GlobalsAAWrapperPass>();
195  }
196};
197}
198
199char BDCELegacyPass::ID = 0;
200INITIALIZE_PASS_BEGIN(BDCELegacyPass, "bdce",
201                      "Bit-Tracking Dead Code Elimination", false, false)
202INITIALIZE_PASS_DEPENDENCY(DemandedBitsWrapperPass)
203INITIALIZE_PASS_END(BDCELegacyPass, "bdce",
204                    "Bit-Tracking Dead Code Elimination", false, false)
205
206FunctionPass *llvm::createBitTrackingDCEPass() { return new BDCELegacyPass(); }
207