LLVM 19.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/Support/Debug.h"
31using namespace llvm;
32using namespace PatternMatch;
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 // If all bits of a user are demanded, then we know that nothing below that
49 // in the def-use chain needs to be changed.
50 if (DB.getDemandedBits(I).isAllOnes())
51 return;
53 // Initialize the worklist with eligible direct users.
56 for (User *JU : I->users()) {
57 auto *J = cast<Instruction>(JU);
58 if (J->getType()->isIntOrIntVectorTy()) {
59 Visited.insert(J);
60 WorkList.push_back(J);
61 }
63 // Note that we need to check for non-int types above before asking for
64 // demanded bits. Normally, the only way to reach an instruction with an
65 // non-int type is via an instruction that has side effects (or otherwise
66 // will demand its input bits). However, if we have a readnone function
67 // that returns an unsized type (e.g., void), we must avoid asking for the
68 // demanded bits of the function call's return value. A void-returning
69 // readnone function is always dead (and so we can stop walking the use/def
70 // chain here), but the check is necessary to avoid asserting.
71 }
73 // DFS through subsequent users while tracking visits to avoid cycles.
74 while (!WorkList.empty()) {
75 Instruction *J = WorkList.pop_back_val();
77 // NSW, NUW, and exact are based on operands that might have changed.
80 // We do not have to worry about llvm.assume, because it demands its
81 // operand, so trivializing can't change it.
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 if (DB.getDemandedBits(J).isAllOnes())
86 continue;
88 for (User *KU : J->users()) {
89 auto *K = cast<Instruction>(KU);
90 if (Visited.insert(K).second && K->getType()->isIntOrIntVectorTy())
91 WorkList.push_back(K);
92 }
93 }
98 bool Changed = false;
99 for (Instruction &I : instructions(F)) {
100 // If the instruction has side effects and no non-dbg uses,
101 // skip it. This way we avoid computing known bits on an instruction
102 // that will not help us.
103 if (I.mayHaveSideEffects() && I.use_empty())
104 continue;
106 // Remove instructions that are dead, either because they were not reached
107 // during analysis or have no demanded bits.
108 if (DB.isInstructionDead(&I) ||
109 (I.getType()->isIntOrIntVectorTy() && DB.getDemandedBits(&I).isZero() &&
111 Worklist.push_back(&I);
112 Changed = true;
113 continue;
114 }
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.countl_zero() >= (DestBitSize - SrcBitSize)) {
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 }
134 // Simplify and, or, xor when their mask does not affect the demanded bits.
135 if (auto *BO = dyn_cast<BinaryOperator>(&I)) {
136 APInt Demanded = DB.getDemandedBits(BO);
137 if (!Demanded.isAllOnes()) {
138 const APInt *Mask;
139 if (match(BO->getOperand(1), m_APInt(Mask))) {
140 bool CanBeSimplified = false;
141 switch (BO->getOpcode()) {
142 case Instruction::Or:
143 case Instruction::Xor:
144 CanBeSimplified = !Demanded.intersects(*Mask);
145 break;
146 case Instruction::And:
147 CanBeSimplified = Demanded.isSubsetOf(*Mask);
148 break;
149 default:
150 // TODO: Handle more cases here.
151 break;
152 }
154 if (CanBeSimplified) {
156 BO->replaceAllUsesWith(BO->getOperand(0));
157 Worklist.push_back(BO);
158 ++NumSimplified;
159 Changed = true;
160 continue;
161 }
162 }
163 }
164 }
166 for (Use &U : I.operands()) {
167 // DemandedBits only detects dead integer uses.
168 if (!U->getType()->isIntOrIntVectorTy())
169 continue;
171 if (!isa<Instruction>(U) && !isa<Argument>(U))
172 continue;
174 if (!DB.isUseDead(&U))
175 continue;
177 LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << U << " (all bits dead)\n");
181 // Substitute all uses with zero. In theory we could use `freeze poison`
182 // instead, but that seems unlikely to be profitable.
183 U.set(ConstantInt::get(U->getType(), 0));
184 ++NumSimplified;
185 Changed = true;
186 }
187 }
189 for (Instruction *&I : llvm::reverse(Worklist)) {
191 I->dropAllReferences();
192 }
194 for (Instruction *&I : Worklist) {
195 ++NumRemoved;
196 I->eraseFromParent();
197 }
199 return Changed;
203 auto &DB = AM.getResult<DemandedBitsAnalysis>(F);
204 if (!bitTrackingDCE(F, DB))
205 return PreservedAnalyses::all();
209 return PA;
Expand Atomic instructions
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
static bool bitTrackingDCE(Function &F, DemandedBits &DB)
Definition: BDCE.cpp:96
#define LLVM_DEBUG(X)
Definition: Debug.h:101
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
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:78
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:351
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
Definition: APInt.h:1229
unsigned countl_zero() const
The APInt version of std::countl_zero.
Definition: APInt.h:1557
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
Definition: APInt.h:1237
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:72
An analysis that produces DemandedBits for a function.
Definition: DemandedBits.h:103
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Definition: IRBuilder.h:2026
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2671
void dropPoisonGeneratingAnnotations()
Drops flags, return attributes and metadata that may generate poison.
Definition: Instruction.h:526
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:146
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:344
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:479
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:299
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:1671
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool wouldInstructionBeTriviallyDead(const 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:419
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: BDCE.cpp:202