Hal Finkel | 2bb61ba | 2015-02-17 01:36:59 +0000 | [diff] [blame] | 1 | //===---- BDCE.cpp - Bit-tracking dead code elimination -------------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements the Bit-Tracking Dead Code Elimination pass. Some |
| 11 | // instructions (shifts, some ands, ors, etc.) kill some of their input bits. |
| 12 | // We track these dead bits and remove instructions that compute only these |
| 13 | // dead bits. |
| 14 | // |
| 15 | //===----------------------------------------------------------------------===// |
| 16 | |
Davide Italiano | 655a145 | 2016-05-25 01:57:04 +0000 | [diff] [blame] | 17 | #include "llvm/Transforms/Scalar/BDCE.h" |
Sanjay Patel | fe346f9 | 2017-08-12 16:41:08 +0000 | [diff] [blame] | 18 | #include "llvm/ADT/SmallPtrSet.h" |
Hal Finkel | 2bb61ba | 2015-02-17 01:36:59 +0000 | [diff] [blame] | 19 | #include "llvm/ADT/SmallVector.h" |
| 20 | #include "llvm/ADT/Statistic.h" |
James Molloy | 87405c7 | 2015-08-14 11:09:09 +0000 | [diff] [blame] | 21 | #include "llvm/Analysis/DemandedBits.h" |
Davide Italiano | 655a145 | 2016-05-25 01:57:04 +0000 | [diff] [blame] | 22 | #include "llvm/Analysis/GlobalsModRef.h" |
Hal Finkel | 2bb61ba | 2015-02-17 01:36:59 +0000 | [diff] [blame] | 23 | #include "llvm/IR/InstIterator.h" |
| 24 | #include "llvm/IR/Instructions.h" |
Hal Finkel | 2bb61ba | 2015-02-17 01:36:59 +0000 | [diff] [blame] | 25 | #include "llvm/Pass.h" |
| 26 | #include "llvm/Support/Debug.h" |
| 27 | #include "llvm/Support/raw_ostream.h" |
Davide Italiano | 655a145 | 2016-05-25 01:57:04 +0000 | [diff] [blame] | 28 | #include "llvm/Transforms/Scalar.h" |
Hal Finkel | 2bb61ba | 2015-02-17 01:36:59 +0000 | [diff] [blame] | 29 | using namespace llvm; |
| 30 | |
| 31 | #define DEBUG_TYPE "bdce" |
| 32 | |
| 33 | STATISTIC(NumRemoved, "Number of instructions removed (unused)"); |
| 34 | STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)"); |
| 35 | |
Sanjay Patel | fe346f9 | 2017-08-12 16:41:08 +0000 | [diff] [blame] | 36 | /// If an instruction is trivialized (dead), then the chain of users of that |
| 37 | /// instruction may need to be cleared of assumptions that can no longer be |
| 38 | /// guaranteed correct. |
| 39 | static void clearAssumptionsOfUsers(Instruction *I, DemandedBits &DB) { |
Sanjay Patel | a1067d9 | 2017-08-14 15:13:46 +0000 | [diff] [blame] | 40 | assert(I->getType()->isIntegerTy() && "Trivializing a non-integer value?"); |
Sanjay Patel | fe346f9 | 2017-08-12 16:41:08 +0000 | [diff] [blame] | 41 | |
| 42 | // Initialize the worklist with eligible direct users. |
| 43 | SmallVector<Instruction *, 16> WorkList; |
| 44 | for (User *JU : I->users()) { |
Sanjay Patel | a1067d9 | 2017-08-14 15:13:46 +0000 | [diff] [blame] | 45 | // If all bits of a user are demanded, then we know that nothing below that |
| 46 | // in the def-use chain needs to be changed. |
Sanjay Patel | fe346f9 | 2017-08-12 16:41:08 +0000 | [diff] [blame] | 47 | auto *J = dyn_cast<Instruction>(JU); |
Hal Finkel | 9e54b70 | 2017-08-16 16:09:22 +0000 | [diff] [blame] | 48 | if (J && J->getType()->isSized() && |
| 49 | !DB.getDemandedBits(J).isAllOnesValue()) |
Sanjay Patel | fe346f9 | 2017-08-12 16:41:08 +0000 | [diff] [blame] | 50 | WorkList.push_back(J); |
Hal Finkel | 9e54b70 | 2017-08-16 16:09:22 +0000 | [diff] [blame] | 51 | |
| 52 | // Note that we need to check for unsized types above before asking for |
| 53 | // demanded bits. Normally, the only way to reach an instruction with an |
| 54 | // unsized type is via an instruction that has side effects (or otherwise |
| 55 | // will demand its input bits). However, if we have a readnone function |
| 56 | // that returns an unsized type (e.g., void), we must avoid asking for the |
| 57 | // demanded bits of the function call's return value. A void-returning |
| 58 | // readnone function is always dead (and so we can stop walking the use/def |
| 59 | // chain here), but the check is necessary to avoid asserting. |
Sanjay Patel | fe346f9 | 2017-08-12 16:41:08 +0000 | [diff] [blame] | 60 | } |
| 61 | |
| 62 | // DFS through subsequent users while tracking visits to avoid cycles. |
| 63 | SmallPtrSet<Instruction *, 16> Visited; |
| 64 | while (!WorkList.empty()) { |
| 65 | Instruction *J = WorkList.pop_back_val(); |
| 66 | |
| 67 | // NSW, NUW, and exact are based on operands that might have changed. |
| 68 | J->dropPoisonGeneratingFlags(); |
| 69 | |
| 70 | // We do not have to worry about llvm.assume or range metadata: |
| 71 | // 1. llvm.assume demands its operand, so trivializing can't change it. |
| 72 | // 2. range metadata only applies to memory accesses which demand all bits. |
| 73 | |
| 74 | Visited.insert(J); |
| 75 | |
| 76 | for (User *KU : J->users()) { |
Sanjay Patel | a1067d9 | 2017-08-14 15:13:46 +0000 | [diff] [blame] | 77 | // If all bits of a user are demanded, then we know that nothing below |
| 78 | // that in the def-use chain needs to be changed. |
Sanjay Patel | fe346f9 | 2017-08-12 16:41:08 +0000 | [diff] [blame] | 79 | auto *K = dyn_cast<Instruction>(KU); |
Hal Finkel | 9e54b70 | 2017-08-16 16:09:22 +0000 | [diff] [blame] | 80 | if (K && !Visited.count(K) && K->getType()->isSized() && |
| 81 | !DB.getDemandedBits(K).isAllOnesValue()) |
Sanjay Patel | fe346f9 | 2017-08-12 16:41:08 +0000 | [diff] [blame] | 82 | WorkList.push_back(K); |
| 83 | } |
| 84 | } |
| 85 | } |
| 86 | |
Davide Italiano | 655a145 | 2016-05-25 01:57:04 +0000 | [diff] [blame] | 87 | static bool bitTrackingDCE(Function &F, DemandedBits &DB) { |
Hal Finkel | 2bb61ba | 2015-02-17 01:36:59 +0000 | [diff] [blame] | 88 | SmallVector<Instruction*, 128> Worklist; |
Hal Finkel | 2bb61ba | 2015-02-17 01:36:59 +0000 | [diff] [blame] | 89 | bool Changed = false; |
Nico Rieck | 7819951 | 2015-08-06 19:10:45 +0000 | [diff] [blame] | 90 | for (Instruction &I : instructions(F)) { |
Davide Italiano | 043e661 | 2016-12-06 21:52:47 +0000 | [diff] [blame] | 91 | // If the instruction has side effects and no non-dbg uses, |
Davide Italiano | 1ed5396 | 2016-12-07 21:47:32 +0000 | [diff] [blame] | 92 | // skip it. This way we avoid computing known bits on an instruction |
| 93 | // that will not help us. |
Davide Italiano | 043e661 | 2016-12-06 21:52:47 +0000 | [diff] [blame] | 94 | if (I.mayHaveSideEffects() && I.use_empty()) |
| 95 | continue; |
| 96 | |
James Molloy | 87405c7 | 2015-08-14 11:09:09 +0000 | [diff] [blame] | 97 | if (I.getType()->isIntegerTy() && |
| 98 | !DB.getDemandedBits(&I).getBoolValue()) { |
| 99 | // For live instructions that have all dead bits, first make them dead by |
| 100 | // replacing all uses with something else. Then, if they don't need to |
| 101 | // remain live (because they have side effects, etc.) we can remove them. |
| 102 | DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n"); |
Sanjay Patel | fe346f9 | 2017-08-12 16:41:08 +0000 | [diff] [blame] | 103 | |
| 104 | clearAssumptionsOfUsers(&I, DB); |
| 105 | |
James Molloy | 87405c7 | 2015-08-14 11:09:09 +0000 | [diff] [blame] | 106 | // FIXME: In theory we could substitute undef here instead of zero. |
| 107 | // This should be reconsidered once we settle on the semantics of |
| 108 | // undef, poison, etc. |
| 109 | Value *Zero = ConstantInt::get(I.getType(), 0); |
| 110 | ++NumSimplified; |
Davide Italiano | 1ed5396 | 2016-12-07 21:47:32 +0000 | [diff] [blame] | 111 | I.replaceNonMetadataUsesWith(Zero); |
James Molloy | 87405c7 | 2015-08-14 11:09:09 +0000 | [diff] [blame] | 112 | Changed = true; |
Hal Finkel | 2bb61ba | 2015-02-17 01:36:59 +0000 | [diff] [blame] | 113 | } |
James Molloy | 87405c7 | 2015-08-14 11:09:09 +0000 | [diff] [blame] | 114 | if (!DB.isInstructionDead(&I)) |
Hal Finkel | 2bb61ba | 2015-02-17 01:36:59 +0000 | [diff] [blame] | 115 | continue; |
| 116 | |
Hal Finkel | 2bb61ba | 2015-02-17 01:36:59 +0000 | [diff] [blame] | 117 | Worklist.push_back(&I); |
| 118 | I.dropAllReferences(); |
| 119 | Changed = true; |
| 120 | } |
| 121 | |
| 122 | for (Instruction *&I : Worklist) { |
| 123 | ++NumRemoved; |
| 124 | I->eraseFromParent(); |
| 125 | } |
| 126 | |
| 127 | return Changed; |
| 128 | } |
| 129 | |
Davide Italiano | 655a145 | 2016-05-25 01:57:04 +0000 | [diff] [blame] | 130 | PreservedAnalyses BDCEPass::run(Function &F, FunctionAnalysisManager &AM) { |
| 131 | auto &DB = AM.getResult<DemandedBitsAnalysis>(F); |
Davide Italiano | bdc2971 | 2016-05-31 17:53:22 +0000 | [diff] [blame] | 132 | if (!bitTrackingDCE(F, DB)) |
| 133 | return PreservedAnalyses::all(); |
| 134 | |
Chandler Carruth | ca68a3e | 2017-01-15 06:32:49 +0000 | [diff] [blame] | 135 | PreservedAnalyses PA; |
| 136 | PA.preserveSet<CFGAnalyses>(); |
Davide Italiano | bdc2971 | 2016-05-31 17:53:22 +0000 | [diff] [blame] | 137 | PA.preserve<GlobalsAA>(); |
| 138 | return PA; |
Hal Finkel | 2bb61ba | 2015-02-17 01:36:59 +0000 | [diff] [blame] | 139 | } |
| 140 | |
Davide Italiano | 655a145 | 2016-05-25 01:57:04 +0000 | [diff] [blame] | 141 | namespace { |
| 142 | struct BDCELegacyPass : public FunctionPass { |
| 143 | static char ID; // Pass identification, replacement for typeid |
| 144 | BDCELegacyPass() : FunctionPass(ID) { |
| 145 | initializeBDCELegacyPassPass(*PassRegistry::getPassRegistry()); |
| 146 | } |
| 147 | |
| 148 | bool runOnFunction(Function &F) override { |
| 149 | if (skipFunction(F)) |
| 150 | return false; |
| 151 | auto &DB = getAnalysis<DemandedBitsWrapperPass>().getDemandedBits(); |
| 152 | return bitTrackingDCE(F, DB); |
| 153 | } |
| 154 | |
| 155 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
| 156 | AU.setPreservesCFG(); |
| 157 | AU.addRequired<DemandedBitsWrapperPass>(); |
| 158 | AU.addPreserved<GlobalsAAWrapperPass>(); |
| 159 | } |
| 160 | }; |
| 161 | } |
| 162 | |
| 163 | char BDCELegacyPass::ID = 0; |
| 164 | INITIALIZE_PASS_BEGIN(BDCELegacyPass, "bdce", |
| 165 | "Bit-Tracking Dead Code Elimination", false, false) |
| 166 | INITIALIZE_PASS_DEPENDENCY(DemandedBitsWrapperPass) |
| 167 | INITIALIZE_PASS_END(BDCELegacyPass, "bdce", |
| 168 | "Bit-Tracking Dead Code Elimination", false, false) |
| 169 | |
| 170 | FunctionPass *llvm::createBitTrackingDCEPass() { return new BDCELegacyPass(); } |