LLVM  14.0.0git
BDCE.cpp
Go to the documentation of this file.
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 
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/Statistic.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"
30 #include "llvm/Transforms/Scalar.h"
32 using namespace llvm;
33 
34 #define DEBUG_TYPE "bdce"
35 
36 STATISTIC(NumRemoved, "Number of instructions removed (unused)");
37 STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
38 STATISTIC(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.
45  assert(I->getType()->isIntOrIntVectorTy() &&
46  "Trivializing a non-integer value?");
47 
48  // Initialize the worklist with eligible direct users.
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() &&
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.
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() &&
88  WorkList.push_back(K);
89  }
90  }
91 }
92 
93 static bool bitTrackingDCE(Function &F, DemandedBits &DB) {
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() &&
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 
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 
167  auto &DB = AM.getResult<DemandedBitsAnalysis>(F);
168  if (!bitTrackingDCE(F, DB))
169  return PreservedAnalyses::all();
170 
172  PA.preserveSet<CFGAnalyses>();
173  return PA;
174 }
175 
176 namespace {
177 struct BDCELegacyPass : public FunctionPass {
178  static char ID; // Pass identification, replacement for typeid
179  BDCELegacyPass() : FunctionPass(ID) {
181  }
182 
183  bool runOnFunction(Function &F) override {
184  if (skipFunction(F))
185  return false;
186  auto &DB = getAnalysis<DemandedBitsWrapperPass>().getDemandedBits();
187  return bitTrackingDCE(F, DB);
188  }
189 
190  void getAnalysisUsage(AnalysisUsage &AU) const override {
191  AU.setPreservesCFG();
194  }
195 };
196 }
197 
198 char BDCELegacyPass::ID = 0;
199 INITIALIZE_PASS_BEGIN(BDCELegacyPass, "bdce",
200  "Bit-Tracking Dead Code Elimination", false, false)
202 INITIALIZE_PASS_END(BDCELegacyPass, "bdce",
203  "Bit-Tracking Dead Code Elimination", false, false)
204 
205 FunctionPass *llvm::createBitTrackingDCEPass() { return new BDCELegacyPass(); }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
Scalar.h
InstIterator.h
llvm::Function
Definition: Function.h:61
Pass.h
llvm::BDCEPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: BDCE.cpp:166
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::IRBuilder<>
Elimination
Bit Tracking Dead Code Elimination
Definition: BDCE.cpp:203
Local.h
GlobalsModRef.h
llvm::DemandedBitsAnalysis
An analysis that produces DemandedBits for a function.
Definition: DemandedBits.h:123
bdce
bdce
Definition: BDCE.cpp:202
llvm::SmallPtrSet< Instruction *, 16 >
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
clearAssumptionsOfUsers
static void clearAssumptionsOfUsers(Instruction *I, DemandedBits &DB)
If an instruction is trivialized (dead), then the chain of users of that instruction may need to be c...
Definition: BDCE.cpp:44
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(BDCELegacyPass, "bdce", "Bit-Tracking Dead Code Elimination", false, false) INITIALIZE_PASS_END(BDCELegacyPass
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::User
Definition: User.h:44
llvm::RegState::Dead
@ Dead
Unused definition.
Definition: MachineInstrBuilder.h:50
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:142
llvm::Instruction
Definition: Instruction.h:45
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:899
SmallPtrSet.h
llvm::APInt::isAllOnesValue
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:401
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::wouldInstructionBeTriviallyDead
bool wouldInstructionBeTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction would have no side effects if it was not used.
Definition: Local.cpp:405
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::DemandedBits
Definition: DemandedBits.h:40
I
#define I(x, y, z)
Definition: MD5.cpp:59
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::initializeBDCELegacyPassPass
void initializeBDCELegacyPassPass(PassRegistry &)
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
uint32_t
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4797
DemandedBits.h
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::APInt::countLeadingZeros
unsigned countLeadingZeros() const
The APInt version of the countLeadingZeros functions in MathExtras.h.
Definition: APInt.h:1664
llvm::DemandedBits::isInstructionDead
bool isInstructionDead(Instruction *I)
Return true if, during analysis, I could not be reached.
Definition: DemandedBits.cpp:482
llvm::DemandedBitsWrapperPass
Definition: DemandedBits.h:102
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::createBitTrackingDCEPass
FunctionPass * createBitTrackingDCEPass()
Definition: BDCE.cpp:205
llvm::salvageDebugInfo
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Definition: Local.cpp:1728
bitTrackingDCE
static bool bitTrackingDCE(Function &F, DemandedBits &DB)
Definition: BDCE.cpp:93
llvm::DemandedBits::getDemandedBits
APInt getDemandedBits(Instruction *I)
Return the bits demanded from instruction I.
Definition: DemandedBits.cpp:443
llvm::APInt::isNullValue
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:411
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
SmallVector.h
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
llvm::tgtok::Bit
@ Bit
Definition: TGLexer.h:50
llvm::DemandedBits::isUseDead
bool isUseDead(Use *U)
Return whether this use is dead by means of not having any demanded bits.
Definition: DemandedBits.cpp:489
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BDCE.h
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
raw_ostream.h
InitializePasses.h
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::Instruction::dropPoisonGeneratingFlags
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
Definition: Instruction.cpp:144
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38