LLVM 17.0.0git
Go to the documentation of this file.
1//===---- BDCE.cpp - Bit-tracking dead code elimination -------------------===//
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
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.
20#include "llvm/ADT/Statistic.h"
23#include "llvm/IR/IRBuilder.h"
27#include "llvm/Pass.h"
28#include "llvm/Support/Debug.h"
32using namespace llvm;
34#define DEBUG_TYPE "bdce"
36STATISTIC(NumRemoved, "Number of instructions removed (unused)");
37STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
39 "Number of sign extension instructions converted to zero extension");
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?");
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() &&
56 !DB.getDemandedBits(J).isAllOnes()) {
57 Visited.insert(J);
58 WorkList.push_back(J);
59 }
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 }
71 // DFS through subsequent users while tracking visits to avoid cycles.
72 while (!WorkList.empty()) {
73 Instruction *J = WorkList.pop_back_val();
75 // NSW, NUW, and exact are based on operands that might have changed.
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.
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).isAllOnes())
88 WorkList.push_back(K);
89 }
90 }
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;
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() && DB.getDemandedBits(&I).isZero() &&
108 Worklist.push_back(&I);
109 Changed = true;
110 continue;
111 }
113 // Convert SExt into ZExt if none of the extension bits is required
114 if (SExtInst *SE = dyn_cast<SExtInst>(&I)) {
115 APInt Demanded = DB.getDemandedBits(SE);
116 const uint32_t SrcBitSize = SE->getSrcTy()->getScalarSizeInBits();
117 auto *const DstTy = SE->getDestTy();
118 const uint32_t DestBitSize = DstTy->getScalarSizeInBits();
119 if (Demanded.countl_zero() >= (DestBitSize - SrcBitSize)) {
122 I.replaceAllUsesWith(
123 Builder.CreateZExt(SE->getOperand(0), DstTy, SE->getName()));
124 Worklist.push_back(SE);
125 Changed = true;
126 NumSExt2ZExt++;
127 continue;
128 }
129 }
131 for (Use &U : I.operands()) {
132 // DemandedBits only detects dead integer uses.
133 if (!U->getType()->isIntOrIntVectorTy())
134 continue;
136 if (!isa<Instruction>(U) && !isa<Argument>(U))
137 continue;
139 if (!DB.isUseDead(&U))
140 continue;
142 LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << U << " (all bits dead)\n");
146 // Substitute all uses with zero. In theory we could use `freeze poison`
147 // instead, but that seems unlikely to be profitable.
148 U.set(ConstantInt::get(U->getType(), 0));
149 ++NumSimplified;
150 Changed = true;
151 }
152 }
154 for (Instruction *&I : llvm::reverse(Worklist)) {
156 I->dropAllReferences();
157 }
159 for (Instruction *&I : Worklist) {
160 ++NumRemoved;
161 I->eraseFromParent();
162 }
164 return Changed;
168 auto &DB = AM.getResult<DemandedBitsAnalysis>(F);
169 if (!bitTrackingDCE(F, DB))
170 return PreservedAnalyses::all();
174 return PA;
177namespace {
178struct BDCELegacyPass : public FunctionPass {
179 static char ID; // Pass identification, replacement for typeid
180 BDCELegacyPass() : FunctionPass(ID) {
182 }
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 }
191 void getAnalysisUsage(AnalysisUsage &AU) const override {
192 AU.setPreservesCFG();
195 }
199char BDCELegacyPass::ID = 0;
201 "Bit-Tracking Dead Code Elimination", false, false)
203INITIALIZE_PASS_END(BDCELegacyPass, "bdce",
204 "Bit-Tracking Dead Code Elimination", false, false)
206FunctionPass *llvm::createBitTrackingDCEPass() { return new BDCELegacyPass(); }
assume Assume Builder
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
Definition: BDCE.cpp:203
static bool bitTrackingDCE(Function &F, DemandedBits &DB)
Definition: BDCE.cpp:93
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static bool runOnFunction(Function &F, bool PostInlining)
This is the interface for a simple mod/ref and alias analysis over globals.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Machine Common Subexpression Elimination
Definition: MachineCSE.cpp:169
print must be executed print the must be executed context for all instructions
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
Definition: Statistic.h:167
Class for arbitrary precision integers.
Definition: APInt.h:75
unsigned countl_zero() const
The APInt version of std::countl_zero.
Definition: APInt.h:1551
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
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:888
An analysis that produces DemandedBits for a function.
Definition: DemandedBits.h:123
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
Legacy wrapper pass to provide the GlobalsAAResult object.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2558
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
This class represents a sign extension of integer types.
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:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
iterator_range< user_iterator > users()
Definition: Value.h:421
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
FunctionPass * createBitTrackingDCEPass()
Definition: BDCE.cpp:206
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition: Utils.cpp:1367
void initializeBDCELegacyPassPass(PassRegistry &)
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:417
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:511
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: BDCE.cpp:167