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/Support/Debug.h"
27#include "llvm/Support/raw_ostream.h"
28#include "llvm/Transforms/Utils/Local.h"
29using namespace llvm;
30
31#define DEBUG_TYPE "bdce"
32
33STATISTIC(NumRemoved, "Number of instructions removed (unused)");
34STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
35STATISTIC(NumSExt2ZExt,
36          "Number of sign extension instructions converted to zero extension");
37
38/// If an instruction is trivialized (dead), then the chain of users of that
39/// instruction may need to be cleared of assumptions that can no longer be
40/// guaranteed correct.
41static void clearAssumptionsOfUsers(Instruction *I, DemandedBits &DB) {
42  assert(I->getType()->isIntOrIntVectorTy() &&
43         "Trivializing a non-integer value?");
44
45  // Initialize the worklist with eligible direct users.
46  SmallPtrSet<Instruction *, 16> Visited;
47  SmallVector<Instruction *, 16> WorkList;
48  for (User *JU : I->users()) {
49    // If all bits of a user are demanded, then we know that nothing below that
50    // in the def-use chain needs to be changed.
51    auto *J = dyn_cast<Instruction>(JU);
52    if (J && J->getType()->isIntOrIntVectorTy() &&
53        !DB.getDemandedBits(J).isAllOnes()) {
54      Visited.insert(J);
55      WorkList.push_back(J);
56    }
57
58    // Note that we need to check for non-int types above before asking for
59    // demanded bits. Normally, the only way to reach an instruction with an
60    // non-int type is via an instruction that has side effects (or otherwise
61    // will demand its input bits). However, if we have a readnone function
62    // that returns an unsized type (e.g., void), we must avoid asking for the
63    // demanded bits of the function call's return value. A void-returning
64    // readnone function is always dead (and so we can stop walking the use/def
65    // chain here), but the check is necessary to avoid asserting.
66  }
67
68  // DFS through subsequent users while tracking visits to avoid cycles.
69  while (!WorkList.empty()) {
70    Instruction *J = WorkList.pop_back_val();
71
72    // NSW, NUW, and exact are based on operands that might have changed.
73    J->dropPoisonGeneratingFlags();
74
75    // We do not have to worry about llvm.assume or range metadata:
76    // 1. llvm.assume demands its operand, so trivializing can't change it.
77    // 2. range metadata only applies to memory accesses which demand all bits.
78
79    for (User *KU : J->users()) {
80      // If all bits of a user are demanded, then we know that nothing below
81      // that in the def-use chain needs to be changed.
82      auto *K = dyn_cast<Instruction>(KU);
83      if (K && Visited.insert(K).second && K->getType()->isIntOrIntVectorTy() &&
84          !DB.getDemandedBits(K).isAllOnes())
85        WorkList.push_back(K);
86    }
87  }
88}
89
90static bool bitTrackingDCE(Function &F, DemandedBits &DB) {
91  SmallVector<Instruction*, 128> Worklist;
92  bool Changed = false;
93  for (Instruction &I : instructions(F)) {
94    // If the instruction has side effects and no non-dbg uses,
95    // skip it. This way we avoid computing known bits on an instruction
96    // that will not help us.
97    if (I.mayHaveSideEffects() && I.use_empty())
98      continue;
99
100    // Remove instructions that are dead, either because they were not reached
101    // during analysis or have no demanded bits.
102    if (DB.isInstructionDead(&I) ||
103        (I.getType()->isIntOrIntVectorTy() && DB.getDemandedBits(&I).isZero() &&
104         wouldInstructionBeTriviallyDead(&I))) {
105      Worklist.push_back(&I);
106      Changed = true;
107      continue;
108    }
109
110    // Convert SExt into ZExt if none of the extension bits is required
111    if (SExtInst *SE = dyn_cast<SExtInst>(&I)) {
112      APInt Demanded = DB.getDemandedBits(SE);
113      const uint32_t SrcBitSize = SE->getSrcTy()->getScalarSizeInBits();
114      auto *const DstTy = SE->getDestTy();
115      const uint32_t DestBitSize = DstTy->getScalarSizeInBits();
116      if (Demanded.countl_zero() >= (DestBitSize - SrcBitSize)) {
117        clearAssumptionsOfUsers(SE, DB);
118        IRBuilder<> Builder(SE);
119        I.replaceAllUsesWith(
120            Builder.CreateZExt(SE->getOperand(0), DstTy, SE->getName()));
121        Worklist.push_back(SE);
122        Changed = true;
123        NumSExt2ZExt++;
124        continue;
125      }
126    }
127
128    for (Use &U : I.operands()) {
129      // DemandedBits only detects dead integer uses.
130      if (!U->getType()->isIntOrIntVectorTy())
131        continue;
132
133      if (!isa<Instruction>(U) && !isa<Argument>(U))
134        continue;
135
136      if (!DB.isUseDead(&U))
137        continue;
138
139      LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << U << " (all bits dead)\n");
140
141      clearAssumptionsOfUsers(&I, DB);
142
143      // Substitute all uses with zero. In theory we could use `freeze poison`
144      // instead, but that seems unlikely to be profitable.
145      U.set(ConstantInt::get(U->getType(), 0));
146      ++NumSimplified;
147      Changed = true;
148    }
149  }
150
151  for (Instruction *&I : llvm::reverse(Worklist)) {
152    salvageDebugInfo(*I);
153    I->dropAllReferences();
154  }
155
156  for (Instruction *&I : Worklist) {
157    ++NumRemoved;
158    I->eraseFromParent();
159  }
160
161  return Changed;
162}
163
164PreservedAnalyses BDCEPass::run(Function &F, FunctionAnalysisManager &AM) {
165  auto &DB = AM.getResult<DemandedBitsAnalysis>(F);
166  if (!bitTrackingDCE(F, DB))
167    return PreservedAnalyses::all();
168
169  PreservedAnalyses PA;
170  PA.preserveSet<CFGAnalyses>();
171  return PA;
172}
173