LLVM 18.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"
26#include "llvm/Support/Debug.h"
29using namespace llvm;
31#define DEBUG_TYPE "bdce"
33STATISTIC(NumRemoved, "Number of instructions removed (unused)");
34STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
36 "Number of sign extension instructions converted to zero extension");
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.
42 assert(I->getType()->isIntOrIntVectorTy() &&
43 "Trivializing a non-integer value?");
45 // Initialize the worklist with eligible direct users.
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 }
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 }
68 // DFS through subsequent users while tracking visits to avoid cycles.
69 while (!WorkList.empty()) {
70 Instruction *J = WorkList.pop_back_val();
72 // NSW, NUW, and exact are based on operands that might have changed.
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.
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 }
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;
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() &&
105 Worklist.push_back(&I);
106 Changed = true;
107 continue;
108 }
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)) {
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 }
128 for (Use &U : I.operands()) {
129 // DemandedBits only detects dead integer uses.
130 if (!U->getType()->isIntOrIntVectorTy())
131 continue;
133 if (!isa<Instruction>(U) && !isa<Argument>(U))
134 continue;
136 if (!DB.isUseDead(&U))
137 continue;
139 LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << U << " (all bits dead)\n");
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 }
151 for (Instruction *&I : llvm::reverse(Worklist)) {
153 I->dropAllReferences();
154 }
156 for (Instruction *&I : Worklist) {
157 ++NumRemoved;
158 I->eraseFromParent();
159 }
161 return Changed;
165 auto &DB = AM.getResult<DemandedBitsAnalysis>(F);
166 if (!bitTrackingDCE(F, DB))
167 return PreservedAnalyses::all();
171 return PA;
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:41
static bool bitTrackingDCE(Function &F, DemandedBits &DB)
Definition: BDCE.cpp:90
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This is the interface for a simple mod/ref and alias analysis over globals.
Select target instructions out of generic instructions
#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:76
unsigned countl_zero() const
The APInt version of std::countl_zero.
Definition: APInt.h:1542
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
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:102
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2628
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
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:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
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
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:1394
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:429
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:417
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: BDCE.cpp:164