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/InitializePasses.h"
27 #include "llvm/Pass.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include "llvm/Transforms/Scalar.h"
31 #include "llvm/Transforms/Utils/Local.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.
clearAssumptionsOfUsers(Instruction * I,DemandedBits & DB)44 static void clearAssumptionsOfUsers(Instruction *I, DemandedBits &DB) {
45 assert(I->getType()->isIntOrIntVectorTy() &&
46 "Trivializing a non-integer value?");
47
48 // Initialize the worklist with eligible direct users.
49 SmallPtrSet<Instruction *, 16> Visited;
50 SmallVector<Instruction *, 16> WorkList;
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).isAllOnesValue()) {
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.
76 J->dropPoisonGeneratingFlags();
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() &&
87 !DB.getDemandedBits(K).isAllOnesValue())
88 WorkList.push_back(K);
89 }
90 }
91 }
92
bitTrackingDCE(Function & F,DemandedBits & DB)93 static bool bitTrackingDCE(Function &F, DemandedBits &DB) {
94 SmallVector<Instruction*, 128> Worklist;
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() &&
108 wouldInstructionBeTriviallyDead(&I))) {
109 salvageDebugInfo(I);
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
147 clearAssumptionsOfUsers(&I, DB);
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
run(Function & F,FunctionAnalysisManager & AM)166 PreservedAnalyses BDCEPass::run(Function &F, FunctionAnalysisManager &AM) {
167 auto &DB = AM.getResult<DemandedBitsAnalysis>(F);
168 if (!bitTrackingDCE(F, DB))
169 return PreservedAnalyses::all();
170
171 PreservedAnalyses PA;
172 PA.preserveSet<CFGAnalyses>();
173 PA.preserve<GlobalsAA>();
174 return PA;
175 }
176
177 namespace {
178 struct BDCELegacyPass : public FunctionPass {
179 static char ID; // Pass identification, replacement for typeid
BDCELegacyPass__anon3ecfb5790111::BDCELegacyPass180 BDCELegacyPass() : FunctionPass(ID) {
181 initializeBDCELegacyPassPass(*PassRegistry::getPassRegistry());
182 }
183
runOnFunction__anon3ecfb5790111::BDCELegacyPass184 bool runOnFunction(Function &F) override {
185 if (skipFunction(F))
186 return false;
187 auto &DB = getAnalysis<DemandedBitsWrapperPass>().getDemandedBits();
188 return bitTrackingDCE(F, DB);
189 }
190
getAnalysisUsage__anon3ecfb5790111::BDCELegacyPass191 void getAnalysisUsage(AnalysisUsage &AU) const override {
192 AU.setPreservesCFG();
193 AU.addRequired<DemandedBitsWrapperPass>();
194 AU.addPreserved<GlobalsAAWrapperPass>();
195 }
196 };
197 }
198
199 char BDCELegacyPass::ID = 0;
200 INITIALIZE_PASS_BEGIN(BDCELegacyPass, "bdce",
201 "Bit-Tracking Dead Code Elimination", false, false)
INITIALIZE_PASS_DEPENDENCY(DemandedBitsWrapperPass)202 INITIALIZE_PASS_DEPENDENCY(DemandedBitsWrapperPass)
203 INITIALIZE_PASS_END(BDCELegacyPass, "bdce",
204 "Bit-Tracking Dead Code Elimination", false, false)
205
206 FunctionPass *llvm::createBitTrackingDCEPass() { return new BDCELegacyPass(); }
207